For this week, here's the plan, Fran…
OK, so now we've seen a whole BUNCH of different encodings. Remember that these are really just long sequences of bits. Also remember that the processor couldn't care less what the bit patterns are really supposed to MEAN. The processor just does what we tell it to do with the bits it is given!
But HOW DOES IT KNOW? AND HOW DOES IT DO THAT?
The answer, of course, is in the logic circuitry of the processor, and here are the basic building blocks that make the magic happen!
As programmers, we have often used the boolean data type. We know well that it can have only one of two values, either true or false. That fits perfectly with the idea of binary, on or off, and with the way a digital computer works, as a series of switches. We've seen how we can represent the information of numbers and characters in the memory of a computer. But how the heck do we get those on and off states to turn into actual computation? What does the computer actually DO when adding two numbers?
There are a couple of terms associated with the concepts of digital logic:
ICthere are lots of transistors, resistors, capacitors, teeny-tiny wires, all on a VERY VERY VERY small device. See the picture below.
There are three basic types of gates: AND, OR, and NOT.
They are all made with transistors, which are like tiny on/off switches. The AND gate
circuit is set up so that only when both of the transistors are ON
will it produce an output; at
all other times [both inputs off, one on and the other off, the other on and the one off] there will be
NO OUTPUT [actually a zero
voltage level]. Here is the logic diagram symbol:
In the diagram, |
AND GATE TRUTH TABLE | ||
---|---|---|
A | B | Y |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
The OR gate comes next. Notice the similarity of the diagram. There are still two inputs,
|
OR GATE TRUTH TABLE | ||
---|---|---|
A | B | Y |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Last but not least is the NOT gate, also known as an inverter because whatever logic level appears on its input, the OPPOSITE value appears on its output. |
NOT GATE TRUTH TABLE | |
---|---|
A | Y |
0 | 1 |
1 | 0 |
From these three simple gates, you can make all the parts that are required to have an entire computer! Of course, there are BILLIONS of these gates in a modern CPU, but it all boils down to the combinations of those basic circuits.
One of the first things that engineers do with gates is combine the AND and the NOT to make a special
type of gate called a NOT-AND
gate, or more commonly, a NAND gate. The idea is
to take the output of an AND gate and run it through a NOT gate. Usually a little circle is put on the
output of the AND gate to denote that it has the inverter function on the output. If you look at the
diagram above for NOT you will see that little circle, or bubble
on the output. That bubble is
what is coopted for use with the NAND gate.
You can also make a NOR gate, and by combining those three gates you can create an XOR or exclusive OR gate. You can combine those functions in other ways to make another device called a flip-flop, and other devices called adders, multiplexers, selectors, and many more. In fact, the central part of the CPU, the Arithmetic Logic Unit [ALU] is exactly that kind of composite device!
You will have a chance to study and learn the operation of these devices in more detail in your Logic Class, EE 385, later in your career here. For now, we'll be looking at ways to combine the parts using our truth table approach.
First, let's look at a way to model a NAND gate using our truth tables. As you know, a NAND gate is just an AND gate with a NOT on the output. So, we can model that with the following table:
NAND GATE TRUTH TABLE | ||||
---|---|---|---|---|
A | B | A 'AND' B | 'NOT' A 'AND' B | Y |
0 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 0 |
Since the Y
and the 'NOT' A 'AND' B
values are the same, we can abbreviate the table as
follows:
NAND GATE TRUTH TABLE | |||
---|---|---|---|
A | B | A 'AND' B | A NAND B |
0 | 0 | 0 | 1 |
0 | 1 | 0 | 1 |
1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 |
We can do similar things for tables with combinations of gates. For example, consider a device that has two inputs, A and B. Let A be the input to BOTH a NOT and an AND, but with the NOT output going as input to a SECOND AND gate. Then let B be the input to BOTH a NOT and an AND, but with the reverse of the other set up. Then let the outputs of both AND gates become the inputs to an OR gate. The output will actually end up being a XOR gate! We can then have the following truth table:
NAND/OR GATE TRUTH TABLE | ||||||
---|---|---|---|---|---|---|
A | B | N | M | BN | AM | Y |
0 | 0 | 1 | 1 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 | 0 | 0 | 0 |
Note here for clarity, N
is the NOT of A, M
is the NOT of B, so that BN
is the AND
of B-AND-NOT-A
and AM
is the AND of A-AND-NOT-B
. TheY
output then is the
output of the OR of those two columns.
Now that you know what the table looks like, see if you can draw what the gate diagram [also known as a schematic diagram would look like. After you've given it a shot, click here to see the answer.
The next thing we need to look at is the way that computers add. It's actually much simpler than what we
are used to with normal
addition, because we only have to use two bits of input and one bit for
output. There are, of course, four possible input combinations, and four possible output combinations,
as you can see from the following table:
HALF-ADDERTRUTH TABLE | |||
---|---|---|---|
A | B | SUM | CARRY |
0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 1 | 1 |
Looked at in the more traditional
format, it looks like this:
0 0 1 1 0 1 0 1 -------- -------- -------- -------- 0 sum 1 sum 1 sum 0 sum 0 carry 0 carry 0 carry 1 carry
The logic circuit for a full-adder is a little more advanced than we will delve into this week. For now, see if you can follow the logic, knowing what you now know about the gate operations. Basically, the sum output is the XOR of the inputs, and if both the inputs are ON, the AND gate generates a carry output. |
The various gates, both individually and collectively as combinational logic
functions, are available on Integrated Circuit [IC] chips. There are several different
families
of these.
Here is a link to the
Wikipedia page that lists and describes the 7400
family. The picture below shows
Investigation: See if you can figure out the truth tables for the following combinations of gates.
That's probably enough for the this week. Be sure to check out the links on this page. Try to figure out a few truth tables for combinations of gates. Don't forget the test on Wednesday/Thursday!