가산기

가산기(加算器, adder)란 덧셈 연산을 수행하는 논리 회로이며 디지털 회로, 조합 회로의 하나이다. 가산기는 산술 논리 장치뿐만 아니라 주소값, 테이블 색인 등을 더하는 프로세서의 한 부분으로 사용되고 있다. 이진화 십진법, 3 초과 부호와 같은 여러가지 수학적 연산을 수행하는 가산기를 구성할 수 있지만, 대부분의 가산기는 2진수의 합을 계산한다. 2의 보수나 1의 보수를 이용하여 음수를 표현하는 경우, 가산기를 가감산기로 사용한다. 다른 숫자의 부호 표현의 경우 더 복잡한 가산기를 필요로 한다.
전자계산기가 발명된 당시에는 진공관에 의해서 구성되었고 현재는 집적 회로로 설계되어서 다양한 기능을 가지는 것이다.
입력신호 전압의 덧셈을 출력하는 디지털 회로를 가산 회로라고도 부른다.

리플 자리올림수 가산기

복수의 전가산기를 이용하여 임의의 비트 수를 더하는 논리회로를 만들 수 있다. 각각의 전가산기가 자리올림수 입력 Cᵢₙ으로 직전의 자리올림수 출력 Cₒᵤₜ을 받는 형식으로, 자리올림수가 물결(ripple)치듯 다음 가산기로 옮겨 간다고 하여 리플 캐리 가산기라 한다. 첫 번째 전가산기에 한하여 반가산기로 대체될 수 있다.
리플 자리올림수 가산기는 틀이 간단하여 빠르게 디자인할 수 있는 장점이 있다. 하지만 전가산기의 자리 올림수 입력이 이전 가산기의 자리 올림수 출력이므로 하나의 전가산기가 계산되기 위해 이전 가산기의 연산을 기다려야한다. 이 때문에 비트 수가 커질수록 연산이 느려지는 단점이 있다. 이 전달 지연은 전가산기의 회로를 보면 쉽게 계산할 수 있다. 각 전가산기는 3레벨의 로직을 필요로 하는데, N비트 가산기의 경우, 임계 경로(critical path) 회로 지연은 3(첫 가산기의 지연 시간) + 2*(N-1)(다음차 가산기의 지연 시간, 주어진 두 수의 합은 자리 올림수가 도달하기 전에 미리 계산되어 있다) 값을 가지게 된다. 이는 2N에 해당하는 회로 지연을 가지며, AND, OR 게이트로 구성된 가산기의 경우 3N에 해당하는 회로 지연을 갖는다.
아래 그림은 4비트 가산기의 회로도이다. (A₃A₂A₁A₀+B₃B₂B₁B₀→C₄S₃S₂S₁S₀)

자리올림수 예측 가산기

덧셈은 정보처리의 기본중에 기본이기 때문에 고속 정보처리를 위해서 우선 가산기 동작의 고속화가 요구된다. 논리회로의 동작속도는 입력에서 출력까지 사이에 있는 논리소자 (논리곱이나 논리합회로)의 개수가 크게 영향을 주기때문에 가산기에서 이 단수를 고찰해 보자.
위의 반가산기는 입력 A와 B로부터 출력 S까지의 기본 논리소자의 단수는 2이고, 출력 C까지의 기본 논리소자의 단수는 1이다. (일반적으로 NOT은 단수에 포함하지 않는다. 기본 논리소자를 구성하는 회로의 입력용 트랜지스터를 반대로 사용하는 것만으로 NOT를 구현할 수 있기 때문이다.)
동일하게 전가산기는 S의 단수는 4이고, C의 단수도 4가 된다. 이것보다 위의 4자리수 가산기에서 최대의 단수가 되는 입력 A₀에서 C₄출력까지는 전가산기 C의 단수 X 4, 즉 4 x 4 = 16단이 된다.
자리수가 커지면 이 단수는 고속처리의 큰 장해가 된다. 그렇기 때문에 단수를 크게하는 자리올림수 신호 (캐리어 신호)의 부분을 따로 계산하여 단수를 줄이는 방법이 자주 행해진다. 이 자리올림수 신호를 다른 논리회로로 생성하는 방법을 자리올림수 예측 (carry look ahead)라고 부른다.
구체적으로는, S₁를 생성하고 있는 전가산기의 자리올림수 입력은,
X₁ ← A₀ AND B₀
가 되어서, S₂를 생성하고 있는 전가산기의 자리올림수 입력은,
X₂ ← (A₁ AND B₁) OR (A₀ AND B₀ AND A₁) OR (A₀ AND B₀ AND B₁)
가 된다. 게다가, S₃를 생성하고 있는 전가산기의 자리올림수 입력은,
X₃ ← (A₂ AND B₂) OR (A₁ AND B₁ AND A₂) OR (A₁ AND B₁ AND B₂)
    OR (A₀ AND B₀ AND A₁ AND A₂) OR (A₀ AND B₀ AND A₁ AND B₂)
    OR (A₀ AND B₀ AND B₁ AND A₂) OR (A₀ AND B₀ AND B₁ AND B₂)
가 된다. 이와같이 자리수가 커지면 회로는 비약적으로 복잡하게 되지만, 모두 2단만으로 자리올림수 신호가 생성된다. (두개 입력의 AND이나 세개 입력의 AND도 회로상에서 트랜지스터를 직렬로 늘어놓으므로 1단임에는 변화가 없다. OR에 대해서도 동일함)
이 방법을 이용하면, 자리수가 몇 개가 되어도 4단만 필요하기 때문에 획기적인 고속화를 도모할 수 있다. 그러나, 필요한 회로 소자수가 현격히 많아지기 때문에 소비전력과 회로의 비용이 커지게 된다.

예측 자리올림수 장치

복수 자리올림수 예측 가산기를 조합하여 더 큰 가산기라도 만들 수 있다. 이것은 더 큰 가산기를 만드는 복수단계에 사용할 수 있다. 예시로, 아래의 가산기는 자리올림수 예측 장치의 두단계와 16 4비트 자리올림수 예측 가산기를 사용한 64비트 가산기이다.

감산기

일반적으로 감산은 가산기에 옮겨서 계산할 수 있다. 우선은 이해하기 쉽게 십진수로 생각해 보자.
예시로 4자리수의 "5714 - 2840"라는 계산을 생각하자. 이 감산을 직접 계산하는 대신에 이 식을 "5714 + 1 + (9999 - 2840) - 10000"라고 고쳐 써 보자.
"9999 - 2840"의 부분은 "7159"이지만, 9999에서 4자리수를 빼는 경우에 자리빌림수가 발생하지 않기 때문에 다른 자리수를 고려할 필요가 없고, 각 행마다 "9-2", "9-8", "9-4", "9-0"을 행하면 된다. 즉 "더하면 9가 되는수"에 각 비트를 옮겨놓는 것 만으로 "9999 - 2840"의 계산을 할 수 있게 된다.
즉, 위의 감산은 다음의 순서로 계산할 수 있게 된다.
1  피감수 2840의 각 비트를 보수화 한다. →  7159
2  거기에 1을 더한다.               →  7160
3  거기에 감수 5714를 더한다.        → 12874
4  마지막으로 10000을 뺀다.         →  2874
계산의 마지막에 감산이 나왔지만, 3행의 계산결과가 20000이상 되는 경우가 없는 것을 생각하면, 이 계산은 단지 만의 자리수를 무시하는 것 만으로 끝난다.
그런데, 이진수로 같은계산을 생각하면, 9의 보수 대신에 1의 보수를 계산할 수 있으며, 감산에 가산기를 이용하여 계산할 수 있음을 알 수 있다. 1의 보수는 "더해서 1이 되는수"이므로, 이진수의 경우에 "0 → 1", "1 → 0"이 되며, 이것은 NOT과 동일하다.
예시로 "100101-010110"이라는 계산은 다음의 순서로 계산할 수 있게 된다.
1  피감수 010110의 각 비트를 반전(NOT)한다. →  101001
2  거기에 1을 더한다.                    →  101010
3  거기에 감수 100101을 더한다.           → 1001111
4  최상위 비트를 무시한다.                 →  001111
이것을 회로로 그리면 다음과 같다.
이 회로는 최하위 비트의 가산에 반가산기가 아닌 전가산기를 사용해서, 자리올림수 입력 X를 강제적으로 1로 함에 따라 위의 2행와 3행을 동시에 행하고 있는 것에 주의하자. 또한, 이 회로에서는 뺄셈의 결과가 음의 수가 되는 경우에만 출력 C가 0이 된다.