International Symposium on Turbo Codes and Iterative Information Processing

Decoding of LDPC codes with binary vector messages and scalable complexity

Gottfried Lechner, Ingmar Land, Lars Kildehoj Rasmussen

Published Sep 1, 2008• 4 citations

Abstract

In this paper, an iterative decoder for LDPC codes, suitable for high-speed processing, is proposed and analyzed. The messages exchanged between the nodes are binary vectors, where the information is conveyed by the number of ones rather than their positions in the vector. Regarding this aspect, the approach exhibits some similarities to stochastic decoding techniques. The check node decoders perform simple bit-wise modulo-2 additions, whereas the variable node decoders perform more complex processing tasks, making the resulting structure attractive for high-speed hardware implementation. By selecting the length of the binary vector messages between one and infinity, the complexity and the performance of the decoder can be scaled between that of the original binary message passing algorithm and that of the sum-product algorithm. Density evolution is developed for the proposed decoding algorithm, and decoding thresholds are determined as functions of the length of the binary vector messages. Simulation results exemplify the performance for finite-length codes.

DOI: 10.1109/turbocoding.2008.4658724

Related papers

Adaptive decoding of LDPC codes with binary messages

Ingmar Land, Gottfried Lechner, Lars Kildehoj Rasmussen

A novel adaptive binary decoding algorithm for LDPC codes is proposed, which reduces the decoding complexity while having a comparable or even better performance than corresponding non-adaptive alternatives. In each iteration the variable node decoders use the binary check node decoders multiple times; each single use is referred to as a sub-iteration. To process the sequences of binary messages in each iteration, the variable node decoders employ pre-computed look-up tables. These look-up tables as well as the number of sub-iterations per iteration are dynamically adapted during the decoding process based on the decoder state, represented by the mutual information between the current messages and the syndrome bits. The look-up tables and the number of sub-iterations per iteration are determined and optimized using density evolution. The performance and the complexity of the proposed adaptive decoding algorithm is exemplified by simulations.

arXiv:0902.3287IEEE International Symposium on Information Theory (ISIT)Jun 1, 20090 citations

Analysis of LDPC code performance over binary symmetric channel

Yuxiang Li

Low-Density Parity-Check code (LDPC) is a kind of linear block error-correcting codes.Sum-product algorithm is an iterative decoding algorithms commonly used in LDPC code decoding.This paper studies into the LDPC code message passing iterative decoding algorithm under the binary symmetric channel (BSC) and simulates the bit error probability,then simulates the convergence of check nodes' and variable nodes' probability density in the iterative process using the method of density evolution.The result show that under a given channel threshold,LDPC code has a good correction performance.

Journal of Northeast Normal UniversityJan 1, 20100 citations

A Differential Binary Message-Passing LDPC Decoder

Nastaran Mobini, Amir H. Banihashemi, Saied Hemati

In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finite-geometry LDPC codes, the proposed algorithm can achieve performance as close as 1.3 dB and 0.7 dB to that of belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.

GlobecomNov 1, 200716 citations

A differential binary message-passing LDPC decoder

Nastaran Mobini, A.H. Banihashemi, Saied Hemati

In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finitegeometry LDPC codes, the proposed algorithm can perform as close as about 1 dB and 0.5 dB to belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.

IEEE Transactions on CommunicationsSep 1, 200931 citations

Analysis of Complexity and Convergence Speed of Sequential Schedules for Decoding LDPC Codes

Sunghwan Kim, Min‐Ho Jang, Song‐Nam Hong +1 more

In this paper, a sequential message-passing decoding algorithm of low-density parity-check (LDPC) codes by partitioning check nodes is analyzed. This decoding algorithm shows better bit error rate (BER) performance than the conventional message-passing decoding algorithm, especially for the small number of iterations. Analytical results tell us that as the number of partitioned subsets of check nodes increases, the BER performance becomes better. We also derive the recursive equations for mean values of messages at check and variable nodes by using density evolution with Gaussian approximation. Finally, the analytical results are conflrmed by the simulation results.

Jan 1, 20062 citations

Efficient algorithms for stochastic decoding of LDPC codes

Kuo-Lun Huang

The expanding demand for high-speed communications has resulted in development of high-throughput error-correcting techniques required by emerging communication standards. Low-Density Parity-Check (LDPC) codes are a class of linear block codes that achieve near-capacity performance and have been selected as part of many digital communication standards. Stochastic computation has been proposed as a hardware efficient approach for decoding LDPC codes. Using stochastic computation, all messages in the iterative decoding process are represented by Bernoulli sequences. Computations on these sequences are performed bit-by-bit using simple logic operations. Furthermore, serial messages used in stochastic decoders help alleviate routing congestion in hardware implementation of decoder. These factors make stochastic decoding a low complexity alternative to implement LDPC decoders. In this dissertation, we analyze the characteristics of stochastic decoding and propose reduced-latency designs for stochastic LDPC decoders to achieve improved performance on various channel models.

Jan 1, 20162 citations