가산기편집자 확인

이진수 덧셈은 디지털 시스템의 가장 기본적인 산술 연산 중 하나이다. 이 연산을 수행하는 논리 회로가 바로 가산기이다. 디지털 시스템은 모든 정보를 0과 1로 표현하는 이진수를 사용하기 때문에, 두 개 이상의 이진수를 더하는 회로는 컴퓨터와 같은 전자 장치의 핵심 구성 요소가 된다.

이진 덧셈의 규칙은 십진법과 유사하지만, 사용 가능한 숫자가 0과 1뿐이라는 점이 다르다. 기본적인 규칙은 0+0=0, 0+1=1, 1+0=1, 1+1=10(이진수로 '2'를 의미)이다. 마지막 경우에서 결과는 두 자릿수가 되는데, 하위 비트는 합(Sum)이고, 상위 비트는 자리올림수(Carry)라고 부른다. 이 자리올림수는 다음 더 높은 자릿수의 덧셈에 입력으로 사용된다.

이러한 덧셈 규칙을 하드웨어로 구현하기 위해 논리 게이트가 사용된다. 기본적인 논리 게이트인 AND 게이트, OR 게이트, NOT 게이트, 그리고 XOR 게이트(배타적 논리합)의 조합으로 덧셈 기능을 만들어낼 수 있다. 예를 들어, 두 비트 A와 B를 더할 때, 합(S)은 A와 B의 XOR 연산(A ⊕ B)과 같고, 자리올림수(C)는 A와 B의 AND 연산(A · B)과 같다. 이는 가장 간단한 형태의 가산기인 반가산기의 동작 원리이다.

자리올림수는 다중 비트 이진수 덧셈에서 핵심적인 개념이다. 한 자리에서 두 비트를 더한 값이 사용 가능한 숫자 범위(이진수에서는 0과 1)를 초과할 때 발생하며, 이 초과분은 바로 왼쪽의 상위 비트로 전달된다. 예를 들어, 십진수에서 9와 1을 더하면 합은 10이 되고, 1은 '올림수'가 되어 십의 자리로 이동한다. 이진수에서도 마찬가지로, 1과 1을 더하면 합은 2(이진수 '10')가 되는데, 이때 하위 비트(S)는 0이 되고, 상위 비트로 전달되는 값 1이 자리올림수가 된다.

논리 회로 설계에서 자리올림수의 처리 방식은 가산기의 성능과 복잡도를 결정한다. 가장 간단한 반가산기는 두 개의 입력 비트(A, B)만을 고려하여 합(S)과 자리올림수(C)를 출력한다. 그러나 다중 비트 덧셈을 위해서는 하위 비트에서 발생한 자리올림수 입력(C_in)을 함께 처리할 수 있는 전가산기가 필요하다. 전가산기는 A, B, C_in 세 입력의 합을 계산하여 새로운 합(S)과 새로운 자리올림수(C_out)를 생성한다. 이 C_out은 다시 다음 상위 비트의 가산기로 입력되어 연쇄적인 덧셈을 가능하게 한다.

자리올림수의 전파 속도는 가산기 전체의 연산 속도를 제한하는 주요 요인이다. 리플 자리올림수 가산기처럼 자리올림수가 낮은 비트에서 높은 비트로 순차적으로 전파되는 구조에서는 비트 수가 증가할수록 최종 결과를 얻기까지의 지연 시간이 길어진다. 이러한 문제를 해결하기 위해 자리올림수 예측 가산기와 같은 고속 구조가 개발되었다. 이 구조는 모든 비트 쌍의 입력을 동시에 분석하여 자리올림수가 발생할지 여부를 미리 예측하고, 이를 병렬로 처리함으로써 지연 시간을 크게 단축한다.

반가산기는 두 개의 1비트 이진수를 더하는 가장 기본적인 논리 회로이다. 두 개의 입력(A와 B)을 받아 두 비트의 합에 해당하는 합(S)과, 덧셈 결과 발생한 자리올림수(C)를 출력한다. 이름에 '반(半)'이 붙은 이유는, 하위 비트에서 올라오는 자리올림수 입력을 처리할 수 없기 때문이다. 즉, 완전한 다중 비트 덧셈을 수행하기에는 기능이 불완전하다.

반가산기의 동작은 다음 진리표로 명확히 정의된다.

이 표에서 볼 수 있듯이, 합(S) 출력은 두 입력이 서로 다를 때(0과 1, 또는 1과 0) 1이 된다. 이는 배타적 논리합(XOR) 연산과 정확히 일치한다. 반면, 자리올림수(C) 출력은 두 입력이 모두 1일 때만 1이 되며, 이는 논리곱(AND) 연산과 같다.

따라서 반가산기의 논리 회로는 하나의 XOR 게이트와 하나의 AND 게이트로 간단히 구성된다. S 출력은 A와 B의 XOR 연산 결과이며, C 출력은 A와 B의 AND 연산 결과이다. 수식으로 표현하면 S = A ⊕ B, C = A · B 이다. 이 간결한 구조 덕분에 반가산기는 더 복잡한 전가산기나 다중 비트 가산기를 구성하는 기본 구성 요소로 널리 사용된다.

전가산기는 이진수의 한 자릿수를 연산할 때, 하위 자리에서 발생한 자리올림수 입력까지 포함하여 처리하는 논리 회로이다. 반가산기가 두 개의 입력(A, B)만을 처리하는 반면, 전가산기는 자리올림수 입력(C_in)이라는 세 번째 입력을 추가로 받아들인다. 이로 인해 다중 비트 덧셈을 구성하는 기본 구성 요소로 사용된다.

하나의 전가산기는 두 개의 반가산기와 하나의 OR 게이트를 조합하여 구성할 수 있다. 첫 번째 반가산기가 입력 A와 B를 더해 중간 합(S')과 중간 자리올림수(C1)를 생성한다. 두 번째 반가산기는 이 중간 합(S')과 하위 자리에서 전달된 자리올림수 입력(C_in)을 더해 최종 합(S)과 또 다른 자리올림수(C2)를 생성한다. 최종 자리올림수 출력(C_out)은 두 반가산기에서 발생한 자리올림수 C1과 C2를 OR 연산하여 얻는다[1].

전가산기의 논리적 동작은 다음 진리표로 명확히 정의된다.

이를 논리식으로 표현하면 합(S)은 세 입력의 배타적 논리합(XOR)이며, 자리올림수(C_out)는 세 입력 중 두 개 이상이 1일 때 1이 되는 다수결 함수이다. 구체적으로 S = A ⊕ B ⊕ C_in 그리고 C_out = (A AND B) OR (C_in AND (A ⊕ B))로 나타낸다. 이 구조는 집적 회로 설계 시 게이트 종류를 최소화하는 데 유용하다.

리플 자리올림수 가산기는 여러 개의 전가산기를 직렬로 연결하여 다중 비트 이진수 덧셈을 수행하는 가장 기본적인 구조의 가산기이다. 각 전가산기는 한 비트의 덧셈을 담당하며, 하위 비트에서 발생한 자리올림수 출력(Cout)이 바로 상위 비트의 자리올림수 입력(Cin)으로 연결된다. 이 연결 방식 때문에 자리올림수가 낮은 비트에서 높은 비트로 물결(ripple)처럼 전파된다고 하여 이러한 이름이 붙었다.

이 구조의 가장 큰 장점은 설계가 매우 간단하고 직관적이라는 점이다. N비트 덧셈을 위해서는 단순히 N개의 전가산기를 연결하기만 하면 되며, 첫 번째(최하위 비트) 가산기는 자리올림수 입력이 항상 0이므로 반가산기로 대체할 수도 있다. 그러나 심각한 단점은 연산 속도이다. 최상위 비트의 결과가 최종적으로 안정되기 위해서는 최하위 비트에서 발생한 자리올림수가 모든 중간 비트를 차례로 통과해야 한다. 이로 인해 총 지연 시간은 가산기의 비트 수에 비례하여 증가한다.

구체적으로, 각 전가산기의 자리올림수 경로에 일정한 지연 시간이 있다고 가정할 때, N비트 리플 자리올림수 가산기의 최악의 경우 지연 시간은 약 N * (한 개의 전가산기 지연 시간)에 가깝다[3]. 따라서 32비트나 64비트와 같은 큰 비트 폭의 덧셈에는 속도가 너무 느려 부적합하며, 주로 비트 수가 적거나 속도보다 설계 간단함이 중요한 경우에 사용된다.

리플 자리올림수 가산기의 가장 큰 단점은 자리올림수가 낮은 자리에서 높은 자리로 순차적으로 전파되어야 한다는 점이다. 이로 인해 비트 수가 증가할수록 연산 속도가 크게 저하된다. 자리올림수 예측 가산기는 이 문제를 해결하기 위해, 모든 비트의 입력값을 동시에 분석하여 자리올림수를 미리 예측하고 생성하는 방식을 사용한다.

이 방식의 핵심은 각 비트 위치 i에서 두 개의 보조 신호, 즉 자리올림수 생성(Generate) 신호 G_i와 자리올림수 전파(Propagate) 신호 P_i를 정의하는 데 있다. 생성 신호 G_i = A_i · B_i는 해당 비트의 두 입력이 모두 1일 때 자리올림수가 '생성'됨을 의미한다. 전파 신호 P_i = A_i ⊕ B_i는 하위 비트에서 올라온 자리올림수가 해당 비트를 '전파'하여 다음 비트로 넘어갈 수 있음을 의미한다. 이를 바탕으로 각 비트의 최종 자리올림수 C_i는 하위 비트들의 G와 P 신호로부터 논리식으로 직접 계산할 수 있다. 예를 들어, C_1 = G_0 + (P_0 · C_0), C_2 = G_1 + (P_1 · G_0) + (P_1 · P_0 · C_0)과 같은 형태로 표현된다[4].

이러한 구조는 모든 자리올림수를 병렬로 계산할 수 있게 만들어, 연산 지연 시간을 비트 수에 비례하는 선형 시간(O(N))에서 로그 시간(O(log N)) 수준으로 크게 단축시킨다. 그러나 더 많은 논리 게이트를 필요로 하여 회로가 복잡해지고 면적이 증가하는 단점이 있다. 이 트레이드오프 때문에 고성능 프로세서의 ALU 등 속도가 중요한 경우에 주로 사용된다.

리플 자리올림수 가산기의 속도 한계를 극복하기 위해, 자리올림수 예측 가산기 외에도 다양한 고속 가산기 구조가 개발되었다. 이들은 병렬 처리, 조건부 합산, 자리올림수 체인 분할 등의 기법을 활용하여 덧셈 연산의 지연 시간을 단축한다.

대표적인 구조로는 자리올림수 선택 가산기(Carry-Select Adder)가 있다. 이 방식은 입력 비트를 여러 개의 블록으로 나누고, 각 블록에 대해 자리올림수 입력이 '0'인 경우와 '1'인 경우의 두 가지 합을 병렬로 미리 계산해 둔다. 실제로 상위 블록에서 자리올림수가 결정되면, 그 값에 따라 미리 계산된 두 결과 중 하나를 빠르게 선택하여 출력한다[5]. 이는 리플 방식보다 하드웨어 자원은 더 많이 소모하지만, 특히 긴 비트 폭에서 상당한 속도 향상을 가져온다.

다른 접근법으로는 자리올림수 건너뛰기 가산기(Carry-Skip Adder)가 있다. 이 구조는 특정 조건에서 자리올림수 전파 경로를 단축시킨다. 만약 가산기 블록 내의 모든 비트 쌍에서 하나라도 A와 B가 서로 다른 값(즉, 하나는 0, 다른 하나는 1)이라면, 그 블록은 자리올림수를 입력에서 출력으로 그대로 전파(propagate)시킨다. 이 경우, 블록의 시작과 끝을 연결하는 우회 경로를 통해 자리올림수가 블록 내의 모든 논리 게이트를 거치지 않고 빠르게 건너뛸 수 있다.

또한, 조건부 합 가산기(Conditional Sum Adder)는 자리올림수 선택 방식의 극단적인 형태로, 재귀적인 분할 정복 알고리즘을 하드웨어에 적용한다. 이 외에도 자리올림수 예측 가산기의 논리를 변형하거나, 여러 기법을 조합한 하이브리드 구조도 널리 사용된다. 이러한 고속 가산기 구조의 선택은 목표하는 연산 속도, 전력 소모, 칩 면적, 그리고 설계 복잡도 간의 트레이드오프에 따라 결정된다.

감산기는 뺄셈 연산을 수행하는 논리 회로이다. 기본적인 디지털 감산기는 가산기와 매우 유사한 구조를 가지며, 특히 2의 보수 표현법을 사용할 때 가산기 회로를 거의 그대로 활용하여 뺄셈을 구현할 수 있다.

가장 간단한 형태인 반감산기와 전감산기는 각각 반가산기와 전가산기와 대응된다. 반감산기는 두 개의 1비트 입력 A와 B를 받아 차(D)와 빌림수(Borrow)를 출력한다. 전감산기는 하위 비트에서의 빌림수 입력을 추가로 고려한다. 그러나 실제 디지털 시스템에서는 빌림수를 직접 처리하는 방식보다는 보수법을 이용한 가산기 재활용 방식이 훨씬 더 널리 사용된다.

2의 보수 체계에서 A - B 연산은 A + (-B)로 변환된다. 여기서 -B는 B의 2의 보수, 즉 B의 모든 비트를 반전시킨 후 1을 더한 값이다. 따라서 감산기는 가산기 앞단에 보수기를 추가하는 방식으로 구성된다. 이때 뺄셈 모드에서는 B 입력이 보수화되어 가산기로 들어가고, 덧셈 모드에서는 그대로 입력된다. 이 선택은 제어 신호에 의해 이루어진다. 이 원리는 가감산기라는 단일 회로로 통합되어 덧셈과 뺄셈 모두를 수행할 수 있게 한다.

전가산기는 기본적으로 덧셈 연산만을 수행하지만, 2의 보수나 1의 보수와 같은 음수 표현 방식을 활용하면 뺄셈 연산도 가능해진다. 이 원리를 이용하여 하나의 논리 회로로 덧셈과 뺄셈을 모두 수행할 수 있도록 설계한 장치가 가감산기이다.

가감산기의 핵심은 제어 신호에 따라 연산 모드를 전환하는 것이다. 일반적으로 M이라는 단일 비트 제어선을 사용하며, M=0일 때는 덧셈, M=1일 때는 뺄셈 모드로 동작한다. 뺄셈을 수행할 때는 감수(뺄 수)의 모든 비트를 반전시킨 후 최하위 비트에 1을 더하는, 즉 2의 보수를 구하는 과정이 필요하다. 이 과정은 각 비트의 XOR 게이트 하나로 간단히 구현된다. XOR 게이트는 한쪽 입력이 0이면 원래 값을 통과시키고, 1이면 값을 반전시키는 특성이 있기 때문이다.

구체적인 구성은 다중 비트 리플 자리올림수 가산기나 자리올림수 예측 가산기 앞단에 각 비트별 XOR 게이트 배열을 추가하는 방식이다. 각 XOR 게이트의 한쪽 입력에는 원래의 B 비트가, 다른 쪽 입력에는 공통의 제어 신호 M이 연결된다. 또한, 최하위 비트의 자리올림수 입력(C_in)에 제어 신호 M을 직접 연결한다. 이렇게 하면 M=1일 때 B 비트가 반전되고 동시에 C_in에 1이 공급되어, 결국 B의 2의 보수가 가산기에 입력되는 효과를 낸다. 따라서 가산기는 A와 (B의 2의 보수)를 더하게 되고, 이는 수학적으로 A - B 연산과 동일하다.

가감산기는 산술 논리 장치(ALU)의 기본 구성 요소로서, 프로세서 설계에서 필수적이다. 하나의 회로로 두 가지 연산을 처리할 수 있어 하드웨어의 효율성과 집적도를 높이는 데 기여했다.

가산기는 주로 이진수 덧셈에 사용되지만, 다른 수 체계에서도 덧셈 연산을 수행하도록 설계하거나 변형하여 사용할 수 있다. 가장 일반적인 변형은 이진화 십진법(BCD) 가산기이다. BCD 가산기는 4비트 이진수를 사용하여 한 자리의 십진수(0-9)를 표현하며, 두 BCD 숫자를 더했을 때 결과가 9를 초과하거나 자리올림수가 발생하면 보정값(보통 6)을 다시 더하여 올바른 BCD 결과를 얻는다[7]. 이는 계산기나 초기의 마이크로프로세서에서 널리 사용되었다.

더 복잡한 수 체계로는 3 초과 부호(Excess-3)나 그레이 코드(Gray code)를 위한 가산기가 있다. 3 초과 부호는 BCD와 유사하지만 각 숫자에 3을 더하여 표현하며, 자체 보완 특성을 가져 일부 계산에 유리하다. 그레이 코드는 인접한 코드 간에 한 비트만 변화하도록 설계되어, 회전식 엔코더 등에서 오류를 줄이는 데 사용되지만, 덧셈 연산을 직접 수행하기에는 표준 이진 가산기보다 회로가 복잡해진다.

이러한 다양한 수 체계용 가산기는 특정 응용 분야의 요구사항을 충족시키기 위해 개발되었다. 그러나 현대의 범용 디지털 회로와 마이크로프로세서는 대부분 효율성과 단순성을 위해 이진수 체계를 기반으로 하며, 필요 시 소프트웨어나 추가 변환 회로를 통해 다른 수 체계의 연산을 처리한다.

초기 가산기는 진공관을 기본 소자로 구성되었다. 1940년대부터 1950년대 중반까지 개발된 초기 컴퓨터들, 예를 들어 ENIAC, EDSAC, UNIVAC I 등은 모두 수천 개에서 수만 개에 이르는 진공관을 사용하여 논리 회로를 구현했으며, 그 핵심 연산 장치인 가산기도 진공관으로 만들어졌다. 이러한 진공관 가산기는 복잡한 배선과 거대한 크기, 높은 전력 소비 및 발열이 특징이었다.

진공관 가산기의 동작 원리는 기본적으로 이진법 논리를 전기 신호로 변환하는 것이었다. 진공관은 스위치나 증폭기 역할을 하여 AND 게이트, OR 게이트, NOT 게이트와 같은 기본 논리 소자를 구성했다. 이러한 게이트들을 조합하여 반가산기와 전가산기를 만들고, 이를 다시 연결하여 다중 비트 덧셈을 수행하는 리플 자리올림수 가산기 구조를 구현했다. 당시의 기술 수준에서는 고속화를 위한 자리올림수 예측 가산기 같은 복잡한 설계보다는 직관적인 리플 구조가 주로 사용되었다.

진공관 가산기는 신뢰성 문제가 컸다. 수많은 진공관 중 하나라도 고장 나면 전체 시스템이 멈추는 경우가 많았고, 발열로 인한 수명 단축과 빈번한 유지보수가 필요했다. 또한, 크기와 전력 소비 면에서 매우 비효율적이었다. 이러한 한계는 1950년대 후반 트랜지스터의 등장과 함께 급속히 해소되었으며, 트랜지스터를 이용한 소형화되고 안정적인 가산기 설계가 본격화되었다.

초기 가산기는 개별 진공관이나 트랜지스터로 구성된 이산 소자 회로였다. 이는 크기가 크고 전력 소모가 많으며 신뢰성이 낮은 한계를 지녔다. 1960년대 집적회로 기술의 등장은 가산기 설계와 구현에 혁명을 가져왔다. 소형 실리콘 칩 안에 수백, 수천 개의 트랜지스터를 집적할 수 있게 되면서, 복잡한 다중 비트 가산기를 단일 패키지로 제작하는 것이 가능해졌다.

초기 집적회로 가산기는 TTL이나 CMOS와 같은 표준 논리 게이트 제품군의 일부로 등장했다. 예를 들어, 4비트 리플 자리올림수 가산기인 7483 칩은 널리 사용되는 표준 부품이었다. 기술이 발전함에 따라 가산기는 더 큰 규모의 집적회로, 즉 마이크로프로세서와 산술 논리 장치의 핵심 구성 요소로 통합되었다. 현대 마이크로프로세서에서는 가산 연산의 속도가 전체 성능을 좌우하므로, 자리올림수 예측 가산기나 더 복잡한 병렬 구조가 내부 데이터 경로에 표준으로 채택된다.

현대의 나노미터 공정 반도체 기술에서 가산기는 단순한 조합 논리 블록을 넘어, 파이프라이닝 기법을 적용하거나 여러 가산기를 병렬로 배치하여 처리량을 극대화한다. 또한, 이동 통신 및 신호 처리용 디지털 신호 처리장치에는 고속 병렬 가산기가 필수적이다. 저전력 설계가 중요한 모바일 장치에서는 전력 소모와 속도 간의 트레이드오프를 고려한 가산기 회로 최적화가 지속적으로 연구되고 구현된다[9].