Lecture #8:

THE DISCRETE TIME FOURIER TRANSFORM (DTFT)

Motivation:

Extends notion of the frequency response of a DT system to the frequency content of a DT signal.

Basis of much of digital signal processing.

The development of the FFT algorithm to compute the DT Fourier series efficiently has revolutionized signal processing.

Outline:

DT processing of CT signals

The discrete time Fourier transform (DTFT)

Transform properties

Transform pairs

DT processing of CT signals revisited

Periodic DT signals

Summary of frequency domain representations of signals

The computation of Fourier transforms — the DFT and the FFT algorithm

Conclusion.

I. DT PROCESSING OF CT SIGNALS

DT filtering of CT signals can be modeled as a cascade of signal transformations. The C/D converter transforms a CT signal to a DT signal, the D/C converter transforms a DT signal to a CT signal.

1/ Model of C/D converter

The C/D converter has two components —a CT sampler and an I/S converter that transforms a CT impulse train to a DT sample train. The CT sampler is modeled as an impulse modulator with so that. Hence,

s ( t ) = ∑ m δ ( t − mT ) s ( t ) = ∑ m δ ( t − mT ) size 12{s \( t \) = Sum rSub { size 8{m} } {δ \( t - ital "mT" \) } } {}

x ˆ ( t ) = x ( t ) × s ( t ) x ˆ ( t ) = x ( t ) × s ( t ) size 12{ { hat {x}} \( t \) =x \( t \) times s \( t \) } {}

x ( t ) = ∑ m x ( mT ) δ ( t − mT ) x ( t ) = ∑ m x ( mT ) δ ( t − mT ) size 12{ { {x}} \( t \) = Sum cSub { size 8{m} } {x \( ital "mT" \) δ \( t - ital "mT" \) } } {}

x [ n ] = ∑ x ( mT ) δ [ n − m ] x [ n ] = ∑ x ( mT ) δ [ n − m ] size 12{x \[ n \] = Sum {x \( ital "mT" \) δ \[ n - m \] } } {}

2/ Motivation for the DTFT

The relation among the x(t), s(t), (t), and x[n] is shown below as is the relation among the X(f), S(f), and (f).

How should we represent the Fourier transform of x[n]?

How are the Fourier transforms of (t) and of x[n] related?

II. THE DISCRETE TIME FOURIER TRANSFORM (DTFT)

1/ Notation for CT and DT transforms

2/ Relation of Z transform and Fourier transform of a DT signal

The Z transform pair is defined as

X ˜ ( z ) = ∑ n = − ∞ ∞ x [ n ] z − n ⇔ z x [ n ] = 1 2πj ∫ X ˜ ( z ) z n − 1 dz X ˜ ( z ) = ∑ n = − ∞ ∞ x [ n ] z − n ⇔ z x [ n ] = 1 2πj ∫ X ˜ ( z ) z n − 1 dz size 12{ { tilde {X}} \( z \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x \[ n \] z} rSup { size 8{ - n} } { dlrarrow } cSup { size 8{z} } x \[ n \] = { {1} over {2πj} } Int { { tilde {X}} \( z \) } z rSup { size 8{n - 1} } ital "dz"} {}

If the ROC of (z) includes the unit circle then the Z transform can be evaluated on the unit circle,

X ˜ ( e j Ω ) = ∑ n = − ∞ ∞ x [ n ] e − j Ω n ⇔ z x [ n ] = 1 2π ∫ − π π X ˜ ( e j Ω ) e j Ω n d Ω X ˜ ( e j Ω ) = ∑ n = − ∞ ∞ x [ n ] e − j Ω n ⇔ z x [ n ] = 1 2π ∫ − π π X ˜ ( e j Ω ) e j Ω n d Ω size 12{ { tilde {X}} \( e rSup { size 8{j %OMEGA } } \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x \[ n \] e rSup { size 8{ - j %OMEGA n} } } { dlrarrow } cSup { size 8{z} } x \[ n \] = { {1} over {2π} } Int rSub { size 8{ - π} } rSup { size 8{π} } { { tilde {X}} \( e rSup { size 8{j %OMEGA } } } \) e rSup { size 8{j %OMEGA n} } d %OMEGA } {}

Finally, we let Ω = 2πφ and define the DTFT as

3/ Properties of the DTFT

a/ Periodicity

X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x [ n ] e − j2 πϕ n X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x [ n ] e − j2 πϕ n size 12{ { tilde {X}} \( ϕ \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x \[ n \] } e rSup { size 8{ - j2 ital "πϕ"n} } } {}

Note that

X ˜ ( ϕ + 1 ) = ∑ n = − ∞ ∞ x [ n ] e − j2π ( ϕ + 1 ) n X ˜ ( ϕ + 1 ) = ∑ n = − ∞ ∞ x [ n ] e − j2π ( ϕ + 1 ) n size 12{ { tilde {X}} \( ϕ+1 \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x \[ n \] e rSup { size 8{ - j2π \( ϕ+1 \) n} } } } {}

= ∑ n = − ∞ ∞ x [ n ] e − j2πn e − j2 πϕ n = ∑ n = − ∞ ∞ x [ n ] e − j2πn e − j2 πϕ n size 12{ {}= Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x \[ n \] e rSup { size 8{ - j2πn} } } e rSup { size 8{ - j2 ital "πϕ"n} } } {}

= X ˜ ( ϕ ) = X ˜ ( ϕ ) size 12{ {}= { tilde {X}} \( ϕ \) } {}

Therefore, (φ) is periodic with period equal to 1.

b/ Symmetry

X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x [ n ] e − j2 πϕ n X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x [ n ] e − j2 πϕ n size 12{ { tilde {X}} \( ϕ \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x \[ n \] e rSup { size 8{ - j2 ital "πϕ"n} } } } {}

Note that

X ˜ ( ϕ ) = ∑ n = − ∞ ∞ ( x e [ n ] + x 0 [ n ] ) ( cos [ 2 πϕ n ] − j sin [ 2 πϕ n ] ) , X ˜ ( ϕ ) = ∑ n = − ∞ ∞ ( x e [ n ] + x 0 [ n ] ) ( cos [ 2 πϕ n ] − j sin [ 2 πϕ n ] ) , size 12{ { tilde {X}} \( ϕ \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } { \( x rSub { size 8{e} } } \[ n \] +x rSub { size 8{0} } \[ n \] \) \( "cos" \[ 2 ital "πϕ"n \] - j"sin" \[ 2 ital "πϕ"n \] \) ,} {}

X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x e [ n ] ( cos [ 2 πϕ n ] − j ∑ n = − ∞ ∞ x 0 [ n ] sin [ 2 πϕ n ] , X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x e [ n ] ( cos [ 2 πϕ n ] − j ∑ n = − ∞ ∞ x 0 [ n ] sin [ 2 πϕ n ] , size 12{ { tilde {X}} \( ϕ \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x rSub { size 8{e} } } \[ n \] \( "cos" \[ 2 ital "πϕ"n \] - j Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x rSub { size 8{0} } } \[ n \] "sin" \[ 2 ital "πϕ"n \] ,} {}

X ˜ ( ϕ ) = X ˜ r ( ϕ ) + j X ˜ i ( ϕ ) X ˜ ( ϕ ) = X ˜ r ( ϕ ) + j X ˜ i ( ϕ ) size 12{ { tilde {X}} \( ϕ \) = { tilde {X}} rSub { size 8{r} } \( ϕ \) +j { tilde {X}} rSub { size 8{i} } \( ϕ \) } {}

where

X ˜ r ( ϕ ) = ∑ n = − ∞ ∞ x e [ n ] cos [ 2 πϕ n ] X ˜ r ( ϕ ) = ∑ n = − ∞ ∞ x e [ n ] cos [ 2 πϕ n ] size 12{ { tilde {X}} rSub { size 8{r} } \( ϕ \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x rSub { size 8{e} } } \[ n \] "cos" \[ 2 ital "πϕ"n \] } {}

X ˜ i ( ϕ ) = − ∑ n = − ∞ ∞ x 0 [ n ] sin [ 2 πϕ n ] X ˜ i ( ϕ ) = − ∑ n = − ∞ ∞ x 0 [ n ] sin [ 2 πϕ n ] size 12{ { tilde {X}} rSub { size 8{i} } \( ϕ \) = - Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x rSub { size 8{0} } \[ n \] "sin" \[ 2 ital "πϕ"n \] } } {}

We can infer symmetry properties of the DTFT of a real time function x[n].

X ˜ r ( ϕ ) = ∑ n = − ∞ ∞ x e [ n ] cos [ 2 πϕ n ] , even function of ϕ X ˜ r ( ϕ ) = ∑ n = − ∞ ∞ x e [ n ] cos [ 2 πϕ n ] , even function of ϕ size 12{ { tilde {X}} rSub { size 8{r} } \( ϕ \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x rSub { size 8{e} } } \[ n \] "cos" \[ 2 ital "πϕ"n \] ,"even function of "ϕ} {}

X ˜ i ( ϕ ) = − ∑ n = − ∞ ∞ x 0 [ n ] sin [ 2 πϕ n ] , odd function of ϕ X ˜ i ( ϕ ) = − ∑ n = − ∞ ∞ x 0 [ n ] sin [ 2 πϕ n ] , odd function of ϕ size 12{ { tilde {X}} rSub { size 8{i} } \( ϕ \) = - Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x rSub { size 8{0} } } \[ n \] "sin" \[ 2 ital "πϕ"n \] ,"odd function of "ϕ} {}

∣ X ˜ ( ϕ ) ∣ = X ˜ r 2 ( ϕ ) + X ˜ i 2 ( ϕ ) , even function of ϕ ∣ X ˜ ( ϕ ) ∣ = X ˜ r 2 ( ϕ ) + X ˜ i 2 ( ϕ ) , even function of ϕ size 12{ lline { tilde {X}} \( ϕ \) rline = sqrt { { tilde {X}} rSub { size 8{r} } rSup { size 8{2} } \( ϕ \) + { tilde {X}} rSub { size 8{i} } rSup { size 8{2} } \( ϕ \) } ,"even function of "ϕ} {}

Therefore, if

x[n] (φ)

x[n] X˜X˜ size 12{ { tilde {X}}} {}(φ)

Real and even function of n Real and even function of φ

Real and odd function of n Imaginary and odd function of φ

The angle can be computed as follows,

tan − 1 ( X ˜ i ( ϕ ) X ˜ r ( ϕ ) ) for { X ˜ π + tan − 1 ( X ˜ i ( ϕ ) X ˜ r ( ϕ ) ) for { X ˜ ∠ X ˜ ( ϕ ) = { r ( ϕ ) > 0 tan − 1 ( X ˜ i ( ϕ ) X ˜ r ( ϕ ) ) for { X ˜ π + tan − 1 ( X ˜ i ( ϕ ) X ˜ r ( ϕ ) ) for { X ˜ ∠ X ˜ ( ϕ ) = { r ( ϕ ) > 0 size 12{∠ { tilde {X}} \( ϕ \) =alignl { stack { left lbrace "tan" rSup { size 8{ - 1} } \( { { { tilde {X}} rSub { size 8{i} } \( ϕ \) } over { { tilde {X}} rSub { size 8{r} } \( ϕ \) } } \) " " ital "for"" {" tilde ital {X}} rSub { size 8{r} } \( ϕ \) >0 {} # right none left lbrace π+"tan" rSup { size 8{ - 1} } \( { { { tilde {X}} rSub { size 8{i} } \( ϕ \) } over { { tilde {X}} rSub { size 8{r} } \( ϕ \) } } \) " " ital "for"" {" tilde ital {X}} rSub { size 8{r} } \( ϕ \) <0 {} # right no } } lbrace } {}

But, since ±n2π can always be added to the angle, and since tan−1(X˜i(ϕ)X˜r(ϕ))tan−1(X˜i(ϕ)X˜r(ϕ)) size 12{"tan" rSup { size 8{ - 1} } \( { { { tilde {X}} rSub { size 8{i} } \( ϕ \) } over { { tilde {X}} rSub { size 8{r} } \( ϕ \) } } \) } {}is an odd function of φ,

− tan − 1 ( x ˜ i ( ϕ ) x ˜ r ( ϕ ) ) for { X ˜ − π − tan − 1 ( x ˜ i ( ϕ ) x ˜ r ( ϕ ) ) for { X ˜ ∠ X ˜ ( − ϕ ) = { r ( ϕ ) > 0 − tan − 1 ( x ˜ i ( ϕ ) x ˜ r ( ϕ ) ) for { X ˜ − π − tan − 1 ( x ˜ i ( ϕ ) x ˜ r ( ϕ ) ) for { X ˜ ∠ X ˜ ( − ϕ ) = { r ( ϕ ) > 0 size 12{∠ { tilde {X}} \( - ϕ \) =alignl { stack { left lbrace - "tan" rSup { size 8{ - 1} } \( { { { tilde {x}} rSub { size 8{i} } \( ϕ \) } over { { tilde {x}} rSub { size 8{r} } \( ϕ \) } } \) " " ital "for"" {" tilde ital {X}} rSub { size 8{r} } \( ϕ \) >0 {} # right none left lbrace - π - "tan" rSup { size 8{ - 1} } \( { { { tilde {x}} rSub { size 8{i} } \( ϕ \) } over { { tilde {x}} rSub { size 8{r} } \( ϕ \) } } \) " " ital "for"" {" tilde ital {X}} rSub { size 8{r} } \( ϕ \) <0 {} # right no } } lbrace } {}

Therefore,  X˜X˜ size 12{ { tilde {X}}} {}(φ) is an odd function of φ.

c/ Time shift

{} x [ n − n 0 ] ⇔ F X ˜ ( ϕ ) e − j2 πϕ n 0 x [ n − n 0 ] ⇔ F X ˜ ( ϕ ) e − j2 πϕ n 0 size 12{x \[ n - n rSub { size 8{0} } \] { size 24{ dlrarrow } } cSup { size 8{F} } { tilde {X}} \( ϕ \) e rSup { size 8{ - j2 ital "πϕ"n rSub { size 6{0} } } } } {}

The proof follows from either the analysis or the synthesis formula,

x [ n ] = ∫ − 1 / 2 1 / 2 X ˜ ( ϕ ) e j2 πϕ n dϕ x [ n ] = ∫ − 1 / 2 1 / 2 X ˜ ( ϕ ) e j2 πϕ n dϕ size 12{x \[ n \] = Int cSub { size 8{ - 1/2} } cSup { size 8{1/2} } { { tilde {X}} \( ϕ \) e rSup { size 8{j2 ital "πϕ"n} } } dϕ} {}

x [ n − n 0 ] = ∫ − 1 / 2 1 / 2 X ˜ ( ϕ ) e j2 πϕ ( n − n 0 ) dϕ x [ n − n 0 ] = ∫ − 1 / 2 1 / 2 X ˜ ( ϕ ) e j2 πϕ ( n − n 0 ) dϕ size 12{x \[ n - n rSub { size 8{0} } \] = Int cSub { - 1/2} cSup {1/2} { { tilde {X}} \( ϕ \) e rSup { size 8{j2 ital "πϕ" \( n - n rSub { size 6{0} } \) } } } size 12{dϕ}} {}

x [ n − n 0 ] = ∫ − 1 / 2 1 / 2 X ˜ ( ϕ ) e j2 πϕ n 0 e j2 πϕ n dϕ x [ n − n 0 ] = ∫ − 1 / 2 1 / 2 X ˜ ( ϕ ) e j2 πϕ n 0 e j2 πϕ n dϕ size 12{x \[ n - n rSub { size 8{0} } \] = Int cSub { - 1/2} cSup {1/2} { { tilde {X}} \( ϕ \) e rSup { size 8{j2 ital "πϕ"n rSub { size 6{0} } } } e rSup {j2 ital "πϕ"n} } size 12{dϕ}} {}

d/ Frequency shift

x [ n ] e j2 πϕ 0 ⇔ F X ˜ ( ϕ − ϕ 0 ) x [ n ] e j2 πϕ 0 ⇔ F X ˜ ( ϕ − ϕ 0 ) size 12{x \[ n \] e rSup { size 8{j2 ital "πϕ" rSub { size 6{0} } } } { size 24{ dlrarrow } } cSup {F} { tilde { size 12{X}} \( ϕ - ϕ rSub {0} } size 12{ \) }} {}

The proof follows from either the analysis or the synthesis formula,

X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x [ n ] e − j2 πϕ n , X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x [ n ] e − j2 πϕ n , size 12{ { tilde {X}} \( ϕ \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x \[ n \] e rSup { size 8{ - j2 ital "πϕ"n} } } ,} {}

X ˜ ( ϕ ) = ∑ n = − ∞ ∞ ( x e [ n ] + x 0 [ n ] ) ( cos [ 2 πϕ n ] − j sin [ 2 πϕ n ] ) , X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x e [ n ] ( cos [ 2 πϕ n ] − j ∑ n = − ∞ ∞ x 0 [ n ] sin [ 2 πϕ n ] , X ˜ ( ϕ ) = X ˜ r ( ϕ ) + j X ˜ i ( ϕ ) X ˜ ( ϕ ) = ∑ n = − ∞ ∞ ( x e [ n ] + x 0 [ n ] ) ( cos [ 2 πϕ n ] − j sin [ 2 πϕ n ] ) , X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x e [ n ] ( cos [ 2 πϕ n ] − j ∑ n = − ∞ ∞ x 0 [ n ] sin [ 2 πϕ n ] , X ˜ ( ϕ ) = X ˜ r ( ϕ ) + j X ˜ i ( ϕ ) alignl { stack { size 12{ { tilde {X}} \( ϕ \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } { \( x rSub { size 8{e} } } \[ n \] +x rSub { size 8{0} } \[ n \] \) \( "cos" \[ 2 ital "πϕ"n \] - j"sin" \[ 2 ital "πϕ"n \] \) ,} {} # { tilde {X}} \( ϕ \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x rSub { size 8{e} } } \[ n \] \( "cos" \[ 2 ital "πϕ"n \] - j Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x rSub { size 8{0} } } \[ n \] "sin" \[ 2 ital "πϕ"n \] , {} # { tilde {X}} \( ϕ \) = { tilde {X}} rSub { size 8{r} } \( ϕ \) +j { tilde {X}} rSub { size 8{i} } \( ϕ \) {} } } {}

X ˜ ( ϕ − ϕ 0 ) = ∑ n = − ∞ ∞ x [ n ] e − j2π ( ϕ − ϕ 0 ) n , X ˜ ( ϕ − ϕ 0 ) = ∑ n = − ∞ ∞ x [ n ] e − j2π ( ϕ − ϕ 0 ) n , size 12{ { tilde {X}} \( ϕ - ϕ rSub { size 8{0} } \) = Sum cSub {n= - infinity } cSup { infinity } {x \[ n \] e rSup { size 8{ - j2π \( ϕ - ϕ rSub { size 6{0} } \) n} } } size 12{,}} {}

X ˜ ( ϕ − ϕ 0 ) = ∑ n = − ∞ ∞ x [ n ] e j2 πϕ 0 n e − j2 πϕ n X ˜ ( ϕ − ϕ 0 ) = ∑ n = − ∞ ∞ x [ n ] e j2 πϕ 0 n e − j2 πϕ n size 12{ { tilde {X}} \( ϕ - ϕ rSub { size 8{0} } \) = Sum cSub {n= - infinity } cSup { infinity } {x \[ n \] e rSup { size 8{j2 ital "πϕ" rSub { size 6{0} } n} } e rSup { - j2 ital "πϕ"n} } } {}

e/ Multiplication of sequences

What is the discrete time Fourier transform of z[n] = x[n]y[n]?

Z ˜ ( ϕ ) = ∑ n x [ n ] y [ n ] e − j2 πϕ n , Z ˜ ( ϕ ) = ∑ n x [ n ] y [ n ] e − j2 πϕ n , size 12{ { tilde {Z}} \( ϕ \) = Sum cSub { size 8{n} } {x \[ n \] y \[ n \] e rSup { size 8{ - j2 ital "πϕ"n} } } ,} {}

= ∑ n x [ n ] ( ∫ − 1 / 2 1 / 2 Y ˜ ( η ) e − j2 πη n dη ) e − j2 πϕ n , = ∑ n x [ n ] ( ∫ − 1 / 2 1 / 2 Y ˜ ( η ) e − j2 πη n dη ) e − j2 πϕ n , size 12{ {}= Sum cSub { size 8{n} } {x \[ n \] \( Int rSub { size 8{ - 1/2} } rSup { size 8{1/2} } { { tilde {Y}} \( η \) } } e rSup { size 8{ - j2 ital "πη"n} } dη \) e rSup { size 8{ - j2 ital "πϕ"n} } ,} {}

= ∫ − 1 / 2 1 / 2 dη Y ˜ ( η ) ∑ n x [ n ] e − j2π ( ϕ − η ) n = ∫ − 1 / 2 1 / 2 dη Y ˜ ( η ) ∑ n x [ n ] e − j2π ( ϕ − η ) n size 12{ {}= Int rSub { size 8{ - 1/2} } rSup { size 8{1/2} } {dη { tilde {Y}} \( η \) } Sum cSub { size 8{n} } {x \[ n \] e rSup { size 8{ - j2π \( ϕ - η \) n} } } } {}

= ∫ − 1 / 2 1 / 2 X ˜ ( ϕ − η ) Y ˜ ( η ) dη = ∫ 1 > X ˜ ( ϕ − η ) Y ˜ ( η ) d η = ∫ − 1 / 2 1 / 2 X ˜ ( ϕ − η ) Y ˜ ( η ) dη = ∫ 1 > X ˜ ( ϕ − η ) Y ˜ ( η ) d η size 12{ {}= Int rSub { size 8{ - 1/2} } rSup { size 8{1/2} } { { tilde {X}} \( ϕ - η \) { tilde {Y}} \( η \) } dη= Int rSub { size 8{<1>} } { { tilde {X}} \( ϕ - η \) { tilde {Y}} \( η \) d} η} {}

This convolution over one period is called circular convolution and we use the symbol ⊗ as follows

X ˜ ( ϕ ) ⊗ Y ˜ ( ϕ ) = ∫ 1 > X ˜ ( ϕ − η ) Y ˜ ( η ) d η = ∫ η 0 η 0 + 1 X ˜ ( ϕ − η ) Y ˜ ( η ) d η X ˜ ( ϕ ) ⊗ Y ˜ ( ϕ ) = ∫ 1 > X ˜ ( ϕ − η ) Y ˜ ( η ) d η = ∫ η 0 η 0 + 1 X ˜ ( ϕ − η ) Y ˜ ( η ) d η size 12{ { tilde {X}} \( ϕ \) ⊗ { tilde {Y}} \( ϕ \) = Int rSub { size 8{<1>} } { { tilde {X}} \( ϕ - η \) { tilde {Y}} \( η \) d} η= Int rSub { size 8{η rSub { size 6{0} } } } rSup {η rSub { size 6{0} } +1} { { tilde {X}} \( ϕ - η \) { tilde {Y}} \( η \) d} size 12{η}} {}

f/ Summary of simple properties

Most proofs of DT Fourier transform properties are simple and similar to those of CT Fourier transform properties. Some important properties are summarized here.

g/ Plotting the DTFT

Because the DTFT of a real DT function

has a period of 1,

has conjugate symmetry (real part and magnitude of the DTFT are even functions of φ, the imaginary part and angle are odd functions of φ),

the DTFT need only be plotted over the frequency range 0 ≤ φ ≤ 0.5. Nevertheless, we shall plot several DTFTs over a larger range of φ to reinforce the periodicity and symmetry properties.

III. DT FOURIER TRANSFORM PAIRS

1/ Unit samples in time and their relatives

From the definition

X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x [ n ] e − j2 ϕπ n X ˜ ( ϕ ) = ∑ n = − ∞ ∞ x [ n ] e − j2 ϕπ n size 12{ { tilde {X}} \( ϕ \) = Sum cSub { size 8{n= - infinity } } cSup { size 8{ infinity } } {x \[ n \] e rSup { size 8{ - j2 ital "ϕπ"n} } } } {}

it is apparent that

δ [ n ] ⇔ F 1 δ [ n ] ⇔ F 1 size 12{δ \[ n \] { size 24{ dlrarrow } } cSup { size 8{F} } 1} {}

Shifting and combining unit samples in time yields

δ [ n ] ⇔ F 1 δ [ n ] ⇔ F 1 size 12{δ \[ n \] { size 24{ dlrarrow } } cSup { size 8{F} } 1} {}

δ [ n ] ⇔ F 1, δ [ n ] ⇔ F 1, size 12{δ \[ n \] { size 24{ dlrarrow } } cSup { size 8{F} } 1,} {}

δ [ n − n 0 ] ⇔ F e − j2 πϕ n 0 , δ [ n − n 0 ] ⇔ F e − j2 πϕ n 0 , δ [ n − n 0 ] ⇔ F e − j2 πϕ n 0 , δ [ n − n 0 ] ⇔ F e − j2 πϕ n 0 , size 12{δ \[ n - n rSub { size 8{0} } \] { size 24{ dlrarrow } } cSup { size 8{F} } e rSup { size 8{ - j2 ital "πϕ"n rSub { size 6{0} } } } ,δ \[ n - n rSub {0} size 12{ \] { size 24{ dlrarrow } } cSup {F} } size 12{e rSup { - j2 ital "πϕ"n rSub { size 6{0} } } } size 12{,}} {}

1 2 ( δ [ n + n 0 ] + δ [ n − n 0 ] ) ⇔ F cos ( 2 πϕ n 0 ) , 1 2 ( δ [ n + n 0 ] + δ [ n − n 0 ] ) ⇔ F cos ( 2 πϕ n 0 ) , 1 2 ( δ [ n + n 0 ] + δ [ n − n 0 ] ) ⇔ F cos ( 2 πϕ n 0 ) , 1 2 ( δ [ n + n 0 ] + δ [ n − n 0 ] ) ⇔ F cos ( 2 πϕ n 0 ) , size 12{ { {1} over {2} } \( δ \[ n+n rSub { size 8{0} } \] +δ \[ n - n rSub { size 8{0} } \] \) { size 24{ dlrarrow } } cSup { size 8{F} } "cos" \( 2 ital "πϕ"n rSub { size 8{0} } \) , { {1} over {2} } \( δ \[ n+n rSub { size 8{0} } \] +δ \[ n - n rSub { size 8{0} } \] \) { size 24{ dlrarrow } } cSup { size 8{F} } "cos" \( 2 ital "πϕ"n rSub { size 8{0} } \) ,} {}

1 2j ( δ [ n + n 0 ] − δ [ n − n 0 ] ) ⇔ F sin ( 2 πϕ n 0 ) , 1 2j ( δ [ n + n 0 ] − δ [ n − n 0 ] ) ⇔ F sin ( 2 πϕ n 0 ) , size 12{ { {1} over {2j} } \( δ \[ n+n rSub { size 8{0} } \] - δ \[ n - n rSub { size 8{0} } \] \) { size 24{ dlrarrow } } cSup { size 8{F} } "sin" \( 2 ital "πϕ"n rSub { size 8{0} } \) ,} {}

1 2 ( δ [ n + n 0 ] − δ [ n − n 0 ] ) ⇔ F j sin ( 2 πϕ n 0 ) , 1 2 ( δ [ n + n 0 ] − δ [ n − n 0 ] ) ⇔ F j sin ( 2 πϕ n 0 ) , size 12{ { {1} over {2} } \( δ \[ n+n rSub { size 8{0} } \] - δ \[ n - n rSub { size 8{0} } \] \) { size 24{ dlrarrow } } cSup { size 8{F} } j"sin" \( 2 ital "πϕ"n rSub { size 8{0} } \) ,} {}

Note that all the DTFTs are periodic in φ with period φ = 1. [Note symmetry properties for imaginary time functions.]

2/ Unit impulse trains in frequency and their relatives

From the definition

we can derive the time sequences that correspond to periodic impulse trains in φ. Since (φ) has period φ = 1, the impulse trains have the same period.

x [ n ] = ∫ − 1 / 2 1 / 2 X ˜ ( ϕ ) e j2 πϕ n dϕ x [ n ] = ∫ − 1 / 2 1 / 2 X ˜ ( ϕ ) e j2 πϕ n dϕ size 12{x \[ n \] = Int rSub { size 8{ - 1/2} } rSup { size 8{1/2} } { { tilde {X}} \( ϕ \) e rSup { size 8{j2 ital "πϕ"n} } } dϕ} {}

Shifting and combining unit impulses in frequency yields

∑ k = − ∞ ∞ δ ( ϕ + k ) ⇔ F 1 ∑ k = − ∞ ∞ δ ( ϕ + k ) ⇔ F 1 size 12{ Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {δ \( ϕ+k \) { size 24{ dlrarrow } } cSup { size 8{F} } } 1} {}

∑ k = − ∞ ∞ δ ( ϕ + k ) ⇔ F 1 ∑ k = − ∞ ∞ δ ( ϕ + k ) ⇔ F 1 size 12{ Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {δ \( ϕ+k \) { size 24{ dlrarrow } } cSup { size 8{F} } } 1} {}

∑ k = − ∞ ∞ δ ( ϕ − ϕ 0 + k ) ⇔ F e j2 πϕ 0 n , ∑ k = − ∞ ∞ δ ( ϕ − ϕ 0 + k ) ⇔ F e j2 πϕ 0 n , size 12{ Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {δ \( ϕ - ϕ rSub { size 8{0} } +k \) { size 24{ dlrarrow } } cSup { size 8{F} } } e rSup { size 8{j2 ital "πϕ" rSub { size 6{0} } n} } ,} {}

∑ k = − ∞ ∞ 1 2 ( ( δ ( ϕ − ϕ 0 + k ) + δ ( ϕ + ϕ 0 + k ) ) ) ⇔ F cos ( 2 πϕ 0 n ) , ∑ k = − ∞ ∞ 1 2 ( ( δ ( ϕ − ϕ 0 + k ) + δ ( ϕ + ϕ 0 + k ) ) ) ⇔ F cos ( 2 πϕ 0 n ) , size 12{ Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } { { {1} over {2} } \( \( δ \( ϕ - ϕ rSub { size 8{0} } +k \) +δ \( ϕ+ϕ rSub { size 8{0} } +k \) \) \) { size 24{ dlrarrow } } cSup { size 8{F} } } "cos" \( 2 ital "πϕ" rSub { size 8{0} } n \) ,} {} ∑ k = − ∞ ∞ 1 2j ( ( δ ( ϕ − ϕ 0 + k ) − δ ( ϕ + ϕ 0 + k ) ) ) ⇔ F sin ( 2 πϕ 0 n ) , ∑ k = − ∞ ∞ 1 2j ( ( δ ( ϕ − ϕ 0 + k ) − δ ( ϕ + ϕ 0 + k ) ) ) ⇔ F sin ( 2 πϕ 0 n ) , size 12{ Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } { { {1} over {2j} } \( \( δ \( ϕ - ϕ rSub { size 8{0} } +k \) - δ \( ϕ+ϕ rSub { size 8{0} } +k \) \) \) { size 24{ dlrarrow } } cSup { size 8{F} } } "sin" \( 2 ital "πϕ" rSub { size 8{0} } n \) ,} {}

3/ Rectangular pulse in time

x [ n ] = ∑ m = − M M δ [ n − m ] x [ n ] = ∑ m = − M M δ [ n − m ] size 12{x \[ n \] = Sum cSub { size 8{m= - M} } cSup { size 8{M} } {δ \[ n - m \] } } {}

We can take the DTFT of this equation as follows.

X ˜ ( ϕ ) = ∑ m = − M M e − j2 πϕ n 0 = 1 + ∑ m = 14 M 2 cos ( 2πmϕ ) X ˜ ( ϕ ) = ∑ m = − M M e − j2 πϕ n 0 = 1 + ∑ m = 14 M 2 cos ( 2πmϕ ) size 12{ { tilde {X}} \( ϕ \) = Sum cSub {m= - M} cSup {M} {e rSup { size 8{ - j2 ital "πϕ"n rSub { size 6{0} } } } } size 12{ {}=1+ Sum cSub {m="14"} cSup {M} {2"cos" \( 2πmϕ \) } }} {}

A closed form solution is obtained by using the formula for the sum of a finite geometric series,

X ˜ ( ϕ ) = ∑ m = − M M ( e − j2 πϕ ) m = e j2 πϕ M − e − j2 πϕ ( M + 1 ) 1 − e − j2 πϕ X ˜ ( ϕ ) = ∑ m = − M M ( e − j2 πϕ ) m = e j2 πϕ M − e − j2 πϕ ( M + 1 ) 1 − e − j2 πϕ size 12{ { tilde {X}} \( ϕ \) = Sum cSub { size 8{m= - M} } cSup { size 8{M} } { \( e rSup { size 8{ - j2 ital "πϕ"} } } \) rSup { size 8{m} } = { {e rSup { size 8{j2 ital "πϕ"M} } - e rSup { size 8{ - j2 ital "πϕ" \( M+1 \) } } } over {1 - e rSup { size 8{ - j2 ital "πϕ"} } } } } {}

A factor of e−jπφ can be factored out of the numerator and the denominator and the resulting expressions reduced to

X ˜ ( ϕ ) = ( sin ( π ( 2M + 1 ) ϕ ) sin ( πϕ ) ) X ˜ ( ϕ ) = ( sin ( π ( 2M + 1 ) ϕ ) sin ( πϕ ) ) size 12{ { tilde {X}} \( ϕ \) = \( { {"sin" \( π \( 2M+1 \) ϕ \) } over {"sin" \( ital "πϕ" \) } } \) } {}

A single unit sample has a DTFT that is 1. Addition of a pair of unit samples at ±1 adds a cosine wave of frequency 1 to the DTFT. Addition of a pair of unit samples at ±2 adds a cosine of frequency 2 to the DTFT. As more unit samples are added, x[n] → 1 and the DTFT approaches a periodic impulse train of frequency 1.

4/ Causal exponential

We have seen that

x [ n ] = α n u [ n ] ⇔ Z X ˜ ( z ) = 1 1 − αz − 1 for ∣ z ∣ > ∣ α ∣ x [ n ] = α n u [ n ] ⇔ Z X ˜ ( z ) = 1 1 − αz − 1 for ∣ z ∣ > ∣ α ∣ size 12{x \[ n \] =α rSup { size 8{n} } u \[ n \] { size 24{ dlrarrow } } cSup { size 8{Z} } { tilde {X}} \( z \) = { {1} over {1 - αz rSup { size 8{ - 1} } } } " " ital "for"" " lline z rline > lline α rline } {}

Provided |α| < 1, we can evaluate the DTFT as

X ˜ ( ϕ ) = 1 1 − αe − j2 πϕ X ˜ ( ϕ ) = 1 1 − αe − j2 πϕ size 12{ { tilde {X}} \( ϕ \) = { {1} over {1 - αe rSup { size 8{ - j2 ital "πϕ"} } } } } {}

We have already examined these functions in connection with DT filters discussed in previous section.

A pole at 0 < α < 1 yields a DTFT with large spectral components at low frequencies. As |α| decreases, the unit sample response approaches a unit sample, the DTFT magnitude approaches 1 (0 dB) and the angle approaches 0.

A pole at −1 < α < 0 yields a DTFT with large spectral components at high frequencies. As |α| decreases, the unit sample response approaches a unit sample, the DTFT magnitude approaches 1 (0 dB) and the angle approaches 0.

IV. MODEL OF C/D CONVERTER

We now return to the model of the C/D converter and relate the DTFT of a sequence to the CTFT of a sampled time function.

1/ Representation of FT of CT impulse train and DT sample train

x ˆ ( t ) = ∑ m x ( mT ) δ ( t − mT ) ⇔ CTFT X ˆ ( f ) = ∑ m x ( mT ) e − j2ρ mfT x ˆ ( t ) = ∑ m x ( mT ) δ ( t − mT ) ⇔ CTFT X ˆ ( f ) = ∑ m x ( mT ) e − j2ρ mfT size 12{ { hat {x}} \( t \) = Sum cSub { size 8{m} } {x \( ital "mT" \) δ \( t - ital "mT" \) } { dlrarrow } cSup { size 8{ ital "CTFT"} } { hat {X}} \( f \) = Sum cSub { size 8{m} } {x \( ital "mT" \) e rSup { size 8{ - j2ρ ital "mfT"} } } } {}

x [ n ] = ∑ m x ( mT ) δ [ n − m ] ⇔ DTFT X ˆ ( ϕ ) = ∑ m x ( mT ) e − j2ρmϕ x [ n ] = ∑ m x ( mT ) δ [ n − m ] ⇔ DTFT X ˆ ( ϕ ) = ∑ m x ( mT ) e − j2ρmϕ size 12{x \[ n \] = Sum cSub { size 8{m} } {x \( ital "mT" \) δ \[ n - m \] } { dlrarrow } cSup { size 8{ ital "DTFT"} } { hat {X}} \( ϕ \) = Sum cSub { size 8{m} } {x \( ital "mT" \) e rSup { size 8{ - j2ρmϕ} } } } {}

Note that X^(f) and X~(φ) are the same for

ϕ = fT = f 1 T = frequency sampling frquency ϕ = fT = f 1 T = frequency sampling frquency size 12{ϕ= ital "fT"= { {f} over { { {1} over {T} } } } = { { ital "frequency"} over { ital "sampling"" " ital "frequency"} } } {}

2/ Completion of the model of a CD converter

3/ Model of C/D converter

4/ Model of D/C converter

Two-minute miniquiz problem

Problem 21-1 — DT filtering of a CT signal

The signal x(t) whose spectrum is band-limited to |f| < 100 is sampled at the Nyquist rate and filtered by the DT filter shown. Find the spectrum of y(t), Y(f).

Solution

Sampling at the Nyquist rate implies that the sampling frequency is 2 × 100 = 200.

V. PERIODIC DISCRETE TIME SEQUENCES

For a periodic sequence of period N

x[n+N] = x[n]

This example shows a periodic sequence for which N = 4.

1/ Discrete time Fourier series (DTFS)

A periodic DT signal with period N can be expanded in a Fourier series of complex exponential sequences of the form

ψ m [ n ] = e j2π ( m N ) n ψ m [ n ] = e j2π ( m N ) n size 12{ψ rSub { size 8{m} } \[ n \] =e rSup { size 8{j2π \( { {m} over {N} } \) n} } } {}

DT frequency

These exponentials have frequencies that are multiples of the fundamental frequency 1/N. Since

ψ m + N [ n ] = e j2π ( m + N N ) n = e j2π ( m N ) n = ψ m [ n ] ψ m + N [ n ] = e j2π ( m + N N ) n = e j2π ( m N ) n = ψ m [ n ] size 12{ψ rSub { size 8{m} } +N rSup { size 8{ \[ n \] } } =e rSup { size 8{j2π \( { {m+N} over {N} } \) n} } =e rSup { size 8{j2π \( { {m} over {N} } \) n} } =ψ rSub { size 8{m} } \[ n \] } {}

there are only N distinct frequencies for a fundamental frequency of 1/N. As a consequence, only N frequencies are required to represent a periodic DT signal of period N.

The DT Fourier series can be expressed as

x [ n ] = ∑ m = 0 N − 1 X ˜ [ m ] e j2π mn N x [ n ] = ∑ m = 0 N − 1 X ˜ [ m ] e j2π mn N size 12{x \[ n \] = Sum cSub { size 8{m=0} } cSup { size 8{N - 1} } { { tilde {X}} \[ m \] e rSup { size 8{j2π { { ital "mn"} over {N} } } } } } {}

X ˜ [ m ] = 1 N ∑ n = 0 N − 1 x [ n ] e − j2π mn N X ˜ [ m ] = 1 N ∑ n = 0 N − 1 x [ n ] e − j2π mn N size 12{ { tilde {X}} \[ m \] = { {1} over {N} } Sum cSub { size 8{n=0} } cSup { size 8{N - 1} } {x \[ n \] e rSup { size 8{ - j2π { { ital "mn"} over {N} } } } } } {}

where

x[n] is periodic in n with period N,

and

is periodic in m with period N.

2/ DTFS — periodic unit sample train

The Fourier series of the periodic unit sample train is

S ˜ [ m ] = 1 N ∑ n = 0 N − 1 δ [ n ] e − j2π mn N = 1 N S ˜ [ m ] = 1 N ∑ n = 0 N − 1 δ [ n ] e − j2π mn N = 1 N size 12{ { tilde {S}} \[ m \] = { {1} over {N} } Sum cSub { size 8{n=0} } cSup { size 8{N - 1} } {δ \[ n \] e rSup { size 8{ - j2π { { ital "mn"} over {N} } } } } = { {1} over {N} } } {}

Therefore,

s [ n ] = ∑ m = − ∞ ∞ δ [ n − mN ] = 1 N ∑ m = 0 N − 1 e − j2π m N s [ n ] = ∑ m = − ∞ ∞ δ [ n − mN ] = 1 N ∑ m = 0 N − 1 e − j2π m N size 12{s \[ n \] = Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } {δ \[ n - ital "mN" \] } = { {1} over {N} } Sum cSub { size 8{m=0} } cSup { size 8{N - 1} } {e rSup { size 8{ - j2π { {m} over {N} } } } } } {}

3/ DTFT of a periodic unit sample train

We have two expressions for a periodic unit sample train,

s [ n ] = ∑ m = − ∞ ∞ δ [ n − mN ] = 1 N ∑ m = 0 N − 1 e − j2π m N s [ n ] = ∑ m = − ∞ ∞ δ [ n − mN ] = 1 N ∑ m = 0 N − 1 e − j2π m N size 12{s \[ n \] = Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } {δ \[ n - ital "mN" \] } = { {1} over {N} } Sum cSub { size 8{m=0} } cSup { size 8{N - 1} } {e rSup { size 8{ - j2π { {m} over {N} } } } } } {}

The DTFT of the first expression is

S ˜ [ ϕ ] = ∑ m = − ∞ ∞ e − j2 πϕ mN S ˜ [ ϕ ] = ∑ m = − ∞ ∞ e − j2 πϕ mN size 12{ { tilde {S}} \[ ϕ \] = Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } {e rSup { size 8{ - j2 ital "πϕ" ital "mN"} } } } {}

To obtain the DTFT of the second expression recall that

e j2π mn N ⇔ F ∑ k = − ∞ ∞ δ ( ϕ − m N − k ) e j2π mn N ⇔ F ∑ k = − ∞ ∞ δ ( ϕ − m N − k ) size 12{e rSup { size 8{j2π { { ital "mn"} over {N} } } } { dlrarrow } cSup { size 8{F} } Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {δ \( ϕ - { {m} over {N} } - k \) } } {}

so that

∑ m = 0 N − 1 e j2π mn N ⇔ F ∑ m = 0 N − 1 ∑ k = − ∞ ∞ δ ( ϕ − m N − k ) = ∑ m = − ∞ ∞ ( ϕ − m N ) ∑ m = 0 N − 1 e j2π mn N ⇔ F ∑ m = 0 N − 1 ∑ k = − ∞ ∞ δ ( ϕ − m N − k ) = ∑ m = − ∞ ∞ ( ϕ − m N ) size 12{ Sum cSub { size 8{m=0} } cSup { size 8{N - 1} } {e rSup { size 8{j2π { { ital "mn"} over {N} } } } } { dlrarrow } cSup { size 8{F} } Sum cSub { size 8{m=0} } cSup { size 8{N - 1} } { Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {δ \( ϕ - { {m} over {N} } - k \) } } = Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } { \( ϕ - { {m} over {N} } \) } } {}

The periodic unit sample train

s [ n ] = ∑ m = − ∞ ∞ δ [ n − mN ] = 1 N ∑ m = 0 N − 1 e j2π mn N s [ n ] = ∑ m = − ∞ ∞ δ [ n − mN ] = 1 N ∑ m = 0 N − 1 e j2π mn N size 12{s \[ n \] = Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } {δ \[ n - ital "mN" \] } = { {1} over {N} } Sum cSub { size 8{m=0} } cSup { size 8{N - 1} } {e rSup { size 8{j2π { { ital "mn"} over {N} } } } } } {}

has the Fourier transform

S ˜ [ ϕ ] = ∑ m = − ∞ ∞ e − j2 πϕ mM = 1 N ∑ m = − ∞ ∞ δ ( ϕ − m N ) S ˜ [ ϕ ] = ∑ m = − ∞ ∞ e − j2 πϕ mM = 1 N ∑ m = − ∞ ∞ δ ( ϕ − m N ) size 12{ { tilde {S}} \[ ϕ \] = Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } {e rSup { size 8{ - j2 ital "πϕ" ital "mM"} } } = { {1} over {N} } Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } {δ \( ϕ - { {m} over {N} } \) } } {}

Therefore, the DT Fourier transform of a periodic unit sample train in time is a periodic unit impulse train in frequency.

4/ DTFT of an arbitrary periodic sequence

We can form an arbitrary periodic sequence x[n] by convolving an aperiodic sequence xN[n] that represents one period of the periodic sequence with a periodic unit sample sequence s[n]. Recall

s [ n ] = ∑ m = − ∞ ∞ δ [ n − mN ] s [ n ] = ∑ m = − ∞ ∞ δ [ n − mN ] size 12{s \[ n \] = Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } {δ \[ n - ital "mN" \] } } {}

and

x [ n ] = x N [ n ] ∗ s [ n ] = x N [ n ] ∗ ∑ m = − ∞ ∞ δ [ n − mN ] = ∑ m = − ∞ ∞ x N [ n − mN ] x [ n ] = x N [ n ] ∗ s [ n ] = x N [ n ] ∗ ∑ m = − ∞ ∞ δ [ n − mN ] = ∑ m = − ∞ ∞ x N [ n − mN ] size 12{x \[ n \] =x rSub { size 8{N} } \[ n \] * s \[ n \] =x rSub { size 8{N} } \[ n \] * Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } {δ \[ n - ital "mN" \] ={}} Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } {x rSub { size 8{N} } \[ n - ital "mN" \] } } {}

Therefore,

X ˜ ( ϕ ) = X ˜ N ( ϕ ) × S ˜ ( ϕ ) = X ˜ N ( ϕ ) × 1 N ∑ m = − ∞ ∞ δ ( ϕ − m N ) ∑ m = − ∞ ∞ X ˜ N ( m / N ) N δ ( ϕ − m N ) X ˜ ( ϕ ) = X ˜ N ( ϕ ) × S ˜ ( ϕ ) = X ˜ N ( ϕ ) × 1 N ∑ m = − ∞ ∞ δ ( ϕ − m N ) ∑ m = − ∞ ∞ X ˜ N ( m / N ) N δ ( ϕ − m N ) alignl { stack { size 12{ { tilde {X}} \( ϕ \) = { tilde {X}} rSub { size 8{N} } \( ϕ \) times { tilde {S}} \( ϕ \) = { tilde {X}} rSub { size 8{N} } \( ϕ \) times { {1} over {N} } Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } {δ \( ϕ - { {m} over {N} } \) } } {} # = Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } { { { { tilde {X}} rSub { size 8{N} } \( m/N \) } over {N} } δ \( ϕ - { {m} over {N} } \) } {} } } {}

The DTFT of a periodic sequence consists of scaled impulses at multiples of the fundamental frequency.

5/ Connection between DTFT and DTFS of an arbitrary periodic sequence

The DTFT of an arbitrary periodic sequence is

X ~ [ ϕ ] = ∑ m = − ∞ ∞ X ( m / N ) N ~ δ ( ϕ − m N ) X ~ [ ϕ ] = ∑ m = − ∞ ∞ X ( m / N ) N ~ δ ( ϕ − m N ) size 12{ {X} cSup { size 8{ "~" } } \[ ϕ \] = Sum cSub { size 8{m= - infinity } } cSup { size 8{ infinity } } { { { {X \( m/N \) } over {N} } } cSup { size 8{ "~" } } } δ \( ϕ - { {m} over {N} } \) } {}

Now we evaluate the areas of the impulses

X ~ N ( m N ) N = ∑ n = 0 N − 1 x [ n ] e − j2π mn N = X ~ [ m ] X ~ N ( m N ) N = ∑ n = 0 N − 1 x [ n ] e − j2π mn N = X ~ [ m ] size 12{ { { {X} cSup { size 8{ "~" } } rSub { size 8{N} } \( { {m} over {N} } \) } over {N} } = Sum cSub { size 8{n=0} } cSup { size 8{N - 1} } {x \[ n \] e rSup { size 8{ - j2π { { ital "mn"} over {N} } } } } = {X} cSup { size 8{ "~" } } \[ m \] } {}

Therefore, just as for periodic CT signals, the areas of the impulses in the DTFT equal the Fourier series coefficients of the DT periodic function.

6/ Summary of frequency domain representations of signals

The red lines and dots indicate the locations of frequency components in the complex s and z planes used to represent aperiodic and periodic CT and DT functions.

7/ The computation of Fourier transforms

Fourier transforms arise in diverse physical situations. The following is a short list of applications areas.

Linear systems — output FT is the input FT times the frequency response.

Probability — characteristic function of a random variable is the Fourier transform of the probability density function

Optics — spatial light amplitude distributions at the front and back focal planes of a converging lens are a FT pair

Random processes — power density spectrum of a random process is the Fourier transform of the autocorrelation function

Quantum physics — particle position and momentum are related by a Fourier transform, a result that gives rise to the uncertainty principle

X-ray crystallography, CAT scans, PET scans — involve the projections of three-dimensional Fourier transforms of structures onto a plane

Boundary value problems — solutions to many systems described by partial differential equations are found by use of the Fourier transform

In all of these and many other problems, it is rarely possible to compute the Fourier transform analytically. Hence, it is desirable to develop computational methods to solve such problems. In 1965 Cooley and Tukey devised an algorithm, called the fast Fourier transform (FFT) algorithm, to compute Fourier transforms efficiently. This computational advance and the large increase in speed and memory capacity of computers has made it routinely possible to solve increasingly more complex problems.

8/ The discrete time Fourier series revisited

Recall that the DTFS pair is

x [ n ] = ∑ m = 0 N − 1 X ~ [ m ] e j2π mn N and X ~ [ m ] = 1 N ∑ n = 0 N − 1 x [ n ] e − j2π mn N x [ n ] = ∑ m = 0 N − 1 X ~ [ m ] e j2π mn N and X ~ [ m ] = 1 N ∑ n = 0 N − 1 x [ n ] e − j2π mn N size 12{x \[ n \] = Sum cSub { size 8{m=0} } cSup { size 8{N - 1} } { {X} cSup { size 8{ "~" } } \[ m \] e rSup { size 8{j2π { { ital "mn"} over {N} } } } } " and " {X} cSup { size 8{ "~" } } \[ m \] = { {1} over {N} } Sum cSub { size 8{n=0} } cSup { size 8{N - 1} } {x \[ n \] e rSup { size 8{ - j2π { { ital "mn"} over {N} } } } } } {}

Note that this pair relates the set of N values of x[n] to the N values of .

We can regard x[n] for one period as samples of x(t) and for one period as samples of X(f). The Fourier transform interpreted in this way is called the discrete Fourier transform (DFT), which is distinct from the DTFT.

Note that to compute

from x[n] (or the reverse)

x [ n ] = ∑ n = 0 N − 1 X ~ [ m ] e j2π mn N and X ~ [ m ] = 1 N ∑ n = 0 N − 1 x [ n ] e − j2π mn N x [ n ] = ∑ n = 0 N − 1 X ~ [ m ] e j2π mn N and X ~ [ m ] = 1 N ∑ n = 0 N − 1 x [ n ] e − j2π mn N size 12{x \[ n \] = Sum cSub { size 8{n=0} } cSup { size 8{N - 1} } { {X} cSup { size 8{ "~" } } \[ m \] e rSup { size 8{j2π { { ital "mn"} over {N} } } } } " and " {X} cSup { size 8{ "~" } } \[ m \] = { {1} over {N} } Sum cSub { size 8{n=0} } cSup { size 8{N - 1} } {x \[ n \] e rSup { size 8{ - j2π { { ital "mn"} over {N} } } } } } {}

requires solution of N algebraic equations with N unknowns. The solution involves N multiplications and additions for each value of m, i.e., N2 operations to compute from x[n]. The FFT algorithm is a method for solving these equations that reduces the number of computations from N2 to N log2N. This is a remarkable reduction in computation. For example, suppose N = 1024, then N2=1,048,576 and N log2N = 1024 × 10 = 10, 240 a saving in computations of a factor of 102.4.

VI. CONCLUSIONS

The DTFT characterizes the frequency content of a DT signal in a manner analogous to the way the CTFT characterizes the frequency content of CT signal. Expansion/compression of DT signals was interpreted as compression/ expansion of the DTFT.

The frequency domain methods were extended to cover both CT and DT signals and both aperiodic and periodic signals.

The DFT, for which an efficient computational algorithm exists (FFT algorithm), was defined as a method to relate samples of the time function to samples of the Fourier transform.