On decoding BCH codes

The Gorenstein-Zierler decoding algorithm for BCH codes is extended, modified, and analyzed; in particular, we show how to correct erasures as well as errors, exhibit improved procedures for finding error and erasure values, and consider in some detail the implementation of these procedures in a special-purpose computer.     

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.     

Efficient heuristic search algorithms for soft-decision decoding oflinear block codes

Efficient new algorithms are presented for maximum-likelihood and suboptimal soft-decision decoding algorithms for linear block codes. The first algorithm, MA*, improves the efficiency of the A* decoding algorithm, conducting the heuristic search through a code tree while exploiting code-specific properties. The second algorithm, H*, reduces search space by successively estimating the cost of the minimum-cost codeword with a fixed value at each of the most reliable and linearly independent components of the received message. The third algorithm, directed search, finds the codeword closest to the received vector by exploring a continuous search space. The strengths of these three algorithms are combined in a hybrid algorithm, applied to the (128,64), the (256,131), and the (256,139) binary-extended Bose-Chaudhuri-Hocquenghem (BCH) codes. Simulation results show that this hybrid algorithm can efficiently decode the (128,64) code for any signal-to-noise ratio, with near-optimal performance. Previously, no practical decoder could have decoded this code with such a performance for all ranges of signal-to-noise ratio     

Simple algorithms for BCH decoding

Proposes some simple algorithms for decoding BCH codes. The authors show that the pruned FFT is an effective method for evaluating syndromes and for finding the roots of error-locator polynomials. They show that a simple variation of the basic Gaussian elimination procedure can be adapted to compute the error-locator polynomial efficiently for codes with small designed distance. Finally, they give a procedure for computing the error values that has half the complexity of the Forney algorithm     

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.     

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     

Parallel decoding of binary BCH codes

A parallel decoding procedure for the BCH codes is introduced, which is particularly useful for decoding BCH codes with small error-correcting capability. The high regularity inherent in the scheme enable it to be easily implemented with VLSI circuits.<>     

Method of soft-decision decoding of block codes

A method of soft-decision decoding of a block code was considered as a solution of the problem of estimating “soft” values of information symbols by the maximum-likelihood method. Estimation of values of information symbols was conducted under conditions where levels of continuous output signals of a discriminator (demodulator) were subjected to an appropriate interpretation with due regard for the coding rule.     

Inversionless decoding of binary BCH codes

The iterative algorithm for decoding binary BCH codes presented by Berlekamp and, in an alternative form, by Massey is modified to eliminate inversion. Because inversion in a finite field is time consuming and requires relatively complex circuitry, this new algorithm should he useful in practical applications of multiple-error-correcting binary BCH codes.     

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.     

Algebraic properties of BCH codes useful for decoding

In this paper theorems are presented which allow the simplified decoding of (n, k, δ) BCH codes in certain cases of practical interest. Such results are in a way implicit in the theory of BCH codes, but so far have not appeared explicitly in the literature. It is shown that any t₀ errors, 1 ? t₀ ? δ-1, can be detected by using any set of only t₀ consecutive coefficients of the syndrome polynomial. The correction of any t₀ errors, 1 ? t₀ ? [(δ-1)/2], can be performed by using any set of 2t₀ consecutive coefficients of the syndrome polynomial, where [x] means the integer part of x. Similar results are derived for punctured BCH codes. In this case sets of t₀ or 2t₀ consecutive coefficients, respectively, for detecting or correcting t₀ errors, are selected from the δ-1-p higher-order coefficients of the modified syndrome polynomial, where p is the number of digits punctured from a code word. These results hold true even when the punctured digits are not consecutive.     

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     

Transform decoding of BCH codes over Zm

For BCH codes with symbols from rings of residue class integers modulo m, denoted by Z_m , we introduce the analogue of Blahut's frequency domain approach for codes over finite fields and show that the problem of decoding these codes is equivalent to the minimal shift register synthesis problem over Galois rings. A minimal shift register synthesis algorithm over Galois rings is obtained by straightforward extention of the Reeds-Sloane algorithm which is for shift register synthesis over Z_m .     

Complete decoding of triple-error-correcting binary BCH codes

An extensive study of binary triple-error-correcting codes of primitive lengthn = 2^{m} - 1is reported that results in a complete decoding algorithm whenever the maximum coset weightW_{max}is five. In this regard it is shown thatW_{max} = 5when four dividesm, and strong support is provided for the validity of the conjecture thatW_{max} = 5for allm. The coset weight distribution is determined exactly in some cases and bounded in others.     

Bit-error probability for maximum-likelihood decoding of linearblock codes and related soft-decision decoding methods

In this correspondence, the bit-error probability P_b for maximum-likelihood decoding of binary linear block codes is investigated. The contribution P_b(j) of each information bit j to P_b is considered and an upper bound on P_b(j) is derived. For randomly generated codes, it is shown that the conventional approximation at high SNR P_b≈(d_H/N).P_s, where P_s represents the block error probability, holds for systematic encoding only. Also systematic encoding provides the minimum P_b when the inverse mapping corresponding to the generator matrix of the code is used to retrieve the information sequence. The bit-error performances corresponding to other generator matrix forms are also evaluated. Although derived for codes with a generator matrix randomly generated, these results are shown to provide good approximations for codes used in practice. Finally, for soft-decision decoding methods which require a generator matrix with a particular structure such as trellis decoding, multistage decoding, or algebraic-based soft-decision decoding, equivalent schemes that reduce the bit-error probability are discussed. Although the gains achieved at practical bit-error rates are only a fraction of a decibel, they remain meaningful as they are of the same orders as the error performance differences between optimum and suboptimum decodings. Most importantly, these gains are free as they are achieved with no or little additional circuitry which is transparent to the conventional implementation     

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.     

On the decoding of Reed-Solomon and BCH codes over integer residuerings

We present a decoding procedure for Reed-Solomon (RS) and BCH codes defined over an integer residue ring pgZ_q, where q is a power of a prime p. The proposed decoding procedure, as for RS and BCH codes over fields, consists of four major steps: (1) calculation of the syndromes; (2) calculation of the “elementary symmetric functions,” by a modified Berlekamp-Massey (1968, 1969) algorithm for commutative rings; (3) calculation of the error location numbers; and (4) calculation of the error magnitudes. The proposed decoding procedure also applies to the synthesis of a shortest linear-feedback shift register (LFSR), capable of generating a prescribed finite sequence of elements lying in a commutative ring with identity