CMSI 284: Welcome to Week 05

This Week's Agenda

For this week, here's the plan, Fran…

Logic Components

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?

The answer lies in the digital logic components from which the CPU is made. These are the working circuts that make the magic!

There are a couple of terms associated with the concepts of digital logic:

Gates and Truth Tables

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:

AND gate animation

In the diagram, A and B are the inputs, and Y is the output. Notice how when the A and B lines are black, or if either one of them is black, the line for Y is also black. However, when BOTH A and B lines turn blue, indicating they are ON, the line for Y is also blue. The idea is that for there to be an output there must be both A AND B inputs active, which is why it is called an AND gate. This situation can be modeled with a AND gate truth table as you see below:


AND GATE TRUTH TABLE
ABY
000
010
100
111

The OR gate comes next. Notice the similarity of the diagram. There are still two inputs, A and B, and one output, Y. The lines still turn blue to indicate when they are active. However, in this gate, the output line for Y turns blue if EITHER ONE of the inputs is blue. This meand that it will produce an output if either A OR B input is active, which is why it is called an OR gate. This situation is modeled with the OR truth table, as you can see below:

OR gate animation

OR GATE TRUTH TABLE
ABY
000
011
101
111

NOT gate animation

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
AY
01
10

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.

Combining the Parts to Make a Machine

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
ABA 'AND' B'NOT' A 'AND' BY
00011
01011
10011
11100

Since the Y and the 'NOT' A 'AND' B values are the same, we can abbreviate the table as follows:

NAND GATE TRUTH TABLE
ABA 'AND' BA NAND B
0001
0101
1001
1110

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
ABNMBNAMY
0011000
0110101
1001011
1100000

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-ADDER TRUTH TABLE
ABSUMCARRY
0000
0110
1010
1111

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.

Half-adder diagram

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.

Week Five Wrap-up

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 Thursday/Friday!