Weight enumerator for second-order Reed-Muller codes

In this paper, we establish the following result. Theorem:A_i, the number of codewords of weightiin the second-order binary Reed-Muller code of length2^mis given byA_i = 0unlessi = 2^{m-1}or2^{m-1} pm 2^{m-l-j}, for somej, 0 leq j leq [m/2], A_0 = A_{2^m} = 1, and begin{equation} begin{split} A_{2^{m-1} pm 2^{m-1-j}} = 2^{j(j+1)} &{frac{(2^m - 1) (2^{m-1} - 1 )}{4-1} } \ .&{frac{(2^{m-2} - 1)(2^{m-3} -1)}{4^2 - 1} } cdots \ .&{frac{(2^{m-2j+2} -1)(2^{m-2j+1} -1)}{4^j -1} } , \ & 1 leq j leq [m/2] \ end{split} end{equation} begin{equation} A_{2^{m-1}} = 2 { 2^{m(m+1)/2} - sum_{j=0}^{[m/2]} A_{2^{m-1} - 2^{m-1-j}} }. end{equation}     

An approximation to the weight distribution of binary primitive BCH codes with designed distances 9 and 11 (Corresp.)

Recently Kasami {em et al.} presented a linear programming approach to the weight distribution of binary linear codes [2]. Their approach to compute upper and lower bounds on the weight distribution of binary primitive BCH codes of length2^{m} - 1withm geq 8and designed distance2t + 1with4 leq t leq 5is improved. From these results, the relative deviation of the number of codewords of weightjleq 2^{m-1}from the binomial distribution2^{-mt} left( stackrel{2^{m}-1}{j} right)is shown to be less than 1 percent for the following cases: (1)t = 4, j geq 2t + 1andm geq 16; (2)t = 4, j geq 2t + 3and10 leq m leq 15; (3)t=4, j geq 2t+5and8 leq m leq 9; (4)t=5,j geq 2t+ 1andm geq 20; (5)t=5, j geq 2t+ 3and12 leq m leq 19; (6)t=5, j geq 2t+ 5and10 leq m leq 11; (7)t=5, j geq 2t + 7andm=9; (8)t= 5, j geq 2t+ 9andm = 8.     

Algorithms for the generation of full-length shift- register sequences

Two algorithms are presented for the generation of full-length shift-register cycles, also referred to as de Bruijn sequences. The first algorithm generates2^{k cdot g(n,k)full cycles of length2^{n}, using3n + k cdot g(n, k)bits of storage, wherekis a free parameter in the range1 leq k leq 2^{((n-4)/2)}, andg(n, k)is of the order ofn - 2 log k. The second algorithm generates about2^{n^{2}/4}full cycles of length2^{n}, using aboutn^{2}/2bits of storage. In both algorithms, the time required to produce the next bit from the lastnbits is close ton. A possible application to the construction of stream ciphers is indicated.     

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.     

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.     

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}.     

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.     

Some 3-error-correcting BCH codes have covering radius 5 (Corresp.)

The coset leader of greatest weight in the 3-error-correcting BCH code of length2^{m}-1has weight 5, for oddm geq 5.     

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.     

On certain projective geometry codes (Corresp.)

LetVbe an(n, k, d)binary projective geometry code withn = (q^{m}-1)/(q - 1), q = 2^{s}, andd geq [(q^{m-r}-1)/(q - 1)] + 1. This code isr-step majority-logic decodable. With reference to the GF(q^{m}) = {0, 1, alpha , alpha^{2} , cdots , alpha^{n(q-1)-1} }, the generator polynomialg(X), ofV, hasalpha^{nu}as a root if and only ifnuhas the formnu = i(q - 1)andmax_{0 leq l < s} W_{q}(2^{l} nu) leq (m - r - 1)(q - 1), whereW_{q}(x)indicates the weight of the radix-qrepresentation of the numberx. LetSbe the set of nonzero numbersnu, such thatalpha^{nu}is a root ofg(X). LetC_{1}, C_{2}, cdots, C_{nu}be the cyclotomic cosets such thatSis the union of these cosets. It is clear that the process of findingg(X)becomes simpler if we can find a representative from eachC_{i}, since we can then refer to a table, of irreducible factors, as given by, say, Peterson and Weldon. In this correspondence it was determined that the coset representatives for the cases ofm-r = 2, withs = 2, 3, andm-r=3, withs=2.     

All binary 3-error-correcting BCH codes of length2^m-ihave covering radius 5 (Corresp.)

Van der Horst and Berger have conjectured that the covering radius of the binary 3-error-correcting Bose-Chaudhuri-Hocquenghem (BCH) code of length2^{m} - l, m geq 4is 5. Their conjecture was proved earlier whenm equiv 0, 1, or 3 (mod 4). Their conjecture is proved whenm equiv 2(mod 4).     

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}).     

Maximum likelihood decoding of certain Reed - Muller codes (Corresp.)

We present an efficient maximum likelihood decoding algorithm for the punctured binary Reed-Muller code of order(m - 3)and length2^{m} - 1, M geq 3, and we give formulas for the weight distribution of coset leaders of such codes.     

When does the modular distance induce a metric in the binary case? (Corresp.)

The modular distance induces a metric if and only if the nonadjacent form of the modulusMhas one of the following forms:1) 2^{n}+2^{n-2} pm 2^{i}, wheren-igeq 4; 2) 2^{n} - 2^{j} pm 2^{i}, where2 leq n -j leq 5andj-igeq 2; 3) 2^{n} pm 2^{j}, wheren -j geq 2; 4) 2^{n}.     

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.     

Mutual information of the white Gaussian channel with and without feedback

The following model for the white Gaussian channel with or without feedback is considered: begin{equation} Y(t) = int_o ^{t} phi (s, Y_o ^{s} ,m) ds + W(t) end{equation} wheremdenotes the message,Y(t)denotes the channel output at timet,Y_o ^ {t}denotes the sample pathY(theta), 0 leq theta leq t. W(t)is the Brownian motion representing noise, andphi(s, y_o ^ {s} ,m)is the channel input (modulator output). It is shown that, under some general assumptions, the amount of mutual informationI(Y_o ^{T} ,m)between the messagemand the output pathY_o ^ {T}is directly related to the mean-square causal filtering error of estimatingphi (t, Y_o ^{t} ,m)from the received dataY_o ^{T} , 0 leq t leq T. It follows, as a corollary to the result forI(Y_o ^ {T} ,m), that feedback can not increase the capacity of the nonband-limited additive white Gaussian noise channel.     

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.     

The geometry of quadrics and correlations of sequences (Corresp.)

Nondegenerate quadrics of PG(2l, 2^{s})have been used to construct ternary sequences of length(2^{2sl+1} - 1)/(2^{s} - 1)with perfect autocorrelation function. The same construction can be used for degenerate quadrics for this case as well as quadrics of PG(N,q), withNarbitrary andq = p^{s}, for any primep. This is possible because it is shown that ifQ subseteq {rm PG} (N, q)is a quadric, possibly degenerate, that has the same size as a hyperplane, then, providedQitself is not a hyperplane, the hyperplanes of PG(N,q)intersectQin three sizes. These sizes depend on whetherNis even or odd and the degeneracy ofQ. Finally, a connection to maximum period linear recursive sequences is made.     

Construction of de Bruijn sequences of minimal complexity

It is well known that the linear complexity of a de Bruijn sequenceSof length2^{n}is bounded below by2^{n- 1} + nforn geq 3. It is shown that this lower bound is attainable for alln.     

On the weight distribution of the coset leaders of the first-order Reed - Muller code (Corresp.)

Letalpha_{n}denote the number of cosets with minimum weightnof the(2^{m}, m + 1)Reed-Muller code. Thealpha_{n}for2^{m-2} leq n < 2^{m-2} + 2^{m - 4}is determined.