LDPC Codes Based on Combinatorial Designs, Graphs, and Superposition

Abstract

Combinatorial designs [1–8] form an important branch in combinatorial mathematics. In the late 1950s and during the 1960s, special classes of combinatorial designs, such as balanced incomplete block designs , were used to construct error correcting codes, especial majority-logic-decodable codes. More recently, combinatorial designs were successfully used to construct structured LDPC codes [9–12]. LDPC codes of practical lengths constructed from several classes of combinatorial designs were shown to perform very well over the binary-input AWGN channel with iterative decoding. Graphs form another important branch in combinatorial mathematics. They were also used to construct error-correcting codes in the early 1960s, but not very successfully. Only a few small classes of majority-logic-decodable codes were constructed. However, since the rediscovery of LDPC codes in the middle of the 1990s, graphs have become an important tool for constructing LDPC codes. One example is to use protographs for constructing iteratively decodable codes as described in Chapters 6 and 8. This chapter presents several methods for constructing LDPC codes based on special types of combinatorial designs and graphs. Balanced Incomplete Block Designs and LDPC Codes Balanced incomplete block designs (BIBDs) form an important class of combinatorial designs. A special subclass of BIBDs can be used to construct RC-constrained matrices or arrays of CPMs from which LDPC codes can be constructed. This section gives a brief description of BIBDs. For an in-depth understanding of this subject, readers are referred to [1–8].