# Carry Lookahead
一般傳統的二進位加法 Ripple Carry Adder（漣漪進位加法器）是將進位從低位元向高位元逐位地傳遞，因此其速度受到進位的傳播延遲，尤其在位元數量增加時，這種延遲會變得更加明顯。

Carry Lookahead Adder（CLA，進位預測加法器）通過預先計算進位的生成和傳播，並將這些信息整合到一個綜合的運算中，以減少進位的傳播延遲。

* 產生carry也就是進位
* 一定必須要任兩個人為1
* 所以要計算carry就是(A * B)+(A * C)+(B * C)
* `* -> AND`
* `+ -> OR`

在Carry Lookahead中，引入了兩個新的術語：

* Generate Carry at Bit i（在位 i 生成進位）
* gi = Ai * Bi
* 如果在位i的A和B都為1，那麼 gi 就會是1。

* Propagate Carry via Bit i（通過位 i 傳播進位）:
* pi = Ai xor Bi
* 如果在位i的A和B中至少有一位為1，那麼 pi 就會是1。

舉例：

* Cin₁ = g0 + (p0 * Cin0)
* 第0個bit的carry out = 第1個bit它的carry in
* g0
* 是第0個bit自己產生出來的，也就是說A0跟B0同時為1，那麼自然而然就一定會有carry out
* (p0 * Cin0)
* 或是A0跟B0它們兩個人至少有一個人為1，且我們的carry in(Cin0)也剛好是1的話，那麼第0個bit一樣也會產生carry out

* Cin₂ = g1 + (P1 * g0) + (P1 * P0 * Cin0)
* 第1個bit它的carry out = 第2個bit它的carry in
* g1
* 是第一個bit自己產生出來的
* (P1 * g0)
* 或是第0個bit自己產生出來了，透過第1個bit把它propagate傳遞出去
* (P1 * P0 * Cin0)
* 或是p1,p0同時都為1，也就是說A1,B1有一個人為1，A0,B0也有一個人為1，在這樣的情況之下假設最前面的Cin0也是1的話
* Cin3 = g2 + (P2 * g1) + (P2 * P1 * g0) + (P2 * P1 * P0 * Cin0)
* Cin4 = g3 + (P3 * g2) + (P3 * P2 * g1) + (P3 * P2 * P1 * g0) + (P3 * P2 * P1 * P0 * Cin0)

* 問題:
* 有注意到方程式的長度越來越長
* 因此不可能一口氣的直接去設計出第31個bit的carry
* 它的效能反而會變得很糟糕
* 解決:
* 用了4個bit讓它變成一組

這4個bit一組
又有不同的組合方式
1. "cascaded carry look-ahead adder"
2. "multiple level carry look-ahead adder"
## cascaded carry look-ahead adder

在這個系統中，有四個 4 位的單元，每個都專門處理 4 位的進位計算。這些單元的目標是計算進位，並且一次只能計算 4 位的進位。

在開始計算之前，系統接收了 propagate（傳遞）、generate（生成） 和Cin（進位輸入） 的值。這些值是計算進位的初始參數。

這個系統是由下往上進行計算的。最底層的 4 位單元先計算，然後傳遞計算結果到上一層。最後，這個過程將一直傳遞到最頂層的單元。

在最頂層的 4 位單元，由於它已經得到了所有底層進位的計算結果，它可以計算最終的 Carry Out ，即第 1 位到第 4 位的進位。

計算完成後，每一個 4 位進位前瞻單元將其計算的進位傳遞到下一級，依此類推。
## multiple level carry lookahead


在multiple level的carry lookahead中，每個區塊內的 Cin 是由前一個區塊的 carry-out 獲得的

最底層處理LSB，而最頂層處理MSB。

每個進位前瞻加法器的計算結果（進位）傳遞到下一個更高層次的加法器，這樣一直到達最頂層。

多層次的進位前瞻允許在不同層次上並行地計算進位，從而提高整體計算效能