IEEE Information Theory Workshop (ITW)

On products of graphs for LDPC codes

Jun Xu, Shu Hwa Lin, Ian F. Blake

Published Mar 2, 2004• 1 citation

Abstract

The notion of product block codes, whose generator matrix is the tensor product of the constituent generator matrices, is well established. Typically, they have good performance and a decoding algorithm with complexity on the order of the complexity of the decoding algorithms of the constituent codes. There has been much recent attention on the construction of bipartite graphs for low density parity check codes whose parity check matrices are the incidence matrices of right versus left vertices of the graph. The relation of the properties of the incidence matrix to code performance is difficult to establish precisely, although some guidelines are available. Two types of incidence matrix constructions are given here that show promise. In the first instance, a combinatorial construction is given, and, secondly, two types of graph products are considered for their application to LDPC codes.

DOI: 10.1109/itw.2003.1216681

Related papers

Low density parity check codes on bipartite graphs with Reed-Solomon constituent codes 1

Valentin B. Afanassiev, Alexander A. Davydov, Victor Zyablov

The following two important problems are considered in the paper: constructing a low density parity check code on a bipartite graph and rapid encoding of this code. For a given constituent code, the first problem solving is reduced to constructing and investigation of pa- rameters of the matrix describing connections of two vertex subsets of a regular bipartite graph (biadjacency matrix). It is convenient to treat the such matrix as a support-matrix of a code word. We propose a number of constructions that essentially extend the region of accessible parameters of the such matrices including these providing graphs without 4-cycles. Biadjacency matrices of regular bipartite graphs without 4-cycles are treated also as the incidence matrices of symmetric combinatorial configurations. This contributes to understanding and solving of the first problem. The second problem solving leads to search of such support-matrix transforma- tions that maximize the encoding speed and allow us to find non trivial complexity estimates.

Jan 1, 20092 citations

The Minimal Product Parity Check Matrix and Its Application

Morteza Esmaeili

In decoding a linear block code C by iterative decoding algorithms, these algorithms are essentially applied on a graphical representation of C such as Tanner graph and factor graph. Due to the impact of the structure of these graphs on the performance of code, we consider minimal parity check matrices(matrices with minimum number of nonzero entries) of product codes. An algorithm constructing such matrices is given. It turns out that under the given construction method, product coding technique is indeed a powerful method to construct irregular LDPC codes. Given two codes A and B, the construction method produces a Tanner graph with girth g := min {8, ga, gb} for the product code A ⊗ B, where ga and gb are the girth of Tanner graphs representing A and B, respectively. Simulation results confirm the positive practical impact of the minimality of the parity check matrices.

International Conference on CommunicationsJun 1, 20064 citations

Construction of low density parity check codes without short cycles

Lizhi Wu

With the rapid expansion of communication networks, there has been an increasing demand for efficient and reliable digital data transmission and storage systems. Many efficient codes have been developed. The LDPC code is one of them. In this thesis, the sum-product algorithm is used in the decoding of LDPC codes. Some schemes for encoding LDPC codes have been studied. In particular, two methods of producing regular H matrices have been attempted that include short cycles of length four with code rates of 0.5, and we present three schemes of finding regular H matrices which do not include short cycles of length four with code rate being 0.5. The effect of short cycles in the bipartite graph of regular LDPC codes has been considered. The simulation results show that the BER performances of regular H matrices that do not include short cycles of length four based on BPSK or 8PSK on AWGN channel is better than those of regular H matrices that include short cycles of length four. In conclusion, in order to obtain good performance with LDPC code, one should design H matrix related to bipartite graph without short cycles.

Jan 1, 20030 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

Joint encoding-decoding construction of LDPC codes with reduced complexity

Ming Shan

LDPC codes are now one of intensely studied areas in coding due to their near Shannon limit performance and parallel decoding architecture. Because the LDPC codes parity-check matrices are defined in terms of sparse random graphs, the implementation of the decoding and encoding is of high complexity. A new design methodology of LDPC codes, which are constructed by the cyclic shift matrices, is proposed in order to reduce the decoding complexity under the Sum-Product algorithm. Meanwhile,the encoding problem of LDPC codes is also considered, then a simplified encoding structure is given. A new procedure of removing the short loops from the bipartite graph is demonstrated according to the construction scheme of our LDPC codes. Performance comparisons between our codes and random constructed LDPC codes on BER, loop distributions and minimum distance estimation are given by extensive simulations and numerical analysis.

Journal of China Institute of CommunicationsJan 1, 20051 citation

Pseudocodewords, Expander Graphs, and the Algebraic Construction of Low-density Parity-check Codes

Christine A. Kelley

In 1948, Claude Shannon provided a sound mathematical foundation for communication, and proved the existence of good codes. Low-density parity-check (LDPC) codes are a family of error-correcting codes that achieve reliable performance (i.e., arbitrarily low probability of decoding error) near the Shannon-limit when decoded iteratively via very efficient graph-based message-passing decoders, the complexity of which grows only linearly in the block-length. Despite their tremendous success, LDPC codes lack a strong theoretical foundation and few explicit constructions of them are known that outperform their random counterparts. The first part of this thesis investigates how the structure of a graph representing an LDPC code affects the decoding performance. In particular, lower bounds on the minimum pseudocodeword weight, a key parameter in predicting iterative decoding performance, are obtained which link the performance of the code to the structural properties of its graph. One bound is a tree bound and is extended to generalized and p-ary LDPC codes. To this end, a suitable definition of pseudocodeword weight is derived for the p-ary symmetric channel. Moreover, the relationship between pseudocodeword weight distributions and different graph representations is examined. Bounds on the minimum pseudocodeword weight are also presented for several classes of expander codes based on the eigenvalues of the adjacency matrix of the Tanner graph. The second part of this thesis constructs LDPC codes having desirable properties. The first construction is combinatorial and uses permutations and mutually orthogonal Latin squares. One type results in the well-known projective-geometrybased LDPC codes. Another type yields a new family of codes having comparable parameters and pseudocodeword weights suitable for iterative decoding. The resulting performance of these codes is superior in comparison with that of comparable random LDPC codes, a feature attributed to the lack of low-weight bad pseudocodewords. For the second construction, unbalanced expander graphs are obtained by modifying the original zig-zag graph product to take bi-regular expander graphs as components, with suitable constraints on the degrees. Graphs resulting from the zig-zag and replacement product graphs are then used in the design of generalized LDPC codes having compact representation and pseudocodeword weights lower-bounded by the eigenvalue bounds.

Sep 15, 20220 citations