1.超前進(jìn)位加法器

看了一些面經(jīng)，提到會(huì)讓你用基礎(chǔ)的門搭加法器，因此首先得熟悉半加器，全加器等最基礎(chǔ)的加法器才能理解之后的超前進(jìn)位加法器，樹(shù)型加法器等復(fù)雜的加法器。

半加器的輸入為a，b，輸出為結(jié)果s和進(jìn)位c，則其關(guān)系為

全加器的輸入多了一個(gè)進(jìn)位cin，輸出為結(jié)果位s和進(jìn)位輸出cout，則其關(guān)系為

使用多個(gè)全加器級(jí)聯(lián)，把每一級(jí)的進(jìn)位輸出作為下一級(jí)的進(jìn)位輸入即構(gòu)成了行波進(jìn)位加法器，其加法過(guò)程是很好理解的，就是從最低位開(kāi)始一位一位運(yùn)算，并且把低位的進(jìn)位加到高位上，與手算的思路是一致的。其結(jié)構(gòu)如圖所示。

但若是畫(huà)出其門級(jí)的電路圖我們會(huì)發(fā)現(xiàn)，由于采用級(jí)聯(lián)結(jié)構(gòu)，行波進(jìn)位加法器的關(guān)鍵路徑非常長(zhǎng)，N比特行波進(jìn)位加法器的最長(zhǎng)路徑位

個(gè)門電路延遲，在高速處理器中將極大地限制電路的性能。因此誕生了超前進(jìn)位加法器以改善關(guān)鍵路徑，其主要思想是將所有的進(jìn)位都并行進(jìn)行，為此需對(duì)原始的加法器計(jì)算公式做一些改動(dòng)。令

則對(duì)于N比特超前進(jìn)位加法器，其結(jié)果位和進(jìn)位可寫(xiě)成如下的形式

則通過(guò)迭代

的表達(dá)式，可將其寫(xiě)成只包含 的表達(dá)式，從而完成并行計(jì)算。以4bit超前進(jìn)位加法器為例，其進(jìn)位鏈公式計(jì)算如下

則對(duì)應(yīng)的，超前進(jìn)位加法器結(jié)構(gòu)如圖所示。

對(duì)于更大位寬的，例如32，64bit的加法運(yùn)算，為了避免造成電路的扇入扇出過(guò)大，會(huì)用多個(gè)4bit超前進(jìn)位加法器級(jí)聯(lián)，從而獲得一個(gè)折中的解決方案。

從關(guān)鍵路徑上來(lái)看，4bit超前進(jìn)位加法器的進(jìn)位都只需要經(jīng)過(guò)3級(jí)門電路延遲即可得到，相比較于行波進(jìn)位加法器有巨大的優(yōu)勢(shì)，即使級(jí)聯(lián)構(gòu)成更大位寬的加法器仍然縮短了關(guān)鍵路徑的長(zhǎng)度。

2.Wallace樹(shù)型結(jié)構(gòu)

話說(shuō)這Wallace是不是該翻譯成華萊士呢，嗯~亦可賽艇啊。

要理解Wallace樹(shù)需要先理解進(jìn)位保存加法器。進(jìn)位保存加法器以三個(gè)樹(shù)作為輸入，輸出兩個(gè)數(shù)，這兩個(gè)數(shù)相加即為最終的加法結(jié)果，因此進(jìn)位保存加法器相當(dāng)于進(jìn)行了一次壓縮過(guò)程，將三個(gè)數(shù)的加法壓縮為兩個(gè)數(shù)的加法。然而進(jìn)位保存加法器并不是什么新奇的黑科技，而是全加器的一個(gè)變形，如下圖所示。

從圖中可以看出，進(jìn)位保存加法器就是對(duì)全加器進(jìn)行重新包裝。

熟悉了進(jìn)位保存加法器后我們就可以來(lái)看Wallace樹(shù)型結(jié)構(gòu)了，其總體結(jié)構(gòu)如下圖所示。

可以看出，樹(shù)型結(jié)構(gòu)就是將多個(gè)加數(shù)分組，每三個(gè)分為一組后，經(jīng)過(guò)進(jìn)位保存加法器壓縮為2個(gè)數(shù)，如此迭代循環(huán)得到最終加法的結(jié)果。

在乘法器中，乘法的積是多個(gè)部分和之和，若使用普通加法器，則需等待前面的部分和計(jì)算完成才能計(jì)算后面的部分和，延遲較高，因此可以使用Wallace樹(shù)型結(jié)構(gòu)，對(duì)部分和進(jìn)行分組計(jì)算得到最后的總和結(jié)果，即為乘法的積。

3.Booth乘法器

若是用補(bǔ)碼表示一個(gè)數(shù)，則其轉(zhuǎn)換為十進(jìn)制的計(jì)算方式為

將其展開(kāi)，并令

，則可以得到

此時(shí)再計(jì)算乘法

可得

從上式可以看出，這樣變化的優(yōu)勢(shì)是若B的某相鄰兩位相同，則可以省去運(yùn)算而只進(jìn)行移位即可。如果

，則為 ，如果 ，則為 ，從而簡(jiǎn)化了運(yùn)算過(guò)程。

以上是Radix-2 Booth算法的推導(dǎo)，其算法流程如下

1.被乘數(shù)和乘數(shù)分別放入A，B寄存器，中間結(jié)果放入M，B寄存器。
2.另設(shè)置一個(gè)1bit的 寄存器。將M， 寄存器初始為0。
3.在每個(gè)周期檢查 寄存器。
4-1.若 = 00 或 11，將{ }直接右移1bit。
4-2.若{ } = 01，則A與M相加，將{ }直接右移1bit。
4-3.若{ } = 10，則A與M相減，將{ }直接右移1bit。
5.最終的結(jié)果即為{M,B}，是乘法積的補(bǔ)碼表示。

需要注意的是，上述所有數(shù)都是補(bǔ)碼表示，且上述右移操作需保留符號(hào)位，即保持M的最高位不變。

在實(shí)際應(yīng)用中較常用的是Radix-4 Booth乘法器，與Radix-2類似，其算法可通過(guò)原始的補(bǔ)碼計(jì)算式展開(kāi)得到

上式中的

設(shè)置為0。Radix-4 Booth編碼表如下表所示。

不難看出，相較于Radix-2 Booth算法，Radix-4 Booth算法需要的循環(huán)次數(shù)更少，因此在實(shí)際中應(yīng)用更加廣泛。

參考鏈接

關(guān)于乘法器和加法器，如下的專欄講述的非常詳細(xì)，可以作為參考。

紙上談芯：【HDL系列】超前進(jìn)位加法器原理與設(shè)計(jì)?zhuanlan.zhihu.com紙上談芯：【HDL系列】乘法器(4)——圖解Wallace樹(shù)?zhuanlan.zhihu.com紙上談芯：【HDL系列】乘法器(5)——Radix-2 Booth乘法器?zhuanlan.zhihu.com紙上談芯：【HDL系列】乘法器(6)——Radix-4 Booth乘法器?zhuanlan.zhihu.com

總結(jié)

以上是生活随笔為你收集整理的原码一位乘法器设计_数字IC校招基础知识点复习（七）——超前进位加法器、Wallace树、Booth乘法器...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。