matematika

MATEMATIKA DISKRIT

FADLISYAH, S.Si BUSTAMI, S.Si, M.Si

PENERBIT GRAHA ILMU

DAFTAR ISI Kata Pengantar Daftar Isi

BAB 1 – LOGIKA 1.1 Gerbang Logika 1.2 Aljabar Boolean

1 1 5

BAB 2 – PETA KARNAUGH 11 BAB 3 – METODE QUINE McCLUSKEY 21 BAB 4 – KONVOLUSI

4.1 Pondasi Konvolusi 4.2 Perancangan Program

39 39 43

BAB 5 – BILANGAN FLOATING-POINT 51 BAB 6 – KODE HAMMING 59 BAB 7 – GRAPH 67 Lampiran Daftar Pustaka

KATA PENGANTAR

Dengan rahmat Allah SWT, buku ini telah selesai disusun walaupun dengan situasi yang sangat tidak menguntungkan bagi penulis. Sedikit tertatih-tatih, alasan kesehatan, penulis hadir dengan buku terbarunya berjudul Matematika Diskrit. Representasi data di dalam komputer bersifat tidak kontinu atau diskrit, sehingga keadaan ini telah mengambil suatu wilayah kajian baru dalam bidang matematika khususnya untuk aplikasi pemanipulasian bit-bit. Perkembangan matematika diskrit sendiri dipengaruhi drastis oleh perkembangan mesin Von Neumann, dan oleh karena itu penulis lebih tertarik untuk menyusun buku matematika diskrit yang berfokus kepada pemanipulasian bit-bit.

Adapun materi yang hadir di dalam buku ini meliputi : Logika, Peta Karnaugh, Metode QuineMcCluskey, Konvolusi, Representasi Bilangan Floating-Point, Kode Hamming, dan Teori Graph. Buku ini ditujukan kepada mahasiswa yang mengambil mata kuliah matematika diskrit, sebagai sarana primitif untuk menjangkau konsep-konsep pemanipulasian data yang lebih mendalam.

BBaabb 11

LOGIKA

1.1 Gerbang Logika

Informasi biner direpresentasikan di dalam komputer digital oleh beberapa kuantitas yang disebut juga sebagai sinyal. Sinyal-sinyal elektris yang hadir di dalam komputer seperti voltase, direpresentasikan ke dalam salah satu bentuk satu atau dua state yang dikenal. Untuk representasi ke dalam dua state, variabel biner dapat berupa nilai 1 atau 0. Pada beberapa komputer digital, sinyal 3 volt merepresentasikan nilai biner 1 dan sinyal 0,5 volt merepresentasikan nilai biner 0.

Logika biner bertransaksi dengan berbagai variabel biner dan operasi-operasi yang mengandung berbagai logika, yang selanjutnya digunakan untuk memaparkan, dalam bentuk tabular atau aljabar, pemanipulasian dan pengolahan informasi biner. Pemanipulasian informasi biner dilakukan oleh berbagai sirkuit logika yang disebut juga sebagai gate. Gate (gerbang) merupakan sebuah blok hardware yang memproduksi sinyal-sinyal biner 1 dan 0 ketika input logikal yang diperlukan telah terpenuhi. Masing-masing gate memiliki simbol grafis yang berbeda dan berbagai operasi yang dilakukan berdasarkan maksud-maksud dari ekspresi aljabar. Hubungan input-output dari berbagai variabel biner untuk masing-masing gate direpresentasikan dalam bentuk tabular, sebagai berikut :

2 MATEMATIKA DISKRIT

1. Gerbang AND

Simbol :

Fungsi aljabar :

BAx ⋅= atau ABx =

Tabel kebenaran :

B

A x

A B x

0 0 0

0 1 0

1 0 0

1 1 1

2. Gerbang OR

Simbol :

Fungsi aljabar :

BAx +=

x B

A

LOGIKA 3

Tabel kebenaran :

A B x

0 0 0

0 1 1

1 0 1

1 1 1

3. INVERTER

Simbol :

Fungsi aljabar :

Ax ′=

Tabel kebenaran :

x A

A x

0 1

1 0

4. BUFFER

Simbol :

4 MATEMATIKA DISKRIT

Fungsi aljabar :

Ax =

Tabel kebenaran :

A x

A x

0 0

1 1

5. Gerbang XOR

Simbol :

Fungsi aljabar :

BAx ⊕= atau BABAx ′+′=

Tabel kebenaran :

A

x

B

LOGIKA 5

A B x

0 0 0

0 1 1

1 0 1

1 1 0

1.2 Aljabar Boolean

Aljabar Boolean merupakan bidang aljabar yang berurusan dengan berbagai variabel biner dan operasi-operasi logika. Perhatikan ekspresi fungsi Boolean berikut :

zyxF ′+=

maka dapat kita tentukan tabel kebenaran ekspresi tersebut sebagai :

x y z F

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1 1

6 MATEMATIKA DISKRIT

Diagram logikanya :

y

z

x

F

Kegunaan aljabar Boolean adalah untuk memfasilitasi analisis dan desain berbagai sirkuit digital. Aljabar Boolean memberikan suatu perangkat yang tepat terhadap :

1. Pengekspresian secara aljabar terhadap berbagai keterhubungan dalam bentuk tabel kebenaran di antara berbagai variabel biner.

2. Pengekspresian secara aljabar terhadap berbagai bentuk keterhubungan input-output diagram logika.

3. Memungkinkan perancangan berbagai sirkuit yang lebih sederhana terhadap fungsi yang sama.

Berbagai sifat-sifat atau identitas dari aljabar Boolean :

1. xx =+ 0

2. 11=+x3. xxx =+

4. 1=′+ xx5. xyyx +=+

6. zyxzyx ++=++ )()(

7. xzxyzyx +=+ )(

8. yxyx ′′=′+ )(

LOGIKA 7

9. xx =′′)(

10. 00 =⋅x

11. xx =⋅112. xxx =⋅

13. 0=′⋅ xx14. yxxy =

15. zxyyzx )()( =

16. ))(( zxyxyzx ++=+

17. yxxy ′+′=′)(

Berbagai contoh kasus, perhatikan ekspresi aljabar Boolean berikut :

DCBADCBA ′+′+′+′

bila diasumsikan bahwa xDCBA =′+′ , maka ekspresi di atas dapat berupa xx + , dan berdasarkan identitas (3) diperoleh :

DCBADCBADCBA ′+′=′+′+′+′

Untuk ekspresi yang lain kita ambil :

CACABABCF ′+′+=

berturut-turut kita peroleh :

CACABABCF ′+′+=

( ) CACCABF ′+′+=

CAABF ′+=

8 MATEMATIKA DISKRIT

dengan diagram logika sebagai :

untuk CACABABCF ′+′+= , dan

untuk CAABF ′+= .

Komplemen fungsi Boolean

Komplemen suatu fungsi Boolean secara sederhana dapat kita lakukan dengan menukar nilai-nilai 1 dan 0 pada tabel kebenaran. Untuk berbagai bentuk ekspresi aljabar, kita dapat menggunakan teorema DeMorgan sebagai berikut :

F

LOGIKA 9

nn xxxxxxxx ′′′′=′++++ ...)...( 321321

nn xxxxxxxx ′++′+′+′=′ ...)...( 321321

Berdasarkan teorema DeMorgan, maka komplemen fungsi Boolean DBDCABF ′+′′+= adalah ))()(( DBDCBAF ′++′+′=′ .

BBaabb 22

PETA KARNAUGH

Kompleksitas dari diagram logika yang merupakan wujud fungsi Boolean, terkait secara langsung dengan kekompleksitasan ekspresi Boolean yang diimplementasikan. Representasi tabel kebenaran dari suatu fungsi bersifat unik, tetapi fungsi dapat muncul dalam berbagai bentuk ketika diekspresikan secara aljabar. Ekspresi dapat disederhanakan menggunakan relasi-relasi dasar aljabar Boolean. Bagaimanapun, prosedur tersebut kadang-kadang masih terasa sulit bila dihadapkan dengan kurangnya aturan-aturan khusus dalam memprediksikan langkah-langkah yang diperlukan selanjutnya di dalam proses pemanipulasian. Untuk mengatasi hal tersebut, maka diperkenalkanlah metode peta Karnaugh.

Berbagai peta berdasarkan jumlah variabelnya :

1. 2 variabel ( )yx,

0 1

0 0m 1m

1 2m 3m

x y

x

y

12 MATEMATIKA DISKRIT

Keterangan :

nm dibaca minterm ke-n .

minterm merupakan perkalian literal yang mengandung semua varaibel.

2. 3 variabel ( )zyx ,,

y

00 01 11 10

0 0m 1m 3m 2m

1 4m 5m 7m 6m

x yz

x

z

3. 4 variabel ( )zyxw ,,,

y

00 01 11 10

00 0m 1m 3m 2m

01 4m 5m 7m 6m

11 12m 13m 15m 14m

10 8m 9m 11m 10m

wx yz

x

w

z

PETA KARNAUGH 13

4. 5 variabel ( )edcba ,,,,

c

000 001 011 010 110 111 101 100

00 0m 1m 3m 2m 6m 7m 5m 4m

01 8m 9m 10m 11m 14m 15m 13m 12m

11 24m 25m 27m 26m 30m 31m 29m 28m

10 16m 17m 19m 18m 22m 23m 21m 20m

d

e e

ab cde

b

a

Tabel format minterm dan Maxterm untuk 5 variabel :

minterm Maxterm abcde

Term Simbol Term Simbol

00000 edcba ′′′′′ 0m edcba ++++ 0M

00001 edcba ′′′′ 1m edcba ′++++ 1M

00010 edcba ′′′′ 2m edcba +′+++

00011 decba ′′′ 3m edcba ′+′+++

00100 edcba ′′′′ 4m edcba ++′++

:

:

:

14 MATEMATIKA DISKRIT

00101 edcba ′′′ 5m edcba ′++′++

00110 ecdba ′′′ 6m edcba +′+′++

00111 cdeba ′′ 7m edcba ′+′+′++

01000 edcba ′′′′ 8m edcba +++′+

01001 edcba ′′′ 9m edcba ′+++′+

01010 edcba ′′′ 10m edcba +′++′+

01011 decba ′′ 11m edcba ′+′++′+

01100 edbca ′′′ 12m edcba ++′+′+

01101 edbca ′′ 13m edcba ′++′+′+

01110 ebcda ′′ 14m edcba +′+′+′+

01111 bcdea′ 15m edcba ′+′+′+′+

10000 edcba ′′′′ 16m edcba ++++′

10001 edcba ′′′ 17m edcba ′++++′

10010 edcba ′′′ 18m edcba +′+++′

10011 decba ′′ 19m edcba ′+′+++′

10100 edcba ′′′ 20m edcba ++′++′

10101 edcba ′′ 21m edcba ′++′++′

10110 ecdba ′′ 22m edcba +′+′++′

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

PETA KARNAUGH 15

10111 cdeba ′ 23m edcba ′+′+′++′

11000 edcab ′′′ 24m edcba +++′+′

11001 edcab ′′ 25m edcba ′+++′+′

11010 edcab ′′ 26m edcba +′++′+′

11011 decab ′ 27m edcba ′+′++′+′

11100 edabc ′′ 28m edcba ++′+′+′

11101 edabc ′ 29m edcba ′++′+′+′

:

:

:

:

:

:

:

:

:

11110 eabcd ′ 30m edcba +′+′+′+′ 30M

11111 abcde 31m edcba ′+′+′+′+′ 31M

5. 6 variabel ( )edcfba ,,,,,

Berbagai istilah terkait :

minterm atau produk baku merupakan perkalian literal yang mengandung semua variabel.

Maxterm atau jumlah baku merupakan jumlah literal yang mengandung semua variabel.

Literal merupakan ekspresi Boolean yang dibentuk oleh hanya satu variabel atau komplemen dari satu variabel.

16 MATEMATIKA DISKRIT

c

000 001 011 010 110 111 101 100

000 0m 1m 3m 2m 6m 7m 5m 4m

001 8m 9m 10m 11m 14m 15m 13m 12m

011 24m 25m 27m 26m 30m 31m 29m 28m

010 16m 17m 19m 18m 22m 23m 21m 20m

110 48m 49m 51m 50m 54m 55m 53m 52m

111 56m 57m 59m 58m 62m 63m 61m 60m

101 40m 41m 43m 42m 46m 47m 45m 44m

100 32m 33m 35m 34m 38m 39m 37m 36m

abf cde

f

f

b

a

d e e

Soal-soal

1. Minimasikan fungsi Boolean ∑= )5,4,2,3(),,( zyxF menggunakan peta Karnaugh ?

Jawab :

Keterangan : dalam pengelompokkan nilai-nilai 1 (satu), setiap kelompok harus memnuhi elemen (vertikal atau horisontal, tidak berbentuk diagonal).

,....,2,1,0,2 =nn

PETA KARNAUGH 17

Hasil minimasi ⇒ xyyxzyxF ′+′=),,( .

y 00 01 11 10

0 1 1

1 1 1

x yz

x

z

xy ′ yx ′

2. Untuk kasus yang sama, minimasikan :

∑= )14,13,12,9,8,6,5,4,2,1,0(),,,( zyxwF

Hasil minimasi ⇒ xzwzyzyxwF ′+′′+′=),,,( .

y 00 01 11 10

00 1 1 1

01 1 1 1

11 1 1 1

10 1 1

wx yz

x

z

w

wz ′′

xz′

y′

18 MATEMATIKA DISKRIT

3. Untuk kasus yang sama, minimasikan :

∑= )15,11,10,9,8,7,6,4,1(),,,( zyxwF

Hasil minimasi ⇒ xyzzwxxyzxwzyxwF ′′+′′++′=),,,( .

00 01 11 10

00 1

01 1 1 1

11 1

10 1 1 1 1

wx yz

x

y

z

w

wx′

xwz ′′

xyz zxy ′′

4. Minimasikan :

=),,,,( edcbaF

∑= )28,27,26,25,24,19,18,17,16,12,11,10,9,8,3,2,1,0(

Jawab :

PETA KARNAUGH 19

Hasil minimasi ⇒ edbcedcbaF ′′+′=),,,,( .

c 000 001 011 010 110 111 101 100

00 1 1 1 1

01 1 1 1 1 1

11 1 1 1 1 1

10 1 1 1 1

ab cde

d

b

e e edb ′′ c′

a

20 MATEMATIKA DISKRIT

BBaabb 33

METODE QUINE McCLUSKEY

Metode alternatif untuk penyederhanaan ekspresi Boolean adalah metode Quine-McCluskey, dikembangkan oleh W.V. Quine dan E.J. McCluskey pada tahun 1950. Tahapan penyelesaian dalam metode ini adalah sebagai berikut :

Ambil kasus, fungsi Boolean ∑= )5,4,2,3(),,( zyxF ,

Langkah pertama, buat tabel berdasarkan term-term yang terdapat di dalam ekspresi Boolean di atas, secara terurut.

(a) (b)

Term x y z Term x y z

2 0 1 0

3 0 1 1

4 1 0 0

5 1 0 1

Langkah kedua, kelompokkan term-term tersebut berdasarkan posisi bit 1, untuk nilai posisi lainnya yang berbeda, diberikan tanda (-). Term-term yang telah dikelompokkan diberi tanda (√).

22 MATEMATIKA DISKRIT

(a) (b)

Term x y z Term x y z

2 0 1 0 √ 2,3 0 1 -

3 0 1 1 √ 4,5 1 0 -

4 1 0 0 √

5 1 0 1 √

Langkah ketiga, buat tabel baru, dan seluruh term yang tidak ditandai (√) dikelompokkan di dalamnya untuk pengujian lanjutan.

Tandai dengan simbol (*) seluruh minterm yang mengandung satu (x), dan beri tanda (√) di bawah tanda (*).

minterm Term

2 3 4 5

2,3 x x

4,5 x x

* * * *

√ √ √ √

Pada tabel terlihat bahwa semua minterm telah tercakup keseluruhannya, maka tugas kita telah selesai dan fungsi minimasi yang diperoleh adalah, xyyxzyxF ′+′=),,( . Perhatikan ekspresi pembentukannya.

QUINE McCLUSKEY 23

Term x y z

2,3 0 1 -

4,5 1 0 -

Nilai 0 berarti komplemen dari literal, nilai 1 berarti literal asalnya. Untuk 2,3 merepresentasikan yx′ dan untuk 4,5 merepresentasikan

. Pembuktian menggunakan peta Karnaugh diperoleh : yx ′

y

00 01 11 10

0 1 1

1 1 1

x yz

x

z

xy ′

yx ′

Kasus yang lain, minimasikan fungsi Boolean (4 variabel) berikut :

∑= )14,13,12,9,8,6,5,4,2,1,0(),,,( zyxwF , menggunakan metode Quine-McCluskey.

Langkah pertama, buat tabel berdasarkan term-term yang terdapat di dalam ekspresi Boolean di atas, secara terurut.

24 MATEMATIKA DISKRIT

(a)

term w x y z

0 0 0 0 0

1 0 0 0 1

2 0 0 1 0

4 0 1 0 0

5 0 1 0 1

6 0 1 1 0

8 1 0 0 0

9 1 0 0 1

12 1 1 0 0

13 1 1 0 1

14 1 1 1 0

Langkah kedua, kelompokkan term-term tersebut berdasarkan posisi bit 1, untuk nilai posisi lainnya yang berbeda, diberikan tanda (-). Term-term yang telah dikelompokkan diberi tanda (√).

QUINE McCLUSKEY 25

(a) (b)

term w x y z term 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,4 0 - 0 0

4 0 1 0 0 √ 0,8 - 0 0 0

5 0 1 0 1 √ 1,5 0 - 0 1

6 0 1 1 0 √ 1,9 - 0 0 1

8 1 0 0 0 √ 2,6 0 - 1 0

9 1 0 0 1 √ 4,5 0 1 0 -

12 1 1 0 0 √ 4,6 0 1 - 0

13 1 1 0 1 √ 4,12 - 1 0 0

14 1 1 1 0 √ 5,13 - 1 0 1

6,14 - 1 1 0

8,9 1 0 0 -

9,13 1 - 0 1

12,13 1 1 0 -

Setelah sampai pada hasil di atas, maka kita perlu menguji sekali atau beberapa kali lagi, maka kita bentuk tabel (c) untuk pengelompokkan lanjutan dari tabel (b).

26 MATEMATIKA DISKRIT

(b) (c)

term w x y z term w x y z

0,1 0 0 0 - √ 0,1,4,5 0 - 0 -

0,2 0 0 - 0 √ 0,1,8,9 - 0 0 -

0,4 0 - 0 0 √ 0,2,4,6 0 - - 0

0,8 - 0 0 0 √ 0,4,1,5 0 - 0 - ↵

1,5 0 - 0 1 √ 0,4,2,6 0 - - 0 ↵

1,9 - 0 0 1 √ 0,8,1,9 - 0 0 - ↵

2,6 0 - 1 0 √ 1,5,9,13 - - 0 1

4,5 0 1 0 - √ 1,9,5,13 - - 0 1 ↵

4,6 0 1 - 0 √ 4,5,12,13 - 1 0 -

4,12 - 1 0 0 √ 4,12,5,13 - 1 0 - ↵

5,13 - 1 0 1 √ 4,12,6,14 - 1 - 0

6,14 - 1 1 0 √ 8,9,12,13 1 - 0 -

8,9 1 0 0 - √

9,13 1 - 0 1 √

12,13 1 1 0 - √

Tanda (↵) bermaksud bahwa term tersebut memiliki kesamaan dengan term lainnya.

QUINE McCLUSKEY 27

(c) (d)

term w x y z term w x y z

0,1,4,5 0 - 0 - √ 0,1,4,5,8,9,12,13 - - 0 -

0,1,8,9 - 0 0 - 0,4,1,5,8,9,12,13 - - 0 -

0,2,4,6 0 - - 0

0,4,1,5 0 - 0 - √

0,4,2,6 0 - - 0 ↵

0,8,1,9 - 0 0 - ↵

1,5,9,13 - - 0 1

1,9,5,13 - - 0 1 ↵

4,5,12,13 - 1 0 -

4,12,5,13 - 1 0 - ↵

4,12,6,14 - 1 - 0

8,9,12,13 1 - 0 - √

Langkah ketiga, buat tabel baru, dan seluruh term yang tidak ditandai (√) dan (↵) dikelompokkan di dalamnya untuk pengujian lanjutan.

Tandai dengan simbol (*) seluruh minterm yang mengandung satu (x), dan beri tanda (√) di bawah tanda (*).

28 MATEMATIKA DISKRIT

minterm Term

0 1 2 4 5 6 8 9 12 13 14

0,1,8,9 x x x x

0,2,4,6 x x x x √

1,5,9,13 x x x x

4,5,12,13 x x x x

4,12,6,14 x x x x √

0,1,4,5,8,9,12,13 x x x x x x x x

* *

√ √ √ √ √ √

Sampai pada tahap ini, masih ada term-term yang tidak terwakilkan, yaitu : 1,5,8,9,13. Maka kita bentuk tabel baru untuk pengujian,

minterm Term

0 1 2 4 5 6 8 9 12 13 14

0,1,8,9 x x x x

0,2,4,6 x x x x √

1,5,9,13 x x x x

4,5,12,13 x x x x

QUINE McCLUSKEY 29

4,12,6,14 x x x x √

0,1,4,5,8,9,12,13 x X x x x x x x √

* *

√ √ √ √ √ √ √ √ √ √ √

Kita pilih term (0,1,4,5,8,9,12,13) mewakili kolom yang tidak memiliki tanda (√).

Diperoleh, (4,12,6,14) mewakili zx ′ , (0,2,4,6) mewakili , (0,1,4,5,8,9,12,13) mewakili

zw ′′y ′ ,

Untuk mendukung hasil di atas, kita dapat menggunakan peta Karnaugh untuk pengujian,

y 00 01 11 10

00 1 1 1

01 1 1 1

11 1 1 1

10 1 1

wx yz

x

z

w

wz ′′

xz′

y′

Hasil minimasi ⇒ xzwzyzyxwF ′+′′+′=),,,( .

30 MATEMATIKA DISKRIT

Kasus 1

Sederhanakan fungsi Boolean ( ) ∑= )15,14,11,10,8,2,1,0(,,, zyxwf .

Penyelesaian :

(a) (b)

Term w x y z Term 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 - √

(c)

Term w x y z

0,2,8,10 - 0 - 0

0,8,2,10 - 0 - 0

QUINE McCLUSKEY 31

10,11,14,15 1 - 1 -

10,14,11,15 1 - 1 -

minterm Term

0 1 2 8 10 11 14 15

0,1 x x √

0,2,8,10 x x x x √

10,11,14,15 x x x x √

* * * * * *

√ √ √ √ √ √ √ √

Hasil minimasi : ( ) wyzxyxwzyxwf +′′+′′′=,,, .

Kasus 2

Sederhanakan fungsi Boolean ( ) ∑= )15,11,10,9,8,7,6,4,1(,,, zyxwf .

Penyelesaian :

(a) (b)

Term w x y z Term w x y z

1 0 0 0 1 √ 1,9 - 0 0 1

4 0 1 0 0 √ 4,6 0 1 - 0

32 MATEMATIKA DISKRIT

8 1 0 0 0 √ 8,9 1 0 0 - √

6 0 1 1 0 √ 8,10 1 0 - 0 √

9 1 0 0 1 √ 6,7 0 1 1 -

10 1 0 1 0 √ 9,11 1 0 - 1 √

7 0 1 1 1 √ 10,11 1 0 1 - √

11 1 0 1 1 √ 7,15 - 1 1 1

15 1 1 1 1 √ 11,15 1 - 1 1

(c)

Term w x y z

8,9,10,11 1 0 - -

8,10,9,11 1 0 - -

minterm Term

1 4 6 7 8 9 10 11 15

1,9 x x √

4,6 x x √

6,7 x x

7,15 x x

QUINE McCLUSKEY 33

11,15 x x

8,9,10,11 x x x x √

* * * *

√ √ √ √ √ √ √

minterm Term

1 4 6 7 8 9 10 11 15

1,9 x x √

4,6 x x √

6,7 x x

7,15 x x √

11,15 x x

8,9,10,11 x x x x √

* * * *

√ √ √ √ √ √ √ √ √

Hasil minimasi : ( ) xwxyzzxwzyxzyxwf ′++′′+′′=,,, .

34 MATEMATIKA DISKRIT

Kasus 3

Sebagai ketua panitia bazaar di RW setempat, ibu Soffie mengusulkan untuk menjual kue bolu. Dari anggota ibu PKK RW, beberapa orang menyatakan kesediaannya untuk menyumbangkan bahan bakunya. Berikut adalah daftar nama-nama penyumbang beserta bahan baku yang disumbangkan.

Terigu Susu Butter Gula Telur

Susi

Debi

Beti

Tuti

Ruli

Kemudian ibu Soffie menyuruh putrinya, Yovie, untuk mengumpulkan bahan-bahan tersebut. Bantulah Yovie dalam mencari kombinasi penyumbang siapa saja yang perlu dikunjungi, dengan catatan seluruh bahan baku lengkap terkumpul dan sesedikit mungkin yang dikunjungi.

Solusi : Asumsikan bahwa inisial s, d, b, t, r digunakan untuk mewakili nama-nama yang terdaftar pada tabel. Berdasarkan tabel, untuk mendapatkan terigu, Yovie harus mengunjungi Susi atau Beti, atau bila dinotasikan dalam ekspresi boolean adalah : (s + b). Sedangkan untuk mendapatkan susu, Yovie harus mengunjungi Beti atau Tuti atau Ruli, atau (b+t+r). Untuk butter, gula, dan telur masing-masing ekspresi booleannya adalah (s + d + r), (d + r), t. Sehingga ekspresi Boolean untuk mendapatkan kelima bahan adalah :

trdrdsrtbbsrtbdsf ⋅+⋅++⋅++⋅+= )()()()(),,,,(

Dan bila ekspresi Boolean ini kita ubah ke dalam bentuk kanonik minterm, akan kita dapatkan:

QUINE McCLUSKEY 35

),,,,( rtbdsf btrdstrbdsdbtrsrdbtsbtrds ′+′′+′+′′+′′=

sdbtrrsdbttrbsdrtbsd +′+′+′′+

Untuk mendapatkan kombinasi penyumbang yang paling minimum, kita harus mencari bentuk paling sederhana dari fungsi Boolean , untuk itu di sini kita gunakan metode Quine-McCluskey.

f

minterm String minterm String

1 btrds ′' 00111 (1,6) btrd ′ -0111

2 rdbts ′' 01110 (2,8) rdbt ′ -1110

3 rtbsd ′′ 11010 (3,7) tbsd ′ 1101-

4 trbds ′′ 10011 (4,7) trbs ′ 1-011

5 dbtrs' 01111 (5,9) dbtr -1111

6 btrds ′ 10111 (6,9) sbtr 1-111

7 trbsd ′ 11011 (7,9) sdtr 11-11

8 rsdbt ′ 11110 (8,9) sdbt 1111-

9 sdbtr 11111 -

minterm String

(1,5,6,9) btr --111

(2,5,8,9) dbt -111-

(3,7,8,9) sdt 11-1-

36 MATEMATIKA DISKRIT

(4,6,7,9) str 1--11

Diperoleh ( ) strsdtdbtbtrrtbdsf +++=,,,, , dengan kata lain kombinasi yang bisa dikunjungi oleh Yovie untuk mendapatkan seluruh bahan : Beti-Tuti-Ruli, atau Debi-Beti-Tuti, atau Susi-Debi-Tuti, atau Susi-Tuti-Ruli.

Kasus 3 diambil dari buku Pengantar Logika Matematika karya Setiadi Rachmat, Penerbit Informatika, ISBN : 979-3338-35-0. Kasus 1 dan 2 diambil dari buku Matematika Diskrit karya Rinaldi Munir, Penerbit Informatika, ISBN 979-96446-3-1.

Penjelasan untuk kasus 3, merubah ekspresi Boolean berikut, trdrdsrtbbsrtbdsf ⋅+⋅++⋅++⋅+= )()()()(),,,,( ke dalam

bentuk kanonik minterm (SOP).

Bentuk tabel kebenaran berikut :

s d

b t r bs +

rtb ++ rds ++ rd + f

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1

QUINE McCLUSKEY 37

0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Term-term yang diambil merepresentasikan nilai 1=f . Perhatikan pada tabel nilai sangat mempengaruhi nilai daripada . t f

Kasus 1

Sebagai seorang manajer pelatih klub sepakbola AC Milan anda diminta untuk membeli beberapa pemain dengan ketentuan pembelian pemain harus mencakup keseluruhan formasi posisi yang dibutuhkan oleh klub dan pengeluaran biaya belanja sehemat mungkin. Tentukan kombinasi pemain-pemain yang akan anda beli dengan pengeluaran biaya seminimum mungkin.

Petunjuk : Pilih para pemain anda secara bebas dengan syarat jumlah biaya keseluruhan pemain tidak melebih Rp. 40 Milyar (Biaya belanja pemain yang disediakan klub).

Daftar pemain yang masuk bursa transfer adalah sebagai berikut :

38 MATEMATIKA DISKRIT

Defender

Wings

Midfield

Attacking

Midfield

Forward

$

Cannavaro 10 Beckham 10 Zidane 15 Del Piero 15 Kaka 15 Ronaldinho 15 Inzaghi 10 Gattuso 15 Pirlo 10 Xavi 10 Maldini 10

Kasus 2

Jika anda akan memilih isteri dari beberapa calon yang akan dijodohkan kepada anda, dengan berbagai kriteria berikut :

Agama Cantik Keturunan Kaya

Intan Fitri Lisa Rani

Maka tentukan urutan pasangan calon yang akan anda pilih dari berbagai nama pada tabel di atas.

BBaabb 44

KONVOLUSI

4.1 Pondasi konvolusi

Konvolusi 2 buah fungsi ( )xf dan didefinisikan sebagai : ( )xg

( ) ( ) ( ) ( ) ( )∫∞

∞−

−≅⊗= daaxgafxgxfxh

notasi merupakan operator konvolusi. Untuk fungsi diskrit konvolusi didefinisikan sebagai,

⊗

( ) ( ) ( ) ( ) ( )∑∞

−∞=

−≅⊗=a

axgafxgxfxh

di mana merupakan kernel konvolusi atau kernel filter. ( )xg

Untuk fungsi dua dimensi, operasi konvolusi didefinisikan sebagai : (untuk fungsi kontinu)

( ) ( ) ( ) ( ) ( )∫ ∫∞

∞−

∞

∞−

−−≅⊗= dadbbyaxgbafyxgyxfyxh ,,,,,

40 PENGOLAHAN CITRA

dan untuk fungsi diskrit, didefinisikan sebagai :

( ) ( ) ( ) ( ) (∑∑∞

∞−

∞

∞−

−−≅⊗= byaxgbafyxgyxfyxh ,,,,, )

Fungsi filter ( )yxg , disebut juga filter konvolusi, mask konvolusi, kernel konvolusi, atau template. Ilustrasi konvolusi diperlihatkan pada gambar 4.1.

0x 1x 2x

3x 4x 5x

6x 7x 8x

A B C

D E F

G H I

template ( )jif ,

Image

( ) 876543210, IxHxGxFxExDxCxBxAxjif ++++++++=

Gambar 4.1 Ilustrasi Konvolusi

KONVOLUSI 41

Perhatikan kasus berikut, citra dikonvolusi

menggunakan template akan menghasilkan citra yang baru

dengan nilai-nilai = .

44111333123441143311

⎥⎦

⎤⎢⎣

⎡1001

******7723*7742*6752

Template–template yang sering muncul penggunaannya dalam pengolahan citra (meminimalisir noise pada citra, edge detection, filtering, dan lain – lain) adalah template klasikal 3x3. Template yang diaplikasikan sebagai low-pass filter adalah,

111111111

Pengaplikasian untuk high-pass filter digunakan template

010141

010

−−−

−

Template yang lain yang sering juga digunakan untuk melakukan smoothing citra adalah,

1313163131

42 PENGOLAHAN CITRA

Tabel 4.1 memperlihatkan operasi high-pass filter dan low-pass filter pada suatu citra yang memiliki nilai-nilai intensitas pixel berikut :

0000001110016100111001110011100111000000

Tabel 4.1

Citra Sesudah high-pass Sebelum low-pass

0000001110016100111001110011100111000000

…………………

2424204

151101101212

−−−

−

…………………

9119111411111411696696464

…………………

Kasus yang lain, perhatikan tabel 4.2.

KONVOLUSI 43

Tabel 4.2

Citra

Sesudah konvolusi

dengan 1111 −−

Sesudah konvolusi

dengan 1111

−−

⎥⎦

⎤⎢⎣

⎡ −−1111

+ ⎥⎦

⎤⎢⎣

⎡−−

1111

333300333300333300333300000000000000000000

000000000000000666300000000000

000600006000060000300000000000

000600006000060666600000000000

4.2 Perancangan program

Untuk Perancangan program konvolusi menggunakan Delphi dapat kita lakukan langkah-langkah berikut :

1. Jalankan Delphi.

44 PENGOLAHAN CITRA

2. Tambahkan icon Panel1, Panel2, Image1, Image2, MainMenu1 dan OpenPictureDialog pada form :

Untuk Panel1, Nilai-nilai property pada object inspector adalah :

Bevellnner bvLowered

BevelOuter bvLowered

Untuk Image1, icon Image1 letakkan di atas Panel1 pada Form1. Nilai-nilai property pada object inspector adalah :

Stretch True

Untuk Panel2, Nilai-nilai property pada object inspector adalah :

Bevellnner bvLowered

KONVOLUSI 45

BevelOuter bvLowered

Untuk Image2, icon Image2 letakkan di atas Panel2 pada Form1. Nilai-nilai property pada object inspector adalah :

Stretch True

Untuk MainMenu1, klik 2x pada icon MainMenu1, sehingga muncul tampilan :

Atur sedemikian hingga, agar tampilan menjadi :

46 PENGOLAHAN CITRA

File

Open Konvolusi

Image Processing

Klik 2x pada MainMenu1→File Open, setelah muncul halaman editor, tuliskan listing berikut :

→

if not OpenPictureDialog1.Execute then exit else begin gambar := TBitmap.Create; gambar.LoadFromFile(OpenPictureDialog1.filename); Form1.Caption:= 'Image Processing - '+ ExtractFileName

(OpenPictureDialog1.Filename); end;

KONVOLUSI 47

if gambar.PixelFormat <> pf24bit then gambar.PixelFormat := Pf24bit;

Image1.Picture.Bitmap := gambar;

Kembali ke form1, Klik 2x pada MainMenu1 Image Processing→ Konvolusi, setelah muncul halaman editor, tuliskan listing berikut :

→

procedure TForm1.Invert1Click(Sender: TObject); const konvolusi : array[0..1,0..2,0..2] of smallint = (((1,1,1),(1,1,1),(1,1,1)), ((0,0,0),(0,0,0),(0,0,0))); var row : array[0..8] of pbytearray; col : pbytearray; x,y : smallint; i,j,k,p : smallint; image : tbitmap; sum,jum : longint; begin P:=-120; image := tbitmap.Create; Image.Assign(gambar); for y:=1 to gambar.Height-2 do begin for i:=-1 to 1 do row[i+1]:= Image.ScanLine[y+i]; col := gambar.ScanLine[y]; x:=3; repeat sum := 0; for i:=-1 to 1 do for j:=-1 to 1 do sum:=sum+(konvolusi[0,i+1,j+1]*row[i+1,x+j*3]); jum:=0; for i:=-1 to 1 do for j:=-1 to 1 do jum:=jum+(konvolusi[1,i+1,j+1]*row[i+1,x+j*3]); sum := (sum + jum)+p;

48 PENGOLAHAN CITRA

if sum>255 then sum:=255; if sum<0 then sum:=0; for k:=0 to 2 do col[x+k]:=sum; inc(x,3); until x>=3*(gambar.Width-4); end; Image2.Picture.bitmap := gambar; gambar.SaveToFile('Fadlisyah.bmp'); Image.free; end;

3. Eksekusikan program (F9).

Gambar 4.2 Hasil eksekusi citra “Zidane”

KONVOLUSI 49

Dengan sedikit merubah nilai-nilai pada template, eksekusi program akan menghasilkan output sebagai berikut :

Gambar 4.3 Hasil eksekusi citra “Zidane” dengan template

const konvolusi : array[0..1,0..2,0..2] of smallint = (((1,0,1),(1,0,1),(1,0,1)), ((0,0,0),(0,0,0),(0,0,0)));

50 PENGOLAHAN CITRA

BBaabb 55

BILANGAN FLOATING POINT

Bilangan floating-point, berisikan 2 bagian, yaitu mantisa (signifikan atau pecahan), dan eksponen. Gambar 5.1 memperlihatkan bentuk 4 byte dan 8 byte dari bilangan floating-point yang disimpan di dalam sistem Intel. Bilangan floating-point atau bilangan real 4 byte disebut single-precision, dan Bilangan floating-point atau bilangan real 8 byte disebut double-precision.

31 30 23 22 0

S Eksponen Mantisa

(a)

63 62 52 51 0

S Eksponen Mantisa

(b)

Gambar 5.1 (a) Presisi tunggal menggunakan bias 7FH, dan (b) Presisi

Ganda menggunakan bias 3FFH

52 MATEMATIKA DISKRIT

Mantisa 24-bit memiliki bit satu yang tersembunyi (implied), yang memungkinkan mantisa untuk mewakili 24-bit walau hanya disimpan 23-bit. Bit yang disembunyikan adalah bit pertama dari bilangan yang dinormalisasi. Pada saat menormalisasi bilangan, bit ini diatur sehingga nilainya sekurang-kurangnya 1, tetapi kurang dari 2. sebagai contoh, jika 12 diubah ke biner ( )21102 , maka dinormalisasi dan hasilnya . Bit satu yang terdapat di depan tanda koma akan disembunyikan, atau tidak disimpan di dalam bagian mantisa.

321,1 ×

Eksponen disimpan dalam eksponen terbias (biased exponent). Untuk presisi tunggal, Bias 7FH (127) akan dijumlahkan ke eksponen sebelum disimpan ke dalam tempat eksponen, dan untuk presisi ganda sebesar 3FFH (1023).

Ada 2 pengecualian mengenai aturan-aturan yang diterapkan mengenai bilangan floating-point. Angka 0,0 disimpan semuanya sebagai nol. Bilangan tak hingga disimpan dalam eksponen sebagai satu, dan dalam mantisa semuanya sebagai nol. Bit tanda menunjukkan bilangan tak hingga tersebut bernilai positif atau negatif.

Kasus 1

Bagaimana bilangan +12 disimpan dalam bentuk presisi tunggal.

Penyelesaian :

Desimal Biner Normal Tanda

+12 1100 321,1 × 0

s Eksponen

0 1 0 0 0 0 0 1 0

31

30

29

28

27

26

25

24

23

FLOATING POINT 53

Mantisa

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

22

21

20

19

18

17

16

15

14

13

12

11

10

9 8 7 6 5 4 3 2 1 0

Penjelasan :

+ = 0, pangkat pada normalisasi adalah 3 atau dalam bentuk biner sama dengan . Selanjutnya untuk presisi tunggal eksponen dapat diperoleh dengan menambahkan +7FH =

211

211 22 111111111 + = . 210000010

Kasus 2

Bagaimana bilangan -12 disimpan dalam bentuk presisi tunggal.

Penyelesaian :

Desimal Biner Normal Tanda

-12 1100 - 321,1 × 1

s Eksponen

1 1 0 0 0 0 0 1 0

31

30

29

28

27

26

25

24

23

Mantisa

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

22

21

20

19

18

17

16

15

14

13

12

11

10

9 8 7 6 5 4 3 2 1 0

54 MATEMATIKA DISKRIT

Kasus 3

Bagaimana bilangan +100 disimpan dalam bentuk presisi tunggal.

Penyelesaian :

Desimal Biner Normal Tanda

+100 1100100 621001,1 × 0

s Eksponen

0 1 0 0 0 0 1 0 1

31

30

29

28

27

26

25

24

23

Mantisa

1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22

21

20

19

18

17

16

15

14

13

12

11

10

9 8 7 6 5 4 3 2 1 0

Penjelasan :

Konversi bilangan 100 menjadi bilangan biner adalah sebagai berikut :

100/2 Sisa 0 3/2 Sisa 1

50/2 Sisa 0 1/2 Sisa 1

25/2 Sisa 1 0

12/2 Sisa 0

6/2 Sisa 0 1100100

FLOATING POINT 55

Kasus 4

Bagaimana bilangan -1,75 disimpan dalam bentuk presisi tunggal.

Penyelesaian :

Desimal Biner Normal Tanda

-1,75 1,11 - 0211,1 × 1

s Eksponen

1 0 1 1 1 1 1 1 1

31

30

29

28

27

26

25

24

23

Mantisa

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22

21

20

19

18

17

16

15

14

13

12

11

10

9 8 7 6 5 4 3 2 1 0

Penjelasan :

Konversi bilangan -1,75 menjadi bilangan biner adalah sebagai berikut: (kita ambil 0,75, 1 desimal = 1 biner), sampai di sini kita sudah dapat menyatakan sebagai 1,…

0,75 x 2

0,5 x 2 Digit 1

1,0 Digit 1

1,11

56 MATEMATIKA DISKRIT

Kasus 5

Bagaimana bilangan +0,25 disimpan dalam bentuk presisi tunggal.

Penyelesaian :

Desimal Biner Normal Tanda

+0,25 0,01 22,1 −× 0

s Eksponen

0 0 1 1 1 1 1 0 1

31

30

29

28

27

26

25

24

23

Mantisa

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22

21

20

19

18

17

16

15

14

13

12

11

10

9 8 7 6 5 4 3 2 1 0

Penjelasan :

Konversi bilangan +0,25 menjadi bilangan biner adalah sebagai berikut: (kita ambil 0,25, 0 desimal = 0 biner), sampai di sini kita sudah dapat menyatakan sebagai 0,…

0,25 x 2

0,5 x 2 Digit 0

1,0 Digit 1

0,01

FLOATING POINT 57

Eksponen terbias kita peroleh dengan menjumlahkan :

7FH 1111111

-2 -0000010

1111101

Berbagai kasus yang lain, ditinggalkan untuk ujicoba para mahasiswa,

Andai diketahui :

Ujicoba 1

s Eksponen

0 1 0 0 0 0 0 0 0

31

30

29

28

27

26

25

24

23

Mantisa

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

22

21

20

19

18

17

16

15

14

13

12

11

10

9 8 7 6 5 4 3 2 1 0

Maka ubahlah bilangan floating-point di atas ke dalam bilangan desimal.

Ujicoba 2

s Eksponen

1 0 1 1 1 1 1 1 1

31

30

29

28

27

26

25

24

23

58 MATEMATIKA DISKRIT

Mantisa

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

22

21

20

19

18

17

16

15

14

13

12

11

10

9 8 7 6 5 4 3 2 1 0

Maka ubahlah bilangan floating-point di atas ke dalam bilangan desimal.

Ujicoba 3

s Eksponen

0 1 0 0 0 0 0 1 0

31

30

29

28

27

26

25

24

23

Mantisa

1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

22

21

20

19

18

17

16

15

14

13

12

11

10

9 8 7 6 5 4 3 2 1 0

Maka ubahlah bilangan floating-point di atas ke dalam bilangan desimal.

Keseluruhan bahan dan berbagai kasus yang menyertai bab ini, disadur dari buku Brey, Barry B. 2000. Mikroprosesor Intel 8086/8088, 80186/80188, 80286, 80386, 80486, Pentium, dan Pentium-Pro : Arsitektur, Pemrograman, Antarmuka (Edisi kelima jilid 1), Penerbit Erlangga, yang diterjemahkan oleh Ir. N.R. Poespawati, M.T.

BBaabb 66

KODE HAMMING

Sistem memori semikonduktor dapat mengalami kegagalan (error). Error-error ini dapat dikategorikan sebagai kegagalan yang berat dan error ringan. Kegagalan berat merupakan kerusakan isi yang permanen sehingga sel memori yang mengalaminya tidak dapat lagi digunakan untuk menampung data. Error-error berat dapat disebabkan oleh kesalahan penggunaan, dan kerusakan yang berasal dari pabrik. Error ringan adalah kejadian yang random dan tidak merusak yang mengubah isi sebuah sel memori atau lebih, tanpa merusak memori. Error ringan dapat disebabkan oleh masalah catu daya atau partikel-partikel alpha. Partikel-partikel ini adalah hasil dari peluruhan radioaktif dan merupakan akibat adanya inti radioaktif dalam jumlah kecil yang secara alami terdapat pada seluruh materi. Baik error berat maupun ringan merupakan hal yang tidak diinginkan, hampir semua sistem memori utama modern memiliki logik untuk mendeteksi dan mengoreksi error-error tersebut.

Gambar 6.1 menjelaskan secara umum tentang proses yang terjadi. Ketika data dibaca ke dalam memori, kalkulasi, yang digambarkan sebagai fungsi , dibentuk dengan data tersebut untuk menghasilkan kode. Baik data maupun kode itu disimpan. Jadi, apabila sebuah word M bit data akan disimpan, dan kode memiliki panjang K bit, maka ukuran aktual word yang disimpan adalah M + K bit.

f

60 MATEMATIKA DISKRIT

Ketika word yang sebelumnya tersimpan akan dibaca, maka kode digunakan untuk mendeteksi dan mengoreksi error yang mungkin terjadi. Bit-bit kode K yang baru dihasilkan dari M bit data dan dibandingkan dengan bit kode yang diambil. Perbandingan tersebut akan menghasilkan salah satu dari tiga kemungkinan :

Tidak terdapat error. Data bit yang diperhatikan akan dikirimkan.

Terjadi error, dan dimungkinkan untuk mengoreksinya. Bit-bit data dan bit-bit koreksi error dimasukkan ke korektor, yang menghasilkan bit-bit M yang dikoreksi akan dikirimkan.

Terjadi error, namun tidak dimungkinkan untuk mengoreksinya. Keadaan ini akan dilaporkan.

Kode yang beroperasi dengan cara seperti ini disebut sebagai error-correcting code. Sebuah kode dicirikan oleh sejumlah error bit dalam word yang dapat dikoreksi dan dideteksinya.

Kode perbaikan error yang paling sederhana adalah kode Hamming yang diciptakan oleh Richard Hamming di Laboratorium Bell. Gambar 6.2 menggunakan diagram Venn untuk menjelaskan penggunaan kode ini bagi word 4 bit (M = 4). Dengan tiga buah lingkaran yang berpotongan, terdapat tujuh kompartemen. Kita akan memberikan 4 buah bit data ke kompartemen yang terletak di tengah (Gambar 6.2 a). Kompartemen sisanya diisi dengan apa yang kita sebut bit paritas. Setiap bit paritas dipilih sehingga bilangan 1 di dalam lingkaran berjamlah genap (Gambar 6.2 b). Jadi, karena lingkaran A terdiri dari tiga buah data bilangan l , maka bit paritas di dalam lingkaran itu disetel menjadi l. Sekarang, apabila suatu error mengubah salah satu bit data (Gambar 6.2 c), maka error itu akan dengan mudah ditemukan. Dengan memeriksa bit paritas, cacat-cacat dapat ditemukan pada lingkaran A dan C namun tidak pada lingkaran B. Hanya salah satu dari kompartemen

KODE HAMMING 61

berada pada A dan C namun tidak pada B. Karena itu error dapat dikoreksi dengan mengubah bit tersebut.

Untuk menjelaskan konsep tersebut, kita akan membuatlah kode yang dapat mendeteksi dan mengoreksi error bit tunggal di dalam word 8-bit. Untuk memulainya, kita tentukan panjang kode seharusnya. Sehubungan dengan Gambar 6.1 logik perbandingan menerimanya sebagai input dua nilai K bit. Perbandingan bit demi bit dilakukan dengan memperhatikan exclusive-or kedua input itu. Hasilnya disebut sebagai syndrome word. Jadi, setiap bit syndrome sama dengan 0 atau 1 apabila terdapat atau tidak cocok dalam posisi bit kedua input tersebut.

Error Signal

Corrector

Compare

Memory f

f

Data Out

Data In

M

M M K

K K

Gambar 6.1 Fungsi kode koreksi error

62 MATEMATIKA DISKRIT

1

1

1 0 1

1

1 0

1

0

0

1

1

0 0

1

0

0 1

1

0 0

1

0

0

(a) (b)

(c) (d)

Gambar 6.2 Error-correcting code dari Hamming

Dengan demikian syndrome word mempunyai lebar K bit dan memiliki range yang berada di antara 0 dan K2 12 −K . Nilai 0 berarti bahwa tidak terdeteksi error, yang menyisakan 12 −K buah nilai untuk mengindikasikan bit mana yang mengalami error, bila terdapat error. Karena suatu error dapat terjadi pada sembarang M bit data atau K bit check, maka syarat yang harus dipenuhi,

KMK +≥−12

KODE HAMMING 63

Mekanismenya adalah, atur layout bit-bit data dan bit-bit check

Bit position Position number Check bit Data bit

12 1100 M8

11 1011 M7

10 1010 M6

9 1001 M5

8 1000 C8

7 0111 M4

6 0110 M3

5 0101 M2

4 0100 C4

3 0011 M1

2 0010 C2

1 0001 C1

Bit-bit check dihitung sebagai berikut :

C1 = M1⊕M2⊕M4⊕M5⊕M7 1,2,4,5,7

C2 = M1⊕M3⊕M4⊕M6⊕M7 1,3,4,6,7

C4 = M2⊕M3⊕M4⊕M8 2,3,4,8

C8 = M5⊕M6⊕M7⊕M8 5,6,7,8

64 MATEMATIKA DISKRIT

Kita akan menguji pola ini, apakah efektif untuk menguji kesalahan yang terjadi.

Kasus :

Andaikan word input 8-bit sama dengan 00111001, dengan bit data M1 berada pada posisi paling kanan.

M8 M7 M6 M5 M4 M3 M2 M1

0 0 1 1 1 0 0 1

Perhitungannya adalah sebagai berikut :

C1 = M1⊕M2⊕M4⊕M5⊕M7 1⊕0⊕1⊕1⊕0=1

C2 = M1⊕M3⊕M4⊕M6⊕M7 1⊕0⊕1⊕1⊕0=1

C4 = M2⊕M3⊕M4⊕M8 0⊕0⊕1⊕0=1

C8 = M5⊕M6⊕M7⊕M8 1⊕1⊕0⊕0=0

Seandainya terjadi kesalahan pada bit data ketiga, berubah dari 0 menjadi 1. Maka kalkulasinya adalah :

M8 M7 M6 M5 M4 M3 M2 M1

0 0 1 1 1 1 0 1

C1 = M1⊕M2⊕M4⊕M5⊕M7 1⊕0⊕1⊕1⊕0=1

C2 = M1⊕M3⊕M4⊕M6⊕M7 1⊕1⊕1⊕1⊕0=0

C4 = M2⊕M3⊕M4⊕M8 0⊕1⊕1⊕0=0

C8 = M5⊕M6⊕M7⊕M8 1⊕1⊕0⊕0=0

KODE HAMMING 65

Bit-bit check yang baru dibandingkan dengan bit-bit check yang lama, maka syndrome word yang terbentuk adalah :

C8 C4 C2 C1

0 1 1 1

⊕ 0 0 0 1

0 1 1 0

0110 biner setara dengan nilai 6 desimal, yang mengindikasikan bahwa posisi bit 6 mengalami error, atau bit data 3 mengalami error.

Keseluruhan isi materi bab ini disadur dari Stalling, William. 1998. Organisasi dan Arsitektur Komputer : Perancangan Kinerja (jilid 1), Prentice Hall yang diterjemahkan oleh PT Prenhallindo, Jakarta.

66 MATEMATIKA DISKRIT

B

)

Baabb 77

GRAPH

Graph terdiri dari sebuah himpunan tidak kosong terbatas dari berbagai verteks dan edge yang memuat sebarang himpunan bagian dari berbagai pasangan

( EVG ,=

{ }{ }wvVwvwv ≠∈ ,,:, . Edge { }wv, dapat diekspresikan sebagai atau dan dinyatakan sebagai relasi verteks ke verteks , di mana disebut titik-titik ujung dari edge .

vw wvv w wv,

vw

Contoh, andaikan ( )EVG ,= merupakan graph dengan sekumpulan verteks V={Meryl Streep, Dustin Hoffman, Jeremy Irons, Anne Bancroft, Robert Redford} dan asumsikan pula sekumpulan edge didefinisikan sebagai :

VwvvwE ∈= ,:{ telah membuat film bersama sebelum 1992 }.

Maka ilustrasi yang mungkin adalah sebagai berikut : G

Jeremy Irons Robert Redford Anne Bancroft

Dustin Hoffman Meryl Streep

68 MATEMATIKA DISKRIT

Derajat verteks Vv∈ di dalam graph ( )EVG ,= merupakan jumlah verteks yang terhubung ke , dinyatakan sebagai v vδ . Ambil kasus berikut :

7

Dapat dilihat bahwa graph ( )EVG ,= memiliki 11 verteks dan 10 edge., dengan derajat verteks 7 adalah 4, .47 =δ Jumlah keseluruhan derajat adalah 20, yang mana dua kali jumlah edge.

Kasus : berapa banyak tree yang dapat dibentuk berdasarkan sekumpulan verteks { }5,4,3,2,1 dengan derajat verteks 31=δ ,

22 =δ , 13 =δ , 14 =δ , 15 =δ ?

Solusi :

5 5

3 2 1 4 3 1 2 4

GRAPH 69

5

1

3 2

4

Keterangan : tree merupakan bagian graph yang terstruktur.

Teorema : andaikan , , merupakan bilangan bulat positif dengan jumlah

nddd ,....,, 21 2≥n22 −n . Maka jumlah tree pada himpunan verteks

dengan derajat verteks { n,...,2,1 } nn dd == δδ ,...,1 1 adalah

( )( ) ( ) ( )!1!....1!1

!2

21 −−−−

ndddn

Bukti : kita tinggalkan sebagai tugas mahasiswa.

Teorema : (Cayley) untuk , jumlah tree pada verteks 2≥n { }n,...,2,1 adalah . 2−nn

Bukti : kita tinggalkan sebagai tugas mahasiswa.

Kasus : ada 16 tree pada himpunan verteks { }4,3,2,1 . Ada 16 pasang pasangan bilangan bulat yang berbentuk , di mana a dan dipilih secara bebas dari himpunan verteks

ab b{ }4,3,2,1 , dan oleh karenanya kita

dapat menamakan setiap tree yang ditemukan dengan 16 pasang bilangan bulat di atas berdasarkan ketentuan. (alasan penamaan tree akan dijelaskan kemudian )

Solusi :

70 MATEMATIKA DISKRIT

Algoritma Prüfer

Algoritma Prüfer digunakan untuk menamakan tree, dan nama yang diperoleh disebut sebagai kode Prüfer.

Jika diberikan sebuah tree dengan himpunan verteks { }n,...,2,1 , maka untuk menentukan kode Prüfer adalah,

1. Temukan verteks yang terkecil berderajat 1, katakan . Andaikan merupakan verteks yang dihubungkan ke .

vw v

2. Nyatakan w dan buang verteks v dan edge . vw3. Jika tree yang terbentuk masih memiliki lebih dari satu edge,

ulangi langkah (1), sebaliknya jika tidak, maka algoritma berhenti.

GRAPH 71

Contoh kasus : aplikasikan algoritma Prüfer untuk menamakan tree T yang diilustrasikan berikut :

3

1

2

6

4 5

3

4 5

6

2

T

2

3

2

5

3

2

23

233

6 6

2 2332

6

72 MATEMATIKA DISKRIT

Seandainya kasus yang terjadi adalah kebalikan dari kasus di atas, kode Prüfer diketahui, dan kita ingin mengkonstruksikan tree dari kode Prüfer tersebut, maka algoritma inverse berikut kita gunakan.

Algoritma : diberikan suatu daftar angka-angka yang secara bebas dipilih dari

21... −naa{ }n,...,2,1 , untuk menemukan tree T menggunakan

daftar kode Prüfer adalah :

1. Nyatakan daftar pertama , daftar kedua dan mulai dengan himpunan verteks

21... −naa n,...,2,1{ }n,...,2,1 dan sekumpulan

kosong berbagai edge.

2. Temukan angka terkecil, katakan i , yang hadir pada daftar kedua dan tidak hadir pada daftar pertama. Hapus leading-entry pada daftar pertama, katakan , hapus i dari daftar kedua dan tambahkan edge ij ke himpunan edge.

j

3. Jika terdapat sebarang angka yang masih tertinggal dalam daftar pertama, maka ulangi langkah (2). Sebaliknya, jika daftar pertama kosong, maka daftar kedua akan terdiri dari dua angka. Tambahkan satu edge terakhir ke himpunan edge yang terdiri dari dua angka yang dihubungkan bersama; kemudian algoritma berhenti.

Contoh kasus : rekonstruksikan tree T dengan kode Prüfer 2332?.

Solusi :

2332 123456 Tambahkan edge 12

Keterangan : mulai dari angka terkecil, pada kolom pertama terlihat bahwa angka terkecil adalah 2, dan angka terkecil yang tidak terdapat pada kolom pertama adalah 1.

Maka kita bentuk edge 12,

GRAPH 73

2

1

Buang angka 2 pada kolom pertama dan angka 1 pada kolom kedua sehingga :

332 23456 Tambahkan edge 34

Keterangan : mulai dari angka terkecil, pada kolom pertama terlihat bahwa angka terkecil adalah 3, dan angka terkecil yang tidak terdapat pada kolom pertama adalah 4.

Maka kita bentuk edge 34,

4

1

3

2

Buang angka 3 pada kolom pertama dan angka 4 pada kolom kedua sehingga :

74 MATEMATIKA DISKRIT

32 2356 Tambahkan edge 35

Keterangan : mulai dari angka terkecil, pada kolom pertama terlihat bahwa angka terkecil adalah 3, dan angka terkecil yang tidak terdapat pada kolom pertama adalah 5.

Maka kita bentuk edge 35,

3

4 5

2

1

Buang angka 3 pada kolom pertama dan angka 5 pada kolom kedua sehingga :

2 236 Tambahkan edge 23

Keterangan : mulai dari angka terkecil, pada kolom pertama terlihat bahwa angka terkecil adalah 2, dan angka terkecil yang tidak terdapat pada kolom pertama adalah 3.

Maka kita bentuk edge 23,

GRAPH 75

3

4 5

2

1

Buang angka 2 pada kolom pertama dan angka 3 pada kolom kedua sehingga :

- 26 Tambahkan edge 26

Maka kita bentuk edge 26,

3

4 5

6

2

1

76 MATEMATIKA DISKRIT

Kasus yang ditinggalkan untuk mahasiswa :

Konstruksikan sebuah graph ( )EVG ′′=′ , yang memuat verteks V = { seluruh negara di kawasan Asia } dan edge yang didefinisikan

′E ′=

{vw : v,w memiliki batas negara yang sama}. Setelah berhasil diselesaikan, kasus diperluas untuk kawasan-kawasan wilayah lainnya.

DAFTAR PUSTAKA

Brey, Barry B. 2000. Mikroprosesor Intel 8086/8088, 80186/80188,

80286, 80386, 80486, Pentium, dan Pentium-Pro : Arsitektur, Pemrograman, Antarmuka (Edisi kelima jilid 1), Penerbit Erlangga.

Bryant, Victor. 1993. Aspect of Combinatorics : A Wide-Ranging Introduction, Cambridge University Press.

Fadlisyah, S.Si., 2007. Computer Vision & Pengolahan Citra., Penerbit Andi Yogyakarta.

Fadlisyah, S.Si., 2007. Pengantar Grafika Komputer., Penerbit Andi Yogyakarta.

Gonzalez, Rafael C., dan Wintz, Paul. 1987. Digital Image Processing, Addison Wesley

Hearn, D. dan Baker, MP. 1994. Computer Graphics. Englewood Cliffs, New Jersey : Prentice-Hall

Konishi, Scott., Yuillie, Alan L., Coughlan, James M., dan Zhu, Song Chun., 2003, Statistical Edge Detection : Learning and Evaluating Edge Cues, IEEE Transaction on Pattern Analysis and Machine Intelligence Vol 5, No. 1, 57 - 74

Low, Adrian. 1991, Computer Vision & Image Processing: Introductory, McGraw-Hill International Editions.

Mano, M. Morris. 1993. Computer System Architecture, Prentice-Hall International.

Munir, Rinaldi. 2003, Matematika Diskrit : Edisi Kedua, Informatika Bandung

Munir, Rinaldi. 2004, Pengolahan Citra Digital dengan Pendekatan Algoritmik, Informatika Bandung

Purcell, Edwin J. dan Varberg, Dale. 1987. Kalkulus dan Geometri Analitis Edisi Kelima, Erlangga

Rachmat, Setiadi. 2004. Pengantar Logika Matematika, Penerbit Informatika, Bandung.

Rogers, DF dan Adams, JA.1989. Mathematical Elements For Computer Graphic : McGraw-Hill

Stalling, William. 1998. Organisasi dan Arsitektur Komputer : Perancangan Kinerja (jilid 1), Prentice Hall yang diterjemahkan oleh PT Prenhallindo, Jakarta.

RIWAYAT HIDUP PENULIS

Fadlisyah, S.Si berprofesi sebagai seorang dosen di Universitas Negeri Malikussaleh (UNIMAL). Saat ini beliau menjabat sebagai Kepala Laboratorium Teknik Informatika. Menyelesaikan pendidikannya di Fakultas MIPA program Ilmu Komputer, Universitas Padjadjaran Bandung pada tahun 2000. Selain aktif menulis beberapa buku teks komputer untuk tingkat bacaan mahasiswa, beliau juga aktif melakukan kegiatan riset – riset

yang berkaitan dengan Artificial Intelligence, dan Computer Vision. Adapun buku – buku yang telah dikeluarkannya antara lain : Komputer Visi & Pengolahan Citra, Komputer Visi Biometriks, dan lain – lain yang belum terpublikasi. Mengasuh mata kuliah Komputer Grafik, Pemrograman Matematika, Teori Bahasa & Otomata, Kecerdasan Buatan, Sistem Operasi (Linux), Pengolahan Citra, Komputer Visi, dll. Alamat yang dapat dihubungi : Fakultas Teknik UNIMAL, jln. Samudera No.35. Lhokseumawe. Telepon 0645- 42076.

MATEMATIKA DISKRIT Representasi data di dalam komputer bersifat tidak kontinu, untuk itu pemanipulasiannya diperlukan suatu teknik khusus. Teknik-teknik ini memiliki kesamaan tujuan yaitu pengolahan diskrit, yang dapat dikatakan sebagai matematika diskrit. Matematika diskrit hadir sebagai suatu bidang kajian yang berkonsentrasi terhadap pemanipulasian berbagai data diskrit. Keunggulan yang ditawarkan buku ini adalah semua pembahasan benar-benar beorientasi kepada pemanipulasian data. Sehingga mahasiswa dapat secara tepat mengasosiakan implementasi dari berbagai materi yang dibahas ke dalam berbagai proses di dalam komputer. Adapun materi yang dibahas di dalam buku ini adalah : Logika, Peta Karnaugh, Metode QuineMcCluskey, Konvolusi, Representasi Bilangan Floating-Point, Kode Hamming, dan Teori Graph. Buku ini ditujukan kepada mahasiswa yang mengambil mata kuliah matematika diskrit, sebagai sarana primitif untuk menjangkau konsep-konsep pemanipulasian data yang lebih mendalam.