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

How often is hard-decision decoding enough?

Peter F. Swaszek, W. Jones

Published May 1, 1998• 15 citations
Publisher

Abstract

The problem of decoding binary linear block codes has received much attention; the two extremes are optimal, high-complexity soft-decision (or maximum-likelihood) decoding and lower performance, much lower complexity hard-decision (or algebraic) decoding. This article considers a class of decoders which first implements hard-decision decoding; second, tests to see if that is enough, that its result matches the result of soft-decision decoding; and third, continues to search if a match is not found. The advantage of such a testing procedure is that if the hard-decision decoding result is found to be enough (called a success for the test), then the computational effort expended by the decoder is low. The performance, as measured by the probability of a success, of a variety of simple tests of the hard-decision codeword are analyzed.

DOI
10.1109/18.669278

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

On maximum likelihood soft-decision decoding of binary linear codes

N.J.C. Lous, P.A.H. Bours, Henk C. A. van Tilborg

Two new implementations of a maximum-likelihood soft-decision decoding algorithm for binary linear codes are derived. Instead of checking only error patterns yielding a codeword when added to the rounded-off version of the received vector, these implementations principally consider all possible column patterns. Compared to known implementations, this allows a more efficient use of branching and bounding techniques.>

IEEE Transactions on Information Theory•Jan 1, 1993•28 citations

Decoding of linear block codes based on ordered statistics

M.P.C. Fossorier

This dissertation presents a novel approach to soft decision decoding for binary linear block codes. The basic idea of this approach is to achieve a desired error performance progressively in a number of stages. For each decoding stage, the error performance is highly bounded and the decoding is terminated at the stage where either near-optimum error performance or a desired level of error performance is achieved. As a result, more flexibility in the trade-off between performance and decoding complexity is provided. The proposed decoding is based on the reordering of the received symbols according to their reliability measure. In the dissertation, we evaluate the statistics of the noise after ordering. Based on these statistics, we derive two monotonic properties which dictate the reprocessing strategy. Each codeword is decoded in two steps: (1) hard-decision decoding based on reliability information and (2) reprocessing of the hard-decision decoded codeword in successive stages until the desired performance is achieved. The reprocessing is based on the monotonic properties of the ordering and is carried out using a cost function. A new resource test highly related to the reprocessing strategy is introduced to reduce the number of computations for each reprocessing stage. For short codes of lengths N ≤ 32 or medium codes with 32 < N ≤ 64 with rate R ≥ 0.6, near-optimum bit error performance is achieved in two stages of reprocessing with at most a computation complexity of o(K2) constructed code-words, where K is the dimension of the code. For longer codes, three or more reprocessing stages are required to achieve near-optimum decoding. However, most of the coding gain is obtained within the first two reprocessing stages for error performances of practical interest. The proposed decoding algorithm applies to any binary linear code, does not require any data storage and is well suitable for parallel processing. Furthermore, the maximum number of computations required at each reprocessing stage is fixed, which prevents buffer overflow at low SNR. Further reductions of the number of computations based on probabilistic or decomposable properties of the code considered are also investigated. The generalization of the algorithm to other channels is discussed. Finally, the discrete time channel associated with the AWGN model after ordering is greatly simplified. This simplification allows an important reduction of the number of computations required to evaluate the theoretical error performance of any algorithm based on a partial or total ordering.

•Jan 1, 1994•0 citations

Decoding linear block codes using a priority-first search: performance analysis and suboptimal version

Yunghsiang Sam Han, Carlos R. P. Hartmann, K. Mehrotra

An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen (1993). We prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10/sup -3/ by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.

IEEE Transactions on Information Theory•May 1, 1998•20 citations

When is hard decision decoding enough?

Peter F. Swaszek

Many algorithms for soft and near-soft decision decoding of block codes start by implementing hard decision decoding. In several instances it has been noted that simple tests of the hard decision result may allow the algorithm to terminate at this point. This paper explores this notion in detail.

IEEE International Symposium on Information Theory (ISIT)•Nov 19, 2002•0 citations

Design of optimization techniques for soft-decision decoding of linear block codes

Ching-Cheng Shih

This dissertation deals with maximum-likelihood soft-decision decoding as well as suboptimal soft-decision decoding of linear block codes. We present three new decoding algorithms: $MA\sp*D,\ H\sp*,$ and Directed Search. The first algorithm, $MA\sp*D,$ is an instance of Algorithm $A\sp*$ that conducts heuristic search through a code tree of the transmitted code when the decoding problem is transformed into a problem of graph-search through a code tree. $MA\sp*D$ takes into consideration more properties of the code and is considerably more efficient than the original $A\sp*$ decoding algorithm presented by Han, Hartmann, and Chen in 1993. The second algorithm, $H\sp*,$ is a new decoding algorithm that determines the value of every component of a minimum-cost codeword by estimating the cost of the minimum-cost codeword, which has a fixed value at one of the k most reliable, linearly independent bit positions. The suboptimal version of this algorithm is combined with other decoding algorithms to reduce the search space during the decoding process. The third algorithm, Directed Search, is designed to enhance the performance of soft-decision decoding by searching in continuous space. This approach explores the search space between a given vector and the received vector and finds the codeword closest to the received vector in the space explored. We also present a novel and efficient hybrid decoding algorithm for (n, k) linear block codes. It hybridizes $MA\sp*D,\ H\sp*,$ and Directed Search algorithms, utilizing their strengths to make the decoding more efficient. Simulation results for this hybrid algorithm are presented for the (104,52) binary-extended quadratic residue code and for the (128,64), the (256, 131), and the (256, 139) binary-extended BCH codes. This hybrid algorithm can efficiently decode the (104,52) binary extended quadratic residue code and the (128,64) code for any signal-to-noise ratio and has near-optimal to optimal performance. Previously, no practical decoder could decode these two codes with such a performance for all signal-to-noise ratio ranges.

•Jan 1, 1996•0 citations
The problem of decoding binary linear block codes has received much attention; the two extremes are optimal, high-complexity soft-decision (or maximum-likelihood) decoding and lower performance, much lower complexity hard-decision (or algebraic) decoding. This article considers a class of decoders which first implements hard-decision decoding; second, tests to see if that is enough, that its result matches the result of soft-decision decoding; and third, continues to search if a match is not found. The advantage of such a testing procedure is that if the hard-decision decoding result is found to be enough (called a success for the test), then the computational effort expended by the decoder is low. The performance, as measured by the probability of a success, of a variety of simple tests of the hard-decision codeword are analyzed.
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
This dissertation presents a novel approach to soft decision decoding for binary linear block codes. The basic idea of this approach is to achieve a desired error performance progressively in a number of stages. For each decoding stage, the error performance is highly bounded and the decoding is terminated at the stage where either near-optimum error performance or a desired level of error performance is achieved. As a result, more flexibility in the trade-off between performance and decoding complexity is provided. The proposed decoding is based on the reordering of the received symbols according to their reliability measure. In the dissertation, we evaluate the statistics of the noise after ordering. Based on these statistics, we derive two monotonic properties which dictate the reprocessing strategy. Each codeword is decoded in two steps: (1) hard-decision decoding based on reliability information and (2) reprocessing of the hard-decision decoded codeword in successive stages until the desired performance is achieved. The reprocessing is based on the monotonic properties of the ordering and is carried out using a cost function. A new resource test highly related to the reprocessing strategy is introduced to reduce the number of computations for each reprocessing stage. For short codes of lengths N ≤ 32 or medium codes with 32 < N ≤ 64 with rate R ≥ 0.6, near-optimum bit error performance is achieved in two stages of reprocessing with at most a computation complexity of o(K2) constructed code-words, where K is the dimension of the code. For longer codes, three or more reprocessing stages are required to achieve near-optimum decoding. However, most of the coding gain is obtained within the first two reprocessing stages for error performances of practical interest. The proposed decoding algorithm applies to any binary linear code, does not require any data storage and is well suitable for parallel processing. Furthermore, the maximum number of computations required at each reprocessing stage is fixed, which prevents buffer overflow at low SNR. Further reductions of the number of computations based on probabilistic or decomposable properties of the code considered are also investigated. The generalization of the algorithm to other channels is discussed. Finally, the discrete time channel associated with the AWGN model after ordering is greatly simplified. This simplification allows an important reduction of the number of computations required to evaluate the theoretical error performance of any algorithm based on a partial or total ordering.
An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen (1993). We prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10/sup -3/ by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.
This dissertation deals with maximum-likelihood soft-decision decoding as well as suboptimal soft-decision decoding of linear block codes. We present three new decoding algorithms: $MA\sp*D,\ H\sp*,$ and Directed Search. The first algorithm, $MA\sp*D,$ is an instance of Algorithm $A\sp*$ that conducts heuristic search through a code tree of the transmitted code when the decoding problem is transformed into a problem of graph-search through a code tree. $MA\sp*D$ takes into consideration more properties of the code and is considerably more efficient than the original $A\sp*$ decoding algorithm presented by Han, Hartmann, and Chen in 1993. The second algorithm, $H\sp*,$ is a new decoding algorithm that determines the value of every component of a minimum-cost codeword by estimating the cost of the minimum-cost codeword, which has a fixed value at one of the k most reliable, linearly independent bit positions. The suboptimal version of this algorithm is combined with other decoding algorithms to reduce the search space during the decoding process. The third algorithm, Directed Search, is designed to enhance the performance of soft-decision decoding by searching in continuous space. This approach explores the search space between a given vector and the received vector and finds the codeword closest to the received vector in the space explored. We also present a novel and efficient hybrid decoding algorithm for (n, k) linear block codes. It hybridizes $MA\sp*D,\ H\sp*,$ and Directed Search algorithms, utilizing their strengths to make the decoding more efficient. Simulation results for this hybrid algorithm are presented for the (104,52) binary-extended quadratic residue code and for the (128,64), the (256, 131), and the (256, 139) binary-extended BCH codes. This hybrid algorithm can efficiently decode the (104,52) binary extended quadratic residue code and the (128,64) code for any signal-to-noise ratio and has near-optimal to optimal performance. Previously, no practical decoder could decode these two codes with such a performance for all signal-to-noise ratio ranges.