【硬體算術設計】硬體加法器原理｜第2章：超前進位加法器，分塊、分級超前進位加法器

上一章：第1章：行波進位加法器與曼徹斯頓加法器

2▏超前進位加法器（CLA， Carry-Lookahead Adder）

這一章我們來討論一下超前進位加法器，以及它的變種“分塊、多級超前進位加法器”，主要是為下一章所討論的並行字首加法器做些鋪墊。

2.1▏超前進位加法器

第1章中我們討論了曼徹斯頓加法器，現在將它的邏輯表示式重寫一遍：

$\begin{align} \rm{ c_i=g_i\vee (p_i\cdot c_{i-1}) \\s_i=x_i\oplus y_i\oplus c_{i-1} } \end{align}\tag{2.1.1}$

其中

$\rm i=0,1,2\dots,n-1$

；

$\rm x,y$

分別是加法器的兩個輸入運算元；

$\rm s$

是加法器輸出；

$\rm c$

是進位訊號；

$\rm p=x\oplus y,\ g=x\cdot y$

。

之前我們說過，該加法器的關鍵路徑就是就是

$\rm {c_{-1}}$

到

$\rm c_n$

這條路徑。就是說，它的關鍵路徑在進位鏈上。因此，要改善該加法器的延遲，我們應該從它的進位鏈條上下手，即改善

$\rm c_i$

的延遲。

要改善進位鏈的延遲，一種樸素的想法就是直接將

$\rm c_i$

不斷地展開，直至無法再展開：

$\\\begin{align} \rm{ \\c_i \\=g_i\vee (p_i\cdot \color{red}{c_{i-1}}) \\{=g_i\vee (p_i\cdot\color{red}{(g_{i-1}\vee (p_{i-1}\cdot \color{green}{c_{i-2}}) })} \\=g_{i}\vee (p_{i}\cdot g_{i-1})\vee (p_{i}\cdot p_{i-1}\cdot \color{green}{c_{i-2}}) \\{=g_{i}\vee (p_{i}\cdot g_{i-1})\vee (p_{i}\cdot p_{i-1}\cdot \color{green}{(g_{i-2}\vee (p_{i-2}\cdot \color{blue}{c_{i-3}})})} \\=g_i\vee (p_i\cdot g_{i-1})\vee (p_i\cdot p_{i-1}\cdot g_{i-2})\vee (p_i\cdot p_{i-1}\cdot p_{i-2}\cdot \color{blue}{c_{i-3}}) \\=g_i\vee (p_i\cdot g_{i-1})\vee (p_i\cdot p_{i-1}\cdot g_{i-2})\vee (p_i\cdot p_{i-1}\cdot p_{i-2}\cdot \color{blue}{(g_{i-3}\vee (p_{i-3}\cdot \color{brown}{c_{i-4}}))}) \\=g_i\vee (p_i\cdot g_{i-1})\vee (p_i\cdot p_{i-1}\cdot g_{i-2})\vee (p_i\cdot p_{i-1}\cdot p_{i-2}\cdot {g_{i-3})\vee (p_i\cdot p_{i-1}\cdot p_{i-2}\cdot p_{i-3}\cdot \color{brown}{c_{i-4}}))}) \\=\cdots }\end{align} \tag{2.1.2}$

這樣就能透過上式

［1］

，根據每個輸入位的

$\rm p$

訊號和

$\rm g$

訊號（還有

$\rm c_{-1}$

），直接生成第

$\rm i$

個進位訊號。

上式

的關鍵路徑顯然要比

小得多。式

就是超前進位鏈的邏輯表示式。

問題在於，

中的多運算元與、或門的扇入係數是會隨位數

$\rm i$

增長的。

在位數已經較高的情況下，再增加位數，會在進位鏈中引入超高扇入的邏輯閘，使得整體電路規模以二次的速率增長。

儘管如今ASIC的面積資源相當充裕（相對而言），但導線延遲也在隨著尺度的縮小而變地日益顯著，甚至成為了延遲的主要來源。而這種高扇入電路的導線開銷是巨大的，所以，超前進位鏈在實際應用中仍受限於位寬，只是原因從電路面積變成了導線延遲。

要控制超前進位鏈電路複雜度的增長，可以考慮：

分塊超前進位

分級超前進位

我們在接下來的兩節中討論這兩個思路。

2.2▏分塊超前進位鏈

圖2。1，將一個32bit超前進位鏈拆成4個8bit超前進位鏈

所謂分塊超前進位鏈，就是將一條較大的完整的超前進位鏈劃分為多塊較小的超前進位鏈塊，例如上圖2。1所示。

（我們也可以從高基加法（高基進位）的角度來理解分塊超前進位鏈，可以將傳統超前進位鏈

理解為基-2的超前進位鏈；而分塊超前進位鏈，比如基於4bit塊的分塊超前進位鏈，就可以理解為基-16的超前進位鏈）

但是具體它是怎麼拆的？現在我們來觀察其中具體的一個塊（圖2。2右）：

圖2。2，4bit超前進位鏈（左）和4bit超前進位鏈塊（右）

超前進位鏈塊和標準的超前進位鏈非常相似，但區別在於，它是從第

$\rm i$

位開始的；以及為了方便後文，這裡還將

$\rm c_3$

替代為了

$\rm g_{[i,i+3]}$

和

$\rm p_{[i,i+3]}$

，這兩個訊號分別叫做“塊

$\rm g$

訊號”和“塊

$\rm p$

訊號”，代表了這個塊的進位資訊。它們的具體形式分別是：

$\\\begin{align}\rm{ g_{[i,i+3]}=(g_{i+3})\vee (g_{i+2}\cdot p_{i+3})\vee (g_{i+1}\cdot p_{i+2}\cdot p_{i+3})\vee (g_i \cdot p_{i+1 }\cdot p_{i+2}\cdot p_{i+3}) \\p_{[i,i+3]}=p_i\cdot p_{i+1}\cdot p_{i+2}\cdot p_{i+3} } \end{align}$

這就是塊

$\rm [i,i+3]$

作為一個整體，所對應的塊

$\rm g$

訊號和塊

$\rm p$

訊號。一般的

$\rm g_{[i,i+n]}$

和

$\rm p_{[i,i+n]}$

的一般形式同理。

然後，塊

$\rm [i,i+n]$

的最高進位輸出可以透過下式生成（如圖2。3中的一個塊）：

$\\\rm c_{i+n}=g_{[i,i+n]}\vee(p_{[i,i+n]}\cdot c_{i-1})\tag{2.2.1}$

將上式與式

對比你會發現它們形式是一樣的，例如對於塊

$\rm[0,3]$

有：

$\\\rm c_{i+3}=g_{[i,i+3]}\vee(p_{[i,i+3]}\cdot c_{i-1}),\quad i=0$

我們可以選擇直接將所有塊串聯，來獲得完整的進位鏈，例如下圖2。3：

圖2。3，將所有的塊串聯，以構成完整的進位鏈

但一類更好的做法是所謂的“分級超前進位鏈”。

2.3▏分級超前進位鏈

將超前進位鏈拆成多個塊後，還可以利用以下性質將相鄰塊的塊

$\rm g,p$

訊號合併：

若假定

$\rm i_0<i_1<i_2$

（即兩個相鄰的塊

$\rm[i_0,i_1-1]$

和

$\rm [i_1,i_2]$

），則有：

$\\\begin{align} \rm{ g_{[i,i_2]}=g_{[i_1,i_2]}\vee (g_{[i_0,i_1-1]}\cdot p_{[i_1,i_2]}) \\p_{[i_0,i_2-1]]]}=p_{[i_0,i_1-1]}\cdot p_{[i_1,i_2]} }\end{align}\tag{2.3.1}$

透過上式，我們就可以將兩個相鄰塊的塊

$\rm g,p$

訊號合併，得到的結果相當於兩個塊合併後，作為一個整體的大塊

$\rm g,p$

訊號（圖2。4）。

圖2。4，兩個相鄰塊的合併

兩個相互重疊的塊也是可以被合併的（圖2。5）。具體來說，對於

$\rm i_0\le i_1-1\le j_0<j_1$

（即兩個有重疊部分的塊

$\rm [i_0,j_0]$

和

$\rm [i_1,j_1]$

），有：

$\\\begin{align} \rm{ g_{[i_0,j_1]}=g_{[i_1,j_1]}\vee( g_{[i_0,j_0]}\cdot p_{[i_1,j_1]}) \\p_{[i_0,j_1]}=p_{[i_0,j_0]}\cdot p_{[i_1,j_1]} } \end{align}\tag{2.3.2}$

圖2。5，兩個重疊塊的合併

利用這種合併的性質，我們就可以構造出所謂的分級超前進位鏈了。例如下圖2。6：

圖2。6，分級超前進位鏈。

這種樹形的分級結構顯然具有非常多種不同的可行構造，在第三章中，我們會引入一個叫做“並行字首運算”的概念，可以用它來非常簡潔地描述出各種不同的分級超前進位鏈構造，這也是許多文獻中所採用的表述。

2.3.1▏時間複雜度的簡單分析

對於單個塊，它的處理步驟以及對應所需的最低邏輯閘級數（gate level）是這樣的：

生成每個位元位的

$\rm g,p$

訊號（需要1級邏輯閘）

生成對應的塊

$\rm g,p$

訊號（需要2級邏輯閘）

（如果需要的話）生成塊的最高進位輸出，以提供給需要的相鄰塊（需要2級邏輯閘）

這就是分級超前加法器中，每級（如圖2。6中的每層）所需的邏輯閘深度。然後，就像圖2。6那樣，這種分級超前加法器是可以以樹的形式構造的，其中只需要對數個這樣的層。於是，這個加法器的時間複雜度（邏輯閘級數）是對數級的，即

$\cal O(\log n)$

。

2.4▏小結，思考與習題

本章介紹了超前進位加法器，以及它的變種：“分塊、分級超前進位加法器”。其實，將圖2。6這樣的分級超前進位設計直接叫做“並行字首加法器的進位鏈”是沒問題的，但是這裡並沒有這麼叫，因為前面的描述不是基於“並行字首運算”來討論的。在下一章中，我們將從一個相對代數化的角度來描述這類加法器設計，以接軌文獻中更常用的表述。

以下是習題與思考題：

用你熟知的技術（如VerilogHDL，或者multisim等）實現一個2進位制的超前進位加法器。

將2。1▏節中介紹的2進位制超前進位加法推廣至16進位制。

將2。1▏節本文中介紹的2進位制超前進位加法推廣至10進位制

［2］

。

將2。1▏節本文中介紹的2進位制超前進位加法推廣至r進位制。

（選做）用多運算元與運算子

$\rm \bigwedge_{i=0}^{n} a_i=a_0\cdot a_1 \cdot a_2\dots a_{n}$

和多運算元或運算子

$\rm \bigvee_{i=0}^{n}a_i=a_0\vee a_1\vee a_2\dots a_n$

寫出式

的一般形式。

參考

可以用多運算元與運算子和多運算元或運算子寫出這個公式的一般形式，但是寫出來非常醜，所以我還是把這個陰間公式刪掉了。

關於r進位制的進位規則，請複習1。5▏節。

小蜜蜂問答

小蜜蜂問答

【硬體算術設計】硬體加法器原理｜第2章：超前進位加法器，分塊、分級超前進位加法器

推薦文章

小蜜蜂問答

小蜜蜂問答

【硬體算術設計】硬體加法器原理｜第2章：超前進位加法器，分塊、分級超前進位加法器

相關文章

摘下來的大櫻桃分揀時用機器分揀好，還是用人工分揀好？

兒童聽力損失程度劃分是什麼？可能引起的問題與需要注意的是什麼？

咖啡豆的G1或G4表示什麼？

加法器和減法器的實現

推薦文章