快速傅里叶变换算法及其在信号处理中的应用毕业论文(编辑修改稿)

快速傅里叶变换算法及其在信号处理中的应用毕业论文(编辑修改稿)内容摘要：

)rr r rkx n k k x k k k   121 2 0 0( 2 2 )rrrrn n n kW   = 1 0 1 2 1 2 0 1 0 1 2 1 2 0( 0 ) ( 0 ) Pl r r r l r r rx n n n k k k x n n n k k k W        （ 38） 式中 1 2 11 2 02 2 2r r rllP n n n      （ 39） 根据式（ 38），第 L 个数组中每个 1 2 0 1 2 0( ) ( )l l r r r rx k x n n n k k k    的计算只依赖于上一个数组的两个数据这两个数 据的标号相差 12 / 2YlN  ，即/2lj i n ，而且这两个数据只用于计算第 L个数组中标号的数据（等号右端为二进制数）。 当 1ln 分别取０和１时，分别有 , / 2 lk i k j i n   。 因此，用上一组的两个数据计算所得的两个新数据仍可储存在原来位置，计算过程中只需要 N个存储器。 将 ()lxi与 ( /2 )llx i n 称为第 L个数组中的对偶结点对。 计算每个对偶结点对只需一次乘法，事实上由式（ 38）可得 11( ) ( ) [ ]2 pll lNx i x i i W   211( ) ( ) [ ]22 pl l lllNNx i x i x i W    （ 310） 式中： lrlr nP   2...2 221 0n ； 0222 2...22 nnP lrlrlr   别为式（ 39）中 1ln 取０，１时对应的 P值。 因 2/2 1112 NPPP R   ，于是对偶结点的 pW 有如下关系： 1112 22 ][ PNPNNPP WeWW   ,因此式（ 38）可表示为 1111( ) ( ) [ ]2( ) ( ) [ ]22pl l l lpl l lllNx i x i x i WNNx i x i x i W      （ 311） 武汉工程大学毕业设计 (论文 )说明书 8 P 的求法：在 )(ixl中， i 写成二进制数 kknnnlrl 01110  右移 lr 位，就成为 nnn l 11000  颠倒位序得 )2,1(00011 rlp nnn l    式（ 37）中，前面的 r 个等式，每个等式均对应一组数据进行计算，每组数据都有 N/２对结点，根据式（ 311），每对结点只需作１次乘法和２次加法，因此，每组数据只需 N/2次乘法和 N次加法，因而完成 r组数据的计算共需 Nr/2 次乘法和 Nr 次加法。 3. 2 CooleyTukey FFT 算法 FFT 的核心是将一层运算映射为二层运算。 作 N 点 FFT 时，若 N 不是素数，则 N 可分解为 12N NN ，那么由 []fn的 DFT 10[ ] [ ] 0 1N nkNnF k f n W k N    （ 312） 通过映射： 2 1 2 1 1 2 21 1 2 1 1 2 20 1 , 0 10 1 , 0 1n N n n n N n Nk k N k k N k N               （ 313） 可得到 2 1 2 1 1 2 2 1 1 1 2 1 2 2 1 1 2 2( ) ( ) ( )N n n k N k N n k N N n k n k N n knkN N NW W W     而 12N NN ， 12NNNWW， 21NNNWW，可化简为 1 1 2 1 2 212n k n k n knkN N N NW W W W （ 314） 从而式（ 312）转化为 212 2 2 1 1 121111 2 1 200[ , ] ( [ , ] )NNn k n k n kN N NnnF k k W W f n n W  （ 315） 其中 1 1 2 20 1 , 0 1k N k N     。 以 20 点 FFT 为例， 1220, 5, 4N N N  ，映射方式为： 124n n n，125k k k ，则计算流图如图 31 所示。 武汉工程大学毕业设计 (论文 )说明书 9 图 31 CooleyTukey 20 点 FFT算法 3. 3 RaderBrenner FFT 算法 RaderBrenner 算法是类似于 CooleyTukey 算法，但是采用的旋转因 子都是纯虚数，以增加加法运算和降低了数值稳定性为代价减少了乘法运算。 这方法之后被 splitradix variant of CooleyTukey 所取代，与 RaderBrenner 算法相比，有一样多的乘法量，却有较少的加法量，且不牺牲数值的准确性 [7]。 Bruun 以及 QFT 算法是不断的把 DFT 分成许多较小的 DFT 运算。 (RaderBrenner 以及 QFT 算法是为了 2 的指数所设计的算法，但依然可以适用在可分解的整数上。 Bruun 算法则可以运用在可被分成偶数个运算的数字 )。 尤其是 Bruun 算法，把 FFT 看成是 1zN ，并把它分解成 1zM 与 12  zz MM a 的形式。 另一个从多项式观点的快速傅立叶变换法是 Winograd 算法。 此算法把n1 k2 f[0] 0 W0 0 F[0] f[4] 1 W0 1 F[5] f[8] 2 W0 2 F[10] f[12] 3 W0 3 F[15] f[16] 4 W0 0 F[1] f[1] 0 W1 1 F[6] f[5] 1 W2 2 F[11] f[9] 2 W3 3 F[16] f[13] 3 f[17] 4 W0 0 F[2] W2 1 F[7] f[2] 0 W4 2 F[12] f[6] 1 W6 3 F[17] f[10] 2 f[14] 3 W0 0 F[3] f[18] 4 W3 1 F[8] W6 2 F[13] f[3] 0 W9 3 F[18] f[7] 1 f[11] 2 W0 0 F[4] f[15] 3 W4 1 F[9] f[19] 4 W8 2 F[14] W12 3 F[19] k1=0 n2=0 n2=1 n2=2 n2=3 k1=1 k1=2 k1=3 k1=4 武汉工程大学毕业设计 (论文 )说明书 10 1zN 分 解成 cyclotomic 多项式，而这些多项式的系 数通常为 1， 0， 1。 这样只需要很少的乘法量 (如果有需要的话 )，所以 winograd 是可以得到最少乘法量的快速傅立叶算法，对于较小的数字，可以找出有效率的算方式。 更精确地说，winograd 算法让 DFT 可以用 2K点的 DFT 来简化，但减少乘法量的同时，也增加了非常多的加法量。 Winograd 也可以利用剩余值定理来简化 DFT。 Rader 算法提出了利用点数为 N(N 为质数 )的 DFT 进行长度为 N1的回旋折积来表示原本的 DFT，如此就可利用折积用一对基本的 FFT 来计算 DFT。 另一个primesize 的 FFT 算法为 chirpZ 算法。 此法也是将 DFT 用折积来表示，此法与 Rader 算法相比，能运用在更一般的转换 上，其转换的基础为 Z 转换 [8]。 Goertsel 算法 如前所述 , N 点时域序列 )(nx 的离散付里叶变换式为   10 )()( Nn knNWnxkX ， 1,....,2,1,0  Nk （ 316） 这 N 点频域序列是同时被算出的，不可能只计算其中某一个或几个指定点。 Goetzel 算法是为了解决这个问题而提出的。 这个算法把离散付里叶变换看作一组滤波器，将输入端的时域序列与其中一个滤波器的冲激响应序列进行卷积运算，求滤波器的输出序列，即得 )(kX 序列的一点。 这种算法利用旋转因子 kNW 的周期性，使 DFT 运算化为线性滤波运算 [9]。 由于 1))(2(   kNNjkNN eW 故式（ 316）可化为 )(1010 )()()( mNkNNmkmNNmkNN WmxWmxWkX  1,....,2,1,0  Nk （ 317） 定义序列 )(nyk 为 )(10 )()( mnkNNmk Wmxny  （ 318） 可见 )(nyk 是由两个序列卷积而得到的序列。 )()()( nhnxny kk  （ 319） 其中， )(nx 是输入的 N 点序列，另。