Overview
Logic and Computer Design Fundamental
Bagian 1 – Rangkaian Gerbang dan Persamaan Boolean.
Chapter h 2 Rangkaian Logika Kombinasi Bagian 1 : Rangkaian Gerbang dan P Persamaan Boolean B l
• Logika Biner dan Gerbang • Aljabar Boolean • Standard Forms
Bagian 2 – Optimasi Rangkaian • • • •
Optimasi 2 – level Manipulasi Peta Optimasi Praktis (Espresso) Optimasi Rangkaian Multi-Level
Bagian g 3 – Gerbang2 g tambahan dan rangkaian g
M. Mano M M & Charles Ch l R. R Kime Ki 2008,, Pearson Education,, Inc
• Tipe2 gerbang yang lain • Operator Exclusive-OR dan Gerbang • Outputs High-Impedance High Impedance
1 Chapter 2 - Part 1
Variabel Biner.
Logika Biner dan Gerbang Variabel Biner : salah satu dari 2 nilai Operator Logika : Beroperasi pada nilai biner dan variabel biner. Dasar operator logika adalah merupakan fungsi logika AND, OR and NOT. Gerbang Logika mengimplementasikan fungsi logika Aljabar Boolean : Suatu sistem matematika yang sangat berguna untuk menspesifikasikan dan mentransformasikan fungsi Aljabar Boolean dipakai sebagai dasar untuk mendesain dan menganalisa sistem digital.
Chapter 2 - Part 1
2
Dua nilai biner disebut dengan beberapa nama berbeda: • True/False • On/Off • Yes/No • 1/0 Digunakan Di k 1d dan 0 untuk t k menyatakan t k 2 nilai. il i ContohVariable identifier : • A, B, y, z, or X1 • RESET, START_IT, atau ADD1 (y.a.d) 3
Chapter 2 - Part 1
4
Contoh:
Operasi Logikal Tiga dasar operasi logikal adalah:
Contoh: • Y = A ⋅ B dibaca “Y adalah : A AND B.” • z = x + y dibaca i “z “ adalah : x OR O y.”” • X = A dibaca “X adalah : NOT A.”
• AND • OR • NOT
AND dinyatakan dengan titik (·). OR dinyatakan dengan tambah (+). (+) NOT dinyatakan dengan overbar ( ¯ ), single quote mark (') sesudah, atau (~) sebelum variabel. Chapter 2 - Part 1
Catatan: Pernyataan: 1 + 1 = 2 (dibaca (dib ““one plus l one equals l two”) t ”)
tidak sama dengan g : 1 + 1 = 1 (read “1 or 1 equals 1”).
5
Truth table − Suatu daftar tabular dari nilai suatu fungsi untuk semua kemungkinan kombinasi. Contoh: Truth tables untuk operasi dasar :
Operasi penerapan untuk nilai "0" and "1" untuk masing2 operator :
0·0=0 0·1=0 1·0=0 1·1=1
6
Truth Tables/Tabel Kebenaran
Definisi e s Operator Ope o
AND
Chapter 2 - Part 1
OR
NOT
0+0=0 0+1=1 1+0=1 1+1=1
0=1 1=0
X 0 0 1 1 Chapter 2 - Part 1
7
AND Y Z = X·Y 0 0 1 0 0 0 1 1
X 0 0 1 1
Y 0 1 0 1
OR Z = X+Y 0 1 1 1
NOT X 0 1
Z=X 1 0
Chapter 2 - Part 1
8
Implementasi Fungsi Logika. MenggunakanSwitch gg
Implementasi Fungsi Logika. (Continued) Contoh: Logic Using Switches
Switches in parallel => OR
B
• Untuk inputs: logic 1 is switch closed logic 0 is switch open
• Untuk outputs: logic 1 is light on logic g 0 is light g off.
D
Switches in series => AND
Lampu nyala (L = 1) untuk: L(A, B, C, D) = Dan bila tidak, mati (L = 0). Model yang berguna untuk rangk relay dan untuk rangk gerbang CMOS , merupakan dasar dari teknologi logika digital saat ini.
• NOT menggunakan switch Normally-closed switch => NOT seperti: logic 1 is switch open logic og c 0 iss sw switch tc closed c osed
C
A
C
Chapter 2 - Part 1
9
Chapter 2 - Part 1
10
Simbol Gerbang Logika dan perilakunya perilakunya.
Gerbang Logika(Logic Gates)
Gerbang Logika mempunyai simbol khusus, X
Pada awal komputer, switches terbuka dan tertutup gg medan magnit g yyang g dihasilkan oleh menggunakan energi dari koil pada relays. Switches secara bergantian membuka dan menutup jalan arus. Kemudian, vacuum tubes membuka dan menutup jalan arus secara elektronik, menggantikan relays. Saat S iini, i transistors i di k i sebagai dipakai b i electronic l i switches i h yang membuka dan menutup jalannya arus. Optional: O ti l Chapter Ch t 6 – Part P t 1: 1 The Th Design D i Space S
Chapter 2 - Part 1
Z 5 X ·Y
Y
X
Z5 X1 Y
Y
X NOT gate or inverter
OR gate
AND gate
Z5 X
(a) Graphic symbols
And waveform behavior in time as follows: X
0
0
1
1
Y
0
1
0
1
X ·Y
0
0
0
1
(OR)
X1 Y
0
1
1
1
(NOT)
X
1
1
0
0
(AND)
11
(b) Timing diagram
Chapter 2 - Part 1
12
Delay pada Gerbang .
Diagram Logika dan Ekspresi-nya.
Secara aktual, physical gates, bila satu atau lebih input berubah menyebabkan output berubah, perubahan tersebut tidak terjadi secara instan. perubahan input p dan p perubahan Delayy antara p hasil output adalah gate delay dinyatakan : tG Input
1 0
1 Output 0 0
tG
tG
XYZ 000 001 010 011 100 101 110 111
tG = 0.3 ns
1.5
1
0.5
Tabel Kebenaran
Time (ns) Chapter 2 - Part 1
13
F = X + Y ⋅Z 0 1 0 X 0 1 Y 1 1 Z 1
Persamaan:
F = X +Y Z Diagram Logika
F
Persamaan Boolean Boolean, tabel kebenaran dan Diagram Logika mentayakan Fungsi yang sama! Tabel Kebenaran adalah unik; ekspresi dan diagram logika tidak. id k Ini I i memberikan b ik fleksibilitas fl k ibili dalam d l implementasi i l i fungsi. Chapter 2 - Part 1
Aljabar Boolean
Beberapa p p properti p dari identitas dan Aljabar. j
If the meaning is unambiguous, we leave out the symbol “·”
Struktur Aljabar didefinisikan pada satu set atau minimum 2 elemen, B, dengan tiga operator biner (denoted +, · and ) yang dirumuskan secara mendasar sbb:
1.
X+0= X
2.
X .1 =X
3.
X+1 =1
4.
X .0 =0
5 5.
X+X =X
6 6.
X .X = X
7.
X+X =1
8.
X .X = 0
9 9.
X=X
10. X + Y = Y + X 12. (X + Y) + Z = X + (Y + Z) 14. X(Y + Z) = XY + XZ 16. X + Y = X . Y
The identities above are organized into pairs. These pairs have names as follows: 1-4 Existence of 0 and 1 5-6 Idempotence 7-8 Existence of complement 9 Involution 10-11 Commutative Laws 12-13 Associative Laws 14-15 Distributive Laws 16-17 DeMorgan’s Laws
11. XY = YX Commutative Associative 13. (XY) ( ) Z = X(YZ) ( ) Distributive 15. X + YZ = (X + Y) (X + Z) DeMorgan’s 17. X . Y = X + Y
Chapter 2 - Part 1
14
15
“Dual” dari ekspresi suatu ekspresi aljabar didapat dengan de ga menggantikan e gga t a + and a d · da dan menggantikan e gga t a 00’ss da dan 1’s.
Chapter 2 - Part 1
16
Beberapa properti dari identitas dan Aljabar. (Continued)
Beberapa properti dari identitas dan Aljabar. (Continued)
Contoh : F = (A + C) · B + 0 dual F = (A · C + B) · 1 = A · C + B Contoh : G = X · Y + (W + Z) d lG= dual Contoh : H = A · B + A · C + B · C dual H = self dual? Are any of these functions self-dual?
Chapter 2 - Part 1
Kemungkinan dapat lebih dari 2 elemen in B, yaitu elemen selain1 and 0. Umumnya disebut apa Aljabar Boolean dengan lebih dari 2 elemen? g of Sets Algebra Algebra of n-bit binary vectors
Bika B terdiri hanya 1 dan 0, maka B disebut switching algebra yang merupakan aljabar yang sering digunakan.
17
Operator Ope o Boolean oo e
Chapter 2 - Part 1
18
Contoh 1: Pembuktian Aljabar j Boolean
Urutan Evaluasi pada Ekspresi Boolean adalah : 1 Parentheses/kurung 1. P th /k 2. NOT 3 AND 3. 4. OR Akibatnya: Kurung muncul sekitar ekspresi OR Contoh : F = A(B + C)(C + D) Chapter 2 - Part 1
19
A + A·B = A Proof Steps A + A·B
(Absorption Theorem) Justification (identity or theorem)
= A·1+A·B = A · ( 1 + B)
X=X·1
= A·1 = A
X · Y + X · Z = X ·(Y + Z)(Distributive Law) 1+X=1 X·1=X
Alasan melakukan pembuktian untuk mempelajari: • Ber Ber-hati2 hati2 dan secara efisien menggunakan rumus dan teorema Aljabar Boolean. • Bagaimana memilih identitas dan teorema yang cocok untuk diterapkan untuk melanjutkan penyelesaian berikutnya diterapkan, berikutnya. Chapter 2 - Part 1
20
Contoh 2: Pembuktian Aljabar j Boolean
Contoh 3: Pembuktian Aljabar j Boolean
AB + AC + BC = AB + AC (Consensus Theorem) Proof Steps Justification (identity or theorem) AB + AC + BC = AB + AC + 1 · BC ? = AB +AC + (A + A) · BC ? = (lanjutkan!)
Chapter 2 - Part 1
21
Teorema eo e yang y g berguna. be gu .
x ⋅ y + x ⋅ y = y (x + y )(x + y )= y x + x⋅y = x x ⋅ (x + y ) = x
( X + Y ) Z + X Y = Y( X + Z ) Proof Steps Justification (identity or theorem) ( X + Y )Z + X Y = (lanjutkan!)
Chapter 2 - Part 1
22
Pembuktian dengan g p penyederhanaan. y
x⋅y + x⋅y = y
Minimizatio i i i ti n Absorption
(x + y )(x + y ) = y
x + x ⋅ y = x + y x ⋅ (x + y )= x ⋅ y Simplification x⋅y + x⋅z + y⋅z = x⋅y + x⋅z Consensus (x + y )⋅ (x + z )⋅ (y + z ) = (x + y )⋅ (x + z ) x + y = x⋅y
x⋅y = x + y
DeMorgan' s Laws
Chapter 2 - Part 1
23
Chapter 2 - Part 1
24
Evaluasi Fungsi Boolean
Proof oo of o DeMorgan’s e o g s Laws ws
x + y = x⋅y
F1 = xy yz F2 = x + yz F3 = x y z + x y z + x y F4 = x y + x z
x⋅y = x + y
Chapter 2 - Part 1
x 0 0 0 0 1 1 1 1
y 0 0 1 1 0 0 1 1
z F1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0
25
F2 0 1 0 0 1 1 1 1
F3
F4
Chapter 2 - Part 1
26
Fungsi Complemen
Penyederhanan e yede Ekspresi sp es Suatu Penerapan p Aljabar j Boolean Sederhanakan agar didapat jumlah literal terkecil. terkecil (variabel complemen dan tidak complemen):
Gunakan Teorema DeMorgan DeMorgan'ss untuk mengkomplemen-kan fungsi: 11. S Saling li ditukar dit k operators t AND dan d OR 2. Komplemen-kan masing2 nilai konstan dan literal. Contoh:Komplemen-kan Contoh:Komplemen kan F = xy z + x y z
A B + ACD + A BD + AC D + A BCD = AB + ABCD + A C D + A C D + A B D = AB + AB(CD) + A C (D + D) + A B D = AB + A C + A B D = B(A + AD) +AC = B (A + D) + A C 5 literals Chapter 2 - Part 1
F = ((x + y + z)(x )( + y + z)) Contoh:Komplemen-kan G = (a + bc)d + e
G= 27
Chapter 2 - Part 1
28
Overview Bentuk Fungsi Kanonik
Bentuk e u Kanonik o Sangat berg berguna na untuk nt k menspecif menspecify F Fungsi ngsi Boolean dalam bentuk seperti:
A Apa it itu B Bentuk t kK Kanonik? ik? Minterms and Maxterms Index Merepresentasikan Minterms dan Maxterms Representasi Sum-of-Minterm (SOM) Representasi Product-of-Maxterm (POM) Representasi R t i Fungsi F i Komplemen K l p Konversi antar Representasi Chapter 2 - Part 1
• Allows comparison for equality. • Has a correspondence to the truth tables
Bentuk Kanonik yang umum digunakan : • S Sum off Minterms i (SOM) (SO ) = Sum S off Product (SOP) • Product of Maxterms (POM)= Product of Sum (POS) 29
Minterms
30
Maxterms
Minterms adalah AND terms dengan adanya setiap variabel baik itu ‘true’ true atau bentuk komplemen form. Diketahui masing2 variabel biner adalah normal (e.g., x) atau komplemen (e.g.,x), maka ada 2n minterms untuk n variable. Contoh: Dua variable (X and Y) akan didapat 2 x 2 = 4 kombinasi:
XY XY XY XY
Chapter 2 - Part 1
Maxterms adalah OR terms dengan g setiap p variable ‘true’ atau bentuk complemen . g variabel biner adalah Diketahui masing2 normal (e.g., x) atau komplemen (e.g., x), maka ada 2n maxterms untuk n variable. Contoh: Dua variable (X and Y) menghasilkan 2 x 2 = 4 kombinasi: X + Y (both normal) p ) X + Y ((x normal, y complemented) X + Y (x complemented, y normal) X + Y (both complemented)
(both normal) (X normal, Y complemented) (X complemented, Y normal) ((both complemented) p )
Berarti ada empat minterms dari dua variabel. Chapter 2 - Part 1
31
Chapter 2 - Part 1
32
Maxterms and Minterms
Urutan Standard.
Contoh: Dua variable minterms dan maxterms. Index
Minterm
Maxterm
0
xy
x+y
1
xy
x+y
2
xy
x+y
3
xy
x+y
Indeks diatas sangat penting untuk menentukan variabel yang mana dalam terms tersebut ‘true’ dan yang mana komplemen. Chapter 2 - Part 1
33
Tujuan dari Index
Minterms dan maxterms didisain dengan subscript Subscript S b i t adalah d l h angka k , ttergantung t pada d bi binary pattern-nya tt Bit pada pattern menyatakan komplemen atau kondisi normal untuk masing2 variable yang ditulis dalam urutan standard. Semua variabel akan ada dalam minterm atau maxterm dan akan ditulis dalam urutan yang sama (umumnya alphabetically) Contoh: Untuk variable aa, b b, c: • Maxterms: (a + b + c), (a + b + c) c) a c b, b dan (c + b + a) TIDAK dalam • Terms: (b + a + c), urutan standard. • Minterms: a b c, a b c, a b c • Terms: (a + c), b c, and (a + b) tidak terdiri dari semua variables Chapter 2 - Part 1 34
Contoh Index untuk Tiga Variabel
Index untuk minterm atau maxterm,, menyatakan sebagai bil biner, yang dipakai untuk menentukan apakah p variable yyang g ada bentuk ‘true’ atau bentuk komplemen. Untuk Minterms:
• “1” berarti var ini “Bukan komplemen” dan • “0” 0 berarti var ini “Komplemen” Komplemen .
Untuk Maxterms:
• • • •
• “0” b berartii var ini i i “Bukan “B k komplemen” k l ” dan d • “1” berarti var ini “Komplemen”. Chapter 2 - Part 1
Contoh: ((Untuk tiga g variabel)) Misalkan Variabel tersebut adalah : X, Y, and Z. Urutan standard-nya standard nya adalah : X X, then Y Y, then Z Z. Index 0 (basis 10) = 000 (basis 2) untuk tiga variables). i ) Ketiga i var tersebut adalah komplemen utk minterm 0 ( X , Y, Z ) dan tidak ada var yang k komplemen l untuk k Maxterm M 0 (X,Y,Z). )
35
Minterm 0, disebut m0 = X Y Z . Maxterm 0, disebut M0 = (X + Y + Z). Minterm 6 ? Maxterm 6 ? Chapter 2 - Part 1
36
Contoh Indeks– Empat Variable. Index i 0 1 3 5 7 10 13 15
Hubungan Minterm and Maxterm
Binary Minterm Maxterm Pattern mi Mi 0000 abcd a + b + c + d 0001 ? abcd 0011 ? a+b+c+d 0101 abcd a + b + c + d 0111 ? a+b+c+d 1010 abcd a + b + c + d ? 1101 abcd 1111 abcd a + b + c + d
Mengulangi: g g DeMorgan's g Theorem x · y = x + y and x + y = x ⋅ y Contoh Dua Variabel: M 2 = x + y dan m 2 = x·y Jadi M2 adalah komplemen dari m2 dan sebaliknya. Bila DeMorgan's Theorem terdiri dari n variabel, maka k tterm di diatas t jjuga tterdiri di i dari d i n variabel. i b l Bila :
m0 1 0 0 0
m1 m2 m3 0 0 0 1 0 0 0 1 0 0 0 1
mi = M i
37
Chapter 2 - Part 1
38
Observasi
Tabel Fungsi ke-dua2-nya.
xy 00 01 10 11
dan
Maka Mi adalah komplemen dari mi. Chapter 2 - Part 1
Minterms dari 2 variabel
Mi = mi
Pada Tabel fungsi:
Maxterms dari 2 variabel x y M0 00 0 01 1 10 1 11 1
M1 1 0 1 1
M2 1 1 0 1
• Masing2 minterm mempunyai satu dan hanya satu, satu 1 berada pada 2n terms ( minimum dari 1s). Selain itu adalah 0. • Masing2 maxterm mempunyai satu dan hanya satu, 0 berada pada 2n terms ( maximum of 0s). 0s) Selain itu adalah 11.
M3 1 1 1 0
Kita dapat mengimplementasikan dengan "ORing" g memasukkan "1" kedalam tabel minterms dengan fungsi. Ini disebut Fungsi dari minterm. Kita dapat mengimplementasikan dengan "ANDing" maxterms t d dengan memasukkan kk "0" k kedalam d l ttabel b l fungsi. Ini disebut Fungsi dari maxterm. Jadi ada dua bentuk kanonik:
Masing2 kolom pada tabel fungsi maxterm adalah komplemen dari kolom tabel fungsi minterm, maka k Mi adalah d l h komplemen k l dari d i mi. Chapter 2 - Part 1
• Sum of Minterms (SOM) – Jumlah sukumin • Product of Maxterms (POM) – Hasil kali sukumax
untuk menyatakan Fungsi Boolean. 39
Chapter 2 - Part 1
40
Contoh Fungsi Minterm
Contoh Fungsi Minterm
Example: Find F1 = m1 + m4 + m7 F1 = x y z + x y z + x y z
F(A, ( , B,, C,, D,, E)) = m2 + m9 + m17 + m23 F(A, B, C, D, E) =
x y z index i d m1 + m4 + m7 = F1 000
0
0
+
0
+
0
=0
001
1
1
+
0
+
0
=1
010
2
0
+
0
+
0
=0
011
3
0
+
0
+
0
=0
100
4
0
+
1
+
0
=1
101
5
0
+
0
+
0
=0
110
6
0
+
0
+
0
=0
111
7
0
+
0
+
1
=1
Chapter 2 - Part 1
41
Contoh Fungsi Maxterm
Chapter 2 - Part 1
44
F( A , B, C, D) = M 3 ⋅ M8 ⋅ M11 ⋅ M14 F(A, B,C,D) =
F1 = ((x + y + z)) ·(x ( + y + z)·(x ) ( + y + z) ·( x + y + z )·( x + y + z) i 0 1 2 3 4 5 6 7
42
Contoh Fungsi g Maxterm
Contoh: Implementasikan F1 dalam maxterms: F1 = M0 · M2 · M3 · M5 · M6
xyz 000 001 010 011 100 101 110 111
Chapter 2 - Part 1
M0 ⋅ M2 ⋅ M3 ⋅ M5 ⋅ M6 0 ⋅ 1 ⋅ 1 ⋅ 1 ⋅ 1 1 ⋅ 1 ⋅ 1 ⋅ 1 ⋅ 1 1 ⋅ 0 ⋅ 1 ⋅ 1 ⋅ 1 1 ⋅ 1 ⋅ 0 ⋅ 1 ⋅ 1 1 ⋅ 1 ⋅ 1 ⋅ 1 ⋅ 1 1 ⋅ 1 ⋅ 1 ⋅ 0 ⋅ 1 1 ⋅ 1 ⋅ 1 ⋅ 1 ⋅ 0 1 ⋅ 1 ⋅ 1 ⋅ 1 ⋅ 1
= F1 =0 =1 =0 =0 =1 =0 =0 =1
Chapter 2 - Part 1
43
Another SOM Example
Kanonikal Jumlah dari Minterms
Example: p F=A+BC There are three variables, A, B, and C which we take to be the standard order. Expanding the terms with missing variables:
Setiap fungsi Boolean dapat dinyatakan dalam : Sum of Minterms. • For the function table, the minterms used are the t terms corresponding di to t the th 1' 1's • For expressions, expand all terms first to explicitly list all minterms. minterms Do this by “ANDing” ANDing any term missing a variable v with a term (v + v ).
f = x + x y as a sum of Example: p Implement p minterms. First expand terms: f = x ( y + y ) + x y Then distribute terms: f = xy + x y + x y
C Collect ll t terms t (removing ( i all ll but b t one off duplicate d li t terms): Express E as SOM SOM:
Express as sum of minterms: f = m3 + m2 + m0 Chapter 2 - Part 1
45
Shorthand SOM Form
Chapter 2 - Part 1
46
Canonical Product of Maxterms Any Boolean Function can be expressed as a Product of Maxterms (POM). (POM)
From the p previous example, p , we started with: F=A+BC We ended up with: F = m1+m4+m5+m6+m7 This can be denoted in the formal shorthand: F( A , B, C) = Σm(1,4,5,6,7 ) Note that we explicitly show the standard variables in order and drop the “m” m designators.
• For the function table, the maxterms used are the terms corresponding to the 0's. • For an expression, expand all terms first to explicitly list all maxterms. Do this by first applying the second distributive law , “ORing” terms missing variable v with a term equal to and d then h applying l i the h di distributive ib i llaw again. i
v⋅ v
Example: Convert to product of maxterms:
f ( x, y , z ) = x + x y
Apply
the distributive law:
x + x y = ((x + x )( )(x + y ) = 1 ⋅ ((x + y ) = x + y
Add missing variable z:
x + y + z ⋅ z = ( x + y + z ) (x + y + z )
Express as POM: f = M2 · M3 Chapter 2 - Part 1
47
Chapter 2 - Part 1
48
Another POM Example
Function Complements
Convert to Product of Maxterms: f(A, B, C) = A C + B C + A B Use x + y z = (x+y)·(x+z) ( y) ( ) with x = ((A C + B C), ), y = A , and z = B to get: f = ((A C + B C + A )( )(A C + B C + B) Then use x + x y = x + y to get: f = ( C + BC + A )(A C + C + B ) and a second time to get: f = ( C + B + A )(A + C + B ) Rearrange to standard order, t give i f = M5 · M2 f = ( A + B + C)(A + B + C) to Chapter 2 - Part 1
The complement p of a function expressed p as a sum of minterms is constructed by selecting the minterms missingg in the sum-of-minterms canonical forms. Alternatively, Alternatively the complement of a function expressed by a Sum of Minterms form is simply the Product of Maxterms with the same indices indices. Example: Given F ( x , y , z ) = Σm ( 1, 3 , 5 , 7 )
F( x, y , z ) = Σm( 0, 2,4,6) F( x, y , z ) = ΠM(1, 3,5,7 )
49
Chapter 2 - Part 1
Conversion Between Forms
Standard Forms
To convert between sum-of-minterms and productp of-maxterms form (or vice-versa) we follow these p steps:
Standard Sum-of-Products ((SOP)) form: equations are written as an OR of AND terms Standard Product-of-Sums (POS) form: equations are written as an AND of OR terms Examples: • SOP: A B C + A B C + B • POS: POS (A + B) · (A+ B + C )· C These “mixed” forms are neither SOP nor POS • (A B + C) (A + C) • A B C + A C (A + B)
• Find the function complement by swapping terms in the list with terms not in the list. • Change from products to sums, or vice versa.
Example:Given F as before: F( x , y , z ) = Σm(1, 3,5,7 ) Form the Complement: F( x, y , z ) = Σm( 0, 2,4,6) Then Th use the th other th form f with ith th the same iindices di – this thi forms the complement again, giving the other form off th the original i i l function: f ti F( x, y , z ) = ΠM( 0, 2,4,6) Chapter 2 - Part 1
51
Chapter 2 - Part 1
50
52
Standard Sum-of-Products (SOP) A sum of minterms form for n variables can be written down directly from a truth table.
A Simplification p Example: p F( A , B, C) = Σm(1,4,5,6,7 ) Writing the minterm expression: F = A B C + A B C + A B C + ABC + ABC Simplifying: F=
• Implementation of this form is a two-level network of gates such that: • The first level consists of n-input AND gates, and • The second level is a single OR gate (with fewer than 2n inputs).
This form often can be simplified so that the corresponding circuit is simpler simpler. Chapter 2 - Part 1
Simplified F contains 3 literals compared to 15 in minterm F 53
AND/OR Two-level Implementation of SOP Expression
A
Chapter 2 - Part 1
54
SOP and POS Observations The p previous examples p show that:
The two implementations p for F are shown below – it is quite apparent which is simpler! A B C A B C A B C A B C A B C
Standard Sum-of-Products Sum of Products (SOP)
• Canonical Forms (Sum-of-minterms, Product-ofMaxterms), or other standard forms (SOP, POS) diff in differ i complexity l it • Boolean algebra can be used to manipulate equations into simpler forms. • Simpler equations lead to simpler two-level implementations
F
B C
F
Questions: • How can we attain a “simplest” expression? • Is there only one minimum cost circuit? • The next part will deal with these issues. Chapter 2 - Part 1
55
Chapter 2 - Part 1
56
Terms e s oof Use
Logic and Computer Design Fundamental
All (or portions) of this material © 2008 by Pearson Education, Inc. Permission is given to incorporate this material or adaptations thereof into classroom presentations and handouts to instructors in courses adopting the latest edition of Logic and Computer Design Fundamentals as the course textbook. These materials or adaptations thereof are not to be sold or otherwise offered for consideration consideration. This Terms of Use slide or page is to be included within g materials or anyy adaptations p thereof. the original
Chapter h 2 Rangkaian Logika Kombinasi Bagian 1 : Rangkaian Gerbang dan P Persamaan Boolean B l
M. Mano M M & Charles Ch l R. R Kime Ki 2008,, Pearson Education,, Inc 58
Chapter 2 - Part 1
Logic and Computer Design Fundamental
Chapter 1 Digital i i l andd Computer Information f i
M. Mano & Charles R. Kime 2008 Pearson Education, 2008, Education Inc
59
57
