實驗八 快速傅立葉變換的實現(xiàn)

實驗八、快速傅立葉變換(FFT)的實現(xiàn).實驗目的在數(shù)字信號處理系統(tǒng)中，F(xiàn)FT作為一個非常重要的工具經(jīng)常使用，甚至成為DSP運算能力的一個考核因素。FFT是一種高效實現(xiàn)離散付氏變換的算法。離散付氏變換的目的是把信號由時域變換到頻域，從而可以在頻域分析處理信息，得到的結果再由付氏逆變換到時域。本實驗的目的在于學習FFT算法，及其在TMS320C54X上的實現(xiàn)，并通過編程掌握C54X的存儲器管理、輔助寄存器的使用、位倒序尋址方式等技巧，同時練習使用CCS的探針和圖形工具。另外在BIOS子目錄下是一個使用DSP/BIOS工具實現(xiàn)FFT的程序。通過該程序，你可以使用DSP/BIOS提供的分析工具評估FFT代碼執(zhí)行情況。,實驗原理㈠基一2按時間抽取FFT算法對于有限長離散數(shù)字信號｛x[n]｝，0<n<N-1，其離散譜｛x[k]｝可以由離散付氏變換(DFT)求得。DFT的定義為X(k)二丈1x[n]e-j(27)nkk=0,1,...,N-1n=0可以方便的把它改寫為如下形式：X()=^-1x[nWnkk=0,1,...,N-1Nn=0不難看出，WN是周期性的，且周期為N，即W(n+mN)(k+lN)=Wnkm,l=0,±1,±2...Wn的周期性是DFT的關鍵性質之一。為了強調起見，常用表達式Wn取代W以便明確其周期是N。由DFT的定義可以看出，在x[n]為復數(shù)序列的情況下，完全直接運算N點DFT需要(N-1)2次復數(shù)乘法和N(N-1)次加法。因此，對于一些相當大的N值(如1024)來說，直接計算它的DFT所作的計算量是很大的。FFT的基本思想在于，將原有的N點序列序列分成兩個較短的序列，這些序列的DFT可以很簡單的組合起來得到原序列的DFT。例如，若N為偶數(shù)，將原有的N點序列分成兩個(N/2)點序列，那么計算N點DFT將只需要約[(N/2)2?2]=N2/2次復數(shù)乘法。即比直接計算少作一半乘法。因子(N/2)2表示直接計算(N/2)點DFT所需要的乘法次數(shù)，而乘數(shù)2代表必須完成兩個DFT。上述處理方法可以反復使用，即(N/2)點的DFT計算也可以化成兩個(N/4)點的DFT(假定N/2為偶數(shù))，從而又少作一半的乘法。這樣一級一級的劃分下去一直到最后就劃分成兩點的FFT運算的情況。比如，一個N=8點的FFT運算按照這種方法來計算FFT可以用下面的流程圖來表示：

x(0)x(1)x(2)x(3)x(0)x(1)x(2)x(3)x(4)x(5)x⑹x⑺X(0)X(1)X(2)X⑶X⑷X(5)X⑹X⑺㈡實數(shù)FFT運算對于離散傅立葉變換（DFT）的數(shù)字計算，F(xiàn)FT是一種有效的方法。一般假定輸入序列是復數(shù)。當實際輸入是實數(shù)時，利用對稱性質可以使計算DFT非常有效。一個優(yōu)化的實數(shù)FFT算法是一個組合以后的算法。原始的2N個點的實輸入序列組合成一個N點的復序列，之后對復序列進行N點的FFT運算，最后再由N點的復數(shù)輸出拆散成2N點的復數(shù)序列，這2N點的復數(shù)序列與原始的2N點的實數(shù)輸入序列的DFT輸出一致。使用這種方法，在組合輸入和拆散輸出的操作中，F(xiàn)FT運算量減半。這樣利用實數(shù)FFT算法來計算實輸入序列的DFT的速度幾乎是一般復FFT算法的兩倍。本實驗就用這種方法實現(xiàn)了一個256點實數(shù)FFT（2N=256）運算。1.實數(shù)FFT運算序列的存儲分配如何利用有限的DSP系統(tǒng)資源，合理的安排好算法使用的存儲器是一個比較重要的問題。參見FFT實驗程序的CMD文件：MEMORY{PAGE0:IPROG:origin=0x3080,len=0x1F80VECT:origin=0x3000,len=0x80EPROG:origin=0x38000,len=0x8000PAGE1:USERREGS:origin=0x60,len=0x1cBIOSREGS:origin=0x7c,len=0x4IDATA:origin=0x80,len=0xB80EDATA:origin=0xC00,len=0x1400SECTIONS{,vectors:{}>VECTPAGE0,sysregs:{}>BIOSREGSPAGE1.trcinit:{}>IPROGPAGE0,gblinit:{}>IPROGPAGE0.bios:{}>IPROGPAGE0frt:{}>IPROGPAGE0.text:{}>IPROGPAGE0,cinit:{}>IPROGPAGE0.pinit:{}>IPROGPAGE0,sysinit:{}>IPROGPAGE0,data{}>EDATAPAGE1.bss:{}>IDATAPAGE1,far:{}>IDATAPAGE1,const:{}>IDATAPAGE1,switch:{}>IDATAPAGE1,sysmem:{}>IDATAPAGE1,cio:{}>IDATAPAGE1,MEM$obj:{}>IDATAPAGE1,sysheap:{}>IDATAPAGE1}從上面的連接定位CMD文件可以了解到，程序代碼安排在0x3000開始的存儲器中。其中0x3000-0x3080存放中斷向量表。FFT程序使用的正弦表、余弦表數(shù)據(jù)（,data段）安排在0xc00開始的地方。變量（,bss段定義）存放在0x80開始的地址中。另外，本256點實數(shù)FFT程序的輸入數(shù)據(jù)緩沖為0x2300-0x23ff，F(xiàn)FT后功率譜的計算結果存放在0x2200-0x22ff中。2.基二實數(shù)FFT運算的算法該算法主要分為四步：第一步，輸入數(shù)據(jù)的組合和位倒序把輸入序列作位倒序，是為了在整個運算最后的輸出中得到的序列是自然順序。首先，原始的輸入的2N=256個點的實數(shù)序列復制放到標記有“d_input_addr”的相鄰單元，當成N=128點的復數(shù)序列d[n]。奇數(shù)地址是d[n]的實部，偶數(shù)地址是d[n]的虛部。這個過程叫做組合（n是從0到無窮，指示時間的變量，N是常量）。然后，復數(shù)序列經(jīng)過位倒序，存儲在數(shù)據(jù)處理緩沖器中，標記為“fft-data”。如圖2，輸入實數(shù)序列為a[n]，n=0，1，2,3,…，255。分離a[n]成兩個序列，如圖3所示。原始的輸入序列是從地址0x2300到0x23FF，其余的從0x2200到0x22FF的是經(jīng)過位倒序之后的組合序列：n=0，1，2,3，…，127。d[n]表示復合FFT的輸入，r[n]表示實部，i[n]表示虛部：d[n]=r[n]+ji[n]

按位倒序的方式存儲d[n]到數(shù)據(jù)處理緩沖中，如圖2。圖2

2200hr[O]=a[0]2201hi[0]=a[1]2202hr[64]=a[128]2203hi[64]=a[129]2204hr[32]=a[64]2205hi[32]=a[65]2206hr[96]=a[192]2207hi[96]=a[193]2208hr[16]=a[32]2209hi[16]=a[33]220Ahr[80]=a[160]220Bhi[80]=a[161]22FEhr[127]=a[254]22FFhi[127]=a[255]2300ha[0]2301ha[1]2302ha[2]2303ha[3]2304ha[4]2305ha[5]2306ha[6]2307ha[7]2308ha[8]2309ha[9]230Aha[10]230Bha[11]23FEha[254]23FFha[255]圖2*編程技巧：在用C54x進行位倒序組合時，使用位倒序尋址方式可以大大提高程序執(zhí)行的速度和使用存儲器的效率。在這種尋址方式中，AR0存放的整數(shù)N是FFT點數(shù)的一半，一個輔助寄存器指向一數(shù)據(jù)存放的單元。當使用位倒序尋址把AR0加到輔助寄存器中時，地址以位倒序的方式產(chǎn)生，即進位是從左到右，而不是從右到左。例如，當AR0=0x0060，AR2=0x0040時，通過指令：MARAR2+0B我們就可以得到AR2位倒序尋址后的值為0x0010。下面是0x0060(1100000)與0x0040(1000000)以位倒序方式相加的過程：TOC\o"1-5"\h\z1100000+10000000010000實現(xiàn)256點數(shù)據(jù)位倒序存儲的具體程序段如下：bit_rev:STM#d_input_addr,ORIGINAL_INPUT；在AR3(ORIGINAL_INPUT)中；放入輸入地址STM#fft_data,DATA_PROC_BUF；在AR7(DATA_PROC_BUF)中；放入處理后輸出的地址MVMMDATA_PROC_BUF,REORDERED_DATA;AR2(REORDERED_DATA);中裝入第一個位倒序數(shù)據(jù)指針STM#K_FFT_SIZE-1,BRCSTM#K_FFT_SIZE,AR0;AR0的值是輸入數(shù)據(jù)數(shù)目的一半=128RPTBbit_rev_endMVDD*ORIGINAL_INPUT+,*REORDERED_DATA+;將原始輸入緩沖中的數(shù)據(jù);放入到位倒序緩沖中去之;后輸入緩沖(AR3)指針加1;位倒序緩沖(AR2)指針也加;;MVDD*ORIGINAL_INPUT-,*REORDERED_DATA+;將原始輸入緩沖中的數(shù)據(jù);放入到位倒序緩沖中去之;后輸入緩沖(AR3)指針減一;位倒序緩沖(AR2)指針加一;以保證位倒序尋址正確MAR*ORIGINAL_INPUT+0B；按位倒序尋址方式修改AR3bit_rev_end:注意，在上面的程序中。輸入緩沖指針AR3(即ORIGINAL_INPUT)在操作時先加一再減一，是因為我們把輸入數(shù)據(jù)相鄰的兩個字看成一個復數(shù)，在用寄存器間接尋址移動了一個復數(shù)(兩個字的數(shù)據(jù))之后，對AR3進行位倒序尋址之前要把AR3的值恢復到這個復數(shù)的首字的地址，這樣才能保證位倒序尋址的正確。第二步，N點復數(shù)FFT在數(shù)據(jù)處理緩沖器里進行N點復數(shù)FFT運算。由于在FFT運算中要用到旋轉因子WN，它是一個復數(shù)。我們把它分為正弦和余弦部分，用Q15格式將它們存儲在兩個分離的表中。每個表中有128項，對應從0度到180度。因為采用循環(huán)尋址來對表尋址，128=27<28，因此每張表排隊的開始地址就必須是8個LSB位為0的地址。參照前面圖1DES系統(tǒng)的存儲區(qū)分配，所以我們必須把正弦表第一項“sine_table”放在0x0D00的位置，余弦表第一項“cos_table”放在0x0E00的位置。①根據(jù)公式D（k）=丈1d[nWnkk=0,1,...,N-1Nn=0利用蝶形結對d[n]進行N=128點復數(shù)FFT運算，其中-j(2兀)nk齊2KWnk=ej(n=cos(nk)一jsin(nk)NNN所需的正弦值和余弦值分別以Q15的格式存儲于內(nèi)存區(qū)以0X0D00開始的正弦表和以0X0E00開始的余弦表中。我們把128點的復數(shù)FFT分為七級來算，第一級是計算兩點的FFT蝶形結，第二級是計算四點的FFT蝶形結，然后是八點、十六點、三十二點六十四點、一百二十八點的蝶形結計算。最后所得的結果表示為：D[k]=F{d[n]}=R[k]+jI[k]其中，R[k]、I[k]分別是D[k]的實部和虛部。

②FFT完成以后，結果序列D[k]就存儲到數(shù)據(jù)處理緩沖器的上半部分，如圖3所示，下半部分任然保留原始的輸入序列a[n]，這半部分將在第三步中被改寫。這樣原始的a[n]序列的所有DFT的信息都在D[k]中了，第三步中需要做的就是就是把D[k]變?yōu)樽罱K的2N=256點復合序列，A[k]=F{a（n）}。*編程技巧：在實際的DSP的編程中為了節(jié)約程序運行時間，提高代碼的效率，往往要用到并行程序指令。比如：STB,*AR3||LD*AR3+,B并行指令的執(zhí)行效果是，使原本分開要兩個指令周期才能執(zhí)行完的兩條指令在一個指令周期中中就能執(zhí)行完。上述指令是將B移位（ASM-16）所決定的位數(shù)，存于AR3所指定的存儲單元中，同時并行執(zhí)行，將AR3所指的單元中的值裝入到累加器B的高位中。由于指令的src和dst都是accB，所以存入*AR3中的值是這條指令執(zhí)行以前的值。這一步中，實現(xiàn)FFT計算的具體程序如下：fft:-stage1：計算FFT的第一步，兩點的FFT,asgAR1,GROUP_COUNTER,asgAR2,PX,asgAR3,QX,asgAR4,WR,asgAR5,WI,asgfft:-stage1：計算FFT的第一步，兩點的FFT,asgAR1,GROUP_COUNTER,asgAR2,PX,asgAR3,QX,asgAR4,WR,asgAR5,WI,asgAR6,BUTTERFLY_COUNTER,asgAR7,DATA_PROC_BUF,asgAR7,STAGE_COUNTER；定義FFT計算的組指針；定義AR2為指向參加蝶形運算第一個數(shù)據(jù)的指針；定義AR3為指向參加蝶形運算第二個數(shù)據(jù)的指針；定義AR4為指向余弦表的指針；定義AR5為指向正弦表的指針；定義AR6為指向蝶形結的指針；定義在第一步中的數(shù)據(jù)處理緩沖指針；定義剩下幾步中的數(shù)據(jù)處理緩沖指針pshmst0pshmar0pshmbk；保存環(huán)境變量SSBXSXM；開啟符號擴展模式STM#K_ZERO_BK,BKLD#-1,ASMMVMMDATA_PROC_BUF,PX；讓BK=0使*ARn+0%=*ARn+0；為避免溢出在每一步輸出時右移一位；PX指向參加蝶形結運算的第一個數(shù)的實部（PR）LD*PX,16,ASTM#fft_data+K_DATA_IDX_1,QXSTM#K_FFT_SIZE/2-1,BRCRPTBDstage1end-1STM#K_DATA_IDX_1+1,AR0SUB*QX,16,A,BADD*QX,16,ASTHA,ASM,*PX+；AH:=PR；QX指向參加蝶形結運算的第二個數(shù)的實部（QR）；設置塊循環(huán)計數(shù)器；語句重復執(zhí)行的范圍到地址stage1end-1處；延遲執(zhí)行的兩字節(jié)的指令（該指令不重復執(zhí)行）；BH:=PR-QR；AH:=PR+QR；PR':=(PR+QR)/2STB,*QX+IILD*PX,ASUB*QX,16,A,BADD*QX,16,ASTHA,ASM,*PX+0%STB,*QX+0%IILD*PX,A；QR':=(PR-QR)/2；AH:=PI；BH:=PI-QI；AH:=PI+QI；PI':=(PI+QI)/2；QI':=(PI-QI)/2；AH:=nextPR;Stage2:計算FFT的第二步，MVMMDATA_PROC_BUF,PXSTM#fft_data+K_DATA_IDX_2,QXSTM#K_FFT_SIZE/4-1,BRCLD*PX,16,ARPTBDstage2end-1STM#K_DATA_IDX_2+1,AR0；以下是第二步運算的第一個蝶形結運算過程SUB*QX,16,A,BADD*QX,16,ASTHA,ASM,*PX+STB,*QX+IILD*PX,ASUB*QX,16,A,BADD*QX,16,ASTHA,ASM,*PX+STHB,ASM,*QX+;以下是第二步運算的第二個蝶形結運算過程MAR*QX+ADD*PX,*QX,ASUB*PX,*QX-,BSTHA,ASM,*PX+SUB*PX,*QX,ASTB,*QXIILD*QX+,BSTA,*PXIIADD*PX+0%,ASTA,*QX+0%IILD*PX,Astage2end:四點的FFT；PX指向參加蝶形結運算第一個數(shù)據(jù)的實部（PR）；QX指向參加蝶形結運算第二個數(shù)據(jù)的實部(QR)；設置塊循環(huán)計數(shù)器；AH:=PR；語句重復執(zhí)行的范圍到地址stage1end-1處；初始化AR0以被循環(huán)尋址；BH:=PR-QR；AH:=;Stage2:計算FFT的第二步，MVMMDATA_PROC_BUF,PXSTM#fft_data+K_DATA_IDX_2,QXSTM#K_FFT_SIZE/4-1,BRCLD*PX,16,ARPTBDstage2end-1STM#K_DATA_IDX_2+1,AR0；以下是第二步運算的第一個蝶形結運算過程SUB*QX,16,A,BADD*QX,16,ASTHA,ASM,*PX+STB,*QX+IILD*PX,ASUB*QX,16,A,BADD*QX,16,ASTHA,ASM,*PX+STHB,ASM,*QX+;以下是第二步運算的第二個蝶形結運算過程MAR*QX+ADD*PX,*QX,ASUB*PX,*QX-,BSTHA,ASM,*PX+SUB*PX,*QX,ASTB,*QXIILD*QX+,BSTA,*PXIIADD*PX+0%,ASTA,*QX+0%IILD*PX,Astage2end:四點的FFT；PX指向參加蝶形結運算第一個數(shù)據(jù)的實部（PR）STM#K_TWID_TBL_SIZE,BK；BK=旋轉因子表格的大小值

ST#K_TWID_IDX_3,d_twid_idxSTM#K_TWID_IDX_3,AR0STM#cos_table,WRSTM#sine_table,WI;初始化旋轉表格索引值;AR0=旋轉表格初始索引值；初始化WR指針；初始化WI指針STM#K_LOGN-2-1,STAGE_COUNTERST#K_FFT_SIZE/8-1,d_grps_cntSTM#K_FLY_COUNT_3-1,BUTTERFLY一ST#K_DATA_IDX_3,d_data_idxstage:STM#fft_data,PXLDd_data_idx,AADD*(PX),ASTLMA,QXMVDKd_grps_cnt,GROUP_COUNTERgroup:MVMDBUTTERFLY_COUNTER,BRCRPTBDbutterflyend-1LD*WR,TMPY*QX+,AMAC*WI+0%,*QX-,AADD*PX,16,A,BSTB,*PXiisub*px+,bSTB,*QXiimpy*qx+,aMAS*QX,*WR+0%,AADD*PX,16,A,BSTB,*QX+iisub*px,bLD*WR,TSTB,*PX+iimpy*qx+,abutterflyend:；初始化步驟指針；初始化組指針_COUNTER;初始化蝶形結指針；初始化輸入數(shù)據(jù)的索引；以下是每一步的運算過程；PX指向參加蝶形結運算第一個數(shù)據(jù)的實部(PR)；QX指向參加蝶形結運算第二個數(shù)據(jù)的實部(QR)；AR1是組個數(shù)計數(shù)器：；以下是每一組的運算過程；將每一組中的蝶形結的個數(shù)裝入BRC；重復執(zhí)行至butterflyend-1處；A:=QR*WRIIQX*QI；A:=QR*WR+QI*WI；B:=(QR*WR+QI*WI)+PR;IIQX指向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];IIQX指向QI；A:=QR*WI-QI*WR；B:=(QR*WI-QI*WR)+PI；QI':=((QR*WI-QI*WR)+PI)/2;IIQX指向QR；B:=PI-(QR*WI-QI*WR)；T:=WR；PI':=(PI-(QR*WI-QI*WR))/2;IIPX指向PR；A:=QR*WRIIQX指向QI;更新指針以準備下一組蝶形結的運算PSHMAR0MVDKd_data_idx,AR0MAR*PX+0MAR*QX+0BANZDgroup,*GROUP_COUNTER-；保存AR0；AR0中裝入在該步運算中每一組所用的蝶形結的數(shù)目；增加PX準備進行下一組的運算；增加QX準備進行下一組的運算；當組計數(shù)器減一后不等于零時，延遲跳轉至group處

POPMAR0;恢復AR0(一字節(jié))MAR*QX-；修改QX以適應下一組的運算；;更新指針和其他索引數(shù)據(jù)以變進入下一個步驟的運算LDd_data_idx,ASUB#1,A,BSUB#1,A,BSTLMB,BUTTERFLY_COUNTERSTLA,1,d_data_idxLDd_grps_cnt,ASTLA,-1,d_grps_cntLDd_twid_idx,ASTLA,-1,d_twid_idxBANZDstage,*STAGE_COUNTER-MVDKd_twid_idx,AR0；B=A-1；修改蝶形結個數(shù)計數(shù)器；下一步計算的數(shù)據(jù)索引翻倍；下一步計算的組數(shù)目減少一半；下一步計算的旋轉因子索引減少一半；AR0=旋轉因子索引(兩字節(jié))；恢復環(huán)境變量popmbkpopmar0popmst0；恢復環(huán)境變量RET第三步，分離復數(shù)FFT的輸出為奇部分和偶部分分離FFT輸出為相關的四個序列：RP、RM、IP和IM，即偶實數(shù)，奇實數(shù)、偶虛數(shù)和奇虛數(shù)四部分，以便第四步形成最終結果。①利用信號分析的理論我們把D[k]通過下面的公式分為偶實數(shù)RP[k]、奇實數(shù)RM[k]、偶虛數(shù)IP[k]和奇虛數(shù)IM[k]：RP[k]=RP[N-k]=0.5*(R[k]+R[N-k])RM[k]=-RM[N-k]=0.5*(R[k]-R[N-k])IP[k]=IP[N-k]=0.5*(I[k]+I[N-k])IM[k]=-IM[N-k]=0.5*(I[k]-I[N-k])RP[0]=R[0]IP[0]=I[0]RM[0]=IM[0]=RM[N/2]=IM[N/2]=0RP[N/2]=R[N/2]IP[N/2]=I[N/2]

②下面的圖4顯示了第三步完成以后存儲器中的數(shù)據(jù)情況,RP[k]和IP[k]存儲在上半部分，RM[k]和IM[k]存儲在下半部分。2200hRP[0]=R[0]2201hIP[0]=I[0]2202hRP[1]2203hIP[1]2204hRP[2]2205hIP[2]2206hRP[3]2207hIP[3]2208hRP[4]2209hIP[4]220AhRP[5]220BhIP[5]22FEhRP[127]22FFhIP[127]2300ha[0]2301ha[1]2302hIM[127]2303hRM[127]2304hIM[126]2305hRM[126]2306hIM[125]2307hRM[125]2308hIM[124]2309hRM[124]230AhIM[123]230BhRM[123]23FEhIM[1]23FFhRM[1]圖4這一過程的程序代碼如下所示：unpack,asgAR2,XP_k.asgAR3,XP_Nminusk,asgAR6,XM_k

.asgAR7,XM_NminuskSTM#fft_data+2,XP_kSTM#fft_data+2*K_FFT_SIZE-2,XP_NminuskSTM#fft_data+2*K_FFT_SIZE+3,XM_NminuskSTM#fft_data+4*K_FFT_SIZE-1,XM_k;AR2指向R[k](tempRP[k]);AR3指向R[N-K](tempRP[N-K]);AR7指向;AR2指向R[k](tempRP[k]);AR3指向R[N-K](tempRP[N-K]);AR7指向tempRM[N-K];AR6指向tempRM[K];設置塊循環(huán)計數(shù)器RPTBDphase3end-1STM#3,AR0ADD*XP_k,*XP_Nminusk,ASUB*XP_k,*XP_Nminusk,BSTHA,ASM,*XP_k+STHA,ASM,*XP_Nminusk+STHB,ASM,*XM_k-NEGBSTHB,ASM,*XM_Nminusk-ADD*XP_k,*XP_Nminusk,ASUB*XP_k,*XP_Nminusk,BSTHA,ASM,*XP_k+STHA,ASM,*XP_Nminusk-0STHB,ASM,*XM_k-NEGBSTHB,ASM,*XM_Nminusk+0phase3end:;從以下指令到phase3end-1處一直;重復執(zhí)行BRC中規(guī)定的次數(shù);設置AR0以備下面程序尋址使用;A:=R[k]+R[N-K]=2*RP[k];B:=R[k]-R[N-K]=2*RM[k];在AR[k]處存儲RP[k];在AR[N-K]處存儲RP[N-K]=RP[k];在AI[2N-K]處存儲RM[k];B:=R[N-K]-R[k]=2*RM[N-K];在AI[N+k]處存儲RM[N-K];A:=I[k]+I[N-K]=2*IP[k];B:=I[k]-I[N-K]=2*IM[k];在AI[k]處存儲IP[k];在AI[N-K]處存儲IP[N-K]=IP[k];在AR[2N-K]處存儲IM[k];B:=I[N-K]-I[k]=2*IM[N-K];在AR[N+k]處存儲IM[N-K]產(chǎn)生2N=256個點的復數(shù)輸出，它與原始的256個點的實輸入序列的DFT一致。輸出駐留在數(shù)據(jù)緩沖器中。通過下面的公式由RP[k]、RM[n]、IP[n]和IM[n]四個序列可以計算出a[n]的DFT：AR[k]=AR[2N-k]=RP[k]+cos(kn/N)*IP[k]-sin(kn/N)*RM[k]AI[k]=-AI[2N-k]=IM[k]-cos(kn/N)*RM[k]-sin(kn/N)*IP[k]AR[0]=RP[0]+IP[0]AI[0]=IM[0]-RM[0]AR[N]=R[0]-I[0]AI[N]=0其中：A[k]=A[2N-k]=AR[k]+jAI[k]=F{a(n)}實數(shù)FFT輸出按照實數(shù)/虛數(shù)的自然順序填滿整個4N=512個字節(jié)的數(shù)據(jù)處理緩沖器。如圖5所示。

2200hAR[0]2201hAI[0]2202hAR[1]2203hAI[1]2204hAR[2]2205hAI[2]22FFhAI[127]2300hAR[128]2301hAI[128]2302hAR[129]2303hAI[129]2304hAR[200]2305hAI[200]23FFhAI[255]圖5這一段程序可以和上面的步驟3的程序合成一個子程序unpack，這一步的程序代碼如下：ST#0,*XM_k-ST#0,*XM_k；計算AR[0],AI[0],AR[N],AI[N],asgAR2,AX_k,asgAR4,IP_0,asgAR5,AX_NSTM#fft_data,AX_kSTM#fft_data+1,IP_0STM#fft_data+2*K_FFT_SIZE+1,AX_NADD*AX_k,*IP_0,ASUB*AX_k,*IP_0,BSTHA,ASM,*AX_k+ST#0,*AX_kMVDD*AX_k+,*AX_N-;RM[N/2]=0;IM[N/2]=0;AR2指向AR[0](tempRP[0]);AR4指向AI[0](tempIP[0])；;RM[N/2]=0;IM[N/2]=0;AR2指向AR[0](tempRP[0]);AR4指向AI[0](tempIP[0])；AR5指向AI[N];A:=RP[0]+IP[0];B:=RP[0]-IP[0];AR[0]=(RP[0]+IP[0])/2;AI[0]=0;AI[N]=0;AR[N]=(RP[0]-IP[0])/2,asgAR5,SINSTM#fft_data+4*K_FFT_SIZE-1,AX_2Nminusk;AR3指向AI[2N-1](tempRM[1])STM#cos_table+K_TWID_TBL_SIZE/K_FFT_SIZE,COS;AR4指向cos(k*n/N)STM#sine_table+K_TWID_TBL_SIZE/K_FFT_SIZE,SIN;AR5指向sin(k*n/N)STM#K_FFT_SIZE-2,BRCRPTBDphase4end-4STM#K_TWID_TBL_SIZE/K_FFT_SIZE,AR0；AR0中存入旋轉因子表的大；小以備循環(huán)尋址時使用LD*AX_k+,16,AMACR*COS,*AX_k,AMASR*SIN,*AX_2Nminusk-,A;A:=RP[k]1修改AR2指向IP[k];A:=A+cos(k*n/N)*IP[k];A:=A-sin(k*n/N)*RM[k]II;修改AR3指向IM[k]LD*AX_2Nminusk+,16,BMASR*SIN+0%,*AX_k-,B;B:=IM[k]II修改AR3指向RM[k];B:=B-sin(k*n/N)*IP[k]II;修改AR2指向RP[k]MASR*COS+0%,*AX_2Nminusk,BSTHA,ASM,*AX_k+STHB,ASM,*AX_k+NEGB;B:=B-cos(k*n/N)*RM[k];AR[k]=A/2;AI[k]=B/2;B:=-BSTHB,ASM,*AX_2Nminusk-STHA,ASM,*AX_2Nminusk-;AI[2N-K]=-AI[k]=B/2;AR[2N-K]=AR;[k]=A/2phase4end:3.計算所求信號的功率由于最后所得的FFT數(shù)據(jù)是一個復數(shù)，為了能夠方便的在虛擬頻譜儀上觀察該信號的特征，我們通常對所得的FFT數(shù)據(jù)進行處理一一取其實部和虛部的平方和，即求得該信號的功率。power:,asgAR2,AX,asgAR3,OUTPUT_BUFpshmst0;保存寄存器的值pshmar0pshmbkSTM#d_output_addr,OUTPUT_BUF;AR3指向輸出緩沖地址STM#K_FFT_SIZE*2-1,BRC;塊循環(huán)計數(shù)器設置為255RPTBDpower_end-4；帶延遲方式的重復執(zhí)行指令STM#fft_data,AX;AR2指向AR[0]SQUR*AX+,A；A:=AR2SQURA*AX+,A；A:=AR2+AI2STHA,7,*OUTPUT_BUF;將A中的數(shù)據(jù)存入輸出緩沖中，ANDM#7FFFH,*OUTPUT_BUF+；避免輸出數(shù)據(jù)過大在虛擬示波器；中顯示錯誤popmbk；保存各個寄存器值popmar0popmst0power_end:RET注意，在上面的程序中將數(shù)據(jù)放回輸出緩沖準備輸出時使用了指令：STHA,7,*OUTPUT_BUF對accA左移7位是為了讓顯示的數(shù)據(jù)值在一個合適的范圍內(nèi)有利于觀察顯示的圖形，由于所有的數(shù)據(jù)都左移了7位，所以從總體上看整個波形的性質還是一樣的。同時，由于有的數(shù)據(jù)太大，為了避免顯示數(shù)據(jù)的溢出而導致在虛擬示波器中觀察到的波形錯誤所以我們使用了指令：ANDM#7FFFH,*OUTPUT_BUF+來取出有效的數(shù)據(jù)位數(shù)。圖6設置探針點和斷點三、實驗內(nèi)容本實驗在CCS下完成256點的實數(shù)FFT，并通過CCS的圖形顯示工具觀察結果。其主程序為初始化，并通過探針工具讀入256點方波數(shù)據(jù)（在文件fft.dat中，該數(shù)據(jù)文件可以通過程序fft_data.c修改，但注意數(shù)據(jù)的絕對值不要超過0x23ff）。FFT的實現(xiàn)由四個子程序代

碼bit_rev、fft、unpack和power代碼完成。實驗可以分為以下幾步：（1）啟動CCS，在Project菜單相項中打開FFT目錄下的fft.mak文件。（2）用鼠標展開左面項目欄，打開fft.asm源程序。（3）使用Bulid命令完成編譯、連接，并使用LoadProgram將生成的fft.out裝入5402片內(nèi)存儲器。（4）（5）將光標移動到下一行“nop”語句，使用工具設置一個斷點，該行變?yōu)檠蠹t色。（4）（5）將光標移動到下一行“nop”語句，使用工具設置一個斷點，該行變?yōu)檠蠹t色。（6）在File菜單中打開選項“FileI/O”，使用“AddFile”在FFT目錄下打開數(shù)據(jù)文件fft.dat，然后修改“Address”參數(shù)為0x2300，修改“Length”參數(shù)為256。這表示程序執(zhí)行到探針點時，將從fft.dat文件中讀出256個數(shù)據(jù)，并將數(shù)據(jù)放入0x2300開始的存儲器中。你可以選擇“WrapAround”，循環(huán)使用該數(shù)據(jù)文件。圖7圖7設置探針參數(shù)（7）選擇“AddProbePoint”，將探針點與數(shù)據(jù)文件連接起來。參見圖8。選擇探針點，然后在“Connect”選項中選擇需要使用的數(shù)據(jù)文件名，再選擇“Replace”，按確定鍵完成。這時將返回圖7所示的對話框。你可以看到“Probe”項被自動修改為“Connected”，表示探針已經(jīng)與數(shù)據(jù)文件成功相連。（8）完成探針設置后，可以使用F5或“Run”命令啟動程序運行。程序執(zhí)行到探針點時自動從數(shù)據(jù)文件讀出256個點的數(shù)據(jù)放入輸入緩沖0x2300。（9）在“View”菜單項下選擇“Graph->Time/Frequency”，打開一個圖形工具以便顯示輸入數(shù)據(jù)波形。將“StartAddress”改為0x2300，將“Acquisiti