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

Electronic Notes in Discrete Mathematics

Reliability-Based Soft-Decision Decoding with Iterative Information Set Reduction

M.P.C. Fossorier

Published Apr 1, 2001• 0 citations
Publisher
DOI
10.1016/s1571-0653(04)00187-8

Related papers

An Iterative Soft-Decision Decoding Algorithm

Takuya Koumoto

•Mar 22, 1996•0 citations

Adaptive Soft-Decision Iterative Decoding Using Edge Local Complementation

Joakim Grahl Knudsen, Constanza Riera, Matthew Geoffrey Parker +1 more

Lecture notes in computer science•Aug 25, 2008•3 citations

Reliability-based soft-decision decoding with iterative information set reduction

M.P.C. Fossorier

The reliability-based decoding approach using the reprocessing of the most reliable information set only is extended into the iterative reprocessing of several information sets. At the end of each information set reprocessing, some information bits are delivered by the decoder. Consequently, information sets with decreasing cardinality values are considered at each iteration. A tight upper bound on the error performance achieved by this new method is derived. Compared to previously proposed competitive approaches, this new method reduces the number of candidate codewords needed to achieve practically optimum decoding. Importantly, it also preserves the very simple structured implementation of the order statistic decoding.

IEEE Transactions on Information Theory•Dec 1, 2002•51 citations

On Decoding Using Codewords of the Dual Code

Martin Bossert

We present novel decoding schemes for hard and soft decision decoding of block codes using the minimal weight codewords of the dual code. The decoding schemes will be described for cyclic codes where polynomials can be used, however, the modification for non-cyclic codes is possible and straight forward. The hard decision decoding calculates syndrome polynomials which are the product of the received polynomial with dual codewords. Proper cyclic shifts of these syndrome polynomials are obtained and the non-zero positions are counted componentwise for these shifts. The values of this counting are a reliability measure and can be used for locating the error and also the non-error positions. This reliability measure is the basis for various variants of hard decision decoding algorithms. Decoding schemes with iterative error reduction are possible as well as information set decoding using the inherent reliability information of the measure even if there is no reliability information from the channel. Further, we will show how reliability information from the channel can be included in order to obtain soft decision decoding schemes. We derive the relation between bit flipping, believe propagation, and majority logic decoding to the novel schemes. As examples to illustrate the functioning we use BCH and Reed-Muller codes as examples for binary codes, and RS codes for non-binary codes. Besides the Plotkin construction we recall a known result that Reed-Muller codes punctured by one position are cyclic and thus, are equivalent to special cases of BCH codes. Simulation results for hard and soft decision decoding will be given for several examples and compared with results from literature. Finally, we analyze the soft decision decoding of the Plotkin construction and derive that one of the two codes uses a $3$ dB better channel (also known as channel polarization).

arXiv:2001.02956•Jan 9, 2020•9 citations

Soft-Decision Minimum-Distance Decoding

Patrick Guy Farrell

Springer eBooks•Jan 1, 1978•2 citations

An efficient information set algorithm for soft-decision decoding of linear block codes

Dulte José de Barros, B.G. Dorsch

This paper presents an approach to soft-decision decoding for a (n, k) binary linear block code. This approach achieves near-optimal to optimal performance for any signal-to-noise ratio value. The proposed decoding is based on the reordering of the received symbols according to their reliability measure and can be applied to any binary linear code. The basic idea is to generate a sequence of codewords such that there will be a high probability that the next codeword is closer to the received vector. In this algorithm the information provided by the soft-decisions is used to generate information sets utilized in decoding. A fast procedure checks whether a given set of k positions is an information set. A sequence of codewords is reconstructed using a sequence of information sets. Each codeword reconstructed is compared with the received word and the closest one is selected. Hence, the decoding algorithm is an iterative procedure designed to enhance the performance of the usual soft-decision decoding, since with each iteration of the procedure, real vectors successively closer to the received vector are examined. A high performance stop rule is utilized to reduce the number of generated information sets, stopping the decoding process when a codeword is closest to the received sequence.

IEEE International Symposium on Information Theory (ISIT)•Nov 22, 2002•1 citation
The reliability-based decoding approach using the reprocessing of the most reliable information set only is extended into the iterative reprocessing of several information sets. At the end of each information set reprocessing, some information bits are delivered by the decoder. Consequently, information sets with decreasing cardinality values are considered at each iteration. A tight upper bound on the error performance achieved by this new method is derived. Compared to previously proposed competitive approaches, this new method reduces the number of candidate codewords needed to achieve practically optimum decoding. Importantly, it also preserves the very simple structured implementation of the order statistic decoding.
We present novel decoding schemes for hard and soft decision decoding of block codes using the minimal weight codewords of the dual code. The decoding schemes will be described for cyclic codes where polynomials can be used, however, the modification for non-cyclic codes is possible and straight forward. The hard decision decoding calculates syndrome polynomials which are the product of the received polynomial with dual codewords. Proper cyclic shifts of these syndrome polynomials are obtained and the non-zero positions are counted componentwise for these shifts. The values of this counting are a reliability measure and can be used for locating the error and also the non-error positions. This reliability measure is the basis for various variants of hard decision decoding algorithms. Decoding schemes with iterative error reduction are possible as well as information set decoding using the inherent reliability information of the measure even if there is no reliability information from the channel. Further, we will show how reliability information from the channel can be included in order to obtain soft decision decoding schemes. We derive the relation between bit flipping, believe propagation, and majority logic decoding to the novel schemes. As examples to illustrate the functioning we use BCH and Reed-Muller codes as examples for binary codes, and RS codes for non-binary codes. Besides the Plotkin construction we recall a known result that Reed-Muller codes punctured by one position are cyclic and thus, are equivalent to special cases of BCH codes. Simulation results for hard and soft decision decoding will be given for several examples and compared with results from literature. Finally, we analyze the soft decision decoding of the Plotkin construction and derive that one of the two codes uses a 333 dB better channel (also known as channel polarization).
This paper presents an approach to soft-decision decoding for a (n, k) binary linear block code. This approach achieves near-optimal to optimal performance for any signal-to-noise ratio value. The proposed decoding is based on the reordering of the received symbols according to their reliability measure and can be applied to any binary linear code. The basic idea is to generate a sequence of codewords such that there will be a high probability that the next codeword is closer to the received vector. In this algorithm the information provided by the soft-decisions is used to generate information sets utilized in decoding. A fast procedure checks whether a given set of k positions is an information set. A sequence of codewords is reconstructed using a sequence of information sets. Each codeword reconstructed is compared with the received word and the closest one is selected. Hence, the decoding algorithm is an iterative procedure designed to enhance the performance of the usual soft-decision decoding, since with each iteration of the procedure, real vectors successively closer to the received vector are examined. A high performance stop rule is utilized to reduce the number of generated information sets, stopping the decoding process when a codeword is closest to the received sequence.