Lecture Notes

for

CSCI 301: Great Ideas in Computer Science

(c) 1993, 1994, 1995 John E. Howland, All Rights Reserved

Department of Computer Science

Trinity University

715 Stadium Drive

San Antonio, Texas 78212-7200

Internet: jhowland@ariel.cs.trinity.edu

4 Computer Circuits ( Terminal Session on this Machine )

Most computer processors are fabricated from a few simple component circuits which have been designed in such a manner as to make it easy for a designer to connect the outputs of one circuit to the inputs of another circuit. This allows complex circuits to be built from simple components in a sort of building blocks fashion.

The TTL (Transistor Transistor Logic) circuit family is one such circuit family. TTL circuits use two voltage levels, 0 volts and +5 volts to represent the two binary digits 0 and 1 respectively. This circuit family also has the property that, within certain reasonable limits, it is possible to wire the outputs of one TTL circuit to the inputs of another TTL circuit and not have to be concerned with such electrical engineering issues of voltagle levels and current flows in the circuit. Recently, circuit families with voltages lower than 5 volts have become widely used in new designs.

4.1 Basic Circuits

We introduce a digital circuit symbol notation for each of the basic circuit elements we wish to use.

The first of these is the or circuit. The logic interpretation of or is the same as its use in ordinary language.

or | 0 | 1
---+---+---
 0 | 0 | 1
---+---+---
 1 | 1 | 1
That is, the conjunction or is 1 when one or the other or both are 1. The circuit symbol for or is:

The second of these is the and circuit. The logic interpretation of and is the same as its use in ordinary language.

and| 0 | 1
---+---+---
 0 | 0 | 0
---+---+---
 1 | 0 | 1
That is, the conjunction and is 1 when and only when both inputs are 1. The circuit symbol for and is:

The third is the not circuit. The logic interpretation of not is the same as its use in ordinary language.

not| 0 | 1
---+---+---
   | 1 | 0
That is, the not of 1 is 0 and not 0 is 1. The circuit symbol for not is:

Two other useful circuit elements are nand (not and) and nor (not or). The function table for nand is:

nand| 0 | 1
----+---+---
  0 | 1 | 1
----+---+---
  1 | 1 | 0
The circuit symbol for nand is :

The function table for the circuit nor is:

nor| 0 | 1
---+---+---
 0 | 1 | 0
---+---+---
 1 | 0 | 0
The circuit symbol for nor is :

4.2 Circuit Models

We wish to build a model for these circuit elements. To do this we need to expand our knowledge of the Scheme notation which we have been using in our laboratory experiments.

4.2.1 OR Model

We first build a model of the or circuit element.
(define bit-or
  (lambda (x y)
    (if (or (= x 1) (= y 1))
      1
      0 )))

4.2.2 Examples:

(bit-or 0 0) ==> 0
(bit-or 0 1) ==> 1
(bit-or 1 0) ==> 1
(bit-or 1 1) ==> 1

4.2.4 AND Model

Next we have the and circuit.
(define bit-and
  (lambda (x y)
    (if (and (= x 1) (= y 1))
      1
      0 )))

4.2.5 Examples:

(bit-and 0 0) ==> 0
(bit-and 0 1) ==> 0
(bit-and 1 0) ==> 0
(bit-and 1 1) ==> 1

4.2.6 NOT Model

Now we model the not circuit.
(define bit-not
  (lambda (x)
    (if (= x 0)
      1
      0)))

4.2.7 Examples:

(bit-not 0) ==> 1
(bit-not 1) ==> 0

4.3 HALF-ADDER Model

We next define a circuit, called a half-adder, using the circuit elements not, and, or. This circuit has two inputs a, b and an output s.

This circuit is modeled as:

(define bit-half-adder
  (lambda (a b)
    (bit-or (bit-and a (bit-not b))
            (bit-and b (bit-not a)))))
The function table for the half-adder circuit may be built from the model output:
(bit-half-adder 0 0) ==> 0
(bit-half-adder 0 1) ==> 1
(bit-half-adder 1 0) ==> 1
(bit-half-adder 1 1) ==> 0

4.3.1 XOR Model

This function is known by another name, exclusive or. Exclusive or is 1 when one or the other but not both arguments are 1. Otherwise the result is 0.

Exclusive or function table:

xor| 0 | 1
---+---+---
 0 | 0 | 1
---+---+---
 1 | 1 | 0
Following is the circuit symbol for exclusive or:

We model the exclusive or circuit with the definition:

(define bit-xor bit-half-adder)

4.4 1 Bit Binary Adder

Next, we use two half-adder circuits plus two and-gates and an or-gate to design a 1 bit binary adder circuit. This circuit has 3 inputs and 2 outputs. The inputs are the two binary digits a, b and a carry input cin. The outputs are the carry output, cout, and the sum, s .

Bit adder

4.4.1 BIT-ADDER Model

We model this with the following function:
(define bit-adder
  (lambda (a b cin)
    (let* ((t (bit-half-adder a b))
           (g (bit-and a b))
           (p (bit-and t cin)))
      (list (bit-or g p)
            (bit-half-adder t cin)))))
The bit-adder has the following characteristics:
(bit-adder 0 0 0) ==> (0 0)
(bit-adder 0 1 0) ==> (0 1)
(bit-adder 1 0 0) ==> (0 1)
(bit-adder 1 1 0) ==> (1 0)
(bit-adder 0 0 1) ==> (0 1)
(bit-adder 0 1 1) ==> (1 0)
(bit-adder 1 0 1) ==> (1 0)
(bit-adder 1 1 1) ==> (1 1)

4.4.2 BIT-ADDER Symbol

We use the following symbol for a bit-adder:

The inputs of this circuits are a b cin and the outputs are cout and s. We number the output lines 0 and 1 respectively.

4.5 2-BIT-ADDER

We next design a circuit which will add two 2 bit numbers. This circuit will accept the digits a1,a0 of the first number and the digits b1,b0 of the second number and produce a 3 bit result of cout,s1,s0.

This circuit will use two bit-adder s. Following is the circuit design.

2-bit-adder

Notice that we are connecting the cout output of the bit-adder on the right to the input of the bit-adder on the left.

4.5.1 Wire Model

Next we show our model for this circuit. But before we do this it is necessary to introduce a model for a wire which is used to connect an output of one circuit to an input of another circuit.
(define wire-output
  (lambda (pin-number outputs)
    (list-ref outputs pin-number)))
The idea here is to produce a mechanism which will allow the selection of one of possibly several outputs from one circuit model as an input to another circuit model. In this case the outputs of a bit-adder must be fed in as inputs to a second bit adder. The above wire-output selects either the first, pin number 0, or the second output, pin number 1.

4.5.2 2-BIT-ADDER Model

Here is the model for the 2-bit-adder
(define 2-bit-adder
  (lambda (a1 a0 b1 b0)
    (let* ((t0 (bit-adder a0 b0 0))
           (t1 (bit-adder a1 b1 (wire-output 0 t0))))
          (list (wire-output 0 t1)
                (wire-output 1 t1)
                (wire-output 1 t0)))))

4.5.3 Examples:

(2-bit-adder 1 0 1 1) ==> (1 0 1)
(2-bit-adder 1 1 1 1) ==> (1 1 0)

4.6 4-BIT-ADDER

Next we design a 4-bit-adder.

Notice, as before, that the carry output of t0 is wired to the carry input of t1, etc. This means that the bit-adder t0 must execute before the bit-adder t1, etc.

We can model this circuit as follows:

4.6.1 4-BIT-ADDER MODEL

(define 4-bit-adder
  (lambda (a3 a2 a1 a0 b3 b2 b1 b0)
    (let* ((t0 (bit-adder a0 b0 0))
           (t1 (bit-adder a1 b1 (wire-output 0 t0)))
           (t2 (bit-adder a2 b2 (wire-output 0 t1)))
           (t3 (bit-adder a3 b3 (wire-output 0 t2))))
          (list (wire-output 0 t3)
                (wire-output 1 t3)
                (wire-output 1 t2)
                (wire-output 1 t1)
                (wire-output 1 t0)))))

4.6.2 Examples:

(4-bit-adder 0 0 1 0  0 0 1 1) ==> (0 0 1 0 1)
(4-bit-adder 1 0 1 0  1 0 1 0) ==> (1 0 1 0 0)
We note that 2 + 3 ==> 5

and 10 + 10 ==> 20 which are the results of the additions in 4.6.2, expressed in decimal notation.

4.7 Complement Arithmetic

Recall that in our discussion of complement arithmetic we said that we would always ignore the carry out of the leftmost digit position when doing complement arithmetic. Actually, most adders compute the high-order carry output and use it to detect certain errors. If our 4-bit adder is used to add two 4-bit unsigned numbers (for example 10 + 10), the existance of the carry indicates that the result is bigger than will fit in 4 bits (range from 0 to 15).

If we use our 4-bit adder to add 4-bit signed numbers (represented as 2's complement numbers), then we must ignore the carry out of the left-most bit. Consider the example of 1 0 1 0 + 1 0 1 0 ==> 1 0 1 0 0. Since

the left-most bit is 1 in the summands we are adding two negative numbers and getting a positive result. Obviously this is some sort of error because two negative values can never sum to a positive value. What is happening? First, note that 1 0 1 0 = -6. To make this obversation either un-two's complement

1 0 1 0 (i.e. subtract 1 and change 1's to 0's and 0's to 1's) or alternately, subtract the next higher power of two (24 = 16) from the unsigned value yielding -6. Since the range of signed 4-bit values runs from -8 to 7, the error in the sum of -6 + -6 is that the sum -12 cannot be represented as a 4 bit signed value!

Our 4-bit-adder design works equally well for both signed (2's complement) summands and unsigned summands.

4.8 Modeling Subtraction

Finally, we wish to extend the design of our 4-bit adder so that it will perform subtractions as well as additions. To do this, we introduce an additonal input, named sub, to the adder (which we now call a 4-bit-alu arithmetic logic unit for reasons which will become evident later). The value of sub will be zero when we want to add and will be 1 when we want to subtract.

Consider the circuit for 4-bit-adder. If we feed sub into the carry input of t0, then when sub is zero the adder will function as before. When sub is one, an extra one will be added. This is just what we want if we could cause each b input to be complemented, i.e., we will subtract by adding the 2's complement.

Consider the following table of values for b and sub

b  sub
0   0 ==> 0
1   0 ==> 1
0   1 ==> 1
1   1 ==> 0
Notice that this set of function results for b and sub is just bit-xor of b and sub. So to summarize, when sub is 0 we add as usual and when b is 1 we add the 2's complement of b which is the same as subtracting b.

4.9 4-BIT-ALU

Here is the circuit for 4-bit-alu

4.9.1 4-BIT-ALU Model

(define 4-bit-alu
  (lambda (a3 a2 a1 a0 b3 b2 b1 b0 sub)
    (let* ((t0 (bit-adder a0 (bit-xor b0 sub) sub))
           (t1 (bit-adder a1 (bit-xor b1 sub)
                             (wire-output 0 t0)))
           (t2 (bit-adder a2 (bit-xor b2 sub)
                             (wire-output 0 t1)))
           (t3 (bit-adder a3 (bit-xor b3 sub)
                             (wire-output 0 t2))))
          (list (wire-output 0 t3)
                (wire-output 1 t3)
                (wire-output 1 t2)
                (wire-output 1 t1)
                (wire-output 1 t0)))))

4.9.2 Examples:

(4-bit-alu 0 1 0 1  0 0 0 1 0) ==> (0 0 1 1 0)
(4-bit-alu 0 1 0 1  0 0 0 1 1) ==> (1 0 1 0 0)

4.10 Processor Model

Next we discuss how our 4-bit-alu might fit into our earlier discussion of the organization of a simple hypothetical computer.

Recall the organization of that processor:

We show a bit more detail inside the processor. Supppose that whenever an operand is fetched from memory, for example in the case of the subtract instruction, that operand is stored in a temporary processor register, known as the b register.

Suppose, further, that the "a" inputs of the 4-bit-alu are wired to the accumulator and the "b" inputs of the 4-bit-alu are wired to the b register and, finally, the sum outputs of the 4-bit-alu are wired to the accumulator.

We have the following more detailed picture of the processor:

A special circuit could be devised to set the sub input to the 4-bit-alu depending on whether the instruction register contained an add instruction or a subtract instruction.