Error Correction Coding, 2nd Edition

Chapter 15Low‐Density Parity‐Check Codes: Introduction, Decoding, and Analysis

15.1 Introduction

Low‐density parity‐check (LDPC) codes, quite simply, are linear block codes whose parity check matrices are sparse, that is, only a small fraction of the elements in the parity check matrices are nonzero. A graphical representation of these codes called a Tanner graph leads to decoding algorithms of fairly low complexity. These decoding algorithms can incorporate soft channel information and run iteratively. LDPC codes have excellent performance — among the best codes known — and have been adopted in modern communication standards, such as IEEE 802.16, IEEE 802.20, IEEE 802.3, and DBV‐S2.

On the negative side, LDPC codes have higher encode complexity than turbo codes, being generically quadratic in the code dimension. This can be mitigated using variations on LDPC codes such as repeat‐accumulate (RA) codes, or LDPC convolutional codes.

It is a curious twist of history that LDPC codes should have been largely unnoticed for so long. LDPC codes were originally proposed in 1962 by Gallager [148, 149]. At that time, the codes might have been overlooked because contemporary investigations in concatenated coding overshadowed LDPC codes and because the hardware of the time could not support effective decoder implementations. As a result, LDPC codes remained largely unstudied for over thirty years, with only scattered references to them appearing in the literature, such as [297, 437, 486 ...