Building the ALU

In this exercise, we build the ALU. This is taking some amount of thinking. Tackling the problem in baby steps.

I created a few internal chips

OpZ16: Takes as input a 16 bit bus and a single bit. It will output 0 is the single bit is 1, otherwise the output is the same as the input.

OpN16: This chip accepts as input a 16 bit bus x[16], Xor a single bit in. The output of this chip is also on a 16 bit bus. If in == 1, then the input is negated to produce the output, otherwise the output is same as the input.

DetectZero16: This chip takes a 16 bit input, and outputs 1 if the input is zero, and outputs 0 if the input is not zero.

DetectNeg16: This chip takes a 16 bit input, and outputs 1 if the input is negative, and outputs 0 if the input is not negative. I am detecting if it is negative, purely by the value of the MSB.

The last two chips had to be created because an internal bus cannot be subscripted.

Finally, here is my ALU:

As part of the peer learning method, I commented on the following peer posts:

1. http://wcdiycs.blogspot.in/2011/08/alu-activity-5.html
2. http://siabard.wordpress.com/2011/12/23/activity-5-tecs-build-an-alu/

16 Bit Incrementer

In this exercise, we will build a 16 bit incrementer. This chip takes a 16 bit number as input, adds 1 to it, and produces a 16 bit output.

This chip seems to be very similar to the 16 bit adder, except that the second number is hard coded to be 1. However, we will not get this '1' as input. We will have to represent it internally. We can represent it as the result of an AND chip, but this is just a possible representation. It is possible to represent 1 in many ways. Also notice the last line in the script. Instead of a HalfAdder, we use an OR gate... guess why...

16 Bit Adder

Now we build the actual thing which will be used in an ALU. Assuming we have a 16 bit bus, we would need to add 16 bit numbers. So we probably need to add 2 numbers such as these:

Notice that the 2 LSB's can be added using a half adder, but after that there may be carry bits, so we will need a full adder for the subsequent bits. So this means that a 16 bit adder can be implemented using 1 half adder, and 15 full adders. If a carry bit is generated at the MSB position, it will be ignored.

Full Adder

In this assignment, we will build a full adder. A full adder adds 3 bits to produce a sum and carry bit.

Why do we need to add 3 bits ?

Let's understand with an example. The image below shows how we add 2 binary numbers.

Notice the carry bit at the top of the addition. For many columns we actually need to add 3 bits. The 2 actual bits and the carry bit.

This is why we need a Full Adder, which will add 3 bits, to generate a sum and carry bit.

So, how do we implement a full adder? Let us look at the truth table.

A Full Adder seems to be a combination of 2 half adders.

The script is embedded below (I am not showing how I deduced this... but it is documented in my notes on paper)

Half Adder

A half adder adds 2 bits to give us the sum and the carry bit.

a b | sum carry

----------------

0 0 | 0 0

0 1 | 1 0

1 0 | 1 0

1 1 | 0 1

Now we need to implement this in logic using the basic gates we have built till now.

We will use different logic for the sum and carry bits.

a b | sum

----------

0 0 | 0

0 1 | 1

1 0 | 1

1 1 | 0

The above truth table is that of an XOR chip.

a b | carry

----------------

0 0 | 0

0 1 | 0

1 0 | 0

1 1 | 1

The above truth table is that of an AND chip.

From the above inferences, we can implement a half adder using an XOR, and AND chip.

Here is the HDL code of a Half Adder.

ALU Notes

The ALU or the Arithmetic Logic Unit of a computer is the part which is responsible for arithmetic computations. Before we proceed with the ALU, let us understand some basic concepts.

Representing negative numbers in binary:

We represent negative numbers using the 2's complement of a number. What this means is that -4 is represented as the 2's complement of 4. So what is the 2's complement of a number. The 2's complement of 0 is 0. For any non zero number, the 2's complement of a number represented by n bits is 2^n - number.

What is -4 in an 8 bit number.

4 is 00000100

-4 is 256 - 4 which is 252 which is 11111100

So -4 can be represented in binary in 2's complement form as 11111100

How do we know if this result is correct. Let us add +4 and -4. This gives us 100000000. If we remove the overflow bit, it gives us 0, which is correct.

If we want to compute the 2's complement manually, we can follow a trick. Take the +ve number and ignore the LSB 0's and the first LSB 1, and then flip everything else.

+4 is 0100

-4 is 1100

To compute the 2's complement mathematically, we should negate all the bits and add 1.

8 Way DMux

In the last exercise, we implemented a 4 way DMux.

In this exercise, we will implement an 8 way DMux. For an 8 way DMux, we need 3 selector pins.

Here we can use one regular (2 way) DMux, and two 4 way DMux's we created in the previous exercise.

Till now, when cascading, I have started from selector[0] and then moved towards selector[n]. In this example I am going the opposite way. We will start with selector[2] and then move on to selector[1] and selector[0].

If you look at the truth table, selector 0 can be used to create 2 sets. The first set, when selector[0] is 0, can result in the output being routed to 'a', 'b', 'c', or 'd'. The second set, when selector[2] is 1, can result in the output being routed to 'e', 'f', 'g', or 'h'.

Here, since we are fanning out into 2 sets, we need to use a regular (2 way) DMux. This DMux will have 2 output lines. Each of these output lines will be fed into a 4 way DMux to create a total of 8 output lines.

The code for the exercise is embedded below.