第三章傅里叶分析

因此，序列的傅里叶变换也就是单位圆上的 因此，序列的傅里叶变换也就是单位圆上的 Z变换。--3-#-在计算机编程时，将蝶形的两个输出值仍放回到两个输入所在的存储器中， 这种运算就称为"同址运算”。倒位序规律及实现I.倒位序的规律这种顺序看似混乱无序，但实际上是有规律的，我们将其称为“ 倒位序”。倒位序的原因是输入.x(M按时域变量.n.的奇偶不断进行分组而造成的。.% 5 叫II.倒位序的实现一般在实际运算中，我们总是先按自然顺序将输入序列存入存储单元中，再通过变址运算来实现倒位序的排列。其具体方法如下：A如果输入序列x(n)的序号n用二进制数(例如n2nino)表示，则其倒位序二进制数n就是(n0nin2)°下表所示的是N=8时的自然顺序二进制数以及相应的倒位序二进制数对照表。自然顺序n自然顺序二进制数倒位序二进制数倒位序顺序n0000000010011004201001023011110641000011510110156110011371111117由此可知，只要在原来存放自然顺序序列 x(n)的单元中，存入倒位序序列 x(n),即可实现倒位序的排列。这个变址过程如图所示。律歸单元4(0)川1、A⑵.4⑶.4(7)目然船序惓入JT❻、JT<-rW)i<7)变址>AV卜j-<4>M3)由图可见，当n=n时，不必调换；只有当 n丰n时，才需要将原来存放x(n)和x(n)的存储单元中的内容互换。为了节省调换时间，避免重复调换(保证只调换一次，否则又回到原状)，

A A A我们只需检查n和n的相对大小，若n>n,则表明此x(n)在前面已经和x(n)调换过了，不必再调换；否则，就必须进行互换。综上所述，实现倒位序排列的具体方法为： 若n>n时,不必调换；若n<n时,就必须将原来存放.x(n)和x(n)的存储单元中的内容互换。.这样就可以得到按时间抽取的同址运算所需要的倒位序排列。三、 按频率抽取(DIF)的基-2FFT算法(桑德-图基算法)前面讨论的FFT算法是将输入序列x(n)按时间变量n的奇偶分解为越来越短的序列。类似地，如果我们将输出序列 X(k)按频域变量k的奇偶分解为越来越短的序列，这种FFT算法就称为"频域抽取法”。四、 IDFT的快速算法(IFFT)利用FFT算法来计算IFFT的具体方法有以下两种：1.方法一首先，比较IDFT公式1N1x(n)IDFT[X(k)]—X(k)WNknNko和DFT公式N1knX(k) DFT[x(n)] x(n)WNn0可见，只要将DFT运算中的每一个系数W,n换成WNkn，最后再乘以常数1/N，则前面所介绍的按时间或按频率抽取的 FFT算法都可用来计算IDFT。例如，我们可直接由8点频率抽取FFT流图出发，把wNkn换成WNkn，并在每级(列)运算中都乘以1/2(注意:因为乘以.1/N就等效于.1/n=1/2m=(1/,2).M,.所以相当于每级都乘以1/2),这样即可得到相应的IFFT流图，如图所示。 输出x(n) 顺序排列 倒序排列aj-CQ)上(4ix⑸cX⑹JCaj-CQ)上(4ix⑸cX⑹JC⑺I-11T方法二首先，对IDFT公式取共轭,x(n)inNk(k)WNkn然后对上式两边再取共轭，得x(n)N1x(n)N1X(k)W『01-{DFT[X(k)]}由此可见，只要先将X(k)由此可见，只要先将X(k)取共