In this paper, efficient methods to improve the box and matching algorithm (BMA) are presented. Firstly, an efficient approach is introduced to terminate the decoding if a local optimal candidate satisfies a probabilistic sufficient condition. The false alarm probability associated with the use of the probabilistic sufficient condition is also derived. Secondly, by constructing a control band which is assumed error free, the matching capability of the BMA is enhanced. More precisely, the performance of BMA of order (i + 1) is nearly achieved with a small increase in complexity and no increase in memory with respect to the BMA of order i. A tight performance analysis is derived based on the theory of order statistics. An error floor associated either with false alarms or with errors in the control band is introduced, but this error floor can be controlled using the analysis in both cases. Simulation results show that the performance of the enhanced BMA for the decoding of the RS(255,239) code with BPSK signaling over an AWGN channel is about 0.1 dB away from that of maximum likelihood decoding at the word error rate (WER) 10-3.
In this paper, efficient methods to improve the box and matching algorithm (BMA) are presented. Firstly, an efficient approach is introduced to terminate the decoding if a local optimal candidate satisfies a probabilistic sufficient condition. The false alarm probability associated with the use of the probabilistic sufficient condition is also derived. Secondly, by constructing a control band which is assumed error free, the matching capability of the BMA is enhanced. More precisely, the performance of BMA of order (i + 1) is nearly achieved with a small increase in complexity and no increase in memory with respect to the BMA of order i. A tight performance analysis is derived based on the theory of order statistics. An error floor associated either with false alarms or with errors in the control band is introduced, but this error floor can be controlled using the analysis in both cases. Simulation results show that the performance of the enhanced BMA for the decoding of the RS(255,239) code with BPSK signaling over an AWGN channel is about 0.1 dB away from that of maximum likelihood decoding at the word error rate (WER) 10-3.
The order statistic decoding (OSD) algorithm is a probabilistic list decoding algorithm which allows to achieve practically optimum soft decision decoding of binary linear block codes of length up to 128. Recently, matching techniques were applied to the OSD algorithm to reduce both the worst case and average complexities of decoding at the expense of memory. The corresponding box-and-match algorithm (BMA) allows to achieve near optimum decoding of codes of length up to 192. In this work, we investigate the application of iterative information set reduction to the BMA, which provides further refinements in the trade-offs between error performance and decoding complexity.
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.
In this correspondence, various aspects of reliability-based syndrome decoding of binary codes are investigated. First, it is shown that the least reliable basis (LRB) and the most reliable basis (MRB) are dual of each other. By exploiting this duality, an algorithm performing maximum-likelihood (ML) soft-decision syndrome decoding based on the LRB is presented. Contrarily to previous LRB-based ML syndrome decoding algorithms, this algorithm is more conveniently implementable for codes whose codimension is not small. New sufficient conditions for optimality are derived. These conditions exploit both the ordering associated with the LRB and the structure of the code considered. With respect to MRR-based sufficient conditions, they present the advantage of requiring no soft information and thus can be preprocessed and stored. Based on these conditions, low-complexity soft-decision syndrome decoding algorithms for particular classes of codes are proposed. Finally, a simple algorithm is analyzed. After the construction of the LRB, this algorithm computes the syndrome of smallest Hamming weight among o(K/sup i/) candidates, where K is the dimension of the code, for an order i of reprocessing. At practical bit-error rates, for codes of length N/spl les/128, this algorithm always outperforms any algebraic decoding algorithm capable of correcting up to t+1 errors with an order of reprocessing of at most 2, where t is the error-correcting capability of the code considered.
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.
In this paper, we improve the ordered statistics decoding algorithm by using matching techniques. This allows us: to reduce the worst case complexity of decoding (the error performance being fixed) or to improve the error performance (for a same complexity); to reduce the ratio between average complexity and worst case complexity; to achieve practically optimal decoding of rate-1/2 codes of lengths up to 128 (rate-1/2 codes are a traditional benchmark, for coding rates different from 1/2, the decoding is easier); to achieve near-optimal decoding of a rate-1/2 code of length 192, which could never be performed before.
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.