Scribd
Upload
5 views36 pages

Lecture 3 Pt.3

The document discusses two-level logic variations, including Sum of Products (SOP) and Product of Sums (POS) forms, and their implementation using NAND and NOR gates. It also covers multiple-output circuits, specifically priority circuits, and introduces concepts like 'don't cares' and floating nodes in digital logic. Additionally, it explains Karnaugh Maps (K-Maps) for minimizing Boolean expressions graphically, including rules and definitions related to K-Maps.

Uploaded by

Tonalli Nava
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views36 pages

Lecture 3 Pt.3

The document discusses two-level logic variations, including Sum of Products (SOP) and Product of Sums (POS) forms, and their implementation using NAND and NOR gates. It also covers multiple-output circuits, specifically priority circuits, and introduces concepts like 'don't cares' and floating nodes in digital logic. Additionally, it explains Karnaugh Maps (K-Maps) for minimizing Boolean expressions graphically, including rules and definitions related to K-Maps.

Uploaded by

Tonalli Nava
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 36

From Logic to Gates

Two-Level Logic Variations


• SOP form: ANDs followed by ORs (most common)
• POS form: ORs followed by ANDs
• SOP form: Only NAND gates
• POS form: Only NOR gates

89
From Logic to Gates
• Two-level logic: ANDs followed by ORs
• Example: Y = ABC + ABC + ABC
A B C

A B C
minterm: ABC

minterm: ABC

minterm: ABC

90
From Logic to Gates
• Two-level logic: ANDs followed by ORs → NANDs only
• Example: Y = ABC + ABC + ABC
A B C

A B C
minterm: ABC

minterm: ABC

minterm: ABC

91
From Logic to Gates
• Two-level logic: ORs followed by ANDs
• Example: Y = (A+B)(A+B+C)

92
From Logic to Gates
• Two-level logic: ORs followed by ANDs → NORs only
• Example: Y = (A+B)(A+B+C)

93
Multiple-Output Circuits
• Example: Priority Circuit
Output asserted
corresponding to most A3 A2 A1 A0 Y3 Y2 Y1 Y0
0 0 0 0
significant TRUE input 0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
A3 Y3 0 1 1 0
0 1 1 1
A2 Y2 1 0 0 0
1 0 0 1
A1 Y1 1 0 1 0
1 0 1 1
A0 Y0 1 1 0 0
PRIORITY 1 1 0 1
CiIRCUIT 1 1 1 0
1 1 1 1

94
Multiple-Output Circuits
• Example: Priority Circuit
Output asserted
A3 A2 A1 A0 Y3 Y2 Y1 Y0
corresponding to most 0 0 0 0 0 0 0 0
significant TRUE input 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0
0 0 1 1 0 0 1 0
0 1 0 0 0 1 0 0
0 1 0 1 0 1 0 0
A3 0 1 1 0 0 1 0 0
Y3
0 1 1 1 0 1 0 0
A2 Y2 1 0 0 0 1 0 0 0
1 0 0 1 1 0 0 0
A1 Y1 1 0 1 0 1 0 0 0
1 0 1 1 1 0 0 0
A0 Y0 1 1 0 0 1 0 0 0
PRIORITY 1 1 0 1 1 0 0 0
CiIRCUIT 1 1 1 0 1 0 0 0
1 1 1 1 1 0 0 0

95
Don’t Cares (X)

A3 A2 A1 A0 Y3 Y2 Y1 Y0 A3 A2 A1 A0 Y3 Y2 Y1 Y0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0 1 X 0 0 1 0
0 0 1 1 0 0 1 0 0 1 X X 0 1 0 0
0 1 0 0 0 1 0 0 1 X X X 1 0 0 0
0 1 0 1 0 1 0 0
0 1 1 0 0 1 0 0
0 1 1 1 0 1 0 0
1 0 0 0 1 0 0 0
1 0 0 1 1 0 0 0
1 0 1 0 1 0 0 0
1 0 1 1 1 0 0 0
1 1 0 0 1 0 0 0
1 1 0 1 1 0 0 0
1 1 1 0 1 0 0 0
1 1 1 1 1 0 0 0

96
Priority Circuit Hardware

A3 A2 A1 A0 Y3 Y2 Y1 Y0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 A3 A2 A1 A0
0
0
0
0
1
1
0
1
0
0
0
0
1
1
0
0
Y3
0 1 0 0 0 1 0 0
0 1 0 1 0 1 0 0 Y2
0 1 1 0 0 1 0 0
0 1 1 1 0 1 0 0
1
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
Y1
1 0 1 0 1 0 0 0
1 0 1 1 1 0 0 0
1 1 0 0 1 0 0 0 Y0
1 1 0 1 1 0 0 0
1 1 1 0 1 0 0 0
1 1 1 1 1 0 0 0

97
Contention: X
A=1
Not a combinational
Y=X Logic, why?
B=0

• The symbol “X” indicates that the circuit node has an


unknown or illegal value
• Contention (X): output driven to 1 and 0 at the same time
– Actual value: 0, 1, or somewhere in between (forbidden zone)
– Might change with voltage, temperature, time, noise
– Often causes excessive power dissipation
• Warnings:
– X is used for “don’t care” or contention - look at the context
to tell them apart
– Contention or uninitialized outputs usually indicate a bug

98
Floating: Z
• The symbol “Z” indicates that a node is being driven neither 1
nor 0
• The node is said to be floating, high impedance, open circuit,
high Z
• Floating output might be 0, 1, or somewhere in between
– A voltmeter won’t indicate whether a node is floating
E

A Y

Tristate Buffer E A Y
0 0 Z
0 1 Z
1 0 0
1 1 1
99
Tristate Busses
Floating nodes are used in tristate busses
• Many different drivers
• Exactly one is active at once

100
Karnaugh Maps (K-Maps)
• K-maps minimize equations graphically by
using PA + PA = P
• Work well for up to 4 variables
• Circle 1’s in adjacent squares
A B C Y
Y
0 0 0 1 AB
0 0 1 1 00 01 11 10
C
0 1 0 0
0 1 1 0 0 1 0 0 0
1 0 0 0
1 0 1 0 1 1 0 0 0
1 1 0 0
1 1 1 0
101
Karnaugh Maps (K-Maps)
• To minimize the Boolean expression, include only
literals who is true
• If a variable’s (C) true and complement forms are both
in the circle, it is excluded from the implicant

A B C Y Y Y
AB AB
0 0 0 1
00 01 11 10 C 00 01 11 10
0 0 1 1 C
0 1 0 0
0 1 1 0 0 1 0 0 0 0 ABC ABC ABC ABC
1 0 0 0
1 0 1 0
1 1 0 0 1 1 0 0 0 1 ABC ABC ABC ABC
1 1 1 0

Y =ABC + ABC = AB
P :AB, A: C
102
3-Input K-Map

Truth Table K-Map


Y
A B C Y AB
0 0 0 0 C 00 01 11 10
0 0 1 0
0 1 0 1 0
0 1 1 1
1 0 0 0
1 0 1 0 1
1 1 0 0
1 1 1 1

Y= AB + BC

103
K-Map Definitions
• Complement: variable with a bar over it
A, B, C
• Literal: variable or its complement
A, A, B, B, C, C
• Implicant: product of literals
ABC, AC, BC
• Prime implicant: implicant corresponding
to the largest circle in a K-map

104
K-Map Rules
• Every 1 must be circled at least once
• Each circle must span a power of 2 (i.e. 1, 2, 4)
squares in each direction
• Each circle must be as large as possible
• A circle may wrap around the edges
• A “don't care” (X) is circled only if it helps
minimize the equation

105
4-Input K-Map
A B C D Y
0 0 0 0 1 Y
0 0 0 1 0 AB
CD 00 01 11 10
0 0 1 0 1
0 0 1 1 1 00
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1 01
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1 11
1 0 1 0 1
1 0 1 1 0
1 1 0 0 0 10
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0

106
4-Input K-Map
A B C D Y Y
0 0 0 0 1 AB
0 0 0 1 0 CD 00 01 11 10
0 0 1 0 1
0 0 1 1 1 00 1 0 0 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1 01 0 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1 11 1 1 0 0
1 0 1 0 1
1 0 1 1 0
10 1 1 0 1
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0

107
4-Input K-Map
A B C D Y Y
0 0 0 0 1 AB
0 0 0 1 0 CD 00 01 11 10
0 0 1 0 1
0 0 1 1 1 00 1 0 0 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1 01 0 1 0 1
0 1 1 1 1
1 0 0 0 1
11 1 1 0 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0 10 1 1 0 1
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0 Y = AC + ABD + ABC + BD
1 1 1 1 0

108
K-Maps with Don’t Cares
A B C D Y
Y
0 0 0 0 1
AB
0 0 0 1 0 CD 00 01 11 10
0 0 1 0 1
0 0 1 1 1 00
0 1 0 0 0
0 1 0 1 X
0 1 1 0 1 01
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1 11
1 0 1 0 X
1 0 1 1 X
10
1 1 0 0 X
1 1 0 1 X
1 1 1 0 X
1 1 1 1 X

109
K-Maps with Don’t Cares
A B C D Y Y
0 0 0 0 1 AB
0 0 0 1 0 CD 00 01 11 10
0 0 1 0 1
0 0 1 1 1 00 1 0 X 1
0 1 0 0 0
0 1 0 1 X
0 1 1 0 1 01 0 X X 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1 11 1 1 X X
1 0 1 0 X
1 0 1 1 X
1 1 0 0 X 10 1 1 X X
1 1 0 1 X
1 1 1 0 X
1 1 1 1 X

110
K-Maps with Don’t Cares
A B C D Y Y
0 0 0 0 1 AB
0 0 0 1 0 CD 00 01 11 10
0 0 1 0 1
0 0 1 1 1 00 1 0 X 1
0 1 0 0 0
0 1 0 1 X
0 1 1 0 1 01 0 X X 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1 11 1 1 X X
1 0 1 0 X
1 0 1 1 X
1 1 0 0 X 10 1 1 X X
1 1 0 1 X
1 1 1 0 X
1 1 1 1 X Y = A + BD + C

111
Combinational Building Blocks
Common Building Blocks
• Multiplexers
• Decoders

112
Multiplexer (Mux)
• Selects between one of N inputs to connect to output
• log2N -bit select input: control input
• Example: 4:1 mux needs 2-bit; 8:1 mux needs 3-bit
• Example: S

D0 0
Y
D1 1

2:1 Mux S D1 D0 Y S Y
0 0 0 0 0 D0
0 0 1 1 1 D1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

113
Multiplexer Implementations
• Logic gates • Tristates
– Sum-of-products form – For an N-input mux, use N tristates
– Turn on exactly one to select the
Y
D0 D1 appropriate input
S 00 01 11 10

0 0 0 1 1

1 0 1 1 0

Y = D 0S + D 1S

D0

S
D1

114
4:1 Multiplexer Implementations
4:1 Mux 2-Level Logic Tristates

Hierarchical

115
Logic using Multiplexers
Using mux as a lookup table
A B Y
0 0 0
• By changing the input, we
0 1 0 could reprogram the mux to
1 0 0
1 1 1 do any logic function
Y = AB • For 3 input variables, we
AB would need an 8:1 mux
00
01
10
Y
11

116
Logic using Multiplexers
Reducing the size of the mux
A
A B Y A Y
0 0 0
0 0 0
0 1 0 Y
Y = AB 1 0 0 1 B B 1
1 1 1

117
Decoders
• N inputs, 2N outputs
• One-hot outputs: only one HIGH output at
once
2:4
Decoder
11 Y3
A1 10 Y2
A0 01 Y1
00 Y0

A1 A0 Y3 Y2 Y1 Y0
0 0 0 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 0 0 0

118
Decoder Implementation
A1 A0
2:4
Decoder
11 Y3
A1 10 Y2
A0 01 Y1 Y3
00 Y0
Y2
A1 A0 Y3 Y2 Y1 Y0
0 0 0 0 0 1 Y1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 0 0 0 Y0

119
Logic Using Decoders
• Using decoder to compute minterms
• Compute output with OR
• Example:
2:4
Decoder Minterm
11 AB
A 10 AB
B 01 AB
00 AB

Y = AB + AB
= A ⊕ B Y
120
Timing
• We know how to build correct circuit. How to
build fast circuits?
• Delay: time between input change and output
changing
A Y

delay

Time

121
Contamination & Propagation Delay

• Contamination delay: tcd = min delay from


input to output
• Propagation delay: tpd = max delay from input to output

A Y

tpd

tcd

Time
122
Propagation & Contamination Delay

• Delay is caused by
– Capacitance (charging) and resistance in a circuit
– Nothing can move faster than the speed of light
• Reasons why tpd and tcd may be different:
– Different rising and falling delays
– Multiple inputs and outputs, some of which are faster
than others
– Circuits slow down when hot and speed up when cold
– Circuits tend to be faster at high voltage and slower
low voltage

123
Critical (Long) & Short Paths

Critical Path

A n1
B
n2
C
D Y

Short Path

Critical (Long) Path: tpd = 2tpd_AND + tpd_OR (Max delay)


Short Path: tcd = tcd_AND (Min delay)

124

You might also like