PENDEKODEAN KODE LINEAR BINER DENGAN PERBAlKAN SATU KESALAHAN
ANSUFRI ID SAMBO
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU DAN PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 1997
RINGKASAN ANSUFRI ID SAMBO. Pendekodcan Kode Linear Biner dengan Pcrbaikan Salu Kesalahan (Decoding Binary Linear Code with Single Error-Correcting). Dibimbing oleh NUR ALIATININGTYAS, FARIDA HANUM dan SUGl GURITMAN. Saat ini banyak orang mcnggunakan jasa telegram untuk mengirim pesan dari suatu tempat ke tempat yang lain. Pcsan itu sebenarnya tidak Iangsung dikirim dalam bahasa aslinya melainkan terlebih dahulu diubah ke dalam benluk kode (rangkaian angka-angka). Hal ini digunakan unluk memudahkan dalam mcmeriksa kesalahan yang terjadi pacta pengiriman pesan tersebut. Pada tulisan ini kade yang digunakan adalah kode biner (rangkaian angka 0 dan I). Tulisan ini bertujuan unluk mel~elaskan prinsip dasar dalam memeriksa dan membetulkan kesalahan yang te/jadi dalam pengiriman pesan. Prinsip dasar tersebut adalah sebagai berikut : jika diasumsikan kata yang diterima memiliki kesalahan maka kata kode yang memiliki jarak terdekat dengan kata tersebut adalah kata kode yang dikirim. Prinsip tersebut dikenal sebagai "prinsip pendekodean dengan tetangga terdekat" (nearest neighbour decoding principle). Misalkan In merupakan jarak minimum antara kata kode-kata kode dalam sualu kode maka kode tersebut dapat memeriksa m-l kesalahan atau kurang dan dapat membetulkan (m-l)/2 kesalahan atau kurang. Menurut prinsip di alas ada tiga cara untuk melakukan pendekodean kala yang dikirim. Pertama, dengan cara menghitung jarak minimum antara kata yang dilerima dengan seluruh kata kode. Kedua, dengan earn mendaftarkan semua kala dalam himpunan biner ke dalam tabel larik standar, Cara ini lebih baik daripada cara pertama. Keliga, dengan cara mendaftarkan seluruh kepala koset dari tabel larik standar dan vektor sindromnya. Cara ini adalah yang paling mudah dan efisien.
PENDEKODEAN KODE LINEAR BINER DENGAN PERBAlKAN SATU KESALAHAN
ANSUFRI ID SAMBO
Skripsi Sebagai salah satu syarat uutuk memperoleh gelar Sarjana Sains pada Program Studi Matematika
JURUSAN MA TEMATIKA FAKULTAS MATEMATIKA DAN ILMU DAN PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR
1997
J udul Nama NIM
Pcndckodean Kode Linear Biner dengan Perbaikan Satu Kesalahan Ansufri Id Sambo G26.0985
Menyelujui.
Dra. Nur Alialininglyas. MS.
Dra. Farida Hanulll. MS.
Pembimbing I
Pembimbillg II
Tanggal Lulus: 24 Mei 1997.
Judul
Nama NIM
Pendekodean Kode Linear Biner dengan Perbaikan Satu Kesalahan Ansufri Id Sambo G26.0985
Menyetujui,
Dra. Nur Alialininglyas , MSi.
Dra. Farida Hallum) MSi.
Pembimbing I
Pembimbing II
Mcngetalmi.
Dr. If. D.S. Priyarsono, MS. Kelua Program Sludi
Tanggal Lulus : 24 Mei 1997.
RIWAYATHIDUP
Penulis dilahirkan di Medan pada tanggal 20 Nopember 1970 sebagai anak keempat dari enam bersalldara, anak dari pasangan Muhammad Idms Sambo dan Anizar Ja'far. Talmn 1989 penulis lui us dari SMA KHALSA Medan dan pada tahun yang sarna lusus seleksi rnasuk Institut Pertanian Bogor rnelalui jalur Undangan Seleksi Masuk IPB (USMI). Pada tahun 1990 penulis rnernilih Program Studi Maternatika, Jumsan Matematika, Fakultas Maternatika dan Ilrnu Pengetahuan Alam, yang ketika itu bam membuka program untuk sarjana. Selama mengikuti perkuliahan penulis menjadi asisten mata kuliah Pengantar Maternatika pada tahun ajaran 1990/1991. Pada tahun 1993 sampai sekarang penulis membuka sanggar belajar dan konsultasi mabasiswa Instillll Perlanian Bogor khuSllS tingkat persiapan bersama (TPB) yang bernama AIJabar.
PRAKATA
Segala puji dan syukur penulis panjatkan ke hadiral Allah SWT alas ralnnal, hidayah dan berkahNya sehingga tulisan ini berhasil diselesaikan. Tema yang dipilih dalam penulisan karya ilmiah ini adalah leori pengkodean, dengan judul Pendekodcan Kode Linear Biner dengan Pemeriksaan Salu Kesalahan. Penulis mengucapkan lerima kasih yang lak tcrhingga kepada berbagai pihak yang telah banyak membanlu penyelesaian karya ilmiah ini, antara lain Ibu Dra. Nur Aliatinigtyas, MS. dan Ibu Dra. Farida Hanum, MS. selaku doscn pembimbing, dan Bapak Ir. Fahren Bukhari, MSc. selaku dosen pcnguji, serta Bapak Dr. Ir. D.S. Priyarsono, MS. selaku ketua Jumsan Matematika, Fakultas Matematika dan Ilmu Pengetalman Alam. Di sam ping itu penulis juga mengucapkan terima kasih kepada rekan-rekan di AI-Jabar yang juga telah membantu penulis. Tak lupa ungkapan terima kasih yang dalam disampaikan kepada Ibunda, Ayahanda, Ananda AI-Hasanah, Istri, serta selumh keluarga, atas segala doa, dorongan dan kasih-sayangnya. Penulis tak dapat membalas segala kebaikan mercka semua, semoga Allah SWT membalas scgala kcbaikan mercka dcngan yang lebih baik.
Semoga karya ilmiah ini bermanfaat.
Bogor, Mei 1997 AnsuJr; ld Sambo
DAFTARISI Ralaman DAFTAR GAMBAR ......... '" ................................................................................. vi PENDAHULUAN ................................................................................................................. 1 Latar Belakang ......... ... ... ... ........ ... ... ..... ..... ... ... ........... ............... ..... ..... ... ........ ... ........... .... I Tujuan ............................................................................................................................. 1 LANDASAN TEORl ............................................................................................................ Gmp ................................................................................................................................ Sub Gmp ......................................................................................................................... Partisi dan Rubungan Ekivalensi ...................................................................................... Koset dan Teorellla Lagrange .............................................................. '" ............... '.. ... ....
1 1 2 2 3
GRUP BINER ............................................... '" ....................................... '" ... ... ... ... ... ... ... ..... 4 PRlNSIP PENDEKODEAN ....................................................................... '" ... ... ... ... ... ... ... .... 5 Kode, Kata Kode, Jarak, dan Bobot .. ................................................ ............................. 5 Pemeriksaan dan Pembetulan Kesalahan ..................... "............... ,................................. 7 K'ODE LINEAR ......................................................................................................... '" ... ... Kode Linear ................................................................................ .. . ... .. . ... .. . .. . .. . .. . ... .. . ..... Kode Linear dengan Matriks Keseilllbangan .............. ................... ... ... ... ... ... ... ... ... ... ... .... Pendekodean Kata yang Dikirilll .. .................. .................... ........... ... ... ... ... ... ... ... ... ... ... ...
8 8 9 10
PENDEKODEAN DENGAN KOSET ....................................................................................... Koset Kode Linear .............................................................................................. .. .. . .. . ... .. . ... Pendekodean dengan Tabel Larik Standar ........ .......... .............. .................... .......... ... ... ... .... Pendekodean dengan Vektor Sindrolll .................................................................................
11 II II 12
KESIMPULAN DAN SARAN ............................................................................................ ..... Kesimpulan ........................................................................................................................ Saran ......................................................................................................................... ...... ...
14 14 14
DAFTARPUSTAKA................................................................................................................
14
DAFTAR GAMBAR Halaman 1. Proses pengiriluan pesan ........ ,....... ,.............. ,............................................. ,....................... ,.. 1 2. Proses pengkodean, pengiriman, dan pendekodean pesan .. ....... ..... ............ ...... .... ...... .......... ... I 3. Dua kata kode dengan jarak minimum m = 2e + I ................... .......... ............................ ...... .... 8
I
PENDAHULUAN Latar Bclakang
Kemajuan dunia saat ini ditandai dengan berkembangnya teknologi telekomunikasi. Manusia bebas berkomunikasi atau mengirim pesan dari suatu tempat ke lcmpal yang lain. Pengiriman pesan ini melalui media perantara yang dinamakan channel. Channel tersebut bisa berupa jalur telepon, frekuensi radio, salelit komunikasi, kaset atau disket. Dalam pengiriman pesan mungkin teljadi gangguan-gangguan pada channel sehingga pesan yang diterima berbeda dengan pesan yang dikirim. Jika leljadi kesalahan Imka pencrima pesan dapat meminla agar pemberi pesan mengnlangi kembali pengiriman pesan. Tetapi kadangkala pengiriman kembali tidak memungkinkan seperti pengiriman gambar dari luar angkasa, pembacaan pada kaset atau disket. gangguan
....
Gall1bar 1. Proses pengiriman pesal1 Sebagai contah pcsan dikirim dalum bahasa aslinya scpcrti llSaya datang II dan pes3n yang diterima adalah "Saya dateng". Melihal hal in;, penerima dapat mengetahui bahwa telah terjadi kesalahan pengiriman. Akan telapi jika pesan yang diterima adalah "Maya datang ll atau IISaya dalang" maka penerima tidak dapat memuluskan apakah telah terjadi kesalahan atau tidak. Unlttk mengalasi hal di alas, pengiriman pesan tidak di'dalam bahasa aslinya telapi terlebih dahulu diubah (dikodekan) ke dalam bentuk vektor biner (unlaian biiangan biner 0 dan I). Pengubahan ke dalam vektor biner ini dinamakan pcngkodcan (encoding). Sedangkan pengubahan kembali dari vektor biner ke pesan yang berbahasa asli dinamakan pcndcl
,
tahu bahwa telah tetjadi kesalaban pengiriman. Kemudian dia akan memutuskan bahwa pesan yang dikirim adalah 00000 atau "ya". pcngirim pcsan
ya
~
gangguan pengkode yn ~ 00000 tdk~lllll
~ ~-
00110 pcndckode _ _~001l0. 00000 =yn
Gambar 2. Proses pengkodean, pengiriman, dan pendekodean pesan Dasar-
LANDASAN TEOR! Sebelum membahas teori pengkoderul lebih lanju!, terlebih dallUlu dibahas hal-hal yang menunjang Illasalah tersebut. Adapun haJ-hal tersebut adalaJl teori tentang grup, sub grup, partisi, kose!, ctrul Teorema Lagrange. GI1IJl
Definis; 1. Suatu operasi biner yang dilrunbangkilll dengan '*' clalrun suatu himpunan A adalaJl sualu aluran yang mengkombinasikan 2 unsur dalrull A yang menghasilkan salu dan !tanya satu unsurdiA. Definisi di atas dapat dilulis dengan cara lain yaitu : jika a,b eA Imka ada satu dan hanya satu CE A sedemikian sehingga a*b = c. Contoh 1. Operasi penjullliahan (+) dan perkalian (.) merupakrul operasi biner pada himpwIan
