올림수 예견

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 신호들이 어디에서 이름을 어디에서 되었는지를 보기 위해 gi가 1이라고 가정해 보자. 그러면, ci+1=gi+pi·ci=1+pi·ci=1 즉, 덧셈기가 올림수 입력신호(ci)에 상관없이 올림수 출력신호(ci+1)를 생성한다(generate). 이제 gi가 0이고 pi는 1이라고 가정해 보자. 그러면, ci+1=gi+pi·ci=0+pi·ci=ci 즉, 덧셈기가 올림수 입력을 올림수 출력으로 전송시킨다(propagate). 두 개를 하나로 합침으로써, gi가 1이거나, 또는 pi와 carryIni 둘 다 동시에 1이면 CarryIni+1은 1이 된다.