Formula Sheets Boolean Algebra & Minimization Techniques - Digital Logic

 Page 1


Bo olean Algebra and Minimization F orm ula Sheet
Bo olean Algebra Basics
• Definition : Algebra for binary v ariables (0, 1) using op erations AND (· ), OR (+ ), NOT (A ).
• V ariables and Literals : V ariable A , literals A or A , L = 2n literals for n v ariables.
• T ruth T able : 2
n
ro ws for n v ariables, eac h ro w maps inputs to output.
• Logic Gates : AND, OR, NOT, NAND, NOR, X OR, XNOR.
– X OR: A?B =AB +AB .
– XNOR: A?B =AB +AB .
• Propagation Dela y : T
gate
, e.g., AND/NOT: 1-2 ns, X OR: 2-3 ns, affects total dela y T
circuit
=
?
T
gate
i
.
La ws of Bo olean Algebra
• Iden tit y : A+0 =A , A·1 =A .
• Null : A+1 = 1 , A·0 = 0 .
• Idemp oten t : A+A =A , A·A =A .
• Complemen t : A+A = 1 , A·A = 0 .
• Comm utativ e : A+B =B +A , A·B =B·A .
• Asso ciativ e : (A+B)+C =A+(B +C) , (A·B)·C =A·(B·C) .
• Distributiv e : A·(B +C) =A·B +A·C , A+(B·C) = (A+B)·(A+C) .
• Absorption : A+A·B =A , A·(A+B) =A .
• De Morgan’s : A+B =A·B , A·B =A+B .
• In v olution : A =A .
Canonical and Standard F orms
• Min term (Sum of Pro ducts, SOP) : Pro duct term with all v ariables, e.g., ABC , m
i
for ro w i
where f = 1 .
• Maxterm (Pro duct of Sums, POS) : Sum term with all v ariables, e.g., A+B+C , M
i
for ro w
i where f = 0 .
• Canonical SOP : f =
?
m
i
, e.g., f(A,B,C) =
?
m(1,3,5) =ABC +ABC +ABC .
• Canonical POS : f =
?
M
i
, e.g., f(A,B,C) =
?
M(0,2,4,6) = (A+B +C)(A+B +C)(A+
B +C)(A+B +C) .
• Num b er of T erms : N
terms
= 2
n
forn v ariables,N
terms
=k wherek is 1’s (SOP) or 0’s (POS) in
truth table.
• Con v ersion : SOP to POS using De Morgan’s, T
con v ert
=O(n·k) .
1
Page 2


Bo olean Algebra and Minimization F orm ula Sheet
Bo olean Algebra Basics
• Definition : Algebra for binary v ariables (0, 1) using op erations AND (· ), OR (+ ), NOT (A ).
• V ariables and Literals : V ariable A , literals A or A , L = 2n literals for n v ariables.
• T ruth T able : 2
n
ro ws for n v ariables, eac h ro w maps inputs to output.
• Logic Gates : AND, OR, NOT, NAND, NOR, X OR, XNOR.
– X OR: A?B =AB +AB .
– XNOR: A?B =AB +AB .
• Propagation Dela y : T
gate
, e.g., AND/NOT: 1-2 ns, X OR: 2-3 ns, affects total dela y T
circuit
=
?
T
gate
i
.
La ws of Bo olean Algebra
• Iden tit y : A+0 =A , A·1 =A .
• Null : A+1 = 1 , A·0 = 0 .
• Idemp oten t : A+A =A , A·A =A .
• Complemen t : A+A = 1 , A·A = 0 .
• Comm utativ e : A+B =B +A , A·B =B·A .
• Asso ciativ e : (A+B)+C =A+(B +C) , (A·B)·C =A·(B·C) .
• Distributiv e : A·(B +C) =A·B +A·C , A+(B·C) = (A+B)·(A+C) .
• Absorption : A+A·B =A , A·(A+B) =A .
• De Morgan’s : A+B =A·B , A·B =A+B .
• In v olution : A =A .
Canonical and Standard F orms
• Min term (Sum of Pro ducts, SOP) : Pro duct term with all v ariables, e.g., ABC , m
i
for ro w i
where f = 1 .
• Maxterm (Pro duct of Sums, POS) : Sum term with all v ariables, e.g., A+B+C , M
i
for ro w
i where f = 0 .
• Canonical SOP : f =
?
m
i
, e.g., f(A,B,C) =
?
m(1,3,5) =ABC +ABC +ABC .
• Canonical POS : f =
?
M
i
, e.g., f(A,B,C) =
?
M(0,2,4,6) = (A+B +C)(A+B +C)(A+
B +C)(A+B +C) .
• Num b er of T erms : N
terms
= 2
n
forn v ariables,N
terms
=k wherek is 1’s (SOP) or 0’s (POS) in
truth table.
• Con v ersion : SOP to POS using De Morgan’s, T
con v ert
=O(n·k) .
1
Minimization of Bo olean F unctions
• Ob jectiv e : Reduce n um b er of literals/gates, minimize T
circuit
and S
circuit
(area).
• Algebraic Minimization : Apply Bo olean la ws, e.g., AB +AB =A(B +B) =A .
• Karnaugh Map (K-Map) :
– Size: 2
n
cells for n v ariables, e.g., 4x4 for 4 v ariables.
– Grouping: Co v er 1’s in groups of 2
k
(1, 2, 4, 8), minimizes literals.
– Literal Reduction: Eac h group of 2
k
reduces k literals, L
min
=n-log
2
( group size) .
– Don’t Cares (X): T reat as 1 or 0 to maximize group size, reduces N
terms
.
• Implican ts in K-Map :
– Prime Implican t: Largest group co v ering 1’s, not subsumed b y larger group.
– Essen tial Prime Implican t: Co v ers at least one 1 not co v ered b y others.
– Num b er of Implican ts: N
prime
= 2
n
, N
essen tial
=N
prime
.
• Minimization Time : T
K-Map
=O(2
n
) for man ual, T
Quine-McClusk ey
=O(3
n
) for algorithmic.
F unctional Completeness
• Definition : Set of gates/op erations can express an y Bo olean function.
• Complete Sets : {AND, OR , NOT}, {NAND}, {NOR}.
• NAND Equiv alence : A·B =A+B , A+B =A·B , T
NAND
˜T
AND
+T
NOT
.
• NOR Equiv alence : A+B =A·B , A·B =A+B , T
NOR
˜T
OR
+T
NOT
.
• Minim um Gates : N
gates
?N
literals
, reduced b y using NAND/NOR only .
• Implemen tation Cost : C
circuit
=
?
(C
gate
i
·N
gate
i
) , lo w er for single-t yp e gates (NAND/NOR).
P erformance Metrics
• Circuit Dela y : T
circuit
=
?
T
gate
i
along critical path, minimized b y few er gates/literals.
• Gate Coun t : N
gates
˜N
literals
/2 (2-input gates), reduced b y K-Map.
• P o w er Consumption : P
circuit
=
?
(C
gate
i
·V
2
·f) , whereC
gate
i
is gate capacitance,V is v oltage,
f is frequency .
• Area : S
circuit
?N
gates
, minimized b y functional completeness (e.g., NAND-only).
• Minimization E?iciency : E
min
=
N
literals-b efore
N
literals-after
, higher for K-Map vs. algebraic.
• Complexit y : C
function
=N
terms
·L
a vg
, where L
a vg
is a v erage literals p er term.
Applications and Concepts
• Logic Gates : Building blo c ks for digital circuits, T
gate
critical for high-sp eed systems.
• Bo olean Algebra : Simplifies circuit design, reduces N
gates
and T
circuit
.
• K-Maps : Optimal for 2-6 v ariables, minimizes N
literals
, used in com binational logic.
• F unctional Completeness : Enables single-gate designs (NAND/NOR), reduces C
circuit
.
• Canonical F orms : Standard re presen tation, N
terms
= 2
n
, simplified to minimal SOP/POS.
• Digital Logic Design : Used in ALUs, con trol units, memory deco ders, T
circuit
?N
gates
.
2