In this work, we investigate a hybrid decoding approach that combines algebraic hard-input decoding of binary block codes with soft-input decoding. In particular, an acceptance criterion is proposed which determines the reliability of a candidate codeword. For many received codewords the stopping criterion indicates that the hard-decoding result is sufficiently reliable, and the costly soft-input decoding can be omitted. The proposed acceptance criterion significantly reduces the decoding complexity. For simulations we combine the algebraic hard-input decoding with ordered statistics decoding, which enables near maximum likelihood soft-input decoding for codes of small to medium block lengths.
In this work, we investigate a hybrid decoding approach that combines algebraic hard-input decoding of binary block codes with soft-input decoding. In particular, an acceptance criterion is proposed which determines the reliability of a candidate codeword. For many received codewords the stopping criterion indicates that the hard-decoding result is sufficiently reliable, and the costly soft-input decoding can be omitted. The proposed acceptance criterion significantly reduces the decoding complexity. For simulations we combine the algebraic hard-input decoding with ordered statistics decoding, which enables near maximum likelihood soft-input decoding for codes of small to medium block lengths.
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.
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.
This correspondence presents a hybrid reliability-based decoding algorithm which combines the reprocessing method based on the most reliable basis and a generalized Chase-type algebraic decoder based on the least reliable positions. It is shown that reprocessing with a simple additional algebraic decoding effort achieves significant coding gain. For long codes, the order of reprocessing required to achieve asymptotic optimum error performance is reduced by approximately 1/3. This significantly reduces the computational complexity, especially for long codes. Also, a more efficient criterion for stopping the decoding process is derived based on the knowledge of the algebraic decoding solution.
Soft-decision decoding of a linear block code using the most reliable basis corresponding to each received word is investigated. Based either on probabilistic properties or on the structure of the code considered, three improvements to the algorithm devised by Fossorier and Lin (see ibid., vol.41, no.9, p.1379-1396, 1995) are presented. These modifications allow large computation savings or significant decoding speedup with little error performance degradation. First, a reduced probabilistic list of codeword candidates is associated with order-i reprocessing of a given code. It results in a large reduction of the maximum number of computations with a very small degradation in performance. Then, a probabilistic stopping criterion is introduced for order-0 reprocessing. This new test significantly decreases the average number of computations when appropriately implemented. Finally, the application of the algorithm to coset decoding is considered for |u|u+v| constructed codes. In addition to the conventional coset decoding, a new adaptive practically optimum coset decoding method is presented where at each reprocessing stage, the number of surviving cosets decreases. Suboptimum closest coset decoding is also investigated. It is shown that two-stage decoding with the algorithm of Fossorier and Lin offers a large variety of choices, since the reprocessing order of each stage can be determined independently.
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.
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.