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.     

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     

On decoding concatenated codes

The correcting properties of concatenated codes with parallel decoding over an additive channel are investigated. The ith inner decoder's output is a codeword if the Euclidean distance between the received vector and some codeword is less than Δ_i and an erasure otherwise. The outer decoders correct errors and erasures. The error-correcting capability, which is taken to be the minimum length of any noise vector that can cause an error, is obtained for a bank of z inner and outer decoders as a function of the thresholds used. The set of thresholds that maximize the error-correcting capability is also found. It is shown that for a small number of branches, the error-correcting capability is nearly as large as any decoder     

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     

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.     

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     

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.     

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.     

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.     

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.     

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.     

Two decoding algorithms for tailbiting codes

The paper presents two efficient Viterbi decoding-based suboptimal algorithms for tailbiting codes. The first algorithm, the wrap-around Viterbi algorithm (WAVA), falls into the circular decoding category. It processes the tailbiting trellis iteratively, explores the initial state of the transmitted sequence through continuous Viterbi decoding, and improves the decoding decision with iterations. A sufficient condition for the decision to be optimal is derived. For long tailbiting codes, the WAVA gives essentially optimal performance with about one round of Viterbi trial. For short- and medium-length tailbiting codes, simulations show that the WAVA achieves closer-to-optimum performance with fewer decoding stages compared with the other suboptimal circular decoding algorithms. The second algorithm, the bidirectional Viterbi algorithm (BVA), employs two wrap-around Viterbi decoders to process the tailbiting trellis from both ends in opposite directions. The surviving paths from the two decoders are combined to form composite paths once the decoders meet in the middle of the trellis. The composite paths at each stage thereafter serve as candidates for decision update. The bidirectional process improves the error performance and shortens the decoding latency of unidirectional decoding with additional storage and computation requirements. Simulation results show that both proposed algorithms effectively achieve practically optimum performance for tailbiting codes of any length.     

Iterative decoding of serially concatenated convolutional codes andMSK

The performance of iterative decoding and demodulation of serially concatenated convolutional codes and minimum shift keying (MSK) is studied. It is shown that by appropriately combining the trellises of MSK and the inner code, a high performance coded modulation system can be achieved. Simulation results also confirms that recursive inner codes are essential for a serially concatenated system     

On concatenated zigzag codes and their decoding schemes

In this letter, we show that a concatenated zigzag code can be viewed as a low-density parity-check (LDPC) code. Based on the bipartite graph representation for such a parallel-concatenated code, various sum-product based decoding algorithms are introduced and compared. The results show that the improved versions of sum-product algorithm exhibit better convergence rate while maintaining the essential parallel form.     

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 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²)     

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.     

Code characteristic matching for iterative decoding of serially concatenated codes

The design of serially concatenated codes has yet been dominated by optimizing asymptotic slopes of error probability curves. We propose mutual information transfer characteristics for soft in/soft out decoders to design serially concatenated codes based on the convergence behavior of iterative decoding. The exchange of extrinsic information is visualized as a decoding trajectory in the Extrinsic Information Transfer Chart (exit chart). By finding matching pairs of inner and outer decoder transfer characteristics we are able to construct serially concatenated codes whose iterative decoder converges towards low bit error rate at signal- to- noise ratios close to the theoretical limits.     

Reduced-complexity decoding algorithms for unitary space-time codes

Two reduced-complexity decoding algorithms for unitary space-time codes based on tree-structured constellation are presented. In this letter original unitary space-time constellation is divided into several groups. Each one is treated as the leaf nodes set of a subtree. Choosing the unitary signals that represent each group as the roots of these subtrees generates a tree-structured constellation. The proposed tree search decoder decides to which sub tree the receive signal belongs by searching in the set of subtree roots. The final decision is made after a local search in the leaf nodes set of the selected sub tree. The adjacent subtree joint decoder performs joint search in the selected sub tree and its ＂surrounding＂ subtrees, which improves the Bit Error Rate （BER） performance of purely tree search method. The exhaustively search in the whole constellation is avoided in our proposed decoding algorithms, a lower complexity is obtained compared to that of Maximum Likelihood （ML） decoding. Simulation results have also been provided to demonstrate the feasibility of these new methods.