[PDF] [PDF] The Shannon Sampling Theorem and Its Implications - Math User

[PDF] AN-236 An Introduction to the Sampling Theorem - Texas Instruments

The prefilter, typically called anti-aliasing filter guarantees, for example in the low pass filter case, that the sampled data system receives analog signals having a 

[PDF] SAMPLING THEOREM 1 Statement of Sampling Theorem 2

Note: Digital Signal Processing is possible because of this SAMPLING THEOREM: EXAMPLE #1 x(t)=cos(2π1000t) sampled at S=8000SAMPLE SECOND

[PDF] Signals Sampling Theorem - Tutorialspoint

back when sampling frequency fs is greater than or equal to the twice the highest frequency component of message signal i e Proof: Consider a continuous 

[PDF] The Sampling Theorem and the Bandpass Theorem - University of

It follow that the continuous function x(t) can be reconstituted from its sampled values {xt,t ∈ I} Proof Since x(t) is a square-integrable function, it is amenable to a 

[PDF] Nyquist–Shannon sampling theorem

The Nyquist theorem describes how to sample a signal or waveform in such a way as to wagon-wheel effect (for example https://youtu be/6XwgbHjRo30) 2

[PDF] The Sampling Theorem - NJIT

BME 333 Biomedical Signals and Systems - J Schesser 159 Sampling Theorem Conclusion • If we have BL signal, don't send the whole signal • Sample it at 

[PDF] The Shannon Sampling Theorem and Its Implications - Math User

1 3 What Else Do We Want to Understand? The above proof does not completely explain what may go wrong if we sample according to a frequency B

[PDF] An Introduction to the Sampling Theorem

tive proof This should hopefully leave the reader with a comfortable understanding of the sampling theorem Theorem If the Fourier transform F(0) of a signal 

4 Sampling Theorem

If periodically continued, the overall frequency response sums up to a constant This is the Nyquist criterion expressed in the frequency domain Fig 4-11 Example 

[PDF] Sampling Theorem - NPTEL

Lecture 28 : Sampling Theorem Objectives In this lecture An another example, consider a 50Hz signal sampled at 50Hz (see in fig 28 3) It can be seen that

[PDF] sams teach yourself cobol in 21 days 3rd edition download

[PDF] sams teach yourself html

[PDF] sams teach yourself php in 24 hours 3rd edition pdf

[PDF] sams teach yourself php in 24 hours 3rd edition pdf free

[PDF] sams teach yourself sql in 10 minutes 3rd edition

[PDF] sams teach yourself sql in 10 minutes 3rd edition pdf

[PDF] sams teach yourself uml in 24 hours pdf

[PDF] samson q2u amazon uk

[PDF] samson q2u driver

[PDF] samson q2u kit

[PDF] samson q2u quiet

[PDF] samson q9u amazon

[PDF] samsung c24fg70 manual

[PDF] samsung can't change keyboard language

[PDF] samsung design guidelines

The Shannon Sampling Theorem and

Its Implications

Gilad Lerman

Notes for Math 5467

1 Formulation and First Proof

The sampling theorem of bandlimited functions, which is often named after Shannon, actually predates Shannon [2]. This is its classical formulation. Theorem 1.1.Iff2L1(R)and^f, the Fourier transform off, is supported on the interval[B;B], then f(x) =X n2Zfn2B sinc 2B xn2B ;(1) where the equality holds in theL2sense, that is, the series in the RHS of(1) converges tofinL2(R). In other words, the theorem says that if an absolutely integrable function contains no frequencies higher thanBhertz, then it is completely deter- mined by its samples at a uniform grid spaced at distances 1/(2B) apart via formula (1).

1.1 Terminology and Clarications

We say that a functionf(with values in eitherRorC) is supported on a setAif it is zero on the complement of this set. Thesupportoff, which we denote by supp(g), is the minimal closed set on whichfis supported, equivalently, it is the closure of the set on whichfis non-zero. We note that iff2L1(R) is real-valued then the support of^fis symmetric around zero (since the real part of^fis even and the imaginary part is odd). A function 1 f2L1(R) isbandlimitedif there existsB2Rsuch that supp(^f)[B;B].

We callBa band limit forfand

:= 2B, the corresponding frequency band. The minimal value ofB(such that supp(^f)[B;B]), that is, the supremum of the absolute values of all frequencies off, is called theNyquist frequencyoffand its corresponding frequency band is called theNyquist rate. We denote the Nyquist frequency byBNyq, so that the Nyquist rate is

2BNyq.

Let us recall that the \general principle of the Fourier transform" states that the decay of^fimplies smoothness offand vice versa. Band-limited functions have the best decay one can wish for (their Fourier transforms are zero outside an interval), they are also exceptionally smooth, that is, their extension to the complex plan is analytic, in particular, they areC1(R) func- tions. This fact follows from a well-known theorem in analysis, the Payley- Wiener Theorem [1]. We thus conclude that iffis a band-limited signal, then its valuesff(k=2B)gk2Zare well-dened.1 Having a bandlimit is natural for audio signals. Human voice only occu- pies a small piece of the band of audible frequencies, typically between 300 Hz and 3.5 KHz (even though we can hear up to approximately 20 KHz). On the other hand, this is a problematic requirement for images. Sharp edges in natural images give rise to high frequencies and our visual system is often in- tolerable to thresholding these frequencies. Nevertheless, Shannon sampling theory still claries to some extent the distortion resulting from subsampling images and how one can weaken this distortion by initial lowpass ltering.

1.2 First Proof of the Sampling Theorem

Sincef2L1(R) and supp(^f)[B;B], then^fis a bounded function

supported on [B;B], in particular,^f2L2([B;B]). We can thus expand^faccording to its following Fourier series:

f() =X n2Zc ne2in2B;(2)1 Iffis a rather arbitrary function inL1(R), then by changing its value at a point, we obtain a function whoseL1distance fromfis 0. That is, in general, the values ff(k=2B)gk2Zare not uniquely determined forf2L1(R), however, sucient smoothness, e.g., continuity, implies their unique denition. 2 where c n=12BZ B

B^f(x)e2in2Bdx=12BZ

1

1^f(x)e2in2Bdx=12Bfn2B

:(3)

Therefore,

f() =X n2Z12Bfn2B e

2in2B=X

n2Z12Bfn2B e2in2B:(4) From (4) it is already clear thatfcan be completely recovered by the valuesff(n=(2B))gn2Z. To conclude the recovery formula we invert^fas follows: f(x) =Z B

B^f()e2ixd=X

n2Zfn2B 12BZ B

Be2i(xn2B)d(5)

X n2Zfn2B 12Be

2i(xn2B)2ixn2B

B =B X n2Zfn2B

12Bxn2Be2iB(xn2B)e2iB(xn2B)2i

X n2Zfn2B sin2Bxn2B2Bxn2B =X n2Zfn2B sinc 2B xn2B

1.3 What Else Do We Want to Understand?

The above proof does not completely explain what may go wrong if we sample according to a frequencyB < BNyq; we refer to such sampling asundersam- pling. It is also not easy to see possible improvement of the theory when B > B Nyq, that is, whenoversampling. Nevertheless, if we try to adapt the above proof to the case whereB < BNyq, then we may need to periodize ^fwith respect to the interval [B;B] and then we can expand the peri- odized function according to its Fourier series. Therefore, inx2 we discuss the Fourier series expansions of such periodized functions. This is in fact the well-known Poisson's summation formula. Inx3 we describe a second proof for the Shannon's sampling theorem, which is based on the Poisson's sum- mation formula. Following the ideas of this proof,x4 explains the distortion 3 obtained by the recovery formula (1) when sampling with frequency rates lower than Nyquist; it also claries how to improve such signal degradation by initial lowpass ltering. Section 5 explains how to obtain better recov- ery formulas when the sampling frequency is higher than Nyquist. At last, we discuss inx6 further implications of these basic principles, in particular, analytic interpretation of the Cooley-Tukey FFT.

2 Poisson's Summation Formula

The following theorem is a formulation of Poisson summation formula with additional frequencyB(so that it ts well with the sampling formula). It uses the functionP1 n=1f(x+n=(2B)), which is a periodic function of period

1=(2B) (indeed, it is obtained by shifting the functionf(x) at distances

n=(2B) for alln2Zand adding up all this shifts). It is common to formulate

Poisson's summation formula with onlyB= 1=2.

Theorem 2.1.Iff2L2(R),B >0and

1 X n=1f x+n2B 2L2 0;12B ;(6) then 1X n=1f x+n2B =1X n=12B^f(2Bn)e2inx2B:(7)

Proof.SinceP1

n=1fx+n2Bis inL2([0;1=(2B)]), we can expand it by its Fourier series as follows: 1 X n=1f x+n2B =1X m=1c me2imx2B;(8) where c m= 2BZ 12B 01 X n=1f x+n2B e

2imx2Bdx(9)

1X n=12BZ 12B 0f x+n2B e

2imx2Bdx:

4 Applying the change of variablesy=x+n=(2B) into the RHS of (9) and then using the fact thate2inm= 1, we conclude the theorem as follows c m=1X n=12BZ n+12B n2Bf(y)e2imy2Bdy(10) = 2BZ 1 1 f(y)e2imy2B= 2B^f(2Bm):We can reformulate Theorem 2.1 as follows:

Theorem 2.2.Iff2L2(R),B >0andP1

n=1^f(+ 2Bn)2L2([0;2B]), then 1X n=1^ f(+ 2Bn) =12B1 X n=1fn2B e2in2B:(11) Theorems 2.1 and 2.2 are clearly equivalent. For example, Theorem 2.2 follows from Theorem 2.1 by replacingfwith^f(and thus^f() withf(x), which equals ^^f(x)) and replacing 2Bwith 1=2Bas well as changing variables in the RHS of (7) fromnton. We use the period 2Bfor the function on the LHS of (11) and 1=(2B) for the function on the LHS of (11) due to the transformation of scale between the spatial and frequency domains (however, the choice of scale can be arbitrary). We note that Theorem 2.2 implies that given the samplesff(n=(2B))gn2Z, we can then recover the periodic summation of^fwith period 2B, that is, the function P

2B(^f) :=1X

n=1^ f(+ 2Bn):(12) This observation is the essence of our second proof of the sampling theorem.

3 A Second Proof of the Sampling Theorem

Since supp(

^f)[B;B],P2B(^f) satises the identity f() =[B;B]()P2B(^f)() for all6=B;B:(13) 5

We remark that if

^f(B)6= 0 (and consequently also^f(B)6= 0), then (13)

does not hold for=B(and consequently also for=B), butP2B(^f)() =^f(B)+^f(B). Nevertheless, the LHS and RHS of (13) are equal inL2([B;B]).

Combining (11)-(13), we conclude the following equality inL2: f() =1X n=1fn2B

12B[B;B]()e2in2B:(14)

We recall that

12B[B;B]() is the Fourier transform of sinc(2Bx) and thus

12B[B;B]()e2in2Bis the Fourier transform of sinc2Bxn2B. At last,

we use this observation and invert the Fourier transforms in both sides of (14). We consequently obtain the sampling formula (as an equality inL2): f(x) =1X n=1fn2B sinc 2B xn2B :(15)

4 On Aliasing and Anti-aliasing

Assume thatfis a band-limited function inL1andBis lower than its Nyquist frequency. Suppose that we samplefatfn=2Bgn2Zand try to recoverfby its samples. It is interesting to know how well we can approxi- matefthis way. The second proof of the sampling theorem provides a good answer. Indeed, sinceP2B(^f) is inL2(this is because^fis bounded and supported in [B;B]), then we can replace (14) with [B;B]()P2B(^f)() =1X n=1fn2B

12B[B;B]()e2in2B:(16)

Letgbe the inverse Fourier transform of[B;B]()P2B(^f)(), then similarly to deriving (15), we obtain that g(x) =1X n=1fn2B sinc 2B xn2B :(17) That is, the sampling formula recoversg, which we refer to as an alias off.

Example 4.1.We arbitrarily x >0andB0>0and let

f(x) =h(x)2B0sinc(2B0x);(18) 6 wheresupp(^h) = [;]andh(0) = 0(equivalentlyR^h()d= 0and thus ^hoscillates). We note that f() =^h()[B0;B0]() =Z B0

B0^h()d=Z

+B0

B0^h()d:(19)

In particular,

^fis supported on the interval[B0;B0+], that is,BNyq= B 0+. Assume that we want to samplefwith frequencyB0. Equation(19) implies that [B0;B0]()P2B0(^f)() =[B0;B0]()Z 1

1^h()d=[B0;B0]h(0) = 0:

(20) That is, the alias functiongis the zero function. We also note that by the denitions offandh,f(n=(2B0)) = 0for anyn2Z. This observation also conrms that the alias recovered by the sampling formula (i.e.,g) is the zero function. Example 4.2.Letf(x) = sinc2(x)so that^f() = (1 jj)[1;1]()(this follows from the solution to the second part of problem 4 in Homework 3 and the fact thatfis real and even). The Nyquist frequency offisBNyq= 1. Assume that we samplefwith frequencyB= 0:5and then try to recoverf by the sampling formula with thisB. By direct calculation (or plotting all intersecting shifts and adding them up) we obtain that [0:5;0:5]()P1(^f)() =[0:5;0:5]()(1 jj+jj) =[0:5;0:5]():(21) This is the Fourier transform of the aliasg(x) = sinc(x). Clearlyfand its aliasgare rather dierent (f=g2). While we cannot recoverffrom its samples at the integer values, we can get a better approximation to it. Indeed, let us zero out its Fourier transform outside the interval[0:5;0:5]. That is, we dene~fto be the function such that ^~f=^f[0:5;0:5]. We note that ~f() = (1 jj)[0:5;0:5]() =12 [0:5;0:5]() +12 (12jj)[0:5;0:5]() 12 [0:5;0:5]() +14

2^f(2):(22)

7 Therefore (applying the solutions of the rst two parts of problem 4 in Home- work 3) f(x) =12 sinc(x) +14 sinc2(x=2) =sinc(x)2 +sinc2(x)2(1 + cos(x)):(23)

The function

~fis closer tofthan the aliasg. We clarify this claim in a more general setting next.

We claim that

~fof Example 4.2 is the bestL2approximation tofthat coincides withfat the undersampled values and reproduced by the sampling formula. The requirement of reproducing by the sampling formula with spac- ing 1=(2B) can be replaced with the requirement of band limit 2B. We even claim the following more general statement. Proposition 4.1.Iff2L1(R)andB >0, then among all functionsh2L1 of band limitBthe function~f, whose Fourier transform is^~f=^f[B;B], obtains the shortestL2distance tof. Proof.Ifh2L1and its Fourier transform is supported in [B;B], then kfhk22=k^f^hk22=Z

Bj^f()^h()j2d+Z

>B j^f()j2d:(24) Since the second term in the RHS of (24) is independent ofh,h=~fis a minimizer ofkfhk2.The replacement offwith~fbefore subsampling is referred to asanti- aliasing(we slightly generalize this denition below). That is, if we need to sample a signalfatfn=2Bgn2Z, whereB < BNyq, we can anti-alias it by rst zeroing out the Fourier transform offoutside the interval [B;B] and then subsample. In other words, we apply a lowpass lter before subsampling. However, we may prefer a low-pass lter, which is more localized in the spatial domain, equivalently, smoother in the Fourier domain. We will thus refer to any such application of low-pass lter (with support of size comparable to

2B, but not smaller than 2B) before subsampling at equidistances 1=(2B)

quotesdbs_dbs17.pdfusesText_23