booth乘法器的原理与verilog实现
?
 一、乘法原理
如圖所示,二進制乘法和十進制乘法類似,都是單bit相乘,移位后相加
 ??????
 如a(4bit)*b(4bit)
 
 將上圖中所有數相加時,我們會用到陣列乘法器
 
 其中,HA表示半加器,FA表示全加器,虛線表示進位鏈
 上圖紅色和紫色線表示最長路徑,代表了組合邏輯深度,我們對其進行優化
 
 優化后,進位鏈變短
 由此我們可以得出,乘法運算由2部分組成:生成部分積、通過加法樹對數據壓縮
 二、部分積生成
 如圖所示,紅框中的數即為部分積
 我們知道,01110 = 10000 - 00010
 因此,上述5個數相加就可化簡為2個數相減
 110100000-110100
 減法可以用加補碼表示
 110100000+001100
 因此,當有連續的“1”時,這種方法可以減少部分積的個數,加法樹的層級變小
 這就是radix編碼
對于二進制有符號數,其二進制好十進制的轉化方法為:
 
 1、Radix-2編碼
 B可以展開為:
 
 A*B可以寫為:
 
 Radix-2編碼可以消除2bit連續的“1”,但是對于硬件電路來說,加法樹的層級并沒有得到減少,反而引入了編碼電路,由此引出radix-4編碼
2、Radix-4編碼
其基系數為:
 
 B可以展開為:
 
A*B可以寫為:
 
 對每一組A、B相乘
 
 由上表可以看出,我們只需要對A進行取補碼或者移位操作,就可完成部分積的計算
 相比于Radix-2 Booth編碼,Radix-4 Booth編碼將使得乘法累積的部分和數減少一半,部分積只涉及到移位和補碼計算。
3、符號位擴展
假設16*16無符號乘法器的所有部分積均為正數,除了底部的部分和為16bit,其他部分和的位寬均為17bit。
這是因為Radix-4編碼是基于最高bit是符號位,所以對于1616的無符號乘法,需要對高位補0
 
 以公式
 
 為例,如圖所示,紫色是與基系數的項,藍色是補充的符號位
 對于
 來說,Bn-1、Bn-2均為0,所以基系數只可能是1或-1,因此底部的部分和為16bit,而其他的基系數的取值范圍是0~2(假設均為正數),所以位寬是17bit
 如圖
 
 假設1616無符號乘法器的所有部分積均為負數,用二進制補碼表示,需要取反,最低bit加1
 
我們對高位的1進行化簡,由于上圖中所有的數相加后即為乘法結果,我們先將高位的1相加,結果如圖
 
 由此,部分積為正數或負數的情況我們都有了,這時候,我們需要對這兩種情況進行區分
 我們可以看出,兩者的區別在于兩個部分,一個是低位是否加1;另一個是高位擴展的2bit數的值。
 對于低位加1,我們設置變量S,讓低位加S,若部分積為負值,則S為1,若部分積為正值,則S為0
 對于高位擴展數的值,如下圖所示,若𝑆為1,則隨著進位,高bit擴展位為0
 
 為減少部分積的個數,優化為下圖
以上是無符號乘法,對于有符號乘法,有以下3點不同
1、
 
 對于16bit*16bit數,最高位第15bit即為符號位,不需要額外擴展符號位
 2、對于最底部的部分積,也不能保證其取值范圍了,因此也需要最低位加S,高位擴展
 我們引入變量E,E為1表示被乘數與編碼有相同符號位,為0則不同
二、加法樹
1、Wallace樹
1963年,C.S.Wallace提出的一種高效快速的加法樹結構,被后人稱為Wallace樹。其基本思想如下在其文章中描述如下:
Assuming that all summands are generated simultaneously the best possible first step is to group the summands into threes, and introduce each group into its own pseudoadder, thus reducing the count of numbers by a factor of 1.5 ( or a little less, if the number of summands is not multiple of three). The best possible second step is to group the numbers resulting from the first step into threes and again add each group in its own pseudoadder. By continuing such steps until only two numbers remain, the addition is completed in a time proportional to the logarithm of the number of summands.
簡單地講即許多個加數求和,每3個加數分為一組,壓縮至2個加數,循環往復。
但是會用到較多的半加器,半加器電路圖如圖所示:
 
 我們可以看到,其輸入為2bit數,輸出2bit數,對于數據的壓縮沒有作用,而我們加法樹的最終目的是將數據壓縮為2行,最后由行波進位加法器相加后即為最終結果。
 因此我們需要用到盡量多的全加器:
 
 其輸入3bit,輸出2bit,對數據起到了壓縮的作用。
 2、Dadda樹
Dadda樹則解決了以上問題。
 Dadda tree首先從部分積的中間位進行FA累加,邊角部分若不滿足下層條件則不進行累加,進位會不斷的補充到高位,高位部分層數會增多(部分積的圖形類似平行四邊形,兩邊層級較少),因此使用更多了FA
 
 三、實現方法
對于基系數的生成
 乘數的相關bit位和基系數的對應關系如表所示
 
 因此
對于基系數的取值范圍:-2~2,它們對部分積的影響有以下幾個方面:
 1、-2、2,被乘數需要乘以2
 2、-2、-1 被乘數取反
 3、0,部分積為0
 為降低電路面積、功耗,直接將dout的3bit數重新賦值
總結
以上是生活随笔為你收集整理的booth乘法器的原理与verilog实现的全部內容,希望文章能夠幫你解決所遇到的問題。
                            
                        - 上一篇: CPLD国产替代的成熟选择
 - 下一篇: 百度云盘测试用例