[밑바닥부터] 6일차 - 2장 불 연산: 반가산기, 전가산기 구현

반가산기, 전가산기 구현

반가산기

1. 진리표

   a	b	carry	sum
   0	0	0	0
   1	0	0	1
   0	1	0	1
   1	1	1	0

• 진리표를 확인했을 때, carry는 and 연산이고 sum은 xor 연산임을 확인할 수 있다.

2. HDL

    CHIP HalfAdder {
        IN a, b;    // 1-bit inputs
        OUT sum,    // Right bit of a + b 
            carry;  // Left bit of a + b
   
        PARTS:
        And(a = a, b = b, out = carry);
        Xor(a = a, b = b, out = sum);
    }

전가산기

1. 진리표

   a	b	c	carry	sum
   0	0	0	0	0
   0	0	1	0	1
   0	1	0	0	1
   0	1	1	1	0
   1	0	0	0	1
   1	0	1	1	0
   1	1	0	1	0
   1	1	1	1	1

• 반가산기를 사용해서 구현해보자.
  a + b + c의 결과는 최대 3이 될 수 있다.
  00, 01, 10, 11 (2진수)
  그래서 왼쪽 비트는 MSB로 carry로 출력되고 오른쪽 비트는 LSB로 sum으로 출력된다.

2. HDL

    CHIP FullAdder {
        IN a, b, c;  // 1-bit inputs
        OUT sum,     // Right bit of a + b + c
            carry;   // Left bit of a + b + c
   
        PARTS:
        HalfAdder(a= a, b= b, sum= sumAB, carry= carryAB);
        HalfAdder(a= sumAB, b= c, sum= sum, carry= carryC);
        Or(a=carryAB, b= carryC, out=carry);
    }

   • 첫 번째 HalfAdder는 a와 b의 합을 구해서 LSB(sumAB), MSB(carryAB)를 계산한다.
   • 두 번째 HalfAdder는 sumAB와 c의 합의 LSB(최종 sum)과 MSB(carryC)를 계산한다.
     • HalfAdder는 두 개의 비트 입력을 받아서 sum(두 비트 합의 LSB)은 Xor 연산으로, carry(두 비트 합의 MSB)는 And 연산으로 얻을 수 있다.
     • sumAB = a Xor b이다.
       sumAB Xor C = a Xor b Xor c와 같다.
       ⇒ sum은 가장 낮은 자리수를 나타내므로, 1이 1개만 있어야 1이 될 수 있다.
       (당연히 1이 두 개면 0이 되고, 그 0과 1을 Xor 연산하면 1이 된다.)
     • carryC = sumAB And c이다.
       sumAB And c = (a Xor b) And c이다.
       1이 1개일 때, c와 1을 더하면 0이 되고 carry(자리 올림)가 발생한다.
   • 최종적으로 carry = carryAB Or carryC이다.
     • (a And B) Or ((a Xor b) And c)와 같다.
     • 이 식을 해석해보면 a와 b 모두 1일 때 carry가 발생하거나, a와 b중 하나만 1이고 c도 1일 때 carry가 발생한다.