构建基础逻辑门

第1章 布尔逻辑

• 布尔代数

1. 如果我们断言“A和B都是真的”这句话是真的，那就表示A是真的，B也是真的。如果“A和B都是真的”是假的，那A和B中至少有一个是假的，用符号表示“A和B都是真的”就是：A and B 。

2. 如果我们断言“A或者B是真的”这句话是真的，那就表示A和B中至少有一个是真的。如果“A或者B是真的”这句话是假的，那就表示A和B没有一个是真的，即A和B都是假的。用符号表示“A或者B是真的”就是：A or B。

3. 我们常说的“不对”表示错，“不错”表示对。同样在逻辑世界也是很简单的，不真就一定假，这种“不”的逻辑让真和假可以转换，可以用符号not表示这种转换。

• 门逻辑

• HDL语言

构建计算机Hack所需要的16种芯片：

• Nand 门

• Not 门

Not(in) = Nand(in, in)

----Nand(a=in, b=in, out=out);----

• And 门

And(a, b) = Not(Nand(a, b)) = Nand(Nand(a, b), Nand(a, b))

---Nand(a=a, b=b, out=aNandB);Not(in=aNandB, out=out);---

• Or 门

Or(a, b) = Nand(Not(a), Not(b))

Not(in=a, out=notA);Not(in=b, out=notB);Nand(a=notA, b=notB, out=out);

• Xor 门

Xor(a, b) = Or(And(Not(a), b), And(a, Not(b)))

Not(in=a, out=notA);Not(in=b, out=notB);And(a=notA, b=b, out=w1);And(a=a, b=notB, out=w2);Or(a=w1, b=w2, out=out);

• Mux 门

Mux(a, b, sel) = Or(And(a, Not(sel)),And(b, sel))

Not(in=sel, out=notSel);And(a=a, b=notSel, out=w1);And(a=b, b=sel, out=w2);Or(a=w1, b=w2, out=out);

• DMux 门

a = And(in, Not(sel))b = And(in, sel)

Not(in=sel, out=notSel);And(a=in, b=notSel, out=a);And(a=in, b=sel, out=b);

• Not16 门

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 门

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 门

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 门

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(a=in[0], b=in[1], out=o1);Or(a=o1, b=in[2], out=o2);Or(a=o2, b=in[3], out=o3);Or(a=o3, b=in[4], out=o4);Or(a=o4, b=in[5], out=o5);Or(a=o5, b=in[6], out=o6);Or(a=o6, b=in[7], out=out);

• Mux4Way16 门

Mux16(a=a, b=b, sel=sel[0], out=o1);Mux16(a=c, b=d, sel=sel[0], out=o2);Mux16(a=o1, b=o2, sel=sel[1], out=out);

• Mux8Way16

Mux4Way16(a=a, b=b, c=c, d=d, sel=sel[0..1], out=o1);Mux4Way16(a=e, b=f, c=g, d=h, sel=sel[0..1], out=o2);Mux16(a=o1, b=o2, sel=sel[2], out=out);

• DMux4Way

DMux(in=in, sel=sel[1], a=d1, b=d2);DMux(in=d1, sel=sel[0], a=a, b=b);DMux(in=d2, sel=sel[0], a=c, b=d);

• DMux8Way

DMux(in=in, sel=sel[2], a=d1, b=d2);DMux4Way(in=d1, sel=sel[0..1], a=a, b=b, c=c, d=d);DMux4Way(in=d2, sel=sel[0..1], a=e, b=f, c=g, d=h);

第二章 布尔运算

• 二进制数

• 有符号二进制数

• 二进制加法

1. 我们可以先计算第一位，即A1+B1，然后得出当前位的和S1与进位C2。

2. C2需要与第二位上的两个数即A2，B2相加，所以现在我们需要计算三个一位二进制数的加法即计。

3. 我们可以先计算其中两位比如A2和B2，来得到一个和s2 与进位C3，然后用s2与C2相加得到当前位上最终的和S2（注意C3已经是更高位的数了，在当前位也就是第二位上就不用考虑它了），以及另一个进位C3’。

4. 按惯性思维来说，我们应该继续计算出C3与C3’的和与进位，来确定进位到底是多少，以及是否有可能会产生进位的进位。

5. 但是从实际来说，三个一位二进制数相加不可能产生进位的进位。可以观察上面的表格，如果进位为1，那和一定是0，而0再与另外任意一个一位二进制数相加进位都不可能为1。

6. 所以C3与C3’最多只有一个是1，它们的和可以简单的使用一个Or门来表示。

• 半加器

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

• 全加器

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:    // Put you code here:    HalfAdder(a=a, b=b, sum=s, carry=c1);    HalfAdder(a=s, b=c, sum=sum, carry=c2);    Or(a=c1, b=c2, out=carry);}

• 16位加法器

CHIP Add16 {    IN a[16], b[16];    OUT out[16];    PARTS:   // Put you code here:   FullAdder(a=a[0], b=b[0], c=false, sum=out[0], carry=c0);   FullAdder(a=a[1], b=b[1], c=c0, sum=out[1], carry=c1);   FullAdder(a=a[2], b=b[2], c=c1, sum=out[2], carry=c2);   FullAdder(a=a[3], b=b[3], c=c2, sum=out[3], carry=c3);   FullAdder(a=a[4], b=b[4], c=c3, sum=out[4], carry=c4);   FullAdder(a=a[5], b=b[5], c=c4, sum=out[5], carry=c5);   FullAdder(a=a[6], b=b[6], c=c5, sum=out[6], carry=c6);   FullAdder(a=a[7], b=b[7], c=c6, sum=out[7], carry=c7);   FullAdder(a=a[8], b=b[8], c=c7, sum=out[8], carry=c8);   FullAdder(a=a[9], b=b[9], c=c8, sum=out[9], carry=c9);   FullAdder(a=a[10], b=b[10], c=c9, sum=out[10], carry=c10);   FullAdder(a=a[11], b=b[11], c=c10, sum=out[11], carry=c11);   FullAdder(a=a[12], b=b[12], c=c11, sum=out[12], carry=c12);   FullAdder(a=a[13], b=b[13], c=c12, sum=out[13], carry=c13);   FullAdder(a=a[14], b=b[14], c=c13, sum=out[14], carry=c14);   FullAdder(a=a[15], b=b[15], c=c14, sum=out[15], carry=c15);}

• 增量器

CHIP Inc16 {    IN in[16];    OUT out[16];    PARTS:   // Put you code here:   Add16(a=in, b[1..15]=false, b[0]=true, out=out);}

• 算术逻辑单元ALU

CHIP ALU {    IN        x[16], y[16],  // 16-bit inputs        zx, // zero the x input?        nx, // negate the x input?        zy, // zero the y input?        ny, // negate the y input?        f,  // compute out = x + y (if 1) or x & y (if 0)        no; // negate the out output?    OUT        out[16], // 16-bit output        zr, // 1 if (out == 0), 0 otherwise        ng; // 1 if (out < 0),  0 otherwise    PARTS:   // Put you code here:   Mux16(a=x, b=false, sel=zx, out=xOrZero);   Mux16(a=y, b=false, sel=zy, out=yOrZero);   Not16(in=xOrZero, out=notXOrZero);   Not16(in=yOrZero, out=notYOrZero);   Mux16(a=xOrZero, b=notXOrZero, sel=nx, out=fX);   Mux16(a=yOrZero, b=notYOrZero, sel=ny, out=fY);   Add16(a=fX, b=fY, out=xAddy);   And16(a=fX, b=fY, out=xAndy);   Mux16(a=xAndy, b=xAddy, sel=f, out=andOradd);   Not16(in=andOradd, out=notAndOrAdd);   Mux16(a=andOradd, b=notAndOrAdd, sel=no, out=out, out[15]=ng,out[0..7]=lowOut, out[8..15]=highOut);   Or8Way(in=lowOut, out=lz);   Or8Way(in=highOut, out=hz);   Or(a=lz, b=hz, out=notZr);   Not(in=notZr, out=zr);}

第三章 时序逻辑

• 触发器

1. 如果AB都是1，那么Q1与Q2都是1。

2. 如果A是0，B是1，那么Q1是1，Q2是0。

3. 如果A是1，B是0，那么Q1是0，Q2是1。

4. 如果A是1，B是1，那么Q1还是Q1，Q2还是Q2，但是Q1与Q2一定相反。

1. 如果C1是0，那么D1被卡在最左边，C2是1但是没有什么用，它左边啥也没有，所以阀门C2左右两边信号再好它俩也没有好聊的。

2. 如果C1变成1，那么D1被传送到中间遇到了C2，而此时C2变成了0所以D1就老老实实呆在中间了。

3. 然后如果C1又变成0了，那么C2自然变成了1，所以D1最终通过了阀门C2。