A straightforward idea is to repeat every bit of the message some prearranged number of times, for example, three times, as shown in figure 1.4.
Figure: The repetition code `R3'.
Let us imagine what happens if
we transmit the source message 
over a binary
symmetric channel with noise level f=0.1 using this repetition code.
We can describe the channel as adding a sparse noise vector 
to the
transmitted vector (in modulo 2 arithmetic, i.e., the binary algebra in which
1+1=0).
How do we decode this received vector?
Clearly, the optimal algorithm looks at the received
bits three at a time and takes
a majority vote.
The majority vote decoder is shown in figure 1.5.
If all bits are 
, we decode the triplet
as a .
If, as in the second triplet, there are two 0s and one 1, we decode
the triplet as a -- which in this case corrects the error.
Figure: Decoding algorithm for R3.
Figure: Transmitting 10000 source bits over a binary symmetric channel
with f=0.1 using a repetition code. The probability
of decoded bit error has fallen to about 3%; the rate has fallen
to 1/3. [Dilbert image Copyright©1997 United Feature Syndicate, Inc.,
used with permission.]
Not all errors are corrected, however. If we are unlucky and
two errors fall in a single block, as in the fifth triplet,
then the decoding rule gets the wrong answer.
Thus the error probability is reduced by the use of this code.
It is easy to compute the error probability.
Compute the error probability of R3 for a binary symmetric channel with noise level f.
Clearly the error probability is dominated by the probability of two
bits in a block of three being flipped, which scales as 
. In the
case of our binary symmetric channel with f=0.1, the R3 code has a
probability of error, after decoding, of 
per bit.
Figure 1.6 shows the
result of transmitting a binary
image over a binary symmetric channel
using the repetition code.
The repetition code R3 has therefore improved our probability of
error, as desired. At the same time, we have lost something: our
rate of information transfer has reduced by a factor of
three. So if we use a repetition code to communicate over a telephone
line, it will reduce the error rate, but it will also reduce our
communication rate. We will have to pay three times as much for each
phone call.
As for our disc drive, we will need three noisy gigabyte disc drives
in order to create a single gigabyte disc drive with .
Can we
push the error probability lower to the sort
of values required from a quality disk drive (
)?
Well, we can achieve lower error probabilities by using repetition
codes with more repetitions.
Show that it takes a repetition
code with rate about 1/60 to get the probability of error
down to .
This means that to build a single
gigabyte disk drive
with the required reliability from noisy gigabyte drives with f=0.1,
we would need sixty of the noisy disk drives.
The tradeoff between error probability and rate for repetition
codes is shown in figure 1.7.
Figure: Error probability 
versus rate for repetition codes
over a binary symmetric channel with f=0.1.
The right hand figure shows on a logarithmic scale. We would like
the rate to be large and 
to be small.