按时间抽取的基2FFT算法分析及MATLAB实现

精品文档 1欢迎下载 按时间抽取的基按时间抽取的基 2FFT2FFT 算法分析及算法分析及 MATLABMATLAB 实现实现 一 一 DIT FFTDIT FFT 算法的基本原理算法的基本原理 基 2FFT 算法的基本思想是把原始的 N 点序列依次分解成一系列短序列 充分利用旋转因子 的周期性和对称性 分别求出这些短序列对应的 DFT 再进行适当的组合 得到原 N 点序 列的 DFT 最终达到减少运算次数 提高运算速度的目的 按时间抽取的基 2FFT 算法 先是将 N 点输入序列 x n 在时域按奇偶次序分解成 2 个 N 2 点序列 x1 n 和 x2 n 再分别进行 DFT 运算 求出与之对应的 X1 k 和 X2 k 然后利用 图 1 所示的运算流程进行蝶形运算 得到原 N 点序列的 DFT 只要 N 是 2 的整数次幂 这 种分解就可一直进行下去 直到其 DFT 就是本身的 1 点时域序列 图 1 DIT FFT 蝶形运算流图 2 2 DIT FFTDIT FFT 算法的运算规律及编程思想算法的运算规律及编程思想 1 原位计算 对 N 点的 FFT 共进行 M 级运算 每级由 N 2 个蝶形运算组成 在同一级中 每个蝶的 M 2 输入数据只对本蝶有用 且输出节点与输入节点在同一水平线上 这就意味着每算完一个 蝶后 所得数据可立即存入原输入数据所占用的数组元素 存储单元 经过 M 级运算后 原来存放输入序列数据的 N 个存储单元中可依次存放 X k 的 N 个值 这种原位 址 计算的 方法可节省大量内存 2 旋转因子的变化规律 N 点 DIT FFT 运算流图中 每个蝶形都要乘以旋转因子 p 称为旋转因子的指数 例 p WN 如 N 8 时各级的旋转因子 3 2 第一级 L 1 有 1 个旋转因子 J 0 p WN J 4 WN J 2L W 第二级 L 2 有 2 个旋转因子 J 0 1 p WN J 2 WN J 2L W 精品文档 2欢迎下载 第三级 L 3 有 4 个旋转因子 J 0 1 2 3 p WN J WN J 2L W 对于 N 的一般情况 第 L 级共有个不同的旋转因子 M 2 1 L 2 J 0 1 2 1 p WN J 2L W 1 L 2 N L 2 M 2 M L 2 M L 2 故 按照上面两式可以确定第 L 级运算的旋转因子 3 同一级中 同一旋转因子对应蝶形数目 第 L 级 FFT 运算中 同一旋转因子用在个蝶形中 L M 2 4 同一级中 蝶形运算使用相同旋转因子之间相隔的 距离 第 L 级中 蝶距 D L 2 5 同一蝶形运算两输入数据的距离 在输入倒序 输出原序的 FFT 变换中 第 L 级的每一个蝶形的 2 个输入数据相距 B 1 L 2 6 码位颠倒 输入序列 x n 经过 M 级时域奇 偶抽选后 输出序列 X k 的顺序和输入序列的顺序 关系为倒位关系 将十进制顺序数用 I 表示 与之对应的二进制是用 IB 表示 十进制倒序数用 J 表示 与之 对应的二进制是用 JB 表示 十进制顺序数 I 增加 1 相当于 IB 最低位加 1 且逢 2 向高位 进 1 即相当于 JB 最高位加 1 且逢 2 向低位进 1 JB 的变化规律反映到 J 的变化分为两种 情况 若 JB 的最高位是 0 J N 2 则直接由加 1 J J N 2 得到下一个倒序值 若 JB 的最高位是 1 J N 2 则要先将最高位变 0 J J N 2 再在次高位加 1 J J N 4 但次高位加 1 时 同样要判断 0 1 值 如果是 0 J N 4 则直接加 1 J J N 4 否则要先将次高位变 0 J J N 4 再判断下一位 依次类推 直到完成 最高位加 1 逢 2 向右进位的运算 I J 时不需要交换 只对 I J 时的情况进行数据交换即 精品文档 3欢迎下载 可 数据倒序程序框图如如 2 7 蝶形运算的规律 序列经过时域抽选后 存入数组中 如果蝶形运算的两个输入数据相距 B 个点 应用 原位计算 蝶形运算可表示成如下形式 8 DIT FFT 程序框图 根据 DIT FFT 原理和过程 DIT FFT 的完整程序框图如图 2 1 倒序 输入自然顺序序列 x n 根据倒序规律 进行倒序处理 2 循环层 1 确定运算的级数 L 1 M N 确定一蝶形两输入数据距离 B M 2 1 L 2 3 循环层 2 确定 L 级的 B 个旋转因子 旋转因子指数 p J J 0 B 1 1 L 2 L M 2 4 循环层 3 对于同一旋转因子 用于同一级个蝶形运算中 k 的取值从 J 到 N 1 步 L M 2 长为 使用同一旋转因子的蝶形相距的距离 L 2 5 完成一个蝶形运算 p J 2M L J 0 1 2 2L 1 1 精品文档 4欢迎下载 倒 倒 送入x n M N 2 M 倒 倒 L 1 M 0 B 1 P 2 M LJ k J N 1 2 L p N p N WBkXkXBkX WBkXkXkX 输 出 倒 倒 B 2 L 1 图 2 数据倒序程序框图 图 3 DIT FFT 的完整程序框图 3 3 程序源代码程序源代码 设计函数myDitFFT xn 完成一个序列的 DIT FFT 运算 function y myDitFFT xn M nextpow2 length xn N 2 M disp 调用 fft 函数运算的结果 fftxn fft xn N if length xn N xn xn zeros 1 N length xn 精品文档 5欢迎下载 end for m 0 N 2 1 旋转因子指数范围 WN m 1 exp j 2 pi N m 计算旋转因子 end disp 输入到各存储单元的数据 disp xn 数据倒序操作 J 0 给倒序数赋初值 for I 0 N 1 按序交换数据和算倒序数 if I K J J K K K 2 end J J K end disp 倒序后各存储单元的数据 disp xn 分级按序依次进行蝶形运算 for L 1 M 分级计算 disp 运算级次 disp L B 2 L 1 精品文档 6欢迎下载 for R 0 B 1 各级按序蝶算 P 2 M L R for K R 2 L N 2 每序依次计算 T xn K 1 xn K B 1 WN P 1 xn K B 1 xn K 1 xn K B 1 WN P 1 xn K 1 T end end disp 本级运算后各存储单元的数据 disp xn end 在主函数中调用 myDitFFT xn 函数实现 DIT FFT 并和直接 DFT 运算结果做对比 xn 0 1 2 3 4 5 6 7 myDitFFT xn 调用调用 fftfft 函数运算的结果函数运算的结果 1 至 7 列 28 0000 0 0000i 4 0000 9 6569i 4 0000 4 0000i 4 0000 1 6569i 4 0000 0 0000i 4 0000 1 6569i 4 0000 4 0000i 8 列 4 0000 9 6569i 调用调用 myDitFFT xn myDitFFT xn 函数运行的结果 函数运行的结果 输入到各存储单元的数据 精品文档 7欢迎下载 0 1 2 3 4 5 6 7 倒序后各存储单元的数据 0 4 2 6 1 5 3 7 运算级次 1 本级运算后各存储单元的数据 4 4 8 4 6 4 10 4 运算级次 2 本级运算后各存储单元的数据 1 至 7 列 12 0000 0 0000i 4 0000 4 0000i 4 0000 0 0000i 4 0000 4 0000i 16 0000 0 0000i 4 0000 4 0000i 4 0000 0 0000i 8 列 4 0000 4 0000i 运算级次 3 本级运算后各存储单元的数据 1 至 7 列 28 0000 0 0000i 4 0000 9 6569i 4 0000 4 0000i 4 0000 1 6569i 4 0000 0 0000i 4 0000 1 6569i 4 0000 4 0000i 8 列 4 0000 9 6569i 经对比可知 DIT FFT 与直接 DFT 的运行结果完全相同 4 4 总结总结 精品文档 8欢迎下载 经过验证可发现 DIT FFT 较直接 DFT 运算有着明显的优势 我们可以将这个函数运用在多 个领域以简化运算 例如计算离散时间序列的卷积或计算 IDFT 时都可以应用到 DIT FFT 算 法 我感受到数字信号处理中科学思想的魅力 由于对设计思路的缺乏 我在设计程序时 在网络上查找了很多有关 DIT FFT 的资料 经过学习他人的解决思路最后才整理出 DIT FFT 的程序 在有些地方我自己理解的还不是很透彻 比如在实现数据倒序的程序我认为 比较困难 当然即使自己想不到能学习一下别人的思路也是很好的 这个程序的代码量并 不大 我自身的能力还很低 要在以后的学习中不断进步才能完成更加复杂的任务 这次 课程设计让我对快速傅