Cryptography Reference
In-Depth Information
Chapter 6
Concatenated codes
The previous chapters presented the elementary laws of encoding like BCH,
Reed-Solomon or CRSC codes. Most of these elementary codes are asymptoti-
cally good, in the sense that their minimum Hamming distances (MHD) can be
made as large as we want, by suciently increasing the degree of the generator
polynomials. The complexity of the decoders is unfortunately unacceptable for
the degrees of polynomials that would guarantee the MHD required by practical
applications.
A simple means of having codes with a large MHD and nevertheless easily
decodable is to combine several reasonably-sized elementary codes, in such a
way that the resulting global code has a high error correction capability. The
decoding is performed in steps, each of them corresponding to one of the ele-
mentary encoding steps. The first composite encoding scheme was proposed by
Forney during work on his thesis in 1965, called concatenated codes [6.4]. In
this scheme, a first encoder, called the outer encoder, provides a codeword that
is then re-encoded by a second encoder, called the inner encoder. If the two
codes are systematic, the concatenated code is itself systematic. In the rest of
this chapter, only systematic codes will be considered.
Figure 6.1(a) shows a concatenated code, as imagined by Forney, and the
corresponding step decoder. The most judicious choice of constituent code is an
algebraic code, typically a Reed-Solomon code, for the outer code, and a convo-
lutional code for the inner code. The inner decoder is then the Viterbi decoder,
which easily takes advantage of the soft values provided by the demodulator,
and the outer decoder, which works on symbols with several bits (for example,
8 bits), can handle errors in bursts at the output of the first decoder. A per-
mutation or interleaving function inserted between the two encoders, and its
inverse function placed between the two decoders, can greatly increase the ro-
bustness of the concatenated code (Figure 6.1(b)). Such an encoding scheme has
worked very successfully in applications as varied as deep space transmissions
and digital, satellite and terrestrial television broadcasting. In particular, it is
