第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法) 运算量比较 lDIT-FFT: N=2V 由图46可见,N-DF→ν级分解/蝶形运算 每一级:均有蝶形运算x 2 +—N 所有v级:×-2xy=092~Nbg +-Nxv=bog2」 2. DET N CN +N(X-1)
二、运算量比较 1.DIT-FFT：N=2ν N − DFT → 级分解/蝶形运算 每一级：均有 蝶形运算 2 N N N 2 — — + N N N N N N 2 2 2 ~ log log log 2 + = = — 所有 级： — 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 由图4-6可见， 2. DFT 2 2 ~ ( 1) N N N N + − — —
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法 3D|TFFT的运算效率 N Ngx=→表4-1P31图4-7 三、DT-FFT算法的特点 1.原位运算( n-place) An(1)=n1()+WAn1(门) An=1() Am()=Am_(G)+WNAm-c m一第m列迭代 一数据所在的行数
3. DIT-FFT的运算效率 4 1 P.131 4 - 7 log 2 log 2 2 N = N N → 表 − 图 N N 三、DIT-FFT算法的特点 1. 原位运算(In-place) ( ) 1 A i m− ( ) 1 A j m− ( ) ( ) ( ) 1 1 A i A i W A j m k m = m− + N − ( ) ( ) ( ) 1 1 A j A i W A j m k m = m− + N − k WN —数据所在的行数 —第 列迭代 i j m m , 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法 2W的变化规律 m=v, Am(D=X(O m=1,An1(i)=x(1) W:W,k=0, N 2 +1 V-n m级 W(2,k=01,,20my)-1 3.输入序列的序号及整序规律 由图4-5可见, 输入x(n):乱序的如何做到?整序 输出X(k):顺序的
2.WN k 的变化规律 1 ( ) ( ) ( ) ( ) 1 m A i x i m A i X i m m = = = = ， − ， WN k ： m级 m =, −1,...,1 0,1,...,2 1 (2 ) ( 1) = − − − k m N W k m ， 3. 输入序列的序号及整序规律 由图4-5可见， 输入x(n)：乱序的 如何做到？ 整序 输出X(k)：顺序的 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 1 2 , 0,1,..., 1 2 = − − + − m k N N W k m
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法 (1)乱序的原因 r(n 例:N=8 1n1n2 0x(00(0 x(000 x(100=x(2) x(001 0+x(010)=x(4) x(010) x(n,n,no x(10)=x(6)正好为 x(011) DIT-FFT /00001)=x)的输入 x(100 L→x(01)=x(3) x(101) 0+x(011)=x(5) x(110 x(11)=x(7) x(11) 比较 正序x(121)→x(mnn2 反序
(1) 乱序的原因 (111) (7) (011) (5) (101) (3) (001) (1) (110) (6) (010) (4) (100) (2) (000) (0) x x x x x x x x x x x x x x x x = = = = = = = = ( ) n2 n1 n0 x 正好为 DIT-FFT 的输入 (111) (110) (101) (100) (011) (010) (001) (000) x x x x x x x x x(n) 比较 ( ) ( ) 2 1 0 n0 n1 n2 x n n n → x 正序 反序 例：N=8 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 n 1 n 2 n 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法) (2)整序的规律 令n=n2n1n0 n=nonn l)n=n,数据不调换 2)n≠n&n>n x x(n) 即序号为n和的数据x(n)和x(n)互换 四、D|T-FFT算法的若干变体 [详见P134-135:图4-11~图414
(2) 整序的规律 0 1 2 2 1 0 ˆ n n n n n n n n = 令 = 1) n = n ˆ，数据不调换 2) n n ˆ & n ˆ n x(n) x(n ˆ) 即序号为n和n ˆ的数据x(n)和x(n ˆ)互换 四、DIT-FFT算法的若干变体 [详见P.134-135:图4-11~图4-14] 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)