帶有飽和處理功能的并行乘加單元設計

本文介紹了一種48bit+24bit×24bit帶飽和處理的MAC單元設計。在乘法器的設計中，采用改進的booth 算法來減少部分積的數目，用由壓縮單元組成的Wallace tree將產生的部分積相加，并將被加數作為乘法器的一個部分積參與到Wallace tree陣列中來完成乘加運算，同時增加了飽和檢測和飽和值運算邏輯來實現飽和處理。
關鍵詞：booth算法； Wallace tree ；飽和處理；飽和檢測

圖1? 飽和MAC結構框圖

圖2? 優化后的飽和MAC結構框圖

引言
在一些數字信號處理應用，如數字濾波、語音編碼、圖形處理等領域中，要大量反復地進行飽和處理操作。所謂飽和處理操作，是指當兩個n位操作數相運算時，如果結果發生溢出，則取其飽和值。對于用補碼表示的n位二進制數，正的飽和值為011…11，負的飽和值為100…00。飽和處理操作一般要用到兩個周期，在第一個周期中處理算術運算操作，在第二個周期中處理飽和操作。更加復雜的操作，例如MAC操作，一般是在分別完成乘法和加法運算之后再進行飽和處理，這通常需要更多的周期。而并行飽和運算操作則是在一個周期之內取得串行操作的結果，這需要更多的硬件電路來實現。
本文設計了一種MAC單元，實現

=>的運算操作，并帶有飽和處理功能。

圖3? 24×24高速乘加器的結構框圖

圖4 并行乘加器中最大的Wallace tree 結構

圖5 最終加法器的實現

飽和乘加單元基本結構
為了實現

=>的飽和運算，在一般情況下，計算P時，可以將X 、Y經乘法器相乘，然后將積與A相加，如果發生溢出，則將所得的和修正為飽和值。這實際上就是將乘法器與加法器簡單串聯，然后進行飽和值修正，如圖1所示。但是以這種結構實現的MAC單元，由于乘法器中的最終加法器和加法器只是簡單的串聯在一起，在關鍵路徑上就有兩級串聯的加法器，面積、延時都比較大。
為了提高MAC單元的性能，本文對上面提到的結構進行了優化， 優化后的結構如圖2所示。 將MAC單元的被加數作為乘法器的一個部分積，參與到部分積加法陣列中，這樣就可以省去完成乘法計算后再進行加法計算的操作，縮短關鍵路徑上的延時。

高速并行乘加單元結構
本文選用修正booth算法和Wallace tree結構實現24×24高速并行乘法器。圖3是24×24高速乘加器的結構框圖，主要由booth編碼、部分積陣列、Wallace tree以及最終加法器構成。
booth編碼
被乘數、乘數分別為n位補碼表示的有符號數，在MBA(修正booth算法)中：
部分積的數目＝，不失一般性，在這里只討論n為偶數的情況。
設： X=-an-12n-1+2i；
?????? Y=-bn-12n-1+2i；
根據MBA，對乘數進行以下變換：
Y=-bn-12n-1+2i
?? =
在這里a-1=0；
令其中i=0,1,2,…(n/2-1)；則
；
；
由上式可以看到加法計算量減少了一半，同時可以看出Ki+1X相對于KiX需要左移兩位。
在MBA中，乘數被劃分成2位的塊，對于第j個塊，塊中的2位(b2j+1,b2j)和前一個塊中的高位b2j-1重新進行編碼，編碼真值表為：
符號擴展及部分積產生
在部分積生成過程中，符號位的擴展隨部分積一起產生，我們將所有的擴展符號位相加：

由于和是48位的，故將上式中第一項舍掉，得：
；
對于部分積的產生，如果乘數經booth重編碼后Ki為負，則需將部分積取反后加1，如表1所示。因此，在設計中可將每一個部分積的最后一位與ni相加，booth編碼值為負時ni=1；編碼值為正時ni=0。
部分積及被加數相加
Wallace tree是通過提高電路的并行度來提高電路速度的一種實現結構，它將所有的部分積在同一時刻相互獨立地并行加到電路中，從而提高運算速度。在Wallace tree結構里面，我們用壓縮單元將乘法操作過程中產生的部分積以及被加數相加。在本設計中，我們把被加數作為一個部分積，加到Wallace tree陣列中，這樣就可以省去完成乘法運算后再進行加法運算的操作延遲，提高MAC單元速度。
最大的樹由3個3-2壓縮單元和4個4-2壓縮單元組成，樹的高度只有3級，這比只用全加器實現時的高度要小得多，延時也小得多。對于其他較小的樹，可以通過減少壓縮單元的數目來實現。圖4為本MAC單元中最大的Wallace tree 結構(其中a22為被加數的相應位)。
最終加法器
在Wallace tree陣列中，Wallace tree的每一列都產生一個初步的進位項和一個初步的加法結果，最后必須使用一個快速加法器將所有的進位項和加法結果加起來。為了獲得較高性能，一般采用先行進位加法器(CLA)，它可以同時產生所有的進位項，因而可以獲得極高的速度，在最壞情況下的延遲正比于n。但是隨著位數的增加，進位項變得越來越復雜，相應地消耗的面積越來越大，同時速度也無法得到保證。研究表明，CLA的最佳位數是4位，這時可以在速度與面積之間取得最優的折衷。在本設計中，加數共有48位，因此將它分成12塊，每塊4位，塊與塊之間通過塊間進位串聯，每一塊的進位只影響本塊中的位，不影響更高塊的位。圖5為最終加法器的實現。

飽和檢測和飽和值的產生
在本設計中，通過下式來檢測結果是否發生溢出：

其中(Xn-1)為XY的符號。在發生溢出的情況下，通過48位2選1的MUX將飽和修正值輸出。修正的飽和值可以由下面的公式計算：
V=
(a2n-1為被加數的符號位)

結語
考察整個MAC單元的實現，優化后的設計將被加數作為部分積的一部分加入到Wallace tree陣列中，從而在關鍵路徑上減少了一級串聯的先行進位加法器；采用特殊的飽和檢測邏輯，可以不用再等待和的產生，使得飽和檢測操作可以和乘加操作并行進行，將飽和檢測邏輯的延時排除在關鍵路徑延時之外。與優化以前的設計實現相比，MAC單元的速度有了很大提高。優化以后的設計實現，其面積和時延都集中消耗在部分積產生、Wallace tree陣列、最終加法器和2選1的MUX這四部分上。
表2是優化前后的面積和時延的比較，從表中可以看出不論是在速度還是在面積方面，優化后比優化前都有了很大的改進。

參考文獻
1 Michael J.Schulte, Pablo I. Balzola, Ahmet Akkas,and Robert W.Brocato. Inter Multiplication with Overflow Detection or Saturation. IEEE TRANSACTIONS ON COMPUTERS,VOL 49,NO.7,JULY 2000
2 Fayez Elguibaly. ast Parallel Multiplier-Accumulator Using the Modified Booth algorithm. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS-II: ANALOG AND DIGITAL SIGNAL PROCESSIONG, VOL.47,NO.9, SEPTEMBER 2000