Metode Tabel Quine-McCluskey
Pada bab sebelumnya, kita telah membahas metode K-map, yang merupakan metode yang nyaman untuk meminimalkan fungsi Boolean hingga 5 variabel. Namun, sulit untuk menyederhanakan fungsi Boolean yang memiliki lebih dari 5 variabel dengan menggunakan metode ini.
Metode tabel Quine-McClukey merupakan metode tabel yang didasarkan pada konsep prime implant. Kami tahu ituprime implicant adalah suku produk (atau penjumlahan), yang tidak dapat disederhanakan lagi dengan menggabungkannya dengan suku produk (atau penjumlahan) lainnya dari fungsi Boolean yang diberikan.
Metode tabel ini berguna untuk mendapatkan implikasi utama dengan berulang kali menggunakan identitas Boolean berikut.
xy + xy '= x (y + y') = x.1 = x
Prosedur Metode Tabel Quine-McCluskey
Ikuti langkah-langkah berikut untuk menyederhanakan fungsi Boolean menggunakan metode tabel Quine-McClukey.
Step 1 - Susun suku-suku min yang diberikan dalam ascending orderdan buat grup berdasarkan jumlah yang ada dalam representasi biner mereka. Jadi, akan adaat most ‘n+1’ groups jika ada 'n' variabel Boolean dalam fungsi Boolean atau bit 'n' dalam ekuivalen biner dari istilah min.
Step 2 - Bandingkan istilah min yang ada di successive groups. Jika ada perubahan hanya dalam posisi satu bit, maka ambil pasangan dari dua suku min tersebut. Letakkan simbol '_' ini pada posisi bit yang berbeda dan pertahankan bit yang tersisa sebagaimana adanya.
Step 3 - Ulangi langkah2 dengan istilah yang baru dibentuk sampai kita mendapatkan semua prime implicants.
Step 4 - Merumuskan prime implicant table. Ini terdiri dari kumpulan baris dan kolom. Implikasi utama dapat ditempatkan dalam baris bijaksana dan istilah min dapat ditempatkan dalam kolom bijaksana. Tempatkan '1' di sel yang sesuai dengan istilah min yang tercakup dalam setiap implik utama.
Step 5- Temukan implan utama yang penting dengan mengamati setiap kolom. Jika suku min hanya dicakup oleh satu implikasi utama, maka suku tersebut adalahessential prime implicant. Implikasi utama esensial tersebut akan menjadi bagian dari fungsi Boolean yang disederhanakan.
Step 6- Kurangi tabel prime implant dengan menghilangkan baris dari setiap prime implant esensial dan kolom-kolom yang sesuai dengan istilah min yang tercakup dalam prime implant esensial tersebut. Ulangi langkah 5 untuk tabel Implikasi utama yang dikurangi. Hentikan proses ini ketika semua istilah min dari fungsi Boolean yang diberikan sudah berakhir.
Contoh
Biarkan kami simplify fungsi Boolean berikut, $ f \ left (W, X, Y, Z \ right) = \ sum m \ left (2,6,8,9,10,11,14,15 \ kanan) $ menggunakan Quine-McClukey metode tabel.
Fungsi Boolean yang diberikan ada di sum of min termsbentuk. Ia memiliki 4 variabel W, X, Y & Z. Suku-suku min yang diberikan adalah 2, 6, 8, 9, 10, 11, 14 dan 15. Urutan menaik suku-suku min ini berdasarkan jumlah suku yang ada dalam suku-suku tersebut. ekuivalen biner adalah 2, 8, 6, 9, 10, 11, 14 dan 15. Tabel berikut menunjukkan inimin terms and their equivalent binary representasi.
| Nama grup | Istilah min | W | X | Y | Z |
|---|---|---|---|---|---|
| GA1 | 2 | 0 | 0 | 1 | 0 |
| 8 | 1 | 0 | 0 | 0 | |
| GA2 | 6 | 0 | 1 | 1 | 0 |
| 9 | 1 | 0 | 0 | 1 | |
| 10 | 1 | 0 | 1 | 0 | |
| 11 | 1 | 0 | 1 | 1 | |
| 14 | 1 | 1 | 1 | 0 | |
| GA4 | 15 | 1 | 1 | 1 | 1 |
Suku-suku min yang diberikan disusun menjadi 4 kelompok berdasarkan jumlah suku yang ada dalam persamaan binernya. Tabel berikut menunjukkan kemungkinanmerging of min terms dari kelompok yang berdekatan.
| Nama grup | Istilah min | W | X | Y | Z |
|---|---|---|---|---|---|
| GB1 | 2,6 | 0 | - | 1 | 0 |
| 2,10 | - | 0 | 1 | 0 | |
| 8,9 | 1 | 0 | 0 | - | |
| 8,10 | 1 | 0 | - | 0 | |
| GB2 | 6,14 | - | 1 | 1 | 0 |
| 9,11 | 1 | 0 | - | 1 | |
| 10,11 | 1 | 0 | 1 | - | |
| 10,14 | 1 | - | 1 | 0 | |
| 11,15 | 1 | - | 1 | 1 | |
| 14,15 | 1 | 1 | 1 | - |
Suku-suku min, yang hanya dibedakan dalam posisi satu-bit dari kelompok yang berdekatan digabungkan. Bit yang berbeda itu diwakili dengan simbol ini, '-'. Dalam kasus ini, ada tiga kelompok dan setiap kelompok berisi kombinasi dari dua suku min. Tabel berikut menunjukkan kemungkinanmerging of min term pairs dari kelompok yang berdekatan.
| Nama grup | Istilah min | W | X | Y | Z |
|---|---|---|---|---|---|
| GB1 | 2,6,10,14 | - | - | 1 | 0 |
| 2,10,6,14 | - | - | 1 | 0 | |
| 8,9,10,11 | 1 | 0 | - | - | |
| 8,10,9,11 | 1 | 0 | - | - | |
| GB2 | 10,11,14,15 | 1 | - | 1 | - |
| 10,14,11,15 | 1 | - | 1 | - |
Grup pasangan istilah min yang berurutan, yang dibedakan hanya dalam posisi satu bit akan digabungkan. Bit yang berbeda itu diwakili dengan simbol ini, '-'. Dalam kasus ini, ada dua kelompok dan setiap kelompok berisi kombinasi empat suku min. Di sini, kombinasi istilah 4 menit ini tersedia dalam dua baris. Jadi, kami dapat menghapus baris yang berulang. Tabel yang dikurangi setelah menghapus baris yang berlebihan ditampilkan di bawah ini.
| Nama grup | Istilah min | W | X | Y | Z |
|---|---|---|---|---|---|
| GC1 | 2,6,10,14 | - | - | 1 | 0 |
| 8,9,10,11 | 1 | 0 | - | - | |
| GC2 | 10,11,14,15 | 1 | - | 1 | - |
Penggabungan lebih lanjut dari kombinasi suku min dari grup yang berdekatan tidak mungkin, karena mereka berbeda dalam lebih dari satu posisi bit. Ada tiga baris pada tabel di atas. Jadi, setiap baris akan memberikan satu implikasi utama. Oleh karena itu,prime implicants adalah YZ ', WX' & WY.
Itu prime implicant table ditampilkan di bawah.
| Istilah min / Implan Utama | 2 | 6 | 8 | 9 | 10 | 11 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|
| YZ’ | 1 | 1 | 1 | 1 | ||||
| WX’ | 1 | 1 | 1 | 1 | ||||
| WY | 1 | 1 | 1 | 1 |
Implikasi utama ditempatkan dalam baris bijaksana dan istilah min ditempatkan dalam kolom bijaksana. 1s ditempatkan di sel umum baris implikasi utama dan kolom istilah min yang sesuai.
Suku min 2 dan 6 hanya dicakup oleh satu implan utama YZ’. Jadi, ini adalahessential prime implicant. Ini akan menjadi bagian dari fungsi Boolean yang disederhanakan. Sekarang, hapus baris implikasi utama ini dan kolom istilah min yang sesuai. Tabel implikasi utama tereduksi ditampilkan di bawah ini.
| Istilah min / Implan Utama | 8 | 9 | 11 | 15 |
|---|---|---|---|---|
| WX’ | 1 | 1 | 1 | |
| WY | 1 | 1 |
Suku min 8 dan 9 hanya dicakup oleh satu implikasi utama WX’. Jadi, ini adalahessential prime implicant. Ini akan menjadi bagian dari fungsi Boolean yang disederhanakan. Sekarang, hapus baris implikasi utama ini dan kolom istilah min yang sesuai. Tabel implikasi utama tereduksi ditampilkan di bawah ini.
| Istilah min / Implan Utama | 15 |
|---|---|
| WY | 1 |
Min term 15 hanya dicakup oleh satu prime implant WY. Jadi, ini adalahessential prime implicant. Ini akan menjadi bagian dari fungsi Boolean yang disederhanakan.
Dalam contoh soal ini, kami mendapat tiga implikasi utama dan ketiganya penting. Oleh karena itu,simplified Boolean function adalah
f(W,X,Y,Z) = YZ’ + WX’ + WY.