武汉工程大学毕业设计(论文)说明书
则式（3-7）即为式（3-6）的分解形式。将初始数据代入式（3-7）的第一个等式，可得每一组计算数据，一般将痗L-1组计算数据代入式（3-7）的第L个等式，计算后可得第L组计算数据（L＝１，２，?，γ），计算公式也可表示为
x1(n0kr?2k0)??k1r?1?0x0(kr?1kr?2k0)W(2r?1nr?1?2r?2nr?2??n0)k0=
xl?1(n0n1nr?20kr?1kr?2k0)?xl?1(n0n1nr?20kr?1kr?2 k0)WP （3-8）
式中P?2r?1nl?1?2r?2nl?2?（3-9） ?2r?1n0
0根据式（3-8），第L个数组中每个xl(k)?xl(n?r1n?r2nk?r1k?r20)k
的计算只依赖于上一个数组的两个数据这两个数据的标号相差2Y?1?N/2l，即
j?i?n/2l，而且这两个数据只用于计算第L个数组中标号的数据（等号右端为二进制数）。当nl?1分别取０和１时，分别有k?i,k?j?i?n/2l。因此，用上一组的两个数据计算所得的两个新数据仍可储存在原来位置，计算过程中只需要N个存储器。将xl(i)与xl(i?n/2l)称为第L个数组中的对偶结点对。计算每个对偶结点对只需一次乘法，事实上由式（3-8）可得
xl(i)?xl?1(i)?[i?Np1]W 2l
xl(i?NNp2)?x(i)?x[i?]W l?1l?12l2l （3-10）
r?2r?lr?lr?2r?lnP?2n?...?2P?2?2n?...?2n0别为式0l?2l?2式中：1 ；2（3-9）
中
nl?1R?1pP?P?2?P211?N/2，取０，１时对应的P值。因于是对偶结点的W有
如下关系：
WP2?WP1?N2?[e???N]P1?N2??WP1,因此式（3-8）可表示为
N]Wpl2NN（3-11）xl(i?l)?xl?1(i)?xl?1[i?l]Wp22
xl(i)?xl?1(i)?xl?1[i? 7
武汉工程大学毕业设计(论文)说明书
P的求法：在xl(i)中，i写成二进制数n0n1?nl?1kr?l?1?k0右移r?l位，就成为
0?0n0n1?nl?1颠倒位序得p?nl?1?n1n00?0(l?1,2?r)式（3-7）中，前面的r个等式，每个等式均对应一组数据进行计算，每组数据都有N/２对结点，根据式（3-11），每对结点只需作１次乘法和２次加法，因此，每组数据只需N/2次乘法和N次加法，因而完成r组数据的计算共需Nr/2次乘法和Nr次加法。 3. 2 Cooley-Tukey FFT算法
作N点FFT时，若N不是素数，FFT的核心是将一层运算映射为二层运算。则N可分解为N?N1N2，那么由f[n]的DFT
nk F[k]??f[n]WNn?0N?1 0?k?N?1 （3-12）
通过映射： 可得到
(N2n1?n2)(k1?N1k2)(N2n1k1?N1N2n1k2?n2k1?N1n2k2)nk WN?WN?WNn?N2n1?n2k?k1?N1k20?n1?N1?1,0?n2?N2?10?k1?N1?1,0?k2?N2?1 （3-13）
N1而N?N1N2，WN?WN2，WNN2?WN1，可化简为
n1k1n2k1n2k2nk WN ?WNWWNN2 （3-14）1从而式（3-12）转化为 F[k1,k2]?其中
N2?1n2?0?Wn2k2N2(Wn2k1NN1?1n1?0?f[n,n]W12n1k1N1 ) （3-15）
0?k1?N1?1,0?k2?N2?1。
以20点FFT为例，N?20,N1?5,N2?4，映射方式为：n?4n1?n2，
k?k1?5k2，则计算流图如图3-1所示。
8
武汉工程大学毕业设计(论文)说明书
n1 k2 f[0] 0 W0 0 F[0] f[4] 1 W0 k 1 =0 1 F[5] 0 f[8] 2 n 2 =0 W2 F[10] f[12] 3 W0 3 F[15] f[16] 4 W0 0 F[1] f[1] 0 W1 k =1 1 F[6] 1f[5] 1 W2 2 F[11] f[9] 2 n 2 =1 W3 3 F[16] f[13] 3 f[17] 4 W0 0 F[2] k=2 W2 1 1 F[7] f[2] 0 W4 2 F[12] f[6] 1 W6 3 F[17] n2=2 f[10] 2 f[14] 3 W0 0 F[3] k1=3 f[18] 4 W3 1 F[8] W6 2 F[13] f[3] 0 W9 3 F[18] f[7] 1 n2=3 0f[11] 2 W k =4 0 F[4] 1f[15] 3 W4 1 F[9] f[19] 4 W8 2 F[14] W12 3 F[19] 图3-1 Cooley-Tukey 20 点FFT算法
3. 3 Rader-Brenner FFT算法
Rader-Brenner 算法是类似于 Cooley-Tukey 算法，但是采用的旋转因子都是纯虚数，以增加加法运算和降低了数值稳定性为代价减少了乘法运算。这方法之后被split-radix variant of Cooley-Tukey所取代，与Rader-Brenner算法相比，有一样多的乘法量，却有较少的加法量，且不牺牲数值的准确性[7]。
Bruun以及QFT算法是不断的把DFT分成许多较小的DFT运算。(Rader-Brenner以及QFT算法是为了2的指数所设计的算法，但依然可以适用在可分解的整数上。Bruun算法则可以运用在可被分成偶数个运算的数字)。尤其是Bruun算法，把FFT看成是z?1 ，并把它分解成z?1 与z的形式。
另一个从多项式观点的快速傅立叶变换法是Winograd 算法。此算法把
9
NM2M?az?1
M武汉工程大学毕业设计(论文)说明书
zN?1 分 解成cyclotomic多项式，而这些多项式的系数通常为1，0，-1。 这
样只需要很少的乘法量(如果有需要的话)，所以winograd是可以得到最少乘法量的快速傅立叶算法，对于较小的数字，可以找出有效率的算方式。更精确地说，winograd算法让DFT可以用2K点的DFT来简化，但减少乘法量的同时，也增加了非常多的加法量。Winograd也可以利用剩余值定理来简化DFT。
Rader算法提出了利用点数为N(N为质数)的DFT进行长度为N-1的回旋折积来表示原本的DFT，如此就可利用折积用一对基本的FFT来计算 DFT。另一个prime-size的FFT算法为chirp-Z算法。此法也是将DFT用折积来表示，此法与Rader算法相比，能运用在更一般的转换 上，其转换的基础为Z转换[8]。 3.4 Goertsel 算法
如前所述, N点时域序列x(n)的离散付里叶变换式为
?kn， k?0,1,2,....,N?1 （3-16） X(k)??x(n)WNn?0N?1这N点频域序列是同时被算出的，不可能只计算其中某一个或几个指定点。Goetzel 算法是为了解决这个问题而提出的。这个算法把离散付里叶变换看作一组滤波器，将输入端的时域序列与其中一个滤波器的冲激响应序列进行卷积运
k算，求滤波器的输出序列，即得X(k)序列的一点。这种算法利用旋转因子WN的
周期性，使DFT运算化为线性滤波运算[9]。
由于
W故式（3-16）可化为 X(k)?W?kNNN?1m?0?kNN?e?j(2?)(?kN)N?1
?x(m)WkmN?k(N?m)??x(m)WNk?0,1,2,....,N?1 （3-17） m?0N?1定义序列yk(n)为
?k(n?m) yk(n)??x(m)WN （3-18）
m?0N?1可见yk(n)是由两个序列卷积而得到的序列。
yk(n)?x(n)?hk(n) （3-19） 其中，x(n)是输入的N点序列，另一个序列被看作滤波器的冲激响应序列
10
武汉工程大学毕业设计(论文)说明书
?knhk(n)?WNu(n)。 （3-20）
对比式(3-17）和式(3-18），可知：按式（3-19）进行卷积运算，当n?N时，滤波器的输出yk(N)就是X(k)：
X(k)?yk(n)|n?N （3-21） 对式(3-20)进行Z变换，可得滤波器的系统函数 Hk(z)?11?W?k?1z （3-22）
这是一个一阶系统。图3-2示出这个系统的信号流图，相应的差分方程为
?k yk(n)?WNyk(n?1)?x(n)， y(?1)?0 (3-23)
按照此式进行递推运算，到了 n?N 时刻，即可依据式（3-21）得到X(k)。
?k按照式(3-22)进行运算时，可先算好旋转因子WN，储存起来。每次递推包含一
次复数乘法。按式(3-16)直接计算N点离散付里叶变换,需要4N2次实数乘法和
N(4N-2)次实数加法。按照上述Goertzel算法，所需的实数乘法和实数加法都
是4N2次。所以当N不大时，上述算法的效率稍差[10]。下面介绍改进的Goertzel 算法，这种算法所需的实数乘法次数约为直接方法的一半。
图3-2 用一阶系统实现Goertzel 算法 图 3-3 用二阶系统实现Goert算法
k?1把式（3-22）的分子和分母都乘上因子(1?WNz)，就得到第k个滤波器的
系统函数为
k?11?WNz Hk(z)? ?k?1k?1(1?WNz)(1?WNz) 11
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库毕业论文-快速傅里叶变换算法及其在信号处理中的应用(3)在线全文阅读。
相关推荐：