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.     

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     

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.     

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

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.     

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     

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.     

High-speed decoding of BCH codes (Corresp.)

A general algorithm is derived for the calculation of the error location polynomial in decoding a Bose-Chaudhuri-Hocquenguem (BCH) code. A shorter decoding time is required by the algorithm for low-weight errors because only a subset of the syndrome equations are to be satisfied. The application of the general algorithm to Berlekamp's algorithm is also presented.     

应用于遥控命令提取的快速BCH译码方法

为了保证遥控信息在有噪信道中可靠传输,结合传统的BCH码算法,根据查表法设计了一种符合分包遥控标准的快速BCH(63,56)译码方法.该译码方法相对简单,便于硬件实现,并通过FPGA对其进行设计、仿真及验证,结果证明,此译码设计具有计算速度快、占用资源少的特点,并且能应用到航天分包遥控通信中.     

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     

New time domain errors and erasures decoding algorithm for BCH codes

A new algorithm is presented for solving the key equation that simultaneously computes the error locator polynomial and the errata evaluator polynomial. The algorithm is similar to the Berlekamp algorithm but is more symmetrical in its treatment of the iterated pairs of polynomials making it particularly well suited to a highly parallel hardware implementation.<>     

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     

A new procedure for decoding cyclic and BCH codes up to actualminimum distance

The paper presents a new procedure for decoding cyclic and BCH codes up to their actual minimum distance. It generalizes the Peterson decoding procedure and the procedure of Feng and Tzeng (1991) using nonrecurrent syndrome dependence relations. For a code with actual minimum distance d to correct up to t=[(d-1)/2] errors, the procedure requires a (2t+1)×(2t+1) syndrome matrix with known syndromes above the minor diagonal and unknown syndromes and their conjugates on the minor diagonal. In contrast to previous procedures, this procedure is primarily aimed at solving for the unknown syndromes instead of determining an error-locator polynomial. Decoding is then accomplished by determining the error vector as the inverse Fourier transform of the syndrome vector (S₀, S₁, S_n-1). The authors show that with this procedure, all binary cyclic and BCH codes of length <63 (with one exception) can be decoded up to their actual minimum distance. The procedure incorporates an extension of their fundamental iterative algorithm and a majority scheme for confirming the true values computed for the unknown syndromes. The complexity of this decoding procedure is O(n³)     

A new error-locating polynomial for decoding of BCH codes (Corresp.)

We develop a new error-locating polynomial for BCH codes. This polynomial has a simple form and suggests a decoding procedure similar to Massey's step-by-step decoding.     

Errors and erasures decoding of BCH and Reed-Solomon codes for reduced M-ary orthogonal signaling

The paper presents a comparison of communication systems using different signal constellation sizes and Reed-Solomon or Bose-Chaudhuri-Hocquengem codes with different rates so that the overall required bandwidth is the same for each system. In these comparisons, the channel symbol size is smaller than the code symbol size, so that a code symbol contains parts of multiple channel symbols. Thus, the normal assumption of independent code symbols does not apply. Instead, consideration must be taken to obtain the best arrangement of channel symbols in each code symbol. Analytical expressions are developed to compare the bit error probability performance of comparable systems, based on individual codewords using errors-only decoding and errors and erasures decoding with transmission over a Rayleigh fading channel.     

A branching control circuit for Berlekamp's BCH decoding algorithm (Corresp.)

At each step in Berlekamp's iterative algorithm for BCH codes, the decoder follows one of two possible branches. This correspondence presents a slight rephrasing of the algorithm for binary codes, which results in a very simple circuit for controlling the branching process. This circuit also performs all necessary tests on the validity of the resulting error-locator polynomial.     

A simple decoding of BCH codes over GF(2m)

A simple decoding method for even minimum-distance Bose-Chaudhuri-Hochquenghem (BCH) codes is proposed. In the method the coefficients of an error locator polynomial are given as simple determinants (named Q determinants) composed of syndromes. The error evaluator is realized as a Q determinant divided by an error locator polynomial. The Q determinants can be efficiently obtained with very simple calculations on syndromes enabling the realization of a high-speed decoder of simple configuration. The number of calculations in obtaining the error locator and the error evaluator with the proposed method is smaller than that with the widely used Berlekamp-Massey algorithm when the number of correctable errors of the code is five or less. The proposed method can also be applied to the binary narrow-sense BCH codes of odd minimum distance