Explains the repetition code for error correction.
Perhaps the simplest error correcting code is the
repetition code .
Repetition code
The upper portion depicts the result of directly modulating
the bit stream
into a transmitted signal
using a baseband BPSK signal set.
is the datarate produced by the source coder. If that bitstream passes through a (3,1) channel coder to yield the bit
stream
, the resulting transmitted signal requires a bit
interval
three times smaller
than the uncoded version. This reduction in the bit intervalmeans that the transmitted energy/bit decreases by a factor of
three, which results in an increased error probability in thereceiver. Here, the transmitter sends the data bit several times, an odd
number of times in fact. Because the error probability
is always less than
, we know that more of the bits should be correct
rather than in error.Simple majority voting of the received bits (hence the reason
for the odd number) determines the transmitted bit moreaccurately than sending it alone.
For example, let's consider the three-fold repetition code:for every bit
emerging from the source coder, the channel coder
produces three. Thus, the bit stream emerging from the channelcoder
has a data rate three times higher than that of the
original bit stream
.
The coding table illustrates when errors can becorrected and when they can't by the majority-vote decoder.
Coding table
Code
Probability
Bit
000
0
001
0
010
0
011
1
100
0
101
1
110
1
111
1
In this example, the transmitter encodes
as
.
The channel creates an error (changing a
into a
)
that with probability
.
The first column lists all possible received datawords and thesecond the probability of each dataword being received. The
last column shows the results of the majority-vote decoder.When the decoder produces
, it
successfully corrected the errors introduced by the channel(if there were any; the top row corresponds to the case in
which no errors occurred). The error probability of thedecoders is the sum of the probabilities when the decoder
produces
.
Thus, if one bit of the three bits is received in
error, the receiver can correct the error; if more than oneerror occurs, the channel decoder announces the bit is
1 instead of transmitted value of
0 . Using this repetition code, the
probability of
equals
.
This probability of a decoding error is always less than
, the uncoded value, so long as
.
Demonstrate mathematically that this claim is
indeed true. Is
?
This question is equivalent to
or
.
Because this is an upward-going parabola, we need only checkwhere its roots are. Using the quadratic formula, we find
that they are located at
and
. Consequently
in the range
the error rate produced by coding is smaller.