一種數(shù)字復(fù)除法器的實現(xiàn)方法

一種數(shù)字復(fù)除法器的實現(xiàn)方法

1數(shù)字個數(shù)除法器除了法器是數(shù)字數(shù)據(jù)處理領(lǐng)域的基本單元外，它也是四種計算操作中最復(fù)雜的操作單元。它的性能直接關(guān)系到整個電路的性能。軟件可以通過直接調(diào)用除法運算符來實現(xiàn)除法操作,不用關(guān)心具體的實現(xiàn)細節(jié)。然而對于FPGA而言,它不像加法、減法或者乘法,可以直接通過調(diào)用相應(yīng)的運算符來實現(xiàn),而是需要調(diào)用IPCore或者自己編程來實現(xiàn),所以如何設(shè)計出高效實用的硬件電路是實現(xiàn)除法器的關(guān)鍵,如何提高除法器的實時性和降低硬件資源已成為除法器算法的研究熱點。常見的除法器有以下幾種:1)對除數(shù)進行直接等效轉(zhuǎn)換的除法器。此除法器對除數(shù)進行等效,采用乘法和移位操作來實現(xiàn),是所有除法器中最基本、最簡單的除法器。比如除2操作可以通過被除數(shù)右移一位來實現(xiàn);除7操作可以通過被除數(shù)乘上73然后除以512(右移8位)來實現(xiàn)。這種除法器雖然實現(xiàn)簡單,但是只適合除數(shù)固定的場景,應(yīng)用面太窄,適用性不強。2)基于線性收斂算法的除法器。此除法器首先需要把被除數(shù)加載到余數(shù)寄存器中,如果余數(shù)大于除數(shù),就用余數(shù)減去除數(shù),將減法結(jié)果存儲到余數(shù)寄存器中,并且將商加1,否則商保持原值不變,這樣通過執(zhí)行循環(huán)減法操作可以得到商和余數(shù)。由于此算法需要執(zhí)行多次迭代,因此在除數(shù)相對被除數(shù)很小的情況下處理延遲大,實時性不強。雖然現(xiàn)在有很多基于線性收斂算法改良的除法器,但是由于都存在迭代過程,最終導(dǎo)致實時性很差,不能適應(yīng)高吞吐率的應(yīng)用場景。3)采用CORDIC算法的除法器。本除法器通過一系列固定的、與運算基數(shù)相關(guān)的角度的不斷偏擺以逼近所需的旋轉(zhuǎn)角度,雖然實現(xiàn)方法簡單,但是計算過程同樣存在多次迭代。如果迭代過程采用資源復(fù)用,則可以減少硬件資源,但是實時性不強;如果迭代過程不采用資源復(fù)用,則實時性較強,但是硬件資源會隨迭代次數(shù)線性增長。4)陣列除法器。此除法器采用可控的加減法單元所組成的流水陣列來實現(xiàn)。一般情況下,一個N比特(被除數(shù)和除數(shù)都是N比特)的陣列除法器需要N2個加減法單元。此算法雖然提高了運算速度,但是除法器位寬較大,造成硬件資源消耗過多。上述幾種除法器算法,要么處理實時性不強,要么硬件資源消耗多。針對這些問題,本文基于線性逼近算法與32段查找表相結(jié)合的方式,提出一種數(shù)字復(fù)數(shù)除法器的實現(xiàn)方法。本算法不但消耗資源少,計算速度快,滿足高吞吐率的場景,而且還可以根據(jù)修改ROM的數(shù)值精度來滿足不同的性能要求,靈活性很高。2個數(shù)除法運算假設(shè)復(fù)數(shù)除法器的分子輸入為x=a+b·j,分母輸入為y=c+d·j,則有:xy=a+b?jc+d?j=(a+b?j)(c-d?j)(c+d?j)(c-d?j)=1c2+d2?(a+b?j)?(c-d?j)(1)xy=a+b?jc+d?j=(a+b?j)(c?d?j)(c+d?j)(c?d?j)=1c2+d2?(a+b?j)?(c?d?j)(1)從式(1)可以看出,復(fù)數(shù)除法運算可以轉(zhuǎn)換成復(fù)數(shù)乘法運算和實數(shù)求倒運算來,如圖1所示。下面針對復(fù)數(shù)乘法和求倒電路的原理和硬件實現(xiàn)分別給以闡述。2.1兩個計數(shù)加法器的硬件實現(xiàn)結(jié)構(gòu)設(shè)計對于復(fù)數(shù)乘法(a+b·j)(c-d·j)=(ac+bd)+(bc-ad)·j,如果采用直接實現(xiàn)的方式,則硬件實現(xiàn)結(jié)構(gòu)如圖2所示。從圖2可以看出,求ac、bd、dc和ad的乘積需要四個實數(shù)乘法器;求ac+bd和bc+ad需要兩個實數(shù)加法器(減法器算作加法器),因此此電路需要四個實數(shù)乘法器和兩個實數(shù)加法器。如果在實現(xiàn)之前,先按照式(2)進行變換,即:(a+b·j)(c-d·j)=(ac+bd)+(bc-ad)·j=[(a-b)·c+(c+d)·b]+[(c-d)·a-(a-b)·c]·j(2)式(2)的硬件實現(xiàn)結(jié)構(gòu)圖如圖3所示。從圖3可以看出,此時實現(xiàn)一個復(fù)數(shù)乘法器只需要三個實數(shù)乘法器和五個實數(shù)加法器。由于一個乘法器的資源遠遠大于一個加法器的資源,而對硬件設(shè)計來說硬件資源的使用都是很寶貴的,因此用一個乘法器換三個加法器還是很值得,所以按照式(2)來實現(xiàn)復(fù)數(shù)乘法器可以節(jié)省硬件資源,減少開發(fā)成本。2.2求倒電路的線性被測方法求倒電路是復(fù)數(shù)除法器的核心模塊,電路的設(shè)計直接決定復(fù)數(shù)除法器的性能,可以通過采用線性逼近算法結(jié)合32段線性查找表的方式來實現(xiàn)1/z的計算。首先在ROM表存儲存1/32～1/64的定點化后的數(shù)值。由于硬件定點化的緣故,ROM表中并不是直接存儲1/32～1/64的小數(shù)數(shù)值,而是存儲擴大了2n倍后的數(shù)值的整數(shù)部分,其中n值越大,復(fù)數(shù)除法器的誤差越小,性能越高,因此通過簡單改變n值的大小,就可以滿足不同系統(tǒng)對性能的要求。在本文的設(shè)計中,n取值為20,ROM表中每個地址的存儲內(nèi)容如表1所示,其中地址i里存儲的數(shù)據(jù)為132+i?220132+i?220四舍五入后的整數(shù)部分。由于ROM表中存儲了1/32～1/64的定點化后的數(shù)值,當(dāng)32≤z≤64時,通過查找ROM表直接得到1/z的數(shù)值;但是當(dāng)z<32或者z>64時,就需要通過線性逼近算法計算得到1/z的數(shù)值,具體算法原理如下所述:1)確定z的最高非0bit位m,即m=log2n,其中為向下取整。2)對z進行左移或者右移操作得到z′,即z′=z2m-5z2m?5,其中32≤z′≤64。3)把z′值當(dāng)作地址查找ROM表,得到1z′和1z′+1。4)計算1z′和1z′+1的差值,得到Δz′=1z′-1z′+1。5)計算步驟2)中移位操作帶來的尾數(shù)誤差N,得到N=z-z′·2m-5。6)將差值Δz′進行2m-5等分,根據(jù)步驟5)計算得到的N值得到線性逼近誤差Δz=Δz′2m-5?Ν。7)由于步驟2)的移位操作對除數(shù)縮小或擴大了2m-5倍,導(dǎo)致求得的倒數(shù)也隨之?dāng)U大或縮小2m-5倍,因此最終的結(jié)果應(yīng)縮小或擴大2m-5倍;又由于ROM中存儲的數(shù)據(jù)擴大了220倍,所以最終結(jié)果要縮小220倍,因此我們采用線性逼近算法,最終可以得到1z=(1z′-Δz)?12m-5。求倒電路硬件實現(xiàn)結(jié)構(gòu)圖如圖4所示。例如z=(40)10時,由于此時32≤z≤64,通過查找ROM表中地址為8的存儲單元,就可以直接得到1/z為26214/220。當(dāng)z=(81)10=(1010001)2時,首先可以得到z的最高非零bit位m為6;其次對z右移一位得到z′=(40)10=(0101000)2;接著可以得到N=1;然后通過查找表得到140和141,并求得(140-141);最終可以得到1z≈[140-(140-141)?12]?12=180-(180-182)?12。如圖5所示,其中e為實際的1/z和采用線性逼近計算的結(jié)果之間的絕對誤差。2.3量化誤差的特征值對于上述算法采用MatLab進行仿真,可以得到計算絕對誤差e的曲線圖。當(dāng)32≤z≤64時,絕對誤差為量化誤差,數(shù)量級為2-16。當(dāng)1≤z≤31時,絕對誤差e的曲線如圖6所示,數(shù)量級在10-6。當(dāng)65≤z時,絕對誤差e的曲線如圖7所示,數(shù)量級在10-6。通過上述分析我們可以得到采用本算法進行除法運算,絕對誤差e最大約為5.1*10-6,相對誤差最大約為1.7*10-6,即不到萬分之二,計算精度很高。3硬件實現(xiàn)的性能根據(jù)現(xiàn)有除法器的實現(xiàn)中存在的缺點,本文采用線性逼近算法和查找表相結(jié)合的方式,實現(xiàn)了復(fù)數(shù)除法器的功能。相對于其它算法,本除法器有以下幾點優(yōu)勢:1)文中的硬件實現(xiàn)沒有任何迭代過程,完全采用流水線處理,具有很高的吞吐率,可以適應(yīng)任何輸入速率,完全滿足數(shù)字通信領(lǐng)域?qū)崟r