DSP常見算法的實現

1、3.6 常見的算法實現在實際應用中雖然信號處理的方式多種多樣，但其算法的基本要素卻大多相同，在本節(jié)中介紹幾種較為典型的算法實現，希望通過對這些例子（單精度，16bit）的分析，能夠讓大家熟悉DSP編程中的一些技巧，在以后的工作中可以借鑒，達到舉一反三的效果。1. 函數的產生在高級語言的編程中，如果要使用諸如正弦、余弦、對數等數學函數，都可以直接調用運行庫中的函數來實現，而在DSP編程中操作就不會這樣簡單了。雖然TI公司提供的實時運行庫中有一些數學函數，但它們所耗費的時間大多太長，而且對于大多數定點程序使用雙精度浮點數的返回結果有點“大材小用”的感覺，因此需要編程人員根據自身的要求“定制”數學函

2、數。實現數學函數的方法主要有查表法、迭代法和級數逼近法等，它們各有特點，適合于不同的應用。查表法是最直接的一種方法，程序員可以根據運算的需要預先計算好所有可能出現的函數值，將這些結果編排成數據表，在使用時只需要根據輸入查出表中對應的函數值即可。它的特點是速度快，但需要占用大量的存儲空間，且靈活度低。當然，可以對上述查表法作些變通，僅僅將一些關鍵的函數值放置在表中，對任意一個輸入，可根據和它最接近的數據采用插值方法來求得。這樣占用的存儲空間有所節(jié)約，但數值的準確度有所下降。迭代法是一種非常有用的方法，在自適應信號處理中發(fā)揮著重要的作用。作為函數產生的一種方法，它利用了自變量取值臨近的函數值之間存

3、在的關系，如時間序列分析中的AR、MA、ARMA等模型，刻畫出了信號內部的特征。因為它只需要存儲信號模型的參量和相關的狀態(tài)變量，所以所占用的存儲空間相對較少，運算時間也較短。但它存在一個致命的弱點，由于新的數值的產生利用了之前的函數值，所以它容易產生誤差累積，適合精度要求不高的場合。級數逼近法是用級數的方法在某一自變量取值范圍內去逼近數學函數，而將自變量取值在此范圍外的函數值利用一些數學關系，用該范圍內的數值來表示。這種方法最大的優(yōu)點是靈活度高，且不存在誤差累積，數值精度由程序員完全控制。該方法的關鍵在于選擇一個合適的自變量取值區(qū)間和尋找相應的系數。下面通過正弦函數的實現，具體對上述三種方法作

4、比較。查表法較簡單，只需要自制一張數據表，也可以利用C5400 DSP ROM內的正弦函數表。迭代法的關鍵是尋找函數值間的遞推關系。假設函數采樣時間間隔為T，正弦函數的角頻率為，那么可以如下推導：令等式的左邊展開為等式的右邊展開為對比系數，可以得到。令，便可以得到如下的遞推式：令，逐一迭代就能夠獲得采樣間隔為T的正弦序列了。從迭代公式可以更清楚地看出，這種方法存在誤差累積。再來看級數逼近法，首先需要尋找一個合適的自變量取值區(qū)間和尋找相應的系數。從正弦函數的對稱性可知，只需要計算取值在內的函數就可以推斷出所有取值范圍內的函數。接下來尋找系數，對于可以作如下變換，那么y的取值范圍在內，而sin_n

5、ew( )與sin( )同構，所以在下面的分析中將sin_new( )替代sin( )，提到的正弦函數即指sin_new( )。若匯編編程時采用的數據為Q15格式，那么取值與實際的弧度的對應關系如下圖所示。圖3- 算法取值與弧度的對應關系在內，正弦函數的修正級數（五次）展開如下式：根據上式，可以寫出正弦函數的生成程序。;compute polynomialstlmA, T;T=xstm#SinePolyCoeff, AR2ld*AR2+, 16, A;AH=c5ld*AR2+, 16, B;BH=c4poly*AR2+;A=c5*x+c4poly*AR2+;A=c5*x2+c4*x+c3pol

6、y*AR2+;A=c5*x3+c4*x2+c3*x+c2poly*AR2+;A=c5*x4+c4*x3+c3*x2+c2*x+c1mpyaAsftaA, 3;adjust AH to Q15SinePolyCoeff:;in Q12 format.word0x1cce; 1.800293(coef for x5 = c5).word0x08b7; 0.5446778(coef for x4 = c4).word0xaacc; -5.325196(coef for x3 = c3).word0x0053; 0.02026367(coef for x2 = c2).word0x3240; 3.14

7、0625(coef for x1 = c1)在編程過程中，使用到了POLY語句，它能夠使多項式的計算簡潔快速地完成。該函數的結果可以通過實驗X來驗證。2. FIR濾波器的實現FIR濾波器由于具有線性相位而且延遲能夠確定，因而在信號處理中廣泛應用。FIR的基本模型如下圖所示。圖3- FIR模型其數學表達式為，根據該表達式可以給出一種最為直接的實現形式。直接形式中采用線性地址來存放數據，如圖3- 所示。圖3- 直接形式程序中可以采用MACD來實現程序如下：ld*(Input), AstlA, *(x_n)stm#x_n_Nm1, AR2mpy*AR2-, #h_Nm1, Brpt#N-2macd*

8、AR2-, h_Nm2, B程序首先將新的數據放置在xn處，然后對狀態(tài)緩存由下而上計算，在循環(huán)語句中每執(zhí)行一次狀態(tài)變量自動向下移動一級，即自動更新。它的計算量基本為N個時鐘周期。當然，數據存放還可以采用循環(huán)緩存。另外，由于FIR的系數存在對稱性，其結構如圖3- 所示。那么可以利用這個特點，實現更為快速的計算。圖3- 對稱結構的FIR為計算方便將狀態(tài)變量分別存放在兩個緩存區(qū)間內，一塊命名為Buffer_new，存放圖3- 上半部分的數據，另一塊命名為Buffer_old，存放圖3- 下半部分的數據。它們都當循環(huán)緩存使用，大小為FIR階數的一半，即N/2（常數SIZE）。根據上述原理編寫的匯編程序

9、如下：stm#Buffer_new, AR2stm#Buffer_old, AR3stm#SIZE, BKstm# -1, AR0fir_loop:;read inputld*(Input), AstlA, *AR2;filteringadd*AR2+0%, *AR3+0%, ArptzB, #SIZE-1firs*AR2+0%, *AR3+0%, FIR_CoeffsthB, *(Output);store outputmar*+AR2(2)%mar*AR3+%mvdd*AR2, *AR3+0%;update bufferbfir_loop為方便理解，在圖3- 中，將狀態(tài)變量更新的過程標明，

10、左邊的是Buffer_new，右邊的是Buffer_old。開始時，指針AR2和AR3分別指向Buffer_new和Buffer_old中的x0與x-19，將最“新”的數據存進Buffer_new（步驟1）。利用FIRS實現FIR，結果放在BH中。計算結束后，AR2和AR3分別指向x-1和x-18（步驟2）。然后調整AR2，讓它指向Buffer_new中最“老”的數據x-9 （步驟3）；調整AR3，讓它指向Buffer_old中最“老”的數據x-19（步驟4）。接下來進行數據更新，將Buffer_new中最“老”的數據放進Buffer_old中，成為最“新”的數據。最后AR2指向x-9的位置，

11、這個位置將在下次計算時放置新的輸入；AR3指向x-18，即Buffer_old中最“老”的數據，便于下次計算（步驟5）。圖3- 對稱結構的FIR實現中狀態(tài)變量的更新利用對稱結構的實現在計算量上有了減少，大約為N/2個時鐘周期。當然，利用上述結構必須注意安排好數據的位置，以保證能進行正常的循環(huán)尋址。3. IIR濾波器的實現IIR濾波器也是數字信號處理的主要工具之一，但由于它不具備線性相位，而且無法準確知道其延遲，所以使用較FIR少。下面，來觀察一下IIR的結構，其數學表達式如下：從其數學公式可以看出，我們可以仿照在FIR處理來直接實現。定義兩段緩存分別對應于x 和y ，然后采用類似于FIR的計算

12、方式，采用MACD語句，便能很快地完成IIR濾波。在直接實現中同時需要保存x 和y ，當其階數較大時，會占用比較大的數據空間。為此，我們來考察IIR的另一種結構。如圖3- ，在這種結構中存儲的狀態(tài)變量為d ，所以存儲空間大大地減少了。圖3- IIR的另一種結構通過對FIR和IIR算法的分析，一方面向讀者介紹這些基本處理中的設計技巧，另一方面也提醒讀者在算法實現過程中應充分考察算法本身的特點，以求利用它們獲得高效的運算和存儲空間的節(jié)省。4. FFT的實現在信號處理中，為突出信號的特征，經常在時域和頻域之間作變換，而傅立葉變換是這當中最為典型的?；?的快速傅立葉變換有比特翻轉排序和蝶形運算組成，前

13、者在3.x節(jié)已經作了介紹，這里著重介紹蝶形運算的實現。蝶形運算是快速傅立葉變換中設計得極為精巧的部分，它充分揭示了傅立葉變換系數間內在的關系，而且還能實現同址計算，如圖所示。完成一次蝶形運算需要一次復數的乘法和兩次復數的加法。圖3- 蝶形運算的示意圖對于時間抽取的FFT而言，在其第一級是乘法的系數為（也就是1），那么這個復數的乘法就名存實亡了，因而在計算FFT時，第一級可以直接用復數的加法實現。第一級的程序如下：;* stage 1 * stm#0, BK ld#-1, ASM stm#FFT_Data, PX stm#FFT_Data+K_DATA_IDX_1, QX ld*PX, 16,

14、A;AH=PX.x stm#K_FFT_SIZE/2-1, BRC rptbdstage1end-1 stm #K_DATA_IDX_1+1, AR0 add*QX, 16, A;AH=PX.x+QX.x sthA, ASM, *PX+ stB, *QX+|ld*PX, A;AH=PX.y add*QX, 16, A;AH=PX.y+QX.y sthA, ASM, *PX+0 stB, *QX+0%|ld*PX, Astage1end:在代碼中，為方便與圖3- 對應，使用.asg偽指令將寄存器的名字替換成示意圖中的表達方式，PX和QX分別指向蝶形運算的數據的地址。可見所有的操作完全是由加減實現

15、的。在第二級中乘法的系數為和（即+1和-j），那么乘法操作只是影響參數的符號，在復數的加減運算時只要弄清與-j相乘造成的結果，所有的操作仍然可以只用加減法來實現。第二級的實現代碼如下：;* Stage 2 * stm#FFT_Data, PX stm#FFT_Data+K_DATA_IDX_2, QX ld*PX, 16, A;AH=PX.x stm#K_FFT_SIZE/4-1, BRC rptbdstage2end-1 stm#K_DATA_IDX_2+1, AR0; 1st butterfly add*QX, 16, A;AH=PX.x+QX.x sthA, ASM, *PX+ stB,

16、 *QX+|ld*PX, A;AH=PX.y add*QX, 16, A;AH=PX.y+QX.y sthA, ASM, *PX+ sthB, ASM, *QX+; 2nd butterfly mar*QX+ add*PX, *QX, A;AH=PX.x+QX.y sthA, ASM, *PX+ stB, *QX|ld*QX+, B;BH=QX.x stA, *PX|add*PX+0%, A;AH=PX.y+QX.x stA, *QX+0%|ld*PX, Astage2end:第二級與第一級相同，計算中不包含乘法。從第三級開始，乘法系數的特征就沒有第一、第二級那樣好了，所以只能直接采用圖3-

17、的方法來計算，代碼如下。;* Stage 3 through Stage logN * stm#K_TWID_TBL_SIZE, BK st#K_TWID_IDX_3, *(d_twid_idx) stm#K_TWID_IDX_3, AR0 stm#Cos, WR stm#Sin, 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: stm#FFT_Data, PX

18、 ld*(d_data_idx), A add*(PX), A stlmA, QX mvdk*(d_grps_cnt), GROUP_COUNTERgroup: mvmdBUTTERFLY_COUNTER, BRC rptbdbutterflyend-1 ld*WR, T; T := WR mpy*QX+, A ; A := QR*WR | QX->QI macr*WI+0%, *QX-, A ; A := QR*WR+QI*WI ; | QX->QR add*PX, 16, A, B ; B := (QR*WR+QI*WI)+PR stB, *PX ; PR':=(QR*

19、WR+QI*WI)+PR)/2|sub*PX+, B; B=PR-(QR*WR+QI*WI); | PX->PI stB, *QX ; QR':= (PR-(QR*WR+QI*WI)/2|mpy*QX+, A ; A := QR*WI T=WI ; | QX->QI masr*QX, *WR+0%, A ; A := QR*WI-QI*WR add*PX, 16, A, B ; B := (QR*WI-QI*WR)+PI stB, *QX+ ; QI':=(QR*WI-QI*WR)+PI)/2|sub*PX, B; B=PI-(QR*WI-QI*WR) ld*WR,

20、 T ; T := WR stB, *PX+ ; PI':= (PI-(QR*WI-QI*WR)/2|mpy*QX+, A ; | PX->PR ; A := QR*WR | QX->QIbutterflyend:; Update pointers for next group pshmAR0 mvdk*(d_data_idx), AR0 mar*PX+0 mar*QX+0 banzdgroup, *GROUP_COUNTER- popmAR0 mar*QX-; Update counters and indices for next stage ld*(d_data_idx), A sub#1, A, B stlmB, BU