Skew circular convolution algorithms over finite integer rings

In recent work, the author has generalised number-theoretic transforms (NTTs) over finite integer rings and derived fast algorithms for computing circular convolution of two discrete sequences. Here, number theoretic results are described and algorithms for computing skew circular convolution over finite integer rings and their complex extensions are developed     

Codes over rings from curves of higher genus

We construct certain error-correcting codes over finite rings and estimate their parameters. These codes are constructed using plane curves and the estimates for their parameters rely on constructing “lifts” of these curves and then estimating the size of certain exponential sums     

Simple method for generating mth-order permutation polynomials over integer rings

A sufficient condition for mth-order (mges1) polynomials as permutation polynomials (PPs) over integer rings is presented and proved. Possible applications of the proposed simple mth-order PP generation method include the design of interleavers for turbo codes and generation of pseudorandom numbers     

Lee metric codes over integer residue rings (Corresp.)

A method for constructing Lee metric codes over arbitrary alphabet sizes using the elementary concepts of module theory is presented. The codes possess a high degree of symmetry. Codes with two information symbols over arbitrary alphabet sizes are cyclic reversible. For alphabet sizes which are a power of two or an odd prime number, codes with one information symbol are reversible and equidistant, and codes having more than two information symbols are quasi-cyclic reversible. Binary Reed-Muller codes arise as subcodes of the codes presented. A method of constructing equidistant Lee metric codes analogous to maximum length shift register codes is presented.     

Interleavers for turbo codes using permutation polynomials over integer rings

A class of deterministic interleavers for turbo codes (TCs) based on permutation polynomials over /spl Zopf//sub N/ is introduced. The main characteristic of this class of interleavers is that they can be algebraically designed to fit a given component code. Moreover, since the interleaver can be generated by a few simple computations, storage of the interleaver tables can be avoided. By using the permutation polynomial-based interleavers, the design of the interleavers reduces to the selection of the coefficients of the polynomials. It is observed that the performance of the TCs using these permutation polynomial-based interleavers is usually dominated by a subset of input weight 2m error events. The minimum distance and its multiplicity (or the first few spectrum lines) of this subset are used as design criterion to select good permutation polynomials. A simple method to enumerate these error events for small m is presented. Searches for good interleavers are performed. The decoding performance of these interleavers is close to S-random interleavers for long frame sizes. For short frame sizes, the new interleavers outperform S-random interleavers.     

Convolutional codes over integer rings suitable for parallel and serial concatenation

Choosing a convolutional encoder over a ring with feedback may not lead to a suitable component code for parallel or serial concatenation. A simple criterion is derived that allows to check whether a rational encoding matrix generating some convolutional code over the integer ring /spl Zopf/(p/sup m/) ( p prime) has exclusively infinite impulse responses.     

Multisequence shift register synthesis over commutative rings with identity with applications to decoding cyclic codes over integer residue rings

We present a new algorithm for solving the multisequence shift register synthesis problem over a commutative ring R with identity. Given a finite set of R-sequences, each of length L, the complexity of our algorithm in terms of R-multiplications is O(L/sup 2/) as L /spl rarr/ /spl infin/. An important application of this algorithm is in the decoding of cyclic codes over Z/sub q/ up to the Hartmann-Tzeng bound, where q is a prime power. Characterization of the set of monic characteristic polynomials of a prescribed set of multiple syndrome sequences leads to an efficient decoding procedure, which we further extend to decode cyclic codes over Z/sub m/ where m is a product of prime powers.     

有限域和剩余类环上非奇异反馈多项式的谱刻划

本文给出了有限域和剩余类环上非线性反馈移存器的非奇异反馈多项式及局部置换多项式的谱刻划，简化了素域上的现有结果，并对有限域上和剩余类环上相关免疫函数的谱特征给出了一个新的证明方法。     

Lower bound on minimum lee distance of algebraic?geometric codes over finite fields

Algebraic-geometric (AG) codes over finite fields with respect to the Lee metric have been studied. A lower bound on the minimum Lee distance is derived, which is a Lee-metric version of the well-known Goppa bound on the minimum Hamming distance of AG codes. The bound generalises a lower bound on the minimum Lee distance of Lee-metric BCH and Reed-Solomon codes, which have been successfully used for protecting against bitshift and synchronisation errors in constrained channels and for error control in partial-response channels.     

On fast algorithms for one-dimensional digital signal processing in finite integer and complex integer rings

In this work, we present and analyze a number theoretic approach to computing one-dimensional cyclic convolution of sequences defined in finite integer and complex integer rings. A fundamental result of this work is that under the nonrestrictive condition, (N, M)=1, the algorithms defined in finite integer and complex integer rings are as intensive computationally as the corresponding algorithms defined in rational and complex rational number systems only in the worst case. They simplify considerably for a large number of cases of importance in digital signal processing.This research work is supported by the National University of Singapore under its Academic Research Fund, grant no. RP960699.     

Optimal p-ary Codes from One-weight Linear Codes over Zpm

We investigate the structures and proper- ties of one-Homogeneous （Lee） weight linear codes over the ring of integers modulo M （M is a power of a prime inte- ger p） with one unique nonzero weight. We fully describe one-Homogeneous （Lee） weight codes over rings of integers modulo 4, 8 and 9. By the generalized Gray map, we ob- tain a class of optimal binary linear codes which reaches the Griesmer bound as well as the plotkin bound and a class of optimal p-ary （p is odd and prime） nonlinear codes which attains the Plotkin bound.     

Consta-Abelian codes over Galois rings

We study n-length consta-Abelian codes (a generalization of the well-known Abelian codes and constacyclic codes) over Galois rings of characteristic p/sup a/, where n and p are coprime. A twisted discrete Fourier transform (DFT) is used to generalize transform domain results of Abelian and constacyclic codes, to consta-Abelian codes. Further, we characterize consta-Abelian codes invariant under two kinds of monomials, whose underlying permutations are effected by: i) multiplying the coordinates with a unit in the appropriate mixed-radix representation of the coordinate positions and ii) shifting the coordinates by t positions. All the codes studied here belong to the class of quasi-twisted codes which are known to contain some good codes. We show that the dual of a consta-Abelian code invariant under the two monomials is also a consta-Abelian code closed under both monomials.     

Constructions of authentication codes from algebraic curves overfinite fields

We present a new application of algebraic curves over finite fields to the constructions of universal hash families and unconditionally secure codes. We show that the constructions derived from the Garcia-Stichtenoth curves yield new classes of authentication codes and universal hash families which are substantially better than those previously known     

Optimal p-ary Codes from Constacyclic Codes over a Non-chain Ring R

This paper is devoted to the study of con- stacyclic codes over a non-chain ring R. The generator polynomials of all constacyclic codes over R are characterized and their dual codes are also determined. We also introduce a Gray map. It is proved that the image of a vconstacyclic code of length n over R under the Gray map is a cyclic code of length 2n over a field with p elements, where p is odd prime. Moreover, we obtain a substantial number of optimal p-ary linear （cyclic） codes, in terms of their parameters, via the Gray map.     

Z2k上的对偶码

利用Z2k-线性码的生成矩阵及检验矩阵,给出了Z2k-线性码为自对偶码的必要条件,并给出了由一个Z2k-线性码构造Z2k-线性码的两种方法。     

Fast algorithms for computing one- and two-dimensional convolution in integer polynomial rings

In a recent work, the factorization properties of polynomials defined over finite integer polynomial rings were analyzed. These properties, along with other results pertaining to polymomial theory, led to the direct sum property and the American-Indian-Chinese extension of the Chinese remainder theorem over such integer rings. The objective of this paper is to describe algorithms for computing the one-and two-dimensional convolution of data sequences defined over finite integer rings. For one-dimensional convolution, algorithms for computing acyclic and cyclic convolution are described. For two-dimensional convolution, only the cyclic case is analyzed. Computational and other relevant aspects associated with the structure of these algorithms are also studied.     

Good Linear Codes from Quadratic Residue Codes over a Finite Non-Chain Ring

This paper is devoted to the study of quadratics residue codes and their extended codes over a finite non-chain ring. A class of Gray maps preserving the self-duality from the ring to the finite field are introduced. Some structural properties of quadratic residue codes and their extended codes are given. As an interesting applica-tion of these families of codes, some good linear codes are obtained by a special Gray map.     

On the factorization of polynomials and direct sum properties in integer polyomial rings

In our recent work, we solved the word sequence length constraint problem associated with number theoretic transforms defined in finite integer rings. This is based on the American-Indian-Chinese extension of the Chinese remainder theorem. This work builds further on the results by extending them to the domain of integer polynomial rings. The theory of polynomial factorization and the resulting direct sum property are studied in depth. The emphasis is on the theory of computational algorithms for processing sequences defined in finite integer and complex integer rings.