《实验六 快速傅立叶变换(FFT)的实现.doc》由会员分享，可在线阅读，更多相关《实验六 快速傅立叶变换(FFT)的实现.doc（44页珍藏版）》请在三一文库上搜索。
1、实验六 快速傅立叶变换(FFT)的实现 STM #fft_data+K_DATA_IDX_1,QX STM #K_FFT_SIZE/2-1,BRC RPTBD stage1end-1 ；QX指向参加蝶形结运算的第二个数的实部（QR） ；设置块循环计数器 ；语句重复执行的范围到地址stage1end-1处 ；延迟执行的两字节的指令（该指令不重复执行） ；BH := PR-QR ；AH := PR+QR ；PR:= (PR+QR)/2 ；QR:= (PR-QR)/2 ；AH := PI ；BH := PI-QI ；AH := PI+QI ；PI:= (PI+QI)/2 ；QI:= (PI-QI)/
2、2 ；AH := next PR STM #K_DATA_IDX_1+1,AR0 SUB *QX,16,A,B ADD *QX,16,A STH A,ASM,*PX+ ST B,*QX+ |LD *PX,A SUB *QX,16,A,B ADD *QX,16,A STH A,ASM,*PX+0% ST B,*QX+0% |LD *PX,A stage1end: ; -Stage 2 ：计算FFT的第二步，四点的FFT MVMM DATA_PROC_BUF,PX ；PX 指向参加蝶形结运算第一个数据的实部（PR） ；QX 指向参加蝶形结运算第二个数据的实部（QR） ；设置块循环计数器 ；AH :
3、= PR ；语句重复执行的范围到地址stage1end-1处 ；初始化AR0以被循环寻址 STM #fft_data+K_DATA_IDX_2,QX STM #K_FFT_SIZE/4-1,BRC LD *PX,16,A RPTBD stage2end-1 STM #K_DATA_IDX_2+1,AR0 ;以下是第二步运算的第一个蝶形结运算过程 SUB *QX,16,A,B ADD *QX,16,A ；BH := PR-QR ；AH := PR+QR ；PR:= (PR+QR)/2 ；QR:= (PR-QR)/2 126 STH A,ASM,*PX+ ST B,*QX+ |LD *PX,A ；
4、AH := PI ；BH := PI-QI ；AH := PI+QI ；PI:= (PI+QI)/2 ；QI:= (PI-QI)/2 SUB *QX,16,A,B ADD *QX,16,A STH A,ASM,*PX+ STH B,ASM,*QX+ ; 以下是第二步运算的第二个蝶形结运算过程 MAR *QX+ ；QX中的地址加一 ；AH := PR+QI ；BH := PR-QI ；PR:= (PR+QI)/2 ；AH := PI-QR ；QR:= (PR-QI)/2 ；BH := QR ；PI:= (PI-QR)/2 ；AH := PI+QR ；QI:= (PI+QR)/2 ；AH := P
5、R ADD *PX,*QX,A SUB *PX,*QX-,B STH A,ASM,*PX+ SUB *PX,*QX,A ST B,*QX |LD *QX+,B ST A, *PX |ADD *PX+0%,A ST A,*QX+0% |LD *PX,A stage2end: ; Stage 3 thru Stage logN-1：从第三步到第六步的过程如下 STM #K_TWID_TBL_SIZE,BK ST #K_TWID_IDX_3,d_twid_idx STM #K_TWID_IDX_3,AR0 STM #cos_table,WR STM #sine_table,WI ；BK = 旋转因子
6、表格的大小值 ；初始化旋转表格索引值 ；AR0 = 旋转表格初始索引值 ；初始化 WR 指针 ；初始化 WI 指针 STM #K_LOGN-2-1,STAGE_COUNTER ；初始化步骤指针 ST #K_FFT_SIZE/8-1,d_grps_cnt ；初始化组指针 ；初始化蝶形结指针 STM #K_FLY_COUNT_3-1,BUTTERFLY_COUNTER ST #K_DATA_IDX_3,d_data_idx stage: ；初始化输入数据的索引 ；以下是每一步的运算过程 127 STM #fft_data,PX LD d_data_idx, A ADD *(PX),A STLM A
7、,QX MVDK d_grps_cnt,GROUP_COUNTER group: MVMD BUTTERFLY_COUNTER,BRC RPTBD butterflyend-1 LD *WR,T MPY *QX+,A MAC *WI+0%,*QX-,A ADD *PX,16,A,B ST B,*PX |SUB *PX+,B ST B,*QX |MPY *QX+,A MAS *QX,*WR+0%,A ADD *PX,16,A,B ST B,*QX+ |SUB *PX,B LD *WR,T ST B,*PX+ |MPY *QX+,A butterflyend: ；更新指针以准备下一组蝶形结的运算
8、；PX 指向参加蝶形结运算第一个数据的实部（PR） ；QX 指向参加蝶形结运算第二个数据的实部（QR） ；AR1 是组个数计数器: ；以下是每一组的运算过程 ；将每一组中的蝶形结的个数装入BRC ；重复执行至butterflyend-1处 ；A := QR*WR | QX*QI ；A := QR*WR+QI*WI ；B := (QR*WR+QI*WI)+PR ; | QX指向QR ；PR:=(QR*WR+QI*WI)+PR)/2 ；B := PR-(QR*WR+QI*WI) ；QR:= (PR-(QR*WR+QI*WI)/2 ；A := QR*WI T=WI ; | QX指向QI ；A :=
9、QR*WI-QI*WR ；B := (QR*WI-QI*WR)+PI ；QI:=(QR*WI-QI*WR)+PI)/2 ; | QX指向QR ；B := PI-(QR*WI-QI*WR) ；T := WR ；PI:= (PI-(QR*WI-QI*WR)/2 ; | PX指向PR ；A := QR*WR | QX指向QI 128 PSHM AR0 ；保存AR0 ；AR0中装入在该步运算中每一组所用的蝶形结的数目 ；增加PX准备进行下一组的运算 MVDK d_data_idx,AR0 MAR *PX+0 MAR *QX+0 ；增加QX准备进行下一组的运算 ；当组计数器减一后不等于零时，延迟跳转至g
10、roup处 ；恢复AR0（一字节） ；修改QX以适应下一组的运算 BANZD group,*GROUP_COUNTER- POPM AR0 MAR *QX- ; ；更新指针和其他索引数据以变进入下一个步骤的运算 LD d_data_idx,A SUB #1,A,B ；B = A-1 ；修改蝶形结个数计数器 STLM B,BUTTERFLY_COUNTER STL A,1,d_data_idx LD d_grps_cnt,A STL A,-1,d_grps_cnt LD d_twid_idx,A STL A,-1,d_twid_idx ；下一步计算的数据索引翻倍 ；下一步计算的组数目减少一半 ；
11、下一步计算的旋转因子索引减少一半 BANZD stage,*STAGE_COUNTER- MVDK d_twid_idx,AR0 popm bk popm ar0 popm st0 fft_end: RET ；恢复环境变量 ；AR0 = 旋转因子索引（两字节） 第三步，分离复数FFT的输出为奇部分和偶部分 分离FFT输出为相关的四个序列：RP、RM、IP和IM，即偶实数，奇实数、偶虚数和奇虚数四部分，以便第四步形成最终结果。 利用信号分析的理论我们把Dk通过下面的公式分为偶实数RPk、奇实数 129 RMk、偶虚数IPk和奇虚数IMk： RPk = RPN-k = 0.5 * (Rk + RN
12、-k) RMk = -RMN-k = 0.5 * (Rk - RN-k) IPk = IPN-k = 0.5 * (Ik + IN-k) IMk = -IMN-k = 0.5 * (Ik - IN-k) RP0 = R0 IP0 = I0 RM0 = IM0 = RMN/2 = IMN/2 = 0 RPN/2 = RN/2 IPN/2 = IN/2 130 百度搜索“就爱阅读”,专业资料、生活学习,尽在就爱阅读网,您的在线图书馆! 实验五 快速傅立叶变换（FFT）的实现 一、 实验目的 在数字信号处理系统中，FFT作为一个非常重要的工具经常使用，甚至成为DSP运算能力的一个考核因素。FFT是一
13、种高效实现离散付氏变换的算法。离散付氏变换的目的是把信号由时域变换到频域，从而可以在频域分析处理信息，得到的结果再由付氏逆变换到时域。 本实验的目的在于学习FFT算法，及其在TMS320C54X上的实现，并通过编程掌握C54X的存储器管理、辅助寄存器的使用、位倒序寻址方式等技巧，同时练习使用CCS的探针和图形工具。另外在BIOS子目录下是一个使用DSP/BIOS工具实现FFT的程序。通过该程序，你可以使用DSP/BIOS提供的分析工具评估FFT代码执行情况。 二、 实验原理 基2按时间抽取FFT算法 对于有限长离散数字信号xn，0 ? n ? N-1，其离散谱xk可以由离散付氏变换X?k?xn
14、en?0N?1?j(2?)nkNk?0,1,.,N?1（DFT）求得。DFT的定义为 可以方便的把它改写为如下形式： 不难看出，WN是周期性的，且周期为N，即 N?1nlN?0(n?mN)(k?)nkWN?WNnkX?k?xnWNk?0,1,.,N?1m,l?0,?1,?2.WN的周期性是DFT的关键性质之一。为了强调起见，常用表达式WN取代W以便明确其周期是N。 由DFT的定义可以看出，在xn为复数序列的情况下，完全直接运算N点DFT需 116 要（N-1）2次复数乘法和N（N-1）次加法。因此，对于一些相当大的N值（如1024）来说，直接计算它的DFT所作的计算量是很大的。FFT的基本思想
15、在于，将原有的N点序列序列分成两个较短的序列，这些序列的DFT可以很简单的组合起来得到原序列的DFT。例如，若N为偶数，将原有的N点序列分成两个（N/2）点序列，那么计算N点DFT将只需要约(N/2)2 2=N2/2次复数乘法。即比直接计算少作一半乘法。因子（N/2）2表示直接计算（N/2）点DFT所需要的乘法次数，而乘数2代表必须完成两个DFT。上述处理方法可以反复使用，即（N/2）点的DFT计算也可以化成两个（N/4）点的DFT（假定N/2为偶数），从而又少作一半的乘法。这样一级一级的划分下去一直到最后就划分成两点的FFT运算的情况。比如，一个N = 8点的FFT运算按照这种方法来计算FF
16、T可以用下面的流程图来表示： x(0)W0x(1)W0x(2)W0x(3)x(4)W0x(5)W0x(6)W0x(7)W2X(7)W3X(6)W2X(5)W2X(0)X(1)X(2)W0W1X(3)X(4) 关于蝶形结运算的具体原理及其推导可以参照讲义，在此就不再赘述。 实数FFT运算 对于离散傅立叶变换（DFT）的数字计算，FFT是一种有效的方法。一般假定输入序列是复数。当实际输入是实数时，利用对称性质可以使计算DFT非常有效。 一个优化的实数FFT算法是一个组合以后的算法。原始的2N个点的实输入序列组合成一个N点的复序列，之后对复序列进行N点的FFT运算，最后再由N点的复数输出拆散成2N点
17、的复数序列，这2N点的复数序列与原始的2N点的实数输入序列的DFT输出一致。 使用这种方法，在组合输入和拆散输出的操作中，FFT运算量减半。这样利用实数FFT算法来计算实输入序列的DFT的速度几乎是一般复FFT算法的两倍。本实验就用这种方法 117 实现了一个256点实数FFT（2N = 256）运算。 实数FFT运算序列的存储分配 如何利用有限的DSP系统资源，合理的安排好算法使用的存储器是一个比较重要的问题。参见FFT实验程序的CMD文件： MEMORY PAGE 0: IPROG: origin = 0x3080, VECT: origin = 0x3000, EPROG: origin
18、 = 0x38000, PAGE 1: USERREGS: origin = 0x60, BIOSREGS: origin = 0x7c, IDATA: origin = 0x80, EDATA: origin = 0xC00, SECTIONS .vectors: VECT PAGE 0 .sysregs: BIOSREGS PAGE 1 .trcinit: IPROG PAGE 0 .gblinit: IPROG PAGE 0 .bios: IPROG PAGE 0 frt: IPROG PAGE 0 .text: IPROG PAGE 0 .cinit: IPROG PAGE 0 .pi
19、nit: IPROG PAGE 0 118 len = 0x1F80 len = 0x80 len = 0x8000 len = 0x1c len = 0x4 len = 0xB80 len = 0x1400 .sysinit: IPROG PAGE 0 .data EDATA PAGE 1 .bss: IDATA PAGE 1 .far: IDATA PAGE 1 .const: IDATA PAGE 1 .switch: IDATA PAGE 1 .sysmem: IDATA PAGE 1 .cio: IDATA PAGE 1 .MEM$obj: IDATA PAGE 1 .sysheap
20、: IDATA PAGE 1 从上面的连接定位CMD文件可以了解到，程序代码安排在0x3000开始的存储器中。其中0x3000-0x3080存放中断向量表。FFT程序使用的正弦表、余弦表数据（.data段）安排在0xc00开始的地方。变量(.bss段定义)存放在0x80开始的地址中。另外，本256点实数FFT程序的输入数据缓冲为0x2300-0x23ff，FFT后功率谱的计算结果存放在0x2200-0x22ff中。 基二实数FFT运算的算法 该算法主要分为四步： 第一步，输入数据的组合和位倒序 把输入序列作位倒序，是为了在整个运算最后的输出中得到的序列是自然顺序。首先，原始的输入的2N = 2
21、56个点的实数序列复制放到标记有“d_input_addr”的相邻单元，当成N = 128点的复数序列dn。奇数地址是dn的实部，偶数地址是dn的虚部。这个过程叫做组合（n是从0到无穷，指示时间的变量，N是常量）。然后，复数序列经过位倒序，存储在数据处理缓冲器中，标记为“fft-data”。 如图2，输入实数序列为an，n=0，1，2，3，255。分离an成两个序列，如图3所示。原始的输入序列是从地址0x2300到0x23FF，其余的从0x2200到0x22FF的是经过位倒序之后的组合序列：n=0，1，2，3，127。 dn表示复合FFT的输入，rn表示实部，in表示虚部： dn=rn+j i
22、n 119 2200h2201h2202h2203h2204h2205h2206h2207h2208h2209h220Ah220Bh22FFh2300h2301h2302h2303h2304h2305h2306h2307h2308h2309h230Ah230Bha0a1a2a3a4a5a6a7a8a9a10a1123FFha255 按位倒序的方式存储dn到数据处理缓冲中，如图2。 图2 120 百度搜索“就爱阅读”,专业资料、生活学习,尽在就爱阅读网,您的在线图书馆! 2200h2201h2202h2203h2204h2205h2206h2207h2208h2209h220Ah220Bhr0=
23、a0i0=a1r64=a128i64=a129r32=a64i32=a65r96=a192i96=a193r16=a32i16=a33r80=a160i80=a16122FEh22FFh2300h2301h2302h2303h2304h2305h2306h2307h2308h2309h230Ah230Bhr127=a254i127=a255a0a1a2a3a4a5a6a7a8a9a10a1123FEh23FFha254a255图2 * 编程技巧：在用C54x进行位倒序组合时，使用位倒序寻址方式可以大大提高程序执行的速度和使用存储器的效率。在这种寻址方式中，AR0存放的整数N是FFT点数的一半，
24、一个辅助寄存器指向一数据存放的单元。当使用位倒序寻址把AR0加到辅助寄存器中时，地址以位倒序的方式产生，即进位是从左到右，而不是从右到左。例如，当AR0 = 0x0060， 121 AR2 = 0x0040时，通过指令： MAR AR2+0B 我们就可以得到AR2位倒序寻址后的值为0x0010。 下面是0x0060（1100000）与0x0040（1000000）以位倒序方式相加的过程： 1 1 0 0 0 0 0+1 0 0 0 0 0 00 0 1 0 0 0 0 实现256点数据位倒序存储的具体程序段如下： bit_rev: STM #d_input_addr,ORIGINAL_INPU
25、T ；在AR3（ORIGINAL_INPUT）中 ；放入输入地址 ；在AR7（DATA_PROC_BUF）中 ；放入处理后输出的地址 STM #fft_data,DATA_PROC_BUF MVMM DATA_PROC_BUF,REORDERED_DATA ;AR2（REORDERED_DATA） STM #K_FFT_SIZE-1,BRC STM #K_FFT_SIZE,AR0 RPTB bit_rev_end MVDD *ORIGINAL_INPUT+,*REORDERED_DATA+ MVDD *ORIGINAL_INPUT-,*REORDERED_DATA+ ;将原始输入缓冲中的数据
26、;放入到位倒序缓冲中去之 ;后输入缓冲(AR3)指针加1 ;位倒序缓冲(AR2)指针也加 ;一 ;将原始输入缓冲中的数据 ;放入到位倒序缓冲中去之 ;后输入缓冲(AR3)指针减一 ;AR0的值是输入数据数目的一半=128 ;中装入第一个位倒序数据指针 ;位倒序缓冲(AR2)指针加一 ;以保证位倒序寻址正确 122 MAR *ORIGINAL_INPUT+0B bit_rev_end: ；按位倒序寻址方式修改AR3 注意，在上面的程序中。输入缓冲指针AR3（即ORIGINAL_INPUT）在操作时先加一再减一，是因为我们把输入数据相邻的两个字看成一个复数，在用寄存器间接寻址移动了一个复数（两个字
27、的数据）之后，对AR3进行位倒序寻址之前要把AR3的值恢复到这个复数的首字的地址，这样才能保证位倒序寻址的正确。 第二步，N点复数FFT 在数据处理缓冲器里进行N点复数FFT运算。由于在FFT运算中要用到旋转因子WN，它是一个复数。我们把它分为正弦和余弦部分，用Q15格式将它们存储在两个分离的表中。每个表中有128项，对应从0度到180度。因为采用循环寻址来对表寻址，128 = 27 根据公式 nkD?k?dnWNn?0N?1k?0,1,.,N?1 利用蝶形结对dn进行N=128点复数FFT运算，其中 ?j(2?)nkNWnkN?e?cos(2?2?nk)?jsin(nk)NN所需的正弦值和余
28、弦值分别以Q15的格式存储于内存区以0x0D00开始的正弦表和以0x0E00开始的余弦表中。我们把128点的复数FFT分为七级来算，第一级是计算两点的FFT蝶形结，第二级是计算四点的FFT蝶形结，然后是八点、十六点、三十二点六十四点、一百二十八点的蝶形结计算。最后所得的结果表示为： Dk = Fdn = Rk + j Ik 123 2200h2201h2202h2203h2204h2205h2206h2207h2208h2209h220Ah220BhR0I0R1I1R2I2R3I3R4I4R5I522FEh22FFh2300h2301h2302h2303h2304h2305h2306h2307
29、h2308h2309h230Ah230BhR127I127a0a1a2a3a4a5a6a7a8a9a10a1123FEh23FFha254a255其中，Rk、Ik分别是Dk的实部和虚部。 图3 FFT完成以后，结果序列Dk就存储到数据处理缓冲器的上半部分，如图3所示，下半部分任然保留原始的输入序列an，这半部分将在第三步中被改写。这样原始的an序列的所有DFT的信息都在Dk中了，第三步中需要做的就是就是把Dk变为最终的2N=256点复合序列，Ak=Fa(n)。 * 编程技巧：在实际的DSP的编程中为了节约程序运行时间，提高代码的效率，往往要用到并行程序指令。比如： 124 ST B,*AR3
30、|LD *AR3+,B 并行指令的执行效果是，使原本分开要两个指令周期才能执行完的两条指令在一个指令周期中中就能执行完。上述指令是将B移位（ASM-16）所决定的位数，存于AR3所指定的存储单元中，同时并行执行，将AR3所指的单元中的值装入到累加器B的高位中。由于指令的src和dst都是acc B，所以存入*AR3中的值是这条指令执行以前的值。 这一步中，实现FFT计算的具体程序如下： fft: ;-stage1 ：计算FFT的第一步，两点的FFT .asg AR1,GROUP_COUNTER .asg AR2,PX .asg AR3,QX .asg AR4,WR .asg AR5,WI ；定
31、义FFT计算的组指针 ；定义AR2为指向参加蝶形运算第一个数据的指针 ；定义AR3为指向参加蝶形运算第二个数据的指针 ；定义AR4为指向余弦表的指针 ；定义AR5为指向正弦表的指针 ；定义AR6为指向蝶形结的指针 ；定义在第一步中的数据处理缓冲指针 ；定义剩下几步中的数据处理缓冲指针 .asg AR6,BUTTERFLY_COUNTER .asg AR7,DATA_PROC_BUF .asg AR7,STAGE_COUNTER pshm st0 pshm ar0 pshm bk SSBX SXM STM #K_ZERO_BK,BK LD #-1,ASM ；保存环境变量 ；开启符号扩展模式 ；让
32、BK=0 使 *ARn+0% = *ARn+0 ；为避免溢出在每一步输出时右移一位 ；PX指向参加蝶形结运算的第一个数的实部（PR） ；AH := PR 125 MVMM DATA_PROC_BUF,PX LD *PX,16,A 百度搜索“就爱阅读”,专业资料、生活学习,尽在就爱阅读网,您的在线图书馆! 下面的图4显示了第三步完成以后存储器中的数据情况，RPk和IPk存储在2200h2201h2202h2203h2204h2205h2206h2207h2208h2209h220Ah220BhRP0=R0IP0=I0RP1IP1RP2IP2RP3IP3RP4IP4RP5IP522FEh22FFh
33、2300h2301h2302h2303h2304h2305h2306h2307h2308h2309h230Ah230BhRP127IP127a0a1IM127RM127IM126RM126IM125RM125IM124RM124IM123RM123.23FEh23FFhIM1RM1上半部分，RMk 和IMk存储在下半部分。 图4 这一过程的程序代码如下所示： unpack 131 .asg AR2,XP_k .asg AR3,XP_Nminusk .asg AR6,XM_k .asg AR7,XM_Nminusk STM #fft_data+2,XP_k ; AR2指向Rk (temp RPk
34、) ; AR3指向 RN-K (temp RPN-K) STM #fft_data+2*K_FFT_SIZE-2,XP_Nminusk STM #fft_data+2*K_FFT_SIZE+3,XM_Nminusk ; AR7指向 temp RMN-K STM #fft_data+4*K_FFT_SIZE-1,XM_k STM #-2+K_FFT_SIZE/2,BRC RPTBD phase3end-1 ; AR6指向temp RMK ; 设置块循环计数器 ; 从以下指令到phase3end-1处一直 ; 重复执行BRC中规定的次数 STM #3,AR0 ; 设置AR0以备下面程序寻址使用 ;
35、 A := Rk+RN-K = 2*RPk ; B := Rk-RN-K= 2*RMk ; 在ARk处存储RPk ; 在ARN-K处存储RPN-K=RPk ; 在AI2N-K处存储RMk ; B := RN-K-Rk =2*RMN-K ; 在AIN+k处存储RMN-K ; A := Ik+IN-K = 2*IPk ; B := Ik-IN-K =2*IMk ; 在AIk处存储IPk ; 在AIN-K处存储IPN-K=IPk ; 在AR2N-K处存储IMk ; B := IN-K-Ik =2*IMN-K ; 在ARN+k处存储IMN-K ADD *XP_k,*XP_Nminusk,A SUB *
36、XP_k,*XP_Nminusk,B STH A,ASM,*XP_k+ STH A,ASM,*XP_Nminusk+ STH B,ASM,*XM_k- NEG B STH B,ASM,*XM_Nminusk- ADD *XP_k,*XP_Nminusk,A SUB *XP_k,*XP_Nminusk,B STH A,ASM,*XP_k+ STH A,ASM,*XP_Nminusk-0 STH B,ASM,*XM_k- NEG B STH B,ASM,*XM_Nminusk+0 phase3end: 第四步，产生最后的N = 256点的复数FFT结果 132 产生2N = 256个点的复数输出，它与原始的256个点的实输入序列的DFT一致。输出驻留在数据缓冲器中。 通过下面的公式由RPk、RMn、IPn和IMn四个序列可以计算出an的DFT： ARk = AR2N-k = RPk + cos(k/N) * IPk - sin(k/N) * RMk AIk = -AI2N-k = IMk - cos(k/N) * RMk - sin(k/N) * IPk AR0 = RP0 + IP0 AI0 = IM0 - RM0 ARN