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

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

引言

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

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

陣列乘法器

2.1 陣列乘法器原理

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

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

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

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

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

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

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

2.2 陣列乘法器FPGA仿真

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

圖2 6x6有符號(hào)陣列乘法器流程圖

圖3 6x6有符號(hào)陣列乘法器仿真

華萊士乘法器原理

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

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

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

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

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

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

圖19 保留進(jìn)位加法器（CSA）

圖20 半加器

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

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

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

華萊士乘法器

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

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

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

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

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

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

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

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

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

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