Cryptography Reference
In-Depth Information
Chapter 8
Turbo product codes
8.1
History
Because of the Gilbert-Varshamov bound, it is necessary to have long codes in
order to obtain block codes with a large minimum Hamming distance (MHD) and
therefore high error correction capability. But, without a particular structure,
it is almost impossible to decode these codes.
The invention of product codes, due to Elias [8.4], can be seen in this con-
text: it means finding a simple way to obtain codes with high error correction
capability that are easily decodable from simple elementary codes. These prod-
uct codes can be seen as a particular realization of the concatenation principle
(Chapter 6).
The first decoding algorithm results directly from the construction of these
codes. This algorithm alternates the hard decision decoding of elementary codes
on the rows and columns. Unfortunately, this algorithm does not allow us to
reach the maximum error correction capability of these codes. The Reddy-
Robinson algorithm [8.15] does allow us to reach it. But no doubt due to its
complexity, it has never been implemented in practical applications.
The aim of this chapter is to give a fairly complete presentation of algorithms
for decoding product codes, whether they be algorithms for hard data or soft
data.
8.2
Product codes
With conventional constructions, it is theoretically possible to build codes
having a high MHD. However, the decoding complexity becomes prohibitive,
even for codes having an algebraic structure, like Reed-Solomon codes or BCH
(see Chapter 4) codes. For example, for Reed-Solomon codes on
F
256
,the
most complex decoder to have been implemented on a circuit has an error
