ALIAS-FREE RANDOMLY TIMED SAMPLING OF STOCHASTIC PROCESSES* by Frederick J. Beutler Information and Control Ehgineering Program The University of Michigan'This study was supported by the National Aeronautics and Space Administration under Research Grant Ns G - 2 - 59.

jM A J 0. ki j >S'a sX ft''

SUMMARY The notion of alias-free sampling is generalized to apply to random processes x(t) sampled at random times t; 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)}, where r(n) = E[x(t +n) X(tm)]. The actual sampling times t need not be known to effect recovery of the spectrum of x(t). Alternative criteria for verifying alias-free sampling are developed. It is then shown that any spectrum can be recovered if {t } is a Poisson point process. A second example of alias-free sampling is provided for spectra on a finite interval by periodic sampling in which samples are independently and randomly skipped (expunged), such that the average 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. Various open questions are discussed. These are related to the practical problem of estimating a spectrum from samples.

I. INTRODUCTION When a wide-sense stationary random process x(t) is sampled at unit intervals, the spectral density s of the sampling sequence {x(t )} consists of the sum of translated replicas of the spectral density S of x(t). This familiar result 00 s(O) - Z S(o - Zirn), -T r -< rr, (1.1) -00 suggests that if S is unrestricted, s includes possible contributions from translates of S having components that intrude onre [-, -r]. The contributions are called aliases; since the aliases are indistinguishable from one another and from S(w), unequivocal determination of S from s is not possible at any frequency w. Suppose, on the other hand, that S is known to be zero outside [-7r, ]. Then the spectral density of {x(tn)} becomes identical with S, so that the spectral density of x(t) is unambiguously and directly determined from that of {x(tn)}. In such a case, sampling is said to be alias-free.1 Uniformly spaced samples, if taken at or above the Nyquist rate (woI/r samples per second for a signal bandwidth wo [11]) are not only alias-free, but also permit error-free recovery of x(t) by a linear combination of the samples. At any lower sampling rate, however, aliasing occurs and errorfree recovery of x(t) is precluded, Thus, the properties of uniform sampling are simple and easily understood. The relationships among alias-free sampling, error-free recovery capability, and average sampling rate are considerably more complex for randomly timed sampling, i. e., sampling at times tn such that {tn} is a discrete parameter random process. For instance, Poisson sampling (independent sampling intervals with identical exponential probability densities) is inherently alias-free for non-bandlimited spectra, even at arbitrarily low sampling rates [14], At the same time, Poisson sampling at less than the Nyquist rate does not permit error-free recovery [1]. Nevertheless, certain More precisely, the sampling is alias-free iff the translates by Zirn (n any integer) of the support of the spectrum of x(t) are all disjoint. See [10]. 1

2 sampling patterns with average sampling rates below the Nyquist rate are consistent with error-free recovery of x(t) [1]; here {X(tn)} need not even be wide-sense stationary, so that nothing meaningful can be said concerning possible implications on aliasing. The tenuous connection between error-free recovery and aliasing is further clouded by requirements on our knowledge of the random tn. For error-free recovery of x(t) from {x(t )} we must always know the precise sampling instants t, while much less is needed for the determination of the spectrum of x(t). If the sampling is alias-free,2 the spectrum of x(t) is uniquely specified as a linear combination of the r(n), where r(n) = E[x(tm+n) (t) (1o 2) Here E denotes the expectation with respect to both x(t) and I{t}, and the overline indicates a complex conjugate. It should be observed that r is deduced from sample values without regard to the (random) times at which the sampling was accomplished; the actual sample times need not be known. Indeed, empirical measurement of the spectrum of x(t) can be based entirely on the sequence of sample values alone. In the next section, we shall define alias-free sampling for random sequences {tn} of a certain type, relative to appropriately chosen families of spectral distribution functions. As in the case of uniformly spaced samp,ling, aliasing occurs if x(t) with different spectra (belonging to ) yield the same correlation sequence {r(n)}. Starting from this definition, we develop several criteria, each of which determines whether {t } is alias-free relative to A. Three examples are studied in detail. The known result that Poisson sampling is alias-free [14] is generalized to apply to arbitrary spectra (over the entire real line) rather than the more limited class of spectral densities belonging to L2. In the next example, we modify uniform sampling by random 2At this point we do not concern ourselves with the exact meaning of "alias free" in this more general context, or with the possible dependence of the right side of (1.2) on m.

3 independent deletion of samples, as may occur with burst jamming or sporadic equipment malfunction. This modification turns out to have the same alias-free property as the uniform sampling from which it was derived. Indeed, the sampling remains alias-free even though the error-free recovery capability is lost when the average sampling rate is only a (small) fraction of the Nyquist rate. The final example treats jittered sampling, in which initially uniformly spaced samples are randomly perturbed. It is concluded that jitter fails to impair the alias-free character of uniform sampling at the Nyquist rate. II. CRITERIA FOR ALIAS-FREE SAMPLING For uniformly spaced sampling, overlapping of spectral densities and ambiguity in the spectral density S of x(t) as determined from the r(n) of (1. 2) coincide. More complex sampling patterns lead to sampling spectra that are not mere replications of S, so that overlapping of replicas is no longer a suitable criterion for determining whether S can be obtained from the r(n). Moreover, the spectrum of {x(tn)} is not easily obtained in terms of S,3 which suggests that the analysis should proceed in other terms. Since the central question in applications is the recoverability of the spectrum of x(t) from r(n), it makes sense to define alias-free sampling by this capability, rather than by any spectral property of {x(tn)}. The definition should, of course, be consistent with the ordinary notion of alias-free sampling when the samples are uniformly spaced. In the latter case, as well as in some involving random {t }, the spectrum of x(t) can be recovered only when it is known to belong to some subclass -of spectra (e. g., spectra whose support is contained in [-Tr, Tr]). It is therefore necessary to specify the family of spectra,; with respect to which the alias-free property holds. Before we give a precise definition to alias-free sampling in a general 3The second-order properties of {x(tn)}, a discrete parameter random process, are quite different from those of Cx(t) 6(t tn), which is a modulation of the signal by a delta function train whose impulses occur at random times tn. The latter, which is often used as a sampling model, leads to spectra calculated in [4] and [9].

4 context, we must introduce certain assumptions and notations. We take x(t) to be a wide-sense stationary real stochastic process possessed of the spectral distribution function G. The process x(t) is sampled at times t, where {tn} constitutes a stationary point process4 (cf. [2] or [3]) independent of x(t). It is supposed that the probability distributions of (t - t ) do not m+n m depend on m; this hypothesis is met by a wide variety of stationary point processes, including those appearing in the examples of the next section. The correlation function of the discrete parameter process {x(t )} is denoted by r(n) = E[x(tm)x(tm ] (2. 1) in which the expectation is taken over both x(t) and {tn}. Under the above hypotheses, {x(tn)} is again wide-sense stationary, so that r depends only on:n. Two random processes- with respective spectra G1 and G2 are said to have different spectra if there exists a continuous function f such that 00 1Sf(w) dH(M) / 0 (2. 2) -00 where H = G1 - Gz. Thus, spectra are regarded as identical iff they differ by at most a constant at all their points of continuity. We then have equivalence classes of spectra among whose class members we do not distinguish. This identification is a natural one, since spectra identical in the above sense correspond to the same correlation function and hence the same {r(n)}. We can now formulate Definition 2. 1: The sampling sequence {tn} is alias-free relative to & (a family of spectra) if no two random processes with different spectra belonging to 2- yield the same correlation sequence {r(n)}. Whether a given {tn} isalias-free relative to is seen to depend on Stationary point processes are characterized as follows: the multivariate distribution of numbers of points in any finite set of intervals is invariant under translation. This definition does not require that the intervals between points be either independent or identically distributed.

5 the relation between G and {r(n)}. The desired expression is obtained from (2.1), in which we may take the expectation successively with respect to x(t) and {t } because of the independence of the two processes. The expectation on x(t) is most conveniently written in terms of its spectral representation, viz. 00oo E[x(tmn X(t) ]1 {exp[io(t -t dG(o) (2.3) x2 —w m+n - 2m+n m If the expectation on {t } is now applied to (2. 3), integration with respect to dG and the probability measure on {t } can be interchanged because G is a finite measure and exp[iw(t - t )] is bounded. There results m+n m 00 r(n) = 2 f*(iw) dG(w) (2 4) for the relationship between G and {r(n)}. The f*' appearing in (2. 4) are well n known in the theory of stationary point processes ([3], Section VII), and have been calculated for a number of the more interesting and important random point processes. By definition f (ic) = Eexp[-iW(t+ -t)} ei dF (u) (2.5) -00 in which Fnis the probability distribution function for n successive sampling intervals (cf. [3], Sections VI and VII). Note that the difference in sign of the exponential in (2.3) and (2. 5) is irrelevant because of the character of G for a real stochastic process. For each possible set of {t } statistics, the mapping G - {r(n)} is a linear bounded transformation. An inverse exists in the sense that G can be inferred from {r(n)} iff this transformation is one-one. Thus, Definition 2.1 identifies the spectral recovery capability with the alias -free property. There is complete consistency with uniformly spaced sampling (unit period),

6 since tn~i - t =1 implies f*(iw) e, so that the closure of trigonometric ~n+1 n n polynomials implies the uniqueness of the (Fourier-coefficients) r(n) if the support of G is, contained in (-Trr, Tr). The alias-free property of Definition 2. 1 can be rephrased slightly as follows. Let b be the family of measures induced by functions H of the form H = G1 - Gz2, where G1 and G2 are any spectra belonging to 4. In particular, the null measure is in %, and we have Theorem 2. 1: The sampling sequence {t } is alias-free relative to 4 iff with H E 00.S fn(iw) dH(w) = 0 for all n implies H = 0.(2 6) -0D The alias-free criterion of Theorem 2. 1 above is of particular interest because - is a Banach space in most applications. As one possibility, -;4 may consist of all spectra supported on an interval I (which might be the entire real axis); then e becomes the Banach space of functions of bounded variation constant on the complement of I. Now C(I), the space of continuous functions defined on I and equipped with the usual sup norm, is the dual of this?. Further, f* E C(I) for each n. Hence, (2. 6) is satisfied in this case iff {fI} is closed in C(1) (cf. [5], Chapter XI). Alternatively, J4 could be the class of absolutely continuous spectra supported on I, with derivatives S E L (I), 1 _ p < oo. Then (2.6) is satisfied P if each f E L(I), whe q - 1 this follows because Lq(I) is the Banach space dual of Lp(I). More generally, we have Corollary 2. 1: Let o be a Banach space with dual', and assume that each f* E. Then {tn} is alias-free relative to 4-iff {f is closed in Since closure and completeness are equivalent in a Banach space (cf. [5], Chapter XI), we may rephrase Corollary 2. 1 to read: 5A more restrictive version of (2. 6) was obtained under less general conditions by Shapiro and Silverman [4].

7 Corollary 2.2: Under the hypotheses of Corollary 2. 1, {t } is alias-free with respect to A iff every g C i can be approximated as closely as desired (in Cha norm) by finite linear combinations of the f*. n We use Corollary 2, 2 to show again that alias-free sampling allows recovery of G by linear combinations of the r(n). We take only the case where,- is the class of all spectra, so that alias-free sampling requires that any continuous function; can be uniformly approximated by linear combinations of f* Now let n <,)0 g(o) = (2o7) N v. Then there is a bounded sequence c kNf' that converges to g everywhere except at wH. If 0 is a continuity point of G, there follows N N 00 lim CO cnNr(n)} lim n(i)dG() - g(w)dG(=). ) 00 -00 (2. 8) Similar arguments are applicable to other Banach spaces, and in particular to the L (I) mentioned earlier. The final result of this section is yet another criterion for alias-free sampling. We assume this time that t - t has a probability density f n+m m n A substitution of (2. 5) in (2. 6), followed by' an application of Fubinil s theorem, yields Corollary 2.3: Let D be the difference of two correlation functions corresponding to spectra belonging to 4. Then {t } is alias-free relative to 4 iff Efn(u) D(u)du = 0 for all n implies D = 0, (2o9) 0 Use will be made of (2. 9) in proving that Poisson sampling is alias free for all spectra.

8 III. EXAMPLES OF ALIAS-FREE SAMPLING Spectra possibly occupying the entire real axis cannot be constructed from {r(n)} when {tn} represents uniformly spaced samples, even at arbitrarily high sampling rates. Nevertheless, alias-free sampling is possible when the average sampling rate is as small as desired, assuming that the structure of {tn} is "sufficiently random, " i.e., if {tn} is a Poisson point process. For random processes with spectral densities belonging to L2, this result was discovered by Shapiro and Silverman [14], For our first example, we give another proof of this alias -free property; our verification shows that the sampling is actually alias-free for all spectra. In a Poisson sampling sequence {tn}, the numbers of points in disjoint intervals are mutually independent. The probability that there are n samples in any interval of length x is p(n, x) =(x)ne- X/nt (3. 1) from which f (x) -(5x) e /(n- 1)! (3. 2) n as is shown in Section 4. 1 of [2]. In (3. 1) and (3. 2) above the parameter 13 represents the average number of samples per unit time. It will be shown that Poisson sampling is alias-free relative to the class of all spectra for any a > o. Corollary 2. 3 will be applied to show that Poisson sampling is aliasfree relative to the family of all spectra. Each D (in the notation of the corollary) is an even uniformlyrcontinuous bounded function for this family. We then define V(t) = D(t)e 2 tu(t), (3.3) where U is the unit step function. Now V E L2(0,'o), as is gn(t) = P(t)n ei ZPtu(t)/(n-)!.1 (3.4) Furthermore, the gn are Laguerre polynomials (modulo irrelevant multiplicative constants), and

9 f (t) D(t) = gn(t) V(t) (3. 5) for each n = 0, 1, 2,... Thus the sampling sequence is alias-free if 00 Sgn(t) V(t)dt = 0 for n = 0,1, 2,.. implies D = 0; (3. 6) 0 this follows from (2. 9). To demonstrate (3. 6), we use the fact that the Laguerre polynomials are closed in Lz(0, oo). This means that V(t) = 0 almost everywhere in [0, oo) whenever the integral in (3. 6) is zero for every n. But if V(t) is zero almost everywhere in [0, co), so is D(t). Finally, the symmetry and continuity of D require that D is identically zero. In the remaining two examples, we examine variants of uniform sampling. For convenience and without loss of generality we assume unity spacing of samples prior to modification of the sampling train. As has been noted earlier, such uniformly spaced samples permit alias-free sampling relative to spectral densities belonging to L (-n, Tr), p > 1. If the larger class of all ('possibly non-absolutely continuous) spectra on, an interval is to be considered, we must take the (slightly) smaller interval [-rr, rT -a], a > 0, in order to maintain the alias-free property. It would be expected that timing errors or missing samples would restrict such an interval further, or possibly preclude alias-free sampling entirely, but this is not the case. In fact, the alias-free property remains exactly as it was for uniform sampling, even though the timing anomalies are known only in a statistical sense. We study first uniform sampling-that has been subjected to random skipping or deletion of samples. It is supposed that each sample has probability q of being lost, and that these skips occur independently. The average rate of sampling is then reduced to 1 - q per period, which is below the Nyquist rate. Nevertheless, the alias-free property is the same as that of uniform (unit period) sampling for any q < 1. It has been shown elsewhere (see [3]9 equation 7.16) that

10 fG(ik) = [(1 -q)e wI/(l qe-i)) ]n n = 0,1, 2,.. (3.7) n for the sampling sequence in question. To prove that skip sampling is aliasfree relative to all spectra supported on; -rr, r - a] we utilize Corollary 2. 2. That is, we show that any continuous function on [-wr, rr - a] can be uniformly approximated by linear combinations of the {fn}. But, since it is already known that {e }, k = 0, 1, +1 +2,.... is closed in C(-ir, rr - a) (cf. [15], p. 414), we need only demonstrate that {fi} can approximate uniformly any one of the e on this interval. For this purpose, replace the family {f)t by an equivalent family {hn}. If h (z) = (z q) = n 0 1, 2,9 (3. 8) each h coincides up to a constant with the corresponding f' on the curve E n - n described by z = e - or = =X The approximation problem has now been reduced to the following: On E, approximate uniformly to z (any integer k) by linear combinations h. n To show that these rational functions h can indeed effect the desired approxin mation, we take D to be a domain (in the complex plane) containing E but excluding both the origin. and q, and such that the complement of the closure of k. D is connected, Now each z is regular in D, and can be uniformly approximated on E by rational functions having their only pole at q, i. e., by the h The asserted approximation by these rationals is an immediate consequence of Runge's theorem ([13], p. 174-1.77)o This completes the verification for the second example. The final example concerns jittered sampling, in which each sampling time is randomly perturbed:from a uniformly spaced position. These random perturbations modify the sampling sequence so that none of the t is pren cisely known. In spite of these random sampling errors, however, the sampling sequence remains alias free respective to all spectra supported on [-Tr, r - a], a >0. In other words, the introduction of jitter entails no deterioration of alias-free cha acteristics as; compared with the original uniform

11 sampling. Further, successful recovery of the spectrum of x(t) requires knowledge only of the jitter statistics, and not of the jitter component on any of the t n We assume that jitter translates the n'th sampling point by an amount u, and that the u are pairwise independent and identically distributed. Then {it} is a stationary point process with t - t n +(u -ur ); (3.9) n+m m n+m m this implies f0' = 1 and fn{2 -iwn fn(iw) = ( iw) i e n = +1, + 2,..., (3.1 0) in which y denotes the characteristic function of any un (compare [3], equation 7.18). In order that the sampling indices not be permuted from the uniformly spaced (unperturbed) samples, u can be distributed only over some unit interval. But also, any stationary point process can be translated as desired without changing its interval statistics. We may therefore suppose that - -< u < l with probability one. The latter hypothesis assures the y(iw) is bounded away from zero on [-ur, Tr]. Since y is continuous, we need only show that y(iw) 1 0 for w 1 _ Tr. For this purpose, we observe that the real part of y is 1 Re [y(iw)] = cos (wx) dF(x) (3. 11 2 where F is the probability distribution function for un. But cos (wx) O0 for iowi < _r and Ix[ < 2, with equality at I 0 = rr, x = -i, Then Re[y(iw)]> 0 for w E- [-Tr, nr] unless F has (only) a unit jump at x = -4. In the latter case, however, Jy(iw) = 1 for- all 0. Hence the result is as claimed. Corollary 2.2 will be used to demonstrate that the jitter process {tn} is alias free relative to all spectra with support in [-iT, w - ac] If h E C( -in, n), there must exist coefficients anN such that h is uniformly approached on [-Tr, ir - a] by the partial surns anN f'. Now the approximation error is -II\J "~Jn n ~

12 bounded at o by 1 N -2 Iy(iw)l L a Ne X- _[h(w) -aN] y(iw)J I (3o12) -N N/o We choose (for all N) Tr f h/() I y (i@) - r do a -N (3.13) aoN +wT f Iy(io)2-dw -Wi and let anN be the coefficient of e of the NYth partial Cesaro mean for the Fourier expansion Lbke of the function [h(a) - aON ] (icj. But s inc e bo = 0 (because of our choice of a N) the sum appearing in (3.1 2) is actually the Cesaro mean for the (continuous) function [h(w) - aN] iJy(ik)|z. The conoN vergence property of Cesaro means ([7], p. 18) then insures that the expression (3.1 2) approaches zero uniformly onfl[-Tr, wi -o] as N approaches infinity. It can also be shown that if h E L (-rr, rr), q > 1, the convergence of (3.1 2) to zero holds in L (-n, T). Thus, if if is the class of spectra which are absolutely continuous with derivatives belonging to L (-rr, r), p > 1, then the jittered sampling is alias-free relative to JO Likewise, the skip sampling of the last example is alias-free relative to the same class. IV. CONCLUDING REMARKS Although it has been possible to deduce some results related to the recovery of the spectrum of a random process from samples taken at random times, much remains unknown. In particular, there are explicit properties applicable to uniformly spaced samples for which there is no random sampling counterpart. Suppose, for instance, that an x(t) with spectrum supported on [i-r, ir - a] is sampled at the Nyquist rate. The spectrum can then be recovered from {r(n)} through the Cesaro means derived from the (formal) Fourier series Cr(n)e (cf. [7], pp. 17-20). The analogous formula for the (more general) case of random sampling is given by (2. 8), but practical means of determining the C N are lacking. Hence, a constructive method

13 for obtaining the spectrum remains to be found. Of interest from a more theoretical viewpoint is the characterization of {r(n)} in terms of {f } and s. Conversely, given a class of {r(n)} and an {fn}, what is the corresponding family ~? For spectra supported on [-Tr, Tr] and sampling at the Nyquist rate, it is known that there is a Fourier transform relation between all non-negative definite sequences { rn)} and these spectra (cf. [12], pp. 116-118). More general sampling sequences lead only to the (obvious) result that {r(n)} must be non-negative definite. Again, Nyquist rate sampling yields inferences on 4 from the behavior in L (-iTr, rT), 1 p <oo (see [ 7], p. 23), of the Cesaro means of Zr(n)e, whereas such conditions need not be significant with random sampling. Since {r(n)} must be obtained from the samples themselves, each term is subject to random error in any practical scheme utilizing only a finite number of samples. Not even an estimate of r(n) will be available for those indices which exceed the number of samples used. The accuracy with which the spectrum can be obtained is therefore affected by the influence variation in {r(n)} has on our estimate of the spectrum. This sensitivity to errors in { r(n)} is again unknown, but we may conjecture that when the sampling is at less than the Nyquist rate the calculated spectrum varies discontinuously with changes in the r(n) 6 Although we have no analytical basis for this conjecture, a recent result of Landau [8] is suggestive; he asserts an analogous property pertaining to error-free recovery of x(t) from samples taken at less than the Nyquist rate (cf. [1]). 6In other words, the linear transformation taking {r(n)} into the spectrum is an unbounded transformation.

14 REFERENCES 1. Beutler, F. J., "Error-free recovery of signals from irregularly spaced samples, " SIAM Rev,, 8 (1966), 328-335. 2. Beutler, F. J. and Leneman, O. A., "The theory of stationary point processes," Acta Math., 116 (1966), 159-197. 3. Beutler, F. J. and Leneman, O.A., "Random sampling of random processes: stationary point processes, " Information, and Control, 9 (1966), 325-346. 4. Beutler, F. J. and Leneman, O.A., "The spectral analysis of impulse processes," to be published. 5. Davis, P. J., Interpolation and Approximation, Blaisdell, New York, 1963. 6. Doob, J. L., Stochastic Processes, Wiley, New York, 1952. 7. Hoffman, K., Banach Spaces of Analytic Functions, Prentice-Hall, Englewood Cliffs, N.J., 1962. 8. Landau, H. J., "Sampling, data transmission, and the Nyquist rate," to be published. 9. Leneman, O.A.,o "Random sampling of random processes: impulse sampling," Information and Control, 9 (1966), 347-363. 10. Lloyd, S. P., "A sampling theorem for stationary (wide sense) stochastic processes," Trans. Amer. Math. Soc., 92 (1959), 1-12. 11. Nyquist, H., "Certain topics in telegraph transmission theory, " Trans. Amer. Inst. Elec. Engrs., 47 (1928), 617-644. 12. Riesz, F. and Nagy, B. Sz., Functional Analysis, trans. by L. Boron, Ungar, New York, 1955. 13. Saks, S. and Zygmund, A., Analytic Functions, trans. by E. Scott, Monografie Matematyc zne, Warsaw, 1952. 14. Shapiro, H- S. andSilverman, Siveran R.A., "Alias-free sampling of random noise,"J. Soc. Indus. Appl. Math., 8 (1960), 225-248. 15. Titchmarch, E.C., Theory of Functions, 2nd ed., Oxford Univ. Press, London, 1939.

UNIVERSITY OF MICHIGAN 3 90111 02229 326311111 11111111111 11111111111 11111 11 3 9015 02229 3263