자리올림수 저장 가산기

자리올림수 저장 가산기(carry-save adder)는 이진법에서 3개 그이상의 n 비트수 덧셈을 계산하기위한 컴퓨터 기본설계에 사용하는 가산기의 한 종류이다. 입력과 같은 크기의 두개의 수를 출력하는 것이 다른 디지털 가산기와 다르다. 하나는 부분적인 덧셈 비트의 반복이고, 다른하나는 자리올림수 비트의 반복이다.

자리올림수 저장 장치는 n 전가산기로 구성되며, 각각은 3개의 입력수의 연관된 비트에 유일하게 기반을둔 합계와 자리올림수 비트를 계산한다. 주어진 3개의 n 비트수는 a, b, c이고, 이것은 소계 (partial sum) ps와 자리올림수 (shift-carry) sc를 만든다:

$ps_{i}=a_{i}\oplus b_{i}\oplus c_{i}$

$sc_{i}=(a_{i}\wedge b_{i})\vee (a_{i}\wedge c_{i})\vee (b_{i}\wedge c_{i})$

전체합은 아래처럼 계산할 수 있다:

1. 한쪽방향 왼쪽으로 자리올림수 반복 sc를 시프트한다.
2. 소계 반복 ps의 앞 (최상위 비트)에 0을 추가한다.
3. 이 두개를 합치고 n + 1 비트값을 발생시키기 위해 리플 자리올림수 가산기를 사용한다.

3개 이상의 수를 더할때, 리플 자리올림수 가산기에 의하여 자리올림수 저장 가산기를 사용하는 것은 두개의 리플 자리올림수 계산기를 사용하는 것보다 빠르다. 이것은 리플 자리올림수 가산기가 아래 자리올림비트 연산을 기다리지 않고서 계산할 수 없기 때문이고, 그리하여 n 전가산기와 동일한 지연을 지녔다. 그러나, 자리올림수 저장 가산기는 병렬로 모든 출력값을 연산하고, 그리하여 하나의 전가산기와 동일한 지연을 갖고있다. 그러므로 자리올림수 저장 가산기 더하기 리플 자리올림수 가산기한 (전가산기 지연시간의 단위에서) 전체 계산 시간은 n + 1이지만, 두개의 리플 자리올림수 가산기는 2n이 된다.