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)

Bounded-distance soft decision decoding of binary product codes

Ofer Amrani, Yair Be'ery

Published Nov 7, 2002• 6 citations
Publisher

Abstract

A two-step sub-optimal algorithm for decoding binary product codes is discussed. This algorithm realizes at least half the minimum Euclidean distance of the code. The fundamental geometric properties associated with the algorithm are investigated, and bounds on the number of nearest neighbors are derived. This investigation also results with an improved algorithm which achieves the minimum effective error coefficient, the number of minimum-weight codewords in the product code.

DOI
10.1109/isit.2000.866375

Related papers

Study on Iterative Soft-Decision Decoding Algorithms for Binary Linear Block Codes

卓也 甲本

For iterative soft-decision decoding algorithms for binary linear block codes, error performance and computational complexity are very important factors.In this thesis, suÆcient conditions of the optimality of decoded codeword and a suÆcient condition which is used for ruling-out some useless iterations of bounded distance decoding which reduces the computational complexity of iterative soft-decision decoding algorithms are shown.New iterative soft-decision decoding algorithms which uses the suÆcient conditions of the optimality of decoded codeword to achievegood error performance with small computational complexity are also shown.First, the suÆcient conditions are derived based on: (1) partial knowledge of the distance pro le of the code, and (2) previously generated candidate codewords.When the numberof previously generated candidate codewords is greater than 1, the conditions presented here are less stringent than those derived by Taipale and Pursley [4] and Kaneko et.al.[5].The condition based on three previously generated candidate codewords is the rst such s u Æ c i e n t condition that has ever been derived.It is shown by computer simulation that these suÆcient condions reduce the computational complexity of iterative decoding algorithms without degradation of error performance.Second, a suÆcient condition to rule-out some useless test error patterns is derived.In an iterative decoding algorithm, such as Chase Type-II decoding algorithm[2] and its improved versions, candidate codewords for a received vector are generated

•Mar 24, 1999•1 citation

A bounded-distance decoding algorithm for binary linear block codes achieving the minimum effective error coefficient

Ba-Zhong Shen, Kenneth K. Tzeng, Chun Wang

A new bounded-distance (BD) decoding algorithm is presented for binary linear (n, k, d) block codes on additive white Gaussian noise channels. The algorithm is based on the generalized minimum distance (GMD) decoding algorithm of Forney (1989) using the acceptance criterion of Taipale and Pursley (GMD/TP) proposed in 1991. It is shown that the GMD/TP decoding algorithm is a BD decoding algorithm with effective error coefficient (/sup n//sub d/). It is also shown that the decision regions of GMD/TP are good inner approximations of those of full GMD decoding, and therefore full GMD decoding is BD and has an effective error coefficient that is well approximated by (/sup n//sub d/). Moreover, by adding a d-erasure-correction step to GMD decoding, the effective error coefficient can be reduced to A/sub d/, the number of minimum-weight codewords, which is the same as the effective error coefficient of maximum-likelihood decoding. The decoding algorithm is mainly based on algebraic errors-and-erasures decoding and therefore has polynomial rather than exponential complexity.

IEEE Transactions on Information Theory•Jan 1, 1996•15 citations

An Iterative Soft-Decision Decoding Algorithm

Shu Wen Lin, Takuya Koumoto, Toyoo Takata +1 more

This paper presents a new minimum-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. Simulation results for the RM(64,22), EBCH(64,24), RM(64,42) and EBCH(64,45) codes show that the proposed decoding algorithm achieves practically (or near) optimal error performance with significant reduction in decoding computational complexity. The average number of search iterations is also small even for low signal-to-noise ratio.

•Jul 10, 1996•7 citations

On iterative soft-decision decoding of linear binary block codes and product codes

R. Lucas, Martin Bossert, Markus Breitbach

Iterative decoding methods have gained interest, initiated by the results of the so-called "turbo" codes. The theoretical description of this decoding, however, seems to be difficult. Therefore, we study the iterative decoding of block codes. First, we discuss the iterative decoding algorithms developed by Gallager (1962), Battail et al. (1979), and Hagenauer et al. (1996). Based on their results, we propose a decoding algorithm which only uses parity check vectors of minimum weight. We give the relation of this iterative decoding to one-step majority-logic decoding, and interpret it as gradient optimization. It is shown that the used parity check set defines the region where the iterative decoding decides on a particular codeword. We make plausible that, in almost all cases, the iterative decoding converges to a codeword after some iterations. We derive a computationally efficient implementation using the minimal trellis representing the used parity check set. Simulations illustrate that our algorithm gives results close to soft decision maximum likelihood (SDML) decoding for many code classes like BCH codes. Reed-Muller codes, quadratic residue codes, double circulant codes, and cyclic finite geometry codes. We also present simulation results for product codes and parallel concatenated codes based on block codes.

IEEE Journal on Selected Areas in Communications•Jan 1, 1998•100 citations

Hard- and soft-decision decoding beyond the half minimum distance---An algorithm for linear codes (Corresp.)

Martin Bossert, F. Hergert

A decoding algorithm for linear codes that uses the minimum weight words of the dual code as parity checks is defined. This algorithm is able to correct beyond the half minimum distance and has the capability of including soft-decision decoding. Results on applying this algorithm to quadratic residue (QR) codes, BCH codes, and the Golay codes (with and without soft-decision decoding) are presented.

IEEE Transactions on Information Theory•Sep 1, 1986•38 citations

A Soft-Input Soft-Output Decoding Algorithm for LDPC Codes

Lixin Wang

A new soft-input,soft-output algorithm for decoding LDPC codes is described in this paper.Using soft squared Euclidean distance as the metric,the algorithm realizes decoding by iterating the antilog-sum of the Euclidean distance.A simplified algorithm is also put forward to reduce computational complexity.The proposed algorithm does not require knowledge of the signal-to-noise ratio of the received signal and is less complex to implement than other soft decision algorithms.The results of simulation show that the performance is very close to that of sum-product algorithm while the computational complexity is sharply reduced.

Journal of Spacecraft TT&C Technology•Jan 1, 2011•0 citations
A two-step sub-optimal algorithm for decoding binary product codes is discussed. This algorithm realizes at least half the minimum Euclidean distance of the code. The fundamental geometric properties associated with the algorithm are investigated, and bounds on the number of nearest neighbors are derived. This investigation also results with an improved algorithm which achieves the minimum effective error coefficient, the number of minimum-weight codewords in the product code.
For iterative soft-decision decoding algorithms for binary linear block codes, error performance and computational complexity are very important factors.In this thesis, suÆcient conditions of the optimality of decoded codeword and a suÆcient condition which is used for ruling-out some useless iterations of bounded distance decoding which reduces the computational complexity of iterative soft-decision decoding algorithms are shown.New iterative soft-decision decoding algorithms which uses the suÆcient conditions of the optimality of decoded codeword to achievegood error performance with small computational complexity are also shown.First, the suÆcient conditions are derived based on: (1) partial knowledge of the distance pro le of the code, and (2) previously generated candidate codewords.When the numberof previously generated candidate codewords is greater than 1, the conditions presented here are less stringent than those derived by Taipale and Pursley [4] and Kaneko et.al.[5].The condition based on three previously generated candidate codewords is the rst such s u Æ c i e n t condition that has ever been derived.It is shown by computer simulation that these suÆcient condions reduce the computational complexity of iterative decoding algorithms without degradation of error performance.Second, a suÆcient condition to rule-out some useless test error patterns is derived.In an iterative decoding algorithm, such as Chase Type-II decoding algorithm[2] and its improved versions, candidate codewords for a received vector are generated
A new bounded-distance (BD) decoding algorithm is presented for binary linear (n, k, d) block codes on additive white Gaussian noise channels. The algorithm is based on the generalized minimum distance (GMD) decoding algorithm of Forney (1989) using the acceptance criterion of Taipale and Pursley (GMD/TP) proposed in 1991. It is shown that the GMD/TP decoding algorithm is a BD decoding algorithm with effective error coefficient (/sup n//sub d/). It is also shown that the decision regions of GMD/TP are good inner approximations of those of full GMD decoding, and therefore full GMD decoding is BD and has an effective error coefficient that is well approximated by (/sup n//sub d/). Moreover, by adding a d-erasure-correction step to GMD decoding, the effective error coefficient can be reduced to A/sub d/, the number of minimum-weight codewords, which is the same as the effective error coefficient of maximum-likelihood decoding. The decoding algorithm is mainly based on algebraic errors-and-erasures decoding and therefore has polynomial rather than exponential complexity.
Iterative decoding methods have gained interest, initiated by the results of the so-called "turbo" codes. The theoretical description of this decoding, however, seems to be difficult. Therefore, we study the iterative decoding of block codes. First, we discuss the iterative decoding algorithms developed by Gallager (1962), Battail et al. (1979), and Hagenauer et al. (1996). Based on their results, we propose a decoding algorithm which only uses parity check vectors of minimum weight. We give the relation of this iterative decoding to one-step majority-logic decoding, and interpret it as gradient optimization. It is shown that the used parity check set defines the region where the iterative decoding decides on a particular codeword. We make plausible that, in almost all cases, the iterative decoding converges to a codeword after some iterations. We derive a computationally efficient implementation using the minimal trellis representing the used parity check set. Simulations illustrate that our algorithm gives results close to soft decision maximum likelihood (SDML) decoding for many code classes like BCH codes. Reed-Muller codes, quadratic residue codes, double circulant codes, and cyclic finite geometry codes. We also present simulation results for product codes and parallel concatenated codes based on block codes.
A new soft-input,soft-output algorithm for decoding LDPC codes is described in this paper.Using soft squared Euclidean distance as the metric,the algorithm realizes decoding by iterating the antilog-sum of the Euclidean distance.A simplified algorithm is also put forward to reduce computational complexity.The proposed algorithm does not require knowledge of the signal-to-noise ratio of the received signal and is less complex to implement than other soft decision algorithms.The results of simulation show that the performance is very close to that of sum-product algorithm while the computational complexity is sharply reduced.