Read dft.pdf text version
Discrete Fourier Transform
Spring 2012
Outline
Periodic Sequences Discrete Fourier Series Fourier Transform of Periodic Signals Sampling the Fourier Transform Discrete Fourier Transform Linear Convolution Using the Discrete Fourier Transform Discrete Cosine Transforms
Discrete Fourier Transform
Periodic Sequences
Definition (periodic sequence, periodic signal) A sequence x [n] is said to be periodic with period N if ~ x [n + N] = x [n], ~ ~ For example, a periodic impulse train
for any integer n.
p [n] = ~
r =
[n  rN],
n = . . . , 1, 0, 1, 2, . . .
a complex exponential signal e ~k [n] = e j (
2k N
)n ,
n = . . . , 1, 0, 1, 2, . . .
Discrete Fourier Transform
Discrete Fourier Series
Theorem (discrete Fourier series) Any periodic sequence can be represented as a sum of the complex exponentials. Such a representation is called a discrete Fourier series (DFS). Specifically, let x [n] be a periodic sequence with period ~ N. Then N1 2 1 ~ X [k]e j ( N k )n . x [n] = ~ N k=0 Note that the frequencies of the complex exponentials are related to the period N via 2k k = . N
Discrete Fourier Transform
Orthogonality
The complex exponentials of a DFS are orthogonal. That is,
N1
ej(
n=0
2k N
)n e j
2k N
n
= Nkk .
If k = k ,
N1
e
n=0
j ( 2k )n j N
e
2k N
N1 n
=
n=0
e
j
2(kk ) N
n
=
1e
j j
2(kk ) N 2(kk ) N
nN
= 0.
1e
2k N
If k = k ,
N1
e
n=0
j ( 2k )n j N
N1 n
e
=
n=0
1 = N.
Discrete Fourier Transform
DFS Coefficients
Theorem (DFS coefficients) ~ The coefficients X [k] of the DFS of x [n] can be obtained by ~
N1
~ X [k] =
n=0
x [n]e j ( ~
2k N
)n .
Proof:
N1 N1 N1
2k N
x [n]e j ( ~
n=0
)n =
1~ j X [k ]e N n=0 k =0 e
j
2k N
2k N
n j ( 2k )n N
e
1 = N
N1
N1
~ X [k ]
k =0 n=0
n j ( 2k )n N
e
1 = N
N1
~ X [k ]Nkk
k =0
~ = X [k].
Discrete Fourier Transform
Periodicity
Theorem ~ X [k] can be treated as a spectral sequence. Clearly, it is periodic with the same period as x [n]. ~
N1
~ X [k + N] =
n=0 N1
x [n]e j ( N (k+N))n ~
2
=
n=0
x [n]e j ( N k )n ~
2
~ = X [k].
Discrete Fourier Transform
The Analysis Equation
Definition (analysis equation) Defining WN
e j( N ) ,
2
we can rewrite the equation for DFS coefficients as
N1
~ X [k] =
n=0
kn x [n]WN . ~
This is called the analysis equation. ~ It yields the weights of the complex exponentials X [k], which is an analysis of the spectral content of x [n]. ~
Discrete Fourier Transform
The Synthesis Equation
Definition (synthesis equation) Complementary to the analysis equation, we have x [n] = ~ 1 N
N1 kn ~ X [k]WN . k=0
This is called the synthesis equation. Definition (DFS pair) ~ The following notation is used to denote a DFS pair (~ [n], X [k]): x x [n] ~
DFS
~ X [k].
Discrete Fourier Transform
Example: Temporal Periodic Impulse Train
Consider a periodic impulse train in the temporal domain
p [n] = ~
r =
[n  rN].
By the analysis equation, the DFS coefficients are
N1
~ P[k] =
n=0
0 kn p [n]WN = WN = 1. ~
That is, the spectral sequence is flat.
Discrete Fourier Transform
Example: Spectral Periodic Impulse Train
Consider a periodic impulse train in the spectral domain
~ Y [k] =
r =
N [k  rN].
By the synthesis equation, the signal is y [n] = ~ 1 N
N1 kn 0 ~ Y [k]WN = WN = 1. k=0
That is, the temporal sequence is flat.
Discrete Fourier Transform
Periodic Rectangular Sequence
Suppose x [n] is periodic with period N = 10. In one period, ~ x [n] = ~ 1, 0 n 4, 0, 5 n 9.
By the analysis equation, the DFS coefficients are
4
~ X [k] =
n=0
kn 1 · W10 =
5k 1  W10 k 1  W10
=e
j 4 k 10
sin k 2 sin k 10
.
Discrete Fourier Transform
Properties of DFS
linearity a~[n] + b~ [n] x y shift x [n  m] ~ duality
DFS ~ x [n] X [k] ~ DFS
DFS
~ ~ aX [k] + bY [k]
km ~ WN X [k]
DFS ~ X [n] N x [k] ~
symmetry ~ x [n] X [k], ~
DFS
~ x [n] X [k] ~
DFS
Discrete Fourier Transform
Proof: Shift
Let y [n] ~ x [n  m]. According to the analysis equation, we have ~
N1
~ Y [k] =
n=0 N1
kn y [n]WN ~
=
n=0 N1
kn x [n  m]WN ~
=
n=0
x [n  m]WN ~
N1
k(nm)
km WN
km = WN
x [n  m]WN ~
k(nm)
=
n=0 km ~ WN X [k].
Discrete Fourier Transform
Proof: Duality
Begin with the synthesis equation. 1 x [n] = ~ N
n n N1 kn ~ X [k]WN k=0 N1 kn ~ X [k]WN k=0 N1
  N x [n] =  ~   N x [k] =  ~
n=0 n k
kn ~ X [n]WN .
~ The last one is the analysis equation of X [n]! Therefore,
DFS ~ X [n] N x [k]. ~
Discrete Fourier Transform
Periodic Convolution
Definition (periodic convolution) The periodic convolution of two periodic sequences of period N, ~ X [n] and y [n], is defined as ~
N1
x [n] ~
y [n] = ~
m=0
x [m]~ [n  m]. ~ y
Let z [n] x [n] y [n]. ~ ~ ~ It is not difficult to see that z [n] a periodic sequence of period N. ~ What is the DFS for z [n]? ~
Discrete Fourier Transform
Periodic Convolution Theorem
Theorem (periodic convolution theorem) x [n] ~ y [n] ~
DFS
~ ~ X [k]Y [k]. x [n] ~ y [n], we have ~
k(nm)
Applying the analysis equation to z [n] ~
N1 N1 kn z [n]WN = ~ n=0 N1 n=0 N1 km x [m]WN ~ m=0 n=0 m=0 N1
~ Z [k] = =
km x [m]~ [n  m] WN WN ~ y
y [n  m]WN ~
k(nm)
~ ~ = X [k]Y [k].
Discrete Fourier Transform
Spectrum of a DiscreteTime Signal
Definition (spectrum of a DT signal) The spectrum of a discretetime signal is the discretetime Fourier transform (DTFT) of the signal. That is,
X (e ) =
n=
j
x[n]e jn .
Note that X (e j ) is a function of a continuous variable is a periodic function with period 2 completely determines x[n], with 1 x[n] = 2
X (e j )e jn d ,

n = . . . , 1, 0, 1, . . .
Discrete Fourier Transform
Spectrum of a Complex Exponential
Theorem The spectrum of a complex exponential with frequency 0 , e [n] = e j0 n , ~ is ~ E (e j ) = 2
l=
 < 0 < ,
(  0  2l ).
Discrete Fourier Transform
Proof
~ The inverse DTFT of E (e j ) must be e [n], ~ 1 2

~ E (e j )e jn d = e [n] = e j0 n . ~
Therefore, within the integration interval [, ], ~ E (e j ) = 2(  0 ). ~ Furthermore, since E (e j ) must be periodic, we have
~ E (e j ) = 2
l=
(  0  2l ).
Discrete Fourier Transform
Periodic Signal as Sum of Complex Exponentials
By the synthesis equation, a periodic signal x [n] can be expressed as ~ 1 x [n] = ~ N
N1
2 ~ X [k]e j N kn ,
k=0
2
which is a sum of complex exponentials e j ( N k )n .
Discrete Fourier Transform
Spectrum of a Periodic Singal
Using the DTFT of e j ( N k )n , we have the spectrum of x [n], ~
2
1 ~ X (e j ) = N = =
N1
~ X [k] 2
k=0 N1 l=

2k + 2l N
2 N 2 N
2(k + lN) ~ X [k + lN]  N .
k=0 l=
k =
2k ~ X [k ]  N
Clearly, the spectrum of a periodic sequence is completely contained in the DFS coefficients ~ X [k], k = 0, 1, . . . N  1.
Discrete Fourier Transform
Example: Periodic Impulse Train
As an example, consider the periodic impulse train with period N
p [n] = ~
r =
[n  rN].
To find the spectrum, we only need to know ~ P[k], k = 0, 1, . . . N  1. ~ By the analysis equation, P[k] = 1. Therefore, the spectrum is 2 2k ~  P(e j ) = N k = N
.
Discrete Fourier Transform
Periodic Signal as Convolution with Impulse Train
Let x [n] be a periodic sequence with period N. Let x[n] be one ~ period of x [n], i. e., ~ x[n] = (0 n N  1) ? x [n] : 0. ~ Then x [n] can be expressed via x[n] as ~
x [n] = ~
r =
x[n  rN]
= x[n]
r =
[n  rN]
= x[n] p [n] ~
Discrete Fourier Transform
Periodic Extension
Definition (periodic extension) Given a signal s[n],
~[n] s
r =
s[n  rN],
is called the periodic extension of s[n] with period N. This is also written as ~[n] s s[(n modulo N)] s[((n))N ].
Normally, N is not smaller than the duration of s[n].
Discrete Fourier Transform
Spectrum
It follows from x [n] = x[n] p [n] that the spectrum of x [n] is ~ ~ ~ ~ ~ X (e j ) = X (e j )P(e j ) = X (e )
j
2k 2  N k= N .
2k 2 X e j(2/N)k  = N k= N
Discrete Fourier Transform
DFS Coefficients are Samples of DTFT
Equating the spectrum of a periodic signal x [n] in two different ~ expressions, i.e. sum of complex exponentials and convolution with periodic impulse trains, 2k 2 ~ ~ X [k]  X (e j ) = N k= N
. . . DFS . . . convolution,
= we have
2k 2 X e j(2/N)k  N k= N ~ X [k] = X (e j )= 2k .
N
~ That is, X [k] are samples of X (e j ) at equally spaced frequencies.
Discrete Fourier Transform
Example
Consider the periodic rectangular sequence with period N = 10. In one period 1, 0 n 4, x [n] = ~ 0, 5 n 9. The spectrum of x[n] is
4
X (e ) =
n=0
j
e jn = e j2
sin 5 2 . sin 2
It is straightforward to verify that
4 ~ X [k] = e j 10 k
sin k 2 sin k 10
= X (e j )= 2k .
10
Discrete Fourier Transform
Sampling the Fourier Transform
Consider an aperiodic signal a[n] and do the following. Obtain the spectrum A(e j ) of a[n]. ~ Sample A[k] at frequencies k = 2k from A(e j ). N ~ [k], apply the synthesis equation of DFS and obtain a With X periodic sequence ~[n]. a In summary, we have a[n]  
DTFT
A(e j )
 
sampling
~ A[k]
 
DFS
a ^[n].
What is the relationship between a[n] and ^[n]? a
Discrete Fourier Transform
Theorem
Theorem a ^[n] is the periodic extension of a[n] with period N. 1 ^[n] = a N = =
m N1
1 kn ~ A[k]WN = N k=0 a[m]e j
k=0 m
2k m N
N1 kn A(e jk )WN k=0 kn WN
1 N
N1
a[m]
1 N
N1
WN
k=0
k(nm)
=
m
a[m]~ [n  m] = p
r
a[n  rN] = ~[n]. a
Discrete Fourier Transform
Aliasing
Consider the case that a[n] is of finite duration M. If N < M (undersamplng), the copies a[n  rN] would overlap in their span. This is called timedomain aliasing. If N = M, a[n] corresponds to one period of ~[n]. a If N > M, a[n] can still be extracted, along with N  M zeros in one period of ~[n]. a
Discrete Fourier Transform
FrequencyDomain Sampling Theorem
Theorem (frequencydomain sampling theorem) For a finiteduration sequence a[n] of length M, it suffices to represent A(e j ) by N samples in [0, 2) with N M. The following diagram shows how this is possible. A[k]  
DFS
a ~[n]
 
one period
a[n]
 
DTFT
A(e j ).
Using a higher number of samples also works, and it leads to finer spectral resolution.
Discrete Fourier Transform
Discrete Fourier Transform
Definition (discrete Fourier transform) The discrete Fourier transform (DFT) of a finiteduration sequence x[n] of length N is defined as
N1
X [k] =
n=0
kn x[n]WN ,
0 k N  1.
Discrete Fourier Transform
Discrete Fourier Transform
Definition (inverse discrete Fourier transform) The inverse discrete Fourier transform (IDFT) is defined as 1 x[n] = N
N1 kn X [k]WN , k=0
0 n N  1.
We henceforth denote a DFT pair by x[n] X [k].
DFT
Discrete Fourier Transform
Circular Shift
Definition (circular shift) The circular shift by m of an Npoint signal x[n] is defined as xm [n] = x[((n  m))N ], 0 n N  1, 0, otherwise
A circular shift can be visualized in two ways: construct periodic extension x [n], shift x [n] to the right by m, ~ ~ and truncate x [n] to the segment 0 n N  1; ~ place the points of x[n] clockwise on a circle, and rotate the points clockwise.
Discrete Fourier Transform
Properties of DFT
linearity ax[n] + by [n] circular shift xm [n] duality x[n] X [k] symmetry x [n] X [((k))N ],
DFT DFT DFT
DFT
aX [k] + bY [k] e j N km X [k]
2
X [n] Nx[((k))N ]
DFT
x [((n))N ] X [k]
DFT
Discrete Fourier Transform
Proof: Circular Shift
xm [n]
DFT
e j N km X [k]
2
This can be argued as follows: x[n] X [k]
DFS ~ x [n] X [k] ~ DFT
~ x [n  m] e j N km X [k] ~ xm [n] e j N km X [k]
DFT
2
DFS
2
Discrete Fourier Transform
Circular Convolution
Definition (Npoint circular convolution) The Npoint circular convolution of two finiteduration sequences x[n] and y [n] is defined as follows:
N1
x[n]
N
y [n] =
m=0 N1
x[((m))N ]y [((n  m))N ] x[m]y [((n  m))N ],
m=0
=
0 n N  1.
Let z[n] x[n] N y [n]. z[n] is of finite duration by definition. z[n] is one period of the periodic convolution z [n] ~
x [n] ~
y [n]. ~
Discrete Fourier Transform
Circular Convolution Theorem
Theorem Let x[n] and y [n] be of finite duration N. Then x[n]
N
y [n]
     
Npoint DFT
X [k]Y [k].
~ ~ Let x [n], y [n] be the periodic extensions and X [k], Y [k] be the DFS ~ ~ coefficients. By the periodic convolution theorem, x [n] ~ y [n] ~
DFS
~ ~ X [k]Y [k].
Taking one period, we get x[n]
N
y [n]
DFT
X [k]Y [k].
Discrete Fourier Transform
Convolution of FiniteDuration Sequences
Theorem (finiteduration convolution) Let x[n] and y [n] be causal and finiteduration sequences with durations L and M respectively, and
L1
z[n]
x[n] y [n] =
m=0
x[m]y [n  m].
Then z[n] is sure to be causal and finiteduration of length no more than L + M  1.
Discrete Fourier Transform
Proof
We show that z[n] = 0 for n < 0 and n > L + M  2. If n < 0, we have n  m < n < 0, 0 m L  1.
Therefore, the convolution sum is 0 as y [n  m] = 0. If n > L + M  2, we have n  m > L + M  2  (L  1) = M  1, 0 m L  1.
Therefore, the convolution sum is 0 as y [n  m] = 0. Since z[n] can be nonzero only for 0 n L + M  2, we conclude that the duration of z[n] is at most L + M  1.
Discrete Fourier Transform
Linear Convolution
Theorem Let x[n] and y [n] be causal and finiteduration sequences with durations L and M respectively. For any N L + M  1, we have x[n] y [n] = x[n]
L1 N
y [n],
0 n N  1.
N1
x[n] y [n] =
m=0 N1
x[m]y [n  m] =
m=0
x[m]y [n  m]
=
m=0
x[m]y [((n  m))N ]
N
= x[n]
y [n].
Discrete Fourier Transform
Implementation of Convolution via DFT
By circular convolution theorem, the DFT of z[n] = x[n] Z [k] = X [k]Y [k]. Therefore, the convolution z[n] of two causal and finiteduration sequences x[n] and y [n] can be obtained as follows. pad x[n] and y [n] with zeros to length N L + M  1; compute DFT of X [k] and Y [k]; compute IDFT of Z [k] = X [k]Y [k]; extract from z[n] a finiteduration sequence of length L + M  1. y [n] is
N
Discrete Fourier Transform
Information
43 pages
Report File (DMCA)
Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:
Report this file as copyright or inappropriate
850363