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 Transactions on Information Theory

One-step majority-logic decoding with symbol reliability information (Corresp.)

C.-E.W. Sundberg

Published Mar 1, 1975• 12 citations
Publisher

Abstract

A method of using reliability information in one-step majority-logic decoders is presented. The idea is, basically, that the received binary digits are corrected in an order such that the least reliable digit is first corrected. With this method the error correction capability of the decoder is extended for large signal-to-noise ratios (SNR's). Different decoding algorithms are used when the number of orthogonal parity-check sums are even and odd, respectively. Computer simulations are presented for some short codes with binary antipodal signals on the additive white Gaussian noise channel.

DOI
10.1109/tit.1975.1055345

Related papers

Near Optimum Majority-Logic Based Decoding of Low-Density Parity-Check Codes

Telex M. N. Ngatched, Attahiru Sule Alfa, Jun Cai

A reliability-based iterative majority-logic decoding algorithm for regular low-density parity-check (LDPC) codes was recently proposed by Huang et al. In this paper we present an improved version of that algorithm by introducing a different reliability measure for each check-sum of the parity-check matrix, and taking it into account in the computation of the extrinsic information that is used to update the reliability measure of each received bit in each iteration. Some simulations results are given, which show that the new algorithm, while requiring very little additional computational complexity, not only achieves a considerable error performance gain over the standard one, but also, importantly, outperforms the iterative decoding based on belief propagation (IDBP), especially for short and medium block length finite-geometry (FG) LDPC codes.

International Conference on Communications•Jun 1, 2011•3 citations

On the reliability-order-based decoding algorithms for binary linear block codes

Yuansheng Tang, San Ling, Fang‐Wei Fu

In this correspondence, we consider the decoding of binary block codes over the additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) signaling. By a reliability-order-based decoding algorithm (ROBDA), we mean a soft-decision decoding algorithm which decodes to the best (most likely) codeword of the form that is the sum of the hard-decision tuple and an error pattern in a set determined only by the order of the reliabilities of the hard decisions. Examples of ROBDAs include many well-known decoding algorithms, such as the generalized-minimum-distance (GMD) decoding algorithm, Chase decoding algorithms, and the reliability-based decoding algorithms proposed by Fossorier and Lin. It is known that the squared error-correction-radii of ROBDAs can be computed from the minimal squared Euclidean distances (MSEDs) between the all-one sequence and the polyhedra corresponding to the error patterns. For the computation of such MSEDs, we give a new method which is more compact than the one proposed by Fossorier and Lin. These results are further used to show that any bounded-distance ROBDA is asymptotically optimal: The ratio between the probability of decoding error of a bounded-distance ROBDA and that of the maximum-likelihood (ML) decoding approaches 1 when the signal-to-noise ratio (SNR) approaches infinity, provided that the minimum Hamming distance of the code is greater than 2.

IEEE Transactions on Information Theory•Dec 28, 2005•8 citations

Attenuated iterative reliability-based decoding algorithm for LDPC codes

Minghua Liu, Lijun Zhang

An attenuated iterative reliability-based majority-logic (AIML) decoding algorithm for low-density parity-check (LDPC) codes is proposed. This novel algorithm is devised based on the orthogonal check-sums of the one-step majority-logic decoding algorithm in conjunction with certain of reliability measures of the received symbols. The computation of reliability measure of the syndrome sum is refined by introducing an attenuation factor. Simulation results show that in binary input-additive white Gaussian noise channel, the AIML algorithm outperforms other popular iterative reliability-based majority-logic decoding algorithms with a slight increase in computational complexity. With maximum iterations five and fifty, the AIML algorithm can achieve almost identical error performance for LDPC codes. No error floor effect can be observed for AIML algorithm down to the bit error rate (BER) of 10−8, while error floor appears for sum product algorithm (SPA) around the BER of 10−7even with maximum iteration 100. The inherent feature of parallel decoding for AIML algorithm enforces the decoding speed in contrast to those serial decoding schemes, such as weighted bit-flipping algorithm.

International Conference on Information Science and Engineering•Dec 1, 2010•0 citations

One-step weighted-majority decoding (Corresp.)

L. Rudolph, Woodrow E. Robbins

It is shown that any decoding function for a linear binary code can be realized as a weighted majority of nonorthogonal parity checks. An example is given of a four-error-correcting code that is neither L-step orthogonalizable nor one-step majority decodable using non-orthogonal parity checks and yet is one-step weighted-majority decodable using only ten nonorthogonal parity checks.

IEEE Transactions on Information Theory•May 1, 1972•9 citations

Efficient decoder design for error correcting codes

Chenrong Xiong

Error correctiong codes (ECC) are widly used in applications to correct errors in data transmission over unreliable or noisy communication channels. Recently, two kinds of promising codes attracted lots of research interest because they provide excellent error correction performance. One is non-binary LDPC codes, and the other is polar codes. This dissertation focuses on efficient decoding algorithms and decoder design for thesetwo types of codes.Non-binary low-density parity-check (LDPC) codes have some advantages over their binary counterparts, but unfortunately their decoding complexity is a significant challenge. The iterative hard- and soft-reliability based majority-logic decoding algorithms are attractive for non-binary LDPC codes, since they involve only finite field additions and multiplications as well as integer operations and hence have significantly lower complexity than other algorithms. We propose two improvements to the majority-logic decoding algorithms. Instead of the accumulation of reliability information in the ex-isting majority-logic decoding algorithms, our first improvement is a new reliability information update. The new update not only results in better error performance and fewer iterations on average, but also further reduces computational complexity. Since existing majority-logic decoding algorithms tend to have a high error floor for codes whose parity check matrices have low column weights, our second improvement is a re-selection scheme, which leads to much lower error floors, at the expense of more finite field operations and integer operations, by identifying periodic points, re-selectingintermediate hard decisions, and changing reliability information.Polar codes are of great interests because they provably achieve the symmetric capacity of discrete memoryless channels with arbitrary input alphabet sizes an explicit construction. Most existing decoding algorithms of polar codes are based on bit-wise hard or soft decisions. We propose symbol-decision successive cancellation (SC) and successive cancellation list (SCL) decoders for polar codes, which use symbol-wise hard or soft decisions for higher throughput or better error performance. Then wepropose to use a recursive channel combination to calculate symbol-wise channel transition probabilities, which lead to symbol decisions. Our proposed recursive channel combination has lower complexity than simply combining bit-wise channel transition probabilities. The similarity between our proposed method and Arıkan's channel transformations also helps to share hardware resources between calculating bit- and symbol-wise channel transition probabilities. To reduce the complexity of the list pruning, atwo-stage list pruning network is proposed to provide a trade-off between the error performance and the complexity of the symbol-decision SCL decoder. Since memory is a significant part of SCL decoders, we also propose a pre-computation memory-saving technique to reduce memory requirement of an SCL decoder.To reduce the complexity of the recursive channel combination further, we propose an approximate ML (AML) decoding unit for SCL decoders. In particular, we investigate the distribution of frozen bits of polar codes designed for both the binary erasure and additive white Gaussian noise channels, and take advantage of the distribution to reduce the complexity of the AML decoding unit, improving the throughput-area efficiency of SCL decoders.Furthermore, to adapt to variable throughput or latency requirements which exist widely in current communication applications, a multi-mode SCL decoder with variable list sizes and parallelism is proposed. If high throughput or small latency is required, the decoder decodes multiple received words in parallel with a small list size. However, if error performance is of higher priority, the multi-mode decoder switches to a serialmode with a bigger list size. Therefore, the multi-mode SCL decoder provides a flexible tradeoff between latency, throughput and error performance at the expense of small overhead.

•May 1, 2016•0 citations

Further results on majority-logic decoding of product codes (Corresp.)

Nguyen Quang Đuc, L.V. Skattebol

In this correspondence additional results on majority-logic decoding of product codes are presented. If one of the component codes is decodable using Rudolph's nonorthogonal algorithm, and the other using Reed-Massey'sL-step orthogonalization, then the resulting product code is majority-logic decodable inLsteps, where nonorthogonal checks are used in the first step and orthogonal checks in the remaining steps. If the component codes are both decodable using Rudolph's algorithm, the product code is majority-logic decodable using the same procedure.

IEEE Transactions on Information Theory•Mar 1, 1972•1 citation
A method of using reliability information in one-step majority-logic decoders is presented. The idea is, basically, that the received binary digits are corrected in an order such that the least reliable digit is first corrected. With this method the error correction capability of the decoder is extended for large signal-to-noise ratios (SNR's). Different decoding algorithms are used when the number of orthogonal parity-check sums are even and odd, respectively. Computer simulations are presented for some short codes with binary antipodal signals on the additive white Gaussian noise channel.
A reliability-based iterative majority-logic decoding algorithm for regular low-density parity-check (LDPC) codes was recently proposed by Huang et al. In this paper we present an improved version of that algorithm by introducing a different reliability measure for each check-sum of the parity-check matrix, and taking it into account in the computation of the extrinsic information that is used to update the reliability measure of each received bit in each iteration. Some simulations results are given, which show that the new algorithm, while requiring very little additional computational complexity, not only achieves a considerable error performance gain over the standard one, but also, importantly, outperforms the iterative decoding based on belief propagation (IDBP), especially for short and medium block length finite-geometry (FG) LDPC codes.
In this correspondence, we consider the decoding of binary block codes over the additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) signaling. By a reliability-order-based decoding algorithm (ROBDA), we mean a soft-decision decoding algorithm which decodes to the best (most likely) codeword of the form that is the sum of the hard-decision tuple and an error pattern in a set determined only by the order of the reliabilities of the hard decisions. Examples of ROBDAs include many well-known decoding algorithms, such as the generalized-minimum-distance (GMD) decoding algorithm, Chase decoding algorithms, and the reliability-based decoding algorithms proposed by Fossorier and Lin. It is known that the squared error-correction-radii of ROBDAs can be computed from the minimal squared Euclidean distances (MSEDs) between the all-one sequence and the polyhedra corresponding to the error patterns. For the computation of such MSEDs, we give a new method which is more compact than the one proposed by Fossorier and Lin. These results are further used to show that any bounded-distance ROBDA is asymptotically optimal: The ratio between the probability of decoding error of a bounded-distance ROBDA and that of the maximum-likelihood (ML) decoding approaches 1 when the signal-to-noise ratio (SNR) approaches infinity, provided that the minimum Hamming distance of the code is greater than 2.
An attenuated iterative reliability-based majority-logic (AIML) decoding algorithm for low-density parity-check (LDPC) codes is proposed. This novel algorithm is devised based on the orthogonal check-sums of the one-step majority-logic decoding algorithm in conjunction with certain of reliability measures of the received symbols. The computation of reliability measure of the syndrome sum is refined by introducing an attenuation factor. Simulation results show that in binary input-additive white Gaussian noise channel, the AIML algorithm outperforms other popular iterative reliability-based majority-logic decoding algorithms with a slight increase in computational complexity. With maximum iterations five and fifty, the AIML algorithm can achieve almost identical error performance for LDPC codes. No error floor effect can be observed for AIML algorithm down to the bit error rate (BER) of 10−8, while error floor appears for sum product algorithm (SPA) around the BER of 10−7even with maximum iteration 100. The inherent feature of parallel decoding for AIML algorithm enforces the decoding speed in contrast to those serial decoding schemes, such as weighted bit-flipping algorithm.
Error correctiong codes (ECC) are widly used in applications to correct errors in data transmission over unreliable or noisy communication channels. Recently, two kinds of promising codes attracted lots of research interest because they provide excellent error correction performance. One is non-binary LDPC codes, and the other is polar codes. This dissertation focuses on efficient decoding algorithms and decoder design for thesetwo types of codes.Non-binary low-density parity-check (LDPC) codes have some advantages over their binary counterparts, but unfortunately their decoding complexity is a significant challenge. The iterative hard- and soft-reliability based majority-logic decoding algorithms are attractive for non-binary LDPC codes, since they involve only finite field additions and multiplications as well as integer operations and hence have significantly lower complexity than other algorithms. We propose two improvements to the majority-logic decoding algorithms. Instead of the accumulation of reliability information in the ex-isting majority-logic decoding algorithms, our first improvement is a new reliability information update. The new update not only results in better error performance and fewer iterations on average, but also further reduces computational complexity. Since existing majority-logic decoding algorithms tend to have a high error floor for codes whose parity check matrices have low column weights, our second improvement is a re-selection scheme, which leads to much lower error floors, at the expense of more finite field operations and integer operations, by identifying periodic points, re-selectingintermediate hard decisions, and changing reliability information.Polar codes are of great interests because they provably achieve the symmetric capacity of discrete memoryless channels with arbitrary input alphabet sizes an explicit construction. Most existing decoding algorithms of polar codes are based on bit-wise hard or soft decisions. We propose symbol-decision successive cancellation (SC) and successive cancellation list (SCL) decoders for polar codes, which use symbol-wise hard or soft decisions for higher throughput or better error performance. Then wepropose to use a recursive channel combination to calculate symbol-wise channel transition probabilities, which lead to symbol decisions. Our proposed recursive channel combination has lower complexity than simply combining bit-wise channel transition probabilities. The similarity between our proposed method and Arıkan's channel transformations also helps to share hardware resources between calculating bit- and symbol-wise channel transition probabilities. To reduce the complexity of the list pruning, atwo-stage list pruning network is proposed to provide a trade-off between the error performance and the complexity of the symbol-decision SCL decoder. Since memory is a significant part of SCL decoders, we also propose a pre-computation memory-saving technique to reduce memory requirement of an SCL decoder.To reduce the complexity of the recursive channel combination further, we propose an approximate ML (AML) decoding unit for SCL decoders. In particular, we investigate the distribution of frozen bits of polar codes designed for both the binary erasure and additive white Gaussian noise channels, and take advantage of the distribution to reduce the complexity of the AML decoding unit, improving the throughput-area efficiency of SCL decoders.Furthermore, to adapt to variable throughput or latency requirements which exist widely in current communication applications, a multi-mode SCL decoder with variable list sizes and parallelism is proposed. If high throughput or small latency is required, the decoder decodes multiple received words in parallel with a small list size. However, if error performance is of higher priority, the multi-mode decoder switches to a serialmode with a bigger list size. Therefore, the multi-mode SCL decoder provides a flexible tradeoff between latency, throughput and error performance at the expense of small overhead.
In this correspondence additional results on majority-logic decoding of product codes are presented. If one of the component codes is decodable using Rudolph's nonorthogonal algorithm, and the other using Reed-Massey'sL-step orthogonalization, then the resulting product code is majority-logic decodable inLsteps, where nonorthogonal checks are used in the first step and orthogonal checks in the remaining steps. If the component codes are both decodable using Rudolph's algorithm, the product code is majority-logic decodable using the same procedure.