《计算机系统要素实验》Pro2:自己做一个算术逻辑单元ALU

标签: 计算机系统

Pro2:布尔运算

HalfAdder半加器

半加器的LSB位叫sum,MSB位叫carry

在这里插入图片描述

观察发现:sum位也就是XOR异或门的结果,carry也就是AND位的结果,可以直接替代

XOR(a=a,b=b,out=sum);
And(a=a,b=b,out=carry);

在这里插入图片描述

FullAdder全加器

在这里插入图片描述

全加器是不是可以用两个半加器组合出来呢?

我们的大脑在进行多位相加时,也不会全部并行相加,一般都是串行,加完一个,在和的基础上再加下一个,如下

  • a+b = tep ;(分为高低位)

  • tep +c = amp;(tep的低位加上c ,低位就是最后结果的低位,但是这一步的和 amp的高位要和tep的高位继续加,算出进位)

  • amp 的高位于tep的高位相加,结果为a+b+c的高位,这里注意,两个高位相加我们只取结果的低位;

我进行了尝试

首先将两位相加,调用半加器加a,b

a b carry1 sum1
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

再将sum1位和c相加,大家可能会想到进位是个头疼的事

c sum1 carry2 sum2
0 0 0 0
0 1 0 1
1 1 1 0
1 0 0 1

sum2位不会变了,这就是最终结果的低位,唯一有影响的是carry位需要相加进位

按照之前的思路,两个高位相加的和,低位是最终结果的高位

carry1 carry2 carry3 sum3
0 0 0 0
0 0 0 0
0 1 0 1
1 0 0 1

这里有点绕,如图,和的高位全为0,只有低位有效

让我们来验证

a b c sum3 sum2
0 0 0 0 0
0 1 0 0 1
1 0 1 1 0
1 1 1 1 1

算理没问题,但是结果不全???

    HalfAdder(a=a,b=b,sum=sum1,carry=carry1);
    HalfAdder(a=c,b=sum1,sum=sum,carry=carry2);
    HalfAdder(a=carry1,b=carry2,sum=carry,carry=carry3);
    //我第一遍写的时候,把最后的carry没有赋值报错了,第三句sum = carry的意思是把第三部运算的低位赋值给最终结果的carry

没问题检验通过

Add16 加法器

在这里插入图片描述

对于加法器,最关键的在于进位

在这里插入图片描述

第一次加:只有两个数字 a[0]:1 +b[0]:0 ,低位直接是out[0],高位参与下一次运算

第二次加:除了a[1],b[1]外还要加上上一次的高位,循环

本16位加法器不处理溢出

    HalfAdder(a=a[0],b=b[0],sum=out[0],carry=w1);
    FullAdder(a=a[1],b=b[1],c=w1,sum=out[1],carry=w2);
    FullAdder(a=a[2],b=b[2],c=w2,sum=out[2],carry=w3);
    FullAdder(a=a[3],b=b[3],c=w3,sum=out[3],carry=w4);
    FullAdder(a=a[4],b=b[4],c=w4,sum=out[4],carry=w5);
    FullAdder(a=a[5],b=b[5],c=w5,sum=out[5],carry=w6);
    FullAdder(a=a[6],b=b[6],c=w6,sum=out[6],carry=w7);
    FullAdder(a=a[7],b=b[7],c=w7,sum=out[7],carry=w8);
    FullAdder(a=a[8],b=b[8],c=w8,sum=out[8],carry=w9);
    FullAdder(a=a[9],b=b[9],c=w9,sum=out[9],carry=w10);
    FullAdder(a=a[10],b=b[10],c=w10,sum=out[10],carry=w11);
    FullAdder(a=a[11],b=b[11],c=w11,sum=out[11],carry=w12);
    FullAdder(a=a[12],b=b[12],c=w12,sum=out[12],carry=w13);
    FullAdder(a=a[13],b=b[13],c=w13,sum=out[13],carry=w14);
    FullAdder(a=a[14],b=b[14],c=w14,sum=out[14],carry=w15);
    FullAdder(a=a[15],b=b[15],c=w15,sum=out[15],carry=w16);		
inc 增量器

也是处理16位的(多位),但只需要加一即可,也就是说把上一个加法器的b[0]赋值为1

Add16(a=in,b[0]=true,out=out);
ALU

在这里插入图片描述
最后的逻辑要跟着这个表走,解释一下

  • zx =1,则x = 0, y的值看zy,ny,f = 1,输出为x+y ,no位指示要不要取反,最后输出

在这里插入图片描述
分析:

Chip name: ALU
Inputs: x[16], y[16], // 两个十六位的输入
        zx,           // 也就是Zero  x 的输入
        nx,           // not x
        zy,           // 
        ny,           // 同x
        f,            //函数: 1 for Add, 0 for And
        no            // 取反输出 not output
Outputs: out[16],      // 16-bit output
        zr,           // True iff out=0
        ng            // True iff out<0
Function: 
        if zx then x = 0            // if (zx == 1) set x = 0
        if nx then x = !x           // 使用not取反
        if zy then y = 0           // 16-bit zero constant
        if ny then y = !y            //取反
        if f then out = x + y         // 两个整数加法
        else out = x & y             // 使用And门
        if no then out = !out            // 取反
        if out=0 then zr = 1 else zr = 0 // 1 if (out == 0), 0 otherwise
        if out<0 then ng = 1 else ng = 0 // 1 if (out < 0),  0 otherwise
        Comment: Overflow is neither detected nor handled.

一个函数一个函数的往下啃:一定要和之前的知识联系起来

  • ----- Zero x (zx bit) 0 X
    如果zx这一位为1,x变成0
    想到了选择器:选择位为0的时候是a,为1的时候是b

    ​ 现在选择为1,X变为0,也就是把Mux的b置为0即可

  • ——Negate x (nx bit) 位

    ​ 和上面的一样,只不过是选择了x的相反数而已 ~x

  • —— zy, ny同理

  • ——f位

    ​ 如果是1 ,使用加法,使用加法器即可

    ​ 如果是0,使用And 与门

    ​ 控制0还是1,任然使用选择器,sel=0,a= and ;sel= 1,b = add

  • ——no位

    ​ 如果是1 ,选择out ;sel =1 ,b = f

    ​ 如果是0 ,选择not out ;sel = 0,a = not out

  • zr位 output = 0 zr=1

    ​ 先使用OR ,如果结果里面有1,or后必为1,取反,赋值给zr

    ​ 如果结果为0 ,or后为0,取反,赋值给zr

  • ng位:判断output是不是负数,负数的话,ng为1

    但是负数该怎么检测呢?

    有下面这张图看出,负数的最后一位(例如:下图四位,b[3])是1的话为负数,也就是符号位为1,是负数

    我们可以用10000…00 b[x] x为最后一位,如果是16位数据为b[15]=1,其余位=0,和output想与,如果output为负数,最后结果必带有1,正数不会有1

    可以使用OR检测
    在这里插入图片描述

代码:

PARTS:
   
    // ----- Zero x (zx bit) 0 X
    //如果zx这一位为1,x变成0
    // 想到了选择器:选择位为0的时候是a
    Mux16(a=x, b=false, sel=zx, out=zxOut);

    // ----- Negate x (nx bit)
  
    Not16(in=zxOut, out=notX);
    Mux16(a=zxOut, b=notX, sel=nx, out=nxOut);

    // ----- Zero y (zy bit)
    
    Mux16(a=y, b=false, sel=zy, out=zyOut);

    // ----- Negate y (zy bit)

    Not16(in=zyOut, out=notY);
    Mux16(a=zyOut, b=notY, sel=ny, out=nyOut);

    // ----- Compute out (f bit)
    // x & y
    And16(a=nxOut, b=nyOut, out=andOut);

    // x + y
    Add16(a=nxOut, b=nyOut, out=addOut);

    // Return the output that the f bit expects
    Mux16(a=andOut, b=addOut, sel=f, out=fOut);

    // ----- Negate output (no bit)
    
    Not16(in=fOut, out=noOut);
    Mux16(a=fOut, b=noOut, sel=no, out=final);

    // 这一步是检验步骤,如果之前都检查完无误,选择final
    // tests on it below.
    Mux16(a=final, b=false, sel=false, out=out);

	//往下是zr,ng两个输出

    // 如果输出为0 ,zr为1 (zr)
    // 先使用OR ,如果结果里面有1,or后必为1,取反,赋值给zr
    // 如果结果为0 ,or后为0,取反,赋值给zr 
    Or16Way(in=final, out=zrOut);
    Not(in=zrOut, out=zr);

    // 如果输出output小于0 ,ng为1 (ng)
    // 判断output是不是负数,负数的话,ng为1
    //但是负数该怎么检测呢?

    //负数的最后一位(例如:下图四位,b[3])是1的话为负数,也就是符号位为1,是负数
    //我们可以用10000.....00  b[x] x为最后一位,如果是16位数据为b[15]=1,其余位=0,和output想与,如果output为负数,最后结果必带有1,正数不会有1

    //可以使用OR检测有没有1 

    And16(a=final,b[0..14]=false,b[15]=true,out=ng1);    
    Or16Way(in=ng1,out=ng);    
   

在编写ALU的过程中,为了方便检查是否最后答案有1 ,我们使用了OR16way但这个还没有编写,我根据OR8way编写完成

本来打算测试之后,在测试ALU,但万万没想到测试一个模块这么复杂

编写tst和cmp文件后,导入测试,最后hdl不报错了,但是这几个测试文件报错

cmp
|     in     | out |
|  0000000000000000  |  0  |
|  1111111111111111  |  1  |
|  0001000000010000  |  1  |
|  0000000100000001  |  1  |
|  0010011000100110  |  1  |

tst
load Or16Way.hdl,
output-file Or16Way.out,
compare-to Or16Way.cmp,
output-list in%B1.16.1 out%B1.1.1;

set in %B0000000000000000,
eval,
output;

set in %B1111111111111111,
eval,
output;

set in %B0001000000010000,
eval,
output;

set in %B0000000100000001,
eval,
output;

set in %B0010011000100110,
eval,
output;

在这里插入图片描述
期待哪位大神帮我调试一下,我i测试的结果是第一行,不是数据的问题,好像是导航栏(in | out )这一栏的格式问题

最后,我们把Or16way.hdl放入ALU的文件下,运行成功,第一个算术单元被成功的造出来了

在这里插入图片描述

版权声明:本文为weixin_44537194原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44537194/article/details/104596990