자리올림수 예측 가산기

자리올림수 예측 가산기(carry-lookahead adder, CLA)는 디지털 논리에서 사용되는 가산기의 한 종류이다. 자리올림수 예측 가산기는 간단하면서도 속도가 느린 "리플 자리올림수 가산기"와 비교할 수 있다. 리플 자리올림수 가산기에서 가산기의 각 비트는 아래 비트로부터 "자리올림수" 출력을 기다려야 하는 반면에, 자리올림수 예측 가산기에서 모든 자리올림수 출력은 특별한 예측 논리에 따라 한 번에 계산된다. 그 결과는 최상위 비트로 올라가는 "리플" 출력을 기다려야 하는 대신에, 전체 결과는 현저하게 적은 지연으로 계산할 수 있다. 헷 자리올림수 예측 가산기는 두 가지 이유에서 리플 자리올림수 가산기보다 빠르다. 첫 번째, 리플 자리올림수 가산기는 많은 수의 논리 게이트가 요구된다. 자리올림수 예측 논리에서, 각 비트는 일정한 수의 논리 게이트가 요구된다. 만약 n이 가산기의 비트 수라면, 논리 게이트의 수는 O(n)이다. 반면에, 리플 자리올림수 가산기(와 자리올림수 예측 가산기의 각각 가산기 요소)는 구현하기 위해서 O($n^{2}$) 논리 게이트가 필요하다. 사실, 현실은 심지어 이것보다 더 나쁘다. n이 커지게 되면, 더 많은 입력과 논리 게이트 사용이 필요하게 된다. 이렇게 큰 논리 게이트는 더 많은 트랜지스터가 필요하게 되고, 논리 게이트의 수가 O($n^{2}$)라고 할지라도, 트랜지스터의 수는 O($n^{3}$)가 된다. 그러므로 n이 커질수록, 리플 자리올림수 가산기의 크기는 굉장히 다루기 힘들어진다. 두 번째로, 많은 입력을 가진 논리 게이트는 느려지는 경향이 있다. 게다가 특정 기술의 한계치 이상으로, 더 많은 입력을 지니는 논리 게이트는 비록 불가능하지 않더라도 비현실적이다. 실행이 불가능할 정도로 큰 논리 게이트는 여러 단계로 구분할 수 있지만, 그 결과 자리올림수 예측 논리의 지연은 비트 수에 완전히 독립적이지 않다.(비록 이것은 여전히 비트 수에서 리플 자리올림수 가산기보다 덜 의존적이다) 맨체스터 자리올림수 회로라고 불리는 계산법은 트랜지스터 수를 줄이기 위해 논리를 공유하여 사용하는 것이 다르다.

요컨대, "순수한" 자리올림수 예측 가산기의 입력에서 비트 수가 증가하면 결과도 줄어들 뿐만 아니라 비용도 증가한다. 그 결과, 실제로 큰 가산기에서 자리올림수 예측 가산기와 리플 자리올림수 기술을 결합하여 사용하는 사례는 드물지 않다. 예시로, 8비트 가산기는 두 개의 4비트 자리올림수 예측 가산기로부터 리플 자리올림수 환경에 연결하여 만들 수도 있다. 이진 덧셈용 자리올림수 예측의 자연 확장처럼 보일 수 있는 다른 진보한 기술은 큰 결과를 얻기 위해서 작은 가산기(그 자체는 자리올림수 예측 가산기일 것이다)의 출력에 자리올림수 예측 방법을 사용한다. 예를 들어, 16비트 가산기는 자리올림수 예측 환경에 연결하여 네 개의 4비트 가산기처럼 구현할 수 있다.

요약

자리올림수 예측 가산기(Carry look Ahead Full Adder)는 각 자리에서 자리올림에 대한 연산을 수행하고, 본 함수부에서 수학적인 분석을 통해 기존 자리의 연산을 기다리지 않고 즉시 단번에 계산을 이끌어 낼 수 있도록 한다.

A/B의 입력이 들어오는 각 비트에 대해서는 다음의 연산을 수행해 G와 P를 얻어낸다.

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

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

G는 "자리올림수 생성"이라고 불리며, 기존 연산과 관계 없이 '반드시' 자리올림수가 생성됨을 확인하는 출력 값이다. P는 "자리올림수 전달"라고 불리며, 추가적으로 자리올림수가 발생할 가능성을 검사한다.

이렇게 얻어진 G와 P는, 주 함수에서 S와 C를 얻는데 다음의 수식으로 활용된다.

$S_{i}=P_{i}\oplus C_{i}$

$C_{i+1}=G_{i}+\left(P_{i}\cdot C_{i}\right)$

위 수식은 그대로 전개가 가능하기 때문에, 굳이 그 전 자리의 자리올림수가 계산되기를 기다리지 않고 직접 처리함으로써 속도를 올릴 수 있다. 예컨대, 3번째 자리에서의 C는 다음과 같다.

$C_{3}=G_{2}+\left(P_{2}\cdot C_{2}\right)$

위 식을 2번째 자리의 C를 기다리지 않기 위해 다음과 같이 풀어쓸 수 있다.

$C_{3}=G_{2}+\left(P_{2}\cdot \left(G_{1}+\left(P_{1}\cdot C_{1}\right)\right)\right)$

최종적으로 모든 C가 기존의 연산을 기다리지 않고 빠르게 처리될 수 있기 때문에 기존의 전가산기에 비해 대단히 빠른 속도로 구동할 수 있게 된다.

자리올림수 예측 방법

자리올림수 예측 논리는 자리올림수의 "생성"(generate)과 "전달"(propagate) 개념을 사용한다. 자리올림수 예측 가산기의 환경에서 이진 덧셈의 환경의 생성과 전달 개념을 생각하는 것이 가장 자연스러움에도 불구하고, 그러한 개념은 이것보다 더 일반적으로 사용될 수 있다. 아래의 설명에서 "자리"(digit)라는 말은 이진 덧셈을 가리킬 때 "비트"(bit)로 대체할 수 있다.

두 개의 1자리 입력 A와 B의 덧셈은 덧셈이 항상 자리올림수가 발생하면 입력 자리올림수(동일하게, 덧셈 자리올림수의 차상위 숫자일 때도 마찬가지)와 상관 없이 "생성한다"고 한다. 예시로, 십진 덧셈 52 + 67에서, 십의 자리 5와 6은 "생성한다". 왜냐하면 한 자리 자리올림수에 관계 없이 결과는 백의 자리로 자리올림수가 발생하기 때문이다.(이 예시에서 일의 자리는 확실히 자리올림이 발생하지 않는다.)

이진 덧셈의 경우에, $A+B$는 A와 B가 모두 1인 경우에만 생성한다. 만약 $A+B$가 생성할 때 참 값을 갖는 이진 부분을 나타내기 위해 $G(A,B)$를 쓰면, 다음이 된다:

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

두 개의 1자리 입력 A과 B의 덧셈은 덧셈이 입력 자리올림수(동일하게, 덧셈 자리올림수에서 차상위 자리일 때)가 있을 때마다 자리 올림이 발생하면 "전달한다"고 한다. 예를 들어, 십진 덧셈 37 + 62에서 십의 자리 3과 6의 덧셈은 "전달한다". 왜냐하면 결과는 일의 자리에 자리올림이 발생하면 (이 예시에는 존재하지 않음) 백의 자리에 자리올림이 발생하기 때문이다. "전달"과 "생성"은 덧셈에 대해 정의하고 덧셈에서 다른 자리에 의존하지 않는 것에 주의하자.

이진 덧셈의 경우에, $A+B$은 A나 B 중 적어도 하나가 1인 경우에만 전달한다. 참 값을 가진 이진 부분을 나타내기 위해 $P(A,B)$를 쓰거나 $A+B$가 전달할 때, 다음이 된다:

$P(A,B)=A+B$

가끔 "전달한다"의 정의가 약간 다르게 사용된다. 이 정의에 따라 A + B는 입력 자리올림수가 있을 때마다 덧셈은 자리올림이 발생하면, 자리올림수가 없다면 "전달한다"라고 말한다. 입력 자리올림수도 없가 없다면 자리올림도 발생하지 않는다. 비트를 생성하고 전달하는 방식은 자리올림수 예측 논리에 따라 사용되며 어느 정의가 사용되는지는 상관이 없다. 이진 덧셈의 경우에, 이 정의는 다음과 같이 표현한다:

$P^{\prime }(A,B)=A\oplus B$

이진 가산기에서, or는 xor보다 빠르고 실행하는 데 적은 트랜지스터가 필요하므로, $P(A,B)$는 일반적으로 $P^{\prime }(A,B)$ 대신에 사용된다. 그러나 다중 단계 자리올림수 예측 가산기에서 $P^{\prime }(A,B)$를 사용하는 것이 더 간단하다.

이러한 생성과 전달의 개념이 주어졌을 때, 언제 덧셈의 자리는 자리올림이 발생할까? 그것은 덧셈이 생성되거나, 혹은 차상위 비트에 자리올림이 발생하거나, 덧셈이 전달될 때 정확히 자리올림이 발생할 것이다. 숫자 i의 자리올림수 비트 $C_{i}$, 자리의 자리올림수 비트 i, i의 전달과 생성 비트 각각 $P_{i}$와 $G_{i}$와 함께 불 대수로 표현하면 다음과 같다.

$C_{i+1}=G_{i}+\left(P_{i}\cdot C_{i}\right)$

이론의 증명

약간의 실험을 해보자. 여기에 숫자열이 있다. 최상위 숫자 (가장 왼쪽에 있는 숫자)를 발견하는 데 얼마나 걸리는지 보자.

  3456789876543
+ 6543210123456

최상위 숫자는 9이다. 어떻게 말할 수 있는가? 가장 왼쪽에 있는 숫자를 합하여 볼 수 있다. 3 + 6 = 9. 만약 이 값에 1을 더하면, 최상위 숫자는 1 (9 + 1 = 10)이 될 것이다. 그래서 만약 자리올림수가 있는지 확인하기 위해서 이것의 오른쪽 숫자를 봐야 한다. 아래의 문제를 동일하게 풀어 보자:

  3456789876543
+ 6544210123456

자리올림수가 발생되어 6 + 4를 발견할 것이다. 왼쪽에 있는 이 값의 합이 9라는 것을 알고 있기 때문에, 최상위 숫자는 1이 될 거라는 것을 즉시 알게 된다. 마지막 문제를 다시 한번 풀어 보자: .

  9999919999999
+ 0000090000000

보이는 것처럼, 보이는 두 값의 합이 9(자리올림수가 전달될 것임)이거나, 9(자리올림수가 생성될 것임)보다 큰 합에 따라 최상위 숫자를 빠르게 판별할 수 있다. 이것이 자리올림수 예측 가산기에 바탕이 되는 기본 원리이다.

구현 설명

더해진 이진 수열의 각 비트에서, 자리올림수 예측 논리는 비트 쌍이 자리올림수를 생성할 것인지 전달할 것인지를 판별할 것이다. 이것은 회로가 더해지는 두 개의 숫자를 "미리 처리"하여 먼저 자리올림수를 결정할 수 있게 해준다. 그러면, 실제 덧셈이 수행될 때, 리플 자리올림수 효과(혹은 첫 번째 완전 가산기에서 마지막 완전 가산기로 통과하는 데 걸리는 시간)를 기다리는 지연 시간이 없게 된다. 아래는 경미한 조정을 거쳐 위에서 사용한 4비트 리플 자리올림수 가산기와 결합한 간단한 4비트로 일반화된 자리올림수 예측 회로이다:

4 비트 자리올림수 예측 가산기

4비트보다 큰 모든 회로에서 자리올림수 예측 회로는 매우 복잡하게 된다. 제공된 예시에서, 생성(g)과 전달(p) 값의 논리는 아래와 같이 주어져 있다. 숫자 값은 가장 왼쪽에 있는 0에서 시작해서 가장 오른쪽에 있는 3까지로 위의 회로에서 신호를 판별하는 것에 주의하자:

$C_{1}=G_{0}+P_{0}\cdot C_{0}$

$C_{2}=G_{1}+P_{1}\cdot C_{1}$

$C_{3}=G_{2}+P_{2}\cdot C_{2}$

$C_{4}=G_{3}+P_{3}\cdot C_{3}$

$C_{2}$에 $C_{1}$을 , $C_{3}$에 $C_{2}$를, $C_{4}$에 $C_{3}$을 대치하여 채운 확장 방정식은 다음과 같다:

$C_{1}=G_{0}+P_{0}\cdot C_{0}$

$C_{2}=G_{1}+G_{0}\cdot P_{1}+C_{0}\cdot P_{0}\cdot P_{1}$

$C_{3}=G_{2}+G_{1}\cdot P_{2}+G_{0}\cdot P_{1}\cdot P_{2}+C_{0}\cdot P_{0}\cdot P_{1}\cdot P_{2}$

$C_{4}=G_{3}+G_{2}\cdot P_{3}+G_{1}\cdot P_{2}\cdot P_{3}+G_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3}+C_{0}\cdot P_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3}$

비트 쌍이 자리올림수를 생성하기 위해서는 다음 논리와 같다:

$G_{i}=A_{i}\cdot B_{i}$

비트 쌍이 자리올림수를 전달하기 위해서는 다음 논리와 같다:

$P_{i}=A_{i}\oplus B_{i}$

$P_{i}=A_{i}+B_{i}$

이것이 동작하는 이유는 $C_{1}=G_{0}+P_{0}\cdot C_{0}$의 평가에 근거한다. ($A\oplus B$)와 ($A+B$)사이에 참 테이블(truth table)에서 다른점은 $A$와 $B$가 1일 때이다. 그러나 만약 $A$와 $B$가 둘 다 1이면, $G_{0}$ 항은 (그것의 방정식은 $A\cdot B$이기 때문에) 1이고, $P_{0}\cdot C_{0}$항은 무의미해진다. 배타적 논리합(XOR)은 기본적인 전가산기 회로 내에 일반적으로 사용된다; 논리합(OR)은 (자리올림수 예측에서만) 트랜지스터 개수 항이 더욱 간단한 대체 조건이다.

자리올림수 4비트 예측 가산기는 높은 수준 CLA 논리 회로가 높은 수준의 CLA 회로에 신호를 전달하고 생성도록 만들어 높은 수준 회로를 사용할 수 있다. 4비트 자리올림수 예측 가산기에 전달된 그룹 ($PG$)과 생성된 그룹 ($GG$)은 다음과 같다:

$PG=P_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3}$

$GG=G_{3}+G_{2}\cdot P_{3}+G_{1}\cdot P_{3}\cdot P_{2}+G_{0}\cdot P_{3}\cdot P_{2}\cdot P_{1}$

4개의 4 비트 자리올림수 예측 가산기를 배치하는 것은 한꺼번에 4개의 전달된 그룹과 4개의 생성된 그룹을 산출한다. 예측 자리올림수 장치 (LCU)는 이런 8개의 값을 가지며 자리올림수 예측 가산기에서 $C_{i}$를 계산하기 위해서 동일한 논리를 사용한다. 그때 예측 자리올림수 장치는 4개의 자리올림수 예측 가산기의 각각에서 생성된 자리올림수를 입력하고 15번째는 $C_{16}$과 같다.

(4개의 자리올림수 예측 가산기와 1개의 예측 자리올림수 장치를 사용하여) 추가된 16비트의 게이트 지연의 계산은 리플 자리올림수 가산기처럼 간단하지 않다. 시간 0에 시작한다:

• $P_{i}$와 $G_{i}$의 계산은 시간 1에 끝난다
• $C_{i}$의 계산은 시간 3에 끝난다
• $PG$의 계산은 시간 2에 끝난다
• $GG$의 계산은 시간 3에 끝난다
• 자리올림수 예측 가산기에서 예측 자리올림수 장치로부터 입력의 계산은 다음 시간에 완료된다.
  • 첫 번째 자리올림수 예측 가산기에서 시간 1이다
  • 두 번째 자리올림수 예측 가산기에서 시간 4이다
  • 세 번째와 네 번째 자리올림수 예측 가산기에서 시간 5이다
• $S_{i}$의 계산은 다음 시간에 완료된다
  • 첫 번째 자리올림수 예측 가산기에서 시간 4이다
  • 두 번째 자리올림수 예측 가산기에서 시간 7이다
  • 세 번째와 네 번째 자리올림수 예측 가산기에서 시간 8이다
• 마지막 자리올림수 비트 ($C_{16}$)의 계산은 시간 5에 끝난다

최대 시간은 ($S_{[8-15]}$에서) 8게이트 지연이다. 표준 16비트 리플 자리올림수 가산기는 31게이트 지연이 걸린다.

맨체스터 자리올림수 회로

맨체스터 자리올림수 회로는 트랜지스터 수를 줄이기 위해 공유한 논리를 사용한 자리올림수 예측 가산기의 변종이다. 위의 실행 문단에서 볼 수 있는 것처럼 각각의 자리올림수 생성을 위한 논리는 이전 자리올림수를 생성하는데 사용되는 모든 논리를 포함한다. 맨체스터 자리올림수 회로는 최상위 자리올림수 값을 계산하는 게이트에서 노드를 꺼내 중간 자리올림수를 생성한다. 모든 논리 계열이 이런 내부 노드를 가지고 있는 것은 아니지만, 시모스가 주요 예시이다. 동적 논리는 전달 게이트 논리가 가능한 것처럼, 공유하는 논리를 지원할 수 있다. 맨체스터 자리올림수 회로의 주요한 단점 중 하나는 이런 모든 출력의 용량 부하와 트랜지스터의 저항이 전달 지연을 일반적인 자리올림수 예측보다 더 빠르게 증가시키는 것이다. 맨체스터 자리올림수 부분은 일반적으로 4비트를 초과하지 않는다.

같이 보기

• 전가산기
• 자리올림수 저장 가산기
• 예측 자리올림수 장치

외부 링크

• (영어) 산술 모듈의 하드웨어 알고리즘 Archived 2007년 4월 9일 - 웨이백 머신, ARITH 연구 그룹, 아오키 실험실, 토호쿠 대학교