PROCEEDINGS OF THE IEEE, VOL. 65, NO. 11, NOVEMBER 1977
1565
The Shannon Sampling TheoremIts Various Extensions and Applications: A Tutorial Review
ABDUL J. JERRI<
br />
AbrrmctIt has been almost thirty yeus since Shannon intmduced the sampling theorem to communicltions theory. In this review plper for the we will attempt to present the v h s contriiutions made sampling theorems with the necessrry mathematid details to make it
s l o t i e . efc nan d
We wiU begin by a clear statement of Shannon’s sampling theorem fdlowed by its applied mterpretation for timeinvariant systems. Then we will review its origiu as Whittaker’s interpolation series. The extensions will include sampling for functions of more than one variable, randomprocesses, nonuniform sampling, nonbmdlimited functions, implicit sampling, generilized functions (disQiutions), sampling with the function aud its derivatives as sllggested by Shannon in his origiual paper, md sampling forgeneral integral trmsforms. Also the conditionsonthefunctionstobesampledwillbesummlrized Theerror & of the va&u samplingexpansions, incldhg specifii error a i s b o d s forthe tnmation, dhing, jitter md parts of vaious other errorswillbediscussed~summnized Thispaperwillbeconcluded of by search@ the different recent applications the samplingtheorems in other fiikls, begides communications theory. These include optics, crystdbgmphy, timevarying systems, boundrry value problems, spline apptoximation, special functions, md the Fourier and other discrete
tT8QSfOmlS.
I. INTRODUCTION
theory is that it allows the replacement of a continuous bandlimited signal by a discrete sequenceof its samples without the loss of any information. Also it specifies the lowest rate (the Nyquist rate) of such sample values that is necessary to reproduce theoriginal continuous signal. We may stress here that the Shannon sampling theorem and most of its extensions are stated primarily for bandlimited functions instead of random processes which are morerelevant to the information theorist. However, and as we shall see in Section ID2, most of these sampling expansions can be extended easily to random processes. It is our intention t o include all possible relevant contributions in communjcations, mathematics, and other fields, a task which we hope to give the justice it deserves. To this end we have attempted to include an exhaustive bibliography to help the specialist and the interested reader of various disciplines (see [205][248]). We will attempt, whenever possible, to unitethedifferentnotationsused,butattention should be given to such differences, especially when we quote certain detailed results such as estimates of various errors.
HE SAMPLING theorem that we shall discuss in detail was introduced by Shannon [ 11 to information theory. A . The Shannon Sampling Theorem Shannon’s original statement [ 11 of the WKS sampling However, the interest of the communications engineer in the sampling theorem may be traced back to Nyquist [2], theorem is the following. Theorem IA1: “If a function f ( t ) contains no frequencies Aswe shall see in Section I1 this theorem was originated by both E. T. and J. M. Whittaker [3][SI and Ferrar [6],even higher than W cps it is completely determined by giving its though some attribute it to Cauchy [7,p. 411. In the Russian ordinates at a series of points spaced (1/2W) s apart.” Shanliterature theorem this was introduced to communications non’s proof starts by letting theory by Kotel’nikov [8], and took its name from him as 2nW opposed to Shannon, Whittaker, popular the or sampling f ( t ) = 27r w F ( w ) e  i w ’ d w = I/ w F(w)ejwrdw theorems in the English literature. In what follows we will use 2n 2nW either one of the above references or, brief, we will use WKS in sampling theorem both after Whittakers, Kotel’nikov, and (1) i l Shannon. We w do this with every sampling theorem that involves a bandlimitedsignal, i.e., represented by a finite limit since F ( o ) , the spectrum of f ( t ) ,is assumed to be zero outside (truncated) inverse Fourier transform. WKSK will stand for the band (2nW, 27rW). The Fourier series expansion of F(w) Kramers’s [ 9 I and Weiss’ [ 101 generalization of the sampling on the fundamental period 2nW < w < 27rW is theorem which involves more general integral transforms than the usual Fourier transform. Attention should be given to the minor variations in the definition and/or the alternate use of the Fourier transform and its inverse. As we shall illustrate in the following sections, the principal impact of the Shannon sampling theorem on information
Manuscript received November 22, 1976; revised April 25, 1977. The submission of this paper w s encouraged after review of an advanced a proposal. This paper is dedicated to Professor ClaudeE. Shannon on his sixtieth birthday. The author is with the Department of Mathematics,Clarkson College of Technology, Potsdam, NY 13676.
We notethattheFourier coefficient c, is proportional to f(n/2W), the sample of the signal f ( t ) . Also, {c,} determines F(w),hence, by the uniqueness propertyof the Fourier transform, f ( t ) is determined.Shannonthenconstructed f ( t ) as
1566
PROCEEDINGS OF THE IEEE, VOL.
65, NO. 11, NOVEMBER 1977
the sampling series
This result is easily established when we use the Fourier exponential series ( 2 ) for F ( w ) in ( l ) , exchange the integration and summation, and use (3). We will see in Section 11C that the outline of this proof and the method of constructing f(t) as in (4)is parallel t o the work of J. M. Whittaker [4]. In fact, Shannon introduced the physics of time and frequency to the second part of Theorem 11C1, where (4) is Whittaker’s cardinal series. This celebrated theorem, with some variations fromtheabovementioned Shannon statement, is discussed briefly in a number of texts [ 11I [ 191 in the field of communications with some detailed illustrations. In the Japanese literature,Someya [ 191discussed the sampling theoremat about the same time Shannon did [ 11. The variations in the proofscenterarounddifferentmethods of manipulationin Fourier analysis, contour integration, and matrices. Due to the symmetry of the Fourier transform pairs, the sampling theorem is also valid for timelimited functions, i.e., for F ( w ) the Fourier transform of a function f ( t ) which is zero for It I > T :
I I \
Y
INPVT
Fig. 1. Physical interpretationo f Shannon’s sampling expansion (4).
I
I
I
\
I0
I
\
\
/
/
\
2y4W1 2w2
wlm* wl
,
WI
\
\,
I
,/‘
2 %
2wc
B. System InterpretationTimeInvariant Systems Reza [ 11, p. 3051 gave the following physical interpretation to Shannon’s (WKS) sampling theorem.Supposethat f(t) represents a continuous bandlimited voltage signal. Then f ( t ) can be sampled attimes { n / 2 W } , n = 0, T1, T 2 , . Here k ( t ) = (sin 2nWt)/(nt) is known to be theimpulse response of an ideal lowpass filter with system function K (a) and frequency cutoff at 2nW (Fig. 1). So f ( t ) of (4) will be the output of such a fiter with input taken to be the pulse train defined by the samples { f ( n / 2 W ) }as shown in Fig. 1. As we will see in Section IVI, Papoulis [ 131, [ 141 later extended the WKS sampling theorem in such a way that he obtained a physical interpretation with more relaxed conditions on the fiter (Fig. 2 ) and with a recognizable pulse as input rather than the unattainable impulse. The relaxation of the Titer’s condition will result in an error that can be minimized by sampling at a rate higher than the Nyquist rate of (4) (see Section IVI).
Fig. 2. A more practical systemfunction expansion.
for a filter o f a sampling

Function. He showed that this analytic expression is not only an interpolatory expression but a representative one as well. At this point, we may say that the sampling theorem of Shannon had its origin. The first thing we notice is that Whittaker’s problem is concerned with equally spaced values of the argument so a periodic functionis expected. Whittaker considered the tabulated values of the function f(t), i.e., f(a), f ( a + w ) , * * ,f ( a + nw), and derived the final form of the cardinal function as
We note that this cardinal series is the one Shannon used for h s sampling theoremand is what is sometimes called the i 11. THE ORIGINOF SHANNON’S SAMPLING THEOREM Whittaker sampling theorem. There are two references here, INTERPOLATORY FUNCTIONS to E. T. Whittaker [3] andJ. M. Whittaker [ 4 ] , [SI. This In ti section we review the theory of interpolatory func may be due to the fact that the final statement of the above hs tions, since this is where the Shannon [ 1 ] sampling theorem sampling theorem in terms of bandlimited signals is very originated. As such we intend to show that itis also here that close to the more refined statements of J. M. Whittaker 15, p. the Weiss [ 101 and Kramer [9] generalization of the above 681 concerning the relation between the cardinal series ( 6 ) and sampling theorem to other integraltransforms besides the the truncated Fourier integral (1). The most complete recent Fourier oneemerged as a natural extension. treatment of Whittaker’s cardinal function as a mathematical tool was given by McNamee, Stenger, and Whitney [ 2 0 ] . A . The Cardinal Series Theylinkedthecardinalfunction to the centraldifference E. T. Whittaker [3] set out to find an analytic expression through their similarities, and showed again how the cardinal for a function when the values of the function are known for function provides a link between Fourier the series and equidistant values a, a + w , . . * ,a + nw, of its argument and Fourier integral. Finally, they showed that the cardinal funcsuch that this expression is free of periodic components with a tion can be used for solving integral equations. Very recently used Whittaker’s cardinalfunction t o derive period less than 2w. This function was called the Cardinal Stegner [ 211
JERRI: SHANNON SAMPLING THEORY: A REVIEW
1567
various types of very accurate approximation procedures, along witherrorbounds,forinterpolating,integrating,and evaluating the Fourier and the Hilbert transforms of functions.
B. Suggestions for Other Series
then C(X) = sin n ( x  b )
n
,=OD
‘
( 1)“C(b + n)
xbn
(13)
At this point it is not surprising that we raise the question: “Is it possible to consider someexpression resembling the cardinal form that deals with the samples of a function at nonequidistant values of its argument, say {t,}?” To follow the same procedure we know that sin At is the simplest periodic function with period (2n/A), so for our case we avoid it and try a moregeneral kernel K (A, t ) with a sampling function
S,(?)
= S O , r,)
(7)
where S(t,, t m ) = 6 , p . The explicit expression for such a S,(t) is given by Kramer [9] forthe generalized sampling theorem for any choice of K ( X , t , ) as an orthogonal set on [ a , b 1. So we can regard Gamer’s generalization as a natural extension of Whittaker’s and work the popular sampling theorem. C. The Cardinal Series and the Fourier Zntegral In this section we will discuss J. M. Whittaker’s [4] important development toward what we now know as the Shannon sampling theorem. In particular, his explicit theorem involves the cardinal series and Fourier and FourierStieltjes integrals. Hence, he came the closest to the present statement of the sampling theorem as it is given interms of a bandlimited signal (i.e., a truncated inverse Fourier transform). J. M.Whittaker’s [ 4, Theorem 21 theorem is thefollowing. Theorem ZICI: “If the series
where {a,} lp implies that the series in (12) and (13) are convergent.” Here {a,} I p means that the series E;= la, Ip is convergent. We also note that, by Hardy’s theorem, for C(x) as (C, 1)summable to beconvergentweneed an/(x  n ) = O( l/n), i.e., if C ( b + n ) is bounded. Ferrar called this the consistency of the cardinal series. This corresponds to the representation of the sampling theorem as compared t o the interpolation only, the in case of interpolatorytheory. Again, J. M. Whittaker asserted that, given a sequence ao, a l , * ,a,, . of real numbers,then the series (cardinal) of type (1 l ) , convergent or (C, 1) summable, affords a meansofdefining the trigonometric integrals associated withtheFourier and FourierStieltjes series, respectively. For example

a
a(x)=
J:
f ( x ) cos x? d?
(14)
converges, the cardinal series
c( x )= n
sin nx
I
a0 +
OD
(1y
x
,=I
[.+I}
(9)
x x nn +
where f ( x ) is represented by the Fourier series and a(x) by the cardinal series. Here, we led are to thetruncatedFourier cosine integral in (14). At this point we note that the above statement is another,more precise statement ofwhat E. T. Whittaker had started, with almost everything centered around the cardinal series. Now we may raise a question of a different nature which is still aimed at tying the Kramer generalization of the sampling theorem to a common origin with the Shannon sampling theorem and, hence, is a natural extension of the latter. This question is, “What of kind integralrepresentation would a series other than the cardinal series offer?” As an example, it is sufficient to consider the Bessel function Jm (x?), of the first kind of order m , instead of sin x t . J. M. Whittaker [5,p. 711 came close to touching the question of the generalized sampling expansion when he considered the general partial fraction series [ S , p. 641 :
is absolutely convergent, and its sum is of the form
1
[cos n x d F ( t ) t
+ sin nxt d G ( ? ) ]
(10) (15) where the cl, CZ, * , is a strictly increasing sequence of positive numbers such that E;=l c i z converges and
where F , G are continuous functions. Given any function f(x) of the form of (10) theseries

i (C, 1) summable to f(x).” The (C, 1) here s stands for “Cesiro summability” where, according t o a theorem due to Hardy [ 221, this means that the series (1 1) converges if f ( n ) is bounded (see Section VI). Previously Ferrar [61 gave the following theorem, which we consider to be even closer to Shannon’s original statement of the sampling theorem. Theorem ZZC2:“If Z= ; la,(P is convergent, p > 1, and C(x) is defined by
In addition, he noted that Theorem 11C1 does not apply to (1 5) in general, but to the special case H ( z ) = sin nz and c, = nn, z = cx, as the cardinal series is in terms of {sin n n x } , an orthogonal set of functions relative to its zeros in [0, 11. At this point he hinted that a theorem similar t o Theorem 1161 holds if cn = t,, the zeros of J o ( z ) , the Bessel function of the fist kind of orderzero,and H ( z ) = z J ~ ( z ) (15)l. So, [in H(xc,) is the orthogonal set relative t o its zeros with a weight function p ( x ) = (l/x). It is then no surprise to find the Bessel functions among the first examples the generalized sampling of theorem (Section 111A), where we accept the theorem as the
1568
PROCEEDINGS OF THE IEEE, VOL.
6 5 , NO. 11, NOVEMBER 1977
natural extension of the work of Ferrar [6] and both Whittakers [ 3 ]  [5 ], and different than their cardinal series. One advantage of using the finite Bessel (Hankel) transform is thatthe ndimensionalFouriertransform, with circular symmetry, is reduced toJnlp(x)BeSSel transform [231 [see (2911.
D . The Sampling Theorem and Interpolation Jagerman and Fogel 1241 considered the W K S sampling theorem as an interpolation formula, then stated and proved a number of interesting extensions. They first considered the Lagrange interpolation polynomial[25 1
[3][5], Kotel’nikov [81, Shannon 111, and Kramer [91 as compared to WKS for theWhittakers’, Kotel’nikov‘s, andShannon’s popular sampling theorem.
A . The Sampling Theorem f o r Hankel (Bessel) Other and Finite Limit Integral Transforms The final generalization of the sampling theorem was stated by Kramer [91 as the following theorem. Theorem 111A1: “Let I be an interval and L2 (I) the class of functions # ( x ) for which hl#(x)12 dx m. Suppose that for each real t
<
f ( r ) = b ( x , t ) g (xx ) d
(19)
then extended the real variable r to a complex variable Note z. that (17) is the partial fractionexpansion of J. M. Whittaker’s equation (15). Here (Pn(z))/(gn(z))is analytic except at the zeros of gn(z), the sampling points, and Pn(z) is entire, i.e., analytic everywhere. This was generalized to include an infinite number of sampling points.Thechoice for g ( z ) was obviously g ( z ) = sin (nz/h), so
P ( z ) = sn i h i=m
where g ( x ) E L z ( Z ) . Suppose that for each real t , K ( x , t ) E L2(Z), and that there exists a countable set = { t n } such that B {K(x, t,)} is a complete orthogonal on I . Then set
where
R K ( . , t ) K ( xt,n )dx
S,(t) = S ( t , t n )=
nz
OD
(l)jf(jh)
.”
~ I K ( X , dx tn)l2
(21)
z  jh
is the cardinal series for the entire function P(z). The sample points are uniformlyspaced on the complexplane. We remark here that a more general choice for g ( z ) would be a function such as Jm(z), where the sample point distribution would be asymptotically uniform. For their choice of g,(z), they stated and proved a’number of basic extensions of the WKS sampling theorem, using themethod of contour integration and the PaleyWiener theorem [ 26, p. 131which states the equivalencebetweenband4imitedfunctions and q a integrable ur e functions of exponential t p . Thentheyextended ye these sampling theorems to include the samples of thefunction f ( j h )and its derivative f(jh), an important extension which was remarked on explicitly by Shannon [ 11 , and which we will discuss in detail in Section IVB.
KO
Here g ( x ) E L2 V) means that g ( x ) is Lebesque measurable and that Ig(x)12 dx < m. Also R ( x , t ) is the complex conjugate of K ( x , r). The simplest proof is readily established when we write the orthogonal expansion for g ( x ) in (19) in terms of
III. THE GENERALIZED SAMPLING THEOREM In t i section we will discuss the generalization of Shanhs non’s sampling theorem to include more general, f f i t e limit (truncated) integral transformsbesides the usual Fourier tmns form. In Section IIC we indicated how Whittaker [51 had
suggested a sampling series for a finite limit integral transform with the Bessel function, instead of the exponential function, as its kernel.Thefirstgeneralization that followed in this direction was considered by Weiss [ 101 for transforms with kernels which are solutions of the SturmIiouville problem associated with secondorder differential equations [27]. Kramer [9] followed this by a detailed treatmentfornthorder differential equations and illustrated it for the case of the Bessel function as a kernel. In the following, we wgive thestatement of the genl l i eralized sampling theorem with various illustrations, compare it t o Shannon’s sampling theorem, present its physical interpretation in terms of timevarying systems, and then discuss its various extensions and applications. As we mentioned in the beginning of Section I, we will refer to t i generalized hs theorem as the WKSK sampling theorem, after both Whittakers
m
=
n= 1
f(tn)Sn(t)
[(19)(20)1
after usiug (19) for f ( r ) and (21) for the sampling function S,(t), or what we sometimes write as S ( t , rn). We may mention here that a weighting function p ( x ) may be introduced [27], [28] in theintegralsof(l9)insteadofhavingitimplicit in the product K ( x , r ) g ( x ) . Also we indicate that the same proof can be followed when K ( x , t ) of (19) is expanded in terms of the same orthogonal functions K ( x , rn). However, the shortest proof is to use Parseval’s equation [29] for the integral in (19) with the Fourier coefficients c, of (23) and
JERRI:
SAMPLING THEORY: A REVIEW
1569
S n ( t ) of (21) for g(x) and K(x, t ) , respectively (see Section
VA). Kramer [91 showed thatconditionsthis the for theorem on the kernel K(x, t ) in (19) are exhibited by the solutions of nthorder selfadjoint differential equations [ 27, p. 188, p. 2841. He illustrated it for the cases when K(x, t) = eix t and when K(x, t ) = Jm(xt), where Jm(xt) is the Bessel function of the fimt kind of order m . Campbell [ 281 illustratedthe case when K(x, t ) = P,(x),where Pt(x) is the Legendre function. Other illustrations including K(x, t ) as the associated Legendre, the Gegenbauer, the Chebyshev, and the prolate spheroidal functions [30] were done in detail in [3 11 with suggestionsfor their use in scattering problems in physics. A recent illustration for K(x, t) as the associate Laguerre function LF(x), but with an integral defined on the semiinfiite interval (0, OD) instead of the usual f i i t e interval, is found in [ 321 . As an illustration of Theorem 111AI , we present the case of the fiiite limit Jm Hankel, or Bessel, transform :
f(t) =
f(t) =
1,
1
G ( x ) F ( x ) dx (27)
we can use the integral representation of C;(x) [33, p. 159, equation (27)] as a truncated Fourier transform in (27), then interchangetheorder of integrationanddefine H ( u ) in a simple way to obtain
J' xJ,(xt)F(x) (24) dx.
0
The sampling function ( t ) of (2 1) derived as S, is ~lxJm(x~)Jm(xtm,n)dx
s n ( t ) =SO, t m , n ) =
1 x [ J m ( x t ) l 2 dx
Jm ( t m , , )
where the {rm,,} are the zeros of the Bessel function J m , i.e., = 0, n = 1 , 2 , . . Here the familiar properties of the Bessel functions wereused [33] to evaluate the integrals of (25).The final sampling series (21)forthe f i i t e limit Hankel transform becomes
so the function + l))/(r(t + 2v)) f(t) and hence f ( t )may be sampled by the WKS sampling theorem. To compare the two sampling theorems in a more precise way, some defiitions were presentedandconditions were found [341 under which the two sampling theorems, namely, the Shannon and the generalized one, are equivalent. In summary, the theorems presented in [34] simply tell us that there is no advantage in using the WKSK sampling theorem when the function is represented by a double inverse Fourier transform with finite limits. This, however, is the case only when we assume that the communications engineer is interested in working with no integral transform other than the Fourier one. So the advantage of the WKSK sampling theorem may become clear when we consider otherhtegral transforms [35], [36] andespecially for timevarying systems [371 which we shall discuss in the following section. One other obvious advantage is the use of the Hankel transform in optics [ 141 where, with circular symmetry, a JoHankel transform is equivalent to adouble Fouriertransform and, in general, a J(m/2)lHankel transFourier transform form is equivalent to an mdimensional [23, p. 821 :
(r(t
Jm(rm,,) = 0, n = 1,2,
*
.
We note here that the weighting function p(x) = x has been introduced explicitly in (24) instead of having it implicit in the product K(x, t)g(x)of (19).
Here, F ( E ) = F ( @ ) = F ( p ) is the mdimensional Fourier transform of f ; = f(ldl) = f ( r ) with circular symmetry. () Hence, in two dimensions we may replace a double WKS sampling series by a single WKSK sampling series associated with the Bessel kernel Jo(x).
C. System InterpretationTimeVarying Systems
B. On the Equivalence of the Generalized (WKSK) and Shannon (WKS) Sampling Theorems The first question related to the generalized sampling theorem was raised by Campbell [ 281 concerning the possibility of applying Shannon's sampling theorem to functions that can be sampled by the generalized sampling theorem. He considered as kernels in (19)thesolutions of regularfirstorderand regular wcondarder differential equations separated with boundary conditions, and the solutions of the singular Bessel andLegendreequations. For these cases Campbellshowed that if a function with such kernels can be expanded by the useof the WKSK sampling theorem, then it can also be expanded the by use of the WKS sampling theorem. These results were extended 1341 to include integral transforms with kernels such as the following: Py (x), the associated Legendre function; C:(x), the Gegenbauer function; Lr;(x), the Chebyshev function of the second kind; and other functions. For example, in the case of the finite Gegenbauer transform:
As we have presented in Section IB, the applied interpretation [ 11 ] for the special caseof K(w, t ) = eJwr, i.e., the Shannon sampling expansion (4), is that f ( t ) is the output of an ideal lowpass filter with impulse response ( t ,t , ) = 2 W (t, h S t n ) = [sin 2nW(r  (nn/2W))]/[n(t  (nn/2W))l and with the =f(n/2W). The applied input taken to be the pulse train f ( t n ) interpretation of the generalized sampling expansion (20) can begiven [361, where f ( t ) is considered as theoutput of a band (or transform) limited [381 and a lowpass filter in the sense of these general integral transforms, with a timevarying impulse response that is related directly to the sampling function in (21) and with the pulse train { f ( t , ) } as its input. This was done for a transformlimitedfunction:
with the Fouriertypeinverse:
1570
PROCEEDINGS OF THE IEEE, VOL. 6 5 , NO. 11, NOVEMBER 1977
F(w)= p ( t ) K ( w , f ( t ) d t .
where p ( w ) is a weighting function. Here K(w, t ) stands for the complex conjugate of K(w, t). Also, the limits of integration in (31) are not finite and will be specified for the particular integral transform. The complete details of this analy[36] withthe main definitions being in ysis arefoundin agreement withthosein D'Angelo [ 3 7 ] , Zadeh [39], and Zemanian [401 . Some basic properties of such transforms including the Parseval's equality, theorthogonality of the sampling functions.on the interval of the integral (3 1), and the convolution product were derived and the Hankel transformwas presented as an example 1351, [36].
s
E. Sampling with the Value of the Function and Its Derivatives When Shannon [ l I introducedthe sampling theorem to communications he also remarked that the value of the function f ( t ) can be constructed from the knowledge of the function and its derivative at every other sample point, then extended his remark to higher derivatives. In Section IVB we w discuss the different methods (141, [241, [50][53] l i of arriving at this result with illustrations and physical inter[ 5 4 ] , 1551 forsuch pretation.Thetruncationerrorbounds series are presented in Section VIA. This result 1241, [52] has beenextended [561,[571 toother integraltransforms associated withthe generalized (WKSK) sampling theorem, which we will discuss at the end of Section IVB and illustrate for the case of Hankel (Bessel) transforms. F. Other ExtensionsSampling for an Infinite Limit LaguerreLt(x) Transform Until recently [ 3 2 ] , all direct illustrations of the sampling theorems have been associated with functions represented by finite limit (truncated) integral transforms whose kernels are orthogonal on the same finite interval. The first example of a sampling expansion functions for represented by an integral with i n f i t e limits is that of the associate LaguerreL t ( x ) transform [321. Here the associate Laguerre polynomials LE(x) are used, which are orthogonalonthe semiinfinite interval (0, =) with respect to the weighting function p ( x ) = e  xx 4 . This result is summarized in the following theorem. Theorem IIIFI: If the function F ( x ) is such that ex x"lF(x)(' dx <a,or i brief F ( x ) E L z (I, p ) with p = e% n * xu and I as (0,~)) then its LaguerreLt transform
D. Some Applications (Also Sections VIIBVIIC) The first reference to the possible application of the gener[35] was for alized sampling theorem communications in timevarying systems analysis [361 which we discussed in the last section. Also in the case of circular symmetry, for exampleinoptics,it is known (141, [23] thatthe needed doubleFouriertransform can be replaced bya single JoHankel (Bessel) transform. Hence, it is advantageous to replace a double Shannon sampling seriesby a singleBessel one. In generd,with circular symmetry,an rndimensional Fourier transform reduces to a onedimensional J(,,,/Z)~ Hankel transwas in the field of form[see (2911. Thenextapplication nuclear scattering [3 11. In particular the sampling functions (21) for the generalized sampling theorem are necessary for evaluating the lth eigenvalue of the unitary Smatrix[4 1] due to the nth Regge pole of the Smatrix. This is especially true when a more general orthogonal expansion is needed rather than the usual Legendre one. In the field of heat transfer, the generalized sampling theorem wasused [ 4 2 ] to facilitate the solution of a conjugated boundary value probem. The analysis is applied to determine the effect of the axial conduction on the temperahs ture field for a fluid withlaminar flow in atube. In t i problem the finite JoHankel transformwas used to algebraize the radial part of the partial differential equation. $0 satisfy theboundaryconditionatthe interface of the fluid, the coefficients of the two i n f i t e series solutions are matched to obtain the final solution. However, since the generalized sampling series is applicable to the finite Hankel transforms it was possible [42] to recognize the infinite series in both solutions as the sampling series and hence assign it the transform function value. This resulted in eliminathg the infinite series on both sides, thereby eliminating the need forapproximations and numerical matching procedures. Themostrecent attempt to use the generalized sampling expansion is in the field of general discrete transforms [ 4 3 ] , [ 4 4 ] . This is in parallel to the discreteFouriertransform [ 4 5 ] , [ 4 6 ] whichlead to the fast Fouriertransform(FFT) algorithm [46][48]. In attempting to develop a discrete Hankel transform [ 4 4 ] , [ 4 9 ] we are guided by its corresponding sampling expansion which dictates the sample spacing. This recent investigation indicates thatforthe discrete J o Hankel transform of N terms, the samples are taken at { ( j o , , ) / b } and { ( j o , , ) / c ) in the two t and w spaces, respectively, with io,, being the nth zero of J o ( x ) and j o , < b c < ~
jO,N+ 1 .
f(v)
=Jex
0
XQ
L:
 F(x)dx,
S ~ ; , ' ; ; ~ O
(32)
has the sampling expansion
1 f ( v ) = (1  x)yr(v
+ 1)
where
We note here that in contrast to the other sampling expanof sions which involve the nth sample f ( n ) in the nth term the sampling series, the sampling expansion in (33) involves a combination of the first n + 1 samples of the function in the nth term of the sampling series. However, for t = k, a nonnegative integer, the sampling expansion (33) gives the sample values f ( k ) . To verify this we note that the summation over n in (33) stops at n = k and all the coefficients of (A  l)"m in the double series cancel out, except that of ( h  l ) k which which involves reduces (33) to f ( k ) . The rigorous proof, writing the Lz(x)Laguerre polynomials orthogonal expansion of F ( x ) , integrating term by term as in (32), and using some
JERRI: SHANNON SAMPLING THEORY: A
REVIEW
1571
special integrals [331 is given in [ 321. We may note that the socalled Laguerre function is d e f i e d as
L;(x) =
r(Y + l ) r ( a + 1) M (Y,
r(Y+a+1)
+ 1 ;x)
(34)
Petersen and Middleton [ 531, [61 I presented a very detailed treatment of the sampling theorem in n dimensions [6 1 I that involved the samples of the amplitude and the gradient I531 of an ndimensional stochastic field (see Sections IVBIVC)
where M(a, b ; x) is the confluent hypergeometric .~  function. We should point out here that the Laguerre function in (24) is defiied differently from that of 133, p. 268, equation (3711,
1 L;(x) =  (  v , a + 1;x) M
fh(?)=
Ikl
[f(~[k])g(3,?[k])+af(r[k])'i;(r,r[k,)1
r(v+ 1)
(38)
where ?(?) is an estimate of the value of the random field f(3) at every point 3 in the Ndimensional Euclidean space. g ( 2 , Iv. VARIOUS EXTENSIONS THE SAMPLING THEOREMS z [ k ] ) and hl(3, z p ] ) ,1 = 1, 2, * * * ,N are functions applying, OF In this section we will present most extensions of Shannon's respectively, t o the values of amplitude and each componentof (WKS) and the generalized(WKSK)sampling theorems. This the gradient measured at the sampling point J [ k ] , for reconincludes sampling in n dimensions, with derivatives, for struction of the random field at any point ?. x [ k ] stands for xkl  x k N . In addition the Ndimensional summation random processes, with nonuniformly spacedsamples,bandpass, implicit sampling, for distributions (generalized func to suggesting various applications (see Section VIIE) they tions), for signals with timevarying bands and others. [ 61 I concluded that, for deterministic fmctions, the most efficient lattice is not ingeneral rectangular, nor is a unique reA . The Sampling Theorems in n Dimensions construction function associated with a given sampling lattice. weighting functions werederived Shannon's sampling theorem was extended by Parzen [58] In addition,suchoptimal to include sampling for bandlimited functions of n variables. [531 for least meansquare reconstruction of the above (38) N The following is the statement given in Reza [ 111 where the dimensional stochastic fields fromdiscretemeasurements of proof follows the same method as used fortheonedimenamplitude and gradient. Montgomery [621 utilized the sional (WKS) sampling theorem (Section IA). function and its gradient then sampling expansion with a Theorem IVA1: "Let f(tl, t2,. * . , r,) be a function of n extended the result of Petersen and Middleton (38) to include real variables, whose ndimensional Fourier integral exists and the samples of the function and its higher partial derivatives is identically zero outside an ndimensional rectangle and is [631 up to orderK < 1 symmetrical about the origin; that is, but it reduces to the Laguerre polynomial L ; ( x ) when Y = n. g(Yl,yz,. Then
.
*
,Yn)=O, lYkl>
Iakl, k = 1 , 2 , .
*
, n.
(36) where f(?) is a square integrable complex valued function in the Ndimensionalspace, ? is avector in thisspace, d~ are points of the sampling lattice and g(?  & ) is the weighting function applied in the construction of f(7). d~ is an integral where n' = (nl, nz, * * * , linear combination of the vectors &, nN) gives the integral coefficientsused. Gaarder [64] extendedthendimensional sampling expansion to allow nonuniformbut periodicsampling, asubject which we shall discuss inSection IVD. Sharma andMehta [65] extended the generalized (WKSK) sampling theorem, with kernels besides the Fourier one, t o higher dimensions for bandpass functions insteadof the usuallowpass ones (see Section IVE).
B. Sampling with the Values of the Function and its Derivatives 1 ) The Shannon (WKS) Sampling Theorem: As we mentioned in Section IllE, when Shannon introducedthe sampling theorem he also remarked that the value of j ( t ) can be reconstructedfrom the knowledge of thefunction and its derivative at every other sample point, and then extended his remarks t o higher derivatives. Fogel [ S O ] considered this question without reference to the above remark, and stated and proved the following theorem. Theorem IVB1: "If a function f ( r j contains no frequency higher than W(Hz j it is determined by giving IU function derivative values at each of a series of points extending
s i n ( w l t l  mln) * . .sin(w,t,  m,) a n t ,  mnn olrl m l n 
, ,
(37)
Miyakawa [59] presenteda sampling theorem for stationary stochastic variables in n dimensions. A very interesting historical review of the sampling theoremswithreference to many relevant applications was presentedbyPetersen [60]. We may remark here that the above Theorem IVA1 can also be proved easily by using the Parseval's equation in n dimensions [29]. Also, we can extend this result to include higher dimensional general integral transforms of the type (1 9) used for the generalized sampling theorem. proof The we give follows the same method used in Section 111Afor proving the generalized sampling theorem and in particular the simple use of the general Parseval's equations for suchhigher dimensional transforms. We may point out again the advantage of the generalized sampling theorem where a J(,,2 Nankel transform is equivalent to the above ndimensional Fourier transform when g($)in (36)and f(?) in (37) possess circular symmetry [23]. Hence, the ndimensional sampling series (37) may bereplacedby a onedimensional Besselsampling series (26) with m = (n/2)  1.
,
1572
PROCEEDINGS OF THE IEEE, VOL. 6 5 , NO. 1 1 , NOVEMBER 1977
throughout the time domain, sampling interval T = (M/2W) being the time interval between instantaneous observations.” Later, Jagerman and Fogel I241 incorporated above the theorem and a theorem dealing with exponential order to give a number of very useful theorems including an explicit form that involves the samples of the function and its derivative. The method of proving their results relies on Lagrange interpolation polynomial and contour integration. The importance of t h i s result lies initsapplication.For example, for an aircraft the estimated velocity as well as position are used to determine a continuous course plot of the path with half the sampling rate. As a generalization to the above results and as an explicit answer to Shannon’s remark [ 11 concerning the reconstruction of a function f(t) when the value of the function and its first R derivatives are given at equidistant sampling points (R + 1)/2 W seconds apart, Linden [ 5 1I and then Linden and Abramson [ 521 gave the following final result after a minor correction. Theorem IVB2: “Let f ( t )be a continuous function with F(o)[F(o) 0 for I w l > 2nWI. = finiteFouriertransform Then
relatesthelimitoftheRderivative sampling expansion as R 00 to Taylortype series weighed by a Gaussian density functioncenteredabouteachsamplepoint. An interesting question would be whether twopoint (Lindstone interpolation [25, p.281) and thenNpoint Taylorseriestype expansion would reduce to a samplingtype expansion as N m? The proof of Theorem NB2 relies on somewhat involved matrix methods [521. However, the method of using contour integration can be employed [56], [ 571 to derive (40) in a very simple fashion. Among other very interestingresultsconcerning the sampling theorems, Papoulis [ 14, p. 1321 presented a very useful decompositiontheoremandutilized it to arrive at a simple method for deriving the sampling expansion with R = N  1 derivatives. Theexplicitform for R = 1(N = 2) was easily obtained by this method
+
(43) where oo is thebandlimitand T = n/(wo). However, this does not seem to be the case when N > 2. Note that R = 0 or N = 1 corresponds to sampling with the function only. As we mentioned in the last section, Petersen and Middleton [53] gave the sampling expansion for stochastic fields representedby an ndimensional bandlimited Fouriertransform that involved only the samples of the function and its gradient lo (38) (see Section NC). They a s suggested many applicationsincludingcrystallography and meteorology where the samples of the function and the gradient were sufficient for their analysis. As such they did not include any higher partial derivatives. Montgomery [63] extended results these to involve higher orderpartial derivatives (39).Later another method was devised 1561,[571 for suchextensionand was illustrated for the double Fourier transform. Such a method uses a generalization to two dimensions of Linden and Abramson’s important lemma [52] that was used for deriving (40). We suggest here that contour integration methods, similar to that used in [24], [561, [57] for functions of several variables [ 661 may be used to establish the sampling expansions with R derivatives for higher dimension bandlimited Fourier and other integral transforms. As we have shown, sampling with derivatives increases the sample spacing required, or in other words it allows the reconstruction of the bandlimited signal with a sampling rate less than the Nyquist rate. Another approach aiming at the same goal was established by Kahn and Liu [67]. They treated the problem of the representation and construction of widesense stationary stochastic signals, not from set one of data {f(nn/a)} but from several sets of sampled values obtained by using a multiple channel sampling scheme. They showed that with the optimum combination of prefilters and postfilters, in the case where two sets of sample values are taken, the frequency range of the input signal is limited by the prefiiters to a total width of 4a. This is instead of the usual total width of 2u when a single channel is used, which makes it stand as a natural extension of the latter case. Todd [68] used multiple channels to reconstruct deterministic bandlimited signals with a sampling rate less than the Nyquist rate. The sample rate needed is inversely related to the number of the channels used and directly proportionalto the Nyquist rate. 2 ) The Generalized (WKSK) Sampling Theorem: Recently,
where h = ( R + 1)/(2W).” are The E(i)(kh) in (40) linear combinations of the f(j)(kh):
Here
The I’$) may be expressed in terms of the noulli numbers. Some of these values are
generalized Ber
r26) =
a(35a2 + 42a + 16) 63
rip)
=0,
for o d d &
Equation (41) may be obtained by multiplying both sides of (40) by {(n sin n(t  kh))/(t  k h ) } (R+l) and equating their jth derivatives at t = (kh)/n. Such expansion makes clear the advantage of sampling with the function and its R derivative since the sample spacing here is h = (R + 1)/2W, which is (R + 1) times that of h = 1/(2W) for the case involving the samples of the function only. Rearrangement of terms in(40) ieldsanalternateform whichemphasizesthe derivatives f 6 ) ( k h ) rather than their linear combinations In (41). addition, alternate this form
JERRI: SHANNON SAMPLING THEORY: A REVIEW
1573
the samplingwith R derivatives (40) was extended [56] to include the finite limit Hankel and other transforms besides the Fourier transform of (40). The method used in such is general results employs contour integration which a generalization of the method used by Jagerman and Fogel [ 2 4 ] . It is shown that, in parallel to the known special case of the trunof samplingwithR catedFouriertransform,theadvantage derivatives is to increase by ( R + 1)fold the asymptotic spacing between the sampling points. The importance of such anadvantage forthe Hankeltransform,forexample, is of course realized in timevarying [361 or spatialvarying systems. As an example, the generalized sampling expansion with one derivative for the finite limit JOHankel transform f ( t )=‘ [
0
xJo(xt)F(x) dx
(44)
is
(45)
where {to$} are the zeros of the JoBessel function of the first kind of order zero and sk(f) is the same sampling function as in (25)
were presentedbyPetersenandMiddleton [ 531, [70] and Petersen [ 7 1I The complete treatment of this subject will be found in [ 721. Among other generalizations of the sampling theorem, Parzen [ 581 presented simple proofs using Fourier series for the Fourier kernel eiwr to establish the above result (47) for random variables. More general theorems that include the above result as a special case were presented by Lloyd [ 731. He first presented conditions under which the above random variables x(t) of a stationary (widesense) stochastic process {x(t), 00 < t < =} are determined linearly by the “sample” } random variables {x(nh), 00 n < a . This maybe summarized as follows: “the process x is determined linearly by its samples if and only if some set of frequencies A containing all the power of the process is disjoint from each of its translates A  (r/h), r = f 1, f 2, * * (that is no two frequencies in A differ by amultiple of (l/h).” ThenLloydshowed that such a linear dependence has the form of the sampling series (47) and discussed its convergence properties. Of themany theoremspresented in thisdirection, wegive the following theorem [731 and its corollarywhich is ageneralization of the above Theorem IVC1. It is noted that most of the results for stochastic processes are based on their corresponding ones for deterministic signals. Theorem IVC2: “If the spectral distribution of process x hasanopensupport A whose translates {A  (n/h), OO < n < a} are mutually disjoint thenthe sampling series is (C, 1) summable in norm to x(t); i.e.,
.
<

The generalprocedurefor deriving (45) fortheJoHankel transform, and other finite transforms including the Legendre transform is outlined in [56] and presented in detail in [571. The derivation of the sampling expansion with derivatives for double finite Fourier transform presented in [ 571. is
C. Sampling Theoremsfor Random Processes Another extension of the WKS sampling theorem was considered by Balakrishnan I691 where he showed that the WKS sampling theorem can be used to represent a process of a continuous time parameter. One of his theorems in this direction is the following. Theorem IVCI : “Let x( t ) , 00 t =, be a real or complex valued stochastic process, stationary in the “wide sense” (or secondorder stationary), possessing a spectral density which vanishes outside the interval [2nW, 2nWI. Then x(t) has the representation
N
x(f) = 1.i.m.
N+m
x(nh)K(t nh)”
,,=N
(48)
where
K ( t ) = he2mktdA,
J*
= < t
< 00.
(49)
< <
A series L: uj is said to be Cisaro summable (or (C, 1)) if the mean u N = ( s l +s2 + * *  s N / N of its partial s u m s s l ; *  , s N ) converges (see Section VA). We may note that if A in (49) is the one interval ( (1/2h), (1/2h)) then K ( t  nh) is the familiar sampling function of (47). The following corollary considers the special case when A is a finite union of mutually disjoint open intervals a = 1 , 2 , * . . ,n} where, accordingto (49): Corollary: “if the set of frequencies A is a finite union of intervals, or more generally, if l.u.b. < t < oo ~ t ~ ( < 00, t)l then the sampling series convergesin norm to x(t); i.e.,
g),
{(g,
x(t) = 1.i.m.
N+
,= +
2 x(nh) K ( t  nh).”
N
for every t , where 1.i.m. stands for limit in the mean square.” The proof consists of using the WKS sampling theorem for the covariance function of the process, since it is assumed to have truncated a Fourier transform. Then x * ( t ) , the optimal estimate of x(t), was constructed by using the sampling series to show that the meansquare erroris zero. chap. 201 also treatedrandomsampling Middleton [ 12, and presented a comparison of random and periodic data sampling. Peterson 1601 gave a very detailed treatment for samplingof spacetimestochasticprocesseswithapplication to informationanddecisionsystemsandavery interesting review. Many applications extensions and of the subject of optimal reconstruction of multidimensional random fields
Here1.u.b. stands for least upper bound which means, as it sounds, that for the set of real numbers A , if x is an upper bound for A and if y is any upper bound for A then x <y , then x is called the least upper bound ofA or x = 1.u.b. A . We may remark here that (50) is a generalization of (47) towards bandpass or multipass systems and away from the usual bandlimited ones. The extension to multidimensional space of the sampling theorem of stationary stochastic variables was treated combines Theorem IVC1 and by Miyakawa 1591 which Parzen’s results [ 5 8 ] forthe ndimensionalsampling. Miyakawa a s considered the application of his extension to lo crystallography. Petersen and Middleton53 ]derived optimum [
1574
PROCEEDINGS OF THE IEEE, VOL.
6 5 , NO. 1 1 , NOVEMBER 1977
weighting, or sampling, functionsforreconstructingthe ndimensional random field f(3) using the sample measurement of its amplitude and gradient (38). Their criterion forthe optimum reconstruction, of the estimate %’(;) for f(31, is to minimize the (statistical) meahsquare errorE { [f(;)  f(3)] } at every point 3. In a later paper, Balakrishnan [74] considered the question, “that a stationary stochastic process is not physically realizable.?’ As an answer hespoke of “essentially bandlimited stochastic processes.” For sampling over a finite interval (0,T ) instead of the usual infinite one (a, Lichtenberger 1751 showed that sampling a) infinitely often over any finite interval (0, T) taken at arbitrary discrete times { t i } leads to perfect reconstruction of an analytic random process f(t). He considered a separable Gaussian random process f ( t ) , with its samples { f ( t i ) } taken at the arbitrary times {tj,} over the fmed interval (0,T ) , then constructed an estimate f&) such that
’
Fig. 3. Recurrent nonuniformsampling,N = 3.
x admits the meanquareequivalent sampling representation:”
1.i.m. E { l f ( t )  &(t>12} = 0,
Nt
a
<t <
00
(51)
where
for all t E ( 00, m).” The proof here is a formal one in the sense that (54) was expanded and the expectationwas allowed to be exchanged with the infinite summation to yield the above result of (54). We may note how this theorem is related to twodimensional deterministic function sampling. Sharma and Mehta [86] presented a generalized sampling theorem nonstationary for processes.
D. Sampling with Nonuniformly Spaced Sampling Points
For the case of a bandlimited function f ( t ) with all the sampling points outside the interval ( T , T ) being exactly zero, Shannon [ 11 remarked, asdid others before him, that only then can f ( t ) be specificed by 2WT sampling points where W is the bandwidth. He also remarked that these 2WT sampling points need not be equally spaced, an idea that obviously cani not be covered by h s version of the WKS sampling theorem and its cardinal series. We review here some of the work which was done in this direction. The first is a statement which was attributed to Cauchy by Black [ 7 , p. 41 ] :
If a signal is a magnitudetime function, if time divided into and
The proof utilized the Lagrange interpolatiohnformula for representing f(t) with its Nth partial s u m for fN(t), in (5 I), then letting N + 00. An error bound was derived as
where 7 = max (It  t , 1, It  tN I) and R is some finite number defined as I D ( N ) R ( t , s ) I< R N . HereR(t,s) is the covariance of f(t) and D c N ) f ( t ) ( d N f ) / ( d p ) . More general results in E this directionwere presented by Beutler [ 761. Instead of the usual sampling at equidistant instants or the above arbitrary instants, Beutler and Leneman [77] considered random selection of the sampling points. Leneman [ 781 and then Leneman and Lewis [79] [8 1 ] considered some specific related results. Barakat [ 8 2 ] used the sampling expansion in one [ 121, [ 841 and higher [ 591, [ 6 11 dimensions, in connection with nonlinear transformation of stochastic processes associated with Fourier transforms of bandlimited positive functions. 1 ) Sampling Theorems for Nonstationary Random Processes: The sampling theorems presented so far in t i section deal hs with widesense stationary random processes, while the rest of the paper dealsmainly with deterministic signals. For nonstationary random processes, Zakai [83] was the first to present a sampling theorem followed byPiranashvili [84] then Gardner [ 85 1 , who presented the following theorem which required a relativelysimple proof and which was motivated toward applications. Theorem I V C  3 : “Let x be a random processwith autocorrelation function k,(t, s. If the double Fourier transform ) K,(f, v) of k,(t, s) satisfies the bandlimiting constraint
equal intervals such that each subdivision comprises an interval T seconds (sic) long, where T is less than half the period of the highest significant frequency component the signal, and i one of f instantaneous sample is taken from each subinterval (sic) in any manner, thenaknowledgeoftheinstantaneousmagnitudeof eachsampleplusaknowledge of theinstantwithineachsubinterval at which the sample is taken, contains all the information of the original signal.
Yen [87] considered the case where a finite number of uniform sample points migrate in a uniform distribution to new distinct positions. He proved that the bandlimited signal f(t) remains uniquely defined, then reconstructed f(t). When the number of migrated points increases without limit he called it a gap and proved a similar theorem. Yenalso considered the case of a “recurrent, nonuniform sampling.” That is, when the sampling points are divided into groups of N points each, and the groups have a recurrent period of N/2W s, as shown in Fig. 3 where W is the maximum frequency of the bandlimited function fir). He determined f(t) uniquely and reconstructed it in terms of its values at r = r p + (mN/2W), p=1,2;~,N,andm=**r,1,0,1;**asfollows. Theorem IVD1: “A bandwidthlimited signal is uniquely determined by its values at a set of recurrent sample points
r=rpm=rp+(rnN~2W),p=i,2;~~,N;m=~~~
*
K,(f, u )
for
jL k,.r,
. . The reconstruction is
*
e2m‘(frvs) d r ds = 0
If1
( 1 / 2 T ) and Iul 2 (1/2T) (for some nonzero
0,then
m=mp=l
JERRI:
REVIEW SAMPLING THEORY: A
1575
where
a=1
1.1
q =1#p
lV
(56)
[88] considered various Recently, Sankur Gerhardt and methods for reconstructing a continuous signal from its nonuniform samples. They employed and compared a number of techniques including lowpass filtering, spline interpolation, and Yen’s [ 871 interpolation. The spline or hillfunctiontype interpolation is a special polynomial expansion which is relatively new, with best approximationproperties (see Section VUC). Their observation,fromthesimulationexperiments with these and other techniques, was that even though Yen’s method was impractical to realize, it still proved superior to the other methods. This is in the sense that it is insensitive to sample migration and signaltonoise ratio (SNR)
SNR =
i=l
sampling expansion is not stable [93, Theorem 1I . They also gave a simple example with uniform sampling that is not stable (see Section VID). Beutler [ 941 considered and proved what is called the “folk theorem” in the sense that a signal f(t) may be represented by any linear combination of irregularly spaced samples f ( t , ) , provided that the average sampling rate exceeds the Nyquist rate, Le., that the number of samples per unit time exceed (on the average) twice the highest frequency present in the signal. Also he showed that only the past need to be sampled at an average rate greater than the Nyquist rate to assure errorfree recovery. Even more, the recovery is sometimes feasible if the average rate is less than the Nyquist rate, e.g., if sampling is concentrated in rare bursts of higher than the Nyquist rate sampling. Like Yao and Thomas [ 931 ,his proofs utilized nonharmonic series expansion, but within a more general mathematical setting. Furthermore, Beutler [941 applied his results to deterministic as wellaswidesense stationary stochastic processes. In summary, for a bandlimited function on(  a , a ) the freedom of having irregular sampling, or allowing the sampling in, stants r to deviate from those of the Nyquist instants (nnla), stems from some theorems due to Levinson [ 951. These theorems give conditions on a set of real numbers I t , } which assure that
N
(Sj

;j)2
i=1
s:
eiWtn g ( o ) dw
= 0,
for all n , g E L , (  a , a )
(58)
where the si are the signal samples and & are the samples from the reconstructed signal. Recently Marvasti and. Gerhardt [891 presented a practical treatmentfor signal transmission using nonuniform sampling. The specialcase of Yen’s nonuniform but periodic sampling was extended to higher dimensions by Gaarder [64] with explicit sampling series which he then applied to nonrectangular lattices. Yao and Thomas [90] derived sampling representation for bandlimited functionswhenthe sampling instantsarenot necessarily spaced uniformly but each deviate less than (1 /n) In 2 21 0.22 from its correspondingNyquist instant, as required by the WKS sampling theorem. They termed such representation as “semiuniform” and used nonharmonic Fourier series for its derivation. Finally they remarked that a sample representation is not possible when all the sampling instants are allowed to deviate nonuniformly by (1 /4) unit from their corresponding Nyquist instants, or if an arbitrary finite number of the sampling instants are placed arbitrarily, or if additional sample points are added. Prior to this, Beutler [ 9 1, p. 11 11, in his unified approach to sampling theorems (see Section VC), treated the same “perturbation” question and concluded that the sampling times need not be periodic, but may vary from the true periodicity by over 20 percent without sacrificing capability of restoring the signal f ( r ) . A l s o , Leneman [92] presentederrorboundsforjittered sampling. In a laterpaper, Yao and Thomas [ 931 considered the question of the stability of the WKS sampling expansion inthe sense that a small change in the amplitude of sample values should lead to small changes in thereconstructedfunction. This subject willbe discussed in Section VID. They showed thatthe uniform Lagrange interpolation sampling expansion preserves some stable properties while a general nonuniform sampling expansion need not possess these stability properties. their For “semiuniform sampling expansion” [ 931 where 1 r  (nn/a)l< , d < (1/4) they showed that it is stable while for the nonuniform sampling, Le., when d > (1/4) the Lagrange interpolation
implies that g = 0 almost everywhere. Here g E L p (  a , a ) means that 1 ,g ( w ) I p d o < m where the usual case of p = 2 I 4 defines finite energy signals. Also the condition (58) defines the set { e i w f n } as a closed set. Brown [96] treated the nonuniform sampling for bandlimited and finite energy signals using a finite energy and bandlimited Lagrange interpolating function. Hegave conditions on the nonuniform sampling instants { t , } such that f ( t ) is uniquely determined by the sample values { f ( t , ) } and posesses a uniformly convergent representation
eo
f(t>=
,=eo
f(t,)Q,(t),
03
< r < 00.
(59)
The function \k,(t) is a Lagrange interpolating function which is bandlimited to the same band as f ( r ) and \k,(tk) = 8 , , k for integers n and k. The conditions on the sequence (t,} are that it is both stable, as defined by Yao and Thomas [93], and exact. By “exact” or “minimal” set it is meant that the closure, as defined by (58) of the set {eiw‘n} on the interval (  a , a ) , is destroyed by the deletion of any single term from it. A detailed treatment of the sampling theorem including nonequidistant sampling points is presented in Churgin and Iakovlev [ 971.
E. Sampling for Bandpass Functions Kohlenberg [ 981 was the first to consider sampling expansions for a bandpass function which lies in the frequency band (Wo, W o + W) instead of the usuallowpass function with band limits (  W, W). This is to bedistinguished from the bandpass function whichvanishes outside the intervals [ W O , W O + W] U [ W o  W,  Wo] . Because of the possible nonuniqueness of the equispaced sampling expansion,heintroduced what he termed “secondorder sampling”whichguaranteed a unique representation. Secondorder sampling involves two interleaved sequences of equispaced sampling
1576
PROCEEDINGS OF THE IEEE, VOL. 65, NO. 11, NOVEMBER 1977
points. In general a pthorder sampling is defined as
P
P
in which the ith sampling series g i ( t ) has particular “sample spacing” ai, “phase” ki, and “sampling function” S i ( t ) . He first considered a firstorder sampling with a 1 = a = (1/2W), kl = 0 for bandlimited function f ( t ) in the frequency range (0,W) and used Fourier analysis to obtain the WKS sampling series
where the frequency spectrum vanishes outside the bandpass region Rm = [ W O  nW, W O + n W ] U [  W O nW,  W O + nw1 instead of the interval Z in (19)(21). Their main result [65, Theorem 2.31 is the following. Theorem ZVE2: “Let g ( w ) be a complex valued function with g ( w ) E L 1 , i.e., i2 Ig(w)ldw<m, on  = < o < m and let K ( t , w ) be a complex function of timesuch that IK(t, w)l = IK(t,  w ) l . Consider a bandpass signalf(t) which is real valued and bandlimited to the bandpass region RBP = [W, nW, Wo + nW] u [ Wo  nW, Wo + nw1. If
then where the samples are independent, since SI(0) = 1 and Sl(n/2W) = 0 for n = + I , ?2, * , and the sampling rate of 2W per second is minimum, For the case of firstorder sampling with u l = a < (1/2W)

where
It is clearthat thesamples are not independentsince Sl (an) # 0 J for n # 0. To treat this problem for the general case of bandKBP‘ ’ pass function f ( t ) on ( W O , o + W), a necessary and sufficient W , was found to permit The explicit expression for L n ( t ) and an example of K ( t , W ) = condition of W o = cW,c = 0, 1, 2, the exact construction of f ( t ) from its samples at the mini Jo(w,t ) , the Bessel function of the first kind of zeroth order, mum rate of 2W per second. In contrast, the following second were also presented. We may remark that the method of provk order sampling expansion (a = a2’ = (1 /W), l = 0,kz = k # 0 ing this general result is a simple and straightforward one in (60)), permits the use of 2W samples per second for any W O which parallels the proof for the generalized (WKSK) sampling theorem (Theorem 111AI). But in contrast tothe remark and W 1981, [12,p.2151. Theorem ZVE1: For a function f ( t ) in a band ( W O , made by Kohlenberg [ 981 and others [ 121, [ 5 11, [ 581, concerning the required sampling rate in order to guarantee the W o + W), the exact interpolation formula is algebraic independence of the samples, no such remark was mentioned forthe above generalization orits specialcase. However the above Theorem IVE2was extended to higher
I ’

S(t) =
COS [2n(Wo
+ W ) t  (r + 1) rWk]  cos [ 2n(rW  W,) t  (r + 1) n W k ]
27rWt sin (r + 1) nWk
In (63), we have two groups of samples each at a rate of W per second with spacing ( 1 / W ) shifted by a phase k from each other. k in (64) is a constant such that kWr, kW(r + 1) # 0, 1, . , and where r is an integer such that (2W0/W) < r < 2 W o / W + 1. Such development of sampling for bandpass functions is discussed in Middleton [ 12, p. 21 51, and was also derived by Linden [ 511 and Parzen [ 58, Theorem 41 using somewhat similar but more direct and simpler methods of Fourier analysis. Linden [ 5 I ] relied on the convolution theorem of Fourier analysis and verycleargraphical illustrations to derive (63) and (64) and also gave secondorder sampling expansion for the usual bandlimited function. The result (63), (64) can be derived easily with the help of the Hilbert transform [ 17, p. 761. 1) TheGeneralized(WKSK) Sampling Theorem for Bandpuss Functions: Sharma and Mehta [65] derived the sampling expansion for bandpass functions represented by more general integral transforms than the Fourier transform. This is a generalization of the WKSK sampling theorem (Theorem 111A1)
dimensions [65, Theorem 3.11which is a generalization of Theorem IVAI for bandpass functions with more general kernels. F. Implicit Sampling All the sampling expansions that we have discussed up till now may be termed “explicit” samplings in the sense that a bandlimited function f ( t ) is represented in terms of its samples f ( t n ) at preselected instants { t n } which are independent of f(r). “Implicit” sampling may refer to the casewhen the function is represented in terms of the instants { f n } in which the function assumed a predetermined value, for example its zero crossings { t n : f ( t n )= 0) or its crossings with a cosine function { t n : f ( t n )= C cos 2nwt,}. The first “implicit” sampling expansion was considered by Bond and Cahn (991 as they extended the WKS sampling theorem when the sampling instants { t n } are not independent of the sampled signal f ( t ) . Their justification was that such a procedure had proved valuable in minimizing the error caused by infinite clipping, which
JERRI:
SAMPLING THEORY: A REVIEW
1577
means that we can transmit a continuous signal over a discrete channel if the zero crossings of f ( t ) are preserved. Forf(t), a bandlimited function on (0,W), they extended t to a complex variable z and used Titchmarsh’s [ 1001 result that
~ ( z ) =
converges uniformly, for w > W o ,in any bounded region of the zplane. Let C > B 2 If(t)l and let
c
(73)
eZKif2 V(f) df
(68)
Then the following infinite product also converges uniformly, though conditionally,in the same region: f(z) = [f(O)  C] lim
nt
is a real, entire function, described by the location of its zeros which are either real or occur as complex conjugate pairs. In general, the zeros tend to cluster near the real axis. Furthermore, the aggregate of the zeros occur at the Nyquist rate.
,
+ c cosnwz. (74)
Thus
A sufficient condition for convergence is that f*k should in
dicate the kthzero to the right (left) of the origin.”
G. Sampling for Generalized Functions (Distributions) where f(0) # 0, z , = R , e i e n , R , < R , + l , and limn,.,, The extension of the WKS sampling theorem ( l ) , (2) to band(2WR,/n) = 1. Note that the formula (69) needs all the past limited generalized functions was f i t considered by Campbell and future zeros, both real and complex, which makes it im [ 1051. He noted that the WKS sampling expansion practicable. Instead, they suggested another, more practicable sin (ar  nn) problem with specified interval ( (T/2), (T/2))and zeros inside f(t) = f this interval occurring at slightlyless than the Nyquist rate, m  nn) zeros outside are real and occurring at the Nyquist rate. Let N be the largest integer not exceeding WT; then there are a of the bandlimited function maximum of 2 N real or complex zeros, z , = t , + iu,, 1 t , 1 < T/2. Outside this interval the zeros occur at t , = *(n/2W), for n = N + 1, N + 2, . Using this in (69) and referring to e  j w t g ( w ) dw (76) f(t) = the infinite product representation of the sine function, they 51 obtained where g ( o ) is integrable, is valid when g ( w ) is replaced by the Dirac delta function 6(w  a), which is a special case of a generalized function. In this case it is obvious that (75)reduces to
g);(
(at

I”
where A , is expressed in terms of the values of the 2N zeros zm inside the interval as a Fourier series expansion of the function f(a) = e  i a t . However when g ( o ) = 6’(w  a ) , the derivative of 6(w  a ) , the Fourier transform (76) in this isjt eiar and f ( n n / a ) = case (innla)e(jnnl”)= O ( n ) , which makes the series (75) diverge. Herewe let 0 and o have their usual meaning, i.e., F ( x ) = O ( g ( x ) ) means that there exists an M such that F ( x ) < M g ( x ) and F ( x ) = o ( g ) means that m+xo ( F ( x ) / g ( x ) ) 0. Thus i, l = Campbell concluded that the WKS sampling theorem (75) does not extend to the Fourier transform of an arbitrary distribution with bounded support. He then investigated functions which are Fourier transforms of distributions with bounded support and showed that these bandlimited distribution functions are still entire and are completely determined by their a bandwidth for the sample values at nn/8. Hereservesas support which we shall present next as Theorem IVG1 . The statements of Campbell’s theorems need a few definitions and the usual notation, as given in Zemanian [ 1061. One of his main results in this directionis the following. Theorem ZVG1: “Let g ( w ) be a distribution with support contained in the open interval ( w :Iwl < (1  q ) where 0 < q < 1. Let f(t) be the Fourier transform of g ( w ) . Then
m+n
where m in the numerator of (71) as the index of the zeros within the interval ( ( T / 2 ) , ( T / 2 ) ) . Later Bond, Cahn,and Hancock [ 1011 found a relation between the above “implicit sampling” and the Fourier coefficients that allows a Fourier series representation of a bandlimited functioninterms of its zero crossings. More work on the subject of implicit samplingwas done by Voelker [ 1021 which was simulated on a computer by Sekey [ 1031. BarDavid [ 1041 considered the important case of implicit sampling in terms of real variables alone. For example, theinstants { f , } at which a bounded bandlimited function f(t) crosses a cosine function { t , : f ( t n )= cos 2nwt,}, where f(0) and { f , } determine f(t) uniquely. He considered bounded functions which are bandlimited in the usualsense or as extended by Zakai [83], to give the following implicit sampling theorem. Theorem IVFI: “Let f(t) be a bounded bandlimited function of bandwidth W o such that the sampling expansion
(a, a),
a}
where S( y ) is the additional factor defined as
1578
PROCEEDINGS OF THE IEEE, VOL. 65, NO. 1 1 , NOVEMBER 1977
B :2nw 1 ( t ) < w < 2nwz (t),the signal f ( t ) is said t o have the timevarying spectrum F(w, t ) and the timevarying band B. Also for constant w1 and w2 in (81) this represents the bandpass signal which we discussed in Section IVE. The expansion for the signal f ( t ) of (81) in terms of the samples off(t, 7)in (82) is
Campbell [ 1051 also derived an expression for the truncation error (see (181)) of (78) that reduced to previouslyderived errors of the usual WKS sampling series, which we shall present at the end of Section VIA. Pfaffelhuber [ 107) presented additional results for the bandlimitedgeneralized functions which include that, fora suitably restricted space of test functions, the WKS sampling theoremexpansion is valid in its classical form,andthata bandlimited generalized function f ( t ) can be represented by a series of delta functions
wow=
f(t) =
5 n=
n 
3 {WI 0 ) + w z w ) .
(87)
f0,) 6 0  t n )
(80)
concentrated at the sampling points { f n } with weights equal to the sampling values f ( t n ) . This means that, as it is the case for ordinary bandlimited functions, the information contained in the whole signal is equalto the informationprovided by the sample values at { t n ) . As we have indicated [29] in Section IVA for sampling in n dimensions and other extensions of the sampling theorem, the proper extension of Parsed’s equation [ 108, p. 641 offers the simplest method of proof. also gave a representation for bandPfaffelhuber [.lo71 limited distribution that lookedlike a combinationof a Taylor series and a conventional sampling series [ 107, Theorem 21.
Thederivation of the sampling expansion(84) is obtained simplybywriting the Fourier series of F(w, t ) in terms of exp { ( i k / 2 w ( t ) )w }
then substitutingin (8 1). We note that the coefficientsf((k/2w(t)), t ) of (84), as specified by (82), are not the same as the samples { f ( t k ) ) of the signalf(t) except at the zeros { t k } of the equation
2 W ( t )  k = 0.
(89)
In this case, & ( t ) may be called a pseudosampling function since it plays the role of the usual sampling function
@k(fn)=Sk,n,
H. Sampling for Time Varying Systems with
TimeVarying Bands Horiuchi [ 1091was the first to extend the WKS sampling theoremforthe analysisof continuous signals specifiedcby timevarying spectra with timevaryingbands. This is in line with what we had presented in Section111C for using the generalized WKSK sampling theorem for timevarying systems. In both cases the analysis is justified only when the fluctuations of the timevarying parameters of the system are predicted in advance. Consider the class of continuous signals
zflwz(t)
k,n=O,T1,*.
(90)
Horiuchi [ 1091 then considered some special cases and showed that only for restricted cases the expansion (84) can be realized as a sampling expansion with the usual physical interpretation of the WKS sampling theorem. We may remark here that the expansion (84) may be realized when we consider the generalized WKSK sampling theorem and its physical interpretation in terms oftimevarying systems (see Section 111C). Applications of boththe WKS and the generalized WKSK sampling theorems to timevarying systems arediscussed in Section VIIB.
f ( t )=
zw(t)
F(w,t)eiwfdw 1)
(8
with timevarying spectrum F ( o , t ) andtimevaryingbands, 2 n w 2 ( t ) , 2 n w 1 ( t ) . Here w l ( t ) and w z ( t ) are bounded realvalued piecewisecontinuous functions such that w z ( t f > W l O ) , w z ( t > 0. ) Signalf(t)of (81) can be specified bya timevarying signal
f(t, 7)=
Pflwz(7)
2flw1(7)
00
F(w,7)eiw7 d7
(82)
and its Fourier transform
I. Other Extensions Papoulis [ 131, [ 141, [ 1 l o ] , [ 1 11 ] presented and discussed in detail various extensions of the WKS sampling theorem. Some of these extensions were utilized to give a more practical physical interpretation of the sampling theorem than the one associated with an ideal lowpass filter (Section IB). He then presented different error bounds for the sampling expansion which we shall discuss in Sections VIA and VIB. We will present here the main extensions which lead to such relaxed physical interpretation of the sampling series t o which we IB (see Fig. 1 and Fig. 2 , Section IB). hintedinSection Papoulis considered a bandlimited signal f ( t )
f ( t )=
F(w, 7)=
where f ( t ) f ( t , t ) . Since thefunction
f ( t ,7)e  id t t w
(83)
2=
[’
w1
F(w)e id w wr
(91)
F(w, t ) vanishes outsidetheinterval
but constructed it in a more general way than that of the WKS sampling theorem (4) t o give
J E R R I : SHANNON SAMPLING THEORY: A REVIEW
1579
where w 2 E ( n / T )2 w l ,w1 G w o < 2 w2  w1. We note here that with the band limit wl, the samplingspacing T ( n / w 2 )< (n/wl), which means that such a relaxed extension (92) requires higher sampling rates. The proof of (92) is considered to be a particularly elegant version [ 14, p. 1201 of the proof of the WKS sampling theorem. Papoulis also proved a converse to the above result, i.e., “Given an arbitrary seq.uence of numbers { a n } , if we form the sum (93) proof assumes the then x ( t ) is bandlimited by wo.”The multiplication by Fourier series expansion of F(w) then ejnT pwo(w)andintegrationterm by term. Of course, we must have a condition on the coefficients {a,} that allows such term by term integration. A sufficient condition is that Z n =   I an I < 0 . A number of theorems in this direction for 0 the WKS and the WKSK sampling theorems are presented in [ 341. Ericson andJohansson [ 1 121alsoderivednecessary and sufficient conditions for some variations of the WKS sampling series. Papoulis [ 141 then presented the sampling expansion for f 2 ( t ) ,instead of f(t), of (92) as
00
and the proof is a straightforward one after writing tbe Fourier on series expansion for (e ‘ w r / ~ ( w ) ) (u, a). Another extension of the sampling theorem is the prediction of bandlimitedprocesses from past samp!es. Brown [ 1131 considered f(t) as either a deterministic or a stochastic signal which is bandlimited to the frequency interval Iw I < II
f(t) =
!2n
J,
c“
F ( o ) eiwr dm, = < t
<
00
(991
with lFIZ integrable on [ n,n] . He showed that for any constant sampling spacing T satisfying 0 < T < (1/2), f ( t ) may be approximated arbitrarily well by a linear combination of past samples f ( r  kT) taken at any constant rate that exceeds twice the associated Nyquist rate
n n+
lim If(r) 
ak, k=1
f ( t  kT)I = 0
(100)
uniformly for  m < t < 00. Here the coefficients a h = ((cos T T ) ~ are independent of the detailed structure of the signal f(t). This result provides a sharpening of a previous result by Wainstein and Zubakov [ 1141 which requires a sampling rate in excess of three times the Nyquist rate. Beutler [94] showzd that there exist coefficients for recovering the signals with sampling rates required to exceed only the Nyquist rate. However, the explicit form for such coefficients are not given and in general they are not independent of the structureof the predicted functionf(t). Maeda [ 115] treated the sampling theorem for bandlimited periodic signals [ 171 with nonuniformly spaced points. These where w2 = (n/T), w2 B 2wl (instead of wz 2 w1 for f ( t ) results were extended by Isomichi [ 1161 to bandlimited sigin (92)), and wo is such that 2wl < wo < 2w2  2w1. We nals with finite energy. Among other extensions of the WKS sampling theorem are note here how (94) with T < (n/2w1) requires more than double the usual sampling rate. Papoulis then used this result the integral sampling [ 1171 in which the sample is taken over (94) for deriving the roundofferror of the sampling series a whole sampling period T and the sampling for signals as solutions of nthorder linear differential equations with constant which we shall discuss in Section VIC. More significance should be assigned to the sampling expan coefficients [ 1181. Holt, Hill, and Linggard [ 1171 developed a sion (94) since in applying the sampling theorem to scattering network that allows integrating the input signal f(t) over the problems or crystallography it is the intensityIf(t)12, and not whole sampling period. The sampled output signal f * ( t ) of the wave function f ( t ) ,that is to be constructed from its mea such a circuit is expressed as sured samples I f ( n T ) l * , as we shall see in Section VILA. Papoulis’ most recent generalization [ 1 11] of the Shannon f*(t) = f(7) d7 f(7) d7} u(t  nT) sampling theorem is to express the bandlimited signal nT2T nTT n=O
(i)
2
{rT rTT
(101) where u ( t ) is the unit step function. In addition his detailed to presentation and applications of the sampling theorem, Lathi [ 181 considered what is termed “natural” sampling where very narrow pulses of finite width are considered instead of the instantaneous impulses of the WKS sampling theorem. Kishi and Maeda [ 1181 considered nthorder linear differential equations with constant coefficients and showed thattheirsolutions obey sampling theorems similar to those of bandlimited functions. Their main result is that a waveform f ( t ) which is a finite linear combination of eUr or tn sin (ut + 8 ) canbe constructed from a finite set of its sample values at equal intervals. In addition they showed that f(t) can also be constructed uniquely in terms of the samples of the derivative f‘(t) as well as f ( t ) . Maeda [ 1191 showed the relations between such signals [ 1181 and bandlimited signals, and then gave some theorems [ 1201 for the interpolatory functions. Kishi and Maeda [ 12 1 ] followed this treatment by an application to waveform approximation.
in terms of the sample valuesg(nT) of the output
of a system H(w)driven by f ( t ) . The sampling expansion is
where
1580
PROCEEDINGS OF THE IEEE,
VOL. 6 5 , NO. 1 1 , NOVEMBER 1977
For integral transforms with infinite limits, like the Hilbert transform, Linden [ 5 1] gave a sampling expansionin terms of the samples of a bandpass function and its Hilbert transform. Papoulis [ 14, p. 1301 presented a sampling expansion for a signal represented by the infinite limit Hilbert transform. The sampling expansion for the infinite limit LaguerreLt(x) transfrom (33) was presented in Section 111F. Wunsch [ 1221 and Kioustelidis [ 1231 considered sampling of duration(ortime)limitedfunctions,instead of bandlimitedfunctions.RecentlyButzerand Splittstosser [ 1241 presented a more detailed treatment of such sampling expansionforcontinuousdurationlimitedfunctions whose spectrum is absolutely integratable. They also gave abound on the truncation error of such series.Slepian and Pollak [30] treated the problem of reconstructing a finitedurationfiniteenergy (FDFE) signal that is observed through an ideal lowpass filter. They showed that such construction could be performed without error by expanding the timelimited signal as a seriesof prolatespheroidalfunctions. Stuller [ 1251 used certain time domain sampling arguments, along withthe series of prolate spheroidal functions [30], to derive an interpolation formula for the FDFE signal from equally spaced samples of the observedwaveform. He showed that in the noiseless case, perfectreconstruction of the FDFE signal canbeobtained when the sampling rate exceeds one half the minimum sampling rate specified by the WKS samplingtheorem.The also limitations imposed by measurement were noise described. Kramer [ 1261 developed a very useful property of the bandlimited functions inthe sense that in digital computations “continuous” operations are replaced by “discrete” ones. In particular he gave explicit relations between the samples of the higher derivative of a bandlimited function f(t) and the samples of f(t). This was also done for bandpass functions.
grable, i.e.,F(x),K(r,)EL,(I) andwhereIis a finiteinterval. In the case of the WKS sampling theorem K(x, t ) = eur E L z ( Z ) and so it is the purpose of this section to investigate relaxing the condition F ( x ) E L 2 ( I ) on the transformed function F(x). A simple mode of proof was offered by Brown [ 1271 for the WKS samplingtheorem which employed theprototype Parseval equation ; that is, when g, h E L2 (I)and c, , d , are their respective Fourier coefficients, for the orthogonal expansion in terms of { K ( x , t , ) } , then
where
I I W , fn)ll:
= J l K ( x , tn)12
I
dx.
Brown considered the bandlimited function
f(t) =
[
eiXtF(x) dx
(1 03)
and employed (102) with g ( x ) = eixt, h(x)= F(x); K ( x , t , ) = ei(nnx’a). Clearly, d , = (1/2a)f(nn/u), IIK(x, tn)ll$ = 2 0 , and
c, = S,(t) =
sin (at  nn) (ut  nn)
f ( t )=
1 :
eixt F ( x ) dx =
,=
2 ):( f
sin (at  nn)
(at  nn)
(105)
V. DIFFERENT METHODS,CONDITIONS, AND REPRESENTATION OF THE SAMPLING SERIES
In this section we will outline most of the methods used in deriving the WKS and the WKSK sampling series. The emphasis here is to relax the conditions on the sampledsignals. This includes sampling for not necessarily finite energy signals, i.e., signals whose transforms are not necessarily square integrable but may be absolutely integrable. Besides the usual finitelimit integral representation of the signal, a triple integral representation,thatallows different physicalinterpretations will also be presented. This wbe concluded by a summaryof the l i various attempts to unify the different aspects of the sampling expansion in the sense of a general mathematicalsetting which we will not pursue here in much detail. We refer the interested reader to theoriginal papers.
as the WKS sampling series. Unless otherwise indicated, a summation like Z c, will assume limits as in (102) while Z” c, signifies the nth partial sum. It is clear thatthismethod of proof is valid forthe WKSK sampling theorem when c, and d , are given in (23) and (21) as Fourier coefficients for F(x) and K(x, t ) of (61), respectively. The WKSK theorem can also be proved by using the Schwarzinequality [91 onf(t)in (19)(20):
2
A . Different Methods and Conditions for Deriving the Sampling Series In Sections I1 and 111,we presented the WKS and the gen and noting that the orthogonal series inside the last integral eralized WKSK sampling theorems offered and the usual converges in the mean to the square integrable kernel K ( x , t ) proofs that included contour integration for the sampled func as tion f ( t ) and orthogonal expansion for the kernel K ( x , t ) or ~ ( xt , = 1i.m. ) S,(t) ~ ( x t,). , (107) Nr I n l 6 N the transformed function F ( x ) in
where both F(x) and K ( x , ) are assumed to be square inte
In attempting to move away from the condition of square insignals, Brown [ 1271 tegrability, or finite energy, bandlimited raised a question concerning the necessity for a “new mode of proof” when F ( x ) (E Lz(Z). Hegave the example ofBessel
JERRI: SHANNON SAMPLING THEORY: A
REVIEW
1581
It is clear that when p = p' = 2thisreduces to Schwarz's inequality. 2) Parseval's Equation: Consider the Fourier series expanJo(nt) = sion for g(x) and h(x) in terms of the orthogonal functions $,(x) = einx on the interval [n,n] with the Fourier coefficients c, and d,, respectively. The following are some relaxed which is bandlimited t o [IT, a ] andwithaFourier transversions of the Parseval equation: form F(x) = (2/4) which is in L1(n,n), i.e., Pm If 1 < p < m a n d g E L p , h E L p f , l / p + l / p ' = l , I 2 / d n T l dx < 00 but not inL 2( n,n). Hence, his version then of using the above prototype Parseval equation or the other method ofusing the Schwan inequality [9] cannot beused C c n d , is (C, 1)desaro summable t o g(x)h(x) dx. for they both require F(x) E L ( n,n). To answer such questions, we will make use of the Holder inequality, as opposed to its special case, the Schwarz inequality, and the many ex(115) tensions of the Parseval equation [ 291. Among the various methods for relaxing the conditions on F(x), both the Holder The case p = p' = 2 is the prototype Parseval equation used inequality and anextension of the Parseval equation allow by Brown [ 1271. The case of interest here, p = 1 is taken to the validity of the WKS sampling expansion (105) when correspondtop'=wand(ll5)isstillvalid. F o r f E L 1 , t h e F(x) E L (  a , a ) , which answers Brown's question of (108) as series converges absolutely and uniformlywhen g E C z . A very brief proof for Brown's example of Jo(nt) in (108) will make a special case. Before we introduce the Holder inequality and the proofs of useof the Parseval equation (1 15). Since eiXrE La( n, n) the sampling theorems, we will present here a few definitions and g(x) E L (n,a), its sampling series is (C, 1) summable and hence convergentwhenwe appeal to Hardy's theorem and state somebasic and very clear results [22]. Let f(x) E Lp(a, b ) mean that f(x) is Lebesque measurable which requires that f ( n ) (sin n(t  n ) ) / ( n ( t  n ) ) = o(l/n). ) J 0 and that : If(x)lp dx < 0 , where we have already used its This is the case since f ( n ) = J o ( n n is bounded, which can be shown by using the Holder inequality (1 14) (108). on two usual special cases L z and L 1 for p = 2 and 1, respectively. The first proof we give here for the WKS sampling theorem The norm l l f l l p of f i s defined by makes immediate use of the Holder inequality (114). Let S N ( t ) and DN(x) be the partial sums of the series expansion respectively, and (109) for f ( t )and K ( x , t ) = eixr in (105) and (107), consider function of zeroth order
3
1 :
Let f(x) E C k mean that f(x) is k times continuously differfunction the is of bounded DN(x)] F(x)dx. entiable. Also f(x) E BV means that variation, which is equivalent t o saying that fis the difference between twomonotonicfunctions.The followinginclusion If we use the Holder inequality (1 14) obtain we relation may prove valuable. For k 2 0,O < q < p < 00,
16) (1
CaC~~~CC~+'CC~C~~~C~CLaCLpCLq. (110)
Aswe hadconsidered inSection II (TheoremII1), nth partial sum SN(X), the
If(r) SN(t)l <
[
UP
Ieixt DN(x)Ip dx]
*[J:
1lP'
IF(x)lp' dx]
.
(117)
Hence the series in (105) converges t o f ( t )when we know that DN(x) converges in themean of order p and F(x) EL,* (  a , a ) . When p = 0 , which is the case, then (105) is valid when F(x) E 0 L (  a , a ) . By employing the Parseval equation (1 15), we can find other conditions on F(x) for the WKS sampling theorem. Also the Holder inequality may be used t o relax the condition on F(x) in (19) for the generalized sampling theorem. This of convergw. Hardy's theorem states that if c, = o( l / n ) then the course depends on our close examination of the convergence, (C, 1) Cesaro summability implies convergence. SN(X) said in the mean of order p , of DN to the particular kernel K(x, t ) . is These extensionsandothers includinggeneralized functions t o converge, in the mean of order p , to f(x)if and sampling in n dimensions for the WKS and the WKSK b sampling theorems are presented in [ 291. N ! If(x)  SN(X)IP dx = 0. (113) Boas [ 1281 presented a simple proof for the Shannon sampling theorem using wellknown summation formulas. He illustrated this method by using Poisson's summation formula 1) HolderInequality: For afiniteorinfiniteintervallet t o derive the sampling expansion including the case when the gELpandhELp~,wherel<p<=,(l/p)+(l/p')=l,then Fourier transform is integrable. Also he used such expansions t o derive an estimate for the aliasing error which results when the sampling series is applied t o a function which is not bandlimited (see Section VIB).
is said t o be (C, 1) Cesaro summable if the arithmetic mean
1582
PROCEEDINGS OF THE IEEE, VOL. 6 5 , NO. 1 1 , NOVEMBER 1977
B. Difderent Representations of the Sampling Series As we state any sampling theorem for a bandlimited function f(t) in terms of its discrete values f(tn), we involve two different representations. The first one is the integral representation for thegeneral bandlimited signal
(19)
tion of
P
r b r b
(1 19) which in our various proofs implies a series representation, i.e., the sampling expansion assumes f(t) as a finite limit transform of F ( x ) . The kernel $(x, A) of this transform is a solution of the nthorder selfadjoint boundary value problem and F ( x ) in (1 19) is the nonhomogeneous term of its associated nonhomogeneous problem with G (x, f', z ) as its Green's function [ 1301.
C. A Unified Approach to the Different Aspects of the Sampling Theorems In this section, wewill only summarize what was done in the direction of a unified and rigorous approach to the sampling expansion, since such development needs more mathematical background than this review paper is intended to deal with. Beutler [911 presented a unified approach to the sampling theorems for (widesense) stationary random processes as it rests upon the concept of Hilbert space. His treatment included, as he haddone in a more recent paper [94], the recovery of the process x ( t ) fromnonperiodic samples, or when any finite number of the samples are missing or deleted. He also gave conditions for obtaining x ( t ) when only the past is sampled and a criterion for restoring x ( t ) from a finite number of consecutive samples. Yao [ 1311 considered a number of cases for the WKSK sampling theorem as it is represented bythe bandlimited integral transforms with kernels including the Bessel, exponential, sine and cosine functions. He considered such general finite energy transforms as a realization of the abstract: I ) Reproducing Kernel Hilbert Space H {RKHS): This is a Hilbert space of functions defined on a set T such that there exists a unique function or kernel K ( x , t ) defined on the cross product T X T such that K (, t ) E K,for all t E T and that
x ( t ) = ( X , K(, t ) )E
where S,(t) = S(t, t n ) is the sampling function (21). The converse of the sampling theorem is to have (20) impIy (19). of Theorems in both such directions and in the direction WKS versus WKSK sampling representations are given in [34] and [ 341, [281,respectively. Another familiar and very useful representation is the contour integral one, which was used in derivingvaxious extensions of the sampling theorems [ 241, [54], [ 561, This method employs the residue theorem, to establish a series expansion, which states thefollowing. Theorem VBI: "Any function h ( z ) which is meromorphic (analytic except at a finite number of points) inside C, for every R , where CR is a circular contour of radius R centered at the origin, may be represented by an expansion of the form
h(z) = 
Rzj
i
+
{%}
if the integral 1/(2ni)$cR (h(f'))/(f' z ) d f 'along CR approaches zero as R 03.'' In (1 18), Rzi denotes theresidue at (zi> and zj stands for the summation over the poles of h ( f ' ) . This residue theorem can be used to produce a variety of sampling expansions. All we need to do is to let h ( z ) = ( f ( z ) ) / ( g ( z )and ) sampling choose the proper function g ( z ) that has zeros at the points of f ( z ) . This was used [24] to derive the sampling expansion (1 15) by letting f ( z ) have a finite Fourier transform representation and g ( z ) = sin z. The corresponding expansion with the function and its first derivative (42) required g ( z ) = sin' z . The same method wasused [561, [571 to derive the sampling expansion with N derivatives for the general bandlimited integral transform (19) by letting h ( z ) = f ( z ) / g N + ' ( z ) . In the specific case of f ( z ) as a bandlimited Hankel transform associated with the Bessel function Jn(z), the choice is h ( z ) = f(z)/J:+'(z). Here the sampling points are in,,, m = 1, 2, , , the zeros of Jn(z). The cases of N = 1 and N = 2 for sampling with the function alone and the function and its first derivative are presented in (26) and (45), (46),respectively. A somewhat novel method for deriving the sampling expansion of the WKSK sampling theorem was introduced by Haddad and Thomas [ 1291 then by Haddad, Yao, and Thomas [ 1301. This method represents the sampled function f ( t ) in (19) as a triple integral where two of its possible six permutations correspond to the two most used methods of derivation, the orthogonal expansion and contour integration. The significance of this representation lies in the fact that each of the six possible permutationsrepresentsan interesting physical interpretation. The derivation of the triple integral representa

for all t E T and for all x E H. The function K o t ) is the (, reproducing kernel of the RKHS. As one of Yao's examples, he proved that the class of fiiite energy, Fouriertransformed bandlimited signals is a realization of the abstract RKHS. He a s made the same statement for the Hankel transform, indilo cating the same method of proof. This is not so clear since his proof in the case of the Fourier transform uses the convolution theorem which is not as feasible or simple in the case of Hankel transforms [ 4 4 1 , [ 491. We may remark here that the reproducing kernel K ( t , T ) is different from K ( x , t ) , the kernel of the integral transform (19), but itis very much related to S(t, 7 )
S(t, 7 )
J Z
I
x(w)Kmdw
(120)
p ( w ) l K ( o , 7)1*dT =
I
p z ( w ) p ( w ) K ( w ,t ) K ( w , d u
(121)
as it represents, aside from the norm factor, the impulse response of a timevarying system when a general integral transform with symmetric kernel K ( x , t ) (30H31) is used. Indeed
JERRI: SHANNON SAMPLING THEORY: A
REVIEW
1583
we have shown [ 361 that in this
general case
and its WKS sampling representation
.~
(at  nn)
(125)
and even closer to (1 20.) we have
the truncation error ET is the result of considering the partial sum f N ( f ) with only 2 N + 1 terms of the infinite series (125),
where S(t, 7)is defined in (1 2 1). Yao [ 1311 alsodiscussed the relevanceof the RKHS for extremum problems for general integral transforms and finally of the gave anupperboundfor thetruncationerror(173) generalized WKSK sampling series, which weshall present in Section VIA. Among other information theoretic results, Jagerman [ 1321 presented the approximation of bandlimited functions in ah abstract setting and derived an upper bound for the truncation error of the sampling series (seeSection VIA). As we mentioned in Section 11A, a general treatment of the cardinal or sampling functions was presented by McNamee, Stenger, and Whitney [20]. They showed thatthe cardinal functions provide a link between the Fourierseries and Fourier transform. They also linked the cardinal functions tothe central difference in numerical analysis. A subject similar to this is Schoenberg’s work [ 1331 in extending the cardinal series expansion to splines, which we will present in Section VIIC. A more abstract generalization of the sampling theorem was established and proved by Kluvinek [ 1341 in terms of abstract harmonic analysis. In this analysis, the role of the real line, in the caseof the bandlimited integral, is replaced by an arbitrary locally compact Abelian group and the role of the sample instants (nnla) in (105) by itsdiscrete subgroups.
Unless otherwise indicated we will use 8~ for all the different truncation errors. Tsybakov and Iakovlev [ 1361 gave the first truncation error bound as
for  T < t Q T and where A t < (l/W), W is the highest frequency of f ( t ) , and E is the total finite energy which is camed by thesignal f ( t ) :
W
E=
IF(o)lZdo.
(128)
Helms and Thomas [ 541 considered the truncation error when f ( t )is approximated by the following finite sum
K+N n=KN
sin (2 Wnt  nn)
, O<N<m
(129)
with a = 2nW in (1 25); K is an integer which is assumed to be a function of t such that 2Wt  (1/2) < K ( t ) Q 2Wt + (1/2), and N is a fixed integer. Thus the truncation error & T ( f )= f(t) f N ( f ) will approachzero as N approachesinfinity provided that f(t) is bandlimited to a = 2nW. In their treatment they VI. ERRORANALYSISN SAMPLING I REPRESENTATION considered a band limit rW < W with 0 < r < 1 which, as we In this chapter, we will present a review of the various errors shall see, improved the bound on the truncation error: that may arise in the practical implementation of the sampling theorems. This includes the truncation error which results when only a finite number of samples are used instead of the infinite samples needed for the sampling representation, the where M max If(t)l for all t , q = 1  I . As an example, when aliasing error which is caused by violating the bandlimitedness N = 24, W = 1000 Hz,f(t) has the highest frequency of 750, of the signal, the jitter error which is caused by sampling at the truncation error of (1 30)is bounded by 0.068. &T instants different from the sampling points, the roundoff A similar bound was given by Jordan [ 1371 error, and the amplitude error which is the result of the uncertainty in measuring the amplitude of the sample values. A comprehensive treatment of some of these errors with their upper bounds were presented by Thomas and Liu [ 1351 and When f ( t )is approximated by an asymmetrical partial sum, Papoulis [ 141, [ 1101. As we mentioned in the Introduction, attention should be given to the different notations used especially for the signal representation as a truncated inverse Fouriertransform[see (1) and (124)]. the truncation error 8 T ( t ) = f(t)  f N , , N , is also shown to be bounded as A . The Truncation Error and Its Bounds For the bandlimited signal
To obtain an upper bound that decreases faster with N than that of (130), they [54] considered a “self truncating” sam
1584
PROCEEDINGS OF THE IEEE, VOL.
6 5 , NO. 1 1 , NOVEMBER 1977
pling expansion
4
with its Nth partial sum fN and the corresponding truncation error & ( t ) = f ( t )  f N ( t ) . With the choice of m in (134) to equal approximately the optimum value (Nqn)/e they gave a new upper bound:
I
I
I
I
0.2
0.4
0.6
0.8
10 .
r
Fig. 4. R : Ratio of Brown’s truncation bound t o Yao and Thomas’
IgT(t)l < 1.48M(qN1.74)’/2(3.2)qN. (135)
bound.’
of was given by Yao and Thomas To compare this upper bound to that in (1 30) they considered tighter bound than that (1 33) [551 with If(r)l < M for all t , 0 < r < 1: the samevaluesof the last example to .find that for (1 35) IbT(t)l< 6.8 X M , which is 1/100 as large as thebound of (1 30). When they considered the truncation error for the sampling expansion with the function and its first derivative the bound was the same as that of & T ( t ) in (130). However, when they which they extended to the case of sampling signals f ( t 1 , t 2 , used the same series with the selftruncating factor as in (1 34), , t m ) in m dimensions (371, the bound on the truncation error was derived as laT(t1, * * tm)l Q Mlsin2nW1 tll Isin2nWmt,l l&T(t)i < 2.1M(qN0.87)1/2(3.2)24N (136)

.
 
where M and q are defined in (1 30) and m in the “selftruncating series,” of thefunctionandits derivative, isaninteger which is set equal t o approximately the optimum value of m = (2Nqn/e). Forthe same example of &T in (130)the error I & T ~ of (136) is bounded by 8 X lo”. The detailed proofs for (130), (133), (135), and (136) are presentedin 1541 where contourintegration waseffectivelyandelegantlyused asa powerfultool.Theconvolutiontheorem was also employed for deriving the sampling series (134), since its selftruncating P factor is the mthrepeated convolutionof a gate function ~ ( W ) with b = (2qW/m).Petersen [601 also presented a treatment for the truncation error. An upper bound on truncation the error was given by deFrancesco [ 1381. Razyner and Bason [ 1391 used the error formula for Lagrange interpolation [25] to derive an expression for the truncation error bound in terms of the sampling rate and the Nyquist frequency for regular sampling and central interpolation. The usual error formula [ 25 ] for interpolation over N samples of g ( t ) is
and to sampling with the functionand one derivative (42),
When the restriction If(t)l < M is replaced by the condition that f ( t ) has a finite energy E (1 28),i.e., f ( t )E L2 ( m, and m) that f ( f ) is bandlimited t o rW Hz, the bound (1 would be 39)
Brown [ 1401 used real analysis methods t o obtain bounds that have the same asymptotic behavior as that of (142) as N1, N2 + m for F ( w ) E L2(m,m) and F ( o ) E L1(m, m). For the first case of finite energy the error boundwas given as
where g N ( [ ) denotes the Nth derivative at some undetermined 5 in the sample range, t is the interpolation point, and tu are the arbitrary sample locations. In terms of the total energy E and the cutoff frequency W, they derived a bound as (138)
In comparing (143) t o (1421, note that W = (1/2) and that (143) represents an improvement over (142) when r is close to 1. This is clear from the ratioR of the upper boundsof (143) and (142),

for samples at regular equal intervals h in equal numbers on either side of theinterpolationpoint.Inorderthatthisinterupperbound of (143) polation converges, it is sufficient t o have h < (l/nW) which R upper bound of (142) requires approximately a 50 percent faster sampling rate than that required by the sampling theoremwith h < (1/2W). A and Fig.4.
.
G
(144)
JERRI:
A
SAMPLING THEORY:
REVIEW
1585
For the second case of F(w)E L 1 (nr, m), i.e.,
rnr
For It1 < (Nnla), hepresented the following boundandattributed i t t oJagerman [ 143, Theorem 1.] :
where It1 Q
3 and
co=ln 1 m
[
1 +sin
1  sin
g
+ ( N  m)']
54)
(1
Later Papoulis [ 1441 used some of his results t o show that for a signal with finite energy E the maximum of truncation the is bounded by the mepsquare valueof the error q ( w ) (147) error resulting i approximately elwr by Fourier n truncated a series,
Piper [ 141] used real analysis methods t o derive a truncation error bound for finite energy signals that are bandlimited t o
E
(m, nr):
(148) for any
t . Then when we expand and use Parseval's equation,
I&T(t+7)l2GE
where m is the nearest integer to t and I t 1 <N. This represents animprovement over the bound (142) ofYao andThomas [55] for 0.73 < r < 1 and that (143) of Brown [ 1401 for all valuesof r. A tighter error bound than that o Helms and f Thomas [ 541 was derived by Hagenauer [ 1421. He considered . the truncated sampling series
W ) +N,
Inl>N
[
sin (UT
 nn) . ((17nn)
]
(156)
In terms of the energy of such error, E, = J= I&T(r)12 d t , the bound is
lbT(7)12
fN,,N,(t) =
f($)
n =K(r) N,
sin (wot  nn)
(oar  nn)
(1 49)
G2 n lnl>~
sin2 u ( 7  nT)
a 2 ( 7  nT12
.
(157)
with oor/nfactor
4 < K ( t ) < wot/n+ +,then used aselftruncating
Jn+112(6wot)
("O)
For signals with finite power
n
U
6 wot / n
with the sampling series
m
the mean square value of &T is bounded the by v(wAf) of Iq(0)l in (155) :
maximum (159)
IgT(t + 7)l2 < l q ( o M ) 1 2 If(t)12
(oor kn) a
(151)
where the average is withrespect t o t. Inthe derivation of (1 59),Papoulis commented that thesampling expansion
00
where 0 <6 < 1, (2n + l)!! = (2n + 1)(2n  1)(2n  3) * * 3 * 1 and Jn+l12is the Bessel function of the first kind of order n + (1/2). We note that this selftruncating factor is similar t o that used in (134) with 6 = 4 and 00 = 2W. The bound on the truncation error &T = f ( t ) fN,,N, given as was
Sin (UT  nn)
f(r+T)=
n=m
f(t+?)
(a7 
nn)
(160)
used is not valid in general for finite powersignals; however, he showed that itholds in the following mean square sense
T=where Cn,k = ($) (k + n ) ! / n ! . l o ] presented and proved the truncation the error for formally of (1 by 26)
l&T(t)l
n
(161)
U
bound
a
lsin at1
Inl>N It
c
f(nn/a)
 (nn/a)I'
53) (1
where 1i.m. stands for "limit in the mean." He then remarked that results such [ 1441 be can extended to stochastic processes replacing time averages by expected values [69], [ 9 l ] . He also extended similar results to two dimensions and Hankel transforms and then related such results t o the uncertainty principle in one and two dimensions [ 145I .
1586
PROCEEDINGS OF THE IEEE, VOL. 65, NO. 11,
NOVEMBER 1977
Mendelovicz and Sherman [ 1461 used a generalization of Papoulis’s approach [ 1451 to give a least upper bound (1.u.b.) on the truncation error for energy bounded bandlimited functions. This was done for the WKS sampling expansion (125) and the selftruncating series (134).They also treatedthe problem of finding an optimum sampling function that minimizes the truncation error. These results compared very favorably withthose of Yao and Thomas [55] andBrown [ 1401 especially when sampling above the Nyquist rate. They concluded that a few percent oversampling gives a significant improvement in errorperformance. In comparison with the cardinal series which converges slowly but is best atthe Nyquist rate, they suggested other series for over sampling that may converge faster. Later Mendelovicz, Sherman, and Murphy [ 1471 presented a more detailed treatment where they considered both stochasticand deterministic signals. Jagerman [ 1431 presented various estimates for the truncation error under some appropriate constraints on the signal f0 )
integer satisfying v  1 < [ u ] 2 v. Jagerman [ 1431 also gave an estimate of the truncation error in terms of the 1.u.b. of the sampling series error
His estimate for 0 < q < 1, v = (nq/e)(N+ (1/2)), N 2 1, m = IvD + 2, It1 2 (n/2a),and f(x) having radian bandwidth (1 6 ) a is
The estimate in (1 54) is one of his first theorems for f ( t ) E L z (  0 w). A corollary to this theorem is the specialcase 0 , when It1 f n/2a
(163) With the different condition t k f ( t ) E L z (  w , integer, N 2 1, he gave the following estimate
w),
k positive
Other estimates including when the conditions of both (164) and (1 70) met were also presented. are The most recent treatmentof the truncation error, for deterministic functions aswellaswidesense stationary processes, was presented by Beutler [ 1481. In contrast to other methods, his method depends on the use of the Dirichlet kernel representation for the truncated series and on properties of functions of bounded variation. Other integral kernels werealso employed. It is known that the truncated series for functions f ( t ) withabsolutely integrable Fouriertransform is slowly convergent [ 1411. As we indicated earlier, bounds for such functions were found [55] , [ 1401, [ 1431 provided that there is a guard band 6 , i.e.,provided that the Fourier transform F(w) of f ( t ) is supported on [n + 6 , n  61. Beutler [ 1481 showed that a similar upper bound can be obtained without the guard requirement which he replaced by requiring that the Fouriertransform of f ( t ) be of bounded variation in the neighborhood of  n and n. I ) Truncation Errorforthe Generalized WKSW Sampling Expansion: Aswe mentioned in Section V C , Yao [ 131] was the first to give an upper bound for the truncation error the of considered this generalized WKSK sampling expansion. He and other expansions as a realization of his abstract RKHS of functions f ( t )and the reproducing kernel K(s, t ) defined on a set T (see Section VC),
f(t) =
f(tn)$n(t, fn).
nE I
where h = (n/a)and
Ek =
(171)
[: I
1’2
tzklf(t)lzdt]
.
(165)
An immediate consequence of (1 64) is the special case for It1 2 (n/2a):
Here $ n ( t , t nis a sampling function where $i(ti, fj) = 6i,j and ) the series (1 7 1) is uniformly convergent for all t E T. He considered the partial sum f o ( t )of (171) with a finite number of terms Z‘, as a proper subset of Z, and showed that the truncation error E;rT(t) =f(t)  f o ( t ) =
nE(I1’)
f ( t n ) $ n (t tn, )
(172)
It1
< _If_. 2a
(166)
is bounded as
8 T ( t ) (135) of the HelmsThomas For the truncation error “self truncating series” (134) (with a = 2nW) the estimate for I1 2 (n/2a)is t
laT(t)l2 E nEI’
[
c~fz(~n)ll’z *[
nE(I1’)
ciKZ(t,t n )
f E H “ (173)
rz
,
for any f E H” where HI’ = { f H : l l f l l : 5 E } , i.e., finite energysignals.Here the constants cn are defined as c n f ( t n )= (f, &), n EZ’,where fo is anelement of smallest norm where 0 < q < 1, v = (nq/e) (N  (1/2)), N 2 1, rn = Uvll + 1 ; satisfying f(x) has radian band width (1  4)a and S = l.u.b.,<,<, (fo,dn) = bn, n 1‘ 74) (1 f(nn/a). Here [ v ] l is the integral part of u, i.e., it is the unique
JERRI: SHANNON SAMPLING THEORY: A REVIEW
1587
{ b f l , n E I f } are fixed constants, {&, n E I } is a complete orthonormalset for the finite energy functions, and Jln(t, n ) = t c,&(t, t n ) = c i K(t, t n ) . In the case of the Shannon (WKS) sampling expansion,
m
f(t) =
n=m
f(n)
sin n(t  n )
(174)
sampling expansion. In this section we will present estimates forthe aliasing error for bandlimited bandpass functions and for thegeneralized WKSK sampling theorem. In their review paper for error problems in sampling representation, Thomas, and Liu [ 1351 showed thatthe meansquare aliasing error is equal to twice the spectral power outside the Nyquist range Io1> 2nW:
n(t  n )
he considered only I' = { n o ( t )  M < n < n o ( t ) + N} terms where n o ( t ) is the nearest integer to t and M and N are positive integers. The truncation erroris
E [ ( f  fJ
1
'J
@ff(o) d o
Iwl>2nW
(182)
where E stands for expectation value and @ff is the power spectral density of f ( t ) . However when an optimum prefilter is used then the meansquare aliasing error is reduced to one half of the error without prefiltering (182). In the deviation of (182), the sample for fs(r) was taken at ( n / 2 W )  CY where and the upper bound was given for finite energy functions f as a is uniformlydistributedinthe interval [0, (1/2W)I.The phase averaging process resulted in a widesense stationary process. Brown [ 1491 considered the samples at ( n / 2 W ) and showed that the meansquare error is less than or equal to twice that of (182). He also added that his result cannot be improved without additional processing such as the above random phase averaging or prefiltering. It is clear that unless the signal is bandlimited to (2nW, 2nW) there will always be an where aliasing error when we sample at the required Nyquist rate. So if there is any alias free sampling it must be based on a rate n0(2)+N+1,differentfromthat of the Nyquist rateorinother words f 2 ( n )< E <=. (1 77) Eo= n=,no(t)+Ml sampling at unequally spaced instants of time. To develop an alias free sampling, Shapiro and Silverman [ 1501 found condiThe limits of the summations (1 75) and (1 77) are thoseof tions on the sampling instants. They showed that various I  z'. schemes with randomly chosen sampling instants satisfy these 2 ) Truncation Error f o r BandLimited Distributions (Generconditions. This problem was later treated by Beutler [ 15 11. alized Functions: Campbell [ 1OS] established a bound for the Weiss [ 1521 considered the aliasing error resulting from truncation error applying the sampling theorem to a function even when it is not bandlimited, i.e., when F(w) does differ from zero for 101 > a. For F(w) E L 1(=, =), F ( o ) = F(w), of bounded variation and 2 F ( o ) = F ( o + 0) + F ( w  0), let f s ( t ) be the (178) sampling series (125) with samples f ( n n / a ) of the nonbandlimited function f ( t ) . Weiss gave an upper bound forthe for the sampling expansion (78) of bandlimited generalized aliasing error as functions(distributions).For f, g , S, q , 52 as in Theorem IVG1, let r be an integer and b a number such that If(t)l 5 IEA = If(t)  f$(t)l5 I F ( w ) l d o . (183) bltl' for It1 > (Nn/a). Also let j be an integer greater than r and let Papoulis [ 1101 derived an upper bound for the aliasing error cj = 4(9)j' [ ( j  l)!]2(2j)!j'12n3~ZbK(179) in terms of the area of the spectrum EA (0) such an error of where
[
o
K' =
Let 0 5 lati < Nn. Then the estimate for the bound of the truncation error&;T(t)of (1 78)is
I,
1
exp (xz  1)' d x .
B=
IEA (
~ ) ld
(184)
(180) as
IEA(f)l G
B 5lsin at1
(185)
B. The Aliasing Error and its Bounds In practice, the signals that we deal with are not necessarily bandlimited in the sense required by the Shannon sampling expansion. The aliasing error EA ( t ) = f ( t )  fJt) is the result from applying the sampling theoremrepresentation f s ( t ) to signals f(t) with samples f ( n n / a )even when they are notbandlimited or bandlimited to different limits than those us&d in
where the upper bound can be attained. Brown [ 1531 showed ut that the f s of the fourW e b conditions, i.e., F(w)E L 1 (OD, 00))is sufficient for thevalidity of (183) with the estimateas
r m
Aswe have indicated in Section VA, Boas [ 1281 used the Poisson summation formula to derive the sampling expansion and the above two estimatesof Weiss [ 1521 and Brown [ 1531
1588
PROCEEDINGS OF
THE IEEE, VOL. 6 5 , NO. 1 1 , NOVEMBER
1977
The amplitude error is caused by the uncertainty in thesample values due to either quantization or to some fluctuation where the roundoff error may be considered as a special case. The jitter error results from sampling a t instants tn = nT + 7, which differ in a random fashion by 7, from the required If ( t ) f s ( t ) l G 2 IFWI d o (187) Nyquistsamplinginstants nT. As it turnedout [ 1351 the L Z B P jitter and amplitude errors are related and require very similar where f , is the sampling series (63) with samples of f ( t ) . He theoretical treatments. Thomas andLiu [ 1351 gave a thorough concluded and proved [ 1531, [ 1541 that the constant multi review of both subjects with a summary of the original work [ 1581, Lloyd and MacMillan [ 1591, Stewart ple in (186) and (187) cannot be reduced further and so the byFranklin [ 1601, Spilker [ 16 1 Chang [ 1621, Brown [ 1631, Middleton 1, crude estimate (1 87) is a very good estimate of aliasing error for almost all values o f t except those for whicht is a sampling and Petersen [ 1641, and Ruchkin [ 1651, on the amplitude [ 1501, Balakrishnan[ 69 I , error, and by Shapiro and Silverman point of the form (nn/a). Standish [ 1551 showed thata [ 1661, Brown [ 1671, and Brown and Palermo [ 1681 on the bound of the form jitter problem.Middleton [ 12, ch. 41treated various sampling proceduresincluding the “jittered” samples. Papoulis IaA(t)l g a ( t ) IF(W)12 d o , OO < t < (188) [ 1101 also gave asimpletreatment of thejitter and the roundoff error where he utilized someextensions of the TVI. In theorem which we presented Section in with a ( t ) independent of f and bounded cannot hold for all sampling 00)). Stickler [ 1561 this section, wewill present the bounds of both errors that signals of finite energy (F(w)E L ~ (   o o , reported the same bound as Weiss (183) without reference to were developed by Papoulis and refer the reader to the above Weiss’s result and then derived a tighter but cumbersome references and in particular [ 1351. In his study of the error analysis for the sampling theorem bound Papoulis [ 1 101 applied (94)
for the aliasing error. Brown then considered the same aliasing error for the sampling expansion of bandpass functions (63) [ 12, p. 2161, where again F(w) does not necessarily vanish outside the bandpass interval 1 ~ as in (63). The bound on p this error is
C. The Jitter, RoundOff,and Other Errors
JU,,.
where where w2 E ( n / T ) and w2 2 2wl (instead of w2 2 w 1 in the case for f ( t ) ) and w o is such that 2wl < w o G 2w2  2wl, to the roundoff error
h ( x ) = smallest integer 2 1x1 and sgn x =
Then he gave a bound for the aliasing error whenf ( t ) is bandlimited but with alarger band oothan a , Le., wo>a:
c
1, x > o 1, x < o .
where A n T ) is the recorded or tabulated sampled values which , . differ from the exactsampled values by E Using the cardinal series (92) with wo = w1 and sampled values R n T ) he constructed the function f r ( t ) , which differs from f ( t ) by the total roundoff error a,(t). Combined with the above results in (94) he showed that this error &,(t) is bounded by its own total energy E,; that is,
which he compared thatgiven by Papoulis(1 85) to
with the comment that (189) or (191) is more usefid than (1 85) for some cases. The aliasing error bounds (1 83) and (1 87) were extended by Mehta [ 1571 to the case of the generalized WKSK sampling theorem for its deviation from “the generalized” bandlimited and bandpass functions,respectively,
IZA(t)l
Papoulis then considered thejitter problem,which arises when the sample values are not exactly at the sampling points nT but are at some other instants nT  u,, where {u,} is the set of deviations of the sampling points from nT. He considered
G2a
2a
lez
Lensp
IF(W)l d o
(192) (193) to be bandlimited, using (93). Higgins [ 1691 presented two series representationsforanerror free reconstruction of a bandlimited finite energy signal from its irregularly spaced or “jittered”samples.The basic theoreticaltreatmentforthis problem was developed by Beutler [ 9 1 , [ 941 . ] Knab and Schwartz [ 1701 considered the truncation error 8~ combined with channel error 8, which is caused by uncor
lsA(t)l
IF(Nl d o
where I is the interval on which {K(w,t,)} are orthogonal, as in (19), R is the bandpass region as in (65). Mehta took a = IK(w, t)l for all real w but it would be more practical to take a = max IR(w,r)l, which doesnot affect his derivation.
JERRI: SHANNON SAMPLING THEORY: A REVIEW
1589
related noise samples. Let the bandlimited signal f(t), with band limit W O , bounded by M and with a Fourier transform of bounded variation be corrupted with zeromean additive noise samples Ek of variance u 2 that are uncorrelated. They used a truncated sampling series to approximate f ( t ) in the interval I t 1 < ( ~ / 2as R t ) : )
sidered the simple constructed function f(t) = 0 with uncorWhen these sample rupted samples { f ( n ) = 0, n = 1 , 2 , * values f ( n ) were corrupted by the specific noise samples h ( n ) of
e } .
h ( t )=
b’I4 sin [(n e ) ( b + t ) ] , n(b + t )
b >O
(202)
they became { f ( n ) + h ( n ) = h ( n ) } . For this noise (202) it is easy to show that where 8 ( t ) is a “selftruncating” sampling function as in (134) with q = 1  6 and a = W O . The reconstruction meansquare error E18(t)12 is found as as the arbitrary b approaches which becomes unbounded infinity which makes such sampling unstable. Landau [ 173I considered the WKS sampling theorem and used the P a r s e d equation (1 02) on (4) whereby
+ [&4t)12.(199)
The error bound t < TI2 as
for such combined errors was found for all
where m is as in (1 34). Knab [ 171] derived an error bound using Lagrange polynomials forinterpolation and extrapolation of finitepower bandlimited signals. He compared this bound to that derived byHelms and Thomas [54] for the selftruncating sampling series (1 34). He also noted that extrapolation is possible with his series while it is not the case with (134). However, the Lagrange extrapolationmethod is not numerically stable as the channel error becomes large very fast with N,the number of terms in the series. Ericson [ 1721 presentedthe sampling series for signals which are not necessarily bandlimited and where the samples are subject to distortionbefore beingused for signal reconstruction. He considered a stationary timecontinuous process x ( t ) whose spectral density(which is assumed to be integrable) is zero outside a more general frequency set than the bandlimit interval.
D. Conditions for a Stable Sampling Expansion As it is the case of the solutionsof many problems in applied mathematics, we always seek a stable solution in the sense (of Hadamard)thata small errorin theinputproduces a correspondingly small error in the output or in other words the output depends continuously on the input. Yao and Thomas [93 I considered the stability of the sampling expansion in the sense that a small error in reading the sample values produces onlyacorrespondingly small errorin the recovered signal. They gave a condition for a stable sampling that “for a bandlimited function g ( t ) to possess a stable sampling expansion with respect to a class of sampling sequence { t n ) there must exist a positive finite absolute constantC (C is independent of f(t) and {tn ) ), such that
and gave the following interesting interpretation as it relates the Nyquist rate with the stability of the sampling expansion. f 2 ( t ) d t < 00, 1) Every signal f(t) of f f i t e energy, i.e., and bandwidth W(Hz) may be completely recovered in a simple way, from the knowledge of its samples taken at the Nyquist rate of 2 per second. Moreover, the recovery is W stable, in the sense of Yao and Thomas (or Hadamard), such that a small error in reading sample values produces only a correspondingly small error in the recovered signal. 2) Every squaresummable sequence of numbersmay be transmitted at the rate of 2W per second over an ideal channel of bandwidth W(Hz) by being represented as the samples of an easily constructed bandlimited signal of finite energy. In relation to the required Nyquist rate for the transmitted sequence of samples or the recovered ones, Landau considered other confiiations, besides the bandlimited finite energy signals,in thehope of improving such rates. This included moving to differently chosen sampling instants or to bandpass or multiband (rather than bandlimited) signals. Emphasizing that only stable sampling is meaningful in practice, he proved the following two very sharp and useful results. 1) Stable sampling cannot be performed at a lower rate than the Nyquist rate. 2) Data cannot be transmitted as samples at a rate higher than the Nyquist rate regardless of the location of sampling instants, the nature of the set of frequencies which the signal occupy, or the methodof construction. These results also apply to bounded signalsbesides finite energy signals.
WI. O T H E R APPLICATIONS THESAMPLING THEOREMS OF In t i chapter we will discuss a number of applications of hs
the WKS and the generalized WKSK sampling theoremsin other fields besides the usual communicationstheory.The latter applications of the sampling theorems are found in most I texts [ 1 1  [ 17I , research papers in information theory, and, in particular [ 131, [ 141.
A . Optics and Crystallography Barakat [ 1741 presented a direct application the sampling of theorem to optical diffraction theory as a computational tool
For an example of an unstable sample expansion, they con
1590
PROCEEDINGS OF THE IEEE, VOL. 6 5 , NO. 1 1 , NOVEMBER I977
and credited Gabor [ 1751 and others for pioneering the introduction of the sampling theorem concept in optics. He developed formulas, in terms of sampled values of the point spread function for the transform function, total illuminance, line spread function, and cumulative line spread function. Then he presented a theory for general point spread functions for slit and square aperture, where the WKS sampling theorems in one and two dimensions are used, respectively. For circular apertures with rotationally symmetric point spread functions, the onedimensional generalized WKSK sampling theorem, associated with the JoBessel function, was used instead of the twodimensional WKS sampling theorem. This, of course, is an advantage of the generalized WKSK, as we pointed out in Section 111B, in general, with circular symmetry, a J(m,2)lHankel transform is equivalent to an rndimensional Fourier transform [see (2911. As an example, the transfer function T ( w ) and thepoint spread function t ( u ) for a slit aperture are related by a bandlimited Fourier transform
t(u) =
3
l
T ( W ) e i u w dw
(205)
where the factor (1/2) enters in order that t ( 0 )be unity for a perfect system. Using the WKS sampling theorem, the point spread function t ( u ) can bewritten in terms of its discrete measured values t(n77/2) as
sampling circles instead of sampling points. This implies that an integration of a function over a given circle is used instead of the value of the function at a given point. We may remark that such polar coordinate sampling is a combination of the WKS sampling in 6 with exponentialkernel and the WKSK sampling in p with kernel as Bessel function. Blaiek mentioned as an example a radiotelescope with circular symmetric transfer function. This makes use of the sampling theorem as a tool to solve system analysis problemsfrom the point of view of transmission of pictorial information. Marks, Walkup, and Hazler [ 1871 developed a sampling expansion whichis applicable to the class of linear spacevariant systems characterized by sufficiently slowlyvarying linespread functions. They showed that the desired sampling rate is determined by both the system and the input and that the corresponding output is bandlimited. McDonnell [ 1881 introduced the “linesegmentlimited” function for image restoration where the emphasis is on the samples themselves and the continuouslyrestored image obtained by the usual sampling expansion. This is in contrast the with usual samplingseries where these samples are convolved with the the restored image. In sampling function to reconstruct avoiding the usual sampling function, he showed that sampling can be performed at a rate lower than the Nyquist rate. These results were extended to two dimensions. 1) Crystallography: Brillouin [189,p. 1051 presented the WKS samplingseries and Fourier methods for analyzing periodic crystal structures. He considered the electron density F G ) as periodicjn :he t h y e dimensions with the correspond, ing translations d l , d 2 and d 3 :
F(?+pJ1 +pJz +p323)=F(?) (207) Som [ 1761 used the twodimensional WKS sampling theorem p in the frequency domain for a coherent optical processor to where ?is the vector ( x l , x 2 , x 3 ) ; p lzr, and p3 are positive or negative integers. The Fourier series for F ( ? ) is obtain multiple reproduction ofspacedlimited functionsin two dimensions. This approach was backed by an experiment F ( x l , x 2 , X 3 ) = c Ch,h,h3 where it was found that the relative separation and the relative h,h,,h, brightness of the multiple reproductions of a given input func. e 2 n i ( h l b l x l + h , b , x , + h , b , x , ) (208) tion can be quantitatively controlled by simply choosing an appropriate sampling function. An early application of the sampling theorem in opticis is F(x1,x2,x3) dueto diFrancia [ 1771 where he used the WKS sampling Chlh,h3 = ’ p vd o expansion to compute the number of degrees of freedom of an * e2ni(h1b1x1+h2b2x~+h3b3x3) d x l d x 2 d x 3 (209) image. He then extended the analysis to antenna theory [ 1781.GoriandGuattari [ 1791[ 1811 used nonuniform sampling in the analysis of holographic restoration and optical where V d = l / b l b z b 3 , the volume of the fundamental lattice. processing. Various applications of the sampling theorem in Brillouin then turned to the Fourier series of the autocorrelaoptics were made by Lohmann [ 1821. Another related appli tion of F ( ? ) or what is called the Patterson function [ 1891, cation in the general field of Fourier spectroscopy is due to Vanasse and Sakai [ 1831. P ( u l , u Z , u 3 ) =  /”’ J g d z J d 3 F ( x , + U l , x2 vd O Hopper [ 1841 utilized the Ndimensional sampling theorem for wavenumberlimited functions with examples of the two+ ~ 2 , ~ 3 + U ~ ) F ( X I ,dxzdx3 X ~ ) ~ X ~ X ~ , (210) dimensional case for coherent optical systems. In particular, in the case of computer generation and construction of holo whose Fourier coefficients are the intensities grams, sampling must be done in space and, hence, it is of advantage to use the most efficient sampling in two dimensions as presented by Petersen and Middleton [ 6 11 and Miakawa and [59]. Instead of the twodimensional sampling in Cartesian u3 lChlh,h31Z coordinates ( x ,y ) , Blaiek [ 1851, [ 1861 considered the ) = p ( u l , u 2 , hl,h,,h, sampling theorem in polar coordinates ( p , 6) to find the number of spatial degrees of freedom of optical wave fields at e 2ni(h1b1u1+h,b2tc2+h~b3u3). (21 1) the output of optical systems with circular symmetric aperhs tures of various shapes. The difference between this sampling T i is a Fourier series analysis whereby the autocorrelation of and that of the WKS sampling is that the former is based on the electron density is determined in terms of the measured
ldz ld3
e
JERRI: SHANNON SAMPLING THEORY: A REVIEW
1591
samples of the intensity ICh,h,h, 1’ where we don’t seem to which led to the powerful tool of the fast Fourier transform find the explicit use of the sampling theorem except in Bril (FFT) algorithm. Petersen [ 1941 employed the WKS sampling discrete transform and FFTfor Nlouin’s other information theoretic discussions. To apply the theorem [53]forthe sampling theorem it is tempting to recognize the intensity as dimensional lattices. As we mentioned in Section 111D, it wehave attempted to employ the the square of a bandlimited functioninthree dimensions is in thisdirectionthat (209) where an extension of Papoulis’s [ 141 sampling expan generalized WKSK sampling theorem for determining the sion (94) for f 2 ( t ) to three dimensions may be used to inter spacing of general discrete transforms associated with classical polate the discrete values of the intensity ( C h ,h,h, I ’. Since orthogonal polynomials [43] and the Bessel functions [44]. ( h l , h z , h determines the direction in which the intensity is g) measured, it seemspossible, for some physical reasons, that C. The Sampling Series and the Hill Functions (BSplines) measurements cannot be done atsome angles and, hence, there As we have briefly indicated in Section VIA, the hill funcis a gap or nonuniform samples which can be treated by the tion $IR+ (a(R + l ) , W) of order R + 1 is defined as the Rthmethods of Section IVD. fold Fourierconvolubon of the gate function p , ( o ) $1 (a, Some related applications of the sampling theorems were ) made by Frank [ 1901 then Frank and Ali [ 191I in the area a . Hence, it is the Fourier transform of [(2 sin at)/(t)] R + 1 which can be recognized as related to the sampling function of radiation damage caused by the electrons used for imaging in theelectron microscope. Earlier, Frank [ 1921 presented for sampling with R derivatives (43) or the factor for theselfa detailed review for computer processing of electron truncating series (134) which improved the error bound for the truncation error (1 35). This function was also used [ 195I micrographs. as a selftruncating Fourier coefficient for efficient evaluation of the hl function of higher order il B. TimeVarying Systems, Boundary Value Problems, and Discrete Fourier and Other Transforms 1 ) TimeVaryingSystems: TheShannon sampling theorem with its bandlimited Fourier transform and the simple convolution translation is a natural tool for the analysis of timenlr invarying systems. Timevarying systems are also analyzed . cos a(R + 1) < w < a(R + 1) (212) a(R + 1)’ using Fourier transform as evident in the work of Zadeh [39] and others, however, we emphasize here a timevarying system ( 1))= is the where a0 = ( ( 2 ~ ) ~ + ~ ) / + a ( R 20 $ R + ~and with a generalized convolution translation [36] which is average value of $R + (w) over the interval [  a @ + l ) , a(R + associated with the generalized integral transforms of the 1). In (21 2) we note the simple form of the coefficients and WKSK sampling theorem.In Section 111C we attempted to their advantage in making the series a selftruncating one for give an applied interpretation of this generalized WKSK large R. A very thorough treatment of the sampling expansion theorem in terms of a timevarying impulse response. In Sec (cardinal interpolation) and spline functions is given by tion IVH we discussed the WKS sampling theorem, using the Schoenberg [ 1331. The above discussion is exclusive for the Fourier transform, with but timevarying bands [ 1091. WKS sampling theorem and its very familiar tool the Fourier Siastnjr [ 1931 considered the reconstruction of timevarying transform. A of yet no mention is made of some “valuable s signals with particular emphasis on the distortion which arises function” like the spline function which can be defined as the during such restoration. He employed the sampling expansion Rthfold general transform convolution [ 361 and which may for bandpass functions and derived a dependence of the distor play the role of improving the error bound for the truncation tion on the sampling frequency which is valid for stationary error of the generalized WKSK sampling theorem. Gaussian random signals and fordeterministic signals with continuous spectrum having a low frequency character. In Section 111D we discussed the possibility of replacing the m D. Special Functions The subject of ti section is varied as we can see that the hs dimensional Fourier transform of functions with circular symmetry by a onedimensional J ( m p  Hankel transform where generalized WKSK sampling theorem is anextension of the the WKSK sampling theorem can be used. This may relate to simple exponential function, as the kernel of Fourier transspatialvarying problems where, in the caseof polar coordi form, to other functions; as solutions of nthorder selfadjoint differential equations, for the kernel of more general integral nates, the sampling is done on circles instead of at points. 2 ) Boundary Value Problems: In Section 111D we discussed transforms. In Section 111B wehave already shown the conequivalence between the Fourier and other how the generalized WKSK sampling theorem was used [42] ditionsforthe to facilitate the study of the effect of the axial heat conduc transforms and, hence, thetwo sampling theorems. In partion on the temperature field for a fluid with laminar flow in ticular, it is known that the sampling functions {(sin (at  nn))/ a tube. This development can still be extended to problems (at  nlr)} which are bandlimited to (  a , a ) are orthogonal on which require matching boundary conditions and uses general (m,m) and we have shown [ 361 that the generalized sampling orthogonal expansion. For example, in the case of a spherical functions { S ( t , t , ) ) of (21) are also orthogonal on theinterval geometry, associated Legendre polynomials or spherical Bessel used for the integral transform inverse (31). This shows that function expansions may used. be In the simple case of the general Fouriertype transforms(30),(31) presene orthoglaminar flow between plates, the Cartisian coordinates are used onality since { K ( x , t , ) } in (2 1) isan orthogonal set and so is and, hence, a finite Fourier transform and its Shannon’s its transform ( S ( t , t n ) } . Some of the following results sampling theorem may be employed. relating bandlimited functions to the transform of some 3) Discrete Fourierand Other Transforms: The role of the special functions areclosely related to the above treatments. Yao and Thomas [ 1961 noted that (sin t ) / ( t ) is a bandWKS sampling theorem is very evident [45], [46] in determining the required spacing of the discrete Fourier transform limited function of the gate function p,(w) which is a poly
1592
PROCEEDINGS OF THE IEEE, VOL. 65, NO. 11, NOVEMBER 1977
nomial of order zero on ( 1 , 1). This is the same for the prolate spheroidal functions [ 27 ], which are also bandlimited and have been used extensively for approximating bandlimited signals. They showed that a more general frequency function, instead of the gate function, bandlimited to ( 1, 1) can be obtained by orthogonalizing the polynomials 1, a,o’, * * * with respect to the weighting function p(o) using the GramSchmidt process. Such functions are the weighted Jacobi polynomials which are complete in L z (  1 , 1) and are also solutions of secondorder selfadjoint differential equations [27]. The time functions as the inverse Fourier transform of thesefunctions arewellknownspecial functions which are also orthogonal [261 on (m, 00). Some of the special cases that they exhibited are the Gegenbauer, the Legendre, and the Tchebyschev polynomials. Mehta [ 197 J considered the same problem for other examples like the associated Legendre polynomials and the prolatespheroidal functions. One of the simplest applications of the WKS sampling theorem is in establishing a relation between the continuous special function and its discrete or sample values. For example, from Titchmarsh [ 198, p. 1861 we have the following bandlimited function representation fora certain combination of gamma functions of x
and developed error bounds resulting from the simplification of a mathematical model for thecardiac pacemaker. A seemingly far removed application is that of sampling the fractional derivative (dOL)/(dta) f ( t ) g ( t ) (Leibnitz rulea not necessarily an integer) [203] of the product of two functions f ( t ) g ( t ) in terms of its samples, the usual nth derivatives ( d n ) / ( d r n ) ( t ) g ( t ) . We remark here that such sampling may f also be attempted for thefractional integrals [ 2041.
ACKNOWLEDGMENT
The author wishes to express his thanks to the members of their the editorial board of the IEEE PROCEEDINGS for encouragement and to the three referees for their very constructive and helpful remarks and suggestions. This paper could not have been as complete without the generous contributions of most researchers in the field by supplying the author with their uptodate results or some other results that he had overlooked. The author is also grateful to Prof. A . C. Newell and Dean B. A. Pethica, of Clarkson College of Technology, Potsdam, NY,for their encouragement and support, to his students for the interest theyshowed in the subject,and to Mrs. D. Mein for typing the manuscript.
REFERENCES C. E. Shannon,“Communications in the presence ofnoise,” P~oc. IRE,vol. 37, pp. 1021, Jan. 1949. H. Nyquist, “Certain topics in telegraph transmission theory,” AIEE Trans., vol. 47, pp. 617644, 1928. E. T. Whittaker, “On the functions which are represented by the expansion of interpolating theory,” Proc. R o y . SOC.Edinburgh, V O ~ .35, pp. 181194, 1915. J. M. Whittaker, “The Fourier theory of the cardinal functions,” Roc. Math. SOC.Edinburgh, vol. 1, pp. 169176, 1929.  Interpolutory , Function Theory. Cambridge, England: Cambridge University Press (Cambridge tracts in Mathematics and Mathematical Physics), 1935, no. 33. W. L. Ferrar, “Ontheconsistency o f cardinal function interpolation,” h c R o y . SOC.Edinburgh, vol. 47, pp. 230242, o.
1927.
a > 1. (213)
We recognize that this is a bandlimited function of x, for which we can immediately write the Shannon sampling series 1 r u a +x)/2)r((a  X
m
1
n=oo
H. S. Black, Modulation Theory.
1953.
New York:
van Nostrand,
a result which apparently is not easily accessible in the literature. Setting a = 2 in (214) leads to the wellknown special
CaSe
1
 sin (n/2)x
IIX
r ( x / 2 ) r ( ~ ( x / 2 ) ) 
V. A. Kotel’nikov, “On the transmission capacity of “ether” and wire in electrocommunications,” (material for the f i i t allunion conference o n questions o f communications) Izd.Red. Up?. SvyaziRKKA (Moscow), 1933. H. P. Kramer, “A generalized sampling theorem,” J . Math. PhyS., V O ~ .38, pp. 6872, 1959. Weiss, “Sampling theorems associated with SturmLiouville Math. Soc., vol. 63, p. 242 (abstract 459), systems,” Bull.
1957.
which is the finite limit Fourier transform of the gate function p(,,p)(t) as in (213) with a = 2. In parallel to the WKS sampling theorem or the Whittaker cardinal series [ 1 1 , [SI, Higgins [ 1991 considered an interpolatory seriesassociated with the WKSK sampling theorem [9 I and in particular theone associated with the Hankel (Bessel) transform. He proved a number of theorems that included basic properties of the WKSK sampling functions [36]. Then he utilized particular cases of his results for special functions expansion which is in parallel to the above expansion (214) of the gamma functions as a WKS sampling series.
F. M. Reza, An IntroductiontoInformationTheory. New York: McGrawHill, 1961. D. Middleton, An Introduction to StatisticalCommunication Theory. New York: McGraw Hill, 1960. A . Papoulis, TheFourier Integral and itsApplications. New York: McGrawNill, 1962. , Systems and Transforms with Applicationsin Optics. New York: McGrawHill, 1968. I. M. Wozencraft and I. M. Jacobs, principles of Communication Engineering. New York: Wiley, 1965. R. B. Ash,Information Theory. New York: Interscience, 1965. S. Goldman,Information Theory. New York: Dover, 1968. B. P. Lathi, Communication Systems. New York: Wiley, 1965. I. Sorneya, Waveform Transmission. Tokyo: Shukyo, Ltd.,
1949.
E. Other Applications Among other applications of the Shannon s a m p h g theorem, Petersen and Middleton utilized the multidimensional sampling theorem [ 5 3 ] , [61] for the analysis of meteorological data [ 2 0 0 ] . Also this sampling expansion [ 531, [61] was referred to by Belyayev [ 201 ] for oceanographic applications. Radzyner [202] employed the nonuniform sampling expansion
J . McNamee, F. Stenger, and L. E. Whitney, ‘Whittakercardinal function in retrospect,” Math. Comput., vol. 25, pp. 141154, Jan. 1971. F. Stegner, “Approximations via Whittaker’s cardinal function,” J. Approx. Theory, vol. 17, no. 3, July 1976. R. E. Edwards, Fourier Series, A Modem Introduction, Vol. I , New York: Holt, Rinehart, and Winston, 1967. I. N.Sneddon, The Use o f Integral Transforms. NewYork: McGrawHill, 1972. D. L. Jagerman and L. Fogel,“Some general aspects o f the sampling theorem,” IRE Trans. Inform. Theory, vol. IT2, pp. 139146, Dec. 1956.
JERRI: SHANNON SAMPLING THEORY: A REVIEW
125) P. J. Davis, Interpolation Approximation. and New York: Blaisdell, 1963. [ ] A. Paleyand N. Wiener, Fourier Transform in Complex .2 6 . R.E. Domain. New York: American Math. Colloq. SOC. Publications, 1934, vol. 19. [ 2 7 ] E. A. Coddingtonand N. Levinson,Theory of OrdinaryDifferential Equations. New York: McGrawHill, 1955. [ 2 8 ] L. L. Campbell, “A comparisonofthe sampling theoremsof Kramer and Whittaker,” J. SIAM, vol. 12, pp. 117130, 1964. (291 A. J . Jerri, “Sampling for not necessarily finite energy signals,” In?. J. System Sei., vol. 4 , no. 2 , pp. 255260, 1973. [ 301 D.Slepianand H. 0. Pollack,“Prolatespheroidalwave functions,Fourier analysis and uncertaintyI,” Bell. Syst. Tech. J . , VOI. 4 0 , pp. 4364, 1961. [ 311 A. J. Jerri, “On the application of some interpolating functions Stands. B. Math. Sciences, vol. in physics,” J. Res.Nut.Bur. 73B, no. 3, pp. 241245, Sept. 1969. [ 3 2 ] , “Samplingexpansion fortheLELaguerreintegraltransform,” J. Research of Nut. Bur. Stands. B. Math.Sciences, vol. SOB, pp. 415418, Sept. 1976. [ 3 3 ] A. Erdelyi, et al., Higher Transcendental Functions, vol. 1. New York: McGrawNill, 1953. equivalenceofKramer’sandShannon’s [ 3 4 ] A. J. Jerri,“Onthe samplingtheorems,” IEEE Trans.Inform. Theory, vol.IT15, pp. 497499, July 1969. [ 351 , “Some applications Kramer’s for generalized sampling theorem,” J. Eng. Math., vol. 3, no. 2 , Apr. 1969. [36] , “Application the of sampling theorem to timevarying systems,” J. FranklinInst., vol. 293, no. 4 , pp. 5358, Jan. 1972. [ 371 H. D’Angelo, Linear Time Varying Systems, Analysis and Synthesis. Boston: Allyn and Bacon, 1970. [ 381 K. Yao, “On some representations and sampling expansions for band limited signals,” Ph.D. Thesis, Dept. Elec. of Engng., Princeton University, Princeton, NJ, 1965. [ 3 9 ] L. A. Zadeh,“Ageneraltheory oflinearsignaltransmission systems,” J. Franklin Inst., vol. 253, pp. 293312, 1952. [40] A. H. Zemanian,Generalized Integral Transforms. New York: Interscience, 1968. jplane. New York: Benjamin, (411 R. G. Newton, The Complex 1964. [ 4 2 ] A. J. Jerri and E. J. Davis, “Application of the sampling theorem t o boundary value problems,” 1. Fng. Math., vol. 8 , pp. 18 , Jan. 1974. I431 A. J. Jerri, “The application ofgeneraldiscretetransforms to computing orthogonal series and solving boundary value problems,” submitted. [ 4 4 ] , “Towards a Discrete Bessel Transform,” to appear, J. Applicable Analysis. [ 4 5 ] J. W. Cooley, P. A. W. Lewisand P. D. Welch,“The fiiite Fourier transform,” IEEE Trans. Audio Electroacoust., vol. AV17, no. 2 , pp. 7785, 1969. [ 4 6 ] E. 0. Brigham, The Fast Fourier Transform. Englewood Cliffs, N J : PrenticeHall, 1974. [ 4 7 ] J. W. Cooley and J. W. Tukey, “An Algorithm for the machine calculations of complex Fourier series,” Math. Comput., vol. 19, pp. 297301, 1965. [ 4 8 ] J. W. Cooley, P. A. W.Lewis, and P. D. Welch, “Application of the fast Fourier transform to computation of Fourier integrals, Fourier series, and convolution integrals,” IEEE Trans. Audio Electroacoust., vol. AU15, pp. 7984, 1967. [ 4 9 ] A. J. Jerri and C. J. Reed, “On the generalized translation for the convolution of discreteHankel transform,” submitted. [ S O ] L. Fogel, “A note on the sampling theorem,”IRE Trans., vol. 1, pp. 4748, Mar. 1955. [ 5 1 ] D. A. Linden, “A discussion of sampling theorems,”hoc. IRE, VOI. 47, pp. 12191226, 1959. [ 5 2 ] D. A. Lindenand N. M. Abramson, “A generalization of the sampling theorem,”Znform. Contr., vol. 3, pp. 2631, 1960 (see correction for equation (40), ibid., vol. 4 , pp. 9596, 1961). P. Petersen and D. Middleton,“Reconstructionofmulti[ 5 3 ] D. dimensional stochastic fields from discrete measurements of 1 , pp. 445476, amplitude and gradient,” Inform. Contr., vol. 1964. [ 5 4 ] H. D. Helms and J. B. Thomas, “Truncation error of sampling theoremexpansion,” h o c . IRE, vol. 50, pp. 179184, Feb. 1962. [ 5 5 ] K. Yaoand J. B. Thomas,“Ontruncationerrorfor sampling representations bandlimited of signals,” IEEE Trans. Aero. Electron. Syst., vol. AESQ, Nov. 1966. [ 5 6 ] A. J. and Jerri D. W. Kreisler, “Sampling expansions with derivatives for finite Hankeland other transforms,” SIAM J. Math. Anal., vol. 6 , no. 2 , Apr. 1975. [ 5 7 ] D. W. Kreisler, “Sampling expansion with derivatives for finite Hankel other and transforms,” Ph.D. dissertation, Clarkson College of Technology, Potsdam, NY, 1972.
1593 [SS] E. Parzen,“Asimpleproofandsomeextensionsofsampling 7, theorems,”Stanford University, Stanford, CA,Tech.Rep. 1956. [ 591 H. Miyakawa, “Sampling theorem of stationary stochastic variJ. ables in multidimensional space,” Inst. Elec. Commun. Engrs., Japan,vol. 42, pp. 421427, 1959. “Sampling space/time of stochastic processes [ 6 0 ] D. P. Petersen, with application t o information and decision systems,” D.E.S. dissertation, Rensselaer Polytechnic Institute, Troy, NY, 1963. [ 611 D. P. Petersen and D. Middleton, “Sampling and reconstruction of wave numberlimited function in NdimensionalEuclidean spaces,”Informat. Contr., vol. 5 , pp. 279323, Dec. 1962. 621 W. D. Montgomery, “The gradient in the sampling ofNdimensional bandlimited functions,” J. Electron. Contr., vol. 17, no. 4 , pp. 437447,013. 1964. 631 W. D. Montgomery, “KOrder sampling of Ndimensional bandlimited functions,” Int. J. Contr., vol. 1 , no. 1, pp. 712, Jan. 1965. 641 N. T. Gaarder,“Anoteonmultidimensional sampling theorem,”hoc. IEEE, vol. 60, DD. 247248, Feb. 1972. [ 651 B. D. Sharma and F. C. Mihta, “Generhized bandpass sampling theorem,” submitted. [ 6 6 ] L. Hormander, An Introduction to Complex Analysis in Several Variables. Princeton, NJ: van Nostrand, 1966. [ 6 7 ] R. E. Kahn and B. Liu, “Sampling representation and optimum reconstructionofsignals,” IEEE Trans.Inform.Theory,vol. IT11, pp. 339347, Apr. 1965. [ 6 8 ] D. E. Todd, “Sampled data reconstruction of deterministic band limitedsignals,” IEEE Trans.Inform. Theory, vol. IT19, pp. 809811,Nov. 1973. (691 A. V. Balakrishnan, “A note on the sampling principle for continuous signals,”IRE Trans. Inform. Theory, vol. IT3, pp. 143146, June 1957. 1701 D. P. Petersenand D. Middleton, “Linear interpolation, extra. . polation prediction and of random spacetime with fields limited domain of measurement,” IEEE Trans. Inform. Theory, vol. IT11, no. 1, Jan. 1965. [ 7 1 ] D.P. Petersen, “Linear sequential coding of random spacetime fields,”Inform. Sci., vol. 10, pp. 217241, 1976. [721 D. P. Petersen and D. Middleton, Srochastic Fields and Signals. In preparationtentative MIT Press, Cambridge, MA. (731 S. P. Lloyd, “A sampling theorem for stationary (wide sense) stochastic processes,” Trans. Am. Math. Soc., vol. 92, pp. 112, 1959. “Essentially bandlimited stochastic pro[ 7 4 ] A. V. Balakrishnan, cesses,’’ IEEE Trans. Inform. Theory, vol. IT11, pp. 145156, 1965. “A on perfect predictability and (751 G. B. Lichtenberger, note analytic processes,”IEEE Trans. Inform. Theory, vol. IT20, pp. 101102, 1974. (761 F. J. Beutler, “Recovery of randomly sampled signals by simple interpolators,”Inform. Cone., vol. 2 6 , no. 4 , pp. 312340, Dec. 1974. and 0. A. Z. Leneman,“Random sampling of (771 F. J . Beutler randomprocesses: stationarypoint process,”Inform.Contr., V O ~ .9 , pp. 325346, 1966. [ 7 8 ] 0. A. 2. Leneman,“Random samplingofrandomprocesses: optimum linear interpolation,” J. Franklin Inst., vol. 281, no. 4 , pp. 302314,1966. [ 7 9 ] 0. 2 . Leneman and J . Lewis, “Random sampling of random A. processes: Mean squarecomparisonofvariousinterpolators,” IEEE Trans. Automat. Contr., vol.ACIO,pp. 396403, July 1965. [SO] 0. A. Z. Leneman and J. Lewis, “A note on reconstruction for randomlysampleddata,” IEEE Trans.Automat.Contr.,vol. AC10, p. 6 2 6 , July 1965. [ 8 1 ] 0. A. 2. Leneman and J . Lewis,“Onmeansquarereconstruction error,” IEEE Trans. Automat. Contr., vol. AC11, pp. 324325, Apr. 1966. [ 82 1 R. Barakat, “Nonlinear transformation of stochastic processes of bandlimited positive associated with Fourier transforms functions,”Int. J. Contr.,vol. 14, no. 6 , pp. 11591167, 1971. [ 8 3 ] M. Zakai, “BandLimited functions and the sampling theorem,” Inform. Contr.,vol. 8 , pp. 143158, 1965. I841 Z. A. Piranashvilli, “On the problem of interpolation of random processes,” Theory Prob. Appl., vol. 12, pp. 647657, 1967. (851 W. A. Gardner, “A sampling theorem for nonstationary random processes,” IEEE Trans.Inform. Theory, vol.IT18,pp. 808809, 1972. [ 8 6 ] B. D.Sharma and F. C. Metha, “A generalized sampling theorem for nonstationary processes,” J. Cybernetics, pp. 8795, 1974. (871 J. L. Yen, “On the nonuniform sampling of band width limited signals,” IRE Trans.CircuitTheory, vol.CT3,pp. 251257, Dec. 1956. [ 8 8 ] B. Sankurand L. Gerhardt,“Reconstructionof signals from nonuniform samples,” in IEEE Int. Con$ Commun., Con$ Rec.,
1594
PROCEEDINGS OF THE IEEE, VOL. 6 5 , NO. 1 1 , NOVEMBER 1977 rem and its applications in systemtheory,”Nachrichtentech. Z.,
V o l a 13, pp. 380382, 1963.
pp. 15.1315.18, June 1113, 1973. (891 F. A. Marvastiand L. A. Gerhardt, “Signaltransmission using nonuniformly spaced samplesA general theory,” presented at Information Theory Int. Symp. (sponsored by IEEE and International Union Radio of Science), Ronneby, Sweden, June 2124, 1976. [ 9 0 ] K. Yao and I. B. Thomas, “On a class of nonuniform sampling representation,” in Symp. Signal Trans. Processing, (sponsored by Columbia University), pp. 6975, May 1968. [ 9 1 ] F. E. Beutler, “Sampling theorems and bases in a Hilbert space,” Inform. Contr.,vol.4 , pp. 97117, 1961. [ 9 2 ] 0.A. 2.Leneman, “On errorboundsforjittered sampling,” IEEE Trans. Automat. Contr., vol. AC11, p. 150, Jan. 1966. [ 9 3 ] K. Yao and J. B. Thomas, “On some stability and interpolating properties of nonuniform samplingexpansions,” IEEE Trans. Circuit Theory, vol. CT14, pp. 404408, Dec. 1967. [ 9 4 ] F. J. Beutler,“Errorfreerecoveryof signals from irregularly spaced samples,” SIAM Rev., vol. 8, no. 3, pp. 328335, July 1966. [ 9 5 ] N. Levinson, Gap Density and Theorems, Colloq. Pub. 26, Amer. Math. Soc. New York, 1940. [ 961 J. L. Brown, Jr., “On exact, stable nonuniform sampling expansions,” private communications. [ 971 J. I. Chargin and V. P. Iakovlev, Finite Functions in Physics and Technology. Moscow: Nauka, 1971, (in Russian). [ 9 8 ] A. Kohlenberg, “Exact interpolation of bandlimited functions,” J. Appl. Physics, vol. 2 4 , pp. 14321436, 1953. [ 9 9 ] F. E. Bond and C. R. Cahn, “On sampling the zeroes of band width limitedsignals,” IRE Trans. Inform. Theory, vol. IT4, pp. 110113, 1958. [ l O O ] E. C. Titchmarsh,“Thezerosofcertainintegralfunctions,” R o c . London Math. SOC., 25, pp. 283302, 1926. vol. [ 1 0 1 1 F. E. Bond, C. R. Cahn, and I. C. Hancock, “A relation between zerocrossingsandFouriercoefficients for bandlimited functions,” IRE Trans. Inform. Theory, vol. 6, pp. 5155, 1960. [ 1021 H. Voelker,“Towardaunifiedtheoryofmodulation,” Roc. IEEE, vol. 54, p. 340, 1966. [ 1031 A. Sekey, “A computer simulation study of realzero interpolation,”IEEE Trans. Audio Electroamst., vol. 18, p. 43, 1970. [ 1041 I. BarDavid, “An implicit sampling theorem for bounded band limitedfunctions,” Inform.Contr., vol. 24, pp. 3644, Jan. 1974. 1051 L. L. Campbell, “Sampling theorem for the Fourier transform of a distribution with bounded support,’’ SIAM J. Appl. Math., vol. 16, pp. 626636, 1968. 1061 A. H. Zemanian, Distribution Theory and Transform Analysir. New York: McGrawHill, 1965. 1071 E. P. Pfaffelhuber, “Sampling series for band limited generalized functions,” IEEE Trans. Inform. Theory, vol. IT17, pp. 650654, Nov. 1971. 108) R. E. Edwards, Fourier Series, A Modem Introduction, vol. 2. New York: Holt, Rinehart, andWinston, 1967. forcontinuous signals with 1091 H. Horiuchi,“Samplingprinciple timevarying bands,” Inform. Contr., vol. 13, pp. 5361, July 1968. A. Papoulis, “Error analysis in sampling theory,” Roc. IEEE, vol. 54, no. 7 , pp. 947955, July 1966. A. Papoulis, Signal A ~ l p i s .New York: McGrawHill, 1977. T. Ericson and U. Johansson, “A new approach t o sampling,” Preliminary draft,Linkoping University, Linkoping, Sweden, Rep. LMISY10051, 1974. J. L. Brown, Jr., “Uniformlinearpredictionofbandlimited samples,” IEEE Trans.Inform.Theory, processes from past vol. IT18, Sept. 1972. L. A. Wainstein and V. D. Zubakov, Extraction of SigMLsfrom Noise. Englewood Cliffs, NJ: PrenticeHall, 1962. N. Maeda, “On sampling theorems of bandlimited periodic signals,’’ J. Inst. Electron. Comm. Engrs., Japan, vol. 50, No. 8, pp. 14721473,1967 (in Japanese, English Abstract in Abstracts, p. 25). Y. Isomichi, “Generalized sampling theorem,” Electron. Commun., Japan, vol. 52, no. 2, 1969. A. G. I. Holt, J. J. Hill, and R. Linggard, ‘‘Integral sampling,” R o c . IEEE, vol. 61, pp. 679680,May 1973. G. Kishi and N. Maeda, “Sampling theorems for signals given by linear differential equations constant with coefficients,” Electron. Commun., Japan, vol. 53, no. 4 , pp. 2936, 1970. N. Maeda,“Somerelationsbetweenbandlimitedsignals and signalssatisfied by linear differential equations with constant coefficients,” Trans. Inst. Electron. Comm. Engrs., Japan, vol. 53A, no. 10, pp. 568569, 1970.  “Timelimitationofnetworkresponse,” , Electron.Commun., Japan, vol. 56, no. 6 , pp. 2532, 1973. G. Kishi and N. Maeda, “Stability of signals and its application Electron.Commun., t o approximationofsignalwaveforms,” Japan,vol. 54, no. 7 , pp. 2938, 1971. G. Wunsch, “Concerning a generalization of the sampling tkeo
[ 1 2 3 ] J. B. Kioustelidis,“Error bounds for the samplingtheorem,” Arch. Elec. mertragung, vol. 2 3 , pp. 629630, 1969. I1241 P. L. Butzerand W. Splettstosser,“Asamplingtheoremfor durationlimited functions error with estimates,” Inform. Contr., t o appear. [ 1 2 5 ] J. A. Stuller, “Reconstruction of finite duration signals,”IEEE Trans. Inform Theory,vol. IT18, pp. 667669, Sept. 1972. (1261 H. P. Kramer, “The digital form of operators on bandlimited functions,” J. Math. Anal. Appl., vol. 4 4 , no. 2 , pp. 275287, Nov. 1973. [ 1271 J. L. Brown, Jr., “Sampling theorem for finite energy signals,” IEEE Trans. Inform. Theory, vol. IT14, pp. 818819,1968. [ 1281 R. P. Boas, Jr., “Summation formulas and bandlimitedsignals,” TShoku Math.J., vol. 24, pp. 121125, 1972. H. Haddad andJ. B. Thomas,“Integralrepresentationfor [ 1 2 9 ] A. nonuniform sampling expansions,” in Roc. 4th Allereton ConE Circuit Syst. Theory, pp. 322333, Oct. 57, 1966. [ 1301 A. H. Haddad, K. Yao, and J. B. Thomas, “General methods for IEEE Trans Inform. the derivation of sampling theorems,” Theory, vol. IT13, Apr. 1967. [ 131 ] K. Yao,“ApplicationsofreproducingkernelHilbertspacesbandlimited signal models,” Inform. Contr., vol. 11, pp. 429444, 1967. [ 1321 D. Jagerman, “Information theory and approximation of bandlimited functions,” BeU. Syst. Tech. J., vol. 49, pp. 19111941, 1970. [ 1331 1. J. Schoenberg, “Cardinal interpolation and spline functions,” J . Approx. Theory,vol. 2 , pp. 167206, 1969. [ 1341 I. Kluvinek, “Sampling theorem in abstract harmonic analysis,” MatematickoFyzikalny Casopis, vol. 15, no. 1, pp. 4348, 1965. [ 1351 I . B. Thomas and B. Liu, “Error problems in samplingrepresentation,’’ IEEE Int. Conv. Rec. (USA), vol. 12, part 5, pp. 269277, 1964. [ 1361 B. S. Tsybakov and V. P. Iakovlev, “On the accuracy of restoringa function with a finite number of terms ofKotel’nikov series,”Radio Eng. Electron. (Phys.),vol. 4 , no. 3, pp. 274275, Mar. 1959. [ 1371 K. L. Jordan, “Discrete representation random of signals,” M.I.T.,Cambridge, MA, Tech. Rep. 378. RLE, July, 1961. [ 1381 S. deFrancesco, “An estimate of Shannon’s sample series partial summation inaccuracy,” presented at 15th Int. Commun. Conv. Int. Inst. Commun., Geneva, Oct. 1967. T. Bason, “An errorboundfor Lagrange [ 1 3 9 ] R. Radzynerand P. Trans. Inform. interpolation low of pass functions,” IEEE Theory, v l IT18, pp. 669671, Sept. 1972. o. (1401 J. L. Brown, “Bounds Jr., for truncation error in sampling expansions of band limited signals,”IRE Trans. Inform. Theory, V O ~ .IT15, pp. 440444, July 1969. [ 1411 H. J. Piper, Jr., “Best asymptotic bounds for truncation error in IEEE Tram. sampling expansionsbandlimited of signals,’’ Inform. Theory (Corresp.),vol. IT21, pp. 687690, Nov. 1975. [ 1421 J. Hagenauer, “Sampling theorem with small truncation error,” Archiv fur Electronic and Ubemagungslechnik, vol. 26, no. 4 , pp. 181184,Apr. 1972. sampling I1431 D. Jagerman,‘‘Boundsfortruncationerrorofthe expansion,” SIAM J. Appl. Math., vol. 14, pp. 614723, July 1966. [ 1 4 4 ] A. Papoulii, “Truncated sampling expansions,” IEEE Trans. Automat. Contr., pp. 604605, Oct. 1967. [ 1451 A. Papoulis, “Limits on bandlimited signals,” R o c . IEEE, vol. 55, no. 10,pp. 16771681,Oct. 1967. [ 1461 E. Mendelovicz and J. W. Sherman, “Truncation error bounds for signalsampling,”in Con5Rec.9thAnn.AsilomarConf. Circuit Syst. Comput., p. 16, Nov. 1975. [ 1 4 7 ] E. Mendelovicz, J. W. Sherman J. Murphy, and T. “Signal sampling theorems and truncation error bounds,” o appear. t [ 1481 F. J. Beutler, “On the truncation error of the cardinal sampling expansion,” IEEE Trans. Inform.Theory, vol. 22, no. 5 , pp. 568573, Sept. 1976. [ 1491 J. L. Brown, Jr., “On mean square aliasing error in the cardinal series expansion of random processes,” appear. to [ 1 5 0 ] H. S. Shapiro and R. A. Silverman, “Alias sampling free of random noise,” J . SIAM, vol. 8, pp. 225236, June 1960. 15 1 ] F. J. Beutler, “Aliasfree randomly timed sampling of stochastic processes,” IEEE Trans. Inform. Theory, vol. IT16, pp. 147152, 1970. 1 5 2 ) P. Weiss, “An estimate of the error arising from misapplication of the sampling theorem,” Amer. Math. SOC. Notices, no. 10.351 (abstract No. 60154), 1963. 1531 I. L. Brown,Jr., “On theerrorinreconstructinganonband limited function by means of the band pans sampling theorem,” J. Math. Anal. Appl., vol. 18, pp. 7584, 1967. 1541 J. L. Brown, Jr., “A least upper bound for aliasing error,” IEEE Trans. Auto. Contr.,vol. AC13, no. 6 , pp. 754755, Dec. 1968.
JERRI: SHANNON SAMPLING THEORY: A REVIEW
[ 1 5 5 ) C. J . Standish, “Two remarks on the reconstruction of sampled nonband limited functions,” IBM J . Res. Develop., vol. 1 1 , no. 6, p. 648, 1967. [ 1561 D. C. Stickler, “An upper bound on aliasing error,”Proc. IEEE (Lett.),vol. 55, pp. 418419, 1967. (1571 F. C. Mehta, “Error bound for generalizedbandpasssampling
1595
theorem,” submitted.
[ 1581 G. Franklin, “Linearfiltering of sampled data,”in IREInt. Conv. Rec., vol. 3, pt. 4 , pp. 119128, Mar. 1955. [ 1591 S . P. Lloyd and B. MacMillan, “Linear least squares fiitering and
[ 1601
[ 161 1
[1621
1 631
1641
1’ 651
1 661 [167] [168] [169] [ 1701 [171] I1721 [173]
[ 1741
[175] [ 1761 [177] (1781 (1791 [ 1801 [ 1811 (1821
[ 1831
[ 1841
[ 185 ]
[186] [187] (1881
prediction of sampled signals,” in Proc. Symp. Modern Network Synthesis, P.I.B., pp. 221247, Apr. 1955. R. M. Stewart, “Statistical design and evaluation of fiiters for the restoration of sampled data,” Proc. IRE, vol. 4 4 , pp. 253257, Feb. 1956. J. I. Spilker,“Theoreticalbounds ontheperformancesof sampled data communications systems,” IRE Trans. Circuit Theory, vol. CT7, pp. 335341, Sept. 1960. S . S. L. Chang, “Optimum transmission of a continuous signal over a sampled.data link,”AIEE Trans., vol. 7 9 , pt. I1 (Appiications and Industry), pp. 538542, Jan. 1961. W. M. Brown,“Optimum prefiltering of sampled data,” IRE Trans. Inform. Theory, vol. IT7, pp. 269270, Oct. 1961. D. Middletonand D. P. Peterson, “A noteonoptimum presamplingfilters,”IEEETrans. on Circuit Theory, vol.CTIO, pp. 108109, Mar. 1963. D. S. Ruchkin, “Linear reconstructionofquantizedand sampled random signals,” IRE Trans. Commun. Syst.,vol. CS9, pp. 350355, Dec. 1961. A. V. Balakrishnan, “On the problemoftimejitterin sampling,” IRE Trans. Inform.Theory, vol. IT8, pp. 226236, Apr. 1962. W. M. Brown, “Sampling with random jitter,”J. SIAM,vol. 1 1 , pp. 460473, June 1963. W. M. Brownand C. J . Palermo,“Systemperformance in the presence of stochastic delays,” IRE Trans. Inform. Theory,vol. IT8, pp. S206S214, Sept. 1962. J. R. Higgins, “A sampling theorem for irregularly spaced sample points,” IEEE Trans. Inform. Theory, IT22, pp. 621622, Sept. 1976. J. J. Knab and M. I. Schwartz, “A system error bound for self truncating reconstruction fiiter class,” IEEE Trans. Inform. Theory, vol. IT21, pp. 341342, May 1975. J .J . Knab,“System errorbounds for Lagrange estimationof bandlimited functions,” IEEE Trans. Inform. Theory, vol. IT21. pp. 474476, July 1975. T. Ericson,“A generalized version of the sampling theorem,” Roc. ZEEE, vol. 6 0 , pp. 15541555, 1972. H. 1. Landau, “Sampling data transmission and the Nyquist rate,”Proc. IEEE, vol. 55, pp. 17011706, 1967. R. Barakat, “Application of the samplingtheorem to optical diffractiontheory,” J . Opt.SOC.Amer., vol. 54, no. 7, pp. 920930,1964. D. Gabor, Progress in Optics, E. Wolf, Ed., vol. 1. Amsterdam, The Netherlands: North Holland, 1961. S . C. Som, “Simultaneous multiple reproduction of spacelimited functions by sampling of spacial frequencies,” J. Optic. SOC. Amer.,vol. 60,no. 12, pp. 16281634, Dec. 1970. G. diFrancia, “Resolving power and information,” J. Opt. SOC. Amer., vol. 45, pp. 497501, July 1955. “Directivity, supergain and information,” IRE Trans. Antennas Propagat., vol. AP4, pp. 473478, 1956. F. Gori and G. Guattari, “Holographic restoration nonof uniformly sampledbandlimited functions,” Opt. Comm., vol. 3, no. 3, pp. 147149, May 1971. , “Use ofnonuniform sampling with a single correcting operation,” Opt.Comm., vol. 3, no. 6 , pp. 404406, Aug. 1971. , “Nonuniform sampling in optical processing,” Optica Acta, VOI. 18,nO. 1 2 , p p . 903911, 1971. A. W. Lohmann,“The spaceband widthproduct,” IBM, San Jose Res., San Jose, CA,Res. paper RJ438, May 9, 1967. G. A. Vanasse and H. Sakai, “Fourier spectroscopy,” in Progress inOptics, E. Wolf,Ed.Amsterdam, TheNetherlands:North Holland, 1967, vol. 4, pp. 261329. W. A. Hopper, “Generalized multidimensional sampling theory and applications in optical systems,” in Proc. 10th Ann. Region 3 Conf., p. R31,1972. V. Blaiek, “Sampling theorem and the number of degrees of freedom of an image,” Opt. Comm.,vol. 11, pp. 144147, June 1974. , “Opticalinformation processing by the FabryPerot resonator,”Opt. Quantum Electron., vol. 8, pp. 237240, 1976, R. J. Marks 11, J . F. Walkup, and M. Hagler, “A sampling theorem for spacevariant systems, J. Opt. SOC. Amer., vol. 6 6 , pp. 918921, Sept. 1976. M. J . McDonnell, “A sampling function appropriate for decon
notation,” IEEETrans.Inform.Theory, IT22, pp. 617621, Sept. 1976. [ 1 8 9 ] L. Brillouin, ScienceandInformationTheory, 2ndEd. New York: Academic Press, 1963. [ 1901 J . Frank, “Radiation damage assessment from electron images using digital correlation methods,” J . Phys. D. Appl. Phys.,vol. 7 , pp. 7477, 1974. [ 19111. Frank and L. Ali, “Signaltonoise ratio of electron micrographsobtainedby crosscorrelation,” Nature, vol. 256, no. 5516, pp. 376379, July 31, 1975. [ 1 9 2 ] J.Frank,“Computer processing ofelectron micrographs,” i n Advanced Techniques in Biological Electron Microscopy, I. K. Koehler, Ed. New York: SpringerVerlag, 1973, pp. 215274. [ 1931 A. Stastnt,“Restorationofcontinuous signals,” Zpravodaj ZLU, no. 3, pp. 3343,1969. (InCzech). (English summary in Inti. Aerospace Abstracts v. 10#24 Abs. A7045434). [ 1941 D. P. Petersen, “Discrete and fast Fourier transformations on Ndimensional lattices,”Proc. IEEE, vol. 58, Aug. 1970. Jerri, “Computations the of hill functions of higher (1951 A. J. order,” J. Math. Comput.. vol. 31, no. 138, pp. 481484, Apr.
1 0 7 7. a . I I
1961 K. Yao and J . B. Thomas, “On bandlimited properties of Fouriertransform pairs ofsome special functions,”in Proc. 1965 Allerton Conf. Circuit Syst. Theory, pp. 2022, Oct. 1965. “Sampling expansion for bandlimited signals 1971 F. C. Mehra, through some special functions,” J . Cybernetics, vol. 5, no. 2 , PP. 6168, 1975, 1981 E. C. Titchmarsh, Introduction to the Fourier Inregral. Oxford: University Press, 1937. interpolation series associated with the 1991 J. R. Higgins, “An BesselHankel transform,” J. LondonMath.SOC., vol. 5, pp. 707714, 1972. [?OD] D. P. Petersenand D. Middleton,“On representativeobservations,” Tellus 1 5 , no. 4 , pp. 387405, 1963. [ 2 0 l ] V. I. Belyayev, Procesring and Theoretical Analysis o f OceanoTranslation from Russian JPRS 6080, graphic Observations. Dec. 19, 1973. [ 2 0 2 ] R.Radzyner,“Aspects of nonreguiarsampledprocesses with particularreference t o interpolationand spectralanalysis, as applied t o an investigation of a cardiac pacemaker model,” M.E.S. dissertation, The University of New South Wales, Kensington, New South Wales, Australia, Dec. 1970. [ 2 0 3 ] T. J . Osler, “A further extension of the Leibnitz rule for fractional derivatives and its relation t o Parseval’s formula,” SIAM J . Math. Anal., vol. 4 , no. 3, Aug. 1973. I2041 T. P.Higgins, “A Hypergeometric function transform,” J. SOC. Indust. Appl. Math., vol. 12, no. 3, Sept. 1964.
Other Related References
Sec tion I :
[ 2 0 5 ] A. L. Cauchy, “Memoire sur diverses formules d’analyse,” CornptesRendus, vol. 12, pp. 283298, 1841. (2061 C. E. Shannonand W. Weaver, TheMathematicalTheory of Communication, Urbana, IL: University of Illinois Press, 1949. interpolation, and smoothing of (2071 N. Wiener, “Extrapolation, stationary time series,” New York: Wiley, 1949. review of some [ 2 0 8 ] A. A. Kharkevich,“Kotel’nikov’stheorema new publications,” Radiotekhnika, vol. 13, no. 8, pp. 310, 1958. 1209) J . R. Ragazzini and G. F. Franklin, SampledDatu Control Systems. New York: McGrawHill, 1958. I2101 V. V. Lebedev, “The description of timelimited signals by discrete values,” Radiotekhnika, vol. 16, no. 1 , pp. 7580, 1961.
.
Section 11:
I2111 I. J.Schoenberg,“Contributions t o t h e problemsofapproximation of equidistant data by analytic functions,” Quart. Appl. Math., vol. 4 , pp. 4599 and pp. 112141, 1946. [ 2 1 2 ] A. I. Velichkin, “Interpolation of continuous signals from discrete transmissions,” Elekrrosvyaz, vol. 14, no. 3, pp. 37, 1962. of samplingand interpolation of sig( 2 1 3 ) I. Neveu,“Theproblem nals,”Comptes Rendus, vol. 260, pp. 4951, 1965.
Section 111: [ 2 1 4 ] R. Kress, “On the general Hermite cardinal interpolation,” Math. Cornput.,vol. 26, no. 120,pp. 925933,Oct. 1972. [ 2 1 5 ] D.K. Chengand D. L. Johnson, Walsh transform of sampled time functions and the sampling principle,” Proc. IEEE, vol. 16, no. 5 , pp. 674675, May 1973. Section I V: [ 2 1 6 ] A. Nathan,“On samplinga functionandits derivatives,” In
1596
PROCEEDINGS O F THE VOL. IEEE,
6 5 , NO. 11, NOVEMBER 1977
form. Conrr.,vol. 22, pp. 172182, 1973. (2171 D. P. Petersen, “Static and dynamic constraints on estimation of spacetime covariance wavenumberfrequency and spectral fields,” I. Atmospheric Science, vol. 30, no. 7, pp. 12571266, Oct. 1973. (2181 I. BarDavid, “Sample functions of aGaussian process cannot be recovered from their zero crossings,” IEEE Trans. Inform. Theory, vol. IT21, pp. 8687, Jan. 1975. (2191 G . Bonnet, “On the optimal interpolation of random sampling,” Comptes Rendus,vol. 260, pp. 784787, 1965. , “On the spectral property of functions with bounded sup (2201 port with an application t o the samplingtheorem,” Comptes Rendus, vol. 265, pp. 628630, 1967. I2211 , ‘‘On a property of decomposition functions of with boundedsupportandanapplication to samplescorrelation,” ComptesRendus, vol. 265, pp. 691693,1967. (2221 , “Problems of s a m p q and linear and quadratic handlingof random signals,” Ann. Tilecommun., vol. 24, pp. 1729, 1969. , “Hybrid correlation of samples,” Ann. TelCcomrnun., vol. (223) 24, pp. 252260, 1969.
(2331 J. R. Mitcheland W. L. McDaniel, Jr., “Calculationofupper boundsfor errors ofanapproximate sampled frequency response,” IEEE Trans. Automat. Contr., vol. AC19, pp. 155156, Apr. 1974.
Section VII:
Section V:
( 2 2 4 ) I. T. Turbovich, “The application of Kotel’nikov’s theorem to time functions with a nonlimitedspectrum,”Radiotekhnika, vol. 13, no. 8, pp. 1112, 1958. (2251 I. T. Turbovich, “The analytical representation of a time function with an unlimited spectrum,” Radiotekhnika. vol. 14, no. 3, pp. 2227, 1959. I2261 N. K. Ignat’ev,”On thediscretization ofsignals with an unboundedspectrum,” Elektrosvyaz, vol. 14, no. 2 , pp. 7172, 1960. (2271 , “General methodsof investigatingsignalsinvolvingdiscretization,” Elektrosvyaz, vol. 14, no. 8 , pp. 31 1, 1960.
Section VI:
[228] I. J. Good, “The loss of information due to clipping a waveform,”Inform Control, vol. 10, pp. 220222, 1967. I2291 V.A. Pis’menetskii, “Errors in representing f h t e duration signals,”Radiotekhnika, no. 16, pp. 99101, 1971. (2301 H J. Landau and H.0. Pollack,’ “Prolate spheroidal wave func. tions, Fourier analysisand uncertainty41 and III,” Bell Syst. Tech. J., vol. 4 0 , pp. 6584, 1961, andvol. 41, pp. 12951336, 1962. I2311 D. Slepian,“On bandwidth,” h c IEEE, vol. 6 4 , no. 3, pp. o. 292300, Mar. 1976. [ 2 3 2 ] A. Ephermides and L.H. Brandenburg, “On the reconstruction error of sampled data estimates,” IEEE Trans. Inform. T h e o v , vol. IT19, pp. 365367, May 1973.
K. Sasakawa, “Application of Miyakawa’s multidimensional sampling theorem I, 11,111, IV, V, VI, “presented at Prof. Group o n Info. Theory, Inst. of Elec. Comm. Engrs. of Japan, 19601961. D. P. Petersen, “On the concept and implementation of sequential analysis for linear random fields,” TelIus, vol. 20, no. 4, pp. 673686,1968. D.P. Petersen, “Algorithm for sequential and random observations,” Meterol. Mono., vol. 11, no. 33, pp. 100109, Oct. 1970. World Meteorological Organization, “Upper air network requirementsfornumericalweather prediction,”Secretariatof the WMO,Tech. Note 29, Geneva, Switzerland, 1960. D. P. Petersen, “A comparison o performance of quasiaptimal f and conventional objective analysis schemes,” J. Appl. Meteorol., vol. 12, no. 7 , pp. 10931101, Oct. 1973. R. N. Bracewell,“Twodimensionalaerialsmoothing in radio astronomy,”Aust. 3. Physics, Vol. 9 , pp. 297314, 1956. R. W. Schafer and L.R. Rabiner, “A digital signal processing approach to interpolation,”Proc. IEEE, vol. 6 1 , no. 6, pp. 692702, June 1973. L. E.Ostrander.“TheFouriertransform ofsplinefunction approximations to continuous data,” IEEE Trans. Audio Elect r ~ ~ ~ VOI.AU19, pp. 103104, Mar. 1971. st., P. Leuthold, “Sampling theorem as an aid t o lucid description of singleside band modulation,” Nachrichtentech. Z.,vol. 22, pp. 6569, Feb. 1969. F. Stengerand J. Schwing,“Numericalintegrationalgorithm based on Whittaker’s cardinal functions,” in progress. F.Stegnerand L. Ludin,“Cardinaltypeapproximationofa function and itsderivative,” in progress.
Other References
(2451 C. J. de la Vallbe Poussin, “Sur l’approximation des fonctions d’une variable rbelleet de leurs dkiv6es des polynomes et de par suites limit& de Fourier,” Bull. Acad. Roy.de Belg. (Classe de Sciences), pp. 193254, 1908. R. T. Proaser, “A multidimensional sampling theorem,” 3. Math. Anal. A p p . , vol. 16, p 574584, 1966. I. J. Schoenberg, Cardinal Ipline Interpolation. Regional Conference Monograph No. 12, SIAM, Philadelphia, PA, 1973. A. J. ,,Lee, “A proximate interpolation and the sampling theorem, SIAM Appl. Math., vol. 32, no. 4 , pp. 731744, June 1977.
~~~~ ~
.
f: