數位邏輯與基本元件

漣波進位加法器(ripple-carry adder)

漣波進位加法器是把兩個多位元數相加最直接的方式:每個位元位置擺一個全加器,讓進位從一個流到下一個,正如你在紙上從最右一欄往左加的做法。這名字描繪了那幅畫面——在低位產生的進位,可能「漣漪」一路往上傳遍整條鏈,每一級都要等鄰居把進位交過來,才能完成自己的計算。它是最容易理解與建造的加法器,也是教科書上從單一全加器走向真實算術的第一步。

要把兩個 4 位元數相加,你接上四個全加器。最低位加器的進位輸入設為 0(或設為 1 以在二補數下做減法)。加器 0 算出和位元 0 和一個進位;那個進位成為加器 1 的進位輸入;加器 1 的進位餵給加器 2;如此一路上到加器 3,它的進位輸出就是溢位指示。問題出在時序:加器 3 必須等進位先傳過加器 0、1、2,才能產生正確的和。所以最壞情況的延遲隨位元數線性增長——對一個 n 位元加器,大約是一級進位延遲的 n 倍,也就是 O(n)。

它為何重要與它的極限:漣波進位加法器是誠實的基準線——正確、極小、容易——但那個線性的進位延遲正是處理器算術的瓶頸。對一次 64 位元加法,等進位慢慢爬過 64 級,會讓加法器成為整顆晶片最慢的路徑,並限制住時脈速度。這就是為什麼真實處理器改用更快(但更大)的方案,如進位前瞻、進位選擇或平行前綴加法器,它們提前算出各個進位,而不是等它們漣漪傳來。

用 4 位元漣波進位加法器算 0111 + 0001。位元 0:1+1 = 0、進位 1。位元 1:1+0+進位 1 = 0、進位 1。位元 2:1+0+進位 1 = 0、進位 1。位元 3:0+0+進位 1 = 1、進位 0。結果 1000(也就是 8)。注意進位在答案定案前一路漣漪穿過了四級——這個序列等待正是該設計的弱點。

進位一次一級、由右往左流;答案只有在最後一個進位穩定後才有效。

更快的加法器給出完全相同的答案——它算的並不是別的東西,只是更早算完。進位前瞻之類用更多閘和面積換取更短的延遲;漣波進位加法器是正確的,只是落在關鍵路徑上。

又称
RCA漣波加法器行波進位加法器