基于FPGA的快速并行平方器

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

?

1 引言

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

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

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

?

?

　

?

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

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

?

?

?

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

?

?

?

4 性能分析與比較

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

?

參考文獻

?

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

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

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