10. 자리올림수 예측 가산기 (Carry look Ahead Full Adder)

전가산기를 이용한 이진수의 덧셈 연산의 경우, 앞 비트의 전가산기 연산이 끝나 Carry가 얻어지기 전에는 다음 비트의 계산을 수행할 수 없어, 숫자가 커질수록 연산에 시간이 많이 소요되는 단점이 있다.

이를 해결하기 위해 모든 자리의 덧셈을 한번에 할 수 있도록 한 것이 자리올림수 예측 계산기이다.

입력 A/B에 대하여 자리올림수 예측 가산기는 다음의 연산을 수행해 G와 P를 구한다.

$$ G(A,B) = A\cdot B \\
P(A,B) = A\oplus B $$

G는 자리올림수 생성^generation이라 불리며, 기존의 연산과 관계 없이 반드시 carry가 생기는 경우, A와 B가 모두 1인 경우를 확인한다.

P는 자리올림수 전파^propagation라 불리며, 추가로 carry가 생길 경우를 검사한다. (A+B의 결과가 1이라, 이전 비트의 carry와 조합하여 새로운 carry를 만드는 경우)

G와 P를 활용하여, 가산기의 Sum과 Carry를 아래와 같이 구할 수 있다.

$$ S_i = P_i \oplus C_i \\
C_{i+1} = G_i + P_i  C_i $$

위의 C에 대한 식을 전개하면 아래와 같다.

$$\begin{align*} C_3 &= G_2 + P_2C_2 \\
&= G_2 + P_2 \cdot (G_1 + P_1C_1) \end{align*}$$

결과적으로 모든 carry가 위와 같이 기존 연산에 구애받지 않고 처리되기 때문에 전가산기에 비해 빠르게 연산을 수행할 수 있다.