第四章快速傅立叶变换讲解.ppt

16点的基-4的FFT算法的流图 分裂基FFT算法 分裂基FFT算法的思想是对偶数序号用基－2FFT算法，对奇数序号用基－4FFT算法，主要原因是考虑到在基－2FFT算法中，每一组的偶序号部分都不乘旋转因子，乘的部分都在奇序号部分，考虑到基－4FFT算法比较有效，因此在1984年提出了“分裂基”算法。 线性调频z变换（chirp－z变换） Chirp－z变换是z变换中采用螺线抽样，是适用于在更为一般的情况下由 求 的快速变换算法 算法基本原理 布鲁斯坦等式（Bluestein）： 变换图示： 实现步骤 选择一个最小整数 ，使其满足 ，同时满足 ，以便采用基－2FFT算法； 将 补上零值点，变为L点的序列 用FFT求DFT 用FFT法求 ，得到 的圆周卷积： 最后求 例如 则 例如 算法原理 实际上是把一位数字用一个矩阵形式表示 例如： ，则 算法步骤： 将 ，利用 利用 得到： 利用 得到： 利用 ，进行整序 例如： 对于前面 步骤： 另外，也可以采用先乘以旋转因子再进行DFT的算法 基－4FFT算法 若 例如： 以第一级为例， 的四点DFT可以表示为： 调整输出的顺序 绘制成为流图形式 第二级运算 按照二进制倒位序排列 倒位序的实现 补充：换位的时候有个换位产生倒码的算法 顺码 二进制 二进制 倒码 0 000 000 0 1 001 100 4 2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7 最高位为“0”的倒码的下一个倒码仅与它的最高位差“1”。即若在最高位用“1”代替“0”，便可以得到0，2，1，3相应的下一个倒码4，6，5，7。一般可以表示成为： 如果倒码的最高位不是“0”而是“1”，如给出的倒码为“4”，则下一个倒码除了要把最高位的“1”改为“0”以外，尚应该测试次高位，若次高位为“0”，则用“1”替代，可得 蝶形运算两结点的“距离” 以前面8点的FFT为例，其输入是倒位序的，输出是自然顺序的，其第一级的每个蝶形的两节点间“距离”为1。第二级的每个蝶形的两节点“距离”为2，依此类推对 点FFT，当输入为倒位序，输出为自然顺序时，其第级运算，每个蝶形的两节点“距离”为 的确定 的确定 存储单元 由于是原位运算，只需输入序列 的 个存储单元，加上系数 的 个存储单元。 按时间抽选，输入自然顺序，输出倒位序的FFT流图： 按时间抽选，输入输出均为自然顺序的FFT流图： 按时间抽取，各级具有相同几何形状，输入倒位序，输出自然顺序的FFT流图： 按频率抽选（DIF）的基－2FFT算法（桑得－图基算法） 算法原理 点DFT按 的奇偶分解为两个 点的DFT 原位运算 蝶形运算两节点间的“距离” 按频率抽选法与按时间抽选法的异同 page155 表格 离散傅立叶反变换（IDFT）的快速计算方法 一种思想： 另一种思想： 若不满足 有几种方法解决： （1）???? 补零值点的方法，以使增长到最邻近的一个，根据DFT的性质可知，补零后并不影响频谱，只不过是频谱的抽样点数增加了，结果是增加了计算量。但是有的时候计算量增加太多，造成很大浪费 （2）???? 如果要求准确的点DFT，而是个素数，则只能采用直接DFT方法，或者用后面将要介绍的CZT（Chirp Z）变换的方法 （3）???? 若是复合数，则可以用混合基FFT算法 整数的多基多进制表示形式 二进制 多基多进制 二进制 ，任何一个 都可以表示成为 则任何一个 的正整数可以用r为基数表示成 形式 多基