[밑바닥부터] 3일차 - 1장 불 논리: 프로젝트

프로젝트

목표

1장에서 소개된 모든 논리 게이트를 구현한다. Nand 게이트를 조합해서 만들되, 밑바닥부터 만든 게이트들만 활용할 수 있다.

자료

NAND2Tetris 웹 IDE로 접속해서 HDL로 논리 게이트 코드를 작성하고 테스트해볼 수 있다.

팁

• 게이트마다 여러 방식으로 구현할 수 있으므로, 가능한 적은 수의 파트를 사용해서 단순하게 구현할 수 있도록 생각해보자.
• Builtin 토글을 활성화시키면 내장되어 있는 논리 게이트를 불러온다.
  당장 Not 게이트를 구현하지 못했어도 내장된 Not을 가져와서 다른 AND나 OR 등 여러 게이트를 구현할 수 있다.

하드웨어 구현 정리

이전 학습 정리에서 논리 게이트를 어떻게 구현할 지 작성했었다.
그 내용을 토대로 직접 1장에 나왔던 모든 논리 게이트를 구현하고 제대로 동작하는지 테스트해보자.

Nand 게이트는 이미 구현되어 있다고 가정했기 때문에 Nand 게이트를 기반으로 나머지를 모두 구현한다.

Not

CHIP Not {    
    IN in;    
    OUT out;
    PARTS:    
        Nand(a=in, b=in, out=out);
}

And

CHIP And {    
    IN a, b;    
    OUT out;        
    PARTS:    
        Nand(a=a, b=b, out=result);    
        Not(in=result, out=out);
}

Or

CHIP Or {    
    IN a, b;    
    OUT out;
    PARTS:    
        Not(in=a, out=nota);    
        Not(in=b, out=notb);    
        Nand(a=nota, b=notb, out=out);
}

Xor

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Xor.hdl

/**
 * Exclusive-or gate:
 * if ((a and Not(b)) or (Not(a) and b)) out = 1, else out = 0
 */
CHIP Xor {
    IN a, b;
    OUT out;

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

Mux

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Mux.hdl

/**
 * Multiplexor:
 * if (sel = 0) out = a, else out = b
 */
CHIP Mux {
    IN a, b, sel;
    OUT out;

    PARTS:
        Not(in=sel, out=notSel);
        And(a=a, b=notSel, out=aAndNotSel);
        And(a=b, b=sel, out=bAndSel);
        Or(a=aAndNotSel, b=bAndSel, out=out);
}

DMux

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/DMux.hdl

/**
 * Demultiplexor:
 * [a, b] = [in, 0] if sel = 0
 *          [0, in] if sel = 1
 */
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

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Not16.hdl

/**
 * 16-bit Not gate:
 * for i = 0, ..., 15:
 * out[i] = Not(a[i])
 */
CHIP Not16 {
    IN in[16];
    OUT out[16];

    PARTS:
        Not(in=in[0], out=out[0]);
        Not(in=in[1], out=out[1]);
        Not(in=in[2], out=out[2]);
        Not(in=in[3], out=out[3]);
        Not(in=in[4], out=out[4]);
        Not(in=in[5], out=out[5]);
        Not(in=in[6], out=out[6]);
        Not(in=in[7], out=out[7]);
        Not(in=in[8], out=out[8]);
        Not(in=in[9], out=out[9]);
        Not(in=in[10], out=out[10]);
        Not(in=in[11], out=out[11]);
        Not(in=in[12], out=out[12]);
        Not(in=in[13], out=out[13]);
        Not(in=in[14], out=out[14]);
        Not(in=in[15], out=out[15]);
}

And16

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/And16.hdl

/**
 * 16-bit And gate:
 * for i = 0, ..., 15:
 * out[i] = a[i] And b[i]
 */
CHIP And16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
        And(a=a[0], b=b[0], out=out[0]);
        And(a=a[1], b=b[1], out=out[1]);
        And(a=a[2], b=b[2], out=out[2]);
        And(a=a[3], b=b[3], out=out[3]);
        And(a=a[4], b=b[4], out=out[4]);
        And(a=a[5], b=b[5], out=out[5]);
        And(a=a[6], b=b[6], out=out[6]);
        And(a=a[7], b=b[7], out=out[7]);
        And(a=a[8], b=b[8], out=out[8]);
        And(a=a[9], b=b[9], out=out[9]);
        And(a=a[10], b=b[10], out=out[10]);
        And(a=a[11], b=b[11], out=out[11]);
        And(a=a[12], b=b[12], out=out[12]);
        And(a=a[13], b=b[13], out=out[13]);
        And(a=a[14], b=b[14], out=out[14]);
        And(a=a[15], b=b[15], out=out[15]);
}

Or16

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Or16.hdl

/**
 * 16-bit Or gate:
 * for i = 0, ..., 15:
 * out[i] = a[i] Or b[i]
 */
CHIP Or16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
        Or(a=a[0], b=b[0], out=out[0]);
        Or(a=a[1], b=b[1], out=out[1]);
        Or(a=a[2], b=b[2], out=out[2]);
        Or(a=a[3], b=b[3], out=out[3]);
        Or(a=a[4], b=b[4], out=out[4]);
        Or(a=a[5], b=b[5], out=out[5]);
        Or(a=a[6], b=b[6], out=out[6]);
        Or(a=a[7], b=b[7], out=out[7]);
        Or(a=a[8], b=b[8], out=out[8]);
        Or(a=a[9], b=b[9], out=out[9]);
        Or(a=a[10], b=b[10], out=out[10]);
        Or(a=a[11], b=b[11], out=out[11]);
        Or(a=a[12], b=b[12], out=out[12]);
        Or(a=a[13], b=b[13], out=out[13]);
        Or(a=a[14], b=b[14], out=out[14]);
        Or(a=a[15], b=b[15], out=out[15]);
}

Mux16

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Mux16.hdl

/**
 * 16-bit multiplexor:
 * for i = 0, ..., 15:
 * if (sel = 0) out[i] = a[i], else out[i] = b[i]
 */
CHIP Mux16 {
    IN a[16], b[16], sel;
    OUT out[16];

    PARTS:
        Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
        Mux(a=a[1], b=b[1], sel=sel, out=out[1]);
        Mux(a=a[2], b=b[2], sel=sel, out=out[2]);
        Mux(a=a[3], b=b[3], sel=sel, out=out[3]);
        Mux(a=a[4], b=b[4], sel=sel, out=out[4]);
        Mux(a=a[5], b=b[5], sel=sel, out=out[5]);
        Mux(a=a[6], b=b[6], sel=sel, out=out[6]);
        Mux(a=a[7], b=b[7], sel=sel, out=out[7]);
        Mux(a=a[8], b=b[8], sel=sel, out=out[8]);
        Mux(a=a[9], b=b[9], sel=sel, out=out[9]);
        Mux(a=a[10], b=b[10], sel=sel, out=out[10]);
        Mux(a=a[11], b=b[11], sel=sel, out=out[11]);
        Mux(a=a[12], b=b[12], sel=sel, out=out[12]);
        Mux(a=a[13], b=b[13], sel=sel, out=out[13]);
        Mux(a=a[14], b=b[14], sel=sel, out=out[14]);
        Mux(a=a[15], b=b[15], sel=sel, out=out[15]);
}

Or8Way

Or8Way 게이트를 만들면서 게이트 구현 방법이 여러가지임을 체감했다.
아래는 첫 번째로 만든 HDL 코드이다.

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Or8Way.hdl

/**
 * 8-way Or gate:
 * out = in[0] Or in[1] Or ... Or in[7]
 */
CHIP Or8Way {
    IN in[8];
    OUT out;

    PARTS:
        Or(a=in[0], b=in[1], out=temp1);
        Or(a=temp1, b=in[2], out=temp2);
        Or(a=temp2, b=in[3], out=temp3);
        Or(a=temp3, b=in[4], out=temp4);
        Or(a=temp4, b=in[5], out=temp5);
        Or(a=temp5, b=in[6], out=temp6);
        Or(a=temp6, b=in[7], out=out);
}

앞의 결과를 가져오는 Cascade 방식으로 구현해서 직관적으로는 가장 쉽게 떠올릴 수 있다.

그러나 비효율적이다. 2개씩 묶어서 결과를 만들어내고 그 결과를 다시 2개씩 묶어서 반복하면 8개의 입력이 들어올 때 지연시간이 3단계로 줄어든다.
기존은 앞선 결과가 먼저 선행되어야 하기 때문에 지연시간이 7단계이다.

개선한 코드는 다음과 같다.

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Or8Way.hdl

/**
 * 8-way Or gate:
 * out = in[0] Or in[1] Or ... Or in[7]
 */
CHIP Or8Way {
    IN in[8];
    OUT out;

    PARTS:
        Or(a=in[0], b=in[1], out=or01);
        Or(a=in[2], b=in[3], out=or23);
        Or(a=in[4], b=in[5], out=or45);
        Or(a=in[6], b=in[7], out=or67);

        Or(a=or01, b=or23, out=or0123);
        Or(a=or45, b=or67, out=or4567);

        Or(a=or0123, b=or4567, out=out);
}

Mux4Way16

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Mux4Way16.hdl

/**
 * 4-way 16-bit multiplexor:
 * out = a if sel = 00
 *       b if sel = 01
 *       c if sel = 10
 *       d if sel = 11
 */
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=abOut);
        Mux16(a=c, b=d, sel=sel[0], out=cdOut);

        Mux16(a=abOut, b=cdOut, sel=sel[1], out=out);
}

Mux8Way16

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Mux8Way16.hdl

/**
 * 8-way 16-bit multiplexor:
 * out = a if sel = 000
 *       b if sel = 001
 *       c if sel = 010
 *       d if sel = 011
 *       e if sel = 100
 *       f if sel = 101
 *       g if sel = 110
 *       h if sel = 111
 */
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:
        Mux16(a=a, b=b, sel=sel[0], out=abOut);
        Mux16(a=c, b=d, sel=sel[0], out=cdOut);
        Mux16(a=e, b=f, sel=sel[0], out=efOut);
        Mux16(a=g, b=h, sel=sel[0], out=ghOut);

        Mux16(a=abOut, b=cdOut, sel=sel[1], out=abcdOut);
        Mux16(a=efOut, b=ghOut, sel=sel[1], out=efghOut);

        Mux16(a=abcdOut, b=efghOut, sel=sel[2], out=out);
}

DMux4Way

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/DMux4Way.hdl

/**
 * 4-way demultiplexor:
 * [a, b, c, d] = [in, 0, 0, 0] if sel = 00
 *                [0, in, 0, 0] if sel = 01
 *                [0, 0, in, 0] if sel = 10
 *                [0, 0, 0, in] if sel = 11
 */
CHIP DMux4Way {
    IN in, sel[2];
    OUT a, b, c, d;

    PARTS:
        DMux(in=in, sel=sel[1], a=temp1, b=temp2);
        DMux(in=temp1, sel=sel[0], a=a, b=b);
        DMux(in=temp2, sel=sel[0], a=c, b=d);
}

DMux8Way

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/DMux8Way.hdl

/**
 * 8-way demultiplexor:
 * [a, b, c, d, e, f, g, h] = [in, 0,  0,  0,  0,  0,  0,  0] if sel = 000
 *                            [0, in,  0,  0,  0,  0,  0,  0] if sel = 001
 *                            [0,  0, in,  0,  0,  0,  0,  0] if sel = 010
 *                            [0,  0,  0, in,  0,  0,  0,  0] if sel = 011
 *                            [0,  0,  0,  0, in,  0,  0,  0] if sel = 100
 *                            [0,  0,  0,  0,  0, in,  0,  0] if sel = 101
 *                            [0,  0,  0,  0,  0,  0, in,  0] if sel = 110
 *                            [0,  0,  0,  0,  0,  0,  0, in] if sel = 111
 */
CHIP DMux8Way {
    IN in, sel[3];
    OUT a, b, c, d, e, f, g, h;

    PARTS:
        DMux(in=in, sel=sel[2], a=temp1, b=temp2);
        DMux(in=temp1, sel=sel[1], a=tempAB, b=tempCD);
        DMux(in=temp2, sel=sel[1], a=tempEF, b=tempGH);
        DMux(in=tempAB, sel=sel[0], a=a, b=b);
        DMux(in=tempCD, sel=sel[0], a=c, b=d);
        DMux(in=tempEF, sel=sel[0], a=e, b=f);
        DMux(in=tempGH, sel=sel[0], a=g, b=h);
}

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

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

이렇게 DMux4Way 게이트를 활용해서 구현할 수도 있다.

작성한 HDL 파일:

01.zip

11.4 kB