Nand2Tetris week-2

Boolean Arithmetic and the ALU

hdl-survival-guide

写HDL时可能出现的问题

本周的ALU代码部分比较复杂，也需要不少技巧性。我在犯错后，也在论坛上浏览不少，总结一下容易犯的错误。

1. 不知道”多重输出“（Multiple Outputs），也就是可以有多个out，输出给不同的寄存器，而且这些寄存器往往只能使用一次。似乎存储结果的out，是不可以被使用的。
2. ”子数据线“（sub-busing）下标问题，常见的有两个，一是中间变量不能使用sub-busing，也就是说，不能使用something[a..b]这个格式；第二就是这个子数据线只能放在左边，不能在右边。

Sub-bussing (indexing) internal pins: Is not permitted. The only bus-pins that can be indexed are the input and output pins of the implemented chip, or the input and output pins of its chip-parts. However, there is a workaround for sub-bussing internal bus-pins. To motivate the workaround, here is an example that doesn’t work: ```verilog CHIP Foo {

IN in[16];

OUT out;

PARTS:

Not16 (in=in, out=notIn);

Or8Way (in=notIn[4..11], out=out); // Error: internal bus cannot be indexed.

}

> Possible fix, using the workaround:
> ```verilog
Not16 (in=in, out[4..11]=notIn);
 Or8Way (in=notIn, out=out); // Works!

作业顺序

半加器 HalfAdder

半加器的真值表

观察真值表，可以得出

sum = a xor b和carry = a and b

全加器 FullAdder

全加器真值表

// 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/02/FullAdder.hdl

/**
 * Computes the sum of three bits.
 */

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=lowbit, carry=tmp1);
    HalfAdder(a=lowbit, b=c, sum=sum, carry=tmp2);
    Or(a=tmp1, b=tmp2, out=carry);
}

16位全加器 Add16

我不太清楚，中间变量只能使用一次？

FullAdder(a=a[1], b=b[1], c=tmp, sum=out[1], carry=tmp1);的写法就出错？

// 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/02/Adder16.hdl

/**
 * Adds two 16-bit values.
 * The most significant carry bit is ignored.
 */

CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
   // Put you code here:
   HalfAdder(a=a[0], b=b[0], sum=out[0], carry=tmp);
//    halfAdder(a=a[0], b=[0], c=false, sum=out[0], carry=tmp);
   FullAdder(a=a[1], b=b[1], c=tmp, sum=out[1], carry=tmp1);
   FullAdder(a=a[2], b=b[2], c=tmp1, sum=out[2], carry=tmp2);
   FullAdder(a=a[3], b=b[3], c=tmp2, sum=out[3], carry=tmp3);
   FullAdder(a=a[4], b=b[4], c=tmp3, sum=out[4], carry=tmp4);
   FullAdder(a=a[5], b=b[5], c=tmp4, sum=out[5], carry=tmp5);
   FullAdder(a=a[6], b=b[6], c=tmp5, sum=out[6], carry=tmp6);
   FullAdder(a=a[7], b=b[7], c=tmp6, sum=out[7], carry=tmp7);
   FullAdder(a=a[8], b=b[8], c=tmp7, sum=out[8], carry=tmp8);
   FullAdder(a=a[9], b=b[9], c=tmp8, sum=out[9], carry=tmp9);
   FullAdder(a=a[10], b=b[10], c=tmp9, sum=out[10], carry=tmp10);
   FullAdder(a=a[11], b=b[11], c=tmp10, sum=out[11], carry=tmp11);
   FullAdder(a=a[12], b=b[12], c=tmp11, sum=out[12], carry=tmp12);
   FullAdder(a=a[13], b=b[13], c=tmp12, sum=out[13], carry=tmp13);
   FullAdder(a=a[14], b=b[14], c=tmp13, sum=out[14], carry=tmp14);
   FullAdder(a=a[15], b=b[15], c=tmp14, sum=out[15], carry=tmp15);
}

16位增量器 Inc16

我也没接触过数字电路，也不知道是不是对应这个名字。

原来输入的“数组”，可以根据下标进行拆分。

// 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/02/Inc16.hdl

/**
 * 16-bit incrementer:
 * out = in + 1 (arithmetic addition)
 */

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分值太高。

算术逻辑单元 ALU

主要就是思考如何实现if，使用Mux选择器，进行选择。

说明：ALU占据的分值最大，不提交最多只能得66分，并不能通过（75分）。

设计逻辑不算难，特别是许多东西能用C语言想到，就考虑如何转化成HDL。

我的错误就在下面标注的两行：

mark1：没有注意到这个“多重输出”，我在后面想直接使用out作为下一步的计算，但是总是提示

error massage: can’t connect gate’s output pin to part

但不幸的是，我的屏幕太小了，刚好看不到下面的错误信息，并且这个软件有个致命缺陷！你缩小它，仅仅是调小了窗口，内容不变小，因此也看不到下面！

最后我通过把任务栏移动到左边，勉强看到一点红色的错误信息，还需要把光标放在上面，通过光标的小窗口才看得到。

mark2：这个错误可能是重写时，无意犯的错误。也就导致了没有通过案例，test会在输出的那一行停下来，仔细对比一下正确输出和自己的输出，看看哪里可能出现问题。

我的错误是，mark2处，b参数填错了，错误的写成了false。

And16(a=sign, b=false, out[0..7]=out1, out[8..15]=out2);

应当注意，如果想要选取一部分，需要与全1进行与运算。

Multiple Outputs

Sometimes you need more than one sub-bus connected to the output of a chip-part. Simply add more than one out= connection to the chip-part definition.

    CHIP Foo {
       IN in[16];
       OUT out[8];
       PARTS:
           Not16 (in=in, out[0..7]=low8, out[8..15]=high8);
           Something8 (a=low8, b=high8, out=out);
    }

This also works if you want to use an output of a chip in further computations.

    CHIP Foo {
    IN a, b, c;
    OUT out1, out2;
    PARTS:
       Something (a=a, b=b, out=x, out=out1);
       Whatever (a=x, b=c, out=out2);
    }

// 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/02/ALU.hdl

/**
 * The ALU (Arithmetic Logic Unit).
 * Computes one of the following functions:
 * x+y, x-y, y-x, 0, 1, -1, x, y, -x, -y, !x, !y,
 * x+1, y+1, x-1, y-1, x&y, x|y on two 16-bit inputs, 
 * according to 6 input bits denoted zx,nx,zy,ny,f,no.
 * In addition, the ALU computes two 1-bit outputs:
 * if the ALU output == 0, zr is set to 1; otherwise zr is set to 0;
 * if the ALU output < 0, ng is set to 1; otherwise ng is set to 0.
 */

// Implementation: the ALU logic manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) set x = 0        // 16-bit constant
// if (nx == 1) set x = !x       // bitwise not
// if (zy == 1) set y = 0        // 16-bit constant
// if (ny == 1) set y = !y       // bitwise not
// if (f == 1)  set out = x + y  // integer 2's complement addition
// if (f == 0)  set out = x & y  // bitwise and
// if (no == 1) set out = !out   // bitwise not
// if (out == 0) set zr = 1
// if (out < 0) set ng = 1

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=x1);
    Not16(in=x1, out=notx);
    Mux16(a=x1, b=notx, sel=nx, out=x2);

    Mux16(a=y, b=false, sel=zy, out=y1);
    Not16(in=y1, out=noty);
    Mux16(a=y1, b=noty, sel=ny, out=y2);

    Add16(a=x2, b=y2, out=xaddy);
    And16(a=x2, b=y2, out=xandy);
    Mux16(a=xandy, b=xaddy, sel=f, out=out0);

    Not16(in=out0, out=notout);
    Mux16(a=out0, b=notout, sel=no, out=out, out=sign, out[15]=flag); //mark1
    /*
    notes: the out can't be used
    error massage: can't connect gate's output pin to part
    */
    And16(a=sign, b=true, out[0..7]=out1, out[8..15]=out2); //mark2
    Or8Way(in=out1, out=st1);
    Or8Way(in=out2, out=st2);
    Or(a=st1, b=st2, out=st);
    Mux(a=true, b=false, sel=st, out=zr);

    Mux(a=false, b=true, sel=flag, out=ng);
}

作业提交

总结

许多错误，巧就巧在撞在了一起。

屏幕小，看不到错误信息，之前都是瞎调，刚好比较容易也没当回事，这次ALU错误猜了好久耽误了时间。

外加不熟悉HDL，很多写法也不知道是否规范。索性最后还是顺利解决了。

还有一个问题，就是对昨天写的很多东西，光看名字确实容易忘、混淆，需要去看一下API和作用。