New array codes for multiple phased burst correction

An optimal family of array codes over GF(q) for correcting multiple phased burst errors and erasures, where each phased burst corresponds to an erroneous or erased column in a code array, is introduced. As for erasures, these array codes have an efficient decoding algorithm which avoids multiplications (or divisions) over extension fields, replacing these operations with cyclic shifts of vectors over GF(q). The erasure decoding algorithm can be adapted easily to handle single column errors as well. The codes are characterized geometrically by means of parity constraints along certain diagonal lines in each code array, thus generalizing a previously known construction for the special case of two erasures. Algebraically, they can be interpreted as Reed-Solomon codes. When q is primitive in GF(q), the resulting codes become (conventional) Reed-Solomon codes of length P over GF(q^p-1), in which case the new erasure decoding technique can be incorporated into the Berlekamp-Massey algorithm, yielding a faster way to compute the values of any prescribed number of errors     

Fast algorithms for determining the linear complexity of sequences over GF(p/sup m/) with period 2/sup t/n

We prove a result which reduces the computation of the linear complexity of a sequence over GF(p^m) (p is an odd prime) with period 2n (n is a positive integer such that there exists an element bisinGF(p^m), bⁿ=-1) to the computation of the linear complexities of two sequences with period n. By combining with some known algorithms such as the Berlekamp-Massey algorithm and the Games-Chan algorithm we can determine the linear complexity of any sequence over GF(p^m) with period 2^tn (such that 2 ^t|p^m-1 and gcd(n,p^m-1)=1) more efficiently     

A new family of frequency-hop codes

We give an algebraic construction for a new family of frequency-hop codes. The construction is based on properties of finite fields: it is shown that for each field GF(p^m), there exists a large number of codes of length p^m. The codes are also shown to possess the best possible simultaneous two-dimensional autocorrelation and cross-correlation properties. Moreover, they include a family of codes: with a code length of a power of 2, which are ideally suitable for applications in digital communication systems     

A versatile time-domain Reed-Solomon decoder

A versatile Reed-Solomon (RS) decoder structure based on the time-domain decoding algorithm (transform decoding without transforms) is developed. The algorithm is restructured, and a method is given to decode any RS code generated by any generator polynomial. The main advantage of the decoder structure is its versatility, that is, it can be programmed to decode any Reed-Solomon code defined in Galois field (GF) 2^m with a fixed symbol size m. This decoder can correct errors and erasures for any RS code, including shortened and singly extended codes. It is shown that the decoder has a very simple structure and can be used to design high-speed single-chip VLSI decoders. As an example, a gate-array-based programmable RS decoder is implemented on a single chip. This decoder chip can decode any RS code defined in GF (2⁵) with any code word length and any number of information symbols. The decoder chip is fabricated using low-power 1.5-μ, two-layer-metal, HCMOS technology     

On lowest density MDS codes

Let F_q denote the finite field GF(q) and let h be a positive integer. MDS (maximum distance separable) codes over the symbol alphabet F_q^b are considered that are linear over F _q and have sparse (“low-density”) parity-check and generator matrices over F_q that are systematic over F_q^b. Lower bounds are presented on the number of nonzero elements in any systematic parity-check or generator matrix of an F_q-linear MDS code over F_q^b, along with upper bounds on the length of any MDS code that attains those lower bounds. A construction is presented that achieves those bounds for certain redundancy values. The building block of the construction is a set of sparse nonsingular matrices over F_q whose pairwise differences are also nonsingular. Bounds and constructions are presented also for the case where the systematic condition on the parity-check and generator matrices is relaxed to be over F_q, rather than over F_q^b     

Fast transform for decoding both errors and erasures of Reed-Solomon codes over GF(2/sup m/) for 8/spl les/m/spl les/10

In this letter, it is shown that a fast, prime-factor discrete Fourier transform (DFT) algorithm can be modified to compute Fourier-like transforms of long sequences of 2/sup m/-1 points over GF(2/sup m/), where 8/spl les/m/spl les/10. Using these transforms, together with the Berlekamp-Massey algorithm, the complexity of the transform-domain decoder for correcting both errors and erasures of the Reed-Solomon codes of block length 2/sup m/-1 over GF(2/sup m/) for 8/spl les/m/spl les/10 is reduced substantially from the previous time-domain decoder. A computer simulation verifies these new results.     

Error-trellises for convolutional codes .I. Construction

An error-trellis is a directed graph that represents all the sequences belonging to the coset which contains the symbol-by-symbol detected version of a given received sequence. A modular construction of error-trellises for an (n,k) convolutional code over GF(q) is presented. The trellis is designed on the basis of partitioning the scalar check matrix of the code into submatrices of l rows, accompanied with a corresponding segmentation of the syndrome. The value of the design parameter l is an essentially unconstrained multiple of n-k. For all the cosets of the code, the sections of the error-trellis are drawn from a collection of only q^l modules; the module for each section is determined by the value of the associated syndrome segment. In case the construction is based on a basic polynomial check matrix, either canonical or noncanonical, then the error-trellis is minimal in the sense that σ⩽μ, where σ is the dimension of the state space of the trellis and μ is the constraint length of a canonical generator matrix for the code. For basic check matrices with delay-free columns, the inequality reduces to σ=μ     

Value Distributions of Exponential Sums From Perfect Nonlinear Functions and Their Applications

In this paper we present a unified way to determine the values and their multiplicities of the exponential sums Sigma_xisinF(q)zeta_p ^Tr(af(x)+bx)(a,bisinF_q,q=p^m,pges3) for all perfect nonlinear functions f which is a Dembowski-Ostrom polynomial or p = 3,f=^x(3(k)+1)/2 where k is odd and (k,m)=1. As applications, we determine (1) the correlation distribution of the m-sequence {a_lambda=Tr(gamma^lambda)}(lambda=0,1,...) and the sequence {b_lambda=Tr(f(gamma^lambda))}(lambda=0,1,...) over F_p where gamma is a primitive element of F_q and (2) the weight distributions of the linear codes over F_p defined by f.     

A characterization of MMD codes

Let C be a linear [n,k,d]-code over GF(q) with k⩾2. If s=n-k+1-d denotes the defect of C, then by the Griesmer bound, d⩽(s+1)q. Now, for obvious reasons, we are interested in codes of given defect s for which the minimum distance is maximal, i.e., d=(s+1)q. We classify up to formal equivalence all such linear codes over GF(q). Remember that two codes over GF(q) are formally equivalent if they have the same weight distribution. It turns out that for k⩾3 such codes exist only in dimension 3 and 4 with the ternary extended Golay code, the ternary dual Golay code, and the binary even-weight code as exceptions. In dimension 4 they are related to ovoids in PG(3,q) except the binary extended Hamming code, and in dimension 3 to maximal arcs in PG(2,q)     

Soft-decision decoding using punctured codes

Let a q-ary linear (n,k)-code be used over a memoryless channel. We design a soft-decision decoding algorithm that tries to locate a few most probable error patterns on a shorter length s ∈ [k,n]. First, we take s cyclically consecutive positions starting from any initial point. Then we cut the subinterval of length s into two parts and examine T most plausible error patterns on either part. To obtain codewords of a punctured (s,k)-code, we try to match the syndromes of both parts. Finally, the designed codewords of an (s,k)-code are re-encoded to find the most probable codeword on the full length n. For any long linear code, the decoding error probability of this algorithm can be made arbitrarily close to the probability of its maximum-likelihood (ML) decoding given sufficiently large T. By optimizing s, we prove that this near-ML decoding can be achieved by using only T≈q^(n-k)k(n+k)/ error patterns. For most long linear codes, this optimization also gives about T re-encoded codewords. As a result, we obtain the lowest complexity order of q^(n-k)k(n+k)/ known to date for near-ML decoding. For codes of rate 1/2, the new bound grows as a cubic root of the general trellis complexity q^min{n-k,k}. For short blocks of length 63, the algorithm reduces the complexity of the trellis design by a few decimal orders     

Family of uncorrelated binary ZCZ sequence pairs with mismatched filtering

A family of uncorrelated binary sequence pairs of length N=4(p^m+1) with zero correlation zone (ZCZ) (N/4) -1 and mismatched filtering is proposed. The sequence pairs are derived from almost- perfect binary and ternary sequences and possess energy efficiency close to 1 as N becomes large. They can be used in quasi-synchronous code division multiple access and radar systems to reduce interference.     

Class of shortened cyclic codes over GF(2/sup 8/) for byte-oriented systems

The author proposes shortened cyclic codes over GF(2/sup 8/), designed to provide additional error protection from both random as well as burst errors, for data consisting of 8-bit bytes, all having even (or odd) parity (e.g. ASCII characters). A specific code of length 29 bytes is described in detail.<>     

On the linear complexity of a new generalized cyclotomic sequence with length mover GF(h)

Based on the Ding-generalized cyclotomy,a new class of generalized cyclotomic sequences with length p^m over the finite field of power of odd prime order was constructed,and the sequence was balanced.The linear complexity of the sequences was determined using the relationship between h and p and the theory of polynomial over finite field.It is shown that the sequence has good linear complexity,and it can resist attacks from the application of the Berlekamp-Massey algorithm.     

Burst-error-correcting algorithm for Reed-Solomon codes

A new decoding algorithm for burst-error-correction is proposed. The proposed algorithm can effectively correct burst errors of length approaching n-k symbols for (n, k) Reed-Solomon (RS) codes. Compared with existing algorithms, the algorithm enables much faster decoding with far less computational complexity     

Relationships between m-sequences over GF(q) andGF(qm)

It is shown that m-sequences over GF(q^m ) of length q^nm-1 corresponding to primitive polynomials in GF[q^m,x] of degree n can be generated from known m-sequences over GF(q) of length q^nm-1 obtained from primitive polynomials in GF[q,x] of degree mn. A procedure for generating the m-sequences over GF(q²) from m-sequences over GF(q) was given which enables the generation of m-sequences over GF( p²ⁿ). In addition it was shown that all of the primitive polynomials in GF[q,^m,x] can be obtained from a complete set of the primitive polynomials in GF[q ,x]     

A note on maximum distance separable (optimal) codes (Corresp.)

Given a positive integerkand a prime powerqwithq leq k, it is proved that the largest value ofnfor which there exists an[n,k,n-k+l]maximum distance separable (MDS) code over GF(q)isk+1. A simple proof for the largest value ofnfor which there exists an[n,2,n-1]MDS code over any finite field is also given.     

Comments on “Weighted sum codes for error detection and theircomparison with existing codes”

A.J. McAuley (IEEE/ACM Trans. Networking, vol.2, p.16-22, 1994) proposed a new family of error detection codes called weighted sum codes. In the present paper it is noted, that these codes are equivalent to lengthened Reed Solomon codes, resp. shortened version of lengthened Reed Solomon codes over GF(2^h/2). It is also shown, that it is possible to use these codes for error correction of one error in the code word over GF(2^h/2)     

Correcting a specified set of likely error patterns

The main concern of this article is to find linear codes which will correct a set of arbitrary error patterns. Although linear codes which have been designed for correcting random error patterns and burst error patterns can be used, we would like to find codes which will correct a specified set of error patterns with the fewest possible redundant bits. Here, to reduce the complexity involved in finding the code with the smallest redundancy which can correct a specified set of error patterns, algebraic codes whose parity check matrix exhibits a particular structure are considered. If the number of redundant bits is T, the columns of the parity check matrix must be increasing powers of a field element in GF(2^T). Given a set of error patterns to be corrected, computations to determine the code rates possible for these type of codes and hence the redundancy for different codeword lengths are presented. Results for various sets of error patterns suggest that the redundancy of these algebraic codes is close to the minimum redundancy possible for the set of error patterns specified and for any codeword length     

Pseudocyclic maximum-distance-separable codes

The (n, k) pseudocyclic maximum-distance-separable (MDS) codes modulo (xⁿ- a) over GF(q) are considered. Suppose that n is a divisor of q+1. If n is odd, pseudocyclic MDS codes exist for all k. However, if n is even, nontrivial pseudocyclic MDS codes exist for odd k (but not for even k) if a is a quadratic residue in GF(q), and they exist for even k (but not for odd k) if a is not a quadratic residue in GF(q). Also considered is the case when n is a divisor of q-1, and it is shown that pseudocyclic MDS codes exist if and only if the multiplicative order of a divides (q-1)/n, and that when this condition is satisfied, such codes exist for all k. If the condition is not satisfied, every pseudocyclic code of length n is the result of interleaving a shorter pseudocyclic code     

A New Scheme to Predict Erasures for Reed-Solomon Decoder in T-DMB Receiver

In this paper, we introduce a new scheme to improve the performance of the terrestrial - digital multimedia broadcasting (T-DMB) system, which exploits the burst error characteristics at the output of the convolutional decoder and the properties of the Reed-Solomon (RS) decoder to correct more errors by predicting erasures in each RS packet in advance as many as possible before decoding in the RS decoder. Simulation results show that the proposed scheme yields performance gain of around 1 dB at BER of 10^-R which can result in the extended coverage area of the T-DMB system.