Bab 4 Rangkaian Logika Kombinasional

Bab 4 Rangkaian Logika Kombinasional

4.1 Logika Biner Dan Gerbang ~ Binary Logic and Gates Rangkaian-rangkaian dijital merupakan komponen perangkat keras (hardware) yang memanipulasi

informasi

biner.

Rangkaian-rangkaian

diimplementasikan

dengan

menggunakan transistor-transistor dan antar-hubungan (interconnection) dalam peralatanperalatan (devices) semikonduktor kompleks yang disebut integrated circuits dan selanjutnya lebih dikenal dengan IC Masing-masing rangkaian dasar disebut sebagai gerbang lojik. Untuk penyederhanaan dalam rancangan, rangkaian-rangkaian elektronik berbasis transistor dimodelkan sebagai gerbang-gerbang lojik. Sehingga perancang tidak perlu memperhatikan tentang elektronik-elektronik internal dan gerbang-gerbang individu, tetapi

banya

tentang

sifat-sifat

lojik

eksternal

mereka.

Masing-masing

gerbang

menyelenggarakan operasi lojik tertentu. Keluaran-keluaran (outputs) dan gerbang-gerbang diterapkan sebagai masukan-masukan (inputs) dan gerbang-gerbang lain untuk membentuk suatu rangkaian dijital. Untuk menggambarkan sifat-sifat operasional rangkaian-rangkaian dijital, perlu diperkenalkan notasi matematik yang menentukan operasi dari masing-masing gerbang dan yang bisa digunakan untuk menganalisa dan merancang rangkaian-rangkaian. Sistem lojik biner ini merupakan salah satu klas sistem matematika yang secana umum disebut sebagai aijabar Boolean. Nama ini sebagai penghormatan matematisi Inggnis George Boole, yang ditahun 1854 menerbitkan sebuah buku yang memperkenalkan teori matematika tentang lojik. Aljabar Boolean khusus yang akan dibicarakan digunakan untuk menggambarkan antar hubungan gerbang-gerbang dijital dan untuk merancang rangkaian-rangkaian lojik melalui manipulasi ekspresi-ekspresi Boolean. Pertama-tama akan diperkenalkan konsep logika biner dan memperlihatkan hubungannya dengan gerbang-gerbang lojik dan sinyalsinyal biner. Kemudian disajikan sifat-sifat aljaban Boolean, bersama dengan konsep-konsep lain dan metode-metode yang bermanfaat dalam perancangan rangkaian-rangkaian lojik. Logika Biner  Binary Logic Logika biner berurusan dengan variabel-variabel biner yang mempunyai dua nilai diskrit dan dengan operasi-operasi logika matematika yang diterapkan pada variabel-variabel tersebut. Dua nilai diskrit yang dimaksud mungkin disebut dengan nama-nama yang berbeda, namun untuk rnaksud dan tujuan ini akan lebih mudah untuk berfikir tentang istilahistilah nilai biner dan memasang (assign) 1 atau 0 ke masing-masing variabel. Variabelvariabel ditandai dengan hunuf-huruf alfabet seperti A, B, C, X, Y, dan Z. Selanjutnya notasi ini akan diperluas dan bisa meliputi string dan huruf-huruf, bilangan-bilangan, dan karakterUniversitas Gadjah Mada

1

karakter khusus. Terhadap variabel-variabel biner terhubung tiga operasi lojik dasar yang disebut AND, OR,dan NOT. 1. AND. Operasi ini dinyatakan (atau diwakili oleh) dengan suatu titik (dot) atau dengan ketidakhadiran (absence) operator. Sebagai contoh, Z = X.Y atau Z = X.Y dibaca Z sama dengan X AND Y. Operator lojik AND diinterpretasikan sebagai berikut : Z = 1 bila dan hanya bila X = 1 dan Y = 1; selain itu Z = 0. (Ingat bahwa X, Y, dan Z merupakan variabel-variabel biner yang hanya bisa mempunyai nilai 1 atau 0.) 2. OR. Operasi ini dinyatakan dengan simbol tambah (+). Sebagai contoh, Z = X + Y dibaca Z sama dengan X OR Y, berarti bahwa Z = 1 bila X = 1 atau jika Y = 1, atau jika kedua X = 1 dan Y = 1. Z = 0 bila hanya bila X =0 dan Y =0. 3. NOT Operasi ini dinyatakan dengan simbol petik tunggal („). Sebagai contoh, Z = X‟ dibaca Z sama dengan NOT X, berarti bahwa Z adalah apa yang X tidak. Dengan kata lain, jika X = 1, maka Z = 0; tetapi jika X = 0, maka Z = 1. Operasi NOT juga disebut sebagai operasi komplemen (complement), karena operasi ini merubah 1 menjadi 0 dan 0 menjadi 1. Logika biner menyerupai aritmatika biner, dan operasi-operasi AND dan OR masing-masing mempunyai kemiripan dengan perkalian dan penjumlahan. Ini kenapa simbol-simbol yang digunakan untuk AND dan OR sama dengan mereka yang digunakan untuk perkalian dan penjumlahan. Akan tetapi, logika biner seharusnya tidak dirancukan dengan aritmatika biner. Di samping itu, harus disadari juga bahwa suatu variabel aritmatika menandakan suatu bilangan yang bisa terdiri dari banyak angka (digits), sementara suatu variabel lojik selalu 1 atau 0. Persamaan-persamaan benikut mendefinisikan operasi-operasi lojik OR: 0+0=0 0+1=1 1+0=1 1+1=1 Dari definisi di atas, kelihatan bahwa operasinya menyerupai operasi jumlahan, kecuali untuk operasi terakhir. Dalam logika biner, 1 + 1 = 1 (dibaca satu OR satu sama dengan satu), tetapi dalam aritmatika biner, 1 + 1 = 10 (dibaca satu tambah satu sama dengan dua). Untuk menghindari anti mendua (ambiguity), sering kali digunakan simbol

. untuk operasi OR dari

pada simbol +. Akan tetapi selama operasi-operasi aritmatika dan logika tidak tercampur, masing-masing bisa menggunakan simbol + dengan anti mereka masing-masing. Persamaan berikutnya mendefinisikan operasi lojik AND: 0•0=0 0 • 1 = 13 1•0=0 1•1=1 Universitas Gadjah Mada

2

Operasi ini identik dengan perkalian biner, asalkan hanya digunakan bit tunggal. Simbol alternatif terhadap • untuk AND adalah A, yang sering digunakan dalam konjungsi dengan symbol v untuk OR. Untuk masing-masing kombinasi nilai-nilai dari variabel biner seperti X dan Y, ada nilai Z yang ditentukan dengan definisi operasi lojik. Definisi bisa didaftar dalam format yang kompak dalam tabel kebenaran (truth table). Suatu tabel kebenaran untuk suatu operasi adalah suatu tabel kombinasi variabel-variabel biner yang memperlihatkan hubungan antara nilai-nilai yang diambil variabel dan nilai-nilai hasil operasi. Tabel-tabel kebenaran untuk operasi-openasi AND, OR, dan NOT diperlihatkan dalam Tabel 4.1. Tabel kebenaran mendaftar semua kombinasi yang mungkin dari nilai-nilai untuk dua variabel dan hasil-hasil operasi. Tabel kebenaran mendemonstrasikan secara jelas definisi dari ketiga operasi. Tabel 4.1 Tabel-tabel kebenaran untuk tiga operasi lojik dasar

Gerbang Lojik  Logic Gates Gerbang-gerbang lojik adalah rangkaian-rangkaian elektronik yang beroperasi pada satu atau lebih sinyal-sinyal masukan untuk menghasilkan sinyal-sinyal keluaran. Sinyalsinyal elektronik seperti voltase atau arus ada dalam suatu sistem dijital dalam salah satu dari dua nilai yang bisa dikenali. Rangkaian-rangkaian yang dioperasikan dengan voltase (voltage-operated) menanggapi dua jangkauan voltase terpisah yang menyatakan suatu variabel biner sama dengan lojik 1 atau lojik 0, seperti digambarkan dalam Gambar 4.1. Terminal-terminal masukan dari gerbang-gerbang lojik menerima sinyal-sinyal biner dalam jangkauan (voltase) yang diperbolehkan dan merespon pada terminal-terminal keluaran dengan sinyal-sinyal biner yang masuk dalam jangkauan yang ditentukan. Simbol-simbol grafik yang digunakan untuk menandakan tiga tipe gerbang - AND, OR, dan NOT - diperlihatkan dalam Gambar 4.2 (a). Gerbang merupakan rangkaianrangkaian elektronik yang menghasilkan ekuivalen sinyal-sinyal output lojik 1 dan lojik 0 sesuai dengan tabel-tabel kebenaran mereka jika ekuivalen sinyal-sinyal input diterapkan. Dua sinyal input X dan Y ke gerbang-gerbang AND dan OR mengambil satu dan empat kombinasi yang mungkin : 00, 01, 10, atau 11. Sinyal-sinyal input ini diperlihatkan sebagai timing diagram dalam Gambar 4.2 (b), bersama dengan timing diagram untuk sinyal output yang bersesuaian untuk masing-masing tipe gerbang. Sumbu mendatar dari timing diagram menyatakan waktu, dan sumbu tegak memperlihatkan sinyal berserta perubahannya antara Universitas Gadjah Mada

3

dua tingkatan voltase yang mungkin. Tingkat bawah (low level) menyatakan lojik 0 dan tingkat atas (high level) menyatakan lojik 1. Gerbang AND merespon dengan sinyal output lojik 1 jika kedua sinyal input adalah lojik 1. Gerbang OR merespon dengan sinyal output lojik 1 jika salah satu atau kedua sinyal input adalah lojik 1. Selanjutnya gerbang NOT lebih dikenal dengan sebutan inverter. Alasan dan penggunaan nama ini adalah jelas, yaitu dari tanggapan dalam timing diagram. Sinyal lojik output merupakan versi kebalikan dari sinyal lojik input X.

Gerbang-gerbang AND dan OR bisa mempunyai lebih dari dua input. Suatu gerbang AND dengan tiga input dan suatu gerbang OR dengan enam input diperlihatkan dalam Gambar 4.3. Gerbang AND dengan tiga input menanggapi dengan output lojik 1 jika tiga input semuanya adalah lojik 1. Sementara output-nya adalah lojik 0 jika ada input berupa

Universitas Gadjah Mada

4

lojik 0. Gerbang OR dengan enam input menanggapi dengan lojik 1 jika ada input berupa lojik 1; dan output-nya menjadi lojik 0 hanya jika semua input berupa lojik 0.

4. 2 Aljabar Boolean  Boolean AIgebra Aljabar Boolean merupakan aljabar yang berhubungan dengan variabel-variabel biner dan operasi-operasi lojik. Variabel-variabel diperlihatkan dengan huruf-huruf alfabet, dan tiga operasi dasar dengan AND, OR, dan NOT (komplemen). Fungsi Boolean terdiri dari variabel-variabel biner yang menunjukkan fungsi, suatu tanda sama dengan, dan suatu ekspresi aljabar yang dibentuk dengan menggunakan variabel-variabel biner, konstantakonstanta 0 dan 1, simbol-simbol operasi lojik, dan tanda kurung. Untuk nilai variabelvariabel yang diketahui, suatu fungsi Boolean bisa sama dengan 1 atau 0. Sebagai contoh perhatikan fungsi Boolean berikut F = X + Y‟Z dua bagian ekspresi, X dan Y‟Z disebut suku-suku (terms) dari fungsi F. Fungsi F sama dengan 1 jika term X sama dengan 1 atau jika term Y‟Z sama dengan 1, dan ini akan terjadi hanya jika kedua Y‟ dan Z sama dengan 1. Selain itu, F sama dengan 0. Operasi komplemen menyebabkan bahwa jika Y‟l, maka Y harus sama dengan 0. Sehingga, kesimpulannya F1 jika X1, atau jika Y0 dan Z1. Suatu fungsi Boolean mengekspresikan relasi lojik antara variabel-variabel biner. Suatu fungsi Boolean bisa dinyatakan dalam tabel kebenaran. Suatu tabel kebenaran untuk fungsi Boolean merupakan daftar semua kombinasi anka-angka biner 0 dan 1 yang diberikan ke variabel-variabel biner dan daftar yang memperlihatkan nilai fungsi untuk masing-masing kombinasi biner. Tabel-tabel kebenaran untuk operasi-operasi lojik dasar diberikan dalam Tabel 4.1. Banyaknya baris dalam tabel kebenaran adalah 2”, di mana n adalah banyaknya variabel dalam fungsi. Kombinasi-kombinasi biner untuk tabel kebenaran adalah bilangan biner n-bit yang bersesuaian dengan cacah dalam desimal dari 0 sampai dengan 2”- l. Tabel 4.2 memperlihatkan tabel kebenaran untuk fungsi FX+Y‟Z. Ada delapan kombinasi biner yang mungkin dengan meng-assign bit ke masing-masing tiga variabel X, Y, dan Z. Kolom dengan label F memuat 0 atau 1 untuk masing-masing delapan kombinasi yang disebut di atas Tabel memperlihatkan bahwa fungsi sama dengan I jika X = 1 dan jika Y = 0 dan Z = 1. Selain itu fungsi sama dengan 0. Suatu fungsi Boolean bisa ditransformasi dari suatu ekspresi aljabar ke suatu diagram rangkaian (circuit diagram) yang dibentuk dari gerbang-gerbang lojik. Diagram Universitas Gadjah Mada

5

rangkaian lojik untuk fungsi F diperlihatkan dalam Gambar 4.4. Suatu inverter pada input Y menghasilkan komplemen dan Y, yaitu Y‟ Kemudian gerbang AND beroperasi pada Y‟ dan Z, dan akhirnya gerbang OR mengkombinasikan X dengan Y‟Z. Dalam diagram rangkaian lojik, variabel-variabel fungsi diambil sebagai input-input rangkaian, dan variabel biner F diambil sebagai output rangkaian. Selanjutnya gerbang-gerbang dihubungkan dengan kabel (wires) yang membawa sinyal-sinyal lojik. Rangkaian-rangkaian lojik tipe ini disebut rangkaian logika kombinasional (combinational logic circuits), karena veriabel-variabel dikombinasikan dengan operasi-operasi lojik.

Selanjutnya dengan menerapkan aturan-aturan operasi lojik dasar di atas, maka tabel kebenaran F = X + YZ bisa diperlihatkan pada Tabel 4.2 berikut.

Hanya ada satu cara jika fungsi Boolean dinyatakan dalam tabel kebenaran. Akan tetapi, ada banyak cara untuk menyatakan fungsi Boolean dalam bentuk aljabar. Dengan memanipulasi suatu ekspresi Boolean menurut aturan-aturan aljabar Boolean, seringkali bisa diperoleh suatu ekspresi yang lebih sederhana untuk fungsi yang sama. Untuk mengetahui bagaimana hal ini dilakukan, penting sekali untuk terlebih dahulu mempelajari aturan-aturan dasar (basic rules) aljabar Boolean. Identitas-identitas Dasar Aljabar Boolean Basic Identities of Boolean Algebra Tabel 4.3 memperlihatkan identitas-identitas dasar aljabar Boolean. Notasi disederhanakan dengan menghilangkan simbol untuk AND. Sembilan identitas dasar memperlihatkan hubungan antara variabel tunggal X, komplemennya X‟, dan konstantakonstanta biner 0 dan 1. Lima identitas berikutnya, yaitu 10 sampai 14 mepunyai lawanpasangan (counterparts) dalam aljabar biasa. Selanjutnya identitas tiga terakhir, yaitu 15 sampai 17 tidak berlaku dalam aljabar biasa, akan tetapi bermanfaat dalam pemanipulasian ekspresi-ekspresi aljabar. Universitas Gadjah Mada

6

Aturan-aturan dasar didaftar dalam tabel yang telah disusun dalam dua kolom yang mendemonstrasikan sifat dualitas aljabar Boolean. Dual dari suatu ekspresi aljabar diperoleh dengan mempertukarkan operasi-operasi OR dengan AND dan sebaliknya, dan angka biner 0 dengan angka biner 1.

Sembilan identitas yang melibatkan variabel tunggal bisa dengan mudah dibuktikan dengan mengganti masing-masing dengan dua nilai yang mungkin dan X. Sebagai contoh, untuk memperlihatkan bahwa X + 0 = X, ambil X = 0 untuk mendapatkan 0 + 0 = 0, dan X = 1 untuk mendapatkan 1 + 0 = 1. Kedua persamaan benilai true menurut definisi operasi lojik OR. Setiap ekspresi bisa diganti dengan variabel X untuk semua persamaan Boolean yang terdaftar dalam tabel. Sehingga dengan identitas nomor dan dengan X = AB + C, akan diperoleh AB + C + 1 = 1. Identitas nomor 9 menyatakan bahwa komplementasi dobel (doubly commplement) akan mengembalikan suatu variabel ke nilai asli. Sehingga jika X = 0,maka X‟= 1 dan X” = 0 = X. Indentitas 15 merupakan dual dan aturan distributif biasa (identitas 14). Seperti yang sudah diilustrasikan sebelumnya bahwa setiap variabel dalam identitas bisa diganti dengan ekspresi Boolean, dan identitas masih tetap berlaku. Jadi untuk ekspresi (A + B)(A + CD), bisa diambil X = A, Y = B, dan Z = CD, dan dengan aturan (identitas 15), diperoleh (A + B)(A + CD) = A + BCD. Selanjutnya dua identitas terakhir, (X + Y)‟ = X‟•Y‟ dan (X•Y)‟ = X‟ + Y‟ disebut dengan teori DeMorgan. Teori ini sangat penting untuk memperoleh komplemen dari suatu ekspresi.

Pada waktu mengkomplemenkan suatu ekspresi, tanda kurung memegang peranan yang sangat penting, karena simbol komplemen yang digunakan dalam pembahasan ini adalah petik tunggal (single quote — ‘). Sehingga ekspresi (X + Y)‟ menyatakan komplemen dari X +


7

Y, akan tetapi jika tanda kurung dihilangkan maka akan mempunyai arti yang berbeda, yaitu X di-OR-kan dengan komplemen dari Y. Teorema DeMorgan bisa diperluas menjadi tiga atau lebih variabel. Selanjutnya teori umum DeMorgan bisa dinyatakan sebagai

Perhatikan bahwa operasi lojik berubah dan OR ke AND atau dari AND ke OR. Di samping itu, komplemen dihilangkan dari keseluruhan ekspresi dan ditempatkan di atas masing-masing variabel. Sebagai contoh, (A + B + C + D)‟ = A‟ B‟ C‟D‟ Manipulasi Aljabar  Algebra Manipulation Aljabar Boolean merupakan alat yang bermanfaat untuk menyederhanakan rangkaian-rangkaian dijital. Sebagai contoh perhatikan fungsi Boolean F = X‟YZ + X‟YZ‟+ XZ. Implementasi dari fungsi di atas dengan gerbang-gerbang lojik diperlihatkan dalam Gambar 4.5 bagian (a). Variabel-variabel input X dan Z dikomplemenkan dengan inverter untuk mendapatkan X‟ dan Z‟ Ketiga term dalam ekspresi diimplemenkan dengan dengan tiga gerbang AND. Gerbang OR membentuk OR logic terms (suku-suku logika OR). Sekarang perhatikan penyederhanaan fungsi dengan penerapan beberapa identitas yang tendaftar dalam Tabel 4.5 :

Terlihat bahwa fungsi bisa direduksi (disederhanakan) menjadi hanya dua term, dan bisa diimplementasikan dengan gerbang-gerbang sepeti dalam Gambar 4.5 (b). Secara jelas bisa dilihat bahwa rangkaian dalam gambar (b) lebih sederhana dibanding dengan gambar (a), meskipun keduanya mengimplementasikan fungsi yang sama. Jika diperlukan bisa digunakan tabel kebenaran untuk membuktikan bahwa dua implementasinya ekuivalen. Sebagainuna diperlihatkan dalam Tabel 4.5.


8

Ketika ekspresi Boolean diimplementasikan dengan gerbang-gerbang lojik, masing-masing term memerlukan sebuah gerbang, dari masing-masing variabel dalam term menandakan sebuah masukan ke gerbang. Dalam pembahasan ini, literal didefinisikan sebagai variabel tunggal terkomplemen (complemented) atau tak-terkomplemen (uncomplemented). Sebagai contoh, fungsi dalam Gambar 4.4 (a) mempunyai tiga terms dan delapan literals; sementara fungsi dalam Gambar 4.4 (b) mempunyai dua terms dan empat literals. Dengan mengurangi jumlah terms atau literals atau keduanya dalam ekspresi Boolean, sering bisa mendapatkan rangkaian yang lebih sederhana. Sehingga aljabar Boolean diterapkan untuk mereduksi ekspresi untuk mendapatkan rangkaian yang lebih sederhana. Untuk fungsi-fungsi yang sangat kompleks, menemukan ekspresi terbaik berdasarkan hitungan terms dan literals adalah sangat sukar, meskipun dengan program-program komputer. Akan tetapi metodemetode tertentu untuk mereduksi ekspresi sering disertakan (included) dalam computer tools untuk melakukan sintesa rangkaian-rangkaian lojik. Metode-metode ini bisa digunakan untuk mendapatkan penyelesaian yang baik meskipun bukan yang terbaik. Satu-satunya metode manual untuk kasus umum adalah prosedur cut-and-try yang menggunakan relasi-relasi dasar dan manipulasi-manipulasi lain yang menjadi terbiasa apabila sering digunakan.


9

Selanjutnya contoh-contoh berikut menggunakan identitas-identitas dari Tabel 4.3 untuk ambarkan beberapa kemungkinan:

Perhatikan bahwa langkah tengahan X = X•1(identitas

2)

dihilangkan dalam persamaan 1,

sehingga X + XY (identitas 2) X•1 + XY (identitas 14) X(1 + Y)= (identitas 3) X•1 = (dentitas 2 lagi) X.

Perhatikan bahwa persamaan 4 sampai 6 merupakan dual persamaan 1 sampai 3, ingat bahwa dual dari suatu ekspresi diperoleh dengan merubah AND ke OR dan sebaliknya, bit-bit 1 menjadi bit-bit 0 dan sebaliknya, jika mereka muncul dalam ekspresi. Prinsip dualitas (duality principle) aljabar Boolean menyatakan bahwa suatu persamaan Boolean tetap valid ekspresi di kedua sisi tanda sama dengan diambil dualnya. Sehingga persamaanpersamaan 4, 5, dan 6 bisa dibuktikan dengan mengambil dual dari masing-masing persamaan-persamaan 1,2, dan 3. Teorema konsesus berikut kadang-kadang bermanfaat ketika menyederhanakan ekspresi-ekspresi Boolean XY+X‟Z+YZ = XY+X‟Z. Teorema memperlihatkan bahwa term ke tiga (yaitu YZ) berlebih (redundant) sehingga bisa dihilangkan. Teorema konsensus bisa dibuktikan dengan terlebih dahulu meg-AND-kan (AND ing) YZ dengan (X + X‟) = 1 sebagai benikut:

Selanjutnya, dual dari teorema konsensus adalah (X + Y)(X‟ + Z)(Y + Z) = (X + Y)(X‟ + Z). Contoh berikut memperlihatkan penggunaan teorema konsensus untuk menyederhanakan (memanipulasi) ekspresi Boolean.

Komplemen Fungsi  Function Complement Komplemen suatu fungsi, F‟ diperoleh dari suatu pertukaran antara angka biner 0 dengan angka biner 1 dan sebaliknya untuk nilai-nilai F dalam tabel kebenaran. Komplemen suatu fungsi bisa diturunkan secara aljabar dengan menerapkan teorema DeMorgan. Bentuk umum dan teorema ini menyatakan bahwa komplemen suatu ekspresi diperoleh dengan Universitas Gadjah Mada

10

menukar operasi AND dengan OR dan sebaliknya, dan mengkomplemenkan masing-masing variabel dan konstan. Contoh 4.1 Mengkomplemenkan Fungsi Tentukan komplemen dari masing-masing dua fungsi berikut : F1 = X‟YZ‟ + X‟Y‟Z dan F2 = X(Y‟Z‟ + YZ). Dengan menerapkan teorema DeMorgan sebanyak yang diperlukan, akan diperoleh komplemen fungsi sebagai benikut: F1‟= (X‟YZ‟+X‟Y‟Z)‟= (X‟Y‟Z)‟(‟XY‟Z)‟= (X+ Y‟+ Z)(X+ Y+ Z‟) F2‟= (X(Y‟Z‟+ YZ))‟=X‟+ (Y‟Z‟+ YZ‟)‟=X‟+ (Y‟Z‟)‟(YZ‟)‟=X‟ + (Y+Z)(Y‟+Z) Metode yang lebih sederhana untuk menurunkan komplemen fungsi adalah dengan mengambil dual dari fungsi dan mengkomplemenkan masing-masing literal. Metode ini sebenarnya merupakan generalisasi dan teorema DeMorgan. Contoh 4.2 Mengkomplemenkan Fungsi Dengan Menggunakan Dual Tentukan komplemen fungsi-fungsi dalam Contoh 4.1 dengan mengambil dual mereka dan mengkomplemenkan masing-masing literal. F1 = X‟YZ‟ + X‟Y‟Z = (X‟YZ)+ (X‟Y‟Z) Dual dari F1: (X‟+ Y+ Z‟)(X‟+ Y‟+ Z) Komplemen masing-rnasmg literal: (X + Y‟ + Z)(X + Y +Z‟) = F,‟ F2 = X(Y‟Z‟ + YZ) = X((Y‟Z‟) + (YZ)) DualdariF2:X+ (Y‟+Z‟)(Y+Z) Komplemen masing-masing literal : X + (Y‟ + Z)(Y‟ + Z‟) = F2‟ Bentuk Standar  Standard Forms Fungsi Boolean bisa ditulis dalam banyak cara jika dinyatakan secara aljabar. Akan tetapi ada beberapa cara penulisan ekspresi aljabar yang dianggap sebagai bentuk standar. Bentuk standar memfasilitasi prosedur-prosedur penyederhanaan untuk ekspresi Boolean dan sering menghasilkan rangkaian-rangkaian lojik yang lebih diinginkan. Bentuk-bentuk standar memuat product terms dan sum terms. Contoh product term misalnya XYZ, yang terdiri dari suatu operasi AND antara tiga literals. Sedang contoh sum term misalnya X + Y + Z‟, yang terdiri dari suatu operasi OR antara tiga literals. Dalam pembahasan ini perlu diperhatikan bahwa kata product dan sum tidak mengakibatkan operasi aritmatika dalam aljabar Boolean; melainkan mereka menentukan masing-masing operasi-operasi lojik AND dan OR. Minterms dan Maxterms Telah diperlihatkan bahwa suatu tabel kebenaran mendefinisikan suatu fungsi Boolean. Suatu ekspresi aljabar yang menyatakan fungsi diturunkan dari tabel dengan menemukan jumlahan lojik dan semua product terms di mana fungsi mempunyai nilai biner 1. Suatu product terms di mana semua literal (variabel) muncul tepat satu kali, baik Universitas Gadjah Mada

11

terkomplemen atau tak-terkomplemen, disebut minterm. Minterm menyatakan secara tepat satu kombinasi dari variabel-variabel biner dalam tabel kebenaran. Untuk fungsi dengan n vaniabel, ada 2n minterms yang berbeda.

Bilangan-bilangan biner dad 000 sampai 111 terdaftar di bawah variabel-variabel. Untuk masing-masing kombinasi biner ada minterm yang terhubung. Masing-masing minterm merupakan product term dari tepat tiga literal. Literal merupakan variabel terkomplemen jika bit yang bersesuaian dan kombinasi biner terhubung adalah 0 dan merupakan vaniabel tak-terkomplemen jika sebaliknya. Simbol mj untuk masingmasing minterm juga diperlihatkan dalam tabel, di mana indeks (subscript) menunjukkan ekuivalen decimal dan kombinasi biner di mana minterm bernilai 1. Daftar minterm untuk sembarang nilai n (banyaknya avriabel) bisa dicari dengan cara serupa. Di samping itu, tabel kebenaran untuk masing-masing minterm diperlihatkan di samping kanan tabel. Tabel kebenaran ini dengan jelas memperlihatkan bahwa masing-masmg minterm bernilai 1 untuk kombinasi biner yang bersesuaian dan bernilai 0 untuk semua kombinasi yang lain. Tabel-tabel kebenanan semacam ini akan bermanfaat dalam pembentukan ekspresi Boolean menggunakan minterm. Sementara suatu suku jumlah yang memuat semua variabel dalam bentuk terkomplemen atau takterkomplemen disebut maxterm. Seperti minterm, dengan n variabel bisa dihasilkan 2n maxterms. Tabel 4.5 memperlihatkan delapan maxterms untuk tiga variabel.


12

Masing-masing maxterm merupakan jumlahan lojik dari tiga variable, dimana masing-masing variabel dikomplemenkan jika bit dari bilangan biner yang bersesuaian sama dengan 1, dan tak-terkomplemen jika sama dengan 0. Simbol untuk maxterm adalah Mj, dengan j menunjukkan ekuivalen desimal dan kombinasi biner di mana maxterm bernilai 0. Separuh sebelah kanan tabel memperlihatkan tabel kebenanan dan masing-masing maxterm. Perhatikan bahwa nilai dari maxterm sama dengan 0 untuk kombinasi yang bersesuaian dan sama dengan 1 untuk semua kombinasi lain. Sampai di sini jelas dari mana datangnya suku minterm dan maxterm, minterm merupakan fungsi yang tidak sama dengan 0 mempunyai jumlah minimum untuk angka biner 1 dalam tabel kebenarannya. Sementara maxterm merupakan fungsi yang tidak sama dengan 1, dan mempunyai jumlah maksimum untuk angka biner 1 dalam tabel kebenarannya. Perhatikan dani Tabel 4.4 dan Tabel 4.5 terlihat bahwa antara minterm dan maxterm dengan indeks yang sama saling komplemen, yaitu Mj = mj‟. Sebagai contoh untuk j = 3, akan diperoleh

Fungsi Boolean bisa dinyatakan secana aljabar dan tabel kebenaran yang diberikan dengan membentuk jumlahan lojik semua minterm yang dalam fungsi menghasilkan nilai 1. Ekspresi ini disebut dengan sum of minterms (jumlahan minterm). Perhatikan fungsi Boolean F dalam Tabel 4.6 (a). Fungsi bernilal 1 untuk masing-masrng kombinasi biner dan variabel X, Y, dan Z, yaitu : 000, 010, 101, dan 111. Kombinasi-kombinasi ini bersesuaian dengan minterms 0, 2, 5, dan 7. Sehingga fungsi ini bisa dinyatakan secara aljabar sebagai jumlaban lojik dan minterm- minterm yang disebutkan di atas, yaitu :

Bentuk ini selanjutnya disingkat dengan hanya menulis indeks-indeks desimal dan minterms:

Simbol  menunjukkan jumlahan lojik sum (Boolean OR) dari minterms. Kemudian bilanganbilangan yang mengikutinya menyatakan minterm ke - dari fungsi. Huruf-huruf dalam pasangan tanda kurung yang mengikuti F membentuk daftar variabel untuk diambil ketika minterms dikonversikan ke product terms.


13

Sekarang perhatikan komplemen fungsi Boolean. Nilai-nilai biner dan F‟ dalam Tabel 3.6 (a) diperoleh dengan mengganti angka biner 1 dengan angka biner 0 dan sebaliknya dalam nilai-nilai F. Selanjutnya dengan mengambil jumlahan lojik dan minterms diperoleh : atau disingkat menjadi bentuk ringkas sebagai : F‟(XY,Z) m(1,3,4,6). Perhatikan bahwa nomor-nomor minterms untuk F‟ adalah mereka-mereka yang tidak muncul dalam F. Selanjutnya dengan mengkomplemenkan F‟akan diperoleh F, yaitu:

Ini memperlihatkan prosedur untuk menyatakan fungsi Boolean sebagai product of maxterms. Bentuk ringkas dan product ini adalah F(X,Y,Z) M(l,3,4,6) di mana simbol  menunjukkan perkalian lojik (logical product - Boolean AND) dan maxterms yang nomornomornya terdaftar dalam pasangan tanda kurung. Perhatikan bahwa bilangan-bilangan desimal yang disertakan dalam product of maxterms akan selalu sama dengan daftar minterms dan fungsi komplemennya, seperti (1,3,4,6) dalam contoh sebelumnya. Maxterms jarang digunakan secara langsung dalam fungsi-fungsi Boolean, selama masih bisa mengganti mereka dengan daftar minterms dan F‟. Berikut adalah rangkunun tentang sifat-sifat yang sangat penting daii minterms: 1. Untuk fungsi Boolean dengan n variabel, ada 2n minterms. Minterms ini bisa dihitung dan bilangan-bilangan biner dan 0 sampai 2n -1. 2. Setiap fungsi Boolean bisa dinyatakan (expressed) sebagai jumlahan lojik dan minterms. 3. Komplemen dari fungsi memuat minterms yang tidak termasuk dalam fungsi asli (original function). 4. Fungsi yang memuat semua 2n minterms sama dengan lojik 1. Fungsi yang tidak berada dalam bentuk sum-of-minterms bisa dikonversikan ke bentuk sumof-minterms dengan menggunakan tabel kebenaran, karena tabel kebenaran selalu menentukan minterms dan fungsi. Sebagai contoh perhatikan fungsi Boolean E=Y‟ + X‟Z‟ Ekspresi ini tidak dalam bentuk sum-of-minterms, karena masing-masing term tidak memuat semua literal (ketiga variabel X, Y dan Z). Tabel kebenaran untuk fungsi ini bisa dilihat pada Tabel 4.6 (b) di halaman sebelumnya. Selanjutnya dan tabel diperoleh minterm-mintermnya, dan selanjutnya fungsi bisa dinyatakan sebagai sum-of minterms:

Dengan mudah akan diperoleh minterms dan fungsi komplemennya, yaitu:


14

Perhatikan bahwa jumlahan antara banyaknya minterms dalam E dengan banyaknya minterms dalam E‟ sama dengan delapan, karena fungsi yang mempunyai tiga variabel akan menghasilkan delapan minterms. Dengan empat vanabel, secara keseluruhan akan ada sebanyak 16 minterms, dan untuk dua variabel akan ada empat minterms. Contoh fungsi yang memuat semua minterms adalah :

Karena G merupakan fungsi dua variabel dan memuat semua empat minterms, sebingga selalu sama dengan 1.

Jumlahan Perkalian - Sum of Products Bentuk sum-of-minterms merupakan ekspresi aljabar standar yang diperoleh secara langsung dari tabel kebenaran. Ekspresi yang diperoleh dengan cara ini memuat cacah terbesar literal dalam masing-masing term biasanya mempunyai lebih banyak product terms dan yang diperlukan. Ini karena, menurut defimsi masing-masing minterm harus memuat semua variabel dan fungsi, terkomplemen atau tak terkomplemen. Sekali jumlahan minterms diperoleh dan tabel kebenaran, langkah selanjutnya adalah mencoba menyederhanakan ekspresi untuk melihat apakah mungkin mengurangi banyaknya product term dan banyaknya literal dalam term. Hasilnya berupa ekspresi tersederhanakan dalam bentuk sum-ofproducts. ini merupakan bentuk standar lain suatu ekspresi yang memuat product terms dengan sam, dua, atau sejumlah berapa saja literals. Suatu contoh fungsi Boolean yang diekspresikan sebagai sum-of-products adalah

Ekspresi di atas mempunyai tiga product terms, pertama dengan satu literal, kedua dengan tiga literals, dan ketiga dengan dua literals. Diagram lojik untuk suatu bentuk sum-of-products terdiri dan sekelompok gerbang AND diikuti oleh gerbang OR tunggal, sebagaimana diperlihatkan dalam Gambar 4.1. Masing-masing product terms memerlukan gerbang AND, kecuali untuk term dengan literal tunggal. Jumlahan lojik dibentuk dengan suatu gerbang OR yang mempunyai literal tunga1 dan ouiputs dan gerbang AND sebagai inputs. Diasumsikan bahwa variabel-vaniabel input tersedia secana langsung dalam bentuk-bentuk terkomplemen dan tak-terkomplemen mereka, sehingga inverter tidak termuat dalam diagram. Gerbang-gerbang AND diikuti oleh gerbang OR membentuk suatu konfigurasi rangkaian (circuit configuration) yang disebut sebagai implementasi tingkat-dua (two-implementation two-level).


15

Gambar 4.1 Implementasi Sum-of Products

Jika suatu ekspresi tidak berada dalam bentuk sum-of-products, ekspresi tersebut bisa dikonversikan menjadi bentuk standar dengan menggunakan hukum-hukum distributif. Perhatikan ekspresi :

Ekspresi di atas tidak berada dalam bentuk sum-ofproducts, karena term D+E merupakan bagian dan literal product, tetapi bukan literal tunggal. Ekspresi bisa dikonversikan ke sum of products dengan menerapkan hukum distributif yang sesuai sebagai berikut :

Fungsi F diimplementasikan dalam bentuk tak-standar dalam Gambar 4.7 (a). Implementasi ini memerlukan dua gerbang AND dan dua gerbang OR Dalam rangkaiannya ada tiga tingkat penggerbangan (three levels of gating). Kemudian dalam Gambar 4.7 (b) F diimplementasikan dalam bentuk sum-of-products. Rangkaian dalam implementasi ini memerlukan tiga gerbang AND dan satu gerbang OR, dan menggunakan dua tingkat penggerbangan. Keputusan apakah mau menggunakan implementasi tingkat-dua atau tingkat-banyak (tingkat-tiga atau lebih) adalah sangat kompleks. Di antara permasalahan permasalahan yang terlibat adalah banyaknya gerbang, banyaknya masukan gerbang, dan sejumlah delay antara waktu di mana nilai-nilai masukan dipasang dan waktu di mana nilainilai keluaran terlihat. Implementasi-implementasi tingkat-dua merupakan bentuk natural untuk teknologi-teknologi implementasi tertentu.

Gambar 4.7 Implementasi Dua-Tingkat dan Tiga-Tingkat


16

Perkalian Jumlahan - Product Of Sums Bentuk standar lain untuk mengekspresikan fungsi-fungsi Boolean secara aljabar adal ahpro duct-ofsums. Bentuk ini diperoleh dengan membentuk suku-suku perkalian lojik dan jumlahan. Masing-masing suku jumlahan lojik bisa mempunyai berapa saja banyaknya literals yang berbeda. Suatu contoh fungsi yang diekspresikan dalam bentuk product-ofsums adalah F = X(Y‟+ Z)(X + Y + Z‟). Ekspresi ini mempunyai suku-suku jumlahan dengan satu, dua, dan tiga literaic. Suku-suku jumlahan menyelenggarakan operasi OR, dan perkalian adalah operasi AND. Struktur gerbang dari ekspresi product-of-sums terdiri dari sekelompok gerbanggerbang OR untuk suku-suku jumlahan (kecuali untuk suku-suku literal tunggal), diikuti oleh sam gebang AND. Implementasi dan fungsi ini bisa dilihat pada Gambar 4.8. Seperti halnya dengan sum-of products, tipe ekspresi standar ini menghasilkan struktur penggerbangan tingkat-dua.

Gambar 4.8 Implementasi Product of sum

Penyederhanaan dengan MAP- Map Simplification Kompleksitas gerbang-gerbang lojik dijital yang mengimplementasikan fungsi Boolean secara langsung berhubungan dengan ekspresi aijabar dari mana fungsi diimplementasikan. Meskipun representasi tabel kebenaran suatu fungsi adalah tunggal, tetapi ketika diekspresikan secara aijabar, fungsi muncul dalam banyak bentuk yang berbeda. Ekspresi-ekspresi Boolean bisa disederhanakan dengan manipulasi aijabar sebagaimana dibicarakan sebelumnya. Akan tetapi prosedur penyederhanaan im sangat membosankan

karena

kurangnya

aturan-aturan

tertentu

(specific

rules)

untuk

memperkirakan langkah-langkah selanjutnya dalam proses manipulatif. Di samping itu, juga sangat sukar untuk menentukan apakah ekspresi paling sederhana telah dicapai. Sebaliknya, metode Map menyediakan prosedur yang jelas untuk penyederhanaan fungsifirngsi Boolean sanrpam empat vanabel. Meskipun Map untuk lima dan enam variabel masih bisa digambar, akan tetapi sudah tidak praktis (cumbersome) untuk digunakan. Map ini juga dikenal sebagai Karnauh-map, atau K-map. Map yang dimaksud merupakan diagram yang dibentuk dan bujur sangkar-bujur sangkar (squares), dengan masing-masing bujur sangkar Universitas Gadjah Mada

17

mewakili satu minterm dan fungsi. Karena sebarang fungsi Boolean bisa dinyatakan sebagai sum of minterms, maka fungsi Boolean secara grafik dikenal dalam Map oleh bujursangkarbujursangkar yang minterm -nya disertakan dalam fungsi. Kenyataannya Map menyajikan diagram visual dan semua cata yang mungkin suatu fungsi diekspresikan dalam bentuk standar. Dengan mengenali berbagai macam pola, pengguna bisa menurunkan ekspresi aljabar lain untuk fungsi yang sama, dan dan beberapa fungsi yang bisa diturunkan, kemudian dipilih yang paling sederhana. Ekspresi-ekspresi tersederhana yang dihasilkan oleh Map selalu dalam bentuk sumof products atau product-of-sums. Selanjutnya akan dianggap bahwa ekspresi aljabar yang paling sederhana adalah mereka yang banyaknya minterm terkecil dan mereka yang jumlah literal-nya terkecil dalam masing-masing term. Proses ini menghasilkan implementasi tingkat-dua yang mempunyai suatu diagram rangkaian lojik dengan banyaknya gerbang terkecil dan banyaknya inputs ke gerbang juga terkecil. Selanjutnya akan bisa dilihat bahwa ekspresi tersederhana tidak harus tunggal. Sehingga senngkali mungkin ditemukan dua atau lebih ekspresi yang memenubi kriteria penyederbanaan. Dalam kasus seperti ini, salah satu penyelesaiannya sama-sama memuaskan. Map Dua-Variabel Two- variable Map Untuk fungsi Boolean dua variabel ada empat minterms. Sehingga map dua-variabel terdiri dari empat bujursangkar, masing-masing untuk satu minterm, sebagaimana diperlihatkan dalam Gambar 4.9 (a). Map digambar kembali dalam Gambar 49. (b) untuk memperlihatkan hubungan antara bujursangkar-bujursangkar dengan dua-variabel X dan Y Tanda-tanda 0 dan 1 pad.a sisi kiri dan atas dan map menandakan nilai dan variabelvariabel. Variabel X muncul terkomplemen pada baris 0 dan tak terkomplemen pada baris 1. Secara serupa, X muncul terkomplemenkan pada kolom 0 dan tak terkomplemenkan pada kolom 1. Perhatikan bahwa empat kombinasi dan nilai-nilai biner ini bersesuaian dengan baris-baris tabel kebenaran yang terhubung dengan empat minterms.

Gambar 4.9

Gambar 4.10

Map Dua-variabel

Representasi fungsi dalam Map


18

Suatu fungsi dengan dua variabel bisa dinyatakan dalam map dengan menandai bujur sangkar - bujursangkar yang bersesuaian dengan minterm-minterm fungsi. Sebagai contoh, fungsi XY diperlihatkan dalam Gambar 4.10 (a). Karena XY sama dengan minterm m3, nilai biner 1 ditempatkan dalam bujur sangkar milik m3. Gambar 4.10 (b) memperlihatkan map untuk jumlahan lojik dan tiga mirnterms m1 + m2 + m3 = X‟Y + XY‟ + XY = X + Y Ekspresi tersederhana X + Y ditentukan dan daerah dua-bujur sangkar untuk variabel X dalam baris kedua dan daerah dua-bujursangkar untuk Y dalam kolom kedua. Bersamasama, dua daerah ini yang termuat dalam tiga bujursangkar kepunyaan X atau Y. Penyederhanaan ini bisa diperlihatkan dengan manipulasi aijabar:

Map Tiga-Variabel Three-variable Map Untuk tiga variabel biner ada delapan minterms. Oleh karena itu map tiga-variabel terdiri dari delapan bujursangkar seperti diperlihatkan dalam Gambar 4.11. Map yang digambar di bagian (b) ditandai dengan bilangan-bilangan biner untuk masing-masing baris dan masing-masing kolom untuk memperlihatkan nilai-nilai biner dan minterms. Perhatikan bahwa bilangan-bilangan sepanjang kolom tidak unit. Karakteristik dan barisan terdaftar (bilangan-bilangan) adalah hanya berubah satu bit dalam nilai dan satu kolom yang berdampingan (adjacern) dengan kolom berikutnya.

Gambar 4.11 Map tiga-variabel

Sebuah bujursangkar minterm bisa ditempatkan dalam map dengan dua cara. Pertama, kita bisa mengingat bilangan-bilangan yang terdaftar dalam Gambar 4.11(a) untuk masing-masing lokasi minterm, atau kita bisa mengacu bilangan-bilangan biner sepanjang baris-baris dan kolom-kolom dalam Gambar 4.12 (b). Sebagai contoh, bujursangkar yang diassign ke m3 bersesuaian dengan baris 1 dan kolom 01. Jika dua bilangan ini digabung akan menjadi bilangan 101, yang ekuivalen dengan desimal 5. Cara lain untuk mencari bujursangkar m5 = XYZ adalah dengan memperhatikannya dalam baris bertanda X dan kolom kepunyaan Y‟Z (kolom 01). Perhatikan bahwa ada empat Universitas Gadjah Mada

19

bujursangkar di mana masing-masing variabel sama dengan 1 dan empat yang lain di mana masing-masing variabel sama dengan 0. Variabel yang muncul tak-terkomplemen dalam empat bujursangkar di mana nilainya sama dengan I dan terkomlemen dalam empat bujursangkan di mana nilainya sama dengan 0. Untuk kenyamanan, tuliskan nama-nama vaniabel bersama dengan empat bujursangkar di mana vaniabel tersebut dikomplemenkan. Setelah terbiasa dengan map, penggunaan variabel-variabel sendirian sudah cukup untuk memberi label daerah-daerah map. Akhirnya, penting untuk diperhatikan lokasi dan labellabel ini untuk mendapatkan semua minterms pada map. Dalam map dua-variabel, fungsi XY mendemonstrasikan bahwa suatu fungsi atau sebuah term untuk suatu fungsi bisa terdiri dari bujursangkar tunggal dalam map. Akan tetapi untuk mencapai penyederhanaan perlu memperhatikan bujursangkar-bujursangkar yang bersesuaian

dengan

product

terms.

Untuk

memahami

bagaimana

penggabungan

bujursangkar-bujursangkar bisa menyederhanakan fungsi-fungsi Boolean, terlebih dahulu baris mengenali sifat-sifat dasar yang dipunyai oleh bujur sangkar-bujursangkar yang bertetangga, yaitu setiap dua bujursangkar yang ditempatkan secara horisontal atau vertikal (tapi tidak secara diagonal) membentuk sebuah bujursangkar yang bersesuaian dengan minterm yang berbeda hanya dalam satu variabel. Variabel tunggal ini muncul takterkomplemen dalam satu bujursangkar dan terkomplemen dalam bujursangkar lain. Sebagai contoh, m5 dan m7 bertempat dalam dua bujursangkar yang adjacent. Variabel Y dikomplemenkan dalam m5 dan tidak dikomplemenkan dalam m7, sementara dua variabel yang lain cocok dalam kedua bujursangkar. Jumlahan lojik dari dua minterms bertetangga seperti ini bisa disederhanakan menjadi product term tunggal dan dua variabel: m5+m7 = XY‟Z+XYZ=XZ(Y‟+Y)XZ Dalam hal ini dua bujursangkar tersebut hanya berbeda dalam variabel Y, yang bisa dihilangkan jika jumlahan lojik (OR) dan dua minterms dibentuk. Sehingga, pada map 3variabel, setiap dua minterms dalam bujursangkar yang bertetangga bisa di-OR-kan bersama menghasilkan sebuah product term dan dua variabel. Contoh 4.3 Penyederhanaan Fungsi Boolean Menggunakan Map Sederhanakan fungsi Boolean F(X,Y,Z) = ∑m(2,3,4,5). Pertama-tama, masing-masing minterm yang mewakili fungsi ditandai dengan 1, lihat Gambar 4.12, di mana bujursangkar-bujursangkar untuk minterms 010, 011, 100, dan 101 ditandai dengan 1. Langkah selanjutnya adalah menjelajahi (explore) koleksi bujursangkarbujursangkar pada map yang mewakili product terms untuk dipertimbangkan dalam ekspresi tersederhana. Selanjutnya objek-objek mi disebut rectangles (empat persegi panjang-empat persegi panjang), karena bentuk mereka adalah persegi-panjang (tentunya termasuk bujursangkar). Akan tetapi, rectangles yang bersesuaian dengan product terms dibatasi Universitas Gadjah Mada

20

hanya memuat jumlah bujursangkar sebanyak bilangan pangkat 2, seperti 1, 2, 4, 8 Sehingga tujuan kita adalah menemukan jumlah paling kecil bujursangkar-bujursangkar seperti yang memuat semua minterms yang ditandai dengan 1. Hal ini akan memberi product terms dengan juinlah terkecil. Pada map dalam gambar, dua bujursangkar memuat empat bujursangkar yang semuanya memuat 1. Bujursangkar kanan atas mewakili product term X‟Y, yang ditentukan dengan mengamati bahwa bujursangkar berada dalam baris 0, bersesuaian dengan X‟, dan dua kolom akhir bersesuaian dengan Y. Secara serupa, bujursangkar kiri bawah mewakili product term XY‟ (Baris kedua mewakili X dan dua kolom kiri mewakili Y‟.) Karena dua rectangles ini semua memuat angka biner 1 dalam map, jumlah lojik dan dua product terms yang bersesuaian memberikan ekspresi tersederhana untuk F; F=X‟Y+XY‟

Gambar 4.12 Map untuk fungsi F = ∑m(2,3,4,5) = X’Y + XY’ Dalam beberapa kasus, dua bujursangkar dalarn map yang bertetangga membentuk suatu rectangle dengan ukuran dua, meskipun mereka tidak saling bersinggungan. Sebagai contoh, dalam Gamban 4.13, mo bertetangga dengan m2 dan m4 bertetangga dengan m6 karena minterms dibedakan oleh satu vaniabel. Selanjutnya bisa dibuktikan secara aljabar sebagai berikut:

Gambar 4.13 Map Tiga-variabel dalam bentuk Rata dan Silinder untuk menunjukkan bujursangkar yang adjacent


21

Empat segiempat untuk product terms ini diperlihatkan dalam Gambar 4.13 (a). Perhatikan bahwa product term Z‟ menggunakan fakta bahwa tepi-tepi kiri dan kanan map adalah adjacent untuk membentuk segiempat. Dua contoh lain dan segiempat yang bersesuaian dengan product terms yang diturunkan dari empat minterms ditunjukkan dalam Gambar 4.13 (b). Pada umumnya, semakin banjak bujunsangkar digabung, akan diperoleh product term dengan jumlah literal semakin kecil . Untuk map tiga-variabel: 

Satu bujursangkar mewakili sebuah minterm dengan tiga literal



Segiempat dengan dua bujursangkar mewakili sebuah product term dengan dua literal



Segiempat dengan empat bujursangkar mewakili sebuah product term dengan satu literal



Segiempat dengan delapan bujursangkar memuat semua map menghasilkan suatu fugsi yang selalu sama dengan lojik 1.

Gambar 4.14 Product term menggunakan empat minterms

Contoh 4. 4 Penyederhanaan Fungsi 3-Variabel Dengan Map Sederhanakan dua fungsi Boolean berikut:

Map untuk F1 diperlihatkan dalam Gambar 4.15 (a). Ada empat bujursangkar yang diberi tanda dengan 1, yaitu untuk masing-masing minterm dan fungsi. Dua bujursangkar yang adjacent dalam kolom ketiga untuk menghasilkan term dua-literal YZ. Sisa dua bujursangkar dengan 1 juga adjacent menurut definisi cylinder-based dan diperlihatkan dalam diagram dengan nilai-nilai mereka termuat dalam separoh segiempat. Ketika Universitas Gadjah Mada

22

digabung, dua separoh segiempat ini akan menghasilkan term dua-literal XZ‟. Sehingga, fungsi tersederhananya adalah F1(X,Y,Z) = YZ + XZ‟ Map untuk F2 diperlihatkan dalam Gambar 4.15 (b). Pertama-tama, empat bujursangkar yang adjacent dalam kolom-kolom pertama dan terakhir bisa digabung dan menghasilkan term dengan literal tunggal Z‟ Sisa bujursangkar tunggal mewakili minterm 5 dan digabung dengan sebuah bujursangkar yang adjacent dengannya meskipun sudah digunakan. Hal seperti ini tidak hanya diperbolehkan, melainkan diperlukan sekali, karena dua bujursangkar yang adjacent menghasilkan term dua-literal XY‟ Sementara bujursangkar tunggal mewakili minterm tiga-literal XY‟Z. Selanjutnya, fungsi tersederhananya adalah: F2(X,Y,Z) = Z‟,+ XY‟ Pada suatu saat ada cara-cara alternatif dalam penggabungan bujursangkarbujursangkar untuk menghasilkan ekspresi-ekspresi tersederhan yang sama. Suatu contoh untuk ini didemonstrasikan dalam map Gambar 4.16. Minterm 1 dan 3 digabung untuk menghasilkan term XZ, dan minterm 4 dan 6 menghasilkan term XZ‟ Akan tetapi ada dua cara bahwa bujursangkar dan minterm 5 bisa digabung dengan bujursangkar adjacent yang lain untuk menghasilkan term dua-literal ketiga. Penabungan minterm 5 dengan minterm 4 menghasilkan term XY‟, sementara penggabungannya dengan minterm 1 menghasilkan term YZ. Masing-masing dua kemungkinan ekspresi tersederhana bisa dilihat pada Gambar 4.16, masing-masing mempunyai tiga terms dengan dua literal, sehingga ada dua penyelesaian tersederhana yang mungkin untuk fungsi ini.

Gambar 4.15 Map untuk contoh 4.4

Jika fungsi tidak dinyatakan sum-of-minterms, kita bisa menggunakan map untuk mendapatkan minterm-minterm dan fungsi, dan kemudian menyederhanakan fungsi. Akan tetapi, perlu mempunyai ekspresi aijabar dalam bentuk sum-of-products, di mana dan masing-masing product term tersebut bisa dengan mudah diplot (plotted) dalam map. Minterm-minterm dan fungsi selanjutnya dibaca secara Iangsung dan map. Sebagai contoh, perhatikan fungsi Boolean Universitas Gadjah Mada

23

Tiga product terms dalam ekspresi di atas mempunyai dua literal dan dinyatakan dalam map tiga-variabel masing-masing dengan dua bujursangkar. Dua bujursangkar bersesuaian dengan term pertama, X‟Z, yang bisa ditemukan dalam Gambar 4.16 sebagai perpotongan dan X‟ (baris pertama) dengan Z (dua kolom tengah), dan menghasilkan bujursangkar-bujursangkar 001 dan 011. Perhatikan bahwa jika menandai dengan bit 1 dalam bujursangkar, ada kemungkinan menjumpai bit 1 sudah berada di bujursangkar tersebut dan term sebelumnya. Kasus ini terjadi pada term kedua X‟Y, yang mempunyai bit 1 dalam bujursangkar-bujursangkar 011 dan 010; akan tetapi bujursangkar 011 sama (common) dengan term pertama X‟Z, sehingga hanya satu bit 1 yang ditandalan dalam bujursangkar tersebut. Dengan melanjutkan model seperti ini, akhirnya akan diperoleh bahwa fungsi ini mempunyai lima minterms, sebagaimana yang ditandakan oleh lima bit 1 dalam gambar. Minterms dibaca secara langsung dan map sebagai 1, 2, 3, 5, dan 7. Fungsi aslinya mempunyai empat product terms, yang bisa disederhanakan pada map menjadi hanya dua term sederhana, F = Z + X‟Y, yang memberi pengurangan sangat berarti dalam biaya implementasi.

Map Empat VariabeI - Four variable Map Untuk empat variabel biner ada 16 minterms, oleh karena itu map empat-variabel terdiri dari 16 bujursangkar, sebagaimana diperlihatkan dalam Gambar 4.18. Pemasangan minterm dalam masing-masing bujursangkar ditunjukkan dalam diagram bagian (a). Map yang digambar di bagian (b) untuk memperlihatkan hubungan empat variabel Baris-baris dan kolom-kolom diberi nomor sedemikian hingga hanya Satu bit dan bilangan biner yang berubah nilai antara setiap dua kolom atau baris yang adjacent, yang menjamin kesamaan sifat untuk bujursangkar-bujursangkar yang adjacent. Minterm yang bersesuaian dengan masing-masing bujursangkar bisa diperoleh dengan menggabung nomor baris dengan nomor kolom. Sebagai contoh, jika nomor dalam bans ke-tiga (11) dan kolom ke-dua (01) digabung akan menghasilkan bilangan biner 1101, yaitu ekuivalen biner 13. Sehingga Universitas Gadjah Mada

24

bujursangkar di baris ke-tiga dan kolom ke-dua mewakili minterm m13. Di samping itu, masing-masing variabel ditandai dalam map untuk memperlihatkan delapan bujunsangkar di mana ia musical tak-terkomplemen. Delapan bujursangkar lain, yang labelnya tidak dimunculkan

bersesuaian

dengan

variabel

terkomplemen.

Sehingga,

W

muncul

terkomplemen dalam dua baris pertama dan tak-terkomplemen dalam dalam dua baris kedua.

Gambar 4.18 Map Empat-variabel

Metode yang digunakan untuk menyederhanakan fungsi empat-variabel serupa dengan metode yang digunakan untuk menyederhanakan fungsi-fungsi tiga-variabel. Bujursangkar-bujursangkar

yang

bertetangga

didefinisikan

sebagai

bujursangkar-

bujursangkar yang saling bersebelahan, sebagaimana untuk map dua- dan tiga-variabel. Dengan kata lain, tepi-tepi bawah dan atas, kiri dan kanan saling bersinggungan sebagai bujur sangkar yang adjacent. Sebagai contoh, mo dan m2, mo dan m8, dan seterusnya merupakan dua bujur sangkar yang adjacent. Kombinasi bujursangkar yang bisa dipilih selama proses penyederhanaan dalam map empat-variabel adalah sebagai berikut: 

Segiempat dengan 1 bujur sangkar mewakili sebuah minterm empat literals.



Segiempat dengan 2 bujur sangkar mewakili sebuah minterm tiga literals.



Segiempat dengan 4 bujur sangkar mewakili sebuah minterm dua literals.



Segiempat dengan 8 bujur sangkar mewakili sebuah minter satu literal., dan segiempat dengan 16 bujur sangkar menghasilkan fungsi yang selalu sama dengan lojik 1. Tidak ada kombinasi lain yang bisa digunakan. Suatu product term dan dua literal XZ‟

yang menarik diperlihatkan dalam Gambar 4.19. Product term ini perlu diperhatikan karena sering kali hilang (atau tidak diperhitungkan). Di samping itu juga untuk mengingatkan kalau tepi bawah dan atas adalah adjacent, demikian juga tepi kiri dan kanan.


25

Gambar 4.19 Map Empat-vaniabel untuk memperlihatkan Adjaceny

Contoh 4.5 Penyederhanaan Fungsi Empat-variabel dengan Map Sederhanakan fungsi Boolean F(WX,Y,Z,) = ∑m(0, 1,2,4,5,6,8,9,12,13,14)

Minterms dan fungsi ditandai dengan angka 1 dalam map Gambar 4.20. Delapan bujursangkar dalam dua kolom sebelah kiri digabung menjadi segiempat yang mewakili term dengan satu literal Y Sisa tiga angka 1 tidak bisa digabung menjadi term yang tersederhana, melainkan mereka harus digabung sebagai segiempat dengan dua- atau empatbujursangkar. Dua angka 1 bagian atas kanan digabung déngan dua angka 1 bagian atas kiri menghasilkan term W‟Z. Sebagai catatan lagi bahwa diperbolehkan menggunakan bujursangkar sama lebih dari satu kali. Sekarang tinggal sebuah bujursangkar dengan tanda angka I dalam baris ketiga dan kolom keempat (yaitu mewakili minterm 1110). Daripada mengambil bujursangkar ini sendirian yang akan menghasilkan term dengan empat literal, bujursangkar ini akan digabung dengan bujursangkar yang sudah digunakan untuk membentuk sebuah segi-empat dengan empat bujursangkar dalam dua bans tengah dan dua kolom akhir, menghasilkan term XZ‟. Selanjutnya ekspresi tersederhananya merupakan jumlahan lojik dan tiga terms: F = Y‟ + W‟Z‟ + XZ‟ Universitas Gadjah Mada

26

Contoh 4..6 Penyederhanaan Fungsi Empat-vañabel dengan suatu Map Sederhanakan fungsi Boolean F = A’B’C’ + B’CD’ + AB’C’ + A’BCD’ Fungsi di atas mempunyai empat variabel A, B, C, dan D yang dinyatakan dalam bentuk sum-of-products dengan tiga term tiga-literal dari Satu term empat-literal. Selanjutnya daerah dalam map yang ditumpu oleh fungsi diperlihatkan dalam Gambar 4.21. Masingmasing term tiga-literal dinyatakan dalam map dengan dua bujursangkar. A „B „C‟ dinyatakan oleh bujursangkar-bujursangkar 0000 dan 0001, B „CD‟ oleh bujursangkar-bujursangkar 0010 dan 1010,dan AB‟C‟ oleh bujursangkar-bujursangkar 1000 dan 1001. Kemudian term dengan empat literal adalah 0110. Fungsi disederhanakan dalam map dengan mengambil angka-angka 1 di empat sudut, dan menghasilkan term B „D‟. Dua angka 1 dalam bans paling atas diagbung dengan dun angka 1 dalam bans paling bawah untuk menghasilkan term B „C‟. Angka 1 sisa dalam bujursangkar, 0110, digabung dengan bujursangkar yang adjacent

dengannya,

0010,

untuk

menghasilkan

term

A„CD‟.

Sehingga,

fungsi

tersederhananya adalah

Manipulasi Map - Map manipulations Ketika menggabungkan bujursangkar-bujursangkar dalam map, supaya dipastikan bahwa semua minterm dalam fungsi termasuk. Pada waktu yang sama, supaya meminimalkan jumlah term dalam fungsi tersederhana dengan menghindari setiap term yang berlebih yaitu minterm yang sudah termuat dalam term lain.

Prime Implicants Penting -Essentiai Prime Implicants Dengan diperkenalkannya implicant, prime implicant, dan essential prime iwplicant akan menjadikan prosedur penggabungan bujursangkar-bujursangkar dalam sebuah map lebih sistematik. Suatu product term merupakan suatu implicant sebuah fungsi jika fungsi mempunyai nilai I untuk semua minterm dan product term tersebut. Jelasnya, semua segiempat pada sebuah map yang terbentuk dari bujursangkar-bujursangkar yang memuat nilai Universitas Gadjah Mada

27

1 bersesuaian dengan implicants. Suatu implicant P merupakan prime itnplicant apabila dengan menghilangkan sebarang literal dan implicant P menghasilkan suatu product term yang bukan lagi merupakan implicant dan fungsi. Pada map untuk fungsi n-variabel, himpunan prime implicant bersesuaian dengan himpunan semua segi empat yang terbuat dan 2m bujursangkar-bujursangkar yang memuat nilai 1 (m =0, 1, ..., n), dengan masingmasing segi-empat memuat sebanyak mungkin bujursangkar. Jika sebuah minterm suatu fungsi termuat hanya dalam satu prime implicant, maka prime implicant dikatakan essential Sehingga, jika sebuah bujursangkar memuat nilai 1 hanya berada dalam satu segi-empat yang menyatakan sebuah prime implicant, maka prime implicant, tersebut essential. Dalam Gambar 4.16 berikut, term-term XZ dan XZ‟ merupakan prime implicants, yang essential sementara term-term XY‟ dan Y7 merupakan prime implicants nonessential.

Prime implicant suatu fungsi bisa diperoleh dari map suatu fungsi sebagai semua koleksi maksimum yang mungkin dan 2m bujursangkar-bujursangkar yang memuat nilai 1 (m=0, 1, ..., n), yang membentuk segiempat. Ini berarti bahwa nilai 1 tunggal pada map menyatakan sebuah prime implicant jika tidak adjacent dengan nilai I lain manapun. Dua nilai 1 membentuk segi-empat yang mewakili prime implicant, selama mereka tidak berada dalam segi-empat yang terdini dan empat atau lebih bujursangkar yang memuat nilai 1. Empat nilai I membentuk segi-empat yang mewakili prime implicant, jika mereka tidak berada dalam segi-empat yang terdini dan delapan atau lebih bujursangkar yang memuat nilai 1, dan seterusnya. Prosedur sistematis untuk menemukan ekspresi tersederhana dari map terlebih dahulu perlu menentukan semua prime implicans. Selanjutnya, ekspresi tersederhana diperoleh dan jumlahan lojik semua essential prime implicants, ditambah prime implicantsprime implicants lain yang dipenlukan untuk memasukkan sisa minterm yang tidak termasuk dalam essentialprime implicants. Untuk lebih jelasnya akan diberikan contoh berikut.


28

Contoh 4.7 Penyederhanaan Dengan Prime Implicarns Menurut Gambar 4.22, ada tiga cara untuk melakukan penggabungan empat bujursangkar menjadi segi-empat. Product term yang diperoleh dan penggabungan ini adalah prime implicant-prime implicant fungsi, yaitu A „D, BD‟, dan A B. Term A V dan BD‟ merupakan essential prime implicants, akan tetapi A „B tidak essential. Karena minterm 1 dan 3 hanya bisa termuat dalam term A „D, dan minterms 12 dan 14 hanya bisa termuat dalam term BD‟. Akan tetapi minterms 4, 5, 6, dan 7 masing-masing termuat dalam dua prime implicants, salah satunya adalah A „B, sehingga term A „B bukan essential prime implicant. Sebenannya, sekali essential prime implicant terpilih, term ketiga tidak diperlukan karena semua minterm sudah termuat dalam essentialprime implicants. Sehingga ekspresi tersederhananya adalah F = A „D + BD‟ Contoh 4.8 Penyederhanaan Melalui Essential & Nonesential Prime Implicants Untuk contoh ini diperlihatkan dalam Gambar 4.23. Fungsi yang digambar di bagian (a) mempunyai tujuh minterms. Jika kita mencoba menggabung bujursangkan-bujursangkar, kita akan menjumpai bahwa ada enam prime implicants. Untuk mendapatkan jumlah minimal minterm untuk fungsi, terlebih dahulu kita harus menentukan prime implicant-prime imp licant yang essential. Sebagaimana diperlihatkan di bagian (b), fungsi mempunyai empat prime implicants yang essential Product term AB „CV‟ adalah essential karena satu-satunyaptime imp licant yang memuat minterm 0. Secara serupa, product terms BC‟D, ABC‟, dan AB „C merupakan prime implicant yang essential karena mereka masing-masing merupakan satu-satunya prime implicant yang memuat minterms 5, 12, dan 10. Minterm 15 termuat dalam dua nonessential prime implicants. Selanjutnya ekspresi tersederhana untuk fungsi merupakan jumlahan lojik dan empat essential prime implicants dan satu prime implicant yang memuat minterm.

Identifikasi essential prime implicants dalam map menyediakan alat tambahan yang mempenlihatkan term-term yang hams muncul dalam setiap ekspresi sum-of-product untuk fungsi, dan menyediakan struktur parsial untuk metode yang lebih sistematis dalam pemilihan pola-pola bujursangkar.


29

(a) Penempatan minterms

(b) Prime implicant yang penting

Gambar 4.23 Penyederhaan dengan Prime Implicants dalam Contoh 4.8 Prime Implicant Tak-Penting Nonessential Prime implicants Di luar penggunaan semua prime implicant yang penting, aturan berikut bisa diterapkan untuk mengikutkan minterm-minterm sisa dan fungsi dalam prime implicants takpenting: Aturan pemilihan : minimalkan di antara prime implicant yang overlap sebanyak mungkin. Khususnya, dalam penyelesaian akhir pastikan bahwa masing-masing prime implicant yang terpilih memuat paling sedilcit sam minterm yang tidak termuat dalam prime implicant terpilih lain manapun. Dalam kebanyakan kasus, ini akan menghasilkan suatu ekspresi tersederbana meskipun tidak harus minimum-cost. Penggunaan aturan pemilihan diilustrasikan dalam contoh berikut:

Contoh 4.9 Penyederhanaan Fungsi Menggunakan Aturan Pemilihan. Tentukan bentuk sum-of-products tersederhana untuk F(A,B,C,D) = Em (0, 1,2, 4,5, 10, 11, 13, 15). Map untuk F diberikan dalam Gambar 4.24, dengan memperlihatkan semua prime implicants. A „C‟ adalah satu-satunya essential prime implicant. Dengan menggunakan aturan pemilihan di depan, kita bisa memilih prime implicants sisa untuk bentuk sum-ofproducts dengan unutan sesuai penomoran. Perhatikan bagaimana prime implicant 1 dan 2 dipilih untuk memuat minterm-minterm tanpa overlapping. Prime implicant 3 (A „B „D‟) dan prime implicant B „CD‟ keduanya memuat satu minterm sisa 0010, dan prime implicant 3 dipilih dengan cara sebarang untuk memuat minterm dan melengkapi ekspresi sum-ofproducts: F(A,B,C)=A‟C‟+ABD +AB‟C+A‟B‟D‟


30

Gambar 4.24 Map untuk contoh 4.9

Penyederhanaan Product of Sums - Product of Sums Simplification Fungsi-fungsi Boolean tersederhana yang diturunkan dan map dalam semua contoh sebelumnya dinyatakan dalam bentuk sum-of-products. Dengan hanya modifikasi kecil, bentuk product-of-sum bisa diperoleh. Prosedur untuk memperoleh suatu ekspresi tersederhana dalam bentuk product-of sum mengikuti sifat-sifat dasar fungsi Boolean. Bit I yang diIempatkan dalam bujursangkarbujursangkar map menyatakan minterm dan fungsi. Minterm-minterm tidak termuat dalam fungsi kepunyaan komplemen fungsinya. Dari sini kita melihat bahwa komplemen dari suatu fungsi dinyatakan dalam map dengan oleh bujursangkar-bujursangkar yang tidak ditandai dengan bit 1. Jika sekarang kita tandai bujursangkar-bujursangkar kosong dengan bit 0 dan menggabung mereka menjadi segiempat-segiempat yang valid, maka kita akan mendapat suatu ekspresi tersederhana dan komplemen suatu fungsi. Kemudian kita akan mengambil komplemen dan fungsi F‟ untak mendapatkan fungsi F sebagai product-of sums. Hal ini dikerjakan dengan mengambil dual fungsi dan kemudian mengkomplemenkan masingmasing literal, seperti yang sudah dijelaskan dalam bagian sebelumnya. Contoh 4.10 Penyederhaan Bentuk Product-of sum Sederhanakan fungsi Boolean berikut dalam bentuk product-of sums: F(A,B,C,D) = ∑m(0,1,2,5,8,9,10) Tanda bit 1 dalam map Gambar 4.25 menyatakan minterm-minterm fungsi. Bujursangkarbujursangkar yang ditandai dengan bit 0 menyatakan minterm-minterm yang tidak termuat dalam F dan oleh karena itu menunjukkan komplemen dan F. Dengan menggabung bujursangkar-bujursangkar yang ditandai dengan bit 0, kita mendapatkan komplemen fungsi tersederhana F‟ = AB + CD + BD‟


31

Kemudian dengan mengambil dualnya, dan mengkomplemenkan masing-masing literalnya akan menghasilkan komplemen dan F‟, yaitu fungsi F dalam bentuk product-of sums: F= (A‟+B‟)(C‟+D‟)(‟B‟+D)

Contoh sebelumnya memperlihatkan prosedur untuk mendapatkan penyederhanaan product-of-sums jika fungsi aslinya diyatakan sebagai jumlahan minterm-minterm. Prosedur juga valid jika fungsi aslinya dinyatakan sebagai product of maxterms atau product-of sums. Ingat bahwa nomor-nomor maxterm sama dengan nomor-nomor minterm dan fungsi terkomplemen, sehingga bit 0 dimasukkan ke dalam map untuk maxterm-maxterm atau komplemen dan fungsi. Untuk memasukkan suatu fungsi yang dinyatakan sebagai productof sums ke dalam map, kita mengambil komplemen dari fungsi dan dari hasil tadi tentukan bujursangkar-bujursangkar untuk ditandai dengan bit 0. Sebagai contoh, fungsi F (A‟+B‟+ C)(B +D) Bisa diplot dalam map dengan terlebih dahulu menentukan komplemennya, yaitu F‟ =ABC‟ + B „D‟. Kemudian menandai bujursangkar-bujursangkar yang menyatakan minterm dan fungsi F‟ dengan bit 0. Selanjutnya bujursangkar-bujursangkar sisa diberi tanda dengan bit 1. Peuggabungan bit-bit 1 akan menghasilkan ekspresi tersederhana dalam bentuk sum-ofproducts. Sedang penggabungan bit-bit 0 dan kemudian mengkomplemenkan alan meughasilkan ekspresi tersederhana dalam bentuk product-of-sums. Sehingga, untuk sebatang fungsi yang diplot pada map, kita bisa menurunkan fungsi tersederhana dalam salah satu dan dua bentuk standar. Kondisi Don’t Care - Don’t Care Condition Minterm-minterm suatu fungsi Boolean menentukan semua kombinasi dan nilai-nilai vanabel di mana fungsi sama dengan 1. Fungsi dianggap sama dengan 0 untuk mintermminterm sisanya. Akan tetapi anggapan ini tidak selalu valid, karena aplikasi-aplikasi di mana Universitas Gadjah Mada

32

fungsi tidak ditentukan untuk kombinasi nilai-nilai variabel tertentu. Kasus ini bisa terjadi karena dua kemungkinan. Kemungkinan pertama, kombinasi-kombinasi input tidak pernah muncul. Sebagai contoh, kode biner empat-bit untuk angka-angka desimal mempunyai enam kombinasi yang tidak digunakan dan tidal diharapkan muncul. Kemungkinan kedua, kombmasi-kombinasi input diharapkan muncul, akan tetapi kita tidal peduli (do not care don‟t care) output apa yang dihasilkan sebagai tanggapan untuk kombinasi-kombinasi tersebut. Dalam kedua kasus, outputs dikatakan tak-ditentukan (unspecified) untuk kombmasi-kombinasi inputs. Fungsi-fungsi yang mempunyai output tak-ditentukan untuk suatu kombinasi inputs disebut “fungsi tertentu secara tidak lengkap” (incompletely specified functions). Dalam kebanyakan penerapan, kita cukup tidak mempedulikan nilai apa yang diasumsikan fungsi untuk minterm-minterm tak-ditentukan. Untuk alasan ini, biasanya minterm-minterm tak-ditentukan (unspecified minterms) dan fungsi disebut sebagai “don‟t care conditions” Kondisi-kondisi ini bisa digunakan pada map untuk menyediakan penyederhanaan Iebih lanjut dan fungsi. Perlu disadari bahwa minterm don‟t care tidak bisa ditandai dengan bit 1 pada map, karena jika demikian akan berarti bahwa fungsi sama dengan 1. Demikian juga dengan menempatkan bit 0 pada map (khususnya bujursangkar) akan berarti bahwa fungsi sama dengan 0. Untuk membedakan kondisi don‟t care dengan bit 1 dan 0, digunakan simbol X. Sehingga suatu simbol X di dalam bujursangkar pada map menandakan bahwa kita tidak peduli apakah nilai 0 atau I yang di-assign ke fungsi untuk minterm tertentu. Dalam

pemilihan

bujur

sangkar-bujur

sangkar

yang

adjacent

untuk

menyederhanakan fungsi dalam map, don‟t care minterm bisa dianggap sama dengan 1 atau 0. Ketika menyederhanakan fungsi, kita bisa memilih untuk memasukkan masing-masing don‟t care minterm dengan bit 1 atau bit 0, tergantung pada kombinasi mana yang menghasilkan ekspresi tersederhana. Di samping itu, suatu don‟t care minterm tidak harus dipilih, jika tidak memberi kontribusi untuk menghasilkan implicant yang lebih besar. Secara keseluruhan pemilihan tergantung pada penyederhanaan yang akan dicapai. Contoh 4.11 Penyederhanaan dengan Kondisi Don’t Care Untuk memperjelas prosedur yang digunakan untuk menangani kondisi don‟t care, perhatikan fungsi F yang terspesifikasi secara tidak lengkap yang mempunyai tiga don‟t care minterms d:

Minterm-minterm dari F adalah kombinasi variabel-variabel yang membuat fungsi sama dengan 1, sementara minterm-minterm dan d adalah don‟t care minterms yang bisa diassign dengan 0 atau 1. Penyederhanaan map diperlihatkan dalam Gambar 4-26. MintermUniversitas Gadjah Mada

33

minterm dan F diberi tanda bit 1, minterm-minterm dan d diberi tanda dengan simbol X, dan bujur sangkar-bujur sangkar sisa diisi dengan bit 0. Untuk mendapatkan fungsi tersederhana dalam bentuk sum-of products, kita harus menyertakan semua lima bit 1 dalam map, tapi symbol X mungkin atau mungkin tidak disertakan tergantung bagaimana fungsi F disederhanakan. Term CD memuat empat minterms dalam kolom ke-tiga, sisa minterm dalam bujur sangkar 0001 bisa digabung dengan bujun sangkar 0011 untuk menghasilkan term tiga-literal. Akan tetapi, dengan menyertakan sam atau dua simbol X yang adjacent kita bisa menggabung empat bujur sangkan menjadi satu empat persegi panjang untuk menghasilkan term dua-literal. Dalam Gambar 4-26 di bagian (a), minterm-minterm don‟t care 0 dan 2 disertakan denga bit 1, yang menghasilkan fungsi tersederhana F= CD +AB‟ Di bagian (b), minterm don‟t care 5 disertakan dengan bit 1, hasil fungsi tersederhananya adalah F=CD+A‟D

Gambar 4.26 Contoh dengan kondisi-kondisi Don‟t care

Dua ekspresi di atas menyatakan dua fungsi berbeda secara aljabar. Keduanya memuat minterm-minterm tertentu dan “fungsi tertentu secana tidak lengkap”, akan tetapi masingmasing memuat minterm don‟t care yang berbeda. Selama memperhatikan “fungsi tertentu secara tidak lengkap”, kedua ekspresi bisa ditenima. Perbedaannya hanya dalam nilai F untuk minterm-minterm yang tidak ditentukan. Di samping itu, mungkin juga mendapatkan ekspresi product-of-sum untuk fungsi Gamban 4-26. Dalam kasus ini, cara menggabung bit 0 adalah untuk memuat mintermminterm don‟t care 0 dan 2 dengan bit 0 menghasilkan fimgsi terkomplemen tersederhana F‟ = D‟ + AC‟. Selanjutnya dengan mengambil komplemen dan F‟ akan menghasilkan ekspresi tersederhana dalam bentuk product-of sum: F = D(A‟ + C)


34

Contoh sebelumnya memperlihatkan bahwa minterm-minterm don‟t care dalam map awalnya dianggap sebagai pernyataan suatu pilihan antara 1 dan 0. Pemilihan dibuat tergantung pada cara kita untuk menyederhanakan “fungsi yang ditentukan secara tidak lengkap”. Akan tetapi, sekali pemilihan dibuat, fungsi tersederhana akan mempunyai nilainilai khusus untuk semua minterm dan fungsi asli, termasuk minterm-minterm yang awalnya tidak ditentukan. Sehingga meskipun outputs dalam penentuan awal mungkin memuat simbol-simbol X, outputs dalam implementasinya hanya bit 0 dan bit 1. 4.6 Gerbang NAND dan NOR - NAND and NOR Gates Karena fungsi-fungsi Boolean dinyatakan dalam terms operasi-operasi AND, OR, dan NOT, maka implementasi dengan gerbang-gerbang AND, OR dan NOT merupakan prosedur yang jelas. Akan tetapi, dijumpai bahwa kemungkinan mengkonstruksikan gerbang dengan operasi-operasi lojik lain merupakan praktek yang menarik. Faktor-faktor yang hams dipertimbangkan ketika mengkonstruksikan tipe-tipe gerbang yang lain adalah kelayakan (feasibility) dan biaya pembuatan gerbang dengan komponenkomponen elektronik, kemungkinan perluasan gerbang untuk bisa meneritna lebth dan dun input, dan kemampuan gerbang

untuk

mengimplementasikan

fungsi-fungsi

Boolean

sendiri

atau

dalam

hubungannya dengan gerbang-gerbang lain.


35

Gambar 4-27 Gerbang-gerbang Lojik Dijital

Di samping gerbang-gerbang AND dan OR, gerbang-gerbang lojik lain digunakan secara ekstensif dalam perancangan rangkaian-rangkaian dijital. Simbol-simbol grafik dan tabel-tabel kebenaran dan delapan gerbang lojik diperlihatkan dalam Gambar 4.27. Gerbang-gerbang diperlihatkan dengan dua variable input biner, X dan Y, dan satu variable output biner, F. Dua simbol grafik digambar untuk masing-masing gerbang. Simbol-simbol segiempat di sebelah kanan direkomendasikan oleh Institute of Electrical and Electronics Engineers‟ (IEEE) Standard Graphic Symbols for Logic Functions (IEEE Standard 9 - 1984). Universitas Gadjah Mada

36

Simbol-simbol dengan bentuk beda di sebelah kiri dianggap sebagai alternatif yang bisa diterima dalam ukuran standar. Simbol-simbol segiempat akan lebih nyaman jika kemampuan komputer grafik terbatas. Akan tetapi, dengan grafika modem, simbol-simbol altematif hampir digunakan secara universal baik untuk grafika komputer maupun dalam literatur-literatur teknik. Gerbang-gerbang AND, OR, dan NOT didefinisikan sebelumnya. Rangkaian NOT membalik (inverl) nilai lojik dan sinyal biner untuk menghasilkan operasi komplemen. Bulatan kecil di ouçput merupakan simbol grafik gerbang NOT secara formal disebut penunjuk negasi (negation indicator) dan menandakan komplemen lojik. Kita akan secara formal merujuk indikator negasi sebagai “bubble‟ Simbol segitiga sendiri menandakan rangkaian „buffer‟: Buffer menghasilkan fungsi lojik Z = X, karena nilai biner darn ouput sama dengan riilai biner dan input. Rangkaian ini utamanya digunakan untuk “amplify” sinyal-sinyal listrik. Gerbang NAND menyatakan komplemen dan operasi AND. Namanya merupakan singkatan darn NOT AND. Simbol-simbol grafik untuk gerbang NAND terdiri dan simbol AND dengan bubble (bulatan kecil) pada output, yang menandakan operasi komplemen. Gerbang NOR merupakan singkatan dan NOT OR) merupakan komplemen darn operasi OR dan disimbolkan dengan simbol grafik OR dengan bubble pada output. Gerbang-gerbang NAND dan NOR digunakan secara ekstensif sebagai gerbanggerbang lojik standar dan kenyataannya jauh lebih populer dibanding dengan gerbang-gerbang AND dan OR. Karena gerbang-gerbang NAND dan NOR merupakan fungsi-fungsi alami untuk rangkaianrangkaian eletrorik paling sederhana. Gerbang exclusive-OR (XOR) serupa dengan gerbang OR, tetapi hanya berbeda (mempunyan nilai o untuk) kombinasi di mana X dan Y mempunyan nilai sama dengan 1. Simbol grafik untuk gerbang XOR menyerupan simbol grafik untuk gerbang OR. kecuali ada tambahan garis melengkung pada input. Exclusive- OR mempunyai simbol khusus

untuk

menunjukkan operasinya. Exclusive-NOR merupakan komplemen dari exclusive-OR, sebagaimana ditunjukkan dengan bubble pada output simbol grafiknya.


37

Gambar 4-28 Operasi-operasi Lojik dengan gerbang-gerbang NAND

Dalam sisa bagian ini akan diseidiki implementasi rangkaian-rangkaian dijital dengan gerbang-gerbang NAND dan NOR. Gerbang XOR akan dibahas dalam bagian benikutnya. Rangkaian NAND - NAND Circuits Gerbang NAND dikatakan sebagai gerbang universal karena setiap sistem dijital bisa diimplementasikan dengan hanya gerbang-gerbang NAND saja. Untuk membuktikan bahwa setiap fungsi Boolean bisa diimplementasikan dengan gerbang-gerbang NAND, kita hanya penlu memperlihatkan bahwa operasi-operasi lojik dan AND, OR dan NOT bisa diperoleh hanya dengan gerbang-gerbang NAND saja. Hal ini dilakukan dalam Gambar 4.28. Operasi komplemen diperoleh dari gerbang NAND satu-input yang berperilaku persis seperti gerbang NOT. Kenyataannya NAND satu-input merupakan simbol invalid sehingga diganti dengan symbol NOT seperti terlihat dalam gambar. Operasi AND memerlukan dua gerbang NAND. Pertama menghasilkan operasi NAND dan kedua membahk (invert) nilai lojik sinyal, sehmgga kombinasinya menjadi sebuah AND. Operasi OR diperoleh dengan menggunakan gerbang NAND dengan NOT pada masing-masing input. Ketika teorema DeMorgan diterapkan sebagaimana dalam Gambar 4.29, inversi membatalkan dan hasilnya fungsi OR. Cara yang nyaman untuk mengimplementasikan fungsi Boolean dengan gerbanggerbang NAND adalah untuk memperoleh fungsi Boolean tersederhana dalam terms operator-operator Boolean AND, 4 OR dan NOT dan kemudian mengkonversi fungsi ke logika NAND. Konversi suatu ekspresi aijabar dari AND, OR dan NOT ke NAND bisa dilakukan dengan teknik sederhana yang merubah diagram lojik AND-OR menjadi diagram lojik NAND.


38

Gambar 4.28 Simbol-simbol grafik alternative untuk Gerbang-gerbang NAND dan NOT

Untuk memfasilitasi konversi ke lojik NAND, akan lebih nyaman jika terlebih dahulu mendefinisikan symbol-simbol grafik alternatif untuk gerbang. Dua symbol grafik yang ekuivalen untuk gerbang NAND diperlihatkan pada Gambar 4.29 (a) dan 4.29 (b). Simbol AND-NOT, yang diberikan untuk NAND sebelumnya, terdiri dari simbol grafik AND dengan bubble pada outputnya. Secara alternatif, dimungkinkan menyatakan gerbang NAND dengan sebuah simbol grafik OR dengan bubble pada masing-masing input. Simbol NOT-OR untuk gerbang NAND mengikuti teorema DeMorgan don konvensi bahwa indikator-indikator negasi menandakan komplementasi. Untuk berurusan dengan simbol-simbol alternatif kasus NAND satu-input, simbol alternatif untuk gerbang NOT diberikan pada Gambar 4.29 (c). Simbol kedua diperoleh dengan memindah bubble dan output ke input buffer. Simbolsimbol grafik alternatif ini akan bermanfaat dalam analisa dan rancangan rangkaian-rangkaian NAND.

Implementasi Dua-Tingkat Two-Ievel implementihon Implementasi fungsi Boolean dengan gerbang NAND adalah paling sederhana jika fungsi dalam bentuk sum-of-products. Bentuk mi bersesuatan dengan rangkaian dua-tingkat (two-level-circuit).

jika

gerbang

AND

dan

sam

gerbang

OR

digunakan

untuk

mengimplementasikan rangkaian, dikatakan bahwa gerbang AND dalam tingkat sam dan gerbang OR dalam level kedua. Untuk rangkaian dua-tingkat sebagaimana yang didefinisikan di sini, inverter-inverter pada input ke para AND dan pada output dart OR tidak terhitung sebagai tingkat. Untuk melihat hubungan antara ekspresi sum-of-products dan implementasi NAND ekuivalensinya, perhatikan diagram lojik dalam Gambar 4.30. Semua tiga diagram adalah ekuivalen dan mengimplementasikan fungsi F = AB + CD. Di (a), fungsi diimplementasikan dengan gerbang-gerbang AND dan OR Sedang di (b), gerbang-gerbang AND diganti dengan gerbang-gerbang NAND dan gerbang OR diganti dengan gerbang NAND yang menggunakan simbol grafik NOT-OR. Ingat bahwa bubble menandakan komplementasi, dan dua bubble pada garis yang sama menyatakan komplementasi ganda; sehingga keduanya bisa dihilangkan dalam penerapannya.


39

Gambar 4-30 Tiga cara implementasi untuk F = AB + CD

Menghilangkan bubble pada gerbang di (b) menghasilkan rangkaian di (a). Oleh karena itu, dua diagram mengtmplementasikan fungsi yang sanu dan ekuivalen. Dalam Gambar 4.30 (c), oulput gerbang NAND digambar-ulang (redrawn) dengan simbol grafik AND-NOT Dalam menggambar diagram-diagram lo1ik NAND, rangkaian yang diperlihatkan dalam (b) atau (c) bisa ditennia. Rangkaian (b) menyatakan hubungan lebih langsung dengan ekspresi Boçan yang diimplementasikan. Implementasi NAND dalam Gambar 4.30 (c) bisa dibuktikan secara aljajar. Fungsi yang diimplementasikan bisa dengan mudah dikonversi ke bentuk sum-of-products dengan menggunakan teorema DeMoran: F = ((AB)‟.(CD)‟)‟ = ((AB))‟ + ((CD)‟)‟ = AB + CD Contoh 4.12 Implementasi Dengan Gerbang-gerbang NAND Implementasikan fungsi Boolean berikut dengan gerbang-gerbang NAND. F(X,Y,Z)=∑m(1,2,3,4,5, 7) Langkah pertama adalah menyederhanakan fungsi menjadi bentuk sum-of-products. Ini dilakukan dengan menggunakan map Gambar 4.31 (a), selanjutnya diperoleh fungsi tersederhanakan F = XY‟ + X‟Y + Z


40

Gambar 4.31 Penyelesaian contoh 4.12

Implementasi NAND dua-tingkat diperlihatkan dalam Gambar 4.31 (b) menggunakan simbol NOT-OR pada level kedua. Perhatikan bahwa input Z hams mempunyai gerbang NOT untuk mengimbangi (compensate) bubble pada gerbang tingkat kedua. Suatu cara lain untuk menggambar diagram lojik diperlihatkan dalam Gambar 4.31 (c). Di sini semua gerbang NAND digambar dengan sirnbol grafik yang sama. Inverter dengan input Z telah dihilangkan, tetapi variabel input dikomplemenkan dan dinyatakan dengan X Prosedur yang dijelaskan dalam contoh sebelumnya menandakan bahwa fungsi Boolean bisa diimplementasikan dengan dua tingkat gerbang NAND. Prosedur untuk mendapatkan diagram lojik dan fungsi Boolean adalah sebagai berikut: 1. Sederhanakan fungsi dan nyatakan dalam bentuk sum-of-products. 2. Gambar gerbang NAND untuk masing-masing product term dan ekspresi yang paling sedikit mempunyai dua literal. Input untuk masing-masing gerbang NAND adalah literalliteral dan term. Ini membentuk kelompok gerbang-gerbang tingkat-pertama. 3. Gambar gerbang tunggal menggunakan simbol-simbol grafik AND-NOT atau NOT-OR di tingkat kedua, dengan input-input dating dan output-ouput gerbang tingkat-pertama. 4. Suatu term dengan literal tunggal memerlukan sebuah NOT di tingkat pertama. Akan tetapi, jika literal tunggal dikomplemenkan dan pemunculan aslinya, maka ia bisa dihubungkan secara langsung ke input dan gerbang NAND tingkat-kedua. Rangkaian NANDTingkat – Banyak MuItileveI NAND Circuits Bentuk standar dari ekspresi fungsi Boolean menghasilkan implementasi tingkatkedua. Akan tetapi, ada banyak kejadian-kejadian ketika merancang sistem dijital Universitas Gadjah Mada

41

menghasilkan struktur-struktur penggerbangan (gatin) dengan tiga atau lebih tingkat. Prosedur yang paling biasa digunakan dalam merancang rangkaian-rangkaian tingkatbanyak untuk menyatakan fungsi Boolean dalam terms operasi-operasi AND, OR, dan NOT. Kemudian fungsi diimplementasikan secara langsung dengan gerbang-gerbang AND, OR, dan NOT. Selanjutnya jika perlu, fungsi tersebut bisa dikonversikan ke dalam suatu rangkaian yang semua gerbang-nya NAND.

Contoh 4.13 Perhatikan fungsi Boolean berikut. F=A(CD+B)+BC’ Meskipun pasangan kurung bisa dihilangkan dan mereduksi ekspresi ke bentuk standar sum-of-products. Sebagai ilustrasi dalam kasus ini akan dipilih implementasi rangkaian tingkat-banyak. Implementasi AND- OR diperlihatkan dalam Gambar 4.32 (a). Dalam rangkaian tersebut terdapat empat tingkat penggerbangan. Tingkat pertama mempunyai dua gerbang AND, tingkat kedua mempunyai sebuah gerbang OR dan diikuti oleh sebuah gerbang AND pada tingkat ketiga dan sebuah gerbang OR pada tingkat keempat. Diagram lojik dengan pola tingkat-tingkat alternatif dan gerbang-gerbang AND dan OR bisa dengan mudah dikonversikan ke rangkaian NAND dengan menggunakan simbolsimbol NAND alternatif. Ini diperlihatkan dalam Gambar 4.32 (b). Prosedur yang digunakan adalah untuk merubah setiap gerbang AND ke simbol grafik AND-NOT. dan setiap gerbang OR dikonversikan ke simbolsimbol grafik NOT-OR Rangkaian NAND menyelenggarakan lojik sama seperti rangkaian AND-OR, selama tidak ada bulatan kecil atau ada dua bulatan kecil Universitas Gadjah Mada

42

sepanjang masing-masing garis. Bulatan kecil yang terhubung dengan input B ke simbol grafik NOT-OR mengakibatkan komplementasi tambahan yang harus diimbangi dengan merubah literal input menjadi B‟.

Prosedur umum untuk mengkonversi diagram AND-OR menjadi diagram NAND-semua dengan menggunakan simbol NAND alternatif sebagai benikut: 1. Konversikan semua gerbang AND ke gerbang NAND dengan simbol-simbol grafik AND- NOT. 2. Konversikan semua gerbang OR ke gerbang NAND. 3. Periksa semua bulatan kecil dalam diagram. Untuk setiap bulatan kecil yang tidak diimbangi oleh bulatan kecil lain sepanjang ganis yang sama, sisipkan gerbang NOT atau komplemenkan literal input dan pemunculan awalnya. Contoh 4.14 Perhatikan fungsi Boolean tingkat-banyak berikut: F= (AB‟+A‟B)E(C+D‟)) Implementasi AND-OR dan fungsi ini diperlihatkan dalam Gambar 4-33 (a) dengan tigatingkat penggerbangan. Konversi ke dalam NAND dengan simbol-simbol alternatif disajikan dalam diagram bagian (b). Dua bulatan kecil tambahan yang dthubungkan dengan iuput C dan D‟ mengakibatkan dua literal ini dikomplemenkan masing-masing menjadi C‟ dan D. Bulatan kecil pada oulput gerbang NAND mengkomplemenkan nilai oulput, sehingga perlu disisipkan gerbang NOT pada oulput untuk mengkomplemenkan lagi sinyal sehingga diperoleh nilai awal. Demikian Juga, bulatan kecil pada oulput gerbang NAND X tidak diimbangi, sehingga gerbang NOT disisipkan. Universitas Gadjah Mada

43

Rangkaian NOR - NOR circuits Operasi NOR merupakan dual dari operasi NAND. Oleh karena itu, semua prosedur dan aturan untuk lojik NOR juga merupakan dual dan prosedur-prosedur dan aturan-aturan yang dikembangkan untuk lojik NAN)). Gerbang NOR merupakan gerbang universal lain yang bisa digunakan untuk mengimplementasikan fungsi Boolean. Implementasi dan operasi-operasi AND, OR, dan NOT dengan gerbang NOR diperlihatkan dalam Gambar 434. Operasi komplemen diperoleh dari gerbang NOR satu input yang seperti NAND akan mengurangi terhadap gerbang NOT. Operasi OR memenlukan dua gerbang NOR, dan operasi AND diperoleh dengan sebuah gerbang NOR yang mempunyai gerbanggerbang NOT pada masing-masing input Dua simbol grafik alternatif untuk gerbang NOR diperlihatkan pada Gambar 4-35. Simbol OR-NOT mendefinisikan operasi NOR sebagai OR diikuti oleh NOT Simbol NOT-AND mengkomplemenkan marng-masing input dan kemudian melakukan suatu operasi AND. Simbol-simbol alternatif ini menandakan operasi NOR yang sama dan identik secara lojik karena teorema DeMorgan.

Gambar 4.34 Operasi-operasi lojik dengan gerbang NOR

Implementasi dua-tingkat dengan gerbang-gerbang NOR adalah yang paling sederhana jika fungsi tersederhananya dalam bentuk product-of sums. Ingat bahwa ekspresi product-of sums tersederhana diperoleh dan map dengan menggabung bit-bit 0 dan kemudian mengkomplemenkan. Suatu ekspresi product-of-sums diimplementasikan dengan tingkat-pertama gerbang-gerbang OR yang menghasilkan sum terms, diikuti oleh tingkat kedua gerbang AND untuk menghasilkan product. Transformasi dan diagram OR-AND ke diagram NOR dicapai dengan mengganti gerbang-gerbang OR menjadi gerbang-gerbang NOR dengan simbol-simbol grafik NOT-AND. Suku dengan literal tunggal yang menuju ke gerbang tingkat-kedua baris dikomplemenkan menurut cara mereka awalnya muncul, atau gerbang NOT harus disisipkan. Gambar 4-36 memperlihatkan implementasi NOR terhadap Universitas Gadjah Mada

44

fungsi yang dinyatakan dalam bentuk product-of sums. Pola OR-AND bisa dengan mudah dideteksi dengan menghilangkan bulatan-bulatan kecil sepanjang garis yang sama. Variabel E dikomplemenkan untuk mengimbangi bulatan kecil ketiga pada input dan gerbang tingkatkedua.

Gambar 4.35 Dua simbol grafik untuk gerbang NOR

Gambar 4.36 Pengimplementasian F = (A + B)(C + D) dengan gerbang-gerbang NOR

Gambar 4-37 Pengimplementasian F = (AB‟ + A B)E(C + D) dengan gerbang-gerbang NOR

Prosedur untuk mengkonversi suatu diagram AND-OR tingkat-banyak ke suatu diagram NORsemua adalah serupa dengan yang disajikan untuk gerbang-gerbang NAND. Untuk kasus NOR, kita hams mengkonversi masing-masing gerbang OR ke suatu simbol OR-NOT dan masing-masing gerbang AND dikonversikan ke simbol NOT-AND. Setiap bulatan kecil yang tidak diimbangi dengan bulatan kecil lain sepanjang ganis yang sama memerlukan suatu inverter atau komplementasi literal input dan pemunculan awalnya. Transformasi diagram AND-OR dalam Gambar 4-33 (a) ke diagram NOR diperlihatkan dalam Gambar 4-37. Fungsi Boolean untuk rangkaian mi adalah F = (AB‟ + A B)E(C + D‟)


45

Diagram NOR ekuivalennya bisa dikenali dan diagram NOR dengan menghilangkan semua bulatan kecil. Agar supaya bulatan-bulatan kecil tenimbangi, suatu inverter ditambahkan pada input dan F yang lebih rendah dan A, B‟, A‟, B, dan E dikomplemenkan. 4.7 Gerbang EkskIusif.OR Exclusive-OR Gates Eksklusif-OR (X-OR) yang ditunjukkan dengan

, merupakan operasi lojik yang

menyelenggarakan fungsi

Gambar 4-38 Eksklusif-OR yang dikonstruksikan dengan gerbang NAND

Fungsi sama dengan 1 jika tepat salah satu variabel sama dengan 1. Eksklusif-NOR, yang juga dikenal sebagai ekuivalensi (equivalence), merupakan komplemen dan eksklusif-OR dan dinyatakan dengan fungsi

Fungsi sama dengan 1 jika kedua X dan Y sama dengan 1 atau jika keduanya sama dengan 0. Dua fungsi bisa diperlihatkan sebagai fungsi yang saling komplemen, baik dengan menggunakan tabel kebenaran atau dengan manipulasi aijabar sebagai berikut:

Identitas-identitas berikut menerapkan operasi eksklusif-OR:

Setiap identitas di atas bisa dibuktikan dengan menggunakan suatu tabel kebenaran mengganti operasi

dengan ekspresi Boolean ekuivalennya. Di samping itu, bisa juga

diperlihatkan bahwa operasi eksklusif-OR bersifat komutatif dan asosiatif, yaitu:

Ini berarti bahwa dua input untuk gerbang eksklusif-OR bisa ditukar tanpa mempengaruhi operasi. Di samping itu, juga berarti bahwa kita bisa mengevaluasi operasi eksklusif-OR tigaUniversitas Gadjah Mada

46

variabel dalam urutan apapun, dan untuk alasan ini eksklusif-OR dengan tiga atau lebih variabel bisa diekspresikan tanpa tanda kurung. Sehingga dimungkinkan menggunakan eksklusif-OR dengan tiga atau lebih input. Suatu fungsi eksklusif-OR dua-input bisa dibentuk dengan gerbang-gerbang konvensional, yaitu dua gerbang NOT, dua gerbang AND, dan Satu gerbang OR. Gambar 438 memperlihatkan sebuah implementasi dengan empat gerbang NAND. Simbol alternatif diagram NAND menyelenggarakan operasi X(X‟+ Y‟) + Y(X‟+ Y‟) = XY‟+X‟Y Fungsi Ganjil - Odd Function Operasi eksklusif-OR dengan tiga atau lebih variabel bisa dikonversi ke dalam suatu fungsi Boolean biasa dengan menukar simbol dengan ekspresi Boolean ekuivalennya. Khususnya, kasus tiga variabel bisa dikonversi ke suatu ekspresi Boolean sebagai berikut:

Ekspresi Boolean secara jelas menandakan bahwa eksklusif-OR tiga-variabel sama dengan I hanya jika satu variabel sama dengan 1 atau jika semua dan tiga variabel sama dengan 1. Sehingga, dalam fungsi dua-variabel hanya satu variabel yang perlu sama dengan 1, dan untuk tiga atau lebih variabel sejumlah ganjil variabel harus sama dengan 1. Sebagai akibatnya, operasi eksklusif-OR variabel banyak didefinisikan sebagai fungsi ganjil (odd function). Kenyataannya, fungsi ganjil adalah nama yang tepat untuk operasi dengan tiga atau lebih variabel; sedang nama “eksklusif-OR” bisa diterapkan hanya untuk kasus dua variabel.

Gambar 4.39 Map untuk Fungsi Ganjil Variabel-banyak


47

Fungsi Boolean yang diturunkan dari fungsi ganjil dinyatakan sebagai jumlahan lojik dan empat minterm yang mempunyai kesesuaian nilai 001, 010, 100, dan 1.11 dalam tabelkebebaran biner. Masing-masing bilangan biner di atas mempunyai sejumlah ganjil bit-bit 1. Empat minterm lain yang tidak termasuk dalam fungsi adalah 000, 011, 101, dan 110, dan mereka mempunyai sejumlah genap bit-bit 1. Pada umurnnya, suatu fungsi ganjil dengan n variabel didefinisikan sebagai jumlahan lojik dan 2‟/2 minterm yang bersesuaian dengan nilai yang mempunyai sejumlah ganjil bit-bit 1 dalam tabel kebenaran biner. Definisi fungsi ganjil bisa diklarifikasi dengan mem-plot (plotting fungsi pada map. Gambar 4-39 (a) mempenlihatkan map utuk fungsi ganjil dengan tiga-vaniabel. Empat minterm dan fungsi berbeda dengan yang lain pada paling sedikit dari literal, jadi tidak bisa adjacent dalam map. Minterm-minterm ini dikatakan “dua jarak” (distance two) dan masingmasing yang lain. Fungsi ganjil dikenali dan ke empat minterm yang nilai-nilai binernya mempunyai sejumlah ganjil bit-bit I. Kasus empat-variabel diperlihatkan pada Gambar 4-39 (b). Delapan minterms yang ditandai dengan bit I dalam map membentuk fungsi ganjil. Perhatikan karaktenistik pola jarak antana bit-bit 1 dalam map. Selanjutnya bisa dikatakan bahwa mintçrmminterm yang tidak ditandai dengan bit 1 membentuk komplemen fungsi ganjil, yang disebut fungsi genap (even function). Fungsi ganjil diimplementasikan dengan menggunakan gerbang-gerbang esklusifOR dua input, sebagaimana diperlihatkan dalam Gambar 4-40. Kemudian fungsi genap diperoleh dengan mengganti gerbang output dengan gerbang eksklusif-NOR.

Gambar 4-40 Fungsi-fungsi Ganjil Input-banyak


48

Bab 4 Rangkaian Logika Kombinasional

Recommend Documents