ALU Implementation

[WBahn]

Let's take a step back.

I have two signals, a and b, and I need a circuit that gives me a 1 if and only if both of the signals are 0.

Using two of the gates that you have at your disposal, can you build a circuit that does this?

[Idrisadeniyi]

I think a Nand gate should do that for me.

[WBahn]

Thank about that carefully.

We want a circuit that outputs a 1 only when both inputs are 0.

Is that really what a Nand gate does?

[Idrisadeniyi]

I think a combination of a Not and a Or gate should do it.

[WBahn]

Yep.

So how would you do it for four signals, a, b, c, and d?

[Idrisadeniyi]

I guess I would double the gates.

[WBahn]

What does that mean?

Go ahead and give the HDL that you would use.

Once you get this, you should find doing all 16-bits to be very trivial.

[Idrisadeniyi]

I think I now have a headway as it seems that my zr and ng pins are now producing the correct result.

However, You gave a clear example of how zx zy etc are suppose modify the two main control bits x and y in the above post. After I implemented those parts, I realized that some pins have not been utilized whch I posted.

Here is my hdl now:
        Mux16(a=x, b=y, sel=zx, out=zxOut); //zx logic
        Not16(in=zxOut, out=notZx); // !x 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
        Not16(in=noOut, out=notNoOut);
        Or16(a=notNoOut, b=notNoOut, out[15]=zr); // check if out is positive
        Or16(a=noOut, b=noOut, out[15]=ng); // check if out is negative

Although I have written this hdl based on that explanation, I still does not have a complete clear picture of it.

[WBahn]

Look at your very first gate.

What is zx supposed to do?

What is that Mux doing based on zx?

Why are you trying to do 2's complement addition?

Just implement the logic that does what the spec says in terms of how the inputs and outputs are modified based on the state of the six control signals.

There is NOTHING in the spec that says ANYTHING about incrementing.

There IS something in the spec about choosing between the And of the two inputs or the Add of the two inputs, yet you don't have an Adder in sight.

Go back to what I said earlier and just focus on manipulating the x input based on the zx and nx control signals. First focus on the using the zx input to create a signal that is either the original x input or nothing but zeroes. Then, using this signal (let's call it Bob), use the nx signal to produce create another signal (let's call it Sue) that is either equal to Bob, or is equal to the bitwise complement of Bob. If you can do that, you have implemented the logic for manipulating the inputs.

[Idrisadeniyi]

Roger that! I was able to edit the six input control bits to the best of my ability, I believe that part should work just fine now.

Regarding zr, could you please explain why I need 4 signals or to be precise 16 signals to get the correct output for zr. I'm a bit confused as I realized that my zr is not producing the correct output after editing the preceding parts.

Here is my current hdl: I know zr part implementation is incorrect.

        Not16(in=true, out=notTrue);
        Mux16(a=x, b=notTrue, sel=zx, out=zxOut); //zx logic
        Not16(in=zxOut, out=notZx); // !x logic
        Mux16(a=zxOut, b=notZx, sel=nx, out=nxOut); // nx Logic
        Mux16(a=y, b=notTrue, sel=zy, out=zyOut); //zy logic
        Not16(in=zyOut, out=notZy); // !y logic
        Mux16(a=zyOut, b=notZy, sel=ny, out=nyOut); // ny logic
        Add16(a=nxOut, b=nyOut, out=xPlusYOut); //x + y addition
        And16(a=nxOut, b=nyOut, out=xAndYOut); // x & y logic
        Mux16(a=xAndYOut, b=xPlusYOut, sel=f, out=fOut); // f logic
        Not16(in=fOut, out=notFOut); // no negate output
        Mux16(a=fOut, b=notFOut, sel=no, out=noOut, out=out); //no logic
        Not16(in=true, out=notTrueForZr);
        Or16(a=notTrueForZr, b=noOut, out=cOut1); // check if out is positive
        Or16(a=notTrueForZr, b=noOut, out=cOut2); // check if out is positive
        Or16(a=noOut, b=noOut, out[15]=ng); // check if out is negative

[WBahn]

I don't see ANY implementation for zr. But I see a huge, unnecessary dance to get ng.

But first, you take 'true' (a built-in signal consisting of all 1s) and use a Not16 to produce a signal of all 0s. Why not just use the built-in signal 'false', which is a signal consisting of all 0s?

Then you Or noOut with a signal consisting of all 0s, which doesn't change anything, not once but twice, to get cOut1 and cOut2. But then you never use either of these. What's the point?

Then you Or noOut with itself, which doesn't change anything, to get the msb. Remember, you can use multiple output statements to connect outputs to different signals. You did this with your final Mux16 to get noOut and out. So just tap off the msb of that Mux to get ng if that is what you want.

I can't comment on your implementation of zr because there isn't one.

But as to why you need to process 16 signals to determine zr, that's because the ALU output is 16-bits wide and any and all of them have to be considered before being able to determine that the output is exactly zero.

[Idrisadeniyi]

I'm sorry if that part of my hdl pissed you off. It was an unfinished work. I didn't intend to put it up here. I was thinking and doing some try and error when I made that post.

[Idrisadeniyi]

The way I think about it is that, since a positive number could be identified when its MSB is zero, so I would pipe zr to out at bit [15].

But it's not yet clear how to implement it that way.

As for ng, I think it's just going to be 1 when the entire bit is negative. And a number of bits is negative when its MSB is 1. Like zr, I would pipe ng to out at [15].

This is the way I'm thinking about it.

I do understand the way you have explained it. But I'm thinking as implementation is always harder.

[WBahn]

But the zr bit does not tell you whether or not the value at the ALU output is positive. The zr bit tells you whether or not the output of the ALU is exactly zero. The ng bit tells you whether or not the ALU output is negative and it makes no distinction between one negative value and another negative value. The zr output makes a big distinction -- if the value is 0, the zr output is HI, but if the value is 1 or 1000 or -5 the zr output is LO.

Let's foreshadow how these bits will get used down the road. Perhaps that will make it all make a bit more since.

A common thing in programming we want to do is compare two numbers. There are six relational operators:

a = b (equal to)
a != b (not equal to)
a > b (strictly greater than)
a < b (strictly less than)
a >= b (greater than or equal to)
a <= b (less than or equal to)

If you subtract b from a and tell me the value of zr and ng, I can answer True or False to any and all of those six operations with just those two pieces of information.

[WBahn]

Not pissed off at all. You seemed to indicate that you had an implementation for zr that you knew had problems, so I assumed that you were looking for feedback on that part of your code.

[Idrisadeniyi]

I would be grateful if you could help with a typical example of how this zr and ng could be implemented. I've tried different ways to get the zr by checking each bit in the bus, but would not work. I'm stuck.

Please help.

[WBahn]

Show your best (or most recent) attempt to implement zr and what your thinking is behind that approach. Also, how you know that it doesn't work. Which test case fails? What does the .cmp file say should be the output and what does the .out file say the output actually is?

We can use that as a starting point to move you to something that will work.

[Idrisadeniyi]

Alright. here is my cmp. it failed at line 14.

|        x         |        y         |zx |nx |zy |ny | f |no |       out        |zr |ng |
| 0000000000000000 | 1111111111111111 | 1 | 0 | 1 | 0 | 1 | 0 | 0000000000000000 | 1 | 0 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 1 | 1 | 1 | 1 | 0000000000000001 | 0 | 0 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 1 | 0 | 1 | 0 | 1111111111111111 | 0 | 1 |
| 0000000000000000 | 1111111111111111 | 0 | 0 | 1 | 1 | 0 | 0 | 0000000000000000 | 1 | 0 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 0 | 0 | 0 | 0 | 1111111111111111 | 0 | 1 |
| 0000000000000000 | 1111111111111111 | 0 | 0 | 1 | 1 | 0 | 1 | 1111111111111111 | 0 | 1 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 0 | 0 | 0 | 1 | 0000000000000000 | 1 | 0 |
| 0000000000000000 | 1111111111111111 | 0 | 0 | 1 | 1 | 1 | 1 | 0000000000000000 | 1 | 0 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 0 | 0 | 1 | 1 | 0000000000000001 | 0 | 0 |
| 0000000000000000 | 1111111111111111 | 0 | 1 | 1 | 1 | 1 | 1 | 0000000000000001 | 0 | 0 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 0 | 1 | 1 | 1 | 0000000000000000 | 1 | 0 |
| 0000000000000000 | 1111111111111111 | 0 | 0 | 1 | 1 | 1 | 0 | 1111111111111111 | 0 | 1 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 0 | 0 | 1 | 0 | 1111111111111110 | 1 | 1 |

here is my hdl:

        Not16(in=true, out=notTrue);
        Mux16(a=x, b=notTrue, sel=zx, out=zxOut); //zx logic
        Not16(in=zxOut, out=notZx); // !x logic
        Mux16(a=zxOut, b=notZx, sel=nx, out=nxOut); // nx Logic
        Mux16(a=y, b=notTrue, sel=zy, out=zyOut); //zy logic
        Not16(in=zyOut, out=notZy); // !y logic
        Mux16(a=zyOut, b=notZy, sel=ny, out=nyOut); // ny logic
        Add16(a=nxOut, b=nyOut, out=xPlusYOut); //x + y addition
        And16(a=nxOut, b=nyOut, out=xAndYOut); // x & y logic
        Mux16(a=xAndYOut, b=xPlusYOut, sel=f, out=fOut); // f logic
        Not16(in=fOut, out=notFOut); // no negate output
        Mux16(a=fOut, b=notFOut, sel=no, out=noOut, out=out); //no logic
        Or16(a=false, b=noOut, out=zrOut); // check if out is positive
        Not16(in=zrOut, out[0]=zr);
        Or16(a=noOut, b=noOut, out[15]=ng); // check if out is negative
       

[WBahn]

What is the .out file contain.

The .cmp file is what the output should be. It was supplied by the authors.

The .out file is what your design actually produced. You need to compare the two to narrow your search on what is going wrong.

Keep in mind that my focus is not on fixing this one design design. It's on helping you learn how to fix your own design so that you can apply that skill to future designs.

[Idrisadeniyi]

Oops! It was the out file I posted. The zr is meant to be 0 on line 14.