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

IEEE International Symposium on Information Theory (ISIT)

Message alignment for discrete LDPC decoders with quadrature amplitude modulation

Jan Lewandowsky, Maximilian Stark, Gerhard Bauch

Published Jun 1, 2017• 16 citations
Publisher

Abstract

Recent works describe the design of discrete decoders for low-density parity-check codes by application of mutual information maximizing clustering algorithms in discrete density evolution. In the resulting discrete message passing decoders only integers are exchanged and node operations become simple lookup operations. Earlier works only describe discrete decoders for binary modulation schemes. This paper presents a new technique called message alignment which enables to design discrete decoders for higher-order modulation schemes. First, we design a channel output quantizer for quadrature amplitude modulation with the Information Bottleneck method. The quantizer attempts to preserve the relevant information on the modulation symbols. Afterwards, we illustrate that the assignment of several bits to one modulation symbol does not allow straightforward decoder design with the available discrete density evolution technique. The proposed message alignment solves this problem. The resulting discrete decoder is compared with state-of-the-art decoders using bit error rate simulations.

DOI
10.1109/isit.2017.8007065

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

Quantization of Binary-Input Discrete Memoryless Channels, with Applications to LDPC Decoding

Brian M. Kurkoski, Hideki Yagi

Abstract—The quantization of the output of a binary-input discrete memoryless channel to a smaller number of levels is considered. The optimal quantizer, in the sense of maximizing mutual information between the channel input and the quantizer output, may be found by an algorithm with complexity which is quadratic in the number of channel outputs. This is a concave optimization problem, and results from the field of concave optimization are invoked. The quantizer design algorithm is a realization of a dynamic program. Then, this algorithm is applied to the design of message-passing decoders for low-density parity-check codes, over arbitrary discrete memoryless channels. A general, systematic method to find message-passing decoding maps which maximize mutual information at each iteration is given. This may contrasted with existing quantized message-passing algorithms which are heuristically derived. The method finds message-passing decoding maps similar to those given by Richardson and Urbanke’s Algorithm E. Using four bits per message, noise thresholds similar to belief-propagation decoding are obtained. Index Terms—discrete memoryless channel, channel quantiza-tion, mutual information maximization, LDPC decoding I.

•Jul 28, 2011•13 citations

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

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

Information-Optimum LDPC Decoders with Message Alignment for Irregular Codes

Maximilian Stark, Jan Lewandowsky, Gerhard Bauch

In practical implementations, message passing decoding of LDPC codes has to be implemented with finite precision, i.e., the messages are quantized with a small number of bits. This results in a significant performance degradation with respect to decoding with high-precision messages. Recently, we have proposed so-called information bottleneck decoders to design finite-precision decoders with error-correction performance close to high-precision belief-propagation decoding. Earlier works solely focus on the design of information bottleneck decoders for regular LDPC codes or specifically optimized irregular LDPC codes. In this paper, we extend the concept of information bottleneck decoders to irregular LDPC with arbitrary degree distribution. We show that this extension is not straightforward and requires an additional information-optimum step. Therefore, we devise a novel intermediate construction step which we call message alignment. Exemplary numerical simulations using an irregular LDPC code taken from the IEEE 802.11 standard show that incorporating message alignment in the construction yields a 4-bit information bottleneck decoder which performs only 0.15 dB worse than a double-precision belief propagation decoder and outperforms a min-sum decoder.

Globecom•Dec 1, 2018•21 citations

Decoding LDPC codes with mutual information-maximizing lookup tables

Francisco Javier Cuadros Romero, Brian M. Kurkoski

A recent result has shown connections between statistical learning theory and channel quantization. In this paper, we present a practical application of this result to the implementation of LDPC decoders. In particular, we describe a technique for designing the message-passing decoder mappings (or lookup tables) based on the ideas of channel quantization. This technique is not derived from sum-product algorithm or any other LDPC decoding algorithm. Instead, the proposed algorithm is based on an optimal quantizer in the sense of maximization of mutual information, which is inserted in the density evolution algorithm to generate the lookup tables. This algorithm has low complexity since it only employs 3-bit messages and lookup tables, which can be easily implemented in hardware. Two quantized versions of the min-sum decoding algorithm are used for comparison. Simulation results for a binary-input AWGN channel show 0.3 dB and 1.2 dB gains versus the two quantized min-sum algorithms. On the binary symmetric channel also a gain is seen.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•35 citations
Recent works describe the design of discrete decoders for low-density parity-check codes by application of mutual information maximizing clustering algorithms in discrete density evolution. In the resulting discrete message passing decoders only integers are exchanged and node operations become simple lookup operations. Earlier works only describe discrete decoders for binary modulation schemes. This paper presents a new technique called message alignment which enables to design discrete decoders for higher-order modulation schemes. First, we design a channel output quantizer for quadrature amplitude modulation with the Information Bottleneck method. The quantizer attempts to preserve the relevant information on the modulation symbols. Afterwards, we illustrate that the assignment of several bits to one modulation symbol does not allow straightforward decoder design with the available discrete density evolution technique. The proposed message alignment solves this problem. The resulting discrete decoder is compared with state-of-the-art decoders using bit error rate simulations.
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.
Abstract—The quantization of the output of a binary-input discrete memoryless channel to a smaller number of levels is considered. The optimal quantizer, in the sense of maximizing mutual information between the channel input and the quantizer output, may be found by an algorithm with complexity which is quadratic in the number of channel outputs. This is a concave optimization problem, and results from the field of concave optimization are invoked. The quantizer design algorithm is a realization of a dynamic program. Then, this algorithm is applied to the design of message-passing decoders for low-density parity-check codes, over arbitrary discrete memoryless channels. A general, systematic method to find message-passing decoding maps which maximize mutual information at each iteration is given. This may contrasted with existing quantized message-passing algorithms which are heuristically derived. The method finds message-passing decoding maps similar to those given by Richardson and Urbanke’s Algorithm E. Using four bits per message, noise thresholds similar to belief-propagation decoding are obtained. Index Terms—discrete memoryless channel, channel quantiza-tion, mutual information maximization, LDPC decoding I.
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.
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.
In practical implementations, message passing decoding of LDPC codes has to be implemented with finite precision, i.e., the messages are quantized with a small number of bits. This results in a significant performance degradation with respect to decoding with high-precision messages. Recently, we have proposed so-called information bottleneck decoders to design finite-precision decoders with error-correction performance close to high-precision belief-propagation decoding. Earlier works solely focus on the design of information bottleneck decoders for regular LDPC codes or specifically optimized irregular LDPC codes. In this paper, we extend the concept of information bottleneck decoders to irregular LDPC with arbitrary degree distribution. We show that this extension is not straightforward and requires an additional information-optimum step. Therefore, we devise a novel intermediate construction step which we call message alignment. Exemplary numerical simulations using an irregular LDPC code taken from the IEEE 802.11 standard show that incorporating message alignment in the construction yields a 4-bit information bottleneck decoder which performs only 0.15 dB worse than a double-precision belief propagation decoder and outperforms a min-sum decoder.
A recent result has shown connections between statistical learning theory and channel quantization. In this paper, we present a practical application of this result to the implementation of LDPC decoders. In particular, we describe a technique for designing the message-passing decoder mappings (or lookup tables) based on the ideas of channel quantization. This technique is not derived from sum-product algorithm or any other LDPC decoding algorithm. Instead, the proposed algorithm is based on an optimal quantizer in the sense of maximization of mutual information, which is inserted in the density evolution algorithm to generate the lookup tables. This algorithm has low complexity since it only employs 3-bit messages and lookup tables, which can be easily implemented in hardware. Two quantized versions of the min-sum decoding algorithm are used for comparison. Simulation results for a binary-input AWGN channel show 0.3 dB and 1.2 dB gains versus the two quantized min-sum algorithms. On the binary symmetric channel also a gain is seen.