Sunday, September 9, 2012

4-bit ALU - Demonstration, Schematics

I'm happy to say I've successfully built a 4-bit version of my ALU. It computes all 18 functions detailed in the truth table from "The Elements of Computing Systems" and outputs them on a 7-segment LED display and 2 single LED's; the number that results from the ALU's computation appears on the 7-segment LED, and the 2 single LED's indicate whether that number is 0 and/or negative.

All and all, the ALU was actually less time consuming that I had feared. It still took an annoyingly long time, but I had a bunch of free time the past 2 days and really wanted to get it done. I had a nice setup with Chappelle's show and Star Trek TNG alternating on my computer that made it a lot easier. Below are the schematics detailing which gate is where on the breadboard and which switch does what. I also numbered the wires according to the variable names for the connections in the hdl code I posted earlier. I was not in the mood to write down all those wires on this schematic, and saw no point as the connections were detailed in the hdl code, so I didn't.

Since I intend to use a different display unit (some sort of lcd screen) later in the project, I didn't add any circuitry so that negative numbers would be properly displayed on the 7-seg; I used 2's compliment to represent negative numbers, so any number displayed larger than 7 actually represents a negative number. Therefore the range of the outputs is from [0]-[15] rather than [-8]-[7]. This means that the 7-seg has to output 2 digit numbers, though it only has room for 1 digit, so for any number greater than 9 it uses special characters.

I also forgot to demonstrate the function x-y; whoops. You'll have to trust me; it works. It took about an hour for me to edit the video and upload it and I'm not planning on doing it again.

Thanks to those of you who gave me advice on reddit, a special thanks to IX for his continued contribution to the blog. Next stop, 16-bit version/CPU!

Thursday, September 6, 2012

4-bit ALU - Progress, HDL code Fix

Today I realized just how long this ALU is going to take; a while. Cutting and placing wires is much more time consuming than I had hoped, though this is not exactly unexpected. I was warned about how long it would take if I used ICs instead of an FPGA. But I'm not backing down so easily. I bought all these ICs and I'll be damned if I don't use them. I think I'll use an FPGA for the 16 bit version, after I do some research to see if there's any loss in speed, and how much loss there would be. I'm suspecting it will actually be faster, as the gates are be a lot closer together in an FPGA than they'd be in an ALU made out of ICs, hence less resistance while the signals are moving. The max delays for most of the IC gates averages around 40 ns, so I'll do some math and compare specs with some FPGA's.

Above is a pic of my current progress. This was all done today, and took about 2 hours, including determining a good layout with short connections between ICs. As you can see, I've added some pull-down resistors to the switches. In my testing post, I mentioned that I was having trouble with the multiplexor; it was because I wasn't using either pull-up or pull-down resistors. Here's a relevant reddit post about the error. I've also added a 7447 chip and a 7-segment display to display the results of the computations. I was considering using the Arduino I have, but this looks cooler, imo. Plus I'd rather not use the arduino for anything other than power (sounds silly, I know), and let the ALU do all the work.

There are also some slight differences in this layout from my original hdl code, because I had made some errors and added 2 extra wires and a chip that didn't do anything. Below is the corrected code for the ALU. There is also another potential optimization, where I could use one of the available inputs on the 1st 4-bit NAND gate listed in the code and eliminate the need for the last NAND gate in the code, but the code doesn't allow it (even though it would work irl), and the layout would be a bit messier. I have NAND's to spare, so I went ahead and kept it.

4-Bit ALU HDL Code (v1.1)

// This file uses software accompanying the book
// "The Elements of Computing Systems" by Nisan and Schocken,
// Download the Hardware Simulator at

 * The ALU. 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 4-bit inputs,
 * according to 6 input bits denoted zx,nx,zy,ny,f,no.
 * The bit-combinations that yield each function are
 * documented in the book. In addition, the ALU
 * computes two 1-bit outputs: if the ALU output
 * is 0, zr is set to 1; otherwise zr is set to 0;
 * If out<0, ng is set to 1; otherwise ng is set to 0.

// Implementation: the ALU manipulates the x and y
// inputs and then operates on the resulting values,
// as follows:
// if (zx==1) set x = 0        // 4-bit constant
// if (nx==1) set x = ~x       // bitwise "not"
// if (zy==1) set y = 0        // 4-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

        x[4], y[4],  // 4-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 out = x & y (if 0)
        no; // negate the out output?

        out[4], // 4-bit output
        zr, // 1 if (out==0), 0 otherwise
        ng; // 1 if (out<0),  0 otherwise

    Nand4(a[0]=zx, a[1]=zy, b=true, out[0]=w1, out[1]=w5);
    And4(a=x, b[0]=w1, b[1]=w1, b[2]=w1, b[3]=w1, out=w2);
    Nand4(a=w2, b=true, out=w3);
    Mux4(a=w2, b=w3, sel=nx, out=w4);
    And4(a=y, b[0]=w5, b[1]=w5, b[2]=w5, b[3]=w5, out=w6);
    Nand4(a=w6, b=true, out=w7);
    Mux4(a=w6, b=w7, sel=ny, out=w8);
    And4(a=w4, b=w8, out=w9);
    Add4(a=w4, b=w8, out=w10);
    Mux4(a=w9, b=w10, sel=f, out=w11);
    Nand4(a=w11, b=true, out=w12);
    Mux4(a=w11, b=w12, sel=no, out=w13, out[3]=ng, out=out);
    Or4Way(in=w13, out=w14);
    Nand(a=w14, b=true, out=zr);