01. Elementary Logic Gates

布尔代数

真值表表示法（Truth Table Representation）枚举所有可能的输入组合，然后写出每一种组合对应的输出。

x	y	z	f(x,y,z)
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

布尔表达式（Boolean Expression）输出变量用布尔算子（And, Or, Not）来描述，上述真值表可以用 $f(x,y,z)=(x+y)\cdot \bar{z}$ 来表示。

规范表示法（Canonical Representation）每个布尔函数都至少由一个布尔表达式来描述。找到真值表所有函数值为 1 的行，每一行用 And 连接，行与行之间用 Or 连接，就得到了 $f(x,y,z)=\bar{x}y\bar{z}+x\bar{y}\bar{z}+xy\bar{z}$。所以无论多复杂的布尔函数都可以用 And, Or, Not 来完全表达。

$Nand(x,y)=\overline{x\cdot y}$

$Nor(x,y)=\overline{x+y}$

$Xor(x,y)=x\cdot \bar{y}+\bar{x}\cdot y$

HDL

只有最简单的语法，没有循环和条件语句：

1. IN/OUT 定义输入输出引脚
2. PARTS 定义内部结构
3. 连线用 引脚名=信号名
4. 切片用 [start..end]
5. 两个特殊常量 true/false
6. 注释用 // 或 /*...*/
7. 禁止直接逻辑运算，禁止覆盖赋值，输入引脚只读

/* Xor.hdl, if a <> 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=a, b=notb, out=w1);
    And(a=nota, b=b, out=w2);
    Or(a=w1, b=w2, out=out);
}

Chip API

芯片名：  Nand
输入：    a,b
输出：    out
功能：    if a=b=1 then out=0 else out=1
说明：    此门是最基本的单元，不需要实现

芯片名：  Not
输入：    in
输出：    out
功能：    If in=0 then out=1 else out=0

芯片名：  And
输入：    a,b
输出：    out
功能：    If a=b=1 then out=1 else out=0

芯片名：  Or
输入：    a,b
输出：    out
功能：    If a=b=0 then out=0 else out=1

芯片名：  Xor
输入：    a,b
输出：    out
功能：    If a=/b then out=1 else out=0

芯片名：  Mux
输入：    a,b,sel
输出：    out
功能：    If sel=0 then out=a else out=b

芯片名：  DMux
输入：    in,sel
输出：    a,b
功能：    If sel=0 then {a=in, b=0} else {a=0, b=in}

芯片名：  Not16
输入：    in[16]  // 16-bit 管脚
输出：    out[16]
功能：    For i=0..15 out[i]=Not(in[i])

芯片名：  And16
输入：    a[16], b[16]
输出：    out[16]
功能：    For i=0..15 out[i]=And(a[i], b[i])

芯片名：  Or16
输入：    a[16], b[16]
输出：    out[16]
功能：    For i=0..15 out[i]=Or(a[i], b[i])

芯片名：  Mux16
输入：    a[16], b[16], sel
输出：    out[16]
功能：    If sel=0 then for i=0..15 out[i]=a[i]
         else for i=0..15 out[i]=b[i]

芯片名：  Or8Way
输入：    in[8]
输出：    out
功能：    out=Or(in[0], in[1],..., in[7])

芯片名：  Mux4Way16
输入：    a[16], b[16], c[16], d[16], sel[2]
输出：    out[16]
功能：    If sel=00 then out=a else if sel=01 then out=b
         else if sel=10 then out=c else if sel=11 then out=d

芯片名：  Mux8Way16
输入：    a[16], b[16], c[16], d[16], e[16], f[16], g[16], h[16], sel[3]
输出：    out[16]
功能：    If sel=000 then out=a else if sel=001 then out=b
         ... else if sel=111 then out=h

芯片名：  DMux4Way
输入：    in, sel[2]
输出：    a,b,c,d
功能：    If sel=00 then {a=in, b=c=d=0}
         else if sel=01 then {b=in, a=c=d=0}
         else if sel=10 then {c=in, a=b=d=0}
         else if sel=11 then {d=in, a=b=c=0}

芯片名：  DMux8Way
输入：    in, sel[3]
输出：    a,b,c,d,e,f,g,h
功能：    If sel=000 then {a=in, b=c=d=e=f=g=h=0}
         else if sel=001 then {b=in, a=c=d=e=f=g=h=0}
         ...
         else if sel=111 then {h=in, a=b=c=d=e=f=g=0}

基本运算律

类别	OR	AND
交换律	$a+b=b+a$	$a\cdot b=b\cdot a$
结合律	$a+(b+c)=(a+b)+c$	$a\cdot (b\cdot c)=(a\cdot b)\cdot c$
分配律	$a\cdot (b+c)=(a\cdot b)+(a\cdot c)$	$a+(b\cdot c)=(a+b)\cdot (a+c)$
幂等律	$a+a=a$	$a\cdot a=a$
吸收律	$a+(a\cdot b)=a$	$a\cdot (a+b)=a$
互补律	$a+\bar{a}=1$	$a\cdot \bar{a}=0$
同一律	$a+0=a$	$a\cdot 1=a$
零一律	$a+1=1$	$a\cdot 0=0$
双重否定律	$\overline{\stackrel{―}{a}}=a$	..

吸收律可以简单推导：

$a+(a\cdot b)=a\cdot 1+a\cdot b=a\cdot (1+b)=a\cdot 1=a$

$a\cdot (a+b)=a\cdot a+a\cdot b=a+(a\cdot b)=a$

De Morgan 定律

$$\begin{array}{rl}\overline{a+b}& =\bar{a}\cdot \bar{b}\text{(第一定律)}\\ \overline{a\cdot b}& =\bar{a}+\bar{b}\text{(第二定律)}\\ Not(a)& =\bar{a}=\overline{a\cdot a}\text{(a + a = a)}\\ And(a,b)& =a\cdot b=\overline{\stackrel{―}{a\cdot b}}\\ Or(a,b)& =a+b=\overline{\stackrel{―}{a}\cdot \stackrel{―}{b}}\\ Xor(a,b)& =a\cdot \bar{b}+\bar{a}\cdot b\\ & =a\cdot \bar{a}+a\cdot \bar{b}+\bar{a}\cdot b+b\cdot \bar{b}\\ & =a(\bar{a}+\bar{b})+b(\bar{a}+\bar{b})\\ & =a(\overline{a\cdot b})+b(\overline{a\cdot b})\\ & =\overline{\stackrel{―}{a(\stackrel{―}{a\cdot b})+b(\stackrel{―}{a\cdot b})}}\\ & =\overline{\stackrel{―}{a(\stackrel{―}{a\cdot b})}\cdot \stackrel{―}{b(\stackrel{―}{a\cdot b})}}\\ Mux(a,b,sel)& =a\cdot \overline{sel}+b\cdot sel\\ & =\overline{\stackrel{―}{a\cdot \stackrel{―}{sel}+b\cdot sel}}\\ & =\overline{\stackrel{―}{a\cdot \stackrel{―}{sel}}\cdot \stackrel{―}{b\cdot sel}}\\ Dmux(in,sel)\\ a& =in\cdot \overline{sel}=\overline{\stackrel{―}{in\cdot \stackrel{―}{sel}}}\\ b& =in\cdot sel=\overline{\stackrel{―}{in\cdot sel}}\end{array}$$

Project 01

A typical computer architecture is based on a set of elementary logic gates like And, Or, Mux, etc., as well as on their bitwise versions And16, Or16, Mux16, etc. (assuming a 16-bit machine). In this project you will build a typical set of basic logic gates. These gates form the elementary building blocks from which you will build the computer’s CPU and RAM chips in later projects.

Below we describe the tools, resources, and implementation tips needed for completing project 1.

Objective

Build the following chips (we use the terms chip and gate interchangeably):

Nand (given)
Not
And
Or
Xor
Mux
DMux
Not16
And16
Or16
Mux16
Or8Way
Mux4Way16
Mux8Way16
DMux4Way
DMux8Way

Since Nand is considered primitive, there is no need to implement it.

Implementation Tips

0. Before implementing a chip, it is recommended to experiment with its builtin implementation. If you are using the online simulator, simply click the builtin toggle; If you are using the desktop version, load the builtin chip from the tools/builtInChips folder.
1. Each chip can be implemented in more than one way. The simpler the implementation, the better. As a general rule, strive to use as few chip-parts as possible.
2. Although each chip can be implemented directly from Nand gates only, you can use any other chip from project 1 as a chip-part, as needed (see the previous tip).
3. There is no need to build “helper chips” of your own design. Your HDL programs should use only the chips listed in this project.
4. We recommend implementing the chips in the order in which they are listed. If, for some reason, you don’t complete the HDL implementation of some chip, you can still use it as a chip-part in other HDL programs. In the online simulator, the chip evaluation process uses builtin chip implementations, so there is no further ado. If you are using the desktop version, rename the chip file that you did not implement, or remove it from the project 1 folder. This will force the desktop simulator to use the chip’s builtin implementation.
5. Each chip can be tested interactively, or using a test script. In the online simulator, simply run the test script. In the desktop simulator, you must first load the chip’s test script, and then run it.

Solutions

Not.hdl

/**
 * Not gate:
 * if (in) out = 0, else out = 1
 */
CHIP Not {
    IN in;
    OUT out;

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

And.hdl

/**
 * And gate:
 * if (a and b) out = 1, else out = 0 
 */
CHIP And {
    IN a, b;
    OUT out;
    
    PARTS:
        Nand(a=a, b=b, out=w);
        Nand(a=w, b=w, out=out);
}

Or.hdl

/**
 * Or gate:
 * if (a or b) out = 1, else out = 0 
 */
CHIP Or {
    IN a, b;
    OUT out;

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

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:
        Nand(a=a, b=b, out=w);
        Nand(a=a, b=w, out=wa);
        Nand(a=b, b=w, out=wb);
        Nand(a=wa, b=wb, out=out);
}

Mux.hdl

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

    PARTS:
        Nand(a=sel, b=sel, out=nsel);
        Nand(a=a, b=nsel, out=wa);
        Nand(a=b, b=sel, out=wb);
        Nand(a=wa, b=wb, out=out);
}

DMux.hdl

/**
 * Demultiplexor:
 * [a, b] = [in, 0] if sel = 0
 *          [0, in] if sel = 1
 */
CHIP DMux {
    IN in, sel;
    OUT a, b;

    PARTS:
        Nand(a=sel, b=sel, out=nsel);
        Nand(a=in, b=nsel, out=wa);
        Nand(a=wa, b=wa, out=a);
        Nand(a=in, b=sel, out=wb);
        Nand(a=wb, b=wb, out=b);
}

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.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.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.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.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.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=ab);
        Mux16(a=c, b=d, sel=sel[0], out=cd);
        Mux16(a=ab, b=cd, sel=sel[1], out=out);
}

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:
        Mux4Way16(a=a, b=b, c=c, d=d, sel=sel[0..1], out=abcd);
        Mux4Way16(a=e, b=f, c=g, d=h, sel=sel[0..1], out=efgh);
        Mux16(a=abcd, b=efgh, sel=sel[2], out=out);
}

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=ab, b=cd);
        DMux(in=ab, sel=sel[0], a=a, b=b);
        DMux(in=cd, sel=sel[0], a=c, b=d);
}

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=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);
}