MATA KULIAH : Arsitektur dan Sistem

Komputer
KODE MATA KULIAH/SKS : TI2133 / 3 SKS
KURIKULUM : 2017
VERSI : 0.0
 Minggu 8
Pertemuan 8
KEMAMPUAN AKHIR YANG DIHARAPKAN

Mahasiswa mampu mengenal logika sirkuit pada arsitektur komputer

dan desain sistem memori
MATERI POKOK

• Logic Gates
• Boolean Algebra
• Designing Combinational logic circuits
• Karnaugh Maps
• Basic Logic Blocks
SUMBER PUSTAKA

1. M. Abd-El-Barr dan H. El-Rewini, Fundamentals of Computer

Organization and Architecture, New Jersey: John Wiley &
Sons, Inc, 2005.
2. L. Null dan J. Lobur, The Essentials of Computer Organization
& Architecture, Burlington: Jones & Bartlett Learning, 2018.
3. A. Bindal, Fundamentals of Computer Architecture and
Design, San Jose: Springer, 2019.
 Basic Definitions
• Binary Operators
• AND
z=x•y=xy z=1 if x=1 AND y=1
• OR
z=x+y z=1 if x=1 OR y=1
• NOT
z = x = x’ z=1 if x=0

• Boolean Algebra
• Binary Variables: only ‘0’ and ‘1’ values
• Algebraic Manipulation
 Boolean Algebra Postulates

• Commutative Law
x•y=y•x x+y=y+x
• Identity Element
x•1=x x+0=x
• Complement
x • x’ = 0 x + x’ = 1
 Boolean Algebra Theorems

• Duality
• The dual of a Boolean algebraic expression is obtained by interchanging the AND
and the OR operators and replacing the 1’s by 0’s and the 0’s by 1’s.
Applied to a valid
x•(y+z)=(x•y)+(x•z) equation produces a
x+(y•z)=(x+y)•(x+z) valid equation

Theorem 1
x•x=x x+x=x

Theorem 2
x•0=0 x+1=1
 Boolean Algebra Theorems

• Theorem 3: Involution
• ( x’ )’ = x (𝑥) = 𝑥

• Theorem 4: Associative & Distributive

(x•y)•z=x•(y•z)
x•(y+z)=(x•y)+(x•z)
x + ( y • z ) = ( x + y ) • ( x + z)
(x+y)+z=x+(y+z)

• Theorem 5: DeMorgan
• ( x • y )’ = x’ + y’ ( x + y )’ = x’ • y’
• (x•y) =x +y (x+y) = x•y
• Theorem 6: Absorption
• x•(x+y)=x x+(x•y)=x
 Operator Precedence
• Parentheses
( . . . ) • ( . . .)
x [ y  z (w  x)]
• NOT
( w  x)
x’ + y
• AND

( w  x)
x+x•y
• OR

z ( w  x)
y  z ( w  x)
x [ y  z ( w  x )]
DeMorgan’s Theorem

a [b  c (d  e )]

a  [b  c (d  e )]

a  b (c ( d  e ))

a  b (c  (d  e ))

a  b (c  (d e))
a  b (c  d e)
 Boolean Functions
• Boolean Expression
Example: F = x + y’ z x y z F
• Truth Table 0 0 0 0
All possible combinations
of input variables 0 0 1 1
• Logic Circuit 0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
x F 1 1 0 1
y
z 1 1 1 1
 Algebraic Manipulation
• Literal:
A single variable within a term that may be complemented or not.
• Use Boolean Algebra to simplify Boolean functions to produce simpler
circuits
Example: Simplify to a minimum number of literals
F = x + x’ y ( 3 Literals)
= x + ( x’ y )
= ( x + x’ ) ( x + y )
=(1)(x+y)=x+y ( 2 Literals)

Distributive law (+ over •)

 Complement of a Function
• DeMorgan’s Theorm
F  A B C
F  A B C
• Duality & Literal Complement
F  A B  C

F  A B C
F A B C
F  A B  C
 Canonical Forms
• Minterm
• Product (AND function)
• Contains all variables
A B C Minterm
• Evaluates to ‘1’ for a 0 0 0 0 m0 ABC
specific combination
Example 1 0 0 1 m1 ABC
A=0 A B C
B=0 (0) • (0) • (0) 2 0 1 0 m2 ABC
C=0
3 0 1 1 m3 ABC
4 1 0 0 m4 ABC
5 1 0 1 m5 ABC
6 1 1 0 m6 ABC
1 • 1 • 1=1
7 1 1 1 m7 ABC
 Canonical Forms
• Maxterm
• Sum (OR function)
• Contains all variables
A B C Maxterm
• Evaluates to ‘0’ for a 0 0 0 0 M0 A  B  C
specific combination
Example 1 0 0 1 M1 A  B  C
A=1 A B C
B=1 (1) + (1) + (1) 2 0 1 0 M2 A  B  C
C=1
3 0 1 1 M3 A  B  C
4 1 0 0 M4 A  B  C
5 1 0 1 M5 A  B  C
6 1 1 0 M6 A  B  C

0 + 0 + 0=0
7 1 1 1 M7 A  B  C
 Canonical Forms
• Truth Table to Boolean Function

A B C F F  ABC  ABC  ABC  ABC

0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1
 Canonical Forms
• Sum of Minterms A B C F F
F  ABC  ABC  ABC  ABC 0 0 0 0 0 1
1 0 0 1 1 0
F ofm
• Product 1  m4  m5  m7
Maxterms
2 0 1 0 0 1
F   (1,4,5,7)
3 0 1 1 0 1
4 1 0 0 1 0
F  ABC  ABC  ABC  ABC 5 1 0 1 1 0
F  ABC  ABC  ABC  ABC 6 1 1 0 0 1
7 1 1 1 1 0
F  ABC  ABC  ABC  ABC
F  ( A  B  C )( A  B  C )( A  B  C )( A  B  C )
F  M0 M2 M3 M6
F   (0,2,3,6)
 Standard Forms
• Sum of Products (SOP)
AB(C  C )
 AB(1)
F  ABC  ABC  ABC  ABC
 AB
AC ( B  B)
 AC
BC ( A  A)
 BC
F  BC ( A  A)  AB(C  C )  AC ( B  B)

F  BC  AB  AC
 Standard Forms
• Product of Sums (POS)
AB(C  C )

F  ABC  ABC  ABC  ABC

BC ( A  A)

AC ( B  B)
F  AC ( B  B)  AB(C  C )  BC ( A  A)

F  AC  AB  BC
F  ( A  C )( A  B)( B  C )
 Two-Level Implementations
• Sum of Products (SOP)
B’
C

F  BC  AB  AC A
B’ F
• Product of Sums (POS)
A
C
A
C
A
F  ( A  C )( A  B)( B  C ) B’ F
B’
C
 Logic Operators
• AND x y AND
0 0 0
x x•y 0 1 0
y 1 0 0
• NAND (Not AND) 1 1 1

x y NAND
0 0 1
x 0 1 1
x•y 1 0 1
y
1 1 0
 Logic Operators
• OR x y OR
0 0 0
x x+y 0 1 1
y 1 0 1
• NOR (Not OR) 1 1 1

x y NOR
0 0 1
x 0 1 0
x+y 1 0 0
y
1 1 0
 Logic Operators
• XOR (Exclusive-OR) x y XOR
0 0 0
x xÅ y 0 1 1
y xy+xy 1 0 1
• XNOR (Exclusive-NOR) 1 1 0
(Equivalence)

x y XNOR
0 0 1
0 1 0
1 0 0
x xÅ y xy+xy
y 1 1 1
x y
 Logic Operators
• NOT (Inverter)
x NOT

0 1
x x
• Buffer 1 0

x Buffer

0 0
x x
1 1
Multiple Input Gates



DeMorgan’s Theorem on Gates