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.

4 Way DMux

In this exercise, we will build a 4 way DMux.

We have already implemented a simple (2 way) DMux. In that there is one input line, and one selector. The value of the selector, determines, which output line the input is routed to.

In a 4 way DMux, we have 1 input line, 4 possible output lines, and 2 selectors. Based on the value of the selector, the input line is router to one of the 4 output lines.

We can implement a 4 way DMux, using multiple regular (2 way) DMux's. If we look at the truth table, we will notice that if selector[0] is 0, then in can be routed to either 'a', or 'c' (based on the value of selector[1]). If selector[0] is 1, then the input can be sent to either 'b', or 'd' (based on the value of selector[1]).


The code for the 4 way DMux us specified below.

Mux 8 way, 16 bit

In this exercise, we build an 8 way, 16 bit Mux. What this means is that there are eight input arrays (of 16 bits each), for which we will need 3 selectors, and these selectors will select one of the eight input lines to appear as the output.

If we look at the truth table below, we notice that we can apply a 4 way Mux to lines A,B,C,D (using sel[0], ans sel[1]) and another 4 way Mux to E, F, G, H (using sel[0], ans sel[1]). This will result in two lines (one from each set moving ahead). We can then apply a simple Mux to select from one of them, using sel[2].

The code for the 8 way 16 bit Mux is embedded below:

Mux 4 way 16 bit

A 4 way, 16 bit Mux is a Mux which which can select among 4 input lines. To select from 4 input lines, we need log24 selectors.

Because this is a 16 bit Mux, each input line is an array of 16 bits.

Looking at the truth table for the Mux, we know that if sel[0] is 0, then line 'a', and 'c', can be selected. While if sel[0] is 1, then line 'b', or line 'd' are selected. So basically sel[0] will cause one set ('a','c' or 'b','d') to be selected.

sel[1], will select one line from the winner.

So, if sel[0] is 0, then the set 'a', 'c' is the winning set, from which one line will be selected by sel[1]. If sel[0] is 1, then set 'b', 'd' is the winning set from which one line will be selected by sel[1].

The code for the 4 way, 16 bit Mux is specified below.

Built an 8 way OR chip

In this activity, we have to build an 8 way OR chip. An 8 way chip is a specific case of an n-ary chip. It takes n (in this case 8) inputs.

An 8 way Or chip, basically takes 8 inputs and applies the OR function on all of them, and finally provides the output on it's 'out' line.

We will built an 8 way OR chip, using the regular 2 pin OR chip, which we have already built.

We have to cascade multiple of these chips to get the output. There are different ways to cascade them... some more efficient than others.

The code for this activity is embedded below.

Built a 16 bit Mux

Built a 16 bit Mux. A 16 bit Mux is very similar to a regular Mux, except that instead of receiving it's input from 2 pins, it receives it's input from an 2, 16 bit arrays. Code for the 16 bit Mux is embedded below.

Or 16 bit chip

The 16 bit Or chip is again very similar to the 16 bit And chip, except that we use the Or chip to connect the input lines with their corresponding output lines.

And 16 bit chip

The 16 bit And chip is similar to the 16 bit Not chip, except that we use the And chip to connect all the 16 input lines to their corresponding 16 output lines. The code is embedded below.

Not16 Chip

The Not16 chip is very similar to the Not chip, except that it has 16 input lines and corresponding 16 output lines.

We need to use 16 Not chips, where we connect each input line to the corresponding output line. I thought HDL might have a loop structure where I could specify the 6 Not chips, but looks like it does not. Had to manually specify the 16 Not chips. The code for the chip is specified below.

Building a DMux

A DMUX is the opposite of MUX. It recieves one input and based on the value of the selector bit, it routes that input to one of two output lines.

Looking at the image above, if sel is 0, then the value of 'in' will be routed to O0, and if sel is 1, then the value of 'in' will be routed to O1.

To achieve this, we can AND 'in' with '`sel', sending that output to O0. We also AND 'in' with 'sel', sending that output to O1.

Mux

A Multiplexer (MUX) is basically a selector. It has two input pins and a selector pin. Based on the selector, it selects one of the input pins.

If the selector is 0, then 'a' is selected, and if selector is 1, then 'b' is selected.

Let's start with an Axiom. Anything ANDed with 1 will result in that thing. So, 'a' AND 1 = 'a'

If we AND 'a' with NOT(selector), then the output of that AND gate (let's call it a1) will be 'a' if selector is 0. Similarly, if we AND 'b' with the selector, then the output of that AND gate (let's call it a1) will be 'b' if the selector is 1.

But along with this, we actually have to implement a conditional. If selector is 0, then 'a', else 'b'. The way to implement conditionals with logic gates is using the OR gate.

Now, if selector is 0, then 'a1' will carry the value of 'a', and 'a2' will carry 0. If selector is 1, then 'a1' will carry 0, and 'a2' will carry, the value of 'b'. Thus if we perform a1 OR a2, then we will get the correct answer.

Xor chip

Built an Xor chip

Or Chip

I have built the Or chip.

And Chip

Completed the And chip

Remember:

If there is a bug in the hdl program, such as incorrectly naming a part, it will simply not load the chip, but will not throw any errors.