快速傅立叶变换(FFT)算法-DSP实验

快速傅立叶变换快速傅立叶变换 FFT 算法实验算法实验 摘要摘要 FFT Fast Fourier Transformation 即为快速傅里叶变换 是 离散傅里叶变换的快速算法 它是根据离散傅里叶变换的奇 偶 虚 实等特性 对离散傅立叶变换的算法进行改进获得的 这种算 法大大减少了变换中的运算量 使得其在数字信号处理中有了广泛 的运用 本实验主要要求掌握在 CCS 环境下用窗函数法设计 FFT 快 速傅里叶的原理和方法 并且熟悉 FFT 快速傅里叶特性 以及通过 本次试验了解各种窗函数对快速傅里叶特性的影响等 引言 引言 快速傅里叶变换 FFT 是离散傅里叶变换 DFT 的一种快速算法 起初 DFT 的计算在数字信号处理中就非常有用 但由于计算量太大 即使采用计算机也很难对问题进行实时处理 所以并没有得到真正 的运用 1965 年 J W 库利和 T W 图基提出快速傅里叶变换 采用这 种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少 特别是被变换的抽样点数 N 越多 FFT 算法计算量的节省就越显著 从此 对快速傅里叶变换 FFT 算法的研究便不断深入 数字信号 处理这门新兴学科也随 FFT 的出现和发展而迅速发展 根据对序列 分解与选取方法的不同而产生了 FFT 的多种算法 基本算法是基 2DIT 和基 2DIF FFT 的出现 使信号分析从时域分析向频域分析成 为可能 极大地推动了信号分析在各领域的实际应用 FFT 在离散傅 里叶反变换 线性卷积和线性相关等方面也有重要应用 一 一 实验原理 实验原理 FFT 并不是一种新的变换 它是离散傅立叶变换 DFT 的一种 快速算法 由于我们在计算 DFT 时一次复数乘法需用四次实数乘法 和二次实数加法 一次复数加法则需二次实数加法 每运算一个 X k 需要 4N 次复数乘法及 2N 2 N 1 2 2N 1 次实数加法 所以整个 DFT 运算总共需要 4N 2 次实数乘法和 N 2 2N 1 2N 2N 1 次实数加法 如此一来 计算时乘法次数和加法次数都是和 N 2 成 正比的 当 N 很大时 运算量是可观的 因而需要改进对 DFT 的算 法减少运算速度 根据傅立叶变换的对称性和周期性 我们可以将 DFT 运算中有 些项合并 我们先设序列长度为 N 2 L L 为整数 将 N 2 L 的序列 x n n 0 1 N 1 按 N 的奇偶分成两组 也就是说我们将一个 N 点的 DFT 分解成两个 N 2 点的 DFT 他们又从新组合成一个如下 式所表达的 N 点 DFT 12 0 12 12 0 2 为奇为偶 1 0 12 2 10 N r kr N N r rk N n nk N n nk N N n nk N WrxWrx WnxWnx NkWnxnxDFTkX 12 2 21 12 0 22 12 0 21 12 0 2 2 12 0 2 1 12 0 2 12 0 2 kXWkX WnxWWnx WnxWWnx WrxWWrx k N N n nk N k N N n nk N N n nk N k N N n nk N N r rk N k N N r rk N 其中 12 0 222 12 0 211 N n nk N N n nk N WnxkX WnxkX 1 2 0 N k 设 x n 为 N 项的复数序列 由 DFT 变换 任一 X m 的计算 都需要 N 次复数乘法和 N 1 次复数加法 而一次复数乘法等于四次 实数乘法和两次实数加法 一次复数加法等于两次实数加法 即使 把一次复数乘法和一次复数加法定义成一次 运算 四次实数乘法 和四次实数加法 那么求出 N 项复数序列的 X m 即 N 点 DFT 变换大约就需要 N 2 次运算 当 N 1024 点甚至更多的时候 需要 N2 次运算 在 FFT 中 利用 WN 的周期性和对称性 把一个 N 项 序列 设 N 2k k 为正整数 分为两个 N 2 项的子序列 每个 N 2 点 DFT 变换需要 N 2 2 次运算 再用 N 次运算把两个 N 2 点的 DFT 变换组合成一个 N 点的 DFT 变换 这样变换以后 总的运算次 数就变成 N 2 N 2 2 N N 2 2 继续上面的例子 N 1024 时 总的运算次数就变成了次 节省了大约 50 的运算量 而如果我们 将这种 一分为二 的思想不断进行下去 直到分成两两一组的 DFT 运算单元 那么 N 点的 DFT 变换就只需要 Nlog2N 次的运算 N 在 1024 点时 运算量仅有 10240 次 是先前的直接算法的 1 点 数越多 运算量的节约就越大 这就是 FFT 的优越性 8 点 DFT 的 FFT 运算流图 计算离散傅里叶变换的快速方法 有按时间抽取的 FFT 算法和 按频率抽取的 FFT 算法 前者是将时域信号序列按偶奇分排 后者 是将频域信号序列按偶奇分排 它们都借助于的两个特点 一是的 周期性 另一是的对称性 这里符号 代表其共轭 这样 便可以把 离散傅里叶变换的计算分成若干步进行 计算效率大为提高 时间抽取算法 令信号序列的长度为 N 2 其中 M 是正整数 可以将时域信号序列 x n 分解成两部分 一是偶数部分 x 2n 另 一是奇数部分 x 2n 1 其中 于是信号序列 x n 的离散傅里叶 变换可以用两个 N 2 抽样点的离散傅里叶变换来表示和计算 一个抽样点数为 N 的信号序列 x n 的离散傅里叶变换 可以 由两个 N 2 抽样点序列的离散傅里叶变换求出 依此类推 这种按 时间抽取算法是将输入信号序列分成越来越小的子序列进行离散傅 里叶变换计算 最后合成为 N 点的离散傅里叶变换 N 2 点的离散傅里叶变换的计算全由蝶形运算组成 需要 M 级运算 每级包括 N 2 个蝶形运算 总共有 个蝶形运算 所以 总的计算量为次复数乘法运算和 N log2N 次复数加法运算 FFT 算法按级迭代进行 N 抽样点的输入信号具有 N 个原 始数据 x0 n 经第一级运算后 得出新的 N 个数据 x1 n 再经过 第二级迭代运算 又得到另外 N 个数据 x2 n 依此类推 直至最后 的结果 x k xM k X k 在逐级迭代计算中 每个蝶形运算的输出数 据存放在原来存贮输入数据的单元中 实行所谓 即位计算 这样 可以节省大量存放中间数据的寄存器 蝶形运算中加权系数随迭代级数成倍增加 对于 N 8 M 3 情况 需进行三级迭代运算 在第一级迭代中 只用到一种加权系 数 蝶形运算的跨度间隔等于 1 在第二级迭代中 用到两种加权 系数即 蝶形运算的跨度间隔等于 2 在第三级迭代中 用到 4 种 不同的加权系数即 蝶形运算的跨度间隔等于 4 可见 每级迭 代的不同加权系数的数目比前一级迭代增加一倍 跨度间隔也增大 一倍 输入数据序列 x n 需重新排列为 x 0 x x x x x x x 这是按照二进制数的码位倒 置所得到的反序数 例如 N 8 中数 1 的二进制数为 001 将 其码位倒转变为 100 即为十进制数 4 频率抽取算法 按频率抽取的 FFT 算法是将频域信号序列 X k 分解为奇偶两部分 但算法仍是由时域信号序列开始逐级运算 同样是把 N 点分成 N 2 点计算 FFT 可以把直接计算离散傅里叶变 换所需的 N 次乘法缩减到 N 2 次 频率信号序列 X 2l 是时间信号序列 x1 n x2 n 的 N 2 点离 散傅里叶变换 频率信号序列 X 2l 1 是时间信号序列 x1 n x2 n 的 N 2 点离散傅里叶变换 因此 N 点离散傅里叶变换的计 算 通过两次加 减 法和一次乘法 从原来序列获得两个子序列 所以 频率抽取算法也具有蝶形运算形式 其计算量完全和时间抽 取算法一样 即只需次乘法运算和 Nlog2N 次加 减 法运算 实际上 频率抽取算法与时间抽取算法的信号流图之间存在着 转置关系 如将流图适当变形 可以得出多种几何形状 除了基 2 的 FFT 算法之外 还有基 4 基 8 等高基数的 FFT 算法以及任意数为 基数的 FFT 算法 二 二 硬件框图 硬件框图 数字信号处理 实验室教学实验箱结构图 教学实验箱结构图 F2812 A 评估板原理框图 F2812 A 评估板实物图 DSP 教学实验箱的硬件连接 1 连接电源 打开实验箱 取出三相电源连接线 如右 图 将电源线的一端插入实验箱外部左恻箱壁上的电源 插孔中 确认实验箱面板上电源总开关 位于实验箱底板左上角 处于 关 的位置 连接电源线的另一端至 220V 交流供电插座上 保证 稳固连接 2 使用电源连接线 如右图 插头是带孔的 连接各模块 电源 确认实验箱总电源断开 连接 ICETEK CTR 板上边 插座到实验箱底板上 12V 电源插座 ICETEK CTR 板下边 插座到实验箱底板上 5V 电源插座 如使用 PP 并口 型 仿真器 则连接仿真器上插座到实验箱底板上 5V 电源插座连接 DSP 评估板模块电源插座到实验箱底板上 5V 电源插座 注意各插 头要插到底 防止虚接或接触不良 3 连接 DSP 评估板信号线 当需要连接信号源输出到 A D 输入插 座 时 使用信号连接线 如右图 分别连接相应插座 4 接通电源 检查实验箱上 220V 电源插座 箱体左侧 中保险管是 否完好 在连接电源线以后 检查各模块供电连线是否正确连接 打开实验箱上的电源总开关 位于实验箱底板左上角 使开关位于 开 的位置 电源开关右侧的指示灯亮 三 三 软件流程图 软件流程图 开始 初始化工作变量 调用波形发生子程序产 生波形 3 个正弦波 调用 FFT 子程序 计算功率谱 波形发生 计算步长 用标准 C 的 sin 函数计算 当前波形值 128 点 结束 FFT 按照编码逆序排列输入 序列 返回计算结果 用蝶形算法计算 计算功率谱 五 五 调试过程和步骤 调试过程和步骤 I 软件调试 1 实验准备 设置软件仿真模式 启动 CCS 2 打开工程 浏览程序 工程目录为 D dsp t7 fft fft pjt 3 编译并下载程序 4 打开观察窗口 选择菜单 View Graph Time Frequency 进行如下图所示设 置 选择菜单 View Graph Time Frequency 进行如下图所示设置 选择菜单 View Graph Time Frequency 进行如下图所示设置 5 清除显示 在以上打开的窗口中单击鼠标右键 选择弹出式菜 单中 Clear Display 功能 6 设置断点 在程序 FFT c 中有注释 break point 的语句上设 置软件断点 7 运行并观察结果 选择 Debug 菜单的 Animate 项 或按 F12 键运行程序 观察 FFT 窗口中时域和频域图形 注意 由于实验运算复杂 需要等一会才能看到运行完结果 8 退出 CCS II 硬件连接 1 实验准备 连接实验设备 准备信号源进行 AD 输入 取出 2 根实验箱附带的信号线 如右图 两端均为单声道语音 插头 用 1 根信号线连接实验箱左侧信号源的波形输出 A 端口和 A D 输入 模块的 ADCIN0 插座注意插头要插牢 到底 这样 信号源波形输出 A 的输出波形即可送到 ICETEK F2812A 板的 AD 输入通道 0 用 1 根信号线连接实验箱左侧信号源的波形输出 B 端口和 A D 输入 模块的 ADCIN1 插座注意插头要插牢 到底 这样 信号源波形输出 B 的输出波形即可送到 ICETEK F2812A 板的 AD 输入通道 1 设置波形输出 A 向内侧按波形频率选择旋钮 直到标有正弦波的指示灯点亮 上下调节波形频率选择旋钮 直到标有 100 1KHz 的指示 灯点亮 调节幅值调整旋钮 将波形输出 A 的幅值调到适当位置 设置波形输出 B 向内侧按波形频率选择旋钮 直到标有正弦波的指示灯点亮 上下调节波形频率选择旋钮 直到标有 1K 10KHz 的指示 灯点亮 调节幅值调整旋钮 将波形输出 B 的幅值调到适当位置 注意 由于模数输入信号未经任何转换就进入 DSP 所以必须 保证输入的模拟信号的幅度在 0 3V 之间 必须用示波器检测信 号范围 保证最小值 0V 最大值 3 V 否则容易损坏 DSP 芯片的 模数采集模块 2 设置 Code Composer Studio 2 21 在硬件仿真 Emulator 方式下运 行 3 启动 Code Composer Studio 2 21 选择菜单 Debug Reset CPU 4 打开工程文件 工程目录 D dsp t8 mixerfft mixerfft pjt 5 编译 下载程序 6 运行程序观察结果 按 CTR 控制板的 K6 键 可以显示 A B 两信号源频谱 K7 键实现混频显示 按 K8 实现键 A B 两信号源分屏显示 7 退出 CCS 六 六 实验结果 实验结果 七 七 结果分析 结果分析 通过观察软件仿真结果中 FFT 窗口的时域图形和频域图形 可知 由上述程序所计算出的测试波形的功率谱与 CCS 计算出的 快速傅里叶变换的结果相近 通过硬件仿真结果可知 按 CTR 控 制板的 K6 键 可以显示出 A B 两信号源频谱 按 K7 键可以实 现混频显示 按 K8 实现键 A B 两信号源分屏显示 八 八 结束语 结束语 通过这次实验更加深刻地理解了快速傅里叶变换的物理意义 并且掌握了用窗函数法设计 FFT 快速傅里叶变换的原理和方法 进 一步熟悉了 FFT 快速傅里叶变换特性 通过对快速傅里叶变换的实 际应用了解了各种窗函数对快速傅里叶变换特性的影响 本科学习期间 通过学习数字信号处理了解到快速傅里叶变换 的知识 但当时仅限于对其理论层面的理解 通过这次实验 加强 了自己动手能力的锻炼 使自己进一步认识到理论知识与实践结合 起来的重要性 从而为自己以后的学习工作提供良好的发展方向 DSP 原理与应用 这门课程在介绍 DSPs 芯片特点和应用的基 础上 以 TI 公司 C28x 系列的 TMS320F2812 芯片为描述对象 系统 的介绍了 DSPs 芯片的基本特点 硬件结构 工作原理 开发环境 和使用方法 其中包括 CPU 内部结构 时钟和系统控制 存储空 间及通用 I O 接口 中断管理方式 片内外设 寻址方式和指令系 统 以及本实验所用到的集成开发环境 CCS DSP 最小系统和相应 的软件设计 通过学习 DSP 原理与应用 我基本掌握了 DSPs 芯片的主要 知识体系 并且通过上课老师的实物讲解和课本概念的联系 结合 理论知识和实际应用 基本建立了 DSP 系统的基本概念与逻辑概念 物理概念之间的联系 同时通过这次实验进一步把 DSPs 的基本概 念和原理应用到了实际的 DSP 系统中 九 九 程序附录 程序附录 C 语言程序代码 语言程序代码 程序 1 include DSP281x Device h DSP281x Headerfile Include File include DSP281x Examples h DSP281x Examples Include File include f2812a h include math h define PI 3 define SAMPLENUMBER 128 void InitForFFT void MakeWave void FFT float dataR SAMPLENUMBER float dataI SAMPLENUMBER int INPUT SAMPLENUMBER DATA SAMPLENUMBER float fWaveR SAMPLENUMBER fWaveI SAMPLENUMBER w SAMPLENUMBE R float sin tab SAMPLENUMBER cos tab SAMPLENUMBER void FFT float dataR SAMPLENUMBER float dataI SAMPLENUMBER int x0 x1 x2 x3 x4 x5 x6 xx int i j k b p L float TR TI temp following code invert sequence for i 0 i SAMPLENUMBER i x0 x1 x2 x3 x4 x5 x6 0 x0 i x1 i 2 x2 i 4 x3 i 8 x4 i 16 x5 i 32 x6 i 64 xx x0 64 x1 32 x2 16 x3 8 x4 4 x5 2 x6 dataI xx dataR i for i 0 i SAMPLENUMBER i dataR i dataI i dataI i 0 following code FFT for L 1 L0 b b 2 i b 2 L 1 for j 0 j0 p pow 2 7 L j p p 2 i p p j for k j k 128 k k 2 b for 3 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 END for 3 END for 2 END for 1 for i 0 i SAMPLENUMBER 2 i w i sqrt dataR i dataR i dataI i dataI i END FFT main int i InitForFFT MakeWave for i 0 i SAMPLENUMBER i fWaveR i INPUT i fWaveI i 0 0f w i 0 0f FFT fWaveR fWaveI for i 0 i SAMPLENUMBER i DATA i w i while 1 break point void InitForFFT int i for i 0 i SAMPLENUMBER i sin tab i sin PI 2 i SAMPLENUMBER cos tab i cos PI 2 i SAMPLENUMBER void MakeWave int i for i 0 i SAMPLENUMBER i INPUT i sin PI 2 i SAMPLENUMBER 3 1024 程序 2 include DSP281x Device h DSP281x Headerfile Include File include DSP281x Examples h DSP281x Examples Include File include f2812a h include LCD h include math h define ADCNUMBER 300 Prototype statements for functions found within this file interrupt void adc isr void void Delay unsigned int nDelay struct struLCDGraph struGraph struGraph1 unsigned int nScreenBuffer 30 128 Global variables used in this example Uint16 LoopCount Uint16 ConversionCount Uint16 Voltage1 1024 Uint16 Voltage2 1024 Uint16 Voltage 1 Voltage 2 flage 0 Uint16 nGraphBuf1 ADCNUMBER nGraphBuf2 ADCNUMBER int nGraphBuf3 ADCNUMBER int ci 0 keyflage nAD Uint16 nMixing 1024 液晶 define CTRLED unsigned int 0 x port8004 define MCTRKEY unsigned int 0 x port8005 define CTRCLKEY unsigned int 0 x port8006 define CTRSTATUS unsigned int 0 x port8000 define pi 3 int nModeAD Uint16 ad1 ad2 define PI 3 define SAMPLENUMBER 128 int INPUT SAMPLENUMBER DATA SAMPLENUMBER int nGraphBuf1 ADCNUMBER nGraphBuf2 ADCNUMBER float fWaveR SAMPLENUMBER fWaveI SAMPLENUMBER float sin tab SAMPLENUMBER cos tab SAMPLENUMBER float fDataR SAMPLENUMBER fDataI SAMPLENUMBER w SAMPLENUMBER void FFT float dataR SAMPLENUMBER float dataI SAMPLENUMBER void InitForFFT void MakeWave int j a 0 main int j uWork uWork1 unsigned int pWork InitSysCtrl 初始化 cpu InitPll 0 x5 DINT 关中断 LCDTurnOff LCDSetScreenBuffer nScreenBuffer for uWork 0 pWork nScreenBuffer uWork 30 128 uWork pWork pWork 0 LCDSetDelay 0 LCDTurnOn 打开显示 LCDCLS 清除显示内存 InitXintf InitPieCtrl 初始化 pie 寄存器 for j 0 j 1024 j Voltage1 j 0 Voltage2 j 0 IER 0 x0000 禁止所有的中断 IFR 0 x0000 InitPieVectTable 初始化 pie 中断向量表 Interrupts that are used in this example are re mapped to ISR functions found within this file EALLOW This is needed to write to EALLOW protected register PieVectTable ADCINT EDIS This is needed to disable write to EALLOW protected registers AdcRegs ADCTRL1 bit RESET 1 Reset the ADC module asm RPT 10 NOP Must wait 12 cycles worst case for ADC reset to take effect AdcRegs ADCTRL3 all 0 x00C8 first power up ref and bandgap circuits AdcRegs ADCTRL3 bit ADCBGRFDN 0 x3 Power up bandgap reference circuitry AdcRegs ADCTRL3 bit ADCPWDN 1 Power up rest of ADC Enable ADCINT in PIE PieCtrlRegs PIEIER1 bit INTx6 1 IER M INT1 Enable CPU Interrupt 1 EINT Enable Global interrupt INTM ERTM Enable Global realtime interrupt DBGM LoopCount 0 ConversionCount 0 Configure ADC AdcRegs ADCMAXCONV all 0 x0001 Setup 2 conv s on SEQ1 AdcRegs ADCCHSELSEQ1 bit CONV00 0 x0 Setup ADCINA3 as 1st SEQ1 conv AdcRegs ADCCHSELSEQ1 bit CONV01 0 x1 Setup ADCINA2 as 2nd SEQ1 conv AdcRegs ADCTRL2 bit EVA SOC SEQ1 1 Enable EVASOC to start SEQ1 AdcRegs ADCTRL2 bit INT ENA SEQ1 1 Enable SEQ1 interrupt every EOS Configure EVA Assumes EVA Clock is already enabled in InitSysCtrl EvaRegs T1CMPR 0 x0080 Setup T1 compare value EvaRegs T1PR 0 x5000 Setup period register EvaRegs GPTCONA bit T1TOADC 1 Enable EVASOC in EVA EvaRegs T1CON all 0 x1042 Enable timer 1 compare upcount mode struGraph uLineMode LINEMODE LCDDrawGraph struGraph keyflage 0 InitForFFT Wait for ADC interrupt for j 0 uWork1 MCTRKEY uWork1 CTRCLKEY 0 if uWork1 128 keyflage 0 if uWork1 64 keyflage 1 if uWork1 32 keyflage 2 if flage 1 flage 0 LCDSetScreenBuffer nScreenBuffer LCDCLS 清除显示内存 if keyflage 0 struGraph pData Voltage2 struGraph uDataMode DATAUINTMODE struGraph uDataLength 256 struGraph uMaxValue 2048 struGraph uWindowX0 0 struGraph uWindowY0 0 struGraph uWindowX1 240 struGraph uWindowY1 128 struGraph nOriginX 0 struGraph nOriginY 0 struGraph uLineMode LINEMODE LCDGraph struGraph uLineMode LINEMODE struGraph pData Voltage1 struGraph uDataMode DATAUINTMODE struGraph uDataLength 256 struGraph uMaxValue 1024 struGraph uWindowX0 0 struGraph uWindowY0 0 struGraph uWindowX1 240 struGraph uWindowY1 128 struGraph nOriginX 0 struGraph nOriginY 64 struGraph uLineMode LINEMODE LCDGraph for j 0 j 20 j Delay 414 LCDSetScreenBuffer nScreenBuffer LCDCLS 清除显示内存 if keyflage 1 struGraph pData nMixing struGraph uDataMode DATAUINTMODE struGraph uDataLength 256 struGraph uMaxValue 2048 struGraph uWindowX0 0 struGraph uWindowY0 0 struGraph uWindowX1 240 struGraph uWindowY1 128 struGraph nOriginX 0 struGraph nOriginY 0 struGraph uLineMode LINEMODE LCDGraph for j 0 j 20 j Delay 414 LCDSetScreenBuffer nScreenBuffer LCDCLS if keyflage 2 InitForFFT for j 0 j SAMPLENUMBER j fDataR j Voltage1 j Voltage2 j 2 0 fDataI j 0 w j 0 FFT fDataR fDataI for j 0 j SAMPLENUMBER j DATA j w j struGraph pData DATA struGraph pData nGraphBuf3 20 struGraph uDataMode DATAUINTMODE struGraph uDataLength 128 struGraph uMaxValue 20000 struGraph uWindowX0 0 struGraph uWindowY0 0 struGraph uWindowX1 240 struGraph uWindowY1 128 struGraph nOriginX 0 struGraph nOriginY 0 struGraph uLineMode LINEMODE LCDGraph for j 0 j 4 Voltage 2 Voltage2 ConversionCount AdcRegs ADCRESULT1 4 Voltage1 ConversionCount Voltage1 ConversionCount 4 Voltage2 ConversionCount Voltage2 ConversionCount 4 nMixing ConversionCount Voltage1 ConversionCount Voltage2 Conve rsionCount If 40 conversions have been logged start over if ConversionCount 300 ConversionCount 0 flage 1 else ConversionCount nGraphBuf1 ConversionCount Voltage1 ConversionCount nGraphBuf2 ConversionCount Voltage2 ConversionCount Reinitialize for next ADC sequence AdcRegs ADCTRL2 bit RST SEQ1 1 Reset SEQ1 AdcRegs ADCST bit INT SEQ1 CLR 1 Clear INT SEQ1 bit PieCtrlRegs PIEACK all PIEACK GROUP1 Acknowledge interrupt to PIE return void FFT float dataR SAMPLENUMBER float dataI SAMPLENUMBER int x0 x1 x2 x3 x4 x5 x6 xx int i j k b p L float TR TI temp following code invert sequence for i 0 i SAMPLENUMBER i x0 x1 x2 x3 x4 x5 x6 0 x0 i x1 i 2 x2 i 4 x3 i 8 x4 i 16 x5 i 32 x6 i 64 xx x0 64 x1 32 x2 16 x3 8 x4 4 x5 2 x6 dataI xx dataR i for i 0 i SAMPLENUMBER i dataR i dataI i dataI i 0 following code FFT for L 1 L0 b b 2 i b 2 L 1 for j 0 j0 p pow 2 7 L j p p 2 i p p j for k j k 128 k k 2 b for 3 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 END for 3 END for 2 END for 1 for i 0 i SAMPLENUMBER 2 i w i sqrt dataR i dataR i dataI i dataI i END FFT void InitForFFT int i for i 0 i SAMPLENUMBER i sin tab i sin PI 2 i SAMPLENUMBER cos tab i cos PI 2 i SAMPLENUMBER 汇编语言程序 汇编语言程序 k stack size set 10 K DATA IDX 1 set 2 K DATA IDX 2 set 4 K DATA IDX 3 set 8 K TWID TBL SIZE set 512 K TWID IDX 3 set 128 K FLY COUNT 3 set 4 K FFT SIZE set 32 N 32 K LOGN set 5 log N log 32 5 PA0 set 0 PA1 set 1 sine usect sine 512 cosine usect cosine 512 fft data usect fft data 2048 d input usect d input 2048 fft out usect fft out 1024 k stack usect STACK k stack size k stack bottorm set k stack k stack size bss d twid idx 1 bss d data idx 1 bss d grps cnt 1 sect fft prg text copy coeff inc Bit Reversal Routine asg AR2 REORDERED asg AR3 ORIGINAL INPUT asg AR7 DATA PROC BUF c int00 start SSBX FRCT STM k stack bottorm SP STM d input AR1 从 PA1 口输入 2N 个数据 RPT 2 K FFT SIZE 1 PORTR PA1 AR1 这部分改为伪 采样数据 STM sine AR1 RPT 511 MVPD sinel AR1 STM cosine AR1 RPT 511 MVPD cosinel AR1 STM d input ORIGINAL INPUT STM fft data DATA PROC BUF MVMM DATA PROC BUF REORDERED STM K FFT SIZE 1 BRC RPTBD bit rev end 1 位倒序 STM K FFT SIZE AR0 MVDD ORIGINAL INPUT REORDERED MVDD ORIGINAL INPUT REORDERED MAR ORIGINAL INPUT 0B bit rev end FFT Code asg AR1 GROUP COUNTER asg AR2 PX asg AR3 QX asg AR4 WR asg AR5 WI asg AR6 BUTTERFLY COUNTER asg AR7 STAGE COUNTER stage1 STM 0 BK LD 1 ASM STM fft data PX LD PX 16 A STM fft data K