Multistage list decoding of generalized Reed-Solomon codes over Galois rings

A two-stage list decoder for generalized Reed-Solomon codes over GR (p/sup l/,m) that can exceed the Guruswami-Sudan decoding radius t/sub GS/ with significant probability for p=2, l/spl ges/2 and m=1 was recently proposed. It makes a distinction between error values which are units and those which are zero divisors in order to exceed t/sub GS/. This letter presents an extension of that approach by exploiting the fact that each element of GR (p/sup l/,m) has a unique p-adic expansion, culminating in a multistage decoder that outperforms the two-stage decoder.     

On decoding of Reed-Solomon codes

It is shown how nonsystematic Reed-Solomon (RS) codes encoded by means of the Chinese remainder theorem can be decoded using the Berlekamp algorithm. The Chien search and calculation of error values are not needed but are replaced by a polynomial division and added calculation in determining the syndrome. It is shown that for certain cases of low-rate RS codes, the total decoding computation may be less than the usual method used with cyclic codes. Encoding and decoding for shorter length codes is presented.     

Fast parallel algorithms for decoding Reed-Solomon codes based onremainder polynomials

The problem of decoding cyclic error correcting codes is one of solving a constrained polynomial congruence, often achieved using the Berlekamp-Massey or the extended Euclidean algorithm on a key equation involving the syndrome polynomial. A module-theoretic approach to the solution of polynomial congruences is developed here using the notion of exact sequences. This technique is applied to the Welch-Berlekamp (1986) key equation for decoding Reed-Solomon codes for which the computation of syndromes is not required. It leads directly to new and efficient parallel decoding algorithms that can be realized with a systolic array. The architectural issues for one of these parallel decoding algorithms are examined in some detail     

Bit-level soft-decision decoding of Reed-Solomon codes

A Reed-Solomon decoder that makes use of bit-level soft-decision information is presented. A Reed-Solomon generator matrix that possesses a certain inherent structure in GF(2) is derived. This structure allows the code to be represented as a union of cosets, each coset being an interleaver of several binary BCH codes. Such partition into cosets provides a clue for efficient bit-level soft-decision decoding. Two decoding algorithms are derived. In the development of the first algorithm a memoryless channel is assumed, making the value of this algorithm more conceptual than practical. The second algorithm, which is obtained as a modification of the first, does account for channel memory and thus accommodates a bursty channel. Both decoding algorithms are, in many cases, orders of magnitude more efficient than conventional techniques     

Algebraic soft-decision decoding of Reed-Solomon codes

A polynomial-time soft-decision decoding algorithm for Reed-Solomon codes is developed. This list-decoding algorithm is algebraic in nature and builds upon the interpolation procedure proposed by Guruswami and Sudan(see ibid., vol.45, p.1757-67, Sept. 1999) for hard-decision decoding. Algebraic soft-decision decoding is achieved by means of converting the probabilistic reliability information into a set of interpolation points, along with their multiplicities. The proposed conversion procedure is shown to be asymptotically optimal for a certain probabilistic model. The resulting soft-decoding algorithm significantly outperforms both the Guruswami-Sudan decoding and the generalized minimum distance (GMD) decoding of Reed-Solomon codes, while maintaining a complexity that is polynomial in the length of the code. Asymptotic analysis for alarge number of interpolation points is presented, leading to a geo- metric characterization of the decoding regions of the proposed algorithm. It is then shown that the asymptotic performance can be approached as closely as desired with a list size that does not depend on the length of the code.     

Soft decision decoding of Reed-Solomon codes

This paper presents a maximum-likelihood decoding (MLD) and a suboptimum decoding algorithm for Reed-Solomon (RS) codes. The proposed algorithms are based on the algebraic structure of the binary images of RS codes. Theoretical bounds on the performance are derived and shown to be consistent with simulation results. The proposed suboptimum algorithm achieves near-MLD performance with significantly lower decoding complexity. It is also shown that the proposed suboptimum, algorithm has better performance compared with generalized minimum distance decoding, while the proposed MLD algorithm has significantly lower decoding complexity than the well-known Vardy-Be'ery (1991) MLD algorithm.     

Iterative soft decoding of Reed-Solomon codes

This letter presents an iterative decoding method for Reed-Solomon (RS) codes. The proposed algorithm is a stochastic shifting based iterative decoding (SSID) algorithm which takes advantage of the cyclic structure of RS codes. The performances of different updating schemes are compared. Simulation results show that this method provides significant gain over hard decision decoding and is superior to some other popular soft decision methods for short RS codes.     

Modified minimum-weight decoding for Reed-Solomon codes

The authors describe an improvement to the minimum-weight decoding (MWD) algorithm for Reed-Solomon (RS) codes. The modification improves the probability of the MWD algorithm `trapping' the error pattern by squaring each of the terms in the received codeword resulting in a transformation which changes the order of the symbols while maintaining the cyclic properties of the codeword. The results of computer simulations are presented which show that the modified decoder provides an improvement in error performance of ~1 dB over the conventional technique with no increase in decoder complexity. The results show that the modified technique achieves an error performance close to that of maximum-likelihood algorithms with ~1/6 the complexity     

Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

Maximum-likelihood decoding is one of the central algorithmic problems in coding theory. It has been known for over 25 years that maximum-likelihood decoding of general linear codes is NP-hard. Nevertheless, it was so far unknown whether maximum-likelihood decoding remains hard for any specific family of codes with nontrivial algebraic structure. In this paper, we prove that maximum-likelihood decoding is NP-hard for the family of Reed-Solomon codes. We moreover show that maximum-likelihood decoding of Reed-Solomon codes remains hard even with unlimited preprocessing, thereby strengthening a result of Bruck and Naor.     

Modified time-domain algorithm for decoding Reed-Solomon codes

A technique for reducing the number of inversions in the time-domain decoding algorithm based on an algebraic decoder (Blahut's decoder) is introduced. It is proved that the modified algorithm is equivalent to the original one. The modified algorithm can be used in the universal Reed-Solomon decoder to decrease complexity     

Applications of algebraic soft-decision decoding of Reed-Solomon codes

Efficient soft-decision decoding of Reed-Solomon (RS) codes is made possible by the Koetter-Vardy (KV) algorithm which consists of a front-end to the interpolation-based Guruswami-Sudan (GS) list decoding algorithm. This paper approaches the soft-decision KV algorithm from the point of view of a communications systems designer who wants to know what benefits the algorithm can give, and how the extra complexity introduced by soft decoding can be managed at the systems level. We show how to reduce the computational complexity and memory requirements of the soft-decision front-end. Applications to wireless communications over Rayleigh fading channels and magnetic recording channels are proposed. For a high-rate RS(255,239) code, 2-3 dB of soft-decision gain is possible over a Rayleigh fading channel using 16-quadrature amplitude modulation. For shorter codes and at lower rates, the gain can be as large as 9 dB. To lower the complexity of decoding on the systems level, the redecoding architecture is explored, which uses only the appropriate amount of complexity to decode each packet. An error-detection criterion based on the properties of the KV decoder is proposed for the redecoding architecture. Queueing analysis verifies the practicality of the redecoding architecture by showing that only a modestly sized RAM buffer is required.     

Iterative algebraic soft-decision list decoding of Reed-Solomon codes

In this paper, we present an iterative soft-decision decoding algorithm for Reed-Solomon (RS) codes offering both complexity and performance advantages over previously known decoding algorithms. Our algorithm is a list decoding algorithm which combines two powerful soft-decision decoding techniques which were previously regarded in the literature as competitive, namely, the Koetter-Vardy algebraic soft-decision decoding algorithm and belief-propagation based on adaptive parity-check matrices, recently proposed by Jiang and Narayanan. Building on the Jiang-Narayanan algorithm, we present a belief-propagation-based algorithm with a significant reduction in computational complexity. We introduce the concept of using a belief-propagation-based decoder to enhance the soft-input information prior to decoding with an algebraic soft-decision decoder. Our algorithm can also be viewed as an interpolation multiplicity assignment scheme for algebraic soft-decision decoding of RS codes.     

Fast factorization architecture in soft-decision Reed-Solomon decoding

Reed-Solomon (RS) codes are among the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to its hard-decision counterpart, soft-decision decoding offers considerably higher error-correcting capability. The recent development of soft-decision RS decoding algorithms makes their hardware implementations feasible. Among these algorithms, the Koetter-Vardy (KV) algorithm can achieve substantial coding gain for high-rate RS codes, while maintaining a polynomial complexity with respect to the code length. In the KV algorithm, the factorization step can consume a major part of the decoding latency. A novel architecture based on root-order prediction is proposed in this paper to speed up the factorization step. As a result, the time-consuming exhaustive-search-based root computation in each iteration level, except the first one, of the factorization step is circumvented with more than 99% probability. Using the proposed architecture, a speedup of 141% can be achieved over prior efforts for a (255, 239) RS code, while the area consumption is reduced to 31.4%.     

一种利用多重偏置的RS码软判译码算法

为了提高RS码的纠错性能,本文将基于盒匹配译码算法(BMA)的多重偏置与自适应置信传播算法(ABP)进行级联,提出了一种利用多重偏置基于可信度迭代的RS码软判译码算法,称为ABP-BIAS-BMA,并将其与传统的基于自适应置信传播的级联算法ABP-BMA及自适应置信传播算法ABP进行了译码性能仿真比较.仿真结果表明,提出的ABP-BIAS-BMA算法比ABP-BMA及ABP的译码性能要好,特别在相同信噪比情况下算法整体平均迭代次数较小.     

Reliability-based decoding of Reed-Solomon codes using their binary image

In this letter, the reliability-based decoding algorithms developed for binary linear codes are investigated for SDD of Reed-Solomon (RS) codes using their binary images. It is shown that if such approaches are promising, they also have to be carefully considered as their behavior at error rates which can be simulated often differ from that at lower error rates for which RS codes have been implemented in concatenated schemes.     

Advanced decoding algorithms for Reed-Solomon/Convolutional concatenated codes

The evaluation of the union bound for theber of Reed-Solomon/Convolutional concatenated codes indicates that their performance might largely improve through the application of soft iterative decoders. This paper presents an iterative decoding algorithm for concatenated codes consisting of an outer Reed-Solomon code, a symbol interleaver and an inner convolutional code. The performance improvement for iterative and non-iterative decoders is evaluated. Existing solutions for the different decoding stages and their interfaces are discussed and their performance is compared. A new procedure is proposed to define the feedback signal from the output of the Reed-Solomon decoder to the input of the convolutional decoder, which captures the reliability information that can be inferred from errors-and-era-suresrs decoders and includes the “state pinning” approach as a particular case. The decoding schemes are applied to the specificdvb-s concatenated code.     

Belief propagation decoding of Reed-Solomon codes; a bit-level soft decision decoding algorithm

In this article we propose the application of Belief Propagation (BP) algorithm as a novel bit-level soft decision decoding (SDD) technique for Reed-Solomon (RS) codes. A brief tutorial on Belief Propagation algorithm is presented. A central issue in the application of BP algorithm to decoding RS codes is the construction of a sparse parity check matrix for the binary image of the code. It is demonstrated that Vardy's technique may be applied to find a sparse parity check matrix for RS codes. However, this technique is not applicable to all cases. The BP algorithm is applied to two test codes. In one case, simulation models show that the BP algorithm outperforms the hard decision Euclidean decoding by more than 2 dB of additional coding gain. The results with the second test code are not as promising.     

On the complexity of decoding Reed-Solomon codes (Corresp.)

Certainq-ary Reed-Solomon codes can be decoded by an algorithm requiring onlyO(q log^{2} q)additions and multiplications inGF(q).     

New concatenated soft decoding of Reed-Solomon codes with lower complexities

To improve error-correcting performance, an iterative concatenated soft decoding algorithm for Reed-Solomon (RS) codes is presented in this article. This algorithm brings both complexity as well as advantages in performance over presently popular sott decoding algorithms. The proposed algorithm consists of two powerful soft decoding techniques, adaptive belief propagation (ABP) and box and match algorithm (BMA), which are serially concatenated by the accumulated log-likelihood ratio (ALLR).Simulation results show that, compared with ABP and ABP-BMA algorithms, the proposed algorithm can bring more decoding gains and a better tradeoffbetween the decoding performance and complexity.     

Exponential error bounds for algebraic soft-decision decoding of Reed-Solomon codes

Algebraic soft-decision decoding of Reed-Solomon codes is a promising technique for exploiting reliability information in the decoding process. While the algorithmic aspects of the decoding algorithm are reasonably well understood and, in particular, complexity is polynomially bounded in the length of the code, the performance analysis has relied almost entirely on simulation results. Analytical exponential error bounds that can be used to tightly bound the performance of Reed-Solomon codes under algebraic soft-decision decoding are presented in this paper. The analysis is used in a number of examples and several extensions and consequences of the results are presented.