Cryptography Reference
In-Depth Information
Chapter 9
LDPC codes
Low Density Parity Check (LDPC) codes make up a class of block codes that
are characterized by a sparse parity check matrix. They were first described
in Gallager's thesis at the beginning of the 60s [9.21]. Apart from the hard
input decoding of LDPC codes, this thesis proposed iterative decoding based
on belief propagation (BP). This work was forgotten for 30 years. Only a few
rare studies referred to it during this dormant period, in particular, Tanner's
which proposed a generalization of the Gallager codes and a bipartite graph
[9.53] representation.
After the invention of turbo codes, LDPC codes were rediscovered in the
middle of the 90s by MacKay
et al.
[9.39], Wilberg [9.64] and Sipser
et al.
[9.52]. Since then, considerable progress concerning the rules for building good
LDPC codes, and coding and decoding techniques, have enabled LDPC codes
to be used, like turbo codes, in practical applications.
This chapter gives an overview of the encoding and decoding of LDPC codes,
and some considerations about hardware implementations.
9.1
Principle of LDPC codes
LDPC codes are codes built from the simplest elementary code: the single parity
check code. We therefore begin this chapter by describing the single parity check
code and its soft in soft out decoding before dealing with the construction of
LDPC codes.
