NAND to Tetris - 1장: 조합 게이트 실습

지난 글에서 정의한 게이트 인터페이스들을 하나씩 직접 구현해보자.

 

Not

Not 게이트는 Nand 게이트 하나만으로 구현할 수 있다. x Nand x는 Not (x And x)이고, x And x는 x와 같으므로 x Nand x는 Not x와 같다.

 

CHIP Not {
    IN in;
    OUT out;

    PARTS:
    Nand(a=in, b=in, out=out);
}

 

And

And 게이트는 단순히 Nand 게이트의 결과를 뒤집으면 된다. Not 게이트는 위에서 만든 것을 가져다 쓴다.

 

CHIP And {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a, b=b, out=aNandb);
    Not(in=aNandb, out=out);
}

 

Or

드 모르간의 법칙: A Or B = Not (Not A And Not B)을 이용한다. Not과 And 게이트를 이미 만들었으니 Or 게이트도 구현할 수 있다.

 

CHIP Or {
    IN a, b;
    OUT out;

    PARTS:
    Not(in=a, out=nota);
    Not(in=b, out=notb);
    And(a=nota, b=notb, out=notaandnotb);
    Not(in=notaandnotb, out=out);
}

 

Xor

Xor 게이트를 정준 표현으로 나타내면 (Not x And y) Or (x And Not y)이다. Not, And, Or 게이트를 모두 만들었으니 Xor 게이트도 만들 수 있다.

 

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    Not(in=a, out=nota);
    Not(in=b, out=notb);
    And(a=nota, b=b, out=notaandb);
    And(a=a, b=notb, out=aandnotb);
    Or(a=notaandb, b=aandnotb, out=out);
}

 

Mux

Mux 는 out이 1이 되는 4개의 행을 Or로 합치는 정준 표현으로도 나타낼 수 있지만, 이것보다 더 간단한 방법으로 구현해보겠다. 

(Not sel And x) Or (sel And y)는 sel이 0인 경우엔 오른쪽 항은 항상 0이 되어 무시되고 왼쪽 항은 x가 1일 때 1, 0일 때 0을 반환하므로, 즉 x와 값이 같아진다. 반대로 sel이 1인 경우엔 왼쪽 항은 항상 0이 되어 무시되고 오른쪽 항은 y가 1일 때 1, 0일 때 0을 반환하므로, 즉 y와 값이 같아진다. 

 

CHIP Mux {
    IN a, b, sel;
    OUT out;

    PARTS:
    Not(in=sel, out=notsel);
    And(a=a, b=notsel, out=sela);
    And(a=b, b=sel, out=selb);
    Or(a=sela, b=selb, out=out);
}

 

Dmux

Dmux는 정준 표현으로 깔끔하게 구현할 수 있다. 출력선 a의 반환 값이 1이 되는 경우는 (Not sel And in)이고, 출력선 b의 반환 값이 1이 되는 경우는 (sel And in)이다. 

 

CHIP DMux {
    IN in, sel;
    OUT a, b;

    PARTS:
    Not(in=sel, out=notsel);
    And(a=in, b=notsel, out=a);
    And(a=in, b=sel, out=b);
}

 

Not16, And16, Or16, Mux16

이 게이트들은 단순히 0번부터 15번 비트까지 총 16개의 1비트 게이트를 구성하면 된다. 코드가 단순하고 길기 때문에 생략하겠다.

 

Or8Way

두 비트씩 Or 게이트를 만들어 나가면 된다.

 

CHIP Or8Way {
    IN in[8];
    OUT out;

    PARTS:
    Or(a=in[0], b=in[1], out=out1);
    Or(a=out1, b=in[2], out=out2);
    Or(a=out2, b=in[3], out=out3);
    Or(a=out3, b=in[4], out=out4);
    Or(a=out4, b=in[5], out=out5);
    Or(a=out5, b=in[6], out=out6);
    Or(a=out6, b=in[7], out=out);
}

 

Mux4Way16

우선은 (a, b, sel[0])와 (c, d, sel[0]) 쌍에 대해서 각각 Mux16을 계산하여 out1, out2으로 반환해보자. sel[0]의 값에 따라 out1과 out2는 각각 a 또는 b, c 또는 d의 값을 가진다. (sel[0]이 0이라면 out1 = a, out2 = c, sel[0]이 1이라면 out1 = b, out2 = d) 그리고 (out1, out2, sel[1])에 대해 다시 Mux16을 계산하여 out으로 반환한다. 그러면 sel[1]의 값에 따라 out1과 out2 중에 적절한 값이 반환될 것이다. (sel[1]이 0이면 out = out1, sel[1]이 1이라면 out = out2)

 

CHIP Mux4Way16 {
    IN a[16], b[16], c[16], d[16], sel[2];
    OUT out[16];

    PARTS:
    Mux16(a=a, b=b, sel=sel[0], out=out0);
    Mux16(a=c, b=d, sel=sel[0], out=out1);
    Mux16(a=out0, b=out1, sel=sel[1], out=out);
}

 

Mux8Way16

Mux16으로 Mux4Way16을 만들었던 것 처럼 Mux4Way16 으로 만들 수 있다.

 

CHIP Mux8Way16 {
    IN a[16], b[16], c[16], d[16],
       e[16], f[16], g[16], h[16],
       sel[3];
    OUT out[16];

    PARTS:
    Mux4Way16(a=a, b=b, c=c, d=d, sel=sel[0..1], out=out0);
    Mux4Way16(a=e, b=f, c=g, d=h, sel=sel[0..1], out=out1);
    Mux16(a=out0, b=out1, sel=sel[2], out=out);
}

 

DMux4Way

DMux4Way 구현은 Mux4Way16의 구현과 반대 순서이다. 

 

CHIP DMux4Way {
    IN in, sel[2];
    OUT a, b, c, d;

    PARTS:
    // sel[1]이 0이면 in1 = in, in2 = 0 이고
    // sel[1]이 1이면 in1 = 0, in2 = in
    DMux(in=in, sel=sel[1], a=in1, b=in2);
    
    // sel[0] 값에 따라 다시 DMux
    DMux(in=in1, sel=sel[0], a=a, b=b);
    DMux(in=in2, sel=sel[0], a=c, b=d);    
}

 

DMux8Way

DMux로 DMux4Way를 만들었던 것 처럼 DMux4Way로 만들 수 있다.

 

CHIP DMux8Way {
    IN in, sel[3];
    OUT a, b, c, d, e, f, g, h;

    PARTS:
    DMux(in=in, sel=sel[2], a=in1, b=in2);
    DMux4Way(in=in1, sel=sel[0..1], a=a, b=b, c=c, d=d);
    DMux4Way(in=in2, sel=sel[0..1], a=e, b=f, c=g, d=h);
}

 

마무리

1비트 Nand 게이트 하나에서 시작하여 총 15개의 조합 회로를 직접 구현해봤다. 아직까지는 간단한 불 연산밖에 안되지만, 이번에 만든 것들을 사용하여 다음 장에서는 이진 덧셈을 하는 회로를 만들 예정이다.