Adder(가산기)
가산기에 대해
개념
가산기(adder)는 2진수의 덧셈 연산을 수행하는 논리 회로 이다.
컴퓨터에서 쓰이는 연산 장치의 하나이다. 디지털 전자식 계산 장치의 모든 수학 연산에 사용되는 기초적 소자이다.
대표 종류
- 반가산기
- 전가산기
- 리플 캐리 가산기
- 자리올림 예측 가산기
- 자리 올림 저장 가산기
여기서는 반가산기와 전가산기만 다뤄보겠다.
1. 반가산기
반가산기(Half-adder)는 가장 간단한 형태의 가산기로 두 개의 숫자 A, B를 입력 받고, 합과 올림수 두 개의 값을 출력한다. 실제로도 아주 간단하다.
2진수에서 A와 B가 둘 다 01(=1)인 경우 1bit 자리에서 합하면 10(=2)이 되기 때문에 올림 수(Carry in)가 1이 되고, 1bit 자리는 합이 0이 된다. 2bit 자리는 올림 수를 받아서 1이 된다. 그 외에 0이 하나 이상 있는 경우에는 올림 수가 발생하지 않는다.
2. 전가산기
전가산기(full-adder)는 하위에서 올라온 자리 올림수를 포함하여 계산하는 가산기이다. 따라서 입력을 숫자 A, B와 이전 단계의 Carry In, 총 세 개를 받는다. 그 외는 반가산기외 계산 방식이 동일하다. 그냥 세 개의 값을 더해서 2이상이 나오면 다음 자리수에 반영되는 Carry Out에 1이 입력되고, 3이 나오면 Sum까지 1 올라가는 식이다. 십진수에서 예를 들자면, 9와 8이 있고 Carry In이 1이면 합의 결과물은 18이 되고 10을 초과했으므로 Carry Out이 1이 되고 Sum은 해당 진수 단위만큼 덜어낸 8이 남는다.
활용
전가산기를 코드로서 구현하면 다음과 같이 표현할 수 있다.
1
2
3
4
5
6
carry = 0
while ():
sum = 0
sum += val1
sum += val2
carry, val = divmod(sum+carry, 10)
carry는 맨 처음 한 번만 초기화 해주면 되고, sum은 매번 loop마다 0으로 초기화 해주어야 한다. 그렇지 않으면 쌓이기 때문.
마지막 divmod는 divmod(N, A)꼴로 사용하는 함수로 N을 A로 나눈 몫과 나머지를 튜플 형태로 리턴한다. 따라서 carry에는 전 자리 올림값(0 or 1) + 현재 자릿수의 숫자 합을 10으로 나눈 몫이 들어가고, val에는 그 나머지가 들어간다. Q16의 given sol #2에서 전가산기를 이용해 깔끔한 계산을 진행한 예시를 볼 수 있다.