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.     

Bounds for truncation error in sampling expansions of band-limited signals

Forf(t)a real-valued signal band-limited to- pi r leq omega leq pi r (0 < r < 1)and represented by its Fourier integral, upper bounds are established for the magnitude of the truncation error whenf(t)is approximated at a generic timetby an appropriate selection ofN_{1} + N_{2} + 1terms from its Shannon sampling series expansion, the latter expansion being associated with the full band[-pi, pi]and thus involving samples offtaken at the integer points. Results are presented for two cases: 1) the Fourier transformF(omega)is such that|F(omega)|^{2}is integrable on[-pi, pi r](finite energy case), and 2)|F(omega)|is integrable on[-pi r, pi r]. In case 1) it is shown that the truncation error magnitude is bounded above byg(r, t) cdot sqrt{E} cdot left( frac{1}{N_{1}} + frac{1}{N_{2}} right)whereEdenotes the signal energy andgis independent ofN_{1}, N_{2}and the particular band-limited signal being approximated. Correspondingly, in case 2) the error is bounded above byh(r, t) cdot M cdot left( frac{1}{N_{1}} + frac{1}{N_{2}} right)whereMis the maximum signal amplitude andhis independent ofN_{1}, N_{2}and the signal. These estimates possess the same asymptotic behavior as those exhibited earlier by Yao and Thomas [2], but are derived here using only real variable methods in conjunction with the signal representation. In case 1), the estimate obtained represents a sharpening of the Yao-Thomas bound for values ofrdose to unity.     

Robust prediction of band-limited signals from past samples (Corresp.)

For a complex-valued deterministic signal of finite energy band-limited to the normalized frequency band|w| leq piexplicit coefficients{a_{kn}}are found such that for anyTsatisfying0 < T leq 1/2,left| f(t)-sum^{2n}_{k=1}a_{kn}f(t - kT)right| leq E_{f}cdot beta^{n}whereE_{f}is the signal energy andbeta doteq 0.6863. Thus the estimate off(t)in terms of2npast samples taken at a rate equal to or in excess of twice the Nyquist rate converges uniformly at a geometric rate tof(t)on(- infty , infty). The suboptimal coefficients{a_{kn}}have the desirable property of being pure numbers independent of both the particular band-limited signal and of the selected sampling rate1/T. It is also shown that these same coefficients can be used to estimate the value ofx(t)of a wide-sense stationary random process in terms of past samples.     

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.     

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.     

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.     

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.     

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.     

Correlation of a signal with an amplitude-distorted form of itself

In comparing a signalf(t)with its amplitude-distorted formg(f(t)), whereg(cdot)is a monotonically increasing function of its argument, one is led to consider the correlation function begin{equation} R(s) triangleq int_{-infty}^{infty} dtg (f(t))f(t-s). end{equation} A rigorous proof is given of the inequalityR(s) leq R(O). Generalizations are presented for the cases of finite domains and of signals defined in two-dimensional space.     

Evaluation of the Q Function

A convenient method of evaluating theQfunction over the parameter space quarter plane is presented. TheQfunction is first expressed as an infinite series. TheNterm truncated seriesQ_{N}(a, b)is used to approximateQ(a, b)fora^{2} + b^{2} leq Rwhere the choice ofNdepends on the accuracy desired andRis determined by considerations such as computer bit capacity, computational time, and accuracy. Fora^{2} + b^{2} > R, alternate expressions are used. Whenb - a geq d, we approximateQby 0, and whenb - a leq d, we approximateQby 1. The accuracy is dependent on the choice of the constantd. In the reniainder of the quarter plane,a^{2} + b^{2} > Rand| b - a < d, and an efficient expression is used, but it is of limited accuracy (from 10^-5to 10^-9) near the linea = b.     

Asymptotic properties of delay-time-weighted probability of error (Corresp.)

Asymptotic properties of expected distortion are studied for the delay-time-weighted probability of error distortion measured_n(x,tilde{x}) = n^{-1} sum_{t=0}^{n-1} f(t + n)[l - delta(x_t,tilde{x}_t)],, wherex = (x_0,x_1,cdots,x_{n-1})andtilde{x} = (tilde{x}_0,tilde{x}_1,cdots,tilde{x}_{n-1})are source and reproducing vectors, respectively, anddelta (cdot, cdot)is the Kronecker delta. With reasonable block coding and transmission constraintsx_tis reproduced astilde{x}_twith a delay oft + ntime units. It is shown that if the channel capacity is greater than the source entropyC > H(X), then there exists a sequence of block lengthncodes such thatE[d_n(X,tilde{X})] rigjhtarrow 0asn rightarrow inftyeven iff(t) rightarrow inftyat an exponential rate. However, iff(t)grows at too fast an exponential rate, thenE[d_n(X,tilde{X})] rightarrow inftyasn rightarrow infty. Also, ifC < H(X)andf(t) rightarrow inftythenE[d_n(X,tilde{X})] rightarrow inftyasn rightarrow inftyno matter how slowlyf(t)grows.     

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.     

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.     

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

Writing on dirty paper (Corresp.)

A channel with outputY = X + S + Zis examined, The stateS sim N(0, QI)and the noiseZ sim N(0, NI)are multivariate Gaussian random variables (Iis the identity matrix.). The inputX in R^{n}satisfies the power constraint(l/n) sum_{i=1}^{n}X_{i}^{2} leq P. IfSis unknown to both transmitter and receiver then the capacity isfrac{1}{2} ln (1 + P/( N + Q))nats per channel use. However, if the stateSis known to the encoder, the capacity is shown to beC^{ast} =frac{1}{2} ln (1 + P/N), independent ofQ. This is also the capacity of a standard Gaussian channel with signal-to-noise power ratioP/N. Therefore, the stateSdoes not affect the capacity of the channel, even thoughSis unknown to the receiver. It is shown that the optimal transmitter adapts its signal to the stateSrather than attempting to cancel it.     

Narrow-band systems and Gaussianity

The approach to Gaussianity of the outputy(t)of a narrow-band systemh(t)is investigated. It is assumed that the inputx(t)is ana-dependent process, in the sense that the random variablesx(t)andx(t + u)are independent foru > a. WithF(y)andG(y)the distribution functions ofy(t)and of a suitable normal process, a realistic boundBon the differenceF(y) -- G(y)is determined, and it is shown thatB rightarrow 0as the bandwidthomega_oof the system tends to zero. In the special case of the shot noise process begin{equation} y(t) = sum_i h(t - t_i) end{equation} it is shown that begin{equation} mid F(y) - G(y) mid < (omega_o/lambda) frac{1}{2} end{equation} wherelambda_iis the average density of the Poisson pointst_i.     

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.     

A Gaussian channel with slow fading (Corresp.)

An interleaved fading channel whose state is known to the receiver is analyzed. The reliability functionE(R)is obtained for ratesRin the rangeR_c leq R leq C. The capacity is shown to beC = E_A { frac{1}{2} ln (1 + A^2 n)}whereAis a factor describing the fading mechanism anduis the signal-to-noise ratio per dimension.     

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.