Senin, 19 Mei 2014

Penyederhanaan dengan metode Quine McCluskey terhadap fungsi SOP




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: