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 Signal Processing and Communication Systems

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

Jan Lewandowsky, Gerhard Bauch

Published Dec 1, 2015• 30 citations
Publisher

Abstract

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.

DOI
10.1109/icspcs.2015.7391731

Related papers

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

Jan Lewandowsky, Maximilian Stark, Gerhard Bauch

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.

International Conference on Communications•May 1, 2016•12 citations

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

Design and Evaluation of Information Bottleneck LDPC Decoders for Software Defined Radios

Jan Lewandowsky, Gerhard Bauch, Matthias Tschauner +1 more

The Information Bottleneck method allows to construct information-optimum message passing decoders for low-density parity-check codes. In such decoders lookup tables replace the classical node operations of the variable and the check nodes. These lookup tables are designed using the Information Bottleneck principle of maximizing the relevant information. Unlike state-of-the-art decoders which use real valued log-likelihood ratios for decoding, the considered decoders do not process any real values, but only quantization indices. Nevertheless, they have performance extremely close to belief propagation decoding. Since hardware representation of unsigned integers is efficient and lookup table implementations have low complexity, it is reasonable to assume that the designed decoders offer advantages over their conventional counterparts in practice. In this paper, we evaluate, quantify and discuss these advantages in a practical experiment. Our focus lies on a software defined radio application, where the channel decoder is implemented on a digital signal processor. We present several implementations of the considered decoders and compare them with state-of-the-art decoders. Our results show considerable gains of the Information Bottleneck decoders in terms of bit error rate performance and net decoding throughput.

International Conference on Signal Processing and Communication Systems•Dec 1, 2018•5 citations

Decoding of Non-Binary LDPC Codes using the Information Bottleneck Method

Maximilian Stark, Gerhard Bauch, Jan Lewandowsky +1 more

Recently, a novel lookup table based decoding method for binary low-density parity-check codes has attracted considerable attention. In this approach, mutual-information-maximizing lookup tables replace the conventional operations of the variable nodes and the check nodes in message passing decoding. Moreover, the exchanged messages are represented by integers with very small bit width. A machine learning framework termed the information bottleneck method is used to design the corresponding lookup tables. In this paper, we extend this decoding principle from binary to non-binary codes. This is not a straightforward extension but requires a more sophisticated lookup table design to cope with the arithmetic in higher order Galois fields. Provided bit error rate simulations show that our proposed scheme outperforms the log-max decoding algorithm and operates close to sum-product decoding.

•May 1, 2019•9 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

Reduced-Complexity Decoding of LDPC Codes

J. Chen, Ajay Dholakia, Evangelos S. Eleftheriou +2 more

Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.

IEEE Transactions on Communications•Aug 1, 2005•952 citations
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.
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.
The Information Bottleneck method allows to construct information-optimum message passing decoders for low-density parity-check codes. In such decoders lookup tables replace the classical node operations of the variable and the check nodes. These lookup tables are designed using the Information Bottleneck principle of maximizing the relevant information. Unlike state-of-the-art decoders which use real valued log-likelihood ratios for decoding, the considered decoders do not process any real values, but only quantization indices. Nevertheless, they have performance extremely close to belief propagation decoding. Since hardware representation of unsigned integers is efficient and lookup table implementations have low complexity, it is reasonable to assume that the designed decoders offer advantages over their conventional counterparts in practice. In this paper, we evaluate, quantify and discuss these advantages in a practical experiment. Our focus lies on a software defined radio application, where the channel decoder is implemented on a digital signal processor. We present several implementations of the considered decoders and compare them with state-of-the-art decoders. Our results show considerable gains of the Information Bottleneck decoders in terms of bit error rate performance and net decoding throughput.
Recently, a novel lookup table based decoding method for binary low-density parity-check codes has attracted considerable attention. In this approach, mutual-information-maximizing lookup tables replace the conventional operations of the variable nodes and the check nodes in message passing decoding. Moreover, the exchanged messages are represented by integers with very small bit width. A machine learning framework termed the information bottleneck method is used to design the corresponding lookup tables. In this paper, we extend this decoding principle from binary to non-binary codes. This is not a straightforward extension but requires a more sophisticated lookup table design to cope with the arithmetic in higher order Galois fields. Provided bit error rate simulations show that our proposed scheme outperforms the log-max decoding algorithm and operates close to sum-product decoding.
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.
Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.