第五章_快速傅立叶变换（ FFT）.pdf

立即下载 作者: 老夫的少女心
上传时间: 2025-11-16
关键词: 算法 FFT 机器  概述 5.1 复数 抽取 5.7 NnX
大小 883.4 KB
描述
第5章 快速傅立叶变换（FFT）
5.1 概述
5.2 时间抽取基 2 算法
5.3 频率抽取基 2 算法
5.4 减少运算量的措施
5.5 分裂基算法
5.6 线性调频 Z 变换
5.7 其它算法
5.1 概述
1
2
0
) ( ) 0,1, 1
N
j nk N
n
X k x n e k Nπ
−
−
=
= = −∑（
2
( ) ( ) DFT
1
x n N x n
N X k
N N N −
若 是 点序列， 实现 的 ，
即求出 个（ ）需要：
次复数乘法，（ ）次复数加法!
2
4 2
1, 2 1 2
( ) : 1024 1048576
( ), 512, 262144 !
x n N N
x n n N N N= = =
＝ ， ＝
FFT 的思路： 2 /j NW e π−＝
1
0
) ( ) 0,1, 1
N
nk
n
X k x n W k N
−
=
= = −∑（
0
2
1. 1
2. 1
3.
4.
mN
N r r
N r r
W
W
W W
W W
+
+
=
=
=
= −
0 0 0 0
0 1 2 3
0 2 4 6
0 3 6 9
1 1
1 1
1 1
1 1
(0) (0)
(1) (1)
(2) (2)
(3) (3)
1 1 1 1 (0)
1 1 (1)
(2)1 1 1 1
(3)1 1
1 1 1 1
1 1
1 1 1 1
1 1
W W W WX x
X W W W W x
X xW W W W
X xW W W W
x
W W x
x
xW W
W W
W W
    
    
    =     
    
     
   
   − −   =    − −   
   − − 

− −
=
−
− −
(0)
(2)
(1)
(3)
x
x
x
x
  
   
   

目录
算法/FFT/机器//概述/5.1/复数/抽取/5.7/NnX/ 算法/FFT/机器//概述/5.1/复数/抽取/5.7/NnX/