An Application Of Block Designs In Coding

Low-density parity-check (LDPC) codes on sparse graphs have attracted considerable attention owing to their capacity-approaching performance and low-complexity iterative decoding. The performance of a LDPC code is determined by its parity-check matrix H uniquely. It was known that the belief-propagation (BP) or sum-product algorithm (SPA) over cycle-free Tanner graphs provides optimum decoding. Hence, it is natural to try to minimize the influence of the cycles in the iterative decoding process, especially the influence of the cycles of length 4.In this thesis, we propose a method to design LDPC parity-check matrices, which can avoid cycles of length 4, derived from the incident matrices of balanced incomplete block designs (BIBD) constructed by using n mutually orthogonal Latin squares (MOLS) of order n . To get moderate LDPC codes with high performance, we also propose a method of constructing large BIBD by comprise pairs of small BIBD with Latin squares permuted randomly. Comparing with the PEG constructions for LDPC codes of short and moderate block lengths (the largest block length is more or less 1.0E003), the significance of the MOLS-BIBD LDPC and comprised BIBD LDPC algorithms lies in its simplicity, flexibility and small storage in the process of constructing. To realize error-free communications at low SNR without a feedback channel, a design of concatenating comprised BIBD-LDPC codes with LT codes is involved.Meanwhile, to avoid infeasibly determining the rank of parity-check matrices of large LDPC codes, we propose a method of replacing the g ? g sub-matrices of parity-check matrices with g ? g matrices by permuting an identity matrix of order g . And simulation results show that the performance of a LDPC code is hardly affected by such a replacement.