Concatenated Error Correction Code - Description

Description

Let Cin be a code, that is, a block code of length n, dimension k, minimum Hamming distance d, and rate r = k/n, over an alphabet A:

Let Cout be a code over an alphabet B with |B| = |A|k symbols:

The inner code Cin takes one of |A|k = |B| possible inputs, encodes into an n-tuple over A, transmits, and decodes into one of |B| possible outputs. We regard this as a (super) channel which can transmit one symbol from the alphabet B. We use this channel N times to transmit each of the N symbols in a codeword of Cout. The concatenation of Cout (as outer code) with Cin (as inner code), denoted Cout∘Cin, is thus a code of length Nn over the alphabet A:

It maps each input message m = (m1, m2, ..., mK) to a codeword (Cin(m'1), Cin(m'2), ..., Cin(m'N)), where (m'1, m'2, ..., m'N) = Cout(m1, m2, ..., mK).

The key insight in this approach is that if Cin is decoded using a maximum-likelihood approach (thus showing an exponentially decreasing error probability with increasing length), and Cout is a code with length N = 2nr that can be decoded in polynomial time of N, then the concatenated code can be decoded in polynomial time of its combined length n2nr = O(N⋅log(N)) and shows an exponentially decreasing error probability, even if Cin has exponential decoding complexity. This is discussed in more detail in section Decoding concatenated codes.

In a generalization of above concatenation, there are N possible inner codes Cin,i and the i-th symbol in a codeword of Cout is transmitted across the inner channel using the i-th inner code. The Justesen codes are examples of generalized concatenated codes, where the outer code is a Reed–Solomon code.

Read more about this topic:  Concatenated Error Correction Code

Famous quotes containing the word description:

    “A sound mind in a sound body, is a short, but full description of a happy state in this World: he that has these two, has little more to wish for; and he that wants either of them, will be little the better for anything else.”
    —John Locke (1632–1704)

    “He hath achieved a maid
    That paragons description and wild fame;
    One that excels the quirks of blazoning pens.”
    —William Shakespeare (1564–1616)

    “The type of fig leaf which each culture employs to cover its social taboos offers a twofold description of its morality. It reveals that certain unacknowledged behavior exists and it suggests the form that such behavior takes.”
    —Freda Adler (b. 1934)