Studying the locator polynomials of minimum weight codewords of BCHcodes

Primitive binary cyclic codes of length n=2^m are considered. A BCH code with designed distance δ is denoted B(n,δ). A BCH code is always a narrow-sense BCH code. A codeword is identified with its locator polynomial, whose coefficients are the symmetric functions of the locators. The definition of the code by its zeros-set involves some properties for the power sums of the locators. Moreover, the symmetric functions and the power sums of the locators are related to Newton's identities. An algebraic point of view is presented in order to prove or disprove the existence of words of a given weight in a code. The principal result is the true minimum distance of some BCH codes of length 255 and 511. which were not known. The minimum weight codewords of the codes B(n2^h -1) are studied. It is proved that the set of the minimum weight codewords of the BCH code B(n,2^m-2-1) equals the set of the minimum weight codewords of the punctured Reed-Muller code of length n and order 2, for any m     

Multiple error detection and identification via signature analysis

Signature analysis has been used widely for fault detection as a part of Built-In Self Test (BIST). In this paper we show how signature analysis can be used not only for fault detection but also for identification of multiple errors produced by faults in the circuits under test. We construct Signature Analysis Registers (SARs) to detect and identify any specified number of errors in the input polynomials by choosing proper characteristic polynomials. To detect and identifyr errors in an input bit stream ofm bits, we use a polynomialg _r (x)=1cm (f ₁ (x), f ₃ (x), ..., f _2r?1 (x)) as the characteristic polynomial for the SAR for any polynomialf ₁ (x), where lcm represents the least common multiple of polynomials al $$fi(x) = Res_t (f_1 (t),x - t^i ), i = 3,...,2r - 1,$$ Res _t denotes thet-Resultant, andm is less than the order off ₁ (x). Given a faulty signature produced by an SAR constructed as described, we present an algorithm for the identification of the actual error bits in the input polynomial to the SAR. We also extend the use of BCH codes for error detection and correction to include nonprimitive polynomials.     

An algebraic complete decoding for double-error-correcting binary BCH codes

An algebraic complete decoding for double-error-correcting binary BCH codes of primitive length is derived. The decoding is done more quickly than the step-by-step decoding devised by Hartmann. And if an error pattern corresponding with syndromess ₁ ands ₂ has weight 3, the decoding can find all error patterns of weight 3 corresponding with these syndromes. At the same time, a discriminant for a polynomial of degree 3 overGF(2 ^m ) has three distinct roots inGF2 ^m ) is also derived. The discriminant is very important for complete decoding of triple-error-correcting binary BCH codes.     

有限域上非本原BCH码的对偶包含判定

 循环陪集在经典和量子纠错编码理论中具有非常重要的作用.根据CSS编码定理知,利用经典BCH码构造量子BCH码时需要判断经典BCH码是否包含其对偶码.本文给出了循环陪集的若干重要性质,根据这些性质得到了判断有限域上非本原BCH码是否包含其对偶码的准则.本文给出的判断准则时间复杂度为多项式的,并且该判断准则对本原BCH码也适用.     

Asymptotic performance comparison of concatenated (turbo) codes over GF(4)

In this paper, we investigate and compare the asymptotic performance of concatenated convolutional coding schemes over GF(4) over additive white Gaussian noise (AWGN) channels. Both parallel concatenated codes (PCC) and serial concatenated codes (SCC) are considered. We construct such codes using optimal non‐binary convolutional codes where optimality is in the sense of achieving the largest minimum distance for a fixed number of encoder states. Code rates of the form k₀/(k₀ + 1) for k₀=1, 8, and 64 are considered, which suite a wide spectrum of communications applications. For all of these code rates, we find the minimum distance and the corresponding multiplicity for both concatenated code systems. This is accomplished by feeding the encoder with all possible weight‐two and weight‐three input information patterns and monitoring, at the output of the encoder, the weight of the corresponding codewords and their multiplicity. Our analytical results indicate that the SCC codes considerably outperform their counterpart PCC codes at a much lower complexity. Inspired by the superiority of SCC codes, we also discuss a mathematical approach for analysing such codes, leading to a more comprehensive analysis and allowing for further improvement in performance by giving insights on designing a proper interleaver that is capable of eliminating the dominant error patterns. Copyright © 2004 John Wiley & Sons, Ltd.     

Analysis and performance evaluation of new coding options for space telecommand links ‐ Part I: AWGN channels

We investigate and compare, over the additive white Gaussian noise channel, different options for updating the error correcting code currently used in space mission telecommand links. Besides some more consolidated proposals, using low‐density parity‐check codes, we characterize and assess the performance of alternative schemes, based on parallel turbo codes and soft‐decision decoded Bose‐Chaudhuri‐Hocquenghem (BCH) codes. The analysis considers relevant metrics like the codeword error rate, the frame error rate, and the undetected frame error rate. The considered codes include binary and non‐binary low‐density parity‐check codes, parallel turbo codes and extended BCH codes, with different decoding algorithms. The complexity of the various schemes and possible limits for their application are considered and discussed. Several numerical examples are provided. International Journal of Satellite Communications and Networking. Copyright © 2014 John Wiley & Sons, Ltd.     

Some Remarks on BCH Bounds and Minimum Weights of Binary Primitive BCH Codes

It is shown that ifm neq 8, 12andm > 6, there are some binary primitive BCH codes (BCH codes in a narrow sense) of length2^{m} - 1whose minimum weight is greater than the BCH bound. This gives a negative answer to the question posed by Peterson [1] of whether or not the BCH bound is always the actual minimum weight of a binary primitive BCH code. It is also shown that for any evenm geq 6, there are some binary cyclic codes of length2^{m} - 1that have more information digits than the primitive BCH codes of length2^{m} - 1with the same minimum weight.     

On 2D finite support convolutional codes: An algebraic approach

Two-dimensional (2D) finite codes are defined as families of compact support sequences indexed in Z × Z and taking values in F ⁿ , F a Galois field. Several properties of encoders, decoders and syndrome decoders are discussed under different hypotheses on the code structure, and related to the injectivity and primeness of the corresponding polynomial matrices in two variables. Dual codes are finally introduced as families of parity checks on a given modular code, and related to the standard theory of 2D behaviors.     

基于删余等效的高码率卷积码的低复杂度译码方法

根据删余卷积码具有较低的译码复杂度这一特征,提出了一种适用于普通高码率卷积码的低复杂度译码方法。通过多项式生成矩阵表示法,推导了删余卷积码的等效多项式生成矩阵,给出了等效多项式生成矩阵的计算准则。在分析删余卷积码与相同码率普通卷积码的等效关系和区别的基础上,提出了高码率卷积码的删余等效并给出了计算高码率卷积码删余等效后原始码和删余矩阵的方法。以原始码和删余矩阵构成的删余等效结构为译码基础,实现了高码率卷积码的低复杂度译码,其译码复杂度与原始码相当。仿真结果表明,删余等效译码方法相对于正常译码方法,其性能损失很小。     

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     

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

秩距离BCH码的进一步研究

本文作者在“关于秩距离BCH码的校验矩阵及其秩距离”一文中提出了秩距离BCH码的概念，讨论了所给秩距离BCH码为最大秩距离BCH码时，码的生成多项式的根应满足的条件。本文在此基础上，讨论当线性秩距离码的生成多项式具有广义连续根时，它能构成秩距离BCH码的充分条件并给出了此充分条件。     

关于BCH码的广义Hamming重量上,下限

一个线性码的第ｒ广义Ｈａｍｍｉｎｇ重量是它任意ｒ维子码的最小支集大小。本文给出了一般（本原、狭义）ＢＣＨ码的广义Ｈａｍｍｉｎｇ重量下限和一类ＢＣＨ码的广义Ｈａｍｍｉｎｇ重量上限     

一种基于与BCH码等价原理的m序列重构算法

该文针对现有m序列特征多项式估计方法在高阶高误码条件下的估计效率不高,精度不够的问题展开研究,通过分析m序列和BCH码的生成原理,得出二者之间的等价关系,进而提出了一种新的m序列特征多项式的估计算法。该算法通过构造与之等价的BCH码,利用其良好的纠错性能,实现高误码条件下的m序列特征多项式的估计,仿真结果表明本算法能较好地解决误码条件下的m序列特征多项式估计问题,运算速度主要适用于通信信号处理中常用20阶以内的m序列分析问题。     

On the dimension and minimum distance of BCH codes over GF(q)

In this paper, only narrow-sense primitive BCH codes over GF(q) are considered. A formula, that can be used in many cases, is first presented for computing the dimension of BCH codes. It improves the result given by MacWilliams and Sloane in 1977. A new method for finding the dimension of all types of BCH codes is proposed. In second part, it is proved that the BCH bound is the leader of some cyclotomic coset, and we guess that the minimum distance for any BCH code is also the leader of some cyclotomic coset. Supported by the National Natural Science Foundation of China     

New Error Control Algorithms for Residue Number System Codes

We propose and describe new error control algorithms for redundant residue number systems (RRNSs) and residue number system product codes. These algorithms employ search techniques for obtaining error values from within a set of values (that contains all possible error values). For a given RRNS, the error control algorithms have a computational complexity of t·O(log₂ n + log₂ m?) comparison operations, where t denotes the error correcting capability, n denotes the number of moduli, and m? denotes the geometric average of moduli. These algorithms avoid most modular operations. We describe a refinement to the proposed algorithms that further avoids the modular operation required in their respective first steps, with an increase of ?log₂ n? to their computational complexity. The new algorithms provide significant computational advantages over existing methods.     

Two applications of cyclotomic cosets to certain BCH codes (Corresp.)

A more accurate designed distance bound is given for a subclass of narrow-sense primitive Bose-Chaudhuri-Hocquenghem (BCH) codes for which Mann has found the number of information digits. It is also determined when two consecutive odd integers are in the same cyclotomic coset.     

卷积码盲识别方法研究

提出了一种码率删除卷积码的盲识别算法.该算法基于卷积码的线性特性和校验性质,利用一种优化方法求解二元域线性方程组,估计出校验多项式矩阵,并建立删除卷积码的数学变换模型,由校验多项式矩阵估计出删除卷积码的源码生成多项式矩阵和删除模式.     

一种删除卷积码识别方法研究

伴随自适应编码调制（AMC）技术的提出与应用,删除卷积码识别已成为自适应通信领域一个亟需解决的问题.针对以（2,1,m）卷积码为源码的删除卷积码识别问题,提出了一种基于构建分析矩阵和遍历删除模式的识别方法.该方法首先由构建的分析矩阵识别出删除卷积码码率和校验多项式矩阵,进而通过遍历确定删除模式,推导得出（2,1,m）源卷积码的生成多项式矩阵.最后,通过MATLAB实例仿真验证了该方法的有效性,并分析了其容错性能.