ADSP TigerSHARC中利用查找表快速計算三角函數
加入技術(shù)交流群
作者Email: batistuta810226@sina.com
摘要：DSP算法中，三角函數的計算是一種運算量比較大，占用時(shí)間比較長(cháng)的運算。如果通過(guò)直接調用DSP生產(chǎn)商或者第三方提供的庫函數進(jìn)行運算，往往需要占用比較多的時(shí)鐘周期。在實(shí)時(shí)性要求比較高的場(chǎng)合，調用庫函數進(jìn)行三角函數計算就不能夠達到實(shí)時(shí)性的要求。在這種情況下，利用查找表的方法來(lái)得到三角函數的值就成為一種可行，并能獲得很高實(shí)時(shí)性的計算方法。本文給出了一種在TS101中利用查找來(lái)實(shí)現三角函數計算的方法，并對這種算法的誤差和運算量進(jìn)行了分析，從結論可以看出，文中提出的通過(guò)查找表計算三角函數的方法有效而且運行效率比較高。
關(guān)鍵詞：查找表TigerSHARCTS101DSP實(shí)時(shí)性
1．概述：
我們知道，在三角函數的運算中，涉及到大量倒數和平方根的運算。TS101的ALU指令中，提供了很方便的求倒數指令RECIPS和求平方根倒數指令RSQRTS，在一個(gè)指令周期內，可以完成求一個(gè)浮點(diǎn)數的倒數或者平方根倒數的運算。但是，在TS101中，倒數和平方根倒數指令僅僅提供了8位浮點(diǎn)的近似值，特別在小數點(diǎn)后位數比較多的情況下，誤差比較大。并且，在很多計算過(guò)程中，隨著(zhù)運算步驟的增加，其誤差也不斷擴大，最終將會(huì )導致運算的結果遠遠偏離正常的數值。如果需要提高倒數和平方根倒數的運算精度，就需要用到收斂算法，這樣就大大增加了運算的周期數，使得運算量驟增。在需要大量三角函數運算的場(chǎng)合，這么大的運算量就顯得很不合適，大大占用了系統的運行時(shí)間。在ADSP的集成開(kāi)發(fā)環(huán)境VisualDSP3.5++中，生產(chǎn)商雖然提供了進(jìn)行三角函數計算的庫函數，并具可以得到很高的計算精度，但是它的運算周期卻比較長(cháng)，很多情況下并不能滿(mǎn)足我們的要求。
ADSPTS101中提供了專(zhuān)用的加法器和乘法器，使得高精度的乘加運算可以在一個(gè)周期內得以完成。如果我們可以利用乘加運算代替大運算量的求倒數和求平方根運算，那么程序運行中就可以大大降低程序的時(shí)間消耗。而且，三角函數具有一定的周期性，我們可以通過(guò)三角函數周期性的變換，將角度值變換到一個(gè)周期內，通過(guò)查表的方式來(lái)獲得三角函數的數值。這種方式直接利用了三角函數的周期性，其誤差大小決定于查找表的大小，也就是對一個(gè)周期內三角函數的數值進(jìn)行采樣的密度。在誤差允許的情況下，可以以很高的運算速度得到三角函數的數值。
2．算法理論與DSP實(shí)現：
（1）DSP算法：正弦和余弦函數是按照2π為周期周期性變化的函數。對于和形式的函數，當我們知道x的數值以后，就可以根據浮點(diǎn)數x的小數部分的數值求得函數的數值，而整數部分可以作為周期循環(huán)的部分不予考慮。所以運算的重點(diǎn)在于如何將小數部分的數值轉變?yōu)椴楸頃r(shí)候所對應的地址單元。我們取余弦函數區間上的數值，在允許的計算精度范圍內首先對其進(jìn)行采樣。因為余弦函數為偶函數，所以在整個(gè)自變量變化的范圍內的三角函數運算都可以轉變到區間內進(jìn)行。
對于三角函數的數值的計算，我們將其自變量x的取值區間以0為中心分為小于零和大于等于零兩部分。對于小于零的區間，首先求出x的絕對值，然后減去0.5，將得到的結果用fix指令求整，再用float指令將其表示為浮點(diǎn)數，將x的絕對值與用float指令求得的數值相減就提取出了數據的小數部分。對于大于零的區間，我們不用求其絕對值就可以直接按照上面的步驟提取出其小數部分。對于正弦函數，由于正弦函數是奇函數，情況就相對比較復雜一些。這時(shí)需要判斷x的數值是大于零等于零還是小于零，如果在大于零的情況下，可以直接將小數部分提取出來(lái)，并對其進(jìn)行查表得到對應的三角函數的數值，而在x的數值小于零的情況下，我們需要將在區間內查表得到的數值再對其取負才可以得到相應的三角函數的數值。我們得到小數部分的數值以后，將小數部分的數值和采樣的樣本點(diǎn)數進(jìn)行乘法運算，就可以得到查表所需要的相對地址。查表實(shí)現的簡(jiǎn)單的匯編語(yǔ)言算法實(shí)現如下（未優(yōu)化）：
xr11=0.5;;
xfr20=absr19;;
fr21=r20-r11;;
xr22=fixfr21;;
xfr23=floatr22;;
xfr4=r20-r23;;
xfr5=r4*r3;;//r30查找表采樣樣本點(diǎn)數
xr6=fixfr5;;
j3=xr6;;
xr1:0=l[j30+j3];;//j30查找表絕對地址
（2）查找表樣本制作和復指數信號的查表：在我們進(jìn)行科學(xué)計算時(shí)，經(jīng)常要碰到形式的復指數運算，由歐拉公式我們可以得到。在我們得到x的值之后，可以對和一起進(jìn)行查表，從而得到相應的三角函數數值。TS101種，每次可以對4個(gè)word進(jìn)行尋址操作。所以，我們在之前制作查找表的時(shí)候，對一個(gè)周期內的正弦和余弦函數采樣之后，可以將正弦和余弦函數的查找表交叉存放。以64bit為單位，低32bit存放余弦函數的查找表數值，高32bit存放正弦函數的查找表數值。這樣，在我們每次得到一個(gè)x的小數位數值之后就可以直接查找到兩個(gè)函數的三角函數值，從而得到的數值，極大的方便了復指數的運算。而且，采用TS101的單周期多指令方式，我們可以實(shí)現一個(gè)程序循環(huán)內并行查找多個(gè)復指數信號數值的操作，從而將速度大大提高。
在我們進(jìn)行查找表運算的時(shí)候，因為函數是周期性變化的，所以往往涉及到很多邊界點(diǎn)的問(wèn)題。在我們提供的這種算法中，對于x的數值為0的情況下，根據我們提供的算法，這個(gè)時(shí)候最后提取的數值為1。這是一個(gè)很特殊的邊界點(diǎn)，在我們進(jìn)行運算的時(shí)候必須將它的影響考慮進(jìn)去，否則將會(huì )影響運算的結果。我們可以利用一種很簡(jiǎn)單的方法，就是在我們制作查找表的時(shí)候，將這種情況考慮進(jìn)去。對采樣的區間取而不是。這樣，在我們進(jìn)行查表運算的時(shí)候就可以避免邊界點(diǎn)錯誤情況的出現。
3．誤差分析
利用查找表進(jìn)行三角函數的運算是一種近似的算法。由于我們是對一個(gè)周期之內的三角函數進(jìn)行的采樣，最終的結果必定會(huì )存在一種誤差。誤差的來(lái)源源自于兩個(gè)方面，一個(gè)是采樣存在的誤差，一個(gè)是在進(jìn)行查表運算的時(shí)，計算表地址的時(shí)候由于需要對數值取整，會(huì )引入一定的誤差。這些誤差的大小直接決定了我們所需要的查找表的大小，下面我們就對信號處理中經(jīng)常用到的線(xiàn)性調頻信號脈沖壓縮的性能的影響來(lái)看一下該查表算法的精確度。（查找表采樣長(cháng)度16k）
（上圖為標準實(shí)部數據，下圖為查表所得實(shí)部數據）
圖三：絕對誤差示意圖
我們看到，在查找表采樣點(diǎn)為16K的情況下，理論上的最大相對誤差為：
在經(jīng)過(guò)脈沖壓縮之后對比，經(jīng)過(guò)驗證可以看出。兩者的結果的誤差已經(jīng)十分小，完全達到了可以忽略的地步。
圖四：脈沖壓縮結果比較（dB）
4．運算量大小比較
在ADSP集成開(kāi)發(fā)環(huán)境VisualDSP3.5++中進(jìn)行開(kāi)發(fā)時(shí)，通過(guò)調用系統提供的庫函數計算正弦和余弦函數的時(shí)候，所耗用的周期個(gè)數最少為20個(gè)周期，最多為58個(gè)周期，可以提供40bit的計算精度。在我們提供的算法中，雖然精度不能夠達到這么高，但是可以在35個(gè)周期內計算2個(gè)復指數信號的函數值，也就是4個(gè)三角函數的數值。連續運算，可以達到38個(gè)周期，對2個(gè)復指數信號的運算?？梢钥闯?，我們雖然犧牲了三角函數的精度，但是卻得到了很高的運算速度。在很多的計算場(chǎng)合下，我們并不需要得到十分精確的三角函數數值，只需要保證計算得到的函數規律在誤差允許的范圍內就可以。這時(shí)候，本文提供的查表運算可以保證有比較好的實(shí)時(shí)性。
利用這種查找表的方式進(jìn)行三角函數的運算，優(yōu)點(diǎn)在于運算的速度比較快，在精度要求不是很高的情況下，可以達到比較高的運算速度。當然，對于速度上的要求必然也會(huì )影響到處理的精度和誤差。如果對于三角函數的數值要求有比較高的精度，那么這種查表的方式就顯得不適合。這樣，我們所允許的誤差的大小，也就決定了我們所需要的查找表的大小。
5．結論
筆者在這里只是介紹了一種以查找表方式進(jìn)行三角函數運算的方法，在筆者所需的實(shí)時(shí)運算要求下，可以達到所需的要求。實(shí)際上該算法還有可以改進(jìn)和值得優(yōu)化的地方，比如（1）查找表縮小到區間內，根據函數的周期性，可以把運算統一到的區間內，在采樣點(diǎn)數不增加的情況下，而提高精度。（2）TS101種，提供了三個(gè)Bank的內部存儲空間，每塊存儲空間的大小分別為2Mbit。如果我們的查找表比較大，占用了很大的內存空間的話(huà)，在最終程序修訂，并需要通過(guò)主控計算機或者EPROM加載的時(shí)候，就會(huì )增大加載的文件的大小。所以，我們需要在查表的大小和精度、誤差、程序占用空間大小方面取一個(gè)權衡，來(lái)決定查表的大小和計算的精度。
筆者在這里介紹的是一種在本人實(shí)際工程經(jīng)驗中所采用的三角函數的計算方法，望不足之處讀者能夠給與指出與修正。
聯(lián)系E_mail:batistuta810226@sina.com
評論