Concatenated error correction codes

From Wikipedia, the free encyclopedia

In coding theory, concatenated codes form a class of error-correcting codes which are derived by combining an inner code and an outer code.

Contents 1 Description 2 Applications 3 How it works 4 Turbo codes, a compromise 5 References 6 Weblinks

[edit] Description

Let C be a code with length N, size K and minimum distance D over an alphabet A with k symbols. Let I be another code with length n, size k and minimum distance d over an alphabet B.

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.

In a generalisation, there are N possible inner codes I_i 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 codes is a Reed-Solomon code.

[edit] Applications

The Compact Disc and Voyager Program spacecraft use concatenated error correction technologies. Concatenated error codes may have been introduced with spacecraft missions that were involved with mapping the Moon and Mars^{[citation needed]}. In typical telecommunications systems before these data intensive missions -- only one hard error correction layer was used.

Concatenating error correction methods is useful in cases where the telecommunications link may be problematical. Typically a soft inner code (Viterbi) is used concatenated to a hard outer code (Reed-Solomon).

[edit] How it works

Inner code vs outer code performance

• typically the inner code is a weaker (and simpler) error correction code
• the outer correction code may not be in the same family of codes as the inner codes -- this is true for Voyager Program codes

[edit] Turbo codes, a compromise

Turbo codes, although not concatenated codes -- do typically utilise two different error correction codes running in parallel.

Concatenating codes can provide performance near that of Turbo codes but with an increase in decoder complexity.

[edit] References

• F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland. pp. 307-316. ISBN 0-444-85193-3. 

[edit] Weblinks

• Concatenated codes at Scholarpedia, curated by Dave Forney.