\magnification=\magstep1
\overfullrule=0pt
\centerline{Mathematics 392 -- Seminar in Coding Theory}
\centerline{The Benefits of Coding}
\centerline{\it January 21, 2002}
\bigskip
Consider a binary symmetric channel with probability
$p = .9999$ (this is the probability that any single bit
is transmitted {\it 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:
\bigskip
\item{$\bullet$} (A) no coding (the message blocks are transmitted
as is).  This method does not make it possible to detect or
correct any errors.
\medskip
\item{$\bullet$} (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.
\medskip
\item{$\bullet$} (C) encode each 3 bit message block to a 6 bit
codeword by adding 3 bits as follows $abc \mapsto 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.

\bigskip
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:
$$
\matrix{{\rm Method} & {\rm words/sec} & {\rm prob.\ correct} & {\rm prob.\ error\ undetected}\cr
                     &&&\cr
A & {10^6\over 3} \doteq 333333 & p^3 \doteq .9997 & 1-p^3 \doteq .0003 \cr
  &                             &                        &\doteq {\rm 100\ words/sec}\cr
&&&\cr
B & {10^6\over 4} = 250000 & p^4 \doteq .9996 &  {4\choose 2}p^2(1-p)^2 + {4\choose 4}(1-p)^4\cr
  &      &    & \doteq .00000012 \cr
  &                             &                        &\doteq {\rm 1\ word\ each\ 33\ sec}\cr
&&&\cr
C & {10^6\over 6} \doteq 166667 & \ge p^6 + {6\choose 1}p^5(1-p) \doteq .99999985 & \doteq {6\choose 3}p^3(1-p)^3 \cr
  &                             &                        &\doteq {\rm 1\ word\ each\ 300000\ sec}\cr  
}$$
\bye