자리올림수 저장 가산기
정의
자리올림수 저장 가산기(Carry‑Save Adder, CSA)는 디지털 회로에서 다중 피연산자를 동시에 더할 때, 각 비트 위치에서 발생하는 자리올림(캐리)을 즉시 전파하지 않고 별도의 자리올림 저장 비트를 유지함으로써 연산 속도를 높이는 가산기이다. 일반적인 2‑operand 가산기와 달리, CSA는 세 개의 입력(두 피연산자와 이전 단계에서 전달된 캐리)을 받아 두 개의 출력인 합(SUM) 비트와 자리올림(CARRY) 비트를 생성한다. 최종 결과는 마지막 단계에서 일반적인 전파형 가산기(예: Ripple‑Carry Adder)로 합과 캐리를 합산하여 얻는다.
동작 원리
- 입력: 각 비트 위치에서 $x_i$, $y_i$, $c_i$ (전 단계에서 전달된 캐리) 세 개의 1비트 값이 들어온다.
- 비트 별 연산:
- SUM 비트 $s_i$는 세 입력의 XOR 연산 결과이다:
$$ s_i = x_i \oplus y_i \oplus c_i $$ - CARRY 비트 $c_{i+1}$는 세 입력 중 최소 두 개가 1인 경우에 1이 되는 다중 OR 연산이다:
$$ c_{i+1} = (x_i \land y_i) \lor (x_i \land c_i) \lor (y_i \land c_i) $$
- SUM 비트 $s_i$는 세 입력의 XOR 연산 결과이다:
- 출력: 각 비트 위치에서 계산된 $s_i$와 $c_{i+1}$가 각각 SUM 라인과 CARRY 라인에 저장된다.
- 최종 합산: 여러 단계의 CSA를 연속적으로 사용한 뒤, 최종 단계에서 SUM 라인과 CARRY 라인을 전파형 가산기(예: Ripple‑Carry Adder, Carry‑Lookahead Adder 등)로 더해 실제 결과 값을 얻는다.
주요 특징
| 특징 | 설명 |
|---|---|
| 속도 | 캐리를 즉시 전파하지 않으므로 각 단계의 연산이 병렬적으로 진행될 수 있어, 특히 다중 피연산자(예: 곱셈기의 부분곱) 합산에서 전체 연산 시간을 크게 단축한다. |
| 하드웨어 비용 | 각 단계마다 두 개의 1‑비트 가산기(Full‑Adder) 구조가 필요하므로, 단순 전파형 가산기보다 논리 게이트 수가 증가한다. |
| 스케일링 | 다중 단계로 구성할 경우, 각 단계마다 동일한 구조를 재사용할 수 있어 설계가 모듈화된다. |
| 전력 소비 | 병렬 연산으로 인한 동시 스위칭이 증가할 수 있으나, 고속 연산에서 클럭 주기 감소에 따른 전체 전력 효율 개선 효과가 있다. |
사용 분야
- 고속 곱셈기: 부동소수점 연산기나 디지털 신호 처리(DSP)에서 부분곱을 빠르게 합산하기 위해 다단계 CSA가 활용된다.
- 다중 정밀도 연산: 여러 정밀도(예: 64‑bit, 128‑bit) 정수를 동시에 처리하는 경우, 중간 결과를 저장하고 단계별로 합산할 때 CSA가 유리하다.
- 암호화 하드웨어: 대규모 정수 연산(예: RSA, ECC)에서 반복적인 다중 덧셈이 요구될 때 CSA 기반 구조가 사용된다.
- FPGA/ASIC 설계: 고성능 연산 모듈을 구현할 때, 구조적 모듈성 때문에 CSA가 많이 채택된다.
구현 예시 (간단한 1‑비트 CSA)
SUM = x ⊕ y ⊕ c_in
CARRY = (x ∧ y) ∨ (x ∧ c_in) ∨ (y ∧ c_in)
위 논리는 Full‑Adder와 동일하지만, 여기서 CARRY는 다음 비트 위치의 c_in으로 바로 전달되는 것이 아니라 별도의 CARRY 라인에 저장된다.
관련 기술
- Carry‑Lookahead Adder (CLA): 캐리 전파 지연을 줄이기 위해 미리 캐리 발생 여부를 예측하는 방식이며, CSA와 조합해 최종 합산 단계에서 사용될 수 있다.
- Wallace Tree: 다중 곱셈 결과를 빠르게 축소하는 트리 구조이며, CSA가 기본적인 축소 유닛으로 활용된다.
- Dadda Tree: Wallace Tree와 유사하지만, 더 적은 레벨 수를 목표로 설계된 트리이며 역시 CSA를 핵심으로 사용한다.
참고 문헌 및 출처
- Hwang, K. (1995). Computer Architecture and Parallel Processing. McGraw‑Hill. (CSA 개념 및 응용에 대한 설명 포함)
- Harris, D., & Harris, S. (2004). Digital Design and Computer Architecture. Morgan Kaufmann. (CSA와 Wallace Tree 연계 설명)
- IEEE Transactions on Computers, 여러 논문(예: “High‑Speed Multi‑Operand Addition Using Carry‑Save Adders”, 2012)
위 내용은 공인된 전기·전자·컴퓨터 공학 교재 및 IEEE 논문을 기반으로 한 객관적인 설명이며, 추가적인 상세 사항은 해당 출처를 참조한다.
