IEEE International Symposium on Information Theory (ISIT)

Construction of low density parity check codes: a combinatoric design approach

Bassem Ammar, B. Honary, Y. Kou, S. Lin

Published Jun 25, 2003• 24 citations

Abstract

This paper presents a method for constructing low density parity check (LDPC) codes based on a special type of combinatoric designs, known as the balanced incomplete block designs (BIBDs). Several classes of BIBDs suitable for constructing LDPC codes are presented. Codes constructed based on these classes of BIBDs perform well with iterative decoding.

DOI: 10.1109/isit.2002.1023583

Related papers

Construction of Low-Density Parity-Check Codes Based on Balanced Incomplete Block Designs

Bassem Ammar, B. Honary, Y. Kou +2 more

This correspondence presents a method for constructing structured regular low-density parity-check (LDPC) codes based on a special type of combinatoric designs, known as balance incomplete block designs. Codes constructed by this method have girths at least 6 and they perform well with iterative decoding. Furthermore, several classes of these codes are quasi-cyclic and hence their encoding can be implemented with simple feedback shift registers.

IEEE Transactions on Information TheoryJun 1, 2004157 citations

Construction of well-structured quasi-cyclic low-density parity check codes

B. Honary, Abdolhosein Moinian, Bassem Ammar

Two classes of well-structured binary low-density parity check codes (LDPC) are described. The first class is based on a branch of combinatorial mathematics, known as the balanced incomplete block design (BIBD). Construction of three types of codes derived from BIBD designs is illustrated in addition to a family of LDPC codes constructed by decomposition of incidence matrices of the proposed BIBD designs. The decomposition technique reduces the density of the parity check matrix and hence reduces the number of short cycles, which generally lead to better performing LDPC codes. The second class of well-structured LDPC codes, Vandermonde or array LDPC codes, are defined by a small number of parameters and cover a large set of code lengths and rates with different column weights. The presented LDPC codes are quasi-cyclic with no cycles of length four; hence simple encoding while maintaining good performance is achieved. Furthermore, the codes are compared with known random LDPC codes, in order to assess their relative achievable performance/complexity trade-offs. It is shown that well-structured LDPC codes perform very similar to the known random LDPC codes.

IEE Proceedings - CommunicationsJan 1, 200510 citations

Combinatorial Construction of Low-Density Parity-Check Codes for Short Block Length and High Rate Applications

Suquan Ding, Zhixing Yang, Jian Song +2 more

This paper presents a method to construct regular low-density parity-check (LDPC) codes of short block length and high rate based on a special type of combinatoric designs, i.e., balanced incomplete block designs (BIBDs) with lambda = 2 whose construction are based on cyclic difference families. Although the Tanner graph of the codes constructed contains some cycles of length 4, simulation results show that they perform well under belief propagation (BP) decoding. Further, these codes are quasi-cyclic (QC) codes and hence can be encoded efficiently

International Conference on Wireless Communications, Networking and Mobile ComputingSep 1, 20061 citation

New Constructions of Quasi-Cyclic LDPC Codes Based on Special Classes of BIBDs for the AWGN and Binary Erasure Channels

Lan Lan, Ying Yu Tai, Shu Lin +2 more

This paper presents new methods for efficiently constructing encodable quasi-cyclic low-density parity-check (LDPC) codes based on special balanced incomplete block designs (BIBDs). Codes constructed perform well over both the additive white Gaussian noise (AWGN) and binary erasure channels with iterative decoding.

IEEE Transactions on CommunicationsDec 1, 200710 citations

Construction of irregular LDPC codes based on Balanced Incomplete Block Designs

Siddarama R. Patil, Sant Saran Pathak

In this paper, we present a method to design irregular structured low-density parity-check (LDPC) codes based on balanced incomplete block designs (BIBD). The problem of designing irregular structured LDPC codes that have good overall error performance for a wide range of code rates and block sizes with attractive storage requirements is attempted. The proposed codes are well structured and unlike random codes can lend themselves to a very low-complexity implementation. The codes constructed by this method have the girth at least 6 and they perform well with the sum-product iterative decoding algorithm. Furthermore, the codes are compared with known random LDPC codes, in order to assess their relative achievable performance. The proposed LDPC codes demonstrate performance that is better than an average random LDPC code of similar block length, code rate and parity check matrix sparsity.

IEEE International Conference on Industrial and Information Systems (ICIIS)Jan 1, 20070 citations

LDPC Codes on Balanced Incomplete Block Designs: Construction, Girth, and Cycle Structure Analysis

Hengzhou Xu, Xiaodong Zhang, Mengmeng Xu +2 more

In this paper, we investigate the cycle structure inherent in the Tanner graphs of low-density parity-check (LDPC) codes constructed from balanced incomplete block designs (BIBDs). We begin by delineating the incidence structure of BIBDs and propose a methodology for constructing LDPC codes based on these designs. By analyzing the incidence relations between points and blocks within a BIBD, we prove that the resulting LDPC codes possess a girth of 6. Subsequently, we provide a detailed analysis of the cycle structure of the constructed LDPC codes and introduce a systematic approach for enumerating their short cycles. Using this method, we determine the exact numbers of cycles of lengths 6 and 8. Simulation results demonstrate that the constructed LDPC codes exhibit excellent performance.

EntropyApr 27, 20250 citations