从0到1构建计算机(3/12)--组合逻辑芯片：逻辑门、加法器、ALU

上篇说到：通过使用Nand门，我们可以实现任何逻辑门，进而实现可以一个CPU。后面我们就会搭建一个麻雀虽小但五脏俱全的计算机平台：hack。本篇我们开始第一步，实现搭建hack所需的一组芯片：组合逻辑芯片

组合逻辑芯片

一个最基本的CPU主要由两类芯片组成：

组合逻辑芯片（Combinational Chips）：与、或、非门，加法器，ALU芯片等。这些芯片主要负责逻辑计算
时序芯片（Sequential Chips）：寄存器，计数器，RAM等。这些芯片主要负责暂存数据

组合逻辑芯片（下面简称逻辑芯片）可以类比为一个布尔函数，它仅负责处理逻辑运算：输出结果仅依赖于其输入变量的排列组合。逻辑芯片是没有记忆能力的，它们不能维持自身的状态，当逻辑芯片的输入值改变的时候，它们的输出值也会实时地改变。

hack所需要的逻辑芯片有以下四种：基本逻辑门、多通道逻辑门、加法器、ALU（算数逻辑单元）。

基本逻辑门

基本逻辑门是一些简单的布尔函数的实现，我们需要的基本逻辑门如下，有1位和多位（16位）之分。

芯片列表

我们所有组合逻辑芯片都是基于Nand实现的，下面是Nand的真值表：只有当两个输入都为1时输出为0，其余输出为1反，然后输出。

Nand真值表

首先我们用Nand实现一个Not。Not很简单，对其输入取反，然后输出。下面是我自己的实现方式：

Not电路图

HDL实现：硬件描述语言实现。

/**
 * Not HDL实现
 * Not gate:
 * out = not in
 */

CHIP Not {
    IN in;
    OUT out;

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

然后我们继续用刚刚实现的Not和Nand组合使用，再实现一个And。

And电路图

/**
 * And gate: 
 * out = 1 if (a == 1 and b == 1)
 *       0 otherwise
 */

CHIP And {
    IN a, b;
    OUT out;

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

多位基本逻辑门是1位基本逻辑门的简单组合，以16位And为例，用16个1位And组合成16位And.

/**
 * 16-bit bitwise And:
 * 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]);
}

以此类推，我们可以一步步实现其他所有基本逻辑门。

加法器

有了上面实现的这些基本逻辑门，我们就可以实现CPU中一个非常重要的基本芯片：加法器。实现加法器的顺序是：半加器->全加器->16位加法器

芯片列表

第一步：实现一个半加器，半加器负责计算两个一位二进制相加，输出sum和carry（进位）。

半加器

虽然半加器看上去跳出了布尔运算，升级到的小学数学，但其仍然可以用真值表表示，所以也就可以用基本逻辑门实现，我们用一个Xor和And就可以实现半加器。

半加器电路图

/**
 * 半加器
 * Computes the sum of two bits.
 */

CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b 
        carry;  // Left bit of a + b

    PARTS:
    Xor(a=a, b=b, out=sum);
    And(a=a, b=b, out=carry);
}

半加器只能计算两个一位二进制数相加，接着我们在输入端再加入一个进位管脚（代表低位做加法时进过来的进位），就成为了一个全加器。

全加器

全加器电路图

/**
 * 全加器
 * 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:
    HalfAdder(a=a, b=b, carry=carryA, sum=sumA);
    HalfAdder(a=sumA, b=c, carry=carryB, sum=sum);
    Or(a=carryA, b=carryB, out=carry);
}

最后我们利用全加器实现16位加法器，有了16位加法器，我们就可以进行2个不大于2^16的整数的加法了。

16位加法器

/**
 * 16位加法器
 * Adds two 16-bit values.
 * The most significant carry bit is ignored.
 */

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

    PARTS:
    FullAdder(a=a[0], b=b[0], c=false, sum=out[0], carry=ca0);
    FullAdder(a=a[1], b=b[1], c=ca0, sum=out[1], carry=ca1);
    FullAdder(a=a[2], b=b[2], c=ca1, sum=out[2], carry=ca2);
    FullAdder(a=a[3], b=b[3], c=ca2, sum=out[3], carry=ca3);
    FullAdder(a=a[4], b=b[4], c=ca3, sum=out[4], carry=ca4);
    FullAdder(a=a[5], b=b[5], c=ca4, sum=out[5], carry=ca5);
    FullAdder(a=a[6], b=b[6], c=ca5, sum=out[6], carry=ca6);
    FullAdder(a=a[7], b=b[7], c=ca6, sum=out[7], carry=ca7);
    FullAdder(a=a[8], b=b[8], c=ca7, sum=out[8], carry=ca8);
    FullAdder(a=a[9], b=b[9], c=ca8, sum=out[9], carry=ca9);
    FullAdder(a=a[10], b=b[10], c=ca9, sum=out[10], carry=ca10);
    FullAdder(a=a[11], b=b[11], c=ca10, sum=out[11], carry=ca11);
    FullAdder(a=a[12], b=b[12], c=ca11, sum=out[12], carry=ca12);
    FullAdder(a=a[13], b=b[13], c=ca12, sum=out[13], carry=ca13);
    FullAdder(a=a[14], b=b[14], c=ca13, sum=out[14], carry=ca14);
    FullAdder(a=a[15], b=b[15], c=ca14, sum=out[15], carry=ignorCa); 
}

有了加法器，我们再实现一个累加器，它对输入数据进行加1，然后输出。累加器是后面CPU中程序计数器的重要部分。

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

CHIP Inc16 {
    IN in[16];
    OUT out[16];

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

多通道逻辑门

我们看到基本逻辑门负责计算布尔运算，但其只能根据输入计算出输出，缺少控制能力。下面我们介绍的多通道逻辑门则在逻辑控制方面扮演了重要角色，因为多通道逻辑门具有选择功能。多通道逻辑门在CPU和RAM中起到了重要作用。多通道逻辑门分为以下两种：

Multiplexor: 有多路输入，一路输出，选择输入中的一路作为输出
DMultiplexor: 有一路输入，多路输出，在输出路中选择一路降输入值输出

芯片列表

Multiplexor

DMultiplexor

这里我们实现一个2路1位的Mux。a，b是两路1位信号输入，sel是选择位。如果sel == 0，out管脚输出a的值，否则输出b的值。

2路1位Mux电路图

/** 
 * 2路1位Mux
 * Multiplexor:
 * out = a if sel == 0
 *       b otherwise
 */

CHIP Mux {
    IN a, b, sel;
    OUT out;

    PARTS:
    Not(in= sel, out=NotSel);
    And(a=a, b=NotSel, out=AndAOut);
    And(a=b, b=sel, out=AndBOut);
    Or(a=AndAOut, b=AndBOut, out=out);
}

当然除了2路选择器，还有4路、8路、16路等多路选择器。

多路Mux

下面是4路16位选择器的一种实现方式

/**
 * 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=outA);
    Mux16(a=c, b=d, sel=sel[0], out=outB);
    Mux16(a=outA, b=outB, sel=sel[1], out=out);
}

ALU

有了多通道逻辑门，我们就可以进一步实现一个更为复杂的芯片：ALU。ALU是CPU的三大基本模块之一（ALU、寄存器、程序计数器）。基本逻辑门只能计算一种布尔逻辑，而ALU可以通过改变控制位输入变量的组合（zx,nz,zy,ny,f,no），可以控制实现多种计算逻辑。这类似于一个CPU可以执行指令集中的众多指令一样（当然这其中就依赖于ALU）。

芯片列表

ALU

ALU真值表

下面我们就用上面实现的芯片来实现一下ALU（。

/**
 * 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:
    Mux16(a=x, b=false, sel=zx, out=zSelX);
    Not16(in=zSelX, out=notZSelx);
    Mux16(a=zSelX, b=notZSelx, sel=nx, out=outX);

    Mux16(a=y, b=false, sel=zy, out=zSelY);
    Not16(in=zSelY, out=notZSelY);
    Mux16(a=zSelY, b=notZSelY, sel=ny, out=outY);

    Add16(a=outX, b=outY, out=outAdd); // X+Y
    And16(a=outX, b=outY, out=outAnd); // X&Y

    Mux16(a=outAnd, b=outAdd, sel=f, out=outF);
    Not16(in=outF, out=notF);

    Mux16(a=outF, b=notF, sel=no, out=out, out[0..7]=outZrA, out[8..15]=outZrB, out[15]=outMSB);

    Or8Way(in=outZrA, out=zrL);
    Or8Way(in=outZrB, out=zrH);
    Or(a=zrL, b=zrH, out=notZr);
    Not(in=notZr, out=zr);

    And(a=true, b=outMSB, out=ng);
}

补码

最后我们再来谈一下补码，上面我们提到的加法器都没有考虑正负符号的问题，如果引入符号，那么电路会变得更加复杂。通过使用补码可以很好的规避这个问题，因为补码有一个很重要的特性：任何两个用补码表示的有符号数的加法和正数的加法完全相同，例如用正数加法操作（-2）+（-3），所得的结果正好是（-5）的补码；补码的减法可以用加法来代替实现，例如x-y == x+(-y)。

从0到1构建计算机(3/12)--组合逻辑芯片：逻辑门、加法器、ALU

组合逻辑芯片

基本逻辑门

加法器

多通道逻辑门

ALU

补码

CATALOG

FEATURED TAGS