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
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.
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
Writing the OR logic function as an algebraic equation, OR is boolean addition so that a + b denotes a OR b.
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?
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?
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?
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?
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.
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.
Any number of inputs
Each output can be represented by a pure logic function/equation
Examples
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.
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?
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...?
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.
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.
Each bit requires a flip-flop (D in this example). This is a 3 bit example.
The bus consists of
Select-in line to the register
Select-out from the register
ANDing may be combined with the data bits
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 |
Half Adder
Must add in the carry bit of previous sum
x |
y |
c_{I} |
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 |
8 bit addition using full adders
What simple modification of the above would allow for an ADD with Carry (ADWC) instruction?
We want to compute X-Y
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 circuits are typically built of adders, shifters. Also need control circuits
There are many techniques to perform multiplication
Some simple analyses on multiplication
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.
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.
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:
Example
28 = 32-8+4 = 2^{5}- 2^{3}+2^{2} = 0 0 1 0 -1 1 0 0
Also 28 = 32-4 = 2^{5} -2^{2}= 0 0 1 0 0 -1 0 0
Signed number systems are redundant.
Negative numbers
negate the one's in the positive representation
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
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.
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 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
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
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.
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.