전가산기

목록

1. 포스팅 개요
2. 본론
3. 요약

1. 포스팅 개요

인프런에서 널널한 개발자님의 강의를 보다가 전가산기가 이해가 안 되서 살펴보았습니다.
전가산기가 덧셈을 하는 이해하고, 기록으로 남기고자 포스팅합니다.

2. 본론

전가산기를 알기 전에 반가산기를 먼저 알아보아야 합니다.

반가산기는 이것입니다.

출처 위키피디아

반가산기는 2개의 2진수를 가지고, 한 자리수를 연산하여 자리올림수(Carry: 이하 자리올림 또는 C)와 최종값(SUM : 이하 S)을 구하는 것입니다.

C는 AND연산으로, S는 XOR연산을 통해서 도출할 수 있습니다.

그런데, 이진수 1 A와 이진수 1 B로 1bit의 연산을 한다면,
이진수 1+1은 10입니다.
그런데, 1bit연산은 1bit 밖에 담지 못하므로, 결과는 0일것입니다.

그럼 앞자리 1은요?
그게 오버플로우가 된 것입니다.

그런데, 반가산기의 치명적인 단점은, 자리올림에 대한 연산을 할 수 없습니다.
자리올림의 여부를 판별한다해도, 그에 대하여 연산을 할 수 없는 것이 치명적인 단점입니다.

따라서, 두 개의 이진수 A, B와 자리올림까지 총 3bit의 연산을 합산할 수 있는 로직이 필요한데, 그것이 바로 전가산기입니다.

제가 그런데 제일 헷갈렸던 것은 이 그림입니다.

이건 4bit 전가산기입니다.
그런데 들어오는 입력값이 8개라서 저는 "이거 8bit아닌가,,?"
라고 생각했지만, 아닙니다.

위에서 보고 계신 a4,a3,a2,a1 이 이진수 A에 대한 자리수이고,
b도 마찬가지로, b4,b3,b2,b1 이 이진수 B에 대한 자리수 입니다.

다음 표를 보도록 하겠습니다.

자리수	a	b
4	1	1
3	0	1
2	1	0
1	0	1

이렇게 되어있다면,
이진수 A는 1010입니다.
이진수 B는 1101입니다.

흠.. 이건 제가 글로 설명을 못 하겠네요... 그림으로 최대한 잘 표현해보겠습니다.
아래에서 봐주세요

만약 4bit 이진수 A + B는 1010+1101이므로, 이진수의 덧셈 최종결과는
'10111' 이 되어야하지만, 4bit 연산 즉, 자리수는 4개에 대한 연산이기때문에,
1은 오버플로우되고, 0111이 되어야 합니다.

대충 이런 그림인데요..

순서대로 한번 가보겠습니다. 오른쪽 끝에 1이 있습니다.

(우측 상단에 있지만, 그림은 힘드네요... 다시 한번 사과드립니다.)

그리고 그전에 알아야될 개념이 있습니다.
XOR연산은 이미 아실테고,(인풋값이 서로 다를 때 1입니다.)
자리올림의 판별에 대한 다수결 함수가 있습니다.

위키 피디아에서 가져왔습니다.

불 논리에서 다수결 함수(majority function), 혹은 중앙값 연산자(median operator)는 입력되는 참의 개수가 n/2보다 크면 참, 아니면 거짓을 반환하는 n항 연산이다

입력되는 참의 개수가 n/2보다 크면 참, 아니면 거짓입니다.
이를 자리올림 판별(연사)에 사용할 수 있습니다.

다수결 함수와 XOR 연산만 있다면, 여러분도 충분히 하실 수 있습니다.
이후 전가산기에 대한 진리표를 보고 확인해보셔도 좋을 거 같습니다.

그리고, 수를 가져오는 것도 잘 봐주시면 좋을 거 같습니다.

// 1. 첫 번째 자리올림에 대한 연산이다. 처음엔 없으므로, 0이다.
// 2. 4번째 자리에 대한 A와 B의 XOR연산을 한다.
// 3. 두 값이 결과가 다르므로, S1은 참인 0을 가진다.
// 4. 자리 올림에 대한 연산인데, A1, B1, C0 에 대한 총 합은 1이고, n/2에 미치지 못하여 다수결함수에 의해서 C1은 0이다.
// 5. A2, B2에 대한 XOR연산을 한다.
// 5-1. 1,0 은 두 값이 다르므로 XOR연산에 의해서 참으로 결정되어 S2는 1이다.
// 6. A2, B2, C1의 합은 1이고, n/2에 미치지 못하여 다수결함수에 의해서 C2는 0이 된다.
// 7. A3, B3에 대한 XOR연산을 한다.
// 8. A3, B3은 두 값이 다르므로, XOR 연산에 의해서 참으로 결정되어 S3는 1이다.
// 9. A3, B3, C2의 합은 1이고, n/2에 미치지 못하여 다수결함수에 의해서 C3는 0이 된다.
// 10. A4, B4에 대한 XOR 연산을 한다.
// 11. A4, B4는 두 값이 동일한 1이므로, XOR연산에 의해서 S4는 0이된다.

(자리 올림 드뎌 나옴.)
// 12. A4, B4, C3의 합은 십진수로 2이다. n/2 보다 크므로, 다수결함수에 의해서 C4는 1이 된다

이 결론을 도출하면, S4=0, S3=1, S2=1, S1=1, 이고,

이 두수 1010, 1101에 대한 4bit 연산에 의한 값은 최종적으로 '0111' 입니다.

그런데, 아까 C4에서 1이 있었죠??

C4에 저장된 1을 쓰려면, 자리수가 더 있어야합니다.
즉 1을 어쩔 수 없이 버리게 되는데, 이는 오버플로우를 나타냅니다.

최종적인 그림은 다음과 같습니다.
(욕하지 마세요..)

3. 요약

지금까지 전가산기로 덧셈하는 방식을 살펴보았습니다.

XOR연산, 다수결 함수
이 두 가지의 개념만 알고 계신다면 충분히 이해하실 수 있을거 같습니다.

혹여 해보신다면,,
저는 이해를 나름하고 해서 4bit로 객기를 부려봤다만,
시작은 2bit부터 해보시면 좋을거 같습니다...!

CS가 부족하여 보고 있는데, 유익하고, 제가 모르는 게 너무나 많습니다.
여튼, 다음에도 좋은 발견을 가지고 포스팅하겠습니다.