基于FPGA的快速并行平方器

關(guān)鍵詞：FPGA，二進(jìn)制補(bǔ)碼，平方器

?

1 引言

平方器在科學(xué)技術(shù)的許多領(lǐng)域被廣泛應(yīng)用，例如圖像壓縮及通信技術(shù)。在實(shí)際FPGA設(shè)計(jì)中，比較常用的方法是直接將乘法器用作平方器，即將相同數(shù)據(jù)直接送至兩輸入乘法器的輸入端，從而完成平方運(yùn)算。但用此方法實(shí)現(xiàn)平方器存在兩個(gè)主要缺點(diǎn)：一是速度慢；二是浪費(fèi)資源。如果使用查表法實(shí)現(xiàn)平方器，雖然能夠提高運(yùn)算速度，但當(dāng)輸入數(shù)據(jù)位數(shù)比較長(zhǎng)時(shí)，所用資源是非常巨大的。本文所介紹的設(shè)計(jì)方法可以有效克服速度與資源的矛盾，從而設(shè)計(jì)出既節(jié)省資源又快速的平方器。

2 平方器的實(shí)現(xiàn)原理

對(duì)于輸入為n位的二進(jìn)制補(bǔ)碼，無(wú)論其是正數(shù)還是負(fù)數(shù)，經(jīng)平方運(yùn)算后都為正數(shù)，所以平方器的輸出結(jié)果只需要2n-1位就可以表示了，默認(rèn)的符號(hào)位為零可以省略。假設(shè)輸入數(shù)據(jù)為長(zhǎng)度為6位的二進(jìn)制補(bǔ)碼，則平方器輸出為11位。根據(jù)參考文獻(xiàn)[1]，可推得平方運(yùn)算的具體過(guò)程如圖1（a）所示。圖中數(shù)字符號(hào)即代表輸入數(shù)據(jù)的對(duì)應(yīng)位，橫杠表示取反，“1”表示二進(jìn)制數(shù)1。圖1（a）的原理對(duì)于二進(jìn)制補(bǔ)碼的正、負(fù)數(shù)均適用。從圖中可以看出，由于乘數(shù)與被乘數(shù)相同，乘積項(xiàng)是沿對(duì)角線對(duì)稱分布的。這樣，根據(jù)二進(jìn)制加法的特點(diǎn)，可以將對(duì)角線以上的乘積項(xiàng)左移一位，從而將對(duì)角線以下的乘積項(xiàng)消去，如圖1（b）所示。觀察圖1（b）可發(fā)現(xiàn)，由于輸出平方值的P0等于輸入X0與自身相與，所以就等于X0，而P1則總等于零。運(yùn)用上述觀察到的特點(diǎn)，可以大大簡(jiǎn)化電路設(shè)計(jì)并提高運(yùn)算速度。下面的設(shè)計(jì)就是依據(jù)圖1（b）進(jìn)行的。

?

?

　

?

3 平方器的FPGA實(shí)現(xiàn)

由圖1（b）可以看出，用FPGA實(shí)現(xiàn)平方運(yùn)算，可以分兩步：第一步，產(chǎn)生乘積項(xiàng)；第二步，用串行進(jìn)位加法器將乘積項(xiàng)逐行相加，最后得出結(jié)果。這樣做雖然思路簡(jiǎn)單清晰，但有一個(gè)缺點(diǎn)，就是在使用串行進(jìn)位加法器時(shí)，因?yàn)榧臃ㄆ鞔嬖谶M(jìn)位傳送延遲，使得在對(duì)每一行乘積項(xiàng)相加時(shí)都存在進(jìn)位延遲，從而降低了運(yùn)算速度。為減少進(jìn)位延遲的影響，可以分三步來(lái)實(shí)現(xiàn)平方運(yùn)算：第一步，產(chǎn)生乘積項(xiàng)；第二步，運(yùn)用全加器及半加器將第一列的乘積項(xiàng)壓縮為只有兩項(xiàng)，原理如圖2所示。其中，A、B是加法器的兩個(gè)加數(shù)輸入端，Ci是進(jìn)位輸入端，Co、Su分別是進(jìn)位輸出端與本位和輸出端，并假設(shè)該列有5個(gè)乘積項(xiàng)（加上前一列的進(jìn)位項(xiàng)），分別用a、b、c、d、e來(lái)表示。這樣，只需一個(gè)全加器和一個(gè)半加器就可將乘積項(xiàng)壓縮為兩項(xiàng)，同時(shí)產(chǎn)生兩個(gè)進(jìn)位項(xiàng)。用此方法對(duì)每一列進(jìn)行壓縮，這樣經(jīng)壓縮后的乘積項(xiàng)就只有兩行；第三步，將第二步產(chǎn)生的兩行乘積項(xiàng)送至進(jìn)位傳送加法器相加，得到平方值?？梢钥闯?，用第二種方法實(shí)現(xiàn)平方器，在對(duì)乘積項(xiàng)進(jìn)行壓縮時(shí)不存在進(jìn)位傳送延遲，而只在第三步存在加法器的進(jìn)位延遲，因此可以大大提高運(yùn)算速度。下面就舉一個(gè)6位平方器的便子來(lái)說(shuō)明如何用第二種方法實(shí)現(xiàn)平方器。原理如圖3所示（圖中，correct項(xiàng)對(duì)應(yīng)于二進(jìn)制數(shù)1，“0”表示二進(jìn)制數(shù)0）。第一步，產(chǎn)生乘積項(xiàng)。因?yàn)槊總€(gè)乘積項(xiàng)是由輸入數(shù)據(jù)的對(duì)應(yīng)比特相與產(chǎn)生的，所以，對(duì)于產(chǎn)生電路用語(yǔ)言描述比用圖形描述更為方便，此處使用VHDL語(yǔ)言來(lái)描述乘積項(xiàng)產(chǎn)生電路；第二步，通過(guò)全加器及半加器組成的網(wǎng)絡(luò)，將乘積項(xiàng)壓縮為兩行。從圖1（b）可以看出，按列進(jìn)行乘積項(xiàng)壓縮，由于每一列的乘積項(xiàng)缺乏規(guī)律性，不便于用語(yǔ)言來(lái)描述，所以此處使用圖形輸入法來(lái)描述乘積項(xiàng)壓縮電路，圖3中虛線框內(nèi)的部分就是乘積項(xiàng)壓縮電路；第三步，將壓縮得到的兩行乘積項(xiàng)送至串行進(jìn)位加法器相加，得到平方值。圖3中虛線框以外的部分就是最后的串行進(jìn)位加法器。

?

?

?

圖4（a）是用MAX+PLUS II 10.0仿真得到的結(jié)果。通過(guò)觀察圖4（a）的仿真結(jié)果可以發(fā)現(xiàn)，由于組合電路的競(jìng)爭(zhēng)與冒險(xiǎn)，使得輸出結(jié)果有毛刺。這個(gè)問(wèn)題可以通過(guò)加流水線的方法來(lái)解決。圖4（b）是經(jīng)流水線處理后的輸出波形，毛刺被完全消除。

?

?

?

4 性能分析與比較

此處，我們使用的FPGA器件是Altera公司的EPM7064LC44-7，用于比較的乘法器是MAX+PLUS II的LPM庫(kù)中的乘法器LPM_MULT。對(duì)于本文的平方器，共使用了15個(gè)邏輯單元，占資源的23%；對(duì)于LPM_MULT，共使用了35個(gè)邏輯單元，占資源的54%。在資源的使用上節(jié)省了一半多。為比較兩種平方器的工作速度，我們使用了MAX+PLUS II中時(shí)序邏輯電路性能分析功能，即在輸入、輸出端口加上D觸發(fā)器，然后進(jìn)行定時(shí)分析。結(jié)果顯示，本文的平方器可以工作的最高頻率是76.92MHz，而LPM_MULT工作的最高頻率是35.71MHz。由此可見(jiàn)，無(wú)論是資源的使用還是工作速度，本文所介紹的平方器都具有很大的優(yōu)越性。

?

參考文獻(xiàn)

?

1 L.Dadda. Fast Multipliers for Tow’s-Complement Num-bers in Serial Form. IEEE Symp. Computer Arithmetic. Urbana,I11,June 1985

2 侯伯亨，顧新.VHDL硬件描述語(yǔ)言數(shù)字邏輯電路設(shè)計(jì).西安：西安電子科技大學(xué)出版社，1999，9

3 宋萬(wàn)杰，羅豐，吳順君.CPLD技術(shù)及其應(yīng)用.西安：西安電子科技大學(xué)出版社，1999，9