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.     

Alias-free randomly timed sampling of stochastic processes

The notion of alias-free sampling is generalized to apply to random processesx(t)sampled at random timest_n; sampling is said to be alias free relative to a family of spectra if any spectrum of the family can be recovered by a linear operation on the correlation sequence{r(n)}, wherer(n) = E[x(l_{m+n}) overline{x(t_m)}]. The actual sampling timest_nneed not be known to effect recovery of the spectrum ofx(t). Various alternative criteria for verifying alias-free sampling are developed. It is then shown that any spectrum whatsoever can be recovered if{t_n}is a Poisson point process on the positive (or negative) half-axis. A second example of alias-free sampling is provided for spectra on a finite interval by periodic sampling (fort leq t_oort geq t_o) in which samples are randomly independently skipped (expunged), such that the average sampling rate is an arbitrarily small fraction of the Nyquist rate. A third example shows that randomly jittered sampling at the Nyquist rate is alias free. Certain related open questions are discussed. These concern the practical problems involved in estimating a spectrum from imperfectly known{ r(n) }.     

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.     

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.     

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.     

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

Optimization of the finite-element solution of the semiconductor-device Poisson equation

A mesh-optimization technique is applied to the numerical simulation of semiconductor devices. The technique consists of moving the mesh-nodes while keeping their number constant, and is based upon the maximization of a functional related to the RHS of Poisson's equation. The result is equivalent to the minimization of the seminorm ofu - u_{t}, whereuis the normalized electric potential and uTits discretization over meshT. The nodal-coordinate variationsDeltabar{x}induce variationsDeltabar{u}onto the electric potential, yielding a system of algebraic equations where both unknown vectorsDeltabar{x},Deltabar{u}appear. A suitable technique avoids any matrix inversion and allows application of the gradient method for the maximization procedure. The method has been tested on a one-dimensional Poisson solver for bipolar transistors.     

On the weight structure of Reed-Muller codes

The following theorem is proved. Letf(x_1,cdots, x_m)be a binary nonzero polynomial ofmvariables of degreenu. H the number of binarym-tuples(a_1,cdots, a_m)withf(a_1, cdots, a_m)= 1 is less than2^{m-nu+1}, thenfcan be reduced by an invertible affme transformation of its variables to one of the following forms. begin{equation} f = y_1 cdots y_{nu - mu} (y_{nu-mu+1} cdots y_{nu} + y_{nu+1} cdots y_{nu+mu}), end{equation} wherem geq nu+muandnu geq mu geq 3. begin{equation} f = y_1 cdots y_{nu-2}(y_{nu-1} y_{nu} + y_{nu+1} y_{nu+2} + cdots + y_{nu+2mu -3} y_{nu+2mu-2}), end{equation} This theorem completely characterizes the codewords of thenuth-order Reed-Muller code whose weights are less than twice the minimum weight and leads to the weight enumerators for those codewords. These weight formulas are extensions of Berlekamp and Sloane's results.     

Robust Quantization of Discrete-Time Signals with Independent Samples

TheN-level uniform quantizer on[-c,c]plus the assignment ofy_{0}deg = -(a _{s}+ c)/2andy_{N+1}deg = (a_{s}+ c)/2to signal values falling in the saturation regions[-a_{s},- c) and (c,a_{s}], respectively, is shown to be the minimax(N + 2)-level quantizer with a nonsaturating input range[-c,c]. The performance criterion considered is the mean weighted quantization error and the input signals are only required to be amplitude bounded bypm a_{s}wherea_{s} > c > 0. The worst case input signal marginal probability distributions are shown to be discrete. From the derivation of this result, the minimax error can be computed. An example is given which illustrates the performance of the minimax quantizer for several input ranges against different input signal probability distributions.     

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.     

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.     

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     

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

A nonconstructive upper bound on covering radius

Lett(n,k)denote the minimum covering radius of a binary linear(n,k)code. We give a nonconstructive upper bound ont(n,k), which coincides asymptotically with the known lower bound, namelyn^{-1}t(n,nR)=H^{-1}(1-R)+O(n^{-l}log n), whereRis fixed,0, andH^{-1}is the inverse of the binary entropy function.     

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.     

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}     

Harmonic analysis for a class of multiplicative processes

The harmonic analysis of certain multiplicative processes of the formg(t)X(t)is considered, wheregis a deterministic function, and the stochastic processX(t)is of the formX(t)=sum X_{n}l_{[n alpha , (n+l) alpha]}(t), where a is a positive constant and theX_{n}, n=0, pm 1,pm 2, cdotsare independent and identically distributed random variables with zero means and finite variances. In particular, we show that if g is Riemann integrable and periodic, with period incommensurate withalpha, theng(t)X(t)has an autocovariance in the Wiener sense equal to the product of the Wiener autocovariances of its factors,C_{gx} = C_{g}C_{x}. Some important cases are examined where the autocovariance of the multiplicative process exists but cannot be obtained multiplicatively.     

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.