Concatenated Error Correction Code - Decoding Concatenated Codes

Decoding Concatenated Codes

A natural concept for a decoding algorithm for concatenated codes is to first decode the inner code and then the outer code. For the algorithm to be practical it must be polynomial-time in the final block length. Consider that there is a polynomial-time unique decoding algorithm for the outer code. Now we have to find a polynomial-time decoding algorithm for the inner code. It is understood that polynomial running time here means that running time is polynomial in the final block length. The main idea is that if the inner block length is selected to be logarithmic in the size of the outer code then the decoding algorithm for the inner code may run in exponential time of the inner block length, and we can thus use an exponential-time but optimal maximum likelihood decoder (MLD) for the inner code.

In detail, let the input to the decoder be the vector y = (y₁, ..., y_N) ∈ (An)N. Then the decoding algorithm is a two-step process:

1. Use the MLD of the inner code C_in to reconstruct a set of inner code words y' = (y'₁, ..., y'_N), with y'_i = MLD_Cin(y_i), 1 ≤ i ≤ N.
2. Run the unique decoding algorithm for C_out on y'.

Now, the time complexity of the first step is O(N⋅exp(n)), where n = O(log(N)) is the inner block length. In other words, it is NO(1) (i.e., polynomial-time) in terms of the outer block length N. As the outer decoding algorithm in step two is assumed to run in polynomial time the complexity of the overall decoding algorithm is polynomial-time as well.