Konstruksi Kode Swa-Dual MDS atau near MDS Hermitian atas GF(9)
TUGAS AKHIR Diajukan untuk Memenuhi Persyaratan Kelulusan Program Studi Sarjana Matematika Institut Teknologi Bandung
Oleh : Mustika Ladia Putri NIM : 10107037
Pembimbing : Dr. Djoko Suprijanto
PROGRAM STUDI SARJANA MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2011
Konstruksi Kode Swa-Dual MDS atau near MDS Hermitian atas GF(9)
TUGAS AKHIR Diajukan untuk Memenuhi Persyaratan Kelulusan Program Studi Sarjana Matematika Institut Teknologi Bandung
Oleh : Mustika Ladia Putri 10107037
Telah diperiksa dan disetujui Bandung, Juni 2011 Pembimbing Tugas Akhir
Dr. Djoko Suprijanto NIP. 132147117
PROGRAM STUDI SARJANA MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2011
”Bekerjalah kamu, maka Allah dan Rasul-Nya serta orang-orang mukmin akan melihat pekerjaanmu itu, dan kamu akan dikembalikan kepada (Allah) Yang Mengetahui akan yang gaib dan yang nyata, lalu diberitahukan-Nya kepada kamu apa yang telah kamu kerjakan (At Taubah: 105)”
Dalam lelah langkah, kau slalu di sisiku Dalam keterpurukan, kau slalu tegarkanku Dalam lubuk hatimu, tak henti harapmu untukku Dalam setiap doamu, tak henti kau sebut namaku Dan inilah wujud dari harap dan doamu Kupersembahkan ini hanya untukmu Ibunda dan Ayahanda tercinta Serta keluargaku yang slalu ada untukku Terima kasih
Konstruksi Kode Swa-Dual MDS atau near MDS Hermitian atas GF(9)
Abstrak Kode swa-dual MDS Hermitian memiliki keunggulan dalam proses pendeteksian dan pengoreksian kesalahan. Salah satu keunggulan kode swa-dual adalah memiliki matriks pemeriksa paritas yang merupakan transpos dari matriks pembangunnya. Sedangkan keunggulan dari kode MDS adalah kode ini memiliki jarak kode terbesar dibandingkan dengan kode lainnya yang memiliki panjang dan dimensi yang sama. Kode near MDS dan kode MDS memiliki selisih jarak kode terkecil dibandingkan dengan selisih jarak antara kode MDS dan kode lainnya, sehingga kode near MDS memiliki kemampuan yang hampir sama baiknya dengan kode MDS. Kode swadual Hermitian atas GF (q) merupakan kode swa-dual yang didefinisikan dengan mengunakan hasil kali dalam Hermitian pada ruang vektor GF (q)n . Konstruksi kode swa-dual Hermitian atas lapangan hingga dengan orde kecil seperti GF (2), GF (3), atau GF (4) sudah banyak menarik perhatian para peneliti sejak teori koding lahir. Hal ini berbeda dengan konstruksi kode swa-dual atas lapangan hingga dengan orde besar seperti GF (9). Oleh karena itu, pada tugas akhir ini, akan dikonstruksi kode swa-dual Hermitian yang baru atas GF (9) dengan panjang 12, sehingga diperoleh 9 kode swa-dual near MDS Hermitian yang baru atas GF (9) dengan panjang 12. Kata kunci: kode MDS, kode swa-dual, GF (9), kode swa-dual Hermitian.
i
Abstract Hermitian self-dual MDS codes have speciality in detection and correction errors. MDS codes have the greatest minimum distance compare to the other codes with the same length and dimension. Near MDS and MDS codes have the smallest difference of minimum distance compare to difference of minimum weight between MDS and other codes. It implies the capability of near MDS codes in detecting and correcting errors are almost the same with MDS codes. Hermitian self-dual codes over GF (q) are self-dual codes that define using Hermitian inner product over vector space GF (q)n . Many scientists have been interested in construction of Hermitian self-dual codes over small finite fields such as GF (2), GF (3), or GF (4) since long time ago. It is different with construction of Hermitian self-dual codes over large finite fields such as GF (9). In this final project, we constructed new Hermitian self-dual codes over GF (9) of length 12 and we obtained 9 new Hermitian self-dual near MDS codes over GF (9) of length 12. Keywords: MDS codes, self-dual codes, GF (9), Hermitian self-dual codes.
ii
Prakata Bismillaahirrohmaanirrohiim. Alhamdulillah. Segala puji bagi Allah SWT Tuhan semesta alam yang maha pemberi kekuatan dan pertolongan bagi hamba-hambanya. Hanya karena izin-Nya penulis dapat menyelesaikan tugas akhir yang berjudul ”Konstruksi Kode Swa-Dual MDS atau near MDS Hermitian atas GF(9)” tepat pada waktunya. Shalawat serta salam semoga terlimpah kepada junjungan Nabi besar Muhammad SAW beserta keluarganya dan seluruh insan manusia yang dikehendaki-Nya. Tugas akhir ini diajukan sebagai salah satu syarat kelulusan pada Program Studi Sarjana Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Teknologi Bandung. Selama pengerjaan tugas akhir ini, banyak pihak yang secara langsung maupun tidak langsung turut membantu penulis. Oleh karena itu, penulis ingin menyampaikan terimakasih kepada: 1. Kedua orangtua tercinta, Ibu Emi Sumiati dan Bapak Drs. E. Hapidi Iyossaputra, atas jasa-jasanya yang tak kenal lelah dalam membesarkan, mendidik, memberi motivasi, dan selalu mengingatkan penulis untuk selalu mengingat Allah SWT. 2. Bapak Dr. Djoko Suprijanto selaku dosen pembimbing yang selalu membimbing dan memotivasi penulis. 3. Bapak Dr. Oki Neswan selaku dosen penguji seminar TA I yang telah memberikan masukan yang membangun. 4. Bapak Prof. Dr. Edy Tri Baskoro dan Ibu Dr. Hanni Garminia selaku dosen penguji seminar TA II yang memberikan banyak masukan dalam penulisan. 5. Ibu Dr. Muchtadi Intan Detiena selaku dosen wali yang telah memberikan berbagai masukan dan perhatiannya kepada penulis selama menjadi mahasiswa di Matematika ITB. iii
6. Kakak-kakak tercinta Yoga Fitriansyah, S.Kom., Yudha Ruliansyah, S.Si., R. Dewi Lestari, S.T., dan Nadia Novianti, S.Kom. untuk dukungan doa, dukungan materi, semangat, dan motivasi tanpa putus. 7. Keponakan-keponakan tersayang Defian Nazwansyah dan Hilal Abiyu Yaqhdan Ruliansyah yang telah menghibur penulis saat penulis mengalami masamasa jenuh dan kehilangan semangat untuk menyelesaikan tugas akhir ini. 8. Ibu Diah atas segala bantuan, dukungan, dan motivasi selama penulis menjalani studi di Matematika ITB. 9. Bapak Dr. Janson Naiborhu yang telah mempercayakan penulis untuk menjadi asisten dosen dan melengkapi pengalaman hidup penulis. 10. Seluruh dosen, staf pengajar, dan staf tata usaha program studi Mate- matika untuk ilmu yang diberikan serta bantuannya selama penulis menjalani studi di ITB. 11. Eka Ismaya Fauzi yang telah memberi motivasi dan bantuan secara teknis kepada penulis dalam menyelesaikan tugas akhir ini. 12. Teman-teman seperjuangan yang telah membantu secara teknis dan motivasi, Epi Okti Sari, Ferawati Magdalena, Ruth Fergie Panggabean, dan Made Rai Laksmi W., serta teman-teman seangkatan Matematika 2007. 13. Teman-teman satu bimbingan, Ulima Azalia, Ranny Rachmaniar, dan Afri Ariyadi atas bantuan, kritik dan saran yang membangun. 14. Semua pihak yang tidak dapat disebutkan satu per-satu yang telah memberikan bantuan materi, moril, dll yang mendukung selesainya pengerjaan tugas akhir ini. Penulis sangat menyadari bahwa tugas akhir yang penulis susun ini masih memiliki banyak kekurangan baik secara konsep maupun teknis. Oleh karena itu penulis sangat mengharapkan masukan dan kritik yang membangun agar penulis dapat memperbaiki kekurangan-kekurangan tersebut dan menghasilkan karya yang lebih baik pada masa yang akan datang.
Bandung, Juni 2011 Penulis iv
Daftar Isi Abstrak
i
Abstract
ii
Prakata
iii
Daftar Isi
vi
1 Pendahuluan
1
2 Lapangan Hingga dan Kode Linier 2.1 Lapangan Hingga . . . . . . . . . . . . . 2.1.1 Lapangan . . . . . . . . . . . . . 2.1.2 Suku Banyak . . . . . . . . . . . 2.1.3 Unsur Primitif . . . . . . . . . . 2.1.4 Konstruksi GF (pm ) . . . . . . . . 2.1.5 Operasi Penjumlahan di GF (pm ) 2.1.6 Operasi Perkalian di GF (pm ) . . 2.2 Kode Linier atas GF (q) . . . . . . . . . 2.2.1 Kode Linier . . . . . . . . . . . . 2.2.2 Kode Ekivalen . . . . . . . . . . . 2.3 Bobot dan Jarak (Hamming) Kode . . . 2.4 Kode Dual . . . . . . . . . . . . . . . . . 2.5 Maximum Distance Separable (MDS) . . 2.6 Matriks . . . . . . . . . . . . . . . . . . 2.6.1 Matriks Pembangun . . . . . . . 2.6.2 Matriks Pemeriksa Paritas . . . . 3
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
4 4 4 5 6 6 8 9 10 10 10 11 14 16 17 17 17
Metode Konstruksi Jon-Lark Kim untuk Kode Swa-Dual Hermitian 19 v
3.1 3.2 3.3 4
5
Kontruksi Kode [2n, n] menjadi [2n + 2, n + 1] . . . . . . . . . . . . . 19 Konstruksi Kode [2n, n] menjadi [2n − 2, n − 1] . . . . . . . . . . . . 21 Konstruksi Kode Swa-Dual Hermitian dengan Dua Kali Iterasi . . . . 22
Hasil Konstruksi Kode Swa-Dual Hermitian 25 4.1 Kode Swa-Dual C[10, 5, 5] . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2 Kode Swa-Dual C[12, 6, 6] . . . . . . . . . . . . . . . . . . . . . . . . 26 Kesimpulan
28
Daftar Pustaka
29
Lampiran A
30
Lampiran B
39
vi
