Is the class of cyclic codes asymptotically good?

There is the long-standing question whether the class of cyclic codes is asymptotically good. By an old result of Lin and Weldon, long Bose-Chaudhuri-Hocquenhem (BCH) codes are asymptotically bad. Berman proved that cyclic codes are asymptotically bad if only finitely many primes are involved in the lengths of the codes. We investigate further classes of cyclic codes which also turn out to be asymptotically bad. Based on reduction arguments we give some evidence that there are asymptotically good sequences of binary cyclic codes in which all lengths are prime numbers provided there is any asymptotically good sequence of binary cyclic codes.     

The q-ary image of some qm-ary cyclic codes: permutationgroup and soft-decision decoding

Using a particular construction of generator matrices of the q-ary image of q^m-ary cyclic codes, it is proved that some of these codes are invariant under the action of particular permutation groups. The equivalence of such codes with some two-dimensional (2-D) Abelian codes and cyclic codes is deduced from this property. These permutations are also used in the area of the soft-decision decoding of some expanded Reed-Solomon (RS) codes to improve the performance of generalized minimum-distance decoding     

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.     

Abelian codes over Galois rings closed under certain permutations

We study n-length Abelian codes over Galois rings with characteristic p/sup a/, where n and p are relatively prime, having the additional structure of being closed under the following two permutations: (i) permutation effected by multiplying the coordinates with a unit in the appropriate mixed-radix representation of the coordinate positions and (ii) shifting the coordinates by t positions. A code is t-quasi-cyclic (t-QC) if t is an integer such that cyclic shift of a codeword by t positions gives another codeword. We call the Abelian codes closed under the first permutation as unit-invariant Abelian codes and those closed under the second as quasi-cyclic Abelian (QCA) codes. Using a generalized discrete Fourier transform (GDFT) defined over an appropriate extension of the Galois ring, we show that unit-invariant Abelian and QCA codes can be easily characterized in the transform domain. For t=1, QCA codes coincide with those that are cyclic as well as Abelian. The number of such codes for a specified size and length is obtained and we also show that the dual of an unit-invariant t-QCA code is also an unit-invariant t-QCA code. Unit-invariant Abelian (hence unit-invariant cyclic) and t-QCA codes over Galois field F/sub p//sup l/ and over the integer residue rings are obtainable as special cases.     

Binary codes with disjoint codebooks and mutual Hamming distance

Equal-length linear binary block error-control codes with disjoint codebooks and mutual Hamming distance are considered. A method of constructing pairs of these disjoint codes from known cyclic codes, and determining their mutual distance, is described. Some sets of length-15 cyclic codes are tabulated.     

Weight distributions of cyclic self-dual codes

We give a 1-level squaring construction for binary repeated-root cyclic codes of length n=2/sup a/b, a/spl ges/1, b odd. This allows us to obtain the weight distributions of all cyclic binary self-dual codes of lengths up to 110, which are not accessible by direct computation. We also use the shadow construction, as a particular method for Type I self-dual codes.     

On existence of good self-dual quasicyclic codes

For a long time, asymptotically good self-dual codes have been known to exist. Asymptotically good 2-quasicyclic codes of rate 1/2 have also been known to exist for a long time. Recently, it was proved that there are binary self-dual n/3-quasicyclic codes of length n asymptotically meeting the Gilbert-Varshamov bound. Unlike 2-quasicyclic codes, which are defined to have a cyclic group of order n/2 as a subgroup of their permutation group, the n/3-quasicyclic c codes are defined with a permutation group of fixed order of 3. So, from the decoding point of view, 2-quasicyclic c codes are preferable to n/3-quasicyclic c codes. In this correspondence, with the assumption that there are infinite primes p with respect to (w r t.) which 2 is primitive, we prove that there exist classes of self-dual 2p-quasicyclic c codes and Type II 8p-quasicyclic c codes of length respectively 2p/sup 2/ and 8p/sup 2/ which asymptotically meet the Gilbert-Varshamov bound. When compared with the order of the defining permutation groups, these classes of codes lie between the 2-quasicyclic c codes and the n/3-quasicyclic c codes of length n, considered in previous works.     

An upper bound onk/nfor affine-invariant codes with fixedd/n(Corresp.)

An upper bound on the transmission ratiok/nfor binary cyclic codes whose extended codes are invariant under the affine group of permutations, is presented. As a consequence, the transmission ratiok/nof any affine-invariant code with a fixedd(minimum weight)/nis shown to approach zero as the code length n increases. This is an extension of the Lin and Weldon result for primitive BCH codes.     

On the construction of group block codes

We consider the construction of group block codes, i.e., subgroups of Gⁿ, the n-fold direct product of a group G. Two concepts are introduced that make this construction similar to that of codes over gf(2). The first concept is that of an indecomposable code. The second is that of a parity-check matrix. As a result, group block codes over a decomposable Abelian group of exponent d_m can be seen as block codes over the ring of residues modulo d_m, and their minimum Hamming distance can be easily determined. We also prove that, under certain technical conditions, (n, k) systematic group block codes over non-Abelian groups are asymptotically bad, in the sense that their minimum Hamming distance cannot exceed [n/k].     

Repeated-root cyclic codes

In the theory of cyclic codes, it is common practice to require that (n,q)=1, where n is the word length and F_q is the alphabet. It is shown that the even weight subcodes of the shortened binary Hamming codes form a sequence of repeated-root cyclic codes that are optimal. In nearly all other cases, one does not find good cyclic codes by dropping the usual restriction that n and q must be relatively prime. This statement is based on an analysis for lengths up to 100. A theorem shows why this was to be expected, but it also leads to low-complexity decoding methods. This is an advantage, especially for the codes that are not much worse than corresponding codes of odd length. It is demonstrated that a binary cyclic code of length 2n (n odd) can be obtained from two cyclic codes of length n by the well-known | u|u+v| construction. This leads to an infinite sequence of optimal cyclic codes with distance 4. Furthermore, it is shown that low-complexity decoding methods can be used for these codes. The structure theorem generalizes to other characteristics and to other lengths. Some comparisons of the methods using earlier examples are given     

Performance of quantizers on noisy channels using structuredfamilies of codes

Achievable distortion bounds are derived for the cascade of structured families of binary linear channel codes and binary lattice vector quantizers. It is known that for the cascade of asymptotically good channel codes and asymptotically good vector quantizers the end-to-end distortion decays to zero exponentially fast as a function of the overall transmission rate, and is achieved by choosing a channel code rate that is independent of the overall transmission rate. We show that for certain families of practical channel codes and binary lattice vector quantizers, the overall distortion can be made to decay to zero exponentially fast as a function of the square root of transmission rate. This is achieved by carefully choosing a channel code rate that decays to zero as the transmission rate grows. Explicit channel code rate schedules are obtained for several well-known families of channel codes     

On codes overZ_m(Corresp.)

The factorization of Abelian codes overZ_{m}, i.e., ideals inZ_{m},G,Ga finite Abelian group, corresponding to a factorization ofmand that of G as a product of cyclic groups are considered. Quasi-Abelian codes overZ_{m}are considered and it is shown that every quasi-Abelian code overZ_{m}is a direct sum of Abelian codes overZ_{m}. A factorization of Gray codes overZ_{m}is also considered.     

Cyclic codes and self-dual codes over F2+uF2

We introduce linear cyclic codes over the ring F₂+uF ₂={0,1,u,u¯=u+1}, where u²=0 and study them by analogy with the Z₄ case. We give the structure of these codes on this new alphabet. Self-dual codes of odd length exist as in the case of Z₄-codes. Unlike the Z₄ case, here free codes are not interesting. Some nonfree codes give rise to optimal binary linear codes and extremal self-dual codes through a linear Gray map     

The average binary weight-enumerator for a class of generalizedReed-Solomon codes

An explicit weight-enumerator for the set of binary expansions of a class of generalized Reed-Solomon codes is derived. This enumerator is then used to show that most of these binary codes are asymptotically good, and to bound the rates of self-intersecting codes     

p-Adic estimates of hamming weights in abelian codes over galois rings

A generalization of McEliece's theorem on the p-adic valuation of Hamming weights of words in cyclic codes is proved in this paper by means of counting polynomial techniques introduced by Wilson along with a technique known as trace-averaging introduced here. The original theorem of McEliece concerned cyclic codes over prime fields. Delsarte and McEliece later extended this to Abelian codes over finite fields. Calderbank, Li, and Poonen extended McEliece's original theorem to cover cyclic codes over the rings Zopf₂ ^d, Wilson strengthened their results and extended them to cyclic codes over Zopf _p ^d, and Katz strengthened Wilson's results and extended them to Abelian codes over Zopf_p ^d. It is natural to ask whether there is a single analogue of McEliece's theorem which correctly captures the behavior of codes over all finite fields and all rings of integers modulo prime powers. In this paper, this question is answered affirmatively: a single theorem for Abelian codes over Galois rings is presented. This theorem contains all previously mentioned results and more     

Parity-check density versus performance of binary linear block codes over memoryless symmetric channels

We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, we derive lower bounds on the bit-error probability and on the gap to capacity for binary linear block codes which are represented by bipartite graphs, and study their performance limitations over MBIOS channels. The latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.     

Locally testable cyclic codes

Cyclic linear codes of block length n over a finite field F/sub q/ are linear subspaces of F/sub q//sup n/ that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in the family have constant rate and constant normalized distance (distance divided by block length). It is a long-standing open problem whether there exists a good family of cyclic linear codes. A code C is r-testable if there exists a randomized algorithm which, given a word x/spl isin//sub q//sup n/, adaptively selects r positions, checks the entries of x in the selected positions, and makes a decision (accept or reject x) based on the positions selected and the numbers found, such that 1) if x/spl isin/C then x is surely accepted; ii) if dist(x,C) /spl ges/ /spl epsi/n then x is probably rejected. ("dist" refers to Hamming distance.) A family of codes is locally testable if all members of the family are r-testable for some constant r. This concept arose from holographic proofs/PCP's. Recently it was asked whether there exist good, locally testable families of codes. In this paper the intersection of the two questions stated is addressed. Theorem. There are no good, locally testable families of cyclic codes over any (fixed) finite field. In fact the result is stronger in that it replaces condition ii) of local testability by the condition ii') if dist (x,C) /spl ges/ /spl epsi/n then x has a positive chance of being rejected. The proof involves methods from Galois theory, cyclotomy, and diophantine approximation.     

On the symmetry of good nonlinear codes

It is shown that there are arbitrarily long "good" (in the sense of Gilbert) binary block codes that are preserved under very large permutation groups. This result contrasts sharply with the properties of linear codes: it is conjectured that long cyclic codes are bad, and known that long affine-invariant codes are bad.     

Polyadic codes revisited

We generalize the notions of duadic codes, triadic codes, polyadic codes, and split group codes to include noncyclic Abelian codes. Necessary and sufficient conditions for the existence of such codes, and properties such as a duality property and a lower bound on the minimum weight of the subcode of "odd-like" codewords, are studied. This construction and its modification lead to many good codes, eight of which have minimum distance better than the lower bound given in Brouwer's table.     

The concatenated structure of cyclic and Abelian codes

It is shown that a linear two-dimensional cyclic code of lengthnNcan be factorized into a direct sum of concatenated codes, with cyclic inner and outer codes and, conversely, thai a two-dimensional cyclic code can be constructed in this way. This result is extended, and it appears that the Abelian codes are obtainable by taking a direct sum of several concatenations of cyclic codes. Codes are constructed that are better than any previously known. In particular, low-rate cyclic codes superior to the duals of high-rate BCH codes are constructed.