基於這本書：

相較於低基乘法，高基乘法直接所需的累加週期更少，例如基4乘法只需要基2乘法一半的週期數，因為基4乘法一個週期能處理2bits。

基4乘法

下面兩張圖展示了基4的移位累加乘法的過程：

對應的硬體設計：

對於基4的移位累加，每個週期都要計算一次部分積

，顯然這裡的

只有四種情況：

對於0，我們可以直接跳過，對於1或2，我們只需要直接給累加器加上

或

。但對於3，我們需要計算

，涉及了一個加法。

對於

，一種辦法是打表（LUT），計算出所有可能的

值，需要時查表即可。

但我們也可以使用{0，a，2a，-a}代替{0，a，2a，3a}作為部分積，即將其中的3a代替為-a。這樣就能避免

的計算。

具體做法是，如果第i次迭代的部分積為3a，那我們就把這個部分積替代為-a，然後在第i+1迭代中補上這個-a。這樣就能避免出現部分積為3a的情況，從而避免這個加法。但這麼做可能導致乘法器最後必須多迭代一次（補上前一次迭代中的-a）。

基於此的設計如下圖：

圖中的+c用於修正部分積-a導致的偏差

其它基數如基8、16也可以有這種思路，先減後加，以簡化部分積。但如上面所說的，這種方法可能導致乘法器必須多一個迭代週期，而對於某些情況（高基乘法器的迭代次數雖然會更少，但每次迭代的開銷會增加），多出的這一週期可能對效能有很嚴重的影響，甚至得不償失。

改良的booth編碼

所謂的改良的booth編碼其實就是將前文（Section 9。4）討論的booth編碼的高基情況推廣，“改良的booth編碼”這個名字可能具有一定的誤導性。

以r=4，s=［0，3］為例，將其轉換為s=［-2，2］上的表示就能得到其booth編碼：

其它情況也是如此，而且，我們也可以用2的補碼錶示booth編碼：

基4booth編碼上的一些情況，說明booth編碼是如何提供稀疏性的。

用2的補碼錶示基4booth編碼的乘法運算過程例子

生成基4booth編碼的電路

基於進位保留加法器（CSA，Carry save adder）

如上圖，我們可以用CSA在一個移位累加週期上計算

，或者說用CSA處理每個迭代週期中的多運算元加法。

CSA乘法器

前面我們就知道了，廣義無符號數GSD的無進位演算法可以避免進位。

我們可以先在GSD上計算多運算元加法

而完成乘法的移位累加過程，然後再將其轉為常規表示，而只有最後這一步轉換會需要進行一次完整的進位。基於此的乘法器就是CSA乘法器。

CSA乘法器

和基於CSA的多運算元加法器的結構是差不多的。

我們同時也可以在CSA乘法器上運用booth編碼，從而再次提高效能，對應的設計如下圖：

帶booth編碼的CSA乘法器

booth編碼和CSA或並行乘法的乘數選擇邏輯

或者我們也可以不用booth編碼，而是像前面FIgure 10。7那樣，用CSA處理每次迭代中部分積涉及

的多運算元加法，對應的設計如下圖：

基8、16乘法器設計

用CSA處理基16乘法上，每次迭代週期中部分積的多位數加法

高基乘法器可以看作是常規二進位制序列乘法器（低速，低面積）和純並行樹乘法器（高速，高面積）間的折中方案（相對高速、低面積），如下示意圖：

當然，實際情況還和工藝等因素有關！

多節拍乘法器（Multibeat Multipliers）

我們可以設計多節拍乘法器，以提高乘法器的時鐘頻率。例如雙節拍乘法器，令其在上一拍和下一拍分別處理一次累加，對應的設計如下圖：

雙節拍的基8booth編碼乘法器

用於順序邏輯的雙相時鐘

三節拍乘法器的抽象示意圖

VLSI複雜性主題

可以看出，前面討論（Chapter 9～10）的序列基2或高基乘法器都很簡單。其中大部分設計使用到的元件包括 CSA、暫存器、MUX（multiplexer）、PPA（carry-propagate adder），以及一些控制邏輯。

（需要注意的是，其中2選1 MUX可以簡化成一組與門，類似地，具有輸入a和

（a的反碼）的MUX可以用一組異或門代替）

討論了乘法器的VLSI面積複雜度開銷情況，還有複雜度下界。見原書有空補。

參考文獻

［Boot51］ Booth， A。 D。， “A Signed Binary Multiplication Technique，”Quarterly J。 Mechanicsand Applied Mathematics， Vol。 4， Pt。 2， pp。 236–240， June 1951。

［Bren81］ Brent， R。 P。， and H。 T。 Kung， “The Area-Time Complexity of Binary Multiplication，”J。 ACM， Vol。 28， No。 3， pp。 521-534， 1981。

［deAn95］ de Angel， E。， A。 Chowdhury， and E。 E。 Swartzlander， “The Star Multiplier，”Proc。29th Asilomar Conf。 Signals， Systems， and Computers， pp。 604–607， 1995。

［Gosl71］ Gosling， J。 B。， “Design of Large High-Speed Binary Multiplier Units，”Proc。 IEE，Vol。 118， Nos。 3/4， pp。 499–505， 1971。［MacS61］ MacSorley， O。 L。， “High-Speed Arithmetic in Binary Computers，”Proc。 IRE， Vol。 49，pp。 67–91， 1961。

［Rubi75］ Rubinfield， L。 P。， “A Proof of the Modified Booth’s Algorithm for Multiplication，”IEEE Trans。 Computers， Vol。 25， No。 10， pp。 1014–1015， 1975。

［Sam90］ Sam， H。， and A。 Gupta， “A Generalized Multibit Recoding of the Two’s ComplementBinary Numbers and Its Proof with Application in Multiplier Implementations，”IEEETrans。 Computers， Vol。 39， No。 8， pp。 1006–1015， 1990。

［Scot07］ Scott， M。， and P。 Szczechowiak， “Optimizing Multiprecision Multiplication for PublicKey Cryptography，” Cryptology ePrint Archive：

http：//

eprint。iacr。org/2007/29

9。pdf

。

［Seid05］ Seidel， P。-M。， L。 D。 McFearin， and D。 W。 Matula， “Secondary Radix Recodings forHigher Radix Multipliers，”IEEE Trans。 Computers， Vol。 54， No。 2， pp。 111–123，2005。

［Vass89］ Vassiliadis， S。， E。 M。 Schwartz， and D。 J。 Hanrahan， “A General Proof for OverlappedMultiple-Bit Scanning Multiplications，”IEEE Trans。 Computers， Vol。 38， No。 2，pp。 172–183， 1989。

［Wase82］ Waser， S。， and M。 J。 Flynn，Introduction to Arithmetic for Digital Systems Designers，Holt， Rinehart， & Winston， 1982。

［Zura87］ Zurawski， J。 H。 P。， and J。 B。 Gosling， “Design of a High-Speed Square-Root，Multiply， and Divide Unit，”IEEE Trans。 Computers， Vol。 36， No。 1， pp。 13–23， 1987。