자리올림수 저장 가산기
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
자리올림수 저장 가산기는 덧셈 연산의 속도를 향상시키기 위해 자리올림수를 별도로 저장하는 방식의 가산기이다. 존 폰 노이만의 아이디어로, 각 자릿수의 덧셈 결과를 즉시 계산하고 자리올림수는 별도로 저장하여 병렬 처리를 가능하게 한다. 전가산기를 사용하여 구현되며, 덧셈 결과가 특정 값보다 큰지 작은지 즉시 알 수 없는 단점이 있다. 몽고메리 곱셈 등에서 활용되며, 자리올림수 전파 지연 감소, 병렬 처리 용이성, 클럭 주파수 증가 등의 장점을 가진다.
더 읽어볼만한 페이지
- 디지털 전자공학 - 트랜지스터-트랜지스터 논리
트랜지스터-트랜지스터 논리(TTL)는 1961년 제임스 L. 부이에 의해 발명된 바이폴라 접합 트랜지스터 기반의 디지털 회로 기술로, 텍사스 인스트루먼츠의 7400 시리즈를 통해 널리 사용되었으며, 저렴한 비용으로 디지털 기술 발전에 기여했다. - 디지털 전자공학 - 플립플롭
플립플롭은 1비트 이상의 정보를 저장하는 디지털 논리 회로로, 에클스-조던 트리거 회로에서 기원하여 SR, D, T, JK 등 다양한 유형으로 구현되며, 컴퓨터 기억 장치의 기본 구성 요소로 사용되지만 타이밍 요소에 민감하게 설계해야 한다. - 컴퓨터 산술 - IEEE 754
IEEE 754는 부동소수점 숫자를 표현하고 처리하기 위한 국제 표준으로, 다양한 형식과 연산, 반올림 규칙, 예외 처리 등을 정의한다. - 컴퓨터 산술 - 1의 보수
1의 보수는 이진수에서 양수는 일반적인 이진수로, 음수는 양수의 각 비트를 반전시켜 표현하며, 덧셈 시 자리올림수가 발생하면 결과값에 더해야 하고, 0을 중복 표현하는 단점으로 현대에는 2의 보수가 주로 사용된다.
| 자리올림수 저장 가산기 | |
|---|---|
| 개요 | |
| 종류 | 디지털 가산기 |
| 작동 방식 | 부분합 및 자리올림수를 별도로 저장하여 덧셈을 수행 |
| 특징 | 빠른 덧셈 속도, 복잡한 회로 구조 |
| 구조 및 작동 원리 | |
| 구성 요소 | 전가산기 (Full Adder) 또는 반가산기 (Half Adder) |
| 작동 원리 | 각 자리의 부분합과 자리올림수를 계산 자리올림수를 다음 자리로 즉시 전달하지 않고 저장 저장된 자리올림수를 사용하여 최종 합을 계산 |
| 장점 | 자리올림수 전달 지연 감소, 빠른 덧셈 연산 |
| 단점 | 자리올림수 저장을 위한 추가 회로 필요, 복잡한 구조 |
| 활용 | |
| 주요 응용 분야 | 곱셈기, 디지털 신호 처리, 고성능 연산 장치 |
| 곱셈 연산 | 부분곱을 더하는 과정에서 효율적인 덧셈 수행 |
| 디지털 신호 처리 | 필터, 상관 관계 계산 등 복잡한 연산에 사용 |
| 기타 | |
| Earle의 래치 캐리-세이브 가산기 | 1965년 J. Earle이 고안한 래치 캐리-세이브 가산기 |
2. 역사
자리올림수 저장 가산기는 존 폰 노이만의 아이디어로, 덧셈 연산 시 자리올림수를 즉시 계산하지 않고 별도로 저장하여 연산 속도를 높이는 방식이다.3. 작동 원리
== 작동 원리 ==
자리올림수 저장 가산기의 기본 작동 원리는 다음과 같다.
세 개의 숫자를 더할 때, 처음 두 숫자를 더하여 합과 자리올림수를 생성한 다음, 그 합과 자리올림수를 세 번째 숫자에 더하여 합과 자리올림수를 생성할 수 있다. 이진법에서는 숫자가 0과 1뿐이므로 0 + 0 = 0, 0 + 1 = 1이며, 1 + 1 = 0이며 1의 자리올림수가 발생한다. 자리올림 비트를 더하면 최대 1 + 1 + 1 = 1이며 1의 자리올림수가 발생하므로 세 숫자 덧셈이 가능하다.
3개의 긴 이진수를 더하는 예시는 다음과 같다.
1011 1010 1010 1101 1111 0000 0000 1101 (a)
+1101 1110 1010 1101 1011 1110 1110 1111 (b)
+0001 0010 1011 0111 0101 0011 0101 0010 (c)
일반적인 방법은 먼저 (a+b)를 계산한 다음, ((a+b)+c)를 계산하는 것이다. 하지만 자리올림수 저장 산술은 각 자릿수를 더하여 합을 계산하고 자리올림수 전파를 포기한다.
1011 1010 1010 1101 1111 0000 0000 1101 (a)
+1101 1110 1010 1101 1011 1110 1110 1111 (b)
+0001 0010 1011 0111 0101 0011 0101 0010 (c)
=2113 2130 3031 2313 2223 1121 1211 2222
결과는 두 개의 이진수 합으로 표시된다. 첫 번째 숫자 S는 각 숫자를 더하여 얻은 합(자리올림수 전파 없이) 즉 Si = ai ⊕ bi ⊕ ci이며, 두 번째 숫자 C는 이전 개별 합으로부터의 자리올림수로 구성된다. 즉, Ci+1 = (aibi) + (bici) + (ciai) :
0111 0110 1011 0111 0001 1101 1011 0000
1 0011 0101 0101 1011 1110 0100 1001 1110
이 두 숫자를 자리올림수 전파 가산기로 보내면 최종 결과가 출력된다.
이 방식은 일반적인 덧셈 방식보다 속도가 빠르다. 일반적인 방법으로 3개의 숫자를 더하려면 2번의 자리올림수 전파 가산기 지연이 필요하지만, 자리올림수 저장 기술을 사용하면 1번의 자리올림수 전파 가산기 지연과 1번의 전가산기 지연만 필요하다.
=== 전가산기 (Full Adder) ===
자리올림수 저장 가산기는 여러 개의 전가산기로 구성된다. 각 전가산기는 3개의 입력 비트(더해지는 두 수의 해당 자릿수 비트와 이전 자릿수로부터의 자리올림수)를 받아, 합(sum)과 자리올림수(carry) 비트를 출력한다. 출력된 합 비트는 해당 자릿수의 부분합을 나타내며, 자리올림수 비트는 다음 자릿수로 전달된다.
3개의 ''n'' 비트 숫자 '''a''', '''b''', '''c'''가 주어지면, 부분합 '''ps'''와 시프트 자리올림 '''sc'''을 생성한다.
:
:
전체 합은 다음을 통해 계산할 수 있다.
# 자리올림 시퀀스 '''sc'''을 한 자리 왼쪽으로 시프트한다.
# 부분합 시퀀스 '''ps'''의 앞에 0을 추가(최상위 비트).
# 리플 캐리 가산기를 사용하여 이 두 값을 더하여 결과(''n'' + 1)비트 값을 생성한다.
3개 이상의 수를 더할 때, 자리올림수 저장 가산기 다음에 자리올림 전파 가산기를 사용하는 방법은 자리올림 전파 가산기 두 개를 사용하는 방법보다 빠르다. 자리올림 전파 가산기에서는 이전 자리올림 비트가 생성될 때까지 합 비트를 계산할 수 없어 지연이 발생하기 때문이다.
3. 1. 기본 개념
자리올림수 저장 가산기는 덧셈 연산 시 각 자릿수의 합과 자리올림수를 분리하여 계산하는 방식이다. 십진법에서 12345678 + 87654322를 계산할 때, 합은 21132130, 자리올림수는 876543210으로 계산된다. 이진법에서도 마찬가지로, 1011 + 1101 + 0001을 계산하면 합은 0111, 자리올림수는 10010으로 계산된다. 이처럼 합과 자리올림수를 별도의 숫자로 취급하여 이후 덧셈에 활용한다.
자리올림수를 저장하는 아이디어는 존 폰 노이만의 아이디어이다. 두 숫자의 합은 최대 1의 자리올림수를 가질 수 있으며, 두 숫자와 1을 더한 값 역시 최대 1의 자리올림수를 가질 수 있다. 예를 들어 십진법에서 9 + 9 = 18은 1의 자리올림수를 가지며, 9 + 9 + 1 = 19 역시 1의 자리올림수를 가진다.
세 개의 숫자를 더할 때, 처음 두 숫자를 더하여 합과 자리올림수를 생성한 다음, 그 합과 자리올림수를 세 번째 숫자에 더하여 합과 자리올림수를 생성할 수 있다. 이진법에서는 숫자가 0과 1뿐이므로 0 + 0 = 0, 0 + 1 = 1이며, 1 + 1 = 0이며 1의 자리올림수가 발생한다. 자리올림 비트를 더하면 최대 1 + 1 + 1 = 1이며 1의 자리올림수가 발생하므로 세 숫자 덧셈이 가능하다.
3개의 긴 이진수를 더하는 예시는 다음과 같다.
1011 1010 1010 1101 1111 0000 0000 1101 (a)
+ 1101 1110 1010 1101 1011 1110 1110 1111 (b)
+ 0001 0010 1011 0111 0101 0011 0101 0010 (c)
일반적인 방법은 먼저 (a+b)를 계산한 다음, ((a+b)+c)를 계산하는 것이다. 하지만 자리올림수 저장 산술은 각 자릿수를 더하여 합을 계산하고 자리올림수 전파를 포기한다.
1011 1010 1010 1101 1111 0000 0000 1101 (a)
+ 1101 1110 1010 1101 1011 1110 1110 1111 (b)
+ 0001 0010 1011 0111 0101 0011 0101 0010 (c)
= 2113 2130 3031 2313 2223 1121 1211 2222
결과는 두 개의 이진수 합으로 표시된다. 첫 번째 숫자 S는 각 숫자를 더하여 얻은 합(자리올림수 전파 없이) 즉 Si = ai ⊕ bi ⊕ ci이며, 두 번째 숫자 C는 이전 개별 합으로부터의 자리올림수로 구성된다. 즉, Ci+1 = (aibi) + (bici) + (ciai) :
0111 0110 1011 0111 0001 1101 1011 0000 and
1 0011 0101 0101 1011 1110 0100 1001 1110
이 두 숫자를 자리올림수 전파 가산기로 보내면 최종 결과가 출력된다.
이 방식은 일반적인 덧셈 방식보다 속도가 빠르다. 일반적인 방법으로 3개의 숫자를 더하려면 2번의 자리올림수 전파 가산기 지연이 필요하지만, 자리올림수 저장 기술을 사용하면 1번의 자리올림수 전파 가산기 지연과 1번의 전가산기 지연만 필요하다.
3. 2. 전가산기 (Full Adder)
자리올림수 저장 가산기는 여러 개의 전가산기로 구성된다. 각 전가산기는 3개의 입력 비트(더해지는 두 수의 해당 자릿수 비트와 이전 자릿수로부터의 자리올림수)를 받아, 합(sum)과 자리올림수(carry) 비트를 출력한다. 출력된 합 비트는 해당 자릿수의 부분합을 나타내며, 자리올림수 비트는 다음 자릿수로 전달된다.
3개의 ''n'' 비트 숫자 '''a''', '''b''', '''c'''가 주어지면, 부분합 '''ps'''와 시프트 자리올림 '''sc'''을 생성한다.
:
:
전체 합은 다음을 통해 계산할 수 있다.
# 자리올림 시퀀스 '''sc'''을 한 자리 왼쪽으로 시프트한다.
# 부분합 시퀀스 '''ps'''의 앞에 0을 추가(최상위 비트).
# 리플 캐리 가산기를 사용하여 이 두 값을 더하여 결과(''n'' + 1)비트 값을 생성한다.
3개 이상의 수를 더할 때, 자리올림수 저장 가산기 다음에 자리올림 전파 가산기를 사용하는 방법은 자리올림 전파 가산기 두 개를 사용하는 방법보다 빠르다. 자리올림 전파 가산기에서는 이전 자리올림 비트가 생성될 때까지 합 비트를 계산할 수 없어 지연이 발생하기 때문이다.
4. 장점 및 단점
캐리 저장 가산기의 각 단계에서,
# 우리는 즉시 덧셈의 결과를 알 수 있다.
# 우리는 덧셈의 결과가 주어진 숫자보다 큰지 작은지 ''여전히 알 수 없다''(예를 들어, 긍정적인지 부정적인지 알 수 없다).
이러한 후자의 점은 캐리 저장 가산기를 사용하여 모듈러 곱셈(나눗셈 다음에 곱셈, 나머지만 유지)을 구현할 때 단점이다.[1][2] 중간 결과가 법보다 큰지 작은지 알 수 없다면 법을 빼야 하는지 어떻게 알 수 있을까?
결과의 가장 오른쪽 자릿수에 의존하는 몽고메리 곱셈은 한 가지 해결책이다. 캐리 저장 가산기 자체와 마찬가지로 고정 오버헤드를 가지므로 몽고메리 곱셈 시퀀스는 시간을 절약하지만 단일 곱셈은 그렇지 않다. 다행히 거듭제곱 연산은 곱셈의 시퀀스이므로 공개 키 암호에서 가장 일반적인 연산이다.
주의 깊은 오류 분석을 통해 덧셈의 결과가 뺄셈을 보장할 만큼 충분히 큰지 확실히 알지 못하더라도 법을 뺄지 여부를 선택할 수 있다. 이것이 작동하려면 회로 설계가 법의 −2, −1, 0, +1 또는 +2배를 더할 수 있어야 한다. 몽고메리 곱셈에 비해 장점은 각 곱셈 시퀀스에 고정 오버헤드가 없다는 것이다.
4. 1. 장점
자리올림수 저장 가산기는 자리올림수 전파 지연을 줄여 덧셈 연산 속도를 크게 향상시킨다. 각 자릿수의 계산이 독립적이므로 병렬 처리에 용이하다.신호가 장거리를 이동할 필요가 없으므로 클럭 주파수를 높일 수 있다. 곱셈기 등에서 부분합을 누적할 때 유리하며, 512비트 곱셈을 실행하는 과정에서 512회의 덧셈을 한 후라면, 마지막 변환 비용은 사실상 512회의 덧셈으로 분산되어 각 덧셈은 최종 "기존" 덧셈 비용의 1/512회분만 부담하게 된다.
자리올림수 전파가 적어 전력 소비가 비교적 낮다는 주장도 제기되나, 이는 부가적인 연구가 필요한 부분이다.
4. 2. 단점
자리올림수 저장 가산기는 각 단계에서 덧셈 결과를 즉시 알 수 있지만, 덧셈 결과가 특정 값보다 큰지 작은지(예: 양수인지 음수인지)는 바로 알 수 없다.[1][2]이는 모듈러 곱셈(곱셈 후 나눗셈을 수행하고 나머지만 취하는 연산)을 구현할 때 단점으로 작용한다. 중간 결과가 법(modulus)보다 큰지 작은지 알 수 없으면 법을 뺄지 여부를 결정할 수 없기 때문이다.
몽고메리 곱셈은 결과의 가장 오른쪽 자릿수에 의존하는 연산으로, 이 문제에 대한 한 가지 해결책이다. 그러나 몽고메리 곱셈은 자리올림수 저장 가산기와 마찬가지로 고정 오버헤드가 있어, 연속적인 몽고메리 곱셈에서는 시간을 절약할 수 있지만 단일 곱셈에서는 그렇지 않다. 다행히 거듭제곱 연산은 연속적인 곱셈이므로 공개 키 암호에서 가장 일반적으로 사용된다.
오류 분석을 통해 덧셈 결과가 뺄셈을 보장할 만큼 충분히 큰지 확실히 알지 못하더라도 법을 뺄지 여부를 선택할 수 있다. 이를 위해서는 회로 설계가 법의 -2, -1, 0, +1 또는 +2배를 더할 수 있어야 한다.
5. 응용 분야
6. 한국의 기여
7. 추가 정보
중복 이진 표현을 사용하면 각 자릿수에 0, 1, 2, 3을 저장할 수 있어, 하나의 이진수를 더해도 저장 용량을 초과하지 않는다. 각 부분 덧셈 시점에 세 비트를 더하는데, 더하는 수(0 또는 1), 저장소 자릿수(0 또는 2면 0, 1 또는 3이면 1), 오른쪽 자릿수(0 또는 1이면 0, 2 또는 3이면 1)를 고려한다. 이는 일반 덧셈처럼 오른쪽에서 자리올림수를 받아 왼쪽에 전달하지만, 자리올림수는 현재가 아닌 이전 계산 결과이다. 자리올림수는 한 단계만 이동하면 되므로, 신호 이동 거리가 짧아 클럭을 빠르게 작동 가능하다. 계산 완료 후 이진수 변환이 필요하며, 자리올림수가 전체 숫자를 통과해야 한다. 512비트 곱셈에서 512번 덧셈을 했다면, 최종 변환 비용은 각 덧셈에 분산된다.
참조
[1]
서적
Computer arithmetic: algorithms and hardware designs
Oxford University Press
2010
[2]
논문
High-Performance Digital Filtering on Truncated Multiply-Accumulate Units in the Residue Number System
2020
[3]
특허
Latched Carry Save Adder Circuit for Multipliers
US patent 3340388
1965-07-12
[4]
간행물
Latched Carry-Save Adder
1965-03
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com