자리올림수 예측 가산기

위키백과 ― 우리 모두의 백과사전.

자리올림수 예측 가산기는 디지털 논리를 사용한 가산기의 한 종류이다. 그것은 일반적으로 느린 "리플 자리올림수 가산기"와 비교할 수 있다. (리플 자리올림수 가산기를 보세요) 반면에 리플 자리올림수 가산기에서, 가산기의 각 비트는 아래 비트로부터 "자리올림수" 출력을 기다려야 하고, 자리올림수 예측 가산기에서, 모든 자리올림수 출력은 특별한 예측 논리에 의하여 한번에 계산된다. 그 결과는 최상위 비트로 올라가는 "리플" 출력을 기다리는 대신에, 전체 결과는 현저하게 적은 지연으로 계산할 수 있다.

자리올림수 예측 가산기는 2가지 이유로 리플 자리올림수 가산기보다 빠르다. 첫번째, 자리올림수 예측 논리는 많은수의 논리 게이트가 요구된다. 리플 자리올림수 가산기 (와 자리올림수 예측 가산기의 각각 가산기 요소)에서, 각 비트는 일정한 수의 논리 게이트가 요구된다. 만약 n가 가산기의 비트수라면, 논리 게이트의 수는 O(n)이다. 상수에 의하여, 자리올림수 예측 논리는 실행하기 위해서 O( $n 2$ ) 논리 게이트가 필요하다. 사실, 현실은 심지어 이것보다 더 나쁘다. n가 커지게 되면, 더 많은 입력과 논리 게이트 사용이 필요하게 된다. 이렇게 큰 논리 게이트는 더 많은 트랜지스터를 요구하게 되고, 논리 게이트의 수가 O( $n 2$ )라고 할지라도, 트랜지스터의 수는 O( $n 3$ )가 된다. 그러므로, n가 커지는것 처럼, 자리올림수 예측 가산기의 크기는 굉장이 다루기 힘들어 진다. 두번째로, 많은 입력의 논리 게이트는 느려지는 경향이 있다. 게다가, 특정 기술-정해진 문턱의 이상, 더 많은 입력을 지니는 설계된 논리 게이트는 비록 불가능하지 않더라도 비현실적이다. 실행 불가능하게 큰 논리 게이트는 다중 단계로 좌절할 수 있지만, 그결과 자리올림수 예측 논리의 지연은 비트수에 완전히 의존하지 않는다. (비록 이것은 여전히 비트수에서 리플 자리올림수 가산기보다 덜 의존적이다) 맨체스터 자리올림수 회로라고 불리는 계산법은 논리를 공유하여 트랜지스터를 줄여서 사용하는것이 다르다.

요약하여, "순수한" 자리올림수 예측 가산기의 입력에서 비트수가 증가하면 증가되는 비용뿐만 아니라 줄어드는 값도 억제된다. 그결과, 실제로 그것이 큰 가산기에서 자리올림수 예측 가산기와 리플 자리올림수 가산기의 조합을 보는것은 일반적이다. 예시로, 8 비트 가산기는 두개의 4 비트 자리올림수 예측 가산기로부터 리플 자리올림수 설정에 열결하여 만들어 진다. 다른 향상된 기술은, 이진 덧셈에 자리올림수 예측의 자연 확장처럼 보일 수 있고, 큰 결과를 얻기 위해서 작은 가산기 (스스로는 자리올림수 예측 가산기일 것이다)의 출력에 자리올림수 예측 방법을 사용한다. 예시로, 16 비트 가산기는 자리올림수 예측 환경에 연결하여 네개의 4 비트 가산기처럼 계산할 수 있다.

[편집] 자리올림수 예측 방법

자리올림수 예측 논리는 "생성"과 "전달" 자리올림수의 개념을 사용한다. 자리올림수 예측 가산기의 환경에도 불구하고, 이진 덧셋의 환경에 생성과 전달를 생각하는 것이 가장 자연적이며, 그러한 개념은 이것보다 더 일반적으로 사용할 수 있다. 아래의 설명에서 "숫자" 용어는 이진 덧셈을 가르킬때 "비트"로 대체 할 수 있다.

두개의 1 숫자 입력 A과 B의 덧셈은 "생성한다"라고 말한다. 만약 덧셈이 항상 자리올림수가 있다면, 입력 자리올림수 (동일하게, 덧셈 자리올림수에서 어떤 하위 숫자라던지 고려되지 않음)와 상관없다. 예시로, 십진수 덧셈 52 + 67에서, 십진 숫자 5와 6의 덧셈은 "생성한다". 왜냐하면 하나의 숫자 자리올림수에 관계없이 결과는 수백 숫자의 자리올림수이기 때문이다. (예시로, 하나의 숫자는 확실히 자리올림수가 아니다.)

이진 덧셋의 경우에, $A + B$ 은 만약 A과 B의 모두가 1인 경우에만 생성한다. 만약 우리가 나타내는것을 $G (A, B)$ 로 적고 이진이 만약 $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 각각의 전달되고 생성된 비트 $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$ )사이에 진리표에서 다른점은 $A$ 과 $B$ 가 1일때 이다. 그러나, 만약 $A$ 과 $B$ 가 1이면, $G 0$ 항은 (그것의 방정식은 $A \cdot B$ 이기 때문에) 1이고, $P_0 \cdot C_0$ 항은 무의미해 진다. 배타적 논리합 (XOR)은 기본적인 전가산기 회로내에 일반적으로 사용된다; 논리합 (OR)은 (자리올림수 예측에서만) 트랜지스터 갯수값을 줄이는 대체 조건이다.

4 비트 자리올림수 예측 가산기는 높은수준 CLA 논리 회로에 전달하고 생성하는 신호를 만드는 각각 CLA 논리 회로를 내재함으로써 높은수준 회로를 사용할 수 있다. 4 비트 자리올림수 예측 가산기에서 전달된 그룹 ( $P G$ )과 생성된 그룹 ( $G G$ )은 다음과 같다:

$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의 시간에 시작:

</math>와 $G i$ 의 계산은 시간 1에 끝난다
$C i$ 의 계산은 시간 3에 끝난다
$P G$ 의 계산은 시간 2에 끝난다
$G G$ 의 계산은 시간 3에 끝난다
자리올림수 예측 가산기에서 예측 자리올림수 장치로부터 입력의 계산은 다음 시간에 완료된다.
- 첫번째 자리올림수 예측 가산기에서 시간 1이다
- 두번째 자리올림수 예측 가산기에서 시간 4이다
- 세번째와 네번째 자리올림수 예측 가산기에서 시간 4이다
S_i의 계산은 다음 시간에 완료된다
- 첫번째 자리올림수 예측 가산기에서 시간 4이다
- 두번째 자리올림수 예측 가산기에서 기산 7이다
- 세번째와 네번째 자리올림수 예측 가산기에서 시간 8이다
마지막 자리올림 비트 ( $C 16$ )의 계산은 시간 5에 끝난다

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

[편집] 맨체스터 자리올림수 회로

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

[편집] 같이 보기

[편집] 바깥 고리

((영어)) 산술 모듈의 하드웨어 알고리즘, ARITH 연구 그룹, 아오키 실험실, 토호쿠 대학교

원본 주소 ‘http://ko.wikipedia.org../../../%EC%9E%90/%EB%A6%AC/%EC%98%AC/%EC%9E%90%EB%A6%AC%EC%98%AC%EB%A6%BC%EC%88%98_%EC%98%88%EC%B8%A1_%EA%B0%80%EC%82%B0%EA%B8%B0.html’

분류: 출처 없는 문장이 포함된 문서 | 컴퓨터 산술 | 디지털 회로