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

尝试只用 Nand 来实现基础门，会更了解布尔代数的运算律。

Nand 的特别之处在于它本身已经带了否定，所以很多实现其实是在控制“什么时候多取一次反”。

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

HDL 没有循环，所以 16-bit chip 写起来会显得重复。但这种重复是有意义的：它把“位级逻辑”和“字级逻辑”之间的关系摊开了。一个 16-bit And 并不是新的运算，只是把同一个 1-bit And 同时应用到 16 条线上。

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 可以先两两 Or，再继续合并；Mux4Way16 可以先用低位 sel[0] 在每组里选，再用高位 sel[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.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);
}