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.     

Reduced Complexity Interpolation Architecture for Soft-Decision Reed–Solomon Decoding

Reed-Solomon (RS) codes are one of the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to hard-decision decoding, soft-decision decoding offers considerably higher error-correcting capability. The Koetter-Vardy (KV) soft-decision decoding algorithm can achieve substantial coding gain, while maintaining a complexity polynomial with respect to the code word length. In the KV algorithm, the interpolation step dominates the decoding complexity. A reduced complexity interpolation architecture is proposed in this paper by eliminating the polynomial updating corresponding to zero discrepancy coefficients in this step. Using this architecture, an area reduction of 27% can be achieved over prior efforts for the interpolation step of a typical (255, 239) RS code, while the interpolation latency remains the same     

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.     

Architecture and Implementation of an Interpolation Processor for Soft-Decision Reed–Solomon Decoding

Reed-Solomon codes are powerful error-correcting codes that can be found in many digital communications standards. Recently, there has been an interest in soft-decision decoding of Reed-Solomon codes, incorporating reliability information from the channel into the decoding process. The Koetter-Vardy algorithm is a soft-decision decoding algorithm for Reed-Solomon codes which can provide several dB of gain over traditional hard-decision decoders. The algorithm consists of a soft-decision front end to the interpolation-based Guruswami-Sudan list decoder. The main computational task in the algorithm is a weighted interpolation of a bivariate polynomial. We propose a parallel architecture for the hardware implementation of bivariate interpolation for soft-decision decoding. The key feature is the embedding of both a binary tree and a linear array into a 2-D array processor, enabling fast polynomial evaluation operations. An field-programmable gate array interpolation processor was implemented and demonstrated at a clock frequency of 23 MHz, corresponding to decoding rates of 10-15 Mb/s     

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.     

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.     

List decoding of algebraic-geometric codes

We generalize Sudan's (see J. Compl., vol.13, p.180-93, 1997) results for Reed-Solomon codes to the class of algebraic-geometric codes, designing algorithms for list decoding of algebraic geometric codes which can decode beyond the conventional error-correction bound (d-1)/2, d being the minimum distance of the code. Our main algorithm is based on an interpolation scheme and factorization of polynomials over algebraic function fields. For the latter problem we design a polynomial-time algorithm and show that the resulting overall list-decoding algorithm runs in polynomial time under some mild conditions. Several examples are included     

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.     

Reliability-Based Forward Recursive Algorithms for Algebraic Soft-Decision Decoding of Reed--Solomon Codes

We propose efficient forward recursive algorithms for algebraic soft-decision list decoding of Reed-Solomon codes, which utilize channel reliability information, and outperform the Koetter-Vardy (KV) algorithm with lower decoding latency. We evaluate the performance of the proposed decoding algorithms on additive white Gaussian noise and partial response channels. Simulation results show that we can achieve better performance on a modified extended-extended partial response class 4 channel than on the best possible performance of the KV algorithm, as given by the asymptotic bound for high-rate codes.     

Further Exploring the Strength of Prediction in the Factorization of Soft-Decision Reed–Solomon Decoding

Reed-Solomon (RS) codes are among the most widely utilized error-correcting codes in digital communication and storage systems. Among the decoding algorithms of RS codes, the recently developed Koetter-Vardy (KV) soft-decision decoding algorithm can achieve substantial coding gain, while has a polynomial complexity. One of the major steps of the KV algorithm is the factorization. Each iteration of the factorization mainly consists of root computations over finite fields and polynomial updating. To speed up the factorization step, a fast factorization architecture has been proposed to circumvent the exhaustive-search-based root computation from the second iteration level by using a root-order prediction scheme. Based on this scheme, a partial parallel factorization architecture was proposed to combine the polynomial updating in adjacent iteration levels. However, in both of these architectures, the root computation in the first iteration level is still carried out by exhaustive search, which accounts for a significant part of the overall factorization latency. In this paper, a novel iterative prediction scheme is proposed for the root computation in the first iteration level. The proposed scheme can substantially reduce the latency of the factorization, while only incurs negligible area overhead. Applying this scheme to a (255, 239) RS code, speedups of 36% and 46% can be achieved over the fast factorization and partial parallel factorization architectures, respectively.     

Limits to List Decoding Reed–Solomon Codes

In this paper, we prove the following two results that expose some combinatorial limitations to list decoding Reed-Solomon codes. 1) Given n distinct elements alpha₁,...,alpha_n from a field F, and n subsets S₁,...,S_n of F, each of size at most l, the list decoding algorithm of Guruswami and Sudan can in polynomial time output all polynomials p of degree at most k that satisfy p(alpha_i)isinS_i for every i, as long as ldelta for small enough delta, we exhibit an explicit received word with a superpolynomial number of Reed-Solomon codewords that agree with it on (2-epsi)k locations, for any desired epsi>0 (agreement of k is trivial to achieve). Such a bound was known earlier only for a nonexplicit center. Finding explicit bad list decoding configurations is of significant interest-for example, the best known rate versus distance tradeoff, due to Xing, is based on a bad list decoding configuration for algebraic-geometric codes, which is unfortunately not explicitly known     

Computing upper bounds to error probability of soft-decision decoding of Reed-Solomon codes based on the ordered statistics algorithm

This correspondence presents performance analysis of symbol-level soft-decision decoding of q-ary maximum-distance-separable (MDS) codes based on the ordered statistics algorithm. The method we present is inspired by the one recently proposed by Agrawal and Vardy (2000), who approximately evaluate the performance of generalized minimum-distance decoding. The correspondence shows that in our context, the method allows us to compute the exact value of the probability that the transmitted codeword is not one of the candidate codewords. This leads to a close upper bound on the performance of the decoding algorithm. Application of the ordered statistics algorithm to MDS codes is not new. Nevertheless, its advantages seem not to be fully explored. We show an example where the decoding algorithm is applied to singly extended 16-ary Reed-Solomon (RS) codes in a 128-dimensional multilevel coded-modulation scheme that approaches the sphere lower bound within 0.5 dB at the word error probability of 10/sup -4/ with manageable decoding complexity.     

Efficient VLSI Architecture for Soft-Decision Decoding of Reed–Solomon Codes

Reed–Solomon (RS) codes have very broad applications in digital communication and storage systems. The recently developed algebraic soft-decision decoding (ASD) algorithms of RS codes can achieve substantial coding gain with polynomial complexity. Among the ASD algorithms with practical multiplicity assignment schemes, the bit-level generalized minimum distance (BGMD) decoding algorithm can achieve similar or higher coding gain with lower complexity. ASD algorithms consist of two major steps: the interpolation and the factorization. In this paper, novel architectures for both steps are proposed for the BGMD decoder. The interpolation architecture is based on the newly proposed Lee-O'Sullivan (LO) algorithm. By exploiting the characteristics of the LO algorithm and the multiplicity assignment scheme in the BGMD decoder, the proposed interpolation architecture for a (255, 239) RS code can achieve 25% higher efficiency in terms of speed/area ratio than prior efforts. Root computation over finite fields and polynomial updating are the two main steps of the factorization. A low-latency and prediction-free scheme is introduced in this paper for the root computation in the BGMD decoder. In addition, novel coefficient storage schemes and parallel processing architectures are developed to reduce the latency of the polynomial updating. The proposed factorization architecture is 126% more efficient than the previous direct root computation factorization architecture.      

A new Reed-Solomon code decoding algorithm based on Newton'sinterpolation

A Reed-Solomon code decoding algorithm based on Newton's interpolation is presented. This algorithm has as main application fast generalized-minimum-distance decoding of Reed-Solomon codes. It uses a modified Berlekamp-Massey algorithm to perform all necessary generalized-minimum-distance decoding steps in only one run. With a time-domain form of the new decoder the overall asymptotic generalized-minimum-distance decoding complexity becomes O(dn), with n the length and d the distance of the code (including the calculation of all error locations and values). This asymptotic complexity is optimal. Other applications are the possibility of fast decoding of Reed-Solomon codes with adaptive redundancy and a general parallel decoding algorithm with zero delay     

High-Speed Interpolation Architecture for Soft-Decision Decoding of Reed–Solomon Codes

Algebraic soft-decision decoding of Reed-Solomon (RS) codes delivers promising coding gains over conventional hard-decision decoding. The most computationally demanding step in soft-decision decoding of RS codes is bivariate polynomial interpolation. In this paper, we present a hybrid data format-based interpolation architecture that is well suited for high-speed implementation of the soft-decision decoders. It will be shown that this architecture is highly scalable and can be extensively pipelined. It also enables maximum overlap in time for computations at adjacent iterations. It is estimated that the proposed architecture can achieve significantly higher throughput than conventional designs with equivalent or lower hardware complexity     

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     

Suboptimum decoding of decomposable block codes

To decode a long block code with a large minimum distance by maximum likelihood decoding is practically impossible because the decoding complexity is simply enormous. However, if a code can be decomposed into constituent codes with smaller dimensions and simpler structure, it is possible to devise a practical and yet efficient scheme to decode the code. This paper investigates a class of decomposable codes, their distance and structural properties. It is shown that this class includes several classes of well-known and efficient codes as subclasses. Several methods for constructing decomposable codes or decomposing codes are presented. A two-stage (soft-decision or hard-decision) decoding scheme for decomposable codes, their translates or unions of translates is devised, and its error performance is analyzed for an AWGN channel. The two-stage soft-decision decoding is suboptimum. Error performances of some specific decomposable codes based on the proposed two-stage soft-decision decoding are evaluated. It is shown that the proposed two-stage suboptimum decoding scheme provides an excellent trade-off between the error performance and decoding complexity for codes of moderate and long block length     

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%.     

Bounds on the bit error probability of a linear cyclic code overGF(2l) and its extended code

An upper bound on the bit-error probability (BEP) of a linear cyclic code over GF(2^l) with hard-decision (HD) maximum-likelihood (ML) decoding on memoryless symmetric channels is derived. Performance results are presented for Reed-Solomon codes on GF(32), GF(64), and GF(128). Also, a union upper bound on the BEP of a linear cyclic code with either hard- or soft-decision ML decoding is developed, as well as the corresponding bounds for the extended code of a linear cyclic code. Using these bounds, which are tight at low bit error rate, the performance advantage of soft-decision (SD) ML and HD ML over bounded-distance (BD) decoding is established     

Upper Bounds on the Number of Errors Corrected by the Koetter–Vardy Algorithm

By introducing a few simplifying assumptions we derive a simple condition for successful decoding using the Koetter-Vardy algorithm for soft-decision decoding of Reed-Solomon codes. We show that the algorithm has a significant advantage over hard decision decoding when the code rate is low, when two or more sets of received symbols have substantially different reliabilities, or when the number of alternative transmitted symbols is very small.