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.     

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.     

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.     

Some results on the minimum weight of primitive BCH codes (Corresp.)

For1 leq i leq m - s- 2and0 leq s leq m -2i, the intersection of the binary BCH code of designed distance2 ^{m-s-1} - 2 ^{m-s-t-1} - 1and length2^m - 1with the shortened(s + 2)th-order Reed-Muller code of length2^m -- 1has codewords of weight2^{m-s-1} - 2^{m-s-t-1} - 1.     

Magnitude and dispersion of Kleinman forbidden nonlinear optical coefficients

Starting with a perturbation expansion for the Kleinman forbidden nonlinear optical coefficientd_{ijk^{F}}and for Miller'sDelta_{ijk^{F}}, and making several approximations, we arrive at a simple result for the ratio of forbidden to allowed mixing nonlinearities (omega_{1} + omega_{2} = omega_{3}), namelyDelta_{ijk^{F}}/Delta_{ijk^{A}} propto (omega_{3}^{2} + 2omega_{1}omega_{2}). For second-harmonic generation (SHG) this can be expressed asDelta_{ijk^{F}}/Delta_{ijk^{A}} simeq (omega/chi)(partialchi/partialomega), which clearly shows the close connection betweenDelta_{ijk^{F}}and the linear dispersion. These expressions are shown to give good agreement with literature experimental values, as well as for our measurements on TeO2for various input frequencies ω1and ω2(i.e.,omega_{3} = 1.88, 2.33, 2.82, 3.50, and 3.76 eV).     

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.     

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 truncation error of the cardinal sampling expansion

Modern communication theory and practice are heavily dependent on the representation of continuous parameter signals by linear combinations, involving a denumerable set of random variables. Among the best known and most useful is the cardinal seriesf_{n} (t) = sum^{+n}_{-n} f(k) frac{sin pi (t - k)}{ pi ( t - k )}for deterministic functions and wide-sense stationary stochastic processes bandlimited to(-pi, pi). When, as invariably occurs in applications, samplesf(k)are available only over a finite period, the resulting finite approximation is subject to a truncation error. For functions which areL_{1}Fourier transforms supported on[-pi + delta, + pi - delta], uniform trunction error bounds of the formO(n^{-1})are known. We prove that analogousO(n^{-1})bounds remain valid without the guard banddeltaand for Fourier-Stieltjes transforms; we require only a bounded variation condition in the vicinity of the endpoints- piand+ piof the basic interval. Our methods depend on a Dirichlet kernel representation forf_{n}(t)and on properties of functions of bounded variation; this contrasts with earlier approaches involving series or complex variable theory. Other integral kernels (such as the Fejer kernel) yield certain weighted truncated cardinal series whose errors can also be bounded. A mean-square trunction error bound is obtained for bandlimited wide-sense stationary stochastic processes. This error estimate requires a guard band, and leads to a uniformO(n^{-2})bound. The approach again employs the Dirichlet kernel and draws heavily on the arguments applied to deterministic functions.     

Bounds on the redundancy of Huffman codes (Corresp.)

New upper bounds on the redundancy of Huffman codes are provided. A bound that for2/9 leq P_{1} leq 0.4is sharper than the bound of Gallager, when the probability of the most likely source letterP_{1}is the only known probability is presented. The improved bound is the tightest possible for1/3 leq P_{1} leq 0.4. Upper bounds are presented on the redundancy of Huffman codes when the extreme probabilitiesP_{1}andP_{N}are known.     

Explicit bounds to R(D) for a binary symmetric Markov source

A new upper houndR_{u}(D)and lower houndR_{ell}(D)are developed for the rate-distortion function of a binary symmetric Markov source with respect to the frequency of error criterion. Both hounds are explicit in the sense that they do not depend on a blocklength parameter. In the intervalD_{c} < D < 1/2 = D_{max}, whereD_{c}is Gray's critical value of distortion,R_{u}(D)is convex downward and possesses the correct value and the correct slope at both endpoints. The new lower boundR_{ell}(D)diverges from the Shannon lower bound at the same value of distortion as does the second-order Wyner-Ziv lower bound. However, it remains strictly positive for allD leq 1/2and therefore eventually rises above all the Wyner-Ziv lower bounds asDapproaches1/2. Some generalizations suggested by the analytical and geometrical techniques employed to deriveR_{u}(D)andR_{ell}(D)are discussed.     

On the quality factor of strip and line source antennas and its relationship to superdirectivity ratio

Exact formulas are derived for the quality factorQof strip and line source antennas. Contrary to popular opinion, none of them is equal to Taylor's superdirectivity ratiogammaor togamma - 1. But in the case ofE-plane strip sources (the complement of the type of strip source treated by Woodward and Lawson) the value ofQis precisely equal togamma_{alpha}^{-1/2}- 1, wheregamma_{alpha}^{beta}is a generalized superdirectivity ratio that reduces to Taylor'sgammawhen the edge exponentalphaand the pattern weighting exponentbetaare both zero. In the case ofH-plane strip sources the value ofQis approximately equal togamma_{alpha}^{1/2} - 1, and forH-plane line sources of vanishing widthait is approximately equal to[(2/pi) ln (2.516lambda/pi a)]gamma_{alpha}^{1}.     

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.     

Bounds for codes over the unit circle

LetCbe a code of lengthnand rateRover the alphabetA(Q)={ exp (2pi ir/Q): r=O,1, cdots ,Q-1}, and letd(C)be the minimum Euclidean distance ofC. For largen, the lower and upper bounds are obtained in parametric form on the achievable pairs(R, delta), wheredelta = d^{2}(C)/nholds. To obtain these bounds, the arguments leading to the Gilbert bound and the Elias bound, respectively, are applied to the alphabetA(Q). ForQ rightarrow infty, they are shown to be expressible in terms of the modified Bessel function of the first kind. The Elias type bound is compared with the Kabatyanskii-Levenshtein (K-L) bound that holds for less restrictive alphabets. It turns out that our upper bound improves the K-L bound fordelta leq 0.93.     

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.     

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.     

Estimating a probability using finite memory

Let{X_{i}}_{i=1}^{infty}be a sequence of independent Bernoulli random variables with probabilitypthatX_{i} = 1and probabilityq=1-pthatX_{i} = 0for alli geq 1. Time-invariant finite-memory (i.e., finite-state) estimation procedures for the parameter p are considered which takeX_{1}, cdotsas an input sequence. In particular, an n-state deterministic estimation procedure is described which can estimate p with mean-square errorO(log n/n)and ann-state probabilistic estimation procedure which can estimatepwith mean-square errorO(1/n). It is proved that theO(1/n)bound is optimal to within a constant factor. In addition, it is shown that linear estimation procedures are just as powerful (up to the measure of mean-square error) as arbitrary estimation procedures. The proofs are based on an analog of the well-known matrix tree theorem that is called the Markov chain tree theorem.     

Further classifications of codes meeting the Griesmer bound (Corresp.)

For any(n, k, d)binary linear code, the Griesmer bound says thatn geq sum_{i=0}^{k-1} lceil d/2^{i} rceil, wherelceil x rceildenotes the smallest integergeq x. We consider codes meeting the Griesmer bound with equality. These codes have parametersleft( s(2^{k} - 1) - sum_{i=1}^{p} (2^{u_{i}} - 1), k, s2^{k-1} - sum_{i=1}^{p} 2^{u_{i} -1} right), wherek > u_{1} > cdots > u_{p} geq 1. We characterize all such codes whenp = 2oru_{i-1}-u_{i} geq 2for2 leq i leq p.     

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}     

On the Schalkwijk-Kailath coding scheme with a peak energy constraint

In a recent series of papers, [2]-[4] Schalkwijk and Kailath have proposed a block coding scheme for transmission over the additive white Gaussian noise channel with one-sided spectral densityN_{0}using a noiseless delayless feedback link. The signals have bandwidthW (W leq infty)and average powerbar{P}. They show how to communicate at ratesR < C = W log (1 + bar{P}/N_{0}W), the channel capacity, with error probabilityP_{e} = exp {-e^{2(C-R)T+o(T)}}(whereTis the coding delay), a "double exponential" decay. In their scheme the signal energy (in aT-second transmission) is a random variable with only its expectation constrained to bebar{P}T. In this paper we consider the effect of imposing a peak energy constraint on the transmitter such that whenever the Schalkwijk-Kailath scheme requires energy exceeding abar{P}T(wherea > 1is a fixed parameter) transmission stops and an error is declared. We show that the error probability is degraded to a "single exponential" formP_{e} = e^{-E(a)T+o(T)}and find the exponentE(a). In the caseW = infty , E(a) = (a - 1)^{2}/4a C. For finiteW, E(a)is given by a more complicated expression.     

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