0. 용어 설명
비트 : 1 또는 0을 저장할 수 있는 저장단위라 해야하노.. 아무튼 2진수 1자리라고 보면 됨
게이트 : 입력을 받아 논리연산을 하여 출력하는 연산 단위라 하면 되려나.. 연산 단위라 하니까 좀 이상한거 같기도하고
0. 서론
컴퓨터가 더하기를 어떻게 계산하는 지 생각해본 적이 있노?
컴퓨터는 멍청하다
하지만 빠르다
컴퓨터는 2진수 밖에 모른다.
그래서 덧셈도 2진수로 한다.
예를 들어 5+7=12를 계산할 때 인간은 한자리+한자리=두자리지만
컴퓨터는
101+111=1100이 된다
더하는 자리수가 많다.
즉, 1비트(1또는 0을 가지는 각 자리)씩 더하는 걸 여러번 해서 전체 결과인 1100을 만들어 내는 것이다
1. 하프 애더
1비트 짜리 두 수를 더하는 경우를 생각해보자.
0+0=0
0+1=1
1+0=1
1+1=10
1비트의 두 수를 더할 때는 이 4가지 경우 밖에 없다.
이제 이 수를 다음과 같은 형식으로 보자
x+y=cs
0+0=00
0+1=01
1+0=01
1+1=10
x,y는 입력값(input)이고
c,s는 우리가 원하는 결과의 출력(output)이다.
이제 c와 s를 x와 y에 대한 함수로 표현해보자.
c : x와 y가 모두 1일 때만 1. 그 외의 경우에는 0
s : x와 y중 하나가 1일 때만 1. 그 외의 경우에는 0
다행스럽게도 이것을 연산해주는 칩은 이미 존재한다.
and(&)와 xor(^)이다. (여기에서 ^은 거듭제곱을 의미하는 게 아닌 다른 의미로 쓰인다)
c = x & y
s = x ^ y
A + B를 구하는 것
D모양의 로직 게이트는 AND, ))>는 XOR을 의미한다.
2. 풀 애더
이제 우리는 1비트 두개를 더하여 최대 2비트의 출력을 가지는 덧셈기를 만들었다.
이제 5+7 같은 계산을 할 수 있을까?
그렇지 않다.
77+88을 계산 해보자.
정답은 165이다.
우리는 이것을 계산할 때 1의 자리의 7과 8을 더하여 15를 만든 후, 5는 그대로 결과의 1의 자리에 적고 1은 10의 자리로 올려준다.
그리고 그 다음의 7과 8을 더할 때 1을 함께 더해 결과를 16으로 적어서 최종적으로 165의 결과를 얻어낸다.
이렇게 1의자리에서 7과 8을 더하여 15가 나왔을 때 1을 Carry라고 한다. 한글로는 그냥 올림.
1의 하프 애더에서 C는 바로 이를 의미하는 것이다.
즉, 1의 하프 애더는 입력이 A와 B 2개 뿐이지만, 실제로는 이전 자리의 Carry값도 함께 계산해주어야 한다.
따라서 우리는 1비트 짜리 3개를 더하는 것을 생각해야 한다.
인풋이 A,B,Ci일 때
결과로 Co,S를 내놓는다고 보고 Co, S의 관계를 생각해보자.
A+B+Ci는 총 4가지의 결과를 가진다.
00 : A=B=Ci=0
01 : A,B,Ci중 하나만 1일 때
10 : A,B,Ci중 두개만 1일 때
11 : A,B,Ci중 세개가 1일 때
이제 Ci, S의 함수식을 구해보자.
Ci : A,B,Ci중 두개이상이 1일 때
S : A,B,Ci중 홀수개가 1일 때
S는 XOR 칩을 이용하면 쉽게 구할 수 있다.
S = A ^ B ^ Ci
Co = A & B + B & Ci + Ci & A (abc=110,011,101,111일 경우 1)
(정확히는 Co = ABC'+A'BC+ABC'+ABC)
이를 로직 게이트로 만들어보자.
사실 여기에서 Co을 구할 때의 정확한 식은
A & B + (A ^ B) & Ci
인데, 위에 표현한 것과 결과적으로 같은 작용을 한다.
(A & B = ABC' + ABC)
자.
여기서, 1개의 XOR 게이트와 1개의 AND 게이트로 연산한 것은 아까 봤던 Half adder이다.
이 부분을 half adder로 치환하면,
비로소 3개의 입력을 받아 2개의 출력을 해주는 full adder가 완성 된다.
half adder는 2개가 있어야 온전한 기능을 하기 때문에 half adder라고 하는 것이다.
3. n비트 덧셈
이제야 드디어 온전한 1비트 짜리 덧셈기를 만들었다.
이 하프 애더만 있으면 몇 비트짜리더라도 쉽게 계산할 수 있다. (물론, 시간은 별개의 이야기이다.)
다시 우리가 10진수 계산하는 것으로 돌아가보자.
일게이 수준에 맞는 어려운 세자리 덧셈 문제를 가져와봤다.
237+116
먼저 1의 자리를 더해 13을 구하고 3은 그대로 쓰고 1은 10의 자리에 올려준다
10의 자리 계산할 때 3과 1과 아까 올렸던 1을 모두 더해서 5를 쓴다.
10의 자리 계산할 때 올라온 것이 없으므로 그냥 2와 1만 더하여 3을 쓴다.
2진수의 계산도 똑같다.
다만 올려지는 수가 1 또는 0인 것만 다를 뿐이다.
실제 2진수의 예로 알아보자.
맨 처음 1의 자리를 계산할 때는 carry가 없으므로 그냥 0과 1을 더한다.
0+1=01
2의 자리에 carry로 0을 적는다.
2의 자리 덧셈할 때 0+1+1=10
4의 자리에 carry로 1을 적는다.
4의 자리 계산할 때 1+1+1=11
8의 자리에 carry로 1을 적는다.
8의 자리 계산할 때 1+0+0=01
따라서 총 결과는 1101
A = 0110
B = 0111
C0 = 0
을 다음 그림에 넣어 눈으로 따라가보자
쉽게 따라갈 수 있을 것이다.
파란 박스로 예쁘게 표시해둔 1-bit Full Adder를 실제 게이트로 표현하면
4비트짜리 두개 더하기 위해서 이런 계산만 하면 된다 이기야!
1바이트짜리 수 (0~255)를 더하는 애더를 보자.
이렇게 하면 최대 255짜리 2개를 더할 수 있다.
오늘도 초당 몇십억번 이짓을 해주는 컴퓨터에게 감사의 마음을 갖자.
출처 및 원글링크
