基于自適應(yīng)查找表法的FPGA內(nèi)高精度求模取對(duì)數(shù)模塊設(shè)計(jì)

徐修峰

(中國(guó)電子科技集團(tuán)公司第三十八研究所,合肥230088)

基于自適應(yīng)查找表法的FPGA內(nèi)高精度求模取對(duì)數(shù)模塊設(shè)計(jì)

徐修峰

(中國(guó)電子科技集團(tuán)公司第三十八研究所,合肥230088)

摘要：作為通用的處理器,FPGA優(yōu)勢(shì)不言而喻,但也存在一些明顯的不足,復(fù)數(shù)的求模取對(duì)數(shù)運(yùn)算就是其中之一。介紹了一種利用CORDIC算法完成高精度的求模運(yùn)算,再利用自適應(yīng)查找表法實(shí)現(xiàn)高精度取對(duì)數(shù)運(yùn)算。該流程實(shí)現(xiàn)簡(jiǎn)單,運(yùn)行速率快。

關(guān)鍵詞:FPGA;CORDIC;求模值;取對(duì)數(shù);自適應(yīng)查找表法

0引言

在現(xiàn)代雷達(dá)信號(hào)處理過(guò)程中,通常將回波信號(hào)分解為實(shí)部和虛部來(lái)進(jìn)行處理,最后再將處理后的數(shù)據(jù)進(jìn)行復(fù)信號(hào)求模取對(duì)數(shù)操作,或者當(dāng)信號(hào)由實(shí)域轉(zhuǎn)換為頻域之后也需要對(duì)得到的復(fù)信號(hào)進(jìn)行求模操作。因此,對(duì)于復(fù)數(shù)信號(hào)的求模和取對(duì)數(shù)操作是必不可少的一個(gè)環(huán)節(jié),在雷達(dá)信號(hào)處理中有著廣泛的使用。

近年來(lái),FPGA技術(shù)的發(fā)展異常迅猛,已經(jīng)逐漸成為雷達(dá)信號(hào)處理的主要高速處理器。利用FPGA進(jìn)行雷達(dá)信號(hào)處理,實(shí)時(shí)性強(qiáng),靈活快捷,處理能力強(qiáng),易于模塊化設(shè)計(jì),開(kāi)發(fā)周期短,支持在線編程,并具有很強(qiáng)的通用性和可擴(kuò)展性。但是,FPGA技術(shù)仍有一些不足之處有待解決。例如,利用FPGA來(lái)實(shí)現(xiàn)復(fù)雜的公式運(yùn)算就是一件非常復(fù)雜或者是不可能實(shí)現(xiàn)的任務(wù)。針對(duì)這些問(wèn)題,一系列的特定功能的算法及模塊應(yīng)運(yùn)而生。本文著重介紹其中利用CORDIC算法來(lái)實(shí)現(xiàn)復(fù)數(shù)求模功能的模塊和利用查找表方式實(shí)現(xiàn)求對(duì)數(shù)的模塊[1],并針對(duì)現(xiàn)有的查找表占用資源太大的方式提出了改進(jìn)措施。

1基于CORDIC算法的復(fù)數(shù)求模

在雷達(dá)信號(hào)處理系統(tǒng)中,求模取對(duì)數(shù)運(yùn)算是必不可少的環(huán)節(jié)。在一些處理速度要求不高的系統(tǒng)中,求模運(yùn)算通常由DSP芯片或者軟件實(shí)現(xiàn),但對(duì)于速度要求很高的場(chǎng)合則只能利用FPGA來(lái)實(shí)現(xiàn)求模去對(duì)數(shù)運(yùn)算。在新推出的FPGA芯片中,目前均已包含了CORDIC運(yùn)算的核[2]。以Xilinx芯片為例,其推出的CORDIC運(yùn)算核能夠?qū)崿F(xiàn)復(fù)數(shù)的旋轉(zhuǎn)、求模等功能,能夠直接實(shí)現(xiàn)復(fù)數(shù)的求模操作。該種方式速度快,程序簡(jiǎn)單,但需要消耗一定數(shù)量的乘法器資源。

CORDIC是由Volder在1959 年提出的。這種算法可以應(yīng)用在圓周坐標(biāo)、線性坐標(biāo)和雙曲線坐標(biāo)中。利用CORDIC算法可以通過(guò)移位和加減運(yùn)算,能夠遞歸計(jì)算出常用函數(shù)值,如sin、cos等函數(shù)。Walther J在1974年利用它研究出了一種能夠計(jì)算出多種超越函數(shù)的統(tǒng)一算法。如今Xilinx FPGA推出了CORDIC IP核。利用該IP核可以方便快捷地實(shí)現(xiàn)復(fù)數(shù)的求模操作,按照其既定的輸入輸出格式即可實(shí)現(xiàn)以往在FPGA中較難實(shí)現(xiàn)的開(kāi)根號(hào)的操作[3]。

圖1給出了Xilinx的CORDIC IP核的調(diào)用(a)及參數(shù)設(shè)置(b)過(guò)程,所采用的軟件版本為vivado_2014.4。

圖1　VIVADO軟件CORDIC模塊IP核設(shè)置界面

樣例設(shè)計(jì)中使用的復(fù)數(shù)數(shù)據(jù)的輸入位寬分別為16位。由于該模塊在使用過(guò)程中的最高位必須為符號(hào)位擴(kuò)展,故而將IP核定制為17位,額外增加一位符號(hào)位,輸出的位寬同時(shí)也定制為17位,同樣最高位為符號(hào)位。輸入輸出格式要求如圖1(b)所示。圖2給出了實(shí)際使用過(guò)程中的IP的輸入輸出的模塊圖。

圖2　VIVADO軟件CORDIC模塊IP核輸入輸出示意圖

該IP利用了坐標(biāo)旋轉(zhuǎn)的方式,將輸入的復(fù)信號(hào)經(jīng)過(guò)旋轉(zhuǎn)與實(shí)數(shù)坐標(biāo)軸重合,獲得了此時(shí)的模值以及旋轉(zhuǎn)角度,從而完成了復(fù)數(shù)求模的過(guò)程。

2基于定長(zhǎng)查找表方式的常精度取對(duì)數(shù)模塊設(shè)計(jì)

在雷達(dá)信號(hào)處理中,通常將數(shù)據(jù)進(jìn)行取對(duì)數(shù)操作。在FPGA中實(shí)現(xiàn)取對(duì)數(shù)操作通常采用的是查找表的方式,即實(shí)現(xiàn)將一定范圍內(nèi)的數(shù)據(jù)的對(duì)數(shù)值以查找表的方式存入到FPGA內(nèi)的存儲(chǔ)區(qū)域內(nèi)部,然后以數(shù)據(jù)為地址索引,取出對(duì)應(yīng)的對(duì)數(shù)值。該種方式能夠快速實(shí)現(xiàn)取對(duì)數(shù)的運(yùn)算,避免了復(fù)雜的運(yùn)算,也避免了在FPGA內(nèi)進(jìn)行取對(duì)數(shù)操作。但是,該方式的不足在于隨著輸入數(shù)據(jù)的位寬增加,其對(duì)應(yīng)的查找表的長(zhǎng)度呈指數(shù)方式增加,如12位的數(shù)據(jù)對(duì)應(yīng)的查找表長(zhǎng)度為4096,這個(gè)一般可以接受,但20位數(shù)據(jù)對(duì)應(yīng)的長(zhǎng)度迅速增加為1 MB。一般的FPGA都很難提供如此大的存儲(chǔ)區(qū)間,并且由于取對(duì)數(shù)運(yùn)算的特殊性,不能通過(guò)簡(jiǎn)單的去除低位的方式來(lái)縮減存儲(chǔ)區(qū)間,因?yàn)楫?dāng)輸入數(shù)據(jù)較小時(shí)其對(duì)數(shù)的輸出結(jié)果卻不可被忽略。為了在沒(méi)有消耗過(guò)多存儲(chǔ)資源的前提下在FPGA中實(shí)現(xiàn)取對(duì)數(shù)的操作,并且滿足特定的精度,需要對(duì)現(xiàn)有的查找表方法進(jìn)行改進(jìn)。

本文提出了一種自適應(yīng)的查找表法來(lái)實(shí)現(xiàn)在FPGA中取對(duì)數(shù)運(yùn)算。在FPGA中例化了一個(gè)深度為4096的RAM,即地址位寬為12位,數(shù)據(jù)位寬也為12位。然后,將1～4 096的對(duì)數(shù)值經(jīng)過(guò)量化后存入到RAM中。FPGA內(nèi)部是無(wú)法表示小數(shù)的,所以必須對(duì)輸出的對(duì)數(shù)結(jié)果進(jìn)行量化。式(1)給出了量化過(guò)程。圖3給出了處理之后RAM內(nèi)儲(chǔ)存的數(shù)據(jù)與地址的對(duì)應(yīng)關(guān)系。

RAM_OUT = 4096*log10(Addr)/log10(4096)

(1)

圖3　RAM內(nèi)存儲(chǔ)數(shù)據(jù)

當(dāng)輸入數(shù)據(jù)的位寬小于等于12位時(shí),可以直接使用該查找表進(jìn)行取對(duì)數(shù)操作。將需要取對(duì)數(shù)的數(shù)據(jù)連接到RAM的地址線Addr上,然后將RAM的輸出的數(shù)據(jù)作為取對(duì)數(shù)結(jié)果進(jìn)行使用。

當(dāng)輸入數(shù)據(jù)的位寬大于12位的時(shí)候,比如說(shuō)輸入數(shù)據(jù)位寬為20時(shí),如果按照之前的方式創(chuàng)建RAM,則RAM的大小必須為1 MB。該存儲(chǔ)深度FPGA一般無(wú)法承受,即使能夠承受也是資源的巨大浪費(fèi)。所以,如果不作特殊處理,查找表法無(wú)法滿足FPGA中對(duì)于20位寬數(shù)據(jù)取對(duì)數(shù)的要求。

針對(duì)如上情況,本文提出了自適應(yīng)查表方式。首先對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理,然后再使用固定長(zhǎng)度的RAM進(jìn)行查表操作,并且不是簡(jiǎn)單地對(duì)輸入數(shù)據(jù)進(jìn)行截位操作,同時(shí)能夠保證結(jié)果達(dá)到固定的精度。假定輸入數(shù)據(jù)的位寬為20位,步驟如下:

(1) 判斷輸入數(shù)據(jù)的最高位是否為1,如是1則取此后的12位,舍去低位,進(jìn)行查表操作,得出結(jié)果之后進(jìn)行補(bǔ)償。

(2) 在最高位也為0情況下,判斷次高位是否為1,如是則取此后的12位進(jìn)行查表,然后進(jìn)行補(bǔ)償操作。

(3) 在次高位也為0情況下,判斷第3高位是否為1,如是則取此后的12位進(jìn)行查表,然后進(jìn)行補(bǔ)償操作。

依次類(lèi)推,直到只剩下12位的情況下則可直接進(jìn)行查表,然后得出結(jié)果,此時(shí)補(bǔ)償操作所增加的值為0。

圖4　自適應(yīng)查表法流程圖

圖4中,當(dāng)Data[20]=1時(shí),即數(shù)據(jù)位的最高為1,就截取其最高的12位進(jìn)行取對(duì)數(shù)操作,即第20位到第9位,然后查出結(jié)果后再進(jìn)行補(bǔ)償操作。所謂的補(bǔ)償操作的原理如式(2)所示。

Log10(2n*Data) =n*Log102+Log10(Data)

(2)

其實(shí),其原理就是對(duì)數(shù)的基本性質(zhì)之一。在圖4中所示的幾位補(bǔ)償操作,其實(shí)就是根據(jù)式(2)中的n來(lái)對(duì)數(shù)據(jù)進(jìn)行補(bǔ)償,每相差一位則在輸出結(jié)果上增加一個(gè)Log102,這樣就保證了數(shù)據(jù)運(yùn)算的正確性。

下面來(lái)計(jì)算一下截位所產(chǎn)生的誤差。當(dāng)Data[20]=1時(shí),低8位數(shù)據(jù)被舍棄,其被舍去的數(shù)據(jù)大小最大為255,假設(shè)其為28,而Data[20..8]的最小值為二進(jìn)制下的20’b10000000000000000000,此時(shí)的誤差相對(duì)最大,轉(zhuǎn)換為十進(jìn)制則為219。按式(3)進(jìn)行誤差運(yùn)算可得其誤差:

=[Log10(219+28)-Log10(219)]/Log10(219)

=Log10(219+28)/Log10(219)-1=3.7*10-5

(3)

設(shè)輸入數(shù)據(jù)有效位寬為A,查找表位寬為B,根據(jù)式(3)可得誤差計(jì)算公式為

=log10(2(A-1)+2(A-B))/log10(2(A-1))-1

(4)

以輸入數(shù)據(jù)位寬A=20為例,查找表采用不同存儲(chǔ)深度情況下的誤差如表1所示。

表1　不同存儲(chǔ)深度下的誤差

以查找表位寬B=12為例,對(duì)應(yīng)不同輸入數(shù)據(jù)位寬情況下的誤差如表2所示。

表2　不同數(shù)據(jù)位寬下的誤差

如表1、2中所示,采用10位存儲(chǔ)寬度即1 024位深度的查找表即可實(shí)現(xiàn)精度10-4的取對(duì)數(shù)精度。當(dāng)查找表位寬為12時(shí),即采用4 096深度的情況下,輸入位寬為16到22位時(shí)可實(shí)現(xiàn)精度10-5的取對(duì)數(shù)精度,且誤差受數(shù)據(jù)位寬影響較小,主要的影響因素是查找表的存儲(chǔ)深度。該方法簡(jiǎn)單可靠,精度高,極易于在FPGA中實(shí)現(xiàn)。

3結(jié)束語(yǔ)

本文中介紹的基于Xilinx軟件提供的CORDIC核所進(jìn)行的求模運(yùn)算,速度快,精度高,實(shí)現(xiàn)簡(jiǎn)單。本文的自適應(yīng)查找表法求對(duì)數(shù)值解決了在FPGA中實(shí)現(xiàn)取對(duì)數(shù)的問(wèn)題,且所需資源小,速度快,精度高。將求模取對(duì)數(shù)模塊合并入一個(gè)模塊中,即可實(shí)現(xiàn)雷達(dá)信號(hào)處理過(guò)程中的復(fù)數(shù)信號(hào)到其能量域的轉(zhuǎn)換過(guò)程,方便快捷,性能好。

參考文獻(xiàn):

[1]牟勝梅,楊曉東．一種改進(jìn)的基于FPGA 的32 位對(duì)數(shù)變換器的設(shè)計(jì)與實(shí)現(xiàn)[J]．計(jì)算機(jī)研究與發(fā)展,2007,44(7):1252-1258．

[2]祁艷杰,劉章發(fā)．基于Parallel_Cordic的高精度高速度直接數(shù)字頻率合成器的FPGA 實(shí)現(xiàn)[J]．電子學(xué)報(bào),2014,42(7)．

[3]邱軍海,關(guān)鍵,等．常用雷達(dá)視頻信號(hào)處理算法在FPGA 上的實(shí)現(xiàn)[J]．海軍航空工程學(xué)院學(xué)報(bào),2006,21(6)．

Design of high-precision modulo operation and logarithm module in FPGA based on adaptive lookup table method

XU Xiu-feng

(No.38 Research Institute of CETC, Hefei 230088)

Abstract:It goes without saying that the FPGA, as the general processor, has a variety of advantages. However, it also has some deficiencies such as mod operation and logarithm algorithm of the complex number. A high-precision mod operation is introduced based on the CORDIC algorithm, and then the high-precision logarithmic algorithm is realized through the adaptive lookup table (LUT) method, both of which can be easily implemented with fast operating speed.

Key words:FPGA; CORDIC; modulo value; logarithm; adaptive LUT method

收稿日期:2016-01-20;修回日期:2016-02-23

作者簡(jiǎn)介:徐修峰(1986-),男,工程師,博士,研究方向:雷達(dá)數(shù)字信號(hào)處理。

中圖分類(lèi)號(hào):TN911.7

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1009-0401(2016)02-0035-03