Sunday, 14 December 2014

Four Bit Full Adder Tutorial

It's time for some digital logic.  I haven't written much on digital logic for some time as to be honest I don't use it much. These days electronics is dominated by microcontrollers and FPGA technology. Logic gates have their place but they aren't used nearly so much any more. Logic can be programmed these days.

Before the days of cheap and easy to use microcontrollers however digital logic was everywhere and used in nearly every electronic circuit.  There are two main families - CMOS and TTL.  CMOS is based on FET transistor technology and TTL is based on bipolar transistors.  The actual devices themselves perform logical functions such as AND, OR and NOT.  From these functions almost any other function can be found.

This tutorial is going to discuss a lot of things but primarily we are going to design and simulate a 4 bit full adder - a logic circuit to take four digital input values and add them together and provide an output.

Binary is a system of counting using ones and zeros.  Computers and digital electronics circuits use binary to represent numbers.  These values can be physically represented by switches or transistors. When a switch is ON it represents a binary 1, when a switch is off it represents a binary 0.  Lots of 1s and 0s together can be used to represent large numbers.  Binary is also known as a twos complement number system.

Binary numbers are normally written in blocks of 8 characters with a space halfway between each 'block':

The number above 1001 1001 can be converted into decimal quite easily -

128 + 0 + 0 + 16 + 8 + 0 + 0 + 1 = 153

1001 1001(b) = 153(d)

each 'block' is known as a byte and half a byte is known as a nibble - see electronics engineers do have a sense of humour!

Anyway adding Binary numbers together is exactly the same as with decimal numbers.  Lets try an example:

8
+ 4
1 2

When we perform the above sum we performed several operations either on paper or in our head. We read the first number (input), we read the second number (input) we performed an add operation (process) and then an result was provided (output)

The reading of the inputs is easy, the summing operation is hard.  We took the number 8 and added 4 to it.  When we did that we used a carry operation.  The result is greater than 9 so a new tens column is required.  So in order to perform this operation we also need a carry function.

To perform the calculation above several things are required: we need a place to store the first number, a place to store the second number, a carry flag and finally a space to store the result.  The 'space' to store the first number is known as a memory register.  The second number is also stored in a memory register.  The number itself is known as an operand.  The sum function is known as a process or operator and the answer is known as the result.

Binary addition is performed in exactly the same way with the same words to describe the parts of the process:

1000 (1st Operand)
0010 (2nd Operand)
1010 (result)

As:

0 + 0 = 0
0 + 1 = 1
0 + 0 = 0
1 + 0 = 1

and 1010(b) = 12(d)

There is one operation that was overlooked.  When we perform a 'sum' operation we look at each column present and add the numbers together whilst checking if there was a carry in from the previous operation.  The carry is stored in it's own special register - also known as a status flag.  If a carry is generated during the sum we 'trip' the carry flag (carry out), write the result from the sum in the present column and move to the next column, check the carry flag and if it's present add one to the sum operation (carry in).  This process is repeated until all of the columns have been 'summed'

So in actual fact we need a carry in flag, a carry out flag and two 4 bit binary numbers (operands)

We know how we can perform a summing operation on 'paper' but how do we recreate this using electronic components?  The answer lies in constructing a truth table.  It's a table listing all the possible inputs and outputs for every possible sum in a 'nibble' or four bit number.

The range of the two numbers is 0(d) to 15(d) which is 0000(b) to 1111(b)

So the first section of the truth table are all of the numbers between 0000(b) and 1111(b)

Here is a table showing the values in decimal and binary:

The final truth table is the result of the sum of the above twice with a carry in and out function and the results. So what we need to do is on paper write down every possible sum and every possible result and if a carry was required.....thats a lot of sums!  Lets get to it:

0000
+ 0000
0000 - no carry in and no carry out

0000
+ 0001
0001 - no carry in and no carry out
0001
+ 0000
0001 - no carry in and no carry out

0001
+ 0001
0010 - no carry in and 1 carry out

0010
+ 0000
0010 - no carry in and no carry out

etc etc etc....

(this is so BORING!!!)

I'm not going to list each operation but continue to construct a truth table.  As the truth table comes together the results can be calculated (still BORING!!!)  I hate theory sometimes I'm more a practical person, I like the practical not theory!  The truth table doesn't take account of a carry in or out only whether a carry operation occurs.  Here is the table:

From this we need to simplify.  We can ignore the 16(d) column as its the same as the carry column. Lets instead of adding two 4 bit numbers together lets add two 2 bit numbers.  The truth table with a carry becomes much simpler!

If we look at the simpler truth table we can see that the result is almost the same as a logical Exclusive OR function.  Result = A 'logical EX-OR' B and the carry is the same as a logical AND function.  If we were to write this out in boolean logic it would be:

This is known as a 2 bit half adder.  Its called a half adder because it doesn't have a carry in function.
To make it a full adder we need to add a carry in function.  That is fairly simple to do....lets just combine two half adders together:
So now the Boolean logic is:

What we need to do is now upscale this for two 4 bit numbers.  So lets just repeat it four times:

There is a well known trick with boolean logic that you can create any logic function with NAND gates or NOR Gates.  Here is the theory...

Lets look at the truth table for an AND gate (Result = A.B):

How can we achieve this function from just NAND gates?  The trick lies in inverting the inputs and outputs.  We can make an inverter by joining the A and B inputs of a NAND gate together.  Here is the way we can turn a NAND gate into an AND gate - just invert the output - simples!

Here is the truth table and circuit:
Next lets make an OR gate from NAND gates.  Its the same sort of trick.  If we invert the inputs to the NAND gate using NAND gate inverters we can make the OR function.  Here is the truth table and circuit:
Now we need to make an EX-OR gate from NAND gates....a little more difficult but still possible and we are going to need lots of NAND gates!  The boolean function for the EX-OR function is:
Now lets make this function occur with just NAND Gates.  Here is the circuit:
Now that we have created all of the logic functions required we now have to combine them all together:
Now to turn it into a 4 bit full adder we need to repeat the circuit and connect the carry outs to the carry in....It gets complicated!

I don't recommend anyone actually tries to realise this circuit!  It would take 12x 74LS00 chips and a lot of patience!  I haven't discussed Karnaugh Mapping which is a technique for simplifying boolean algebra expressions.  It wasn't really needed in this case.

Take care - Langster!