摘要：乘法是數(shù)字信號處理中重要的基本運算，在很大程度上影響著系統(tǒng)的性能。本文將介紹三種高速乘法器實現(xiàn)原理：陣列乘法器、華萊士（WT）乘法器、布斯華萊士樹超前進位乘法器。而且通過FPGA技術(shù)實現(xiàn)了這三種乘法器，并對基于以上三種架構(gòu)的乘法器性能進行了分析比較。

關(guān)鍵字：陣列乘法器，華萊士乘法器，超前進位乘法器，F(xiàn)PGA

引言

隨著3G技術(shù)的發(fā)展，關(guān)于圖像、語音、加密等數(shù)字信號處理技術(shù)隨處可見，而且信號處理的實時性也要求越高。實時性即是要求對信號處理的速度要快，而乘法器是數(shù)字信號處理中重要的基本運算，在很大程度上影響著系統(tǒng)的性能。人們開始開發(fā)高速的乘法器。

以下將對三種乘法器：陣列乘法器、華萊士（WT）乘法器、布斯華萊士樹超前進位乘法器進行原理分析，并用FPGA技術(shù)實現(xiàn)了這三種乘法器，對其結(jié)果進行了仿真，得出相應(yīng)的性能比較。

陣列乘法器

2.1 陣列乘法器原理

硬件乘法器的常規(guī)設(shè)計是適用“串行移位”和“并行加法”相結(jié)合的方法，這種方法并不需要很多器件。然而串行方法畢竟太慢，執(zhí)行一次乘法的時間至少是執(zhí)行一次加法時間的n倍，不能滿足科學(xué)技術(shù)對高速乘法所提出的要求。自從大規(guī)模集成電路問世以來，高速的單元陣列乘法器應(yīng)運而生，出現(xiàn)了各種形式的流水線陣列乘法器，它們屬于并行乘法器，提供了極快的速度。陣列乘法器的運算過程如下：

第一：當(dāng)乘數(shù)的位數(shù)字為1 時，我們可以將被乘數(shù)的值直接放置適當(dāng)?shù)奈恢谩６m當(dāng)?shù)奈恢檬且莱藬?shù)的第幾個位和被乘數(shù)做運算之后所放的位置。

第二：當(dāng)乘數(shù)的位數(shù)字為0 時，我們可以將0 放置適當(dāng)?shù)奈恢茫?以作為部分乘積。

第三：我們利用筆和紙計算的乘法，在硬件中使用與門來實現(xiàn)。例如：1000 ×1中，乘數(shù)1 和每一個被乘數(shù)的位都個別做與運算，其結(jié)果為1000 正是我們所要的結(jié)果。由此可知我們只需用與門就可以完成我們所要的乘法。

第四：當(dāng)部分乘積都運算完成后，使用加法來完成最終的乘法結(jié)果運算。

根據(jù)以上四點的說明，我們可以運用最簡單、最直觀的方式來描述固定點乘法器的電路描述。我們使用與門來做部分積運算，使用全加器（Full adder）來運算部分積的最終結(jié)果。圖1所示為有符號位的6×6固定點乘法器的架構(gòu)圖。

圖1 6×6有符號位陣列乘法器乘法器架構(gòu)圖

2.2 陣列乘法器FPGA仿真

在名為comult的實體中設(shè)置mulc和mulp兩個輸入端口和一個prod輸出端口。其中mulc代表被乘數(shù)，mulp為乘數(shù)，二者均為6位。乘積prod是一個12位的結(jié)果，輸入與輸出端口的數(shù)據(jù)類型均為std_logic_vector。流程圖如圖2所示，仿真如圖3所示。

圖2 6x6有符號陣列乘法器流程圖

圖3 6x6有符號陣列乘法器仿真

華萊士乘法器原理

部分積相加， 若采用累加移位的方法， 速度太慢。華萊士樹算法（Wallace Tree Algorithm）是部分積化簡的一種樹形算法。它使乘法器的延時得到最大限度的縮短，但全加陣列的布局布線復(fù)雜度大為增加。

一個全加器有三個輸入： A ， B ， C （進位） 和兩個輸出S ， C′（輸出進位） ， 3個輸入對2個輸出而言是對稱的， 即它們互相交換位置， 結(jié)果不會受影響。如果把一串全加器簡單排成一行， 它們之間進位線不連， 把這樣一串全加器稱為保留進位加法器（CSA ） ， 它有以下特性： 三個輸入數(shù)之和等于二個輸出數(shù)之和， 即3個相加數(shù)每通過一次保留進位加法器， 其個數(shù)就減少1個。

Wallace最早提出的方案就利用了這一特點：第一步將每列的部分積按三位進行分組，每組通過使用全加器構(gòu)成的CSA部件，將加數(shù)的數(shù)目減少;第二步對第一步產(chǎn)生的結(jié)果仍按三位分組的方式將同權(quán)的偽和與局部進位信號通過CSA 部件進行處理，再次減少加數(shù)的數(shù)目，這種處理一直進行到最后只有兩個輸出為止。對最后的偽和與局部進位通過進位傳遞加法器相加得出真正的結(jié)果。在這種處理方式中，每列中求偽和的操作是并行完成的。由于采用全加器作為加法部件，每次能將3個權(quán)為20的輸入信號經(jīng)處理后得到一個權(quán)為21的局部進位信號和一個權(quán)為20的偽和信號，這樣操作數(shù)的數(shù)目減少1/ 3，將產(chǎn)生的中間偽和也按照這種方式處理，經(jīng)過時間為O（log3/ 2 N） 的處理后可以得到最后的偽和與局部進位信號。

圖16 華萊士樹加法樹示意圖

圖17 4x4位華萊士樹乘法器實現(xiàn)圖

圖18 4x4位華萊士樹乘法器架構(gòu)圖

圖19 保留進位加法器（CSA）

圖20 半加器

布斯算法（Booth’s Algorithm）的做法是對乘數(shù)編碼以計算出乘法運算的結(jié)果，主要的想法在于乘數(shù)中連續(xù)的1，這些1會造成被乘數(shù)的連加。

但是，乘數(shù)01110又可表示為10000-00010，這樣可將部分積減少為2個。當(dāng)我們遇到乘數(shù)中連續(xù)的’1’時（從右往左看），第一個’1’減去被乘數(shù)，最后一個’1’后面的’0’則加上被乘數(shù)。

布斯編碼的核心在于對連續(xù)的’1’字串進行頭、中、尾三段的分段處理（從右往左看）。當(dāng)然，’0’字串由于本身就無須進行運算，所以不必理會。

華萊士乘法器

先介紹陣列乘法器，我們用筆計算乘法時，第一個操作數(shù)為被乘數(shù)（multiplicand），第二個操作數(shù)為乘數(shù)（multiplier）。而乘數(shù)中的每一個位和被乘數(shù)做相乘的運算后的結(jié)果稱之為部分乘積（partial product），而將所有的部分乘積相加之后，其運算結(jié)果稱為乘積（product）。如：1000×1001為例，

通過以上的示例我們可以發(fā)現(xiàn)如下四點：

第一：當(dāng)乘數(shù)的位數(shù)字為1 時，我們可以將被乘數(shù)的值直接放置適當(dāng)?shù)奈恢谩６m當(dāng)?shù)奈恢檬且莱藬?shù)的第幾個位和被乘數(shù)做運算之后所放的位置。

第二：當(dāng)乘數(shù)的位數(shù)字為0 時，我們可以將0 放置適當(dāng)?shù)奈恢茫?以作為部分乘積。

第三：我們利用筆和紙計算的乘法，在硬件中使用與門來實現(xiàn)。例如：1000 ×1中，乘數(shù)1 和每一個被乘數(shù)的位都個別做與運算，其結(jié)果為1000 正是我們所要的結(jié)果。由此可知我們只需用與門就可以完成我們所要的乘法。

第四：當(dāng)部分乘積都運算完成后，使用加法來完成最終的乘法結(jié)果運算。

根據(jù)以上四點的說明，我們可以運用最簡單、最直觀的方式來描述固定點乘法器的電路描述。我們使用與門來做部分積運算，使用全加器（Full adder）來運算部分積的最終結(jié)果。因為作加法時，會有進位問題，且上一位所產(chǎn)生的進位也非常重要，所以只有全加器能滿足我們的加法要求。圖13所示為有符號位的6×6固定點乘法器的架構(gòu)圖。

圖13 6×6固定點乘法器架構(gòu)圖

原文標題：三種高速乘法器的FPGA實現(xiàn)及性能比較

文章出處：【微信公眾號：FPGA設(shè)計論壇】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。