快速傅立葉變換(FFT)實(shí)現(xiàn)

1、電子科技大學(xué)通信與信息工程學(xué)院標(biāo) 準(zhǔn) 實(shí) 驗(yàn) 報(bào) 告（實(shí)驗(yàn)）課程名稱 DSP設(shè)計(jì)與實(shí)踐 電子科技大學(xué)教務(wù)處制表電 子 科 技 大 學(xué)實(shí) 驗(yàn) 報(bào) 告學(xué)生姓名： 學(xué) 號(hào) 指導(dǎo)教師：實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)時(shí)間：一、實(shí)驗(yàn)室名稱： 科B341 二、實(shí)驗(yàn)項(xiàng)目名稱：快速傅立葉變換（FFT）的實(shí)現(xiàn)三、實(shí)驗(yàn)學(xué)時(shí)：4四、實(shí)驗(yàn)原理：基2按時(shí)間抽取FFT算法對(duì)于有限長(zhǎng)離散數(shù)字信號(hào)xn，0 £ n £ N-1，其離散譜xk可以由離散付氏變換（DFT）求得。DFT的定義為可以方便的把它改寫為如下形式：不難看出，WN是周期性的，且周期為N，即WN的周期性是DFT的關(guān)鍵性質(zhì)之一。為了強(qiáng)調(diào)起見，常用表達(dá)式WN取代

2、W以便明確其周期是N。由DFT的定義可以看出，在xn為復(fù)數(shù)序列的情況下，完全直接運(yùn)算N點(diǎn)DFT需要（N-1）2次復(fù)數(shù)乘法和N（N-1）次加法。因此，對(duì)于一些相當(dāng)大的N值（如1024）來說，直接計(jì)算它的DFT所作的計(jì)算量是很大的。FFT的基本思想在于，將原有的N點(diǎn)序列序列分成兩個(gè)較短的序列，這些序列的DFT可以很簡(jiǎn)單的組合起來得到原序列的DFT。例如，若N為偶數(shù)，將原有的N點(diǎn)序列分成兩個(gè)（N/2）點(diǎn)序列，那么計(jì)算N點(diǎn)DFT將只需要約(N/2)2 ·2=N2/2次復(fù)數(shù)乘法。即比直接計(jì)算少作一半乘法。因子（N/2）2表示直接計(jì)算（N/2）點(diǎn)DFT所需要的乘法次數(shù)，而乘數(shù)2代表必須完成兩個(gè)D

3、FT。上述處理方法可以反復(fù)使用，即（N/2）點(diǎn)的DFT計(jì)算也可以化成兩個(gè)（N/4）點(diǎn)的DFT（假定N/2為偶數(shù)），從而又少作一半的乘法。這樣一級(jí)一級(jí)的劃分下去一直到最后就劃分成兩點(diǎn)的FFT運(yùn)算的情況。比如，一個(gè)N = 8點(diǎn)的FFT運(yùn)算按照這種方法來計(jì)算FFT可以用下面的流程圖來表示：關(guān)于蝶形結(jié)運(yùn)算的具體原理及其推導(dǎo)可以參照講義，在此就不再贅述。實(shí)數(shù)FFT運(yùn)算 對(duì)于離散傅立葉變換（DFT）的數(shù)字計(jì)算，F(xiàn)FT是一種有效的方法。一般假定輸入序列是復(fù)數(shù)。當(dāng)實(shí)際輸入是實(shí)數(shù)時(shí)，利用對(duì)稱性質(zhì)可以使計(jì)算DFT非常有效。 一個(gè)優(yōu)化的實(shí)數(shù)FFT算法是一個(gè)組合以后的算法。原始的2N個(gè)點(diǎn)的實(shí)輸入序列組合成一個(gè)N點(diǎn)的復(fù)

4、序列，之后對(duì)復(fù)序列進(jìn)行N點(diǎn)的FFT運(yùn)算，最后再由N點(diǎn)的復(fù)數(shù)輸出拆散成2N點(diǎn)的復(fù)數(shù)序列，這2N點(diǎn)的復(fù)數(shù)序列與原始的2N點(diǎn)的實(shí)數(shù)輸入序列的DFT輸出一致。使用這種方法，在組合輸入和拆散輸出的操作中，F(xiàn)FT運(yùn)算量減半。這樣利用實(shí)數(shù)FFT算法來計(jì)算實(shí)輸入序列的DFT的速度幾乎是一般復(fù)FFT算法的兩倍。本實(shí)驗(yàn)就用這種方法實(shí)現(xiàn)了一個(gè)256點(diǎn)實(shí)數(shù)FFT（2N = 256）運(yùn)算。 實(shí)數(shù)FFT運(yùn)算序列的存儲(chǔ)分配如何利用有限的DSP系統(tǒng)資源，合理的安排好算法使用的存儲(chǔ)器是一個(gè)比較重要的問題。參見FFT實(shí)驗(yàn)程序的CMD文件：MEMORY PAGE 0: IPROG: origin = 0x3080, len = 0

5、x1F80 VECT: origin = 0x3000, len = 0x80 EPROG: origin = 0x38000, len = 0x8000 PAGE 1: USERREGS: origin = 0x60, len = 0x1c BIOSREGS: origin = 0x7c, len = 0x4 IDATA: origin = 0x80, len = 0xB80 EDATA: origin = 0xC00, len = 0x1400 SECTIONS .vectors: > VECT PAGE 0 .sysregs: > BIOSREGS PAGE 1 .trcin

6、it: > IPROG PAGE 0 .gblinit: > IPROG PAGE 0 .bios: > IPROG PAGE 0 frt: > IPROG PAGE 0 .text: > IPROG PAGE 0 .cinit: > IPROG PAGE 0 .pinit: > IPROG PAGE 0 .sysinit: > IPROG PAGE 0 .data > EDATA PAGE 1 .bss: > IDATA PAGE 1 .far: > IDATA PAGE 1 .const: > IDATA PAGE 1

7、 .switch: > IDATA PAGE 1 .sysmem: > IDATA PAGE 1 .cio: > IDATA PAGE 1 .MEM$obj: > IDATA PAGE 1 .sysheap: > IDATA PAGE 1從上面的連接定位CMD文件可以了解到，程序代碼安排在0x3000開始的存儲(chǔ)器中。其中0x3000-0x3080存放中斷向量表。FFT程序使用的正弦表、余弦表數(shù)據(jù)（.data段）安排在0xc00開始的地方。變量(.bss段定義)存放在0x80開始的地址中。另外，本256點(diǎn)實(shí)數(shù)FFT程序的輸入數(shù)據(jù)緩沖為0x2300-0x23ff，F(xiàn)F

8、T后功率譜的計(jì)算結(jié)果存放在0x2200-0x22ff中。 基二實(shí)數(shù)FFT運(yùn)算的算法該算法主要分為四步：第一步，輸入數(shù)據(jù)的組合和位倒序 把輸入序列作位倒序，是為了在整個(gè)運(yùn)算最后的輸出中得到的序列是自然順序。首先，原始的輸入的2N = 256個(gè)點(diǎn)的實(shí)數(shù)序列復(fù)制放到標(biāo)記有“d_input_addr”的相鄰單元，當(dāng)成N = 128點(diǎn)的復(fù)數(shù)序列dn。奇數(shù)地址是dn的實(shí)部，偶數(shù)地址是dn的虛部。這個(gè)過程叫做組合（n是從0到無窮，指示時(shí)間的變量，N是常量）。然后，復(fù)數(shù)序列經(jīng)過位倒序，存儲(chǔ)在數(shù)據(jù)處理緩沖器中，標(biāo)記為“fft-data”。 如圖2，輸入實(shí)數(shù)序列為an，n=0，1，2，3，255。分離an成兩個(gè)序

9、列，如圖3所示。原始的輸入序列是從地址0x2300到0x23FF，其余的從0x2200到0x22FF的是經(jīng)過位倒序之后的組合序列：n=0，1，2，3，127。 dn表示復(fù)合FFT的輸入，rn表示實(shí)部，in表示虛部： dn=rn+j in 按位倒序的方式存儲(chǔ)dn到數(shù)據(jù)處理緩沖中，如圖2。圖2* 編程技巧：在用C54x進(jìn)行位倒序組合時(shí)，使用位倒序?qū)ぶ贩绞娇梢源蟠筇岣叱绦驁?zhí)行的速度和使用存儲(chǔ)器的效率。在這種尋址方式中，AR0存放的整數(shù)N是FFT點(diǎn)數(shù)的一半，一個(gè)輔助寄存器指向一數(shù)據(jù)存放的單元。當(dāng)使用位倒序?qū)ぶ钒袮R0加到輔助寄存器中時(shí)，地址以位倒序的方式產(chǎn)生，即進(jìn)位是從左到右，而不是從右到左。例如，當(dāng)

10、AR0 = 0x0060，AR2 = 0x0040時(shí)，通過指令：MAR AR2+0B 我們就可以得到AR2位倒序?qū)ぶ泛蟮闹禐?x0010。 下面是0x0060（1100000）與0x0040（1000000）以位倒序方式相加的過程：實(shí)現(xiàn)256點(diǎn)數(shù)據(jù)位倒序存儲(chǔ)的具體程序段如下：bit_rev: STM #d_input_addr,ORIGINAL_INPUT ；在AR3（ORIGINAL_INPUT）中 ；放入輸入地址 STM #fft_data,DATA_PROC_BUF ；在AR7（DATA_PROC_BUF）中 ；放入處理后輸出的地址 MVMM DATA_PROC_BUF,REORDERE

11、D_DATA ;AR2（REORDERED_DATA） ;中裝入第一個(gè)位倒序數(shù)據(jù)指針 STM #K_FFT_SIZE-1,BRC STM #K_FFT_SIZE,AR0 ;AR0的值是輸入數(shù)據(jù)數(shù)目的一半=128 RPTB bit_rev_end MVDD *ORIGINAL_INPUT+,*REORDERED_DATA+;將原始輸入緩沖中的數(shù)據(jù) ;放入到位倒序緩沖中去之 ;后輸入緩沖(AR3)指針加1 ;位倒序緩沖(AR2)指針也加 ;一 MVDD *ORIGINAL_INPUT-,*REORDERED_DATA+ ;將原始輸入緩沖中的數(shù)據(jù) ;放入到位倒序緩沖中去之 ;后輸入緩沖(AR3)指針

12、減一 ;位倒序緩沖(AR2)指針加一 ;以保證位倒序?qū)ぶ氛_ MAR *ORIGINAL_INPUT+0B；按位倒序?qū)ぶ贩绞叫薷腁R3bit_rev_end:注意，在上面的程序中。輸入緩沖指針AR3（即ORIGINAL_INPUT）在操作時(shí)先加一再減一，是因?yàn)槲覀儼演斎霐?shù)據(jù)相鄰的兩個(gè)字看成一個(gè)復(fù)數(shù)，在用寄存器間接尋址移動(dòng)了一個(gè)復(fù)數(shù)（兩個(gè)字的數(shù)據(jù)）之后，對(duì)AR3進(jìn)行位倒序?qū)ぶ分耙袮R3的值恢復(fù)到這個(gè)復(fù)數(shù)的首字的地址，這樣才能保證位倒序?qū)ぶ返恼_。第二步，N點(diǎn)復(fù)數(shù)FFT 在數(shù)據(jù)處理緩沖器里進(jìn)行N點(diǎn)復(fù)數(shù)FFT運(yùn)算。由于在FFT運(yùn)算中要用到旋轉(zhuǎn)因子WN，它是一個(gè)復(fù)數(shù)。我們把它分為正弦和余弦部分，用

13、Q15格式將它們存儲(chǔ)在兩個(gè)分離的表中。每個(gè)表中有128項(xiàng)，對(duì)應(yīng)從0度到180度。因?yàn)椴捎醚h(huán)尋址來對(duì)表尋址，128 = 27 < 28，因此每張表排隊(duì)的開始地址就必須是8個(gè)LSB位為0的地址。參照前面圖1 DES 系統(tǒng)的存儲(chǔ)區(qū)分配，所以我們必須把正弦表第一項(xiàng)“sine_table”放在0x0D00的位置,余弦表第一項(xiàng)“cos_table”放在0x0E00的位置。 根據(jù)公式 利用蝶形結(jié)對(duì)dn進(jìn)行N=128點(diǎn)復(fù)數(shù)FFT運(yùn)算，其中所需的正弦值和余弦值分別以Q15的格式存儲(chǔ)于內(nèi)存區(qū)以0x0D00開始的正弦表和以0x0E00開始的余弦表中。我們把128點(diǎn)的復(fù)數(shù)FFT分為七級(jí)來算，第一級(jí)是計(jì)算兩點(diǎn)的

14、FFT蝶形結(jié)，第二級(jí)是計(jì)算四點(diǎn)的FFT蝶形結(jié)，然后是八點(diǎn)、十六點(diǎn)、三十二點(diǎn)六十四點(diǎn)、一百二十八點(diǎn)的蝶形結(jié)計(jì)算。最后所得的結(jié)果表示為： Dk = Fdn = Rk + j Ik其中，Rk、Ik分別是Dk的實(shí)部和虛部。圖3 FFT完成以后，結(jié)果序列Dk就存儲(chǔ)到數(shù)據(jù)處理緩沖器的上半部分，如圖3所示，下半部分任然保留原始的輸入序列an，這半部分將在第三步中被改寫。這樣原始的an序列的所有DFT的信息都在Dk中了，第三步中需要做的就是就是把Dk變?yōu)樽罱K的2N=256點(diǎn)復(fù)合序列，Ak=Fa(n)。* 編程技巧：在實(shí)際的DSP的編程中為了節(jié)約程序運(yùn)行時(shí)間，提高代碼的效率，往往要用到并行程序指令。比如： ST

15、 B,*AR3 |LD *AR3+,B 并行指令的執(zhí)行效果是，使原本分開要兩個(gè)指令周期才能執(zhí)行完的兩條指令在一個(gè)指令周期中中就能執(zhí)行完。上述指令是將B移位（ASM-16）所決定的位數(shù)，存于AR3所指定的存儲(chǔ)單元中，同時(shí)并行執(zhí)行，將AR3所指的單元中的值裝入到累加器B的高位中。由于指令的src和dst都是acc B，所以存入*AR3中的值是這條指令執(zhí)行以前的值。這一步中，實(shí)現(xiàn)FFT計(jì)算的具體程序如下：fft:;-stage1 ：計(jì)算FFT的第一步，兩點(diǎn)的FFT .asg AR1,GROUP_COUNTER；定義FFT計(jì)算的組指針 .asg AR2,PX；定義AR2為指向參加蝶形運(yùn)算第一個(gè)數(shù)據(jù)的指

16、針 .asg AR3,QX；定義AR3為指向參加蝶形運(yùn)算第二個(gè)數(shù)據(jù)的指針 .asg AR4,WR；定義AR4為指向余弦表的指針 .asg AR5,WI；定義AR5為指向正弦表的指針 .asg AR6,BUTTERFLY_COUNTER；定義AR6為指向蝶形結(jié)的指針 .asg AR7,DATA_PROC_BUF ；定義在第一步中的數(shù)據(jù)處理緩沖指針 .asg AR7,STAGE_COUNTER ；定義剩下幾步中的數(shù)據(jù)處理緩沖指針 pshm st0 pshm ar0 pshm bk；保存環(huán)境變量 SSBX SXM；開啟符號(hào)擴(kuò)展模式 STM #K_ZERO_BK,BK ；讓BK=0 使 *ARn+0%

17、 = *ARn+0 LD #-1,ASM ；為避免溢出在每一步輸出時(shí)右移一位 MVMM DATA_PROC_BUF,PX；PX指向參加蝶形結(jié)運(yùn)算的第一個(gè)數(shù)的實(shí)部（PR） LD *PX,16,A ；AH := PR STM #fft_data+K_DATA_IDX_1,QX；QX指向參加蝶形結(jié)運(yùn)算的第二個(gè)數(shù)的實(shí)部（QR） STM #K_FFT_SIZE/2-1,BRC；設(shè)置塊循環(huán)計(jì)數(shù)器 RPTBD stage1end-1；語句重復(fù)執(zhí)行的范圍到地址stage1end-1處 STM #K_DATA_IDX_1+1,AR0；延遲執(zhí)行的兩字節(jié)的指令（該指令不重復(fù)執(zhí)行） SUB *QX,16,A,B；BH

18、 := PR-QR ADD *QX,16,A；AH := PR+QR STH A,ASM,*PX+；PR':= (PR+QR)/2 ST B,*QX+；QR':= (PR-QR)/2 |LD *PX,A；AH := PI SUB *QX,16,A,B；BH := PI-QI ADD *QX,16,A；AH := PI+QI STH A,ASM,*PX+0%；PI':= (PI+QI)/2 ST B,*QX+0%；QI':= (PI-QI)/2 |LD *PX,A；AH := next PRstage1end:; -Stage 2 ：計(jì)算FFT的第二步，四點(diǎn)的FF

19、T MVMM DATA_PROC_BUF,PX；PX 指向參加蝶形結(jié)運(yùn)算第一個(gè)數(shù)據(jù)的實(shí)部（PR） STM #fft_data+K_DATA_IDX_2,QX；QX 指向參加蝶形結(jié)運(yùn)算第二個(gè)數(shù)據(jù)的實(shí)部（QR） STM #K_FFT_SIZE/4-1,BRC；設(shè)置塊循環(huán)計(jì)數(shù)器 LD *PX,16,A；AH := PR RPTBD stage2end-1；語句重復(fù)執(zhí)行的范圍到地址stage1end-1處 STM #K_DATA_IDX_2+1,AR0；初始化AR0以被循環(huán)尋址;以下是第二步運(yùn)算的第一個(gè)蝶形結(jié)運(yùn)算過程 SUB *QX,16,A,B；BH := PR-QR ADD *QX,16,A；AH

20、 := PR+QR STH A,ASM,*PX+；PR':= (PR+QR)/2 ST B,*QX+；QR':= (PR-QR)/2 |LD *PX,A；AH := PI SUB *QX,16,A,B；BH := PI-QI ADD *QX,16,A；AH := PI+QI STH A,ASM,*PX+；PI':= (PI+QI)/2 STH B,ASM,*QX+；QI':= (PI-QI)/2; 以下是第二步運(yùn)算的第二個(gè)蝶形結(jié)運(yùn)算過程 MAR *QX+；QX中的地址加一 ADD *PX,*QX,A；AH := PR+QI SUB *PX,*QX-,B；BH :

21、= PR-QI STH A,ASM,*PX+；PR':= (PR+QI)/2 SUB *PX,*QX,A；AH := PI-QR ST B,*QX；QR':= (PR-QI)/2 |LD *QX+,B；BH := QR ST A, *PX；PI':= (PI-QR)/2 |ADD *PX+0%,A；AH := PI+QR ST A,*QX+0%；QI':= (PI+QR)/2 |LD *PX,A；AH := PRstage2end:; Stage 3 thru Stage logN-1：從第三步到第六步的過程如下 STM #K_TWID_TBL_SIZE,BK；

22、BK = 旋轉(zhuǎn)因子表格的大小值 ST #K_TWID_IDX_3,d_twid_idx；初始化旋轉(zhuǎn)表格索引值 STM #K_TWID_IDX_3,AR0；AR0 = 旋轉(zhuǎn)表格初始索引值 STM #cos_table,WR；初始化 WR 指針 STM #sine_table,WI；初始化 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；初始化蝶形結(jié)指針 ST #K_DATA_IDX_3,d_data_idx

23、；初始化輸入數(shù)據(jù)的索引stage:；以下是每一步的運(yùn)算過程 STM #fft_data,PX ；PX 指向參加蝶形結(jié)運(yùn)算第一個(gè)數(shù)據(jù)的實(shí)部（PR） LD d_data_idx, A ADD *(PX),A STLM A,QX；QX 指向參加蝶形結(jié)運(yùn)算第二個(gè)數(shù)據(jù)的實(shí)部（QR） MVDK d_grps_cnt,GROUP_COUNTER；AR1 是組個(gè)數(shù)計(jì)數(shù)器:group:；以下是每一組的運(yùn)算過程 MVMD BUTTERFLY_COUNTER,BRC；將每一組中的蝶形結(jié)的個(gè)數(shù)裝入BRC RPTBD butterflyend-1；重復(fù)執(zhí)行至butterflyend-1處 LD *WR,T MPY *Q

24、X+,A；A := QR*WR | QX*QI MAC *WI+0%,*QX-,A；A := QR*WR+QI*WI ADD *PX,16,A,B；B := (QR*WR+QI*WI)+PR ; | QX指向QR ST B,*PX；PR':=(QR*WR+QI*WI)+PR)/2 |SUB *PX+,B；B := PR-(QR*WR+QI*WI) ST B,*QX；QR':= (PR-(QR*WR+QI*WI)/2 |MPY *QX+,A；A := QR*WI T=WI ; | QX指向QI MAS *QX,*WR+0%,A；A := QR*WI-QI*WR ADD *PX,1

25、6,A,B；B := (QR*WI-QI*WR)+PI ST B,*QX+；QI':=(QR*WI-QI*WR)+PI)/2 ; | QX指向QR |SUB *PX,B；B := PI-(QR*WI-QI*WR) LD *WR,T；T := WR ST B,*PX+；PI':= (PI-(QR*WI-QI*WR)/2 ; | PX指向PR |MPY *QX+,A；A := QR*WR | QX指向QIbutterflyend:；更新指針以準(zhǔn)備下一組蝶形結(jié)的運(yùn)算 PSHM AR0；保存AR0 MVDK d_data_idx,AR0；AR0中裝入在該步運(yùn)算中每一組所用的蝶形結(jié)的數(shù)目

26、 MAR *PX+0；增加PX準(zhǔn)備進(jìn)行下一組的運(yùn)算 MAR *QX+0；增加QX準(zhǔn)備進(jìn)行下一組的運(yùn)算 BANZD group,*GROUP_COUNTER-；當(dāng)組計(jì)數(shù)器減一后不等于零時(shí)，延遲跳轉(zhuǎn)至group處 POPM AR0；恢復(fù)AR0（一字節(jié)） MAR *QX-；修改QX以適應(yīng)下一組的運(yùn)算;；更新指針和其他索引數(shù)據(jù)以變進(jìn)入下一個(gè)步驟的運(yùn)算 LD d_data_idx,A SUB #1,A,B；B = A-1 STLM B,BUTTERFLY_COUNTER；修改蝶形結(jié)個(gè)數(shù)計(jì)數(shù)器 STL A,1,d_data_idx；下一步計(jì)算的數(shù)據(jù)索引翻倍 LD d_grps_cnt,A STL A,-1

27、,d_grps_cnt；下一步計(jì)算的組數(shù)目減少一半 LD d_twid_idx,A STL A,-1,d_twid_idx；下一步計(jì)算的旋轉(zhuǎn)因子索引減少一半 BANZD stage,*STAGE_COUNTER- MVDK d_twid_idx,AR0；AR0 = 旋轉(zhuǎn)因子索引（兩字節(jié)） popm bk popm ar0 popm st0；恢復(fù)環(huán)境變量fft_end: RET第三步，分離復(fù)數(shù)FFT的輸出為奇部分和偶部分 分離FFT輸出為相關(guān)的四個(gè)序列：RP、RM、IP和IM，即偶實(shí)數(shù)，奇實(shí)數(shù)、偶虛數(shù)和奇虛數(shù)四部分，以便第四步形成最終結(jié)果。 利用信號(hào)分析的理論我們把Dk通過下面的公式分為偶實(shí)數(shù)R

28、Pk、奇實(shí)數(shù)RMk、偶虛數(shù)IPk和奇虛數(shù)IMk：RPk = RPN-k = 0.5 * (Rk + RN-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 = R0IP0 = I0RM0 = IM0 = RMN/2 = IMN/2 = 0RPN/2 = RN/2IPN/2 = IN/2 下面的圖4顯示了第三步完成以后存儲(chǔ)器中的數(shù)據(jù)情況，RPk和IPk存儲(chǔ)在上半部分，RMk 和IMk存儲(chǔ)在下半部分。圖4 這一過程的程序代碼如下所示：un

29、pack .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)STM #fft_data+2*K_FFT_SIZE-2,XP_Nminusk; AR3指向 RN-K (temp RPN-K)STM #fft_data+2*K_FFT_SIZE+3,XM_Nminusk; AR7指向 temp RMN-KSTM #fft_data+4*K_FFT_SIZE-1,XM_k; AR6指向temp RMKSTM #-2+K_FFT_SIZE

30、/2,BRC; 設(shè)置塊循環(huán)計(jì)數(shù)器RPTBD phase3end-1; 從以下指令到phase3end-1處一直; 重復(fù)執(zhí)行BRC中規(guī)定的次數(shù)STM #3,AR0; 設(shè)置AR0以備下面程序?qū)ぶ肥褂肁DD *XP_k,*XP_Nminusk,A; A := Rk+RN-K = 2*RPkSUB *XP_k,*XP_Nminusk,B; B := Rk-RN-K= 2*RMkSTH A,ASM,*XP_k+; 在ARk處存儲(chǔ)RPkSTH A,ASM,*XP_Nminusk+; 在ARN-K處存儲(chǔ)RPN-K=RPkSTH B,ASM,*XM_k-; 在AI2N-K處存儲(chǔ)RMkNEG B; B := R

31、N-K-Rk =2*RMN-KSTH B,ASM,*XM_Nminusk-; 在AIN+k處存儲(chǔ)RMN-KADD *XP_k,*XP_Nminusk,A; A := Ik+IN-K = 2*IPkSUB *XP_k,*XP_Nminusk,B; B := Ik-IN-K =2*IMkSTH A,ASM,*XP_k+; 在AIk處存儲(chǔ)IPkSTH A,ASM,*XP_Nminusk-0; 在AIN-K處存儲(chǔ)IPN-K=IPk STH B,ASM,*XM_k-; 在AR2N-K處存儲(chǔ)IMkNEG B; B := IN-K-Ik =2*IMN-KSTH B,ASM,*XM_Nminusk+0; 在A

32、RN+k處存儲(chǔ)IMN-Kphase3end:第四步，產(chǎn)生最后的N = 256點(diǎn)的復(fù)數(shù)FFT結(jié)果 產(chǎn)生2N = 256個(gè)點(diǎn)的復(fù)數(shù)輸出，它與原始的256個(gè)點(diǎn)的實(shí)輸入序列的DFT一致。輸出駐留在數(shù)據(jù)緩沖器中。 通過下面的公式由RPk、RMn、IPn和IMn四個(gè)序列可以計(jì)算出an的DFT：ARk = AR2N-k = RPk + cos(k/N) * IPk - sin(k/N) * RMkAIk = -AI2N-k = IMk - cos(k/N) * RMk - sin(k/N) * IPkAR0 = RP0 + IP0AI0 = IM0 - RM0ARN = R0 - I0AIN = 0其中：A

33、k = A2N-k = ARk + j AIk = Fa(n) 實(shí)數(shù)FFT輸出按照實(shí)數(shù)/虛數(shù)的自然順序填滿整個(gè)4N=512個(gè)字節(jié)的數(shù)據(jù)處理緩沖器。如圖5所示。圖5這一段程序可以和上面的步驟3的程序合成一個(gè)子程序unpack，這一步的程序代碼如下： ST #0,*XM_k-; RMN/2=0 ST #0,*XM_k; IMN/2=0; 計(jì)算AR0,AI0, ARN, AIN .asg AR2,AX_k .asg AR4,IP_0 .asg AR5,AX_N STM #fft_data,AX_k; AR2指向AR0 (temp RP0) STM #fft_data+1,IP_0; AR4指向AI0

34、 (temp IP0) STM #fft_data+2*K_FFT_SIZE+1,AX_N; AR5指向AIN ADD *AX_k,*IP_0,A; A := RP0+IP0 SUB *AX_k,*IP_0,B; B := RP0-IP0 STH A,ASM,*AX_k+; AR0 = (RP0+IP0)/2 ST #0,*AX_k; AI0 = 0 MVDD *AX_k+,*AX_N-; AIN = 0 STH B,ASM,*AX_N; ARN = (RP0-IP0)/2; 計(jì)算最后的輸出值A(chǔ)Rk, AIk .asg AR3,AX_2Nminusk .asg AR4,COS .asg AR5

35、,SIN STM #fft_data+4*K_FFT_SIZE-1,AX_2Nminusk ; AR3指向AI2N-1(temp RM1) STM #cos_table+K_TWID_TBL_SIZE/K_FFT_SIZE,COS ; AR4指向cos(k*/N) STM #sine_table+K_TWID_TBL_SIZE/K_FFT_SIZE,SIN; AR5指向sin(k*/N) STM #K_FFT_SIZE-2,BRC RPTBD phase4end-4 STM #K_TWID_TBL_SIZE/K_FFT_SIZE,AR0; AR0中存入旋轉(zhuǎn)因子表的大 ;小以備循環(huán)尋址時(shí)使用 L

36、D *AX_k+,16,A; A := RPk |修改AR2指向IPk MACR *COS,*AX_k,A; A :=A+cos(k*/N)*IPk MASR *SIN,*AX_2Nminusk-,A; A := A-sin(k*/N)*RMk | ;修改AR3指向IMk LD *AX_2Nminusk+,16,B; B := IMk |修改AR3指向RMk MASR *SIN+0%,*AX_k-,B; B := B-sin(k*/N)*IPk | ;修改AR2指向RPk MASR *COS+0%,*AX_2Nminusk,B; B := B-cos(k*/N)*RMk STH A,ASM,*

37、AX_k+; ARk = A/2 STH B,ASM,*AX_k+; AIk = B/2 NEG B; B := -B STH B,ASM,*AX_2Nminusk-; AI2N-K = -AIk= B/2 STH A,ASM,*AX_2Nminusk-; AR2N-K = AR ; k = A/2phase4end: 計(jì)算所求信號(hào)的功率 由于最后所得的FFT數(shù)據(jù)是一個(gè)復(fù)數(shù)，為了能夠方便的在虛擬頻譜儀上觀察該信號(hào)的特征，我們通常對(duì)所得的FFT數(shù)據(jù)進(jìn)行處理取其實(shí)部和虛部的平方和，即求得該信號(hào)的功率。 power: .asg AR2,AX .asg AR3,OUTPUT_BUF pshm st0；

38、保存寄存器的值 pshm ar0 pshm bk STM #d_output_addr,OUTPUT_BUF；AR3指向輸出緩沖地址 STM #K_FFT_SIZE*2-1,BRC；塊循環(huán)計(jì)數(shù)器設(shè)置為255 RPTBD power_end-4；帶延遲方式的重復(fù)執(zhí)行指令 STM #fft_data,AX；AR2指向AR0 SQUR *AX+,A；A := AR2 SQURA *AX+,A；A := AR2 + AI2 STH A,7,*OUTPUT_BUF；將A中的數(shù)據(jù)存入輸出緩沖中， ANDM #7FFFH,*OUTPUT_BUF+；避免輸出數(shù)據(jù)過大在虛擬示波器 ；中顯示錯(cuò)誤 popm bk；保存各個(gè)寄存器值 popm ar0 popm st0 power_end: RET注意，在上面的程序中將數(shù)據(jù)放回輸出緩沖準(zhǔn)備輸出時(shí)使用了指令： STH A,7,*OUTPUT_BUF對(duì)acc A左移7位是為了讓顯示的數(shù)據(jù)值在一個(gè)合適的范圍內(nèi)有利于觀察顯示的圖形，由于所有的數(shù)據(jù)都左移了7位，所以從總體上看整個(gè)波形的性質(zhì)還是一樣的。同時(shí)，由于有的數(shù)據(jù)太大，為了避免顯示數(shù)據(jù)的溢出而導(dǎo)致在虛擬示波器中觀察到的波形錯(cuò)誤所以