Dengan Peta Karnaugh, penyelesaian persamaan lebih dari
empat variabel adalah kompleks. Metode tabulasi dari Quine-Mc.Cluskey dapat
membantuk menyelesaiakan persamaan yang kompleks tersebut.
Metode tabulasi Quine-Mc.Cluskey terdiri dari dua bagian,
yaitu :
a. Menentukan term-term sebagai kandidat
(prime implicant)
b. Memilih prime implicant untuk menentukan
ekspresi dengan jumlah literal sedikit.
Contoh kasus :
Sederhanakan F(w,x,y,z) = ∑m(0,2,3,6,7,8,9,10,13)
Langkah – langkahnya adalah sebagai berikut :
A. Menentukan term-term sebagai
kandidat (prime implicant)
A.1.Susun tabel minterm, bentuk biner dari minterm, dan banyaknya angka 1 pada kode biner tersebut.
|
Minterm
|
Bentuk biner
|
Jumlah angka 1
|
|
m0
|
0000
|
0
|
|
m2
|
0010
|
1
|
|
m3
|
0011
|
2
|
|
m6
|
0110
|
2
|
|
m7
|
0111
|
3
|
|
m8
|
1000
|
1
|
|
m9
|
1001
|
2
|
|
m10
|
1010
|
2
|
|
m13
|
1101
|
3
|
|
Kelompok
|
Jumlah angka 1
|
Minterm
|
Bentuk biner
|
|
0
|
0
|
m0
|
0000
|
|
1
|
1
1
|
m2
m8
|
0010
1000
|
|
2
|
2
|
m3
|
0011
|
|
2
2
2
|
m6
m9
m10
|
0110
1001
1010
|
|
|
3
|
3
3
|
m7
m13
|
0111
1101
|
A.2.Urutkan dan kelompokkan data pada tabel diatas berdasarkan jumlah angka 1 yang terdapat pada kode
binernya.
A.3.Pasangkan dua buah minterm dengan ketentuan sebagai berikut :
- Kedua minterm tersebut hanya memiliki perbedaan 1 digit pada kode binernya
- Kedua minterm harus dari 2 kelompok yang berbeda dan dari kelompok yang berurutan
- Mengganti digit yang berbeda dengan tanda “-” dan hasil pasangan yang didapatkan kita
masukkan ke tabel baru yang disebut tabel “Kubus-1”
Contoh 1 :
m0 (0000) dan m2 (0010) BOLEH dipasangkan.
Karena :
·
memiliki perbedaan 1 digit pada kode binernya yaitu digit 2-an
·
m0 dan m2 berasal dari dua kelompok
yang berurutan yaitu kelompok-0 dan
kelompok-1
·
sebagai hasil
pemasangannya adalah 00-0 (pada digit yang berbeda
diganti dengan -)
·
setiap kali kita menyusun
pasangan, jangan lupa untuk memberikan
tanda ( √ ) pada
minterm yang terlibat, tanda ini sebagai
pengingat bahwa minterm tersebut pernah dipasangkan.
Secara keseluruhan pasangan yang BOLEH dilakukan antara lain :
|
Pasangan minterm
|
Hasil pasangan
|
|
m0 (kelompok 0)
m2 (kelompok 1)
|
0000
0010
00 -0
|
|
m0 (kelompok 0)
m8 (kelompok 1)
|
0000
1000
-000
|
|
m2 (kelompok 1)
m3 (kelompok 2)
|
0010
0011
001-
|
|
m2 (kelompok 1)
m6 (kelompok 2)
|
0010
0110
0-10
|
|
m2 (kelompok 1)
m10 (kelompok 2)
|
0010
1010
-010
|
|
m8 (kelompok 1)
m9 (kelompok 2)
|
1000
1001
100-
|
|
m8 (kelompok 1)
m10 (kelompok 2)
|
1000
1010
10-0
|
|
m3 (kelompok 2)
m7 (kelompok 3)
|
0011
0111
0-11
|
|
m6 (kelompok 2)
m7 (kelompok 3)
|
0110
0111
011-
|
|
m9 (kelompok 2)
m13 (kelompok 3)
|
1001
1101
1-01
|
|
Kelompok
|
Jumlah angka 1
|
Minterm
|
Bentuk biner
|
tanda
|
|
0
|
0
|
m0
|
0000
|
√
|
|
1
|
1
1
|
m2
m8
|
0010
1000
|
√
√
|
|
2
|
2
|
m3
|
0011
|
√
|
|
2
2
2
|
m6
m9
m10
|
0110
1001
1010
|
√
√
√
|
|
|
3
|
3
3
|
m7
m13
|
0111
1101
|
√
√
|
Catatan :
O Tidak boleh memasangkan 2 buah minterm yang memiliki
perbedaan lebih dari 1 digit Pada kode binernya.
O Tidak boleh
mernasangkan 2 buah
minterm yang berasal dari dua kelompok yang tidak berurutan
Dari pemasangan yang dilakukan akan didapatkan table minterm dan table
kubus-1 sebagai berikut :
|
Tabel Kubus-1
|
|
|
m0,m2
m0,m8
|
00-0
-000
|
|
m2,m3
m2,m6
m2,m10
m8,m9
m8,m10
|
001-
0-10
-010
100-
10-0
|
|
m3,m7
m6,m7
|
0-11
011-
|
|
m9,m13
|
1-01
|
Lakukan
pemasangan serupa terhadap
data hasli yang tertera
pada kubus-1 dan tuliskan
hasilnya pada kubus 2.
|
Kubus-1
|
||
|
m0,m2
m0,m8
|
00-0
-000
|
√
√
|
|
m2,m3
m2,m6
m2,m10
m8,m9
m8,m10
|
001-
0-10
-010
100-
10-0
|
√
√
√
**
√
|
|
m3,m7
m6,m7
m9,m13
|
0-11
011-
1-01
|
√
√
**
|
Catatan :
Tanda bintang
( ** ) menandakan bahwa minterm tersebut belum
pernah mendapat pasangan pada proses membentukan tabel kubus berikutnya.
Minterm ini dinamakan sebagai
Prime Implicant.
|
Kubus-2
|
|
|
m0,m2 & m8,m10
|
-0-0
|
|
m0,m8 & m2,m10
|
-0-0
|
|
m2,m3 & m6,m7
|
0-1-
|
|
m2,m6 & m3,m7
|
0-1-
|
|
Kubus-2
|
|
|
m0,m2 & m8,m10
|
-0-0
|
|
m2,m3 & m6,m7
|
0-1-
|
Jika pasangan minterm
menghasilkan kode biner yang sama
maka cukup ditulis salah satu saja. Sehingga tabel kubus-2 menjadi :
A.4.
Jika masih
menungkinkan lakukan pemasangan lagi
terhadap data pada kubus-kubus berikutnya hingga
tidak ada lagi data pada kubus
terakhir yang bisa dipasangkan lebih lanjut.
A.5.
Jika sudah tidak ada lagi yang bisa dipasangkan seperti pada kubus-2, sebenarnya kita sudah mendapatkan prime
implikant.
|
Kubus-2
|
|
|
|
m0,m2 & m8,m10
|
-0-0
|
**
|
|
m2,m3 & m6,m7
|
0-1-
|
**
|
Pada contoh ini kita mendapatkan 4 prime implicant yaitu :
m8,m9 → 1 0 0
-
m9,m13 → 1 -
0 1
m0,m2 & m8,m10 → - 0 - 0
m2,m3 & m6,m7 → 0 -
1 -
B. Memilih prime implicant
untuk menentukan ekspresi dengan jumlah literal sedikit
B.1 Susun tabel prime implicant (lihat tabel berikut ini).
|
Flag
|
Prime Implicant
|
m0
|
m2
|
m3
|
m6
|
m7
|
m8
|
m9
|
m10
|
m13
|
|
|
m0,m2 & m8,m10
|
*
|
*
|
|
|
|
*
|
|
*
|
|
|
|
m2,m3 & m6,m7
|
|
*
|
*
|
*
|
*
|
|
|
|
|
|
|
m8,m9
|
|
|
|
|
|
*
|
*
|
|
|
|
|
m9,m13
|
|
|
|
|
|
|
*
|
|
*
|
|
|
|
|
|
|
|
|
|
|
|
|
B.2 Beri tanda ‘√‘ pada kolom flag untuk kelompok prime implicant yang memiliki kolom bertanda * satu buah saja
|
Flag
|
Prime Implicant
|
m0
|
m2
|
m3
|
m6
|
m7
|
m8
|
m9
|
m10
|
m13
|
|
√
|
m0,m2 & m8,m10
|
ê
|
*
|
|
|
|
*
|
|
ê
|
|
|
√
|
m2,m3 & m6,m7
|
|
*
|
ê
|
ê
|
ê
|
|
|
|
|
|
|
m8,m9
|
|
|
|
|
|
*
|
*
|
|
|
|
√
|
m9,m13
|
|
|
|
|
|
|
*
|
|
ê
|
|
|
|
|
|
|
|
|
|
|
|
|
Catatan : pada kelompok prime implicant
m8, m9 tidak diberi
tanda ‘ê’ karena tidak memiliki kolom yang
hanya memua t satu
tanda ‘* ’
B.3 Prime Implicant yang memiliki tanda ‘ê ‘ adalah yang terpilih untuk penyusunan fungsi boolean yang dimaksud.
Susun fungsi boolean berdasarkan prime implicat yang terpilih, yaitu :
m0,m2 & m8,m10 : - 0 – 0
→ x’ z’
m2,m3 & m6,m7 :
0 – 1
- → w’y
m9,m13 : 1 – 0 1 → wy’z
Jadi fungsi boolean yang dimaksud adalah :
F(w,x,y,z) = x’ z’ + w’y + wy’z
0 komentar:
Posting Komentar