The Arithmetic-Logic Unit
All of mathematics solved with six bits.
The ALU is the work-horse in the CPU. It is responsible for almost all computations. In previous posts I have described building various kinds of chips that have somewhat simple functionality. Each chip was required to have a specific behavior that can be repeated giving the same result every time. The last chip I described which was the Full-Adder was the first chip that had some immediate mathematical utility. Well this is the post where we bring everything together to create the most complicated chip we have made thus far, which will be able to do the following :
ALU -(Inputs x,y)
So how does the chip know which function you want to execute? Well it employs the idea of control bits. This chip actually has 6 control bits that ingeniously tell the ALU which function to compute. Those inputs are named : ‘zx’, ‘nx’, ‘zy’, ‘ny’,’ f’, and ‘no’.
So what do these control bits do? Looks complicated but as with most things, when broken down it is super simple. The first four bits act directly on the x and y input. The ‘zx’ and ‘zy’ have the same functionality. They stand for zero-x and zero-y . As the name suggests if the ‘zx’ bit is set to one(true) then the x input will be set to zero. If the ‘zx’ bit is set to zero(false) then nothing will be done to the x input. The same thing happens with the ‘zy’ bit. It will either set the y input to zero or do nothing based on the value. The ‘nx’ and ‘ny’ stand for not-x and not-y. And……you guessed it! If the ‘nx’ bit is set to one it will ‘not’ the x input. If the input is zero then again nothing will be done to the x input. The ‘f’ or function control bit performs x+y if set to one. Otherwise it performs an ‘and’ operation on x and y if set to zero. Lastly, if the ‘no’ control bit is set to one then the entire output will be negated, otherwise it will be left as is. One last thing to note about this is that these functions are applied in order from left to right. So if the ‘no’ control bit is set to one the entire output will be negated only after all the other (if any) functions have been executed. So that’s all well and good but I am sure you are still skeptical about why this matters to you and your pursuit of mathematical superiority.
Well it turns out that if you wanted to add x to y you need only to feed the x and y inputs into the ALU and set the control bits to “000010”. If you refer to the illustration you would see that setting the control bits to that code would have disabled all control bits except for the ‘f’ bit. Which we have already said that if the ‘f’ bit is set to one then we perform addition to x and y. So that’s pretty awesome but also a little bit of a trivial example. Lets do something more complicated. Lets say we want to perform y-x. How would we do that?
So let’s see how this will work by defining our terms and running it through the ALU manually and seeing if the results match what we would expect. Let’s say that x=3 and y =5. At this point we would expect the output to be 2. Lets see what happens. First it looks like nothing happens until the ‘ny’ bit. So lets start by applying a ‘not’ operation to the y input. As we remember from before it simply just reverses the bits. One more thing to remember is that inputs are 16-bit. So even though there will be
//5 in binary = 101
//Convert it into 16 bits
//Not operation flips each bit.
//Which is -6 in decimal
//Since f =1 we need to add x to y
//x = 3 or 11 in binary
// or 0000000000000011 in 16 bit format.
Which we now add together.
x 0000000000000011 // = 3
+ y 1111111111111010 // = -6
1111111111111101 // =-3
//Now since 'no' is set to one we now negate the whole output.
//Which in decimal is........drum roll please... 2!!!
Now that we have proven that works perfectly I will leave you with a list of commands you send to the ALU to get desired results and I will leave you to run examples to prove to yourself that the desired behavior will be achieved.
So you can get any of those functions on the right-hand side of the table by feeding the appropriate values to the control bits. As shown on the left-hand side of the table.
There are two outputs I have neglected to mention that complete the specification for the HACK ALU. Those are outputs ‘zr’ and ‘ng’. I call these observation bits because ‘zr’ will be one if and only if the output is equal to zero. While ‘ng’ will be one if and only if the output is less than zero. Why is that info important? Well with those magic bits we can now perform equality checks like greater than or less than. Knowing the equality of an object now allows us to have our first primitive condition. Having our first primitive condition allows us to implement jump commands (which I will talk about in a later post). With jump commands at our disposal we can take over the world. At this point in the past I usually would now dive into how you would design this chip using HDL. I wont be doing that in this post because of the level of complication. I feel as if the complete implementation would be dull. Instead I will leave you with this gorgeous schematic that you can inspect to see my proposed implementation of the ALU.