DIGITAL DESIGN Edited by Chu Yu

Digital Circuit Design

 Primary Logic Gates

Page: 1
 DIGITAL DESIGN Edited by Chu Yu

 Boolean Algebra
 Commutative law of addition and multiplier:
A+B = B+A
AB = BA
 Associative law of addition and multiplier:
A + (B + C) = (A + B) + C
A(BC) = (AB)C
 Distributive law:
A(B + C) = AB + AC
(A + B)(C + D) = AC + AD + BC + BD

Page: 2
DIGITAL DESIGN Edited by Chu Yu

Page: 3
 DIGITAL DESIGN Edited by Chu Yu

 Sum of Product (SOP)

 F(A, B, C) = A’B C’ + AB’C + ABC = (2, 5, 7)

 Product of Sum (POS)

 F(A, B, C) = (A’+B+ C’)(A+B’+C)(A+B+C) = (5, 2, 0)

 Exchange Between SOP and POS

 (0, 2, 6, 7) = (1, 3, 4, 5)

 Standard Term
 The term contains all the input variable.
 EX: F(A, B, C) = A’BC + ABC + AC
to be not a standard term

Page: 4
 DIGITAL DESIGN Edited by Chu Yu

 Dual Theorem
 F D(X1, X2, … Xn, 0, 1, +, •)
= F(X1, X2, … Xn, 1, 0, •, +)
EX:
F = AB + AB ＝ (A+B)•(A+B) = AB + AB

 DeMorgan’s Theorem
 F ‘(X1, X2, … Xn, 0, 1, +, •)
= F(X1’, X2’, … Xn’, 1, 0, •, +)
Ex:
A+B = AB , ABC = A+B+C

Page: 5
 DIGITAL DESIGN Edited by Chu Yu

 Shannon Theorem
 F (xn-1, xn-2, … ,x0) = xn-1F(1, xn-2, … ,x0) + x’n-1F(0, xn-2, … ,x0)
 F(xn-1, xn-2, … ,x0) = [xn-1+F(0, xn-2, … ,x0)] • [x’n-1+F(1, xn-2, … ,x0) ]

 F(xn-1, xn-2, … ,x0) = xn-1 xn-2 … x0F(1, 1, … ,1)

+ xn-1 xn-2 … x’0F(1, 1, … ,0)
+ … + x’n-1 x’n-2 … x’0F(0, 0, … ,0)
2 n 1
= a m
k 0
k k

where a0 = F(0,0, … ,0) , a1 = F(0,0, … ,0,1) , … ,

n-2 n-1
a2 = F(1, 1, … ,1,0) , a2 = F(1, 1, … ,1)
and
m0 = x’n-1 x’n-2 … x’0 , m1 = x’n-1 x’n-2 … x0 , … ,
n-2 n-1
m2 = xn-1 xn-2 … x’0 , m2 = xn-1 xn-2 … x0

Page: 6
 DIGITAL DESIGN Edited by Chu Yu

 Variable-Entered Map
xy
z 00 01 10 11
0 B’ 0 0 A

1 1 B  1

 set all external variables to 0

xy
z 00 01 10 11
0 0 0 0 0

1 1 0  1 y’z

Page: 7
DIGITAL DESIGN Edited by Chu Yu

 set one variable to 1 only, and change “1” in the original map to 
xy
z 00 01 10 11
0 1 0 0 0

1  0  

B’x’y’
 repeat step 2, until all variables are applied
xy xy
z 00 01 10 11 z 00 01 10 11
0 0 0 0 0 0 0 0 0 1

1  1   1  0  

Bz Axy’

F = y’z + Axy’ + Bz + B’x’y’

Page: 8
DIGITAL DESIGN Edited by Chu Yu

Page: 9
 DIGITAL DESIGN Edited by Chu Yu

列表法 (The Tabulation Method)

F(w, x, y, z)
= w’x’y’ + x’z’ + wy

1. Group binary representation of the minterms according to the number of 1’s contained.
2. The minterms of one section are compared with those of the next section down only.
Any two minterms that differ from each other by only one variable can be combined,
and the unmatched variable removed.
3. Repeat step 2, until all terms are unchecked.
4. The uncheck terms form the prime implicants.
Page: 10
DIGITAL DESIGN Edited by Chu Yu

Page: 11
 DIGITAL DESIGN Edited by Chu Yu

Selection of Prime Implicants

1 4 6 7 8 9 10 11 15 yz
 x’y’z 1, 9 x x wx 00 01 11 10
 w’xz’ 4, 6 x x 00 1
w’xy 6, 7 x x 01 1 1 1
 xyz 7, 15 x x 11 1
wyz 11, 15 x x
10 1 1 1 1
 wx’ 8, 9, 10, 11 x x x x
      

F(w, x, y, z) = x’y’z + w’xz’ + wx’ + xyz

 Each prime implicant is represented in a row and each minterm in a column (marked
by one ‘X’ symbol)
 Columns containing only a single X mark a check () on the corresponding position of
the last row and the X’s corresponding row (essential prime implicant).
 Next check each column whose minterm is covered by the selected essential prime
implicants. (marked by ‘*’)
 A minimum set of prime implicants is chosen that covers all the minterms in the
function.
Page: 12
DIGITAL DESIGN Edited by Chu Yu

Page: 13
DIGITAL DESIGN Edited by Chu Yu

Page: 14
DIGITAL DESIGN Edited by Chu Yu

 PLA

Page: 15
 DIGITAL DESIGN Edited by Chu Yu

 Example
 Design a circuit to implement a function X 2 + 3X + 1, where
variable X is a 2-bit input data.

Sol: p0 = x0 + 0 + x0 + 1 = 1
x1 x0
p1 = x0 + x0 + x1 = x1
x1 x0
p2 = x0 + x1+ x1x0 + x1
x1x0 x0 = x0 + x1x0
x1 x1x0 p3 = x1 + “p2’s carry”
p4 = p3’s carry
x1+x1x0 0 x0  x2
x1 x1x0 x0 x1 1
x1 x0 0 3x
x1 x0
HA HA
1
p3 p2 p1 p0 p4 p3 p2 p1 p0

Page: 16
 DIGITAL DESIGN Edited by Chu Yu

 Static Hazard
 Since the propagation delay (Tpd) for each of gates is different, the
output of the circuit may be occur errors when its input signal is
changed.
 Example: F(x, y, z) = x’y + xz

xz
x’
x’y

x’y+xz

Page: 17
 DIGITAL DESIGN Edited by Chu Yu

 K-Map
yz
x 00 01 11 10
0 1 1
1 1 1

F = x’y + xz + yz

x’
y

x
F
z

y
z

Page: 18
 DIGITAL DESIGN Edited by Chu Yu

 Flip-Flop Characteristic Table

 JK-type FF  RS-type FF

J K Q(t+1) S R Q(t+1)
0 0 Q(t) 0 0 Q(t)
0 1 0 0 1 0
1 0 1 1 0 1
1 1 Q’(t) 1 1 ?

 D-type FF  T-type FF

D Q(t+1) T Q(t+1)
0 0 0 Q(t)
1 1 1 Q’(t)

Page: 19
DIGITAL DESIGN Edited by Chu Yu

 Flip-Flop Stimulus Table

 JK-type FF  RS-type FF

Q(t) Q(t+1) J K Q(t) Q(t+1) S R

0 0 0  0 0 0 
0 1 1  0 1 1 0
1 0  1 1 0 0 1
1 1  0 1 1  0

 D-type FF  T-type FF

Q(t) Q(t+1) D Q(t) Q(t+1) T

0 0 0 0 0 0
0 1 1 0 1 1
1 0 0 1 0 1
1 1 1 1 1 0
Page: 20
 DIGITAL DESIGN Edited by Chu Yu

 D-type Flip-Flop
 Output changes only on the clock edge

D D Q D Q Q
D D
latch latch _ _
C C Q Q

Page: 21
 DIGITAL DESIGN Edited by Chu Yu

 Exchange of FF’s Each Other

 Use of D-type FF to implement T-type FF

Q
T D Q

CK Q
CK Q

 Use of SR- or JK-type FF to implement D-type FF

D S Q Q

R Q Q

D J Q Q

K Q Q

Page: 22
 DIGITAL DESIGN Edited by Chu Yu

 Exchange of FF’s Each Other

 Use of SR-type FF to implement T-type FF

1
3
2 S Q Q
T CK CK
1 Q
3 R Q
2

 Use of JK-type FF to implement T-type FF

T Q
J Q
CK CK
Q
K Q

Page: 23
 DIGITAL DESIGN Edited by Chu Yu

 Asynchronous Ripple Counter

– Mod-6 (method 1)

1 Q0 1 Q1 1 Q2 1 2 3 4 5 0 1 2
J Q J Q J Q CK
CK CK CK CK Q0
1 1 1
reset

reset

reset
K Q K Q K Q Q1

Q2

– Mod-6 (method 2) 1 2 3 4 5 0 1 2
CK

Q0

1 Q0 1 Q1 1 Q2 Q1
J Q J Q J Q Q2
CK
CK CK CK
preset
preset

preset

1 1 1
K Q K Q K Q Mod-M counter
 Evaluate M-1.
 FF’s to be 1 input to
NAND gate, and NAND
connects to FF’s to be 0.

Page: 24
DIGITAL DESIGN Edited by Chu Yu

 Down Ripple Counter

1 Q0 1 Q1 1 Q2
J Q J Q J Q
CK
CK CK CK
1 1 1
reset

reset

reset
K Q K Q K Q

CK

Q0 0 1 0 1 0 1 0 1

Q1 0 1 1 0 0 1 1 0

Q2 0 1 1 1 1 0 0 0

Page: 25
 DIGITAL DESIGN Edited by Chu Yu

 Synchronous Sequential Circuit

 Design of a mod-5 counter
 State Diagram
0 1

2
4
3
 State Transition

PS NS FF’s Input
q2 q1 q0 q2 q1 q0 J2K2 J1K1 J0K0
0 0 0 0 0 1 0 0 1
0 0 1 0 1 0 0 1 1
0 1 0 0 1 1 0 0 1
0 1 1 1 0 0 1 1 1
1 0 0 0 0 0 1 0 0
Page: 26
DIGITAL DESIGN Edited by Chu Yu

 K-Map

J2 K2 J1 K1 J0 K0
q2 q0 q2 q0 q2 q0
q1 0 1 q1 0 1 q1 0 1
00 0 0 00 0 1 00 1 1
01 0 1 01 0 1 01 1 1
11   11   11  
10 1  10 0  10 0 
J2 = q1q0 J1 = q 0 J 0 = q 2’
K2 = 1 K1 = q0 K0 = 1
 Implementation

q0 q1 q2
J0 Q J1 Q J2 Q
CK CK CK
1 1
K0 Q K1 Q K2 Q

CK

Page: 27
 DIGITAL DESIGN Edited by Chu Yu

 Example II:
x 001/1 z

A 0/0 B 0/0 C
1/0 0/0
1/0 1/1

NS, Z
PS X=0 X=1

A B,0 A,0
B C,0 A,0
C C,0 A,1

Page: 28
DIGITAL DESIGN Edited by Chu Yu

PS NS, Z X=0 X=1

y1y0 X=0 X=1 J1K1 J0K0 J 1K 1 J 0K 0

A = 00 01,0 00,0 0 1 0 0
B = 01 11,0 00,0 1 0 0 1
C = 11 11,0 00,1 0 0 1 1

y 1y 0 y 1y 0
x 00 01 11 10 x 00 01 11 10
0 0 1 0  0 1 0 0 
1 0 0 1  1 0 1 1 
J1 = x’y0 k1 = x J0 = x’ k0 = x

Page: 29
DIGITAL DESIGN Edited by Chu Yu

y1y0
x 00 01 11 10
0 0 0 0 
1 0 0 1 
z = xy1

1
3
X J Q
y0 2
J Q
y1 1
3 Z
CK CK 2
1
K Q K Q

CK

Page: 30
 DIGITAL DESIGN Edited by Chu Yu

Design of Asynchronous Sequential Circuit

 Example of flow tables
 A circled entry indicates a stable condition, other non-circled entries
denote unstable states.

Two states with two inputs

and one output

Four states with one input

Page: 31
DIGITAL DESIGN Edited by Chu Yu

Gated–Latch Logic Diagram

DG DG
y 00 01 11 10 y 00 01 11 10
0 0 0 1 0 0 0 0 1 0
1 1 0 1 1 1 1 0 1 1
Y = DG + G’y Q = Y = DG + G’y

D
Y
Q
G
y

Y: next state y: present state

Page: 32
DIGITAL DESIGN Edited by Chu Yu

Gated–Latch Logic Diagram-SR Latch

DG
y 00 01 11 10 y Y S R
Y
0 0 0 1 0 0 0 0 
0 1 1 0
1 1 0 1 1 1 0 0 1
1 1  0

DG DG
y 00 01 11 10 y 00 01 11 10
0 0 0 1 0 0   0 
1  0   1 0 1 0 0
S = DG R = D’G

D S
Q
G
R

Page: 33
DIGITAL DESIGN Edited by Chu Yu

Total State

 Combine the internal state with the input value together.

Gated-latch total states

state input output
Comments
D G Q
a 0 1 0 Q = D because G = 1
b 1 1 1 Q = D because G = 1
c 0 0 0 After state a or state d
d 1 0 0 After state c
e 1 0 1 After state b or state f
f 0 0 1 After state e

Page: 34
DIGITAL DESIGN Edited by Chu Yu

Primitive Flow Table

 Simultaneous transitions of two input variables, such as 0110 or 11
 00, are not allowed. We can enter dash marks for this case.
 All outputs associated with unstable states are marked with a dash to
indicate don’t-care conditions.
DG
00 01 11 10
a c, - a, 0 b, - -, -

b -, - a, - b, 1 e, -

c c, 0 a, - -, - d, -

d c, - -, - b, - d, 0

e f, - -, - b, - e, 1

f f, 1 a,- -, - e, -

Page: 35
DIGITAL DESIGN Edited by Chu Yu

Page: 36
DIGITAL DESIGN Edited by Chu Yu

Implication Table
 Two states can be combined into one if they can be shown to be
equivalent.
 Equivalent: if for each possible input, they give exactly the same
output and go to the same next states or to equivalent next states.
 If the pair of states (c, d) are equivalent, then the pair of states (a, b)
will also be equivalent.
 If (a, b) imply (c, d) and (c, d) imply (a, b), then both pairs of states
are equivalent. (a = b, c = d)

Page: 37
DIGITAL DESIGN Edited by Chu Yu

Example I

Page: 38
DIGITAL DESIGN Edited by Chu Yu

Page: 39
DIGITAL DESIGN Edited by Chu Yu

Page: 40
DIGITAL DESIGN Edited by Chu Yu

Example II

Page: 41
DIGITAL DESIGN Edited by Chu Yu

Maximal Compatibles without Imply States

 Merge Diagrams (The chosen set will cover all the states of the original table)

2 nodes 3 nodes 4 nodes 5 nodes

a a
b
h
f
b
g c

e c d
f
d e
Maximal Compatible Maximal Compatible
(a, b)(a, c, d)(b, e, f) (a, b, e, f)(b, c, h)(c, d)(g)

Page: 42
DIGITAL DESIGN Edited by Chu Yu

Closed Covering Condition

a
b b, c 
c  d, e  e b (a, b)(a, d)
d b, c   a, d  (b, c) (c, d, e)

e    b, c 
a b c d d c

Implication Table Merge Diagram

Closure Table
compatibles (a, b) (a, d) (b, c) (c, d, e) (a=d) if (b=c),
Implied States (b, c) (b, c) (d, e) (a, d) (b=c) if (d=e),
(b, c) (c=d=e) if (a=d)&(b=c)

 Not closed covering condition: (a, b) (c, d, e), because (a, b) imply
(b, c) but (b ,c) is not included in the chosen set of (a, b) (c, d, e).
 Closed covering condition: A set of compatibles (a, d) (b, c) (c, d, e).
Page: 43
 DIGITAL DESIGN Edited by Chu Yu

 Example III: Negative-edge-trigged T Flip Flop

state input output

Note
T C Q
a 1 1 0 Initial output to be 0
b 1 0 1 After state a
c 1 1 1 Initial output to be 1
d 1 0 0 After state c
e 0 0 0 After state d or state f
f 0 1 0 After state e or state a
g 0 0 1 After state b or state h
h 0 1 1 After state g or state c

Page: 44
 DIGITAL DESIGN Edited by Chu Yu

 Original Flow
TC
00 01 11 10
state input output
a -, - f, - a, 0 b, - Note
T C Q
b g, - -, - c, - b, 1 a 1 1 0 Initial output to be 0
b 1 0 1 After state a
c -, - h, - c, 1 d, - c 1 1 1 Initial output to be 1
d 1 0 0 After state c
d e, - -, - a, - d, 0 e 0 0 0 After state d or state f
f 0 1 0 After state e or state a
e e, 0 f, - -, - d, - g 0 0 1 After state b or state h
h 0 1 1 After state g or state c
f e, - f, 0 a, - -, -

g g, 1 h, - -, - b, -

h g, - h, 1 c, - -, -

Page: 45
DIGITAL DESIGN Edited by Chu Yu

Page: 46
DIGITAL DESIGN Edited by Chu Yu

a
b
h

g c (a, f)(b, g, h) (c, h) (d, e, f)

f d
e

Page: 47
DIGITAL DESIGN Edited by Chu Yu

a = 00 b = 01

d = 10 c = 11

TC TC
y1y2 00 01 11 10 y1y2 00 01 11 10
a = 00 10 00 00 01 00 0 0 0 
b = 01 01 01 11 01 01 1 1 1 1
c = 11 01 11 11 10 11 1 1 1 
d = 10 10 10 00 10 10 0 0 0 0
Transition Table Output

Page: 48
DIGITAL DESIGN Edited by Chu Yu

TC TC
y1y2 00 01 11 10 y1y2 00 01 11 10
00 1 0 0 0 00 0   
01 0 0 1 0 01   0 
11 0    11 1 0 0 0
10   0  10 0 0 1 0
S1 = y2TC + y’2T’C’ R1 = y2T’C’ + y’2TC

TC TC
y1y2 00 01 11 10 y1y2 00 01 11 10
00 0 0 0 1 00    0
01     01 0 0 0 0
11    0 11 0 0 0 1
10 0 0 0 0 10    
S2 = y’1TC’ R2 = y1TC’
Page: 49
DIGITAL DESIGN Edited by Chu Yu

S1 = y2TC + y’2T’C’
R1 = y2T’C’ + y’2TC

Page: 50