Number theory and lab 3 continued

So, the schematics below may not make a terrible amount of sense, so let me go through the process.

The idea is that you have a set of tools, namely AND, OR, NOT and XOR. With these four operators you can express just about any set of outcomes. In the case of lab 3, we are looking for a way of expressing addition and subtraction in a simple manner that can be infinitely expanded.

This may sound daunting, but it’s not; it’s only a puzzle. So, like a puzzle, we are looking for not only correct combination, but efficient ones. This usually requires stripping a problem into smaller chunks and analyzing what the exact parts.

Let’s start with normal addition, namely two numbers at a time. If you add just single digit numbers it may look like the following:

This is the simplest addition possible. No carry, only 1 digit numbers. We can also do larger numbers and carries, but how to look at them? Well, for instance, you will never carry a number larger than 1 in this kind of addition, even in the largest numbers we can muster.

So, it can stand to reason that you will never have to carry a number larger than 1 in any base. A valuable piece of information.

Next, we figure out that we will have up to 3 numbers being added, the “x” bit, the “y” bit and the “carry” bit. It also stands to reason that if all 3 were 1’s, the largest outcome is 1 with a carry of 1. So we split the system twice. X + Y + Carry (handled by using XOR gates) and then figuring out IF there is another carry. It stands to reason that if ANY 2 of the 3 inputs are 1, then the carry will need to be one.

Great, so how do we implement that? Well, we construct a table of all possibilities, like so:

I unfortunately do not have the space to explain the methods to how I built the “carry” system in my adder, this is what the entire system looks like:

The next section we need is to be able to handle subtraction. Usually, in binary we use two’s compliment. To oversimplifiy, you express negative numbers by inverting the bits + 1. This also requires an extra bit. So +9 (01001) can be expressed as -9 (10110+1=11000). This may sound overly complicated, but it makes life very easy on the logic level. By tying one end of an XOR to a switch (creating 0 for addition and 1 for subtraction) then the other to the “y” input (in this case) it will flip the bits as so. This way with using our “full adder” we can also have a subtracter with the flip of a switch.

Next Lab: Multiplying
~Locke

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: