Formula Sheets: Karnaugh Maps (K-Maps) | Digital Electronics - Electrical Engineering (EE) PDF Download

 Page 1


Digital Electronics: Karnaugh Maps (K-M aps)
F orm ula Sheet for Electrical GA TE
K-Map Basics
• Min term Represen tation : F orn v ariables, a min term is a pro duct term where eac h
v ariable app ears exactly once (complemen ted or uncomplemen ted).
m
i
= Pro duct of n v ariables (1 for uncomplemen ted, 0 for complemen ted)
where i is the decimal equiv alen t of the binary min term.
• Maxterm Represen tation :
M
i
= Sum of n v ariables (0 for uncomplemen ted, 1 for complemen ted)
• K-Map Size : F or n v ariables, K-Map has 2
n
cells.
2 v ariables: 2×2, 3 v ariables: 4×2, 4 v ariables: 4×4
K-Map Simplification
• Grouping R ule : Group adjacen t 1s (for SOP) or 0s (for POS) in p o w ers of 2 (1, 2,
4, 8 cells).
Group size = 2
k
, k = 0,1,2,3,...
• Minimized SOP Expression :
Y =
?
( Pro duct terms from groups of 1s)
• Minimized POS Expression :
Y =
?
( Sum terms from groups of 0s)
• Num b er of V ariables Reduced : Eac h group of 2
k
cells eliminates k v ariables from
the term.
Grouping R ules
• V alid Groups : Rectangular groups of 1, 2, 4, or 8 cells (m ust b e p o w er of 2).
• A djacency : Cells are adjacen t if they differ b y exactly one bit (including wrap-around
edges).
Example (3-v ariable K-Ma p) :m
0
(000) is adjacen t to m
1
(001),m
2
(010),m
4
(100)
• Minimal Co v er : Use the few est groups to co v er all 1s (for SOP) or 0s (for POS).
1
Page 2


Digital Electronics: Karnaugh Maps (K-M aps)
F orm ula Sheet for Electrical GA TE
K-Map Basics
• Min term Represen tation : F orn v ariables, a min term is a pro duct term where eac h
v ariable app ears exactly once (complemen ted or uncomplemen ted).
m
i
= Pro duct of n v ariables (1 for uncomplemen ted, 0 for complemen ted)
where i is the decimal equiv alen t of the binary min term.
• Maxterm Represen tation :
M
i
= Sum of n v ariables (0 for uncomplemen ted, 1 for complemen ted)
• K-Map Size : F or n v ariables, K-Map has 2
n
cells.
2 v ariables: 2×2, 3 v ariables: 4×2, 4 v ariables: 4×4
K-Map Simplification
• Grouping R ule : Group adjacen t 1s (for SOP) or 0s (for POS) in p o w ers of 2 (1, 2,
4, 8 cells).
Group size = 2
k
, k = 0,1,2,3,...
• Minimized SOP Expression :
Y =
?
( Pro duct terms from groups of 1s)
• Minimized POS Expression :
Y =
?
( Sum terms from groups of 0s)
• Num b er of V ariables Reduced : Eac h group of 2
k
cells eliminates k v ariables from
the term.
Grouping R ules
• V alid Groups : Rectangular groups of 1, 2, 4, or 8 cells (m ust b e p o w er of 2).
• A djacency : Cells are adjacen t if they differ b y exactly one bit (including wrap-around
edges).
Example (3-v ariable K-Ma p) :m
0
(000) is adjacen t to m
1
(001),m
2
(010),m
4
(100)
• Minimal Co v er : Use the few est groups to co v er all 1s (for SOP) or 0s (for POS).
1
Don’t Care Conditions
• Don’t Care (X) : Can b e treated as 1 or 0 to optimize grouping.
Include X in group if it reduces the n um b er of terms or literals
• Effect on Simplification : Don’t cares simplify the expression without affecting
functionalit y .
SOP and POS Con v ersion
• SOP from K-Map :
Y =
?
m
i
(min terms corresp o nding to 1s in groups)
• POS from K-Map :
Y =
?
M
i
(maxterms corresp onding to 0s in groups)
• Con v ersion Using De Morgan’s Theorem:
A+B =A·B, A·B =A+B
Key Notes
• K-Map La y out : Gra y co de ordering for ro ws and columns to ensure adjacency .
• Essen tial Prime Implican ts : Groups that c o v er 1s not co v ered b y an y other group.
• Don’t Cares : Common in GA TE problems to simplify logic.
• GA TE F o cus : Practice 3-v ariable and 4-v ariable K-Maps, iden tify prime implican ts,
and con v ert b et w een SOP and POS.
• Error A v oidance : Ensure all 1s (SOP) or 0s (POS) are co v ered; a v oid in v alid group-
ings.
2