Sign in

Not a member? | Forgot your Password?

Search Online Books



Search tips

Free Online Books

Free PDF Downloads

A Quadrature Signals Tutorial: Complex, But Not Complicated

Understanding the 'Phasing Method' of Single Sideband Demodulation

Complex Digital Signal Processing in Telecommunications

Introduction to Sound Processing

C++ Tutorial

Introduction of C Programming for DSP Applications

Fixed-Point Arithmetic: An Introduction

Cascaded Integrator-Comb (CIC) Filter Introduction

Chapters

FIR Filter Design Software

See Also

Embedded SystemsFPGA
Chapter Contents:

Search Mathematics of the DFT

  

Book Index | Global Index


Would you like to be notified by email when Julius Orion Smith III publishes a new entry into his blog?

  

Sampling Theorem

Let $ x(t)$ denote any continuous-time signal having a continuous Fourier transform

$\displaystyle X(j\omega)\isdef \int_{-\infty}^\infty x(t) e^{-j\omega t} dt.
$

Let

$\displaystyle x_d(n) \isdef x(nT), \quad n=\ldots,-2,-1,0,1,2,\ldots,
$

denote the samples of $ x(t)$ at uniform intervals of $ T$ seconds. Then $ x(t)$ can be exactly reconstructed from its samples $ x_d(n)$ if $ X(j\omega)=0$ for all $ \vert\omega\vert\geq\pi/T$.D.3



Proof: From the continuous-time aliasing theoremD.2), we have that the discrete-time spectrum $ X_d(e^{j\theta})$ can be written in terms of the continuous-time spectrum $ X(j\omega)$ as

$\displaystyle X_d(e^{j\omega_d T}) = \frac{1}{T} \sum_{m=-\infty}^\infty X[j(\omega_d +m\Omega_s )]
$

where $ \omega_d \in(-\pi/T,\pi/T)$ is the ``digital frequency'' variable. If $ X(j\omega)=0$ for all $ \vert\omega\vert\geq\Omega_s /2$, then the above infinite sum reduces to one term, the $ m=0$ term, and we have

$\displaystyle X_d(e^{j\omega_d T}) = \frac{1}{T} X(j\omega_d ), \quad \omega_d \in\left(-\frac{\pi}{T},\frac{\pi}{T}\right)
$

At this point, we can see that the spectrum of the sampled signal $ x(nT)$ coincides with the nonzero spectrum of the continuous-time signal $ x(t)$. In other words, the DTFT of $ x(nT)$ is equal to the FT of $ x(t)$ between plus and minus half the sampling rate, and the FT is zero outside that range. This makes it clear that spectral information is preserved, so it should now be possible to go from the samples back to the continuous waveform without error, which we now pursue.

To reconstruct $ x(t)$ from its samples $ x(nT)$, we may simply take the inverse Fourier transform of the zero-extended DTFT, because

\begin{eqnarray*}
x(t) &=& \hbox{\sc IFT}_t(X)
\isdef \frac{1}{2\pi}\int_{-\inft...
...j\theta}) e^{j\omega t} d\omega
\isdef \hbox{\sc IDTFT}_t(X_d).
\end{eqnarray*}

By expanding $ X_d(e^{j\theta})$ as the DTFT of the samples $ x(n)$, the formula for reconstructing $ x(t)$ as a superposition of weighted sinc functions is obtained (depicted in Fig.D.1):

\begin{eqnarray*}
x(t) &=& \hbox{\sc IDTFT}_t(X_d) \\
&\isdef & \frac{1}{2\pi}...
...um_{n=-\infty}^{\infty}x(nT) h(t-nT) \\
&\isdef & (x\ast h)(t)
\end{eqnarray*}

where we defined

\begin{eqnarray*}
h(t-nT) &\isdef & \frac{T}{2\pi} \int_{-\pi/T}^{\pi/T} e^{j\om...
...t(\frac{t-nT}{T}\right) = \mbox{sinc}\left(\frac{t}{T}-n\right),
\end{eqnarray*}

or

$\displaystyle h(t) =$   sinc$\displaystyle \left(\frac{t}{T}\right),$   where    sinc$\displaystyle (t)\isdef \frac{\sin(\pi t)}{\pi t}.
$

The ``sinc function'' is defined with $ \pi $ in its argument so that it has zero crossings on the nonzero integers, and its peak magnitude is 1. Figure D.2 illustrates the appearance of the sinc function.

We have shown that when $ x(t)$ is bandlimited to less than half the sampling rate, the IFT of the zero-extended DTFT of its samples $ x(nT)$ gives back the original continuous-time signal $ x(t)$. This completes the proof of the sampling theorem.
$ \Box$

Conversely, if $ x(t)$ can be reconstructed from its samples $ x_d(n) \isdef x(nT)$, it must be true that $ x(t)$ is bandlimited to $ [-f_s/2,f_s/2]$, since a sampled signal only supports frequencies up to $ f_s/2$ (see §D.4 below). While a real digital signal $ x(n)$ may have energy at half the sampling rate (frequency $ f_s/2$), the phase is constrained to be either 0 or $ \pi $ there, which is why this frequency had to be excluded from the sampling theorem.

A one-line summary of the essence of the sampling-theorem proof is

$\displaystyle \zbox {x(t) = \hbox{\sc IFT}_t\left\{\hbox{\sc ZeroPad}_\infty\left\{\hbox{\sc DTFT}\{x_d\}\right\}\right\}}
$

where $ x_d \isdef \hbox{\sc Sample}_T(x)$.

The sampling theorem is easier to show when applied to sampling-rate conversion in discrete-time, i.e., when simple downsampling of a discrete time signal is being used to reduce the sampling rate by an integer factor. In analogy with the continuous-time aliasing theorem of §D.2, the downsampling theorem7.4.11) states that downsampling a digital signal by an integer factor $ L$ produces a digital signal whose spectrum can be calculated by partitioning the original spectrum into $ L$ equal blocks and then summing (aliasing) those blocks. If only one of the blocks is nonzero, then the original signal at the higher sampling rate is exactly recoverable.


Previous: Continuous-Time Aliasing Theorem
Next: Appendix: Frequencies Representable by a Geometric Sequence

Order a Hardcopy of Mathematics of the DFT


About the Author: Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.


Comments


No comments yet for this page


Add a Comment
You need to login before you can post a comment (best way to prevent spam). ( Not a member? )