Sabtu, 31 Desember 2011
Jumat, 30 Desember 2011
Teknik Minimasi
BAB II
PEMBAHASAN
I . Metode Peta Karnaugh
Cara menggambarkan Peta Karnaugh adalah dengan dengan cara menggambarkan
sejumlah kotak berbentuk persegi panjang yang berisi minimal term / minterm
dari persamaan logika. Banyaknya kotak-kotak tergantung pada banyaknya jumlah
input yang diberikan pada rangkaian logika.
Adapun rumus yang digunakan untuk menentukan banyaknya kotak dari Peta
Karnaugh adalah :
A = 2n
Untuk lebih
jelasnya akan diperhatikan pada tabel dibawah ini :
Tabel 2.7. Tabel
Variasi Pada Peta Karnaugh
|
Variable
Input
|
Kombinasi
|
Jumlah
Term
|
|
1
|
21
|
2
|
|
2
|
22
|
4
|
|
3
|
23
|
8
|
|
4
|
24
|
16
|
I.1 . Peta Karnaugh dengan Dua Variabel Input
Sebuah rangkaian logika yang mempunyai 2 buah input, maka akan mempunyai
4 buah variabel input (sesuai dengan rumus 2n = 22 = 4).
Bentuk Peta Karnaughnya adalah
seperti dibawah ini :
Gambar 2.3. Peta Karnaugh dengan Dua Variabel
I.2
. Peta Karnaugh dengan Tiga Variabel Input
Dalam
sebuah rangkaian logika yang mempunyai tiga buah input, akan mempunyai 8 buah
kombinasi variabel input ( 23 ). Jadi sebuah Peta Karnaugh dari
sebuah rangkaian logika dengan 3 buah input akan memiliki 8 buah kotak.
Bentuk Peta Karnaughnya adalah :
Gambar 2.4. Peta Karnaugh dengan Tiga variabel
Bila kita perhatikan, penempatan nilai 11 ada dikolom ketiga dari Peta
Karnaugh tiga variabel. Prinsip yang dipergunakan adalah perubahan antara kolom
yang satu dengan yang lainnya harus memiliki satu nilai perubahan saja.
Demikian juga dengan Peta Karnaugh diatas, kolom ke-2 = 01maka pada kolom
berikutnya (ke-3) harus 00 atau 11, karena pada kolom pertama 00 sudah
didefinisikan, maka kolom ke-3 diisi dengan nilai 11.
I.3
. Peta Karnaugh dengan Empat Variabel Input
Apabila sebuah rangkaian logika
mempunyai empat buah variabel input, maka akan dihasilkan sebanyak 16 buah
kombinasi variabel input. Untuk menggambarkan Peta Karnaugh dengan 4 buah
input, maka harus dibuatkan 16 buah kotak.
Gambar 2.5. Peta Karnaugh
dengan Empat Variabel
I.4
. Peta Karnaugh dengan Lima
Variabel Input
Apabila sebuah rangkaian logika
mempunyai lima
buah variabel input, maka akan dihasilkan sebanyak 32 buah kombinasi variabel
input. Untuk menggambarkan Peta Karnaugh dengan 5 buah input, maka harus
dibuatkan 32 buah kotak.
Gambar 2.6. Peta Karnaugh dengan Lima
variabel
I.5
. Penggunaan Peta Karnaugh
Penggunaan
Peta Karnaugh dapat dijelaskan dengan contoh persamaan seperti dibawah ini
berdasarkan tabel kebenaran dari AND GATE.
F = ABC + ABC + ABC + ABC+ ABC {Pers. 2.7}
Dengan tabel kebenaran :
Tabel 2. 8. Tabel Kebenaran
|
A
|
B
|
C
|
F
|
|
|
0
|
0
|
0
|
0
|
A’B’C
A’B C
A B’C
A B C’
A B C
|
|
0
|
0
|
1
|
1
|
|
|
0
|
1
|
0
|
0
|
|
|
0
|
1
|
1
|
1
|
|
|
1
|
0
|
0
|
0
|
|
|
1
|
0
|
1
|
1
|
|
|
1
|
1
|
0
|
1
|
|
|
1
|
1
|
1
|
1
|
Dari
tabel kebenaran diatas, pada kolom F terdapat angka logika 0 dan 1 yang akan
disederhanakan adalah mempunyai hasil 1 dan selanjutnya dikonversikan kedalam
Peta Karnaugh seperti dibawah ini :
Gambar 2.7. Hasil Konversi
Didalam kotak-kotak
tersusun angka logika 1 dan logika 0, dimana angka logika 1 letaknya bisa
berdekatan / berdampingan dan bisa juga berjauhan tergantung bentuk soal yang
mempunyai nilai 1.
Berdasarkan
letak angka 1 maka akan didapat beberapa kemungkinan yang akan terjadi, yaitu
sebagai berikut :
1.
PAIR, apabila ada dua angka logika 1 yang berdampingan.
2.
QUAD, apabila ada empat angka logika 1 berdampingan.
3.
OKTET, apabila ada delapan angka logika 1 berdampingan.
4.
ROLLING (melingkar), apabila nilai logika 1 yang
terdapat pada kolom sebelah kiri dengan nilai logika 1 pada kolom sebelah
kanan, atau nilai logika 1 pada baris paling atas dengan logika 1 pada baris
paling bawah.
5.
OVERLAPPING, apabila pembacaan logika 1 yang digunakan
lebih dari 1 (satu) kali.
Pasangan yang terbentuk dari angka 1 yang
berdampingan seperti pada contoh penyederhanaan diatas adalah sebuah pair dan
sebuah quad.
Langkah-langkah penyederhanaan rangkaian
logika dengan menggunakan Peta Karnaugh bila secara singkat adalah sebagai
berikut :
1.
Masukkan angka-angka 1 ke dalam Peta Karnaugh untuk
setiap hasil kali fundamental yang bersesuaian dengan kelaran 1 dalam tabel
logika.
Tulislah
angka-angka 0 ditempat-tempat yang tersisa
2.
Lingkarilah pair, quad, oktet, dan pasangan yang ada
pada peta. Jangan lupa melakukan proses pengulangan dan penandaan
kelompok-kelompok tumpang tindih untuk memperoleh kelompok yang sebesar
mungkin.
3.
Lingkarilah sisa-sisa angka 1 yang terisolasi.
4.
Hapuslah kelompok-kelompok kelebihan bilamana ada.
5.
Tulislah persamaan boolean dalam pernyataan operasi OR
dari hasil kali yang bersesuaian dengan kelompok-kelompok yang dilingkari dalam
Peta Karnaugh.
6.
Gambarlah rangkaian logika ekivalennya.
II . Metode Quine Mc.Cluskey
Metode lain yang
digunakan untuk menyederhanakan fungsi boolean adalah dengan menggunakan metode
Quine-McCluskey atau biasa disebut metode tabulasi. Jika jumlah variabel yang
terlibat pada suatu fungsi lebih dari enam variabel maka penggunaan Peta
Karnaugh menjadi semakin rumit. Untuk itu digunakan metode Quine-McCluskey atau
tabulasi ini. Dasar hukum yang digunkan metode ini adalah aksioma distribusi.
Metode
Quine-McCluskey ini terdiri dari dua bagian, yaitu :
1. Menentukan
term-term sebagai kandidat (Prime Implicant).
2.
Memilih prime implicant untuk mendapatkan
ekspresi dengan jumlah literal paling sedikit.
I.1 . Menentukan
Prime Implicant
Langkah-langkah
penyelesaian dalam menentukan prime implicant (kandidat-kandidat) adalah
dengan cara :
a.
Kelompokkan representasi biner untuk minterm
menurut jumlah digit 1-nya.
Tabel
2.9. Konversi Biner
|
Desimal
|
Biner
|
|
0
|
0000
|
|
1
|
0001
|
|
2
|
0010
|
|
8
|
1000
|
|
10
|
1010
|
|
11
|
1011
|
|
14
|
1110
|
|
15
|
1111
|
Berdasarkan tabel
diatas, pisahkan menurut jumlah digit 1-nya menjadi :
Tabel 2.10. Tabel
Menurut Jumlah Digit
|
Jumlah Digit 1
|
Desimal
|
|
0
|
0
|
|
1
|
1,2,8
|
|
2
|
10
|
|
3
|
11,14
|
|
4
|
15
|
Jika dibuat kedalam
bentuk tabel kelompok, menjadi :
Tabel 2.11. Tabel
Kelompok
|
Desimal
|
w
|
x
|
Y
|
z
|
|
0
|
0
|
0
|
0
|
0
|
|
1
2
8
|
0
0
1
|
0
0
0
|
0
1
0
|
1
0
0
|
|
10
|
1
|
0
|
1
|
0
|
|
11
14
|
1
1
|
0
1
|
1
1
|
1
0
|
|
15
|
1
|
1
|
1
|
1
|
b. Dari dua minterm
yang berbeda nilai digit 1-nya dapat dikombinasikan dengan angka 0 untuk
menghilangkan minterm dari suatu bagian lainnya jika mempunyai nilai bit
yang sama dalam semua posisi kecuali satu posisi. Satu posisi yang berbeda
tersebut dapat diganti dengan tanda ‘-‘, misalnya :
0000
000- 0001
sehingga jika
contoh diatas diselesaikan, menjadi :
Tabel 2.12. Tabel
Penyederhanaan (1)
|
( 1 )
|
( 2 )
|
||||||||||
|
Desimal
|
w
|
X
|
Y
|
z
|
|
Reduksi
|
w
|
x
|
y
|
z
|
|
|
0
|
0
|
0
|
0
|
0
|
√
|
0,1
|
0
|
0
|
0
|
-
|
|
|
1
|
0
|
0
|
0
|
1
|
√
|
0,2
|
0
|
0
|
-
|
0
|
√
|
|
2
|
0
|
0
|
1
|
0
|
√
|
0,8
|
-
|
0
|
0
|
0
|
√
|
|
8
|
1
|
0
|
0
|
0
|
√
|
2,10
|
-
|
0
|
1
|
0
|
√
|
|
10
|
1
|
0
|
1
|
0
|
√
|
8,10
|
1
|
0
|
-
|
0
|
√
|
|
11
|
1
|
0
|
1
|
1
|
√
|
10,11
|
1
|
0
|
1
|
-
|
√
|
|
14
|
1
|
1
|
1
|
0
|
√
|
10,14
|
1
|
-
|
1
|
0
|
√
|
|
15
|
1
|
1
|
1
|
1
|
√
|
11,15
|
1
|
-
|
1
|
1
|
√
|
|
|
|
|
|
|
|
14,15
|
1
|
1
|
1
|
-
|
√
|
Keterangan :
√ : Bilangan yang bisa dikerjakan
lagi pada proses berikutnya.
a.
Kelompokkan hasil minterm tahap b seperti tahap a.
b.
Ulangi tahap b dan c sampai minterm dari setiap bagian
tidak dapat saling menghilangkan.
I.2 . Memilih Prime-Implicant
Dari tabel 2.13 di atas,
terlihat hasil dari tahap penentuan prime-implicant pada kolom 1, 2, dan
3. pada kolom 3 (sudah tidak dapat dihilangkan), terlihat pada bagian pertama
mencakup desimal 0,2,8,10, dan bagian kedua meliputi desimal 10,11,14,15. Hal
ini berarti dari fungsi boolean F = ∑ (0,1,2,8,10,11,14,15); desimal yang belum
ada pada kolom 3 adalah desimal 1. Hal ini berarti calon prime implicant-nya
adalah :
√
: 0,1 (0 0
0 -) ditandai dengan A
√
: 0,2,8,10 (- 0 -
0) ditandai dengan B
√
: 10,11,14,15 (1 - 1 -)
ditandai dengan C
Jika dibuat dalam
bentuk tabel, adalah sebagai berikut :
Tabel 2.14 Tabel Prime
Implicant
|
|
0
|
1
|
2
|
8
|
10
|
11
|
14
|
15
|
|
A
|
X
|
@
|
|
|
|
|
|
|
|
B
|
X
|
|
@
|
@
|
X
|
|
|
|
|
C
|
|
|
|
|
X
|
@
|
@
|
|
Keterangan :
Tanda @ adalah yang harus dipilih.
Jadi bentuk sederhana setelah
menggunakan metode Quine-McCluskey dari fungsi boolean F = ∑
(0,1,2,8,10,11,14,15) adalah:
F = A + B + C
= W’X’Y’ + X’Z’ + WZ
Metode peta Karnaugh diperlukan
ketelitian yang cukup tinggi didalam proses penyederhanaannya, karena setelah
persamaan yang akan disederhanakan dikonversikan kedalam peta karnaugh, ada
banyak kemungkinan yang terbentuk antara angka 1 yang berhubungan. {Dalam 1
quad bisa terdiri dari 2 pair, dalam 1 oktet bisa terdiri dari 2 buah quad dan
4 buah pair, dan lain-lain}. Sedangkan untuk metode fungsi aljabar dan metode
Quine-McCluskey hasil akhirnya pasti.
Langganan:
Postingan (Atom)