Hybrid low autocorrelation sequences (Corresp.)

Skew-symmetric sequences of(2n + 1)terms,a_0,a_1,cdots,a_{2n}, are described for which the "merit factor" begin{equation} F_h = frac{biggl[sum_{i=0}^{2n} mid a_i mid biggr] ^2}{ 2 sum_{k=1}^{2n} biggl[ sum_{i=0}^{2n-k} text{sign} (a_i) cdot a_{i+k} biggl] ^2} end{equation} is unusually high.     

Gleason's theorem on self-dual codes

The weight enumerator of a code is the polynomial begin{equation} W(x,y)= sum_{r=0}^n A_r x^{n-r} y^r, end{equation} wherendenotes the block length andA_r, denotes the number of codewords of weightr. LetCbe a self-dual code overGF(q)in which every weight is divisible byc. Then Gleason's theorem states that 1) ifq= 2 andc= 2, the weight enumerator ofCis a sum of products of the polynomialsx^2 + y^2andx^2y^2 (x^2 - y^2 )^2ifq= 2 andc= 4, the weight enumerator is a sum of products ofx^8 + 14x^4 y^4 + y^8andx^4 y^4 (x^4 - y^4)^4; and 3) ifq= 3 andc= 3, the weight enumerator is a sum of products ofx^4 + 8xy^3andy^3(x^3 - y^3)^3. In this paper we give several proofs of Gleason's theorem.     

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.     

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.     

A theorem on the entropy of certain binary sequences and applications--I

In this, the first part of a two-part paper, we establish a theorem concerning the entropy of a certain sequence of binary random variables. In the sequel we will apply this result to the solution of three problems in multi-user communication, two of which have been open for some time. Specifically we show the following. LetXandYbe binary randomn-vectors, which are the input and output, respectively, of a binary symmetric channel with "crossover" probabilityp_0. LetH{X}andH{ Y}be the entropies ofXandY, respectively. Then begin{equation} begin{split} frac{1}{n} H{X} geq h(alpha_0), qquad 0 leq alpha_0 &leq 1, Rightarrow \ qquad qquad &qquad frac{1}{n}H{Y} geq h(alpha_0(1 - p_0) + (1 - alpha_0)p_0) end{split} end{equation} whereh(lambda) = -lambda log lambda - (1 - lambda) log(l - lambda), 0 leq lambda leq 1.     

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.     

Estimation of the mean with time-varying finite memory (Corresp.)

LetX_1,X_2,cdotsbe a sequence of independent identically distributed observations with a common meanmu. Assume that0 leq X_i leq 1with probability 1. We show that for eachvarepsilon > 0there exists an integerm, a finite-valued statisticT_n = T_n(X_1, cdots , X_n) in {t_1,cdots,t_m}and a real-valued functionddefined on{t_1,cdots,t_m}such thati)T_{n+1} = f_n(T_n,X_{n+1}); ii)P[lim sup mid d(T_n) - mu mid leq varepsilon] = 1. Thus we have a recursive-like estimate ofmu, for which the data are summarized for eachnby one ofmstates and which converges to withinvarepsilonofmuwith probability 1. The constraint on memory here is time varying as contrasted to the time-invariant constraint that would haveT_{n+1} = f(T_n, X_{n+1})for alln.     

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.     

A dichotomy of functionsF(X, Y)of correlated sources(X, Y)

Consider separate encoding of correlated sourcesX^{n}=(X_{l}, cdots ,X_{n}), Y^{n} = (Y_{l}, cdots ,Y_{n})for the decoder to reliably reproduce a function{F(X_{i}, Y_{i})}^{n}_{i=1}. We establish the necessary and sufficient condition for the set of all achievable rates to coincide with the Slepian-Wolf region whenever the probability densityp(x,y)is positive for all(x,y).     

On the mutual information of memoryless channels

Letx_1, cdots ,x_nandy_1, cdots, y_nbe input and output sequences of a channel. In the case of memoryless input sources, the following inequality on mutual information is well known: begin{equation} I((x_1, cdots ,x_n),(y_1, cdots ,y_n)) geq sum I(x_i, y_i). end{equation} It is straightforward to show that the inequality sign is reversed if the channel instead of the input source is memoryless. In this paper we establish these inequalities when the input and output are functions instead of sequences.     

On the weight distribution of binary linear codes (Corresp.)

LetVbe a binary linear(n,k)-code defined by a check matrixHwith columnsh_{1}, cdots ,h_{n}, and leth(x) = 1ifx in {h_{1}, cdots , h_{n}, andh(x) = 0ifx in neq {h_{1}, cdots ,h_{n}}. A combinatorial argument relates the Walsh transform ofh(x)with the weight distributionA(i)of the codeVfor smalli(i< 7). This leads to another proof of the Plessith power moment identities fori < 7. This relation also provides a simple method for computing the weight distributionA(i)for smalli. The implementation of this method requires at most(n-k+ 1)2^{n-k}additions and subtractions,5.2^{n-k}multiplications, and2^{n-k}memory cells. The method may be very effective if there is an analytic expression for the characteristic Boolean functionh(x). This situation will be illustrated by several examples.     

Uniform linear prediction of bandlimited processes from past samples (Corresp.)

Forx(t)either a deterministic or stochastic signal band-limited to the normalized frequency intervalmidomegamid leq pi, explicit coefficients{ a_{kn} }are exhibited that have the property that begin{equation} lim_{n rightarrow infty} parallel x(t) - sum_{1}^n a_{kn} x(t - kT) parallel = 0 end{equation} in an appropriate norm and for any constant intersample spacingTsatisfying0 < T < fac{1}{2}; that is,x(t)may be approximated arbitrarily well by a linear combination of past samples taken at any constant rate that exceeds twice the associated Nyquist rate. Moreover, the approximation ofx(t)is uniform in the sense that the coefficients{ a_{kn} }do not depend on the detailed structure ofx(t)but are absolute constants for any choice ofT. The coefficients that are obtained provide a sharpening of a previous result by Wainstein and Zubakov where a rate in excess of three times the Nyquist rate was required.     

Bayes estimation with asymmetrical cost functions (Corresp.)

It is known that under certain restrictions on the posterior density and assigned cost function, the Bayes estimate of a random parameter is the conditional mean. The restrictions on the cost function are that it must be a symmetric convex upward function of the difference between the parameter and the estimate. In this correspondence, asymmetrical cost functions of the following form are examined: begin{equation} C(a, hat{a})= begin{cases} f_1(a- hat{a}),& a geq hat{a} \ f_2(hat{a}- a),& a < hat{a} end{cases} end{equation} wheref_1(cdot), f_2(cdot)are both twice-differentiable convex upward positive functions on[0, infty]that intersect the origin. It is shown that for posterior densities satisfying a certain symmetry condition, the biased Bayes estimate is a generalized median. Furthermore, for linear polynomial functionsf_1(cdot), f_2(cdot), the unbiased Bayes estimate is shown to be the conditional mean.     

On the survival of sequence information in filters (Corresp.)

Given a binary data streamA = {a_i}_{i=o}^inftyand a filterFwhose output at timenisf_n = sum_{i=0}^{n} a_i beta^{n-i}for some complexbeta neq 0, there are at most2^{n +1)distinct values off_n. These values are the sums of the subsets of{1,beta,beta^2,cdots,beta^n}. It is shown that all2^{n+1}sums are distinct unlessbetais a unit in the ring of algebraic integers that satisfies a polynomial equation with coefficients restricted to +1, -1, and 0. Thus the size of the state space{f_n}is2^{n+1}ifbetais transcendental, ifbeta neq pm 1is rational, and ifbetais irrational algebraic but not a unit of the type mentioned. For the exceptional values ofbeta, it appears that the size of the state space{f_n}grows only as a polynomial innifmidbetamid = 1, but as an exponentialalpha^nwith1 < alpha < 2ifmidbetamid neq 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.     

New family of single-error correcting codes

A construction is given that combines an(n, M_1, d_1)code with an(n, M_2, d_2 = [frac{1}{2}(d_1 + 1)])code to form a(2n, M_1 M_2, d_1)code. This is used to construct a new family of nongroup single-error correcting codes of all lengthsnfrom2^mto 3 ·2^{m-1} - 1, for everym geq 3. These codes have more codewords than any group code of the same length and minimum distance. A number of other nongroup codes are also obtained. Examples of the new codes are (16,2560,3) and (16,36,7) codes, both having more codewords than any comparable group code.     

Coding the vertexes of a graph

Given a graphGofnnodes. We wish to assign to each nodei(i = 1, 2, cdots n)a unique binary codec_{i}of lengthmsuch that, if we denote the Hannuing distance betweenc_{i}andc_{j}asH(c_{i}, c_{j}), thenH(c_{i}, c_{j})leq Tif nodesiandjare adjacent (i.e., connected by a single branch), andH(c_{i}, c_{j}) geq T+1otherwise. If such a code exists, then we say thatGis doable for the value ofTand tn associated with this code. In this paper we prove various properties relevent to these codes. In particular we prove 1) that for every graphGthere exists anmandTsuch thatGis doable, 2) for every value ofTthere exists a graphG̃which is notTdoable, 3) ifGisT'doable, then it isT'+ 2pdoable forp = 0, 1, 2, cdots, and is doable for allT geq 2T'ifT'is odd, and is doable for allT geq 2T' + 1ifT'is even. In theory, the code can be synthesized by employing integer linear programming where eitherTand/ormcan be minimized; however, this procedure is computationally infeasible for values ofnandmin the range of about10or greater.