综合课程设计报告第三组.doc

综合课程设计报告基于ADSP-2191的数字信号处理实现 题目：基二频率抽取的快速傅立叶变换算法 小组成员: 安海鹏 高轩 王康蔚 朱峻岗 蒋骏宁（组长） 东南大学信息科学与工程学院 二○一一年一月 题目概述 快速傅立叶变换是一种快速有效地计算离散傅立叶变换的方法。一般情况下输入的时间序列及其离散傅立叶变换是用复数表示的，直接计算DFT及IDFT需要次复数乘法以及次复数加法，由于1次复数乘法对应4次实数惩罚和2次实数加法，1次复数加法需要做2次实数加法，所以1次离散傅立叶变换需要做次实数乘法及次实数加法。20世纪60年代Cooley和Tukey提出了一种离散傅立叶变换的快速算法，将其运算量下降为次复数乘法和次复数加法。本次基于ADSP-2191的数字信号处理实现基二频率抽取的算法就是对上述功能在DSP平台上的利用汇编语言的实现。 算法介绍 基二频率抽取FFT运算流图 图2.1.1 N=16的基二频率抽取的FFT运算流图 图2.1.1为N=16的基二频率抽取的FFT运算流图，构成了课题目标算法的理论基础，流图包含：蝶形运算和序数重排两个部分，总的蝶形个数为 ，每个蝶形需要完成2次加（减）法运算，1次乘法运算，序数重排需要将输出结 果重新排序得到正确的结果。在N=16的情况下，一共有32次蝶形运算，即一共需要32次复数乘法运算和64次复数加法运算。 图2.1.2 输入稀疏度为4的N=16的基二频率抽取的FFT运算流图 图2.1.2为本课程要求的输入稀疏度为4基二频率抽取的FFT运算流图，从图上可以得到需要进行12次半蝶形运算和16次蝶形运算，一共需要进行28次复数乘法和32次复数加法运算。对比图2.1.1的流图，N=16的FFT运算流图需要32次复数乘法和64次复数加法，图2.1.2的流图去除了输入为0的点，将一部分蝶形运算转换成为半蝶形运算，减少了4次复数乘法和32次复数加法，提高了算法的效率。 蝶形运算与半蝶形运算 复数加法与减法 复数加法 一次复数加法包含行两次实数加法过程。对于实数加法，设输入X操作数X,Y操作数Y，X,Y ，且X,Y均为16位有符号数，加法得到的结果Z ,Z为17位有符号数。如果输入的X,Y操作数均为，得到的结果就是溢出的，如果将存入寄存器继续运算的话，将带来链式错误。考虑上述情况，需要 Z和X,Y具有相同的范围即，本程序采取先将X,Y均算术右移一位，即可使得Z的范围满足要求。同时考虑到，最后一位的舍入误差，在右移后，先将X,Y的最后一位进行加法运算，在考虑进位的情况下，进行主值加法。此方法的误差为不考虑末位进位的1/2，降低的误差率。 复数减法 一次复数减法包含两次实数减法过程。对于实数减法，设输入X操作数X,Y操作数Y，X,Y ，且X,Y均为16位有符号数，加法得到的结果Z ,Z为17位有符号数。如果输入的X,Y操作数为和，得到的结果就是溢出的，如果将存入寄存器继续运算的话，将带来链式错误。考虑上述情况，需要 Z和X,Y具有相同的范围即，本程序采取先将X,Y均算术右移一位，即可使得Z的范围满足要求。同时考虑到，最后一位的舍入误差，在右移后，先将X,Y的最后一位进行减法运算，在考虑借位的情况下，进行主值减法。此方法的误差为不考虑末位借位的1/2，降低的误差率。 复数乘法 一次复数乘法包含四次实数乘法和二次实数加法，设输入数据， 为一次复数乘法运算的结果，其中为的实部和虚部，其绝对值都不超过1。为输入数据的实部和虚部，其均的范围。在极端情况下，假设均为，在阻止溢出的情况下，可以采取复数加减法的策略，即对进行算术右移后再进行运算，也可以预先设计的输入数格式，将通用的1.15的表示格式变成2.14的表示格式。这样，在输入均为的情况下，依然能够防止输出溢出。 序数重排 表2.3.1 N=16基二频率抽取序号重排位置序号与实际序号 输出数据位置序号 输出数据实际序号 0000 X(0) 0000 0001 X(8) 1000 0010 X(4) 0100 0011 X(12) 1100 0100 X(2) 0010 0101 X(10) 1010 0110 X(6) 0110 0111 X(14) 1110 1000 X(1) 0001 1001 X(9)