ADSP TigerSHARC中利用查找表快速計(jì)算三角函數(shù)

1、ADSP TigerSHARC中利用查找表快速計(jì)算三角函數(shù)    作者Email: batistuta810226摘要：DSP算法中，三角函數(shù)的計(jì)算是一種運(yùn)算量比較大，占用時(shí)間比較長(zhǎng)的運(yùn)算。如果通過(guò)直接調(diào)用DSP生產(chǎn)商或者第三方提供的庫(kù)函數(shù)進(jìn)行運(yùn)算，往往需要占用比較多的時(shí)鐘周期。在實(shí)時(shí)性要求比較高的場(chǎng)合，調(diào)用庫(kù)函數(shù)進(jìn)行三角函數(shù)計(jì)算就不能夠達(dá)到實(shí)時(shí)性的要求。在這種情況下，利用查找表的方法來(lái)得到三角函數(shù)的值就成為一種可行，并能獲得很高實(shí)時(shí)性的計(jì)算方法。本文給出了一種在TS101中利用查找來(lái)實(shí)現(xiàn)三角函數(shù)計(jì)算的方法，并對(duì)這種算法的誤差和運(yùn)算量進(jìn)行了分析，從結(jié)論可

2、以看出，文中提出的通過(guò)查找表計(jì)算三角函數(shù)的方法有效而且運(yùn)行效率比較高。 關(guān)鍵詞：查找表        Tiger SHARC TS101 DSP        實(shí)時(shí)性 1    概述： 我們知道，在三角函數(shù)的運(yùn)算中，涉及到大量倒數(shù)和平方根的運(yùn)算。TS101的ALU指令中，提供了很方便的求倒數(shù)指令RECIPS和求平方根倒數(shù)指令RSQRTS，在一個(gè)指令周期內(nèi)，可以完成求一

3、個(gè)浮點(diǎn)數(shù)的倒數(shù)或者平方根倒數(shù)的運(yùn)算。但是，在TS101中，倒數(shù)和平方根倒數(shù)指令僅僅提供了8位浮點(diǎn)的近似值，特別在小數(shù)點(diǎn)后位數(shù)比較多的情況下，誤差比較大。并且，在很多計(jì)算過(guò)程中，隨著運(yùn)算步驟的增加，其誤差也不斷擴(kuò)大，最終將會(huì)導(dǎo)致運(yùn)算的結(jié)果遠(yuǎn)遠(yuǎn)偏離正常的數(shù)值。如果需要提高倒數(shù)和平方根倒數(shù)的運(yùn)算精度，就需要用到收斂算法，這樣就大大增加了運(yùn)算的周期數(shù)，使得運(yùn)算量驟增。在需要大量三角函數(shù)運(yùn)算的場(chǎng)合，這么大的運(yùn)算量就顯得很不合適，大大占用了系統(tǒng)的運(yùn)行時(shí)間。在ADSP的集成開(kāi)發(fā)環(huán)境Visual DSP 3.5+中，生產(chǎn)商雖然提供了進(jìn)行三角函數(shù)計(jì)算的庫(kù)函數(shù)，并具可以得到很高的計(jì)算精度，但是

4、它的運(yùn)算周期卻比較長(zhǎng)，很多情況下并不能滿足我們的要求。     ADSP TS101中提供了專用的加法器和乘法器，使得高精度的乘加運(yùn)算可以在一個(gè)周期內(nèi)得以完成。如果我們可以利用乘加運(yùn)算代替大運(yùn)算量的求倒數(shù)和求平方根運(yùn)算，那么程序運(yùn)行中就可以大大降低程序的時(shí)間消耗。而且，三角函數(shù)具有一定的周期性，我們可以通過(guò)三角函數(shù)周期性的變換，將角度值變換到一個(gè)周期內(nèi)，通過(guò)查表的方式來(lái)獲得三角函數(shù)的數(shù)值。這種方式直接利用了三角函數(shù)的周期性，其誤差大小決定于查找表的大小，也就是對(duì)一個(gè)周期內(nèi)三角函數(shù)的數(shù)值進(jìn)行采樣的密度。在誤差允許的情況下，可以以很高的運(yùn)算速度得到

5、三角函數(shù)的數(shù)值。 2    算法理論與DSP實(shí)現(xiàn)： （1）DSP算法：正弦和余弦函數(shù)是按照2為周期周期性變化的函數(shù)。對(duì)于 和 形式的函數(shù)，當(dāng)我們知道x的數(shù)值以后，就可以根據(jù)浮點(diǎn)數(shù)x的小數(shù)部分的數(shù)值求得函數(shù)的數(shù)值，而整數(shù)部分可以作為周期循環(huán)的部分不予考慮。所以運(yùn)算的重點(diǎn)在于如何將小數(shù)部分的數(shù)值轉(zhuǎn)變?yōu)椴楸頃r(shí)候所對(duì)應(yīng)的地址單元。我們?nèi)∮嘞液瘮?shù) 區(qū)間上的數(shù)值，在允許的計(jì)算精度范圍內(nèi)首先對(duì)其進(jìn)行采樣。因?yàn)橛嘞液瘮?shù)為偶函數(shù)，所以在整個(gè)自變量變化的范圍內(nèi)的三角函數(shù)運(yùn)算都可以轉(zhuǎn)變到 區(qū)間內(nèi)進(jìn)行。 對(duì)于三角函數(shù) 的數(shù)值的計(jì)

6、算，我們將其自變量x的取值區(qū)間以0為中心分為小于零和大于等于零兩部分。對(duì)于小于零的區(qū)間，首先求出x的絕對(duì)值，然后減去0.5，將得到的結(jié)果用fix指令求整，再用float指令將其表示為浮點(diǎn)數(shù)，將x的絕對(duì)值與用float指令求得的數(shù)值相減就提取出了數(shù)據(jù)的小數(shù)部分。對(duì)于大于零的區(qū)間，我們不用求其絕對(duì)值就可以直接按照上面的步驟提取出其小數(shù)部分。對(duì)于正弦函數(shù) ，由于正弦函數(shù)是奇函數(shù)，情況就相對(duì)比較復(fù)雜一些。這時(shí)需要判斷x的數(shù)值是大于零等于零還是小于零，如果在大于零的情況下，可以直接將小數(shù)部分提取出來(lái)，并對(duì)其進(jìn)行查表得到對(duì)應(yīng)的三角函數(shù)的數(shù)值，而在x的數(shù)值小于零的情況下，我們需要將在 區(qū)

7、間內(nèi)查表得到的數(shù)值再對(duì)其取負(fù)才可以得到相應(yīng)的三角函數(shù)的數(shù)值。我們得到小數(shù)部分的數(shù)值以后，將小數(shù)部分的數(shù)值和采樣的樣本點(diǎn)數(shù)進(jìn)行乘法運(yùn)算，就可以得到查表所需要的相對(duì)地址。 查表實(shí)現(xiàn)的簡(jiǎn)單的匯編語(yǔ)言算法實(shí)現(xiàn)如下（未優(yōu)化）：        xr11=0.5;        xfr20=abs r19;        fr21=r20-r11;   

8、0;    xr22=fix fr21;        xfr23=float r22; xfr4=r20-r23;        xfr5=r4*r3;                /r30    

9、;    查找表采樣樣本點(diǎn)數(shù)        xr6=fix fr5;        j3=xr6;        xr1:0=lj30+j3;            /j30    

10、;    查找表絕對(duì)地址     （2）查找表樣本制作和復(fù)指數(shù)信號(hào)的查表：在我們進(jìn)行科學(xué)計(jì)算時(shí)，經(jīng)常要碰到 形式的復(fù)指數(shù)運(yùn)算，由歐拉公式我們可以得到 。在我們得到x的值之后，可以對(duì) 和 一起進(jìn)行查表，從而得到相應(yīng)的三角函數(shù)數(shù)值。TS101種，每次可以對(duì)4個(gè)word進(jìn)行尋址操作。所以，我們?cè)谥爸谱鞑檎冶淼臅r(shí)候，對(duì)一個(gè)周期內(nèi)的正弦和余弦函數(shù)采樣之后，可以將正弦和余弦函數(shù)的查找表交叉存放。以64bit為單位，低32bit存放余弦函數(shù)的查找表數(shù)值，高32bit存放正弦函數(shù)的查找表數(shù)

11、值。這樣，在我們每次得到一個(gè)x的小數(shù)位數(shù)值之后就可以直接查找到兩個(gè)函數(shù)的三角函數(shù)值，從而得到 的數(shù)值，極大的方便了復(fù)指數(shù)的運(yùn)算。而且，采用TS101的單周期多指令方式，我們可以實(shí)現(xiàn)一個(gè)程序循環(huán)內(nèi)并行查找多個(gè)復(fù)指數(shù)信號(hào)數(shù)值的操作，從而將速度大大提高。 在我們進(jìn)行查找表運(yùn)算的時(shí)候，因?yàn)楹瘮?shù)是周期性變化的，所以往往涉及到很多邊界點(diǎn)的問(wèn)題。在我們提供的這種算法中，對(duì)于x的數(shù)值為0的情況下，根據(jù)我們提供的算法，這個(gè)時(shí)候最后提取的數(shù)值為1。這是一個(gè)很特殊的邊界點(diǎn)，在我們進(jìn)行運(yùn)算的時(shí)候必須將它的影響考慮進(jìn)去，否則將會(huì)影響運(yùn)算的結(jié)果。我們可以利用一種很簡(jiǎn)單的方法，就是在我們制作查找表的時(shí)候，將這種情

12、況考慮進(jìn)去。對(duì)采樣的區(qū)間取 而不是 。這樣，在我們進(jìn)行查表運(yùn)算的時(shí)候就可以避免邊界點(diǎn)錯(cuò)誤情況的出現(xiàn)。 3    誤差分析 利用查找表進(jìn)行三角函數(shù)的運(yùn)算是一種近似的算法。由于我們是對(duì)一個(gè)周期之內(nèi)的三角函數(shù)進(jìn)行的采樣，最終的結(jié)果必定會(huì)存在一種誤差。誤差的來(lái)源源自于兩個(gè)方面，一個(gè)是采樣存在的誤差，一個(gè)是在進(jìn)行查表運(yùn)算的時(shí)，計(jì)算表地址的時(shí)候由于需要對(duì)數(shù)值取整，會(huì)引入一定的誤差。這些誤差的大小直接決定了我們所需要的查找表的大小，下面我們就對(duì)信號(hào)處理中經(jīng)常用到的線性調(diào)頻信號(hào)脈沖壓縮的性能的影響來(lái)看一下該查表算法的精確度。（查找表采樣長(zhǎng)度16k）

13、圖二：查表數(shù)據(jù)與標(biāo)準(zhǔn)三角函數(shù)數(shù)據(jù)對(duì)比 （上圖為標(biāo)準(zhǔn)實(shí)部數(shù)據(jù)，下圖為查表所得實(shí)部數(shù)據(jù)） 圖三：絕對(duì)誤差示意圖我們看到，在查找表采樣點(diǎn)為16K的情況下，理論上的最大相對(duì)誤差為： 。我們運(yùn)算得到的最大相對(duì)誤差約為 5.2 * 10 (-4)，在精度不是要求十分高的情況下，已經(jīng)可以完全滿足我們的需要。 在經(jīng)過(guò)脈沖壓縮之后對(duì)比，經(jīng)過(guò)驗(yàn)證可以看出。兩者的結(jié)果的誤差已經(jīng)十分小，完全達(dá)到了可以忽略的地步。 圖四：脈沖壓縮結(jié)果比較（dB）4    運(yùn)算量大小比較     在ADSP集成開(kāi)發(fā)環(huán)境Visual

14、0;DSP 3.5+中進(jìn)行開(kāi)發(fā)時(shí)，通過(guò)調(diào)用系統(tǒng)提供的庫(kù)函數(shù)計(jì)算正弦和余弦函數(shù)的時(shí)候，所耗用的周期個(gè)數(shù)最少為20個(gè)周期，最多為58個(gè)周期，可以提供40bit的計(jì)算精度。在我們提供的算法中，雖然精度不能夠達(dá)到這么高，但是可以在35個(gè)周期內(nèi)計(jì)算2個(gè)復(fù)指數(shù)信號(hào)的函數(shù)值，也就是4個(gè)三角函數(shù)的數(shù)值。連續(xù)運(yùn)算，可以達(dá)到38個(gè)周期，對(duì)2個(gè)復(fù)指數(shù)信號(hào)的運(yùn)算。可以看出，我們雖然犧牲了三角函數(shù)的精度，但是卻得到了很高的運(yùn)算速度。在很多的計(jì)算場(chǎng)合下，我們并不需要得到十分精確的三角函數(shù)數(shù)值，只需要保證計(jì)算得到的函數(shù)規(guī)律在誤差允許的范圍內(nèi)就可以。這時(shí)候，本文提供的查表運(yùn)算可以保證有比較好的實(shí)時(shí)性。  

15、   利用這種查找表的方式進(jìn)行三角函數(shù)的運(yùn)算，優(yōu)點(diǎn)在于運(yùn)算的速度比較快，在精度要求不是很高的情況下，可以達(dá)到比較高的運(yùn)算速度。當(dāng)然，對(duì)于速度上的要求必然也會(huì)影響到處理的精度和誤差。如果對(duì)于三角函數(shù)的數(shù)值要求有比較高的精度，那么這種查表的方式就顯得不適合。這樣，我們所允許的誤差的大小，也就決定了我們所需要的查找表的大小。 5    結(jié)論     筆者在這里只是介紹了一種以查找表方式進(jìn)行三角函數(shù)運(yùn)算的方法，在筆者所需的實(shí)時(shí)運(yùn)算要求下，可以達(dá)到所需的要求。實(shí)際上該算法還有可以改進(jìn)和值得優(yōu)化的地方，比如（1）查找表縮小到 區(qū)間內(nèi)，根據(jù)函數(shù)的周期性，可以把運(yùn)算統(tǒng)一到 的區(qū)間內(nèi)，在采樣點(diǎn)數(shù)不增加的情況下，而提高精度。（2）TS101種，提供了三個(gè)Bank的內(nèi)部存儲(chǔ)空間，每塊存儲(chǔ)空間的大小分別為2Mbit。如果我們的查找表比較