Kode Linier dari Graf Strongly Regular dan Operasinya
TUGAS AKHIR Diajukan untuk Memenuhi Persyaratan Sidang Sarjana Program Studi Matematika ITB
Oleh : Ranny Rachmaniar 10107053
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2011
Kode Linier dari Graf Strongly Regular dan Operasinya
TUGAS AKHIR Diajukan untuk Memenuhi Persyaratan Sidang Sarjana Program Studi Matematika ITB
Oleh : Ranny Rachmaniar 10107053
Telah diperiksa dan disetujui Bandung, Juni 2011 Dosen pembimbing
Dr. Djoko Suprijanto NIP. 132147117
PROGRAM STUDI SARJANA MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2011
” Hai orang-orang beriman apabila dikatakan kepadamu: ” Berlapang-lapanglah dalam majlis ”, maka lapangkanlah niscaya Alloh akan memberi kelapangan untukmu. Dan apabila dikatakan: ”Berdirilah kamu”, Maka berdirilah, niscaya Alloh akan meninggikan orang-orang yang beriman di antaramu dan orang-orang yang diberi ilmu pengetahuan beberapa derajat. Dan Alloh Maha mengetahui apa yang kamu kerjakan”. (Q.S. al-Mujadalah: 11)
Tugas Akhir ini kupersembahkan untuk Tuhan, Bangsa, dan Almamater.
Kode Linier dari Graf Strongly Regular dan Operasinya
Abstrak Salah satu cara untuk mengonstruksi kode linier atas lapangan F2 = {0, 1} adalah dengan mengonstruksi matriks pembangkit dari matriks ketetangaan suatu graf. Kode Linier dengan panjang tertentu yang cukup besar, yang dikonstruksi dari matriks ketetanggaan suatu graf senantiasa memenuhi batas Gilbert-Varshamov. Untuk graf strongly regular, beberapa kode yang nearly optimal dan optimal telah berhasil dikonstruksi. Graf strongly regular dapat dioperasikan sehingga didapat graf baru dan kode baru yang dikonstruksi dari graf tersebut. Beberapa operasi graf yang ditinjau dalam tugas akhir ini adalah operasi gabungan, operasi join, operasi product dan operasi line graf. Dengan menggunakan operasi line graf, didapat beberapa kode yang nearly optimal dan optimal. Katakunci: kode linier, matriks pembangkit, graf strongly regular, matriks ketetanggaan, operasi graf.
i
Abstract Binary linear code can be defined by constructing generator matrix from adjacency matrix of undirected graphs. A binary linier code which is constructed by a high dimensional adjacency matrix of undirected graf will always accomplish GilbertVarshamov bound. It is well-known that from strongly regular graphs we can obtain nearly optimal and optimal codes. Moreover, strongly regular graphs can be operated to get a new graph and, as a by-product, a new code. In this final project, we observe four kind of operations on graph theory: union, join, product, and line graph. By using line graph operation, we get several codes which are nearly optimal and optimal. Keywords: linear codes, generator matrix, strongly regular graph, adjacency matrix, graph operation.
ii
Prakata Bismillaahirrohmaanirrohiim. Alhamdulillahirabbil’alamin. Segala puji hanya milik Allah SWT, Tuhan semesta alam. Berkat rahmat dan karunia-Nya penulis masih diberi kesempatan untuk menyelesaikan tugas akhir ini . Shalawat serta salam semoga terlimpah kepada junjungan Rasulullah Muhammad SAW beserta keluarganya dan seluruh insan manusia yang dikehendaki-Nya. Tugas akhir yang berjudul ”Kode Linier dari Graf Strongly Regular” ini diajukan sebagai salah satu syarat Sidang Sarjana Program Studi Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Teknologi Bandung. Terselesaikannya tugas akhir ini tidak terlepas dari semua pihak yang secara langsung maupun tidak langsung turut membantu dalam penyelesaian tugas akhir ini. Oleh karena itu dalam kesempatan ini penulis ingin mengucapkan terimakasih yang sebesar-besarnya kepada : 1. Atin Karyatin dan Dede Saeful Rachman, orangtua terbaik sedunia atas kasih sayang, doa, dan perjuangan yang tak kenal lelah dalam membesarkan dan mendidik anak-anaknya. 2. Adik-adik tersayang, Riska Amalia Rachman dan Tania Nurul Islah atas pengertian dan dukungannya. Semoga menjadi anak-anak yang shalehah.
iii
3. Bi Usi dan Nenek Awat yang selalu penulis repotkan, terima kasih atas doa, perhatian dan kasih sayangnya selama penulis tinggal ditempat beliau. 4. Dr. Djoko Suprijanto selaku dosen pembimbing atas bimbingan, perhatian, pengertian, dukungan, kesabaran, waktu, dan pengetahuan yang diberikan kepada penulis. 5. Dr. Oki Neswan. selaku dosen penguji seminar TA I dan seminar TA II atas masukan-masukan yang sangat berguna bagi penulis. 6. Drs. Warsoma Djohan M.Si selaku dosen penguji TA II atas kesediaan dan masukan-masukannya. 7. Dr. Udjianna S. Pasaribu selaku dosen wali yang telah memberikan perhatiannya kepada penulis selama menjadi mahasiswa Matematika ITB. 8. Seluruh dosen dan staf pengajar atas ilmu yang diberikan kepada penulis selama menjadi mahasiswa ITB. 9. Seluruh staf tata usaha dan perpustakaan program studi Matematika, khususnya Bu Diah atas segala bantuan dan dukungan selama penulis menjalani studi di Matematika ITB. 10. Devi Aprianti Rimadhani, yang selalu ada disaat suka dan duka, atas persahabatan yang terjalin sejak TPB. Semoga persahabatan ini tetap terjalin sampai ajal memisahkan kita nanti. 11. sahabat-sahabat senasib seperjuangan, KK Kombinatorik, teman berbagi suka dan duka dalam pengerjaan tugas akhir, Mustika Ladia P (MA’07), Ulima Azalia (MA’07), Riska Aditya P (MA’07), Afri Ariyadi(MA’07). 12. sahabat-sahabat tersayang, teman belajar dan berbagi pengetahuan, Dwi Endah W (MA’07), Novry Erwina (MA’07), Hafidzati Dini (MA’07), Dasep Purnama iv
(MA’07), Elvira kusniyanti (MA 07), Chandra Novtiar (MA’07), Dewi Handayani (MA’07), Nandia Primasari (MA’07), Nadia Indah (MA’07), Sandy Vantika (MA’07), Ina syafarina (MA’08) atas pinjaman buku-bukunya, Vina (MA’08), Falah (MA’08), Tanti Permatsari F, Laili Fajri, terimakasih atas segala bantuan dan dukungan yang begitu besar selama penulis menjalani studi di ITB. 13. sahabat-sahabat seatap, Cuti Artini (KI’07), Nuha Aina (FI’07), Fanny Aditya (KI’07), Vina Listiawati (BI’07), Intan Nurhidayatin (GL’07) atas segala bantuan dan dukungannya selama ini. 14. MA’07, KM3-ITB, HIMATIKA-ITB, KPA-ITB, KOKESMA-ITB, FKA KMITB, yang telah memberikan banyak sekali pelajaran dalam berorganisasi, bersosialisasi, pengalaman, serta persahabatan yang akan selalu penulis kenang. 15. Semua pihak yang tidak dapat disebutkan satu per-satu yang telah memberikan banyak bantuan dan dukungan dalam penyelesaian tugas akhir ini.
Penulis sangat menyadari bahwa tugas akhir yang penulis susun ini masih memiliki banyak kekurangan. Oleh karena itu saran dan kritik yang membangun sangat penulis harapkan agar penulis dapat memperbaiki kekurangan-kekurangan tersebut dan menghasilkan karya yang lebih baik lagi pada masa yang akan datang. Semoga karya tulis ini bermanfaat bagi para pembacanya.
Bandung, Juli 2011 Penulis
v
Daftar Isi
Abstrak
i
Abstract
ii
Prakata
iii
Daftar Isi
vii
Daftar Tabel
viii
1 Pendahuluan
1
2 Kode, GSR, dan Operasi Pada Graf
3
2.1
Ruang Vektor Atas F2 . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.1
Vektor Eigen dan Nilai Eigen . . . . . . . . . . . . . . . . . .
5
2.2
Kode atas F2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3
Bobot dan Jarak Kode . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3.1
Bobot Katakode dan Bobot Kode . . . . . . . . . . . . . . . .
6
2.3.2
Jarak antar Katakode dan Jarak Kode . . . . . . . . . . . . .
6
2.3.3
Hubungan Bobot dan Jarak . . . . . . . . . . . . . . . . . . .
6
2.3.4
Distribusi Bobot dan Pencacah Bobot . . . . . . . . . . . . .
7
2.4
Kode Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.5
Matriks Pembangkit . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
vi
2.6
Matriks Cek Paritas . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.7
Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.7.1
9
2.8
Graf Strongly regular . . . . . . . . . . . . . . . . . . . . . . .
Operasi-Operasi Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.8.1
Operasi gabungan (union) . . . . . . . . . . . . . . . . . . . . 10
2.8.2
Operasi jumlah (join) . . . . . . . . . . . . . . . . . . . . . . 11
2.8.3
Operasi kali(product) . . . . . . . . . . . . . . . . . . . . . . . 11
2.8.4
Line Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Konstruksi Kode
4
13
3.1
Kode Linier dari Graf Umum . . . . . . . . . . . . . . . . . . . . . . 13
3.2
Kode Linier dari Hasil Operasi Graf Strongly Regular . . . . . . . . . 15 3.2.1
Operasi gabungan (union) . . . . . . . . . . . . . . . . . . . . 15
3.2.2
Operasi jumlah (join) . . . . . . . . . . . . . . . . . . . . . . 16
3.2.3
Operasi kali (product) . . . . . . . . . . . . . . . . . . . . . . 17
3.2.4
Line Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.5
Line Graf pada Graf Bipartit Lengkap . . . . . . . . . . . . . 19
Kesimpulan
28
Daftar Pustaka
30
Lampiran
32
vii
Daftar Tabel 3.1
Kode dari GSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2
Kode dari operasi join . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3
Kode line graf
3.4
Kode tipe(2) dari line graf bipartit lengkap . . . . . . . . . . . . . . . 27
4.1
Pencacah bobot kode tipe (1) GSR . . . . . . . . . . . . . . . . . . . 35
4.2
Pencacah bobot kode tipe (2) GSR . . . . . . . . . . . . . . . . . . . 37
4.3
Pencacah bobot kode tipe (1) dari operasi join . . . . . . . . . . . . . 40
4.4
Pencacah bobot kode tipe(2) operasi join . . . . . . . . . . . . . . . . 42
4.5
Pencacah bobot kode line GSR tipe (1) . . . . . . . . . . . . . . . . . 43
4.6
Pencacah bobot kode line GSR tipe(2) . . . . . . . . . . . . . . . . . 46
4.7
Pencacah bobot kode line graf bipartit lengkap tipe(2) . . . . . . . . 47
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
viii
