Labeling algorithms for construction-A and construction-B lattices with respect to pyramid boundaries are presented. The algorithms are developed based on relations between lattices and linear block codes as well as on transformations among several specifically defined lattices and their translations. The mechanism for the construction of these algorithms can be considered as an extension of that given by Fischer (1986). The algorithms are noted to achieve 100% efficiency in utilizing index bits for binary representations. Furthermore, it is determined that many important lattices (E/sub 8/, /spl Lambda//sub 16/...) can be indexed to arbitrary norms and dimensions. The complexity of these algorithms in terms of both memory and computation is quite low and thus it is possible to develop practical lattice vector quantizers of large norms and high dimensions using these algorithms.

A new bounded-distance (BD) decoding algorithm is presented for binary linear (n, k, d) block codes on additive white Gaussian noise channels. The algorithm is based on the generalized minimum distance (GMD) decoding algorithm of Forney (1989) using the acceptance criterion of Taipale and Pursley (GMD/TP) proposed in 1991. It is shown that the GMD/TP decoding algorithm is a BD decoding algorithm with effective error coefficient (/sup n//sub d/). It is also shown that the decision regions of GMD/TP are good inner approximations of those of full GMD decoding, and therefore full GMD decoding is BD and has an effective error coefficient that is well approximated by (/sup n//sub d/). Moreover, by adding a d-erasure-correction step to GMD decoding, the effective error coefficient can be reduced to A/sub d/, the number of minimum-weight codewords, which is the same as the effective error coefficient of maximum-likelihood decoding. The decoding algorithm is mainly based on algebraic errors-and-erasures decoding and therefore has polynomial rather than exponential complexity.

A simple method based on Newton's identities and their extensions is presented for determining the actual minimum distance of cyclic codes. More significantly, it is shown that this method also provides a mechanism for generating the type of syndrome matrices needed by Feng and Tzeng's (see ibid., vol.40, p.1364-1374, Sept. 1994) new procedure for decoding cyclic and BCH codes up to their actual minimum distance. Two procedures for generating such matrices are given. With these procedures, we have generated syndrome matrices having only one class of conjugate syndromes on the minor diagonal for all binary cyclic codes of length n<63 and many codes of length 63/spl les/n/spl les/99. A listing of such syndrome matrices for selected codes of length n<63 is included. An interesting connection of the method presented to the shifting technique of van Lint (1986) and Wilson is also noted.

A new algorithm is developed for decoding geometric Goppa codes (algebraic-geometric codes) up to their designed minimum distance. This algorithm is constructed on the basis of the one introduced by Porter, Shen, and Pellikaan (1992), but has improved it considerably in decoding capability by incorporating a majority voting scheme conceptually analogous to that employed by the algorithms of Feng and Rao (1993), and Duursma (1993). The algorithm is distinct from others in that its major steps are accomplished by solving a key equation in an affine ring. The result is a new algorithm with decoding capability on a par with that of Feng and Rao's and Duursma's algorithms. The new algorithm is applicable to a large class of geometric Goppa codes and thus provides a viable alternative to the algorithms of Feng and Rao, as well as Duursma for decoding geometric Goppa codes up to designed minimum distance.

Newton's identities have played a significant role in decoding and minimum distance determination of cyclic and BCH codes. The present paper carries the notion over from cyclic codes to algebraic-geometric (AG) codes and introduces Newton's identities for AG codes, also for the purpose of minimum distance determination and decoding.

An approach based on code decomposition and partial transform for constructing algorithms for decoding cyclic codes and algebraic-geometric (AG) codes is introduced. A general decoding procedure applicable to arbitrary linear codes and their subfield subcodes is then developed. In particular, we have developed algorithms for error-and-erasure decoding of cyclic codes up to their actual minimum distance, error-and-erasure decoding of AG codes up to their designed minimum distance, and decoding of subfield subcodes of AG codes (geometric BCH codes). Moreover, a generalization of geometric BCH codes is introduced. It is shown by an example that for a simple class of AG codes, the so-called one-point codes, this generalization brings a better estimate of their minimum distance. It is also shown that the algorithms developed in this paper can be applied to decode these codes up to their estimated minimum 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)/spl times/(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/sub 0/, S/sub 1/, S/sub n-1/). The authors show that with this procedure, all binary cyclic and BCH codes of length>

An efficient decoding algorithm for algebraic-geometric codes is presented. For codes from a large class of irreducible plane curves, including Hermitian curves, it can correct up to [(d*-1)/2] errors, where d* is the designed minimum distance. With it we also obtain a proof of d/sub min//spl ges/d* without directly using the Riemann-Roch theorem. The algorithm consists of Gaussian elimination on a specially arranged syndrome matrix, followed by a novel majority voting scheme. A fast implementation incorporating block Hankel matrix techniques is obtained whose worst-case running time is O(mn/sup 2/), where m is the degree of the curve. Applications of our techniques to decoding other algebraic-geometric codes, to decoding BCH codes to actual minimum distance, and to two-dimensional shift register synthesis are also presented.>

The generalized Hamming weights of a linear code are fundamental code parameters related to the minimal overlap structures of the subcodes. They were introduced by V.K. Wei (1991) and shown to characterize the performance of the linear code in certain cryptographical applications. Results are presented on the generalized Hamming weights of several classes of binary cyclic codes, including primitive double-error-correcting and triple-error-correcting BCH codes, certain reversible cyclic codes, and some extended binary Goppa codes. In particular, the second generalized Hamming weight of primitive double-error-correcting BCH codes is determined and upper and lower bounds are obtained for the generalized Hamming weights for the codes studied. These bounds are compared to results from other methods.>

Procedures are presented for error-and-erasure decoding of cyclic codes up to the Hartmann-Tzeng (HT) bound. Emphasis is placed on converting the problem of error-and-erasure decoding to an error-only decoding problem so that the Berlekamp-Massey or the Feng-Tzeng multisequence shift-register synthesis algorithms can be applied. This work has thus extended the result, which was up to a special case of the HT bound, obtained by P. Stevens (1990) on error-and-erasure decoding of binary cyclic codes.>

A generalization of the Berlekamp-Massey algorithm is presented for synthesizing minimum length linear feedback shift registers for generating prescribed multiple sequences. A more general problem is first considered, that of finding the smallest initial set of linearly dependent columns in a matrix over an arbitrary field, which includes the multisequence problem as a special case. A simple iterative algorithm, the fundamental iterative algorithm (FIA), is presented for solving this problem. The generalized algorithm is then derived through a refinement of the FIA. Application of this generalized algorithm to decoding cyclic codes up to the Hartmann-Tzeng (HT) bound and Roos bound making use of multiple syndrome sequences is considered. Conditions for guaranteeing that the connection polynomial of the shortest linear feedback shift register obtained by the algorithm will be the error-locator polynomial are determined with respect to decoding up to the HT bound and special cases of the Roos bound.>

The decoding capabilities of algebraic algorithms, mainly the Berlekamp-Massey algorithm, the Euclidean algorithm, and the authors' (1989) generalizations of these algorithms, are basically constrained by the minimum distance bounds of the codes. The authors introduce a more general procedure which breaks away from this restriction and which can determine the, error locations from nonrecurrent dependence relations among the syndromes. It can decode many cyclic and BCH codes up to their actual minimum distance and is seen to be a generalization of the procedure introduced by W.W. Peterson and E.J. Weldon (1972).>

The problem of finding a linear-feedback shift register of shortest length capable of generating prescribed multiple sequences is considered. A generalized Euclidean algorithm, which is based on a generalized polynomial division algorithm, is presented. A necessary and sufficient condition for the uniqueness of the solution is given. When the solution is not unique, the set of all possible solutions is also derived. It is shown that the algorithm can be applied to the decoding of many cyclic codes for which multiple syndrome sequences are available. When it is applied to the case of a single sequence, the algorithm reduces to that introduced by Y. Sugiyama et al. (Inf. Control, vol.27, p.87-9, Feb. 1975) in the decoding of BCH codes.>

Several theorems are presented which characterize Goppa codes having the property of becoming cyclic when an overall parity cheek is added. If such a Goppa code has location setL = GF (q^{m})and a Goppa polynomialg(z)that is irreducible overGF(q^{m}), theng(z)must be a quadratic. Goppa codes defined by(z- \beta)^{a}and location setLwith cardinalitynsuch thatn+l|q^{m}-1are considered along with their subcodes. A sufficient condition onLis derived for the extended codes to become cyclic. This condition is also necessary whena= 1. The construction ofLfor differentnsatisfying the stated condition is investigated in some detail. Some irreversible Goppa codes have been shown to become cyclic when extended by an overall parity check.

The class of linear codes introduced by Goppa are noncyclic in general. The only Goppa codes known to be cyclic are the Bose--Chaudhuri-Hocquengbem (BCH) codes which are a special class of Goppa codes. Recently, Berlekamp and Moreno showed that certain double-error-correcting binary Goppa codes become cyclic when extended by an overall parity check. In this correspondence, results of a further investigation on extending Goppa codes to cyclic codes are presented. It is shown that a large class of multiple-error-correctingq-ary Goppa codes also become cyclic when extended by an overall parity check. These Goppa codes are found to be reversible. The Goppa codes considered in this correspondence consist of two subclasses that, after extension, give rise to the two subclasses of reversible cyclic codes of primitive and nonprimitive length, respectively. These cyclic codes are noted to include, respectively, the expurgated Melas codes and the Zetterberg codes as special cases.

Many cyclic codes are generated by polynomials possessing more than one set of consecutive roots. Thus more than one set of syndrome sequences are available for decoding. In this correspondence, a decoding method based on Berlekamp's iterative algorithm is presented which makes use of the multiple sets of syndrome sequences for decoding such cyclic codes beyond the BCH bound.

Some new lower bounds on the minimum distance of cyclic codes of composite length are presented. These bounds generalize some existing bounds and give better estimates of the minimum distance for a wide range of cyclic codes, Lower bounds on the random-error-correction capability of a particular class of cyclic codes of composite lengthn = n_1n_2, wheren_1andn_2are relatively prime, are easily derived.

An upper bound on the minimum distance of cyclic codes of composite length is presented. This upper bound proves the BCH bound to be exact for many cyclic codes.

This correspondence presents an upper bound on the minimum distance of arithmetic codes of composite lengthn = n_1 n_2. The tightness of this bound gives a rather good working estimate of the minimum distance of a prospective code.

This paper presents a number of interesting results relating to the determination of actual minimum distance of cyclic codes. Codes with multiple sets of consecutive roots are constructed. A bound on the minimum weight of odd-weight codewords is determined. Relations on the distribution of roots of the generator polynomial are investigated. Location polynomials of reversible codes are examined. These results are used to obtain better estimates of the minimum distance of many new cyclic codes.

The minimum distance of a class of reversible cyclic codes has been proved to be greater than that given by the BCH bound. It is also noted that this class of codes includes the class of primitive double-error-correcting binary codes of Melas as well as the class of nonprimitive double-error-correcting binary codes discovered by Zetterberg as special cases.