4 Computer Circuits

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 the verb or is the same as its use in ordinary language. For example, consider the compound sentence: The sky is blue or it is raining outside. This sentence is true if one or the other or both of the sentences, The sky is blue., It is raining outside. are true.


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 the verb and is the same as its use in ordinary language. For example, consider the compound sentence: The sky is blue and it is raining outside. This sentence is true when and only when both of the sentences, The sky is blue. , It is raining outside. are true.


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. That is, the sentence It is not raining outside. is false if it is raining outside.


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 J notation which we have been using in our laboratory experiments.

We first make the following verb definitions:


or =. +.
and =. *.
not =. -.

We could use these definitions directly to implement circuit models, however it will be more convenient, later, to have expressed or, and as monads. The or function table may be expressed as:


   0 1 or/ 0 1
0 1
1 1

The or verb is true when one or the other or both inputs are true. This is the same as the usual meaning of or.

The and function table may be expressed as:


   0 1 and/ 0 1
0 0
0 1

The and verb is true when and only when both inputs are true. This is the same as the usuall meaning of and.

Finally, the not vert has the following function table:


   not 0 1
1 0

In the following sections we model these verbs as monads. When you read these models you will notice repeated use of the verbs:


link =: ;
append =: ,

using the formal spelling of these verbs ( ; and ,). You may find it beneficial to reread sections 1.3.9 and 1.3.10 of the Introduction chapter to help you understand the use of these verbs in the following sections.

4.2.1 OR Model

We first build a model of the or circuit element.


bitOr =. monad define
('a' ; 'b') =. y.
a or b
)

4.2.2 Examples:


bitOr 0 0 ==> 0
bitOr 0 1 ==> 1
bitOr 1 0 ==> 1
bitOr 1 1 ==> 1

4.2.4 AND Model

Next we have the and circuit.


bitAnd =. monad define
('a' ; 'b') =. y.
a and b
)

4.2.5 Examples:


bitAnd 0 0 ==> 0
bitAnd 0 1 ==> 0
bitAnd 1 0 ==> 0
bitAnd 1 1 ==> 1

4.2.6 NOT Model

Now we model the not circuit.


bitNot =: not

4.2.7 Examples:


bitNot 0 ==> 1
bitNot 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. We call this circuit a half-adder because it does about half the work (forms the sum, but not the carry) of two 1 bit binary numbers. We can see this from the function table for this circuit.


a   b  |  s
-------|---
0   0  |  0
0   1  |  1
1   0  |  1
1   1  |  0

This circuit is modeled as:


bitHalfAdder =. monad define
('a' ; 'b') =. y.
bitOr (bitAnd a , bitNot b) , bitAnd (bitNot a) , b
)

The function table for the half-adder circuit may be built from the model output:


bitHalfAdder 0 0 ==> 0
bitHalfAdder 0 1 ==> 1
bitHalfAdder 1 0 ==> 1
bitHalfAdder 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:


bitXor =: bitHalfAdder

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:


bitAdder =. monad define
('a' ; 'b' ; 'cin') =. y.
t =. bitHalfAdder a , b
g =. bitAnd a , b
p =. bitAnd t , cin
(bitOr g , p) , bitHalfAdder t , cin
)

The bit-adder has the following characteristics:


bitAdder 0 0 0 ==> 0 0
bitAdder 0 1 0 ==> 0 1
bitAdder 1 0 0 ==> 0 1
bitAdder 1 1 0 ==> 1 0
bitAdder 0 0 1 ==> 0 1
bitAdder 0 1 1 ==> 1 0
bitAdder 1 0 1 ==> 1 0
bitAdder 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.


wireOutput =. monad define
('pin' ; 'outputs') =. y.
pin from outputs
)

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


twoBitAdder =. monad define
('a1' ; 'a0' ; 'b1' ; 'b0') =. y.
t0 =. bitAdder a0 , b0 , 0
t1 =. bitAdder a1 , b1 , wireOutput 0 ; t0
(wireOutput 0 1 ; t1) , wireOutput 1 ; t0
)

4.5.3 Examples:


twoBitAdder 1 0 1 1 ==> 1 0 1
twoBitAdder 1 1 1 1 ==> 1 1 0

4.5.4 Exercise

We could have designed our 2-bit-adder so that it had a carry input, cin, inaddition to the inputs a1, a0, b1 and b0. This design approach would require using 0 for cin when adding two 2-bit numbers, however, it would allow the design of a 4-bit-adder by using two 2-bit-adders. Modify the twoBitAdder model given in 4.5.2 so that it has a carry input.

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


fourBitAdder =: monad define
('a3' ; 'a2' ; 'a1' ; 'a0' ; 'b3' ; 'b2' ; 'b1' ; 'b0') =. y.
t0 =. bitAdder a0 , b0 , 0
t1 =. bitAdder a1 , b1 , wireOutput 0 ; t0
t2 =. bitAdder a2 , b2 , wireOutput 0 ; t1
t3 =. bitAdder a3 , b3 , wireOutput 0 ; t2
(wireOutput 0 1 ; t3) , (wireOutput 1 ; t2) , (wireOutput 1 ; t1) , wireOutput 1 ; t0
)

4.6.2 Examples:


fourBitAdder 0 0 1 0  0 0 1 1 ==> 0 0 1 0 1
fourBitAdder 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.6.3 Exercise

Build a model for a 4-bit-adder which uses two 2-bit-adders which are described in Exercise 4.5.4 .

4.6.4 Exercise

Modify the fourBitAdder given in Section 4.6.1 so that it has a carry input, cin. This version of fourBinAdder could be used in pairs to build an 8-bit-adder.

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 (2⁴ = 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


fourBitAlu =: monad define
('a3' ; 'a2' ; 'a1' ; 'a0' ; 'b3' ; 'b2' ; 'b1' ; 'b0' ; 'sub') =. y.
t0 =. bitAdder a0 , (bitXor b0 , sub) , sub
t1 =. bitAdder a1 , (bitXor b1 , sub) , wireOutput 0 ; t0
t2 =. bitAdder a2 , (bitXor b2 , sub) , wireOutput 0 ; t1
t3 =. bitAdder a3 , (bitXor b3 , sub) , wireOutput 0 ; t2
(wireOutput 0 1 ; t3) , (wireOutput 1 ; t2) , (wireOutput 1 ; t1) , wireOutput 1 ; t0
)

4.9.2 Examples:


fourBitAlu 0 1 0 1  0 0 0 1 0 ==> 0 0 1 1 0
fourBitAlu 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.