快速傅里叶变换课件

《快速傅里叶变换课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章　快速傅里叶变换1.　引言2.　直接计算DFT的问题及改进的途径3.　按时间抽选（DIT）的基－2FFT算法4.　离散傅里叶反变换（IDFT）的快速计算方法5.　N为复合数的FFT算法－混合基算法6.　线性调频Z变换（Chirp-z变换）算法7.　线性卷积与线性相关的FFT算法1.　引言库利和图基发表的“机器计算傅里叶级数的一种算法”桑德和图基的快速算法的出现。主要讨论几种FFT算法。2.　直接计算DFT的问题及改进的途径DFT和IDFT的变换公式4.1式可写成（4.3）4.1(4-2)存在问题：整个DFT运算总共需要4次行乘法运算和次加法运算。直接计算DF

2、T，乘法次数和加法次数都是和　　成正比。减少DFT运算工作量的途径：利用　　对称性：（1）　　的对称性：（2）　　的周期性：（3）　　的可约性：可以得出实际办法：（1）用上述特性对项合并（2）将长序列的DFT分解为短序列的DFT。3.　按时间抽选的基－2FFT算法－－3.1　算法原理先设序列点数为　　　　，按n的奇偶进行分解将DFT化为利用系数　　的可约性，即　　　　　　　　　　　　　　得（4.5）式中（4.6）（4.7）应用系数的周期性　　　　　　　　　可得（4.8）（4.9）再考虑性质　　　　　　　　　　　　　（4.10）把4.8,4.9,4.10代入4.5

3、式，将X(k)表达成前后两部分，前部分为（4.11）后部分为（4.12）这样，4.11、12式只要0-(N/2-1)区间的所有的值，即可求0到(N-1)区间所有X(k)值。4.11和4.12式用图4－1的蝶形符号表示。N＝8的情况如图4－2分析：每个蝶形运算需要一次复数乘法　　　　及两次复数加（减）法。通过分解后运算工作量差不多减少到一半。进一步把N/2点子序列再按奇偶部分分解为两个N/4点的子序列且其中图4－3，给出N＝8时，在分解为两个N/4点DFT，由两个N/4点DFT组合成N/2点DFT的流图。也可进行同样分解：其中一个N＝8点DFT就可分解为四个N/4＝

4、2点DFT如图序列按奇偶分解标号变化讨论（N＝8）第一次分解：两个N/2点序列：第二次分解，每个N/2点子序列按其奇偶分解为两个N/4点子序列最后2点DFT按4－14~17进行计算。这种方法的每一步分解都是按输入序列在时间上的次序是属于偶数不是属于奇数来分解为两个更短的子序列，所以称为“按时间抽选法”。运算量分析直接DFT复数算法次数是FFT复数乘法次数是DFT和FFT算法的计算量之比为结论：FFT比DFT更优越，当N越大时，优点更明显。三、按时间抽选的FFT算法特点1.　原位运算每个蝶形结构完成下述基本迭代运算：4.21的蝶形运算如图4－7所示。2.　倒位序规律

5、3.　倒位序的实现：通过变址运算完成4.　蝶形运算两结点的距离：第m级运算，每个蝶形的两节点距离为的确定第m级运算由4－21式写成其中r的求解方法为6.　存储单元输入序列　　　　　　　　　　　　N个单元系数　　　　　　　　　　　　　N/2个单元四.　按时间抽选的FFT算法的其它形式流程图4.5　离散傅里叶反变换的快速计算方法从IDFT公式与DFT公式比较可知，只要把DFT运算中的每一个系数变成　　　，最后再乘常数1/N，则以上所有按时间抽选或按频率抽选的FFT都可以拿来运算IDFT。不改FFT的程序计算IFFT方法：对4.29式取共轭因而4.6　N为复合数的FFT

6、算法－－混合基算法当N不满足　　　　　时，可有以下几种办法（1）将x(n)补一些零值点的办法（2）如要求准确的N点DFT，而N又是素数，则只能采用直接DFT方法，或者用CZT方法。（3）N是复合数，即它可以分解成一些成一些因子的乘积，用混合基算法。一.　整数的多基多进制表示形式（1）对于二进制，　　　表示为二进制倒序为（2）对于r进制，正序倒序（3）对于多进制或称混合基N可以表示成复合数，　　　　　　　　，则对于的任一个正整数n,可以按L个基　　　　　　　　表示。正序倒序在这一多进制的表示中可记为例4－1二、　　　　　的快速算法要计算N点DFT为（4.39）设n

7、是一个复合数　　　　　，可将n的数用下面的公式表达：（4.40）同样，倒序表达为（4.41）例：设　　　　　　，则那么所以则排列为同样，若　　　　　　　　则所以将4.40式与4.41式代入4.39式，可得上式运用了　　　　　　　　　　　　　　结果4.42式可进一步表示为式中N为复合数　　　　　的DFT算法的步骤归纳如下：（1）将x(n)改写成　　　　　　　利用利用4.44式做　　个　　点DFT，得利用4.45式，把N个　　　　　乘以相应的旋转因子　　　　，组成　　　　　　　。利用4.46式，做　　个　　点DFT，得利用4.47式，进行整序，得到其中对于　　　　　　

8、　　　重写