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     

A simple proof of the Ahlswede - Csiszár one-bit theorem (Corresp.)

It is proved that if(X,Y)are two finite alphabet correlated sources withp(x,y)>0for all(x,y) in ({cal X} times {cal Y}), and if a functionF(X,Y)isalpha-sensitive, then the rateRof transmission fromXtoYnecessary to computeF(X,Y)reliably must be greater thanH(X|Y). The same result holds if the function is highly sensitive and for everyx_{1} neq x_{2} in {cal X}, then the number of elementsy in {cal Y}withp(x_{l},y) cdot p(x_{2}, y)>0is different from one.     

Sequences achieving the boundary of the entropy region for a two-source are virtually memoryless (Corresp.)

For a joint distribution{rm dist}(X,Y), the functionT(t)=min { H(Y|U): I(U wedge Y|X)=O, H(X|U)geq t}is an important characteristic. It equals the asymptotic minimum of(1/n)H(Y^{n})for random pairs of sequences(X^{n}, Y^{n}), wherefrac{1}{n} sum ^{n}_{i=1}{rm dist} X_{i} sim {rm dist} X, {rm dist} Y^{n}|X^{n} = ({rm dist} Y|X)^{n}, frac{1}{n}H(X^{n})geq t.We show that if, for(X^{n}, Y^{n})as given, the rate pair[(1/n)H(X^{n}),(1/n)H(Y^{n})]approaches the nonlinear part of the curve(t,T(t)), then the sequenceX^{n}is virtually memoryless. Using this, we determine some extremal sections of the rate region of entropy characterization problems and find a nontrivial invariant for weak asymptotic isomorphy of discrete memoryless correlated sources.     

Capacity theorems for the relay channel

A relay channel consists of an inputx_{l}, a relay outputy_{1}, a channel outputy, and a relay senderx_{2}(whose transmission is allowed to depend on the past symbolsy_{1}. The dependence of the received symbols upon the inputs is given byp(y,y_{1}|x_{1},x_{2}). The channel is assumed to be memoryless. In this paper the following capacity theorems are proved. 1)Ifyis a degraded form ofy_{1}, thenC : = : max !_{p(x_{1},x_{2})} min ,{I(X_{1},X_{2};Y), I(X_{1}; Y_{1}|X_{2})}. 2)Ify_{1}is a degraded form ofy, thenC : = : max !_{p(x_{1})} max_{x_{2}} I(X_{1};Y|x_{2}). 3)Ifp(y,y_{1}|x_{1},x_{2})is an arbitrary relay channel with feedback from(y,y_{1})to bothx_{1} and x_{2}, thenC: = : max_{p(x_{1},x_{2})} min ,{I(X_{1},X_{2};Y),I ,(X_{1};Y,Y_{1}|X_{2})}. 4)For a general relay channel,C : leq : max_{p(x_{1},x_{2})} min ,{I ,(X_{1}, X_{2};Y),I(X_{1};Y,Y_{1}|X_{2}). Superposition block Markov encoding is used to show achievability ofC, and converses are established. The capacities of the Gaussian relay channel and certain discrete relay channels are evaluated. Finally, an achievable lower bound to the capacity of the general relay channel is established.     

On theepsilon-entropy and the rate-distortion function of certain non-Gaussian processes

Letxi = {xi(t), 0 leq t leq T}be a process with covariance functionK(s,t)andE int_0^T xi^2(t) dt < infty. It is proved that for everyvarepsilon > 0thevarepsilon-entropyH_{varepsilon}(xi)satisfies begin{equation} H_{varepsilon}(xi_g) - mathcal{H}_{xi_g} (xi) leq H_{varepsilon}(xi) leq H_{varepsilon}(xi_g) end{equation} wherexi_gis a Gaussian process with the covarianeeK(s,t)andmathcal{H}_{xi_g}(xi)is the entropy of the measure induced byxi(in function space) with respect to that induced byxi_g. It is also shown that ifmathcal{H}_{xi_g}(xi) < inftythen, asvarepsilon rightarrow 0begin{equation} H_{varepsilon}(xi) = H_{varepsilon}(xi_g) - mathcal{H}_{xi_g}(xi) + o(1). end{equation} Furthermore, ff there exists a Gaussian processg = { g(t); 0 leq t leq T }such thatmathcal{H}_g(xi) < infty, then the ratio betweenH_{varepsilon}(xi)andH_{varepsilon}(g)goes to one asvarepsilongoes to zero. Similar results are given for the rate-distortion function, and some particular examples are worked out in detail. Some cases for whichmathcal_{xi_g}(xi) = inftyare discussed, and asymptotic bounds onH_{varepsilon}(xi), expressed in terms ofH_{varepsilon}(xi_g), are derived.     

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 capacity of certain additive non-Gaussian channels

A model of an additive non-Gaussian noise channel with generalized average input energy constraint is considered. The asymptotic channel capacityC_{zeta}(S), for large signal-to-noise ratioS, is found under certain conditions on the entropyH_{ tilde{ zeta}}( zeta)of the measure induced in function space by the noise processzeta, relative to the measure induced bytilde{zeta}, where is a Gaussian process with the same covariance as that ofzeta. IfH_{ tilde{zeta}}( zeta) < inftyand the channel input signal is of dimensionM< infty, thenC_{ zeta}(S)= frac{1}{2}M ln(1 + S/M) + Q_{zeta}( M ) + {o}(1), where0 leq Q_{ zeta}( M ) leq H_{ tilde{ zeta}}( zeta). If the channel input signal is of infinite dimension andH_{ tilde{ zeta}}( zeta) rightarrow 0forS rightarrow infty, thenC_{ zeta}(S) = frac{1}{2}S+{o}(1).     

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.     

Repeated use of codes which detect deception (Corresp.)

A senderAwants to sendNmessagesx_{i} = 1 , ldots ,N, chosen from a set containingMdifferent possible messages,M > N, to a receiverB. Everyx_{i}has to pass through the hands of a dishonest messengerC. ThereforeAandBagree on a mathematical transformationfand a secret parameter, or keyk, that will be used to produce the authenticatory_{i} = f(x_{i} , k ), which is sent together withx. The key is chosen at random from a set ofLelements.Cknowsfand can find all elements in the setG(x_{i},y_{i}) = {k|f(x_{i}, k) = y_{i}}given enough time and computer resources.Cwants to changex_{i} into x^{prime}withoutBsuspecting. This means thatCmust find the new anthenticatory^{prime} = f(x^{prime} , k). SinceG(x_{i},y_{i})can be found for any(x_{i},y_{i}), it is obvious thatCwill always succeed unlessG(x_{i},y_{i})contains more than one element. Here it is proved that the average probability of success forCis minimized if (a)G(x_{i}, y_{i})containsL^{(N-1)/N}elements and (b) each new known pair(x_{j}, y_{j})will diminish this set of solutions by a factor ofL^{-l/N}. The minimum average probability will then beL^{-l/N}.     

Improvements of Winograd's result on computation in the presence of noise (Corresp.)

Winograd's result concerning Elias' model of computation in the presence of noise can be stated without reference to computation. If a codevarphi: {0,1}^{k} rightarrow {0,1}^{n}is min-preserving(varphi (a wedge b) = varphi (a) wedge varphi (b)fora,b in {0,1}^{k})andepsilon n-error correcting, then the ratek/n rightarrow 0ask rightarrow infty. This result is improved and extended in two directions. begin{enumerate} item For min-preserving codes with {em fixed} maximal (and also average) error probability on a binary symmetric channel againk/n rightarrow 0ask rightarrow infty(strong converses). item Second, codes with lattice properties without reference to computing are studied for their own sake. Already for monotone codes( varphi (a) leq varphi (b)fora leq b)the results in direction 1) hold for maximal errors. end{enumerate} These results provide examples of coding theorems in which entropy plays no role, and they can be reconsidered from the viewpoint of multiuser information theory.     

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.     

Some cross correlation properties for distorted signals

For a nondecreasing distortion characteristicphi(cdot)and a given signalx(cdot), the "cross correlation" function defined byR_{phi} (tau) triangleq int_{-infty}^{infty} phi[x(t)]x(t - tau) dtis shown to satisfy the inequalityR_{phi}(tau) leq R_{phi}(0), for alltau, generalizing an earlier result of Richardson that requiredphi(cdot)to be continuous and strictly increasing. The methods of the paper also show that, under weak conditions, begin{equation} R_{phi,psi}(tau) triangleq int_{-infty}^{infty} phi[x(t)]psi[x(t - tau)] dt leq R_{phi,psi}(0) end{equation} whenpsiis strictly increasing andphiis nondecreasing. In the case of hounded signals (e.g., periodic functions), the appropriate cross correlation function is begin{equation} mathcal{R}_{phi,psi}(tau} triangleq lim_{T rightarrow infty} (2T)^{-l} int_{-T}^T phi[x(t)]psi[x(t - tau)] dt. end{equation} For this case it is shown thatmathcal{R}_{phi,psi} (tau) leq mathcal{R}_{phi,psi}(0)for any nondecreasing (or nonincreasing) distortion functionsphiandpsi. The result is then applied to generalize an inequality on correlation functions for periodic signals due to Prosser. Noise signals are treated and inequalities of a similar nature are obtained for ensemble-average cross correlation functions under suitable hypotheses on the statistical properties of the noise. Inequalities of this type are the basis of a well-known method of estimating the unknown time delay of an observed signal. The extension to nondecreasing discontinuous distortion functions allows the use of hard limiting or quantization to facilitate the cross correlation calculation.     

An upper bound for codes for the noisy two-access binary adder channel (Corresp.)

Using earlier methods a combinatorial upper bound is derived for|C|. cdot |D|, where(C,D)is adelta-decodable code pair for the noisy two-access binary adder channel. Asymptotically, this bound reduces toR_{1}=R_{2} leq frac{3}{2} + elog_{2} e - (frac{1}{2} + e) log_{2} (1 + 2e)= frac{1}{2} - e + H(frac{1}{2} - e) - frac{1}{2}H(2e),wheree = lfloor (delta - 1)/2 rfloor /n, n rightarrow inftyandR_{1}resp.R_{2}is the rate of the codeCresp.D.     

Distribution-free performance bounds for potential function rules

In the discrimination problem the random variabletheta, known to take values in{1, cdots ,M}, is estimated from the random vectorX. All that is known about the joint distribution of(X, theta)is that which can be inferred from a sample(X_{1}, theta_{1}), cdots ,(X_{n}, theta_{n})of sizendrawn from that distribution. A discrimination nde is any procedure which determines a decisionhat{ theta}forthetafromXand(X_{1}, theta_{1}) , cdots , (X_{n}, theta_{n}). For rules which are determined by potential functions it is shown that the mean-square difference between the probability of error for the nde and its deleted estimate is bounded byA/ sqrt{n}whereAis an explicitly given constant depending only onMand the potential function. TheO(n ^{-1/2})behavior is shown to be the best possible for one of the most commonly encountered rules of this type.     

A method for computing addition tables inGF(p^n)(Corresp.)

Conway showed that a table of Zech's logarithms is useful to perform addition in GF(p^{n})when the elements are represented as powers of a primitive element. The Zech's logarithmZ(x)ofxis defined by the equationalpha^{z(x)}=alpha^{x} + 1, wherealphais a primitive element, zero is written asalpha^{ast}, andx=ast,O,1, cdots ,p^{n}-2. A simple algorithm for making a table of Zech's logarithms is presented.     

Partial-optimal piecewise decoding of linear codes

LetAandBbe matrices over a finite fieldGF(q), with same column size n, having linearly independent rows. The problem is to find an optimal estimate of the "information"uB^{T}from the partial "syndrome"vA^{T}, with the conditionuA^{T} = 0, for a transmissionu rightarrow vofn-tuples on aq-ary totally symmetric memoryless channel. The best estimate has the formvB^{T}-f(vA^{T}), wheref(x)is the value ofymaximizing a so-called decision functionDelta (x,y). Explicit expressions are obtained forDelta; they allow computation of the critical probabilities of the channel. The theory is applied to multidimensional orthogonal check set decoding.     

Hypothesis testing with multiterminal data compression

The multiterminal hypothesis testingH: XYagainstH̄: X̄Ȳis considered whereX^{n} (X̄^{n})andY^{n} (Ȳ^{n})are separately encoded at ratesR_{1}andR_{2}, respectively. The problem is to determine the minimumbeta_{n}of the second kind of error probability, under the condition that the first kind of error probabilityalpha_{n} leq epsilonfor a prescribed0 < epsilon < 1. A good lower boundtheta_{L}(R_{1}, R_{2})on the power exponenttheta (R_{1}, R_{2},epsilon)= lim inf_{n rightarrow infty}(-1/n log beta_{n})is given and several interesting properties are revealed. The lower bound is tighter than that of Ahlswede and Csiszár. Furthermore, in the special case of testing against independence, this bound turns out to coincide with that given by them. The main arguments are devoted to the special case withR_{2} = inftycorresponding to full side information forY^{n}(Ȳ^{n}). In particular, the compact solution is established to the complete data compression cases, which are useful in statistics from the practical point of view.     

Representation of stationary Gaussian processes on a finite interval (Corresp.)

A stationary Gaussian processxi_{t}, with a spectral densityfsatisfyingint (log f)(1 + x_{2})^{-1} dx > inftyagrees in a finite interval [- T,T] with a process et which has a purely discrete spectral measure.     

On the inequivalence of generalized Preparata codes

Ifmis odd andsigma /in Aut GF(2^{m})is such thatx rightarrow x^{sigma^{2}-1}is1-1, there is a[2^{m+1}-1,2^{m+l}-2m-2]nonlinear binary codeP(sigma)having minimum distance 5. All the codesP(sigma)have the same distance and weight enumerators as the usual Preparata codes (which rise asP(sigma)whenx^{sigma}=x^{2}). It is shown thatP(sigma)andP(tau)are equivalent if and only iftau=sigma^{pm 1}, andAut P(sigma)is determined.