Character sum constructions of constrained error-correcting codes

We estimate parameters of constrained error-correcting codes constructed by means of additive and multiplicative characters. To get the bounds we derive estimates for some incomplete character sums.This work was supported in part by the Academy of Finland. The first-named author would also like to express his gratitude to the Department of Mathematics of the University of Turku for the hospitality during his visit in August, 1992.     

On minimum distance bounds for abelian codes

This paper is an exposition of two methods of formulating a lower bound for the minimum distance of a code which is an ideal in an abelian group ring. The first, a generalization of the cyclic BCH (Bose-Chaudhuri-Hoquenghem) bound, was proposed by Camion [2]. The second method, presented by Jensen [4], allows the application of the BCH bound or any of its improvements by viewing an abelian code as a direct sum of concatenations of cyclic codes. This second method avoids the mathematical analysis required for a direct generalization of a cyclic bound to the abelian case. It can produce a lower bound that improves the generalized BCH bound. We present simple algorithms for 1) deriving the generalized BCH bound for an abelian code 2) determining direct sum decompositions of an abelian code to concatenated codes and 3) deriving a bound on an abelian code, viewed as a direct sum of concatenated codes, by applying the cyclic BCH bound to the inner and outer code of each concatenation. Finally, we point out the applicability of these methods to codes that are not ideals in abelian group rings.     

Bounds and constructions of asymmetric or unidirectional error-correcting codes

Binary block codes for correctingt symmetric, asymmetric and unidirectional errors are calledt-SyEC codes,t-AsEC codes andt-UEC codes respectively. Two tables with bounds on the cardinality of binary block codes for correcting asymmetric and unidirectional errors respectively are presented. They include many improvements over the existing literature. The lower bounds follow from explicit constructions, while the upper bounds are obtained by applying combinatorial arguments to the weight structure of such codes.The authors are with Department of Mathematics and Computing Science of Eindhoven University of Technology, The Netherlands. Part of this work was presented at the IEEE International Symposium on Information Theory, Budapest, 1991     

Group codes on certain algebraic curves with many rational points

We construct a series of algebraic geometric codes using a class of curves which have many rational points. We obtain codes of lengthq ² over _q , whereq = 2q ₀ ² andq ₀ = 2 ⁿ , such that dimension + minimal distance q ² + 1 – q ₀ (q – 1). The codes are ideals in the group algebra _q [S], whereS is a Sylow-2-subgroup of orderq ² of the Suzuki-group of orderq ² (q ² + 1)(q – 1). The curves used for construction have in relation to their genera the maximal number of GF _q -rational points. This maximal number is determined by the explicit formulas of Weil and is effectively smaller than the Hasse—Weil bound.Supported by Deutsche Forschungsgemeinschaft while visiting Essen University     

Rotational invariance of two-level group codes over dihedral and dicyclic groups

Phase-rotational invariance properties for two-level constructed, (using a binary code and a code over a residue class integer ring as component codes) Euclidean space codes (signal sets) in two and four dimensions are discussed. The label codes are group codes over dihedral and dicyclic groups respectively. A set of necessary and sufficient conditions on the component codes is obtained for the resulting signal sets to be rotationally invariant to several phase angles.     

Structural properties and enumeration of quasi cyclic codes

Given any finite fieldF _q , an (N, K) quasi cyclic code is defined as aK dimensional linear subspace ofF _q ^N which is invariant underT ⁿ for some integern, 0 <n N, and whereT is the cyclic shift operator. Quasi cyclic codes are shown to be isomorphic to theF _q []-submodules ofF _q ^N where the product(gl)· is naturally defined as ₀ + ₁T ⁿ +...+ _m T ^mn if()= ₀ + ₁ +...+ _{m m} .In the case where (N/n, q)=1, all quasi cyclic codes are shown to be decomposable into the direct sum of a fixed number of indecomposable components called irreducible cyclicF _q []-submodules providing for the complete characterisation and enumeration of some subclasses of quasi cyclic codes including the cyclic codes, the quasi cyclic codes with a cyclic basis, the maximal and the irreducible ones. Finally a general procedure is presented which allows for the determination and characterisation of the dual of any quasi cyclic code.     

Gröbner basis approach to list decoding of algebraic geometry codes

We show how our Gröbner basis algorithm, which was previously applied to list decoding of Reed Solomon codes, can be used in the hard and soft decision list decoding of Algebraic Geometry codes. In addition, we present a linear functional version of our Gröbner basis algorithm in order to facilitate comparisons with methods based on duality.     

Linear codes with balanced weight distribution

In this paper, we study particular linear codes defined overF _q , with an astonishing property, their weight distribution is balanced, i.e. there is the same number of codewords for each nonzero weight of the code. We call these codesBWD-codes. We first study BWD-codes by means of the Pless identities and we completely characterize the two-weight projective case. We study the class of codes defined under subgroups of the multiplicative group ofF _q ^s , using the Gauss sums. Then, given a primep and an integerN dividingp – 1, we construct all theN-weight BWD-codes of that class. We conclude this paper by some tables of BWD-codes and an open problem.     

Space-time block codes which can be identified as rings

In this paper, we give a general criterion to determine when a complex space-time block code has a ring structure and then we provide a complete list of complex space-time block codes which have ring structures up to size 4.     

Dual codes of systematic group codes over abelian groups

For systematic codes over finite fields the following result is well known: If [I∣P] is the generator matrix then the generator matrix of its dual code is The main result is a generalization of this for systematic group codes over finite abelian groups. It is shown that given the endomorphisms which characterize a group code over an abelian group, the endomorphisms which characterize its dual code are identified easily. The self-dual codes are also characterized. It is shown that there are self-dual and MDS group codes over elementary abelian groups which can not be obtained as linear codes over finite fields. Received March 7, 1995; revised version April 3, 1996     

Evaluation codes at singular points of algebraic differential equations

We use the special geometry of singular points of algebraic differential equations on the affine plane over finite fields to study the main features and parameters of error correcting codes giving by evaluating functions at sets of singular points. In particular, one gets new methods to construct codes with designed minimum distance. This work was partially supported by MCyT BFM2001-2251.     

Skew-cyclic codes

We generalize the notion of cyclic codes by using generator polynomials in (non commutative) skew polynomial rings. Since skew polynomial rings are left and right euclidean, the obtained codes share most properties of cyclic codes. Since there are much more skew-cyclic codes, this new class of codes allows to systematically search for codes with good properties. We give many examples of codes which improve the previously best known linear codes.     

Construction of Improved Geometric Goppa Codes from Klein Curves and Klein-like Curves

Linear error-correcting codes, especially Reed-Solomon codes, find applications in communication and computer memory systems, to enhance their reliability and data integrity. In this paper, we present Improved Geometric Goppa (IGG) codes, a new class of error-correcting codes, based on the principles of algebraic-geometry. We also give a reasonably low complexity procedure for the construction of these IGG codes from Klein curves and Klein-like curves, in plane and high-dimensional spaces. These codes have good code parameters like minimum distance rate and information rate, and have the potential to replace the conventional Reed-Solomon codes in most practical applications. Based on the approach discussed in this paper, it might be possible to construct a class of codes whose performance exceeds the Gilbert-Varshamov bound. Received: November 14, 1995; revised version: November 22, 1999     

Polynomial-time construction of codes I: Linear codes with almost equal weights

We prove that there are infinite families (C_i)_i0 of codes over F_q with polynomial complexity of construction whose relative weights are as close to as we want and are such that

Function-field codes

Function-field codes provide a general perspective on the construction of algebraic-geometry codes. We briefly review the theory of function-field codes and establish some new results in this theory, including a propagation rule. We show how to derive linear codes from function-field codes, thus generalizing a construction of linear codes due to Xing, Niederreiter, and Lam. The research of the second and third author was partially supported by the DSTA research grant R-394-000-025-422 with Temasek Laboratories in Singapore.     

Minimum distance of relative Reed–Muller codes

We describe a construction of error-correcting codes on a fibration over a curve defined over a finite field, which may be considered as a relative version of the classical Reed–Muller code. In the case of complete intersections in a projective bundle, we give an explicit lower bound for the minimum distance.     

基于Spinal码的编码协作

针对5G的高速率传输需求,研究了基于Spinal码的编码协作。基于Spinal码的无速率性,提出了直接选用不同通道内所有编码符号实现编码协作的CC-SPSC方案。在此方案基础上,考虑基站在设备条件和中心调度方面的优势,引入以基站为控制核心的策略,提出了CC-SPSC-BSC-AL方案和CC-SPSC-BSC-SR方案。仿真结果表明,所提方案在模拟信道和数字信道下均有显著的误码率性能提升,尤其是CC-SPSC和CC-SPSC-BSCSR方案,分别在模拟信道和数字信道下的应用优势突出。     

Two new decoding algorithms for Reed-Solomon codes

The subject of decoding Reed-Solomon codes is considered. By reformulating the Berlekamp and Welch key equation and introducing new versions of this key equation, two new decoding algorithms for Reed-Solomon codes will be presented. The two new decoding algorithms are significant for three reasons. Firstly the new equations and algorithms represent a novel approach to the extensively researched problem of decoding Reed-Solomon codes. Secondly the algorithms have algorithmic and implementation complexity comparable to existing decoding algorithms, and as such present a viable solution for decoding Reed-Solomon codes. Thirdly the new ideas presented suggest a direction for future research. The first algorithm uses the extended Euclidean algorithm and is very efficient for a systolic VLSI implementation. The second decoding algorithm presented is similar in nature to the original decoding algorithm of Peterson except that the syndromes do not need to be computed and the remainders are used directly. It has a regular structure and will be efficient for implementation only for correcting a small number of errors. A systolic design for computing the Lagrange interpolation of a polynomial, which is needed for the first decoding algorithm, is also presented.This research was supported by a grant from the Canadian Institute for Telecommunications Research under the NCE program of the Government of Canada     

Fast decoding of non-binary first order Reed-Muller codes

A minimum distance decoding algorithm for non-binary first order Reed-Muller codes is described. Suggested decoding is based on a generalization of the fast Hadamard transform to the non-binary case. We also propose a fast decoding algorithm for non-binary first order Reed-Muller codes with complexity proportional to the length of the code. This algorithm provides decoding within the limits guaranteed by the minimum distance of the code.Partly supported by the Guastallo Fellowship. This work was presented in part at the 9th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, New Orleans, USA, October 1991