Recrystallization (metallurgy)

In coding theory, the repetition code is one of the most basic error-correcting codes. In order to transmit a message over a noisy channel that may corrupt the transmission in a few places, the idea of the repetition code is to just repeat the message several times. The hope is that the channel corrupts only a minority of these repetitions. This way the receiver will notice that a transmission error occurred since the received data stream is not the repetition of a single message, and moreover, the receiver can recover the original message by looking at the received message in the data stream that occurs most often.

The repetition code is generally a very naive method of encoding data across a channel, and it is not preferred for Additive White Gaussian Noise Channels (AWGN), due to its worse-than-the-present error performance. Repetition codes generally offer a poor compromise between data rate and bit error rate, and other forms of error correcting codes can provide superior performance in these areas. The chief attraction of the repetition code is the ease of implementation.

There are two parts to the repetition code, as for any other code: the encoder and decoder, which will be described in detail.

Repetition Coder

The encoder is a simple device that repeats, $r$ times, a particular bit to the waveform modulator when the bit is received from the source stream.

For example, if we have a $(3,1)$ repetition code, then encoding the signal $m=101001$ yields a code $c=111000111000000111$.

Repetition Decoder

Repetition decoding is usually done using Majority logic detection. To determine the value of a particular bit, we look at the received copies of the bit in the stream and choose the value that occurs more frequently.

For example, suppose we have a $(3,1)$ repetition code and we are decoding the signal $c=110001111$. The decoded message is $m=101$, as we have most occurrence of 1's (two to one), 0's (two to one), and 1's (three to zero) in the first, second, and third code sequences, respectively.

This approach discards any 'soft' probability information obtained when decoding each received bit, and the performance of the code can be improved by retaining this probability information and using it to derive a joint probability across all n bits of the actual information bit value.

Repetition Codes on Fading Channel

File:Repetition Code On Fading Channel Graph.jpg

For fading channels repetition codes perform well with increasing repetition factor. In this figure, the coding gains for various repetition factors are seen.

Repetition Codes on Gaussian Channel

File:Repetition Code On AWGN Channel Graph.jpg

For the AWGN channels perform worse for longer repetition factors. In this figure, the coding gains are progressively worse with the increasing parameter.

Code parameters

The minimum Hamming distance ($d_{min}$) is $r$ for an $(r,1)$ repetition code, and there are two valid code words - all ones and all zeros, so the minimum weight ($w_{min}$) is r. This gives the repetition code an error correcting capacity of $\frac{r}{2}$ (i.e. it will correct up to $\frac{r}{2}$ errors in any code word).

Applications

Due to the simplicity of the channel encoding and decoding for repetition codes, they find applications in fading channels and non-AWGN environments. Repetition codes can be viewed as a method of space-time diversity as well.

Most modulation techniques transmit a bit or chip over many cycles of a sinusoid carrier signal. The low-pass filter used to average the relevant parameter (amplitude, phase, or frequency) over the entire bit-time or chip-time can be seen as a kind of repetition decoder.

Some UARTs, such as the ones used in the FlexRay protocol, use a majority filter to ignore brief noise spikes. This spike-rejection filter can be seen as a kind of repetition decoder.

Despite their poor performance as stand-alone codes, use in Turbo code-like iteratively decoded concatenated coding schemes, such as repeat-accumulate (RA) and accumulate-repeat-accumulate (ARA) codes, allows for surprisingly good error correction performance.

Repetition codes are one of the few known codes whose code rate can be automatically adjusted to varying channel capacity, by sending more or less parity information as required to overcome the channel noise, and it is the only such code known for non-erasure channels. Practical adaptive codes for erasure channels have been invented only recently, and are known as fountain codes.

See also

• majority logic decoding
• Hamming code
• Convolutional code
• triple modular redundancy