Introduction to Binary Logic Circuits - by Nick Fletcher (2006)
home | page 1 | page 2 | page 3 | page 4 | page 5 | page 6
I still haven't explained how machines manipulate those bytes to produce the addition of
numbers… Well, let's
start small and work our way up.
Think back to our LOGIC GATES. The secret to machines being able to add numbers is in those gates and it
starts with the OR GATE.
The OR GATE is the addition operator between two bits! Think about it. If you have an OR GATE that has
two bits as input,
the output of that OR GATE is the sum of the two inputs. Ah...… Not so I here you scream. The OR
GATE will lose one of
the input bits if there are two of them. Did I lose you?! Think of the TRUTH TABLE, or
better yet,
refer to it above.
Let's imagine you wish to add 0 and 1. Having those two values as the input to an OR GATE will give the
output of 1, which is
correct! But… If we are trying to input two 1's into the OR GATE, the output is ONE!!! Wrong
answer...
(Please note that I use 1 to represent anything above the threshhold voltage and 0 for below it.
You
can imagine
what I'm describing as a real light switch, a bit in a computer or a fantasy world re-enactment...!
To us, they may as
well be the same.). And in our code, there is no provision to have a '2' in one of the
columns!
Our code can only be
made of 1's or 0's or on lamps or off lamps! There is no doubly bright lamp to represent the number 2 in
a column, and it wouldn't
make sense anyway…
"Quite the conundrum."
All is not lost, we just have to ask the AND GATE if it can help us out. You see, binary numbers behave
the same way as decimal
numbers. It's like magic really. In decimal, we have symbols that we map to real life amounts. The
symbols range from 0 through 9.
Using these 10 symbols, we can represent any amount of things. The key to this
representation lies in how we display
those numeric symbols.
(If this is starting to put you to sleep, trust me, it gets very interesting, very
soon!)
We arrange our symbols/numerals into columns and each column has a 'weight' associated with it. The
rightmost column
has the units weight. We multiply any symbols in that column by 1. Moving left, we have the 'tens' and
then the hundreds
and so on. Each column can display all the numerals from 0 to 9, but when a column ticks over past 9, we
have a carry over
into the next column. This happens every ten ticks for each column. It's exactly the same
principle in binary notation, with
a different amount of 'ticks'. There are only two symbols in binary, 0 and 1. And remember, we can map
those values to
anything we like, including the reading of voltages above and below certain thresholds.
To count in binary notation, you start as with decimal, at zero. Then comes one, then... Then, we carry
over to the next
column and leave a zero in the first column.
0000 00 0001 01 0010 02 0011 03 0100 04 0101 05 0110 06 0111 07 1000 08 1001 09 1010 10 1011 11 1100 12 1101 13 1110 14 1111 15
Now here's an idea! What if we attach an AND GATE plus an OR GATE to the inputs and run 'em side by
side???
Remember that the AND GATE only gives an output of 1 if all inputs are 1? And in binary, what happens if
you have
to represent 2 bits in the same column? Nothing. It's not possible. You have to carry a bit to the next
column
and leave what's left.
This is the setup we now have. We have two inputs, both going to an OR GATE and an AND GATE. Whatever
comes out of the OR
GATE is the result of the addition. Whatever comes out of the AND GATE is the carry! We now have a
machine that can
add two binary digits together and arrive at the correct answer. Here is a run down of what will
happen.
Let's say, we wish to add together 1 and 0. Our sum will look like this:
1 + 0 = ?To get the machine to do this, we put the two inputs through it like this:
INPUT #1(1)----------->|INPUT #1 | |OR GATE -----> 1 INPUT #2 | (0)------->|INPUT #2 | | | | | | | ------>|INPUT #2 | |AND GATE -----> 0 ----------->|INPUT #1Sorry if that looks really confusing, but it is just supposed to represent that we send both inputs through both the AND GATE and the OR GATE at the same time. It's not very useful in this form though. What we would really like is to send the output from the AND GATE into the next 'column' to show that a carry was produced. Remember, this will only be the case if both inputs were 1's. There is another problem with our little machine, but we should understand something important first.
What we are trying to achieve here is a machine that can add a bank of binary digits or bits to another bank of bits. Particularly a bank of 8 bits! The above diagram describes a single column from that bank. To make a machine that can add eight bits to eight other bits, you would need eight OR GATES and eight AND GATES connected as shown above. The output from the AND GATE in each column will be sent to the input of the AND GATE/OR GATE arrangement to it's left to effect the carry. This way, the carry can be part of the equation also, and we'll examine that soon. For now, let's look at the major flaw in my circuitry!
If we run another set of bits though the wonderful electric adding machine, we will discover that it gives incorrect results. Why? Consider the follow sum:
1 + 0 = ?To get the machine to do this, we put the two inputs through it like this:
INPUT #1(1)----------->|INPUT #1 | |OR GATE -----> 1 INPUT #2 | (1)------->|INPUT #2 | | | | | | | ------>|INPUT #2 | |AND GATE -----> 1 ----------->|INPUT #1Can you see the error? It's in the OR GATE. When we add binary 1 with binary 1 we should carry a one over to the left and leave 0 in the original column. We are doubling up on work here. The OR GATE is actually telling us about the carry also, but it's output stays in the column. What we need is an OR GATE that only outputs a one if one or the other inputs is a 1.
This can be done, but first we need another type of gate called the NOT GATE. The NOT GATE only accepts one input and gives one output. Whatever you input is output as the opposite value. If you input 1, you'll get the output of 0 and vice-versa.
We will use the NOT GATE to build something called an EXCLUSIVE OR GATE. The EXCLUSIVE OR GATE or XOR GATE is very important as you may now realise! Here is it's truth table:
The XOR Truth Table | ||
---|---|---|
input 1 | input 2 | output |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Only when the inputs are different will we see an output from this gate. How can we build one using an AND GATE, OR GATE and a NOT GATE? We use the truth table and place gates to correspond to the results we want. For inputs of (1)(1), we want an output of 0. For either (1)(0) and (0)(1) we need an output of 1. Let's put two AND GATES side by side:
INPUT1 AND INPUT2 INPUT1 AND INPUT2
INPUT1|--------------IN1 | AND1-----IN1 ---+--------NOT1--IN2 OR------------->OUTPUT | | ---IN2 | | | | NOT2----IN1 | | AND2---------- INPUT2--------IN2This amazing contraption(!) is my own design based on a sketchy memory of one I saw a long time ago! Let's test it with some sums:
1 XOR(mine) 0 = 1(trace through the above diagram to find the answer(I know it's a bad diagram!)) 1 XOR 1 = 0 0 XOR 1 = 1 0 XOR 0 = 0The two inputs are split into four, two for each input. One branch of the the split input is sent to an AND GATE unchanged, but the other branch is inverted and sent to the other AND GATE. This means that the two split portions of the input can never be the same as each other. Using the logic of the AND GATE, we see that only when the inputs are different can we see an output. If the inputs are both 1, they will cancel each other out! That's exactly what we want. Also, the OR GATE at the end there is a way to tie the double output to one output. An OR GATE can never show less than what is input to it. The OR GATE is saying, "I don't care which AND GATE produced an output, either is good enough for me!". What a nice OR GATE. We also cover the event of both inputs being zero. This would mean that a zero and a one are sent to each AND GATE, and we know that AND GATEs need all inputs to be 1 before they give an output of 1.
We can hide the implementation of the XOR GATE because we know how it works. Let's place it back into the original adding machine and check the results.
INPUT #1(1)----------->|INPUT #1 | |XOR GATE -----> 0 INPUT #2 | (1)------->|INPUT #2 | | | | | | | ------>|INPUT #2 | |AND GATE -----> 1 ----------->|INPUT #1
Fingers crossed... SUCCESS!
home | page 1 | page 2 | page 3 | page 4 | page 5 | page 6
nickeax AT gmail.com