Repetition code
Encyclopedia
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.
times, a particular bit to the
waveform modulator when the bit is received from the source stream.
For example, if we have a
repetition code, then encoding the signal
yields a code 
.
. 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
repetition code and we are decoding the signal
. The decoded message is 
, 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.
For fading channels repetition codes perform well with increasing repetition factor.
In this figure, the coding gains for various repetition factors are seen.
For the AWGN channels perform worse for longer repetition factors.
In this figure, the coding gains are progressively worse with the increasing parameter.
(
) is 
for an 
repetition code, and there are two valid code words - all ones and all zeros, so the minimum weight
(
) is r. This gives the repetition code
an error correcting capacity of
(i.e. it will correct up to 
errors in any code word).
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 channel
s. Practical adaptive codes for erasure channels have been invented only recently, and are known as fountain code
s.
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
, 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, times, a particular bit to thewaveform modulator when the bit is received from the source stream.
For example, if we have a
repetition code, then encoding the signal yields a code .Repetition Decoder
Repetition decoding is usually done using Majority logic detectionMajority logic decoding
In error detection and correction, majority logic decoding is a method to decode repetition codes, based on the assumption that the largest number of occurrences of a symbol was the transmitted symbol.-Theory:...
. 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
repetition code and we are decoding the signal. The decoded message is , as we have most occurrenceof 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
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
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 distanceHamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
(
) is for an repetition code, and there are two valid code words - all ones and all zeros, so the minimum weightMinimum weight
In error-correcting coding, the minimum Hamming weight, commonly referred to as the minimum weight wmin of a code is the weight of the lowest-weight code word. The weight w of a code word is the number of 1s in the word...
(
) is r. This gives the repetition codean error correcting capacity of
(i.e. it will correct up to 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
Time diversity
Time Diversity is used in digital communication systems to combat that the transmissions channel may suffer from error bursts due to time-varying channel conditions...
as well.
Most modulation techniques transmit a bit or chip over many cycles of a sinusoid carrier signal.
The low-pass filter
Low-pass filter
A low-pass filter is an electronic filter that passes low-frequency signals but attenuates signals with frequencies higher than the cutoff frequency. The actual amount of attenuation for each frequency varies from filter to filter. It is sometimes called a high-cut filter, or treble cut 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
FlexRay
FlexRay is an automotive network communications protocol developed by the . It is designed to be faster and more reliable than CAN and TTP, but is also more expensive...
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
Turbo code
In information theory, turbo codes are a class of high-performance forward error correction codes developed in 1993, which were the first practical codes to closely approach the channel capacity, a theoretical maximum for the code rate at which reliable communication is still possible given a...
-like iteratively decoded concatenated coding
Concatenated error correction codes
In coding theory, concatenated codes form a class of error-correcting codes that are derived by combining an inner code and an outer code...
schemes, such as repeat-accumulate
Repeat-Accumulate Code
In computer science, repeat-accumulate codes are a low complexity class of error-correcting codes. They were devised so that their ensemble weight distributions are easy to derive...
(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
Code rate
In telecommunication and information theory, the code rate of a forward error correction code is the proportion of the data-stream that is useful...
can be automatically adjusted to varying channel capacity
Channel capacity
In electrical engineering, computer science and information theory, channel capacity is the tightest upper bound on the amount of information that can be reliably transmitted over a communications channel...
, 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 channel
Binary erasure channel
A binary erasure channel is a common communications channel model used in coding theory and information theory. In this model, a transmitter sends a bit , and the receiver either receives the bit or it receives a message that the bit was not received...
s. Practical adaptive codes for erasure channels have been invented only recently, and are known as fountain code
Fountain code
In coding theory, fountain codes are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can ideally be recovered from any subset of the encoding symbols of...
s.
See also
- majority logic decodingMajority logic decodingIn error detection and correction, majority logic decoding is a method to decode repetition codes, based on the assumption that the largest number of occurrences of a symbol was the transmitted symbol.-Theory:...
- Hamming codeHamming codeIn telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming-code invented by Richard Hamming in 1950. Hamming codes can detect up to two and correct up to one bit errors. By contrast, the simple parity code cannot correct errors, and can detect only...
- Convolutional codeConvolutional codeIn telecommunication, a convolutional code is a type of error-correcting code in which* each m-bit information symbol to be encoded is transformed into an n-bit symbol, where m/n is the code rate and...
- triple modular redundancyTriple modular redundancyIn computing, triple modular redundancy is a fault tolerant form of N-modular redundancy, in which three systems perform a process and that result is processed by a voting system to produce a single output. If any one of the three systems fails, the other two systems can correct and mask the...