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.     

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.     

Linear feedback rate bounds for regressive channels (Corresp.)

This article presents new tighter upper bounds on the rate of Gaussian autoregressive channels with linear feedback. The separation between the upper and lower bounds is small. We havefrac{1}{2} ln left( 1 + rho left( 1+ sum_{k=1}^{m} alpha_{k} x^{- k} right)^{2} right) leq C_{L} leq frac{1}{2} ln left( 1+ rho left( 1+ sum_{k = 1}^{m} alpha_{k} / sqrt{1 + rho} right)^{2} right), mbox{all rho}, whererho = P/N_{0}W, alpha_{l}, cdots, alpha_{m}are regression coefficients,Pis power,Wis bandwidth,N_{0}is the one-sided innovation spectrum, andxis a root of the polynomial(X^{2} - 1)x^{2m} - rho left( x^{m} + sum^{m}_{k=1} alpha_{k} x^{m - k} right)^{2} = 0.It is conjectured that the lower bound is the feedback capacity.     

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.     

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

Higher dimensional orthogonal designs and applications

The concept of orthogonal design is extended to higher dimensions. A properg-dimensional design[d_{ijk cdots upsilon}]is defined as one in which all parallel(g-1)-dimensional layers, in any orientation parallel to a hyper plane, are uncorrelated. This is equivalent to the requirement thatd_{ijk cdots upsilon} in {0, pm x_{1}, cdots , pm x_{t} }, wherex_{1}, cdots , x_{t}are commuting variables, and thatsum_{p} sum_{q} sum_{r} cdots sum_{y} d_{pqr cdots ya} d_{pqr cdots yb} = left( sum_{t} s_{i}x_{i}^{2} right)^{g-1} delta ab,where(s{1}, cdots , s{t})are integers giving the occurrences ofpm x_{1}, cdots , pm x_{t}in each row and column (this is called the type(s_{1}, cdot ,s_{t})^{g-1})and(pqr cdots yz)represents all permutations of(ijk cdots upsilon). This extends an idea of Paul J. Shlichta, whose higher dimensional Hadamard matrices are special cases withx_{1}, cdots , x_{t} in {1,- 1}, (s_{1}, cdots, s_{t})=(g), and(sum_{t}s_{i}x_{i}^{2})=g. Another special case is higher dimensional weighing matrices of type(k)^{g}, which havex_{1}, cdots , x_{t} in {0,1,- 1}, (s_{1}, cdots, s_{t})=(k), and(sum_{t}s_{i}x_{i}^{2})=k. Shlichta found properg-dimensional Hadamard matrices of size(2^{t})^{g}. Proper orthogonal designs of type     

Dual product constructions of Reed - Muller type codes (Corresp.)

Various linear and nonlinearR(r,m)codes having parameters(2^{m}, 2^{k}, 2^{m-r})withk=sum_{i=0}^{r}left(^{m}_{i}right)are constructed fromR(r,q)andR(r,p)codes,m=p+q. A dual construction forR(m-r,m)codes fromR(p-r,p)andR(q-r,q)codes is also presented,m=p+q. As a simple corollary we have that the number of nonequivalentR(r,m)codes is at least exponential in the length (forr>1). ForR(m-r,m)codes, the lower bound is doubly exponential in the length (forr>1).     

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 algorithm for maximizing expected log investment return

Let the random (stock market) vectorX geq 0be drawn according to a known distribution functionF(x), x in R^{m}. A log-optimal portfoliob^{ast}is any portfoliobachieving maximal expectedlogreturnW^{ast}=sup_{b} E ln b^{t}X, where the supremum is over the simplexb geq 0, sum_{i=1}^{m} b_{i} = 1. An algorithm is presented for findingb^{ast}. The algorithm consists of replacing the portfoliobby the expected portfoliob^{'}, b_{i}^{'} = E(b_{i}X_{i}/b^{t}X), corresponding to the expected proportion of holdings in each stock after one market period. The improvement inW(b)after each iteration is lower-bounded by the Kullback-Leibler information numberD(b^{'}|b)between the current and updated portfolios. Thus the algorithm monotonically improves the returnW. An upper bound onW^{ast}is given in terms of the current portfolio and the gradient, and the convergence of the algorithm is established.     

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.     

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.     

On single-sample robust detection of known signals with additive unknown-mean amplitude-bounded random interference--II: The randomized decision rule solution (Corresp.)

A randomized decision rule is derived and proved to be the saddlepoint solution of the robust detection problem for known signals in independent unknown-mean amplitude-bounded noise. The saddlepoint solutionphi^{0}uses an equaUy likely mixed strategy to chose one ofNBayesian single-threshold decision rulesphi_{i}^{0}, i = 1,cdots , Nhaving been obtained previously by the author. These decision rules are also all optimal against the maximin (least-favorable) nonrandomized noise probability densityf_{0}, wheref_{0}is a picket fence function withNpickets on its domain. Thee pair(phi^{0}, f_{0})is shown to satisfy the saddlepoint condition for probability of error, i.e.,P_{e}(phi^{0} , f) leq P_{e}(phi^{0} , f_{0}) leq P_{e}(phi, f_{0})holds for allfandphi. The decision rulephi^{0}is also shown to be an eqoaliir rule, i.e.,P_{e}(phi^{0}, f ) = P_{e}(phi^{0},f_{0}), for allf, with4^{-1} leq P_{e}(phi^{0},f_{0})=2^{-1}(1-N^{-1})leq2^{-1} , N geq 2. Thus nature can force the communicator to use an {em optimal} randomized decision rule that generates a large probability of error and does not improve when less pernicious conditions prevail.     

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.     

On MDS extensions of generalized Reed- Solomon codes

An(n, k, d)linear code overF=GF(q)is said to be {em maximum distance separable} (MDS) ifd = n - k + 1. It is shown that an(n, k, n - k + 1)generalized Reed-Solomon code such that2leq k leq n - lfloor (q - 1)/2 rfloor (k neq 3 {rm if} qis even) can be extended by one digit while preserving the MDS property if and only if the resulting extended code is also a generalized Reed-Solomon code. It follows that a generalized Reed-Solomon code withkin the above range can be {em uniquely} extended to a maximal MDS code of lengthq + 1, and that generalized Reed-Solomon codes of lengthq + 1and dimension2leq k leq lfloor q/2 rfloor + 2 (k neq 3 {rm if} qis even) do not have MDS extensions. Hence, in cases where the(q + 1, k)MDS code is essentially unique,(n, k)MDS codes withn > q + 1do not exist.     

On mean-square aliasing error in the cardinal series expansion of random processes (Corresp.)

An upper bound is derived for the mean-square error involved when a non-band-limited, wide-sense stationary random processx(t)(possessing an integrable power spectral density) is approximated by a cardinal series expansion of the formsum^{infty}_{-infty}x(n/2W)sinc2W(t-n/2W), a sampling expansion based on the choice of some nominal bandwidthW > 0. It is proved thatlim_{N rightarrow infty} E {|x(t) - x_{N}(t)|^{2}} leq frac{2}{pi}int_{| omega | > 2 pi W}S_{x}( omega) d omega,wherex_{N}(t) = sum_{-N}^{N}x(n/2W)sinc2W(t-n/2W), andS_{x}(omega)is the power spectral density forx(t). Further, the constant2/ piis shown to be the best possible one if a bound of this type (involving the power contained in the frequency region lying outside the arbitrarily chosen band) is to hold uniformly int. Possible reductions of the multiplicative constant as a function oftare also discussed, and a formula is given for the optimal value of this constant.     

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.     

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.