Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » Digital Signal Processing and Digital Filter Design (Draft) » Sampling, Up--Sampling, Down--Sampling, and Multi--Rate

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This module is included in aLens by: Digital Scholarship at Rice UniversityAs a part of collection: "Brief Notes on Signals and Systems"

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

  • NSF Partnership display tagshide tags

    This collection is included inLens: NSF Partnership in Signal Processing
    By: Sidney Burrus

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Click the "Featured Content" link to see all content affiliated with them.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Sampling, Up--Sampling, Down--Sampling, and Multi--Rate

Module by: C. Sidney Burrus. E-mail the author

A very important and fundamental operation in discrete-time signal processing is that of sampling. Discrete-time signals are often obtained from continuous-time signal by simple sampling. This is mathematically modeled as the evaluation of a function of a real variable at discrete values of time [16]. Physically, it is a more complicated and varied process which might be modeled as convolution of the sampled signal by a narrow pulse or an inner product with a basis function or, perhaps, by some nonlinear process.

The sampling of continuous-time signals is reviewed in the recent books by Marks [10] which is a bit casual with mathematical details, but gives a good overview and list of references. He gives a more advanced treatment in [11]. Some of these references are [13], [17], [9], [8], [7], [16], [15]. These will discuss the usual sampling theorem but also interpretations and extensions such as sampling the value and one derivative at each point, or of non uniform sampling.

Multirate discrete-time systems use sampling and sub sampling for a variety of reasons [4], [18]. A very general definition of sampling might be any mapping of a signal into a sequence of numbers. It might be the process of calculating coefficients of an expansion using inner products. A powerful tool is the use of periodically time varying theory, particularly the bifrequency map, block formulation, commutators, filter banks, and multidimensional formulations. One current interest follows from the study of wavelet basis functions. What kind of sampling theory can be developed for signals described in terms of wavelets? Some of the literature can be found in [1], [6], [12], [5], [2].

Another relatively new framework is the idea of tight frames [5], [19], [2]. Here signals are expanded in terms of an over determined set of expansion functions or vectors. If these expansions are what is called a tight frame, the mathematics of calculating the expansion coefficients with inner products works just as if the expansion functions were an orthonormal basis set. The redundancy of tight frames offers interesting possibilities. One example of a tight frame is an over sampled band limited function expansion.

Fourier Techniques

We first start with the most basic sampling ideas based on various forms of Fourier transforms [14], [3], [19].

The Spectrum of a Continuous-Time Signal and the Fourier Transform

Although in many cases digital signal processing views the signal as simple sequence of numbers, here we are going to pose the problem as originating with a function of continuous time. The fundamental tool is the classical Fourier transform defined by

F ( ω ) = ∫ f ( t ) e - j ω t d t F ( ω ) = ∫ f ( t ) e - j ω t d t
(1)

and its inverse

f ( t ) = 1 2 π ∫ F ( ω ) e j ω t d ω . f ( t ) = 1 2 π ∫ F ( ω ) e j ω t d ω .
(2)

where j=-1j=-1. The Fourier transform of a signal is called its spectrum and it is complex valued with a magnitude and phase.

If the signal is periodic with period f(t)=f(t+P)f(t)=f(t+P), the Fourier transform does not exist as a function (it may as a distribution) therefore the spectrum is defined as the set of Fourier series coefficients

C ( k ) = 1 P ∫ 0 P f ( t ) e - j 2 π k t / P d t C ( k ) = 1 P ∫ 0 P f ( t ) e - j 2 π k t / P d t
(3)

with the expansion having the form

f ( t ) = ∑ k C ( k ) e j 2 π k t / P . f ( t ) = ∑ k C ( k ) e j 2 π k t / P .
(4)

The functions gk(t)=ej2πkt/Pgk(t)=ej2πkt/P form an orthogonal basis for periodic functions and Equation 3 is the inner product C(k)=〈f(t),gk(t)〉C(k)=〈f(t),gk(t)〉.

For the non-periodic case in Equation 1 the spectrum is a function of continuous frequency and for the periodic case in Equation 3, the spectrum is a number sequence (a function of discrete frequency).

The Spectrum of a Sampled Signal and the DTFT

The discrete-time Fourier transform (DTFT) as defined in terms samples of a continuous function is

F d ( ω ) = ∑ n f ( T n ) e - j ω T n F d ( ω ) = ∑ n f ( T n ) e - j ω T n
(5)

and its inverse

f ( T n ) = T 2 π ∫ - π / T π / T F d ( ω ) e j ω T n d ω f ( T n ) = T 2 π ∫ - π / T π / T F d ( ω ) e j ω T n d ω
(6)

can be derived by noting that Fd(ω)Fd(ω) is periodic with period P=2π/TP=2π/T and, therefore, it can be expanded in a Fourier series with Equation 6 resulting from calculating the series coefficients using Equation 3.

The spectrum of a discrete-time signal is defined as the DTFT of the samples of a continuous-time signal given in Equation 5. Samples of the signal are given by the inverse DTFT in Equation 6 but they can also be obtained by directly sampling f(t)f(t) in Equation 2 giving

f ( T n ) = 1 2 π ∫ - ∞ ∞ F ( ω ) e j ω T n d ω f ( T n ) = 1 2 π ∫ - ∞ ∞ F ( ω ) e j ω T n d ω
(7)

which can be rewritten as an infinite sum of finite integrals in the form

f ( T n ) = 1 2 π ∑ ℓ ∫ 0 2 π / T F ( ω + 2 π ℓ / T ) e j ( ω + 2 π ℓ / T ) T n d ω f ( T n ) = 1 2 π ∑ ℓ ∫ 0 2 π / T F ( ω + 2 π ℓ / T ) e j ( ω + 2 π ℓ / T ) T n d ω
(8)
= 1 2 π ∫ 0 2 π / T ∑ ℓ F ( ω + 2 π ℓ / T ) e j ( ω + 2 π ℓ / T ) T n d ω = 1 2 π ∫ 0 2 π / T ∑ ℓ F ( ω + 2 π ℓ / T ) e j ( ω + 2 π ℓ / T ) T n d ω
(9)

where Fp(ω)Fp(ω) is a periodic function made up of shifted versions of F(ω)F(ω) (aliased) defined in Equation 10 Because Equation 9 and Equation 6 are equal for all TnTn and because the limits can be shifted by π/Tπ/T without changing the equality, the integrands are equal and we have

F d ( ω ) = 1 T ∑ ℓ F ( ω + 2 π ℓ / T ) = 1 T F p ( ω ) . F d ( ω ) = 1 T ∑ ℓ F ( ω + 2 π ℓ / T ) = 1 T F p ( ω ) .
(10)

where Fp(ω)Fp(ω) is a periodic function made up of shifted versions of F(ω)F(ω) as in Equation 9. The spectrum of the samples of f(t)f(t) is an aliased version of the spectrum of f(t)f(t) itself. The closer together the samples are taken, the further apart the centers of the aliased spectra are.

This result is very important in determining the frequency domain effects of sampling. It shows what the sampling rate should be and it is the basis for deriving the sampling theorem.

Samples of the Spectrum of a Sampled Signal and the DFT

Samples of the spectrum can be calculated from a finite number of samples of the original continuous-time signal using the DFT. If we let the length of the DFT be NN and separation of the samples in the frequency domain be ΔΔ and define the periodic functions

F p ( ω ) = ∑ ℓ F ( ω + N Δ ℓ ) F p ( ω ) = ∑ ℓ F ( ω + N Δ ℓ )
(11)

and

f p ( t ) = ∑ m f ( t + N T m ) f p ( t ) = ∑ m f ( t + N T m )
(12)

then from Equation 66 and Equation 10 samples of the DTFT of f(Tn)f(Tn) are

F p ( Δ k ) = T ∑ n f ( T n ) e - j T Δ n k F p ( Δ k ) = T ∑ n f ( T n ) e - j T Δ n k
(13)
= T ∑ m ∑ n = 0 N - 1 f ( T n + T N m ) e - j Δ ( T n + T N m ) k = T ∑ m ∑ n = 0 N - 1 f ( T n + T N m ) e - j Δ ( T n + T N m ) k
(14)
= T ∑ n = 0 N - 1 ∑ m f ( T n + T N m ) e - j Δ ( T n + T N m ) k , = T ∑ n = 0 N - 1 ∑ m f ( T n + T N m ) e - j Δ ( T n + T N m ) k ,
(15)

therefore,

F p ( Δ k ) = DFT { f p ( T n ) } F p ( Δ k ) = DFT { f p ( T n ) }
(16)

if ΔTN=2πΔTN=2π. This formula gives a method for approximately calculating values of the Fourier transform of a function by taking the DFT (usually with the FFT) of samples of the function. This formula can easily be verified by forming the Riemann sum to approximate the integrals in Equation 1 or Equation 2.

Samples of the DTFT of a Sequence

If the signal is discrete in origin and is not a sampled function of a continuous variable, the DTFT is defined with T=1T=1 as

H ( ω ) = ∑ n h ( n ) e - j ω n H ( ω ) = ∑ n h ( n ) e - j ω n
(17)

with an inverse

h ( n ) = 1 2 π ∫ - π π H ( ω ) e j ω n d ω . h ( n ) = 1 2 π ∫ - π π H ( ω ) e j ω n d ω .
(18)

If we want to calculate H(ω)H(ω), we must sample it and that is written as

H ( Δ k ) = ∑ n h ( n ) e - j Δ k n H ( Δ k ) = ∑ n h ( n ) e - j Δ k n
(19)

which after breaking the sum into an infinite sum of length-NN sums as was done in Equation 15 becomes

H ( Δ k ) = ∑ m ∑ n = 0 N - 1 h ( n + N m ) e - j Δ k n H ( Δ k ) = ∑ m ∑ n = 0 N - 1 h ( n + N m ) e - j Δ k n
(20)

if Δ=2π/NΔ=2π/N. This allows us to calculate samples of the DTFT by taking the DFT of samples of a periodized h(n)h(n).

H ( Δ k ) = DFT { h p ( n ) } . H ( Δ k ) = DFT { h p ( n ) } .
(21)

This a combination of the results in Equation 10 and in Equation 16.

Fourier Series Coefficients from the DFT

If the signal to be analyzed is periodic, the Fourier integral in Equation 1 does not converge to a function (it may to a distribution). This function is usually expanded in a Fourier series to define its spectrum or a frequency description. We will sample this function and show how to approximately calculate the Fourier series coefficients using the DFT of the samples.

Consider a periodic signal f˜(t)=f˜(t+P)f˜(t)=f˜(t+P) with NN samples taken every TT seconds to give Tn˜(t)Tn˜(t) for integer nn such that NT=PNT=P. The Fourier series expansion of f˜(t)f˜(t) is

f ˜ ( t ) = ∑ k = - ∞ ∞ C ( k ) e 2 π k t / P f ˜ ( t ) = ∑ k = - ∞ ∞ C ( k ) e 2 π k t / P
(22)

with the coefficients given in Equation 3. Samples of this are

f ˜ ( T n ) = ∑ k = - ∞ ∞ C ( k ) e 2 π k T n / P = ∑ k = - ∞ ∞ C ( k ) e 2 π k n / N f ˜ ( T n ) = ∑ k = - ∞ ∞ C ( k ) e 2 π k T n / P = ∑ k = - ∞ ∞ C ( k ) e 2 π k n / N
(23)

which is broken into a sum of sums as

f ˜ ( T n ) = ∑ ℓ - ∞ ∞ ∑ k = 0 N - 1 C ( k + N ℓ ) e 2 π ( k + N ℓ ) n / N = ∑ k = 0 N - 1 ∑ ℓ - ∞ ∞ C ( k + N ℓ ) e 2 π k n / N . f ˜ ( T n ) = ∑ ℓ - ∞ ∞ ∑ k = 0 N - 1 C ( k + N ℓ ) e 2 π ( k + N ℓ ) n / N = ∑ k = 0 N - 1 ∑ ℓ - ∞ ∞ C ( k + N ℓ ) e 2 π k n / N .
(24)

But the inverse DFT is of the form

f ˜ ( T n ) = 1 N ∑ k = 0 N - 1 F ( k ) e j 2 π n k / N f ˜ ( T n ) = 1 N ∑ k = 0 N - 1 F ( k ) e j 2 π n k / N
(25)

therefore,

DFT { f ˜ ( T n ) } = N ∑ ℓ C ( k + N ℓ ) = N C p ( k ) . DFT { f ˜ ( T n ) } = N ∑ ℓ C ( k + N ℓ ) = N C p ( k ) .
(26)

and we have our result of the relation of the Fourier coefficients to the DFT of a sampled periodic signal. Once again aliasing is a result of sampling.

Shannon's Sampling Theorem

Given a signal modeled as a real (sometimes complex) valued function of a real variable (usually time here), we define a bandlimited function as any function whose Fourier transform or spectrum is zero outside of some finite domain

| F ( ω ) | = 0 for | ω | > W | F ( ω ) | = 0 for | ω | > W
(27)

for some W<∞W<∞. The sampling theorem states that if f(t)f(t) is sampled

f s ( n ) = f ( T n ) f s ( n ) = f ( T n )
(28)

such that T<2π/WT<2π/W, then f(t)f(t) can be exactly reconstructed (interpolated) from its samples fs(n)fs(n) using

f ( t ) = ∑ n = - ∞ ∞ f s ( n ) sin ( π t / T - π n ) π t / T - π n . f ( t ) = ∑ n = - ∞ ∞ f s ( n ) sin ( π t / T - π n ) π t / T - π n .
(29)

This is more compactly written by defining the sinc function as

sinc ( x ) = sin ( x ) x sinc ( x ) = sin ( x ) x
(30)

which gives the sampling formula Equation 53 from Least Squared Error Design of FIR Filters the form

f ( t ) = ∑ n f s ( n ) sinc ( π t / T - π n ) . f ( t ) = ∑ n f s ( n ) sinc ( π t / T - π n ) .
(31)

The derivation of Equation 53 from Least Squared Error Design of FIR Filters or Equation 56 from Least Squared Error Design of FIR Filters can be done a number of ways. One of the quickest uses infinite sequences of delta functions and will be developed later in these notes. We will use a more direct method now to better see the assumptions and restrictions.

We first note that if f(t)f(t) is bandlimited and if T<2π/WT<2π/W then there is no overlap or aliasing in Fp(ω)Fp(ω). In other words, we can write Equation 2 as

f ( t ) = 1 2 π ∫ - ∞ ∞ F ( ω ) e j ω t d ω = 1 2 π ∫ - π / T π / T F p ( ω ) e j ω t d ω f ( t ) = 1 2 π ∫ - ∞ ∞ F ( ω ) e j ω t d ω = 1 2 π ∫ - π / T π / T F p ( ω ) e j ω t d ω
(32)

but

F p ( ω ) = ∑ ℓ F ( ω + 2 π ℓ / T ) = T ∑ n f ( T n ) e - j ω T n F p ( ω ) = ∑ ℓ F ( ω + 2 π ℓ / T ) = T ∑ n f ( T n ) e - j ω T n
(33)

therefore,

f ( t ) = 1 2 π ∫ - π / T π / T T ∑ n f ( T n ) e - j ω T n e j ω t d ω f ( t ) = 1 2 π ∫ - π / T π / T T ∑ n f ( T n ) e - j ω T n e j ω t d ω
(34)
= T 2 π ∑ n f ( T n ) ∫ - π / T π / T e j ( t - T n ) ω d ω = T 2 π ∑ n f ( T n ) ∫ - π / T π / T e j ( t - T n ) ω d ω
(35)
= ∑ n f ( T n ) sin ( π T t - π n ) π T t - π n = ∑ n f ( T n ) sin ( π T t - π n ) π T t - π n
(36)

which is the sampling theorem. An alternate derivation uses a rectangle function and its Fourier transform, the sinc function, together with convolution and multiplication. A still shorter derivation uses strings of delta function with convolutions and multiplications. This is discussed later in these notes.

There are several things to notice about this very important result. First, note that although f(t)f(t) is defined for all tt from only its samples, it does require an infinite number of them to exactly calculate f(t)f(t). Also note that this sum can be thought of as an expansion of f(t)f(t) in terms of an orthogonal set of basis function which are the sinc functions. One can show that the coefficients in this expansion of f(t)f(t) calculated by an inner product are simply samples of f(t)f(t). In other words, the sinc functions span the space of bandlimited functions with a very simple calculation of the expansion coefficients. One can ask the question of what happens if a signal is “under sampled". What happens if the reconstruction formula in Equation 12 from Continuous Time Signals is used when there is aliasing and Equation 57 from Least Squarred Error Design of FIR Filters is not true. We will not pursue that just now. In any case, there are many variations and generalizations of this result that are quite interesting and useful.

Calculation of the Fourier Transform and Fourier Series using the FFT

Most theoretical and mathematical analysis of signals and systems use the Fourier series, Fourier transform, Laplace transform, discrete-time Fourier transform (DTFT), or the z-transform, however, when we want to actually evaluate transforms, we calculate values at sample frequencies. In other words, we use the discrete Fourier transform (DFT) and, for efficiency, usually evaluate it with the FFT algorithm. An important question is how can we calculate or approximately calculate these symbolic formula-based transforms with our practical finite numerical tool. It would certainly seem that if we wanted the Fourier transform of a signal or function, we could sample the function, take its DFT with the FFT, and have some approximation to samples of the desired Fourier transform. We saw in the previous section that it is, in fact, possible provided some care is taken.

Summary

For the signal that is a function of a continuous variable we have

FT: f ( t ) → F ( ω ) DTFT: f ( T n ) → 1 T F p ( ω ) = 1 T ∑ ℓ F ( ω + 2 π ℓ / T ) DFT: f p ( T n ) → 1TFp(Δk) for ΔTN=2π FT: f ( t ) → F ( ω ) DTFT: f ( T n ) → 1 T F p ( ω ) = 1 T ∑ ℓ F ( ω + 2 π ℓ / T ) DFT: f p ( T n ) → 1TFp(Δk) for ΔTN=2π
(37)

For the signal that is a function of a discrete variable we have

DTFT: h ( n ) → H ( ω ) DFT: h p ( n ) → H ( Δ k ) for Δ N = 2 π DTFT: h ( n ) → H ( ω ) DFT: h p ( n ) → H ( Δ k ) for Δ N = 2 π
(38)

For the periodic signal of a continuous variable we have

FS: g ˜ ( t ) → C ( k ) DFT: g ˜ ( T n ) → NCp(k)forTN=P FS: g ˜ ( t ) → C ( k ) DFT: g ˜ ( T n ) → NCp(k)forTN=P
(39)

For the sampled bandlimited signal we have

Sinc: f ( t ) → f ( T n ) f ( t ) = ∑ n f ( T n ) sinc ( 2 π t / T - π n ) if F(ω)=0 for |ω|>2π/T Sinc: f ( t ) → f ( T n ) f ( t ) = ∑ n f ( T n ) sinc ( 2 π t / T - π n ) if F(ω)=0 for |ω|>2π/T
(40)

These formulas summarize much of the relations of the Fourier transforms of sampled signals and how they might be approximately calculate with the FFT. We next turn to the use of distributions and strings of delta functions as tool to study sampling.

Sampling Functions — the Shah Function

Th preceding discussions used traditional Fourier techniques to develop sampling tools. If distributions or delta functions are allowed, the Fourier transform will exist for a much larger class of signals. One should take care when using distributions as if they were functions but it is a very powerful extension.

There are several functions which have equally spaced sequences of impulses that can be used as tools in deriving a sampling formula. These are called “pitch fork" functions, picket fence functions, comb functions and shah functions. We start first with a finite length sequence to be used with the DFT. We define

⨿ M ( n ) = ∑ m = 0 L - 1 δ ( n - M m ) ⨿ M ( n ) = ∑ m = 0 L - 1 δ ( n - M m )
(41)

where N=LMN=LM.

D F T { ⨿ M ( n ) } = ∑ n = 0 N - 1 ∑ m = 0 L - 1 δ ( n - M m ) e - j 2 π n k / N D F T { ⨿ M ( n ) } = ∑ n = 0 N - 1 ∑ m = 0 L - 1 δ ( n - M m ) e - j 2 π n k / N
(42)
= ∑ m = 0 L - 1 ∑ n = 0 N - 1 δ ( n - M m ) e - j 2 π n k / N = ∑ m = 0 L - 1 ∑ n = 0 N - 1 δ ( n - M m ) e - j 2 π n k / N
(43)
= ∑ m = 0 L - 1 e - j 2 π M m k / N = ∑ m = 0 L - 1 e - j 2 π m k / L = ∑ m = 0 L - 1 e - j 2 π M m k / N = ∑ m = 0 L - 1 e - j 2 π m k / L
(44)
= { L < k > L = 0 0 otherwise ={ L < k > L = 0 0 otherwise
(45)
= L ∑ l = 0 M - 1 δ ( k - L l ) = L ⨿ L ( k ) =L ∑ l = 0 M - 1 δ ( k - L l ) =L ⨿ L (k)
(46)

For the DTFT we have a similar derivation:

D T F T { ⨿ M ( n ) } = ∑ n = - ∞ ∞ ∑ m = 0 L - 1 δ ( n - M m ) e - j ω n D T F T { ⨿ M ( n ) } = ∑ n = - ∞ ∞ ∑ m = 0 L - 1 δ ( n - M m ) e - j ω n
(47)
= ∑ m = 0 L - 1 ∑ n = - ∞ ∞ δ ( n - M m ) e - j ω n = ∑ m = 0 L - 1 ∑ n = - ∞ ∞ δ ( n - M m ) e - j ω n
(48)
= ∑ m = 0 L - 1 e - j ω M m = ∑ m = 0 L - 1 e - j ω M m
(49)
= { L ω = k 2 π / M 0 otherwise ={ L ω = k 2 π / M 0 otherwise
(50)
= ∑ l = 0 M - 1 δ ( ω - 2 π l / M l ) = K ⨿ 2π/M ( ω ) = ∑ l = 0 M - 1 δ(ω-2πl/Ml)=K ⨿ 2π/M (ω)
(51)

where KK is constant.

An alternate derivation for the DTFT uses the inverse DTFT.

I D T F T { ⨿ 2 π / M ( ω ) } = 1 2 π ∫ - π π ⨿ 2 π / M ( ω ) e j ω n d ω I D T F T { ⨿ 2 π / M ( ω ) } = 1 2 π ∫ - π π ⨿ 2 π / M ( ω ) e j ω n d ω
(52)
= 1 2 π ∫ - π π ∑ l δ ( ω - 2 π l / M ) e j ω n d ω = 1 2 π ∫ - π π ∑ l δ ( ω - 2 π l / M ) e j ω n d ω
(53)
= 1 2 π ∑ l ∫ - π π δ ( ω - 2 π l / M ) e j ω n d ω = 1 2 π ∑ l ∫ - π π δ ( ω - 2 π l / M ) e j ω n d ω
(54)
= 1 2 π ∑ l = 0 M - 1 e 2 π l n / M = { M / 2 π n = M 0 otherwise = 1 2 π ∑ l = 0 M - 1 e 2 π l n / M ={ M / 2 π n = M 0 otherwise
(55)
= ( M 2π ) ⨿ 2π/M ( ω ) =( M 2π ) ⨿ 2π/M (ω)
(56)

Therefore,

⨿ M ( n ) → ( 2π M ) ⨿ 2π/T ( ω ) ⨿ M (n)→( 2π M ) ⨿ 2π/T (ω)
(57)

For regular Fourier transform, we have a string of impulse functions in both the time and frequency. This we see from:

F T { ⨿ T ( t ) } = ∫ - ∞ ∞ ∑ n δ ( t - n T ) e - j ω t d t = ∑ n ∫ δ ( t - n T ) e - j ω t d t F T { ⨿ T ( t ) } = ∫ - ∞ ∞ ∑ n δ ( t - n T ) e - j ω t d t = ∑ n ∫ δ ( t - n T ) e - j ω t d t
(58)
= ∑ n e - j ω n T = { ∞ ω = 2 π / T 0 otherwise = ∑ n e - j ω n T ={ ∞ ω = 2 π / T 0 otherwise
(59)
= 2π T ⨿ 2π/T ( ω ) = 2π T ⨿ 2π/T (ω)
(60)

The multiplicative constant is found from knowing the result for a single delta function.

These “shah functions" will be useful in sampling signals in both the continuous time and discrete time cases.

Up–Sampling, Signal Stretching, and Interpolation

In several situations we would like to increase the data rate of a signal or, to increase its length if it has finite length. This may be part of a multi rate system or part of an interpolation process. Consider the process of inserting M-1M-1 zeros between each sample of a discrete time signal.

y ( n ) = { x ( n / M ) < n > M = 0 ( or n = kM ) 0 otherwise y(n)={ x ( n / M ) < n > M = 0 ( or n = kM ) 0 otherwise
(61)

For the finite length sequence case we calculate the DFT of the stretched or up–sampled sequence by

C s ( k ) = ∑ n = 0 M N - 1 y ( n ) W M N n k C s ( k ) = ∑ n = 0 M N - 1 y ( n ) W M N n k
(62)
C s ( k ) = ∑ n = 0 M N - 1 x ( n / M ) ⨿ M ( n ) W M N n k C s ( k ) = ∑ n = 0 M N - 1 x ( n / M ) ⨿ M ( n ) W M N n k
(63)

where the length is now NMNM and k=0,1,⋯,NM-1k=0,1,⋯,NM-1. Changing the index variable n=Mmn=Mm gives:

C s ( k ) = ∑ m = 0 N - 1 x ( m ) W N m k = C ( k ) . C s ( k ) = ∑ m = 0 N - 1 x ( m ) W N m k = C ( k ) .
(64)

which says the DFT of the stretched sequence is exactly the same as the DFT of the original sequence but over MM periods, each of length NN.

For up–sampling an infinitely long sequence, we calculate the DTFT of the modified sequence in Equation 34 from FIR Digital Filters as

C s ( ω ) = ∑ n = - ∞ ∞ x ( n / M ) ⨿ M ( n ) e - j ω n = ∑ m x ( m ) e - j ω M m C s ( ω ) = ∑ n = - ∞ ∞ x ( n / M ) ⨿ M ( n ) e - j ω n = ∑ m x ( m ) e - j ω M m
(65)
= C ( M ω ) = C ( M ω )
(66)

where C(ω)C(ω) is the DTFT of x(n)x(n). Here again the transforms of the up–sampled signal is the same as the original signal except over MM periods. This shows up here as Cs(ω)Cs(ω) being a compressed version of MM periods of C(ω)C(ω).

The z-transform of an up–sampled sequence is simply derived by:

Y ( z ) = ∑ n = - ∞ ∞ y ( n ) z - n = ∑ n x ( n / M ) ⨿ M ( n ) z - n = ∑ m x ( m ) z - M m Y ( z ) = ∑ n = - ∞ ∞ y ( n ) z - n = ∑ n x ( n / M ) ⨿ M ( n ) z - n = ∑ m x ( m ) z - M m
(67)
= X ( z M ) = X ( z M )
(68)

which is consistent with a complex version of the DTFT in Equation 66.

Notice that in all of these cases, there is no loss of information or invertibility. In other words, there is no aliasing.

Down–Sampling, Subsampling, or Decimation

In this section we consider the sampling problem where, unless there is sufficient redundancy, there will be a loss of information caused by removing data in the time domain and aliasing in the frequency domain.

The sampling process or the down sampling process creates a new shorter or compressed signal by keeping every MthMth sample of the original sequence. This process is best seen as done in two steps. The first is to mask off the terms to be removed by setting M-1M-1 terms to zero in each length-MM block (multiply x(n)x(n) by ⨿M(n)⨿M(n)), then that sequence is compressed or shortened by removing the M-1M-1 zeroed terms.

We will now calculate the length L=N/ML=N/M DFT of a sequence that was obtained by sampling every MM terms of an original length-NN sequence x(n)x(n). We will use the orthogonal properties of the basis vectors of the DFT which says:

∑ n = 0 M - 1 e - j 2 π n l / M = { M if n is an integer multiple of M 0 otherwise. ∑ n = 0 M - 1 e - j 2 π n l / M = { M if n is an integer multiple of M 0 otherwise.
(69)

We now calculate the DFT of the down-sampled signal.

C d ( k ) = ∑ m = 0 L - 1 x ( M m ) W L m k C d (k)= ∑ m = 0 L - 1 x(Mm) W L m k
(70)

where N = L M N=LM and k = 0,1,...,L-1 k=0,1,...,L-1. This is done by masking x ( n ) x(n) .

C d ( k ) = ∑ n = 0 N - 1 x ( n ) x M ( n ) W L n k C d (k)= ∑ n = 0 N - 1 x(n) x M (n) W L n k
(71)
= ∑ n = 0 N - 1 x ( n ) [ 1 M ∑ l = 0 M - 1 e - j 2 π n l / M ] e - j 2 π n k / N = ∑ n = 0 N - 1 x(n)[ 1 M ∑ l = 0 M - 1 e - j 2 π n l / M ] e - j 2 π n k / N
(72)
= 1 M ∑ l = 0 M - 1 ∑ n = 0 N - 1 x ( n ) e j 2 π ( k + L l ) n / N = 1 M ∑ l = 0 M - 1 ∑ n = 0 N - 1 x(n) e j 2 π ( k + L l ) n / N
(73)
= 1 M ∑ l = 0 M - 1 C ( k + L l ) = 1 M ∑ l = 0 M - 1 C(k+Ll)
(74)

The compression or removal of the masked terms is achieved in the frequency domain by using k = 0,1,...,L-1 k=0,1,...,L-1 This is a length-L DFT of the samples of x ( n ) x(n). Unless C(k)C(k) is sufficiently bandlimited, this causes aliasing and x(n)x(n) is not unrecoverable.

It is instructive to consider an alternative derivation of the above result. In this case we use the IDFT given by

x ( n ) = 1 N ∑ k = 0 N - 1 C ( k ) W N - n k . x ( n ) = 1 N ∑ k = 0 N - 1 C ( k ) W N - n k .
(75)

The sampled signal gives

y ( n ) = x ( M n ) = 1 N ∑ k = 0 N - 1 C ( k ) W N - M n k . y ( n ) = x ( M n ) = 1 N ∑ k = 0 N - 1 C ( k ) W N - M n k .
(76)

for n=0,1,⋯,L-1n=0,1,⋯,L-1. This sum can be broken down by

y ( n ) = 1 N ∑ k = 0 L - 1 ∑ l = 0 M - 1 C ( k + L l ) W N - M n ( k + L l ) . y ( n ) = 1 N ∑ k = 0 L - 1 ∑ l = 0 M - 1 C ( k + L l ) W N - M n ( k + L l ) .
(77)
= 1 N ∑ k = 0 L - 1 ∑ l = 0 M - 1 C ( k + L l ) W N - M n k . = 1 N ∑ k = 0 L - 1 ∑ l = 0 M - 1 C ( k + L l ) W N - M n k .
(78)

From the term in the brackets, we have

C s ( k ) = ∑ l = 0 M - 1 C ( k + L l ) C s ( k ) = ∑ l = 0 M - 1 C ( k + L l )
(79)

as was obtained in Equation 74.

Now consider still another derivation using shah functions. Let

x s ( n ) = ⨿ M ( n ) x ( n ) x s ( n ) = ⨿ M ( n ) x ( n )
(80)

From the convolution property of the DFT we have

C s ( k ) = L ⨿ L ( k ) * C ( k ) C s ( k ) = L ⨿ L ( k ) * C ( k )
(81)

therefore

C s ( k ) = ∑ l = 0 M - 1 C ( k + L l ) C s ( k ) = ∑ l = 0 M - 1 C ( k + L l )
(82)

which again is the same as in Equation 74.

We now turn to the down sampling of an infinitely long signal which will require use of the DTFT of the signals.

C s ( ω ) = ∑ m = - ∞ ∞ x ( M m ) e - j ω M m C s ( ω ) = ∑ m = - ∞ ∞ x ( M m ) e - j ω M m
(83)
= ∑ n x ( n ) ⨿ M ( n ) e - j ω n = ∑ n x ( n ) ⨿ M ( n ) e - j ω n
(84)
= ∑ n x ( n ) 1 M ∑ l = 0 M - 1 e - j 2 π n l / M e - j ω n = ∑ n x ( n ) 1 M ∑ l = 0 M - 1 e - j 2 π n l / M e - j ω n
(85)
= 1 M ∑ l = 0 M - 1 ∑ n x ( n ) e - j ( ω - 2 π l / M ) n = 1 M ∑ l = 0 M - 1 ∑ n x ( n ) e - j ( ω - 2 π l / M ) n
(86)
= 1 M ∑ l = 0 M - 1 C ( ω - 2 π l / M ) = 1 M ∑ l = 0 M - 1 C ( ω - 2 π l / M )
(87)

which shows the aliasing caused by the masking (sampling without compression). We now give the effects of compressing xs(n)xs(n) which is a simple scaling of ωω. This is the inverse of the stretching results in Equation 66.

C s ( ω ) = 1 M ∑ l = 0 M - 1 C ( ω / M - 2 π l / M ) . C s ( ω ) = 1 M ∑ l = 0 M - 1 C ( ω / M - 2 π l / M ) .
(88)

In order to see how the various properties of the DFT can be used, consider an alternate derivation which uses the IDTFT.

x ( n ) = 1 2 π ∫ - π π C ( ω ) e j ω n d ω x ( n ) = 1 2 π ∫ - π π C ( ω ) e j ω n d ω
(89)

which for the down–sampled signal becomes

x ( M n ) = 1 2 π ∫ - π π C ( ω ) e j ω M n d ω x ( M n ) = 1 2 π ∫ - π π C ( ω ) e j ω M n d ω
(90)

The integral broken into the sum of MM sections using a change of variables of ω=(ω1+2πl)/Mω=(ω1+2πl)/M giving

x ( M n ) = 1 2 π ∑ l = 0 M - 1 ∫ - π π C ( ω 1 / M + 2 π l / M ) e j ( ω 1 / M + 2 π l / M ) M n d ω 1 x ( M n ) = 1 2 π ∑ l = 0 M - 1 ∫ - π π C ( ω 1 / M + 2 π l / M ) e j ( ω 1 / M + 2 π l / M ) M n d ω 1
(91)

which shows the transform to be the same as given in Equation 9 from Chebyshev of Equal Ripple Error Approximation Filters.

Still another approach which uses the shah function can be given by

x s ( n ) = ⨿ M ( n ) x ( n ) x s ( n ) = ⨿ M ( n ) x ( n )
(92)

which has as a DTFT

C s ( ω ) = ( 2 π M ) ⨿ 2 π / M ( ω ) * C ( ω ) C s ( ω ) = ( 2 π M ) ⨿ 2 π / M ( ω ) * C ( ω )
(93)
= 2 π M ∑ l = 0 M - 1 C ( ω + 2 π l / M ) = 2 π M ∑ l = 0 M - 1 C ( ω + 2 π l / M )
(94)

which after compressing becomes

C s = 2 π M ∑ l = 0 M - 1 C ( ω / M + 2 π l / M ) C s = 2 π M ∑ l = 0 M - 1 C ( ω / M + 2 π l / M )
(95)

which is same as Equation 9 from Chebyshev of Equal Ripple Error Approximation Filters.

Now we consider the effects of down–sampling on the z-transform of a signal.

X ( z ) = ∑ n = - ∞ ∞ x ( n ) z - n X ( z ) = ∑ n = - ∞ ∞ x ( n ) z - n
(96)

Applying this to the sampled signal gives

X s ( z ) = ∑ n x ( M n ) z - M n = ∑ n x ( n ) ⨿ M ( n ) z - n X s ( z ) = ∑ n x ( M n ) z - M n = ∑ n x ( n ) ⨿ M ( n ) z - n
(97)
= ∑ n x ( n ) ∑ l = 0 M - 1 e j 2 π n l / M z - n = ∑ n x ( n ) ∑ l = 0 M - 1 e j 2 π n l / M z - n
(98)
= ∑ l = 0 M - 1 ∑ n x ( n ) e j 2 π l / M z - n = ∑ l = 0 M - 1 ∑ n x ( n ) e j 2 π l / M z - n
(99)
= ∑ l = 0 M - 1 X ( e - j 2 π l / M z ) = ∑ l = 0 M - 1 X ( e - j 2 π l / M z )
(100)

which becomes after compressing

= ∑ l = 0 M - 1 X ( e - j 2 π l / M z 1 / M ) . = ∑ l = 0 M - 1 X ( e - j 2 π l / M z 1 / M ) .
(101)

This concludes our investigations of the effects of down–sampling a discrete–time signal and we discover much the same aliasing properties as in sampling a continuous–time signal. We also saw some of the mathematical steps used in the development.

More Later

We will later develop relations of sampling to multirate systems, periodically time varying systems, and block processing. This should be a very effective formulation for teaching as well as research on these topics.

References

  1. Burrus, C. S. and Gopinath, R. A. (1993). Introduction to Wavelets and the Wavelet Transform. [Notes for the IEEE Signal Processing Society's tutorial program held in conjunction with the ICASSP-93 on April 26, 1993]. Minneapolis, MN: ICASSP-93 Tutorial.
  2. Burrus, C. Sidney and Gopinath, Ramesh A. and Guo, Haitao. (1998). Introduction to Wavelets and the Wavelet Transform. Upper Saddle River, NJ: Prentice Hall.
  3. Bracewell, R. N. (1985). The Fourier Transform and Its Applications. (Third). New York: McGraw-Hill.
  4. Crochiere, R. E. and Rabiner, L. R. (1983). Multirate Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall.
  5. Daubechies, Ingrid. (1992). Ten Lectures on Wavelets. [Notes from the 1990 CBMS-NSF Conference on Wavelets and Applications at Lowell, MA]. Philadelphia, PA: SIAM.
  6. Gopinath, R. A. and Burrus, C. S. (1992, May). On the Moments of the Scaling Function. In Proceedings of the IEEE International Symposium on Circuits and Systems. (Vol. 2, p. 963–966). ISCAS-92, San Diego, CA
  7. Jerri, Abdul J. (1977, November). The Shannon Sampling Theroem — Its Various Extensions and Applications: A Tutorial Review. Proceedings of the IEEE, 65(11), 1565–1596.
  8. Kramer, H. P. (1959). A Gereralized Sampling Theorem. J. Math. Phys., 38, 68–72.
  9. Linden, D. A. (1959, July). A Discussion of Sampling Theorems. Proceedings of the IRE, 47(7), 1219–1226.
  10. Marks II, R. J. (1991). Introduction to Shannon Sampling and Interpolation Theory. New York: Springer-Verlag.
  11. Marks II, Robert J. (Ed.). (1993). Advanced Topics in Shannon Sampling and Interpolation Theory. New York: Springer–Verlag.
  12. Meyer, Yves. (1993). Wavelets, Algorithms and Applications. [Translated by R. D. Ryan based on lectures given for the Spanish Institute in Madrid in Feb. 1991]. Philadelphia: SIAM.
  13. Nyquist, H. (1928). Certain Topics in Telegraph Transmission Theory. AIEE Transactions, 47, 617–644.
  14. Papoulis, A. (1962). The Fourier Integral and Its Applications. McGraw-Hill.
  15. Papoulis, A. (1977). Generalized Sampling Expansion. IEEE Trans. on Circuits and Systems, 24, 652–654.
  16. Papoulis, Athanasios. (1977). Signal Analysis. New York: McGraw-Hill.
  17. Shannon, C. E. (1949, January). Communication in the Presence of Noise. Proceedings of the IRE, 37, 10–21.
  18. Vaidyanathan, P. P. (1992). Multirate Systems and Filter Banks. Englewood Cliffs, NJ: Prentice-Hall.
  19. Young, R. M. (1980). An Introduction to Nonharmonic Fourier Series. New York: Academic Press.

Collection Navigation

Content actions

Download module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks