[Truth Table] Design of Binary Adders

Block Diagram and Function of Binary Adder

이번 포스트에서는 2개의 unsigned 4bit 덧셈을 하는 parallel adder를 설계해 볼 것이다.
여기서 unsigned는 따로 sign bit를 사용하지 않는 것을 의미한다.
Sign bit의 내용은 이전 포스트 'Negative Numbers'를 참고하기 바란다.
쉽게 말하면 0을 포함한 양수계산을 하는 adder를 설계하는 것이다.

위 그림은 4-bit parallel adder의 대략적인 모습을 나타내고 있다.
이렇게 어떤 복잡한 system을 모두 표현하는 대신 block 형태로 간단히 표시하고
input과 output만을 표시한 것을 block diagram이라고 한다.

Block으로 들어가는 화살표는 input을 나타내고 있으며,
block에서 빠져나오는 화살표는 output을 나타낸다. 
여기서의 input은 A_0 ~ A_3, B_0 ~ B_3, C_0 이고, Output은 S_0 ~ S_3, C_4로 표시되어있다.

두 개의 숫자를 각각 A, B라고 놓았으며, 오른쪽의 숫자는 각각의 자리수를 나타낸다.
S_0 ~ S_3은 각 덧셈의 결과물이 되고, C_0는 carry in, C_4는 carry out 인데,
이에 대한 설명은 아래 그림을 보는것이 좋을 것 같다.

위 그림은 큰 block diagram을 다시 여러개의 작은 block diagram으로 쪼개놓은 것이다.
각각의 block diagram은 여기서는 full adder라는 이름을 갖고 있다.
Full adder는 '전가산기'라고 번역되는 것으로, 1자리 수 덧셈을 하고 결과(sum)과 올림수(carry)를 내보낸다.

Parallel 이라는 단어를 빼 놓고 설명한 이유는 여기에 있는데,
4개의 full adder가 병렬(parallel)로 연결되어있기 때문이다. 
여기서의 full adder는 subcircuit으로써, 모두 같은 동작을 하도록 해야 한다.
각각의 full adder는 3개의 input, 2개의 output을 가지고 있다.

위의 숫자는 1011 + 1011의 예를 보여주고 있다.
우리가 일반적으로 binary 덧셈을 계산하는것과 마찬가지로
우리는 작은 자리수부터 차례로 한자리씩 계산하고, carry를 윗자리로 보내고,
덧셈의 결과를 내보내는 계산을 한다. 

한가지 의문이 드는 것은 'end-around carry for 1's complement' 라고 되어있는 부분인데,
이를 이용하면 굳이 subtracter를 만들지 않아도 뺄셈 계산을 할 수 있다. 
먼저, End-around carry는 MSB에서 나온 carry를 의미한다.
이해를 위해서 먼저 10진수의 예를 생각해 보자.

우리는 567 - 345를 계산하고 싶다.
먼저 345의 nine's complement를 구해야 한다.
이전에는 나오지 않은 개념인데, 더해서 9를 만드는 어떤 수라고 생각하면 된다.
(2진수에서는 1's complement와 같다.)
이 경우에는 3자리 이므로 999가 되고, 구하고자 하는 수는 999 - 345 = 654 일 것이다.
그런 다음 567 + 654를 하면 1221이 된다. 천의 자리수가 1이 되었다.
이것이 위에서 말하는 end-around carry가 되어 다시 일의 자리에 더해지게 되는 것이다.
따라서 최종적으로 221 + 1 = 222, 즉 567 - 345의 결과를 얻게 된다.

마찬가지 예를 2진수에서 해보면, 1111 - 1000을 하고싶다고 하자.
1000의 1's complement는 0111이다.
1111 + 0111 = 10110 이고, 위에서 했던데로 end-around carry를 더하면,
우리가 원래 얻고자 하는 결과 0111을 얻는다.

(한편 2's complement를 사용하는 경우, end-around carry를 사용할 필요가 없다.)

대략적인 동작은 이렇게 이해하도록 하고, 이제 각각의 full adder에 대해서 truth table을 만들어 보자.

Truth Table and Its Equation

Truth table을 만드는 과정은 어려울 것이 없다.
모든 Input이 나올 combination, 즉 XYC_in = 000 에서부터 111까지의 8가지 경우에 대해
올림수가 발생하는지, 두 수의 합은 얼마인지를 결정하면 된다.

여기서 C_in은 carry in, C_out은 carry out을 의미하며,
C_in은 이전 full adder에서 온 carry 혹은 end-around carry를 의미하고,
C_out은 다음 full adder에게 전해줄 carry값을 나타낸다.

예를 들어, X와 Y가 1이고, carry도 1이라면,  1 + 1 + 1을 계산하는 꼴이 된다.
이 때에는 output은 11 이 되겠지만, 각 full adder는 한자리수 계산만을 하고
옆의 full adder로 올림수를 보내는 역할을 하도록 설계해야 하기 때문에 carry를 1을 만들어 주는 것이다.
즉, 이때의 output은 C_out = 1, Sum = 1 이 된다.

모든 경우에 대해 truth table은 위와 같이 만들 수 있다.
이제 해야할 것은 2개의 output을 기준으로 logic equation을 만들어 보면,

위와 같이 할 수 있다.
Block diagram 대신 XOR, AND, OR gate를 이용하면 full adder를 구현할 수 있게 되는 것이다.
실제 구현은 아래처럼 할 수 있다.

(만약 2's complement륵 사용하는 경우 첫번째 full adder는 C_in = 0 이므로, equation이 더 간단해진다.)

이러한 parallel binary adder는 숫자가 커질경우 매우 느려진다.
뒤에서 부터 차례로 계산해서 carry를 받고 또 다음 자리수를 계산하기 때문이다.
이를 개선하기 위해 나온 것이 carry-look-ahead adder 인데, 
다음의 링크를 참조하기 바란다: http://en.wikipedia.org/wiki/Carry-lookahead_adder

Overflow

Overflow는 signed binary number를 더할 때 발생한다.
예를 들어 4bit signed binary number의 계산을 한다고 하자.
MSB는 sign bit로 사용되기 때문에, 예를 들어 0100 + 0100 을 하게 되면
full adder는 1000 이라는 결과를 내보낼 것이다.
하지만 full adder에서 1000은 -8을 의미한다. 4 + 4 = -8 이라는 엉뚱한 결과가 나오게 되는 것이다.
이런 현상을 overflow라고 한다.

overflow는 더해지는 두 숫자 A, B의 MSB가 같고, 결과로 나오는 숫자의 MSB와 다를 때 발생한다.
즉, A_3 = 1, B_3 = 1, S_3 = 0 일때 발생하거나, A_3 = 0, B_3 = 0, S_3 = 1 일때 발생한다.
이를 equation으로 나타내면, overflow를 V로 나타낼때,

다음과 같이 할 수 있다.

이를 이용하여 맨 위의 그림에 V 라는 output을 만들고, A_3, B_3, S_3의 input을 받아
AND, OR gate를 이용해 overflow가 발생했는지 검출하는 기능을 추가할 수 있다.