文章目錄

• 八位“Booth二位乘算法”乘法器
• • 原理
  • • 補碼乘法器
    • Booth一位乘
    • Booth二位乘
  • 設計思路
  • • 減法變加法
    • vivado特性
  • 設計文件
  • • 綜合電路
  • 測試文件
  • • 仿真波形

八位“Booth二位乘算法”乘法器

原理

補碼乘法器

之前介紹了幾篇無符號乘法器或加法器的寫法，當然，稍作修改也就可以改成符合有符號數的乘法器或加法器。

但是呢，我們之前寫的乘法器或加法器，其實都是默認是正數來寫的，而且是以正數的原碼來寫的，所以上面說稍作修改也就可以成為有符號數的乘法器或加法器，其實就是對我們以為的原碼進行取補碼，再進行乘法或加法的運算。

隨著計算機硬件部件的升級，處理器技術的發展，現代處理器中的定點數(小數點位置固定)都是按照補碼形式來存儲的。

所以在之前寫的無符號加法器中，只要利用：
$$X_{補}+Y_{補}=[X+Y{]}_{補}$$
就可以輕易將原先的加法器改寫成有符號加法器——只要對結果再取一次補碼即可。

但是乘法器呢？稍作學習可以知道，補碼的乘法是這樣的：
$$X?Y_{補}=[X?Y{]}_{補}$$
我們再考慮一下之前所說的：在現代處理器中的定點數都是按照補碼形式來存儲的。

所以我們要想得到兩個數的乘法結果，首先應該知道被乘數的原碼和補碼，再對最終結果取補碼，即可得到我們期望的乘法結果。

那么如何求“X*Y補”呢？在處理器中，一個二進制數Y補形如y7y6y5y4y3y2y1y0，也就是表示一個數的補碼，那么它的原碼是多少呢？

補碼的計算方法，除了“首位不變，余位取反再加一”的方式，還有一種就是“用溢出條件來減這個數”，在我們之前第一節課說二進制的時候，以鐘表為例——“十二進制”，得到結論——“4是-8的補碼”。

我們用第二種取補碼的方式：-8的補碼=12-8=4（這里沒有考慮符號問題，只是求了補碼的值）

所以考慮一下符號的話，-8的補碼=8-12=-4

同理：

十進制下，-4的補碼=4-10=-6

二進制下，-101補碼=1101補碼=101-1000=-011=1011

這樣解決求補碼的方式在接下來的計算方面就更方便了，至于正數嘛，不變就好了。

回到上面的問題，一個二進制數Y補形如y7y6y5y4y3y2y1y0，它的原碼是多少呢？根據：
$$[X_{補}{]}_{補}=X$$
Y補的原碼Y應該為：
$$Y=(y_7?2^7+y_6?2^6+y_5?2^5+\dots \dots +y_0?2^0)?1?2^8$$
稍微化簡一下：
$$Y=?y_7?2^7+(y_6?2^6+y_5?2^5+\dots \dots +y_0?2^0)$$
所以我們如果想求X*Y，可以先求其補碼：
$$[X?Y{]}_{補}=[X?(?y_7?2^7)+X?(y_6?2^6+y_5?2^5+\dots \dots +y_0?2^0){]}_{補}$$
根據補碼加法“X補+Y補=[X+Y]補”再稍微化簡一下：
$$[X?Y{]}_{補}=?y_7?[X?2^7{]}_{補}+y_6?[X?2^6{]}_{補}+y_5?[X?2^5{]}_{補}+\dots \dots +y_0?[X?2^0{]}_{補}$$
再引入一個定理：
$$[X?2^n{]}_{補}=X_{補}?2^n$$
所以上式又可以換一種寫法：
$$[X?Y{]}_{補}=X_{補}?(?y_7?2^7+(y_6?2^6+y_5?2^5+\dots \dots +y_0?2^0))=Y?X_{補}$$
哦這不就是上面介紹過的補碼乘法嘛：
$$[X?Y{]}_{補}=Y?X_{補}=X?Y_{補}$$
如果令一個數Y1補=y6y6y5y4y3y2y1y0，去掉了首位，那么上式是不是可以理解為：
$$[X?Y{]}_{補}=X_{補}?Y{1}_{補}?y_7?X_{補}?2^7$$
其中的Y1補不就剛好是Y補的后7位嘛？也就是說一個乘法可以分為兩部分理解：首位的乘法和其他位的乘法。首位的乘法產生的部分積符號是減，其他位的部分積符號為加。

經過上面的推導大家應該會對補碼乘法的原理有了一定的概念，我們來把它寫成豎式的形式，以(-6)x(-7)為例，原碼乘應該是1110x1111，在計算機中是以補碼的形式存儲，所以補碼乘是1010x1001，代入公式，令X補=1010，Y補=1001，其運算過程如下：

這里可能有一些迷惑的是：為什么第一步運算得到的結果是11111010？為什么要在前面填充1111？

這也就是所謂的符號填充，我們之前的設計中都沒有涉及到符號位，所以默認都是填充0，現在遇到了負數問題，也就需要填充符號了，但是這樣看起來是不是一點都覺得很奇怪？如果沒辦法理解的話，我建議你可以嘗試對它求補碼，看看是不是可以保持首位符號位不變，余位取反加一。驚嘆于設計師的機智。

補碼乘法器的原理講明白了，具體電路實現的話，大家可以嘗試一下，本節重點不在于此。

Booth一位乘

在上面已經討論了補碼乘法器的原理，那么什么是Booth乘法器呢？Booth乘法器是由英國的Booth夫婦提出的，并沒有什么特殊含義，所以我們直接快進到內容。

經過補碼乘法器的推導：
$$[X?Y{]}_{補}=X_{補}?(?y_7?2^7+(y_6?2^6+y_5?2^5+\dots \dots +y_0?2^0))$$
參考中學數學：
$$2^n=2?2^{n?1}$$
其核心計算思想是括號里的形式，也就是**Y補的原碼Y，**所以我們對括號里的內容再進行分解合并，也就是對Y分解合并。先分解：
$$Y=?y_7?2^7+((2?1)y_6?2^6+(2?1)y_5?2^5+\dots \dots +(2?1)y_0?2^0)$$
這樣應該挺直觀了吧：
$$Y=?y_7?2^7+(y_6?2^7?y_6?2^6)+(y_5?2^6?y_5?2^5)+\dots \dots +(y_0?2^1?y_0?2^0)$$
再合并：
$$Y=(y_6?y_7)?2^7+(y_5?y_6)?2^6+(y_4?y_5)?2^5+\dots \dots +(0?y_0)?2^0$$
最后有個0-y0的項，看起來有點不合群，所以令：
$$y_{?1}=0$$
代入上式，即：
$$Y=(y_6?y_7)?2^7+(y_5?y_6)?2^6+(y_4?y_5)?2^5+\dots \dots +(y_{?1}?y_0)?2^0$$
這也就是Booth一位乘算法的原理。其優點就在于不用再像補碼乘法器那樣，不需要專門對最后一次部分積采用補碼減法。

根據上式，還可以列出Booth一位乘的規則：

y(i-1)y(i)y(i-1) - y(i)操作

0	0	0	加0
0	1	-1	減X補
1	0	1	加X補
1	1	0	加0

再舉個例子來計算，仍以(-6)x(-7)為例，補碼乘是1010x1001，列出豎式：

可是這里為什么還是有減法呢？和常規的補碼乘法器相比，簡直是老和尚抹洗頭膏，大可不必。甚至由于每次判斷兩位數字，增大了電路的復雜度，那么為什么booth乘法器如此好用呢？

其實booth一位乘算法并不常用，但是booth二位乘就不一樣了，通過增加一定的空間復雜度，將運算周期減為一半！

Booth二位乘

還是根據補碼乘法器，我們將Y的表達式再進行變換——先分解：
$$Y=?2?y_7?2^6+y_6?2^6+(y_5?2^6?2?y_5?2^4)+\dots \dots +y_0?2^0+y_{?1}?2^0$$
再整合：
$$Y=(y_5+y_6?2?y_7）?2^6+（y_3+y_4?2?y_5）?2^4)+\dots \dots +(y_{?1}+y_0?2?y_1)?2^0$$
好了Booth二位乘算法也完事了，類比于Booth一位乘，我們也可以列出Booth二位乘的規則：

y(i-1)y(i)y(i+1)y(i-1) + y(i) - 2*y(i+1)操作

0	0	0	0	加0
0	1	0	1	加X補
1	0	0	1	加X補
1	1	0	2	加2*X補，即X補<<1
0	0	1	-2	減2*X補，即X補<<1
0	1	1	-1	減X補
1	0	1	-1	減X補
1	1	1	0	加0

再舉個例子來計算，仍以(-6)x(-7)為例，補碼乘是1010x1001，列出豎式：

運算周期減半了！

好了，那Booth乘法器有沒有三位乘呢？可以有，但是三位的時候就會出現加3*X補，2*X補可以通過左移一位得到，而3*X補就有點麻煩了，所以不再介紹，至于四位乘、八位乘，想挑戰的同學可以挑戰一下。

設計思路

減法變加法

首先我們來解決一個問題，如何把減法消除？我們知道，**減去一個數，等于加上這個數的相反數；減去一個數，也等于加上這個數的補碼。**這個過程中的減數也默認是正數，因為正數的補碼還是正數，只有正數前面加一個符號再去補碼才有用。那么如上面豎式所寫，減去一個負補碼，就應該等于加上“這個負補碼的補碼的相反數”，比如上面的補碼乘法器豎式，就應該變換成如下形式：

再說明一下吧：減11010，就相當于加11010的補碼的相反數，即加10110的相反數，即00110。

所以booth一位乘算法的示例應該變成這樣：

booth二位乘算法的示例應該變成這樣：

vivado特性

考慮到上述減法變加法的操作后，容易總結出：減法變加法，其實就是對補碼的符號位取反，也就是對減數每一位取反后再加一。

再回讀一邊上述的理論部分，可能你會發現，在乘法運算中，只用到了補碼和**“負補碼”兩種概念的數字。而在vivado中（相當于在處理器中），數字默認是以補碼形式存儲的，即輸入的乘數默認就是補碼形式**，這樣只需要再求出**“負補碼”**即可。設X[3:0]表示一個乘數，默認是以補碼形式存儲，則其“負補碼”：
$$X_{負補碼}=!X+1$$
至于其原碼：
$$X_{原碼}=(X[3],!X[2:0])+1$$
其實根本用不著。

有了以上知識儲備，我們就可以寫代碼啦~

設計文件

//由于實力不夠，沒能設計成改一個數字變一個規模的程序 `define size 8 module mul_booth_signed(input wire [`size - 1 : 0] mul1,mul2,input clk,input wire [2:0] clk_cnt,//運算節拍，相當于狀態機了，8位的話每次運算有4個拍output wire [2*`size - 1 : 0] res);//由于傳值默認就是補碼，所以只需要再計算“負補碼”即可wire [`size - 1 : 0] bmul1,bmul2;assign bmul1 = (~mul1 + 1'b1) ;assign bmul2 = (~mul2 + 1'b1) ;//其實乘數2的負補碼也沒用到。//其實可以把狀態機的開始和結束狀態都寫出來，我懶得寫了，同學們可以嘗試一下啊~parameter zeroone = 3'b00,twothree = 3'b001,fourfive = 3'b010,sixseven = 3'b011;//y(i-1),y(i),y(i+1)三個數的判斷寄存器，由于有多種情況，也可以看成狀態機（也可以改寫成狀態機形式，大家自己試試吧）reg [2:0] temp;//部分積reg [2*`size-1 : 0] A;//每個節拍下把相應位置的數據傳給temp寄存器always @ (posedge clk) begincase(clk_cnt)zeroone : temp <= {mul2[1:0],1'b0};twothree : temp <= mul2[3:1];fourfive : temp <= mul2[5:3];sixseven : temp <= mul2[7:5];default : temp <= 0;endcaseendalways @(posedge clk) beginif (clk_cnt == 3'b100) begin//如果節拍到4就讓部分積歸0，此時已經完成一次計算了A <= 0;end else case (temp)3'b000,3'b111 : begin//這些是從高位到低位的判斷，別看反了噢A <= A + 0;end3'b001,3'b010 : begin//加法操作使用補碼即可，倍數利用左移解決A <= A + ({{8{mul1[`size-1]}},mul1} << 2*(clk_cnt-1));end3'b011 : beginA <= A + ({{8{mul1[`size-1]}},mul1} << 2*(clk_cnt-1) + 1);end3'b100: begin//減法操作利用“負補碼”改成加法操作，倍數利用左移解決A <= A + ({{8{bmul1[`size-1]}},bmul1} << 2*(clk_cnt-1) + 1);end3'b101,3'b110 : beginA <= A + ({{8{bmul1[`size-1]}},bmul1} << 2*(clk_cnt-1));enddefault: A <= 0;endcaseend//當節拍到4的時候寫入結果寄存器。assign res = (clk_cnt == 3'b100) ? A : 0; endmodule

這是一個八位Booth二位乘算法的乘法器，至于Booth一位和Booth四位的乘法器，大家各自嘗試就好。

此外在這個文件當中，我用到了clk_cnt這個寄存器，大家是不是以為我會多用一個模塊用來產生clk_cnt的波形？

身為一個懶人，我直接在測試文件里寫了吼吼吼~

綜合電路

37個元件，36個IO口，318根線

測試文件

`timescale 1ns / 1ps module mul_tb();reg [7:0] mul1,mul2;wire [15:0] res;reg clk;wire clk_en;reg [2:0] clk_cnt;initial beginmul1 <= -8'd7;mul2 <= -8'd3;clk <= 0;clk_cnt <= 3'b0;endalways # 10 clk = ~clk;//clk_cnt發生器，懶人版always @(posedge clk) beginclk_cnt <= clk_cnt + 1'b1;if (clk_cnt == 3'b100)clk_cnt <= 3'b00;end//每次運算結束后，讓乘數變化，以便產生不同的數據用以觀察assign clk_en = (clk_cnt == 3'b100) ? 1'b1 : 1'b0;always @ (posedge clk_en) beginmul2 <= mul2 + 1'b1;endmul_booth_signed try(.mul1(mul1),.mul2(mul2),.res(res),.clk(clk),.clk_cnt(clk_cnt)); endmodule

仿真波形

將其改成有符號十進制數形式顯示，可以驗證電路設計正確。

總結

以上是生活随笔為你收集整理的八位“Booth二位乘算法”乘法器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。