In coding theory, concatenated codes form a class of error-correcting codes that are derived by combining an inner code and an outer code. They were conceived in 1966 by Dave Forney as a solution for the problem of finding a code that has both exponentially decreasing error probability with increasing block length and polynomial-time decoding complexity.
Description
Let C be a code with length N and rate R over an alphabet A with K=N*R symbols. Let I be another code with length n and rate r over an alphabet B with k=n*r symbols.
The inner code I takes one of k possible inputs, encodes onto an n-tuple from B, transmits, and decodes into one of k possible outputs. We regard this as a channel which can transmit one symbol from the alphabet A, also of size k. We use this channel N times to transmit each of the N symbols in a codeword of C. The concatenation of C (as outer code) with I as (inner code) is thus a code of length Nn over the alphabet B.
The key insight in this approach is that if I is decoded using a maximum-likelihood approach (thus showing an exponentially decreasing error probability with increasing length), and C is a code with length N=2^(n*r) that can be decoded in polynomial time of N, then the concatenated code can be decoded in polynomial time of its combined length n*2^(n*r) and shows an exponentially decreasing error probability, even if I has exponential decoding complexity.
In a generalisation of above concatenation, there are N possible inner codes Ii and the i-th symbol in a codeword of C is transmitted across the inner channel using the i-th inner code. The Justesen codes are examples of generalised concatenated codes, where the outer code is a Reed-Solomon code.
Simplified mathematical overview
How does concatenated error correction work in real transmission situations? In essence you have a datastream, typically composed of packets containing and obeying the general process or function
- Packet = Outer Code (Inner Code(data))
That may or may not at some further point be defined as
- datastream = randomizer(Packet)
- datastream = interleaver(Packet)
The receiver and decoder at the other end merely reverse the process, weather this be on a Compact Disc player or a Deep Space Network telemetry system.
The randomizer or interleaver essentially perform the same function of removing any DC biases in datastream.
- Interleavers scramble data but do not alter it in any way.
- Randomizers alter data, but mostly do not touch its structure.
- Concatenating an interleaver and a randomizer can improve link margins.
The CCSDS Standard and NICAM Standard interleavers are closely related to each other. A good interleaver works just as well for a TV broadcaster as it would for a deep space mission. CCSDS recommends always using the CCSDS interleaver -- and NICAM's interleaver cannot be turned off. Space missions that have not used interleavers have run into telecom problems, so their usage is essentially mandatory as far as the CCSDS is concerned.
Applications
Concatenated codes were first implemented for deep space communication in the Voyager program, which launched their first probe in 1977, but all images were transmitted with a Golay Code.[1] Since then, concatenated codes became the workhorse for efficient error correction coding, and stayed so at least until the invention of turbo codes and LDPC codes.
Typically, the inner code is not a block code but a soft-decision convolutional Viterbi-decoded code with a short constraint length. For the outer code, a longer hard-decision block code, frequently Reed Solomon with 8-bit symbols, is selected. The larger symbol size makes the outer code more robust to burst errors that may occur due to channel impairments, and because erroneous output of the convolutional code itself is bursty. Additionally, an interleaving layer (possibly coupled with a randomizer) may be used to spread burst errors across a wider range.
The combination of an inner Viterbi convolutional code with an outer Reed-Solomon code (known as an RSV code) was to became the most commonly used Error Correction Code construction outside of the Space sector. The RSV code was thoroughly proven on the Voyager Program spacecraft over a 20 year time span.
The RSV code is still in use today for deep-space and satellite communication, notably the DVB-S digital television broadcast standard.
In a more loose sense, any (serial) combination of two or more codes may be referred to as a concatenated code. For example, within the DVB-S2 standard, a highly efficient LDPC code is combined with an algebraic outer code in order to remove any resilient errors left over from the inner LDPC code due to its inherent error floor.
The Compact Disc uses concatenated Reed-Solomon codes (of different lengths), with no Viterbi code involvement at all.
Turbo codes: A parallel concatenation approach
The description above is given for what is now called a serially concatenated code. Turbo codes, as described first in 1993, implemented a parallel concatenation of two convolutional codes, with an interleaver between the two codes and an iterative decoder that would pass information forth and back between the codes.[1] This construction had much higher performance than all previously conveived concatenated codes. However, a key aspect of turbo codes is their iterated decoding approach.
Iterated decoding is now also applied to serial concatenations in order to achieve higher coding gains, as with the 3 or 4 iteration Galileo Code as used by the Galileo (spacecraft).
Notes
References
- F.J. MacWilliams (1977). The Theory of Error-Correcting Codes. North-Holland. pp. 307–316. ISBN 0-444-85193-3.
{{cite book}}: Unknown parameter|coauthors=ignored (|author=suggested) (help)
External links
- Dave Forney (ed.). "Concatenated codes". Scholarpedia.
- Why space missions fail (some detail on Galileo ECC)