KONSTRUKSI KODE SWA-DUAL ATAS ℤ8 TUGAS AKHIR Diajukan untuk Memenuhi Persyaratan Sidang Sarjana Program Studi Matematika ITB
Oleh MUHAMMAD ARZAKI 10105068
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2009
KONSTRUKSI KODE SWA-DUAL ATAS Z8
TUGAS AKHIR Diajukan untuk Memenuhi Persyaratan Sidang Sarjana Program Studi Matematika ITB
Oleh: Muhammad Arzaki 10105068
Program Studi Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Bandung 2009
KONSTRUKSI KODE SWA-DUAL ATAS Z8
TUGAS AKHIR Diajukan untuk Memenuhi Persyaratan Sidang Sarjana Program Studi Matematika ITB
Oleh: Muhammad Arzaki 10105068
Telah diperiksa dan disetujui, Bandung, Agustus 2009 Dosen pembimbing
Dr. Djoko Suprijanto NIP. 132147117
Program Studi Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Bandung 2009
ii
Dan katakanlah, “Ya Tuhanku, masukkanlah aku secara masuk yang benar dan keluarkanlah (pula) aku secara keluar yang benar dan berikanlah kepadaku dari sisi Engkau kekuasaan yang menolong” (Q.S 17: 80)
Yesterday is history. Tomorrow is a mystery. But today is a gift. That is why it is called “the present”. (Master Oogway wise word, from Kung Fu Panda)
Untuk kedua orang tuaku serta semua orang dan kucing yang kusayangi
Abstrak Kode swa-dual linier merupakan salah satu jenis kode yang memiliki keunggulan dalam proses pendeteksian kesalahan. Keunggulan itu terletak pada matriks pemeriksa paritasnya yang sama dengan transpos dari matriks pembangkitnya. Kode linier atas Z8 merupakan salah satu contoh kode atas gelanggang hingga yang cukup penting. Kode ini memiliki keunggulan dalam sifat-sifat aljabar yang berguna dalam pengiriman kode serta pendeteksian dan pengoreksian kesalahan. Tugas akhir ini memperkenalkan dua buah metode sederhana untuk mengkonstruksi kode swa-dual baru dari kode swa-dual lama dengan cara memanipulasi matriks pembangkitnya. Kata kunci: kode linier, kode swa-dual, Z8 , matriks pembangkit, konstruksi kode.
iii
Abstract A linear-self dual code is one type of codes that has speciality on its error detection process. The speciality is the parity check matrix for any self dual codes is equal to the transpose of its generator matrix. A linear code over Z8 is one type of important codes over a …nite ring. The code has some speciality on its algebraic properties which are important for transmission, error detection, and error correction. This …nal project introduces two simple methods to construct new self dual codes from the old one by manipulating its generator matrix. Keywords: linear codes, self dual codes, Z8 , generator matrix, codes construction.
iv
Prakata Alhamdulillahirâbbilalãmin, segala puji penulis panjatkan hanya kepada Allâh SWT, karena hanya berkat karunia, kehendak, dan izin-Nyalah penulis dapat menyelesaikan tugas akhir ini. Shâlawat serta salam semoga tercurah kepada Nabi ¼ Muhammad SAW, yang sekiranya menjadi panutan hidup bagi setiap muslim sampai akhir zaman. Tugas akhir ini berjudul "Konstruksi Kode Swa-Dual atas Z8 ", penulis susun untuk memenuhi syarat kelulusan Sarjana Matematika di Institut Teknologi Bandung. Penulisan tugas akhir ini didasari oleh ketertarikan penulis terhadap ilmu teori informasi dalam matematika, dalam hal ini adalah teori pengodean informasi (teori koding). Salah satu dasar ilmu matematika yang sangat berhubungan erat dengan teori informasi adalah aljabar, sehingga penulis berharap agar mahasiswa S1 Matematika yang telah mempelajari Aljabar Linier maupun Aljabar Abstrak dapat memahami tugas akhir ini, meskipun belum pernah mempelajari teori pengodean informasi secara khusus. Dalam penulisan tugas akhir ini, penulis tidak terlepas dari berbagai pihak yang selama ini mendukung penulis untuk menyelesaikan pendidikan sarjana di ITB. Oleh karena itu penulis mengucapkan terima kasih kepada:
v
BAB 0. PRAKATA 1. Kedua orang tua penulis, M. Ari…n dan Dina Gayatri, atas segala bentuk dukungan mereka, baik dukungan …nansial, emosional maupun spiritual, serta segala pengalaman mereka ketika berkuliah di ITB (Teknik Perminyakan dan Teknik Kimia), yang sangat membantu penulis dalam menentukan sikap ketika berkuliah di ITB. 2. Pakde Wahyu dan Bude Poppy, serta Mbak Intan dan Mas Agni, yang telah bersedia untuk menampung penulis selama hari-hari kuliah di ITB sejak semester 4 sampai semester 8 dan atas berbagai jenis bantuan yang mereka berikan. 3. Dr. Djoko Suprijanto, selaku dosen pembimbing tugas akhir penulis, atas segala kesempatan, tenaga maupun ide yang membantu penulis dalam menyelesaikan tugas akhir ini. 4. Dr. Hilda Assiyatun dan Dr. Irawati, selaku dosen penguji penulis untuk seminar 1 dan 2, atas segala kesempatan, tenaga maupun saran yang membantu penulis dalam memperbaiki tugas akhir ini. 5. Drs. Hidayat Sardi MS., selaku dosen wali penulis selama kuliah di ITB sejak bulan Agustus 2005 sampai dengan bulan Juli 2009, atas segala jenis bantuan yang telah diberikannya kepada penulis. 6. Seluruh dosen Program Studi Matematika ITB dan pegawai Tata Usaha, terutama Ibu Diah yang telah membantu penulis dalam menyelesaikan berbagai masalah administrasi akademik selama kuliah di ITB.
vi
BAB 0. PRAKATA 7. Seluruh keluarga besar Dirdjojuwono, diantaranya Eyang Suprihatin, Eyang Mulyati Ari…n, dan Tante Erna, atas segala motivasi yang telah mereka berikan. 8. Semua teman di S1 Matematika ITB angkatan 2005, terutama Aditya P.S dan Gilang T.P, atas berbagai motivasi maupun saran yang telah mereka berikan kepada penulis dalam hal akademik maupun non-akademik. Meskipun terkadang mereka cukup menyebalkan. 9. Semua teman S1 Matematika ITB angkatan 2004, 2006, maupun 2007 yang telah membantu penulis dalam menempuh studi sarjana di ITB. 10. Semua teman di KM3 ITB, atas segala bentuk bantuan yang telah mereka berikan kepada penulis, baik dukungan emosional maupun spriritual, yang membantu penulis dalam menentukan jalan hidup yang terbaik. 11. Semua kawan HIMATIKA yang telah membantu penulis selama kuliah di ITB. 12. Semua teman yang telibat dalam pelatihan IMC dan ISOM tahun 2008 dan ONMIPA-PT tahun 2009. 13. Semua teman di Tim Indonesia untuk ISOM 2009, yaitu: Ahmad Agung A. (IT Telkom), Novi Murniati (UI), serta Ricky Aditya dan Hadrian Andradi (UGM). Serta Dr. Siti Fatimah (UPI) selaku team leader Indonesia. Penulis mengucapkan terima kasih atas segala motivasi, saran, dan nasihat yang telah mereka berikan. Penulis juga mengucapkan terima kasih kepada
vii
BAB 0. PRAKATA semua pihak yang telah membantu penulis selama mengikuti ISOM 2009, baik ketika di Indonesia maupun di Iran. 14. Seluruh jamaah shâlat isya di Masjid Al-Anshâr dan Masjid Darul Falah, atas segala dukungan spiritual yang mereka berikan. 15. Semua teman-teman penulis, baik teman SMP, SMA, maupun teman kuliah dari berbagai universitas yang telah membantu penulis selama kuliah di ITB. 16. Semua kucing yang telah menghibur penulis ketika sedang stress, diantaranya: Weisy, Blacky, Blendut, Onye’, Moncil, Tequl, dan Mollen. 17. Semua pihak lain yang tidak dapat penulis sebutkan yang telah memberi dukungan kepada penulis untuk dapat menyelesaikan pendidikan sarjana di ITB.
Akhirnya penulis menyadari bahwa tugas akhir ini tidaklah sempurna, karena kesempurnaan hanyalah milik-Nya. Oleh karena itu penulis memohon maaf atas segala kekurangan yang terdapat dalam tugas akhir ini. Penulis berharap agar tugas akhir ini dapat bermanfaat bagi setiap orang yang membacanya. Penulis bersedia menerima saran dan kritik yang membangun yang dapat menjadikan penulis lebih berkembang. Bandung, Agustus 2009
Muhammad Arzaki
viii
Daftar Isi
Halaman Pengesahan
i
Abstrak
iii
Abstract
iv
Prakata
v
Daftar Isi
xi
1 Pendahuluan
1
1.1 Aljabar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.1
Modul atas Zm . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.2
Kombinasi Linier, Bebas Linier, dan Basis . . . . . . . . .
2
1.1.3
Bebas Modular dan Basis Modular . . . . . . . . . . . . .
3
1.1.4
Matriks atas Zm
. . . . . . . . . . . . . . . . . . . . . . .
6
1.2 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.3 Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2 Kode atas Gelanggang Hingga
10
ix
DAFTAR ISI
DAFTAR ISI
2.1 De…nisi Kode dan Notasinya . . . . . . . . . . . . . . . . . . . . .
10
2.2 Bobot & Jarak . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.2.1
Bobot (Hamming) Katakode dan Kode . . . . . . . . . . .
11
2.2.2
Jarak (Hamming) antar Katakode dan Kode . . . . . . . .
11
2.2.3
Distribusi Bobot dan Pencacah Bobot . . . . . . . . . . .
12
2.3 Kode Ekivalen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.4 Kode Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.5 Matriks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.5.1
Matriks Pembangkit . . . . . . . . . . . . . . . . . . . . .
15
2.5.2
Matriks Pemeriksa Paritas . . . . . . . . . . . . . . . . . .
15
2.6 Kode Residu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.6.1
Pemetaan
dan
. . . . . . . . . . . . . . . . . . . . . .
17
2.6.2
Kode Residu . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3 Kode atas Z8
19
3.1 Matriks Pembangkit . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.2 Kode Swa-Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.2.1
Syarat Kode Swa-Dual atas Z8
. . . . . . . . . . . . . . .
20
3.2.2
Eksistensi Kode Swa-Dual atas Z8 . . . . . . . . . . . . . .
21
4 Konstruksi
27
4.1 Konstruksi Kode Non Bebas . . . . . . . . . . . . . . . . . . . . .
27
4.2 Konstruksi Kode Bebas . . . . . . . . . . . . . . . . . . . . . . . .
31
4.3 Hasil Konstruksi . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4.3.1
Kode Swa-Dual Non Bebas dengan Panjang 10 . . . . . . . x
34
Daftar Isi
Daftar Isi 4.3.2
Kode Swa-Dual Bebas dengan Panjang 16 . . . . . . . . .
37
5 Kesimpulan
39
Daftar Pustaka
40
xi
