Bandlimited Functions and the Whittaker-Shannon-Kotel’nikov Sampling Theorem

During the next weeks I will be writing a series of posts about my pre-print with Daniel Abreu, it essentially has to do with Sampling Theory, Frames and Applied Harmonic Analysis. The first post of this series will be a more elementary one, and will be devoted to introducing bandlimited function and presenting one of the classical results in this subject, the Shannon Sampling Theorem.

In Signal Processing it is usual to represent a signal by a function [;f(t);] depending on [;t\in\mathbb{R};] (usually considered to be time). It is often important to consider the same signal on the frequency side, this is achieved by the Fourier Transform of the signal,

[;\hat{f}(\xi)=\frac1{\sqrt{2\pi}}\int_{\mathbb{R}}f(t)e^{-i\xi t}dt.;]

Roughly speaking, the value of [;\hat{f}(\xi);] stands for how much the frequency [;e^{i\xi\cdot};] is present in [;f;]. The Fourier Transform lies in the heart of the Fourier Analysis, and is a mathematical object with several beautiful (and sometimes amazing) proprieties. Two of them are very important in what follows:

– The Plancharel Theorem that essentially states that the Fourier Transform is an isometry in [;L^2(\mathbb{R});], meaning that: [;\int_{\mathbb{R}}|f(t)|^2dt=\int_{\mathbb{R}}|\hat{f}(\xi)|^2d\xi;].

and,

– The inversion formula, that essentially gives the relation

[; f(t)=\frac{1}{\sqrt{2\pi}}\int_{\mathbb{R}}\hat{f}(\xi)e^{i\xi t}d\xi . ;]

In several applications it is reasonable to assume that a signal can not have frequencies of arbitrarily big absolute value (a simple illustration of this is the fact that the human ear can only listen sounds whose frequency lie on a certain band). For this reason one is interested in studying functions whose frequency is supported on [;[-W,W];], for some [;W>0;] (we will restrict ourselves to [;[-\pi,\pi];] to make the exposition cleaner, although all results below can be easily generalized to a general band space[;[-W,W];]). This motivates the next definition.

Definition 1: Bandlimited functions

The space of bandlimited functions [;\mathcal{B};] is the space of all [;f\in L^2(\mathbb{R});] such that its Fourier Transform is supported on [;[-\pi,\pi];], i.e. such that

[;\hat{f}(\xi)=\frac1{\sqrt{2\pi}}\int_{\mathbb{R}}f(t)e^{-i\xi t}dt=0,\ \forall \xi\notin [-\pi,\pi].;]

The space of bandlimited functions is also tightly connected to a space of entire functions by the Paley-Wiener Theorem.

Now, we are ready to state and prove the Whittaker-Shannon-Kotel’nikov Sampling Theorem.

Theorem 1: Whittaker-Shannon-Kotel’nikov

Let [;f;] be a Bandlimited function (see Definition 1), i.e.: [;f\in\mathcal{B};]. Then

[;f(t)=\sum_{k\in\mathbb{Z}}f(k)\frac{\sin(\pi (t-k))}{\pi (t-k)}.;]

Moreover

[;\int_{\mathbb{R}}|f(t)|^2dt=\sum_{k\in\mathbb{Z}}|f(k)|^2.;]

Proof: Let [;f\in\mathcal{B};] be given. By the Plancharel Theorem we have [;\hat{f}(\xi)\in L^2(\mathbb{R});]. As [;\{\frac1{\sqrt{2\pi}}e^{ik\cdot}\}_{k\in\mathbb{Z}};] is an orthonormal basis of [;L^2(-\pi,\pi);] (Fourier Series are based on this fact) and [;\hat{f}(\xi);] is supported on [;[-\pi,\pi];], then we can write

[;\hat{f}(\xi)=\frac1{\sqrt{2\pi}}\sum_{k\in\mathbb{Z}}a_k1_{[-\pi,\pi]}e^{ik\xi};]

for some coefficients [;a_k;], where [;1_X;] stands for the characteristic function of the set [;X;]. Using the inversion formula and performing simple calculations we obtain

[;f(t)=\frac1{\sqrt{2\pi}}\int_{\mathbb{R}}\sum_{k\in\mathbb{Z}}a_k1_{[-\pi,\pi]}e^{ik\xi}e^{it\xi}d\xi=\sum_{k\in\mathbb{Z}}a_k\frac{\sin(\pi(t+k))}{\pi(t+k)}.;]

Setting [;t=-k;] we obtain [;a_{-k}=f(k);] giving the first equality of the Theorem.

The second part of the theorem is obtained with a direct application of the Plancharel Theorem and the fact that [;\{\frac1{\sqrt{2\pi}}e^{ik\cdot}\}_{k\in\mathbb{Z}};] is an orthonormal basis of [;L^2(-\pi,\pi);].

[;\Box;]

This theorem shows that [;\mathbb{Z};] is a sequence where we can sample functions in [;\mathcal{B};] in the sense that, if we know the values of a bandlimited function at [;\mathbb{Z};] the function is uniquely determined and can be reconstructed by the formula in Theorem 1, this sampling rate is known as the Nyquist Rate.

One question that naturally arises is if there exists a sampling sequence “smaller” than [;\mathbb{Z};] (or, in other words, the optimality of the Nyquist Rate). To properly ask this question one needs to define what is smaller than in infinite sets and one needs to define sampling sequence. This will be done in the next post, and an answer to this question, due to Landau, will be discussed in future posts as well.

As this is my first Math blog post I would much appreciate comments about it. Was it too elementary? Did I lost too much time on basic stuff? Was it too fast to follow? too slow? too long? too short? Was something not clear enough? Answers to these questions will help me writing better posts in the future.

Advertisements

7 thoughts on “Bandlimited Functions and the Whittaker-Shannon-Kotel’nikov Sampling Theorem

  1. I think your speed is good. Maybe in the future you will need/be able to write longer posts but I liked this one. I already knew most of the mathematics presented, so I can’t give good answers to the other questions.

    Just one observation: I believe that not every function [;L^2(R);] has its Fourier transform defined (not by the integral anyway). So in definition 1, you are only considering functions for which the integral in the definition of the Fourier transform converges?

    1. Joel,

      Thank you for your suggestion. About the definition of the Fourier Transform, to be rigorous one needs to define it for functions in [;L^1(\mathbb{R})\cap L^2(\mathbb{R});] by the integral (because the integral converges if [;f\in L^1(\mathbb{R});]) and then using the Plancharel theorem together with the fact that [;L^1(\mathbb{R})\cap L^2(\mathbb{R});] is dense in [;L^2(\mathbb{R});] one can extend it to a unitary operator in [;L^2(\mathbb{R});].

  2. I really liked the question of whether a smaller sampling sequence exists. By assuming the function band limited in frequency, doesn’t it imply it is not limited in time? So by the hypothesis of the theorem we get a sampling rate, but we always obtain an infinite number of samples anyway. Looking forward to the next post.

    1. Thiago,

      Thank you for your comment. That is a very good point. Roughly the uncertainty principle (or one of the uncertainty principles) tells us that a function cannot be both concentrated on time and on frequency and, in particular, that if it is band-limited it has to unlimited on time, (this concentration ideas will play a vital role in posts to come).

      It is true that a sampling sequence has to consist of an infinite set of points but even so we can talk on smaller sets in a density prespective. For example one agrees that the set of the integers is (somehow) twice as big as the set of the even numbers. In a future post I will give a formal definition of density.

      I will write the next post during the weekend.

      Afonso

  3. Today I was reading Shannon’s mathematical theory of communication and his notation wasn’t as clear as yours. I definitely appreciate your elementary translation and thank you for your efforts.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s