RECOVERY OF RANDOMLY SAMPLED SIGNALS BY SIMPLE INTERPOLATORS by Frederick J.n\\eutler Professor of Information and Control Engineering Computer, Information and Control Engineering Program The University of Michigan January 1973 Research sponsored by the Air Force Office of Scientific Research, AFSC, USAF, under Grant No. AFOSR-70-1920B, and the National Science Foundation under Grant No. GK-20385.

",7 4.. ",I I a -:7, -, -,

ABSTRACT The mean square error performance of simple polynomial interpolators is analyzed for wide-sense stationary signals subjected to randomly timed sampling represented by stationary point processes. This performance is expressed in dimensionless parametric terms, with emphasis on asymptotic error behavior at high dimensionless sampling rates y. The form of the asymptotic error expression, and particularly its dependence on y, is shown to vary according to the number of points utilized, together with the differentiability properties of the signal. One -2 point extrapolation yields a mean square error varying with y if the signal is differentiable, and as y' if the signal is not. Similarly, two-4t -3 point (polygonal) interpolation error exhibits linearity in y, y or -2 y, according as the signal is twice, exactly once, or non-differentiable. Specific examples are offered to furnish insight into actual error magnitudes. It is shown, for instance, that introduction of jitter in the sampling sequence increases the error by only a negligible amount. Exponential decay of the sample values is compared with stepwise holding; little is gained for a non-differentiable signal, while for a differentiable signal -2 -1 the error performance deteriorates from y to y at high sampling rates. When more than two points are used in a polynomial fitting recovery scheme, specific computations or error become excessively difficult. However, it is proved that the asymptotic mean square error varies with -2n y when n points are utilized, and the signal is continuously differentiable at least n times. Finally, we compare the mean square errors of one and two sample schemes as described above with those attained by causal (extrapolating) and non- causal (interpolating) Wiener-Kolmogorov optimal filters. We demonstrate non-trivial instances in which the Wiener-Kolmnogorov mean square error varies as y, so that any of the simple recovery schemes considered exhibits superior performance at high sampling rates. This is explained by noting that the latter represent time-varying filters, whereas the Wiener-Kolmogorov filter is time-invariant.

I. INTRODUCTION Practical recovery of a signal from its samples has concerned. engineers for several decades, as Shannon's famous paper [23] amply demonstrates. Originally, periodic sampling was routinely assumed. It was soon realized, however, that a stochastic model of the sampling sequence {tn} more realistically reflects timing errors (jitter) [1] [9], lost samples (skipping), time-shared computer operation, and the like. It is indeed tempting to approach reconstitution of the signal x(t) through highly sophisticated optimization techniques. For instance, if x(t) is wide sense stationary and independent of (stationary) {t }, one can sometimes (see [9] [14]) apply the Wiener-Kolmogorov technique to the sampled signal y(t) by regarding it as a delta function train y(t) = x(t)s(t) = x(t )(t-t ): (1. 1 -0e n n thus, one minimizes the mean square recovery error ~ =E{[x(t)-_(t)] }.1 In this work, we consider instead, simple interpolators based, on only a small number of samples, following [13][16][17]. It is our contention that such an interpolator is often preferable to a WienerKolmogorov (or Kalman-Bucy) filter. Our preference follows from a number of considerations, namely: 1. The optimum is often difficult or impossible to compute. 2. Its implementation can be complicated. 1 This optimization, as applied to generalized random processes, is rigorously treated in [11] and [22].

3. Unless the statistics of x(t) and {t ) are well known, a Wiener or Kalman-Bucy filter cannot be obtained,. Even then, its effectiveness is seriously denigrated by noise and/or imperfect knowledge of the relevant statistics. On the other hand, simple interpolators are robust. 4. A simple interpolator depends neither on the remote past (as does the Wiener filter) nor on initial time varying computation and implementation (as does the Kalman-Bucy filter); it operates immediately and without start-up transient whenever the data becomes available. Lastly-and most surprisingly —the simple interpolator often exhibits performance superior to a comparable Wiener filter. This apparent paradox (which the author first observed by a direct calculation) is readily explained.. A time invariant filter is perforce based only on the statistics of the sampling train {t ) only, whereas even a simple sample-and-hold interpolator represents a time-varying weighting function [acting linearly on x(t)] predicated on the actual realization of the sampling instants t n [see (1.3)]. It is seen that simple interpolators are well worthy of attention. At the same time, our understanding of the performance of such interpolators (when used in connection with non-periodic sampling) is quite limited. Answers do not now exist to any of the following: 1. For typical sampling schemes and random signals, what mean square error performance is achieved by various simple interpolators?

2. Can the error be expressed. parametrically to show the extent of dependence on factors such as sampling rates, number of points employed, irregularity of sampling times, etc.? 3. What is the mean square interpolatory error as compared with that attained by a Wiener-Kolmogorov filter (causal or non- causal)? 4. How is the error affected, in form and magnitude by the characteristics of the signal, as expressed by its "smoothness" or degree of differentiability? Although our results do not dispose of the above questions completely we are able to make considerable progress with them. To do so, we limit ourselves to wide-sense stationary signals x(t) stochastically independent of the sampling process {t }. Our {t } is only subject to the weak hypothesis that {t } is a stationary point process (hereafter abbreviated s. p. p. ) [8][7], which imposes merely the requirement that any joint probability distribution of numbers of points in intervals be invariant under time axis translations. The class of s. p. p. thus embraces a wide variety of sampling schemes, including those most likely to appear in practice (see [8] and [7] for examples which include jitter, skips, Poisson, etc. ). Properties of s. p. p. are well understood [5][6], so that the analytical tools for investigating interpolation errors are at hand. Finally, the stationarity properties of {t }) in combination with those of x(t), result in wide-sense stationary {x(tn)); then, unless the interpolation scheme is explicitly time dependent, the interpolated process x(t) is wide-sense stationary also. Throughout our work, the measure of interpolator performance will be the

mean square error I2 = E{[x-(t)] }. For convenience, we take x(t) real, and to standardize our results, we shall always suppose E {[x/t)]2} 1. We begin with the simplest possible interpolator, the sample-andhold scheme shown in'Figure 1, and described. by the output xf(t) = x(t) for t < t <t (1. 2) n n- n+l' Each x(t ) is thus held. until the arrival of the next sample at time tn+1' at which instant the current x(t) is "dumped," and replaced by a new value x(t ) While the sample-and-hold interpolator corresponds to the time n+l varying weighting function 00 h(t,u) = [(u-tn-)- U(u-tn+)] [U(t-t) - U(t-tn+l)] (1.3) -00 n n n n+l it is actually easy to mechanize as a hardware device, and, its performance can readily be calculated without reference to (1. 3). A variation of the above method, designated exponential interpolation, is shown in Figure 2; it differs from sample-and-hold only in the exponential weighting of the sample value used. In other words, -b(t-t A(t) = e n x(t) for t < t <t (1. 4) ~n n — n+l' where b > 0 is chosen as desired. On strictly intuitive grounds, it could. be argued, that the exponential sampling of (1. 4) is preferable to (1. 2), since exponential sampling is superior at low sampling rates. In fact, Here U(. ) is the unit step function.

if the autocorrelation of R (T) -( 0 as T -- o Lalways true if x(t) has an abX 2 solutely continuous spectral distribution function], we have ~ -* 2 as the sampling rate tends toward zero with sample-and-hold. recovery, whereas 2 E -' 1 for exponential interpolation. At high sampling rates, however, the relative ranking of these two interpolation schemes is reversed. for all differentiable signals. This becomes clear once exponential interpolation is analyzed in conjunction with sample-and-hold interpolation by calculating errors respective to (1. 4) with arbitrary b > 0, that is, by regarding sample-and-hold as a special or limiting case of exponential interpolation. On each interval [tn, tn+l), sample-and-hold recovery is recognized as polynomial interpolation (see [10], p. 24) with n=l. The same type of interpolation, but with n=2, connects successive samples with straight'line segments as shown in Figure 3. We refer to the interpolatory method of Figure 3 as polygonal interpolation. When the sampling times are random, computation of mean square errors becomes quite difficult; this becomes evident when we see that recurrence times (i. e., time intervals from t to the nearest sampling instant) are present in both numerator and denominator of a quotient, and. that joint statistics of forward and, backward recurrence times are required. Nonetheless, we have been able to determine the mean square error for some special cases, and to formulate parametric relations on error behavior. The latter lend themselves naturally to comparisons with non-causal WienerKolmogorov filtering, since the usual polygonal interpolator is itself non-causal. It will be observed that the simple interpolator exhibits

better performance at high sampling rates, even though its delay requirements are small, in contrast to the infinite delay postulated for the noncausal Wiener-Kolmogorov filter. We also consider both causal and non-causal polynomial interpolators of arbitrary degree at high sampling rates. Exact mean square error expressions then become insuperably difficult to calculate, and, in any case, lead to such complicated expressions that insight is inevitably lost. Athigh sampling rates, however, simple parametric relationships are obtained, and easy mean square error bounds established. It should be noted that the emphasis on high sampling rate results is not a serious restriction. Indeed, any meaningful application of sampled signal recovery requires that the error be small relative to the signal magnitude, and, this in turn demands high sampling rates. The notion of sampling rate is made more precise in the next section, in which some of the other implication of asymptotic error analysis at high sampling rates will also be discussed. II. NOTATION AND BACKGROUND Since the material of this paper leans heavily on properties of s. p. p. it is convenient to summarize the notation and, background to be used; the interested reader will find. further results and the applicable derivations in [5] and [6]. Fundamental is the notion of recurrence time Lk(t), which is the time interval between t and the k'th sampling point occurring thereafter. If k is a negative integer, Lk(t) denotes the interval length between the k'th point preceding t and t itself. The distribution function of Lk(t)

does not depend on t (by virtue of the stationarity of {tn}), and i's known to be absolutely continuous; hence, a statistical description of Lk(t) is furnished by the probability density function gk( ), which is zero for negative argument. A particularly prominent role is played by gl, which turns out to be the density of the distance to the nearest sampling point in either direction. Moreover, gl is a monotone function for which g1(0+) = fl, where f3 is defined to be the mean number of sampling points per unit time. It is sometimes convenient as well as natural to operate in the frequency domain, for which purpose one introduces the transform -Su g'(s) = g (u)e du E{exp[-sLk(t)]} (2. 1) 0 It can be shown that g*k is related to the conditional distribution Fk for Lk(t), given that a sampling point occurs at t; if f* is the LaplaceStieltjes transform of Fk, we have (see [6]) g (s) -= /s [f* (s) - f(s)] (2.2) If the intervals are independent and identically distributed, Fk becomes the (unconditioned) distribution of k successive intervals. Of greatest interest are the recovery capabilities of interpolation schemes at relatively high sampling rates. To justify this claim, it would suffice to remark that the mean square error (i. e., error power) should be small compared to the signal power in any practical situation, and that this is true only at high sampling rates. However, there are additional reasons for concentrating on high sampling rates. For one

thing, the mean square error expressions tend to be quite complex, so that comparison among sampling schemes, signals, and interpolators is awkward. The asymptotic (high sampling rate) formulas are nmuch simpler, so that a direct parametric understanding of factors affecting error becomes possible. Finally, one can often find universal error formulations related to moments of x(t) and {t }, independently of the form of the autocorrelation or other statistics. Insofar as possible, we shall present our results in nondimensionally normalized form. For instance, our notion of sampling rate is the nondimensional ratio y =,' in which j3 is the mean number of samples per unit time (as previously defined), and W is some consistent bandwidth measure for x(t). One possible choice of W is W = inf S (w)dw (2. 3) A -A) S being the spectral density of x(t). The mean square error will then be given in terms of the (normalized) sampling rate y, together with some statistical parameters of the unit bandwidth process x(Wt) = x(t) and the unit rate sampling sequence {tn} defined by t = At. In this fashion, it is n n n possible to isolate the effect of sampling rate on the error, as distinct from variations in x(t) and {t } unrelated to frequency content. If the requisite moments and the n'th derivative [of x(t) in quadratic mean] exist, the separation is obtained from relations such as E{[xn(t)] } = wnmE{xn(0)]m} (2. 4) m. We assume throughout for convenience only that the spectral distribution function of x(t) is absolutely continuous.

10 and E{IL k(t)lm) = mE{[Lk(O)]Jm. (. 5) Elementary calculations also yield gk(u) - (IgOk(fiu), g:(s) = g *(S) S () W S (W w) and R (T) = R-(WT); here we have consistently used the tilde to refer to statistics of the normalized processes, and have denoted correlations by R with appropriate subscript. Although some of our results hold for any s. p. p. satisfying E{[L1(0)]2} <oo, it is frequently desirable and necessary to turn to explicit forms, chosen on the basis of analytic tractability as well as practical applicability. One of these is the so-called skip-jitter sampling process, which can be viewed as idealized periodic sampling (period T) modified by equipment and environmental conditions. One supposes that points are deleted independently, each with deletion probability q. In addition, the remaining sample points are randomly perturbed; jitter displacements uk are mutually independent, and may be statistically described by the generating function4 C(s) = E[exp(-suk)]. (2.6) With the above notation, we obtain for the skip jitter process -sT] -sTn f*(s) = C(s)C(-s)[l-q)e sTn/[iqe- (2.7) n as shown in [6], eq. (7.20). Of course, the skip jitter process can be specialized if desired by setting either q=0 or C(s) = 1. For comparison, it is of interest to consider the'Lmost random" (i. e., largest entropy4The jitter cannot be so large that indices of sampling points are permuted. It follows that the uk must be distributed over an interval whose length cannot exceed T, and which (by the stationarity of {t }) can be taken as [0, T).

11 see [21]) s. p. p., namely the well-known Poisson point process. For this s. p. p. gl(u) = /3eu and g* (s) f*(s) ] (2. 8) which corresponds to,the classical formulas of renewal theory. One process x(t) whose interpolation is analyzed in considerable detail is the wide sense Markov process, whose correlation is necessarily of the form (see [3], Theorem 3) R ((T) = exp(-a T ). (2. 9) There are several reasons why this stochastic process should be of special interest to us. Aside from its mathematical simplicity, we note that the correlation is not differentiable at the origin, so that x(t) is non-differentiable in quadratic mean. Thus, the wide sense Markov process is suitable to the study of interpolation for non-differentiable processes. Furthermore, it is known that the minimum mean square causal estimator for the process is [2j x(t) = x(t-L l(t))exp[-aL (t)] (2. 10) with resulting mean square error C2 = 1 -g*(2a) (2. 11) for any s. p. p. sampling process whatsoever. Lastly, the interpolation error for any x(t) with rational spectral density having distinct poles is readily found once the error corresponding to (2. 9) is known. This follows because the mean square error is linear in R, so that a solution for (2. 9) extends immediately to x(t) possessing correlations of the form

12 Rx(T) - Ak[exp(-a TI )]. (2. 12) III. EXPONENTIAL AND SAMPLE-AND-HOLD INTERPOLATION In this section, we obtain and compare the mean square errors incurred when the recovery is based, on the single sample value which immediately precedes the present time t. We consider in particular interpolators whose output is x(t) = x(t-L l(t))exp[-bL (t) (3. 1) for some b > 0, as in (1. 2) and (1. 4). Because the statistics of {t } appear only in a simple form within (3. 1), the mean square error corresponding to the x(t) of (3. 1) is relatively easy to evalute. For interpolators or estimators of general type, the mean square error can always be written as 2 At 2 (3.t2) = 1 - 2E[x(t)x(t)] + E{[x(t)] (3. 2) where x(t) and. (t) are assumed to be of finite mean square, with x(t) normalized so that E{x(t)] } = 1. Since x(t) and {t } are supposed statistically independent, expectations involving x(t) can be calculated when desired by applying successively these expectations in the more convenient order. We thus have E[x(t)9(t)] = E{R rL l(t)]exp[-bL l(t- R (u)e (u)du (3 3) 0 x gl (u)d and (by an even simpler computation)

13 E[Q(ot) 3 = E{[x(t)] )}Eexp[-2bL l(t)] (3. 4) -e 2bug(u)du = g (2b) 0 From the three foregoing equations, it is seen that the mean square error pertinent to the exponential interpolator is 2 f -bu -u (3u) [1-R (u)e +e gl(u)du (3. 5) 0 for arbitrary x(t) and {t}). The expression (3. 5) is especially simple for a wide sense Markov signal. Example 3. 1: (wide sense Markov signal-arbitrary sampling statistics) On substituting in (3. 5), we find that 2 = 1 - 2g (a+b) + g 1(2b) (3. 6) If W is defined as in (2. 3), we have W = a. We also let a = b, so that the error takes on the dimensionless form 2 -1 +y-1 -1 = 1 - 2gg*(y +ay) + g(2y (3.7) At high sampling rates, y becomes large, and since (see Section II) a=1 minimizes the mean square error, we may suppose a (the normalized exponential decay) not large. Then we may take advantage of the small arguments of gj to derive a high sampling rate approximation to (3. 7). In fact, the assumed existence of the second moment of Ll(t) implies (see [20], p. 199) that g' (Z) = 1-zE[L1(0)] + ~zZE{[L1(O)J} + o(z2) (3. 8)

14 where o(z )/z — 0 as z — 0 by definition. With the substitution (3. 8), (3.7) becomes 2 1Y22 2) 2 2 E = -y E[L (0)]+ y [a -2a-l]E{[L1(O)j} + o(y ). (3.9) The significance of (3. 9) is discussed later, when a comparable expression for differentiable signals is available. To this end, we first derive an alternative frequency domain version of (3.5). One of the terms needed is already given by (3. 4). The other follows from (3. 3) by writing R as an inverse Fourier transform of S, and then (since gl and S are both x x integrable) applying Fubini's theorem. The final result, stated in dimensionless parameters, is 2=-1 1 1 -1 (3) 1 g I1 + ~* (2ay -j SN(w)g (ay -i(y )dw. (3. 10) We use (3. 10) in Example 3. 2: (differentiable signal-high sampling rates) If'1 in (3. 10) is put in series form (3. 8), there follows 2 = Y E[L1(0)]2} (a + E{[x(0)]}) + o(y (3.11) We conclude that the mean square error always varies as the inverse square of the sampling rate when the signal is differentiable; this is clearly more desirable than the variation with y encountered for the wide sense Markov signal. We further conjecture-but have been unable -1 to prove-that the error behaves as y for any non-differentiable signal. Exponential interpolation is undesirable in conjunction with a differentiable signal x(t); as (3. 11) indicates, the mean square error increases directly with the decay rate squared. On the other hand, the

15 error (3. 9) applicable to the wide sense Markov signal is quite insensitive to the decay rate a even at moderate sampling rates y Both error behavior with y and effect of decay are readily explained by the manner in which R drops off near the origin. If x(t) is differentiable, R (0) = 0, and so x(t) is more highly correlated with x(t) than for the non-differentiable (wide sense Markov) signal. This leads to smaller interpolation A errors for differentiable signals, and also suggests that decay in x(t) emphasizes its deviation from x(t) whenever R departs only a little from x unity during a sampling interval. Our next object of investigation is the finfluence of jitter on the mean square error. A limited approach is through (3. 9) or (3. 11), in which one observes the change in E[L1(0)] or E4,1(0)]2}, respectively, as the sampling point locations are modified by independent identically distributed perturbations. Example 3. 3: (wide sense Markov signal-jittered periodic sampling) The interval lengths in this instance are T+u -u 1' where the uk are the jitter variables. Then if Q( ) is the (common) distribution function of u -u1' we have gl(u) = T [1-Q(u-T)] by the relation of F1 to gl o00 (see [5], eq. (3.4. 1)). One then computes E{[L1(0)m } - o u gl(u)du. We shall assume in particular that each uk is uniformly distributed over the interval [O,vT), whence it follows that 2 1' 1 V E[L1(0)] =2 12 (3. 12) the mean square error (3.9) is therefore 2 = y[+ ]+o(y-2 Although jitter augments the error, the increase is negligibly small;

16 if each sampling point is allowed to deviate by as much as a'quarter of the sampling interval (i. e., v = ), there is an increase of but one percent in the error. The sanme reasoning is pertinent to differentiable signals, for which we have Example 3. 4: (differentiable signal-jittered periodic sampling) 2 We proceed as in Example 3.3, and obtain E{ L(O0)]} + 6 The latter yields a high sampling rate approximation 2 1 -2 v 2 2 2 =Y (1 + 2)(2 + E{[ (0)])+ o(y2 ). (3. 13) If the sampling points are perturbed in a uniform distribution extending (as in Example 3. 3) over a quarter of the sampling interval, the error increase is three percent-still a small amount, especially in view of the relatively large sampling time deviation. The small influence of jitter can be explained intuitively by observing that L l(t) is unchanged, on the average, but since there is a symmetrical occurrence of smaller and. larger occurrence times since the most recent sample, the mean square weighting generates a second order error effect. Jitter may be imposed on sampling processes other than the periodic. It is seen from (3.7) and (3. 10) that the change in g* resulting from the jitter translates into its influence on the mean square error. Consequently, general approximation formulas can be derived if the variation in g* can be related to the jitter. Let us call f* the interval characteristic funcol tion [see (2. 2)] prior to the imposition of jitter, and take C(- ) the jitter characteristic function as defined by (2. 6). Then f*(s) = C(s)C(-s)f* (s) (3. 14) 1 ol

17 and from the connection (2. 2) between f and g 1-C(s)C(-s) g*(s) = g*(s) -g* (s) sg (s)- 1] (3. 15) ~~1 1 ol s ol In nondimensional form, (3. 15) can be expanded in the series Lsg4(s) ='-so- + +o(s2) (3. 16) 2 in which ar is the variance of the normalized jitter variable Ofu. Example 3. 5: (wide sense Markov signal —arbitrary jitter statistics) The mean square error increase consequent to the introduction of jitter is determined for moderate or larger sampling rates by substituting (3. 16) into the general mean square error formula (3. 7). Upon performing the indicated operations, one sees that 2 2 -1 2 -2 2 -2 2_ 2cr y + 2r Y (a 2a-1) + o( )(3. 17) 2 Evidently, jitter enlarges the error by the ratio vr /E[L1(0)) for high sampling rates. Although we have been unable to find an a priori bound for this ratio, the requirement that the jitters not permute sampling points suggests that 1/4 is not exceeded. As we have seen in Examples 3. 3 and 3. 4, even large jitters do not come close to this figure under plausible conditions. The techniques of Example 3. 5 are equally suitable to a determination of error increase for differentiable signals when jitter is imposed on the sampling sequence. Example 3. 6: (differentiable signal-arbitrary jitter statistics) We put (3. 16) into (3. 10), observing that some terms cancel, while others assume the form f wSx (C)dwo = O. There remains x

18 2 = 2r2 ( + E{[(0)} + o(y ). (3. 18) In this instance, the mean square error augmentation ratio is 2o- /E[L (0)] }, which is again likely to be small in practical applications. Skipping of samples is yet another phenomenon which may be encountered in practice as a result of sampler malfunction, jamming, fading or other environmental causes. Like jitter, skipping exacts a performance penalty intuitively connected with irregularity of sampling intervals. For simplicity, we consider only periodic sampling subjected to independent deletions, each sample being omitted with probability q. The fl for this case is then given by (2. 7) with C(s) = 1, and mL1 m+l m = (-1) (3nd (3. 19) E{[L1(O)J } = f (s) (3. 19) n+l +ls d.s s=O where /3 = -. We are therefore led to the high sampling rates results of T Example 3. 7: (periodic sampling with independent random skips) Because E[LI(O) = -2(l+q)j3, substitution in (3. 9) for the wide sense Markov signal yields 2 -1 2 = y (l+q)+o(( ) (3. 20) The procedure is entirely analogous for differentiable signals; taking m=2 in (3. 19) and putting E{[L1(0)]2} into (3. 11) gives 2 1-2 2f2 2 2 3 y (1+4q+q) a + E{[x(0)]}) + o(y ) (3. 21) The error increase engendered by the skipping is connected with the consequent irregularity of the sampling, and is expressed by the factors

19 (l+q) and (1+4q+q ) in (3. 20) and (3. 21), respectively. Of course, if T is held constant in face of increasing skipping probability q, the sampling rate y decreases, thus leading to a larger error also. It is worth noting that the sampling tends to a Poisson process if we let q-*l while taking T 0 such that the ratio -i remains undisturbed; we could use this T fact to calculate mean square errors attendant to Poisson sampling, but find it as easy to proceed directly. We next compare the mean square error of exponential interpolation with that achieved by causal Wiener-Kolmogorov filtering. Unfortunately, the comparison is severely limited by difficulties in the factorization which is a crucial aspect. of the Wiener procedure. Nonetheless, our results strongly suggest the conjecture that the exponential interpolator gains in relative performance as the sampling sequence becomes more rand om. Our discussion is of necessity confined to wide sense Markov signals. For these, the exponential interpolator (with a=l) is optimal (among all linear causal filters) with respect to any sampling sequence [2]. When the sampling sequence is periodic, the exponential interpolator and Wiener filter coincide. But if random skipping (see preceding example) is introduced, the corresponding Wiener filter possesses infi5 nite memory [14]; since its output must then differ from the optimum 5In this instance, the Wiener filter and its mean square error depend implicitly on q, T and a through the solution of a quadratic equation. We have therefore been unable to obtain a high sampling rate approximation to the mean square error.

20 (exponential) interpolator-see [2]), the causal Wiener filter must generate a larger mean square error. An explicit comparison is feasible for Poisson sampling, which can be regarded as'rnost random" among all sampling schemes when judged on the basis of entropy [21]. Example 3. 8: (wide sense Markov signal-Poisson sampling) The exact mean square error formula is immediate from (2. 8) and. (3. 7), viz. 2 l+a 1_ E ={ 2 11 - (3. 22) 1+2ay 1 +ay + The asymptotic error form is computed either from (3. 22), or by using E[L1(0)] = 1 in (3. 9), whence 2 = z2y +.(y. ) (3. 23) This represents a definite improvement over Wiener filtering, for which ([14], equation 2. 43) we have the asymptotic error relation 2 -1 2 = y-2 + 0(y ) (3. 24) Further quantitative comparisons between Wiener filters and simple interpolators will appear in the next section. There, the fair comparison is with non-causal time invariant mean square optimal filters. Since the latter are calculable without the need for spectral factorization, we will be able to obtain a greater number of results for reference.

21 IV. POLYGONAL INTERPOLATION The interpolatory methods presented thus far utilize only the last sample preceding time t to produce x(t). Use of a greater number of samples in linear combination should decrease the interpolation error; this is expected in analogy with the non-random interpolation of functions (see, for instance, [10], p. 56 ff. ). There we recognize sample-andhold interpolation as zeroeth order polynomial interpolation, while polygonal interpolation is identified with interpolation by polynomials of order one. It follows that the sample-and-hold error should depend inversely on the interval length, while the error of polygonal interpolation is inverse to the square of this length. Moreover, the error for the latter becomes much smaller (by a constant multiplicative factor) when one sample is to each side of time t than when both samples lie in the past. Motivated by the above considerations, we now analyze polygonal interpolation; it will be of particular interest to note whether the behavior of the mean square error is consistent with the arguments of the preceding paragraph. To this end, consider the interpolation scheme illustrated by Figure 3. We see that \(t) lies on the straight line joining the samples x(tn) and x(tn+l ) the index n being such that t <t < t + Evidently, this interpolation method is non-causal, although the delay is likely to be small at high sampling rates. An analytical expression for Q(t) can be developed in terms of the forward recurrence time Ll(t) and backward recurrence time L l(t); the contributions of x(tn) and X(tn+1) are in linear combination that depends on these recurrence times. More specifically, we have for x(t)

22 L lx(t+L1) + Llx(t-L 1) x(t) = (4. 1) L +L 1 -1 in which we have suppressed the arguments of Ll(t) and L l(t). Calculation of the mean square error ~2 from (3. 2) requires a knowledge of E{[A(t)] } and E[x(t)~(t)], where x(t) is given by (4. 1) above. We cannot in general hope to obtain these expectations without the joint probability distribution of L1 and L 1' since these appear in nonlinear combination in the expression for the square of the error. Even when the appropriate integrands are available, the (L1+L 1) term in the denominator of (4. 1) usually leads to integrals that cannot be evaluated in closed form. In view of these problems, few direct results are explicitly obtainable. It is advantageous to use the symmetry of R to write (L )Rx(L )+ (L)R (L A 1 1 x -1 E[x(t)x(t)] = E{ L + L (4.2) L1 +-L1 and to put E4I(t)]2} in the form 2 2 (LL) ++2(L L )Rx(L +L E{j[(t)]2) = E{ -2 (4. 3) (L1 + L1) We can then obtain a fairly general error formula, namely Example 4. 1: (twice differentiable signal-high sampling rates) Let us call G(,. ) the joint distribution function of L1 and L 1' and assume the existence of the joint second moments of the recurrence times, voz. EL1(t)L(t) = f u v dG(u,v). (4.4) 0

23 The mean square error, as furnished by (3. 2), now appears as a double (t)A ffA 2 integral with respect to G, with E[x(t)](t)] and EJx(t) }) given by (4. 2) and (4. 3), respectively. Because x(t) is supposed twice differentiable, R may be e:panded as in [20], p. 199. If the integral is written in dimensionless form using the sampling rate y, we find that C2 I —4 (45 = 4y 4E{[(t)] )E4L-(t)L (t)] + o( ). (4. 5) If G(',.) is too difficult to find, one may modify (4. 5) by utilizing the upper bound E L (t) l (t)]2) < EL1 (t)]4 } (4. 6) the latter follows from the Schwarz inequality and the fact that L1 and L 1 both have the same probability distribution (see [14]). It is noteworthy that the mean square error varies with the sampling -4 rates according to y. This behavior, together with that of once differentiable signals under sample-and-hold interpolation, is entirely consistent with the classical results on polynomial interpolation (see again [10]). While it would be desirable to compare the mean square error expression (4. 5) with the corresponding error for Wiener-Kolmogorov filtering, nontrivial computations oh the latter appear to pose insuperable difficulties. As we have observed earlier, the polygonal interpolator of Example 4. 1 is non-causal. However, this fact is irrelevant to the fashion in which the mean square error varies with the sampling rate y. To further demonstrate this fact, and to observe the influence of causality, we borrow a result from the next section for

24 Example 4. 2: (twice differentiable signal-causal polygonal extrapolator at high sampling rates) We suppose here that x(t) is the linear extrapolation of the two sample values immediately preceding t, i. e. x(t-L 1) - x(t-L 2) x(t) = x(t-L_ 1) + { - 2 }(t-L1) Then it may be shown that 2 14 2 2 -4 -~ = 4Ex(0)] }E{[L l(t)L 2(t)]} + o(y (4. 8) it is clear that the only difference between the errors of the non-causal and, causal interpolators lies in the mean square distance between t and the sampling instants. For purposes of comparison, it is of interest to find also the form and error magnitude associated with optimum two point interpolation. That is, we take x(t) = a(t)x(t-L_1) + b(t)x(t+L 1)' (4. 9) choosing a and b to minimize the mean square interpolation error. Applying the orthogonality principle, one easily shows Rx (L )-R (L1)Rx(L 1+L1 ) a(t) =, (4. 10) 1 -[Rx(L + L_ and that (by symmetry) b is precisely like a, but with L1 and L 1 interchanged. The mean square error for this (optimal) a and b is calculated asymptotically at high sampling rates by substituting (4. 9) into 2 = 1 - E[x(t)x(t)] with optimal values of a and b entered therein. Although the formal computation is routine, as are the simpler ones leading

25 to mean square errors (4. 5) and (4. 8), rigorous justification of the results prove more complicated in all these cases. The problems arise relative to the truncated Maclaurin expansion of R. since the latter is expressed in series form prior to taking the expectation with respect to {t }; it must then be shown that the remainder term leads only to a con{tn tribution of o(y ) in the final expression. The denominator term of (4. 10) necessitates particularly delicate analysis, since the manner in which it tends toward zero with L1 + L 1 is crucial. Under mild. assumptions (i. e., the ekistence of the sixth moment of L1), one shows the total integrand with respect to the probability distribution G(', ~) well behaved, and. indeed admitting an asymptotic expansion whose leading term has -4 y as its multiplicand. We shall omit the rigorous verification of this assertion, and only note that the final result is (Ex (t) - (Ex (t)] E{[L(t)L (t)] } + o(y (4. 11) Thus, there is some reduction in mean square error, but no fundamental difference in error behavior with sampling rate y, or with the sampling scheme [ reflected only by the last term on the right of (4. 11)]. Since a and b must be'individually computed for every t, it seems questionable whether the additional complexity of the two point optimization is warranted.. To secure a better feeling for the comparative performance of the two point interpolators discussed above, we shall compute their respective mean square errors under similar conditions. To this end, let us assume Poisson sampling of a band-limited white signal.

Example 4. 3: (band-limited white signal with Poisson sampling-comparison of two-point reconstruction of signal) It is only necessary to substitute in the expressions already derived. Straightforward calculations yield 2 16'. 2 16 6 E{[x (t)]} 16 (Ex (t)j }) 166 (4. 12) E{[Ll(t)L l(t)]z} 4 and E{L l(t)L 2 (t)] = 40. For the (non-causal) polygonal interpolator, we then have 2 16 -4 2 16 - (4. 13) whereas the causal polygonal extrapolator yields ten times this figure, or 2. -4 2 = 32y. (4. 14) As is expected, the smallest mean square error is associated with the optimal two-point interpolator; it is 2 64 -4 ~ 45Y (4. 15) We again call attention to the similarity of the error forms, and that the dependence on sampling rate is the same for all. Indeed, differences in signal or sampling characteristics, as well as the choice of two-point reconstruction method;, is reflected only in a fixed numerical multiplier. The superiority of the simple two-point interpolator over a WienerKolmogorov non-causal filter becomes evident when we calculate the mean 6In this example, our notion of bandwidth is furnished by the half power frequency, i.e. by (2.3).

27 square error for the latter under comparable conditions. We again assume Poisson sampling of band-limited white signal. The technique (standard in any case) suggested in [14] is applied to the spectral densities obtained from [7], equations (3. 7) and (4. 6). The mean square optimal time invariant interpolator then yields mean square error 2 =- yl + 0(y~2), 7 (4. 16) -4 which compares unfavorably with the variation with y of any of the two point interpolators mentioned in Example 4. 3. Nor is the behavior of the Wiener-Kolmogorov interpolator merely a special case relevant only to Poisson sampling. For instance, we could assume periodic sampling subject to skips (deletion of samples) each occurring independently with probability q; the latter model leads to a mean square error expression 2 2q -1 -1 (4. 17) ~ = Qy +o (y ) (4. 17) It is our belief that the y leading term is typical of Wiener-Kolmogorov interpolation of a differentiable signal. Of course, a regular sampling pattern at a high sampling rate leads to error-free recovery, so that this statement is applicable only if some degree of randomness is present in the sampling train. We have been unable to answer to our satisfaction the nature of the p o i p i r w xi c f n l fa-1 The exact error formula is e = -y [1 +]

28 introduce (4. 2) and (4. 3) into the general error expression (3. 2) and exyuE'x t)2 2 pand R as R (u) 1 - E}x](t)] ) + o(u ), we see that all the terms canX X 2 cel mutually except the last; hence we are left with 2 o(-2) (4. 18) Approximation techniques are also useless in attempting to derive asymptotic error expressions for non-differentiable signals. Fortunately, it has been possible to evaluate the error in certain special cases (e. g., wide-sense Markov signals). Here one is generally able to determine the exact mean square expression, from which the asymptotic form is then obtained. Example 4. 4:; (wide sense Markov signal with independent skip samplingpolygonal interpolation) We return to (4. 2) and (4. 3), which enable us to compute the desired mean square error. In order to deal with the denominators comprised of powers of L1+L 1' we apply the total probability law E(Z) = ZE(Z C )P(C ) n n where {Cn) constitutes a partition of the probability space. In this instance, we take C, as the event that time t falls in a sampling interval of length nT, where T is the nominal distance between successive (unskipped) samples. We then have Cn = {L +L = nT}. and as may readily be verified P(C) = nqnl(l -q)2 (4. 19) under the earlier assumption of independent skips each having probability q. The conditional density of L1, given C, is

29 (nT)-I 0 <u <nT gl(ul C) (4. 20) n 0 otherwise. With this information one computes for later use in the total probability formula E{[(t)]2C } = 2 + R (nT)] (4. 21) which holds generally for any Rx. On specializing (4. 21) by assigning R (T) = exp(-al T I), multiplying by P(C ), and summing one obtains X n E{A(t)]2} = {2 + 1 - )(aT)+ o(aT). (4. 22) The same technique, applied to the computation of E[x(t)S(t)], yields the closed form expression E[x(t)a(t)] T2 q -=q 1 - log( l)- (4. 23) aT 2 (aT4 -q An expansion of the logarithm [whose argument is written 1+ (l-e) l-e for this purpose] leads to a high sampling rate approximation to E[Xx(t)(t)] identical to the right side of (4. 22). The estimates of E{JB(t)j } and E[x(t)l(t)], valid for high sampling rates y = are entered into the =a a 2 2~xtAAtt] A 1{1o-.4 general mean square error formula 1 = l-2E[x(t) (t) +E{2(t)] }, thus giving -2 =(a3 l+)) (4. 24) The above error invites comparison with the corresponding error associated with use of onlyone sampling point [see (3. 20)]. Although the mean square error is reduced by a factor of three by interpolation between two sampling points relative to sample-and-hold extrapolation, its

30 dependence on the sampling rate through y remains unchanged. The benefits of employing a second sampling point are therefore relatively small, and are even further minimized if a two-point (causal) extrapolator is considered in place of the interpolator of the present example. It is noteworthy that the error for twice differentiable x(t) with a -4 polygonal recovery scheme varies as y, whereas the variation is with -i y for the non-differentiable signal just considered. We also showed. -2 by (3. 18) that the mean square error behaved as o(y ) when the signal is (at least) once differentiable. It therefore appears that signal differentiability is a vital error consideration at high sampling rates. This is again seen from the next example, in which we are also able to make error comparisons with Wiener-Kolmogorov non-causal filtering. Example 4. 5: (Poisson sampling of a wide-sense Markov signalpolygonal interpolation) Because L1 and L 1 are statistically independent, each having exponential density with parameter 3, one can find the joint probability density of L +L and L to be 1 -1 32u 0 <v <u h(u, v) = (4. 25) 0 otherwise. Knowledge of this joint density permits us to determine E[x(t)x(t)] by noting that (4. 2) consists of two terms having the same expectation, so that

31 o0 (u-v)R (v) E[x(t)w(t)] = Z f j h(u, v)dtudv. (4. 2() 0 We integrate first on v, taking advantage of the exponential form of R; X the second integral can then be treated as a Laplace transform whose transform variable is /. The final result is E[x(t)Ax(t)] = 2y{l- ylog(l+y )}. (4. 27) By proceeding in similar fashion we also obtain EIAx(t)J} = -2 -1 )2 (4. 28) 3 - 1 2) (l+Y where the nondimensional sampling rate y =-a as before. Although the mean square error is directly available from (4. 27) and. (4. 28.) above, the effect of y on error behavior is not transparent. However, the asymptotic expression resulting from expansion of the logarithm in (4. 27) and. the denominator in (4. 28) takes on the relatively simple form 2 2 -1 8 -3 o(-3,z- 15y + ) (4.30) -3 Here we have deliberately carried the y term, which will prove useful in the next example. For the non-differentiable signal x(t) considered above, the error -1 is linear in y, as it was in the preceding example likewise concerned with polygonal interpolation of a non-differentiable x(t). While the error magnitude is not as responsive to sampling rate as for a twice differentiable signal, the performance (4. 30) is nevertheless superior to that achieved by a noncausal Wiener-Kolmogorov interpolator. It has been shown elsewhere (equation 2. 37 of [14], that for the latter

32 2 1 E2 = y 2 + o(y 2), (4. 31) which is clearly worse than the mean square error (4. 30) applicable to the polygonal interpolator depending on only one point to each side of it. It is also instructive to observe the relation between sampling rate and mean square error when the signal is exactly once differentiable; as -4 we have seen, this error varies as y for a signal which is twice differentiable, and as y (in Examples 4. 4 and 4. 5) if the signal cannot be differentiated. Since general results in this direction seem to be beyond our grasp, we must again rely on a convenient example. Example 4..6: (Poisson sampling of once differentiable signalpolygonal interpolation) Although we are unable to treat once differentiable signals of general type, we can use the results of the preceding example to handle any signal of rational spectral density having distinct real poles. The correlation R of such a signal can be written n Rx(T) = Ak exp(-akr ) (4. 32) whose coefficients must satisfy Ak =1 and, EAkak= 0 (4. 33) because E{[x(t)] } = 1 and the derivative of R at the origin exists and is x zero by the assumed differentiability (in quadratic mean) of x(t). More3 over, Akak < 0, with equality iff x(t) is twice differentiable. Let us now compute the mean square error for an R furnished by x (4. 32). Now the mean square recovery error is linear in R, so that the formula (4. 30) can be applied term-by-term to (4. 32). For notational

33 brevity, call the right side of (4. 30) ~ (y). Take y =, where j is the Poisson rate as before, and a is any consistent measure of signal bandwidth (e. g., the half power frequency). The linearity property, as applied to the mean square error, then yields 2 Ak EA 2 (j ) ) (4. 34) ak in which bk= By virtue of the second equality in (4. 33) and the def-. k a inition of ~ (1) from (4. 30), the y terms sum to zero, and there remains 8 3, -3A.3 -- = [ A bkjy3 + o(). (4. 35) We have thus shown that for this (large) class of precisely once differ-3 entiable signals the mean square error varies according to y. The same qualitative behavior may be demonstrated for once differentiable signals whose spectral density has multiple poles, and. for the skip sampling considered earlier in different connections. By way of comparison, we again recall that the error relevant to -4 twice differentiable signals varied with y, while that of non-differentiable signals behaved like y. Wiener-Kolmogorov non-causal filtering of a non-differentiable signal yielded the still worse figure y 2. It is also worth noting that utilization of two interpolation points (in place of one) improves the mean square error behavior from y to y 3 for a once -2 -4 differentiable signal, from y to y for a twice differentiable signal, and leavesthe factor y unchanged if the signal is not differentiable at all.

34 V. GENERAL POLYNOMIAL INTERPOLATI ON The interpolation and extrapolation schemes studied in the preceding two sections repre sent classical Lagrange polynomial interpolation. ([ 10], Section 2. 5) of degree zero and one, respectively. The computational difficulties experienced there discourages direct mean square error calculations for polynomials of higher degree fitted to larger numbers of sample points. Thus, there seems no way to readily determine the asymptotic mean square error incurred by interpolating an m times differentiable signal by a polynomial of degree n-l passed through n sample points when m< n-l and n > 3. However, we can and do derive an error expression of polynomial interpolation valid for m > n and n arbitrary. The formula obtained will hold for causal as well as non-causal estimators; -Zn in either case, the mean square error varies as y Our starting point is the expression for the Cauchy remainder ([10], Section 3. 1) indicative of the difference between an n times differentiable function f and the n-1 degree polynomial Pn1 passed through the points f(tk), k=l, 2,..., n; we have if(t) w Pnitl n! 1I t-t k (5. 1) in which the indicated n'th derivative is to be taken at some (unspecified time s, t1 < s <t. We assume here that the sampling points tl < tZ < < t, without requiring that t falls within the interval [tl1 tn] marked by the sampling time extremes tl and t. In fact, t > t or t < t < t n n 1 —n according as we consider (causal) extrapolation or (non-causal) interpolation.

35 The error formula (5. 1) applies ipso facto to randomly timed sampling of an n times differentiable stochastic signal x(t). We nowhave t-tkl = L.j, where jl...., represent the combination of indices appropriate to the recovery scheme contemplated; all indices are negative for extrapolation, whereas interpolation leads to some positive and some negative indices. Once the substitution by the L. is accomplished, one Jk is tempted to square (5. 1) [with f replaced by x], and to take the resulting expectation in order to find the mean square error. But unfortunately, one cannot claim that n_ zn n E{fx (s)]Zn [L (t)] } = E{x(o) IH [L (0)] }, (5. 2) k k since in general the s on the left side of (5. 2) depends not only on x(t), but also on t }. 8 We must therefore resort to a different technique n which avoids the dependence problem, although its validity is limited to asymptotically large sampling rates y. It is possible to majorize the error (5. 1) by replacing fn(s) with sup [fn(s)]. Correspondingly, we may write in terms of the nont <s <t 1- - n dimensional processes introduced in Section II 2n2 2 [n,.n 2n ~ 2 y 6 < (n') E{sup[x (u)] II[L (t)] (5. 3) where * indicates that the supremum is to be taken over the interval It is not even obvious —although it can be shown-that s is measurable on the product space generated by the stochastic processes x(t) and {t }.

36 [y tl 1 t ]. The right side of (5. 3) is further enlarged by taking the supremum instead over the interval [0 A Y t 0 V t ], in which the n symbols A and v are defined by a A b =min(a, b) and a v b = max(a, b), respectively. The supremum of [xn(u)] over the larger interval is denoted by **. We now assume the following: the n'th derivative of x(t) not only exists, but is also almost surely continuous at each t. 9 A consequence of this assumption is lim {sup [xn(u)]} = [xn(0)]23 (5. 4) y - oo ** here the interval over which the supremum is taken shrinks to the single point zero, so that the indicated convergence is monotone. Lebesgue's monotone convergence theorem, applied to (5. 3) with sup replaced by sup, therefore yields *n * lirm Y a < (n! ) Ef[x (0)] }Efjl L. (0 )J. (5. 5) %y -O.1 Jk In writing (5. 5), we have taken advantage of the independence of x(0) and {t }, and have used the stationarity of {t} to eliminate t (I 5], Theorem 2.3. 1). The arguments just concluded may be modified by substituting inf for sup, in which case the inequalities obtained are in the opposite direction. One may again employ the monotone convergence theorem, which For n=l and n=2, the results to be derived in this section are already given by (3. 11) and (4. 5), respectively, but without any requirement on the continuity of the n'th derivative.

37 now yields 2n 2 -2 2 n 2 lim Zn > (n!) E{x (0)] }E H [L. (0)I }. (5. 6) y --- o 1 Jk 2n 2 It follows rom (5. 5) and (5. 6) above that the limit of y ~ exists and. is given by the right side of these inequalities. A statement equivalent to this assertion is 2 -Zn -2 En 2 n 2 -Zn E = y (n!) E{xx (0)] }E{f [L. (0)]} + o(y ). (5.7) Jk We have thus shown that the mean square error for polynomial interpolation of a randomly sampled signal is consistent with the classical error formula as well as the results obtained earlier in the context of sample-and-hold and polygonal interpolation recovery. VI. SUMMARY AND CONCLUSIONS We have analyzed the asymptotic mean square errors for polynomial recovery schemes when stochastic signals are sampled at random times. The results are expressed in dimensionless parametric form emphasizing the role of the nondimensional sampling rate y. Sample-and-hold recovery is seen to exhibit mean square error pro-2 -1 portional to y when the signal is differentiable, and y when it is not. Error penalties for jitter appear to be negligible, nor does low probability random skipping exact a major error increase. Introduction of exponential decay fails to improve high sampling rate performance measurably when the signal is not differentiable; for a differentiable signal, the decay

38 -2 -l changes the dependence on sampling rate from y to y Polygonal interpolation or extrapolation yields a mean square error depending on y for twice differentiable signals. The error varies ac-3 -1 cording to y when the signal is only once differentiable, and with y for a non-differentiable signal. It is clear from these results that signal differentiability is a desirable attribute at high sampling rates. It is shown that n point polynomial interpolation gives mean square -2n errors proportionate to y if the signal is at least n times continuously differentiable. The mean square error also varies directly with moments of the forward and/or backward recurrence times, as it does with sampleand-hold and polygonal interpolation; this variation is multiplicative and does not negate the y dependencies mentioned above. Virtues of the simple (e. g. sample-and-hold and. polygonal) interpolators (or extrapolators) include ease of mechanization, lack of complex design computations, robustness and good performance. Comparisons regarding the latter have been made with Wiener-Kolmogorov filters for the few cases when the optimal time-invariant interpolator (extrapolator) could. be derived. Mean square errors for the Wiener-Kolmogorov interpolators tended to vary with y 2, which distinctly favors the simple interpolators (extrapolators). An explanation of this apparent paradox is easily found; although the simple interpolators are easy to implement, they nevertheless constitute time-varying filters, whereas the WienerKolmogorov filter is constrained to be time-invariant.

3 9 REFERENCES [1] A. V. Balakrishnan, "On the problenl of jitter in sanlpling, IRE Trans. Information Th., 3 (1957), 226-236. [2] F. J. Beutler, "Prediction for wide-sense Markov processes," IRE Trans. on Information Th., 7 (1961), 267-269. [3] F. J. Beutler, "Multivariate wide-sense Markov processes and prediction theory, "Ann. Math. Stat., 34 (1963), 424-438. [4] F. J. Beutler, "Error-free recovery of signals from irregularly spaced samples, "SIAM Review, 8 (1966), 328-335. [5] F. J. Beutler and 0. Leneman, "The theory of stationary point processes, "Acta Mathematica, 116 (1966), 159-197. [6] F. J. Beutler and 0. Leneman, "Random sampling of random processes: stationary point processes, "Information and Control, 9 (1966), 325-346. [7] F. J. Beutler and 0. Leneman, "The spectral analysis of impulse processes, "Information and Control, 12 (1968), 236-258. [8] F. J. Beutler and 0. Leneman, "On the statistics of random pulse processes, " Information and Control, 18 (1971), 326-341. [9] W. M. Brown, "Sampling with random jitter, "J. SIAM, 11 (1961), 460 -473. [10] P. J. Davis, Interpolation and Approximation, Blaisdell, New York, 1963. [11] I. Gelfand and N. Vilenkin, Generalized Functions: Volume 4, Applications of Harmonic Analysis (trans. by A. Feinstein), Academic Press, New York, 1964. [12] V. I. Kryukov, "Calculation of the correlation function and the spectral power density of random sampling," (English trans. ) Radio Engr. and Elec. Phys., 12 (1967), [13] O. A. Leneman, "On error bounds for jittered sampling, "IEEE Trans. on Automatic Control, 11 (1966), 150. [14] O. A. Leneman, "Random sampling of random processes: optimum linear interpolation, "J. Franklin Inst., 281 (1966), 302-3 14. [15] O. Leneman and J. Lewis, "A note on reconstruction for randomly sampled data, "IEEE Trans. Automatic Control, 10 (1965), 626.

40 [16] 0. Lenenlan and J. Lewis, "On nmean square reconstruction error, IEEE Trans. Automatic Control, 11 (1966), 324-325. [17] O. Leneman and J. Lewis, "Random sampling of random processes: mean-square comparison of various interpolators, " IEEE Trans. Automatic Control, 11 (1966), 396-403. [18] A. I. Liff, "Mean square reconstruction error, "IEEE Trans. Automatic Control, 10 (1965), 370-371. [19] B. Liu and T. Stanley, "Error bounds for jittered sampling, " IEEE Trans. Automatic Control, 10(1965), 449-454. [20] M. Loeve, Probability Theory, 1st ed., Van Nostrand, New York, 1955. [21] J. A. McFadden, "The entropy of a point processes, "J. SIAM, 13 (1965), 988-994. [22] Yu. A. Rozanov, "To the extrapolation of generalized random stationary processes, " (English translation), Th. Probab. and Appl., 4 (1959), 426-431. [23] C. E. Shannon, "Communications in the presence of noise, " Proc. IRE, 37 (1949), 10-21.

x(t) /iI I I nn-2 n-it tn+l L L (t) Figure Sample-and-hold Figure 1: Sample-and-hold Interpolation

x (t) X(t) I I ~~~I I ~I I ~~~I I!I I ~~~I I'./~~~~~. n — _ nxpnetia-Dcay__-n + n~tl t

x(t) tn- tn tn tn+ Figure'3: Polygonal Interpolation w

l&@@&gl&@R|22029@Nli&0@t~ir IY u vv SI.T,( I F3