Data Link

Error Detection dan Correction

Error Detection dan Correction adalah mekanisme pendeteksian kesalahan dan perbaikan pada layer data link. Error Detection dan Correction (disingkat EDC) dibutuhkan pada layer data link karena bit stream yang masuk dari layer physical tidaklah dijamin bebas dari kesalahan.

Ada banyak kemungkinan dimana bit stream yang sedang dikirimkan melalui media transmisi akan rusak karena gangguan seperti attenuation, distortion, dan noise. Jika ada bit bit yang salah atau rusak, maka akan merusak frame yang berakibat rusaknya data tersebut, maka itu diperlukan metode error detection dan jika diperlukan dengan correctionnya juga.

Ada dua jenis error yang ditemukan pada layer data link, yaitu single-bit error dan burst error.

  • Single-bit Error, error ini merupakan jenis dimana hanya satu bit yang mengalami kerusakan. Biasanya terjadi pada parallel transmission.
  • Burst Error, error ini merupakan jenis dimana banyak bit dalam bit stream yang mengalami kerusakan dimana biasanya durasi dari gangguan lebih dari durasi satu bit. Biasanya terjadi pada serial transmission.

type error

Untuk mengatasi kesalahan ini, ada beberapa jenis konsep yang digunakan untuk mendeteksi sebuah kesalahan (error detection) pada bit stream yang diterima penerima, antara lain adalah :

  1. Parity Check
  2. Two-Dimensional Parity Check
  3. Checksum
  4. Cyclic Redundancy Check

Sedangkan untuk pendeteksian kesalahan sekaligus dengan pengkoreksian (error detection dan correction), teknik yang paling umum digunakan adalah Hamming Code.

Parity Check

Parity Check adalah salah satu teknik pendeteksian kesalahan yang paling mudah dipahami karena hanya menambahkan satu bit parity untuk pengecekan frame. Ada dua jenis parity check, yaitu Even Parity (parity dengan jumlah bit genap) dan Odd Parity (parity dengan jumlah bit ganjil).

Jika ada bit stream dengan “1011001“, maka

even odd parityBisa dilihat pada gambar, bahwa jika kita menggunakan even parity, maka parity bitnya 0 karena jika dijumlah akan menghasilkan angka yang genap, sebaliknya pada odd parity, dimana jika dijumlahkan maka ganjil.

Jangan bingung untuk membedakan Even Parity dan Odd Parity, seperti artikel sebelumnya tentang Metode Framing, disana dijelaskan tentang synchronous dan asynchronous transmission, dimana even parity biasanya digunakan pada synchronous transmission dan odd parity digunakan pada asychronous transmission.

flowchart parity

Jika data yang sampai pada penerima (menggunakan even parity) bernilai genap, maka frame diterima, sedangkan jika bernilai ganjil maka frame direject.

Ini adalah salah satu kelemahan dari parity check dimana hanya dapat mendeteksi single-bit error dan tidak dapat mendeteksi burst error, apakah pembaca tau kenapa?

Two-Dimensional Parity Check

Untuk mengatasi kekurangan dari Parity Check, dibuatlah teknik two-dimensional parity check. Teknik ini selain dapat mendeteksi single-bit error, juga dapat mendeteksi burst error. Cara kerjanya adalah data dibagi menjadi beberapa blok bit dimana bit disusun menyerupai tabel dimana parity bit dicari setiap baris dan setiap kolomnya.

two-dimensional parity checkDari bit-bit stream tersebut, diperoleh parity bit (dengan menggunakan parity check) pada kolom-kolom bit dan juga pada baris-baris bit, lalu dicari parity dari parity baris dan parity kolom tersebut. bit-bit disusun seperti gambar dimana parity kolom diletakan dibagian akhir bit stream. Teknik ini efektif untuk medeteksi single bit error ataupun burst error.

Bisa dilihat terdapat error pada bit stream dan dapat dideteksi dengan teknik two-dimensional parity check, dengan menukarkan dan mengorbankan beberapa slot bit, performa pendeteksian meningkat. Teknik ini dapat mendeteksi burst error, tetapi tidak semua burst error dapat dideteksi, kelemahannya ada pada contoh dibawah ini :

Jika ada bit dengan kelipatan dua (2,4,6,…) yang error pada bit stream (dua bit pada baris dan dua bit pada kolom) maka error tidak dapat dideteksi.

Checksum

Checksum adalah metode pendeteksian kesalahan dimana bit stream dipecah menjadi beberapa segmen. Setiap segmen dijumlah dengan metode tertentu untuk menghasilkan sebuah hasil yang disebut sum. Hasil sum ini akan di invers untuk menghasilkan checksum dan checksum akan dimasukan pada bit stream sebagai error detection.

Pertambahan (sum) pada biner agak berbeda dengan aritmatika biasa, jika ada bit 1 ditambahkan dengan bit 1 maka hasilnya adalah 0 dengan carry 1 (ditambahkan pada kolom selanjutnya), dan jika ada carry 1 ditambahkan dengan bit 1 dan bit 1, maka hasilnya adalah 1 dengan carry 1.

checksumPada proses checksum pada sender, semua bit-bit stream di tambahkan (sum) sehingga menghasilkan sebuah sum yang digunakan untuk mencari checksum. Checksum ini dibawa dengan data hingga sampai ke penerima. dipenerima dilakukan proses yang sama yaitu menjumlahkan data-data dan juga dengan data checksum. Jika dihasilkan binary satu pada penjumlahan dan jika diinvers hasilnya 0 maka data akan diterima, jika tidak maka ada kesalahan pada data.

Salah satu contoh penerapan checksum ada pada pendeteksian kesalahan pada IPv4 header (hanya untuk headernya saja), penjumlahan bisa dilakukan pada binary, hexsadesimal ataupun desimal. Sebagai contoh adalah dengan studi kasus berikut :

dengan melakukan capture dengan menggunakan wireshark pad IPv4 Header, didapatkan header dalam heksa yaitu 4500 0054 9a50 4000 4001 ce5b c0a8 0145 0808 0808. Dimana heksa ce5b adalah checksumnya, lalu bagaimana cara mendapatkannya?

wireshark

dari heksa terebut, dijumlahkanlah semua heksa tersebut (terkecuali checksumnya, karena saat proses pengiriman jelas checksum masih kosong dan harus dicari terlebih dahulu). Jika dijumlahkan dalam heksa, ditemukan bilangan Heksa 231A2.

ipv4 header checksum

Cyclic Redundancy Check

Cyclic Redundancy Check adalah teknik pendeteksian kesalahan yang paling populer dan yang paling powerful diantara semua teknik pendeteksian kesalahan. Teknik ini berbeda dengan teknik checksum dimana data ditambahkan, pada cyclic redundancy check, bit-bit dibagi dengan sebuah divisor dengan sebelumnya ditambahkan bit-bit 0 dengan jumlah divisor dikurangi satu.

CRCProses pembagian ini akan menghasilkan sebuah bit CRC (dari hasil pembagian) yang akan digabungkan dengan data untuk dikirim. Sesampainya dipenerima, bit-bit tersebut dibagi dengan sebuah divisor yang sama, jika hasil baginya adalah 0, maka data tersebut diterima, jika tidak maka data tersebut ditolak.

Proses pembagian pada cyclic redundancy check adalah menggunakan XOR gate. Berikut adalah tabel kebenaran atas XOR gate :

xor gate

Lalu daprimanakan divisor tersebut kita tentukan? setelah saya mencoba beberapa tes, ternyata kita dapat mengunakan sembarang divisor, tetapi sudah ada standar yang mengatur tentang divisor tersebut, jadi divisor untuk masing-masing protokol di data link adalah berbeda, kamu dapat mengecek standar yang digunakan disini.

Error Correction

Setelah mempelajarai beberapa cara yang digunakan untuk mendeteksi kesalahan, maka anda juga harus mempelajari bagaimana cara perbaikan error di data link. Ada dua jenis pendeteksian kesalahan

  1. Backward error correction, yaitu jika ditemukan sebuah kerusakan dengan menggunakan teknik pendeteksian kesalahan, maka penerima akan meminta pengirim untuk mengirimkan ulang frame yang rusak.
  2. Forward error correction, dimana didalam frame, ditambahkan beberapa bit yang digunakan sebagai redundancy untuk memperbaiki kerusakan pada frame.

Kita akan fokus membahas forward error correction, dan salah satu yang terkenal adalah Hamming Code. meskipun hamming code merupakan proses perbaikan kesalahan, ternyata hamming code dapat digunakan untuk mendeteksi kesalahan.

Hamming Code

Hamming code sangat mudah untuk diimpementasikan dan dipahami, jika anda paham dengan konsep parity bit, maka hamming code mengunakan konsep seperti parity bit. Didalam hamming code, kita mengenal parity bit (bit yang digunakan untuk mendeteksi dan mengkoreksi) dan data bit.

Letak parity bit dalam hamming code adalah dengan menggunakan “power of two”, jadi letak parity bit adalah pada bit pertama, bit kedua, bit keempat, bit kedelapan, bit ke enam belas, dan seterusnya. dengan sisanya adalah diisi dengan data bit.

Kasus : jika ingin mengirimkan 10 data bit, berapa jumlah total bit dan jumlah parity bit yang dibutukan?

Jumlah total bit (parity+data) adalah 14 bit, dibutuhkan 4 parity bit untuk mengirimkan 10 data bit dengan jumlah bit. Yang pertama yang harus dilakukan adalah dengan menggambar slot seperti diatas dimana di letakan dulu parity bit pada slot sesuai power of two. jika sudah maka slot yang kosong adalah slot untuk data bit. Jika dilihat data bit hanya sampai slot ke 14, maka slot ke 15 tidak dipakai dimana terdapat 4 parity bit.

Untuk mencari parity bit, konsep yang digunakan sama seperti mencari parity pada error detection (dengan ganjal ataupun genap). yang harus diketahui adalah tidak semua data bit digunakan untuk mencari sebuah parity bit. Ada sebuah aturan untuk memilih mana slot yang digunakan untuk sebuah parity bit, konsep tersebut adalah melakukan check and skip.

  • pada parity pertama, dimulai dari parity pertama, check satu slot, skip satu slot, check satu slot, skip satu slot, dst.
  • pada parity kedua, dimulai dari parity kedua, check dua slot, skip dua slot, check dua slot, skip dua slot, dst.
  • pada parity keempat, dimulai dari parity keempat, check empat slot, skip empat slot, check empat slot, skip dua slot, dst.
  • pada parity kedelapan, dimulai dari parity kedelapan, check delapan slot, skip delapan slot, dst

hamming2sebagai contoh ada 10 data bit (1010110011), maka yang dikirimkan adalah gabungan antara data bit dengan parity bit (10110100110011).

Hamming code error detection

Jika bit stream tersebut sampai kepenerima, maka yang pertama kali dilakukan adalah mendeteksi apakah ada kesalahan dengan menggunakan parity bit. Asumsikan ada kesalahan bit pada D4.

Dengan begitu, dapat terdeteksi kesalahan pada bit stream yang masuk.

Hamming Code Error Correction

Jika terdeteksi kesalahan pada sebuah parity, maka parity yang terdeteksi error diberi nilai 1, dimana sebaliknya, jika tidak terdeteksi error, maka parity tersebut diberi nilai 0.

hamming error correction