Skip to content Skip to navigation

Connexions

You are here: Home » Content » Convergence of the DTFT

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

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

      What is in a lens?

      Lens makers point to Connexions 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 Connexions 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
  • E-mail the author
  • Rate this module (How does the rating system work?)

    Rating system

    Ratings

    Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

    How to rate a module

    Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

    		(0 ratings)

Recently Viewed

This feature requires Javascript to be enabled.

Convergence of the DTFT

Module by: Richard Baraniuk

Summary: An overview of the convergence of the DTFT.

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

Note:

Use notation Xⅇⅈω X ω here.
The inverse DTFT
xn=∫-ππXⅇⅈωⅇⅈωn12πdω x n ω X ω ω n 1 2 (1)
is a finite integral, and therefore well defined. The forward DTFT
Xⅇⅈω=∑n=-∞∞xnⅇ-ⅈωn X ω n x n ω n (2)
is an infinite sum and therefore can exhibit strange behaviour.

We would like to say that Equation 1 and Equation 2 are inverses of each other, that is, that

∑n=-∞∞∫-ππXⅇⅈωⅇⅈωn12πdωⅇ-ⅈωn=Xⅇⅈω n ω X ω ω n 1 2 ω n X ω (3)

Unfortunately, Equation 3 is not always true. To study Equation 3, define the partial DTFT ∑n=-MMxnⅇ-ⅈωn n M M x n ω n and look at

∑n=-MM∫-ππXⅇⅈωⅇⅈωn12πdωⅇ-ⅈωn= X m ⅇⅈω n M M ω X ω ω n 1 2 ω n X m ω (4)
Let's study whether limM→∞ X m ⅇⅈω=Xⅇⅈω M X m ω X ω

FACT:

If ∑n=-∞∞xn<∞ n x n , then x M x M converges to x x uniformly, that is limM→∞|Xⅇⅈω− X m ⅇⅈω|=0 M X ω X m ω 0 for all ω ω

Note:

Although similar, uniform convergence is slightly stronger than pointwise convergence.

Uniform Convergence

Figure 1
Figure 1 (fig1.png)
as ε→0 ε 0 , we can increase M M to keep X m ⅇⅈω X m ω within ±ε ± ε of X m ⅇⅈω X m ω .

UNIFORM CONVERGENCE IS NICE!!!

Example 1

Think of DTFTs of these impulse responses of LTI systems:

  1. DELAY hn=δ n− n o h n δ n n o
  2. MOVING AVERAGE h n=1 M 1 + M 2 +1if- M 1 ≤n≤ M 2 0 if Otherwise h n 1 M 1 M 2 1 M 1 n M 2 0 Otherwise
  3. RECURSIVE (1st order): hn=anun h n a n u n
  4. ANY STABLE SYSTEM?

Unfortunately, there exists useful system/signals such that (Reference) does not hold uniformly.

Example 2: Key Example: Ideal Lowpass Fiter

Figure 2
Figure 2 (fig2.png)
hn=∫- ω c ω c 1ⅇⅈωn12πdω=sin ω c nπn h n ω ω c ω c 1 ω n 1 2 ω c n n for all n n
hn=sin ω c nπn h n ω c n n (5)
This is a sampled sinc function (well defined in terms of H H)
Figure 3
Figure 3 (fig3.png)

Notes

  1. hn h n is noncasual
  2. ∑n=-∞∞|hn|=∞ n h n
One practical way to get around the problems in notes 1 and 2 would be to use a truncated version of hn h n h M n=sin ω c nπnif-M≤n≤M 0 if else h M n ω c n n M n M 0 else
Figure 4
Figure 4 (fig4.png)
We would of course hope that h M ω=DTFT h M n h M ω DTFT h M n is a good approximation to the ideal response Hω H ω . Furthermore that the approximation gets better as M→∞ M .

Unfortunately, this is not the case!

H m ⅇⅈω=∑n=-MMhnⅇ-ⅈωn H m ω n M M h n ω n does not converge uniformly to Hⅇⅈω H ω

Figure 5
Figure 5 (fig5.png)
H M ⅇ-ⅈω H M ω cannot match the discontinuities in Hⅇⅈω H ω .

As M→∞ M , the oscillations converge to around ± ω c ± ω c without their magnitude going to zero!

In this case H M H M converges to H H in mean-square (engery) sense

limM→∞∫-ππ| H M ⅇⅈω−Hⅇⅈω|212πdω=0 M ω H M ω H ω 2 1 2 0 (6)
This is much weaker than uniform convergence.

Figure 6
Figure 6 (weak.png)

ie: DTFT has convergence in norm that is not pointwise and not uniformly.

Table 1: Symmetry Properties of the Discrete Time Fourier Transform
Sequence xn x n Fourier Transform Xⅇⅈω X ω
xn¯ x n Xⅇ-ⅈω¯ X ω
x-n¯ x n Xⅇ-ⅈω¯ X ω ("even")
ℜxn x n X e ⅇⅈω X e ω (conjugate-symmetric part of Xⅇⅈω X ω )
ⅈℑxn x n X o ⅇⅈω X o ω (conjugate-antisymmetric part of Xⅇⅈω X ω ) ("odd")
x e n x e n (conjugate-symmetric part of xn x n X R ⅇⅈω X R ω
x o n x o n (conjugate-antisymmetric part of xn x n ⅈ X I ⅇⅈω X I ω
Any real xn x n Xⅇⅈω=Xⅇ-ⅈω¯ X ω X ω (Fourier transform is conjugate-symmetric)
Any real xn x n X R ⅇⅈω= X R ⅇ-ⅈω X R ω X R ω (real part is even)
Any real xn x n X I ⅇⅈω=- X I ⅇ-ⅈω X I ω X I ω (imaginary part is odd)
Any real xn x n |Xⅇⅈω|=|Xⅇ-ⅈω| X ω X ω (magnitude is even)
Any real xn x n ∡Xⅇⅈω=-∡Xⅇ-ⅈω ∡ X ω ∡ X ω (phase is odd)
x e n x e n (even part of xn x n ) X R ⅇⅈω X R ω
x o n x o n (odd part of xn x n ) ⅈ X I ⅇⅈω X I ω

Notation:

Xω=Xⅇⅈω X ω X ω
Table 2: Discrete Time Fourier Transform Theorems
Sequence xn x n yn y n Fourier Transform Xⅇⅈω X ω Yⅇⅈω Y ω
axn+byn a x n b y n aXⅇⅈω+bYⅇⅈω a X ω b Y ω
xn− n d x n n d , ( n d n d an integer) ⅇ-ⅈω n d Xⅇⅈω ω n d X ω
ⅇⅈ ω o nxn ω o n x n Xⅇⅈω− ω o X ω ω o
x-n x n Xⅇ-ⅈω X ω Xⅇⅈω¯ X ω if xn x n real.
nxn n x n ⅈddωXⅇⅈω ω X ω
xn*yn x n y n XⅇⅈωYⅇⅈω X ω Y ω
xnyn x n y n 12π∫-ππXⅇⅈθYⅇⅈω−θdθ 1 2 θ X θ Y ω θ
Parseval's Theorem
∑n=-∞∞|xn|2=12π∫-ππ|Xⅇⅈω|2dω n x n 2 1 2 ω X ω 2
∑n=-∞∞xnyn¯=12π∫-ππXⅇⅈωYⅇⅈω¯dω n x n y n 1 2 ω X ω Y ω

Example 3: Modulation

ⅇⅈ ω o nxn ↔ DTFT Xω− ω o ω o n x n ↔ DTFT X ω ω o (7)

Proof

yn=ⅇⅈ ω o nxn y n ω o n x n

Figure 7
Figure 7 (fig7.png)
Yω=∑k=-∞∞xnⅇⅈ ω o nⅇ-ⅈωn=∑xnⅇ-ⅈω− ω o n=Xω− ω o Y ω k x n ω o n ω n k x n ω ω o n X ω ω o (8)

Figure 8
Figure 8 (fig8.png)
Table 3: Discrete Time Fourier Transform Pairs
Sequence Fourier Transform
δn δ n 1 1
δn− n o δ n n o ⅇ-ⅈω n .o ω n .o
1 1 -∞<n<∞ n ∑k=-∞∞2πδω+2πk k 2 δ ω 2 k
a n un a n u n |a|<1 a 1 11−aⅇ-ⅈω 1 1 a ω
un u n 11−ⅇ-ⅈω+∑k=-∞∞πδω+2πk 1 1 ω k δ ω 2 k
n+1 a n un n 1 a n u n |a|<1 a 1 11−aⅇ-ⅈω2 1 1 a ω 2
r n sin ω p n+1sin ω p un r n ω p n 1 ω p u n |a|<1 a 1 11−2rcos ω p ⅇ-ⅈω+r2ⅇ-ⅈ2ω 1 1 2 r ω p ω r 2 2 ω
sin ω c nπn ω c n n Xⅇⅈω= 1if|ω|< ω c 0if ω c <|ω|≤π X ω 1 ω ω c 0 ω c ω
xn= 1if 0≤n≤M 0ifotherwise x n 1 0 n M 0 otherwise sinωM+12sinω2ⅇ-ⅈωM2 ω M 1 2 ω 2 ω M 2
ⅇⅈ ω o n ω o n ∑k=-∞∞2πδω− ω o + 2 π k k 2 δ ω ω o 2 k
cos ω o n+φ ω o n φ π∑k=-∞∞ⅇⅈφδω− ω o + 2 π k +ⅇⅈφδω+ ω o + 2 π k k φ δ ω ω o 2 k φ δ ω ω o 2 k

Note:

" δ δ " is the felt column is different from " δ δ" in the right column. How/why?

Comments, questions, feedback, criticisms?

Send feedback