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

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.

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 | 1That is, the conjunction

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 | 1That is, the conjunction

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

not| 0 | 1 ---+---+--- | 1 | 0That is, the

Two other useful circuit elements are ** nand** (not and) and

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

The function table for the circuit ** nor** is:

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

(define bit-or (lambda (x y) (if (or (= x 1) (= y 1)) 1 0 )))

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

(define bit-and (lambda (x y) (if (and (= x 1) (= y 1)) 1 0 )))

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

(define bit-not (lambda (x) (if (= x 0) 1 0)))

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

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

Exclusive or function table:

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

We model the exclusive or circuit with the definition:

(define bit-xor bit-half-adder)

Bit adder

(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)

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.

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.

(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.

(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)))))

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

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:

(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-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.

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 (2^{4} = 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.

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 ==> 0Notice 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.

(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-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)

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.