자리올림수 예측 가산기

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 작동 원리
3. 자리올림수 예측 방법
- 3.1. 자리올림수 예측의 이점
4. 구현
- 4.1. 4비트 자리올림수 예측 가산기
- 4.2. 확장
5. 맨체스터 자리올림수 체인
- 5.1. 특징
- 5.2. 한계
6. 응용
참조

1. 개요

자리올림수 예측 가산기는 덧셈 연산 속도를 향상시키기 위해 사용되는 디지털 회로이다. 이 회로는 자리올림수의 생성과 전달 개념을 사용하여 각 자릿수의 자리올림수를 미리 계산한다. 자리올림수 예측 가산기는 리플 자리올림수 가산기의 지연 문제를 해결하며, 4비트 단위로 묶어 사용하거나, 예측 자리올림수 장치(LCU)를 활용하여 더 큰 비트의 가산기를 구현할 수 있다. 맨체스터 자리올림수 체인은 트랜지스터 수를 줄이기 위한 자리올림수 예측 가산기의 변형으로, 공유된 논리를 사용하지만, 출력의 용량 부하와 저항으로 인해 일반적으로 4비트를 초과하여 사용하지 않는다.

더 읽어볼만한 페이지

디지털 전자공학 - 트랜지스터-트랜지스터 논리
트랜지스터-트랜지스터 논리(TTL)는 1961년 제임스 L. 부이에 의해 발명된 바이폴라 접합 트랜지스터 기반의 디지털 회로 기술로, 텍사스 인스트루먼츠의 7400 시리즈를 통해 널리 사용되었으며, 저렴한 비용으로 디지털 기술 발전에 기여했다.
디지털 전자공학 - 플립플롭
플립플롭은 1비트 이상의 정보를 저장하는 디지털 논리 회로로, 에클스-조던 트리거 회로에서 기원하여 SR, D, T, JK 등 다양한 유형으로 구현되며, 컴퓨터 기억 장치의 기본 구성 요소로 사용되지만 타이밍 요소에 민감하게 설계해야 한다.
컴퓨터 산술 - IEEE 754
IEEE 754는 부동소수점 숫자를 표현하고 처리하기 위한 국제 표준으로, 다양한 형식과 연산, 반올림 규칙, 예외 처리 등을 정의한다.
컴퓨터 산술 - 1의 보수
1의 보수는 이진수에서 양수는 일반적인 이진수로, 음수는 양수의 각 비트를 반전시켜 표현하며, 덧셈 시 자리올림수가 발생하면 결과값에 더해야 하고, 0을 중복 표현하는 단점으로 현대에는 2의 보수가 주로 사용된다.

자리올림수 예측 가산기

2. 작동 원리

자리올림수 예측 논리는 자리올림수의 "생성"(generate)과 "전달"(propagate) 개념을 사용한다. 이 개념은 이진 덧셈뿐 아니라 더 일반적인 경우에도 적용될 수 있다. 아래 설명에서 "자리"는 이진 덧셈에서 "비트"로 대체될 수 있다.

두 개의 1자리 입력 A와 B의 덧셈에서, 덧셈 결과 항상 자리올림수가 발생하면 입력 자리올림수와 상관없이 "생성한다"고 한다. 예를 들어, 십진 덧셈 52 + 67에서 십의 자리 5와 6은 한 자리 자리올림수에 관계없이 항상 백의 자리로 자리올림수를 발생시키므로 "생성한다". 이진 덧셈의 경우, A와 B가 모두 1일 때만 생성한다. 이를 수식으로 표현하면 다음과 같다.

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

반면, 덧셈이 입력 자리올림수가 있을 때마다 자리올림이 발생하면 "전달한다"고 한다. 예를 들어, 십진 덧셈 37 + 62에서 십의 자리 3과 6은 일의 자리에 자리올림이 발생하면 백의 자리로 자리올림이 발생하므로 "전달한다". 이진 덧셈에서는 A나 B 중 적어도 하나가 1인 경우에 전달한다. 이를 수식으로 표현하면 다음과 같다.

: $P(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$ 는 다음과 같이 표현할 수 있다.

: $C_{i+1} = G_i + \left( P_i \cdot C_i \right)$

여기서 $G_i$ 는 자리 i의 생성 비트, $P_i$ 는 자리 i의 전달 비트이다. 즉, 덧셈이 생성되거나 ( $G_i$ ), 이전 자리에서 자리올림이 발생하고 현재 자리가 전달될 때 ( $P_i \cdot C_i$ ) 자리올림이 발생한다.

2. 1. 자리올림수 생성 (Carry Generate, G)

2. 2. 자리올림수 전달 (Carry Propagate, P)

2. 3. 자리올림수 예측 (Carry Lookahead)

자리올림수 예측 논리는 각 자릿수의 자리올림수(C)를 계산하기 위해 G와 P를 사용하며, 이 계산식은

C_{i+1} = G_i + (P_i \cdot C_i)

이다. 이 식을 전개하면 이전 자리의 자리올림수 계산을 기다리지 않고 현재 자리의 자리올림수를 바로 계산할 수 있다.

캐리-룩어헤드 방식은 각 자리수 위치에 대해 오른쪽에서 캐리가 들어올 경우 해당 위치가 캐리를 전달할지 여부를 계산하고, 이 계산된 값을 결합하여 각 자릿수 그룹에 대해 해당 그룹이 오른쪽에서 들어오는 캐리를 전달할지 여부를 빠르게 추론한다.

4개의 자릿수 그룹을 선택했다고 가정하면, 모든 1비트 덧셈기가 결과를 계산하는 동시에 룩어헤드 유닛이 계산을 수행한다. 특정 그룹에서 캐리가 발생하면, 최대 5개의 게이트 지연 내에 그룹의 왼쪽 끝에서 나타나 왼쪽으로 전파된다. 이 캐리가 다음 그룹 전체를 통과하여 전파될 경우, 룩어헤드 유닛은 이미 이를 추론했을 것이고, 룩어헤드 유닛은 즉시 다음 왼쪽 그룹에 캐리를 수신할 것이라고 알릴 수 있으며, 동시에 다음 룩어헤드 유닛에 캐리가 오는 중이라고 알릴 수 있다.

결과적으로 캐리는 리플 캐리 시스템에서와 같이 각 4비트 그룹을 통해 천천히 전파되기 시작하지만, 룩어헤드-캐리 유닛 간을 건너뛰어 4배 더 빠르게 이동한다. 마지막으로, 캐리를 수신하는 각 그룹 내에서 캐리는 해당 그룹의 자릿수 내에서 천천히 전파된다.

그룹의 비트 수가 많을수록 룩어헤드 캐리 로직은 더 복잡해지고, 그룹 간의 "고속 도로"가 아닌 각 그룹의 "저속 도로"에서 더 많은 시간이 소요된다. 반면에 그룹의 비트 수가 적을수록 한 숫자의 끝에서 다른 끝까지 도달하기 위해 더 많은 그룹을 통과해야 하며, 그 결과 가속이 덜 얻어진다.

둘 이상의 룩어헤드-캐리 로직 수준을 가질 수 있으며, 실제로 이 방식으로 수행된다. 각 룩어헤드-캐리 유닛은 "오른쪽에서 캐리가 들어오면 왼쪽으로 전달합니다"라는 신호를 생성하며, 이러한 신호를 결합하여 슈퍼그룹을 만들수 있다. "슈퍼그룹" 룩어헤드-캐리 로직은 슈퍼그룹에 들어가는 캐리가 전체를 통해 전파될지 여부를 말할 수 있으며, 이 정보를 사용하여 단순한 리플 캐리보다 16배 더 빠르게 오른쪽에서 왼쪽으로 캐리를 전파할 수 있다.

매우 큰 숫자의 경우, 슈퍼그룹과 수퍼슈퍼그룹의 레이어를 필요에 따라 추가할 수 있으므로 룩어헤드-캐리 로직이 더 복잡해지지 않는다.

3. 자리올림수 예측 방법

자리올림수 예측 논리는 자리올림수의 "생성"(generate)과 "전달"(propagate) 개념을 사용한다. 이 개념은 이진 덧셈뿐만 아니라 더 일반적인 경우에도 적용될 수 있다. 아래 설명에서 "자리"는 이진 덧셈을 가리킬 때 "비트"로 대체될 수 있다.

두 개의 1자리 입력 A와 B의 덧셈에서, 덧셈 결과 항상 자리올림수가 발생하면 "생성한다"고 한다. 예를 들어, 십진 덧셈 52 + 67에서 십의 자리 5와 6은 일의 자리의 자리올림 여부와 관계없이 항상 백의 자리로 자리올림수를 생성하므로 "생성한다". 이진 덧셈의 경우, A와 B가 모두 1일 때만 생성한다. 이를 수식으로 표현하면 다음과 같다:

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

여기서 $A \cdot B$ 는 AND 연산이다.

반면, 덧셈이 입력 자리올림수가 있을 때마다 자리올림이 발생하면 "전달한다"고 한다. 예를 들어, 십진 덧셈 37 + 62에서 십의 자리 3과 6은 일의 자리에 자리올림이 발생하면 백의 자리로 자리올림을 전달하므로 "전달한다". 이진 덧셈에서는 A나 B 중 적어도 하나가 1인 경우에 전달한다. 이를 수식으로 표현하면 다음과 같다:

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

여기서 $A + B$ 는 OR 연산이다.

"전달한다"는 개념은 다른 정의로 사용될 수 있다. 입력 자리올림수가 있을 때 덧셈이 자리올림을 발생시키고, 입력 자리올림수가 없을 때는 자리올림을 발생시키지 않는 경우를 "전달한다"고 정의할 수 있다. 이진 덧셈에서 이 정의는 다음과 같이 표현된다:

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

여기서 $A \oplus B$ 는 XOR 연산이다.

어떤 정의를 사용하든, 자리올림수 예측 논리에서 생성 및 전달 비트가 사용되는 방식은 동일하다.

'''자리올림이 전파되거나 생성되는 ''때''를 보여주는 표.'''

$A$	$B$	$C_i$	$C_o$	자리올림 유형
0	0	0	0	없음
0	0	1	0	없음
0	1	0	0	없음
0	1	1	1	전파
1	0	0	0	없음
1	0	1	1	전파
1	1	0	1	생성
1	1	1	1	생성/전파

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

숫자 i의 자리올림수 비트 $C_i$ 는 덧셈이 생성되거나, 차상위 비트에 자리올림이 발생하고 덧셈이 전달될 때 발생한다. 이를 불 대수로 표현하면 다음과 같다.

: $C_{i+1} = G_i + \left( P_i \cdot C_i \right)$

3. 1. 자리올림수 예측의 이점

4. 구현

더해진 이진 수열의 각 비트에서, 자리올림수 예측 논리는 비트 쌍이 자리올림수를 생성할 것인지 전달할 것인지를 판별한다. 이것은 회로가 더해지는 두 개의 숫자를 "미리 처리"하여 먼저 자리올림수를 결정할 수 있게 해준다. 그러면, 실제 덧셈이 수행될 때, 리플 자리올림수 효과를 기다리는 지연 시간이 없게 된다.

비트 쌍이 자리올림수를 생성하는지 판별하는 논리는 다음과 같다:

: $G_i = A_i \cdot B_i$

비트 쌍이 자리올림수를 전달하는지 판별하는 논리는 다음과 같다:

: $P_i = A_i \oplus B_i$

또는

: $P_i = A_i + B_i$

$A \oplus B$ 와 $A + B$ 사이의 진리표에서 다른 점은 $A$ 와 $B$ 가 모두 1일 때이다. $A$ 와 $B$ 가 모두 1이면, $G_0$ 항은 1이 되고, $P_0 \cdot C_0$ 항은 무의미해진다. 배타적 논리합(XOR)은 전가산기 회로에 사용되며, 논리합(OR)은 트랜지스터 개수 항이 더욱 간단한 대체 조건이다.

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$

자리올림수 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개의 CLA와 1개의 LCU를 사용하는 16비트 가산기의 게이트 지연 계산은 다음과 같다.

시간 0에 시작한다:

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

최대 시간은 (

S_{[8-15]}

에서) 8게이트 지연이다. 표준 16비트 리플 자리올림수 가산기는 31게이트 지연이 걸린다.

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

4. 2. 확장

여러 개의 4비트 자리올림수 예측 가산기를 연결하여 더 큰 비트의 가산기를 구현할 수 있다. 예를 들어, 16비트 가산기는 4개의 4비트 자리올림수 예측 가산기를 연결하여 만들 수 있다. 이 때, 각 4비트 가산기의 자리올림 출력(Cout)은 다음 가산기의 자리올림 입력(Cin)으로 연결된다.

더 큰 가산기를 만들 때, 자리올림수 전달 지연을 줄이기 위해 예측 자리올림수 장치(Lookahead Carry Unit, LCU)를 추가로 사용하기도 한다. LCU는 여러 가산기 블록의 자리올림수를 예측하고 관리하여 전체 덧셈 속도를 향상시킨다.

5. 맨체스터 자리올림수 체인

맨체스터 자리올림수 회로는 트랜지스터 수를 줄이기 위해 공유한 논리를 사용한 자리올림수 예측 가산기의 변종이다. 위의 실행 문단에서 볼 수 있는 것처럼 각각의 자리올림수 생성을 위한 논리는 이전 자리올림수를 생성하는데 사용되는 모든 논리를 포함한다. 맨체스터 자리올림수 회로는 최상위 자리올림수 값을 계산하는 게이트에서 노드를 꺼내 중간 자리올림수를 생성한다.

모든 논리 계열이 이런 내부 노드를 가지고 있는 것은 아니지만, 시모스가 주요 예시이다. 동적 논리는 전달 게이트 논리가 가능한 것처럼, 공유하는 논리를 지원할 수 있다. 맨체스터 자리올림수 회로의 주요한 단점 중 하나는 이런 모든 출력의 용량 부하와 트랜지스터의 저항이 전달 지연을 일반적인 자리올림수 예측보다 더 빠르게 증가시키는 것이다. 맨체스터 자리올림수 부분은 일반적으로 4비트를 초과하지 않는다.

5. 1. 특징

맨체스터 캐리 체인은 트랜지스터 수를 줄이기 위해 공유 논리를 사용하는 캐리-룩어헤드 가산기의 변형이다. 각 캐리를 생성하는 논리에는 이전 캐리를 생성하는 데 사용된 모든 논리가 포함되어 있다. 맨체스터 캐리 체인은 가장 중요한 캐리 값을 계산하는 게이트의 노드를 탭하여 중간 캐리를 생성한다.

동적 논리는 공유 논리를 지원할 수 있으며, 전송 게이트 논리도 마찬가지이다. 맨체스터 캐리 체인의 주요 단점 중 하나는 이러한 모든 출력의 정전 용량 부하가 트랜지스터의 저항과 함께 일반적인 캐리 룩어헤드보다 훨씬 빠르게 전파 지연을 증가시킨다는 것이다. 맨체스터 캐리 체인 섹션은 일반적으로 4비트를 초과하지 않는다.

5. 2. 한계

맨체스터 캐리 체인은 논리 회로군에서 트랜지스터 수를 줄이기 위해 공유 논리를 사용하는 자리올림수 예측 가산기의 변형이다. 그러나 모든 논리 회로가 이러한 내부 노드를 갖는 것은 아니며, CMOS가 대표적인 예이다. 동적 논리는 공유 논리를 지원할 수 있으며, 전송 게이트 논리 또한 지원 가능하다.

맨체스터 캐리 체인의 주요 단점은 출력의 정전 용량 부하와 트랜지스터의 저항으로 인해, 일반적인 자리올림수 예측보다 전파 지연이 훨씬 빠르게 증가한다는 것이다. 따라서 맨체스터 캐리 체인 섹션은 일반적으로 4비트를 초과하지 않는다.

6. 응용

참조

_[1] 웹사이트 Analytical Engine – History of Charles Babbage Analytical Engine https://history-comp[...] 2021-06-19
_[2] 논문 The Z1: Architecture and Algorithms of Konrad Zuse's First Computer 2014-06-07

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com