第4意快速傅里叶夜换(H 1024 直接计算 512 米256 FFT算法 128 64 64128256 512 1024 N(取样点数) 图42.5FFT算法与直接计算DFT所需乘法次数的比较曲线
第4章 快速傅里叶变换(FFT) 图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线
第4意快速傅里叶夜换(H 42.4DIT—FFT的运算规律及编程思想 1原位计算 由图424可以看出, DIT-FFT的运算过程很有规 律。N=2M点的FFT共进行M级运算,每级由N/2个蝶 形运算组成 2.旋转因子的变化规律 如上所述,N点DIT—FFT运算流图中,每级都有 N2个蝶形。每个蝶形都要乘以因子WN,称其为旋转 因子,p称为旋转因子的指数
第4章 快速傅里叶变换(FFT) 4.2.4 DIT―FFT的运算规律及编程思想 1.原位计算 由图4.2.4可以看出，DIT―FFT的运算过程很有规 律。N=2M点的FFT共进行M级运算，每级由N/2个蝶 形运算组成。 2.旋转因子的变化规律 如上所述，N点DIT―FFT运算流图中，每级都有 N/2个蝶形。每个蝶形都要乘以因子Wp N，称其为旋转 因子，p称为旋转因子的指数
第4章快速傅里叶夜换(FEE) 观察图424不难发现,第L级共有2L1个不同的旋 转因子。N=23=8时的各级旋转因子表示如下: L=1时,W=WM4W2L,J=0 L=2Hf, WN=WN2=W2L,J=0,1 L=3时,W=W=W 对N=2M的一般情况,第L级的旋转因子为 WR=W2L2J=0,1,2,…,22-1 2=2×2 L-M N·2 WN=W,M=WN,J=0,,2…,2 1(42.12) 2 M-L (4.2.13)
第4章 快速傅里叶变换(FFT) 观察图4.2.4不难发现，第L级共有2 L-1个不同的旋 转因子。N=2 3=8时的各级旋转因子表示如下： L=1时，Wp N=WJ N/4=WJ 2L， J=0 L=2时， Wp N =WJ N/2=WJ 2L， J=0，1 L=3时， Wp N =WJ N=WJ 2L， J=0，1，2，3 对N=2 M的一般情况，第L级的旋转因子为 1 2 2 1 2 , 0,1,2, ,2 1 2 2 2 2 , 0,1,2, ,2 1 2 M L L M p J L N L M L M L M P J J L N N N M L W W L J N W W W J p J − − − − − − − = = − = = = = = − = (4.2.12) (4.2.13)
第4意快速傅里叶夜换(H 3.蝶形运算规律 设序列x(n)经时域抽选(倒序)后,存入数组X中。 如果蝶形运算的两个输入数据相距B个点,应用原位计 算,则蝶形运算可表示成如下形式: XO XL-1(+XL+B)WPN XI+B)E XLI)-XLI+B)WPN 式中p-J.2M;J=0,1,…,2L-1-1;L=1,2,M
第4章 快速傅里叶变换(FFT) 3. 蝶形运算规律 设序列x(n)经时域抽选(倒序)后，存入数组X中。 如果蝶形运算的两个输入数据相距B个点，应用原位计 算，则蝶形运算可表示成如下形式： X (J) XL-1(J)+X L-1 (J+B)Wp N XL (J+B) XL-1 (J)-X L-1 (J+B)Wp N 式中 p=J·2 M-L；J=0,1,…，2 L-1-1；L=1,2,…，M
第4章快速傅里叶夜换(FEE) 下标L表示第L级运算,X(J)则表示第L级运算后 数组元素X(J)的值。如果要用实数运算完成上述蝶形 运算,可按下面的算法进行。 设 T=XL+BWPNFTR+JTI ⅹL1(J)=Xg(J)+jxJ 式中下标R表示取实部,I表示取虚部, 2丌 2丌 REXRO+ B)COSp+XRO+ B)sin p T=X(+ B)cosp+XR(+B),sin2t 2丌
第4章 快速傅里叶变换(FFT) 下标L表示第L级运算，XL (J)则表示第L级运算后 数组元素X(J)的值。如果要用实数运算完成上述蝶形 运算，可按下面的算法进行。 设 T=X L-1 (J+B)Wp N=TR+jTI X L-1 (J)=X′ R(J)+jX′ I (J) 式中下标R表示取实部，I表示取虚部， 2 2 ( )cos ( ) sin 2 2 ( )cos ( ) sin R R R I I I R I T X J B p X J B p N N T X J B p X J B p N N = + + + = + + +