Number Theory

Cool! Computers can subtract now. Except…. we have a problem. Let’s look at the following subtraction as run through our system:

Nice! Obviously 0 - 1 = 15! Wait, no. That’s probably not right. We have now run face first into the problem of negative numbers. How do we represent them in binary? We can’t just write a - in front of our numbers if they’re negative. Again, to set the ground work for the right answer, let’s go through a naive solution first.

So far throughout this lab, we’ve treated all integers as unsigned, that is they can only be positive. We now need to expand our understanding of numbers to signed integers. You may have seen/experienced this type of thing programming languages such as C or Java, where there are separate data types for signed and unsigned integers.

Obviously, signed integers must keep track of their sign somehow or they would be… well… unsigned integers. This puts an extra impetus on the binary representation somehow. One of the bits in our number has to be what we use to keep track of things. For a naive solution, let’s just use the most significant bit as if it were a +/- sign: 1 = + | 0 = -. Now, we can easily represent a full gamut of signed integers:

Cool, this is progress! You can tell just by looking at the most significant bit of each number if it is negative or positive. However, this comes at a cost. If we have 8 bit wide numbers, we can no longer represent 0 → 255, but instead +0 → +127 and -0 → -127 since one of our eight bits is only for sign information.

Let’s run another subtraction experiment to see how this work:

Well, shoot. +10 != -6, at least most of the time. Obviously our number representation system is incompatible with this subtractor solution. For that matter… how can we do additions with this system? After all +5 + -2 = 3. If we were to try that with our full adder from the previous lab, it would not work. I won’t even run through the example to prove it, Just Trust Me.

This number representation system we’ve come up with needs a ton of supporting circuitry to work. We would need to bring a sign bit check int our adder to invoke special subtraction logic, we would need to handle the rollover condition properly for going from positive to negative in a subtraction, and more myriad issues.

Let’s take a different approach. Let’s keep the whole most significant bit is sign bit idea, but flip it. How about we leave well enough alone for the positive numbers. MSB is 0 = + | 1 = -. This lets us just keep 0001 = 1, 0010 = 2, …​ and so on. So… how do we count negative numbers? If we just do the same thing we did above and say 1001 = -1 we will be just as in trouble as we were before. So, again, let’s flip the script.

Let’s say that negative numbers are represented as the bitwise inversion of their positive counterpart – also known as compliment. This means:

Alright, let’s try our trick with 0 - 1:

OK… so this produced the same answer, obviously, but what does this mean? Well, since we have decided that negative numbers are the bitwise inversion of their positive compliments, we can say that 1111 = -0. Oh… negative zero. That’s not -1 but it sure is closer than 15.

But… what if we have a way out? I’ve marked the final borrow up above with two asterisks. If we simply wire this up to the borrow input of the LSB subtractor, creating something called an end-around borrow this might just work:

AHA! That’s it. 1110 is -1. With this end around borrow, we successfully can represent negative numbers and construct a working subtraction circuit. It has just one final test to pass – can we do addition with our number format with a regular adder?

Oh… heck. This is 0000 = +0 not 0001 = +1. However, the astute among you may have noticed that there is yet another carry marked with a double asterisk. Correct! If we do what is called an end-around carry we will now get the right answer:

Excellent! We now have a number representation that can use completely regular adders and subtractors to keep track of all signed integer arithmetic. We could implement a full computer around this! We have used this method to split our unsigned integer space into a signed one, from +0 → +7 and -0 → -7. Notice this system just did 2 - 1! It can subtract with an adder, given we can just find the compliment for any input number to do subtraction.

This system we have discovered together is called Ones’ Compliment. It suffers from a number of problems (pun intended) including two we have already faced. We have two zeros (+0 and -0) as well as requiring the end-around borrows and carries. For reasons we will get into in later labs, that end-around problem causes absolute havoc with computer systems and makes them significantly more slow than they would otherwise be. However, it has some notable advantages as well. We don’t need to implement a standalone subtractor circuit, as we can just add the negative version of a number to simulate subtraction, and getting the compliment of any number is as simple as inverting all of its bits.

In the previous section we established that Ones’ Compliment is a workable method for tracking signed integers and using regular adding circuitry to do addition and subtraction. However, the end around carry is a real downer. Let’s see if we can get a new representation system that can save us.

Referring back to our first problem example:

What if we just… say that 1111 = -1? This is basically the same operation as we saw in One’s Compliment except that we just skip past the end-around borrow. How would this system work? It passes at least one sniff check – we can run our result back through a completely normal adder to reverse things:

The entire above operation can be done with an utterly standard adder, making our -1 + 1 = 0 test work. It also looks the same as the Ones’ Compliment addition, save the absence of the end-around carry. However, we now have an issue. Previously, with Ones’ Compliment, in order to invert a number, all we would have to do is bitwise invert. That won’t work anymore, as 0000 (0) ⇒ 1111 (-1). Remember, the goal here is to design a number system that can operate with mostly unmodified adders only, as bringing a subtractor into our design is extra circuitry.

The solution to this is relatively easy for Twos’ Compliment, however. Since we have effectively shifted our negative numbers down, now representing 0000 (0) → 7 (0111) and 1111 (-1) → 1000 (-8), we can start with a Ones’ Compliment intermediary and add one to it to convert. Let’s see as follows:

That, by the way, is what makes it a Twos’ Compliment. Whereas the Ones Compliment is called so because a number and its compliment, when added together, are all 1s. The Twos’ Compliment is called so because when two N bit numbers are added together, their sum is 2^N. We can see that example here below:

Let’s make sure this works by performing a subtraction with an adder. To do so, we will need to find the compliment of our second number to make it negative. Let’s do 5 - 2. The Twos’ compliment of 2 is 0010 → 1110 based on our previous steps:

Nice! Our subtraction gave us the right answer. That means our Twos’ Compliment is a fully working signed number system that requires only the use of regular adders in a computer system to build a full set of basic addition and subtraction. Keep in mind the examples I have shown are for a four bit system, and the ranges of positive and negative integers will change with the radix.

Hopefully, by this point, you can see how effective Twos Compliment is. It allows us to use totally regular unsigned integer adders to do both addition and subtraction. Also, it does not force us to do the complicated end-around carry/borrow that Ones Compliment does. This means minimal additional circuitry imposed upon our computers, and things can now run faster than if implemented in Ones Compliment. However, as you can also see, there is not really anything overtly complicated within these concepts. Most of what we’ve seen in this lab is combining our already-written full_adder from the previous lab. Twos Compliment, while initially seeming to be a complicated concept, is simple when we look at it from a practical point of view.

If you are having troubles wiring up your top level module, see here.