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].
We investigate a systematic construction of regular low density parity check (LDPC) codes based on (γργ-1, ργ, ρ, γ{0,1}) combinatorial designs. The proposed (γ,ρ) regular LDPC ensemble has rate
(1−ρ1)γ girth ≥2γ+1, and exists for all γ≥2. The codes are a subset of Gallager’s random ensemble, but contains a good combination of structure and (pseudo)randomness. In particular, the simple case of γ=2 results in a class of codes that are high-rate, systematic, quasi-cyclic, linear-time encodable and decodable, and free of length-4 and length-6 cycles. Analysis on distance spectrum shows that they are better than the Gallager ensemble of the same parameters. Simulation of the proposed codes on intersymbol interference channels show that they perform comparably to random LDPC codes. Unlike random codes, the proposed structured LDPC codes can lend themselves to a low-complexity implementation for high-speed applications.
Analytically constructed LDPC codes comprise only a very small subset of possible codes and as a result LDPC codes are still, for the most part, constructed randomly. This paper extends the class of LDPC codes that can be systematically generated by presenting a construction method for regular LDPC codes based on combinatorial designs known as Kirkman triple systems. We construct (3, /spl rho/)-regular codes whose Tanner graph is free of 4-cycles for any integer /spl rho/, and examine girth and minimum distance properties of several classes of LDPC codes obtained from combinatorial designs.