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)

CHIP ALU4 {
// This file uses software accompanying the book
// "The Elements of Computing Systems" by Nisan and Schocken,
// Download the Hardware Simulator at www.idc.ac.il/tecs

/**
 * 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


CHIP ALU4 {
    IN
        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
        out[4], // 4-bit output
        zr, // 1 if (out==0), 0 otherwise
        ng; // 1 if (out<0),  0 otherwise

    PARTS:
    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);
}

Saturday, August 25, 2012

4-bit ALU - Testing Chips

I have successfully tested 4 out of the 5 chips I need for the ALU. The multiplexor was giving me some trouble; hopefully I can figure out what was going wrong. I've tried several different chips, and I think whatever's going on is because of me, not faulty chips.

Here's a video of that testing in action, on the 4 good chips. While its not overly exciting, I want to document most of this project. So... enjoy?

4-bit ALU - Design

Today I finished coding my ALU in Hardware Description Language. I had already implemented a 16-bit ALU, so I didn't have to change much; I just switched all the 16-bit gates to 4-bit gates and substituted NAND gates for NOT gates, as I don't have any NOT gates. Though I came up with this particular implementation, the functionality was detailed in this book. Here's the truth table I used to build it:


As you can see, it performs a number of different functions, but it doesn't multiply or divide. While I may add that function to the 16-bit ALU, I'm sticking with these functions for the 4-bit ALU.

I've copied the code I wrote for the 4-bit ALU below. (NOTE: ALU CODE HAS BEEN CHANGED) The language is fairly self explanatory, but I've also included a link to the Hardware Simulator I used and materials explaining how to interpret it.

So far so good!

4-Bit ALU HDL Code v1.0

CHIP ALU4 {
    IN
        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
        out[4], // 4-bit output
        zr, // 1 if (out==0), 0 otherwise
        ng; // 1 if (out<0),  0 otherwise

    PARTS:
    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=w14, out[3]=w15, out=out);
    Or4Way(in=w13, out=w16);
    Nand(a=w16, b=true, out=zr);
    And(a=w15, b=true, out=ng);
}

Thursday, August 23, 2012

4-bit ALU


This is the beginning of DupinComp. Though I don't quite know all the parts I need or the final design, I'm impatient, so I'm building the ALU before finishing the book. I haven't done any electrical engineering before, and I know very little about electricity, so I'm starting off with a 4-bit ALU. If it ends up not working, or I end up frying anything, then I've wasted less time and money than if I wired the 16-bit ALU I'll eventually need.  Here are all the components I'm using:

3 840 hole breadboards
3 spools of wire (1 green, 1 red, 1 black)
Arduino UNO (power supply)
2 DIP 8 slide switches (CTS 206-8)
4 NAND gates (sn74ls00n)
4 AND gates (sn74ls08n)
1 OR gate (sn74ls32n)
4 MUX gates (sn74hct157n)
1 Full Adder (sn7483n)

*Note: This list may change, if I find I need more parts

Though I planned out what I needed based on a design I had already tested with software, I'm tweaking it a little bit. Once I've written it down in HDL (hardware description language, for those who haven't read the book), I'll probably upload it.