博主最近在學習加法器、乘法器、IEEE的浮點數標準，作為數字IC的基礎。當看到booth編碼的乘法器時，對booth編碼不是很理解，然後在網上找各種理解，終於豁然開朗。現將一個很好的解釋分享給大家，希望能對大家有所幫助。 首先，看看這幾個公式： 可以證明的是，這三個公式是相等的，一個有符號的二進位數 ...
博主最近在學習加法器、乘法器、IEEE的浮點數標準，作為數字IC的基礎。當看到booth編碼的乘法器時，對booth編碼不是很理解，然後在網上找各種理解，終於豁然開朗。現將一個很好的解釋分享給大家，希望能對大家有所幫助。
首先，看看這幾個公式：
可以證明的是，這三個公式是相等的，一個有符號的二進位數的補碼用公式1來表示，可以等價地寫成公式2和公式3。
布斯編碼可以減少部分積的數目（即減少乘數中1的個數），用來計算有符號乘法，提高乘法運算的速度。
如上圖所示為二進位乘法的過程，也是符合我們正常計算時的邏輯，我們假設有一個8位乘數（Multiplier），它的二進位值為0111_1110，它將產生6行非零的部分積，因為它有6個非零值（即1）。如果我們利用公式2將這個二進位值改為1000_00-10，其中低四位中的-1表示負1，可以證明兩個值是相等的。可以這樣簡單理解，那就是現在原值得末尾加輔助位0，變為0111_1110_0，然後利用低位減去高位，即得到1000_00-10。這樣一變換可以減少0的數目，從而減少加的次數，我們只需相加兩個部分積，但是終的加法器必須也能執行減法。這種形式的變換稱為booth encoding（即booth編碼），它保證了在每兩個連續位中最多只有一個是1或-1。部分積數目的減少意味著相加次數的減少，從而加快了運算速度（並減少了面積）。從形式上來說，這一變換相當於把乘數變換成一個四進位形式。
最經常使用的是改進的booth編碼。乘數按三位一組進行劃分，相互重疊一位。其實就是把公式1重寫為公式3。每一組按下表編碼，並形成一個部分積。
