# Digital Circuits

This chapter is an introduction to the implementation of logic operations in electronic circuits

Gates are the basic building blocks that are mapped to the standard logic functions

• Gates are arrangements of switching circuits. Since data can be represented in binary as electrical voltages (0v = 0 and 5v = 1), simple on/off switches that represent data input control the flow of electricity through the circuit producing an output.
• Each gate has one or more inputs, either from an external source or from the output of another gate
• Each gate produces one output. This output can be used to control a device or is used as input to other gates.
• Wired together and interconnected to form circuits that represent functions found in a CPU. Often the input and outputs correspond to a logic variable.

## Simple Logic Gates

### AND as an example gate

Inputs are usually on the left and the output on right of the gate. The output always has one of the binary values or is in transition to the other value based on the inputs.

Note that writing the AND logic function as an algebraic equation, AND is boolean multiplication so that ab denotes a AND b.

### Timing Diagram of the AND gate

A timing diagram represents the inputs and outputs over time and tries to show all possible combinations of inputs. The diagram on the left is drawn with the assumption that transitions to opposite logic values are instantaneous, but there is, in reality, a "rise" time and a "fall" time in which the righthand side diagram represents.

For the AND Gate

### OR gate and its timing diagram

Writing the OR logic function as an algebraic equation, OR is boolean addition so that a + b denotes a OR b.

### NOT Gate

The not gate is often called an "Inverter". It has one input and one output. The little circle attached to any gate indicates that the output is logically negated or inverted. A not gate is then drawn as in the first drawing. It is simply an "amplification" then inverted. The simple triangle symbol is amplification or strengthening.

Sometimes in a real circuit a signal is used as input to several gates. The output of one gate cannot "drive" more than a few inputs to other gates and may need amplification. That limit of uses of the output is called "fan-out". There is a corresponding concept of "fan-in".

What is the timing diagram?

### NAND Gate

A NAND gate is drawn as in the first drawing. Since NANDs are easier to implement than AND, an AND is then created typically by the connection of a NAND and Inverter as in the second drawing.

What is the timing diagram?

### 3 Input AND

Often there is a need for higher input AND, OR, NAND, NOR gates. Below is a three input AND gate composed of two. Three and four input NANDs are easy to construct. A three input AND symbol is also shown.

What is the timing diagram?

### XOR Gate

The "exclusive or" can be thought of as having an output of one when the inputs are opposite. This equation represents this concept:
a XOR b = (a AND ~b) OR (~a AND b)

The "exclusive or" can be thought of as" OR but not both". This equation represents this concept:
a XOR b = (a OR b) and (a NAND b)
the leftmost diagram is this implementation of XOR

This equation is a derived from an application of the logic algebra theorem "DeMorgan's Law" in which
a and b = ~a NOR ~b
a XOR b = (a NOR b) NOR (a AND b)
the rightmost diagram is this implementation of XOR

This latter equation requires only 4 basic gates (2 NORs, NAND and NOT). While the first one requires 6 and the second requires 5. How many NORs, NANDs and NOTs?

What should be the timing diagram of an XOR?

## Building Other Circuits

• Adders and other ALU circuits
• Registers - these are storage devices and require a special arrangement of the circuit
• Busses and the connections of registers and other circuits to them

### The Bus

A bus is an exception to the normal circuit construction. Normally you do NOT want two or more outputs of a gate to be wired together. This is called a "wired or". The electrical properties then have to be carefully considered. For instance what happens when you have explicit logic 0 ( 0v connected to the ground), connected to an explicit logic 1 (5v switched to the power source)? See your nearest electrical engineer or take your own electronics or EE courses. But for the case of a bus, we'll do it anyway, recognizing that more is involved in the actual implementation.

### Register Connection to a bus

You can use AND gates to control flow: recall that x and 0 = 0 (or no output) and x and 1 = x (or pass the output)

You need one AND gate per bit in a register.

A common control line connects to all these controlling ANDs of a register output.

Bus states (tristate)

• high (logic 1)
• low (logic 0)
• float (disconnected)

Consider a bus, a 4-bit register and its gating mechanism using an AND with a control line, such that when the control line is high then the output is its register contents, otherwise output zeroes.

### Combinational Circuits

Any number of inputs

Each output can be represented by a pure logic function/equation

Examples

• Seven segment display
• Decoders: take a value represented by n lines (eg. Bits in the IR) and activate an output line from 2n lines (make it 1) and other lines low.
• Encoders: does the opposite of a decoder. Take the number of line of 2n lines that is 1 (all others are 0) and set the output n lines to represent the number of that line that is high.
• Simple control circuits

# Memory and Sequential Circuits

A sequential circuit takes an output line and reuses it as an input (feedback) line. There are usually other input lines as in the combinational circuit.

The output is no longer representing a simple logic function. Instead the output is based on the previous output value and the current input.

The output results in a sequence of values over time, even if there are no changes in the input. Also a sequential circuit output will not change on some input changes.

The result is memory

The feedback line(s) in the circuit constitute the memory.

### Example Sequential Circuit

Consider the following sequential circuit. The logic table is written to include the external input a and the feedback line x and the new output value x' (which is then fed back into the circuit)

 `A` `X` `X'` `0` `0` `1` `0` `1` `1` `1` `0` `1` `1` `1` `0`

What's the timing diagram? What might you use this circuit for?

## Flip-flop

A flip-flop is the basic active, logic gate memory device for retaining one bit of data.

A simple flip-flop can be built with two cross-coupled NANDs or NORs.

Using NORs you can construct the "S-R Flip-flop" (SR = Set-Reset)

Truth Table of the SR flip-flop

 `S` `R` `Q` `~Q` `0` `0` `Q` `~Q` `0` `1` `0` `1` `1` `0` `1` `0` `1` `1` `0` `0`

if both S and R switch from 1 to 0 simultaneously...?

### Clocked S-R Flip-Flop

When clock line (Cl) is low, the flip-flop holds the previous SR value and S and R can change randomly without affecting the flip-flop. The clock is really a control line to signal the flip-flop when to accept a new value. It may be connected in some way to the system clock, but not necessarily. It's a term used for the special input line that performs this function.

When clock line is high, the flip-flop assumes a new value based on S and R. S and R should hold steady long enough with the high clock signal for the flip-flop to stabilize.

### D Flip-Flop

The "Data flip-flop" assures that no oscillation will occur by forcing R and S to be the complement of the other.

Other flip-flops are the J-K and the master-slave J-K flip-flop which are flip-flops that assure no illegal values can enter the feedback circuit and permit useful operations on all combinations of inputs.

### Register Construction

Each bit requires a flip-flop (D in this example). This is a 3 bit example.

### The Bus

The bus consists of

• Data lines: carry the data bits among the registers and other circuits in the CPU
• Control lines with a variety of functions: the clock for synchronization, a line to specify that the register is to read, a line to specify that the register is to write its value, and to select the register (address the register)

Select-in line to the register

AND Register select as decoded from above
AND Clock for synchronization

Select-out from the register

• Write operation from CPU
AND Register select as decoded from above
AND Clock

ANDing may be combined with the data bits

# ALU Construction

Executing the AND operation on registers X and Y.

 `x` `y` `Carry` `Sum` `0` `0` `0` `0` `0` `1` `0` `1` `1` `0` `0` `1` `1` `1` `1` `0`

• Carry = x AND y
• Sum = x XOR y

Must add in the carry bit of previous sum

 `x` `y` `cI` `Carry` `Sum` `0` `0` `0` `0` `0` `0` `0` `1` `0` `1` `0` `1` `0` `0` `1` `0` `1` `1` `1` `0` `1` `0` `0` `0` `1` `1` `0` `1` `1` `0` `1` `1` `0` `1` `0` `1` `1` `1` `1` `1`
• Carry = yci+ xy + xci
• Sum = ~x~yci + ~xy~ci + x~y~ci + xyci

What simple modification of the above would allow for an ADD with Carry (ADWC) instruction?

## Subtraction

We want to compute X-Y

1. X-Y = X + (-Y) , that is , convert subtraction to an addition problem by adding the negative of Y
2. X-Y = X + (~Y)+1 , but the negative is a 2's complement value which is found by taking the 1's complement of Y and adding one
3. The +1 can be accomplished by using an initial carry in on the least significant bit that normally is zero.
4. One's complement is the logical negation .Flipflops that are used to build registers conveniently have the complement (~Q) value of each bit!

Following is the modification to an adder circuit to implement subtraction. Shown is the circuit on the outputs of only one of the bits on the Y register. The line from the right is the control line from the control unit of the CPU to the ALU that the add operation is either an add or subtract. The 2-AND-OR-NOT gate combination is a classic circuit to select one of two inputs as the output.

## Multiplication

Multiplication circuits are typically built of adders, shifters. Also need control circuits

There are many techniques to perform multiplication

• variations on shift and add

Some simple analyses on multiplication

• costliest operation in the final analysis is the add operation
• shifting of bits and testing of bits are relatively quick compared to add
• try to minimize invoking the add operation. Subtraction costs the same as addition.

Example

```  25 (MULTIPLICAND or "Q")
x 13 (MULTIPLIER or "M")
= 25 + 25 + 25 + ... + 25 (13 times)
= 325 (PRODUCT or "P")```

Analysis

• number of iterations (and additions)= M, i.e., performance depends on size of M
• So for efficiency, noting multiplication is commutative, then if Q<M then swap Q and M before invoking the additions
• But, the multiplier must be positive; if not then negate Q and M and the above test really must be |Q|<|M|

Check out the subroutine MULT1 which performs repeat addition multiplication.

Example

```  25
x 13
75 = 25+25+25
25   = 250 (25 shifted one digit place)
325```

Analysis and observations

• number of iterations (and maximum number of additions) = sum of digits of M
• it is not worth checking for minimum sum of digits
• be sure the multiplier is positive; multiplicand can be left as negative if you are certain the sign is extended.
• We can add the summands as we go.
• As we perform multiplication by hand, we "shift" the multiplicand to the left to create our diagonal array of summands. If we add on the fly we can shift the partial product (partial sum) to the right.
```  25
x 13
+75
7:5  shift partial product to right
+25
32:5```

In a binary number system context

```   11001
x 1101
101000101```

```   11001
x 1101
>>11001    shift P
11001
>> 11001   shift P
1111101
>>1111101  shift
101000101```

Check out the subroutine MULT2 which performs shift and add multiplication.

### C. Booth's Multiplication Algorithm

Want to treat positive and negative multipliers uniformly, i.e., no sign analysis

Want to performs fewer additions (and subtractions) than in add/shift algorithm if possible

Idea:

• A binary number is normally viewed as a sum of powers of 2
• 28 = 16+8+4 = 24+23+22 = 000111002
• Decode the multiplier into a series of alternating subtractions and additions of powers of two ("signed digit" number system)
• Use the decoding to calculate the product by a series of additions and subtractions

### Signed digit system

Example

28 = 32-8+4 = 25- 23+22 = 0 0 1 0 -1 1 0 0

Also 28 = 32-4 = 25 -22= 0 0 1 0 0 -1 0 0

Signed number systems are redundant.

Negative numbers

• -28 = -32+8-4 = -25+23-22= 0 0 -1 0 1 -1 0 0
• -28 = -32+4 = -25+22= 0 0 -1 0 0 1 0 0

negate the one's in the positive representation

### Translating 2's complement to sign system

Scan right to left analyzing each pair of bits

```00 -> 0
01 -> 1
10 -> -1
11 -> 0```

Example

28 = 00011100.0 = 0 0 1 0 0 -1 0 0

-28 = 11100100.0 = 0 0 -1 0 1 -1 0 0

### C. Booth's Algorithm

Scan M right to left and analyze bit pairs instead of the single bit:

• if 01 then add Q to P
• if 10 then subtract Q from P
• else (if 00 or 11) do nothing;
• in all cases shift the result (or Q)

Check out the subroutine MULT3 which performs Booth's algorithm.

### D. Booth's Modified Algorithm

Take into account that immediately adjacent addition and subtraction pair can be replaced by one operation

Example

• 23-22= 22
• 2n-2n-1= 2n-1
• -2n+2n-1= -2n-1

Now look at triples of bits instead of pairs (two pairs transform to one triple). Accounting for the shift that occurs, in the original algorithm:

```00 -> Shift
10 -> Sub then Shift
11 -> Shift```

Replace with

```000 -> Shift, Shift
100 -> Shift, Sub, Shift
101 ->
110 ->
111 ->```

Check out the subroutine MULT4 which performs Booth's modified algorithm.

### Division

Division is repeat subtraction. Unfortunately, since division is not commutative there are few algorithms to efficiently perform subtraction.

Decimal example

```   021 R1
13)274
26
14
13
1```

Binary example

```     000010101 R1
1101)100010010
1101
10000
1101
1110
1101
1```

### Restoring Technique

Shift next digit from dividend for subtraction

Subtract divisor from dividend'

If difference > 0 then set quotient bit

else clear quotient bit and add divisor back (restore) into dividend'

Repeat until all digits are shifted

### Notes on implementation

Division is the inverse of multiplication.

Begin with double word dividend and a single word divisor.

Result in single word quotient and single word remainder. Note that overflow is possible.

As dividend shrinks (shifted) the quotient grows so that the dividend and quotient can share the register pair.

Examples

• 20/3 = 6 R2 or in binary: 10100/11 = 0110 R 0010
```    R0     R1
0 0 0 1|0 1 0 0 initial
0 0 1 0|1 0 0:  shift (1)
0 0 1 0|1 0 0:0 sub/restore (1)
0 1 0 1|0 0:0   shift(2)
0 0 1 0|0 0:0 1 sub/set (2)
0 1 0 0|0:0 1   shift(3)
0 0 0 1|0:0 1 1 sub/set (3)
0 0 1 0:0 1 1   shift(4)
0 0 1 0:0 1 1 0 sub/restore (4)
remainder:quotient```

Check out the subroutine RESDIV which performs restoring division.

### Non-restoring division

Improvement: really don't need to restore quotient; instead, keep shifting and add rather than subtract.

Only when sub/add operation results in a positive dividend do we set quotient bit and switch back to subtract.

Sequence of operations in original algorithm in the loop after subtraction:

• IF dividend (A) is positive THEN shift and subtract divisor (M) = (2A-M)
• IF dividend (A) is negative THEN restore (A+M) then shift and subtract = 2(A+M)-M
• But 2(A+M)-M = 2A+M

Working through the example

• 10100/11 = 0110 R 0010
```    R0      R1
0 0 0 1|0 1 0 0 initial
0 0 1 0|1 0 0:  shift (1)
1 1 1 1|1 0 0:0 sub/clear (1)
1 1 1 1|0 0:0   shift(2)
0 0 1 0|0 0:0 1 add/set (2)
0 1 0 0|0:0 1   shift(3)
0 0 0 1|0:0 1 1 sub/set (3)
0 0 1 0:0 1 1   shift(4)
1 1 1 1:0 1 1 0 sub/clear (4)
0 0 1 0:0 1 1 0 restore negative remainder
remainder:quotient```

Check out the subroutine NONDIV which performs nonrestoring division.