Para perancang jaringan
telah membuat dua strategi dasar yang berkenaan dengan error. Cara pertama
adalah dengan melibatkan informasi redundansi secukupnya bersama-sama dengan
setiap blok data yang dikirimkan untuk memungkinkan penerima menarik kesimpulan
tentang apa karakter yang ditransmisikan yang seharusnya ada. Cara lainnya
adalah dengan hanya melibatkan redundansi secukupnya untuk menarik kesimpulan
bahwa suatu error telah terjadi, dan membiarkannya untuk meminta pengiriman
ulang. Strategi pertama menggunakan kode-kode pengkoreksian error
(error-correcting codes), sedangkan strategi kedua menggunakan kode-kode
pendeteksian error (error-detecting codes).
Untuk bisa mengerti
tentang penanganan error, kita perlu melihat dari dekat tentang apa yang
disebut error itu. Biasanya, sebuah frame terdiri dari m bit data (yaitu pesan)
dan r redundan, atau check bits. Ambil panjang total sebesar n (yaitu, n=m+r).
Sebuah satuan n-bit yang berisi data dan checkbit sering kali dikaitkan sebagai
codeword n-bit.
Ditentukan dua buah
codeword: 10001001 dan 10110001. Disini kita dapat menentukan berapa banyak bit
yang berkaitan berbeda. Dalam hal ini, terdapat 3 bit yang berlainan. Untuk
menentukannya cukup melakukan operasi EXCLUSIVE OR pada kedua codeword, dan
menghitung jumlah bit 1 pada hasil operasi. Jumlah posisi bit dimana dua
codeword berbeda disebut jarak Hamming (Hamming, 1950). Hal yang perlu
diperhatikan adalah bahwa bila dua codeword terpisah dengan jarak Hamming d,
maka akan diperlukan error bit tunggal d untuk mengkonversi dari yang satu
menjadi yang lainnya.
Pada sebagian besar
aplikasi transmisi data, seluruh 2m pesan data merupakan data yang
legal. Tetapi sehubungan dengan cara penghitungan check bit, tidak semua 2n
digunakan. Bila ditentukan algoritma untuk menghitung check bit, maka akan
dimungkinkan untuk membuat daftar lengkap codeword yang legal. Dari daftar ini
dapat dicari dua codeword yang jarak Hamming-nya minimum. Jarak ini merupakan
jarak Hamming bagi kode yang lengkap.
Sifat-sifat pendeteksian
error dan perbaikan error suatu kode tergantung pada jarak Hamming-nya. Untuk
mendeteksi d error, anda membutuhkan kode dengan jarak d+1 karena dengan kode
seperti itu tidak mungkin bahwa error bit tunggal d dapat mengubah sebuah
codeword yang valid menjadi codeword valid lainnya. Ketika penerima melihat
codeword yang tidak valid, maka penerima dapat berkata bahwa telah terjadi
error pada transmisi. Demikian juga, untuk memperbaiki error d, anda memerlukan
kode yang berjarak 2d+1 karena hal itu menyatakan codeword legal dapat terpisah
bahkan dengan perubahan d, codeword orisinil akan lebih dekat dibanding
codeword lainnya, maka perbaikan error dapat ditentukan secara unik.
Sebagai sebuah contoh
sederhana bagi kode pendeteksian error, ambil sebuah kode dimana parity bit
tunggal ditambahkan ke data. Parity bit dipilih supaya jumlah bit-bit 1 dalam
codeword menjadi genap (atau ganjil). Misalnya, bila 10110101 dikirimkan dalam
parity genap dengan menambahkan sebuah bit pada bagian ujungnya, maka data itu
menjadi 101101011, sedangkan dengan parity genap 10110001 menjadi 101100010.
Sebuah kode dengan parity bit tunggal mempunyai jarak 2, karena sembarang error
bit tunggal menghasilkan sebuah codeword dengan parity yang salah. Cara ini
dapat digunakan untuk mendeteksi erro-error tunggal.
Sebagai contoh sederhana
dari kode perbaikan error, ambil sebuah kode yang hanya memiliki empat buah
codeword valid :
0000000000,0000011111,1111100000
dan 1111111111
Kode ini mempunyai jarak
5, yang berarti bahwa code tersebut dapat memperbaiki error ganda. Bila
codeword 0000011111 tiba, maka penerima akan tahun bahwa data orisinil
seharusnya adalah 0000011111. Akan tetapi bila error tripel mengubah 0000000000
menjadi 0000000111, maka error tidak
akan dapat diperbaiki.
Bayangkan bahwa kita akan
merancang kode dengan m bit pesan dan r bit check yang akan memungkinkan semua
error tunggal bisa diperbaiki. Masing-masing dari 2m pesan yang
legal membutuhkan pola bit n+1. Karena jumlah total pola bit adalah 2n,
kita harus memiliki (n+1)2m £ 2n.
Dengan memakai n = m + r,
persyaratan ini menjadi (m + r + 1)£2r. Bila m
ditentukan, maka ini akan meletakkan batas bawah pada jumlah bit check yang
diperlukan untuk mengkoreksi error tunggal.
Dalam kenyataannya, batas bawah teoritis ini dapat diperoleh dengan
menggunakan metoda Hamming (1950). Bit-bit codeword dinomori secara berurutan, diawali dengan bit
1 pada sisi paling kiri. Bit bit yang merupakan pangkat 2 (1,2,4,8,16 dan
seterusnya) adalah bit check. Sisanya (3,5,6,7,9 dan seterusnya) disisipi
dengan m bit data. Setiap bit check memaksa parity sebagian kumpulan bit,
termasuk dirinya sendiri, menjadi genap
(atau ganjil). Sebuah bit dapat dimasukkan dalam beberapa komputasi parity.
Untuk mengetahui bit check dimana bit data pada posisi k berkontribusi, tulis
ulang k sebagai jumlahan pangkat 2. Misalnya, 11=1+2+8 dan 29=1+4+8+16. Sebuah
bit dicek oleh bit check yang terjadi pada ekspansinya (misalnya, bit 11 dicek
oleh bit 1,2 dan 8).
Ketika sebuah codeword tiba, penerima menginisialisasi counter ke nol.
Kemudian codeword memeriksa setiap bit check, k (k=1,2,4,8,....) untuk melihat apakah
bit check tersebut mempunyai parity yang benar. Bila tidak, codeword akan
menambahkan k ke counter. Bila counter sama dengan nol setelah semua bit check
diuji (yaitu, bila semua bit checknya benar), codeword akan diterima sebagai
valid. Bila counter tidak sama dengan nol, maka pesan mengandung sejumlah bit
yang tidak benar. Misalnya bila bit check 1,2, dan 8 mengalami kesalahan
(error), maka bit inversinya adalah 11, karena itu hanya satu-satunya yang
diperiksa oleh bit 1,2, dan 8. Gambar berikut ini menggambarkan beberapa
karakter ASCII 7-bit yang diencode sebagai codeword 11 bit dengan menggunakan
kode Hamming. Perlu diingat bahwa data terdapat pada posisi bit
3,5,6,7,9,10,11.
Kode Hamming hanya bisa memperbaiki error tunggal. Akan tetapi, ada
trick yang dapat digunakan untuk memungkinkan kode Hamming dapat memperbaiki
error yang meletup. Sejumlah k buah codeword yang berurutan disusun sebagai
sebuah matriks, satu codeword per baris. Biasanya, data akan ditransmisikan
satu baris codeword sekali, dari kiri ke kanan. Untuk mengkoreksi error yang
meletup, data harus ditransmisikan satu kolom sekali, diawali dengan kolom yang
paling kiri. Ketika seluruh k bit telah dikirimkan, kolom kedua mulai
dikirimkan, dan seterusnya. Pada saat frame tiba pada penerima, matriks
direkonstruksi, satu kolom per satuan waktu. Bila suatu error yang meletup
terjadi, paling banyak 1 bit pada setiap k codeword akan terpengaruh. Akan
tetapi kode Hamming dapat memperbaiki satu error per codeword, sehingga seluruh
blok dapat diperbaiki. Metode ini memakai kr bit check untuk membuat km bit
data dapat immune terhadap error tunggal yang meletup dengan panjang k atau
kurang.
Baca Juga :
