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


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

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)

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

generic combinational ciruit


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)

simple sequential 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)

set-reset flip-flop

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

Select-in line to the register

Select-out from the register

ANDing may be combined with the data bits



ALU Construction

Executing the AND operation on registers X and Y.

Addition in Logic Gates

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

Half Adder

Full Adder

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

Ripple Carry Adder

8 bit addition using full adders

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

Some simple analyses on multiplication

A. Repeat Addition

Example

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

Analysis

Check out the subroutine MULT1 which performs repeat addition multiplication.

B. Shift and Add

Example

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

Analysis and observations

  25
x 13
 +75
   7:5  shift partial product to right
 +25
  32:5

 

In a binary number system context

   11001
  x 1101 
   11001 add
  00000 shift Q, no add
 11001 shift Q, add
11001 shift Q, add
101000101

 

   11001
  x 1101 
  +11001     add
  >>11001    shift P
  +00000     no add
    11001
  >> 11001   shift P
  +11001     add
   1111101
  >>1111101  shift
  +11001    add
  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:

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

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

Modification of shift and add

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

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

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
01 -> Add then Shift
10 -> Sub then Shift
11 -> Shift

Replace with

000 -> Shift, Shift
001 -> Add, Shift, Shift
010 -> Add, Shift, Shift
011 -> Shift, Add, 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

    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:

Working through the example

    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.