carry-save adder: 세 수의 합을 두 수로 남겨 두는 이유

13, 11, 7을 더해 31을 구하는 데에는 보통 두 번의 덧셈이 필요해 보인다. 13+11을 완성한 뒤 그 결과에 7을 더하면, 각 덧셈에서 carry가 긴 비트열을 지나갈 수 있다. carry-save adder는 첫 단계에서 답을 하나의 이진수로 완성하지 않는다. 세 수를 같은 합을 나타내는 두 수로 줄여, 긴 carry 전파를 마지막까지 미룬다.

carry-save에서 save는 carry를 버린다는 뜻이 아니다. 각 자리에서 생긴 carry를 다음 자리의 가중치를 가진 별도 벡터에 보관한다. 합의 정보는 유지되지만 표현이 두 개로 나뉜다.

한 자리에서 세 입력을 두 출력으로

같은 자리의 입력 비트 a, b, c에는 0이 세 개일 수도, 1이 세 개일 수도 있다. 1의 개수를 나타내려면 두 출력이 필요하다. 낮은 가중치의 sum 비트는 XOR이고, 높은 가중치의 carry 비트는 셋 중 둘 이상이 1일 때 올라간다.

S = A XOR B XOR C

K = (A AND B) OR (B AND C) OR (C AND A)

숫자 전체의 관계는 A+B+C = S + (K << 1)이다. K의 bit i는 원래 자리보다 한 단계 높은 가중치를 가져야 하므로 왼쪽으로 이동한다. 이 이동은 고정 배선 관계이며, 가변 시프트 연산기를 의미하지 않는다.

5비트로 쓴 A=01101(13), B=01011(11), C=00111(7)을 계산하면 S=00001(1), K=01111(15)이다. 이동한 carry는 011110(30)이므로 1+30=31이다. 첫 단계가 만들어 낸 두 벡터만으로 원래 세 수의 합을 정확히 복원할 수 있다.

왜 한 carry가 이웃 자리로 계속 달리지 않나

각 자리의 full adder는 그 자리의 A_i, B_i, C_i만 보고 S_i와 K_i를 만든다. bit0에서 만들어진 K_0가 bit1의 계산에 즉시 들어가고, 다시 bit2로 이어지는 사슬이 없다. bit1의 carry도 자기 자리의 세 입력으로 독립적으로 계산된다.

Yosys의 $fa 매핑은 세 입력의 XOR와 carry 함수를 bitwise 논리로 구현한다. 이어지는 carry-propagate 계산과 구조가 다르다는 것을 코드에서 확인할 수 있다. 이 셀의 출력 중 carry가 어떤 포트에 나오는지와 상위 자리로의 연결은 사용 문맥에서 확인해야 한다.

첫 단계의 결과는 아직 일반적인 단일 이진 합이 아니다. 두 벡터를 비교하거나 외부에 하나의 숫자로 내보내려면 S와 이동한 K를 더하는 단계가 필요하다. carry-save의 이득은 긴 덧셈을 없애는 데 있지 않고, 여러 항을 축약하는 동안 매번 완성하지 않는 데 있다.

항이 많으면 두 수가 될 때까지 줄이기

예를 들어 여러 부분곱을 모으는 회로에서는 세 벡터를 두 벡터로 바꾸는 단계를 반복할 수 있다. 마지막에 두 벡터만 남으면 carry-propagate adder로 하나의 결과를 만든다. 매번 두 항의 합을 완성하는 직렬 덧셈보다 긴 carry 의존을 줄일 수 있다.

Yosys의 multiply-accumulate 매핑 코드는 여러 비트 열의 항을 축약하고 최종 연산으로 연결하는 실제 합성 구현이다. 어떤 결과 폭이 필요한지와 부호 처리에 따라 생성하는 비트의 범위도 달라진다.

이 구조를 순차 누산에도 사용할 수 있다. 누산 상태를 sum과 carry 두 벡터로 보관하고 새 항을 넣어 다시 축약하면, 각 단계에서 완전한 carry 전파를 피할 수 있다. 대신 상태 비트가 늘고, 최종 숫자를 꺼내는 순간의 변환 비용이 남는다. 다음 동작이 비교나 포화 처리라면 두 벡터 표현이 그 조건 계산을 더 어렵게 만들 수 있다.

폭과 부호를 빼먹으면 저장한 carry가 사라진다

N비트 unsigned 세 수의 최대 합은 3×(2^N−1)이다. N=5이면 최대 93이므로 전체 결과에는 7비트가 필요하다. 예제의 31이 5비트에 들어간다고 모든 세 입력의 합이 그 폭에 들어가는 것은 아니다.

K를 왼쪽으로 이동할 때 높은 carry를 자르거나, 마지막 덧셈 폭을 작게 두면 상위 정보가 사라진다. 의도적인 modulo 합이라면 잘라낸 범위가 계약의 일부지만, 전체 합이 필요한 회로에서는 오류다. signed 입력은 부호 확장과 최상위 가중치를 포함해 정의해야 하므로 unsigned 예제를 그대로 복사해서는 안 된다.

파이프라인을 넣으면 처리량도 바뀌지만 carry-save 표현 자체가 자동으로 레지스터나 여러 사이클을 만들지는 않는다. 조합 축약 트리일 수도 있고 단계별 등록 구조일 수도 있다. 구조 선택과 인터페이스 latency는 따로 명시해야 한다.

세 수를 더하는 첫 질문에 대한 답은 “덧셈 하나를 마친 뒤 다음 덧셈”만 있는 것이 아니다. 같은 값을 두 벡터로 유지하면 긴 carry 계산을 필요한 마지막 순간으로 옮길 수 있다. carry-save adder를 평가할 때는 얼마나 많은 항을 축약하는지, 마지막 변환이 어디에 있는지, 그동안 모든 가중치가 보존되는지를 보면 된다. carry를 미룬 이득과 남겨 둔 책임이 함께 보인다.