On the minimum distance of cyclic codes

The main result is a new lower bound for the minimum distance of cyclic codes that includes earlier bounds (i.e., BCH bound, HT bound, Roos bound). This bound is related to a second method for bounding the minimum distance of a cyclic code, which we call shifting. This method can be even stronger than the first one. For all binary cyclic codes of length< 63(with two exceptions), we show that our methods yield the true minimum distance. The two exceptions at the end of our list are a code and its even-weight subcode. We treat several examples of cyclic codes of lengthgeq 63.     

On computing the weight spectrum of cyclic codes

Two deterministic algorithms of computing the weight spectra of binary cyclic codes are presented. These algorithms have the lowest known complexity for cyclic codes. For BCH codes of lengths 63 and 127, several first coefficients of the weight spectrum in number sufficient to evaluate the bounded distance decoding error probability are computed     

On the minimum distance of ternary cyclic codes

There are many ways to find lower bounds for the minimum distance of a cyclic code, based on investigation of the defining set. Some new theorems are derived. These and earlier techniques are applied to find lower bounds for the minimum distance of ternary cyclic codes. Furthermore, the exact minimum distance of ternary cyclic codes of length less than 40 is computed numerically. A table is given containing all ternary cyclic codes of length less than 40 and having a minimum distance exceeding the BCH bound. It seems that almost all lower bounds are equal to the minimum distance. Especially shifting, which is also done by computer, seems to be very powerful. For length 40⩽n⩽50, only lower bounds are computed. In many cases (derived theoretically), however, these lower bounds are equal to the minimum distance     

On synchronizable binary cyclic codes (Corresp.)

In this correspondence a method is presented whereby the average synchronization-error-correcting capability of Tavares' subset codes may be improved with no additional cost in rate and with only a small increase in the complexity of encoding and decoding. The method consists simply in shifting every word of the subset codes in such a way so that the shifted versions have a maximum number of leading and trailing zeros. A lower bound on the increase in synchronization-error-correcting capability provided by this method is derived.     

On a class of majority-logic decodable cyclic codes

A new infinite class of cyclic codes is studied. Codes of this class can be decoded in a step-by-step manner, using` majority logic. Some previously known codes fall in this class, and thus admit simpler decoding procedures. As random error-correcting codes, the codes are nearly as powerful as the Bose-Chaudhuri codes.     

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     

Linear codes derived from cyclic codes

This paper presents a procedure for the construction of linear block codes derived from cyclic subspaces. The distance properties of these codes are determined indirectly by the BCH bound despite the fact that they are not cyclic.     

On the existence of optimum cyclic burst- correcting codes

It is shown that for each integerb geq 1infinitely many optimum cyclicb-burst-correcting codes exist, i.e., codes whose lengthn, redundancyr, and burst-correcting capabilityb, satisfyn = 2^{r-b+1} - 1. Some optimum codes forb = 3, 4, and5are also studied in detail.     

On the structure of convolutional and cyclic convolutional codes

Algebraic convolutional coding theory is considered. It is shown that any convolutional code has a canonical direct decomposition into subcodes and that this decomposition leads in a natural way to a minimal encoder. Considering cyclic convolutional codes, as defined by Piret, an easy application of the general theory yields a canonical direct decomposition into cyclic subcodes, and at the same time a canonical minimal encoder for such codes. A list of pairs(n,k)admitting completely proper cyclic(n, k)-convolutional codes is included.     

Good block codes derived from cyclic codes

By combining irreducible cyclic codes, we obtain good quasicyclic or extended quasicyclic codes. Some of these improve on the lower bound of Helgert and Stinaff.     

Self-synchronizing codes derived from binary cyclic codes

The sensitivity of a binary block code to loss of synchronism (misplacement of the "commas" separating codewords) can be characterized by a pair of numbers[s, delta]such that any synchronization slip of s bits or less produces an overlap sequence differing from a legitimate codeword in at leastdeltaplaces. This definition is broader than that of comma freedom of indexdelta, which is included as the special case of s equal to the integer part of half the code block length. For codes having the slip-detecting characteristic[s, delta]there exists the possibility of implementation to restore synchronism during an interval relatively free from bit errors. It is shown that certain error-correcting binary cyclic block codes can be altered to obtain the characteristic[s, delta]by the addition of a fixed binary vector to each codeword prior to transmission. These altered cyclic codes retain the full error-correcting power of the original cyclic codes. An error-detecting/correcting data format providing protection against the acceptance of misframed data is thus obtained without the insertion of special synchronizing sequences into the bit stream.     

Permutation-decodable binary cyclic codes

The letter develops bounds on the information rates of certain binary cyclic codes so that they are s-step permutation decodable (s=2, 3, 4).     

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.     

Efficient burst-correcting cyclic codes

A class of single burst error-correcting cyclic codes is introduced. The binary version of these codes has block length n = 2m ? 1, number of parity check digits n ? k = 2m?1, and correct bursts of length b = 2m?2, where m is an integer. These codes achieve the upper bound b ?(n ? k)/2, and normally have more information digits than interleaved codes of the same burst-correcting power. The multilevel case is also treated in the letter.     

On the optimum design of unitary cyclic group space-time codes

In this letter, based on the exact pairwise-error probability, we derive the union bound on the symbol-error probability (SEP) of the differential unitary space-time (DUST) modulation employing group codes. Instead of using the rank-and-determinant or Euclidean distance criteria, we optimize the cyclic group codes such that the union bound on the SEP is minimized for a predetermined scenario, taking into account the number of transmit and receive antennas and the operating signal-to-noise ratio (SNR). Our simulation results show that for a wide range of SNRs, the codes with the minimum union bound for a particular SNR outperform the codes designed based on rank-and-determinant or Euclidean distance criteria.     

On the weight distribution of cyclic codes (Corresp.)

Letg(x)h(x) = x^n - 1, n = q^m - 1, and assume thath(x)contains a primitive factorf(x)of degreem. IfVis theq-ary(n, k)cyclic code generated byg(x), Uits subcode generated byg(x)f(x), then it will be shown that the weight distribution ofVcan be obtained from the weight distribution ofUand its cosetU + g(x).     

Quantum cyclic and constacyclic codes

Based on classical quaternary constacyclic linear codes, we construct a set of quantum codes with parameters [[(4/sup m/ -1)/3, (4/sup m/ -1)/3 -2(3l + b)m, 4l + b + 2]] where m/spl ges/4, 1/spl les/b/spl les/3, and 12l + 3b < 2 /spl times/ 4/sup /spl lfloor/(m+2)/3/spl rfloor//-1, which are better than the codes in Bierbrauer and Edel (2000).     

Easily decodable binary cyclic codes

This paper presents a class of binary cyclic codes with block length n = 2^m? 1, having n?k = 2^m? parity checks and a minimum distance d=m +1, where m is an integer. These codes are shown to be majority logic decodable in one step by making use of the concept of a quasi-perfect finite difference set.     

New binary codes from a chain of cyclic codes

Starting with a chain of cyclic linear binary codes of length 127, linear binary codes of lengths 129-167, and dimensions 30-50 are constructed. Some of these codes have a minimum distance exceeding the lower bound given in Brouwer's table     

Threshold decoding of cyclic codes

It is shown that every cyclic code overGF(p)can be decoded up to its minimum distance by a threshold decoder employing general parity checks and a single threshold element. This result is obtained through the application of a general decomposition theorem for complex-valued functions defined on the space of alln-tuples with elements from the ring of integers modulop.