第四章 DFT与其快速算法(数字信号处理)

正弦波就是一个圆周运动在一条直线上 的投影。所以频域的基本单元也可以理 解为一个始终在旋转的圆：
4.2基2FFT算法
4.2.1 直接计算DFT的特点及减少运算量的基本途径 1.直接计算DFT 长度为N的有限长序列x(n)的DFT为：
kn X (k ) x (n )WN , k 0,1, , N 1 n 0 N 1
｛
4.2 基2FFT算法
(2)用N/2点X1(k)和X2(k)表示序列x(n)的N点DFT X(k)
kn kn X ( k ) x ( n )WN x ( n ) W N kn kn X ( k ) x ( n ) W x ( n ) W kn kn 奇数 n 偶数 n kn kn N N X (k ) X ( x ( n ) W x ( n ) W k ) x ( n ) W x ( n ) W N N N n nN
W e
2 j 2 kr 2 kr N 2 (k )
注意：这里的k的取值范围为0，1，…，N-1
4.2 基2FFT算法
由于X1(k)和X2(k)均以N/2为周期，且 WN
k k N 2 N 2 k N 2 k k 1 N 2 1 N 2 k 1 N 2
x ( r ) W x ( r )W x ( r ) W x ( r ) W W x ( r ) W x ( r ) (2 1)W e W x (r) W xW x (rre ) W x (2 )W
x ( r ) W x ( r )W X (k ) x ( r )W W x ( r )W
第3章 离散傅里叶变换(DFT) 第4章 快速傅里叶变换(FFT)

DFT及其快速算法DFT（离散傅里叶变换）是傅里叶变换在离散时间序列上的表示，具有广泛应用于信号处理和图像处理等领域。

DFT的计算复杂度通常为O(N^2)，其中N为序列的长度。

为了减少计算复杂度，人们发展了许多快速算法，其中最著名的是快速傅里叶变换（FFT）。

DFT可以将一个信号或序列分解成一系列正弦和余弦函数的频谱成分。

它将时域的信号转换为频域的频谱，揭示了信号中各个频率成分的振幅和相位信息。

DFT可以用于信号滤波、频谱分析、数据压缩等许多应用。

DFT的定义如下：X[k]=Σ(x[n]*e^(-j*2πk*n/N))，其中0<=k<N该公式表示了将N个离散时间域样本x[n]变换为N个离散频率域样本X[k]的计算方式。

其中e^(-j*2π/N)为旋转因子，N为序列的长度。

DFT的计算复杂度为O(N^2)，需要进行N次乘法和加法运算。

对于大规模的序列，计算速度较慢，为了提高计算效率，人们提出了FFT算法。

FFT是一种高效的DFT计算方法，它基于DFT的对称性质和递归算法来减少计算量。

FFT的计算复杂度为O(NlogN)，比DFT快速得多。

FFT算法的基本思想是将一个长度为N的序列分解为两个长度为N/2的子序列，并利用子序列的DFT结果计算整个序列的DFT结果。

这个过程不断重复，直到达到长度为1的序列，也就是基本的正弦和余弦函数。

FFT算法主要有两种形式：快速递归FFT和快速迭代FFT。

快速递归FFT是通过递归的方式将序列分解为子序列，并利用子序列的DFT结果计算整个序列的DFT结果。

这个过程类似于分治法，将复杂的问题分解为简单的子问题，然后将子问题的解合并起来得到最终结果。

快速迭代FFT是通过迭代的方式将序列分解为子序列，然后利用旋转因子和蝶形运算来计算序列的DFT结果。

蝶形运算是FFT算法中的基本操作，通过两两配对的方式进行乘法和加法运算，将两个输入序列转换为两个输出序列。

这个过程可以通过迭代的方式进行，并且可以实现并行计算，提高计算速度。

G[3] 1
k 0,1, , N 1
2
13
4.2 按时间抽取（DIT）的基2–FFT算法
将系数统一为 WNk 2 WN2k ,则可得
x[0]
N 4点
x[4]
DFT
G[0]
X [0]
G[1]
X [1]
x[2]
N 4点
WN0
x[6]
DFT
WN2
G[2]
1 G[3]
1
X [2] X [3]
x[1]
N 4点
X m1[i] WNr X m1[ j] , X m1[i] WNr X m1[ j]
m 1, 2 ,
每一个蝶形需要一次复数乘法和两次复数加法。
17
4.2 按时间抽取（DIT）的基2–FFT算法
N点的DIT-FFT计算量为
复数乘法：
1
N 2
log2
N
N 2
复数加法：
2
N 2
log2
N
N
例： 如果每次复数乘法需要100us，每次复数加法需要20us，来 计算N=1024点DFT，则需要
12
4.2 按时间抽取（DIT）的基2–FFT算法
同理
( N 4)1
( N 4)1
G[k] DFT[g[r]]
g[2l]WN2lk2
g[2l 1]WN(22l1)k
l 0
l 0
( N 4)1
( N 4)1
g[2l]WNlk 4 WNk 2
g[2l 1]WNlk 4 ,
l 0
l 0
k 0,1,
(3) WN0 WN4 WN8 WN12 WN16 WN20 WN24 WN28
或 WN4i i 0,1, 2, 3, 4, 5, 6, 7 (dm 1)

X 6(k)
x6 (l)WNkl/ 4 DFT [x6(l)]
i0
x5 (l ) x6 (l )

x2 x2
(2l (2l
)
1)

,
l

0,1, N
/
4
1
(4.2.11)
课件
12
第4章 快速傅里叶变换(FFT)
x(0 )
N/4点 X3(0 )
x(4 )
DFT X3(1 )
e N
j 2 m
e N
WNm
(4.2.2)
其对称性表现为
WNm WNN m 或者 [WNN m ] WNm
m N
WN 2
WNm
课件
4
第4章 快速傅里叶变换(FFT)
4.2.2 时域抽取法基2FFT基本原理 FFT 算 法 基 本 上 分 为 两 大 类 ： 时 域 抽 取 法
课件
21
第4章 快速傅里叶变换(FFT)
x(0 )
N/4点
X(0 )
x(1 )
DFT
X(4 )
x(2 )
W
0 N
N/4点
X(2 )
x(3 )
W
2 N
DFT
X(6 )
x(4 )
W
0 N
N/4点
X(1 )
x(5 )
W
1 N
DFT
X(5 )
x(6 )
W
2 N
W
0 N
N/4点
X(3 )
x(7 )
W
3 N
W
X
(k

N 2
)