Error Detection

Error Detection

Dalam proses pengiriman data, sering kali terjadi kesalahan atau error pada bit-bit frame yang dikirimkan. Sehingga menyebabkan data yang dikirim mengalami perubahan, kerusakan, hilang, atau terduplikasi. Perlu dilakukan pengecekan terhadap data untuk mendeteksi adanya error.

Tipe error ada 2 kemungkinan yaitu :

- Random error : Jika hanya terjadi perubahan satu bit data yang dikirimkan

- Burst error : Jika terjadi perubahan dua atau lebih bit data yang dikirimkan

Terdapat beberapa jenis metode error checking, diantaranya :

1.      Parity Check

Adalah metode deteksi error yang dilakukan dengan menambahkan sebuah ‘parity’ bit pada setiap paket data, sehingga dapat dideteksi valid tidaknya suatu paket data.

Metode parity bit ini terbagi menjadi dua jenis yakni :

• Even Parity

Biasa digunakan dalam transmisi data secara asynchronous. Sebelum paket data dikirim, setiap paket data di cek apakah jumlah ‘1’ berjumlah ganjil atau genap, jika paket data berjumlah genap maka bit parity akan tetap 0 sedangkan jika jumlah ‘1’ ganjil maka bit parity akan menjadi 1 sehingga jumlah bit menjadi genap. Proses penghitungan ini menggunakan XOR gate.

• Odd parity

Biasa digunakan dalam transmisi data secara synchronous. Sebelum paket data dikirim, setiap paket data di cek apakah jumlah ‘1’ berjumlah ganjil atau genap, jika paket data berjumlah genap maka bit parity akan menjadi 1 sehingga jumlah bit ‘1’ menjadi ganjil  sedangkan jika jumlah ‘1’ sudah ganjil maka bit parity akan tetap menjadi 0.

Kelebihan dari metode parity check :

• Mudah direalisasikan dalam bentuk rangkaian/hardware
• Analisis dan penggunaan system cukup sederhana

Kekurangan dari metode parity check :

• Kemungkinan kesalahan yang terjadi cukup besar, yaitu 50%
• Kurang handal dalam mengatasi deteksi dan perbaikan error
• Jumlah bit yang terdeteksi terbatas : 1-3 bit errors.

2.      Checksum

Metode ini merupakan proses yang relative mudak dilaksanakan, dimana pengirim harus menjumlahkan bilangan-bilangan bulat biner yang membentuk data untuk menghasilkan suatu nilai jumlah (sum).  Biasa diterapkan  utnuk data yang terdiri dari bilangan-bilangan, gambar, karakter, dan bilangan floating point. Metode ini mirip dengan parity check, perbedaannya adalah jumlah bit pada sums lebih besar dan hasil dari penjumlahan data dengan checksum harus selalu dibuat nol.

Di sisi pengirim:

-          Unit data dibagi ke dalam k seksi yang masing-masing seksi berisi n-bit data.

-          Semua seksi data tersebut ditambahkan menggunakan 1’s complement untuk mendapatkan jumlahnya.

-          Jumlah tersebut kemudian dikomplemenkan dan menjadi nilai checksum.

-          Checksum dikirim bersama dengan data sebagai unit terakhir dalam paket pengiriman.

Di sisi penerima:

-          Unit data yang diterima kembali dibagi ke dalam k seksi yang masing-masing seksi berisi b-bit data.

-          Semua seksi unit data tersebut dijumlahkan menggunakan 1’s complement untuk mendapatkan jumlahnya.

-          Jumlah tersebut kemudian dikomplemenkan.

-          Jika hasilnya adalah nol, maka data diterima; jika tidak, data akan ditolak.

Kelebihan dari metode Checksum :

• Mudah diimplemantasikan dalam software
• Memiliki kehadalan sistem yang cukup tinggi, yaitu sekitar 90%.

Kekurangan dari metode Checksum :

• Kehandalan sistem deteksi error yang masih lemah (walaupun lebih handal dibanding parity check) karena tidak dapat mendeteksi unit data (bytes/words) yang urutannya berantakan, tidak dapat mendeteksi unit data mana yang mengalami kesalahan.

3.      CRC – Cyclic Redundancy Check

CRC adalah metode error checking yang beroperasi pada sebuah frame/block. Setiap block berukuran m bit yang akan dikirim dihitung CRC checksumnya (berukuran r bit), kemudian dikirim bersama dengan frame (dengan ukuran m+r bit). Penerima akan menghitung CRC checksum pada frame yang diterima, dan dibandingkan dengan checksum yang diterima, jika berbeda, berarti frame rusak.

CRC menggunakan prinsip modulo bilangan. Data dianggap sebagai sebuah bilangan, dan untuk menghitung checksum, sama dengan menambahkan digit untuk data dengan digit untuk checksum (berisi 0) kemudian dibagi dengan pembilang tertentu, dan sisa pembagiannya menjadi checksum untuk data tersebut. Tergantung pemilihan bilangan pembagi, CRC dapat mendeteksi single-bit error, double bit error, error berjumlah ganjil, burst error dengan panjang maksimum r. Bilangan pembagi tersebut disebut sebagai generator (polinomial).

Pada CRC ini, generator pembagi data ini sering disebut generator polinomial karena nilai pembagi ini dapat direpresentasikan dalam bentuk polinomial peubah banyak, tergantung pada jenis atau nilai pembagi yang digunakan. Gambar berikut menjelaskan konsep tersebut.

Kelebihan dari metode CRC :

• Mampu mendeteksi bit error dalam jumlah banyak (burst error) dengan panjang yang kurang dari jumlah redundansi bitnya.
• Dapat digunakan dalam pengiriman data berkecepatan tinggi (16-32 bit).
• Memiliki kehadalan sistem yang sangat tinggi, yaitu sekitar 99%.

Kekurangan dari metode CRC :

• Analisis dan perhitungan dalam perancangan yang cukup sulit.
• Realisasi rangkaian/hardware dan software yang paling sulit dibanding parity check dan checksum.

4.      Hamming Code

Hamming code merupakan sistem yang dikembangkan dari error correction code yang mengunakan parity bit. Linear error-correction code memiliki berbagai keterbatasan kesalahan. Pada Hamming Code, kesalahan yang dapat diketahui hanya 1 ( satu ) buah sedangkan yang dapat dideteksi adalah 2 ( dua ) buah.

Konsep Dasar Kode Hamming adalah dengan menggunakan bit pariti untuk disisipkan pada posisi tertentu dalam blok data, dengan demikian memungkinkan untuk dapat digunakan dalam pemeriksaan kesalahan dalam blok data. Aturan untuk menyatakan bit Hamming adalah melalui pendekatan 2n, nilai n dan n adalah bilangan bulat positif.

Cara untuk menentukan bit Hamming adalah sebagai berikut:

·         Data = 1011 → penyisipan bit Hamming adalah 101x1xx

·         Nilai x dapat dipilih 1 atau 0 dan disisipkan pada data

·         Menentukan jumlah modulo-2 bit-1 agar data berpariti genap.

Bit ke-           7   6   5   4   3   2   1

Data              1   0   1   x   1   x   x

Langkah selanjutnya adalah menentukan bit-Hamming yang harus disisipkan ke dalam bit-bit data, dalam hal ini semua bit yang ditandai dengan hurf x adalah tempat posisi bit Humming yang seharus disisipkan. Dengan demikian data yang semula terdiri dari 4 bit data maka pada akhirnya jumlah bit adalah 7 bit.

Tabel penentuan bit Hamming

Bit-Hamming disisipkan ke dalam data, sehingga menjadi:

      Bit ke-             7   6   5   4   3   2   1

Data                1   0   1   0   1   0   1

Deteksi data error yang diakibatkan data berubah saat transmisi, diasumsikan terjadi perubahan pada bit ke 3 dari nilai logika 1 menjadi logika 0. Sehingga data yang diterima sebgai berikut :
      Bit ke-             7   6   5   4   3   2   1

Data                1   0   1   000   1

Pemeriksaan data melalui bit-bit Hamming ditemukan error berikut posisi bitnya, pada contoh terjadi error pada posisi bit ke 3.

Tabel penentuan error(modulo-2)

Berdasarkan tabel penentuan error diperoleh nilai biner 011, yang berarti bisa ditentukan kesalahan adalah pada posisi bit ke 3 pada data. Perbaikan logika bit dapat dilakukan dengan melakukan inverting bit ke dari data, dengan demikian tidak diperlukan lagi pengiriman NAK ke pengirim untuk melakukan pengiriman ulang.

Kelebihan kode hamming :

• Cara kerjanya yang cukup  sederhana  dan  tidak  membutuhkan  alokasi memori yang banyak
• Jika ditemukan error saat pendeteksian, data tidak perlu ditransmisikan ulang tetapi  langsung  dikoreksi  di  simpul  tujuan

Kekurangan kode hamming :

• Tidak dapat mendeteksi bila terjadi dua buah kesalahan sekaligus