Digital Logic Design - Revision
Digital Logic Design - Revision
Digital Logic Design - Revision
(å )+ ( å )
i j
(Number)r =
Ai r Aj r
i=0 j=-m
Chapter 1 1
Number Systems – Examples
Chapter 1 2
Special Powers of 2
Chapter 1 3
ARITHMETIC OPERATIONS - Binary
Arithmetic
Chapter 1 4
Single Bit Binary Addition with Carry
Carry in (Z) of 1: Z 1 1 1 1
X 0 0 1 1
+Y +0 +1 +0 +1
CS 01 10 10 11
Chapter 1 5
Multiple Bit Binary Addition
Chapter 1 6
Single Bit Binary Subtraction with Borrow
Given two binary digits (X,Y), a borrow in (Z) we
get the following difference (S) and borrow (B):
Borrow in (Z) of 0: Z
0 0
0
0
X 0 0 1 1
-Y -0 -1 -0 -1
BS 00 11 01 00
Borrow in (Z) of 1:
Z 1 1 1 1
X 0 0 1 1
-Y -0 -1 -0 -1
BS 11 10 00 11
Chapter 1 7
Multiple Bit Binary Subtraction
Chapter 1 8
Binary Multiplication
0 1 11 2,048
1 2 12 4,096
2 4 13 8,192
3 8 14 16,384
4 16 15 32,768
5 32 16 65,536
6 64 17 131,072
7 128 18 262,144
8 256 19 524,288
9 512 20 1,048,576
10 1024 21 2,097,152
Chapter 1 10
Converting Binary to Decimal
Chapter 1 11
Converting Decimal to Binary
Method 1
• Subtract the largest power of 2 (see slide 14) that gives
a positive remainder and record the power.
• Repeat, subtracting from the prior remainder and
recording the power, until the remainder is zero.
• Place 1’s in the positions in the binary result
corresponding to the powers recorded; in all other
positions place 0’s.
Example: Convert 62510 to N2
Chapter 1 12
Commonly Occurring Bases
Binary 2 0,1
Octal 8 0,1,2,3,4,5,6,7
Decimal 10 0,1,2,3,4,5,6,7,8,9
Hexadecimal 16 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
Chapter 1 13
Numbers in Different Bases
00 00000 00 00
01 00001 01 01
02 00010 02 02
03 00011 03 03
04 00100 04 04
05 00101 05 05
06 00110 06 06
07 00111 07 07
08 01000 10 08
09 01001 11 09
10 01010 12 0A
11 0101 1 13 0B
12 01100 14 0C
13 01101 15 0D
14 01110 16 0E
15 01111 17 0F
16 10000 20 10
Chapter 1 14
Conversion Between Bases
Method 2
To convert from one base to another:
1) Convert the Integer Part
Chapter 1 15
Conversion Details
Chapter 1 16
Example: Convert 46.687510 To Base 2
Convert 46 to Base 2
Chapter 1 19
Why Do Repeated Division and
Multiplication Work?
Divide the integer portion of the power series
on slide 11 by radix r. The remainder of this
division is A0, represented by the term A0/r.
Discard the remainder and repeat, obtaining
remainders A1, …
Multiply the fractional portion of the power
series on slide 11 by radix r. The integer part of
the product is A-1.
Discard the integer part and repeat, obtaining
integer parts A-2, …
This demonstrates the algorithm for any radix
r >1.
Chapter 1 20
Octal (Hexadecimal) to Binary and
Back
Octal (Hexadecimal) to Binary:
• Restate the octal (hexadecimal) as three
(four) binary digits starting at the radix
point and going both ways.
Binary to Octal (Hexadecimal):
• Group the binary digits into three (four) bit
groups starting at the radix point and going
both ways, padding with zeros as needed in
the fractional part.
• Convert each group of three bits to an octal
(hexadecimal) digit.
Chapter 1 21
Octal to Hexadecimal via Binary
Chapter 1 23
Binary Numbers and Binary Coding
Flexibility of representation
• Within constraints below, can assign any binary
combination (called a code word) to any data as long
as data is uniquely encoded.
Information Types
• Numeric
Must represent range of data needed
Very desirable to represent data such that simple,
straightforward computation for common arithmetic
operations permitted
Tight relation to binary numbers
• Non-numeric
Greater flexibility since arithmetic operations not applied.
Not tied to binary numbers
Chapter 1 24
Non-numeric Binary Codes
Blue 101
Code 100 is Indigo 110
Chapter 1 25
Number of Bits Required
Chapter 1 28
Binary Coded Decimal (BCD)
Chapter 1 29
Excess 3 Code and 8, 4, –2, –1 Code
Chapter 1 31
BCD Arithmetic
Given a BCD code, we use binary arithmetic to add the digits:
8 1000 Eight
+5 +0101 Plus 5
13 1101 is 13 (> 9)
Note that the result is MORE THAN 9, so must be
+5 +0101 Plus 5
13 1101 is 13 (> 9)
+0110 so add 6
Chapter 1 32
BCD Addition Example
Chapter 1 33
ALPHANUMERIC CODES - ASCII Character
Codes
American Standard Code for Information
Interchange (Refer to Table 1 -4 in the text)
This code is a popular code used to represent
information sent as character-based data. It uses
7-bits to represent:
• 94 Graphic printing characters.
• 34 Non-printing characters
Some non-printing characters are used for text
format (e.g. BS = Backspace, CR = carriage
return)
Other non-printing characters are used for record
marking and flow control (e.g. STX and ETX start
and end text areas).
Chapter 1 34
ASCII Properties
Chapter 1 35
PARITY BIT Error-Detection Codes
Chapter 1 36
4-Bit Parity Code Example
000 - 000
-
001 - 001
-
010 - 010
-
011 - 011
-
100 - 100
-
101 - 101
-
110 - 110
-
111 - 111
The codeword "1111" has even parity
- and the
codeword "1110" has odd parity. Both can be
used to represent 3-bit data.
Chapter 1 37
GRAY CODE – Decimal
0 0000 0000
1 0001 0100
2 0010 0101
3 0011 0111
4 0100 0110
5 0101 0010
6 0110 0011
7 0111 0001
8 1000 1001
9 1001 1000
Chapter 1 38
Logic and Computer Design Fundamentals
Chapter 1 40
Binary Logic and Gates
Chapter 1 41
Binary Variables
Recall that the two binary values have
different names:
• True/False
• On/Off
• Yes/No
• 1/0
We use 1 and 0 to denote the two values.
Variable identifier examples:
• A, B, y, z, or X for now
1
• RESET, START_IT, or ADD1 later
Chapter 1 42
Logical Operations
Chapter 1 43
Notation Examples
Examples:
• Y = A ×B
is read “Y is equal to A AND B.”
• z = x + y
is read “z is equal to x OR y.”
• X = A
is read “X is equal to NOT A.”
Note: The statement:
1 + 1 = 2 (read “one plus one equals two”)
Chapter 1 44
Operator Definitions
Operations are defined on the values "0" and "1" for each
operator:
AND OR NOT
0·0=0 0+0=0 0 = 1
0·1=0 0+1=1 1 = 0
1·0=0 1+0=1
1·1=1 1+1=1
Chapter 1 45
Truth Tables
0 1 0
0 1 1 1 0
1 0 0
1 0 1
1 1 1
1 1 1
Chapter 1 46
Logic Gate Symbols and Behavior
Y 0 1 0 1
(AND) X ·Y 0 0 0 1
(OR) X1 Y 0 1 1 1
(NOT) X 1 1 0 0
(b) Timing diagram
Chapter 1 47
Logic Diagrams and Expressions
000 0 F = X + Y Z
001 1
011 0 X
100 1
Y F
101 1
110 1 Z
111 1
Chapter 1 48
Boolean Algebra
An algebraic structure defined on a set of at least two elements, B, together with three binary operators (denoted
.
1. X +0 = X 2. X 1 = X
.
3. X + 1 = 1 4. X 0 = 0
.
5. X+X = X 6. X X = X
.
7. X+X = 1 8. X X = 0
9. X=X
Chapter 1 49
Some Properties of Identities & the Algebra
The identities above are organized into pairs. These pairs have names as follows:
The dual of an algebraic expression is obtained by interchanging + and · and interchanging 0’s
and 1’s.
The identities appear in dual pairs. When there is only one identity on a line the identity is self-
Chapter 1 50
Some Properties of Identities & the Algebra (Continued)
Chapter 1 51
Some Properties of Identities & the Algebra
(Continued)
Chapter 1 52
Boolean Operator Precedence
expression is:
1. Parentheses
2. NOT
3. AND
4. OR
Consequence: Parentheses appear
around OR expressions
Example: F = A(B + C)(C + D)
Chapter 1 53
Example 1: Boolean Algebraic Proof
Chapter 1 54
Example 2: Boolean Algebraic Proofs
AB + AC + BC = AB + AC (Consensus Theorem)
Proof Steps Justification (identity or theorem)
AB + AC + BC
= AB + AC + 1 · BC ?
= AB +AC + (A + A) · BC ?
=
Chapter 1 55
Example 3: Boolean Algebraic Proofs
(X + Y)Z + X Y = Y ( X +Z )
Proof Steps Justification (identity or theorem)
( X + Y ) Z + X Y
=
Chapter 1 56
Useful Theorems
x× y + x × y = y (x + y )(x + y ) = y M inimizatio n
x xy x x x y x Absorption
x + x × y = x + y x× (x + y ) = x× y Simplifica tion
x× y + x × z + y× z = x× y + x × z Consensus
(x + y )×(x + z )× (y + z ) = (x + y )×(x + z)
x + y = x ×y x ×y = x + y DeMorgan' s Laws
Chapter 1 57
Proof of Simplification
x ×y + x ×y = y (x + y )(x + y ) = y
Chapter 1 58
Proof of DeMorgan’s Laws
x+ y = x ×y x ×y = x + y
Chapter 1 59
Boolean Function Evaluation
F1 = xy z
x y z F1 F2 F3 F4
F2 = x + yz 0 0 0 0 0
F3 = x y z + x y z + x y 0 0 1 0 1
F4 = x y + x z 0 1 0 0 0
0 1 1 0 0
1 0 0 0 1
1 0 1 0 1
1 1 0 1 1
1 1 1 0 1
Chapter 1 60
Expression Simplification
Chapter 1 63
Canonical Forms
Chapter 1 64
Minterms
Chapter 1 66
Maxterms and Minterms
Chapter 1 67
Standard Order
Minterms and maxterms are designated with a subscript
The subscript is a number, corresponding to a binary
pattern
The bits in the pattern represent the complemented or
normal state of each variable listed in a standard order.
All variables will be present in a minterm or maxterm and
will be listed in the same order (usually alphabetically)
Example: For variables a, b, c:
• Maxterms: (a + b + c), (a + b + c)
• Terms: (b + a + c), a c b, and (c + b + a) are NOT in
standard order.
• Minterms: a b c, a b c, a b c
• Terms: (a + c), b c, and (a + b) do not contain all
variables
Chapter 1 68
Purpose of the Index
Chapter 1 69
Index Example in Three Variables
• Minterm 6 ?
• Maxterm 6 ?
Chapter 1 70
Index Examples – Four Variables
Chapter 1 71
Minterm and Maxterm Relationship
Chapter 1 72
Function Tables for Both
Minterms of Maxterms of
2 variables 2 variables
xy m 0 m 1 m 2 m 3 xy M 0 M 1 M 2 M 3
00 1 0 0 0 00 0 1 1 1
01 0 1 0 0 01 1 0 1 1
10 0 0 1 0 10 1 1 0 1
11 0 0 0 1 11 1 1 1 0
Chapter 1 73
Observations
Example: Find F1 = m1 + m4 + m7
F1 = x y z + x y z + x y z
xyz index m1 + m4 + m7 = F1
000 0 0 + 0 + 0 =0
001 1 1 + 0 + 0 =1
010 2 0 + 0 + 0 =0
011 3 0 + 0 + 0 =0
100 4 0 + 1 + 0 =1
101 5 0 + 0 + 0 =0
110 6 0 + 0 + 0 =0
111 7 0 + 0 + 1 =1
Chapter 1 75
Minterm Function Example
Chapter 1 76
Maxterm Function Example
·( x + y + z )·( x + y + z)
xyz i M0 M2 M3 M5 M6 = F1
000 0 0 1 1 1 1 =0
001 1 1 1 1 1 1 =1
010 2 1 0 1 1 1 =0
011 3 1 1 0 1 1 =0
100 4 1 1 1 1 1 =1
101 5 1 1 1 0 1 =0
110 6 1 1 1 1 0 =0
111 7 1 1 1 1 1 =1
Chapter 1 77
Maxterm Function Example
F( A, B, C, D) = M 3
× M 8
× M 11
× M 14
F(A, B,C,D) =
Chapter 1 78
Canonical Sum of Minterms
Chapter 1 79
Another SOM Example
Example: F = A + B C
There are three variables, A, B, and C which we
take to be the standard order.
Expanding the terms with missing variables:
Chapter 1 80
Shorthand SOM Form
Chapter 1 81
Canonical Product of Maxterms
Any Boolean Function can be expressed as a Product of
Maxterms (POM).
• For the function table, the maxterms used are the terms
corresponding to the 0's.
• For an expression, expand all terms first to explicitly list all
maxterms. Do this by first applying the second distributive
law , “ORing” terms missing variable v with a term equal to
v× v
and then applying the distributive law again.
Example: Convert to product of maxterms:
f ( x, y, z) = x + x y
Apply the distributive law:
x + x y = (x + x )(x + y ) = 1 × (x + y ) = x + y
Add missing variable z:
x + y + z × z = ( x + y + z ) (x + y + z )
Express as POM: f = M2 · M3
Chapter 1 82
Another POM Example
Chapter 1 83
Function Complements
F(x, y, z) = S m
( 0, 2,4,6 )
F(x, y, z) = P M
( 1, 3, 5 , 7 )
Chapter 1 84
Conversion Between Forms
Then use the other form with the same indices – this
Chapter 1 86
Standard Sum-of-Products (SOP)
Chapter 1 90
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals
as the course textbook.
These materials or adaptations thereof are not to be
sold or otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 91
Logic and Computer Design Fundamentals
Chapter 1 93
Circuit Optimization
Example 1: GN = G + 2 = 9
F=A+ B C + B C
L= 5
G=L+2= 7
B
C
A F
literal OR input.
G (gate input count) adds the remaining OR gate inputs
Chapter 1 97
Cost Criteria (continued)
Example 2: A
F=AB C + A B C B
C
L = 6 G = 8 GN = 11 F
F = (A + C)( B + C)( A + B)
L = 6 G = 9 GN = 12
Same function and same
A
literal cost
B
But first circuit has better C
gate input count and better F
gate input count with NOTs
Select it!
Chapter 1 98
Boolean Function Optimization
Chapter 1 100
Some Uses of K-Maps
Chapter 1 102
K-Map and Truth Tables
Input Function
01 b x=1 c d
10 c
11 d
Chapter 1 103
K-Map Function Representation
x=0 0 0
x=1 1 1
Chapter 1 104
K-Map Function Representation
x=0 0 1
x=1 1 1
G (x, y ) = (x y + x y )+ (xy + x y )= x + y
Duplicate x y
Chapter 1 105
Three Variable Maps
A three-variable K-map:
yz=00 yz=01 yz=11 yz=10
x=0 m0 m1 m3 m2
x=1 m4 m5 m7 m6
x=0 x y z x y z x y z x y z
x=1 x y z x y z x y z x y z
Note that if the binary value for an index differs in one
bit position, the minterms are adjacent on the K-Map
Chapter 1 106
Alternative Map Labeling
0 1 3 2 0 1 3 2
x 0
4 5 7 6
x x
1 4 5 7 6
z z z
z
Chapter 1 107
Example Functions
Chapter 1 109
Example: Combining Squares
z
Applying the Minimization Theorem three
times:
F(x, y, z) = x y z + x y z + x y z + x y z
= yz + y z
Chapter 1 111
Three-Variable Maps
0
4 X
6 5
7
Y 3 Z
2 1
Chapter 1 112
Three-Variable Maps
4 5 7 6
x
z
Read off the product terms for the
rectangles shown
Chapter 1 113
Three-Variable Maps
4 5 7 6
x
z
Read off the product terms for the
rectangles shown
Chapter 1 114
Three Variable Maps
1 1 1
x 1 1
F(x, y, z) = z + x y
Chapter 1 115
Three-Variable Map Simplification
Chapter 1 116
Four Variable Maps
0 1 3 2
4 5 7 6
X
Variable Order 12 13 15 14
W
8 9 11 10
Chapter 1 117
Four Variable Terms
Chapter 1 118
Four-Variable Maps
0 1 3 2
4 5 7 6
X
12 13 15 14
W
8 9 11 10
Chapter 1 119
Four-Variable Maps
0 1 3 2
4 5 7 6
X
12 13 15 14
W
8 9 11 10
Z
Chapter 1 120
Four-Variable Map Simplification
Chapter 1 121
Four-Variable Map Simplification
Chapter 1 122
Systematic Simplification
A Prime Implicant is a product term obtained by combining the maximum possible number of adjacent
squares in the map into a rectangle with the number of squares a power of 2.
A prime implicant is called an Essential Prime Implicant if it is the only prime implicant that covers
(includes) one or more minterms.
Prime Implicants and Essential Prime Implicants can be determined by inspection of a K-Map.
A set of prime implicants "covers all minterms" if, for each minterm of the function, at least one prime
implicant in the set of prime implicants includes the minterm.
Chapter 1 123
Example of Prime Implicants
1 1 1
1 1 1
BD 1 1 BD 1 1
B B
1 1 1 1
A A
1 1 1 1 1 1 1 1
A B
D D
Chapter 1 125
Another Example
Chapter 1 126
Five Variable or More K-Maps
Y Y
X X
W W
Z Z
Chapter 1 127
Don't Cares in K-Maps
Chapter 1 128
Don't Cares in K-Maps
Chapter 1 129
Example: BCD “5 or More”
w
1 1 X X
8 9 11 10
POS solution for F1(w,x,y,z) is not changed
z by using the don't cares.
Chapter 1 130
Product of Sums Example
Chapter 1 131
Optimization Algorithm
Chapter 1 132
Prime Implicant Selection Rule
Chapter 1 133
Selection Rule Example
1 1 1 1 1
1 1 1 1 1 1 1 1
B B
1 1
A A
1 1 1 1
D D
Minterms covered by essential prime implicants
Chapter 1 134
Selection Rule Example with Don't Cares
1 x 1 x
1 x x 1 1 x x 1
B B
x x
A A
1 1 x 1 1 x
D D
Minterms covered by essential prime implicants
Chapter 1 135
Practical Optimization
Illustration on a K-map:
C C
1 1 1 1 1X 1X 1X 1X
1 1 1 1 1 1
B B
1 1 1 1 1 1
A A
D D
Original F & EXPAND ESSENTIAL & IRREDUNDANT
COVER
Chapter 1 137
Example Algorithm: Espresso
Continued:
C C
X X X X X X X X
1 1 1 1 1 1
B B
1 1 1 1 1 1
A A
D D
REDUCE EXPAND
Chapter 1 138
Example Algorithm: Espresso
Continued:
C C
X X X X 1 1 1 1
1 1 1 1 1 1
B B
1 1 1 1 1 1
A A
D D
IRREDUNDANT COVER After REDUCE, EXPAND,
IRREDUNDANT COVER,
1 1 1 1
1 1 1
B
Selected 1 1 1
A
Minterms covered by essential prime implicants
Chapter 1 142
Transformations (continued)
Chapter 1 143
Transformation Examples
Algebraic Factoring
F = A C D + A B C + ABC + AC D G = 16
• Factoring:
F = A ( C D + B C ) + A (BC + C D ) G = 16
• Factoring again:
F = A C ( B + D ) + AC (B + D ) G = 12
• Factoring again:
F=( + AC) (B + ) G = 10
A C D
Chapter 1 144
Transformation Examples
Decomposition
• The terms B + D and A C + AC can be defined as
new functions E and H respectively,
decomposing F:
F = E H, E = B + D , and H = A C + AC G = 10
This series of transformations has reduced G from
16 to 10, a substantial savings. The resulting
circuit has three levels plus input inverters.
Chapter 1 145
Transformation Examples
Substitution of E into F
• Returning to F just before the final factoring step:
F = A C ( B + D ) + AC (B + D ) G = 12
• Defining E = B + , and substituting in F:
D
F = A C E + ACE G = 10
• This substitution has resulted in the same cost as the
decomposition
Chapter 1 146
Transformation Examples
Elimination
• Beginning with a new set of functions:
X=B+C
Y=A+B
Z= AX+CY G = 10
• Eliminating X and Y from Z:
Z = A (B + C) + C (A + B) G = 10
• “Flattening” (Converting to SOP expression):
Z = B + C + AC + BC G = 12
A A
• This has increased the cost, but has provided an new
SOP expression for two-level optimization.
Chapter 1 147
Transformation Examples
Two-level Optimization
• The result of 2-level optimization is:
Z= A B+ C G=4
This example illustrates that:
• Optimization can begin with any set of equations,
not just with minterms or a truth table
• Increasing gate input count G temporarily during a
series of transformations can result in a final
solution with a smaller G
Chapter 1 148
Transformation Examples
Extraction
• Beginning with two functions:
E = A B D + A BD
H = B C D + BCD G = 16
• Finding a common factor and defining it as a
function:
F = B D + BD
• We perform extraction by expressing E and H as
the three functions:
F= + BD, E = F, H = CF G = 10
B D A
• The reduced cost G results from the sharing of logic
between the two output functions
Chapter 1 149
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals
as the course textbook.
These materials or adaptations thereof are not to be
sold or otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 150
Logic and Computer Design Fundamentals
Chapter 1 152
Other Gate Types
Why?
• Implementation feasibility and low cost
• Power in implementing Boolean functions
• Convenient conceptual representation
Gate classifications
• Primitive gate - a gate that can be described using a
single primitive operation type (AND or OR) plus an
optional inversion(s).
• Complex gate - a gate that requires more than one
primitive operation type for its description
Primitive gates will be covered first
Chapter 1 153
Buffer
X F
In terms of Boolean function, a buffer is the
same as a connection!
So why use it?
• A buffer is an electronic amplifier used to
improve circuit voltage levels and increase the
speed of circuit operation.
Chapter 1 154
NAND Gate
Y F( X , Y, Z ) = X × Y × Z
Z
Chapter 1 155
NAND Gates (continued)
Y F( X , Y, Z ) = X + Y + Z
Z
Chapter 1 156
NAND Gates (continued)
Chapter 1 157
NOR Gate
Y F( X, Y, Z) = X + Y + Z
Z
Chapter 1 158
NOR Gate (continued)
Chapter 1 160
Exclusive OR/ Exclusive NOR
Chapter 1 161
Exclusive OR/ Exclusive NOR
Chapter 1 162
Truth Tables for XOR/XNOR
or X º Y
0 0 0 0 0 1
0 1 1 0 1 0
1 0 1 1 0 0
Chapter 1 163
XOR/XNOR (Continued)
X Å 0 = X X Å 1 = X
X Å X = 0 X Å X = 1
X Å Y = Y Å X
( X Å Y) Å Z = X Å ( Y Å Z ) = X Å Y Å Z
Chapter 1 164
Symbols For XOR and XNOR
XOR symbol:
XNOR symbol:
Chapter 1 165
XOR Implementations
X Y
X Y
Chapter 1 166
Odd and Even Functions
Y
F
Z
Chapter 1 168
Example: Even Function Implementation
X
F
Chapter 1 169
Parity Generators and Checkers
In Chapter 1, a parity bit added to n-bit code to produce an n
+ 1 bit code:
• Add odd parity bit to generate code words with even parity
• Add even parity bit to generate code words with odd parity
• Use odd parity circuit to check code words with even parity
• Use even parity circuit to check code words with odd parity
Example: n = 3. Generate even
X
parity code words of length four
Y
with odd parity generator: P
Check even parity code words of Z
Chapter 1 173
Resolving 3-State Values on a Connection
0 X 0 X X IN1
EN1
Chapter 1 175
More Complex Gates
Chapter 1 176
More Complex Gates (continued)
Chapter 1 177
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 178
Logic and Computer Design Fundamentals
Chapter 1 180
Overview (continued)
Chapter 1 181
Combinational Circuits
Logic
Circuit
m Boolean Inputs
n Boolean Outputs
Chapter 1 182
Design Procedure
1. Specification
• Write a specification for the circuit if one is not
already available
2. Formulation
• Derive a truth table or initial Boolean equations that
define the required relationships between the inputs
and outputs, if not in the specification
• Apply hierarchical design if appropriate
3. Optimization
• Apply 2-level and multiple-level optimization
• Draw a logic diagram or provide a netlist for the
resulting circuit using ANDs, ORs, and inverters
Chapter 1 183
Design Procedure
4. Technology Mapping
• Map the logic diagram or netlist to the
implementation technology selected
5. Verification
• Verify the correctness of the final design
manually or using simulation
Chapter 1 184
Design Example
1. Specification
• BCD to Excess-3 code converter
• Transforms BCD code for the decimal digits to
Excess-3 code for the decimal digits
• BCD code words for digits 0 through 9: 4-bit
patterns 0000 to 1001, respectively
• Excess-3 code words for digits 0 through 9: 4-bit
patterns consisting of 3 (binary 0011) added to
each BCD code word
• Implementation:
multiple-level circuit
NAND gates (including inverters)
Chapter 1 185
Design Example (continued)
2. Formulation
• Conversion of 4-bit codes can be most easily
formulated by a truth table
• Variables Input BCD Output Excess-3
- BCD: ABCD WXYZ
A,B,C,D 0000 0011
• Variables 0001 0100
0010 0101
- Excess-3 0011 0110
W,X,Y,Z 0100 0111
• Don’t Cares 0101 1000
- BCD 1010 0110 1001
0111 1010
to 1111 1000 1011
1001 1011
Chapter 1 186
Design Example (continued)
3. Optimization z
C
y
C
a.
1 1 1 1
2-level using
0 1 3 2 0 1 3 2
1 1 1 1
K-maps
4 5 7 6 4 5 7 6
X X X X B X X X X B
12 13 15 14 12 13 15 14
W = A + BC + BD A 1
8 9
X
11
X
10
A 1
8 9
X
11
X
10
X = BC + BD + BC D
D D
Y = CD + C D
Z= D
x C C
w
1 1 1
0 1 3 2 0 1 3 2
1 1 1 1
4 5 7 6 4 5 7 6
X X X X B X X X X B
12 13 15 14 12 13 15 14
A 1 X X A 1 1 X X
8 9 11 10 8 9 11 10
D Chapter 1 D 187
Design Example (continued)
3. Optimization (continued)
b. Multiple-level using transformations
W = A + BC + BD
X = B C + BD + B C D
Y = CD + C D
Z= D G = 7 + 10 + 6 + 0 = 23
• Perform extraction, finding factor:
T1 = C + D
W = A + BT1
X = B T1 + B C D
Y = CD + C D
Z= D G = 2 + 1 + 4 + 7 + 6 + 0 = 19
Chapter 1 188
Design Example (continued)
3. Optimization (continued)
b. Multiple-level using transformations
T1 = C + D
W = A + BT1
X = B T1 + B C D
Y = CD + C D
Z = D G = 19
• An additional extraction not shown in the text since it uses a
Boolean transformation: ( = C +C DD = ): T1
W = A + BT1
X = B T1 + B T1
Y = CD + T1
Z= D G = 2 +1 + 4 + 6 + 4 + 0 = 16!
Chapter 1 189
Design Example (continued)
4. Technology Mapping
• Mapping with a library containing inverters and 2-input
NAND, 2-input NOR, and 2-2 AOI gates
A A
W
W
B
X
B
X
C
C
DY Y
D
Z
Chapter 1 190
Beginning Hierarchical Design
Chapter 1 191
Hierarchy for Parity Tree Example
X0
X1
X2
9-Input
X3
X4 odd Z O
X5 function
X6 X0 A 0
3-Input
X7
X8 X1 A 1
odd B O
function
X A
(a) Symbol for circuit 2 2
X 3
A 0
A 0
3-Input 3-Input
X4 A odd B A odd B Z
1 O 1 O O
function function
X5 A 2
A 2
X6 A 0
3-Input
X7 A odd B
1 O
function
X8 A 2
function blocks
A 0
A 1 B O
A 2
interconnected exclusive-OR
blocks
NANDs
Chapter 1 192
Reusable Functions
Chapter 1 193
Top-Down versus Bottom-Up
Chapter 1 194
Technology Mapping
Mapping Procedures
• To NAND gates
• To NOR gates
• Mapping to multiple types of logic blocks in
covered in the reading supplement: Advanced
Technology Mapping.
Chapter 1 195
Mapping to NAND gates
Assumptions:
• Gate loading and delay are ignored
• Cell library contains an inverter and n-input NAND
gates, n = 2, 3, …
• An AND, OR, inverter schematic for the circuit is
available
The mapping is accomplished by:
• Replacing AND and OR symbols,
• Pushing inverters through circuit fan-out points, and
• Canceling inverter pairs
Chapter 1 196
NAND Mapping Algorithm
. .
. .
. .
. .
. .
. .
Chapter 1 197
NAND Mapping Example
A A X
5
B B
6
Y OI
7 2
F 1
C C F
4
3
D D 8 9
E E
(a) (b)
A
B
X
5
C F
6
Y
5 7 D
(c) (d)
Chapter 1 198
Mapping to NOR gates
Assumptions:
• Gate loading and delay are ignored
• Cell library contains an inverter and n-input NOR
gates, n = 2, 3, …
• An AND, OR, inverter schematic for the circuit is
available
The mapping is accomplished by:
• Replacing AND and OR symbols,
• Pushing inverters through circuit fan-out points, and
• Canceling inverter pairs
Chapter 1 199
NOR Mapping Algorithm
. .
. .
. .
. .
. .
. .
Chapter 1 200
NOR Mapping Example
A A
B
B
2
X
1
F
C
C F
3
D
D
E
A E
(a)
(b)
C
F
(c)
Chapter 1 201
Verification
Chapter 1 202
Basic Verification Methods
Chapter 1 203
Verification Example: Manual Analysis
D C C D
Chapter 1 204
Verification Example: Manual Analysis
Find the circuit truth table from the equations and compare to
specification truth table:
Input BCD Output Excess -3
AB CD WXYZ
0000 0011
0001 0100
0010 0101
0011 0110
0100 0111
0101 1000
0110 1001
0111 1010
1000 1011
1001 1011
Simulation procedure:
• Use a schematic editor or text editor to enter a
gate level representation of the final circuit
• Use a waveform editor or text editor to enter a
test consisting of a sequence of input
combinations to be applied to the circuit
This test should guarantee the correctness of the
circuit if the simulated responses to it are correct
Short of applying all possible “care” input
combinations, generation of such a test can be
difficult
Chapter 1 206
Verification Example: Simulation
INV
NOR2
B
INV
NAND2 X
NAND2
C
INV
NAND3 AOI symbol
D not available
INV AND2
Y
NOR2
AND2 AOI
Z
Chapter 1 207
Verification Example: Simulation
INPUTS
A
B
C
D
0 50 ns 100 ns
Chapter 1 208
Verification Example: Simulation
Chapter 1 209
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 210
Logic and Computer Design Fundamentals
Chapter 1 212
Functions and Functional Blocks
Chapter 1 213
Rudimentary Logic Functions
V CC or V DD
1 F5 1 F5 1 X F5 X
(c)
0 F5 0 F5 0
X F5 X
Multi-bit Examples:
A F3 A
2
3
1 2 2:1 F(2:1)
F2 1 4 4
F F
0 F1 0 1
0 (c)
A F0 A
3
(a) (b)
A wide line is used to represent 4 3,1:0 F(3), F(1:0)
F
a bus which is a vector signal
(d)
In (b) of the example, F = (F3, F2, F1, F0) is a bus.
The bus can be split into individual bits as shown in (b)
Sets of bits can be split from the bus as shown in (c)
for bits 2 and 1 of F.
The sets of bits need not be continuous as shown in (d) for bits 3, 1, and 0
of F.
Chapter 1 215
Enabling Function
variables
Chapter 1 217
Decoder Examples
1-to-2-Line Decoder A D0 D1
D0 5 A
0 1 0
1 0 1 A D1 5 A
2-to-4-Line Decoder (a) (b)
A 0
A 1 A 0 D 0 D 1 D 2 D 3
A 1
0 0 1 0 0 0
D 0 5 A 1 A 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1 D 1 5 A 1 A 0
(a)
D 2 5 A 1 A 0
made up of 2 1-to-2- D 3 5 A 1 A 0
Chapter 1 218
Decoder Expansion
Chapter 1 219
Decoder Expansion - Example 1
3-to-8-line decoder
• Number of output ANDs = 8
• Number of inputs to decoders driving output ANDs = 3
• Closest possible split to equal
2-to-4-line decoder
1-to-2-line decoder
• 2-to-4-line decoder
Number of output ANDs = 4
Number of inputs to decoders driving output ANDs = 2
Closest possible split to equal
• Two 1-to-2-line decoders
D0
A0
D1
A1
D2
2-to-4-Line D3
decoder
D4
A2 D5
1-to-2-Line decoders D6
D7
Chapter 1 221
Decoder Expansion - Example 2
7-to-128-line decoder
• Number of output ANDs = 128
• Number of inputs to decoders driving output ANDs = 7
• Closest possible split to equal
4-to-16-line decoder
3-to-8-line decoder
• 4-to-16-line decoder
Number of output ANDs = 16
Number of inputs to decoders driving output ANDs = 2
Closest possible split to equal
• 2 2-to-4-line decoders
• Complete using known 3-8 and 2-to-4 line decoders
Chapter 1 222
Decoder with Enable
demultiplexer A 0
D 0
EN A 1 A 0 D0 D1 D2 D3 D1
0 X X 0 0 0 0
1 0 0 1 0 0 0 D2
1 0 1 0 1 0 0
1 1 0 0 0 1 0
D3
1 1 1 0 0 0
(b)
Chapter 1 223
Combinational Logic Implementation
- Decoder and OR Gates
P2 = A7 + A6 + A3
1
A6
2
+ +
P4 = A7 A6 A5 A5 3
4 P2
Finding sum of A4
5
minterms expressions 6
P1 = Sm(1,2,5,6,8,11,12,15)
8
9
P4
P2 = Sm(1,3,4,6,8,10,13,15) 10
P4 = Sm(2,3,4,5,8,9,14,15)
11
12
Find circuit 13
14
Is this a good idea? 15
Chapter 1 225
Encoding
A decimal-to-BCD encoder
• Inputs: 10 bits corresponding to decimal digits 0
through 9, (D0, …, D9)
• Outputs: 4 bits with BCD codes
• Function: If input bit D is a 1, then the output
i
(A3, A2, A1, A0) is the BCD code for i,
The truth table could be formed, but
alternatively, the equations for each of the
four outputs can be obtained directly.
Chapter 1 227
Encoder Example (continued)
1 0 0 0 0 0 X X X 0
1 0 0 0 0 1 0 0 0 1
2 0 0 0 1 X 0 0 1 1
4 0 0 1 X X 0 1 0 1
8 0 1 X X X 0 1 1 1
16 1 X X X X 1 0 0 1
Xs in input part of table represent 0 or 1; thus table entries correspond to
product terms instead of minterms. The column on the left shows that all 32
minterms are present in the product terms in the table
Chapter 1 230
Priority Encoder Example (continued)
V = D4 + F1 + D1 + D0
Chapter 1 231
Selecting
Since 2 = 21, n = 1
The single selection variable S has two values:
• S = 0 selects input I 0
• S = 1 selects input I 1
The equation:
Y = S I0 + SI1
Enabling
The circuit: Decoder Circuits
I0
Y
S
I1
Chapter 1 234
2-to-1-Line Multiplexer (continued)
Chapter 1 235
Example: 4-to-1-line Multiplexer
2-to-22-line decoder
22 ´ 2 AND-OR
Decoder
S1
4 3 2 AND-OR
S0
Decoder
S1
S0
Y
I1
Y
I2
I3
Chapter 1 236
Multiplexer Width Expansion
quad multi- A0
D0
I 3,0
I 0,1
4 3 2 AND-OR
plexer . Y1
2-to-4-Line decoder . .
. .
.
D3
A1 I 3,1 4 3 2 AND-OR
I 0,2
Y2
.
.
.
I 3,2 4 3 2 AND-OR
I 0,3
Y3
I 3,3
Chapter 1 237
Other Selection Implementations
I1
S1
I2
I3
Chapter 1 239
Example: Gray to Binary Code
0 0 0 0 0 0
code to a binary code 10 0 0 01
010 01 1
the truth table on the 01 1 10 0
right 1 1 1 101
0 01
1 10
1 1 1
table that X = C and the
Y and Z are more complex
Chapter 1 240
Gray to Binary (continued)
0
0 D00 D10
1 D01 1 D11
1 D02 1 D12
D03 0 D13
0
0 D04 1 D14
Out Y Out Z
1 D05 0 D15
1 D06 0 D16
0 D07 1 D17
A S2 A S2
8-to-1 8-to-1
B S1 B S1
MUX MUX
S0 C S0
C
Chapter 1 242
Combinational Logic Implementation
- Multiplexer Approach 2
Chapter 1 243
Example: Gray to Binary Code
0 0 0 0 0 0
code to a binary code 10 0 0 01
010 01 1
the truth table on the 01 1 10 0
right 1 1 1 101
0 01
1 10
1 1 1
table that X = C and the
Y and Z are more complex
Chapter 1 244
Gray to Binary (continued)
Chapter 1 245
Gray to Binary (continued)
C D01 C D11
C C
C D02 Out Y C D12 Out Z
C D03 C D13
8-to-1 8-to-1
A S1 A S1
B S0 MUX B S0 MUX
Note that this approach (Approach 2) reduces the cost by almost
half compared to Approach 1.
This result is no longer ROM-like
Extending, a function of more than n variables is decomposed into
several sub-functions defined on a subset of the variables. The
multiplexer then selects among these sub-functions.
Chapter 1 246
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 247
Logic and Computer Design Fundamentals
Arithmetic functions
• Operate on binary vectors
• Use the same subfunction in each bit position
Can design functional block for subfunction and
repeat to obtain functional block for overall
function
Cell - subfunction block
Iterative array - a array of interconnected cells
An iterative array can be in a single dimension
(1D) or multiple dimensions
Chapter 1 250
Block Diagram of a 1D Iterative Array
A n-1 B n-1 A1 B0
X n-1 X2 X1
Xn X0
Cell n-1 Y n-1 Y2 Cell 1 Y1 Cell 0
Yn Y0
C n-1 C1 C0
Example: n = 32
• Number of inputs = ?
• Truth table rows = ?
• Equations with up to ? input variables
• Equations with huge number of terms
• Design impractical!
Iterative array takes advantage of the regularity to make
design feasible
Chapter 1 251
Functional Blocks: Addition
Chapter 1 252
Functional Block: Half-Adder
+Y +0 +1 +0 +1
CS 00 01 01 10
A half adder adds two bits to produce a two-bit sum
The sum is expressed as a
X Y C S
sum bit , S and a carry bit, C
0 0 0 0
The half adder can be specified as
a truth table for S and C 0 1 0 1
1 0 0 1
1 1 1 0
Chapter 1 253
Logic Simplification: Half-Adder
X 1 2 3 X 2 1 3
S = X × Y + X × Y = X Å Y
S = ( X + Y )×( X + Y )
and
C = X × Y
C = (( X×Y ) )
These equations lead to several implementations.
Chapter 1 254
Five Implementations: Half-Adder
(a) S = X × Y + X × Y ( d ) S = ( X + Y )× C
C = X × Y C = ( X + Y )
( b ) S = ( X + Y )×( X + Y ) (e) S = X Å Y
C = X × Y C = X × Y
( c ) S = ( C + X× Y)
(a), C(b),
= and (e) are
X × Y
SOP, POS, and XOR implementations
for S.
In (c), the C function is used as a term in the AND-NOR
implementation of S, and in (d), the function is used in a
POS term for S. C
Chapter 1 255
Implementations: Half-Adder
S = X Å Y C
C = X × Y
Chapter 1 256
Functional Block: Full-Adder
CS 0 0 01 01 10
• For a carry- in
(Z) of 1: Z 1 1 1 1
X 0 0 1 1
+Y +0 +1 +0 +1
CS 01 10 10 1 1
Chapter 1 257
Logic Optimization: Full-Adder
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
Full-Adder K-Map: 1
1
0
1
1
0
1
1
0
0
1 1 1 1 1
S Y C Y
1 1 1
0 1 3 2 0 1 3 2
X 1 1 X 1 1 1
4 5 7 6 4 5 7 6
Z Z
Chapter 1 258
Equations: Full-Adder
Chapter 1 259
Implementation: Full Adder
Chapter 1 260
Binary Adders
Chapter 1 261
4-bit Ripple-Carry Binary Adder
C3 C2 C1
FA FA FA C0
C4 S3 S2 S1 S0
Chapter 1 262
Unsigned Subtraction
Algorithm:
• Subtract the subtrahend N from the minuend M
• If no end borrow occurs, then M ³ N, and the result is a
non-negative number and correct.
• If an end borrow occurs, the N > M and the difference
M - N + 2n is subtracted from 2n, and a minus sign is
appended to the result.
Examples: 0 1
1001 0100
- 0111 - 0111
0010 1101
10000
- 1101
Chapter 1 263
Unsigned Subtraction (continued)
Result
Chapter 1 264
Complements
Two complements:
• Diminished Radix Complement of N
(r - 1)’s complement for radix r
1’s complement for radix 2
Defined as (rn - 1) - N
• Radix Complement
r’s complement for radix r
2’s complement in binary
Defined as rn - N
Subtraction is done by adding the complement of the
subtrahend
If the result is negative, takes its 2’s complement
Chapter 1 265
Binary 1's Complement
Chapter 1 266
Binary 2's Complement
Chapter 1 268
Subtraction with 2’s Complement
Chapter 1 269
Unsigned 2’s Complement Subtraction Example 1
1
01010100 01010100
2’s comp
– 01000011 + 10111101
00010001
The carry of 1 indicates that no correction
of the result is required.
Chapter 1 270
Unsigned 2’s Complement Subtraction Example 2
Chapter 1 271
Signed Integers
Chapter 1 273
Signed Integer Representation Example
r =2, n=3
– 0 100 111 —
– 4 — — 100
Chapter 1 274
Signed-Magnitude Arithmetic
Chapter 1 275
Sign-Magnitude Arithmetic Examples
Example 1: 0010
+ 0101
Example 2: 0010
+ 1101
Example 3: 1010
- 0101
Chapter 1 276
Signed-Complement Arithmetic
Addition:
1. Add the numbers including the sign bits,
discarding a carry out of the sign bits (2's
Complement), or using an end-around carry (1's
Complement).
2. If the sign bits were the same for both numbers
and the sign of the result is different, an overflow has
occurred.
3. The sign of the result is computed in step 1.
Subtraction:
Form the complement of the number you are
subtracting and follow the rules for addition.
Chapter 1 277
Signed 2’s Complement Examples
Example 1: 1101
+ 0011
Example 2: 1101
- 0011
Chapter 1 278
2’s Complement Adder/Subtractor
of B is formed by using S
passed through
unchanged C4 S3 S2 S1 S0
Chapter 1 279
Overflow Detection
Chapter 1 280
Overflow Detection
Signed number cases with carries Cn and Cn-1 shown for correct result
signs:
0 00 01 11 1
0 0 1 1
+ 0 - 1 - 0 +1
0 0 1 1
Signed number cases with carries shown for erroneous result signs
(indicating overflow):
0 10 11 01 0
0 0 1 1
+ 0 - 1 -0 + 1
1 1 0 0
Simplest way to implement overflow V = Cn + Cn - 1
This works correctly only if 1’s complement and the addition of the
carry in of 1 is used to implement the complementation! Otherwise
fails for - 10 ... 0
Chapter 1 281
Other Arithmetic Functions
A2 A1 A0
S2 S1 S0
(b)
Incrementing
• Adding a fixed value to an arithmetic variable
• Fixed value is often 1, called counting (up)
• Examples: A + 1, B + 4
• Functional block is called incrementer
Decrementing
• Subtracting a fixed value from an arithmetic variable
• Fixed value is often 1, called counting (down)
• Examples: A - 1, B - 4
• Functional block is called decrementer
Chapter 1 285
Multiplication/Division by 2n
(a) Multiplication B3 B2 B1 B0
by 100
• Shift left by 2 C5 C4 C3 C2
0
C1
0
C0
by 100 B3 B2 B1 B0
• Shift right by 2
• Remainder 0 0
preserved
C3 C2 C1 C0 C 21 C 22
(b)
Chapter 1 286
Multiplication by a Constant
4-bit Adder
Carry
output Sum
C 6 C 5 C 4 C 3 C 2 C 1 C 0
Chapter 1 287
Zero Fill
Chapter 1 288
Extension
Chapter 1 289
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 290
Logic and Computer Design Fundamentals
Chapter 1 292
Introduction to Sequential Circuits
Inputs Outputs
Combina-tional
A Sequential
Logic
circuit contains:
Storage
Implements a multiple-output
switching function
Inputs are signals from the outside.
Outputs are signals to the outside.
Other inputs, State or Present State, are signals
from storage elements.
The remaining outputs, Next State are inputs
to storage elements.
Chapter 1 293
Introduction to Sequential Circuits
Inputs Outputs
Combina-tional
Logic
Storage
Elements
Combinatorial Logic Next
• Next state function State State
Next State = f(Inputs, State)
• Output function (Mealy)
Outputs = g(Inputs, State)
• Output function (Moore)
Outputs = h(State)
Output function type depends on specification and affects the
design significantly
Chapter 1 294
Types of Sequential Circuits
Chapter 1 295
Discrete Event Simulation
Chapter 1 296
Simulated NAND Gate
0 1 Þ 0 1 1 Ü 0 0 F(I) changes to 1
Chapter 1 297
Gate Delay Models
Chapter 1 298
Circuit Delay Model
Consider a simple A
2-input multiplexer: 0.4
With function: 0.2
Y
• Y = A for S = 1 0.5
• Y = B for S = 0 S
B 0.4
A
B
S
Y
“Glitch” is due to delay of inverter
Chapter 1 299
Storing State
What if A con-
nected to Y? 0.4
Circuit becomes: 0.2
With function: 0.5
• Y = B for S = 1, and S Y
Y(t) dependent on
0.4
Y(t – 0.9) for S = 0 B
B
S
1 1 1 Y = B when S = 1
0 0 0 Y “remembers” B = 0 for S = 0
Chapter 1 301
Storing State (Continued)
Suppose we place
an inverter in the
“feedback path.” 0.4
0.2
0.2
0.5
S Y
B 0.4
The following behavior results:
The circuit is said B S Y Comment
to be unstable. 0 1 0 Y = B when S = 1
For S = 0, the 1 1 1
Chapter 1 302
Basic (NAND) S – R Latch
“Cross-Coupling” S (set)
Q
two NAND gates gives
the S -R Latch:
Which has the time Q
R (reset)
sequence behavior:
Time R S Q Q Comment
1 0 1 0 “Set” Q to 1
S = 0, R = 0 is 1 1 1 0 Now Q “remembers” 1
0 1 0 1 “Reset” Q to 0
forbidden as 1 1 0 1 Now Q “remembers” 0
input pattern 0 0 1 1 Both go high
1 1 ? ? Unstable!
Chapter 1 303
Basic (NOR) S – R Latch
0 1 1 0 “Set” Q to 1
0 0 1 0 Now Q “remembers” 1
1 0 0 1 “Reset” Q to 0
0 0 0 1 Now Q “remembers” 0
1 1 0 0 Both go low
0 0 ? ? Unstable!
Chapter 1 304
Clocked S - R Latch
S - R NAND latch
C
gives the clocked
S – R latch: Q
R
Chapter 1 305
Clocked S - R Latch (continued)
Chapter 1 306
D Latch
Adding an inverter D
no “indeterminate”
states! The graphic symbol for a
Q D Q(t+1) Comment
D Latch is:
0 0 0 No change D Q
0 1 1 Set Q
1 0 0 Clear Q
C Q
1 1 1 No Change
Chapter 1 307
Flip-Flops
Chapter 1 308
The Latch Timing Problem
Chapter 1 309
The Latch Timing Problem (continued)
D Q Y
Clock Q
Suppose that initially Y = 0. C
Clock
Y
As long as C = 1, the value of Y continues to change!
The changes are based on the delay present on the loop
through the connection from Y back to Y.
This behavior is clearly unacceptable.
Desired behavior: Y changes only once per clock pulse
Chapter 1 310
The Latch Timing Problem (continued)
Chapter 1 311
S-R Master-Slave Flip-Flop
C C C
with the clock on the
R R
second latch inverted Q R Q Q
Chapter 1 312
Flip-Flop Problem
Chapter 1 314
Edge-Triggered D Flip-Flop
The edge-triggered
D D S
D flip-flop is the Q Q Q
C C
slave D flip-flop Q R Q Q
Formed by D D Q S
adding inverter
Q Q
to clock input C C
Q R Q Q
Chapter 1 316
Standard Symbols for Storage
Elements
S S D D
R R C C
Postponed output S S D D
indicators C C
R R C C
Dynamic
indicator
D D
C C
Triggered D Triggered D
it begins operation
This initialization is often done C Q
Chapter 1 318
Sequential Circuit Analysis
General Model
• Current State Inputs
Combina-tional
Outputs
Chapter 1 319
Example 1 (from Fig. 5-15)
Input: x(t)
x
Output: y(t) D Q A
A
C Q
CP C Q
Function?
Chapter 1 320
Example 1 (from Fig. 5-15) (continued)
Boolean equations
for the functions: x
• A(t+1) = A(t)x(t) D Q A
+ B(t)x(t) C Q A
Next State
• B(t+1) = A(t)x(t)
• y(t) = x(t)(B(t) + A(t)) D Q B
CP C Q'
Output
Chapter 1 321
Example 1(from Fig. 5-15) (continued)
Where in time are inputs, outputs and states
defined?
0 0
0
1
Chapter 1 322
State Table Characteristics
Chapter 1 323
Example 1: State Table (from Fig. 5-15)
The state table can be filled in using the next state and
output equations: A(t+1) = A(t)x(t) + B(t)x(t) B(t+1) =A
(t)x(t) y(t) =x (t)
(B(t) + A(t))
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 0 0 1
0 1 1 1 1 0
1 0 0 0 0 1
1 0 1 1 0 0
1 1 0 0 0 1
1 1 1 1 0 0
Chapter 1 324
Example 1: Alternate State Table
0 0 0 0 0 1 0 0
0 1 0 0 1 1 1 0
1 0 0 0 1 0 1 0
1 1 0 0 1 0 1 0
Chapter 1 325
State Diagrams
Chapter 1 326
State Diagrams
Label form:
• On circle with output included:
state/output
Moore type output depends only on state
• On directed arc with the output included:
input/output
Mealy type output depends on state and
input
Chapter 1 327
Example 1: State Diagram
x=0/y=0 x=0/y=1
Which type? x=1/y=0
Diagram gets AB
00 10
confusing for
x=0/y=1
usually easier to
understand than 01 11
the state table x=1/y=0
Chapter 1 328
Equivalent State Definitions
Chapter 1 329
Equivalent State Example
1 is S2. 1/0
Chapter 1 330
Equivalent State Example
1/0
Chapter 1 331
Moore and Mealy Models
Chapter 1 332
Moore and Mealy Example Diagrams
x=0/y=0
0 1
0/0
x=0
x=1
x=1
x=0
2/1
1/0
x=1
Chapter 1 333
Moore and Mealy Example Tables
0 0 1 0
1 0 2 0
2 0 2 1
0 0 1 0 0
1 0 1 0 1
Chapter 1 334
Mixed Moore and Mealy Outputs
specification
1/0
10 11
1/0
Chapter 1 335
Example 2: Sequential Circuit Analysis
Logic Diagram: D Q
A
Z
C R Q
D
B
Q
C R Q
D
C
Q
Clock C R Q
Reset
Chapter 1 336
Example 2: Flip-Flop Input Equations
Variables
• Inputs: None
• Outputs: Z
• State Variables: A, B, C
Initialization: Reset to (0,0,0)
Equations
• A(t+1) = Z=
• B(t+1) =
• C(t+1) =
Chapter 1 337
Example 2: State Table
X’ = X(t+1)
ABC A’B’C’ Z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Chapter 1 338
Example 2: State Diagram
ABC
Reset 000
Chapter 1 340
Logic and Computer Design Fundamentals
Chapter 1 342
The Design Procedure
Specification
Formulation - Obtain a state diagram or state table
State Assignment - Assign binary codes to the states
Flip-Flop Input Equation Determination - Select flip-flop
types and derive flip-flop equations from next state entries in the table
Output Equation Determination - Derive output equations from
output entries in the table
Optimization - Optimize the equations
Technology Mapping - Find circuit from equations and map to
flip-flops and gate technology
Verification - Verify correctness of final design
Chapter 1 343
Specification
Chapter 1 344
Formulation: Finding a State Diagram
Chapter 1 345
Formulation: Finding a State Diagram
Chapter 1 346
Sequence Recognizer Procedure
To develop a sequence recognizer state diagram:
•Begin in an initial state in which NONE of the initial portion of the
sequence has occurred (typically “reset” state).
• Add a state that recognizes that the first symbol has occurred.
• Add states that recognize each successive symbol occurring.
• The final state represents the input sequence (possibly less the
final input value) occurence.
• Add state transition arcs which specify what happens when a
symbol not in the proper sequence has occurred.
• Add other arcs on non-sequence inputs which transition to states
that represent the input subsequence that has occurred.
The last step is required because the circuit must recognize the input
sequence regardless of where it occurs within the overall sequence
applied since “reset.”.
Chapter 1 347
State Assignment
Chapter 1 348
Sequence Recognizer Example
Chapter 1 349
Example: Recognize 1101
Chapter 1 350
Example: Recognize 1101 (continued)
• Transition arcs are used to denote the output function (Mealy Model)
• Output 1 on the arc from D means the sequence has been recognized
• To what state should the arc from state D go? Remember: 1101101 ?
• Note that D is the last state but the output 1 occurs for the input applied in
D. This is the case when a Mealy model is assumed.
Chapter 1 351
Example: Recognize 1101 (continued)
1/1
Chapter 1 352
Example: Recognize 1101 (continued)
1/1
The state have the following abstract meanings:
• A: No proper sub-sequence of the sequence has
occurred.
• B: The sub-sequence 1 has occurred.
• C: The sub-sequence 11 has occurred.
• D: The sub-sequence 110 has occurred.
• The 1/1 on the arc from D to B means that the last 1 has
occurred and thus, the sequence is recognized.
Chapter 1 353
Example: Recognize 1101 (continued)
Answer:
1/1
"0" arc from A
"0" arc from B
"1" arc from C
"0" arc from D.
Chapter 1 354
Example: Recognize 1101 (continued)
0/0
1/1
Chapter 1 355
Formulation: Find State Table
Chapter 1 356
Formulation: Find State Table
0/0
1/1
0/0
Present Next State Output
State x=0 x=1 x=0 x=1
A A B 0 0
B A C 0 0
C D C 0 0
What
D
wouldA
the
B
state diagram
0 1
and state table look
like for the Moore model?
Chapter 1 357
Example: Moore Model for Sequence 1101
Chapter 1 358
Example: Moore Model (continued)
state transitions
0 1
Add a new state E to 1
Chapter 1 359
Example: Moore Model (continued)
below 1 1
0
A/0 B/0 C/0 D/0
A A B 0
B A C 0
C D C 0
D A E 0
E A C 1
Chapter 1 360
State Assignment – Example 1
A A B 0 0
B A B 0 1
A A B 0 0
B A C 0 0
C D C 0 0
D A B 0 1
Chapter 1 362
State Assignment – Example 2 (continued)
00 00 01 0 0
01 00 10 0 0
10 11 10 0 0
11 00 01 0 1
Chapter 1 363
State Assignment – Example 2 (continued)
Chapter 1 364
Find Flip-Flop Input and Output Equations:
Example 2 – Counting Order Assignment
Assume D flip-flops
Interchange the bottom two rows of the state table, to obtain K-maps for D1, D2,
and Z:
D1 D2 Z
X X X
0 0 0 1 0 0
0 1 0 0 0 0
Y2 Y2 Y2
0 0 0 1 0 0
Y1 Y1 Y1
1 1 1 0 0 1
Chapter 1 365
Optimization: Example 2: Counting Order
Assignment
0 0 0 1 0 0
0 1 0 0 0 0
Y2 Y2 Y2
0 0 0 1 0 0
Y1 Y1 Y1
1 1 1 0 0 1
D1 = Y1Y2 + XY1Y2
D2 = XY1Y2 + XY1Y2 + XY1Y2
Z = XY1Y2 Gate Input Cost = 22
Chapter 1 366
Find Flip-Flop Input and Output Equations:
Example 2 – Gray Code Assignment
Assume D flip-flops
Obtain K-maps for D1, D2, and Z:
D1 D2 Z
X X X
0 0 0 1 0 0
0 1 0 1 0 0
Y2 Y2 Y2
1 1 0 1 0 0
Y1 Y1 Y1
0 0 0 1 0 1
Chapter 1 367
Optimization: Example 2: Assignment 2
0 0 0 1 0 0
0 1 0 1 0 0
Y2 Y2 Y2
1 1 0 1 0 0
Y1 Y1 Y1
0 0 0 1 0 1
D1 = Y1Y2 + XY2 Gate Input Cost = 9
D2 = X Select this state assignment to
Z = XY1Y2 complete design in slide
Chapter 1 368
One Flip-flop per State (One-Hot) Assignment
Chapter 1 369
State Assignment – Example 2 (continued)
Chapter 1 370
Optimization: Example 2: One Hot Assignment
• NAND gates
with up to 4 C
R
inputs and
Z
inverters
Y2
X D
Clock C
R
Reset
Chapter 1 372
Mapped Circuit - Final Result
Y1
D
C
R
Y2
X D
Clock C
R
Reset
Chapter 1 373
Sequential Design: Example 3
Chapter 1 374
Example 3 (continued)
00
Reset A/00
01
C/10 B/01
Chapter 1 375
Example 3 (continued)
Chapter 1 376
Example 3 (continued)
X X
X X
Y0 Y0
X X X X X X X X
Y1 Y1
X X
X0 X0
D1 =
D0 =
Chapter 1 377
Circuit - Final Result with AND, OR, NOT
X1
Y1
D Z1
X0
C
R
Y0
D Z0
C
R
Reset
Clock
Chapter 1 378
Other Flip-Flop Types
Behavior
• Same as S-R flip-flop with J analogous to S and K
analogous to R
• Except that J = K = 1 is allowed, and
• For J = K = 1, the flip-flop changes to the opposite
state
• As a master-slave, has same “1s catching” behavior as
S-R flip-flop
• If the master changes to the wrong state, that state will
be passed to the slave
E.g., if master falsely set by J = 1, K = 1 cannot reset it during
the current clock cycle
Chapter 1 380
J-K Flip-flop (continued)
Implementation Symbol
• To avoid 1s catching
behavior, one solution
used is to use an
J
edge-triggered D as
the core of the flip-flop
C
J D
K
C
Chapter 1 381
T Flip-flop
Behavior
• Has a single input T
For T = 0, no change to state
For T = 1, changes to opposite state
Same as a J-K flip-flop with J = K = T
As a master-slave, has same “1s catching”
behavior as J-K flip-flop
Cannot be initialized to a known state using the T
input
• Reset (asynchronous or synchronous) essential
Chapter 1 382
T Flip-flop (continued)
Implementation Symbol
• To avoid 1s catching
behavior, one solution
used is to use an T
edge-triggered D as
the core of the flip-flop
C
D
T
Chapter 1 383
Basic Flip-Flop Descriptors
Used in analysis
• Characteristic table - defines the next state of
the flip-flop in terms of flip-flop inputs and
current state
• Characteristic equation - defines the next state
of the flip-flop as a Boolean function of the
flip-flop inputs and the current state
Used in design
• Excitation table - defines the flip-flop input
variable values as function of the current state
and next state
Chapter 1 384
D Flip-Flop Descriptors
Characteristic Table
D Q(t + 1) Operation
0 0 Reset
1 1 Set
Characteristic Equation
Q(t+1) = D
Excitation Table
Q(t +1) D Operation
0 0 Reset
1 1 Set
Chapter 1 385
T Flip-Flop Descriptors
Characteristic Table
T Q(t + 1) Operation
0 Q (t) No change
1 Q (t) Complement
Characteristic Equation
Q(t+1) = T Å Q
Excitation Table
Q(t
+ 1) T Operation
Q (t) 0 No change
Q (t) 1 Complement
Chapter 1 386
S-R Flip-Flop Descriptors
Characteristic Table
S R Q(t + 1) Operation
0 0 Q (t) No change
0 1 0 Reset
1 0 1 Set
Characteristic
1 1
Equation
? Undefined
Q(t+1) = S + R Q, S.R = 0
Excitation Table
Q(t) Q(t+ 1) S R Operation
0 0 0 X No change
0 1 1 0 Set
1 0 0 1 Reset
1 1 X 0 No change
Chapter 1 387
J-K Flip-Flop Descriptors
Characteristic Table
J K Q(t + 1) Operation
0 0 Q (t) No change
0 1 0 Reset
1 0 1 Set
1 1 Q (t) Complement
Characteristic Equation
Q(t+1) = J Q + K Q
Excitation Table
Q(t) Q(t 1) J K Operation
+
0 0 0 X No change
0 1 1 X Set
1 0 X 1 Reset
1 1 X 0 No Change
Chapter 1 388
Flip-flop Behavior Example
Use the characteristic tables to find the output waveforms for
the flip-flops shown:
Clock
D,T
D QD
QT
T
Chapter 1 389
Flip-Flop Behavior Example (continued)
Use the characteristic tables to find the output waveforms for
the flip-flops shown:
Clock
S,J
R,K
S QSR ?
C
R
J QJK
C
K
Chapter 1 390
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 391
Logic and Computer Design Fundamentals
Chapter 1 393
Finite State Machines
Chapter 1 394
Issues with Traditional State Diagram and
Table Representations
Chapter 1 396
The State Machine Diagram Model
Chapter 1 397
The State Machine Diagram
Chapter 1 398
State Machine Diagram
Chapter 1 399
State Machine Diagram
Chapter 1 400
The State Machine Diagram
Chapter 1 401
The State Machine Diagram
Chapter 1 402
The State Machine Diagram
Chapter 1 403
The State Machine Diagram
Chapter 1 404
Examples Of Transition & Output Conditions
Output Variables Y, Z S0 S1 S0 S1
Default: Y = 0, Z = 0 A + B
A + B
Y, Z A/Y, B/Z
S2 S2
C/Y
A×B/Y A×B
S0 S1 S0 S1
C/Y
(A + B)/Z
(A + B)
S2 S2
Chapter 1 405
Constraint Checking
TC Constraints
• Constraint 1: In state Si, for all possible TC pairs (Tij, Tik) on arcs to
distinct next states from Si,
Tij × Tik = 0
• Constraint 2: In state Si, for all possible TCs, Tij
S Tij = 1
OC Constraints
• Constraint 1: For every output action in state Si or on its transitions having
coincident output variables with differing values, the corresponding pair
of output condition (Oij, Oik) must be mutually exclusive, i. e., satisfy
Oij × Oik = 0
• Constraint 2:For every output variable, the output conditions for state Si or
its transitions must cover all possible combinations of input variables that
can occur, i. e.,
S Oij = 1
• For both output constraints above, TCs must be used in evaluating O ij for
output actions of TCD and TCOD output action types
• See text for using don’t cares and defaults.
Chapter 1 406
Constraint Checking Example
Chapter 1 407
Constraint Violation Examples
Transition Constraints X
• Example A: X×Y ¹ 0 and X + Y ¹ 1, A
S0
Y
S1
so constraint 2 is violated X
Outputs XY
S1
Chapter 1 408
State Table Format
Chapter 1 409
State Table Example
A+ B S2 10
S1 01 A/Y, B/Z
A×C S2 10
A+ C S3 11
Continued on next slide
Chapter 1 410
State Table Example (continued)
Chapter 1 411
State Machine Design Procedure
Chapter 1 412
Example State Machine Design –
Elevator Control – Inputs
Circuit: Elevator control for two-floor elevator
Warning: Does not include safety features or all user buttons!
C1(C2) – Call button (outside elevator) to floor 1(2)
0 – no action; 1 – call for elevator
G1(G2) – Go button (inside elevator) to floor 1(2)
• 0 – no action; 1 – go to floor command
F1(F2) – Senses elevator at floor 1(2)
• 0 – elevator not at floor; 1 – elevator at floor
S1(S2) – Senses elevator approaching floor 1(2) (Controls slowdown of
elevator)
• 0 – elevator not approaching floor; 1 – elevator approaching floor
DO – Doors open
• 0 – doors not fully open; 1 – doors fully open
TO – End of time interval from button push to elevator movement starting
• 0 – waiting for time interval to end; 1 – time interval has ended
DC – Doors closed
• 0 – doors not closed; 1 – doors closed
Chapter 1 413
Example – Elevator Control - Outputs
• Up – elevator to go up
0 – no action; 1 – commands elevator to go up
• Down – commands elevator to go down
0 – no action; 1 – commands elevator to go down
• TS – timer start
0 – no action; 1 – initialize and start timer
• SD – slow down
0 – elevator moves as normal speed; 1 – elevator approaching
target floor slows down
• OD – Open Doors
0 – no action; 1 – open doors
• CD – Close Doors
0 – no action; 1 – close doors
Chapter 1 414
Example – Elevator Operation –
Specifications
The elevator parks at the floor to which it has last taken passengers
with doors open.
Call button Ci calls elevator to a floor.
If the elevator is not at the floor, TS is used to initialize and start the
timer;
After TO becomes 1, the doors close, and when DC is active, the Up
or Down output is activated.
The Si sensor detects the floor approach and activates output SD to
slow elevator.
The Fi sensor detects the elevator at the floor, forces both Up and Dn
to 0, and opens the doors.
Passenger(s) enter elevator and push the Gi button.
After TO becomes 1, the doors close, and when DC is active, the Up
or Down output is activated.
The Si sensor detects the approach and activates output SD to slow
elevator.
The Fi sensor detects the elevator at the floor, forces both Up and Dn
to 0, and opens the doors, permitting passengers to exit.
Chapter 1 415
Example – Elevator Control – States
Chapter 1 416
Example – Elevator Control – SMD
S1/SD
F1
F1 Dn
Down
TO
TO
Hd_A Hd_B Hd_C DC×(F1 + F2)/CD
DO/OD
DC×F1
Up
S2/SD
Chapter 1 417
Example – Elevator Control – SMT
F1 Hd_A 00001
U Up, S2/SD
F2 Up 10000
F2 Hd_A 00001
Chapter 1 419
Example – Elevator Control - Equations
Chapter 1 420
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 421
Logic and Computer Design Fundamentals
Chapter 1 423
Integrated Circuits
Chapter 1 424
MOS Transistor
0 V olts
0 V olts
G (G ate) V V olts
DD
S (Source) D (D rain)
Channel
length Location of
conducting
layer
Substrate
Chapter 1 425
MOS Transistor
V D D Volts
0 Volts G (G ate) V D D Volts
S (Source) D (D rain)
Channel
length Location of
conducting
layer
Substrate
Chapter 1 426
Switch Models for MOS Transistors
Chapter 1 427
Circuits of Switch Models
Series
X: X
X A ND Y
Y: Y
Series
Parallel
X: X Y: Y X O R Y
Parallel
Chapter 1 428
Fully-Complementary CMOS Circuit
F using
•
p-type
•
•
transistors
(NC switches)
• F
X1 •
X2 F using
• n-type
•• •
•
• • transistors
Xn • (NO switches)
logic 0
Chapter 1 429
CMOS Circuit Design Example
Chapter 1 430
CMOS Circuit Design Example
Z: Z
The function for this circuit is:
F1 Circuit: F = (X + Y) Z
which is the correct F.
Chapter 1 431
CMOS Circuit Design Example
+V
Replacing the From F 1 •
switch models
• •
with CMOS
•
transistors;
note input •
Z must be • •
used. X •
Z •
Y •
From F 0
•
Chapter 1 432
Technology Parameters
Chapter 1 433
Fan-out
In an integrated circuit:
• The cost of a gate is proportional to the chip area
occupied by the gate
• The gate area is roughly proportional to the number and
size of the transistors and the amount of wiring
connecting them
• Ignoring the wiring area, the gate area is roughly
proportional to the gate input count
• So gate input count is a rough measure of gate cost
If the actual chip layout area occupied by the gate
is known, it is a far more accurate measure
Chapter 1 435
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 436
Logic and Computer Design Fundamentals
Chapter 1 438
Propagation Delay
Chapter 1 439
Propagation Delay (continued)
IN
t (ns)
1.0 ns per division
Chapter 1 441
Delay Models
Chapter 1 442
Delay Model Example
A B:
No Delay
(ND)
a b c d e
Transport
Delay (TD)
Inertial
Delay (ID)
0 2 4 6 8 10 12 14 16 Time (ns)
Chapter 1 444
Circuit Delay
Consider a simple A
2-input multiplexer: 0.4
With function: 0.2
Y
• Y = A for S = 1 0.5
• Y = B for S = 0 S
B 0.4
A
B
S
Y
“Glitch” is due to delay of inverter
Chapter 1 445
Fan-out and Delay
Chapter 1 446
Cost/Performance Tradeoffs
Gate-Level Example:
• NAND gate G with 20 standard loads on its output has a delay of
0.45 ns and has a normalized cost of 2.0
• A buffer H has a normalized cost of 1.5. The NAND gate driving
the buffer with 20 standard loads gives a total delay of 0.33 ns
• In which if the following cases should the buffer be added?
1. The cost of this portion of the circuit cannot be more than 2.5
2. The delay of this portion of the circuit cannot be more than 0.40 ns
3. The delay of this portion of the circuit must be less than 0.30 ns and the
cost less than 3.0
Tradeoffs can also be accomplished much higher in the
design hierarchy
Constraints on cost and performance have a major role in
making tradeoffs
Chapter 1 447
Flip-Flop Timing Parameters
C t wL $ t wL,min
th - hold time
t s th
tw - clock S /R
t
pulse width
p-,min
t p-,max
tpx - propa- Q
• tPHL - High-to-
C t wL $ t wL,min
Low
ts t h
• tPLH - Low-to-
D
High t p-,min
tPLH) Q
ts - setup time
• Master-slave - Equal to the width of the triggering
pulse
• Edge-triggered - Equal to a time interval that is
generally much less than the width of the the triggering
pulse
th - hold time - Often equal to zero
tpx - propagation delay
• Same parameters as for gates except
• Measured from clock edge that triggers the output
change to the output change
Chapter 1 449
Circuit and System Level Timing
Consider a system
comprised of ranks D
C
Q
Q'
D
C
Q
Q'
of flip-flops D Q D Q
C
Q
Q'
D
C
Q
Q'
circuit to flip-flop
C Q' C Q'
Chapter 1 450
Circuit and System Level Timing
Chapter 1 451
Circuit and System Level Timing
C
t pd,FF t pd,COMB ts t slack
tp
C
t pd,FF t pd,COMB t slack ts
Chapter 1 452
Circuit and System Level Timing
Timing Equations
tp = tslack + (tpd,FF + tpd,COMB + ts)
• For t slack greater than or equal to zero,
tp ≥ max (tpd,FF + tpd,COMB + ts)
for all paths from flip-flop output to flip-flop input
Can be calculated more precisely by using tPHL and
tPLH values instead of tpd values, but requires
consideration of inversions on paths
Chapter 1 453
Calculation of Allowable tpd,COMB
Chapter 1 454
Calculation of Allowable tpd,COMB
Chapter 1 455
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 456
Logic and Computer Design Fundamentals
Facts:
• It is most economical to produce an IC in large
volumes
• Many designs required only small volumes of ICs
Need an IC that can be:
• Produced in large volumes
• Handle many designs required in small volumes
A programmable logic part can be:
• made in large volumes
• programmed to implement large numbers of different
low-volume designs
Chapter 1 459
Programmable Logic - More Advantages
Chapter 1 460
Programming Technologies
Chapter 1 461
Programming Technologies
Chapter 1 462
Technology Characteristics
Chapter 1 463
Programmable Configurations
Chapter 1 465
Read Only Memory
Chapter 1 466
Read Only Memory
Chapter 1 467
Read Only Memory Example
D5 X X
The programmable "OR“ D4 X
Chapter 1 469
Programmable Array Logic Example
AND gates inputs
terms
2 1
F1 = A B
+ C 5
X X
F 2
F2 = A
B C + AC + AB 6
I2 5 B
F3 = X X
F4 = 8
X X
F 3
I3 5 C
X X
10
X X
11 F 4
12
I4
Chapter 1 470
Programmable Logic Array (PLA)
Chapter 1 471
Programmable Logic Array (PLA)
Disadvantages
• Often, the product term count limits the application of a
PLA.
• Two-level multiple-output optimization is required to
reduce the number of product terms in an
implementation, helping to fit it into a PLA.
• Multi-level circuit capability available in PAL not
available in PLA. PLA requires external connections to
do multi-level circuits.
Chapter 1 472
Programmable Logic Array Example
A
What are the equations for F1 and F2?
B Could the PLA implement the
X X 1 X X
AB
X X 2 X
BC X Fuse intact
Fuse blown
X 3
X X
AC
X 4 X
X
AB
X
C C B B A A 0
X
1
3-input, 3-output PLA
F 1
Chapter 1 473
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 474
Logic and Computer Design Fundamentals
Chapter 1 476
Registers
Chapter 1 477
Example: 2-bit Register
0 0 00 01 10 11 0 0
0 1 00 01 10 11 0 1
1 0 00 01 10 11 1 0
1 1 00 01 10 11 1 1
What are the quantities above for an n-bit register?
Chapter 1 478
Register Design Models
Chapter 1 479
Register Storage
Expectations:
• A register can store information for multiple clock cycles
• To “store” or “load” information should be controlled by a signal
Reality:
• A D flip-flop register loads information on every clock cycle
Realizing expectations:
• Use a signal to block the clock to the register,
• Use a signal to control feedback of the output of the register back to its
inputs, or
• Use other SR or JK flip-flops, that for (0,0) applied, store their state
Load is a frequent name for the signal that controls register
storage and loading
• Load = 1: Load the values on the data inputs
• Load = 0: Store the values in the register
Chapter 1 480
Registers with Clock Gating
Clock
Load
Gated Clock to FF
What logic is needed for gating?
What is the problem? Gated Clock = Clock + Load
Chapter 1 481
Registers with Load-Controlled Feedback
A more reliable way to selectively load a register:
• Run the clock continuously, and
• Selectively use a load control to change the register contents.
Example: 2-bit register
with Load Control:
2-to-1 Multiplexers
For Load = 0,
loads register contents
(hold current values)
For Load = 1, A1
Y1
loads input values Load D Q
In0
Clock
Chapter 1 482
Register Transfer Operations
Chapter 1 483
Register Notation
R 76543210
15 8 7 0 15 0
PC(H) PC(L) R2
Chapter 1 484
Conditional Transfer
R1 R2
where K1 is a control
variable specifying a
conditional execution Clock
of the microoperation.
Clock
K1
Transfer Occurs Here
Chapter 1 485
Microoperations
Logical Groupings:
• Transfer - move data from one register to another
• Arithmetic - perform arithmetic on data in registers
• Logic - manipulate data or use bitwise logical operations
• Shift - shift data in registers
+ Addition Logical OR
– Subtraction Logical AND
* Multiplication Logical Exclusive OR
/ Division
Not
Chapter 1 486
Example Microoperations
Chapter 1 487
Example Microoperations (Continued)
Chapter 1 488
Control Expressions
(subtract).
Chapter 1 489
Arithmetic Microoperations
R0 ¬ R1 + 1 Two's Complement
Chapter 1 490
Logical Microoperations
Symbolic Description
Designation
R0 ¬ R1 Bitwise NOT
Chapter 1 491
Logical Microoperations (continued)
Let R1 = 10101010,
and R2 = 11110000
Then after the operation, R0 becomes:
R0 Operation
01010101 R0 R1
11111010 R0 R1 R2
10100000 R0 R1 R2
01011010 R0 R1 R2
Chapter 1 492
Shift Microoperations
becomes: R1 Operation
10010010 R1 ¬ sl R2
01100100 R1 ¬ sr R2
Note: These shifts "zero fill". Sometimes a separate flip-flop is used to provide the data
Chapter 1 493
Register Transfer Structures
Chapter 1 494
Multiplexer-Based Transfers
K
R2 2
K
1
Load
n S
0 n
MUX R0
n
Load 1
R1
Chapter 1 495
Shift Registers
Shift Registers move data laterally within the register toward its
MSB or LSB position
In the simplest case, the shift register is simply a set of
D flip-flops connected in a row like this:
In A B C Out
DQ DQ DQ DQ
CP
Data input, In, is called a serial input or the shift right input.
Data output, Out, is often called the serial output.
The vector (A, B, C, Out) is called the parallel output.
Chapter 1 496
Shift Registers (continued)
Chapter 1 497
Parallel Load Shift Registers
By adding a mux DA DB
shifted or loaded
If SHIFT is low, SHIFT
A and B are CP
Chapter 1 498
Shift Registers with Additional Functions
Chapter 1 499
Terms of Use
Chapter 1 500
Logic and Computer Design Fundamentals
Chapter 1 502
Counters
Chapter 1 503
Ripple Counter
of A, A complements
• The clock input for flip- D B
causing B to
B
complement
0 1 2 3 0 1
Chapter 1 504
Ripple Counter (continued)
The corresponding B
Chapter 1 506
Ripple Counter (continued)
significant bit. B
Chapter 1 507
Synchronous Counters
A3 S3 D3 Q3
A2 S2 D2 Q2
A1 S1 D1 Q1
A0 S0 D0 Q0
Clock
Chapter 1 508
Synchronous Counters (continued)
Carry Out
• Added as part of incrementer D Q3
• Connect to Count Enable of C
EN
Carry chain
• series of AND gates through which the Q1
carry “ripples” C1
• Yields long path delays
• Called serial gating
Q2
Replace AND carry chain with ANDs => C2
in parallel
• Reduces path delays Q3
• Called parallel gating
CTR 4
C3
• Like carry lookahead EN Q0
• Lookahead can be used on COs Q1
Q2
and ENs to prevent long paths in Q3
large counters CO CO
Chapter 1 510
Other Counters
Chapter 1 511
Counter with Parallel Load
D 0 D Q 0
and Count = 1
The resulting function table:
D 2 D Q 2
1 X Load D C
Carry
Output CO
Clock
Chapter 1 512
Design Example: Synchronous BCD
0 0 1 0 0 0 1 1
0 0 1 1 0 1 0 0
0 1 0 0 0 1 0 1
0 1 0 1 0 1 1 0
0 1 1 0 0 1 1 1
0 1 1 1 1 0 0 0
1 0 0 0 1 0 0 1
1 0 0 1 0 0 0 0
Chapter 1 513
Synchronous BCD (continued)
Chapter 1 514
Synchronous BCD (continued)
Find the actual values of the six next states for the don’t
care combinations from the equations
Find the overall state diagram to assess behavior for the
don’t care states (states in decimal)
0
Present State Next State
9 1
Q8 Q4 Q2 Q1 Q8 Q4 Q2 Q1 14
1 0 1 0 1 0 1 1
8 2
1 0 1 1 0 1 1 0 15
12
1 1 0 0 1 1 0 1
1 1 0 1 0 1 0 0 7 11 13 3
1 1 1 0 1 1 1 1
6 10
4
1 1 1 1 0 0 1 0
5
Chapter 1 515
Synchronous BCD (continued)
Chapter 1 516
Counting Modulo N
Chapter 1 517
Counting Modulo 7: Detect 7 and
Asynchronously Clear
7 counter. D2 Q2
Chapter 1 518
Counting Modulo 7: Synchronously Load on
Terminal Count of 6
Modulo 7 counter 0 D0 Q0
Reset CLEAR
load in "zero". This gives
a count of 0, 1, 2, 3, 4, 5, 6,
0, 1, 2, 3, 4, 5, 6, 0, ...
Using don’t cares for states
above 0110, detection of 6 can be done with
Load = Q4 Q2
Chapter 1 519
Counting Modulo 6: Synchronously Preset 9 on
Reset and Load 9 on Terminal Count 14
Modulo 6 counter. 0 D1 Q1
This gives a count of 9, 10, 11, 12, 13, 14, 9, 10, 11, 12,
13, 14, 9, …
If the terminal count is 15 detection is usually built in as
Carry Out (CO)
Chapter 1 520
Register Cell Design
Chapter 1 521
Register Cell Specifications
A register
Data inputs to the register
Control input combinations to the register
• Example 1: Not encoded
Control inputs: Load, Shift, Add
At most, one of Load, Shift, Add is 1 for any clock cycle
(0,0,0), (1,0,0), (0,1,0), (0,0,1)
• Example 2: Encoded
Control inputs: S1, S0
All possible binary combinations on S1, S0
(0,0), (0,1), (1,0), (1,1)
Chapter 1 522
Register Cell Specifications
Chapter 1 523
Multiplexer Approach
Dedicated 4
logic 0 Encoder
. ...
.
. Sm S0 Load
. .
Dedicated 4 . .
logic k 2 1 . . MUX
k2 1 4
4 R0
k
. .
. Registers or . .
. . .
. shared logic 4
n2 1
Chapter 1 524
Multiplexer Approach
Dedicated 4
logic 0 Encoder
. ...
.
. Sm S0 Load
. .
Dedicated 4 . .
logic k 2 1 . . MUX
k2 1 4
4 R0
k
. .
. Registers or . .
. . .
. shared logic 4
n2 1
Chapter 1 525
Example 1: Register Cell Design
Chapter 1 526
Example 1: Register Cell Design (continued)
Load Control
Load = CX + CY
Since all control combinations appear as if
encoded (0,0), (0,1), (1,0) can use multiplexer
without encoder:
S1 = CX
S0 = CY
D0 = Ai Hold A
D1 = Ai ← Bi + Ai CY = 1
D2 = Ai ← Bi v Ai CX = 1
Note that the decoder part of the 3-input
multiplexer can be shared between bits if desired
Chapter 1 527
Sequential Circuit Design Approach
Chapter 1 528
Example 1 Again
State Table:
Hold Ai v Bi Ai + Bi
CX = 0 CX = 1 CX = 1 CY = 1 CY = 1
Ai CY = 0 Bi = 0 Bi = 1 Bi = 0 Bi = 1
0 0 0 1 0 1
1 1 1 1 1 0
• Four variables give a total of 16 state table entries
• By using:
Combinations of variable names and values
Don’t care conditions (for CX = CY = 1)
only 8 entries are required to represent the 16 entries
Chapter 1 529
Example 1 Again (continued)
0 0 1 1
0 1 0 1
CY
X X X X
CX
0 1 1 1
Bi
Chapter 1 530
Example 1 Again (continued)
Chapter 1 532
Dedicated MUX-Based Transfers
Multiplexer connected
S0 L0
MUX
n
Load
simultaneous transfers n
0
S
MUX
n
Load
structure.
S2 L2
n S n
Load
0
n MUX
1 R2
Chapter 1 533
Multiplexer Bus
Load
R0
L1
Characterize the n
0
S1 S0
simultaneous transfers n
1
MUX
n n
Load
structure.
Characterize the cost L2
savings compared to n
Load
dedicated multiplexers R2
Chapter 1 534
Three-State Bus
Characterize the
simultaneous transfers n
Load
n R2
E2
Chapter 1 535
Serial Transfers and Microoperations
Serial Transfers
• Used for “narrow” transfer paths
• Example 1: Telephone or cable line
Parallel-to-Serial conversion at source
Serial-to-Parallel conversion at destination
• Example 2: Initialization and Capture of the contents of
many flip-flops for test purposes
Add shift function to all flip-flops and form large shift register
Use shifting for simultaneous Initialization and Capture operations
Serial microoperations
• Example 1: Addition
• Example 2: Error-Correction for CDs
Chapter 1 536
Serial Microoperations
By using two shift registers for operands, a full adder, and a flip
flop (for the carry), we can add two numbers serially, starting at
the least significant bit.
Serial addition is a low cost way to add large numbers of
operands, since a “tree” of full adder cells can be made to any
depth, and each new level doubles the number of operands.
Other operations can be performed serially as well, such as
parity generation/checking or more complex error-check codes.
Shifting a binary number left is equivalent to multiplying by 2.
Shifting a binary number right is equivalent to dividing by 2.
Chapter 1 537
Serial Adder
and B(3:0). In A
Parallel Load
Sum
Cout
Parallel Load
Q D
CP
Chapter 1 538
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 539
Logic and Computer Design Fundamentals
Chapter 1 541
Introduction to Register Transfer Systems
Chapter 1 543
Register Transfer System Design Procedure
Chapter 1 544
Design Example – DASHWATCH - Specs
Chapter 1 545
DASHWATCH Inputs, Outputs, and Registers
TA BLE 7-15
Inputs, Outputs, and Registers of the D ashWatch
Chapter 1 546
DASHWATCH State Machine Diagram with
Register Transfer Outputs
R ESE T
S1 SD (9999) BCD
STA RT
CSS?STA RT STO P
CSS?STA RT S4 D IS = TM
CSS
S5
TM > SD TM , SD
STA RT
S7 S6 SD TM
STA RT D IS 5 SD
Chapter 1 547
State Machine Diagram Design
Chapter 1 548
DASHWATCH Output Control/Status Table
TA BLE 7-16
D atapath Output A ctions and Status Generation with Control and Status Signals
Control or
Status
Action or Status Signals Meaning for Values 1 and 0
D IS = TM DS 0: Select TM for D IS
D IS = SD 1: Select SD for D IS
Chapter 1 549
Determination of Internal Control/Status
Signals
TM – Timer
• Reset to 0000: RSTM
• Enable to Count Up: ENTM
SD – Shortest Dash
• Load SD: LSR = 1;
• Select input 9999: UPDATE = 0
• Select input TM: UPDATE = 1
DIS – Display (B1, B0, DP, B– 1, B– 2)
• Select input TM: DS = 0
• Select input SD: DS = 1
Compare TM and SD (Status)
• TM < SD: ALTB = 1
• TM ³ SD: ALTB = 0
Chapter 1 550
DASHWATCH Datapath
TM
C0 E NTM
4-Digit BCD Counter
R STM SR ST
Chapter 1 552
DASHWATCH – Datapath Development –
Display Logic
Chapter 1 553
DASHWATCH – SMD with Control Signal
Outputs Replacing Register Transfers
S1 LSR
R E SE T
STA RT S2 R STM
STA RT
STO P S3 E NTM
CSS?STA RT STO P
CSS?STA RT S4
CSS
S5
A LTB A LTB
STA RT S7 S6 U P DA TE ,LSR
STA RT
DS
(b) Chapter 1 554
DASHWATCH – FF Input Equations
D S2 S2( t 1) S1 S2 ST A R T S4 CSS ST A R T S7 ST A R T
D S3 S3( t 1) S2 ST A R T S3 ST O P
D S4 S4( t 1) S3 ST O P S4 CSS ST A R T
D S5 S5( t 1) S4 CSS
D S6 S5 A L T B
D S7 S7( t 1) S5 A L T
Chapter 1 555
DASHWATCH – Output Equations
L SR = S1 + S6
R ST M = S2
E N T M = S3
UPDAT E = S6
DS =
Chapter 1 556
Microprogrammed Control
Chapter 1 557
Microprogrammed Control (continued)
Control
inputs Status signals from datapath
Next-address
generator
Sequencer
Control address
register
Control address
Address
Control
memory
(R OM)
Data
Microinstruction
Chapter 1 559
Logic and Computer Design Fundamentals
Memory definitions
Random Access Memory (RAM)
Static RAM (SRAM) integrated circuits
• Cells and slices
• Cell arrays and coincident selection
Arrays of SRAM integrated circuits
Dynamic RAM (DRAM) integrated circuits
DRAM Types
• Synchronous (SDRAM)
• Double-Data Rate (DDR SRAM)
• RAMBUS DRAM (RDRAM)
Arrays of DRAM integrated circuits
Chapter 1 561
Memory Definitions
Chapter 1 562
Memory Definitions (Continued)
Typical data elements are:
• bit ─ a single binary digit
• byte ─ a collection of eight bits accessed together
• word ─ a collection of binary bits whose size is a
typical unit of access for the memory. It is typically a
power of two multiple of bytes (e.g., 1 byte, 2 bytes, 4
bytes, 8 bytes, etc.)
Memory Data ─ a bit or a collection of bits to be
stored into or accessed from memory cells.
Memory Operations ─ operations on memory data
supported by the memory unit. Typically, read
and write operations over some data element (bit,
byte, word, etc.).
Chapter 1 563
Memory Organization
Chapter 1 564
Memory Block Diagram
shown here: n
Chapter 1 565
Memory Organization Example
Example memory
contents: Memory Address Memory
0 to 7. 100 4 10111001
• 23 = 8 words of 8-bit 1
101
10
5
6
10000110
00110011
data 111 7 11001100
Chapter 1 566
Basic Memory Operations
20 ns
Clock T1 T2 T3 T4 T1
Memory
enable
Read/
Write
65 ns
Read cycle
Chapter 1 569
Memory Operation Timing
Write timing:
20 ns
Clock T1 T2 T3 T4 T1
Memory
enable
Read/
Write
Data
input Data valid
75 ns
• Address must be established at least a specified time before 1-0 and held for
at least a specified time after 0-1 to avoid disturbing stored contents of other
addresses
• Data must be established at least a specified time before 0-1 and held for at
least a specified time after 0-1 to write correctly
Chapter 1 570
RAM Integrated Circuits
Chapter 1 571
Static RAM Cell
• SR Latch
• Select input for
control B C
Inputs B and B
• Dual Rail Data B
R Q
C
Chapter 1 572
Static RAM Bit Slice
words
Word
select
0
B C
X
C Word
• Control Lines: B R Q
R A M cell
select
0
R A M cell
• Data Lines: R Q
RA M cell
R ead/Write
logic
Data in D ata in
Q
Data out D ata in
S
R ead/
Write
D ata out
Bit
select
R Q
(b) Symbol
Write logic
R ead logic D ata out
R ead/ Bit
Write select
(a) Logic diagram
Chapter 1 573
2n-Word 1-Bit RAM IC
3
Decoder 0
Word select
A A
A A 2 3
we need:
2 2 2
A A 1 5
• Decoder decodes 1 1 2
6 RAM cel l
A A 0 7
0 0 2
11
13
15
Read/Write
Chip select
Chapter 1 575
Cell Arrays and Coincident Selection
(continued)
Row decoder
2-to-4
Decoder 0
1
A 2
3
RAM cell RAM cell RAM cell RAM cell
0 1 2 3
A 20
2
1
Data input
Read/Write
X X X X
1 0
2 2 Enable
A A
1 0
Chip select Chapter 1 576
RAM ICs with > 1 Bit/Word
Chapter 1 577
Making Larger Memories
Data In
Using the CS lines, we De c o de r
A1 D-In
can make larger A0
R/W
memories from smaller D3 CS D-Out
by A2 S0
Data Out
1-Bit memory. A1
A0
R/W
Chapter 1 578
Making Wider Memories
Chapter 1 579
Dynamic RAM (DRAM)
Chapter 1 580
Dynamic RAM (continued)
Select
Stored 1 Stored 0
To Pump
T
B
C
DRAM cell
(b) (c)
(a)
Write 1 Write 0
Select
(d) (e)
B D Q C
Read 1 Read 0
C DRAM cell
model
Chapter 1 581
Dynamic RAM - Bit Slice
drivers B
D Q
C
voltage change on C
select
1
Select D R A M cell
into H or L 2 1
In the electronics, B, C,
D Q
2 1
C D R A M cell
R ead/Write
into non-destructive
Write select
read
(b) Symbol
Write logic
Read logic D ata out
Bit
Read/
select
Write
(a) Logic diagram
Chapter 1 582
Dynamic RAM - Block Diagram
Chapter 1 583
Dynamic RAM Read Timing
20 ns
Clock T1 T2 T3 T4 T1
Row Column
Address
Address Address
RAS
CAS
Output
enable
Read/
Write
Data Hi-Z
Data valid
output
65 ns
Read cycle
Chapter 1 584
DRAM Types
Types to be discussed
• Synchronous DRAM (SDRAM)
• Double Data Rate SDRAM (DDR SDRAM)
• RAMBUS® DRAM (RDRAM)
Justification for effectiveness of these types
• DRAM often used as a part of a memory hierarchy (See details in
chapter 14)
• Reads from DRAM bring data into lower levels of the hierarchy
• Transfers from DRAM involve multiple consecutively addressed
words
• Many words are internally read within the DRAM ICs using a single
row address and captured within the memory
• This read involves a fairly long delay
Chapter 1 585
DRAM Types (continued)
Chapter 1 586
Synchronous DRAM
Chapter 1 587
Double Data Rate Synchronous DRAM
Chapter 1 588
RAMBUS DRAM (RDRAM)
Uses a packet-based bus for interaction between the RDRAM ICs and the
memory bus to the processor
The bus consists of:
• A 3-bit row address bus
• A 5-bit column address bus
• A 16 or 18-bit (for error correction) data bus
The bus is synchronous and transfers on both edges of the clock
Packets are 4-clock cycles long giving 8 transfers per packet representing:
• A 12-bit row address packet
• A 20-bit column address packet
• A 128 or 144-bit data packet
Multiple memory banks are used to permit concurrent memory accesses with
different row addresses
The electronic design is sophisticated permitting very fast clock speeds
Chapter 1 589
Arrays of DRAM Integrated Circuits
Chapter 1 590
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 591
Logic and Computer Design Fundamentals
Part 1 – Datapaths
Chapter 1 593
Introduction
Computer Specification
• Instruction Set Architecture (ISA) - the
specification of a computer's appearance to a
programmer at its lowest level
• Computer Architecture - a high-level
description of the hardware implementing the
computer derived from the ISA
• The architecture usually includes additional
specifications such as speed, cost, and
reliability.
Chapter 1 594
Introduction (continued)
Chapter 1 595
Datapaths
Chapter 1 596
Datapath Example
Load enable A select B select
registers Load
R0 2 2
Two mux-based n n
register selectors
Load
R1
0
n 1
Register destination n
0
2
3
MU X
decoder Load
R2
1
2
MU X
constant input 0 1 2 3
Load R3
n n
n
Buses A and B with external
Register file
D ecoder
D address A data B data
2 Constant in n n
address and data outputs D estination select n 1 0
MB select
G H
0 1
V, C, N, Z MF select MU X F
F
Function unit
D ata in
n n
MD select 0 1
MU X D
n Bus D
Chapter 1 597
Datapath Example: Performing a
Microoperation
Load enable A select B select
Microoperation: R0 ← R1 + R2 Write
D data n
A address B address
Load R3
B n n
Apply 0 to MF select and 0 to MD
0 1 2 3
D ecoder
n
Register file
MB select n 1
2
MU X
n
3
Provide an address and data for a Load
0
1
MU X
R2 2
memory or output write n n
3
D estination select n 1 0
for a memory or output read MB select
Bus A
MU X B
n A ddress
out
microoperation – apply 1 to MD A B
Bus B n
n
D ata
out
select
G select H select
4 A B 2 B
S2:0 || Cin S
V A rithmetic/logic 0 IR Shifter IL 0
MD select 0 1
MU X D
n Bus D
Chapter 1 599
Arithmetic Logic Unit (ALU)
Chapter 1 600
Arithmetic Circuit Design (continued)
n
A X
n n-bit n
B parallel G X Y C in
add
B input n
Y
S0 logic
S1
C out
Chapter 1 601
Arithmetic Circuit Design (continued)
S1 S0 Y Cin =0 Cin =1
Chapter 1 602
Logic Circuit
The custom circuit has interchanged the (S1,S0) codes for XOR and NOT
compared to the MUX circuit. To preserve compatibility with the text, we
use the MUX solution.
Next, use the arithmetic circuit, the logic circuit, and a 2-way multiplexer to
form the ALU. See the next slide for the bit slice diagram.
The input connections to the arithmetic circuit and logic circuit have been
been assigned to prepare for seamless addition of the shifter, keeping the
selection codes for the combined ALU and the shifter at 4 bits:
• Carry-in Ci and Carry-out Ci+1 go between bits
• Ai and Bi are connected to both units
• A new signal S2 performs the arithmetic/logic selection
• The select signal entering the LSB of the arithmetic circuit, Cin, is
connected to the least significant selection input for the logic circuit, S0.
Chapter 1 604
Arithmetic Logic Unit (ALU) (continued)
C0 5
Ci Ci Ci 1 1
Ai Ai
O ne stage of
Bi Bi arithmetic
circuit 2-to-1
S0 S0
0 MU X
S1 S1
Gi
1
Ai S
B i O ne stage of
C in S logic circuit
0
S1
S2
The next most significant select signals, S0 for the arithmetic circuit and S1
for the logic circuit, are wired together, completing the two select signals
for the logic circuit.
The remaining S1 completes the three select signals for the arithmetic
circuit.
Chapter 1 605
Combinational Shifter Parameters
Chapter 1 606
4-Bit Basic Left/Right Shifter
B 3 B 2 B 1 B 0
Serial
output L
Serial
output R
IR IL
0 1 2 M 0 1 2 M 0 1 2 M 0 1 2 M
S U S U S U S U
X X X X
2
S
Serial Inputs:
H 3 H 2 H 1 H 0
Chapter 1 607
Barrel Shifter
D3 D2 D1 D0
S0
S1
3 2 1 0 S1 S0 3 2 1 0 S1 S0 3 2 1 0 S1 S0 3 2 1 0 S1 S0
M M M M
U U U U
X X X X
A rotate is a shift
Y
in which theY bits shifted outY are inserted into
3 2 Y
the positions 1 0
vacated
The circuit rotates its contents left from 0 to 3 positions depending on S:
S = 00 position unchanged S = 10 rotate left by 2 positions
S = 01 rotate left by 1 positions S = 11 rotate left by 3 positions
See Table 10-3 in text for details
Chapter 1 608
Barrel Shifter (continued)
Chapter 1 609
Datapath Representation
in slide 8 m
D address
m
Constant in
decoder, and enable hardware for n
n n
file Bus A n
Address out
The ALU, shifter, Mux F and Bus B n
Data out
0 1
MD select
MUX D
Chapter 1 610
Datapath Representation (continued)
In the register file: n
D address
B address
m
and B data
A data B data
• Input data to the registers becomes Constant in
n n
D data n
MUX B
0
Z
F
n
n Data in
0 1
MD select
MUX D
Chapter 1 611
Definition of Function Unit Select (FS) Codes
G Select, H Select, and MF
in T of FS Codes
MF G H
FS(3:0) Select Select(3:0) Select(3:0) Micr ooperation
0010 0 0010 XX F ¬A + B
Equations:
0011 0 0011 XX F ¬A + B + 1
MFS = F3 F2
0100 0 0100 XX F ¬A + B
0111 0 0111 XX F ¬ A
HSi = Fi
1000 0 1 X 00 XX F ¬ A ÙB
1001 0 1 X 01 XX F ¬ A ÚB
1010 0 1 X 10 XX F ¬ A ÅB
1011 0 1 X 11 XX F ¬ A
1100 1 XXXX 00 F ¬ B
1101 1 XXXX 01 F ¬ sr B
1110 1 XXXX 10 F ¬ sl B
Chapter 1 612
The Control Word
Chapter 1 613
The Control Word Fields
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
M M R
DA AA BA FS
B D W
• DA – D Address
• AA – A Address
• BA – B Address
• MB – Mux B
• FS – Function Select
• MD – Mux D
• RW – Register Write
The connections to datapath are shown in the next slide
Chapter 1 614
Control Word Block Diagram
n
R W 0 Write D data
15
D A 14 D address
13 8 x n
Register file
12 9
AA 11 A address B address 8 BA
10 7
A data B data
n n
n
Constant in
1 0
MB 6 MUX B
Bus A n
Address out
Bus B n
Data out
A B
V
5
C Function
4
FS
unit
N 3
Z 2
n
n
Data in
0 1
MD 1 MUX D
Bus D
Chapter 1 615
Control Word Encoding
Encoding of Control W
D A, AA, B A MB FS MD R W
Function Code Function Code Function Code Function Code Function Code
R 2 010 F ¬A + B 0010
R 3 011 F ¬A + B + 1 0011
R 4 100 F ¬A + B 0100
R 5 101 F ¬A + B + 1 0101
R 6 110 F ¬A - 1 0110
R 7 111 F ¬A 0111
F ¬A Ù B 1000
F ¬A Ú B 1001
F ¬A Å B 1010
F ¬ 1011
A
F ¬B 1100
F ¬ sr B 1101
F ¬ sl B 1110
Chapter 1 616
Microoperations for the Datapath - Symbolic
Representation
Micr o-
op eratio n D A A A B A M B F S M D R W
Data out ¬ R 3 —— R 3 R eg i s t e r — — N o Wr it e
Chapter 1 617
Microoperations for the Datapath -
Binary Representation
m Microoperations from T a Binary C o o
Micr o-
o p eratio n D A A A B A M B F S M D R W
R 4 ¬ s l R6 10 0 XX X 110 0 111 0 0 1
Chapter 1 618
Datapath Simulation
Clock 1 2 3 4 5 6 7 8
DA 1 4 7 1 0 4 5
AA 2 0 7 0
BA 3 6 0 3 0
FS 5 14 1 2 0 10
Constant_in X 2 X
MB
A ddress_out 2 0 7 0
D ata_out 3 6 0 2 3 0
D ata_in 18 18
MD
RW
reg0 0
reg1 1 255 2
reg2 2
reg3 3
reg4 4 12 18
reg5 5 0
reg6 6
reg7 7 8
Status_bits 2 0 0 1 X
Chapter 1 619
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 620
Logic and Computer Design Fundamentals
Part 1 – Datapaths
Part 2 – A Simple Computer
• Instruction Set Architecture (ISA)
• Single-Cycle Hardwired Control
PC Function
Instruction Decoder
Example Instruction Execution
Part 3 – Multiple Cycle Hardwired
Control
Chapter 1 622
Instruction Set Architecture (ISA) for Simple
Computer (SC)
A programmable system uses a sequence of instructions to
control its operation
An typical instruction specifies:
• Operation to be performed
• Operands to use, and
• Where to place the result, or
• Which instruction to execute next
Instructions are stored in RAM or ROM as a program
The addresses for instructions in a computer are provided
by a program counter (PC) that can
• Count up
• Load a new address based on an instruction and, optionally, status
information
Chapter 1 623
Instruction Set Architecture (ISA) (continued)
Chapter 1 624
ISA: Storage Resources
instruction implementation 8 x 16
Chapter 1 625
ISA: Instruction Format
Chapter 1 626
ISA: Instruction Format
15 9 8 6 5 3 2 0
(a) Register
15 9 8 6 5 3 2 0
(b) Immediate
15 9 8 6 5 3 2 0
The three formats are: Register, Immediate, and Jump and Branch
All formats contain an Opcode field in bits 9 through 15.
The Opcode specifies the operation to be performed
More details on each format are provided on the next three slides
Chapter 1 627
ISA: Instruction Format (continued)
15 9 8 6 5 3 2 0
(a) Register
This format supports instructions represented by:
• R1 ← R2 + R3
• R1 ← sl R2
There are three 3-bit register fields:
• DR - specifies destination register (R1 in the examples)
• SA - specifies the A source register (R2 in the first example)
• SB - specifies the B source register (R3 in the first example and
R2 in the second example)
Why is R2 in the second example SB instead of SA?
• The source for the shifter in our datapath to be used in
implementation is Bus B rather than Bus A
Chapter 1 628
ISA: Instruction Format (continued)
15 9 8 6 5 3 2 0
(b) Immediate
This format supports instructions described by:
• R1 ← R2 + 3
The B Source Register field is replaced by an Operand
field OP which specifies a constant.
The Operand:
• 3-bit constant
• Values from 0 to 7
The constant:
• Zero-fill (on the left of) the Operand to form 16-bit constant
• 16-bit representation for values 0 through 7
Chapter 1 629
ISA: Instruction Format (continued)
15 9 8 6 5 3 2 0
Mne- Status
Instruction Opcode monic Format Description Bits
* For all of these instructions, PC ← PC + 1 is also executed to prepare for the next cycle
Chapter 1 632
ISA:Example Instructions and Data in
Memory
Memory Repr esentation of Instruc t ions and Data
Im mediate)
on Z e ro ) PC ¬ PC - 20
Data = 80.
Chapter 1 633
Single-Cycle Hardwired Control
Chapter 1 634
IR (8:6) || IR (2:0)
V E xtend
C Branch Jump A ddress
PC
N Control
Z
P J B A ddress
LBC Instruction
memory RW D
Instruction DA R egister
AA file BA
A B
Z ero fill
IR (2:0) Constant
in
Instruction decoder
1 0
MB
MU X B
A ddress out
Bus A Bus B
D ata out
MW
D B A M F M R M P J B
A A A B S D W W L B C A B D ata in A ddress
FS
CO NTRO L
V D ata
C Function memory
unit
N
D ata out
Z
F
D ata in
0 1
MD MU X D
Bus D
DATA PATH
Chapter 1 635
The Control Unit
Chapter 1 636
PC Function
Chapter 1 637
PC Function (continued)
Chapter 1 638
Instruction Decoder
Chapter 1 639
Instruction Decoder (continued)
Chapter 1 640
Instruction Decoder (continued)
registers
Memory read 0 0 1 X 0 1 1 0 0 X X
Memory write 0 1 0 X 0 X 0 1 0 X X
Unconditional J ump 1 1 1 X X X 0 0 1 1 X
Chapter 1 641
Instruction Decoder (continued)
The types are based on the blocks controlled and the seven signals to be
generated; types can be divided into two groups:
• Datapath and Memory Control (First 4 types)
• PC Control (Last 3 types)
In Datapath and Memory Control blocks controlled are considered:
• Mux B (1st and 4th types)
• Memory and Mux D (2nd and 3rd types)
• By assigning codes with no or only one 1 for these, implementation of MB,
MD, RW and MW are simplified.
In Control Unit more of a bit setting approach was used:
• Bit 15 = Bit 14 = 1 were assigned to generate PL
• Bit 13 values were assigned to generate JB.
• Bit 9 was use as BC which contradicts FS = 0000 needed for branches. To
force FS(6) to 0 for branches, Bit 9 into FS(6) is disabled by PL.
Also, useful bit correlations between values in the two groups were
exploited in assigning the codes.
Chapter 1 642
Instruction Decoder (continued)
The end result by use of the types, careful assignment of
codes, and use of don't cares, yields very simple logic:
This completes the Instruction
Opcode DR SA SB
essential parts of
the single-cycle
simple computer
DA AA BA MB FS MD RW MW PL JB BC
Operation Symb ol ic
co de na m e Fo rm a t D e s c r ip ti on Fu nc ti on MB MD RW MW PL JB BC
Instruction
1 0 0 0 0 1 0
Opcode DR SA SB
1 0010 0 1 0 0 0 0
DA AA BA MB FS MD RW MW PL JB BC
Control word
Chapter 1 645
IR(8:6) || IR(2:0)
Extend
V
C Branch
PC
N Control
Z
Control Inputs and Paths for ADI
P J B Address
L B C
Instruction 1
0 0 0 memory RW D
DA Register
Instruction
file
Increment AA A B BA
PC Zero fill
IR(2:0) Constant
in
Instruction decoder
1 0
MB 1
MUX B
Address out
C
+
Function
Data
memory
unit
N
Data out
Z
F
Data in
0 1
0 MD
MUX D
Bus D
DATAPATH Chapter 1 646
Decoding for LD
Instruction
0 0 1 0 0 0 0
Opcode DR SA SB
0 0000 1 1 0 0 1 0
DA AA BA MB FS MD RW MW PL JB BC
Control word
Chapter 1 647
IR(8:6) || IR(2:0)
Extend
V
C Branch
PC
N Control Control Inputs and Paths for LD
Z
P J B Address
L B C
Instruction 1
0 1 0 memory RW D
DA Register
Instruction
file
Increment AA A B BA
PC Zero fill
IR(2:0) Constant
in
Instruction decoder
1 0
MB 0
MUX B
Address out
V Data
Function
C memory
unit
N
Data out
Z
F
Data in
0 1
1 MD
MUX D
Bus D
DATAPATH Chapter 1 648
Decoding for BRZ
Instruction
11 0 0 0 0 0
Opcode DR SA SB
1 0000 0 0 0 1 0 0
DA AA BA MB FS MD RW MW PL JB BC
Control word
Chapter 1 649
IR(8:6) || IR(2:0)
Extend
V
C Branch
PC
N
Z
Control
Control Inputs and Paths for BRZ
No Write
P J B Address
L B C
Instruction 0
1 0 0 memory RW D
DA Register
Instruction
file
Branch on AA A B BA
Z Zero fill
IR(2:0) Constant
in
Instruction decoder
1 0
MB 1
MUX B
Address out
V Data
Function
C memory
unit
N
Data out
Z
F
Data in
0 1
0 MD
MUX D
Bus D
DATAPATH Chapter 1 650
Terms of Use
Chapter 1 651
Logic and Computer Design Fundamentals
Part 1 – Datapaths
Part 2 – A Simple Computer
Part 3 – Multiple Cycle Hardwired Control
• Single Cycle Computer Issues
• Modifications to Datapath
• Modifications to Control
• Sequential Control Design
Chapter 1 653
Single-Cycle Computer Issues
Chapter 1 654
Multiple-Cycle Computer
Chapter 1 655
E xtend
2
PS PC
D
4 RW
DR R egister 4 DA 16 16
3 R egister
16 SA address
3 file
SB logic AA BA
3 4 A B
IR 4 4 4
IL O pcode D R SA SB A X BX D X
7 3 3 3 Z ero fill
1 0 MB
MU X B
Chapter 1 656
Datapath Modifications
Chapter 1 657
E xtend
New Instruction Path
2
PS PC
D
4 RW
DR DA 16 16
3 Register 4 R egister
16 SA address
3 file
SB logic AA BA
3 4 A B
IR 4 4 4
IL O pcode D R SA SB A X BX D X
Inst. & Data Address
7 3 3 3 Z ero fill
Mux
1 0 MB
MU X B
CO NTRO L DATAPATH
Chapter 1 658
Datapath Modifications (continued)
D
4 RW
DR DA 16 16
3 R egister 4 R egister
16 SA address
3 file
SB logic AA BA
3 4 A B
IR 4 4 4
IL O pcode D R SA SB A X BX D X
Inst. & Data Address
7 3 3 3 Z ero fill
Mux
1 0 MB
MU X B
Chapter 1 660
Control Unit Modifications
Chapter 1 661
E xtend
2
PS PC
Add "hold" operation
D
4 RW
Instruction Register DR DA 16 16
3 R egister 4 R egister
16 SA address
IR 3 file
SB logic AA BA
3 4 A B
IR 4 4 4
IL O pcode D R SA SB A X BX D X
7 3 3 3 Z ero fill
1 0 MB
MU X B
Chapter 1 662
Sequential Control Design
Chapter 1 663
E xtend
2
PS PC
D
4 RW
DR DA 16 16
3 R egister 4 R egister
16 SA address
3 file
SB logic A A BA
3 4 A B
IR 4 4 4
IL O pcode D R SA SB A X BX D X
Control State Register
7 3 3 3 Z ero fill
1 0 MB
MU X B
Chapter 1 664
Control Word
27 24 23 22 21 20 17 16 13 12 9 8 7 4 3 2 1 0
I M M R M M
NS PS DX AX BX FS
L B D W M W
Sequencing Datapath
Datapath part: fields DA, AA, and BA replaced by DX, AX, and
BX, respectively, and field MM added
• If the MSB of a field is 0, e.g., AX = 0XXX, then AA is 0 concatenated
with 3 bits obtained from the SA field in the IR
• If the MSB of a field is 1, e. g. AX = 1011, then AA = 1011
Sequencing part:
• IL controls the loading of the IR
• PS controls the operations of the PC
• NS gives the next state of the Control State register
NS is 4 bits, the length of the Control State register - 16 states are viewed as
adequate for this design
Chapter 1 665
Encoding for Datapath Control
R 9 R 9 R 9 1001 F ←A + B 0010
R 12 R 12 R 12 1100 F ←A + B + 1 0101
R 13 R 13 R 13 1101 F ←A – 1 0110
R 15 R 15 R 15 1111 F ←A B 1000
^
F ←A v B 1001
F ←A + B 1010
1011
F ←A
F ←B 1100
F ← sr B 1101
F ← sl B 1110
Unused 1111
Chapter 1 666
Encoding for Sequencing Control
NS PS IL
Chapter 1 667
SMDs for Sequential Control
Chapter 1 668
ISA: Instruction Specifications (for reference only)
St a t u s
Chapter 1 669
SMD for Two-Cycle Instructions -
Part 1
PC PC + 1
S
INF IR M[PC]
O pcode =
R [D R ] R [SA ] 0000000
R [D R ] R [SA ] + 1 0000001
R [D R ] R [SA ] + R [SB] 0000010
R [D R ] R [SA ] + R [SB] +1 0000101
R [D R ] R [SA ] 2 1 0000110
R [D R ] R [SA ] R [SB] 0001000
R [D R ] R [SA ] R [SB] 0001001
E X0
R [D R ] R [SA ] % R [SB] 0001010
R [D R ] R [SA ] 0001011
Chapter 1 670
ISA: Instruction Specifications (for reference only)
St a t u s
Chapter 1 671
SMD for 2-Cycle
Instructions – Part 2
Instruction Fetch
Portion Duplicated
From Part 1
Chapter 1 672
State Table for 2-Cycle Instructions
In puts O utp uts
N e xt
State
st ate I P M M R M M
O pcode V C N Z L S D X A X B X B F S D W M W C o m m e nts
IN F X X XX X X X XXXX EX0 1 00 X XX X XX X X X X XX X X X XX X 0 1 0 I R← M [ PC ]
Chapter 1 673
SMD for Right Shift and Left Shift Multiple
From INF
R8 R [SA ]
PC PC 1 1
Z · ((O pcode = 0001101) + (O pcode = 0001110))
E X0 E X1
Z · ((O pcode = 0001101)
+ (O pcode = 0001110))
0 ))
Z · ((O pcode = 0001101) PC PC 1 1 0 0 0111 R9 zf O P
e =
co d
+ (O pcode = 0001110)) (O p
0 1) +
= 0 0011
e
co d
· ( (O p
Z
E X2 E X3
O pcode = 0001101 R 8 sr R 8
O pcode = 0001110 R 8 sl R 8
Z · ((O pcode = 0001101)
+ (O pcode = 0001110)) R9 R92 1
E X4
R [D R ] R 8,
(O pcode = 0001101) + (O pcode = 0001110) PC PC 1 1
To INF
Chapter 1 674
State Table For Right and Left Shift Multiple
TA BLE 9-15
State Table for Illustration of Instructions Having Three or Mo re Cycles
Inputs Outputs
Next
State Comments
state I M
Opcode VCNZ L PS DX AX BX MB FS MD RW MM W
Chapter 1 675
Terms of Use
All (or portions) of this material © 2008 by Pearson
Education, Inc.
Permission is given to incorporate this material or
adaptations thereof into classroom presentations and
handouts to instructors in courses adopting the latest
edition of Logic and Computer Design Fundamentals as
the course textbook.
These materials or adaptations thereof are not to be sold or
otherwise offered for consideration.
This Terms of Use slide or page is to be included within
the original materials or any adaptations thereof.
Chapter 1 676