Kode pendeteksian error kadang kala digunakan dalam
transmisi data. Misalnya, bila saturan simplex, maka transmisi ulang tidak bisa
diminta. Akan tetapi sering kali deteksi error yang diikuti oleh transmisi
ulang lebih disenangi. Hal ini disebabkan karena pemakaian transmisi ulang
lebih efisien. Sebagai sebuah contoh yang sederhana, ambil sebuah saluran yang
errornya terisolasi dan mempunyai laju error 10 –6 per bit.
Anggap ukuran blok sama dengan 1000 bit. Untuk
melaksanakan koreksi error blok 1000 bit, diperlukan 10 bit check; satu megabit
data akan membutuhkan 10.000 bit check. Untuk mendeteksi sebuah blok dengan
error tunggal 1-bit saja, sebuah bit parity per blok akan mencukupi. Sekali
setiap 1000 blok dan blok tambahan (1001) akan harus ditransmisikan. Overhead
total bagi deteksi error + metoda transmisi ulang adalah hanya 2001 bit per
megabit data, dibanding 10.000 bit bagi kode Hamming.
Bila sebuah bit parity tunggal ditambahkan ke
sebuah blok dan blok dirusak oleh error letupan yang lama, maka probabilitas error
dapat untuk bisa dideteksi adalah hanya 0,5 hal yang sangat sulit untuk bisa
diterma. Bit-bit ganjil dapat ditingkatkan cukup banyak dengan mempertimbangkan
setiap blok yang akan dikirim sebagai matriks persegi panjang dengan lebar n
bit dan tinggi k bit. Bit parity dihitung secara terpisah bagi setiap kolomnya
dan ditambahkan ke matriks sebagai baris terakhir. Kemudian matriks
ditransmisikan kembali baris per baris. Ketika blok tiba, penerima akan
memeriksa semua bit parity, Bila ada bit parity yang salah, penerima meminta
agar blok ditransmisi ulang.
Metoda ini dapat mendeteksi sebuah letupan dengan
panjang n, karena hanya 1 bit per kolom yang akan diubah. Sebuah letupan dengan
panjang n+1 akan lolos tanpa terdeteksi. Akan tetapi bila bit pertama diinversikan,
maka bit terakhir juga akan diinversikan, dan semua bit lainnya adalah benar.
(Sebuah error letupan tidak berarti bahwa semua bit salah; tetapi
mengindikasikan bahwa paling tidak bit pertama dan terakhirnya salah). Bila
blok mengalami kerusakan berat akibat terjadinya error letupan yang panjang
atau error letupan pendek yang banyak, maka probabilitas bahwa sembarang n
kolom akan mempunyai parity yang benar adalah 0,5. Sehingga probabilitas
dari blok yang buruk akan bisa diterima adalah 2 –n.
Walaupun metoda di atas kadang-kadang adekuat, pada
prakteknya terdapat metode lain yang luas digunakan: Kode polynomial (dikenal
juga sebagai cyclic redundancy code atau kode CRC). Kode polynomial didasarkan
pada perlakuan string-string bit sebagai representatsi polynomial dengan
memakai hanya koefisien 0 dan 1 saja. Sebuah frame k bit berkaitan dengan
daftar koefisien bagi polynomial yang mempunyai k suku, dengan range dari xk-1
sampai x0. Polynomial seperti itu disebut polynomial yang bertingkat
k-1. Bit dengan orde tertinggi (paling kiri) merupakan koefisien dari xk-1;
bit berikutnya merupakan koefisien dari xk-2, dan seterusnya.
Misalnya 110001 memiliki 6 bit, maka merepresentasikan polynomial bersuku 6
dengan koefisien 1,1,0,0,0 dan 1:x5+x4+x0.
Aritmetika polynomial dikerjakan dengan modulus 2,
mengikuti aturan teori aljabar. Tidak ada pengambilan untuk pertambahan dan
peminjaman untuk pengurangan. Pertambahan dan pengurangan identik dengan
EXCLUSIVE OR, misalnya :
Pertambahan
dengan EXOR
Pembagian juga diselesaikan dengan cara yang sama
seperti pada pembagian bilangan biner, kecuali pengurangan dikerjakan
berdasarkan modulus 2. Pembagi dikatakan “masuk ke” yang dibagi bila bilangan
yang dibagi mempunyai bit sebanyak bilangan pembagi.
Saat metode kode polynomial dipakai, pengirim dan
penerima harus setuju terlebih dahulu tentang polynomial generator, G(x). Baik
bit orde tinggi maupun bit orde rendah dari generator harus mempunyai harga 1.
Untuk menghitung checksum bagi beberapa frame dengan m bit, yang berkaitan
dengan polynomial M(x), maka frame harus lebih panjang dari polynomial
generator. Hal ini untuk menambahkan checksum
keakhir frame sedemikian rupa sehingga polynomial yang direpresentasikan
oleh frame berchecksum dapat habis dibagi oleh G(x). Ketika penerima memperoleh
frame berchecksum, penerima mencoba membaginya dengan G(x). Bila ternyata
terdapat sisa pembagian, maka dianggap telah terjadi error transmisi.
Algoritma untuk perhitungan checksum adalah sebagai
berikut :
1. Ambil r sebagai pangkat G(x), Tambahkan bit nol r
ke bagian orde rendah dari frame, sehingga sekarang berisi m+r bit dan
berkaitan dengan polynomial xrM(x).
2. Dengan menggunakan modulus 2, bagi string bit yang
berkaitan dengan G(x) menjadi string bit yang berhubungan dengan xrM(x).
3. Kurangkan sisa (yang selalu bernilai r bit atau
kurang) dari string bit yang berkaitan dengan xrM(x) dengan menggunakan
pengurangan bermodulus 2. Hasilnya merupakan frame berchecksum yang akan
ditransmisikan. Disebut polynomial T(x).
Perhitungan checksum kode polynomial
Gambar di atas menjelaskan proses
perhitungan untuk frame 1101011011 dan G(x) = x4 + x + 1.
Jelas bahwa T(x) habis dibagi (modulus 2) oleh G(x). Dalam sembarang
masalah pembagian, bila anda mengurangi angka yang dibagi dengan sisanya, maka
yang akan tersisa adalah angka yang
dapat habis dibagi oleh pembagi. Misalnya dalam basis 10, bila anda membagi
210.278 dengan 10.941, maka sisanya 2399. Dengan mengurangkan 2399 ke 210.278,
maka yang bilangan yang tersisa (207.879) habis dibagi oleh 10.941.
Sekarang kita menganalisis kekuatan metoda ini.
Error jenis apa yang akan bisa dideteksi ? Anggap terjadi error pada suatu
transmisi, sehingga bukannya string bit untuk T(x) yang tiba, akan tetapi T(x)
+ E(X). Setiap bit 1 pada E(x) berkaitan dengan bit yang telah diinversikan.
Bila terdapat k buah bit 1 pada E(x), maka k buah error bit tunggal telah
terjadi. Error tunggal letupan dikarakterisasi oleh sebuah awalan 1, campuran 0
dan 1, dan sebuah akhiran 1, dengan semua bit lainnya adalah 0.
Begitu frame berchecksum diterima, penerima
membaginya dengan G(x); yaitu, menghitung [T(x)+E(x)]/G(x). T(x)/G(x) sama
dengan 0, maka hasil perhitungannya adalah E(x)/G(x). Error seperti ini dapat
terjadi pada polynomial yang mengandung G(x) sebagai faktor yang akan mengalami
penyimpangan, seluruh error lainnya akan dapat dideteksi.
Bila terdapat error bit tunggal, E(x)=xi,
dimana i menentukan bit mana yang mengalami error. Bila G(x) terdiri dari dua
suku atau lebih, maka x tidak pernah dapat habis membagi E(x), sehingga seluruh
error dapat dideteksi.
Bila terdapat dua buah error bit-tunggal yang
terisolasi, E(x)=xi+xj, dimana i > j. Dapat juga
dituliskan sebagai E(x)=xj(xi-j + 1). Bila kita mengasumsikan
bahwa G(x) tidak dapat dibagi oleh x, kondisi yang diperlukan untuk dapat
mendeteksi semua error adalah bahwa G(x)
tidak dapat habis membagi xk+1 untuk sembarang harga k sampai
nilai maksimum i-j (yaitu sampai panjang frame maksimum). Terdapat polynomial
sederhana atau berorde rendah yang memberikan perlindungan bagi frame-frame
yang panjang. Misalnya, x15+x14+1 tidak akan habis
membagi xk+1 untuk sembarang harga k yang kurang dari 32.768.
Bila terdapat jumlah bit yang ganjil dalam error,
E(x) terdiri dari jumlah suku yang ganjil (misalnya,x5+x2+1,
dan bukannya x2+1). Sangat menarik, tidak terdapat polynomial yang
bersuku ganjil yang mempunyai x + 1 sebagai faktor dalam sistem modulus 2.
Dengan membuat x + 1 sebagai faktor G(x), kita akan mendeteksi semua error yang
terdiri dari bilangan ganjil dari bit yang diinversikan.
Untuk mengetahui bahwa polynomial yang bersuku
ganjil dapat habis dibagi oleh x+1, anggap bahwa E(x) mempunyai suku ganjil dan
dapat habis dibagi oleh x+1. Ubah bentuk E(x) menjadi (x+1)Q(x). Sekarang
evaluasi E(1) = (1+1)Q(1). Karena 1+1=0 (modulus 2), maka E(1) harus nol. Bila
E(x) mempunyai suku ganjil, pensubtitusian 1 untuk semua harga x akan selalu
menghasilkan 1. Jadi tidak ada polynomial bersuku ganjil yang habis dibagi oleh
x+1.
Terakhir, dan yang terpenting, kode polynomial
dengan r buah check bit akan mendeteksi semua error letupan yang memiliki
panjang <=r. Suatu error letupan dengan panjang k dapat dinyatakan oleh xi(xk-1
+ .....+1), dimana i menentukan sejauh mana dari sisi ujung kanan frame yang
diterima letupan itu ditemui. Bila G(x) mengandung suku x0, maka
G(x) tidak akan memiliki xi sebagai faktornya. Sehingga bila tingkat
ekspresi yang berada alam tanda kurung kurang dari tingkat G(x), sisa pembagian
tidak akan pernah berharga nol.
Bila panjang letupan adalah r+1, maka sisa
pembagian oleh G(x) akan nol bila dan hanya bila letupan tersebut identik
dengan G(x). Menurut definisi letupan, bit awal dan bit akhir harus 1, sehingga
apakah bit itu akan sesuai tergantung pada bit pertengahan r-1. Bila semua
kombinasi adalah sama dan sebanding, maka probabilitas frame yang tidak benar
yang akan diterima sebagai frame yang valid adalah ½ r-1.
Dapat juga dibuktikan bahwa bila letupan error yang
lebih panjang dari bit r+1 terjadi, maka probabilitas frame buruk untuk
melintasi tanpat peringatan adalah 1/2r yang menganggap bahwa semua
pola bit adalah sama dan sebanding.
Tiga buah
polynomial telah menjadi standard internasional:
§ CRC-12 =
X12 + X11 + X3 + X2 + X1
+ 1
§ CRC-16 =
X16 + X15 + X2 + 1
§ CRC-CCITT = X16
+ X12 + X5 + 1
Ketiganya mengandung x+1 sebagai faktor
prima.CRC-12 digunakan bila panjang
karakternya sama dengan 6 bit. Dua polynomial lainnya menggunakan karakter 8
bit. Sebuah checksum 16 bit seperti CRC-16 atau CRC-CCITT, mendeteksi semua
error tunggal dan error ganda, semua error dengan jumlah bit ganjil, semua
error letupan yang mempunyai panjang 16 atau kurang, 99,997 persen letupan
error 17 bit, dan 99,996 letupan 18 bit
atau lebih panjang.
Baca Juga :
