3.3 离散傅立叶变换
3.3 离散傅里叶变换
(DFT-Discrete Fourier Transform)
时间连续的周期信号 频率离散的傅立叶级数时间连续的非周期信号 频率连续的傅立叶变换时间离散的周期序列 频率离散的周期级数时间离散的非周期序列 频率连续的周期变换?
非周期序列称为是有限长度序列,分析有限长度序列和周期序列之间的关系,推导离散傅立叶变换,
离散周期序列的傅里叶级数展开式
NjN eW?2
Nk
njk
kN Necnx
2
)(
Nn
njk
Nk NenxNc
2
)(1
nkNjkn
N eW
2 nkNjkn
N eW
2
Nn
kn
NNk WnxNc )(
1
Nk
kn
NkN Wcnx )(
离散傅里叶变换定义式
1
0
)(1 N
n
kn
NNk WnxNc
Nk
knNkN Wcnx )(
由于周期序列只有有限个序列值有意义,所以离散傅里叶级数也使用于有限长序列,
如果把长度为 N的有限长序列看成是周期为 N周期序列的一个周期,则可以利用离散傅立叶级数计算有限长序列把有限长序列周期延拓,也可以看成是 X(k)主值序列的周期研拓,由于 DFS求和运算只限定在 n=0-N-1和 k=0-N-1,
所以完全适用于有限长序列的傅立叶变换对
kc
一 DFT的定义
1
0
2
)()(
N
n
nNjk
enxkX
)12,1,0( Nk?
1
0
2
)(1)(
N
k
nNjk
ekXNnx
)12,1,0( Nn?
1
0
)()(
N
n
nk
NWnxkX
1
0
)(1)(
N
k
nk
NWkXNnx
)]([D F T)( nxkX?
)]([I D F T)( kXnx?
)12,1,0( Nk?
)12,1,0( Nn?
1
0
)()(
N
n
nk
NWnxkX
1
0
)(1)(
N
k
nk
NWkXNnx
)1(
)1(
)0(
)1(
)1(
)0(
)1()1(1)1(0
)1(110
000
Nx
x
x
WWW
WWW
WWW
NX
X
X
NNN
N
)1(
)1(
)0(
)1(
)1(
)0(
)1()1(1)1(0
)1(110
000
NX
X
X
WWW
WWW
WWW
Nx
x
x
NNN
N
)1(
)1(
)0(
)1(
)1(
)0(
)1()1(1)1(0
)1(110
000
Nx
x
x
WWW
WWW
WWW
NX
X
X
NNN
N
从矩阵可看出，计算一个 N点 DFT，无论是正变换环视反变换，都需要 N2x(n)次复数乘法和 N(N-1)次加法运算，如果一个中等长度序列 N=210=1024,就需要 100多万次复数乘法,N更长时,所需计算时间更长,
x(n)和 X(k)是有限长序列的离散傅立叶变换对,都是长度为 N的值,都有 N个独立值,已知其中一个序列,就能唯一确定另一序列
1
0
)()(
N
n
nk
NWnxkX
1
0
)(1)(
N
k
nk
NWkXNnx
DFT和 DTFT 都是处理有限长序列的重要工具,他们之间有什么关系?
二 DTFT,DFS及 DFT之间的关系
Nk
j
k eXNc?2)(
1
Nn
n
N
jk
N
Nn
n
N
jk
Nk
N
k
j enxenx
N
NNceX
22
2 )()(
1)(
)12,1,0()()( 2 NkNceXkX k
Nk
j
X(k)是连续 DTFT的等间隔采样,
图 DFT和 DFS (a)有限长序列 (b) 频谱
(c) 周期延拓 (d) 的 DFS系数
)(nx )(nx
)(nx )(nx
N )(nxN
的物理含义,)(kX
(1) 是周期函数，区间 [0,]上的 已经包含了全部信息,所以 只取该区间上的 N个点上的值。
(2) 序列 是 的周期延拓。
(3) DFT事实上是用周期序列 傅里叶级数展开式系数在区间 [0,N-1]上乘以 N倍后来表征有限长序列 的频谱。
)(?jeX?2 )(?jeX
)(kX
)(kXkNc
)(nxN kc
)(nx
DFT逆变换定义
Nk
n
N
jk
kN ecnx
2
)(
1
0
2
)(1)(
N
k
n
N
jk
N ekXNnx
)1,2,1,0()(1)()(
1
0
2
NnekX
N
nxnx
N
k
n
N
jk
N?
例 1计算有限长序列 x(n)=GN(n),N=4,8,16的 DFT
解 (1) N=4
3,2,1,0,
4
s i n
s i n
1
1
)(
4
3
2
23
0
2
3
0
4
k
k
k
e
e
e
eWkX
kj
kj
k
n
nkj
n
nk
(2) N=8
7,6,5,4,3,2,1,0,
8
s in
2
s in
)( 8
23
0
4
7
0
8
kk
k
eeWkX
kj
n
nkj
n
nk
(2) N=16
15,,3,2,1,0,
16
s in
4
s in
)( 16
33
0
8
15
0
16
kk
k
eeWkX
kj
n
nkj
n
nk
三 连续信号的离散傅立叶变换处理图 (a) 时的周期延拓：无混叠
(b) 时的周期延拓：产生混叠
NNS?
NNS?
Discrete Fourier Transform assumes N samples
in time and frequency.
By sampling in time,we get a periodic spectrum
with the sampling frequency fs,The
approximation of a Fourier transform by a DFT is
reasonable only if the frequency components of
x(t) are concentrated on a smaller range than
the Nyquist frequency fs/2.
1 时域采样
2 频域采样
k
s
jjj
s kXXX eee S ))()()()( (
k
s
j
j
s
kFeXF
FeXFnx
S
)(*)(
)(*)()(
11
11
对 的频谱 进行理想采样后频谱 为：)(nx )(?jeX )(?js eX
所对应的时域序列 为：)(?js eX )(nxs
l ssk
s lnkF )
2(1)(1
l ssl ss
l ss
s
lnxlnnx
lnnxnx
)
2
(
1
)
2
(*)(
1
)
2
(
1
*)()(
N
s
2
)2(2)(
k ssl
s NkNlNnF
)()2(1 s
kl ss
klnF
所以结论：
(1)DFT以 为间隔离散化,所以事实上 DFT是以刚好不产生时域混叠的采样间隔对 进行的采样。
(2)如果对 进行更密的采样，即,则等效于在时域中取 [ ]范围内的 进行周期延拓，
其中,当,如图 所示。
(3) 如果,即对 进行欠采样，则将造成时域的混叠,如图 所示。
N/2? )(?jeX
)(?jeX
)(?jeX
NsNs
22
1,0?sN
)1(,1, sNNNn?0)(?nx
NsN? )(?jeX
)(nx
By sampling in the frequency domain,
the time function becomes periodic,i.e.,
the DFT assumes the time series to be
periodic,If an N-sample DFT is applied
to a signal that does not complete an
integer number of cycles with an N-
sample window,a phenomenon called
leakage occurs,
四、周期卷积和圆周卷积
1,周期卷积
)(*)()( nhnxny NNN?
1
0
)()(
N
m
NN mnhmx
1
0
)()(
N
m
NN mnxmh
)2()()( 000 NnyNnyny NNN
)(nyN 是周期函数。
周期卷积的说明
2,圆周卷积
=)(ny )()](*)([ nRnhnx NNN
即圆周卷积是周期卷积在,主值区间,上的值。
3,圆周移位周期序列的移位和取主值
4,周期卷积和线性卷积周期卷积 是线性卷积 以 为周期的周期延拓,即：
)(nyN )(1 ny N
r
N rNnyny )()( 1
能否用循环卷积实现线性卷积?
条件是循环卷积的长度必须大于等于两序列的长度和,
即,L>=N+M-1.具体步骤为两序列补零为 L点,然后循环卷积,
五,DFT性质
mNjk
NN ekXnRmnxD F T
2
)()]()([
性质一 线性 )()()]()([ 2121 kbXkaXnbxnaxD F T
若 x1(n)和 x2(n)长度均为 N,则所得序列的长度也为 N;
若 x1(n)和 x2(n)长度为 N1,N2，则所得序列的长度为两者中得最大值性质二 时移特性有限长序列的循环移位始终局限于 0-N-1主值区间,序列的长度也为 N;
km
NNN
km
NNN
WkXnRmnxD F T
WkXnRmnxD F T
)()]()([
)()]()([
性质三 频移特性
)()(])([
2
kRlkXenxD FT NNmNjl
性质四 时域圆周卷积 (周期卷积 )
)()(
)()](*)([
)()](*)([
kHkX
nRnxnhD F T
nRnhnxD F T
NNN
NNN
)()(
)())](*)([1
nhnx
kRkHkX
N
I D F T N
同样可证解,序列的 DFT为例：两个有限长序列相等，求他们的循环卷积
o t h e r
Nnnxnx
,0
10,1)()(
21
o t h e r
kNWkXkX N nk
N,0
0,)()( 1
0
21
o th e r
kNkXkXkY
,0
0,)()()( 2
21
10,)( NnNny
性质五 频域周期卷积 (圆周卷积 )
)()(*)(1
)()(*)(
1
)]()([
kRkXkH
N
kRkHkX
N
nhnxD F T
NNN
NNN
性质六 实数序列奇偶性
)()(
)()(
)()()(
kXkX
kXkX
kjXkXkX
ii
rr
ir
性质七 共轭对称性
)()(*)](*[D F T kRkNXnx NN
若为实数序列,
)()(*)( kRkNXkX NN
性质八 泊斯瓦耳公式
1
0
2
21
0
)(1)(
N
k
N
n
kXNnx
How to get the frequency axis in the DFT
The DFT operation just converts one set of
number,x[k] into another set of numbers X[n] -
there is no explicit definition of time or frequency
How can we relate the DFT to the CFT and obtain
spectral amplitudes for discrete frequencies?
Where are the,low” and,high” frequencies on
the DFT spectrum?
1N
0
x
.
x
]k[x
1N
0
X
.
X
]n[X
(N-point FFT)
n=0 1 2 3 4 n=N
f=0 f = fs
N
fs
3.4 快速傅立叶变换
3.4 快速傅里叶变换
(FFT-Fast Fourier Transform)
一 直接按照定义式计算 DFT的计算量
1
0
)()(
N
n
nkWnxkX
复数乘,次； 复数加 次2N )1(?NN
二 FFT的基本思想
FFT的实质是利用 的对称性和周期性，把 N点 DFT
进行一系列分解和组合，使 DFT变成一系列叠代运算
knNW
)( m o d Nlnk
WWW
lrNnk
lr
N
nk
l
N
lrN
N
nk
N
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 2 5
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
6 0 6 4 2 0 6 4 2
7 0 7 6 5 4 3 2 1
三 的性质nkNW
性质二 12NNW
性质一 lNnkNnkN WW )(22 lNnkNjnkNj ee
12
2
j
N
Nj ee
性质三 nkNNnkN WW 2 nkNjNnkNj ee 2)2(2
性质四 nkNnkN WW 2/2? nkNjnkNj ee 2/222
四 N点 DFT计算分解为两个 N/2点的 DFT计算
)12,1,0( Nk?
设 N为偶数，将 N点的 分为两组 N/2点的等长的序列：)(nx
)2()(1 rxnx? )12()(2 rxnx 12,1,0 Nrn?
1
0
)()(
N
n
nk
NWnxkX )()( 21 kXWkX kN
12
0
2/1
12
0
2/1 )()2()(
N
n
nk
N
N
r
rk
N WnxWrxkX
1
2
0
2/2
1
2
0
2/2 )()12()(
N
n
nk
N
N
r
rk
N WnxWrxkX
其中
)()2( 11 kXNkX
)()2( 22 kXNkX
)()()
2
()
2
()
2
(
)()()(
212
2
1
21
kXWkX
N
kXW
N
kX
N
kX
kXWkXkX
k
N
N
k
N
k
N
由 N/2点计算 N点问题,
)12,1,0( Nk?
The Cooley-Tukey FFT is the most universal of
all FFT algorithms,because any factorization of
N is possible.
时间抽取基 2 FFT算法
频率抽取基 2 FFT算法五 基本算法
Algorithm,Cooley-Tukey Algorithm
An N = N1 N2 -point DFT can be done using
the following steps:
1) Compute an index transform of the input
sequence according to,n = N2n1 + n2
2) Compute the N2 DFTs of length N1.
3) Apply the twiddle factors WN n2k1 to the output
of the first transform stage.
4) Compute the N1 DFTs of length N2.
5) Compute an index transform of the output
sequence according to,k = k1 + N1k2
See Example 6.9,Cooley-Tukey FFT for N =
12.
Radix-r Cooley-Tukey Algorithm
Radix-r algorithms,N = rs,S is the
number of stages,
The most popular algorithms are of
basis r = 2 or r =4,because the
necessary basic DFTs can be
implemented without any multiplications.
2-point DFT,Butterfly
X(0) = x(0)e0 + x(1)e0
= x(0) + x(1)
X(1) = x(0)e0 + x(1)e–j2?/2
= x(0)? x(1)
1
x(0)
x(1)
X(0)
X(1)
4-point FFT
n = 2n1 + n2
k = k1 + 2k2
1
1?1
1
W0
W2
x(0)
x(2)
x(1)
x(3)
X(0)
X(2)
X(1)
X(3)
1
1?1
1
W0
W2
x(0)
x(1)
x(2)
x(3)
X(0)
X(2)
X(1)
X(3)
Group
Rearrange the positions of x(1) and x(2)
Decimation-in-frequency (DIF)
FFT algorithm
The Decimation-in-frequency algorithm starts
in the frequency domain to split the original
DFT into shorter DFTs.
The input values typically occur in natural
order,while the index of the frequency values
is in bit-reversed order.
The decimation-in-time (DIT) FFT algorithm can be
found in the book,Fundamentals of Signals and
Systems using the WEB and MATLAB”,pages 339-
342.
Number of complex multiplications
and add/subtract operations
For r = 2 and S stages (S = log2 N),the
number of complex twiddle factor
multiplications is
(S – 1)?N/2 = ((log2 N) – 1)? N/2.
The number of complex add/subtract
operations is
S?N = (log2 N)? N.
Compare with the direct DFT computation:
Complex multiplications,N?N
Complex add/subtract operations,N?(N – 1)
Radix-2 Cooley-Tukey Algorithm
Implementation
Butterfly processor
Complex multiplication
Complex multiplication with the twiddle factor
is often implemented with 4 real
multiplications and two add/subtract
operations.
A more efficient complex multiplier is
implemented with 3 real multiplications and 3
add/subtract operations,
See Algorithm 6.10.
五,FFT的应用举例应用一 利用 FFT计算线性卷积
(1)分别将 和 补零,使其长度均为 L,且满足 ；
(2)分别对 和 计算 L点的 FFT得到,；
(3)计算乘积 ；
(4)计算 FFT逆变换 ；
)(nx )(nh
121 NNL
)(nx )(nh
)()()( kHkXkY?
)(kX )(kH
)(I F F T)( kYny?
应用一 利用 FFT计算线性卷积通过循环卷积即 FFF可以大大减少卷积所需要的工作量,因此 快速卷积可以实现信号的实时处理,但要处理的信号很长时,可以采用分段卷积方法,
应用二 利用 FFT计算快速相关
)(kH
F F T
F F T
共 扼序 列相 乘
F F T
)( nx )( nh )( ny)( kX
)(* kH
利用 FFT计算序列的相关函数步骤：
(1)分别将 和 补零，使其长度均为 L，且满足 ；
(2)分别对 和 计算 L点的 FFT得到,；
(3) 计算 的共轭 ；
(4) 计算乘积 ；
(5) 计算 FFT逆变换
)(1 nx )(2 nx
121 NNL
)(1 nx )(2 nx )(1 kX )(2 kX
)(2 kX )(*2 kX
)()( *21 kXkX
)()(I F F T *21 kXkX
Image Enhancement
Detection of Discontinuities
Image Spectrum
2-D Fourier Transform (DFT & FFT)
Spectral Filtering
Lab 2,Spatial and Spectral Filtering
Low-pass
High-pass
应用三 图象处理
Image Preprocessing
Enhancement Restoration
Spatial
Domain
Spectral
Domain
Point Processing
>>imadjust
>>histeq
Spatial filtering
>>filter2
Filtering
>>fft2/ifft2
>>fftshift
Inverse filtering
Wiener filtering
应用四 离散时间信号滤波图 FFT用于谱估计 (a)无噪声信号 (b)无噪声信号功率谱
(c)噪声污染后信号 (d)噪声污染后信号功率谱
0 20 40 60 80 100
-2
-1
0
1
2
0 100 200 300 400 500
0
50
100
0 10 20 30 40 50
-5
0
5
0 100 200 300 400 500
0
50
100
(a) (b)
(c) (d)
应用五 功率谱估计已知两序列为求两序列的线性卷积和 16点循环卷积，用 MATLAB实现练习：
o th e r
nnx n
0
1609.0)(
o th e r
nnh
0
801)(
3.3 离散傅里叶变换
(DFT-Discrete Fourier Transform)
时间连续的周期信号 频率离散的傅立叶级数时间连续的非周期信号 频率连续的傅立叶变换时间离散的周期序列 频率离散的周期级数时间离散的非周期序列 频率连续的周期变换?
非周期序列称为是有限长度序列,分析有限长度序列和周期序列之间的关系,推导离散傅立叶变换,
离散周期序列的傅里叶级数展开式
NjN eW?2
Nk
njk
kN Necnx
2
)(
Nn
njk
Nk NenxNc
2
)(1
nkNjkn
N eW
2 nkNjkn
N eW
2
Nn
kn
NNk WnxNc )(
1
Nk
kn
NkN Wcnx )(
离散傅里叶变换定义式
1
0
)(1 N
n
kn
NNk WnxNc
Nk
knNkN Wcnx )(
由于周期序列只有有限个序列值有意义,所以离散傅里叶级数也使用于有限长序列,
如果把长度为 N的有限长序列看成是周期为 N周期序列的一个周期,则可以利用离散傅立叶级数计算有限长序列把有限长序列周期延拓,也可以看成是 X(k)主值序列的周期研拓,由于 DFS求和运算只限定在 n=0-N-1和 k=0-N-1,
所以完全适用于有限长序列的傅立叶变换对
kc
一 DFT的定义
1
0
2
)()(
N
n
nNjk
enxkX
)12,1,0( Nk?
1
0
2
)(1)(
N
k
nNjk
ekXNnx
)12,1,0( Nn?
1
0
)()(
N
n
nk
NWnxkX
1
0
)(1)(
N
k
nk
NWkXNnx
)]([D F T)( nxkX?
)]([I D F T)( kXnx?
)12,1,0( Nk?
)12,1,0( Nn?
1
0
)()(
N
n
nk
NWnxkX
1
0
)(1)(
N
k
nk
NWkXNnx
)1(
)1(
)0(
)1(
)1(
)0(
)1()1(1)1(0
)1(110
000
Nx
x
x
WWW
WWW
WWW
NX
X
X
NNN
N
)1(
)1(
)0(
)1(
)1(
)0(
)1()1(1)1(0
)1(110
000
NX
X
X
WWW
WWW
WWW
Nx
x
x
NNN
N
)1(
)1(
)0(
)1(
)1(
)0(
)1()1(1)1(0
)1(110
000
Nx
x
x
WWW
WWW
WWW
NX
X
X
NNN
N
从矩阵可看出，计算一个 N点 DFT，无论是正变换环视反变换，都需要 N2x(n)次复数乘法和 N(N-1)次加法运算，如果一个中等长度序列 N=210=1024,就需要 100多万次复数乘法,N更长时,所需计算时间更长,
x(n)和 X(k)是有限长序列的离散傅立叶变换对,都是长度为 N的值,都有 N个独立值,已知其中一个序列,就能唯一确定另一序列
1
0
)()(
N
n
nk
NWnxkX
1
0
)(1)(
N
k
nk
NWkXNnx
DFT和 DTFT 都是处理有限长序列的重要工具,他们之间有什么关系?
二 DTFT,DFS及 DFT之间的关系
Nk
j
k eXNc?2)(
1
Nn
n
N
jk
N
Nn
n
N
jk
Nk
N
k
j enxenx
N
NNceX
22
2 )()(
1)(
)12,1,0()()( 2 NkNceXkX k
Nk
j
X(k)是连续 DTFT的等间隔采样,
图 DFT和 DFS (a)有限长序列 (b) 频谱
(c) 周期延拓 (d) 的 DFS系数
)(nx )(nx
)(nx )(nx
N )(nxN
的物理含义,)(kX
(1) 是周期函数，区间 [0,]上的 已经包含了全部信息,所以 只取该区间上的 N个点上的值。
(2) 序列 是 的周期延拓。
(3) DFT事实上是用周期序列 傅里叶级数展开式系数在区间 [0,N-1]上乘以 N倍后来表征有限长序列 的频谱。
)(?jeX?2 )(?jeX
)(kX
)(kXkNc
)(nxN kc
)(nx
DFT逆变换定义
Nk
n
N
jk
kN ecnx
2
)(
1
0
2
)(1)(
N
k
n
N
jk
N ekXNnx
)1,2,1,0()(1)()(
1
0
2
NnekX
N
nxnx
N
k
n
N
jk
N?
例 1计算有限长序列 x(n)=GN(n),N=4,8,16的 DFT
解 (1) N=4
3,2,1,0,
4
s i n
s i n
1
1
)(
4
3
2
23
0
2
3
0
4
k
k
k
e
e
e
eWkX
kj
kj
k
n
nkj
n
nk
(2) N=8
7,6,5,4,3,2,1,0,
8
s in
2
s in
)( 8
23
0
4
7
0
8
kk
k
eeWkX
kj
n
nkj
n
nk
(2) N=16
15,,3,2,1,0,
16
s in
4
s in
)( 16
33
0
8
15
0
16
kk
k
eeWkX
kj
n
nkj
n
nk
三 连续信号的离散傅立叶变换处理图 (a) 时的周期延拓：无混叠
(b) 时的周期延拓：产生混叠
NNS?
NNS?
Discrete Fourier Transform assumes N samples
in time and frequency.
By sampling in time,we get a periodic spectrum
with the sampling frequency fs,The
approximation of a Fourier transform by a DFT is
reasonable only if the frequency components of
x(t) are concentrated on a smaller range than
the Nyquist frequency fs/2.
1 时域采样
2 频域采样
k
s
jjj
s kXXX eee S ))()()()( (
k
s
j
j
s
kFeXF
FeXFnx
S
)(*)(
)(*)()(
11
11
对 的频谱 进行理想采样后频谱 为：)(nx )(?jeX )(?js eX
所对应的时域序列 为：)(?js eX )(nxs
l ssk
s lnkF )
2(1)(1
l ssl ss
l ss
s
lnxlnnx
lnnxnx
)
2
(
1
)
2
(*)(
1
)
2
(
1
*)()(
N
s
2
)2(2)(
k ssl
s NkNlNnF
)()2(1 s
kl ss
klnF
所以结论：
(1)DFT以 为间隔离散化,所以事实上 DFT是以刚好不产生时域混叠的采样间隔对 进行的采样。
(2)如果对 进行更密的采样，即,则等效于在时域中取 [ ]范围内的 进行周期延拓，
其中,当,如图 所示。
(3) 如果,即对 进行欠采样，则将造成时域的混叠,如图 所示。
N/2? )(?jeX
)(?jeX
)(?jeX
NsNs
22
1,0?sN
)1(,1, sNNNn?0)(?nx
NsN? )(?jeX
)(nx
By sampling in the frequency domain,
the time function becomes periodic,i.e.,
the DFT assumes the time series to be
periodic,If an N-sample DFT is applied
to a signal that does not complete an
integer number of cycles with an N-
sample window,a phenomenon called
leakage occurs,
四、周期卷积和圆周卷积
1,周期卷积
)(*)()( nhnxny NNN?
1
0
)()(
N
m
NN mnhmx
1
0
)()(
N
m
NN mnxmh
)2()()( 000 NnyNnyny NNN
)(nyN 是周期函数。
周期卷积的说明
2,圆周卷积
=)(ny )()](*)([ nRnhnx NNN
即圆周卷积是周期卷积在,主值区间,上的值。
3,圆周移位周期序列的移位和取主值
4,周期卷积和线性卷积周期卷积 是线性卷积 以 为周期的周期延拓,即：
)(nyN )(1 ny N
r
N rNnyny )()( 1
能否用循环卷积实现线性卷积?
条件是循环卷积的长度必须大于等于两序列的长度和,
即,L>=N+M-1.具体步骤为两序列补零为 L点,然后循环卷积,
五,DFT性质
mNjk
NN ekXnRmnxD F T
2
)()]()([
性质一 线性 )()()]()([ 2121 kbXkaXnbxnaxD F T
若 x1(n)和 x2(n)长度均为 N,则所得序列的长度也为 N;
若 x1(n)和 x2(n)长度为 N1,N2，则所得序列的长度为两者中得最大值性质二 时移特性有限长序列的循环移位始终局限于 0-N-1主值区间,序列的长度也为 N;
km
NNN
km
NNN
WkXnRmnxD F T
WkXnRmnxD F T
)()]()([
)()]()([
性质三 频移特性
)()(])([
2
kRlkXenxD FT NNmNjl
性质四 时域圆周卷积 (周期卷积 )
)()(
)()](*)([
)()](*)([
kHkX
nRnxnhD F T
nRnhnxD F T
NNN
NNN
)()(
)())](*)([1
nhnx
kRkHkX
N
I D F T N
同样可证解,序列的 DFT为例：两个有限长序列相等，求他们的循环卷积
o t h e r
Nnnxnx
,0
10,1)()(
21
o t h e r
kNWkXkX N nk
N,0
0,)()( 1
0
21
o th e r
kNkXkXkY
,0
0,)()()( 2
21
10,)( NnNny
性质五 频域周期卷积 (圆周卷积 )
)()(*)(1
)()(*)(
1
)]()([
kRkXkH
N
kRkHkX
N
nhnxD F T
NNN
NNN
性质六 实数序列奇偶性
)()(
)()(
)()()(
kXkX
kXkX
kjXkXkX
ii
rr
ir
性质七 共轭对称性
)()(*)](*[D F T kRkNXnx NN
若为实数序列,
)()(*)( kRkNXkX NN
性质八 泊斯瓦耳公式
1
0
2
21
0
)(1)(
N
k
N
n
kXNnx
How to get the frequency axis in the DFT
The DFT operation just converts one set of
number,x[k] into another set of numbers X[n] -
there is no explicit definition of time or frequency
How can we relate the DFT to the CFT and obtain
spectral amplitudes for discrete frequencies?
Where are the,low” and,high” frequencies on
the DFT spectrum?
1N
0
x
.
x
]k[x
1N
0
X
.
X
]n[X
(N-point FFT)
n=0 1 2 3 4 n=N
f=0 f = fs
N
fs
3.4 快速傅立叶变换
3.4 快速傅里叶变换
(FFT-Fast Fourier Transform)
一 直接按照定义式计算 DFT的计算量
1
0
)()(
N
n
nkWnxkX
复数乘,次； 复数加 次2N )1(?NN
二 FFT的基本思想
FFT的实质是利用 的对称性和周期性，把 N点 DFT
进行一系列分解和组合，使 DFT变成一系列叠代运算
knNW
)( m o d Nlnk
WWW
lrNnk
lr
N
nk
l
N
lrN
N
nk
N
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 2 5
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
6 0 6 4 2 0 6 4 2
7 0 7 6 5 4 3 2 1
三 的性质nkNW
性质二 12NNW
性质一 lNnkNnkN WW )(22 lNnkNjnkNj ee
12
2
j
N
Nj ee
性质三 nkNNnkN WW 2 nkNjNnkNj ee 2)2(2
性质四 nkNnkN WW 2/2? nkNjnkNj ee 2/222
四 N点 DFT计算分解为两个 N/2点的 DFT计算
)12,1,0( Nk?
设 N为偶数，将 N点的 分为两组 N/2点的等长的序列：)(nx
)2()(1 rxnx? )12()(2 rxnx 12,1,0 Nrn?
1
0
)()(
N
n
nk
NWnxkX )()( 21 kXWkX kN
12
0
2/1
12
0
2/1 )()2()(
N
n
nk
N
N
r
rk
N WnxWrxkX
1
2
0
2/2
1
2
0
2/2 )()12()(
N
n
nk
N
N
r
rk
N WnxWrxkX
其中
)()2( 11 kXNkX
)()2( 22 kXNkX
)()()
2
()
2
()
2
(
)()()(
212
2
1
21
kXWkX
N
kXW
N
kX
N
kX
kXWkXkX
k
N
N
k
N
k
N
由 N/2点计算 N点问题,
)12,1,0( Nk?
The Cooley-Tukey FFT is the most universal of
all FFT algorithms,because any factorization of
N is possible.
时间抽取基 2 FFT算法
频率抽取基 2 FFT算法五 基本算法
Algorithm,Cooley-Tukey Algorithm
An N = N1 N2 -point DFT can be done using
the following steps:
1) Compute an index transform of the input
sequence according to,n = N2n1 + n2
2) Compute the N2 DFTs of length N1.
3) Apply the twiddle factors WN n2k1 to the output
of the first transform stage.
4) Compute the N1 DFTs of length N2.
5) Compute an index transform of the output
sequence according to,k = k1 + N1k2
See Example 6.9,Cooley-Tukey FFT for N =
12.
Radix-r Cooley-Tukey Algorithm
Radix-r algorithms,N = rs,S is the
number of stages,
The most popular algorithms are of
basis r = 2 or r =4,because the
necessary basic DFTs can be
implemented without any multiplications.
2-point DFT,Butterfly
X(0) = x(0)e0 + x(1)e0
= x(0) + x(1)
X(1) = x(0)e0 + x(1)e–j2?/2
= x(0)? x(1)
1
x(0)
x(1)
X(0)
X(1)
4-point FFT
n = 2n1 + n2
k = k1 + 2k2
1
1?1
1
W0
W2
x(0)
x(2)
x(1)
x(3)
X(0)
X(2)
X(1)
X(3)
1
1?1
1
W0
W2
x(0)
x(1)
x(2)
x(3)
X(0)
X(2)
X(1)
X(3)
Group
Rearrange the positions of x(1) and x(2)
Decimation-in-frequency (DIF)
FFT algorithm
The Decimation-in-frequency algorithm starts
in the frequency domain to split the original
DFT into shorter DFTs.
The input values typically occur in natural
order,while the index of the frequency values
is in bit-reversed order.
The decimation-in-time (DIT) FFT algorithm can be
found in the book,Fundamentals of Signals and
Systems using the WEB and MATLAB”,pages 339-
342.
Number of complex multiplications
and add/subtract operations
For r = 2 and S stages (S = log2 N),the
number of complex twiddle factor
multiplications is
(S – 1)?N/2 = ((log2 N) – 1)? N/2.
The number of complex add/subtract
operations is
S?N = (log2 N)? N.
Compare with the direct DFT computation:
Complex multiplications,N?N
Complex add/subtract operations,N?(N – 1)
Radix-2 Cooley-Tukey Algorithm
Implementation
Butterfly processor
Complex multiplication
Complex multiplication with the twiddle factor
is often implemented with 4 real
multiplications and two add/subtract
operations.
A more efficient complex multiplier is
implemented with 3 real multiplications and 3
add/subtract operations,
See Algorithm 6.10.
五,FFT的应用举例应用一 利用 FFT计算线性卷积
(1)分别将 和 补零,使其长度均为 L,且满足 ；
(2)分别对 和 计算 L点的 FFT得到,；
(3)计算乘积 ；
(4)计算 FFT逆变换 ；
)(nx )(nh
121 NNL
)(nx )(nh
)()()( kHkXkY?
)(kX )(kH
)(I F F T)( kYny?
应用一 利用 FFT计算线性卷积通过循环卷积即 FFF可以大大减少卷积所需要的工作量,因此 快速卷积可以实现信号的实时处理,但要处理的信号很长时,可以采用分段卷积方法,
应用二 利用 FFT计算快速相关
)(kH
F F T
F F T
共 扼序 列相 乘
F F T
)( nx )( nh )( ny)( kX
)(* kH
利用 FFT计算序列的相关函数步骤：
(1)分别将 和 补零，使其长度均为 L，且满足 ；
(2)分别对 和 计算 L点的 FFT得到,；
(3) 计算 的共轭 ；
(4) 计算乘积 ；
(5) 计算 FFT逆变换
)(1 nx )(2 nx
121 NNL
)(1 nx )(2 nx )(1 kX )(2 kX
)(2 kX )(*2 kX
)()( *21 kXkX
)()(I F F T *21 kXkX
Image Enhancement
Detection of Discontinuities
Image Spectrum
2-D Fourier Transform (DFT & FFT)
Spectral Filtering
Lab 2,Spatial and Spectral Filtering
Low-pass
High-pass
应用三 图象处理
Image Preprocessing
Enhancement Restoration
Spatial
Domain
Spectral
Domain
Point Processing
>>imadjust
>>histeq
Spatial filtering
>>filter2
Filtering
>>fft2/ifft2
>>fftshift
Inverse filtering
Wiener filtering
应用四 离散时间信号滤波图 FFT用于谱估计 (a)无噪声信号 (b)无噪声信号功率谱
(c)噪声污染后信号 (d)噪声污染后信号功率谱
0 20 40 60 80 100
-2
-1
0
1
2
0 100 200 300 400 500
0
50
100
0 10 20 30 40 50
-5
0
5
0 100 200 300 400 500
0
50
100
(a) (b)
(c) (d)
应用五 功率谱估计已知两序列为求两序列的线性卷积和 16点循环卷积，用 MATLAB实现练习：
o th e r
nnx n
0
1609.0)(
o th e r
nnh
0
801)(
