IEEE International Symposium on Information Theory (ISIT)

On the effect of parity-check weights in iterative decoding

Nandakishore Santhi, Alexander Vardy

Published Dec 23, 2004• 10 citations

Abstract

It is well-established "folk knowledge" that in order to be iteratively decodable, a code should have a sparse parity-check matrix, as it has some qualitative and quantitative properties for finite-length codes.

DOI: 10.1109/isit.2004.1365137

Related papers

On General Linear Block Code Decoding Using the Sum–Product Iterative Decoder

Todd K. Moon

The sum-product iterative decoder, conventionally used for low-density parity-check (LDPC) codes, hold promise as a decoder for general linear block code decoding. However, the promise is only partly fulfilled because, as we show experimentally, the decoder performance degrades rapidly as a function of parity check matrix weight. Even in the case of decoder failure, however, we demonstrate that there is information present in the decoder output probabilities that can still help with the decoding problem.

IEEE Communications LettersJun 1, 200410 citations

On the suboptimality of iterative decoding for finite length codes

Motohiko Isaka, M.P.C. Fossorier, H. Imai

We investigate the property of iterative decoding for finite length codes, and give some insights on the suboptimality of iterative decoding due to the cycles in the graph representation of the codes, for several different types of iteratively decodable codes.

IEEE International Symposium on Information Theory (ISIT)Jun 25, 20033 citations

A finite-field transform domain construction of binary low-density parity-check codes

Robin Horan, Cen Jung Tjhai, Martin Tomlinson +2 more

A new method of finding binary cyclic codes from the finite-field transform domain is presented. These cyclic codes have sparse parity-check matrix and thus are suitable for iterative decoding. Some interesting properties of the proposed construction method include the knowledge of the minimum distance and the ability to trade the increase in code dimension with a reduction in the parity-check matrix sparsity. By means of simulations, we show that the error correcting performance of the codes under iterative decoding is very close to the sphere-packing-bound constrained for binary transmission.

IEEE Information Theory Workshop (ITW)Jan 1, 20051 citation

Belief Propagation Decoding for Short-Length Codes Based on Sparse Tanner Graph

Zongyao Li, Yifei Shen, Yuqing Ren +3 more

In this paper, we present a novel approach to improve belief propagation (BP) decoding performance by sparsifying the Tanner graph. Our proposed method first constructs a low-weight parity-check (LWPC) matrix with increased rows based on the original parity-check matrix. Then, all 4-cycles in the LWPC matrix are eliminated by adding auxiliary variable nodes and corresponding parity-check rows, resulting in the generalized LWPC (G-LWPC) matrix. Compared to the original matrix, the sparsity is greatly improved without altering the encoding constraints. Simulation results show that BP decoding based on the G-LWPC matrix is particularly effective for short code lengths. For a (128,20) polar code with 24-bit cyclic redundancy check, our proposed G-LWPC matrix reduces the density from 17.4% to 1.3%, and with 10 iterations, BP decoding can achieve the performance of successive cancellation list decoding with a list size of 32.

IEEE Communications LettersFeb 14, 20248 citations

Iterative Decoding of Low-Density Parity Check Codes

Venkatesan Guruswami

Much progress has been made on decoding algorithms for error-correcting codes in the last decade. In this article, we give an introduction to some fundamental results on iterative, message-passing algorithms for low-density parity check codes. For certain important stochastic channels, this line of work has enabled getting very close to Shannon capacity with algorithms that are extremely ecient (both in theory and practice).

Bulletin of the European Association for Theoretical Computer ScienceJan 1, 200611 citations

Baseline parity‐check matrix for iterative soft‐decision decoding of binary cyclic codes

Oluwaseyi Paul Babalola, Olayinka Olaolu Ogundile, D.J.J. Versfeld

Belief propagation (BP) is a soft‐decision (SD) decoder that is commonly used to obtain near‐optimal decoding performance for linear codes defined over sparse parity‐check matrix. Nevertheless, the BP yields poor performance when used in the decoding of algebraic block codes, usually described by a dense parity‐check matrix. Hence, enhanced BP decoders transform the parity check matrix of such codes at each iteration for efficient decoding. In this article, the performance of the transformed parity‐check matrix of the iterative SD decoder is analysed for the class of binary cyclic codes using a perfect knowledge model (PKM). The PKM computes a list of candidate matrices and selects a baseline parity‐check matrix according to a distance metric. The selected matrix is optimal since it minimizes the probability of error over various choices in the list. Results show that, for a given channel condition, the conventional transformed matrix obtained by Gaussian elimination is sub‐optimal and does not necessarily contain unitary weighted columns at corresponding columns of the unreliable bits. Moreover, PKM can be used to verify the performances of newly developed iterative SD decoders for binary cyclic codes based on parity‐check equations instead of maximum‐likelihood decoding.

IET CommunicationsApr 17, 20201 citation