TRELLIS STRUCTURES OF BLOCK CODES AND THEIR DECODING

Trellis structures of block codes are discussed. L-section trellis structures of some BCH codes are presented. A fast maximum likelihood decoding algorithm for BCH codes is proposed correspondingly, the decoding problem of q-ary images of qm-ary block codes is also discussed. The direct-sum partition and the associated decoding algorithms are given for the images.     

Multisequence Linear Shift Register Synthesis and Its Application to BCH Decoding

This concise paper demonstrates the decoding of BCH codes by using a multisequence linear feedback shift register (MLFSR) synthesis algorithm. The algorithm is investigated and developed. With this algorithm, a class of good codes has been found with errorcorrecting capability at least as good as the BCH bound. The application of this algorithm to BCH decoding is discussed.     

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     

分组码的格图结构和译码

本文讨论了分组码的格图结构,给出了某些BCH码L段格图结构,并据此提出了BCH码的快速最大似然译码算法,同时讨论了qm元分组码的q元映象的译码问题,给出了q元映象的直和划分结构和相应的译码算法。     

Generalized rational interpolation over commutative rings and remainder decoding

We propose a new decoding procedure for Bose-Chaudhuri-Hocquenghem (BCH) and Reed-Solomon (RS) codes over Z/sub m/ where m is a product of prime powers. Our method generalizes the remainder decoding technique for RS codes originally introduced by Welch and Berlekamp and retains its key feature of not requiring the prior evaluation of syndromes. It thus represents a significant departure from other algorithms that have been proposed for decoding linear block codes over integer residue rings. Our decoding procedure involves a Welch-Berlekamp (WB)-type algorithm for solving a generalized rational interpolation problem over a commutative ring R with identity. The solution to this problem includes as a special case, the solution to the WB key equation over R which is central to our decoding procedure. A remainder decoding approach for decoding cyclic codes over Z/sub m/ up to the Hartmann-Tzeng bound is also presented.     

The algebraic decoding of Goppa codes

An interesting class of linear error-correcting codes has been found by Goppa [3], [4]. This paper presents algebraic decoding algorithms for the Goppa codes. These algorithms are only a little more complex than Berlekamp's well-known algorithm for BCH codes and, in fact, make essential use of his procedure. Hence the cost of decoding a Goppa code is similar to the cost of decoding a BCH code of comparable block length.     

Hard- and soft-decision decoding beyond the half minimum distance---An algorithm for linear codes (Corresp.)

A decoding algorithm for linear codes that uses the minimum weight words of the dual code as parity checks is defined. This algorithm is able to correct beyond the half minimum distance and has the capability of including soft-decision decoding. Results on applying this algorithm to quadratic residue (QR) codes, BCH codes, and the Golay codes (with and without soft-decision decoding) are presented.     

北斗导航信号BCH译码器中校正子辅助的列表译码算法

针对北斗卫星导航系统B1I信号中的BCH译码问题,该文提出一种校正子辅助的列表译码算法。首先,以校正子和汉明重量为准则构造若干错误模式列表;然后根据接收数据硬判决的校正子选择对应的错误模式列表;最后按照相关函数差测度搜索最优错误模式并译码。仿真结果表明,校正子辅助的列表译码算法在误码率10-5时,与最大似然译码算法的信噪比仅差0.08 dB,说明该方法是北斗B1I信号BCH码的一种近优译码方法;另外,该方法具有线性复杂度和可并行实现的特点。     

Decoding of alternant codes (Corresp.)

It is shown that the only modification of the Berlekamp algorithm required to decode the class of alternant codes consists of a linear transformation of the syndromes prior to the application of the algorithm. Since alternant codes include all Bose-Chaudhuri-Hocquenghem (BCH) and Goppa codes, the Chien-Choy generalized BCH codes, and the generalized Srivastava codes, all of these can be decoded with no increase in complexity over BCH decoding.     

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.     

Decoding binary 2-D cyclic codes by the 2-D Berlekamp-Masseyalgorithm

A method of decoding two-dimensional (2-D) cyclic codes by applying the 2-D Berlekamp-Massey algorithm is proposed. To explain this decoding method, the author introduces a subclass of 2-D cyclic codes, which are called 2-D BCH codes due to their similarity with BCH codes. It is shown that there are some short 2-D cyclic codes with a better cost parameter value. The merit of the approach is verified by showing several simple examples of 2-D cyclic codes     

On the problem of finding zero-concurring codewords

Zero-concurring codewords disclose a certain structure of the code that may be used for efficient soft-decision decoding and for designing DC-free codes. Methods for constructing sets of zero-concurring codewords are presented for several families of codes. For the general case an algorithm solution of the problem is offered. A table of results obtained using the proposed techniques is supplied for all the primitive narrow-sense binary BCH codes of length up to 127     

Construction and decoding of a class of algebraic geometry codes

A class of codes derived from algebraic plane curves is constructed. The concepts and results from algebraic geometry that were used are explained in detail; no further knowledge of algebraic geometry is needed. Parameters, generator and parity-check matrices are given. The main result is a decoding algorithm which turns out to be a generalization of the Peterson algorithm for decoding BCH decoder codes     

Application of circulant matrices to the construction and decodingof linear codes

The Fourier transform technique is used to analyze and construct several families of double-circulant codes. The minimum distance of the resulting codes is lower-bounded by 2√r and can be decoded easily employing the standard BCH decoding algorithm or the majority-logic decoder of Reed-Muller codes. A decoding procedure for Reed-Solomon codes is presented, based on a representation of the parity-check matrix by circulant blocks. The decoding procedure inherits both the (relatively low) time complexity of the Berlekamp-Massey algorithm and the hardware simplicity characteristic of Blahut's algorithm. The procedure makes use of the encoding circuit together with a reduced version of Blahut's decoder     

Iterative Decoding of Multiple-Step Majority Logic Decodable Codes

We investigate the performance of iterative decoding algorithms for multistep majority logic decodable (MSMLD) codes of intermediate length. We introduce a new bit-flipping algorithm that is able to decode these codes nearly as well as a maximum-likelihood decoder on the binary-symmetric channel. We show that MSMLD codes decoded using bit-flipping algorithms can outperform comparable Bose-Chaudhuri-Hocquenghem (BCH) codes decoded using standard algebraic decoding algorithms, at least for high bit-flip rates (or low and moderate signal-to-noise ratios (SNRs)).     

A generalized Euclidean algorithm for multisequence shift-registersynthesis

The problem of finding a linear-feedback shift register of shortest length capable of generating prescribed multiple sequences is considered. A generalized Euclidean algorithm, which is based on a generalized polynomial division algorithm, is presented. A necessary and sufficient condition for the uniqueness of the solution is given. When the solution is not unique, the set of all possible solutions is also derived. It is shown that the algorithm can be applied to the decoding of many cyclic codes for which multiple syndrome sequences are available. When it is applied to the case of a single sequence, the algorithm reduces to that introduced by Y. Sugiyama et al. (Inf. Control, vol.27, p.87-9, Feb. 1975) in the decoding of BCH codes     

Reed-Solomon codes for correcting phased error bursts

A code structure is introduced that represents a Reed-Solomon (RS) code in two-dimensional format. Based on this structure, a novel approach to multiple error burst correction using RS codes is proposed. For a model of phased error bursts, where each burst can affect one of the columns in a two-dimensional transmitted word, it is shown that the bursts can be corrected using a known multisequence shift-register synthesis algorithm. It is further shown that the resulting codes posses nearly optimal burst correction capability, under certain probability of decoding failure. Finally, low-complexity systematic encoding and syndrome computation algorithms for these codes are discussed. The proposed scheme may also find use in decoding of different coding schemes based on RS codes, such as product or concatenated codes.     

Decoding beyond the BCH bound using multiple sets of syndrome sequences (Corresp.)

Many cyclic codes are generated by polynomials possessing more than one set of consecutive roots. Thus more than one set of syndrome sequences are available for decoding. In this correspondence, a decoding method based on Berlekamp's iterative algorithm is presented which makes use of the multiple sets of syndrome sequences for decoding such cyclic codes beyond the BCH bound.     

Decoding binary two-error correcting cyclic codes with Zechlogarithms

A decoding method for binary two-error correcting cyclic codes whose generator polynomials have at most two irreducible factors is presented. This class includes binary narrow-sense BCH codes with designed distance 5. The decoding algorithm uses the Zech logarithm for the finite field in which the roots of the code lie     

DTMB标准中BCH译码算法及其FPGA的实现

首先证明了DTMB标准中采用的BCH码是纠错能力为1的循环汉明码,并基于此提出了适用于该BCH码的译码算法,及其串行和并行两种FPGA实现电路。考虑到该BCH码缩短码的特性,通过修改差错检测电路,使其译码时延缩短34%。实现结果表明,译码器译码正确无误,FPGA资源占用极少。串行译码器总时延为762个时钟周期,最大工作时钟频率可达357MHz。并行译码器总时延仅为77个时钟周期,最大工作时钟频率可达276MHz。