올림수 예견

1단계 추상화를 통한 빠른 올림수 : 전송(Propagate)과 생성(Generate)
대부분의 빠른 올림수 구현을 위한 방식은 하드웨어를 단순화시키기 위해 식의 복잡성에 제한을 두면서도 RCA(Ripple Carry Adder)에 비해 속도 향상을 기한다. 그러한 하나의 전략이 바로 올림수 예견 덧셈기(CLA Carry Lookahead Adder)이다. 1장에서 컴퓨터 시스템은 여러 단계의 추상화(abstraction)과정을 통해 복잡성을 크게 줄일 수 있음을 살펴보았다. CLA는 구현에 있어 여러 단계의 추상화에 의존한다.
첫 번째 단계로 원래식을 간략화해 보자.
ci+1=(bi·ci)+(ai·ci)+(ai·bi)
=(ai·bi)+(ai+bi)·ci
이 식을 이용하여 c2를 다시 쓰면, 비슷한 형태로 반복되는 패턴을 구할 수 있다.
c2=(a1·b1)+(a1+b1)·((a0·b0)+(a0+b0)·c0)
위의 식에서 반복되는 (ai·bi)항과 (ai+bi)항을 주목하라. 이 두 가지 중요한 항들은 전통적으로 생성신호, gi(generate)와 전송신호, pi(propagate)라고 부른다.
gi=ai·bi
pi=ai+bi
ci+1을 정의하는 데 이들을 이용하면 다음을 얻을 수 있다.
ci+1=gi+pi·ci
신호들이…(생략)