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