i0
相xi (邻n)两长段度输为出p点序，列而有y（i (nM)长度1）为点p重 m叠。1点，
重叠保留法
（每1）段先长将度x为(n)N分点成，几M个为短短序序列列x的i (n长)，度；
这样分段后，应在每一段的前边
再补上前一段保留下来的(M 1)个输入序列值，
组成L点短序列L N M 1，准备进行圆卷积。
N
N 1
与X (k ) x(n)WNnk比较
n0
可知：只须将频域成份一个求共轭变换，即（1）将X(k)的虚部乘 以-1，即先取X(k)的共轭，得X*(k)。(2)将X*(k)直接送入FFT程序 即可得出Nx*(n)。(3)最后再对运算结果取一次共轭变换，并乘以 常数1/N，即可以求出IFFT变换的x(n)的值。
按时间抽取法解过程的规律。
1.原位运算（in-place)
2.码位倒读规则，乱序输入，顺序输出
（1）“级”概念 将N 点DFT先分成两个N/2点DFT，再是四个N/4点
DFT…直至N/2个两点DFT.每分一次称为“一”级 运算。 因为N=2M所以N点DFT可分成M级 依次m=0,m=1….M-1共M级
0
0n M n
M 1 L 1
计算L点DFT X ((32))计相算乘L：点YIi F(kF)T
i (k) DFT[xi (n)], H (k) H (k)X i (k)
yi (n) IFFT[Yi (k)]
DFT [h(n)]
(4)将各段yi (n)重叠部分相加起来：y(n) yi (n)
其zk 中 A00：0为k e螺j(0线k的0 ) 伸展率。
它的大小控制着围线盘旋是向内弯曲还是向外弯曲
0 0
1: 随着k的增加，围线（螺线）盘旋向外弯曲 1: 随着k的增加，
围线（螺线）盘旋向内弯曲（向原点盘旋）
若0A0 1：1，表这示段半园径弧A0的则一是段单园位弧园，上的一部分。
6、说明3
3.用CZT求解DFT的流图
x(n)
g(n)
n2 G(k)
X (zk )
h(n) W 2
n2
k2
An 2
2
6、说明1
（1）A为起始样点位置
通AA00：：常为A为A00e起起j始0始1，, 样样表点点示相半在角径园（，内可正可负，为角频率）
6、说明2
（2）zk是z平面一段螺线上的等分角上某一 采样点。
一个完整N=8的按DIF频率抽
取FFT的运算)
x(1) x(2)
X(4)
W80
W80
X(2)
x(3)
W82
x(4)
W80
x(5)
W81
x(6)
W82
W80
x(7)
W83
W82
其中旋转因子，共有WN0 WNN / 21
W80
W80
X(6) X(1) X(5)
X(3)
W80 X(7)
2.直接利用FFT流图方法的推
导
x(n)
1 N
N 1
X (k )WNnk
k 0
对它取共轭：x＊(n)
1 N
N 1
X
*
(k
)W
nk N
k 0
x(n)
1 N
N 1
[
k 0
X
*
(k )WNnk
]*
(取共轭再取共轭）
1 {DFT [ X * (k )]}*
此为DFT可用FFT程序
（它(3即)可z00以：~是表z1正示, z值1两~或相z负2邻,值zk)之。间角频率差。
当 当
00为为正负时时，，表表示示zz
的路径是顺时针旋转。 k的路径是逆时针旋转。
k
6、说明4
(4)当满足下面特殊条件：
（a) : M N
(b) A A0e j0 1,即A0 1 0 0
2
(c)
0e j0
（2）“组”概念
每一级都有N/2个蝶形单元，例如：N=8,则每级
都有4个蝶形单元。每一级的N/2个蝶形单元可以分 成若干组，每一组具有相同的结构，相同的 WNr 因子 分布，第m级的组数为：
N 2 m 1
例：N=8=23，分3级。
m=0级,分成四组,每组系数为
W0 N /4
W20
W80
m=1级,分成二组,每组系数为 WN0/2 ,WN1 /2 WN0 ,WN2 W80 ,W82 m=2级,分成一组,每组系数为 WN0 ,WN1 ,WN2 ,WN3 W80 ,W81,W82 ,W83
(3) WNr 因子的分布
由上可知：
m 0级，W2k k 0 W20 W80 m 1级，W4k k 0，1 W40，W41 W80，W82 m 2级，W8k k 0，1,2,3 W80，W81,W82，W83 看出：第m级的系数为W2km1 , k 0,12m 1
结论：每由后向前（m由M-1-->0级）推进一 级，则此系数为后级系数中偶数序号的那一半。
第四章 快速傅立叶变换(FFT)
一、直接用DFT计算的运算量与用FFT计算的运 算量比较，减少运算量的途径
直接用DFT 计算的运算量：
复乘N 2次，复加N（N 1）次。
用FFT 计算的运算量：
复乘
N 2
log 2
N次, 复加N
log 2
N次。
减少运算量的途径：
（1）合并法
（2）分解法
二、FFT算法中一些概念
例M=50，N=50，N*M=2500次
而CZT<1600次。
重叠相加法
（1）x(n)为分段，每段长为p点，p选择与
M数量组相同。用xi(n)表示x(n)的第i段.
（1）计算L点DFT
x(n) ip n (i 1) p 1
xi (n)
0
(i 1) p n L 1
h(n)
h(n)
而对第一段，由于没有前一段保留信号，
则需要在它前边填充M 1个零值点。
j
e N
,
即 0
1。 0
2
M
2（N等分）时，
N
即此由时CzkZ为T变 均换匀求 分出布该 在序单列 位D园F上T。，
10、CZT运算量与直接运算量比较
CZT 共需复乘次数为：
5N
3 2
L
log2
L
L
M
直接计算X (zk )需要 NM 次复数乘法
当M、N足够小时，直接算法运算量少。
但M、N值比较大时（大于50），CZT算法比 直接算法的运算量少得多。
三、一个完整N=8的按DIT时间抽取FFT的 运算流图
m=0 x(0)
m=1
m=2
x(4)
x(2) W80
W80
x(6)
x(1) W80
W82
W80
x(5)
W81
x(3) W80
W80
W82
x(7)
W其80 中旋转因W子82 ，共有WN0
W83 WNN / 21
X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7)