Mathematics 392 – Seminar in Coding Theory The Benefits of Coding January 21, 2002

Consider a binary symmetric channel with probability p = .9999 (this is the probability that any single bit is transmitted correctly), assume that bit errors are independent, and assume that the channel can transmit 10^{6} bits per second. We consider messages consisting of blocks of 3 bits, and the following three coding methods:

• (A) no coding (the message blocks are transmitted as is). This method does not make it possible to detect or correct any errors.

• (B) encode each 3 bit message block to a 4 bit codeword by adding a single check bit. This method makes it possible to detect that an odd number of errors have occurred, but not to correct them. If errors are detected, we would probably ask the sender to retransmit that word.

• (C) encode each 3 bit message block to a 6 bit codeword by adding 3 bits as follows abc ↦ abc(a+b)(a+c)(b+c). This method ensures that if 1 error occurs in a codeword, then the received word is still “closer” to the codeword sent than to any other word, so the error can be corrected. Similarly, any two errors can occur without changing the codeword to another codeword so two errors can be detected. We assume that there is a decoder available to perform decoding in this case and recover the correct codeword if a single error occurs in transmission.

The following table gives the number of words per second that can be transmitted, the probability of correct transmission (including applying the decoder with method C), and the probability of an undetected error:

Method words/sec  prob. correct  prob. error undetected
A  \frac{10^{6}}{3} ≐ 333333  p^{3} ≐ .9997  1 − p^{3} ≐ .0003
≐ 100 words/sec
B  \frac{10^{6}}{4} = 250000  p^{4} ≐ .9996  \binom{4}{2}p^{2}(1 − p)^{2} + \binom{4}{4}(1 − p)^{4}
≐ .00000012
≐ 1 word each 33 sec
C  \frac{10^{6}}{6} ≐ 166667 ≥ p^{6} + \binom{6}{1}p^{5}(1 − p) ≐ .99999985  ≐ \binom{6}{3}p^{3}(1 − p)^{3}
≐ 1 word each 300000 sec