Pesan yang belum dikodekan dapat tersusun atas huruf atau karakter, tetapi biasanya terdiri atas tupel-\(m\) biner. Pesan-pesan ini dikodekan menjadi kata kode, yang terdiri atas tupel-\(n\) biner, oleh perangkat yang disebut pengode. Pesan tersebut ditransmisikan, lalu didekode. Kita akan mempertimbangkan terjadinya kesalahan selama transmisi. Kesalahan terjadi jika terdapat perubahan pada satu atau lebih bit dalam kata kode. Skema pendekodean adalah metode yang mengubah sebarang tupel-\(n\) yang diterima menjadi pesan bermakna yang telah didekode atau memberikan pesan kesalahan untuk tupel-\(n\) tersebut. Jika pesan yang diterima merupakan kata kode (salah satu tupel-\(n\) khusus yang diizinkan untuk ditransmisikan), maka pesan yang didekode harus merupakan pesan tunggal yang dikodekan menjadi kata kode tersebut. Untuk kata bukan-kode yang diterima, skema pendekodean akan memberikan tanda kesalahan, atau, jika dirancang dengan lebih cermat, benar-benar mencoba mengoreksi kesalahan dan merekonstruksi pesan semula. Tujuan kita adalah mentransmisikan pesan bebas kesalahan semurah dan secepat mungkin.
Salah satu skema pengodean yang mungkin adalah mengirimkan pesan beberapa kali dan membandingkan salinan-salinan yang diterima. Andaikan pesan yang hendak dikodekan adalah tupel-\(n\) biner \((x_{1}, x_{2}, \ldots,
x_{n})\text{.}\) Pesan tersebut dikodekan menjadi tupel-\(3n\) biner dengan mengulang pesan itu tiga kali:
Untuk mendekode pesan, sebagai digit ke-\(i\) kita memilih digit yang muncul pada posisi ke-\(i\) dalam sedikitnya dua dari tiga transmisi. Sebagai contoh, jika pesan semula adalah \((\codeword{0110})\text{,}\) maka pesan yang ditransmisikan adalah \((\codeword{0110}\; \codeword{0110}\; \codeword{0110})\text{.}\) Jika terjadi kesalahan transmisi pada digit kelima, kata kode yang diterima adalah \((\codeword{0110}\; \codeword{1110}\; \codeword{0110})\text{,}\) yang akan didekode dengan benar sebagai \((\codeword{0110})\text{.}\) 1
Kita akan menggunakan konvensi bahwa bit dalam tupel-\(n\) biner dinomori dari kiri ke kanan.
Metode pengulangan tiga kali ini secara otomatis mendeteksi dan mengoreksi semua kesalahan tunggal, tetapi metode tersebut lambat dan tidak efisien: untuk mengirimkan pesan yang terdiri atas \(n\) bit, diperlukan \(2n\) bit tambahan, dan kita hanya dapat mendeteksi serta mengoreksi kesalahan tunggal. Kita akan melihat bahwa dapat ditemukan skema pengodean yang mengodekan pesan \(n\) bit menjadi \(m\) bit dengan \(m\) jauh lebih kecil daripada \(3n\text{.}\)
Paritas genap, suatu skema pengodean yang umum digunakan, jauh lebih efisien daripada skema pengulangan sederhana. Sistem pengodean ASCII (American Standard Code for Information Interchange) menggunakan tupel-\(8\) biner, yang menghasilkan \(2^{8} = 256\) kemungkinan tupel-\(8\text{.}\) Namun, hanya diperlukan tujuh bit karena hanya terdapat \(2^7 = 128\) karakter ASCII. Apa yang dapat atau seharusnya dilakukan dengan bit tambahan tersebut? Dengan menggunakan kedelapan bit sepenuhnya, kita dapat mendeteksi kesalahan transmisi tunggal. Sebagai contoh, kode ASCII untuk A, B, dan C adalah
Bit tersebut dapat digunakan untuk memeriksa kesalahan pada tujuh bit lainnya. Bit itu ditetapkan sebagai \(0\) atau \(1\) agar jumlah keseluruhan bit \(1\) dalam representasi suatu karakter genap. Dengan menggunakan paritas genap, kode untuk A, B, dan C kini menjadi
Andaikan A dikirimkan dan derau pada saluran komunikasi menyebabkan kesalahan transmisi pada bit keenam sehingga \((\codeword{0100}\; \codeword{0101})\) diterima. Kita mengetahui bahwa telah terjadi kesalahan karena kata yang diterima mempunyai jumlah bit \(1\) yang ganjil, dan kini kita dapat meminta agar kata kode ditransmisikan kembali. Ketika digunakan untuk memeriksa kesalahan, bit paling kiri disebut bit pemeriksa paritas.
Kode pendeteksi kesalahan yang paling umum digunakan dalam komputer sejauh ini didasarkan pada penambahan bit paritas. Biasanya, komputer menyimpan informasi dalam tupel-\(m\) yang disebut kata. Panjang kata yang umum adalah \(8\text{,}\)\(16\text{,}\) dan \(32\) bit. Satu bit dalam kata dicadangkan sebagai bit pemeriksa paritas dan tidak digunakan untuk menyimpan informasi. Bit ini ditetapkan sebagai \(0\) atau \(1\text{,}\) bergantung pada banyaknya bit \(1\) dalam kata tersebut.
Penambahan bit pemeriksa paritas memungkinkan pendeteksian semua kesalahan tunggal karena perubahan satu bit akan menambah atau mengurangi banyaknya bit \(1\) sebanyak satu, dan dalam kedua kasus paritas berubah dari genap menjadi ganjil, sehingga kata baru tersebut bukan kata kode. (Kita juga dapat menyusun skema pendeteksian kesalahan berdasarkan paritas ganjil; yaitu, kita dapat menetapkan bit pemeriksa paritas sedemikian sehingga kata kode selalu mempunyai jumlah bit \(1\) yang ganjil.)
Sistem paritas genap mudah diimplementasikan, tetapi mempunyai dua kelemahan. Pertama, kesalahan jamak tidak dapat dideteksi. Andaikan A dikirimkan dan bit pertama serta ketujuh diubah dari \(0\) menjadi \(1\text{.}\) Kata yang diterima merupakan kata kode, tetapi akan didekode menjadi C, bukan A. Kedua, kita tidak mempunyai kemampuan untuk mengoreksi kesalahan. Jika tupel-8 \((\codeword{1001}\; \codeword{1000})\) diterima, kita mengetahui bahwa telah terjadi kesalahan, tetapi tidak mengetahui bit mana yang telah berubah. Sekarang kita akan menyelidiki skema pengodean yang tidak hanya memungkinkan pendeteksian kesalahan transmisi, tetapi benar-benar mengoreksinya.
Andaikan pesan semula adalah \(0\) atau \(1\text{,}\) dan \(0\) dikodekan menjadi \((\codeword{000})\text{,}\) sedangkan \(1\) dikodekan menjadi \((\codeword{111})\text{.}\) Jika hanya terjadi satu kesalahan selama transmisi, kita dapat mendeteksi dan mengoreksi kesalahan tersebut. Sebagai contoh, jika \((\codeword{101})\) diterima, bit kedua pastilah telah berubah dari \(1\) menjadi \(0\text{.}\) Kata kode yang semula ditransmisikan pastilah \((\codeword{111})\text{.}\) Metode ini akan mendeteksi dan mengoreksi semua kesalahan tunggal.
Dalam Tabel 8.1.5, kita menyajikan semua kemungkinan kata yang dapat diterima untuk kata kode \((\codeword{000})\) dan \((\codeword{111})\) yang ditransmisikan. Tabel 8.1.5 juga menunjukkan banyaknya bit yang membedakan setiap tupel-\(3\) yang diterima dari setiap kata kode semula.
Skema pengodean yang disajikan dalam Contoh 8.1.4 belum merupakan penyelesaian lengkap karena tidak memperhitungkan kemungkinan terjadinya kesalahan jamak. Sebagai contoh, \((\codeword{000})\) ataupun \((\codeword{111})\) dapat dikirimkan dan \((\codeword{001})\) diterima. Dari kata yang diterima, kita tidak dapat menentukan apakah terjadi satu kesalahan pada bit ketiga atau dua kesalahan, masing-masing pada bit pertama dan kedua. Apa pun skema pengodean yang digunakan, pesan yang salah dapat diterima. Kita dapat mentransmisikan \((\codeword{000})\text{,}\) mengalami kesalahan pada ketiga bit, lalu menerima kata kode \((\codeword{111})\text{.}\) Penting untuk menyatakan secara eksplisit asumsi tentang kemungkinan dan distribusi kesalahan transmisi agar, dalam penerapan tertentu, dapat diketahui apakah suatu skema pendeteksian kesalahan sesuai. Kita akan mengasumsikan bahwa kesalahan transmisi jarang terjadi dan, ketika terjadi, kesalahan pada setiap bit saling bebas; yaitu, jika \(p\) adalah probabilitas kesalahan pada satu bit dan \(q\) adalah probabilitas kesalahan pada bit lain, maka probabilitas terjadinya kesalahan pada kedua bit tersebut secara bersamaan adalah \(pq\text{.}\) Kita juga akan mengasumsikan bahwa tupel-\(n\) yang diterima didekode menjadi kata kode yang paling dekat dengannya; yaitu, kita mengasumsikan bahwa penerima menggunakan pendekodean kemungkinan maksimum. 2
Bagian ini memerlukan pengetahuan tentang probabilitas, tetapi dapat dilewati tanpa mengganggu kesinambungan pembahasan.
Saluran simetris biner adalah model yang terdiri atas pemancar yang mampu mengirimkan sinyal biner, yakni \(0\) atau \(1\text{,}\) bersama sebuah penerima. Misalkan \(p\) adalah probabilitas bahwa sinyal diterima dengan benar. Maka \(q = 1 - p\) adalah probabilitas penerimaan yang salah. Jika \(1\) dikirimkan, probabilitas diterimanya \(1\) adalah \(p\) dan probabilitas diterimanya \(0\) adalah \(q\) (Gambar 8.1.6). Probabilitas tidak terjadinya kesalahan selama transmisi kata kode biner dengan panjang \(n\) adalah \(p^{n}\text{.}\) Sebagai contoh, jika \(p=0.999\) dan pesan yang terdiri atas 10.000 bit dikirimkan, probabilitas transmisi sempurna adalah
Jika tupel-\(n\) biner \((x_{1}, \ldots,
x_{n})\) ditransmisikan melalui saluran simetris biner dengan probabilitas \(p\) bahwa tidak terjadi kesalahan pada setiap koordinat, maka probabilitas terjadinya kesalahan pada tepat \(k\) koordinat adalah
Tetapkan \(k\) koordinat yang berbeda. Mula-mula kita menghitung probabilitas terjadinya kesalahan pada himpunan koordinat tetap ini. Probabilitas terjadinya kesalahan pada salah satu koordinat tertentu dari \(k\) koordinat tersebut adalah \(q\text{;}\) probabilitas tidak terjadinya kesalahan pada setiap koordinat dari \(n-k\) koordinat yang tersisa adalah \(p\text{.}\) Probabilitas masing-masing dari \(n\) kejadian saling bebas ini adalah \(q^{k}p^{n-k}\text{.}\) Banyaknya pola kesalahan yang mungkin dengan tepat \(k\) kesalahan adalah
yaitu banyaknya kombinasi \(n\) objek yang diambil \(k\) sekaligus. Setiap pola kesalahan ini mempunyai probabilitas \(q^{k}p^{n-k}\) untuk terjadi; dengan demikian, probabilitas seluruh pola kesalahan tersebut adalah
Untuk mengembangkan kode pendeteksi dan pengoreksi kesalahan yang efisien, kita memerlukan perangkat matematika yang lebih canggih. Teori grup memungkinkan metode pengodean dan pendekodean pesan yang lebih cepat. Suatu kode adalah \((n, m)\)-kode blok jika informasi yang hendak dikodekan dapat dibagi menjadi blok-blok berisi \(m\) digit biner, yang masing-masing dapat dikodekan menjadi \(n\) digit biner. Secara lebih khusus, kode blok-\((n, m)\) terdiri atas fungsi pengodean
Kata kode adalah sebarang unsur dalam citra \(E\text{.}\) Kita juga mensyaratkan agar \(E\) bersifat satu-ke-satu sehingga dua blok informasi tidak dikodekan menjadi kata kode yang sama. Jika kode kita hendak mengoreksi kesalahan, maka \(D\) harus bersifat pada.
Sistem pengodean paritas genap yang dikembangkan untuk mendeteksi kesalahan tunggal pada karakter ASCII merupakan kode blok-\((8,7)\text{.}\) Fungsi pengodeannya adalah
Misalkan \({\mathbf x} = (x_1, \ldots,
x_n)\) dan \({\mathbf y} = (y_1, \ldots,
y_n)\) adalah tupel-\(n\) biner. Jarak Hamming atau jarak, \(d({\mathbf x}, {\mathbf y})\text{,}\) antara \({\mathbf x}\) dan \({\mathbf y}\) adalah banyaknya bit tempat \({\mathbf x}\) dan \({\mathbf y}\) berbeda. Jarak antara dua kata kode adalah jumlah minimum kesalahan transmisi yang diperlukan untuk mengubah satu kata kode menjadi kata kode lainnya. Jarak minimum suatu kode, \(d_{\min}\text{,}\) adalah nilai minimum dari semua jarak \(d({\mathbf x}, {\mathbf y})\text{,}\) dengan \({\mathbf x}\) dan \({\mathbf y}\) merupakan kata kode yang berbeda. Bobot, \(w({\mathbf x})\text{,}\) dari suatu kata kode biner \({\mathbf x}\) adalah banyaknya bit \(1\) dalam \({\mathbf x}\text{.}\) Jelas bahwa \(w({\mathbf x}) = d({\mathbf x}, {\mathbf 0})\text{,}\) dengan \({\mathbf 0} = (\codeword{00 \cdots 0})\text{.}\)
Misalkan \({\mathbf x} = (\codeword{10101})\text{,}\)\({\mathbf y} = (\codeword{11010})\text{,}\) dan \({\mathbf z} = (\codeword{00011})\) merupakan semua kata kode dalam suatu kode \(C\text{.}\) Maka kita memperoleh jarak Hamming berikut:
Bobot dalam suatu kode biasanya jauh lebih mudah dihitung daripada jarak Hamming antara semua kata kode dalam kode tersebut. Jika kode disusun dengan cermat, fakta ini dapat kita manfaatkan.
Andaikan \({\mathbf x} = (\codeword{1101})\) dan \({\mathbf y} = (\codeword{1100})\) merupakan kata kode dalam suatu kode. Jika kita mentransmisikan \((\codeword{1101})\) dan terjadi kesalahan pada bit paling kanan, maka \((\codeword{1100})\) akan diterima. Karena \((\codeword{1100})\) merupakan kata kode, pendekode akan mendekode \((\codeword{1100})\) sebagai pesan yang ditransmisikan. Kode ini jelas kurang sesuai untuk mendeteksi kesalahan. Masalahnya adalah \(d({\mathbf x}, {\mathbf y}) = 1\text{.}\) Jika \({\mathbf x} = (\codeword{1100})\) dan \({\mathbf y} = (\codeword{1010})\) merupakan kata kode, maka \(d({\mathbf x}, {\mathbf y}) = 2\text{.}\) Jika \({\mathbf x}\) ditransmisikan dan terjadi satu kesalahan, maka \({\mathbf y}\) tidak mungkin diterima. Tabel 8.1.12 memberikan jarak antara semua kata kode 4 bit dengan tiga bit pertama membawa informasi dan bit keempat merupakan bit pemeriksa paritas genap. Kita dapat melihat bahwa jarak minimum di sini adalah \(2\text{;}\) oleh karena itu, kode tersebut sesuai sebagai kode pendeteksi kesalahan tunggal.
Untuk menentukan secara tepat kemampuan suatu kode dalam mendeteksi dan mengoreksi kesalahan, kita perlu menganalisis jarak minimum kode tersebut. Misalkan \({\mathbf x}\) dan \({\mathbf y}\) merupakan kata kode. Jika \(d({\mathbf x}, {\mathbf y}) = 1\) dan terjadi kesalahan pada posisi tempat \({\mathbf x}\) dan \({\mathbf y}\) berbeda, maka \({\mathbf x}\) berubah menjadi \({\mathbf y}\text{.}\) Kata kode yang diterima adalah \({\mathbf y}\) dan tidak diberikan pesan kesalahan. Sekarang andaikan \(d({\mathbf x}, {\mathbf y}) = 2\text{.}\) Maka satu kesalahan tidak dapat mengubah \({\mathbf x}\) menjadi \({\mathbf y}\text{.}\) Oleh karena itu, jika \(d_{\min} = 2\text{,}\) kita mampu mendeteksi kesalahan tunggal. Namun, andaikan \(d({\mathbf x}, {\mathbf y}) = 2\text{,}\)\({\mathbf y}\) dikirimkan, dan suatu kata bukan-kode \({\mathbf z}\) diterima sedemikian sehingga
Maka pendekode tidak dapat memilih antara \({\mathbf x}\) dan \({\mathbf y}\text{.}\) Meskipun mengetahui bahwa telah terjadi kesalahan, kita tidak mengetahui kesalahan tersebut.
Andaikan \(d_{\min} \geq 3\text{.}\) Maka skema pendekodean kemungkinan maksimum mengoreksi semua kesalahan tunggal. Berawal dari kata kode \({\mathbf x}\text{,}\) kesalahan dalam transmisi satu bit menghasilkan \({\mathbf y}\) dengan \(d({\mathbf x}, {\mathbf y}) = 1\text{,}\) tetapi \(d({\mathbf z}, {\mathbf y}) \geq 2\) untuk setiap kata kode lain \({\mathbf z} \neq {\mathbf x}\text{.}\) Jika kita tidak mensyaratkan pengoreksian kesalahan, kita dapat mendeteksi kesalahan jamak ketika kode mempunyai jarak minimum yang lebih besar dari atau sama dengan \(3\text{.}\)
Misalkan \(C\) suatu kode dengan \(d_{\min} = 2n + 1\text{.}\) Maka \(C\) dapat mengoreksi sebarang \(n\) kesalahan atau kurang. Selanjutnya, sebarang \(2n\) kesalahan atau kurang dapat dideteksi dalam \(C\text{.}\)
Andaikan kata kode \({\mathbf x}\) dikirimkan dan kata \({\mathbf y}\) diterima dengan paling banyak \(n\) kesalahan. Maka \(d( {\mathbf x}, {\mathbf y}) \leq n\text{.}\) Jika \({\mathbf z}\) adalah sebarang kata kode selain \({\mathbf x}\text{,}\) maka
Dengan demikian, \(d({\mathbf y}, {\mathbf z} ) \geq n+1\) dan \({\mathbf y}\) akan didekode dengan benar sebagai \({\mathbf x}\text{.}\) Sekarang andaikan \({\mathbf x}\) ditransmisikan dan \({\mathbf y}\) diterima serta sedikitnya satu kesalahan telah terjadi, tetapi tidak lebih dari \(2n\) kesalahan. Maka \(1 \leq d( {\mathbf x}, {\mathbf y} ) \leq 2n\text{.}\) Karena jarak minimum antara kata kode adalah \(2n +1\text{,}\)\({\mathbf y}\) tidak mungkin merupakan kata kode. Akibatnya, kode tersebut dapat mendeteksi antara \(1\) dan \(2n\) kesalahan.
Teori pengodean modern dimulai pada tahun 1948 melalui makalah C. Shannon, “A Mathematical Theory of Information” [7]. Makalah ini memberikan contoh kode aljabar, dan Teorema Shannon menyatakan secara tepat seberapa baik kode yang dapat diharapkan. Richard Hamming mulai meneliti kode linear di Bell Labs pada akhir 1940-an dan awal 1950-an setelah merasa frustrasi karena program yang dijalankannya tidak dapat pulih dari kesalahan sederhana yang ditimbulkan oleh derau. Teori pengodean telah berkembang pesat selama beberapa dasawarsa terakhir. The Theory of Error-Correcting Codes, karya MacWilliams dan Sloane [5], yang diterbitkan pada tahun 1977, telah memuat lebih dari 1.500 referensi. Kode linear (kode blok Reed-Muller \((32, 6)\)) digunakan pada wahana antariksa Mariner milik NASA. Wahana antariksa yang lebih baru, seperti Voyager, menggunakan apa yang disebut kode konvolusi. Saat ini, penelitian yang sangat aktif dilakukan terhadap kode Goppa, yang sangat bergantung pada geometri aljabar.
