ALU Implementation

[Idrisadeniyi]

I'm trying to implement ALU chip. Currently, I have an incompletely clear understanding of what to do and I have so far written some truth table, draw out some combination of logic gates, and simulate it on paper to see that the result conforms with what I expect. I have also written the hdl code based on this but, when i ran it, it failed at line 1. I know my solution is flawed but this is my best attempt. please help put me on the right track. Thanks

Below is my HDL.

 Not16(in[0]=zx, out=notzx);
   And16(a=x, b=notzx, out=xandnotzxout1);
   And16(a=notzx, b=x, out=xandnotzxout2);
   Mux16(a=xandnotzxout1, b=xandnotzxout2, sel=zx, out=zxout);
 
   //nx logic
   Not16(in[0]=nx, out=notnx);
   Not16(in=zxout, out=notx);
   And16(a=zxout, b=notnx, out=xandnotnxout);
   Or16(a=notx, b=notnx, out=notxornotnxout);
   Mux16(a=xandnotnxout, b=notxornotnxout, out=nXOut);
      //zy logic
   Not16(in[0]=zy, out=notzy);
   And16(a=y, b=notzy, out=yandnotzyout1);
   And16(a=notzy, b=y, out=yandnotzyout2);
   Mux16(a=yandnotzyout1, b=yandnotzyout2, sel=zy, out=zyout);
      //ny logic
   Not16(in[0]=ny, out=notny);
   Not16(in=zyout, out=noty);
   And16(a=zyout, b=notny, out=yandnotnyout);
   Or16(a=noty, b=notny, out=notyornotnyout);
   Mux16(a=yandnotnyout, b=notyornotnyout, sel=ny, out=nYOut);
   //F logic
   Add16(a=nXOut, b=nYOut, out=xPlusYOut);
   And16(a=nXOut, b=nYOut, out=xAndYOut);
   Mux16(a=xPlusYOut, b=xAndYOut, sel=f, out=xPlusYOrXAndYOut);
   //no Logic
   Not16(in[0]=no, out=notNo);
   Not16(in=xPlusYOrXAndYOut, out=notXPlusYOrXAndYOut);
   And16(a=xPlusYOrXAndYOut, b=notNo, out=noOut1);
   Or16(a=notXPlusYOrXAndYOut, b=notNo, out=noOut2);
   Mux16(a=noOut1, b=noOut2, sel=no, out=noOut, out=out);
   //Zr Logic
   Not(in=true, out=zr);
   Not(in=true, out=ng);

[WBahn]

You are definitely off the beaten path.

The ALU is actually amazingly simple, far simpler than it appears at first.

You have two basic operations -- adding two 16-bit values (the A in ALU) and anding two 16-bit values (the L in ALU). The f input simply chooses between the two.

So set up the core of your ALU to do just that. Take two inputs and choose which of the two operations is used for the output.

The other control inputs merely control what happens to the inputs before they are sent to this core portion or what happens to the output of the core portion before it is sent to the chip output.

[Idrisadeniyi]

But there are inputs that modifies the bits before it gets to f. And another element of confusion is that x and y are 16bits and I'm to test each against 1bit value(zx, nx, zy, ny). It's really not clear how to get that implemented.

[WBahn]

What f does has nothing to do with how the input and output signals are modified by the other control bits.

The zx anf nx bits make some changes to the 16-bit x-input resulting in a 16-bit signal, call it Fred, and that signal is sent to the adder and the ander. The f input controls which of the two 16-bit outputs of those two is used for further processing.

Remember that you have a part that is specifically designed to let a 1-bit control signal choose which of two 16-bit signals to pass to its output.

[Idrisadeniyi]

As per getting this idea into the hdl, the way I could best think about this process is to break the entire operations into different chunks and setup a truth table for each. for example:

x zx |out
0 0    0
0 1    0
1 0    1
1 1    0

For this combination of bits, I setup logic gates to achieve the outputs; and this is the same approach I've used to implement the rest of the operations of the ALU. If my approach is not correct, please lead me in the right direction. I do understand what the ALU is doing, but to implement it is actually the problem here.

[WBahn]

There are many ways to implement the logic and any logic that works is valid.

The authors are definitely trying to steer you toward a particular solution (or at least very close to one) both by the parts they have you build, the way they word the specification, and how they describe it in the text.

Forget about the ALU spec and let's focus on just a tiny piece of the puzzle.

You have two 16-bit signals, let's call them A and B.

You have a 1-bit control signal, called C.

Can you use one (just one) of the parts you have already built so that the output is A if the control signal is a 0 and it is B is the control signal is a 1?

What if the signal B is always 0 (i.e., all sixteen bits are always a 0)?

Now compare how this works to what the zx and zy control signals are supposed to do.

Now let's take another example in which you have a single 16-bit input. Can you think of a way to use one (just one) of the parts you have already built to generate a second signal that is always the bitwise opposite of the first signal?

Can you use another part (just one more) that you have already built to use a 1-bit control signal, called D, so that it outputs the original signal if D is a 0 and the bitwise-negated version of the original signal if D is a 1.

Now compare how this works to what the nx, ny, and no control signals are supposed to do.

[WBahn]

This might help you visualize things.

You have a data path through the ALU (and later the CPU) that is sixteen bits wide. That data path is like a set of water pipe that flow through a bunch of valves. Those valves, based on the control signals, pick which pipes are allowed to send their data to the next part of the machine.

[Idrisadeniyi]

Thanks for the clarification. It indeed shed some light on my confusion.

However, as I'm trying to build the ALU chip based on that explanation, I realized I'm not utilizing some input pins which make me become skeptical about my implementation. The following is my hdl:

Mux16(a=x, b=y, sel=zx, out=zxOut); //zx and zy logic
        Not16(in=zxOut, out=notZx); // !x and !y logic
        Inc16(in=notZx, out=xPlusYOut); //2's complement addition
        And16(a=zxOut, b=notZx, out=xAndYOut); // x & y logic
        Mux16(a=xPlusYOut, b=xAndYOut, out=fOut); // f logic
        Mux16(a=zxOut, b=notZx, sel=no, out=noOut, out=out); //no logic
        DMux (in[0]=noOut[0], sel[0]=noOut[0], a=zr, b=ng); // zr and ng logic
         

Another confusion is being able to implement the zr and ng based on out. I'm using DMux to implement that portion. Since out is now a 16bits pin, while zr and ng are 1bit out pin respectively, connecting these pins has been a major challenge.

Thank you for always being there

 

[WBahn]

Describe, in words, how YOU would look at a 16-bit value and determine True or False to the question of whether that 16-bit value was positive or negative. Or how you would determine if it represents the value zero.

[Idrisadeniyi]

I think this involve some 2's complement operation, but I'm still struggling to get a clear picture of it in my head.

[WBahn]

Look at the two's complement representation described in the text and look for a feature that ALL strictly negative numbers have that ALL strictly positive numbers do not. Hint, this feature is why zero is considered non-negative by pretty much every programming language on the planet.

[Idrisadeniyi]

Thanks I got that. A positive number is represented with a MSB of 0 and 1 for negative number.

[WBahn]

Good.

So now do you have a clear picture of how to get the zr ang ng signals?

If you are still struggling with the zr, using the parts available, consider the opposite question of how you would know that a value is NOT zero.

[Idrisadeniyi]

I think a value is not zero when it's either positive or negative. Knowing that I would need a part to simply do that for me. But I'm still struggling to figure out what part it could be.

[WBahn]

You are overthinking it.

If I give you the bit pattern:

000101010111010110100101010001001011100101010

Is that zero or not?

If I give you the bit pattern:

000000000000000000000000000000000000000000000

Is that zero or not?

If I give you the bit pattern:

000000000000000000000100000000000000000000000

Is that zero or not?

If I give you the bit pattern:

100000000000000000000000000000000000000000000

Is that zero or not?

What mental test did YOU use to decide which of those, if any, were zero?

[Idrisadeniyi]

I know that the one which was comprised of low bits altogether is zero.  

[WBahn]

Exactly!

A value is zero if and only if every bit in it is 0.

Or, put another way,

A value is NOT zero if ANY bit is a 1.

What logic gate returns a 1 if ANY of its inputs is a 1?

[Idrisadeniyi]

The Or logic gate.

[WBahn]

So how can you use the gates that you have to build a circuit that checks if all of the bits are zero?

[Idrisadeniyi]

I'll appreciate if I could get some clue. Thank you.