Concatenated error correction code: Difference between revisions

Revision as of 01:07, 7 May 2014

Revision as of 09:00, 20 July 2014

Line 1:

{{Use dmy dates|date=July 2014}}

In [[coding theory]], '''concatenated codes''' form a class of [[error-correcting code]]s that are derived by combining an '''inner code''' and an '''outer code'''. They were conceived in 1966 by [[Dave Forney]] as a solution to the problem of finding a code that has both exponentially decreasing error probability with increasing block length and [[polynomial-time]] decoding [[Computational complexity theory|complexity]].<ref name="Forney">

{{cite journal

Line 73 ⟶ 74:

|volume=12

|issue=2

|pages=125−131125–131

|publisher=IEEE

|date=April 1966

Line 86 ⟶ 87:

|volume=26

|issue=2

|pages=238−243238–243

|publisher=IEEE

|date=March 1980

Line 98 ⟶ 99:

|volume=53

|issue=1

|pages=387−393387–393

|publisher=IEEE

|date=January 2007

Line 120 ⟶ 121:

|title=Reed–Solomon Codes and the Exploration of the Solar System

|publisher=JPL

|date=20 AugAugust 1993

}}

</ref>

Line 129 ⟶ 130:

In a looser 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]].<ref>[http://www.etsi.org/deliver/etsi_en/302300_302399/302307/01.02.01_60/en_302307v010201p.pdf Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2)], [[ETSI]] EN 302 307, V1.2.1, April 2009.</ref>

A simple concatenation scheme is also used on the [[compact disc]] (CD), where an interleaving layer between two Reed–Solomon codes of different sizes spreads errors across various blocks.

== Turbo codes: A parallel concatenation approach ==

The description above is given for what is now called a serially concatenated code. [[Turbo code]]s, 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 passes information forth and back between the codes.<ref name="deep-space-codes"/> This design has a better performance than any previously conceived 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, such as within serially concatenated convolutional codes (SCCCs). An early form of iterated decoding was implemented with two to five iterations in the "Galileo code" of the [[Galileo (spacecraft)|Galileo space probe]].<ref name="McEliece"/>