快速傅里叶变换(FFT)的DSP实现

目录 一 前言 二 设计题目 三 设计要求 3 1 设计目的 3 2 设计要求 四 设计内容 五 设计原理 5 2 离散傅里叶变换 DFT 5 3 快速傅里叶变换 FFT 六 总体方案设计 6 1 设计有关程序流程图 6 2 在 CCS 环境下加载 调试源程序 七 主要参数 八 实验结果分析 九 设计总结 一 前言一 前言 随着数字电子技术的发展 数字信号处理的理论和技术广泛的应 用于通讯 语音处理 计算机和多媒体等领域 快速傅里叶变换 FFT 使离散傅里叶变换的时间缩短了几个数量级 在数字信号处 理领域被广泛的应用 FFT 已经成为现代化信号处理的重要手段之一 本次课程设计主要运用 CCS 这一工具 CCS Code Composer Studio 是 一种针对 TM320 系列 DSP 的集成开发环境 在 Windows 操作系统 下 采用图形接口界面 提供环境配置 源文件编辑 程序调试 跟踪和分析等工具 可以帮助用户在一个软件环境下完成编辑 编 译 链接 调试和数据分析等工作 CCS 有两种工作模式 即软件仿真器和硬件在线编程 软件仿真 器工作模式可以脱离 DSP 芯片 在 PC 上模拟 DSP 的指令集和工作 机制 主要用于前期算法实现和调试 硬件在线编程可以实时运行 在 DSP 芯片上 与硬件开发板相结合进行在线编程和调试应用程序 二 二 设计题目设计题目 快速傅里叶变换 FFT 的 DSP 实现 三三 设计要求设计要求 3 1 设计目的 加深对 DFT 算法原理和基本性质的理解 熟悉 FFT 的算法原理和 FFT 子程序的算法流程和应用 学习用 FFT 对连续信号和时域信号进行频谱分析的方法 学习 DSP 中 FFT 的设计和编程思想 学习使用 CCS 的波形观察器观察波形和频谱情况 3 2 基本要求 研究 FFT 原理以及利用 DSP 实现的方法 编写 FFT 程序 调试程序 观察结果 四 四 设计内容设计内容 用 DSP 汇编语言及 C 语言进行编程 实现 FFT 运算 对输入信号进行频谱分析 五 五 设计原理设计原理 快速傅里叶变换 FFT 快速傅里叶变换 FFT 是一种高效实现离散傅里叶变换 DFT 的快速算法 是数字信号处理中最为重要的工具之一 它在声学 语音 电信和信号处理等领域有着广泛的应用 5 1 离散傅里叶变换 DFT 对于长度为 N 的有限长序列 x n 它的离散傅里叶变换 DFT 为 1 1 0 1 0 NkWnxkX n n nk N 1 式中 Nj N eW 2 称为旋转因子或蝶形因子 从 DFT 的定义可以看出 在 x n 为复数序列的情况下 对某 个 k 值 直接按 1 式计算 X k 只需要 N 次复数乘法和 N 1 次 复数加法 因此 对所有 N 个 k 值 共需要 N2 次复数乘法和 N N 1 次 复数加法 对于一些相当大有 N 值 如 1024 点 来说 直接计算 它的 DFT 所需要的计算量是很大的 因此 DFT 运算的应用受到了很 大的限制 5 2 快速傅里叶变换 FFT 旋转因子 WN 有如下的特性 对称性 2 Nk N k N WW 周期性 Nk N k N WW 利用这些特性 既可以使 DFT 中有些项合并 减少了乘法积项 又可以将长序列的 DFT 分解成几个短序列的 DFT FFT 就是利用了旋 转因子的对称性和周期性来减少运算量的 FFT 的算法是将长序列的 DFT 分解成短序列的 DFT 例如 N 为 偶数时 先将 N 点的 DFT 分解为两个 N 2 点的 DFT 使复数乘法减 少一半 再将每个 N 2 点的 DFT 分解成 N 4 点的 DFT 使复数乘又 减少一半 继续进行分解可以大大减少计算量 最小变换的点数称 为基数 对于基数为 2 的 FFT 算法 它的最小变换是 2 点 DFT 一般而言 FFT 算法分为按时间抽取的 FFT DIT 和按 频率抽取的 DIF FFT 两大类 IF FFT 算法是在时域内将每 一级输入序列依次按奇 偶分成 个短序列进行计算 而 DIF FFT 算 法是在频域内将每一级输入序列依次奇 偶分成 个短序列进行计 算 两者的区别是旋转因子出现的位置不同 得算法是一样的 在 DIF FFT 算法中 旋转因子 k N W 出现在输入端 而在 DIF FFT 算法中 它出现在输入端 假定序列 x n 的点数 N 是 2 的幂 按照 DIF FFT 算法可将其分为 偶序列和奇序列 偶序列 12 1 0 2 2 N 4 2 0 1 Nrrxxxxxx 即 奇序列 12 1 0 12 1 N 5 3 1 2 Nrrxxxxxx 即 则 x n 的 DFT 表示为 2 12 2 12 0 2 2 12 0 2 1 12 0 12 12 0 2 1 0 1 0 N r rk N k N N r rk N N r kr N N r rk N N n nk N N n nk N WrxWWrx WrxWrx nn WnxWnxkX 为奇数为偶数 由于 2 2 2 2 2 2 N NjNj N WeeW 则 3 式 可表示为 3 12 1 0 21 12 0 2 2 12 0 2 1 NkkXWkX WrxWWrxkX k N N r rk N k N N r rk N 式中 1 kX 和 2 kX 分别为 1 nx 和 2 nx 的 N 2 的 DFT 由于对称性 2 K N Nk N WW 则 2 21 kXWkXNkX k N 因此 N 点 kX 可分为两部分 前半部分 12 1 0 21 NkkXWkXkX k N 4 后半部分 12 1 0 2 21 NkkXWkXNkX k N 5 从式 4 和式 5 可以看出 只要求出 0 N 2 1 区间 1 kX 和 2 kX 的值 就可求出 0 N 1 区间 kX 的 N 点值 以同样的方式进行抽取 可以求得 N 4 点的 DFT 重复抽取过程 就可以使 N 点的 DFT 用上组 2 点的 DFT 来计算 这样就可以大减少 运算量 基 2 DIF FFT 的蝶形运算如图 a 所示 设蝶形输入为 1 pxm 和 1 qxm 输出为 pxm 和 qxm 则有 k Nmmm Wqxpxpx 11 6 k Nmmm Wqxpxqx 11 7 在基数为 2 的 FFT 中 设 N 2M 共有 M 级运算 每级有 N 2 个 2 点 FFT 蝶形运算 因此 N 点 FFT 总共有 NN 2 log 2 个蝶形运算 1 qxm pxm 1 qxm qxm 1 图 a 基 2 DIF FFT 的蝶形运算 例如 基数为 2 的 FFT 当 N 8 时 共需要 3 级 12 个基 2 DIT FFT 的蝶形运算 其信号流程如图 b 所示 图 b 8 点基 2 DIF FFT 蝶形运算 从图 b 可以看出 输入是经过比特反转的倒位序列 称为位码倒 置 其排列顺序为 7 3 5 1 6 2 4 0 xxxxxxxx 输出是按自然 顺序排列 其顺序为 7 6 1 0 xxxx 六 六 总体方案设计总体方案设计 6 1 设计程序流程图 6 2 在 CCS 环境下加载 调试源程序 1 起动 CCS 在 CCS 中建立一个工程文件 project new FFT 往工 程文件里添加程序 file new sourcefile 建立 C 源文件和一个命令文件 并将这两个文件添加到工程 再编译并装载程序 阅读 Dsp 原理及应用中 fft 用 dsp 实现的有关程序 双击 启动 CCS 的仿真平台的配着选项 选择 C5510 Simulator Add 加到 my system 按下 save 2 启动 c5510 后打开文件 FFT pjt 将编写好的源程序 和命令 文件加载到文件 FFT pjt Source 3 按下 project build 调试程序 看其中是否有错误 4 无错后 Debug run 运行 FFT out 程序 5 通过 graph property dialog 窗口 改变 N 点的值 得到不同的结 果 七 主要参数主要参数 进行 N 点 FFT 运算 分别实现 N 256 N 512 得到不同的功率谱图 六 源程序 Cmd 源文件代码 f 0 w stack 500 sysstack 500 l rts55 lib MEMORY DARAM o 0 x100 l 0 x7f00 VECT o 0 x8000 l 0 x100 DARAM2 o 0 x8100 l 0 x7f00 SARAM o 0 x10000 l 0 x30000 SDRAM o 0 x40000 l 0 x3e0000 SECTIONS text DARAM vectors VECT trcinit DARAM gblinit DARAM frt DARAM cinit DARAM pinit DARAM sysinit DARAM2 far DARAM2 const DARAM2 switch DARAM2 sysmem DARAM2 cio DARAM2 MEM obj DARAM2 sysheap DARAM2 sysstack DARAM2 stack DARAM2 input DARAM2 fftcode DARAM2 C 文件源码 include math h define sample 1 256 define signal 1 f 60 define signal 2 f 200 define signal sample f 512 define pi 3 1415926 int input sample 1 float fwaver sample 1 fwavei sample 1 w sample 1 float sin tab sample 1 float cos tab sample 1 void init fft tab void input data void fft float datar sample 1 float datai sample 1 void main int i init fft tab input data for i 0 i sample 1 i fwaver i input i fwavei i 0 0f w i 0 0f fft fwaver fwavei while 1 void init fft tab float wt1 float wt2 int i for i 0 i sample 1 i wt1 2 pi i signal 1 f wt1 wt1 signal sample f wt2 2 pi i signal 2 f wt2 wt2 signal sample f input i cos wt1 cos wt2 2 32768 void input data int i for i 0 i sample 1 i sin tab i sin 2 pi i sample 1 cos tab i cos 2 pi i sample 1 void fft float datar sample 1 float datai sample 1 int x0 x1 x2 x3 x4 x5 x6 x7 xx int i j k b p L float TR TI temp for i 0 i sample 1 i x0 x1 x2 x3 x4 x5 x6 0 x0 ix1 i 2 x2 i 4 x3 i 8 x4 i 16 x5 i 32 x6 i 64 x7 i 128 xx x0 128 x1 64 x2 32 x3 16 x4 8 x5 4 x6 2 x7 datai xx datar i for i 0 i sample 1 i datar i datai i datai i 0 for L 1 L0 b b 2 i for j 0 j0 p p 2 i p p j for k j k 256 k k 2 b TR datar k TI datai k temp datar k b datar k datar k datar k b cos tab p datai k b sin tab p datai k datai k datar k b sin tab p datai k b cos tab p datar k b TR datar k b cos tab p datai k b sin tab p datai k b TI temp sin tab p datai k b cos tab p for i 0 i sample 1 2 i w i sqrt datar i datar i datai i datai i 八 八 实验结果及分析实验结果及分析 作图 得到输入信号的功率图谱 2 FFT 变换结果图 3 改变信号的频率可以再做次实验 FFT 算法特点 r N2 共需r次迭代 第 1 rLL 次迭代对偶结点的偶距为 LLr LL NKK2 2 因此一组 结点覆盖的序号个数是 1 2 2 L LL N KK 第 1 rLL 次迭代结点的组数为 1 2 2 L LL KKN L P N W 可以预先计算好 而且 L P 的变化范围是 1 2 0 N 因此