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.     

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

Performance of anM-ary orthogonal communication system using stationary stochastic signals

This paper considers the performance of a communication system which transmits forTseconds the real part of a sample function of one ofMstationary complex Gaussian processes whose spectral densities are all frequency translations of the functionS_{xi (f). At the receiver white Gaussian noise of one-sided densityN_{0}is added. The center frequencies of the processes are assumed to be sufficiently separated that theMcovariance functions are orthogonal overT. Exponently tight bounds are obtained for the error probability of the maximum likelihood receiver. It is shown that the error probability approaches zero exponentially withTfor all ratesR = (ln M)/Tup toC= int_{-infty}^{infty} [S_{xi (f)/N_{0}] df - int_{- infty}^{infty} ln [1 + S_{xi}(f)/N_{0}] dfwhich is shown to be the channel capacity. Similar results are obtained for the case of stochastic signals with specular components.     

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.     

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

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.     

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.     

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.     

Two methods to deconvolve: L1-method using simplex algorithm and L2-method using least squares and parameter

Ifr(t)is the linear scattering response of an object to an excitation waveforme(t), thenr(t) = (e ast h) (t). One would like to deconvolve and solve forh(t), the impulse response. It is well-known that this is often an ill-conditioned problem. Two methods are discussed. The first method replaces the discretized matrix formE cdot H = Rby the following problem. Minimize|h_{1}|+ ldots + |h_{n}|subject toR - lambda leq E cdot H leq R + lambdawherelambdais a column vector chosen sufficiently small to yield acceptable residuals, yet large enough to make the problem well-conditioned. This problem is converted to a linear programming problem so that the simplex algorithm can be used. The second method is to minimizeparallel E cdot H - R parallel^{2} +lambda parallel H parallel^{2}where againlambdais chosen small enough to yield acceptable residuals and large enough to make the problem well-conditioned. The method will be demonstrated with a Hilbert matrix inversion problem, and also by the deconvolution of the impulse response of a simple target from measured data.     

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.     

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.     

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.     

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.     

Some integrals involving theQ_Mfunction (Corresp.)

Some integrals are presented that can be expressed in terms of theQ_Mfunction, which is defined as begin{equation} Q_M(a,b) = int_b^{infty} dx x(x/a)^{M-1} exp (- frac{x^2 + a^2}{2}) I_{M-1}(ax), end{equation} whereI_{M-1}is the modified Bessel function of orderM-1. Some integrals of theQ_Mfunction are also evaluated.     

Estimation of a quadrature cross- correlation detector by analog, polarity-coincidence, and relay methods (Corresp.)

The variance of the output of a cross-correlation detector, which is called a quadrature cross-correlation detector, is estimated. In this type of detector two zero-mean Gaussian quadrature processesalpha(t)andbeta(t)of a complex process(alpha(t) -j beta(t))are cross correlated. This cross-correlation functionR_{A} (tau)is estimated when neither of the two processes is distorted (the analog method), when both processes are distorted by a signum function before being cross correlated (the polarity coincidence method), and when one of the two processes is distorted by either a signum function or by a "comparator logic" function (the relay method). These quadrature cross-correlation detectors then are compared on the basis of output signal-to-noise ratio (s/n) and the clipping and relay losses are computed for two test quadrature processes of an Edgeworth-expansion-approximated power spectrum. SinceR_{A} (0)is zero, the four corresponding differential estimators, such as(R_{A} (tau) - R_{A} (0))are also estimated and are compared on the basis of s/n. For these differential estimators, the clipping and relay losses are computed for the two test processes. In all cases the exact expressions for the s/n are derived as a function oftau. Some applications of these correlation detectors are outlined. The mathematical techniques employed here are thought to have potential usefulness for related problems in statistical communication theory and signal processing.     

Complexity-based induction systems: Comparisons and convergence theorems

In 1964 the author proposed as an explication of {em a priori} probability the probability measure induced on output strings by a universal Turing machine with unidirectional output tape and a randomly coded unidirectional input tape. Levin has shown that iftilde{P}'_{M}(x)is an unnormalized form of this measure, andP(x)is any computable probability measure on strings,x, thentilde{P}'_{M}geqCP(x)whereCis a constant independent ofx. The corresponding result for the normalized form of this measure,P'_{M}, is directly derivable from Willis' probability measures on nonuniversal machines. If the conditional probabilities ofP'_{M}are used to approximate those ofP, then the expected value of the total squared error in these conditional probabilities is bounded by-(1/2) ln C. With this error criterion, and when used as the basis of a universal gambling scheme,P'_{M}is superior to Cover's measurebast. WhenHastequiv -log_{2} P'_{M}is used to define the entropy of a rmite sequence, the equationHast(x,y)= Hast(x)+H^{ast}_{x}(y)holds exactly, in contrast to Chaitin's entropy definition, which has a nonvanishing error term in this equation.     

On the detection of known binary signals in Gaussian noise of exponential covariance

The optimum test statistic for the detection of binary sure signals in stationary Gaussian noise takes a particularly simple form, that of a correlation integral, when the solution, denoted byq(t), of a given integral equation is well behaved(L_{2}). For the case of a rational noise spectrum, a solution of the integral equation can always be obtained if delta functions are admitted. However, it cannot be argued that the test statistic obtained by formally correlating the receiver input with aq(t)which is notL_{2}is optimum. In this paper, a rigorous derivation of the optimum test statistic for the case of exponentially correlated Gaussian noiseR(tau) = sigma^{2} e^{-alpha|tau|}is obtained. It is proved that for the correlation integral solution to yield the optimum test statistic whenq(t)is notL_{2}, it is sufficient that the binary signals have continuous third derivatives. Consideration is then given to the case where a, the bandwidth parameter of the exponentially correlated noise, is described statistically. The test statistic which is optimum in the Neyman-Pearson sense is formulated. Except for the fact that the receiver employsalpha_{infty}(which in general depends on the observed sample function) in place ofalpha, the operations of the optimum detector are unchanged by the uncertainty inalpha. It is then shown that almost all sample functions can be used to yield a perfect estimate ofalpha. Using this estimate ofalpha, a test statistic equivalent to the Neyman-Pearson statistic is obtained.     

Power-Bandwidth Performance of Smoothed Phase Modulation Codes

Constant envelope phase varying sinusoids of the formsqrt{2E/T} cos(omega_{c}t + phi(t))are studied, in which the phase functionphi(t)follows some coded pattern in response to data. Power and bandwidth performance are studied for such patterns. The patterns depend on a phase shaping function, a modulation index (h), and a sequence ofM-ary underlying changes in phase which are chosen at random. A cutoff rate-like parameter R0is computed, which guarantees existence of codes at all ratesR < R_{0}bits/T-interval whose error performance varies as exp[-N(R_{0} - R)], whereNis the code word length inT-intervals. Plots of R0are given as a function of interval energyE, the shaping functionhandM. Extensive spectral calculations give the spectra of these phased sinusoids, and their performance is plotted in the power-bandwidth plane. The results give strong evidence that phase codes can approximate any power-bandwidth combination consistent with Shannon's Gaussian channel capacity, and that linear channels are not required for narrow-band transmission.