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 to the problem of finding a code that has both exponentially decreasing error probability with increasing block length and polynomial-time decoding complexity. Concatenated codes became widely used in space communications in the 1970s.
Background
The field of channel coding is concerned with sending a stream of data at the highest possible rate over a given communications channel, and then decoding the original data reliably at the receiver, using encoding and decoding algorithms that are feasible to implement in a given technology.
Shannon's channel coding theorem shows that over many common channels there exist channel coding schemes that are able to transmit data reliably at all rates less than a certain threshold , called the channel capacity of the given channel. In fact, the probability of decoding error can be made to decrease exponentially as the block length of the coding scheme goes to infinity. However, the complexity of a naive optimum decoding scheme that simply computes the likelihood of every possible transmitted codeword increases exponentially with , so such an optimum decoder rapidly becomes infeasible.
In his doctoral thesis, Dave Forney showed that concatenated codes could be used to achieve exponentially decreasing error probabilities at all data rates less than capacity, with decoding complexity that increases only polynomially with the code block length.
Description
Let Cin be a [n, k, d] 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 [N, K, D] 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.
Properties
1. The distance of the concatenated code Cout∘Cin is at least dD, that is, it is a [nN, kK, D'] code with D' ≥ dD.
Proof: Consider two different messages m1 ≠ m2 ∈ BK. Let Δ denote the distance between two codewords. Then
Thus, there are at least D positions in which the sequence of N symbols of the codewords Cout(m1) and Cout(m2) differ. For these positions, denoted i, we have
Consequently, there are at least d⋅D positions in the sequence of n⋅N symbols taken from the alphabet A in which the two codewords differ, and hence
2. If Cout and Cin are linear block codes, then Cout∘Cin is also a linear block code.
This property can be easily shown based on the idea of defining a generator matrix for the concatenated code in terms of the generator matrices of Cout and Cin.