一個初學者理解的乘法器和布思編碼

1、被乘數(shù) 1 1 0 1 乘數(shù) (*) 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 (+) 1 1 0 1積 1 0 0 0 1 1 1 1 n 處理器中乘法器原理跟手算大致相同。 即：把乘數(shù)每一位與被乘數(shù)相乘，最后結(jié)果相加。n 但是有兩種處理方式：一.每算出一個乘積項就去做累加。二.算出所有的乘積項，最后一起加。第一種方法叫迭代；第二種方法叫陣列l(wèi)為了避免上述中的特殊操作，我們可以用布思編碼。l布思編碼的設(shè)計主要作用是避是減少部分積的數(shù)量。其中：E = - An + An-1E真值表： AnAn-1E00- 0 + 0 = 001- 0 + 1 = 110- 1 + 0 =

2、 - 111- 1 + 1 = - 0 當編碼以4為基數(shù)，則稱為基4布思算法（有符號數(shù)）。其中：E = - 2A2n+1 + A2n + A2n-1 當編碼以4為基數(shù)，則稱為基4布思算法（有符號數(shù)）。E的值為： 以上就是（有符號數(shù)）基4布思算法， 基4 布思編碼一次考慮了三位：本位、相鄰高位、相鄰低位；處理了兩位，確定運算量0、1B、2B，形成(N/2)項編碼項、乘積項。 而對于無符號數(shù)則比較麻煩，因為在確定運算量的時候出現(xiàn)了3，這非常難處理，所以一般遇到無符號數(shù)會先轉(zhuǎn)換成有符號數(shù)再進行運算。 以上是基2和基4布思算法，而對于更高基的算法因為會出現(xiàn)3和對位寬要求變得更加復雜，不適合使用。A =

3、 1011B = 1101 運用布思編碼的迭代算法與普通算法區(qū)別 在累加之前要有布思編碼邏輯，用于判斷操作是加還是減操作數(shù)為0還是B如果是基4布思編碼還是2B。 低位擴展，因為A總是左移使本位處于最低位，但是當判斷E時需要用到臨低位，所以要有一位擴展位用于保存臨低位，而基4要有兩位擴展位。 陣列實現(xiàn)就是將所有的乘積項全部都算出來，最后一并相加，當使用基2布思編碼的時候產(chǎn)生N/2項乘積項。 對于無符號數(shù)，一般轉(zhuǎn)換成有符號數(shù)來運算（高位做符號數(shù)擴展）。 但對于減操作（加一個負數(shù)）可以把乘積項做取補邏輯實現(xiàn)。這里的取補（取反加一）邏輯設(shè)計上有一定技巧。 右圖為華萊士樹假發(fā)陣列，它使運算盡量并行。 雖

4、然運用華萊士樹但是超前進位加法器的延時也很高，不是很實用。 一般用上圖中的CSA或4-2壓縮器加一級CLA進行運算。加法器種類 行波進位加法器 超前進位加法器（CLA） 進位旁路加法器 進位保留加法器（CSA) 4-2壓縮加法器 其中進位保留加法器和4-2壓縮加法器是加法陣列中主要采用基本單元CSA-保留進位加法器CSA-保留進位加法器 CSA電路結(jié)構(gòu)圖：關(guān)鍵路徑為兩級異或門延時CSA-保留進位加法器 舉一個例子來說明CSA在陣列加法器中的應用 假設(shè)將3個4位數(shù)A3:0、B3:0、C3:0相加。用CSA實現(xiàn)：上面一行最大延時為4級保留進位加法器的延時CSA-保留進位加法器 如果把保留進位加法器

5、的進位端輸出到下一級 這樣第一級的延時為一個進位保留加法器的延時3-2計數(shù)器 此進位保留加法器輸入3個一位的數(shù)據(jù)A、B、Ci；輸出兩個1位的數(shù)據(jù)D、Co。 代數(shù)運算式如下：Co * 2 + D = A + B + Ci 非常明顯，保留進位加法器為一計數(shù)器計算輸入信號中“1”的個數(shù)，計數(shù)值由Co、D 指示，且： Co權(quán)值為2；A、B、Ci、D權(quán)值為1。 其邏輯表達式如下：D = A B Ci Co = A & B # A & Ci # Ci & A 5-3計數(shù)器 CSA將3個數(shù)據(jù)轉(zhuǎn)換成2個數(shù)據(jù)為3-2計數(shù)器，如果能把5個數(shù)據(jù)轉(zhuǎn)換成3個數(shù)據(jù)則稱之為5-3計數(shù)器。 它有五個輸

6、入端：I0、I1、I2、I3、Ci；三個輸出端：D、C、Co。 代數(shù)運算式如下： D + C * 2 + Co * 2 = I0 + I1 + I2 + I3 + Ci即：I0、I1、I2、I3、Ci、D權(quán)值為1；C、Co權(quán)值為2。其真值表如下頁：5-3計數(shù)器CiI0,I1,I2,I3和值CoCD00000100120/11/0030/11/0141101000110/11/0020/11/0131104111 D = I0 I1 I2 I3 Ci C = (I0 I1 I2 I3) & Ci # ( (I0 I1 I2 I3) & (I0 & I1 # I2 &

7、; I3) = (I0 I1 I2 I3) & Ci # ( (I0 I1 I2 I3) # ( (I0 & I1 # I2 & I3) Co = (I0 # I1) & (I2 # I3)5-3計數(shù)器 傳統(tǒng)結(jié)構(gòu)圖：根據(jù)表達式優(yōu)化后： 有數(shù)據(jù)表示優(yōu)化后的結(jié)構(gòu)可以減小門延時，傳統(tǒng)結(jié)構(gòu)為2個CSA延時，而優(yōu)化后的延時大約為1.5個CSA延時4-2壓縮加法器 如果連續(xù)的兩個高低位5-3計數(shù)器之間Ci和Co級聯(lián)的話,則稱為4-2壓縮加法器 如下圖 A2B2C2D2 A1B1C1D1 A0B0C0D0最低位Ci=0最高位Co單獨保存A2:0、B2:0、C2:0、D2:0為待累加的部分積，分別為3位，如果有更多位則在上圖左邊繼續(xù)級聯(lián)。T13:0、T22:0為經(jīng)過4-2壓縮器壓縮后的兩個中間數(shù)。T13:0 = C2:0,1b0 （C的權(quán)值是2，左