Getting started with ALU

[nathan613]

I got everything done in Project 2 except for the ALU assignment. I don't want to start this without some guidance. I must with some embarrassment ask - just what exactly is it we have to do? I see the truth table, and I see the input pins and output pins. Do I just copy the the values of the 6 pins for each line? Or do I use logic gates to derive them? For output - what is the approach to get that last right f(x,y) column on the truth table? What about the outputs zr and ng - where does that figure in?
     Indeed, what is the overall aim and strategy?

[cadet1620]

The ALU is complex enough that it is not easy to analyze it with a truth table.  You need to think about the data paths through the ALU; how it transforms and combines its inputs to produce the output.

Look at the software-like description that's given

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

With very little syntax change, you could feed this to Java and have an ALU() function.

There are two tricky aspects to doing this in hardware.

The first is that you can't change a signal's value so the construct "set x=0" does not work since x already has a value coming from outside the ALU. The solution to this is to always make new signals in each step. Transform the if (zx... to

if (zx) x1 = 0
   else x1 = x

Then the next step transforms x1 to x2, etc.

The second problem is that you can't have only some of the hardware work. In this code

if (f == 1)  set fun = x2 + y2  // integer 2's complement addition
    else     set fun = x2 & y2  // bitwise and

both the Add16 and And16 are always their doing their operation. Your hardware needs to choose which part's output is connected to 'fun'. What part did you make in project 1 that can choose between 2 16-bit inputs? Yol'll use it for almost every step in the ALU.

First, get the main output value working so that your ALU will pass ALU-nostat.tst. This test ignores zr and ng. Once it is passing, then you can concentrate on the zr and ng outputs.

--Mark

[Jack Draak]

After browsing through ~a dozen posts here: Thanks! What a great community you've got here! This is some great advice.  I have to admit, that at some points I found myself completely stumped by this course (i.e. trying to design my first MUX).  Had I found this forum sooner, I'm sure it would have helped immensely.

I feel I have a bit of advantage though, as I have a long history of tinkering with various programming languages to do fairly simple things. Still, when I was approaching my ALU I was feeling similarly to the OP.... Where do I even start? How could I possibly truth-table a solution here, or draft a k-map for 22 inputs and 18 outputs? Well, when my programmer brain took a close look at the stub file, what seemed fairly obvious was, as Mark point's out, that no matter what the flag inputs are set to, each operation must be performed and then the flag can be used to select which of two states to "push down the wire" so to speak.

So, in the end (and as usual) the majority of my trouble building my ALU came from typos (and learning the syntax to output specific signals more than once from given chips).  I also had a few stumbles around the specific operations, for example the book tells us,

"to obtain the code of -x from the code of x, leave all the trailing (least significant) 0’s and the first least significant 1 intact, then flip all the remaining bits (convert 0’s to 1’s and vice versa). An equivalent shortcut, which is easier to implement in hardware, is to flip all the bits of x and add 1 to the result."


I interpret this to mean that if I have a 16-bit number (x) on my bus (in 2's complement format) I can shove it through a Not16 then an Inc16 and et viola! -x..... For the benefit of those who have yet to do their ALU I don't want to say much more about that, but frankly, although my ALU now passes it's tests, I'd love to grok either the statement from the book (because apparently I don't) or what magic I've crafted that let's me do it differently that I've just described.

But again, thanks to the community for sharing and helping each other here.  I may not have found it soon enough to help with my MUX, but there's no doubt I'll be looking for more help before I finish this course.

[cadet1620]

Jack Draak wrote

...although my ALU now passes it's tests, I'd love to grok either the statement from the book (because apparently I don't) or what magic I've crafted that let's me do it differently that I've just described.

You correctly understand the second half of that statement, and that is what counts: -x = !x + 1. (I think of the first half as just a pencil and paper shortcut; I think that it would be hard to prove because the operations are dependent upon the position of the least significant 1 bit.)


As stated in its comments, the ALU uses bit-wise Boolean negation -- which is Not -- and the operation code for -x is 001111: zx, nx = 0, zy, ny, f, no = 1, which results in

-x = !(x + (-1) )

Here is a proof that shows that the above operation is identical to the standard definition of 2's-complement negation.

    -x = !(x + (-1) )   Invert both sides and simplify
 !(-x) = x - 1          Substitute x = -x
!(--x) = -x - 1         Simplify
    !x = -x - 1         Add 1 to both sides
!x + 1 = -x
      QED

--Mark

[Jack Draak]

Ahah! That sneaky elegance got me on that one then... I'd been overlooking the actual impact of ZY.NY

Thank you for spelling it out for me!