Geometrical and performance analysis of GMD and Chase decodingalgorithms

The overall number of nearest neighbors in bounded distance decoding (BDD) algorithms is given by N_0,eff=N₀+N _BDD. Where NBDD denotes the number of additional, non-codeword, neighbors that are generated during the (suboptimal) decoding process. We identify and enumerate the nearest neighbors associated with the original generalized minimum distance (GMD) and Chase (1972) decoding algorithms. After careful examination of the decision regions of these algorithms, we derive an approximated probability ratio between the error contribution of a noncodeword neighbor (one of N_BDD points) and a codeword nearest neighbor. For Chase algorithm 1 it is shown that the contribution to the error probability of a noncodeword nearest neighbor is a factor of 2^d-1 less than the contribution of a codeword, while for Chase algorithm 2 the factor is 2^[d/2]-1, d being the minimum Hamming distance of the code. For Chase algorithm 3 and GMD, a recursive procedure for calculating this ratio, which turns out to be nonexponential in d, is presented. This procedure can also be used for specifically identifying the error patterns associated with Chase algorithm 3 and GMD. Utilizing the probability ratio, we propose an improved approximated upper bound on the probability of error based on the union bound approach. Simulation results are given to demonstrate and support the analytical derivations     

Generalized threshold chase algorithms

 Three generalized threshold Chase algorithms called GTC Ⅰ,GTC Ⅱ and STC are proposed in this paper.They are the combination of the generalized minimum distance(GMD)decoding algorithm with the Chase algorithm.Although the decoding error probabilities of these algorithms are very close to that of the Chase algorithm,the decoding speeds are faster,especially at higher signal-to-noise ratio(SNR),hence they are of greater practical value.The results of computer simulations are given,showing the advantages of these algorithms.     

Error performance analysis for reliability-based decodingalgorithms

The statistical approach proposed by Agrawal and Vardy (see ibid., vol.46, no.1, p.60-83, 2000) to evaluate the error performance of the generalized minimum distance (GMD) decoding is extended to other reliability-based decoding algorithms for binary linear block codes, namely Chase (1972) type, combined GMD and Chase type, and order statistic decoding (OSD). In all cases, tighter and simpler bounds than those previously proposed have been obtained with this approach     

On algebraic soft-decision decoding algorithms for BCH codes

Three algebraic soft-decision decoding algorithms are presented for binary Bose-Chaudhuri-Hocquengham (BCH) codes. Two of these algorithms are based on the bounded distance (BD)+1 generalized minimum-distance (GMD) decoding presented by Berlekamp (1984), and the other is based on Chase (1972) decoding. A simple algebraic algorithm is first introduced, and it forms a common basis for the decoding algorithms presented. Next, efficient BD+1 GMD and BD+2 GMD decoding algorithms are presented. It is shown that, for binary BCH codes with odd designed-minimum-distance d and length n, both the BD+1 GMD and the BD+2 GMD decoding algorithms can be performed with complexity O(nd). The error performance of these decoding algorithms is shown to be significantly superior to that of conventional GMD decoding by computer simulation. Finally, an efficient algorithm is presented for Chase decoding of binary BCH codes. Like a one-pass GMD decoding algorithm, this algorithm produces all necessary error-locator polynomials for Chase decoding in one run     

Chase-type and GMD coset decodings

In this letter, Chase decoding algorithms are generalized into a family of bounded distance decoding algorithms, so that the conventional Chase algorithm-2 and Chase algorithm-3 become the two extremes of this family. Consequently, more flexibility in the tradeoffs between error performance and decoding complexity is provided by this generalization, especially for codes with large minimum distance. Finally this approach is extended to decoding with erasures     

Generalization of chase algorithms for soft decision decoding of binary linear codes

Soft decision decoding of binary linear block codes transmitted over the additive white Gaussian channel (AWGN) using antipodal signaling is considered. A set of decoding algorithms called generalized Chase algorithms is proposed. In contrast to Chase algorithms, which require alfloor (d- 1)/2 rfloorbinary error-correcting decoder for decoding a binary linear block code of minimum distanced, the generalized Chase algorithms can use a binary decoder that can correct less thanlfloor ( d - 1)/2 rfloorhard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. The performance of all proposed algorithms is asymptotically optimum for high signal-to-noise ratio (SNR). Simulation results for the(47, 23)quadratic residue code indicate that even for low SNR the performance level of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.     

On combining Chase-2 and GMD decoding algorithms for nonbinaryblock codes

In this letter, a class of algorithms that combines Chase-2 and GMD (generalized minimum distance) decoding algorithms is presented for nonbinary block codes. This approach provides additional trade-offs between error performance and decoding complexity. Reduced-complexity versions of the algorithms with practical interests are then provided and simulated     

Generalized minimum distance decoding in Euclidean space:performance analysis

We present a detailed analysis of generalized minimum distance (GMD) decoding algorithms for Euclidean space codes. In particular, we completely characterize GMD decoding regions in terms of receiver front-end properties. This characterization is used to show that GMD decoding regions have intricate geometry. We prove that although these decoding regions are polyhedral, they are essentially always nonconvex. We furthermore show that conventional performance parameters, such as error-correction radius and effective error coefficient, do not capture the essential geometric features of a GMD decoding region, and thus do not provide a meaningful measure of performance. As an alternative, probabilistic estimates of, and upper bounds upon, the performance of GMD decoding are developed. Furthermore, extensive simulation results, for both low-dimensional and high-dimensional sphere-packings, are presented. These simulations show that multilevel codes in conjunction with multistage GMD decoding provide significant coding gains at a very low complexity. Simulated performance, in both cases, is in remarkably close agreement with our probabilistic approximations     

On the performance and complexity of A generalized minimum distance reed–solomon decoding algorithm

The article reports on the characteristics of an algorithm that implements generalized minimum distance (GMD) decoding of Reed-Solomon codes. The algorithm uses the novel Welch-Berlekamp (WB) algorithm, as modified by Tze-Hua, in order to minimize the complexity of the decoder. Both the WB algorithm and the GMD extension of the WB algorithm are described in outline. The performance of the GMD algorithm was simulated on AWGN channels and fading channels. Results are presented both for RS and concatenated RS codes. The gains over conventional decoding are larger for fading channels than for AWGN conditions but seem useful in all cases. The complexities of the GMD algorithm and the WB algorithm are analysed and compared to that of conventional RS decoding algorithms.     

Efficient Generalized Minimum-distance Decoders of Reed-Solomon Codes

Generalized minimum distance (GMD) decoding of Reed–Solomon (RS) codes can correct more errors than conventional hard-decision decoding by running error-and-erasure decoding multiple times for different erasure patterns. The latency of the GMD decoding can be reduced by the Kötter’s one-pass decoding scheme. This scheme first carries out an error-only hard-decision decoding. Then all pairs of error-erasure locators and evaluators are derived iteratively in one run based on the result of the error-only decoding. In this paper, a more efficient interpolation-based one-pass GMD decoding scheme is studied. Applying the re-encoding and coordinate transformation, the result of erasure-only decoding can be directly derived. Then the locator and evaluator pairs for other erasure patterns are generated iteratively by applying interpolation. A simplified polynomial selection scheme is proposed to pass only one pair of locator and evaluator to successive decoding steps and a low-complexity parallel Chien search architecture is developed to implement this selection scheme. With the proposed polynomial selection architecture, the interpolation can run at the full speed to greatly increase the throughput. After efficient architectures and effective optimizations are employed, a generalized hardware complexity analysis is provided for the proposed interpolation-based decoder. For a (255, 239) RS code, the high-speed interpolation-based one-pass GMD decoder can achieve 53% higher throughput than the Kötter’s decoder with slightly more hardware requirement. In terms of speed-over-area ratio, our design is 51% more efficient. In addition, compared to other soft-decision decoders, the high-speed interpolation-based GMD decoder can achieve better performance-complexity tradeoff.     

Reduced GMD decoding

A framework is presented for generalized minimum distance (GMD) decoding with a limited number of decoding trials and a restricted set of reliability values. In GMD decoding, symbols received from the channel may be erased before being fed into an algebraic error-erasure decoder for error correction, in subsequent or simultaneous trials with different erasing patterns. The decision whether or not to erase a symbol in a certain trial is taken by an erasure-choosing algorithm which takes into account reliability information from the channel. The final GMD decoder output is a codeword which results from a decoding trial and satisfies a certain distance criterion. For various erasing strategies and reliability sets, the guaranteed error-correction radius and the unsuccessful decoding probability of this technique are studied. Both known and new results, with applications to concatenated coding, follow from the unified approach presented in this correspondence.     

Fast generalized minimum-distance decoding of algebraic-geometryand Reed-Solomon codes

Generalized minimum-distance (GMD) decoding is a standard soft-decoding method for block codes. We derive an efficient general GMD decoding scheme for linear block codes in the framework of error-correcting pairs. Special attention is paid to Reed-Solomon (RS) codes and one-point algebraic-geometry (AG) codes. For RS codes of length n and minimum Hamming distance d the GMD decoding complexity turns out to be in the order O(nd), where the complexity is counted as the number of multiplications in the field of concern. For AG codes the GMD decoding complexity is highly dependent on the curve in consideration. It is shown that we can find all relevant error-erasure-locating functions with complexity O(o₁nd), where o₁ is the size of the first nongap in the function space associated with the code. A full GMD decoding procedure for a one-point AG code can be performed with complexity O(dn²)     

Two algorithms for soft-decision decoding of reed-solomon codes, with application to multilevel coded modulations

In this paper two symbol-level soft-decision decoding algorithms for Reed-Solomon codes, derived form the ordered statistics (OS) and from the generalized minimum-distance (GMD) decoding methods, are presented and analyzed. Both the OS and the GMD algorithms are based on the idea of producing a list of candidate code words, among which the one having the larger likelihood is selected as output. We propose variants of the mentioned algorithms that allow to finely tune the size of the list in order to obtain the desired decoding complexity. The method proposed by Agrawal and Vardy for computing the error probability of the GMD algorithm is extended to our decoding methods. Examples are presented where these algorithms are applied to singly-extended Reed-Solomon codes over GF(16) used as outer codes in a 128-dimensional coded modulation scheme that attains good performance, with manageable decoding complexity.     

Limited-trial Chase decoding

Chase decoders permit flexible use of reliability information in algebraic decoding algorithms for error-correcting block codes of Hamming distance d. The least complex version of the original Chase algorithms uses roughly d/2 trials of a conventional binary decoder, after which the best decoding result is selected as the final output. On certain channels, this approach achieves asymptotically the same performance as maximum-likelihood (ML) decoding. In this correspondence, the performance of Chase-like decoders with even less trials is studied. Most strikingly, it turns out that asymptotically optimal performance can be achieved by a version which uses only about d/4 trials.     

Bounded-distance decoding: algorithms, decision regions, and pseudonearest neighbors

For a code C, bounded distance decoding algorithms perform as optimal algorithms within the balls B(c), centered at the codewords c∈C, with radius equal to half the minimum Euclidean distance of the code. Thus distinct bounded-distance algorithms vary in performance due to their different behavior outside the balls B(c). We investigate this issue by analyzing the decision regions of some known (e.g., GMD) and some new bounded-distance algorithms presented in this work. In particular, we show that there are three distinct types of nearest neighbors and classify them according to their influence on the decision region. Simulation results and computer-generated images of the decision regions are provided to illustrate the analytical results for block and lattice codes on additive white Gaussian noise (AWGN) channels     

Turbo乘积码译码算法的简化

Chase算法是Turbo乘积码(TPC)软判决译码中常采用的算法之一。分析了传统Chase算法中寻找竞争码字对译码复杂度的影响,在此基础上提出了两种新的简化译码算法,省去了寻找竞争码字的过程。仿真结果表明,简化算法在基本保持传统Chase算法译码性能的基础上,降低了译码复杂度,提高了译码速度。     

An improvement to generalized-minimum-distance decoding

A novel acceptance criterion that is less stringent than previous criteria is developed. The criterion accepts the codeword that is closest to the received vector for many cases where previous criteria fail to accept any codeword. As a result, the performance of generalized minimum distance (GMD) decoding is better if the new criterion is used. For M-ary signaling, the weights used in GMD decoding are generalized to permit each of the possible M symbol values to have a different weight     

On acceptance criterion for efficient successiveerrors-and-erasures decoding of Reed-Solomon and BCH codes

We describe an efficient algorithm for successive errors-and-erasures decoding of BCH codes. The decoding algorithm consists of finding all necessary error locator polynomials and errata evaluator polynomials, choosing the most appropriate error locator polynomial and errata evaluator polynomial, using these two polynomials to compute a candidate codeword for the decoder output, and testing the candidate for optimality via an originally developed acceptance criterion. Even in the most stringent case possible, the acceptance criterion is only a little more stringent than Forney's (1966) criterion for generalised minimum distance (GMD) decoding. We present simulation results on the error performance of our decoding algorithm for binary antipodal signals over an AWGN channel and a Rayleigh fading channel. The number of calculations of elements in a finite field that are required by our algorithm is only slightly greater than that required by hard-decision decoding, while the error performance is almost as good as that achieved with GMD decoding. The presented algorithm is also applicable to efficient decoding of product RS codes     

广义门限蔡斯算法

本文提出了三种广义的门限蔡斯算法:GTC Ⅰ、GTC Ⅱ和 STC。这些算法是广义最小距离译码(GMD)算法与蔡斯算法的结合,它们的译码错误概率与蔡斯算法的非常接近,但译码速度要快,特别当信噪比高时更是如此,因而有较大的实用价值。文中最后给出了计算机模拟结果,证实了这些算法的优越性。     

一种Golay码的快速译码算法

本文提出了一种（２４，１２，８）扩展Ｇｏｌａｙ码的新的软判决译码算法，其译一组码字的运算量最多为５０７次二元运算，优于目前已发表的各种算法。我们证明了该算法，并实现了广义最小距离译码。计算机模拟表明在完备译码时其性能与最大似然译码几乎一样。