漣波進位、先行進位、進位保留加法器的差異:延遲、電路規模、用途比較
三者都是由全加器組成的加法電路,差別在於處理進位的方式。漣波進位加法器將全加器串接,進位從低位依序傳到高位,因此延遲與位元數n成正比(O(n))。先行進位加法器由各位元的產生訊號與傳遞訊號平行求出所有進位,將先行電路階層化後,延遲只需O(log n)。進位保留加法器把三個數在不傳遞進位的情況下整理成和與進位兩個數,延遲與位元數無關,只有一級全加器。乘法器以進位保留加法器組成的樹(如華里士樹)減少部分積,最後剩下的兩個數再用高速加法器相加。
| 項目 | 漣波進位加法器 | 先行進位加法器 | 進位保留加法器 |
|---|---|---|---|
| 輸入與輸出 | 將兩個數(與進位輸入)相加,輸出一個和與進位輸出 | 將兩個數(與進位輸入)相加,輸出一個和與進位輸出 | 把三個數整理成和S與進位Cy兩個數(A + B + C = S + Cy) |
| 進位的處理 | 各全加器等待來自低位的進位,再依序傳到高位 | 使用產生訊號g = a·b與傳遞訊號p = a ⊕ b,展開c(i+1) = g(i) + p(i)·c(i),平行求出進位 | 不傳給相鄰位元,而是作為左移一位的數交給下一級 |
| 延遲的增加方式 | O(n)。最壞情況下進位從最低位傳到最高位 | O(log n)(先行電路階層化時) | O(1)。與位元數無關,只有一級全加器 |
| 64位元的參考值 | 進位通過64級全加器 | 以4位元區塊組成3個階層。若用平行前綴加法器,Kogge-Stone型的進位計算為log₂64 = 6級 | 一級為一個全加器的延遲。將64個部分積整理成兩個數的華里士樹為10級 |
| 電路規模 | 最小。n位元需要n個全加器 | 多出先行電路的部分。越快的架構閘與佈線越多(Kogge-Stone型約為n log n) | 一級為n個全加器,沒有傳遞進位的電路。乘法器整棵樹的規模與部分積的位元數(約n²)成正比 |
| 結果的形式 | 一般的二進位數 | 一般的二進位數 | 分成和與進位兩個數的冗餘形式。要成為單一值,最後需用一般的加法器相加 |
| 主要用途 | 不要求速度的小型電路與低功耗電路。在FPGA中常以專用的進位電路(進位鏈)實作 | CPU的ALU、位址計算、浮點運算單元、乘法器最後一級的加法 | 乘法器的部分積加總(華里士樹、Dadda樹)、乘積累加的累積、多個數的加總 |
| 相關方式 | 進位跳躍加法器、進位選擇加法器(速度與面積介於中間) | 平行前綴加法器(Kogge-Stone型、Brent-Kung型等) | 4:2壓縮器,以及與減少部分積的布斯演算法組合 |
數值為具代表性的大致參考值,會因世代或產品而異。