Further classifications of codes meeting the Griesmer bound (Corresp.)

For any(n, k, d)binary linear code, the Griesmer bound says thatn geq sum_{i=0}^{k-1} lceil d/2^{i} rceil, wherelceil x rceildenotes the smallest integergeq x. We consider codes meeting the Griesmer bound with equality. These codes have parametersleft( s(2^{k} - 1) - sum_{i=1}^{p} (2^{u_{i}} - 1), k, s2^{k-1} - sum_{i=1}^{p} 2^{u_{i} -1} right), wherek > u_{1} > cdots > u_{p} geq 1. We characterize all such codes whenp = 2oru_{i-1}-u_{i} geq 2for2 leq i leq p.     

Some long cyclic linear binary codes are not so bad

We show that when an inner linear cyclic binary code which has an irreducible check polynomial is concatenated with an appropriately chosen maximal-distance-separable outer code, then the overall code is cyclic OverGF(2). Using this theorem, we construct a number of linear cyclic binary codes which are better than any previously known. In particular, by taking the inner code to be a quadratic residue code, we obtain linear cyclic binary codes of lengthN, rateR, and distanceD geq (1 - 2R)N/ sqrt{2 log N}, which compares favorably with the BCH distanceD sim (2 ln R^{-1})N/log N, although it still fails to achieve the linear growth of distance with block length which is possible with noncyclic linear concatenated codes. While this construction yields many codes, including several with block lengths greater than10^{10^5}, we have not been able to prove that there are arbitrarily long codes of this type without invoking the Riemann hypothesis or the revised Artin conjecture, as the existence of long codes of our type is equivalent to the existence of large primespfor which the index of 2 is(p - 1)/2.     

A new class of codes meeting the Griesmer bound

An infinite sequence ofk-dimensional binary linear block codes is constructed with parametersn=2^{k}+2^{k-2}-15,d=2^{k-1}+2^{k-3}-8,k geq 7. Fork geq 8these codes are unique, while there are five nonisomorphic codes fork=7. By shortening these codes in an appropriate way, one finds codes meeting the Griesmer bound for2^{k-1}+2^{k-3}-15 leq d leq 2^{k-1}+2^{k-3}-8; k geq 7.     

On efficient majority logic decodable codes

A particular shortening technique is applied to majority logic decodable codes of length2^{t}. The shortening technique yields new efficient codes of lengthsn = 2^{p}, wherepis a prime, e.g., a (128,70) code withd_{maj} = 16. For moderately long code lengths (e.g.,n = 2^{11} or 2^{13}), a 20-25 percent increase in efficiency can be achieved over the best previously known majority logic decodable codes. The new technique also yields some efficient codes for lengthsn = 2^{m}wheremis a composite number, for example, a (512,316) code withd_{maj} = 32code which has 42 more information bits than the previously most efficient majority logic decodable code.     

Aperiodic correlation constraints on large binary sequence sets

The existence of binary sequences with specific aperiodic autocorrelation and cross correlation properties is investigated. Relationships are determined among the size of a sequence set, the length of the sequences n, the maximum autocorrelation sidelobe magnitudealpha, and the maximum cross correlation magnitudebeta. The principal result is the proof of the existence of sequence sets characterized by certain combinations ofn, alpha, andbeta. The proof makes use of a new lower bound to the expected size of sequence sets constructed according to an explicit "random coding" procedure. For largen, the sequence set size is controlled primarily by the cross correlation constraintbeta. Two consequences of the existence theorem are 1) a demonstration that large sequence sets exist for which the maximum autocorrelation sidelobe and cross correlation magnitudes vanish almost as fast as the inverse square root of the sequence length(l/sqrt{n}); 2)a new proof of the Gilbert bound of coding theory.     

On some properties of the undetected error probability of linear codes (Corresp.)

A recent paper [1] discussed the2^{-p}bound (wherep = n- k) for the probability of undetected errorP(epsilon)for an(n,k)block code used for error detection on a binary symmetric channel. This investigation is continued and extended and dual codes are studied. The dual and extension of a perfect code obey the2^{-p}bound, but this is not necessarily true for arbitrary codes that obey the bound. Double-error-correcting BCH codes are shown to obey the bound. Finally the problem of constructing uniformly good codes is examined.     

High-radix transforms for Reed-Solomon codes over Fermat primes (Corresp.)

It is shown that a high-radix fast Fourier transform (FFT) with generatorgamma = 3over GF(F_{n}), whereF_{n} = 2^{2}^{n'} + 1is a Fermat prime, can be used for encoding and decoding of Reed-Solomon (RS) codes of length2^{2}^{n}. Such an RS decoder is considerably faster than a decoder using the usual radix 2 FFT. This technique applies most ideally to a 16-error-correcting, 256-symbol RS code of 8 bits being considered currently for space communication applications. This special code can be encoded and decoded rapidly using a high-radix FFT algorithm over GF(F_{3}).     

Duadic Codes

A new family of binary cyclic(n,(n + 1)/2)and(n,(n - 1)/2)codes are introduced, which include quadratic residue (QR) codes whennis prime. These codes are defined in terms of their idempotent generators, and they exist for all oddn = p_{1}^{a_{1}} p_{2}^{a_{2}} cdots p_{r}^{a_{r}}where eachp_{i}is a primeequiv pm 1 pmod{8}. Dual codes are identified. The minimum odd weight of a duadic(n,(n + 1)/2)code satisfies a square root bound. When equality holds in the sharper form of this bound, vectors of minimum weight hold a projective plane. The unique projective plane of order 8 is held by the minimum weight vectors in two inequivalent(73,37,9)duadic codes. All duadic codes of length less than127are identified, and the minimum weights of their extensions are given. One of the duadic codes of length113has greater minimum weight than the QR code of that length.     

Some Remarks on BCH Bounds and Minimum Weights of Binary Primitive BCH Codes

It is shown that ifm neq 8, 12andm > 6, there are some binary primitive BCH codes (BCH codes in a narrow sense) of length2^{m} - 1whose minimum weight is greater than the BCH bound. This gives a negative answer to the question posed by Peterson [1] of whether or not the BCH bound is always the actual minimum weight of a binary primitive BCH code. It is also shown that for any evenm geq 6, there are some binary cyclic codes of length2^{m} - 1that have more information digits than the primitive BCH codes of length2^{m} - 1with the same minimum weight.     

Weight distribution of translates, covering radius, and perfect codes correcting errors of given weights

LetVbed binary linear(n,k)code defined by a check matrixHand leth(x)be the characteristic function for the set of columns ofH. Connections between the Walsh transform ofh(x)and the weight distributions of all translates of the code are obtained. Explicit formulas for the weight distributions of translates are given for small weightsi(i<8). The computation of the weight distribution of all translates (including the code itself) fori<8requires at most7(n-k)2^{n-k}additions and subtractions,6 cdot 2^{n-k}multiplications and2^{n-k+l}memory cells. This method may be very effective if there is an analytic expression forh(x). A simple method for computing the covering radius of the code by the Walsh transform ofh(x)is described. The implementation of this method requires for largenat most2^{n-k}(n-k) log_{2}(n-k)arithmetical operations and2^{n-k+1}memory cells. We define the conceptL-perfect for codes, whereLis a set of weights. After describing several linear and nonlinearL-perfect codes, necessary and sufficient conditions for a code to beL-perfect in terms of the Walsh transform ofh(x)are established. An analog of the Lloyd theorem for such codes is proved.     

A fundamental inequality between the probabilities of binary subgroups and cosets

The probability of a set of binaryn-tuples is defined to be the sum of the probabilities of the individualn-tuples when each digit is chosen independently with the same probabilitypof being a "one." It is shown that, under such a definition, the ratio between the probability of a subgroup of order2^{k}and any of its proper cosets is always greater than or equal to a functionF_{k}(p), whereF_{k}(p) geq 1forp leq frac{1}{2}with equality when and only whenp = frac{1}{2}. It is further shown thatF_{k}(p)is the greatest lower bound on this ratio, since a subgroup and proper coset of order2^{k}can always be found such that the ratio between their probabilities is exactlyF_{k}(p). It is then demonstrated that for a linear code on a binary symmetric channel the "tall-zero" syndrome is more probable than any other syndrome. This result is applied to the problem of error propagation in convolutional codes.     

New binary codes

In this paper constructions are given for combining two, three, or four codes to obtain new codes. The Andryanov-Saskovets construction is generalized. It is shown that the Preparata double-error-correcting codes may be extended by about (block length)^{1/2}symbols, of which only one is a check symbol, and thate-error-correcting BCH codes may sometimes be extended by (block !ength)^{1/e}symbols, of which only one is a check symbol. Several new families of linear and nonlinear double-error-correcting codes are obtained. Finally, an infinite family of linear codes is given withd/n = frac{1}{3}, the first three being the(24,2^12, 8)Golay code, a(48,2^15, 16)code, and a(96,2^18, 32)code. Most of the codes given have more codewords than any comparable code previously known to us.     

Some randomness properties of cascaded sequences (Corresp.)

The autonomous response sequences of cascade coupled sequence generators are investigated. Them-tuple distribution and autocorrelation function of such sequences are related to them-tuple distribution of the component sequences. Cascade coupled pseudonoise (PN) sequence generators withtcumpunents have output sequences with anm-tuple distribution that approximates them-tuple distribution of a random sequence in which the probability of a one is2^{-t}. The phase shifts are almost uncorrelated for most shifts, but some shifts are highly correlated.     

Multiple-burst error-correcting cyclic product codes (Corresp.)

LetCbe the cyclic product code ofpsingle parity check codes of relatively prime lengthsn_{1}, n_{2},cdots , n_{p} (n_{1} < n_{2} < cdots < n_{p}). It is proven thatCcan correct2^{P-2}+2^{p-3}-1bursts of lengthn_{1}, andlfloor(max{p+1, min{2^{p-s}+s-1,2^{p-s}+2^{p-s-1}}}-1)/2rfloorbursts of lengthn_{1}n_{2} cdots n_{s} (2leq s leq p-2). Forp=3this means thatCis double-burst-n_{1}-correcting. An efficient decoding algorithm is presented for this code.     

On the distribution of de Bruijn sequences of given complexity

The distributiongamma (c, n)of de Bruijn sequences of ordernand linear complexitycis investigated. It is shown that forn geq 4, gamma (2^{n} - 1, n) equiv 0 pmod{8}, and fork geq 3, gamma (2^{2k} - 1,2k) equiv 0 pmod{l6}. It is also shown thatgamma (c, n) equiv 0 pmod{4}for allc, andn geq 3such thatcnis even.     

Ternary sequences with perfect periodic autocorrelation (Corresp.)

We construct0, pm 1sequences of length(q^{2l+1}-l)/(q-1), whereq=2^{s}, with out-of-phase periodic autocorrelation0, and in-phase correlationq^{2l};SUch that the peak factor of radiation is(q^{2l+1}-1) /(q^{2+l}-q^{2l}), which is close to1asqbecomes large.     

The inhibition of negative resistance dipole waves and domains in n-GaAs

Expressions describing the growth and propagation of infinitesimal space-charge waves in the presence of a differential negative resistance are derived, and conditions for the inhibition of dipole waves and domains inn-GaAs of resistivity greater than 10Ω-cm at 300°K are obtained. Thermoelectric effects are estimated and found to be small for carrier densities much less than 10¹⁵cm^-3. Taking the negative differential resistivity to be larger than the ohmic resistivity by a factor of 10²leads to 1) condition for inhibition of dipole waves:nl^{2} lsim 10^{9}cm^-12) condition for inhibition of stable domains:nl lsim 10^{12}cm^-2whenn= electron density andl= specimen length. The relevance of these results to explaining the phenomena observed in amplifying crystals is pointed out. It is suggested that the condition for amplification is(frac{10^{9}}{n})^{1/2} lsim l lsim frac{10^{12}}{n}.     

The fast decoding of Reed-Solomon codes using Fermat transforms (Corresp.)

It is shown thatsqrt[8]{2}is an element of order2^{n+4}inGF(F_{n}), whereF_{n}=2^{2^{n}}+1is a Fermat prime forn=3,4. Hence it can be used to define a fast Fourier transform (FFT) of as many as2^{n+4}symbols inGF(F_{n}). Sincesqrt[8]{2}is a root of unity of order2^{n+4}inGF(F_{n}), this transform requires fewer muitiplications than the conventional FFT algorithm. Moreover, as Justesen points out [1], such an FFT can be used to decode certain Reed-Solomon codes. An example of such a transform decoder for the casen=2, wheresqrt{2}is inGF(F_{2})=GF(17), is given.     

On the covering radius of binary codes (Corresp.)

Upper bounds on the covering radius of binary codes are studied. In particular it is shown that the covering radiusr_{m}of the first-order Reed-Muller code of lenglh2^{m}satisfies2^{m-l}-2^{lceil m/2 rceil -1} r_{m} leq 2^{m-1}-2^{m/2-1}.