之 之 之 十 之 十 令型回
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
之 +e 尔图的 己"e z
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 Wn x k X k k n nk ⋅ + = ⋅ + = =∑ = 1 0 ≤ ≤ k − = ⋅ + = + = ⋅ + = ∴ ) 4( ) 0( )4( ) 0( )1( ) 4( )0( ) 4( ) 0( )0( 0 12 3 0 02 3 x W x x W x X x W x x W x X NN
之 十 2 兴 × z同兴媳
13 同理可求 − = + = ) 6( ) 2( ) 1( ) 6( ) 2( ) 0( 0 4 0 4 x W x X x W x X NN − = + = ) 5( ) 1( ) 1( ) 5( ) 1( ) 0( 0 5 0 5 x W x X x W x X NN − = + = ) 7( ) 3( ) 1( ) 7( ) 3( ) 0( 0 6 0 6 x W x X x W x X NN 综合起来，可得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 二、运算量分析 次分解 经 N2 log = γ γ2 = N 每级共有N/2个蝶形，而每个蝶形有一次复乘和两次复加。 = ⋅ ⋅ = ⋅ N N N N N N 2 2 log 2 2 log 2 2 γ γ 复乘： 复加： 级运算量为 γ ∴ 即DIT FFT运算量与 成正比 ，而直接计算DFT与 N2 成正比。 N N 2 log 186 log 2 2 ≈ N N N 如：N=2048，则