Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Communications

Optimum message mapping LDPC decoders derived from the sum-product algorithm

Jan Lewandowsky, Maximilian Stark, Gerhard Bauch

Published May 1, 2016• 12 citations
Publisher

Abstract

Starting from a discrete density evolution scheme originally introduced by Brian M. Kurkoski et al. which we improved by applying the Information Bottleneck method, we recently presented results on message passing decoders for Low Density Parity Check codes that have much lower complexity than state of the art decoders. In the decoders all node operations are replaced by discrete message mappings of unsigned integers what yields a great complexity reduction. Anyway the decoders perform very close to belief propagation decoding. New included simulation results prove that using a 4 bit integer architecture these decoders loose only 0.1 dB over Eb/No in comparison to an exact belief propagation decoder applied to the quantized output of a Gaussian channel. The most important contribution of this paper is the derivation of the message mapping decoders from the sum-product algorithm. Until now these decoders are assumed to not be linked to this algorithm. In order to reveal the hidden connection, we explain the decoding principle of the message mapping decoders in general factor graphs.

DOI
10.1109/icc.2016.7510906

Related papers

Information-Optimum LDPC Decoders Based on the Information Bottleneck Method

Jan Lewandowsky, Gerhard Bauch

The Information Bottleneck method is a powerful and generic tool from the field of machine learning. It compresses an observation to a quantized variable while attempting to preserve the mutual information shared with a relevant random variable. This paper describes a new application of the Information Bottleneck method in communications. It explains in detail, how the Information Bottleneck method can be applied to construct discrete message passing decoders for regular low-density parity-check codes. The obtained decoders process only unsigned integers and use only simple lookup tables as node operations. As a consequence, the decoders can be implemented using only unsigned integer arithmetic which makes them significantly simpler and faster than the state-of-the-art decoders which process real valued log-likelihood ratios. Anyway, included results show that the considered discrete message passing decoders perform surprisingly close to optimum message passing decoders and even outperform state-of-the-art decoders, such as the min-sum decoder. We aim to take the reader on a journey from the theoretical idea of the Information Bottleneck method to a complete design framework for the considered discrete decoders. Several included figures and examples illustrate the decoder construction process and its analysis.

IEEE Access•Jan 1, 2018•84 citations

Noise Thresholds for Discrete LDPC Decoding Mappings

Brian M. Kurkoski, Kazuhiko Yamaguchi, Kingo Kobayashi

For decoding low-density parity-check (LDPC) codes on discrete memoryless channels, a method to quantize messages and to find message-passing decoding functions for the variable and check nodes is developed. These are used to obtain noise thresholds by density evolution. The message-passing decoding alphabet is restricted to be discrete with a fixed maximum alphabet size. Discrete quantization is required to obtain this fixed alphabet size; a greedy algorithm which uses the mutual information between the code bit and message is presented. It is argued that using this message-passing decoding framework is more efficient for approaching channel capacity than simply quantizing the belief-propagation algorithm. This method is evaluated using regular LDPC codes on the binary symmetric channel. Using a maximum alphabet size of 16 (4 bits), noise thresholds close to those of belief propagation are obtained.

Globecom•Jan 1, 2008•51 citations

Trellis based node operations for LDPC decoders from the Information Bottleneck method

Jan Lewandowsky, Gerhard Bauch

We utilize the Information Bottleneck method in a discrete density evolution scheme that was introduced by Brian M. Kurkoski et al. in order to find message mappings for the node operations of discrete LDPC decoders. The resulting decoders have performance close to belief propagation decoding but require much lower implementation efforts because they only process unsigned integers instead of log-likelihood-ratios. An efficient trellis implementation of the resulting discrete node operations is presented. In the trellis implementation the passed messages are calculated using recursive formulas that are fully characterized by two static vectors of integers. Bit error rate simulations for exemplary (3, 6)-regular LDPC codes with a 4 bit message representation prove the performance of the proposed decoders that even outperform Min-Sum decoders with quasi continuous message representation.

International Conference on Signal Processing and Communication Systems•Dec 1, 2015•30 citations

Density Evolution for GF(q) LDPC Codes Via Simplified Message-passing Sets

Brian M. Kurkoski, Kazuhiko Yamaguchi, Kingo Kobayashi

A message-passing decoder for GF(q) low-density parity-check codes is defined, which uses discrete messages from a subset of all possible binary vectors of length q. The proposed algorithm is a generalization to GF(q) of Richardson and Urbanke's decoding "Algorithm E" for binary codes. Density evolution requires a mapping between the probability distribution spaces for the channel, variable and check messages, and under the proposed algorithm, exact density evolution is possible. Symmetries in the message densities permit reduction in the size of the probability distribution space. Noise thresholds are obtained for LDPC codes on discrete memoryless channels, and as with Algorithm E, are remarkably close to noise thresholds under more complex belief propagation decoding.

Information Theory and Applications Workshop (ITA)•Jan 1, 2007•9 citations

Design and Implementation of Low Bit Error Rate of LDPC Decoder

Ashlesha P. Kshirsagar, Sandeep Kakde, Manish Devendra Chawhan +1 more

Many classes of high-performance Low-density parity check codes are based on parity check matrices composed of permutation sub matrices. The emulation-simulation framework further allows the algorithm and implementation to be iteratively redefined to improve the error floor performance of message passing decoder. Log-Like hood-Ratio (LLR) based Belief-Propagation (BP) algorithm is presented for Low Density Parity Check codes. Numerically accurate representation of check node update computation used in LLR-BP decoding is described. The implementation of Sum-Product algorithm (SPA) within Low Density Parity Check Code (LDPC) decoder is described in this paper and the correction term is used to improve the decoding performance of min-sum algorithm (MSA). Quantization and log-tanh function approximation in sum-product decoder strongly affect which absorbing set dominates in error floor region. For LDPC decoder, bit error rate (BER) decreases with increase in the signal to noise ratio.

International Conference on Communication Systems and Network Technologies•Apr 1, 2015•1 citation

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 Communications•Sep 1, 2009•31 citations
Starting from a discrete density evolution scheme originally introduced by Brian M. Kurkoski et al. which we improved by applying the Information Bottleneck method, we recently presented results on message passing decoders for Low Density Parity Check codes that have much lower complexity than state of the art decoders. In the decoders all node operations are replaced by discrete message mappings of unsigned integers what yields a great complexity reduction. Anyway the decoders perform very close to belief propagation decoding. New included simulation results prove that using a 4 bit integer architecture these decoders loose only 0.1 dB over Eb/No in comparison to an exact belief propagation decoder applied to the quantized output of a Gaussian channel. The most important contribution of this paper is the derivation of the message mapping decoders from the sum-product algorithm. Until now these decoders are assumed to not be linked to this algorithm. In order to reveal the hidden connection, we explain the decoding principle of the message mapping decoders in general factor graphs.
The Information Bottleneck method is a powerful and generic tool from the field of machine learning. It compresses an observation to a quantized variable while attempting to preserve the mutual information shared with a relevant random variable. This paper describes a new application of the Information Bottleneck method in communications. It explains in detail, how the Information Bottleneck method can be applied to construct discrete message passing decoders for regular low-density parity-check codes. The obtained decoders process only unsigned integers and use only simple lookup tables as node operations. As a consequence, the decoders can be implemented using only unsigned integer arithmetic which makes them significantly simpler and faster than the state-of-the-art decoders which process real valued log-likelihood ratios. Anyway, included results show that the considered discrete message passing decoders perform surprisingly close to optimum message passing decoders and even outperform state-of-the-art decoders, such as the min-sum decoder. We aim to take the reader on a journey from the theoretical idea of the Information Bottleneck method to a complete design framework for the considered discrete decoders. Several included figures and examples illustrate the decoder construction process and its analysis.
For decoding low-density parity-check (LDPC) codes on discrete memoryless channels, a method to quantize messages and to find message-passing decoding functions for the variable and check nodes is developed. These are used to obtain noise thresholds by density evolution. The message-passing decoding alphabet is restricted to be discrete with a fixed maximum alphabet size. Discrete quantization is required to obtain this fixed alphabet size; a greedy algorithm which uses the mutual information between the code bit and message is presented. It is argued that using this message-passing decoding framework is more efficient for approaching channel capacity than simply quantizing the belief-propagation algorithm. This method is evaluated using regular LDPC codes on the binary symmetric channel. Using a maximum alphabet size of 16 (4 bits), noise thresholds close to those of belief propagation are obtained.
We utilize the Information Bottleneck method in a discrete density evolution scheme that was introduced by Brian M. Kurkoski et al. in order to find message mappings for the node operations of discrete LDPC decoders. The resulting decoders have performance close to belief propagation decoding but require much lower implementation efforts because they only process unsigned integers instead of log-likelihood-ratios. An efficient trellis implementation of the resulting discrete node operations is presented. In the trellis implementation the passed messages are calculated using recursive formulas that are fully characterized by two static vectors of integers. Bit error rate simulations for exemplary (3, 6)-regular LDPC codes with a 4 bit message representation prove the performance of the proposed decoders that even outperform Min-Sum decoders with quasi continuous message representation.
A message-passing decoder for GF(q) low-density parity-check codes is defined, which uses discrete messages from a subset of all possible binary vectors of length q. The proposed algorithm is a generalization to GF(q) of Richardson and Urbanke's decoding "Algorithm E" for binary codes. Density evolution requires a mapping between the probability distribution spaces for the channel, variable and check messages, and under the proposed algorithm, exact density evolution is possible. Symmetries in the message densities permit reduction in the size of the probability distribution space. Noise thresholds are obtained for LDPC codes on discrete memoryless channels, and as with Algorithm E, are remarkably close to noise thresholds under more complex belief propagation decoding.
Many classes of high-performance Low-density parity check codes are based on parity check matrices composed of permutation sub matrices. The emulation-simulation framework further allows the algorithm and implementation to be iteratively redefined to improve the error floor performance of message passing decoder. Log-Like hood-Ratio (LLR) based Belief-Propagation (BP) algorithm is presented for Low Density Parity Check codes. Numerically accurate representation of check node update computation used in LLR-BP decoding is described. The implementation of Sum-Product algorithm (SPA) within Low Density Parity Check Code (LDPC) decoder is described in this paper and the correction term is used to improve the decoding performance of min-sum algorithm (MSA). Quantization and log-tanh function approximation in sum-product decoder strongly affect which absorbing set dominates in error floor region. For LDPC decoder, bit error rate (BER) decreases with increase in the signal to noise ratio.
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.