Number of information symbols in polynomial codes

Polynomial codes and their dual codes as introduced by Kasami, Lin, and Peterson have considerable algebraic and geometric structure. It has been shown that these codes contain many well-known classes of cyclic codes as subclasses, such as BCH codes, projective geometry codes (PG codes), Euclidean geometry codes (EG codes), and generalized Reed-Muller codes (GRM codes). In this paper, combinatorial expressions for the number of information symbols and parity-check symbols in polynomial codes are derived. The results are applied to two important subclasses of codes, the PG codes and EG codes.     

Polynomial codes

A class of cyclic codes is introduced by a polynomial approach that is an extension of the Mattson-Solomon method and of the Muller method. This class of codes contains several important classes of codes as subclasses, namely, BCH codes, Reed-Solomon codes, generalized primitive Reed-Muller codes, and finite geometry codes. Certain fundamental properties of this class of codes are derived. Some subclasses are shown to be majority-logic decodable.     

Euclidean Geometry LDPC-VBLAST System Design and Performance Evaluation

Among popular multi-transmit and multi-receive antennas techniques, the VBLAST (Vertical Bell Laboratories Layered Space-Time) architecture has been shown to be a good solution for wireless communications applications that require the transmission of data at high rates. Recently, the application of efficient error correction coding schemes such as low density parity-check (LDPC) codes to systems with multi-transmit and multi-receive antennas has shown to significantly improve bit error rate performance. Although irregular LDPC codes with non-structure are quite popular due to the ease of constructing the parity check matrices and their very good error rate performance, the complexity of the encoder is high. Simple implementation of both encoder and decoder can be an asset in wireless communications applications. In this paper, we study the application of Euclidean geometry LDPC codes to the VBLAST system. We assess system performance using different code parameters and different numbers of antennas via Monte-Carlo simulation and show that the combination of Euclidean geometry LDPC codes and VBLAST can significantly improve bit error rate performance. We also show that interleaving data is necessary to improve performance of LDPC codes when a higher number of antennas is, used in order to mitigate the effect of error propagation. The simplicity of the implementation of both encoder and decoder makes Euclidean geometry LDPC codes with VBLAST system attractive and suitable for practical applications.     

Majority decoding the nonorthogonal parity checks (Corresp.)

A new bound on the error-correcting capability of majority decoding using nonorthogonal parity checks is derived. The new bound is then applied to a class of Euclidean geometry codes.     

On majority-logic decoding of finite geometry codes

In this paper, an improved decoding algorithm for codes that are constructed from finite geometries is introduced. The application of this decoding algorithm to Euclidean geometry (EG) and projective geometry (PG) codes is further discussed. It is shown that these codes can be orthogonalized in less than or equal to three steps. Thus, these codes are majority-logic decodable in no more than three steps. Our results greatly reduce the decoding complexity of EG and PG codes in most cases. They should make these codes very attractive for practical use in error-control systems.     

一种RS码快速盲识别方法

提出了一种RS码的快速盲识别方法.该方法基于RS码的等效二进制分组码的循环移位特性,通过欧几里德算法计算循环移位前后码字的最大公约式,根据最大公约式指数的相关性来估计码长,并快速剔除含错码字,进而利用伽罗华域的傅里叶变换(Galois Field Fourier Transform,GFFT)实现RS码的本原多项式和生...     

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     

关于Justesen代数几何码

本文通过建立保持Hamming距离的同构,给出了研究Justesen等(1989)所构造的代数几何码的一般方法,并取得一些新的结果。本文在进行译码研究时,首次把同类型的较小的代数几何码的码字与错误位置多项式的值相对应,从而清晰地揭示了译码过程,以及纠错能力。本文还得到一般代数几何码维数的上界和下界。最后给出了一个容易理解的译码算法。此算法类似于RS码的Peterson译码算法。     

F4m上厄米特自正交常循环码

有限域上常循环码具有丰富的代数结构,其编译码电路容易实现,因而在信息传输实践中具有重要的应用.该文研究了一类有限域上任意长度的厄米特自正交常循环码的结构,给出了此类有限域上厄米特自正交常循环码的生成多项式与存在条件,确立了此类有限域上厄米特自正交常循环码的计数公式,并且利用此类有限域上偶长度的厄米特自正交常循环码构造了最优的量子码.     

General principles for the algebraic decoding of cyclic codes

This paper provides two theorems for decoding all types of cyclic codes. It is shown that from a polynomial ideal point of view, the decoding problems of cyclic codes are closely related to the monic generators of certain polynomial ideals. This conclusion is also generalized to the decoding problems of algebraic geometry codes.<>     

On Justesen’s algebraic geometry codes

An isomorphism preserving Hamming distance between two algebraic geometry (AG) codes is presented to obtain the main parameters of Justesen’s algebraic geometry (JAG) codes. To deduce a simple approach to the decoding algorithm, a code word in a “small” JAG code is used to correspond to error-locator polynomial. By this means, a simple decoding procedure and its ability of error correcting are explored obviously. The lower and upper bounds of the dimension of AG codes are also obtained.     

Multifold Euclidean geometry codes

This paper presents a class of majority-logic decodable codes whose structure is based on the structural properties of Euclidean geometries (EG) and codes that are invariant under the affine group of permutations. This new class of codes contains the ordinary EG codes and some generalized EG codes as subclasses. One subclass of new codes is particularly interesting: they are the most efficient majority-logic decodable codes that have been constructed.     

序列综合与一类代数几何码的有效译码＊

Berlekamp-Massey算法是用来解决域上序列的综合问题。本文用多元多项式系数的齐次方程给出这个问题的新的数学模型。本文利用多项式理想论中的Grbner基理论,给出了上述模型的算法。此算法适用于环F[X_1,…,X_n]中,当n=2时,就类似于Euclid算法。文中算法还可用于求解一类代数几何码的快速译码问题。     

多个序列综合问题的新模型及其应用

本文提出新的数学模型,用来刻划序列的综合问题,并将其推广,揭示了可用Grbner基理论解决序列的综合问题,并得到有效的算法,从而成功地开辟了解决多个序列综合问题的新途经.本文另一重要结果是给出了J.Justesen等构造的一类代数几何码(JAG码)的有效译码算法,此算法是Euclid算法的非平凡推广.     

Special hardware for computing the probability of undetected errorfor certain binary CRC codes and test results

A hardware device for efficiently evaluating the probability of undetected error for a class of CRC error detection codes with a large number of parity check digits is described. The generator polynomial for the codes in this class are of the form g(x)=(1+x)p(x) where p(x) is a primitive irreducible polynomial. The degree of g(x), R, is the number of parity check digits. Using this hardware, a search was conducted for codes in this class (for 8⩽R⩽39) which are “proper” for shortened block lengths. A table of codes satisfying this condition is included     

Quasi-cyclic LDPC codes with high-rate and low error floor based on Euclidean geometries

An improved Euclidean geometry approach to design quasi-cyclic (QC) Low-density parity-check (LDPC) codes with high-rate and low error floor is presented.The constructed QC-LDPC codes with high-rate ha...     

Projective Reed-Muller codes

A class of codes in the Reed-Muller family, the projective Reed-Muller codes (PRM codes), is studied. The author defines the PRM codes of all orders and discusses their relation to polynomial codes. The exact parameters of PRM codes are given. The duals are characterized, and, in parallel to the classical works on generalized Reed-Muller codes, the cyclic properties are studied. Tables over parameters of the codes are given     

The art of signaling: fifty years of coding theory

In 1948 Shannon developed fundamental limits on the efficiency of communication over noisy channels. The coding theorem asserts that there are block codes with code rates arbitrarily close to channel capacity and probabilities of error arbitrarily close to zero. Fifty years later, codes for the Gaussian channel have been discovered that come close to these fundamental limits. There is now a substantial algebraic theory of error-correcting codes with as many connections to mathematics as to engineering practice, and the last 20 years have seen the construction of algebraic-geometry codes that can be encoded and decoded in polynomial time, and that beat the Gilbert-Varshamov bound. Given the size of coding theory as a subject, this review is of necessity a personal perspective, and the focus is reliable communication, and not source coding or cryptography. The emphasis is on connecting coding theories for Hamming and Euclidean space and on future challenges, specifically in data networking, wireless communication, and quantum information theory     

A new decoding algorithm for correcting both erasures and errors of Reed-Solomon codes

In this paper, a high efficient decoding algorithm is developed here in order to correct both erasures and errors for Reed-Solomon (RS) codes based on the Euclidean algorithm together with the Berlekamp-Massey (BM) algorithm. The new decoding algorithm computes the errata locator polynomial and the errata evaluator polynomial simultaneously without performing polynomial divisions, and there is no need for the computation of the discrepancies and the field element inversions. Also, the separate computation of the Forney syndrome needed in the decoder is completely avoided. As a consequence, the complexity of this new decoding algorithm is dramatically reduced. Finally, the new algorithm has been verified through a software simulation using C/sup ++/ language. An illustrative example of (255,239) RS code using this program shows that the speed of the decoding process is approximately three times faster than that of the inverse-free Berlekamp-Massey algorithm.     

Coding for Satellite Communication

This paper discusses a number of coding techniques for future satellite communication; they include Reed-Solomon error decoding for message blocks, probabilistic decoding techniques for punctured convolutional codes, and planar Euclidean geometry difference set codes for random multiple access applications. The provision of code concatenation, helical interleaving, and simulation results of new punctured convolutional codes are included. A number of coded satellite systems that demonstrate the usefulness of coding in satellite communications are described.