Day: September 18, 2014

1. Hamming Code

• Mekanisme dan Cara Kerja

Ada  beberapa  metode  yang  digunakan  untuk  mendeteksi error  dan  mengkoreksi  error  yang  terjadi.  Salah  satunya adalah dengan menggunakan metode Hamming Code. Metode  hamming  code  merupakan  salah  satu  metode yang  paling  sederhana.  Metode  ini menggunakan  operasi  logika  XOR  (Exclusive-OR)   dalam proses pendeteksian error  maupun pengkoreksian error. Input dan  output  dari metode  ini  berupa  bilangan  biner.  Hamming code  merupakan  salah  satu  jenis  linier  error  correcting  code yang  sederhana  dan  banyak  dipergunakan  pada  peralatan elektronik (Satra, 2007).

Metode  hamming  code  bekerja  dengan  menyisipkan beberapa  buah  check  bit  ke  data.  Jumlah  check  bit  yang disisipkan  tergantung  pada  panjang  data.  Rumus  untuk menghitung jumlah  check bit  yang akan disisipkan ke dalam data. Data 2^n bit,  c = (n+1) bit, dimana c adalah jumlah check  bit yang disisipkan.

Tabel 1. Kenaikan data bit dan check bit

Check bit kemudian disisipkan pada data pada posisi yang dihitung menggunakan rumus perhitungan posisi check bit.

Rumus perhitungan posisi Check Bit C^i= 2^(i-1)

Sehingga dengan rumus posisi tersebut, didapat posisi check bit yang akan diletakkan pada data diperlihatkan pada tabel.

Tabel 2. Tabel posisi check bit

• Proses Pendeteksian Error

1. Hitung panjang data masukan dari metode  hamming code  yang  merupakan  hasil  penjumlahan  dari panjang  data  masukan  dengan  panjang  check  bit. Panjang  data  keluaran  dari  metode  hamming  code sama  dengan  panjang  data  masukan  dari  metode hamming code.

2. Tandai posisi bit yang merupakan posisi dari check bit. Posisi selain posisi check bit merupakan posisi data bit.

3. Tentukan  rumus  perhitungan  dari  masing-masing check bit.untuk n = 1 hingga jumlah dari check bit, lakukan hal berikut:

a.) Catat  semua  posisi  dimana  bit  n  dari  member position  bernilai  1,  kecuali  posisi  bit  itu  sendiri. Member position merupakan bentuk biner dari posisi bit.  Rumus  dari  check  bit  n  sama  dengan  operasi XOR dari posisi-posisi yang dicatat.

b.)  Hitung berapa panjang bit yang diterima dan original.

c.)  Cek tabel posisi check bit dan ekstrak chek bit nya.

d.)  Hitung kembali chek bit nya dengan bit yang didapat.

e.)  Konversikan operasikan XOR ke bentuk decimal.

• Contoh Kasus Hamming Code

Suatu memori internal menyimpan word 8 bit, suatu data 0011 0010 disimpan pada suatu alamat. Hitunglah bit paritas untuk mendeteksi dan memperbaiki kesalahan. Andaikan bit ke lima mengalami kesalahan, tunjukkan bagaimana kode Hamming mendeteksi kesalahan tersebut dan memperbaikinya.

Jawab:

8 bit = 2^n = 2^3. n=3

bit paritas = n+1 = 3+1 = 4

8+4 = 12

P1 (melangkahi 1) = 00101 = 0 (menggunakan operasi XOR, jika bit 1 berjumlah ganjil maka = 1,

P2 (melangkahi 2) = 01101 = 1 sedangkan jika bit 1 berjumlah genap maka = 0)

P4 (melangkahi 3) = 0110 = 0

P8 (melangkahi 4) = 0010 = 1

Andaikan bit 5 mengalami kesalahan, maka:

P1 = 01101 = 1 (salah)

P2 = 01101 = 1 (benar)

P4 = 1110 = 1 (salah)

P8 = 0010 = 1 (benar)

Karena kesalahan terjadi di P1 dan P4, maka 1+4 = 5. Maka kesalahan terjadi di bit ke-5

• Kekurangan dan Kelebihan Hamming Code

Kelebihan yang didapatkan dengan menggunakan metode ini adalah cara kerjanya yang cukup  sederhana  dan  tidak  membutuhkan  alokasi memori yang banyak. Selain itu dengan digunakannya konsep error  correcting  code  pada  metode  ini  maka  jika  ditemukan error saat pendeteksian, data tidak perlu ditransmisikan ulang tetapi  langsung  dikoreksi  di  simpul  tujuan.

Sedangkan kekurangan dari metode Hamming Code adalah tidak dapat mendeteksi bila terjadi dua buah kesalahan sekaligus. Contohnya bila 1111111 terkirim sebagai 11011110 pada odd parity code yang seharusnya adalah 11111111.

 

2. Metode Longitudinal Redundancy Check

• Mekanisme dan cara kerja

Longitudinal Redundancy Check (LRC) adalah metode pendeteksi kesalahan untuk mendeterminasikan kebenaran dari data yang disimpan/ditransmit. Pada metode pengecekan error LRC, blok bit diorganisasikan kedalam baris dan kolom. Kemudian paritas bit tiap kolom dihitung sehingga terbentuk baris dari hasil perhitungan paritas tersebut. Seletah itu, hasil yang didapat disatukan dengan data aslinya dan dikirim pada receiver. Setelah sampai pada receiver, hasil perhitungan data asli dibandingkan dengan data yang diterima pada receiver.

Contoh perhitungan LRC :

Terdapat 5 baris data yang terdiri dari 8 bit, yaitu : 11010010 11100010 00101010 01110100 00101111

Setiap baris atau kolom dihitung untuk mendapatkan hasil paritas bit dan hasil dikirim pada receiver.

Bit yang ada pada receiver akan dihitung dan dibandingkan dengan hasil paritas bit yang dikirimkan. Jika terjadi error akan dapat terlihat dengan jelas (lihat baris 2, error ditandai dengan lingkaran).

• Kelebihan dan Kekurangan LRC

Kelebihan dari LRC yaitu lebih mudah dalam mendeteksi adanya burst error, namun kelemahan dari LRC yaitu ketidak mampuannya mendeteksi kesalahan jika terjadi 2 bit error di baris yang sama namum berbeda kolom. LRC juga membutuhkan lebih banyak alokasi memori.

 

3. Metode Two Dimensional Parity

Two-dimensional parity adalah sebuah error detection dengan menambahkan bit parity untuk tiap baris data dan juga kolom data. Dengan menggunakan two-dimensional parity ini kita dapat mendeteksi kesalahan sampai dengan 3 bit.

Contoh :

Diketahui biner data sebagai berikut : 1111111 0000000 1010101 1100110 0101101 0010011

Maka bit data dan parity adalah : 11111111 00000000 10101010 11001100 01011010 00100111 11100100

• KELEBIHAN:

• BISA MENDETEKSI LETAK BIT YANG SALAH (JIKA HANYA TERDAPAT 1 KESALAHAN)

•MENINGKATKAN DETEKSI BURST ERROR

• KELEMAHAN:

• TIDAK DAPAT MENDETEKSI KESALAHAN SEPERTI CONTOH: DATA: 11110000 11000011 ERROR: 01110001 01000010 (ADA 2 DATA DI BAGIAN PERTAMA YANG SALAH KEMUDIAN DI BAGIAN KEDUA JUGA ADA 2 DATA YANG SALAH DI POSISI YANG SAMA)

 

Referensi:

Lubis, Ahmad Alfi Albar dkk. (2010). Perancangan Error Detection System And Error Correction System

Menggunakan Metode Hamming Code Pada Pengiriman Data Text. Medan: USU.

 http://t4planet.tripod.com/longitudinalredundancycheck.html

http://w ww.slideshare.net/angelgdiaz_ut/errors-error-detection-and-error-control-8600677

http://www.techopedia.com/definition/1800/longitudinal-redundancy-check-lrc

http://www.s cribd.com/doc/221737240/Teori-Informasi-Error-Detection

 

PERANAN ANGGOTA KELOMPOK