Globecom

Iterative encoding of low-density parity-check codes

David Haley, Alex J. Grant, J.L. Buetefuer

Published Mar 22, 2004• 45 citations

Abstract

Motivated by the potential to reuse the decoder architecture, and thus reduce circuit space, we explore the use of iterative encoding techniques which are based upon the graphical representation of the code. We design codes by identifying associated encoder convergence constraints and also eliminating some well known undesirable properties for sum-product decoding such as 4-cycles. In particular we show how the Jacobi method for iterative matrix inversion can be viewed as message passing and employed as the core of an iterative encoder. Example constructions of both regular and irregular LDPC codes that are encodable using this method are investigated.

DOI: 10.1109/glocom.2002.1188405

Related papers

Reversible Low-Density Parity-Check Codes

David Haley, Alex J. Grant

Low-density parity-check (LDPC) codes may be decoded using a circuit implementation of the sum-product algorithm which maps the factor graph of the code. By reusing the decoder for encoding, both tasks can be performed using the same circuit, thus reducing area and verification requirements. Motivated by this, iterative encoding techniques based upon the graphical representation of the code are proposed. Code design constraints which ensure encoder convergence are presented, and then used to design iteratively encodable codes, while also preventing 4-cycle creation. We show how the Jacobi method for iterative matrix inversion can be applied to finite field matrices, viewed as message passing, and employed as the core of an iterative encoder. We present an algebraic construction of4-cycle free iteratively encodable codes using circulant matrices. Analysis of these codes identifies a weakness in their structure, due to a repetitive pattern in the factor graph. The graph supports pseudo-codewords of low pseudo-weight. In order to remove the repetitive pattern in the graph, we propose a recursive technique for generating iteratively encodable codes. The new codes offer flexibility in the choice of code length and rate, and performance that compares well to randomly generated, quasi-cyclic and extended Euclidean-geometry codes.

IEEE Transactions on Information TheoryApr 22, 20099 citations

Iterative Decoding of Codes on Graphs

Sundararajan Sankaranarayanan

The growing popularity of a class of linear block codes called the low-density parity-check (LDPC) codes can be attributed to the low complexity of the iterative decoders, and their potential to achieve performance very close to the Shannon capacity. This makes them an attractive candidate for ECC applications in communication systems. This report proposes methods to systematically construct regular and irregular LDPC codes.A class of regular LDPC codes are constructed from incidence structures in finite geometries like projective geometry and affine geometry. A class of irregular LDPC codes are constructed by systematically splitting blocks of balanced incomplete block designs to achieve desired weight distributions. These codes are decoded iteratively using message-passing algorithms, and the performance of these codes for various channels are presented in this report.The application of iterative decoders is generally limited to a class of codes whose graph representations are free of small cycles. Unfortunately, the large class of conventional algebraic codes, like RS codes, has several four cycles in their graph representations. This report proposes an algorithm that aims to alleviate this drawback by constructing an equivalent graph representation that is free of four cycles. It is theoretically shown that the four-cycle free representation is better suited to iterative erasure decoding than the conventional representation. Also, the new representation is exploited to realize, with limited success, iterative decoding of Reed-Solomon codes over the additive white Gaussian noise channel.Wiberg, Forney, Richardson, Koetter, and Vontobel have made significant contributions in developing theoretical frameworks that facilitate finite length analysis of codes. With an exception of Richardson's, most of the other frameworks are much suited for the analysis of short codes. In this report, we further the understanding of the failures in iterative decoders for the binary symmetric channel. The failures of the decoder are classified into two categories by defining trapping sets and propagating sets. Such a classification leads to a successful estimation of the performance of codes under the Gallager B decoder. Especially, the estimation techniques show great promise in the high signal-to-noise ratio regime where the simulation techniques are less feasible.

Jan 1, 20060 citations

Low-density parity-check codes

Sarah J. Johnson

Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.

Cambridge University Press eBooksNov 19, 20095 citations

The low-density parity-check codes based on The n-queen problem

Li Peng, Guangxi Zhu, Xiao Liu

This paper presents a new family of low-density parity-check (LDPC) code, the sparse parity-check matrix of which is constructed by self-defining non-diagonal identity sub-matrix that is a solution of the "n-queen problem". So this sub-matrix is called the Q-matrix and these LDPC codes are called the Q-matrixes LDPC codes. The Q-matrixes LDPC codes are good or very good codes with iterative decoding and their Tanner graphs are free of 4-lines cycle. Furthermore, they can be created in cycle form. Their encoding can be achieved in linear time. Especially, their code length and code rate can be flexible and quickly adjusted according to the practical situation, and the performance of high rate is also very good. The other unique excellence is that the large sparse parity-check matrixes of long Q-matrixes LDPC codes require very small storage space. The result of this paper is very significant not only for designing low complexity encoder, improving performance and reducing the complexity of the sum-product iterative decoding algorithm, but also for building practice system of encodable and decodable LDPC code.

Oct 15, 20046 citations

Iterative Decoding for Low-Density Parity-Check Lattices

Young-Seob Choi, Ihn-Jung Baik, Sae-Young Chung

Low-density parity-check (LDPC) lattices are introduced by Sadeghi et al. (2006). The construction method of such lattices and the decoding algorithm based on the min-sum algorithm are also proposed in [1]. In this paper we apply two iterative message passing algorithms, the sum-product algorithm and the max-product algorithm, to the Tanner graph representation of LDPC lattices. We evaluate the performance of two iterative message passing algorithms.

International Conference on Advanced Communication TechnologyFeb 1, 200813 citations

Improved reversible LDPC codes

David Haley, Alex J. Grant

We provide a thorough analysis for a class of iteratively encodable low-density parity-check codes. The iterative encoding technique is based upon the graphical representation of the code and allows the decoder circuit to also be used for encoding, thus saving circuit area. The analysis identifies a weakness in the structure of the code, which arises due to a repetitive pattern in its factor graph. We show that the graph supports pseudo-codewords of low pseudo-weight, and relate this to the empirical observation of some near-codewords. We then propose a new recursive technique for constructing iteratively encodable codes which have improved expansion. The new codes offer a large amount of flexibility in the choice of code length and rate, and performance that compares well to both randomly generated and extended Euclidean-geometry codes

IEEE International Symposium on Information Theory (ISIT)Jan 1, 20059 citations