1 1.1
PENDAHULUAN
Latar Belakang
Media informasi, seperti sistem komunikasi dan media penyimpanan untuk data, tidak sepenuhnya reliabel. Hal ini dikarenakan bahwa pada praktiknya ada gangguan (noise) atau inferensi lainnya sehingga pesan yang dikirim berubah (terdapat galat pada pesan). Salah satu masalah dalam teori koding (coding theory) adalah untuk mendeteksi atau bahkan mengoreksi galat tersebut. Artikel tentang masalah tersebut pertama kali ditulis oleh C. E. Shannon pada tahun 1948 dalam artikelnya yang berjudul A Mathematical Theory of Communication. Masalah itu dapat digambarkan sebagai berikut. Apabila suatu pesan (informasi) dikirim melalui saluran terganggu (noisy channel), sering kali terjadi bahwa pesan yang diterima tidak sama dengan yang dikirim, misalnya pesan yang berupa gambar atau suara menjadi tidak jelas. Di dalam komunikasi, pesan direpresentasikan dalam bentuk digital sebagai blok (barisan) simbol, sering kali digunakan simbol biner yang dikenal dengan bitstring. Saluran biasanya berupa jaringan telepon, jaringan radio berfrekuensi tinggi atau jaringan komunikasi satelit. Saluran yang terganggu menyebabkan berubahnya beberapa simbol yang dikirim, sehingga mengurangi kualitas informasi yang diterima. Suatu kode (code) diciptakan untuk mendeteksi atau mengoreksi galat (error) akibat saluran terganggu. Dalam hal ini sebelum dikirim, semua pesan akan diubah menjadi kata kode (codeword) dengan cara menambahkan beberapa simbol ekstra pada simbol pesan. Proses pengubahan pesan menjadi kata kode disebut enkoding. Perangkat yang mengubah pesan menjadi kata kode disebut Enkoder. Kode merupakan himpunan yang anggotanya kata kode. Pendefinisian kode ini dilakukan sedemikian sehingga apabila terjadinya perubahan beberapa simbol pada kata kode, maka galat itu bisa dipulihkan lagi oleh dekoder. Dekoder merupakan perangkat yang mengubah barisan simbol yang diterima menjadi kata kode. Suatu model komunikasi dapat digambarkan seperti pada Gambar 1, dan untuk contohnya dapat dilihat pada Gambar 2.
2
sumber pesan
mesin penerima
enkoder sumber
dekoder sumber
enkoder saluran
saluran
dekoder saluran
gangguan
Gambar 1. Proses koding untuk suatu pesan.
Apel
Apel
00
00
00000
channel
01000
gangguan
Gambar 2. Contoh enkoding dan dekoding dari suatu pesan.
Ilustrasi tentang source coding dan channel coding akan dijelaskan pada paragraf berikut ini. Source coding terdiri dterdiri atasari dua bagian, yaitu source encoding dan source decoding. Source encoding meliputi perubahan pesan asal (message source) menjadi kode yang bersesuaian sehingga dapat dikirimkan melalui suatu saluran/jalur data, sedangkan source decoding meliputi perubahan kode yang dikirimkan menjadi pesan asal. Kode ASCII adalah salah satu contoh source coding yang mengubah setiap karakter menjadi suatu “byte” yang terdiri atas delapan bit. Sebagai contoh, misalkan source encoding untuk empat jenis buah-buahan didefinisikan sebagai berikut. •
Apel = 00
•
Pisang = 01
•
Ceri = 10
•
Anggur = 11
3
Misalkan pula pesan “Apel”, yang dikodekan sebagai “00” akan dikirimkan melalui noisy channel (jalur bergangguan). Pesan tersebut dapat saja menyimpang/ berubah dan diterima sebagai “10”. Dalam kasus ini, mesin penerima tidak dapat mendeteksi kesalahan tersebut, sehingga komunikasi tersebut gagal (lihat Gambar 3).
Apel
00
Pisang
channel
01
gangguan
Gambar 3. Contoh informasi yang gagal terkirim.
Pesan yang telah dikodekan oleh source encoder dapat saja berubah jika melalui noisy channel. Ide dari channel coding adalah untuk mendeteksi kesalahan tersebut dengan cara men-enkode lagi pesan yang akan dikirimkan dengan cara menambahkan unsur redundansi/unsur ekstra sehingga kesalahan tersebut dapat dideteksi atau bahkan dikoreksi. Untuk mengilustrasikan channel encoding, misalkan ditambahkan satu bit data redundansi pada contoh sebelumnya sebagai berikut. •
00 = 000
•
01 = 011
•
11 = 110
Misalkan pula pesan “apel” yang dikodekan sebagai “000” (setelah dilakukan source dan channel encoding) dikirimkan melalui saluran yang terganggu (noise) memiliki kesalahan satu bit, sehingga pesan yang diterima dapat berubah menjadi “001”, 010”, atau “100”. Dalam kasus ini, kesalahan dapat dideteksi karena tidak ada satupun dari “001”, “010”, dan “100” yang merupakan pesan awal. Untuk contoh di atas, kesalahan pesan dapat dideteksi dengan kompensasi kecepatan transfer, karena untuk mengirim pesan berukuran dua bit, perlu ditransmisikan kata kode berukuran tiga bit. Walaupun kesalahan pada pesan dapat dideteksi, mesin
4
penerima tidak dapat memperbaiki kesalahan tersebut, karena jika yang diterima adalah “100”. Ada kemungkinan kata kode tersebut berasal dari “000”, “110”, atau “101”. Namun, dengan ditambahkan lagi unsur redundansi, kesalahan tersebut dapat dikoreksi. Sebagai contoh, dapat didesain skema koding sebagai berikut. •
00 = 00000
•
01 = 01111
•
10 = 10110
•
11 = 11001
Untuk dapat membandingkan dengan contoh sebelumnya, misalkan pesan “apel” akan dikirimkan melalui sinyal terganggu dan hanya terjadi satu bit kesalahan. Dengan demikian, pesan yang diterima adalah salah satu dari lima kemungkinan berikut: “10000”, “01000”, “00100”, “00010”, atau “00001”. Misalkan yang sampai adalah “10000”, mesin penerima akan dapat mengambil kesimpulan bahwa pesan tersebut berasal dari “0000”, karena kesalahan yang terjadi hanya satu bit, sehingga tidak mungkin pesan tersebut berasal dari “01111”, “10110”, dan “11001”. Namun, dengan skema seperti ini, lebih banyak waktu yang terbuang. Secara umum, tujuan dari teori koding adalah untuk mengonstruksi suatu kode (enkoder dan dekoder) sehingga 1. dapat meng-enkode suatu pesan dengan cepat, 2. dapat mentransmisi pesan yang sudah di-enkode dengan mudah, 3. dapat men-dekode suatu pesan yang diterima dengan cepat, 4. dapat memaksimumkan informasi yang ditransfer per satuan waktu, dan 5. dapat secara maksimal dalam mendeteksi dan mengoreksi kesalahan. 1.2
Tujuan Penelitian
Berdasarkan latar belakang yang dipaparkan di atas, maka tujuan dari penelitian ini adalah: 1. Mengkaji teorema yang terkait dengan konstruksi kode linear, terutama Gilbert-Vashamov bound. 2. Menyusun algoritme-algoritme untuk mengontruksi kode linear biner.
5
3. Mengimplementasikan algoritme-algoritme tersebut dalam suatu bahasa pemograman dan mengujicobakan untuk kode linear dengan jarak minimum 9 dan 11. Dari tujuan-tujuan tersebut, penelitian ini diharapkan dapat memberikan suatu hal yang baru dalam teori koding, yaitu memperbaiki batas bawah dari Tabel Brouwer.