1
第四章
FFT---DFT
的快速算法
2
§
1 FFT
算法的基本思想
∑
=
=
1
0
)
(
)
(
:
N
n
kn
N
W
n
x
k
X
DFT
1
0
≤
≤
N
k
N
j
N
e
W
π
2
=
1
、直接计算
DFT
存在的问题：
设
x(n)
为复数对每个
k
，计算
X(k)
，共需
N
次复乘及
N-1
次复加。
N
个
k
，则共需
N
2
次复乘及
N(N-1)
次复加。
4N
2
次实乘及
2N(2N-1)
次实加
3
如
N=1024
复乘次数约为
100
万次。
2
、提高
DFT
的运算效率的途径
kn
N
W
（
1
）利用的对称性
=
=
)
(
)
(
kn
N
kn
N
n
N
k
N
W
W
W
k
N
N
N
k
N
N
k
N
W
W
W
W
=
=
+
2
2
()
(
)
=
=
kn
N
kn
N
n
k
N
N
W
W
W
4
的周期性
）
kn
N
W
2
（
n
N
k
N
N
n
k
N
kn
N
W
W
W
)
(
)
(
+
+
=
=
k
N
k
N
W
W
2
2
=
2
2
k
N
k
N
W
W
=
1
2
/
=
N
N
W
1
=
N
N
W
(3)
将大点数
DFT
分解成小点数
DFT
5
§
2
时域抽取基
—2 FFT
算法
)
2
(
—
基一、算法原理：
γ
2
=
N
思想：将
x(n)
在时域按序号
n
的奇偶性分成两个
N/2
点子序列，
然后再计算
DFT,
+
=
=
)
1
2
(
)
(
)
2
(
)
(
2
1
r
x
r
x
r
x
r
x
设
1
2
0
≤
≤
N
r
∑
∑
∑
=
+
=
=
+
+
=
=
1
2
0
)
1
2
(
1
2
0
2
1
0
)
1
2
(
)
2
(
)
(
)
(
N
r
k
r
N
N
r
rk
N
N
n
nk
N
W
r
x
W
r
x
W
n
x
k
X
则
∑
∑
=
=
+
=
1
2
0
2
2
1
2
0
2
1
)
(
)
(
N
r
k
N
rk
N
N
r
rk
N
W
W
r
x
W
r
x
6
∑
∑
=
=
+
=
1
2
0
2
2
1
2
0
2
1
)
(
)
(
N
r
rk
N
k
N
N
r
rk
N
W
r
x
W
W
r
x
)
(
)
(
2
1
k
X
W
k
X
k
N
+
=
1
0
≤
≤
N
k
X
1
(k),X
2
(k)
分别为偶数号序列和奇数号序列的
N/2
点
DFT,
其周期均为
N/2.
=
+
=
+
)
(
)
2
(
)
(
)
2
(
2
2
1
1
k
X
N
k
X
k
X
N
k
X
k
N
N
k
N
W
W
=
+
2
Q
又
7
上式又可写为
∴
=
+
+
=
)
(
)
(
)
2
(
)
(
)
(
)
(
2
1
2
1
k
X
W
k
X
N
k
X
k
X
W
k
X
k
X
k
N
k
N
1
2
0
≤
≤
N
k
这样
N
点
X(k)
，可由两个
N/2
点
DFT
求出。上述算法可用蝶形运算表示：
)
(
1
k
X
)
(
2
k
X
k
N
W
)
(
)
(
2
1
k
X
W
k
X
k
N
+
)
(
k
X
)
2
(
N
k
X
+
)
(
)
(
2
1
k
X
W
k
X
k
N
8
那么求一个
N
点
DFT
的流图可如下实现
(
以
N=8
为例）：
)
0
(
)
0
(
1
x
x
=
)
2
(
)
1
(
1
x
x
=
)
4
(
)
2
(
1
x
x
=
)
6
(
)
3
(
1
x
x
=
)
1
(
)
0
(
2
x
x
=
)
3
(
)
1
(
2
x
x
=
)
5
(
)
2
(
2
x
x
=
)
7
(
)
3
(
2
x
x
=
)
0
(
X
)
1
(
X
)
2
(
X
)
3
(
X
)
4
(
X
)
5
(
X
)
6
(
X
)
7
(
X
)
0
(
1
X
)
1
(
1
X
)
2
(
1
X
)
3
(
1
X
)
0
(
2
X
)
1
(
2
X
)
2
(
2
X
)
3
(
2
X
0
N
W
1
N
W
2
N
W
3
N
W
D
F
T
N
点
2
/
D
F
T
N
点
2
/
9
运算量分析：
N/2
次复乘
1
次复乘每个蝶形运算
N/2
个蝶形：
N
次复加
2
次复加而两个
N/2
点
DFT:
共需
)
1
2
(
)
1
2
(
2
2
=
×
N
N
N
N
次复乘，
2
)
2
(
2
2
2
N
N
=
×
次复加
=
+
≈
+
=
+
2
)
1
2
(
2
2
)
1
(
2
2
2
2
2
N
N
N
N
N
N
N
N
N
复加：复乘：
分解一次后，共需
≈=
22
NN
复加
：
复乘
：
而直接运算
N
点
DFT
需：
10
即经过一次分解，运算量就节省一半。
继续分解,将
X
1
(k)
、
X
2
(k)
分别分解成两个
N/4
点子序列的
DFT
。
+
==
)
1
2
(
)
(
)
2
(
)
(
1
4
1
3
l
x
l
x
l
x
l
x
令：
1
4
0
≤
≤
N
l
则有
∑
∑
=
+
=
+
+
=
1
4
0
)
1
2
(
2
1
1
4
0
2
2
1
1
)
1
2
(
)
2
(
)
(
N
l
k
l
N
N
l
lk
N
W
l
x
W
l
x
k
X
∑
∑
=
=
+
=
1
4
0
4
4
2
1
4
0
4
3
)
(
)
(
N
l
lk
N
k
N
N
l
lk
N
W
l
x
W
W
l
x
1
2
0
≤
≤
N
k
11
同理，令
=
+
+
=
)
(
)
(
)
4
(
)
(
)
(
)
(
4
2
3
1
4
2
3
1
k
X
W
k
X
N
k
X
k
X
W
k
X
k
X
k
N
k
N
+
==
)
1
2
(
)
(
)
2
(
)
(
2
6
2
5
l
x
l
x
l
x
l
x
k
N
W
2
1
4
0
≤
≤
N
k
可得：
=
+
+
=
)
(
)
(
)
4
(
)
(
)
(
)
(
6
2
5
2
6
2
5
2
k
X
W
k
X
N
k
X
k
X
W
k
X
k
X
k
N
k
N
1
4
0
≤
≤
N
k
12
如
N=8
则经两次分解后：
)
4
(
)
2
(
)
1
(
)
0
(
)
0
(
)
0
(
1
3
1
3
x
x
x
x
x
x
=
=
=
=
)
6
(
)
3
(
)
1
(
)
2
(
)
1
(
)
0
(
1
4
1
4
x
x
x
x
x
x
=
=
=
=
)
5
(
)
2
(
)
1
(
)
1
(
)
0
(
)
0
(
2
5
2
5
x
x
x
x
x
x
=
=
=
=
)
7
(
)
3
(
)
1
(
)
3
(
)
1
(
)
0
(
2
6
2
6
x
x
x
x
x
x
=
=
=
=
其中点均为而
,
2
)
(
),
(
),
(
),
(
6
5
4
3
DFT
k
X
k
X
k
X
k
X
)
4
(
)
0
(
)
1
(
)
0
(
)
(
)
(
2
3
2
3
1
0
2
3
3
x
W
x
x
W
x
W
n
x
k
X
k
k
n
nk
+
=
+
=
=
∑
=
1
0
≤
≤
k
=
+
=
+
=
+
=
∴
)
4
(
)
0
(
)
4
(
)
0
(
)
1
(
)
4
(
)
0
(
)
4
(
)
0
(
)
0
(
0
1
2
3
0
0
2
3
x
W
x
x
W
x
X
x
W
x
x
W
x
X
N
N
13
同理可求
=
+
=
)
6
(
)
2
(
)
1
(
)
6
(
)
2
(
)
0
(
0
4
0
4
x
W
x
X
x
W
x
X
N
N
=
+
=
)
5
(
)
1
(
)
1
(
)
5
(
)
1
(
)
0
(
0
5
0
5
x
W
x
X
x
W
x
X
N
N
=
+
=
)
7
(
)
3
(
)
1
(
)
7
(
)
3
(
)
0
(
0
6
0
6
x
W
x
X
x
W
x
X
N
N
综合起来，可得
N=8 DIT FFT
算法流图
14
)
0
(
X
)
1
(
X
)
2
(
X
)
3
(
X
)
4
(
X
)
5
(
X
)
6
(
X
)
7
(
X
)
0
(
x
)
4
(
x
)
2
(
x
)
6
(
x
)
1
(
x
)
5
(
x
)
3
(
x
)
7
(
x
0
N
W
0
N
W
0
N
W
0
N
W
0
N
W
1
N
W
2
N
W
3
N
W
)
0
(
3
X
)
1
(
3
X
)
0
(
4
X
)
1
(
4
X
)
0
(
5
X
)
1
(
5
X
)
0
(
6
X
)
1
(
6
X
)
0
(
1
X
)
1
(
1
X
)
2
(
1
X
)
3
(
1
X
)
0
(
2
X
)
1
(
2
X
)
2
(
2
X
)
3
(
2
X
0
N
W
0
N
W
2
N
W
2
N
W
15
二、运算量分析次分解经
N
2
log
=
γ
γ
2
=
N
每级共有
N/2
个蝶形，而每个蝶形有一次复乘和两次复加。
=
=
N
N
N
N
N
N
2
2
log
2
2
log
2
2
γγ
复加：复乘：
级运算量为
γ
∴
即
DIT FFT
运算量与成正比
，而直接计算
DFT
与
N
2
成正比。
N
N
2
log
186
log
2
2
≈
N
N
N
如：
N=2048
，则
16
三、算法特点及软件实现,1
、算法特点
(1)
原址运算：
k
N
m
m
m
W
j
A
i
A
i
A
)
(
)
(
)
(
1
1
+
=
k
N
m
m
m
W
j
A
i
A
j
A
)
(
)
(
)
(
1
1
=
(2)
、输入反序，输出正序
(
顺序
)
如：
N=8,
输入顺序为
)
7
(
)
3
(
)
5
(
)
1
(
)
6
(
)
2
(
)
4
(
)
0
(
x
x
x
x
x
x
x
x
若将
n
用
3
位二进制数表示，
17
n
反序顺序
0
000
000
0
4
100
001
1
2
010
010
2
6
110
011
3
1
001
100
4
5
101
101
5
3
011
110
6
7
111
111
7
(3)
蝶形运算变化规律个蝶形级每级共分解
2
2
N
N
γ
γ
=
1
2
m
其中第
m
级的蝶型数为个。
18
如
N=8
第一级个，
只有一种蝶算类型第二级个，
有两种蝶算类型第三级个，
有四种蝶算类型
0
N
W
0
N
W
0
N
W
2
N
W
2
N
W
3
N
W
0
2
1
2
2
2
1
N
W∴
∴
∴
2
、软件实现
(1)
、输入序列的整序及变址设输入序列存放为顺序
x(0)---x(7)
序号记为
n
而
FFT
要求反序
,
序号记为
n
n
n
0 000 000 1 001 100 2
010 010
3 011 110 4 100 001 5 101 101 6 110 011 7 111 111
19
对反序数
，下一个数是上一个数在最高位加
1
得到的。
而进位是从高位向低位进位。 由此从
0
开始便可得到其后的每一个反序数反向加法过程：
已知一反序数
J
2
N
J
<
2
N
J
J
=
2
N
J
+
下一反序数
4
N
J
<
4
N
J
≥
4
N
J
+
4
N
J
J
=
J
？
判断最高位
1
=
比较与
2
N
比较与
4
N
1
=
次高位
)
2
(
的作用即清零最高位
N
J
J
=
下一反序数比较与
8
N
1
+
最高位
20
变址过程
)
0
(
x
)
1
(
x
)
2
(
x
)
3
(
x
)
4
(
x
)
5
(
x
)
6
(
x
)
7
(
x
)
0
(
x
)
1
(
x
)
2
(
x
)
3
(
x
)
4
(
x
)
5
(
x
)
6
(
x
)
7
(
x
自然顺序反序设I表示自然数，J表示反序数当I
<
J
时，交换
x(
I
)
与
x(
J
)
，不交换当
J
I
≥
整序及变址程序框图
(
见
P
436
)
：
21
输入
N
开始
YES
YES
NO
2
2
N
NV
←
1
1
←
N
NM
1
←
J
1
←
I
J
I
≥
)
(
J
A
T
←
)
(
)
(
I
A
J
A
←
T
I
A
←
)
(
2
NV
K
←
J
K
≥
K
J
J
←
2
K
K
←
K
J
J
+
←
1
+
←
I
I
1
NM
I
>
1
1
Y
N
N
22
（
2
）
FFT
的递推运算
a.
用
L
表示运算的级数
DO 20 L=1,M
共
M
级
1
2
1
=
L
LE
b.
用
LE1
表示每级蝶算的类型数及同类型中参加运算的两点间距离
(
例第
1
级间隔
1
点，第
2
级间隔
2
点，第
3
级间隔
4
点
)
c.
用
LE
表示每级同类蝶算相距的距离，
点如第
1
级共
4
个，计算两个间距点第
3
级各
1
，计算两个间距点
L
L
E
2
=
2
2
1
=
8
2
3
=
0
8
W
3
8
0
8
~
W
W
0
8
W
0
8
W
l
N
l
k
N
kl
N
W
W
W
=
)
1
(
k
N
W
d,
系数的计算采用递推运算：
23
其中,L,
控制蝶算的级数
J
,
控制每一级蝶算的类型数 I
,
控制每一种蝶形的个数及运算起始点 因各种类型计算的起点不 同，当计算第J种蝶算时,I应从J开始取第一点计算第一级初始化计算第一种蝶形同类蝶形完？ 所有蝶形完？
M级完
？
结束跳过L
E
点计算下一类型
J
=J+1
计算下一级
L=L+1
N
DO 10
I=J,N,LE
内层循环
DO 20 J=1,LE1
次层循环
DO 20
L=1,M
外层循环
Y
NN
整序
Y Y
24
§
3
按频率抽取
(DIF)
的
FFT
算法
γ
2
=
N
一、算法原理：
∑
∑
∑
=
=
=
+
=
=
1
2
1
2
0
1
0
)
(
)
(
)
(
)
(
N
N
n
nk
N
N
n
nk
N
N
n
nk
N
W
n
x
W
n
x
W
n
x
k
X
∑
∑
=
+
=
+
+
=
1
2
0
2
1
2
0
)
2
(
)
(
N
n
k
N
n
N
N
n
nk
N
W
N
n
x
W
n
x
)
2
(
N
n
m
=
令将
x(n)
按
n
的顺序分成前后两半
()
∑
=
+
+
=
1
2
0
)
2
(
1
)
(
N
n
nk
N
k
W
N
n
x
n
x
1
0
≤
≤
N
k
k
k
N
N
N
N
W
W
)
1
(
,
1
2
2
=
=
Q
1
2
0
≤
≤
N
r
1
2
2
+
=
=
r
k
r
k
及令
25
rn
N
N
n
rn
N
N
n
W
N
n
x
n
x
W
N
n
x
n
x
r
X
2
1
2
0
2
1
2
0
)
2
(
)
(
)
2
(
)
(
)
2
(
∑
∑
=
=
+
+
=
+
+
=
n
r
N
N
n
n
N
n
r
N
N
n
W
W
N
n
x
n
x
W
N
n
x
n
x
r
X
2
1
2
0
)
1
2
(
1
2
0
)
2
(
)
(
)
2
(
)
(
)
1
2
(
∑
∑
=
+
=
+
=
+
=
+
)
2
(
)
(
)
(
1
N
n
x
n
x
n
x
+
+
=
令
1
2
0
≤
≤
N
n
n
N
W
N
n
x
n
x
n
x
)]
2
(
)
(
[
)
(
2
+
=
)
2
(
)
(
1
r
X
r
X
=
则
1
2
0
≤
≤
N
r
)
1
2
(
)
(
2
+
=
r
X
r
X
26
)
(
n
x
n
N
W
n
N
W
N
n
x
n
x
)]
2
(
)
(
[
+
)
2
(
)
(
N
n
x
n
x
+
+
)
2
(
N
n
x
+
蝶形经顺序分解，将
N
点
DFT
按
k
的奇偶分成了两个新的序列的
N/2
点
DFT
。当
N=8
时，如下图示：
)
0
(
x
)
1
(
x
)
2
(
x
)
3
(
x
)
4
(
x
)
5
(
x
)
6
(
x
)
7
(
x
0
N
W
1
N
W
2
N
W
3
N
W
)
0
(
1
x
)
1
(
1
x
)
2
(
1
x
)
3
(
1
x
)
0
(
2
x
)
1
(
2
x
)
2
(
2
x
)
3
(
2
x
)
0
(
X
)
1
(
X
)
2
(
X
)
3
(
X
)
4
(
X
)
5
(
X
)
6
(
X
)
7
(
X
N/2点
DFT
N/2点
DFT
27
继续分解，可得
( ),N=8
时的
DIF
流图如下次分解经
γ
0
N
W
0
N
W
0
N
W
0
N
W
0
N
W
0
N
W
2
N
W
0
N
W
1
N
W
2
N
W
3
N
W
2
N
W
x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)
X(0) X(4) X(2) X(6) X(1) X(5) X(3) X(7)
28
二、特点：
1
、顺序输入，反序输出。
2
、与
DIT FFT
流图互为转置三、
IFFT
算法流图
∑
=
=
1
0
)
(
1
)
(
N
k
kn
N
W
k
X
N
n
x
据
IDFT
用代替
，并将计算结果乘
1/N(
一般分解
)
。
N
W
γ
)
2
(
1
W
1
N
则
DIT FFT
算法及
DIF FFT
算法均可直接用来运算
IDFT
。
如：利用
DIF FFT
流图计算
IFFT
，如下图示：
29
)
0
(
X
)
1
(
X
)
2
(
X
)
3
(
X
)
4
(
X
)
5
(
X
)
6
(
X
)
7
(
X
)
0
(
x
)
4
(
x
)
2
(
x
)
6
(
x
)
1
(
x
)
5
(
x
)
3
(
x
)
7
(
x
21 21 21 21
0
21
N
W
1
21
N
W
2
21
N
W
3
21
N
W
0
21
N
W
2
21
N
W
0
21
N
W
0
21
N
W
0
21
N
W
0
21
N
W
0
21
N
W
2
21
N
W
21
21 21
2121
21
21
21
相当于
DIT IFFT
。
时域被抽取
(
奇偶
)
DIT FFT
可用于计算
DIF IFFT
DIF FFT
可用于计算
DIT IFFT
30
§
4 N
为组合数的
FFT
算法互素）
、
如：
1
1
1
1
(
q
p
q
p
N
=
可将
x(n)
分解成
p
1
组，每组有
q
1
点组成，且每两点相距
p
1
点。即：每隔
p
1
点抽取一个数据。
5
3
15
×
=
=
N
如：
x(0) x(3) x(6) x(9) x(12) x(1) x(4) x(7) x(10) x(13) x(2) x(5) x(8) x(11) x(14)
]
[
[
)
0
(
x
)
1
(
x
)
1
(
1
p
x
……
通式：
[
]
1
1
1
)
1
(
)
2
(
p
q
x
p
x
L
L
[
]
1
)
1
(
)
1
2
(
1
1
1
+
+
p
q
x
p
x
L
L
[
]
1
)
1
(
)
1
2
(
1
1
1
1
1
+
+
p
p
q
x
p
p
x
L
L
……
)
(
1
p
x
)
1
(
1
+
p
x
)
1
(
1
1
+
p
p
x
则
x(n)
的
N
点
DFT
为：
31
∑
∑
∑
=
=
=
+
+
+
=
1
0
1
0
1
0
)
(
)
(
)
(
)
(
N
n
nk
N
N
n
nk
N
N
n
kn
N
W
n
x
W
n
x
W
n
x
k
X
L
1
)
1
(
1
1
1
+
=
p
r
p
n
p
n
组取
1
1
1
+
=
r
p
nn
组取
r
p
nn
1
0
=
组取
1
0
1
≤
≤
q
r
∑
∑
∑
=
+
=
+
=
+
+
+
+
+
=
1
)
1
(
1
1
1
0
)
1
(
1
1
0
1
1
1
1
1
1
1
1
)
1
(
)
1
(
)
(
q
o
r
p
r
p
k
N
q
r
r
p
k
N
q
r
r
kp
N
W
p
r
p
x
W
r
p
x
W
r
p
x
L
∑
∑
∑
=
=
=
+
+
+
+
+
=
1
1
1
)
1
(
1
0
1
1
0
1
1
1
1
1
1
1
1
)
1
(
)
1
(
)
(
q
o
r
kr
q
p
k
N
q
r
kr
q
k
N
q
r
kr
q
W
p
r
p
x
W
W
r
p
x
W
W
r
p
x
L
∑
∑
∑
=
=
=
+
+
+
=
1
1
)
1
(
1
0
1
1
0
0
1
1
1
1
1
1
1
1
)
(
)
(
)
(
q
o
r
kr
q
p
p
k
N
q
r
kr
q
k
N
q
r
kr
q
W
r
x
W
W
r
x
W
W
r
x
L
)
(
)
(
)
(
1
)
1
(
1
0
0
1
1
k
X
W
k
X
W
k
X
W
p
p
k
N
k
N
N
+
+
+
=
L
1
,
3
,
2
,
1
,
0
=
N
k
L
32
这就是混合基
(
基
p
1
+
基
q
1
) FFT
算法的递推公式。
运算量分析：
1
1)
-
(
1
1
1
1
2
1
1
1
1
=
=
)
N(q
q
q
p
q
p
C
DFT
q
p
N
复数加法：复数乘法直接运算，需点个次复加也为次复乘为个不计第一项次每个
)
1
(
)
1
(
,
)
,
1
(
1
,
1
1
0
1
=
p
N
p
N
k
N
W
p
k
N
而分解后
)
1
(
)
1
(
:
1
1
1
2
1
1
+
=
+
∴
p
N
Nq
p
N
q
p
共需复数乘法为
)
(
1
1
q
p
N
=
2
1
1
)
1
(
N
q
p
N
<
+
=
)
2
(
)
1
(
)
1
(
1
1
1
1
+
=
+
q
p
N
p
N
q
N
复数加法：
1
1
1
1
)
1
(
q
p
q
p
<
+
一般
Q
33
分解后运算量为点则可继续分解，如：
若
DFT
q
q
p
q
q
1
2
2
1
1
,
=
+
+
)
2
(
)
1
(
2
2
1
2
2
1
q
p
q
q
p
q
复加：复乘：
)
2
(
)
1
(
)
1
(
2
2
1
2
2
1
1
1
+
+
=
+
+
∴
q
p
p
N
q
p
q
p
p
N
复乘：
总运算量为：
)
3
(
)
2
(
)
1
(
2
2
1
2
2
1
1
1
+
+
=
+
+
q
p
p
N
q
p
q
p
p
N
复加：
则有一般地，若
,
2
1
m
m
q
p
p
p
N
=
L
)
1
(
)
(
2
1
2
1
+
+
+
+
+
+
+
+
m
q
p
p
p
N
m
q
p
p
p
N
m
m
m
m
LL
复加：复乘：
34
例：画出
N=6
点的
FFT
信号流图
3
2
6
×
=
=
N
点序列。
分解成两个将
3
)
(
n
x
)
2
(
x
)
3
(
x
)
4
(
x
)
5
(
x
]
[
=
)
(
0
r
x
[
)
(
1
r
x
]
)
0
(
x
)
1
(
x
∑
∑
=
+
=
+
+
=
∴
2
0
)
1
2
(
6
2
0
2
6
)
1
2
(
)
2
(
)
(
r
k
r
r
rk
W
r
x
W
r
x
k
X
∑
∑
=
=
+
+
=
2
0
3
6
2
0
3
)
1
2
(
)
2
(
r
rk
k
r
rk
W
r
x
W
W
r
x
5
0
≤
≤
k
)
(
)
(
1
6
0
k
X
W
k
X
k
+
=
35
∑
=
=
2
0
3
0
0
)
(
)
(
r
rk
W
r
x
k
X
其中：
∑
=
=
2
0
3
1
1
)
(
)
(
r
rk
W
r
x
k
X
k
k
W
x
W
x
x
k
X
2
3
0
3
0
0
0
)
2
(
)
1
(
)
0
(
)
(
+
+
=
即：
3
点
DFT
k
k
W
x
W
x
x
2
3
3
)
4
(
)
2
(
)
0
(
+
+
=
2
0
≤
≤
k
)
4
(
)
2
(
)
0
(
)
0
(
0
x
x
x
X
+
+
=
2
3
1
3
0
)
4
(
)
2
(
)
0
(
)
1
(
W
x
W
x
x
X
+
+
=
4
3
2
3
0
)
4
(
)
2
(
)
0
(
)
2
(
W
x
W
x
x
X
+
+
=
同理：
)
5
(
)
3
(
)
1
(
)
0
(
1
x
x
x
X
+
+
=
2
3
1
3
1
)
5
(
)
3
(
)
1
(
)
1
(
W
x
W
x
x
X
+
+
=
4
3
2
3
1
)
5
(
)
3
(
)
1
(
)
2
(
W
x
W
x
x
X
+
+
=
36
具体流图如下：
展开将
)
(
),
(
1
0
k
X
k
X
)
0
(
0
X
)
1
(
0
X
)
2
(
0
X
)
0
(
1
X
)
1
(
1
X
)
2
(
1
X
0
6
W
1
6
W
2
6
W
3
6
W
4
6
W
5
6
W
0
3
W
1
3
W
2
3
W
2
3
W
4
3
W
0
3
W
x(0) x(2) x(4) x(1)
x(3)
x(5)
X(0)
X(1) X(2) X(3) X(4)
X(5)
37
§
5、线性调频z变换
(Chirp z Transform)
一、问题的提出基
-2 FFT
算法是研究在
Z
平面单位圆上等间隔取样点
Z
k
处的取样值
X(z
k
)
的快速算法，要求
N
为高度复合的数。
实际上有时对其它围线上的
Z
变换发生兴趣，或能有效地计算当
N
是素数时序列的
DFT
CZT
就是适用于这种更为一般情况下由
x(n)
求
X (z
k
)
的快速变换
38
二、算法原理
)
(
n
x
1
0
≤
≤
N
n
∑
=
=
1
0
)
(
)
(
N
n
n
z
n
x
z
X
令
)
(
1
,
,
1
,
0
,
N
M
M
k
AW
z
k
k
≠
=
=
L
0
0
0
0
,
Φ
=
=
j
j
e
W
W
e
A
A
W
A
θ
均为任意复数，其中
、
0
0
0
0
)
(
Φ
=
∴
jk
k
j
k
e
W
e
A
z
θ
L
L
）
（
0
0
1
0
0
1
Φ
+
=
θ
j
e
W
A
z
0
0
0
θ
j
e
A
z
=
即
）
）
（
（
0
0
1
-
)
1
(
0
0
1
Φ
+
=
M
j
M
M
e
W
A
z
θ
39
1
,
)
1
(
0
0
0
≤
A
Z
A
的矢量半径，一般起始点的相位（可正可负）
0
0
,
)
2
(
Z
θ
顺时针转逆时针转，
，
间的相位差相邻
k
k
k
Z
Z
Z
,
0
0
,
)
3
(
0
0
0
<
Φ
>
Φ
Φ
的一段圆弧半径为向内弯曲向外弯曲控制围线盘旋方向
0
0
0
0
0
0
0
,
1
,
,
1
,
,
1
)
4
(
A
W
W
K
W
W
K
W
W
KK
=
↓
↑
>
↑
↑
<
取样围线如图所示
0
Φ
0
Φ
1
M
Z
1
Z
0
Z
0
θ
0
A
1
0
0
W
A
)
Re(
Z
)
Im(
Z
j
DFT
n
x
N
W
A
N
M
的即为若满足
)
(
2
,
1
,
0
,
1
,
)
5
(
0
0
0
0
π
θ
=
Φ
=
=
=
=
40
计算表示：
∑
=
=
1
0
)
(
)
(
N
n
nk
n
k
W
A
n
x
z
X
[]
2
2
2
)
(
21
n
k
k
n
nk
+
=
Q
∑
=
=
∴
1
0
2
2
)
(
2
2
2
2
)
(
)
(
N
n
k
n
k
n
n
k
W
W
W
A
n
x
z
X
∑
=
=
1
0
2
)
(
2
2
2
2
2
]
)
(
[
N
n
n
k
n
n
k
W
W
A
n
x
W
2
2
)
(
)
(
n
n
W
A
n
x
n
f
=
令
2
2
)
(
n
W
n
h
=
1
0
≤
≤
N
n
∑
=
=
1
0
2
)
(
)
(
)
(
2
N
n
k
k
n
k
h
n
f
W
z
X
则
)
(
)
(
2
2
k
h
k
f
W
k
=
1
0
≤
≤
M
k
41
运算流程
)
(
k
g
)
(
n
h
)
(
n
f
)
(
n
x
)
(
k
Z
X
1
,
2
,
1
,
0
=
N
n
L
1
,
2
,
1
,
0
=
M
k
L
2
2
n
n
W
A
2
2
k
W
三、
CZF
实现步骤：
相乘再与求由求
)
(
,
,
,
,
,
),
(
).
1
(
2
0
0
0
0
2
n
x
W
A
W
A
n
f
n
n
Φ
θ
)
(
)
(
,
,
2
0
0
2
0
0
n
x
W
A
n
f
e
W
W
e
A
A
n
n
j
j
Φ
=
=
=
θ
1
0
≤
≤
N
n
DFT
n
f
FFT
L
N
M
L
L
m
的求并利用且使选取最小
)
(
,
2
1
,
).
2
(
=
+
>
∑
=
=
1 0
2
)
(
)
(
L n
rn
L
j
e
n
f
r
F
π
1
0
≤
≤
L
r
42
如下选取
2
2
)
(
).
3
(
n
W
n
h
=
点取
M
k
g
)
(
Q
≤
≤
≤
≤
+
≤
≤
=
N
L
n
M
L
n
N
L
W
M
n
W
n
h
n
L
n
任意
，
1
1
,
1
0
,
)
(
2
)
(
2
2
2
个结果线性卷积前与等于个点圆周卷积的前与如此取
M
n
h
n
f
M
n
h
n
f
)
(
)
(
,
)
(
)
(
)]]
(
[
)]
(
[
[
)
(
,
),
(
)
1
(
),
(
)
(
).
4
(
n
h
FFT
n
f
FFT
IFFT
k
g
M
k
g
N
M
n
h
n
f
=
+
≥
个值取前求列长作
1
0
,
)
(
)
(
).
5
(
2
2
≤
≤
=
M
k
W
k
g
z
X
k
k
求四、运算量
)
,
(
),
(
)
(
).
1
(
2
2
2
2
可先计算好次复乘
。
需形成
n
n
n
n
W
A
N
n
x
W
A
n
f
=
次复乘各需求
L
L
r
H
r
F
2
log
2
)
(
),
(
).
2
(
次复乘需作
L
r
H
r
F
)
(
)
(
)
3
(
43
L
L
r
H
r
F
FFT
k
g
2
1
log
2
)],
(
)
(
[
)
(
).
4
(
又需求
=
次复乘需输出点形成
M
W
k
g
Z
X
M
k
k
,
)
(
)
(
).
5
(
2
2
=
M
L
N
L
L
+
+
+
=
∴
2
log
23
总的复乘数次复乘需时点而直接计算
N
M
Z
X
M
k
,
)
(
要小很多。
算法比直接算法运算量后，
量较小，但当较小时，直接计算运算在 CZT
N
M
N
M
50
>
44
算法特点五、
CZT
率也是任意的
。
是任意的，即频率分辨的角间隔者均可为素数不必是高度合成数，二与入与出列长可不等可不等，
与
0
).
3
(
).
2
(
)
(
).
1
(
Φ
k
Z
M
N
M
N
为素数时也可以。
，即使来计算
，则可用
，
，
若率的分析数据进行窄带的高分辨任意频率上开始对输入可任意选定，因此可从起始点些特点。
析中螺旋形周线具有某平面上的圆，在语音分周线不必是
N
DFT
CZT
e
W
N
M
A
z
Z
N
j
π
2
0
1
).
6
(
).
5
(
).
4
(
=
=
=
.
DFT
CZT
个一般化的
，在某种意义上它是一算法具有很大的灵活性总之，
45
§
6 FFT
的应用一、计算卷积和相关
、计算卷积
1
)
(
)
(
)
(
)
(
)
(
1
0
n
h
n
x
k
n
h
k
x
n
y
N k
=
=
∑
=
)
(
n
x
)
(
n
h
)
(
n
y
2
1
)
(
,
)
(
N
n
h
N
n
x
→
列长设
N
n
h
n
x
N
N
N
N
补零到将且选择
)
(
),
(
2
1
).
1
(
2
1
γ
=
+
≥
)]
(
[
)
(
)],
(
[
)
(
)
(
),
(
).
2
(
n
h
FFT
k
H
n
x
FFT
k
X
k
H
k
X
=
=
计算
)
(
)
(
)
(
).
3
(
k
H
k
X
k
Y
=
求
)
(
).
4
(
k
Y
求
[
]
{}
则运算效率很高。
较大若次调用求
,
,
3
)
(
1
)
(
).
5
(
N
k
Y
FFT
N
n
y
=
46
、计算相关
2
∑
=
+
=
1
0
2
1
3
)
(
))
((
)
(
)
(
N
k
N
N
n
R
k
n
x
k
x
n
x
离散相关：
∑
=
+
=
1
0
2
1
3
)
(
)
(
)
(
N
k
k
n
x
k
x
n
x
线性相关
：
)
(
)
(
)
(
2
1
3
k
X
k
X
k
X
=
相关定理：
γ
2
,
1
).
1
(
2
1
=
+
≥
N
N
N
N
补零过程：
)]
(
[
)
(
)],
(
[
)
(
)
(
),
(
).
2
(
2
2
1
1
2
1
n
x
FFT
k
X
n
x
FFT
k
X
k
X
k
X
=
=
计算
)
(
)
(
)
(
).
4
(
2
1
3
k
X
k
X
k
X
=
求
)
(
).
3
(
1
k
X
求
[
]
{
}
=
=
)
(
1
)]
(
[
)
(
).
5
(
3
3
3
k
X
FFT
N
k
X
IFFT
n
x
求
47
DFT
N
FFT
N
点实序列同时运算两个点二、一个的实序列均为列长为设
N
n
x
n
x
)
(
),
(
2
1
)
(
)
(
)
(
2
1
n
jx
n
x
n
x
+
=
则，可令
)]
(
)
(
[
)]
(
[
)
(
2
1
n
jx
n
x
FFT
n
x
DFT
k
X
+
=
=
而
)
(
)
(
2
1
k
jX
k
X
+
=
呢？
和表示如何用
)
(
)
(
)
(
2
1
k
X
k
X
k
X
[]
[
]
)
(
)
(
21
)
(
)
(
2
n
x
n
x
n
x
jI
n
jx
m
=
=
)]
(
)
(
[
21
)]
(
Re[
)
(
1
n
x
n
x
n
x
n
x
+
=
=
Q
)
(
)]]
(
[Re[
k
X
n
x
DFT
ep
=
而
)
)
(
(
的周期性共轭对称分量
k
X
)]
(
))
((
)
(
[
21
)
(
)
(
1
k
R
k
X
k
X
k
X
k
X
N
N
ep
+
=
=
∴
)]
(
)
(
[
21
k
N
X
k
X
+
=
1
0
≤
≤
N
k
48
)]]
(
[
[
1
)]
(
[
)
(
2
2
n
x
jI
DFT
j
n
x
DFT
k
X
m
=
=
同理：
)]
(
))
((
)
(
[
21
)
(
1
k
R
k
X
k
X
j
k
X
j
N
N
op
=
=
)]
(
)
(
[
21
k
N
X
k
X
j
=
1
0
≤
≤
N
k
)
(
)
(
)
(
1
2
1
n
jx
n
x
n
x
+
=
>
<
构成复序列，
步骤：
1
0
≤
≤
N
n
)]
(
[
)
(
2
n
x
FFT
k
X
=
>
<
计算
)
0
(
)
(
3
X
N
X
=
>
<
令
1
0
),
(
4
≤
≤
>
<
N
k
k
N
X
求
)]
(
)
(
[
21
)
(
5
1
k
N
X
k
X
k
X
+
=
>
<
求
)]
(
)
(
[
21
)
(
2
k
N
X
k
X
j
k
X
=
49
DFT
N
FFT
N
点实序列同时运算一个点三、一个
2
N
n
x
2
)
(
实序列，列长为点实序列变成两个利用奇偶抽取
，将
N
n
x
)
(
)
2
(
)
(
1
n
x
n
x
=
即：令
)
1
2
(
)
(
2
+
=
n
x
n
x
1
0
≤
≤
N
n
构成一个复序列然后将
)
(
),
(
2
1
n
x
n
x
)
(
)
(
)
(
2
1
n
jx
n
x
n
y
+
=
：
、
、
求
)
(
)
(
)
(
2
1
k
X
k
X
k
Y
)]
(
[
)
(
n
y
FFT
k
Y
=
)]
(
)
(
[
21
)
(
1
k
N
Y
k
Y
k
X
+
=
)]
(
)
(
[
2
)
(
2
k
N
Y
k
Y
j
k
X
=
50
而由奇偶抽取原理：
)
(
)
(
)
(
2
2
1
k
X
W
k
X
k
X
k
N
+
=
1
0
≤
≤
N
k
)
(
)
(
)
(
2
2
1
k
X
W
k
X
k
N
X
k
N
=
+
)
1
2
(
)
(
),
2
(
)
(
)
(
1
2
1
+
=
=
>
<
n
x
n
x
n
x
n
x
n
x
进行奇偶抽取，得将具体步骤
：
)
(
)
(
)
(
,
2
2
1
n
jx
n
x
n
y
+
=
>
<
构成复序列
)
(
)
(
)
(
3
2
1
k
X
k
X
k
Y
及及求
>
<
1
0
),
(
)
(
)
(
4
2
2
1
≤
≤
+
=
>
<
N
k
k
X
W
k
X
k
X
k
N
求
1
0
),
(
)
(
)
(
5
2
2
1
≤
≤
=
+
>
<
N
k
k
X
W
k
X
N
k
X
k
N
求
51
作业：
1
、画出
9
点
FFT
算法流图，并分析其运算量。
2
、编写基
-2 DIT FFT
子程序，并用其计算以下两序列的线性卷积，打印输出结果。
)
(
),
(
2
1
n
x
n
x
1
123
4
0
第四章
FFT---DFT
的快速算法
2
§
1 FFT
算法的基本思想
∑
=
=
1
0
)
(
)
(
:
N
n
kn
N
W
n
x
k
X
DFT
1
0
≤
≤
N
k
N
j
N
e
W
π
2
=
1
、直接计算
DFT
存在的问题：
设
x(n)
为复数对每个
k
，计算
X(k)
，共需
N
次复乘及
N-1
次复加。
N
个
k
，则共需
N
2
次复乘及
N(N-1)
次复加。
4N
2
次实乘及
2N(2N-1)
次实加
3
如
N=1024
复乘次数约为
100
万次。
2
、提高
DFT
的运算效率的途径
kn
N
W
（
1
）利用的对称性
=
=
)
(
)
(
kn
N
kn
N
n
N
k
N
W
W
W
k
N
N
N
k
N
N
k
N
W
W
W
W
=
=
+
2
2
()
(
)
=
=
kn
N
kn
N
n
k
N
N
W
W
W
4
的周期性
）
kn
N
W
2
（
n
N
k
N
N
n
k
N
kn
N
W
W
W
)
(
)
(
+
+
=
=
k
N
k
N
W
W
2
2
=
2
2
k
N
k
N
W
W
=
1
2
/
=
N
N
W
1
=
N
N
W
(3)
将大点数
DFT
分解成小点数
DFT
5
§
2
时域抽取基
—2 FFT
算法
)
2
(
—
基一、算法原理：
γ
2
=
N
思想：将
x(n)
在时域按序号
n
的奇偶性分成两个
N/2
点子序列，
然后再计算
DFT,
+
=
=
)
1
2
(
)
(
)
2
(
)
(
2
1
r
x
r
x
r
x
r
x
设
1
2
0
≤
≤
N
r
∑
∑
∑
=
+
=
=
+
+
=
=
1
2
0
)
1
2
(
1
2
0
2
1
0
)
1
2
(
)
2
(
)
(
)
(
N
r
k
r
N
N
r
rk
N
N
n
nk
N
W
r
x
W
r
x
W
n
x
k
X
则
∑
∑
=
=
+
=
1
2
0
2
2
1
2
0
2
1
)
(
)
(
N
r
k
N
rk
N
N
r
rk
N
W
W
r
x
W
r
x
6
∑
∑
=
=
+
=
1
2
0
2
2
1
2
0
2
1
)
(
)
(
N
r
rk
N
k
N
N
r
rk
N
W
r
x
W
W
r
x
)
(
)
(
2
1
k
X
W
k
X
k
N
+
=
1
0
≤
≤
N
k
X
1
(k),X
2
(k)
分别为偶数号序列和奇数号序列的
N/2
点
DFT,
其周期均为
N/2.
=
+
=
+
)
(
)
2
(
)
(
)
2
(
2
2
1
1
k
X
N
k
X
k
X
N
k
X
k
N
N
k
N
W
W
=
+
2
Q
又
7
上式又可写为
∴
=
+
+
=
)
(
)
(
)
2
(
)
(
)
(
)
(
2
1
2
1
k
X
W
k
X
N
k
X
k
X
W
k
X
k
X
k
N
k
N
1
2
0
≤
≤
N
k
这样
N
点
X(k)
，可由两个
N/2
点
DFT
求出。上述算法可用蝶形运算表示：
)
(
1
k
X
)
(
2
k
X
k
N
W
)
(
)
(
2
1
k
X
W
k
X
k
N
+
)
(
k
X
)
2
(
N
k
X
+
)
(
)
(
2
1
k
X
W
k
X
k
N
8
那么求一个
N
点
DFT
的流图可如下实现
(
以
N=8
为例）：
)
0
(
)
0
(
1
x
x
=
)
2
(
)
1
(
1
x
x
=
)
4
(
)
2
(
1
x
x
=
)
6
(
)
3
(
1
x
x
=
)
1
(
)
0
(
2
x
x
=
)
3
(
)
1
(
2
x
x
=
)
5
(
)
2
(
2
x
x
=
)
7
(
)
3
(
2
x
x
=
)
0
(
X
)
1
(
X
)
2
(
X
)
3
(
X
)
4
(
X
)
5
(
X
)
6
(
X
)
7
(
X
)
0
(
1
X
)
1
(
1
X
)
2
(
1
X
)
3
(
1
X
)
0
(
2
X
)
1
(
2
X
)
2
(
2
X
)
3
(
2
X
0
N
W
1
N
W
2
N
W
3
N
W
D
F
T
N
点
2
/
D
F
T
N
点
2
/
9
运算量分析：
N/2
次复乘
1
次复乘每个蝶形运算
N/2
个蝶形：
N
次复加
2
次复加而两个
N/2
点
DFT:
共需
)
1
2
(
)
1
2
(
2
2
=
×
N
N
N
N
次复乘，
2
)
2
(
2
2
2
N
N
=
×
次复加
=
+
≈
+
=
+
2
)
1
2
(
2
2
)
1
(
2
2
2
2
2
N
N
N
N
N
N
N
N
N
复加：复乘：
分解一次后，共需
≈=
22
NN
复加
：
复乘
：
而直接运算
N
点
DFT
需：
10
即经过一次分解，运算量就节省一半。
继续分解,将
X
1
(k)
、
X
2
(k)
分别分解成两个
N/4
点子序列的
DFT
。
+
==
)
1
2
(
)
(
)
2
(
)
(
1
4
1
3
l
x
l
x
l
x
l
x
令：
1
4
0
≤
≤
N
l
则有
∑
∑
=
+
=
+
+
=
1
4
0
)
1
2
(
2
1
1
4
0
2
2
1
1
)
1
2
(
)
2
(
)
(
N
l
k
l
N
N
l
lk
N
W
l
x
W
l
x
k
X
∑
∑
=
=
+
=
1
4
0
4
4
2
1
4
0
4
3
)
(
)
(
N
l
lk
N
k
N
N
l
lk
N
W
l
x
W
W
l
x
1
2
0
≤
≤
N
k
11
同理，令
=
+
+
=
)
(
)
(
)
4
(
)
(
)
(
)
(
4
2
3
1
4
2
3
1
k
X
W
k
X
N
k
X
k
X
W
k
X
k
X
k
N
k
N
+
==
)
1
2
(
)
(
)
2
(
)
(
2
6
2
5
l
x
l
x
l
x
l
x
k
N
W
2
1
4
0
≤
≤
N
k
可得：
=
+
+
=
)
(
)
(
)
4
(
)
(
)
(
)
(
6
2
5
2
6
2
5
2
k
X
W
k
X
N
k
X
k
X
W
k
X
k
X
k
N
k
N
1
4
0
≤
≤
N
k
12
如
N=8
则经两次分解后：
)
4
(
)
2
(
)
1
(
)
0
(
)
0
(
)
0
(
1
3
1
3
x
x
x
x
x
x
=
=
=
=
)
6
(
)
3
(
)
1
(
)
2
(
)
1
(
)
0
(
1
4
1
4
x
x
x
x
x
x
=
=
=
=
)
5
(
)
2
(
)
1
(
)
1
(
)
0
(
)
0
(
2
5
2
5
x
x
x
x
x
x
=
=
=
=
)
7
(
)
3
(
)
1
(
)
3
(
)
1
(
)
0
(
2
6
2
6
x
x
x
x
x
x
=
=
=
=
其中点均为而
,
2
)
(
),
(
),
(
),
(
6
5
4
3
DFT
k
X
k
X
k
X
k
X
)
4
(
)
0
(
)
1
(
)
0
(
)
(
)
(
2
3
2
3
1
0
2
3
3
x
W
x
x
W
x
W
n
x
k
X
k
k
n
nk
+
=
+
=
=
∑
=
1
0
≤
≤
k
=
+
=
+
=
+
=
∴
)
4
(
)
0
(
)
4
(
)
0
(
)
1
(
)
4
(
)
0
(
)
4
(
)
0
(
)
0
(
0
1
2
3
0
0
2
3
x
W
x
x
W
x
X
x
W
x
x
W
x
X
N
N
13
同理可求
=
+
=
)
6
(
)
2
(
)
1
(
)
6
(
)
2
(
)
0
(
0
4
0
4
x
W
x
X
x
W
x
X
N
N
=
+
=
)
5
(
)
1
(
)
1
(
)
5
(
)
1
(
)
0
(
0
5
0
5
x
W
x
X
x
W
x
X
N
N
=
+
=
)
7
(
)
3
(
)
1
(
)
7
(
)
3
(
)
0
(
0
6
0
6
x
W
x
X
x
W
x
X
N
N
综合起来，可得
N=8 DIT FFT
算法流图
14
)
0
(
X
)
1
(
X
)
2
(
X
)
3
(
X
)
4
(
X
)
5
(
X
)
6
(
X
)
7
(
X
)
0
(
x
)
4
(
x
)
2
(
x
)
6
(
x
)
1
(
x
)
5
(
x
)
3
(
x
)
7
(
x
0
N
W
0
N
W
0
N
W
0
N
W
0
N
W
1
N
W
2
N
W
3
N
W
)
0
(
3
X
)
1
(
3
X
)
0
(
4
X
)
1
(
4
X
)
0
(
5
X
)
1
(
5
X
)
0
(
6
X
)
1
(
6
X
)
0
(
1
X
)
1
(
1
X
)
2
(
1
X
)
3
(
1
X
)
0
(
2
X
)
1
(
2
X
)
2
(
2
X
)
3
(
2
X
0
N
W
0
N
W
2
N
W
2
N
W
15
二、运算量分析次分解经
N
2
log
=
γ
γ
2
=
N
每级共有
N/2
个蝶形，而每个蝶形有一次复乘和两次复加。
=
=
N
N
N
N
N
N
2
2
log
2
2
log
2
2
γγ
复加：复乘：
级运算量为
γ
∴
即
DIT FFT
运算量与成正比
，而直接计算
DFT
与
N
2
成正比。
N
N
2
log
186
log
2
2
≈
N
N
N
如：
N=2048
，则
16
三、算法特点及软件实现,1
、算法特点
(1)
原址运算：
k
N
m
m
m
W
j
A
i
A
i
A
)
(
)
(
)
(
1
1
+
=
k
N
m
m
m
W
j
A
i
A
j
A
)
(
)
(
)
(
1
1
=
(2)
、输入反序，输出正序
(
顺序
)
如：
N=8,
输入顺序为
)
7
(
)
3
(
)
5
(
)
1
(
)
6
(
)
2
(
)
4
(
)
0
(
x
x
x
x
x
x
x
x
若将
n
用
3
位二进制数表示，
17
n
反序顺序
0
000
000
0
4
100
001
1
2
010
010
2
6
110
011
3
1
001
100
4
5
101
101
5
3
011
110
6
7
111
111
7
(3)
蝶形运算变化规律个蝶形级每级共分解
2
2
N
N
γ
γ
=
1
2
m
其中第
m
级的蝶型数为个。
18
如
N=8
第一级个，
只有一种蝶算类型第二级个，
有两种蝶算类型第三级个，
有四种蝶算类型
0
N
W
0
N
W
0
N
W
2
N
W
2
N
W
3
N
W
0
2
1
2
2
2
1
N
W∴
∴
∴
2
、软件实现
(1)
、输入序列的整序及变址设输入序列存放为顺序
x(0)---x(7)
序号记为
n
而
FFT
要求反序
,
序号记为
n
n
n
0 000 000 1 001 100 2
010 010
3 011 110 4 100 001 5 101 101 6 110 011 7 111 111
19
对反序数
，下一个数是上一个数在最高位加
1
得到的。
而进位是从高位向低位进位。 由此从
0
开始便可得到其后的每一个反序数反向加法过程：
已知一反序数
J
2
N
J
<
2
N
J
J
=
2
N
J
+
下一反序数
4
N
J
<
4
N
J
≥
4
N
J
+
4
N
J
J
=
J
？
判断最高位
1
=
比较与
2
N
比较与
4
N
1
=
次高位
)
2
(
的作用即清零最高位
N
J
J
=
下一反序数比较与
8
N
1
+
最高位
20
变址过程
)
0
(
x
)
1
(
x
)
2
(
x
)
3
(
x
)
4
(
x
)
5
(
x
)
6
(
x
)
7
(
x
)
0
(
x
)
1
(
x
)
2
(
x
)
3
(
x
)
4
(
x
)
5
(
x
)
6
(
x
)
7
(
x
自然顺序反序设I表示自然数，J表示反序数当I
<
J
时，交换
x(
I
)
与
x(
J
)
，不交换当
J
I
≥
整序及变址程序框图
(
见
P
436
)
：
21
输入
N
开始
YES
YES
NO
2
2
N
NV
←
1
1
←
N
NM
1
←
J
1
←
I
J
I
≥
)
(
J
A
T
←
)
(
)
(
I
A
J
A
←
T
I
A
←
)
(
2
NV
K
←
J
K
≥
K
J
J
←
2
K
K
←
K
J
J
+
←
1
+
←
I
I
1
NM
I
>
1
1
Y
N
N
22
（
2
）
FFT
的递推运算
a.
用
L
表示运算的级数
DO 20 L=1,M
共
M
级
1
2
1
=
L
LE
b.
用
LE1
表示每级蝶算的类型数及同类型中参加运算的两点间距离
(
例第
1
级间隔
1
点，第
2
级间隔
2
点，第
3
级间隔
4
点
)
c.
用
LE
表示每级同类蝶算相距的距离，
点如第
1
级共
4
个，计算两个间距点第
3
级各
1
，计算两个间距点
L
L
E
2
=
2
2
1
=
8
2
3
=
0
8
W
3
8
0
8
~
W
W
0
8
W
0
8
W
l
N
l
k
N
kl
N
W
W
W
=
)
1
(
k
N
W
d,
系数的计算采用递推运算：
23
其中,L,
控制蝶算的级数
J
,
控制每一级蝶算的类型数 I
,
控制每一种蝶形的个数及运算起始点 因各种类型计算的起点不 同，当计算第J种蝶算时,I应从J开始取第一点计算第一级初始化计算第一种蝶形同类蝶形完？ 所有蝶形完？
M级完
？
结束跳过L
E
点计算下一类型
J
=J+1
计算下一级
L=L+1
N
DO 10
I=J,N,LE
内层循环
DO 20 J=1,LE1
次层循环
DO 20
L=1,M
外层循环
Y
NN
整序
Y Y
24
§
3
按频率抽取
(DIF)
的
FFT
算法
γ
2
=
N
一、算法原理：
∑
∑
∑
=
=
=
+
=
=
1
2
1
2
0
1
0
)
(
)
(
)
(
)
(
N
N
n
nk
N
N
n
nk
N
N
n
nk
N
W
n
x
W
n
x
W
n
x
k
X
∑
∑
=
+
=
+
+
=
1
2
0
2
1
2
0
)
2
(
)
(
N
n
k
N
n
N
N
n
nk
N
W
N
n
x
W
n
x
)
2
(
N
n
m
=
令将
x(n)
按
n
的顺序分成前后两半
()
∑
=
+
+
=
1
2
0
)
2
(
1
)
(
N
n
nk
N
k
W
N
n
x
n
x
1
0
≤
≤
N
k
k
k
N
N
N
N
W
W
)
1
(
,
1
2
2
=
=
Q
1
2
0
≤
≤
N
r
1
2
2
+
=
=
r
k
r
k
及令
25
rn
N
N
n
rn
N
N
n
W
N
n
x
n
x
W
N
n
x
n
x
r
X
2
1
2
0
2
1
2
0
)
2
(
)
(
)
2
(
)
(
)
2
(
∑
∑
=
=
+
+
=
+
+
=
n
r
N
N
n
n
N
n
r
N
N
n
W
W
N
n
x
n
x
W
N
n
x
n
x
r
X
2
1
2
0
)
1
2
(
1
2
0
)
2
(
)
(
)
2
(
)
(
)
1
2
(
∑
∑
=
+
=
+
=
+
=
+
)
2
(
)
(
)
(
1
N
n
x
n
x
n
x
+
+
=
令
1
2
0
≤
≤
N
n
n
N
W
N
n
x
n
x
n
x
)]
2
(
)
(
[
)
(
2
+
=
)
2
(
)
(
1
r
X
r
X
=
则
1
2
0
≤
≤
N
r
)
1
2
(
)
(
2
+
=
r
X
r
X
26
)
(
n
x
n
N
W
n
N
W
N
n
x
n
x
)]
2
(
)
(
[
+
)
2
(
)
(
N
n
x
n
x
+
+
)
2
(
N
n
x
+
蝶形经顺序分解，将
N
点
DFT
按
k
的奇偶分成了两个新的序列的
N/2
点
DFT
。当
N=8
时，如下图示：
)
0
(
x
)
1
(
x
)
2
(
x
)
3
(
x
)
4
(
x
)
5
(
x
)
6
(
x
)
7
(
x
0
N
W
1
N
W
2
N
W
3
N
W
)
0
(
1
x
)
1
(
1
x
)
2
(
1
x
)
3
(
1
x
)
0
(
2
x
)
1
(
2
x
)
2
(
2
x
)
3
(
2
x
)
0
(
X
)
1
(
X
)
2
(
X
)
3
(
X
)
4
(
X
)
5
(
X
)
6
(
X
)
7
(
X
N/2点
DFT
N/2点
DFT
27
继续分解，可得
( ),N=8
时的
DIF
流图如下次分解经
γ
0
N
W
0
N
W
0
N
W
0
N
W
0
N
W
0
N
W
2
N
W
0
N
W
1
N
W
2
N
W
3
N
W
2
N
W
x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)
X(0) X(4) X(2) X(6) X(1) X(5) X(3) X(7)
28
二、特点：
1
、顺序输入，反序输出。
2
、与
DIT FFT
流图互为转置三、
IFFT
算法流图
∑
=
=
1
0
)
(
1
)
(
N
k
kn
N
W
k
X
N
n
x
据
IDFT
用代替
，并将计算结果乘
1/N(
一般分解
)
。
N
W
γ
)
2
(
1
W
1
N
则
DIT FFT
算法及
DIF FFT
算法均可直接用来运算
IDFT
。
如：利用
DIF FFT
流图计算
IFFT
，如下图示：
29
)
0
(
X
)
1
(
X
)
2
(
X
)
3
(
X
)
4
(
X
)
5
(
X
)
6
(
X
)
7
(
X
)
0
(
x
)
4
(
x
)
2
(
x
)
6
(
x
)
1
(
x
)
5
(
x
)
3
(
x
)
7
(
x
21 21 21 21
0
21
N
W
1
21
N
W
2
21
N
W
3
21
N
W
0
21
N
W
2
21
N
W
0
21
N
W
0
21
N
W
0
21
N
W
0
21
N
W
0
21
N
W
2
21
N
W
21
21 21
2121
21
21
21
相当于
DIT IFFT
。
时域被抽取
(
奇偶
)
DIT FFT
可用于计算
DIF IFFT
DIF FFT
可用于计算
DIT IFFT
30
§
4 N
为组合数的
FFT
算法互素）
、
如：
1
1
1
1
(
q
p
q
p
N
=
可将
x(n)
分解成
p
1
组，每组有
q
1
点组成，且每两点相距
p
1
点。即：每隔
p
1
点抽取一个数据。
5
3
15
×
=
=
N
如：
x(0) x(3) x(6) x(9) x(12) x(1) x(4) x(7) x(10) x(13) x(2) x(5) x(8) x(11) x(14)
]
[
[
)
0
(
x
)
1
(
x
)
1
(
1
p
x
……
通式：
[
]
1
1
1
)
1
(
)
2
(
p
q
x
p
x
L
L
[
]
1
)
1
(
)
1
2
(
1
1
1
+
+
p
q
x
p
x
L
L
[
]
1
)
1
(
)
1
2
(
1
1
1
1
1
+
+
p
p
q
x
p
p
x
L
L
……
)
(
1
p
x
)
1
(
1
+
p
x
)
1
(
1
1
+
p
p
x
则
x(n)
的
N
点
DFT
为：
31
∑
∑
∑
=
=
=
+
+
+
=
1
0
1
0
1
0
)
(
)
(
)
(
)
(
N
n
nk
N
N
n
nk
N
N
n
kn
N
W
n
x
W
n
x
W
n
x
k
X
L
1
)
1
(
1
1
1
+
=
p
r
p
n
p
n
组取
1
1
1
+
=
r
p
nn
组取
r
p
nn
1
0
=
组取
1
0
1
≤
≤
q
r
∑
∑
∑
=
+
=
+
=
+
+
+
+
+
=
1
)
1
(
1
1
1
0
)
1
(
1
1
0
1
1
1
1
1
1
1
1
)
1
(
)
1
(
)
(
q
o
r
p
r
p
k
N
q
r
r
p
k
N
q
r
r
kp
N
W
p
r
p
x
W
r
p
x
W
r
p
x
L
∑
∑
∑
=
=
=
+
+
+
+
+
=
1
1
1
)
1
(
1
0
1
1
0
1
1
1
1
1
1
1
1
)
1
(
)
1
(
)
(
q
o
r
kr
q
p
k
N
q
r
kr
q
k
N
q
r
kr
q
W
p
r
p
x
W
W
r
p
x
W
W
r
p
x
L
∑
∑
∑
=
=
=
+
+
+
=
1
1
)
1
(
1
0
1
1
0
0
1
1
1
1
1
1
1
1
)
(
)
(
)
(
q
o
r
kr
q
p
p
k
N
q
r
kr
q
k
N
q
r
kr
q
W
r
x
W
W
r
x
W
W
r
x
L
)
(
)
(
)
(
1
)
1
(
1
0
0
1
1
k
X
W
k
X
W
k
X
W
p
p
k
N
k
N
N
+
+
+
=
L
1
,
3
,
2
,
1
,
0
=
N
k
L
32
这就是混合基
(
基
p
1
+
基
q
1
) FFT
算法的递推公式。
运算量分析：
1
1)
-
(
1
1
1
1
2
1
1
1
1
=
=
)
N(q
q
q
p
q
p
C
DFT
q
p
N
复数加法：复数乘法直接运算，需点个次复加也为次复乘为个不计第一项次每个
)
1
(
)
1
(
,
)
,
1
(
1
,
1
1
0
1
=
p
N
p
N
k
N
W
p
k
N
而分解后
)
1
(
)
1
(
:
1
1
1
2
1
1
+
=
+
∴
p
N
Nq
p
N
q
p
共需复数乘法为
)
(
1
1
q
p
N
=
2
1
1
)
1
(
N
q
p
N
<
+
=
)
2
(
)
1
(
)
1
(
1
1
1
1
+
=
+
q
p
N
p
N
q
N
复数加法：
1
1
1
1
)
1
(
q
p
q
p
<
+
一般
Q
33
分解后运算量为点则可继续分解，如：
若
DFT
q
q
p
q
q
1
2
2
1
1
,
=
+
+
)
2
(
)
1
(
2
2
1
2
2
1
q
p
q
q
p
q
复加：复乘：
)
2
(
)
1
(
)
1
(
2
2
1
2
2
1
1
1
+
+
=
+
+
∴
q
p
p
N
q
p
q
p
p
N
复乘：
总运算量为：
)
3
(
)
2
(
)
1
(
2
2
1
2
2
1
1
1
+
+
=
+
+
q
p
p
N
q
p
q
p
p
N
复加：
则有一般地，若
,
2
1
m
m
q
p
p
p
N
=
L
)
1
(
)
(
2
1
2
1
+
+
+
+
+
+
+
+
m
q
p
p
p
N
m
q
p
p
p
N
m
m
m
m
LL
复加：复乘：
34
例：画出
N=6
点的
FFT
信号流图
3
2
6
×
=
=
N
点序列。
分解成两个将
3
)
(
n
x
)
2
(
x
)
3
(
x
)
4
(
x
)
5
(
x
]
[
=
)
(
0
r
x
[
)
(
1
r
x
]
)
0
(
x
)
1
(
x
∑
∑
=
+
=
+
+
=
∴
2
0
)
1
2
(
6
2
0
2
6
)
1
2
(
)
2
(
)
(
r
k
r
r
rk
W
r
x
W
r
x
k
X
∑
∑
=
=
+
+
=
2
0
3
6
2
0
3
)
1
2
(
)
2
(
r
rk
k
r
rk
W
r
x
W
W
r
x
5
0
≤
≤
k
)
(
)
(
1
6
0
k
X
W
k
X
k
+
=
35
∑
=
=
2
0
3
0
0
)
(
)
(
r
rk
W
r
x
k
X
其中：
∑
=
=
2
0
3
1
1
)
(
)
(
r
rk
W
r
x
k
X
k
k
W
x
W
x
x
k
X
2
3
0
3
0
0
0
)
2
(
)
1
(
)
0
(
)
(
+
+
=
即：
3
点
DFT
k
k
W
x
W
x
x
2
3
3
)
4
(
)
2
(
)
0
(
+
+
=
2
0
≤
≤
k
)
4
(
)
2
(
)
0
(
)
0
(
0
x
x
x
X
+
+
=
2
3
1
3
0
)
4
(
)
2
(
)
0
(
)
1
(
W
x
W
x
x
X
+
+
=
4
3
2
3
0
)
4
(
)
2
(
)
0
(
)
2
(
W
x
W
x
x
X
+
+
=
同理：
)
5
(
)
3
(
)
1
(
)
0
(
1
x
x
x
X
+
+
=
2
3
1
3
1
)
5
(
)
3
(
)
1
(
)
1
(
W
x
W
x
x
X
+
+
=
4
3
2
3
1
)
5
(
)
3
(
)
1
(
)
2
(
W
x
W
x
x
X
+
+
=
36
具体流图如下：
展开将
)
(
),
(
1
0
k
X
k
X
)
0
(
0
X
)
1
(
0
X
)
2
(
0
X
)
0
(
1
X
)
1
(
1
X
)
2
(
1
X
0
6
W
1
6
W
2
6
W
3
6
W
4
6
W
5
6
W
0
3
W
1
3
W
2
3
W
2
3
W
4
3
W
0
3
W
x(0) x(2) x(4) x(1)
x(3)
x(5)
X(0)
X(1) X(2) X(3) X(4)
X(5)
37
§
5、线性调频z变换
(Chirp z Transform)
一、问题的提出基
-2 FFT
算法是研究在
Z
平面单位圆上等间隔取样点
Z
k
处的取样值
X(z
k
)
的快速算法，要求
N
为高度复合的数。
实际上有时对其它围线上的
Z
变换发生兴趣，或能有效地计算当
N
是素数时序列的
DFT
CZT
就是适用于这种更为一般情况下由
x(n)
求
X (z
k
)
的快速变换
38
二、算法原理
)
(
n
x
1
0
≤
≤
N
n
∑
=
=
1
0
)
(
)
(
N
n
n
z
n
x
z
X
令
)
(
1
,
,
1
,
0
,
N
M
M
k
AW
z
k
k
≠
=
=
L
0
0
0
0
,
Φ
=
=
j
j
e
W
W
e
A
A
W
A
θ
均为任意复数，其中
、
0
0
0
0
)
(
Φ
=
∴
jk
k
j
k
e
W
e
A
z
θ
L
L
）
（
0
0
1
0
0
1
Φ
+
=
θ
j
e
W
A
z
0
0
0
θ
j
e
A
z
=
即
）
）
（
（
0
0
1
-
)
1
(
0
0
1
Φ
+
=
M
j
M
M
e
W
A
z
θ
39
1
,
)
1
(
0
0
0
≤
A
Z
A
的矢量半径，一般起始点的相位（可正可负）
0
0
,
)
2
(
Z
θ
顺时针转逆时针转，
，
间的相位差相邻
k
k
k
Z
Z
Z
,
0
0
,
)
3
(
0
0
0
<
Φ
>
Φ
Φ
的一段圆弧半径为向内弯曲向外弯曲控制围线盘旋方向
0
0
0
0
0
0
0
,
1
,
,
1
,
,
1
)
4
(
A
W
W
K
W
W
K
W
W
KK
=
↓
↑
>
↑
↑
<
取样围线如图所示
0
Φ
0
Φ
1
M
Z
1
Z
0
Z
0
θ
0
A
1
0
0
W
A
)
Re(
Z
)
Im(
Z
j
DFT
n
x
N
W
A
N
M
的即为若满足
)
(
2
,
1
,
0
,
1
,
)
5
(
0
0
0
0
π
θ
=
Φ
=
=
=
=
40
计算表示：
∑
=
=
1
0
)
(
)
(
N
n
nk
n
k
W
A
n
x
z
X
[]
2
2
2
)
(
21
n
k
k
n
nk
+
=
Q
∑
=
=
∴
1
0
2
2
)
(
2
2
2
2
)
(
)
(
N
n
k
n
k
n
n
k
W
W
W
A
n
x
z
X
∑
=
=
1
0
2
)
(
2
2
2
2
2
]
)
(
[
N
n
n
k
n
n
k
W
W
A
n
x
W
2
2
)
(
)
(
n
n
W
A
n
x
n
f
=
令
2
2
)
(
n
W
n
h
=
1
0
≤
≤
N
n
∑
=
=
1
0
2
)
(
)
(
)
(
2
N
n
k
k
n
k
h
n
f
W
z
X
则
)
(
)
(
2
2
k
h
k
f
W
k
=
1
0
≤
≤
M
k
41
运算流程
)
(
k
g
)
(
n
h
)
(
n
f
)
(
n
x
)
(
k
Z
X
1
,
2
,
1
,
0
=
N
n
L
1
,
2
,
1
,
0
=
M
k
L
2
2
n
n
W
A
2
2
k
W
三、
CZF
实现步骤：
相乘再与求由求
)
(
,
,
,
,
,
),
(
).
1
(
2
0
0
0
0
2
n
x
W
A
W
A
n
f
n
n
Φ
θ
)
(
)
(
,
,
2
0
0
2
0
0
n
x
W
A
n
f
e
W
W
e
A
A
n
n
j
j
Φ
=
=
=
θ
1
0
≤
≤
N
n
DFT
n
f
FFT
L
N
M
L
L
m
的求并利用且使选取最小
)
(
,
2
1
,
).
2
(
=
+
>
∑
=
=
1 0
2
)
(
)
(
L n
rn
L
j
e
n
f
r
F
π
1
0
≤
≤
L
r
42
如下选取
2
2
)
(
).
3
(
n
W
n
h
=
点取
M
k
g
)
(
Q
≤
≤
≤
≤
+
≤
≤
=
N
L
n
M
L
n
N
L
W
M
n
W
n
h
n
L
n
任意
，
1
1
,
1
0
,
)
(
2
)
(
2
2
2
个结果线性卷积前与等于个点圆周卷积的前与如此取
M
n
h
n
f
M
n
h
n
f
)
(
)
(
,
)
(
)
(
)]]
(
[
)]
(
[
[
)
(
,
),
(
)
1
(
),
(
)
(
).
4
(
n
h
FFT
n
f
FFT
IFFT
k
g
M
k
g
N
M
n
h
n
f
=
+
≥
个值取前求列长作
1
0
,
)
(
)
(
).
5
(
2
2
≤
≤
=
M
k
W
k
g
z
X
k
k
求四、运算量
)
,
(
),
(
)
(
).
1
(
2
2
2
2
可先计算好次复乘
。
需形成
n
n
n
n
W
A
N
n
x
W
A
n
f
=
次复乘各需求
L
L
r
H
r
F
2
log
2
)
(
),
(
).
2
(
次复乘需作
L
r
H
r
F
)
(
)
(
)
3
(
43
L
L
r
H
r
F
FFT
k
g
2
1
log
2
)],
(
)
(
[
)
(
).
4
(
又需求
=
次复乘需输出点形成
M
W
k
g
Z
X
M
k
k
,
)
(
)
(
).
5
(
2
2
=
M
L
N
L
L
+
+
+
=
∴
2
log
23
总的复乘数次复乘需时点而直接计算
N
M
Z
X
M
k
,
)
(
要小很多。
算法比直接算法运算量后，
量较小，但当较小时，直接计算运算在 CZT
N
M
N
M
50
>
44
算法特点五、
CZT
率也是任意的
。
是任意的，即频率分辨的角间隔者均可为素数不必是高度合成数，二与入与出列长可不等可不等，
与
0
).
3
(
).
2
(
)
(
).
1
(
Φ
k
Z
M
N
M
N
为素数时也可以。
，即使来计算
，则可用
，
，
若率的分析数据进行窄带的高分辨任意频率上开始对输入可任意选定，因此可从起始点些特点。
析中螺旋形周线具有某平面上的圆，在语音分周线不必是
N
DFT
CZT
e
W
N
M
A
z
Z
N
j
π
2
0
1
).
6
(
).
5
(
).
4
(
=
=
=
.
DFT
CZT
个一般化的
，在某种意义上它是一算法具有很大的灵活性总之，
45
§
6 FFT
的应用一、计算卷积和相关
、计算卷积
1
)
(
)
(
)
(
)
(
)
(
1
0
n
h
n
x
k
n
h
k
x
n
y
N k
=
=
∑
=
)
(
n
x
)
(
n
h
)
(
n
y
2
1
)
(
,
)
(
N
n
h
N
n
x
→
列长设
N
n
h
n
x
N
N
N
N
补零到将且选择
)
(
),
(
2
1
).
1
(
2
1
γ
=
+
≥
)]
(
[
)
(
)],
(
[
)
(
)
(
),
(
).
2
(
n
h
FFT
k
H
n
x
FFT
k
X
k
H
k
X
=
=
计算
)
(
)
(
)
(
).
3
(
k
H
k
X
k
Y
=
求
)
(
).
4
(
k
Y
求
[
]
{}
则运算效率很高。
较大若次调用求
,
,
3
)
(
1
)
(
).
5
(
N
k
Y
FFT
N
n
y
=
46
、计算相关
2
∑
=
+
=
1
0
2
1
3
)
(
))
((
)
(
)
(
N
k
N
N
n
R
k
n
x
k
x
n
x
离散相关：
∑
=
+
=
1
0
2
1
3
)
(
)
(
)
(
N
k
k
n
x
k
x
n
x
线性相关
：
)
(
)
(
)
(
2
1
3
k
X
k
X
k
X
=
相关定理：
γ
2
,
1
).
1
(
2
1
=
+
≥
N
N
N
N
补零过程：
)]
(
[
)
(
)],
(
[
)
(
)
(
),
(
).
2
(
2
2
1
1
2
1
n
x
FFT
k
X
n
x
FFT
k
X
k
X
k
X
=
=
计算
)
(
)
(
)
(
).
4
(
2
1
3
k
X
k
X
k
X
=
求
)
(
).
3
(
1
k
X
求
[
]
{
}
=
=
)
(
1
)]
(
[
)
(
).
5
(
3
3
3
k
X
FFT
N
k
X
IFFT
n
x
求
47
DFT
N
FFT
N
点实序列同时运算两个点二、一个的实序列均为列长为设
N
n
x
n
x
)
(
),
(
2
1
)
(
)
(
)
(
2
1
n
jx
n
x
n
x
+
=
则，可令
)]
(
)
(
[
)]
(
[
)
(
2
1
n
jx
n
x
FFT
n
x
DFT
k
X
+
=
=
而
)
(
)
(
2
1
k
jX
k
X
+
=
呢？
和表示如何用
)
(
)
(
)
(
2
1
k
X
k
X
k
X
[]
[
]
)
(
)
(
21
)
(
)
(
2
n
x
n
x
n
x
jI
n
jx
m
=
=
)]
(
)
(
[
21
)]
(
Re[
)
(
1
n
x
n
x
n
x
n
x
+
=
=
Q
)
(
)]]
(
[Re[
k
X
n
x
DFT
ep
=
而
)
)
(
(
的周期性共轭对称分量
k
X
)]
(
))
((
)
(
[
21
)
(
)
(
1
k
R
k
X
k
X
k
X
k
X
N
N
ep
+
=
=
∴
)]
(
)
(
[
21
k
N
X
k
X
+
=
1
0
≤
≤
N
k
48
)]]
(
[
[
1
)]
(
[
)
(
2
2
n
x
jI
DFT
j
n
x
DFT
k
X
m
=
=
同理：
)]
(
))
((
)
(
[
21
)
(
1
k
R
k
X
k
X
j
k
X
j
N
N
op
=
=
)]
(
)
(
[
21
k
N
X
k
X
j
=
1
0
≤
≤
N
k
)
(
)
(
)
(
1
2
1
n
jx
n
x
n
x
+
=
>
<
构成复序列，
步骤：
1
0
≤
≤
N
n
)]
(
[
)
(
2
n
x
FFT
k
X
=
>
<
计算
)
0
(
)
(
3
X
N
X
=
>
<
令
1
0
),
(
4
≤
≤
>
<
N
k
k
N
X
求
)]
(
)
(
[
21
)
(
5
1
k
N
X
k
X
k
X
+
=
>
<
求
)]
(
)
(
[
21
)
(
2
k
N
X
k
X
j
k
X
=
49
DFT
N
FFT
N
点实序列同时运算一个点三、一个
2
N
n
x
2
)
(
实序列，列长为点实序列变成两个利用奇偶抽取
，将
N
n
x
)
(
)
2
(
)
(
1
n
x
n
x
=
即：令
)
1
2
(
)
(
2
+
=
n
x
n
x
1
0
≤
≤
N
n
构成一个复序列然后将
)
(
),
(
2
1
n
x
n
x
)
(
)
(
)
(
2
1
n
jx
n
x
n
y
+
=
：
、
、
求
)
(
)
(
)
(
2
1
k
X
k
X
k
Y
)]
(
[
)
(
n
y
FFT
k
Y
=
)]
(
)
(
[
21
)
(
1
k
N
Y
k
Y
k
X
+
=
)]
(
)
(
[
2
)
(
2
k
N
Y
k
Y
j
k
X
=
50
而由奇偶抽取原理：
)
(
)
(
)
(
2
2
1
k
X
W
k
X
k
X
k
N
+
=
1
0
≤
≤
N
k
)
(
)
(
)
(
2
2
1
k
X
W
k
X
k
N
X
k
N
=
+
)
1
2
(
)
(
),
2
(
)
(
)
(
1
2
1
+
=
=
>
<
n
x
n
x
n
x
n
x
n
x
进行奇偶抽取，得将具体步骤
：
)
(
)
(
)
(
,
2
2
1
n
jx
n
x
n
y
+
=
>
<
构成复序列
)
(
)
(
)
(
3
2
1
k
X
k
X
k
Y
及及求
>
<
1
0
),
(
)
(
)
(
4
2
2
1
≤
≤
+
=
>
<
N
k
k
X
W
k
X
k
X
k
N
求
1
0
),
(
)
(
)
(
5
2
2
1
≤
≤
=
+
>
<
N
k
k
X
W
k
X
N
k
X
k
N
求
51
作业：
1
、画出
9
点
FFT
算法流图，并分析其运算量。
2
、编写基
-2 DIT FFT
子程序，并用其计算以下两序列的线性卷积，打印输出结果。
)
(
),
(
2
1
n
x
n
x
1
123
4
0
