IEEE Vehicular Technology Conference

A low complexity FEC scheme based on the intersection of interleaved block codes

O. Pothier, Loïc Brunel, Joseph J. Boutros

Published Jan 20, 2003• 19 citations

Abstract

We describe a class of asymptotically good codes built from the intersection of randomly permuted binary BCH codes. This family of pseudo-random error correcting codes, called generalized low density (GLD) codes, is a direct generalization of Gallager's low density parity check (LDPC) codes. GLD codes belong to the larger family of Tanner codes based on a random bipartite graph. We study the GLD ensemble performance and prove the asymptotically good property. We also compare GLD codes minimum distance and performance to the Varshamov-Gilbert bound and BSC capacity respectively. The results show that maximum-likelihood decoding of GLD codes achieves near capacity efficiency. The suboptimal iterative decoding of GLD codes is briefly presented. Experimental results of small and large blocklength codes are finally illustrated on both AWGN and Rayleigh fading channels.

DOI: 10.1109/vetec.1999.778060

Related papers

Generalized low density (Tanner) codes

Joseph J. Boutros, O. Pothier, Gilles Zémor

We build a class of pseudo-random error correcting codes, called generalized low density codes (GLD), from the intersection of two interleaved block codes. GLD code performance approaches the channel capacity limit and the GLD decoder is based on simple and fast SISO (soft input-soft output) decoders of smaller block codes. GLD codes are a special case of Tanner codes and a generalization of Gallager's LDPC codes. It is also proved by an ensemble performance argument that these codes are asymptotically good in the sense of the minimum distance criterion. The flexibility in selecting the parameters of GLD codes makes them suitable for small and large block length forward error correcting schemes.

International Conference on CommunicationsJan 20, 2003183 citations

On generalized low-density parity-check codes based on Hamming component codes

Michael Lentmaier, Kamil Sh. Zigangirov

In this paper we investigate a generalization of Gallager's (1963) low-density (LD) parity-check codes, where as component codes single error correcting Hamming codes are used instead of single error detecting parity-check codes. It is proved that there exist such generalized low-density (GLD) codes for which the minimum distance is growing linearly with the block length, and a lower bound of the minimum distance is given. We also study iterative decoding of GLD codes for the communication over an additive white Gaussian noise channel. The performance in terms of the bit error rate, obtained by computer simulations, is presented for GLD codes of different lengths.

IEEE Communications LettersAug 1, 1999190 citations

Generalized LDPC codes and generalized stopping sets

N. Miladinovic, M.P.C. Fossorier

A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.

IEEE Transactions on CommunicationsFeb 1, 200852 citations

High-performance, low-complexity decoding of generalized low-density parity-check codes

T. Zhang, Keshab K. Parhi

A class of pseudo-random compound error-correcting codes, called generalized low-density (GLD) parity-check codes, has been proposed recently. As a generalization of Gallager's low-density parity-check (LDPC) codes, GLD codes are also asymptotically good in the sense of minimum distance criterion and can be effectively decoded based on iterative soft-input soft-output (SISO) decoding of individual constituent codes. The code performance and decoding complexity of GLD codes are heavily dependent on the employed SISO decoding algorithm. In this paper, we show that Max-Log-MAP is an attractive SISO decoding algorithm for GLD coding scheme, considering the trade-off between performance and complexity in the practical implementations. A normalized Max-Log-MAP is presented to improve the GLD code performance significantly compared with using conventional Max-Log-MAP. Moreover, we propose two techniques, decoding task scheduling and reduced search Max-Log-MAP, to effectively reduce the decoding complexity without any performance degradation.

GlobecomNov 13, 200210 citations

Efficient decoding of generalized low-density parity-check codes based on long component codes

Telex M. N. Ngatched, Fambirai Takawira

A class of pseudo-random compound error-correcting codes, called generalized low density (GLD) parity-check codes, has been proposed recently. As a generalization of Gallager's low-density parity check (LPDC) codes, GLD codes are also asymptotically good in the sense of minimum distance criterion and can be effectively decoded based on iterative soft-input soft-output (SISO) decoding of individual constituent codes. The code performance and decoding complexity of GLD codes are heavily dependent on the employed SISO decoding algorithm. In this paper, we present an efficient SISO decoding algorithm for GLD codes. The proposed algorithm utilizes Kaneko's decoding algorithm for soft-input hard-output decoding. These hard outputs are converted to soft-decision using reliability calculations. The algorithm proposed here presents a major advantage over existing decoding algorithms for GLD codes by being applicable even when long and powerful component codes are used. The complexity of the proposed algorithm is less than that of trellis-based decoding algorithms with a performance degradation of only 0.3 dB.

IEEE Wireless Communications and Networking ConferenceJan 24, 20046 citations

Compound codes based on irregular graphs and their iterative decoding.

Telex Magloire Ngatched. Nkouatchah

Low-density parity-check (LDPC) codes form a Shannon limit approaching class of linear block codes. With iterative decoding based on their Tanner graphs, they can achieve outstanding performance. Since their rediscovery in late 1990's, the design, construction, and decoding of LDPC codes as well as their generalization have become one of the focal research points. This thesis takes a few more steps in these directions. The first significant contribution of this thesis is the introduction of a new class of codes called Generalized Irregular Low-Density (GILD) parity-check codes, which are adapted from the previously known class of Generalized Low-Density (GLD) codes. GILD codes are generalization of irregular LDPC codes, and are shown to outperform GLD codes. In addition, GILD codes have a significant advantage over GLD codes in terms of encoding and decoding complexity. They are also able to match and even beat LDPC codes for small block lengths. The second significant contribution of this thesis is the proposition of several decoding algorithms. Two new decoding algolithms for LDPC codes are introduced. In principle and complexity these algorithms can be grouped with bit flipping algorithms. Two soft-input soft-output (SISO) decoding algorithms for linear block codes are also proposed. The first algorithm is based on Maximum a Posteriori Probability (MAP) decoding of low-weight subtrellis centered around a generated candidate codeword. The second algorithm modifies and utilizes the improved Kaneko's decoding algorithm for soft-input hard-output decoding. These hard outputs are converted to soft-decisions using reliability calculations. Simulation results indicate that the proposed algorithms provide a significant improvement in error performance over Chase-based algorithm and achieve practically optimal performance with a significant reduction in decoding complexity. An analytical expression for the union bound on the bit error probability of linear codes on the Gilbert-Elliott (GE) channel model is also derived. This analytical result is shown to be accurate in establishing the decoder performance in the range where obtaining sufficient data from simulation is impractical.

Jan 1, 20040 citations