怎麼理解Booth演算法?

12-27

http://wapbaike.baidu.com/view/1283105.htm?ref=wiseref=wisessid=0from=1086kuid=0pu=usm@0,sz@1320_2001,ta@iphone_1_5.0_3_534bd_page_type=1baiduid=2A69F0025CA2E29129FDA4C2B5108E3Dtj=www_normal_2_0_10_title

首先，把下圖的三個式子依次稱為【1】【2】【3】。

一個有符號的二進位數的補碼用式子【1】來表示，可以等價地寫成式子【2】和【3】。

布斯編碼可以減少部分積的數目，用來計算有符號乘法，提高乘法運算的速度。

下圖是二進位乘法的過程：

例如假設有一個8位乘數（Multiplier）：0111_1110，它將產生6行非零的部分積。如果把該數字記成另一種形式，1000_00-10（可以驗證是同一個數字，-1是負1），其實就是式子【1】重寫為式子【2】，則可以大大減少非零行的數目。採用這一形式，我們只需相加兩個部分積，但最終的加法器必須也能執行減法。這種形式的變換稱為Booth Encoding，它保證了在每兩個連續位中最多只有一個是1或-1。部分積數目的減少意味著相加次數的減少，從而加快了運算速度（並減少了面積）。從形式上來說，這一變換相當於把乘數變換成一個四進位形式。

但最經常使用的是改進的布斯編碼。乘數按三位一組進行劃分，相互重疊一位。其實就是把式子【1】重寫為式子【3】。每一組按下表編碼，並形成一個部分積。

再考慮前面提及的8位二進位數0111_1110。從msb到lsb，可以把它分為三位一組首尾重疊的四組：01（1），11（1），11（1），10（0），末尾補了一個輔助位0。根據上表編碼得到：10（2×），00（0×），00（0×），-10（-2×），或者表示為1000_000-10，這與前面得到結果是一樣的。這時，乘2就是移位。所以布斯演算法僅涉及加法，減法和移位操作。

知道了這個過程，這時你再看布斯演算法應該很容易理解了。我覺得最重要的是那三個式子！

另外，大（即位數較多的）乘法器可以採用高基（high radix）的布斯編碼。

希望能幫到你。

關與原理維基百科是這麼寫的：

考慮一個由若干個0包圍著若干個1的正的二進位乘數，比如00111110，積可以表達為：
${displaystyle M imes ,^{prime prime }0;0;1;1;1;1;1;0,^{prime prime }=M imes (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M imes 62}$
其中，M代表被乘數。變形為下式可以使運算次數可以減為兩次：
${displaystyle M imes ,^{prime prime }0;1;0;0;0;0{mbox{-1}};0,^{prime prime }=M imes (2^{6}-2^{1})=M imes 62}$
事實上，任何二進位數中連續的1可以被分解為兩個二進位數之差：
${displaystyle (ldots 0overbrace {1ldots 1} ^{n}0ldots )_{2}equiv (ldots 1overbrace {0ldots 0} ^{n}0ldots )_{2}-(ldots 0overbrace {0ldots 1} ^{n}0ldots )_{2}}$
因此，我們可以用更簡單的運算來替換原數中連續為1的數字的乘法，通過加上乘數，對部分積進行移位運算，最後再將之從乘數中減去。它利用了我們在針對為零的位做乘法時，不需要做其他運算，只需移位這一特點，這很像我們在做和99的乘法時利用99 = 100 ? 1這一性質。這種模式可以擴展應用於任何一串數字中連續為1的部分（包括只有一個1的情況）。那麼，
${displaystyle M imes ,^{prime prime }0;0;1;1;1;0;1;0,^{prime prime }=M imes (2^{5}+2^{4}+2^{3}+2^{1})=M imes 58}$ ${displaystyle M imes ,^{prime prime }0;1;0;0{mbox{-1}};0;1;0,^{prime prime }=M imes (2^{6}-2^{3}+2^{1})=M imes 58}$
布斯演算法遵從這種模式，它在遇到一串數字中的第一組從0到1的變化時（即遇到01時）執行加法，在遇到這一串連續1的尾部時（即遇到10時）執行減法。這在乘數為負時同樣有效。當乘數中的連續1比較多時（形成比較長的1串時），布斯演算法較一般的乘法演算法執行的加減法運算少。