A. Hamming Code
langkah – langkah pendeteksian kesalahan dengan hamming code adalah sebagai berikut :
- Menangani single error code
- Cara membuat codenya :
- Posisi parity bit ada di bit sesuai 2n (1,2,4,8,16,32….)
- Selain posisi tersebut akan dipakai sebagai data (3,5,6,7…)
- Untuk mencari besar parity (0 atau 1) dapat dilakukan sbb:
- Posisi 1 : bergantian ada 1bit dan tidak ada 1bit : ada 1bit, gak ada 1 bit,ada 1bit…..
- Posisi 2 : bergantian ada 2 bit dan tidak ada 2 bit : ada 2bit, gak ada 2 bit,ada 2bit…..
- Posisi 4 : bergantian ada 4 bit dan tidak ada 4 bit : ada 4 bit, gak ada 4 bit,ada 4 bit…..
- Dan seterusnya untuk 8, 16,32,64….
- Bit Paritas ditentukan sebagai 1 bila jumlah bit 1-nya adalah ganjil. Bit Paritas ditentukan sebagai 0 bila jumlah bit 1-nya adalah genap
- Contoh :
- Suatu data : 1 0 0 1 1 0 1 0
- Membuat data word –nya:
- - – 1 – 0 0 1 – 1 0 1 0 ( – paritas 15)
- Carilah paritas-nya :
- Posisi 1 : ? – 1 – 0 0 1 – 1 0 1 0
- Jumlah bit 1 genap paritas : 0
- Posisi 2 : 0 ? 1 – 0 0 1 – 1 0 1 0
- Jumlah bit 1 ganjil paritas : 1
- Posisi 4 : 0 1 1 ? 0 0 1 – 1 0 1 0
- Jumlah bit 1 ganjil paritas : 1
- Posisi 8 : 0 1 1 1 0 0 1 ? 1 0 1 0
- Jumlah bit 1 genap paritas : 0
- Jadi Code-word-nya :
- 0 1 1 1 0 0 1 0 1 0 1 0
B. Parity Checks
Bit parity merupakan bilangan biner yang ditambahkan untuk meyakinkan bahwa jumlah bit yang dikirimkan mempunyai angka satu yang selalu genap atau ganjil. Ada dua varian bit parity, yaitu even parity bit dan odd parity bit. Even parity bit diset ke 1 jika jumlah angka 1 yang dikirimkan berjumlah ganjil (berarti membuat total angka 1 berjumlah genap). Odd parity bit akan diset ke 1 jika jumlah angka 1 yang dikirimkan berjumlah genap (berarti membuat total angka 1 berjumlah ganjil). Berikut gambaran even dan odd parity bit:
Jika jumlah bit ganjil (termasuk bit parity) berubah pada waktu transmisi, maka bit parity menjadi tidak benar dan mengindikasikan adanya kesalahan pada waktu pengiriman. Oleh karena itu, bit parity merupakan kode pendeteksi kesalahan (error detecting code), dan bukan merupakan kode pengoreksi kesalahan (error correcting code) karena tidak ada cara untuk menentukan bit mana yang keliru. Data harus diabaikan seluruhnya dan mengulangi lagi transmisi dari awal. Pada media transmisi yang terganggu, transmisi yang berhasil akan membutuhkan banyak waktu atau tidak berhasil sama sekali. Parity mempunyai keuntungan, yaitu hanya menggunakan satu bit saja dan membutuhkan satu saja gerbang XOR untuk men-generate-nya. Bit parity checking sering digunakan untuk transmisi karakter ASCII, karena karakter ini hanya mempunyai 7 bit dan bit ke-8 dapat digunakan untuk bit parity. Sebagai contoh, diasumsikan pengiriman 4 bit dengan nilai 1001, dengan bit parity terletak di sebelah paling kanan. Penjelasan transmisi menggunakan even parity, sebagai berikut:
A akan mengirim : 1001
A menghitung nilai bit parity : 1^0^0^1 = 0 (tanda ^ artinya xor)
A menambahkan bit parity dan kirim : 10010
B menerima : 10010
B menghitung keseluruhan parity : 1^0^0^1^0 = 0
B melaporkan bahwa transmisi berhasil dengan parity yang benar (genap).
Jika transmisi menggunakan odd parity, maka penjelasannya sebagai berikut:
A akan mengirim : 1001
A menghitung nilai bit parity : ~(1^0^0^1) = 1
A menambahkan bit parity dan kirim : 10011
B menerima : 10011
B menghitung keseluruhan parity : 1^0^0^1^1 = 1
B melaporkan bahwa transmisi berhasil dengan parity yang benar (ganjil).
A akan mengirim : 1001
A menghitung nilai bit parity : 1^0^0^1 = 0
A menambahkan bit parity dan kirim : 10010 *TRANSMISSION ERROR*
B menerima : 11010
B menghitung keseluruhan parity : 1^1^0^1^0 = 1
B melaporkan terjadi transmisi yang tidak benar, karena nilai parity tidak sama.
Pada kasus di atas, B menghitung nilai parity (0) tidak sama dengan bit parity (1) pada nilai yang diterima. Hal ini mengindikasikan terjadi kesalahan. Di bawah ini contoh yang sama tetapi dengan kesalahan pada bit parity-nya sendiri.
A akan mengirim : 1001
A menghitung nilai bit parity : 1^0^0^1 = 0
A menambahkan bit parity dan kirim : 10010 *TRANSMISSION ERROR*
B menerima : 10011
B menghitung keseluruhan parity : 1^0^0^1^1 = 1
B melaporkan terjadi transmisi yang tidak benar, karena nilai parity tidak sama.
Sekali lagi, B menghitung keseluruhan odd parity, dan mengindikasikan kesalahan bit. Ada keterbatasan pada skema parity ini, yaitu ketika ada kesalahan pada pengiriman data dengan bit yang salah berjumlah genap seperti pada contoh di bawah ini:
A akan mengirim : 1001
A menghitung nilai bit parity : 1^0^0^1 = 0
A menambahkan bit parity dan kirim : 10010 *TRANSMISSION ERROR*
B menerima : 11011
B menghitung keseluruhan parity : 1^1^0^1^1 = 0
B melaporkan transmisi berhasil dengan parity yang benar walaupun sebenarnya data sudah tidak benar.
C. Cyclic Redundancy Check (CRC)
- Cyclic redundancy check (CRC) adalah method yang umum digunakan untuk mendeteksi error
- CRC beroperasi pada sebuah frame/block. Setiap block data (berukuran m bit à m=M(x)+R(x)) yang akan dikirim akan terlebih dahulu dihitung CRC checksumnya (berukuran R bit dari standart).
- M(x) = pesan yang dikirim. G(x) = generator polynomial. R=jumlah bit CRC yang digunakan (mengikuti standart)
- Kalikan D dengan 2R
- Lakukan pembagian modulo 2 dengan G(x) untuk mendapatkan sisa R(x)
- Kemudian M(x)+R(x) sumnya akan dikirim sebagai frame (dengan ukuran m bit).
- Pada sisi penerima, CRC checksum akan dihitung kembali berdasarkan pada frame yang diterima, dan dibandingkan dengan checksum yang dikirimkan. Jika hasil baginya tidak 0, berarti frame telah rusak.
- CRC menggunakan prinsip modulo bilangan 2.
- Contoh:
- Akan mengirim karakter “W”
- Dalam desimal 8710
- Biner : M(x) = x6 + x4 + x2 + x + 1 = 1010111
- Generator menggunakan standart CRC-8-ATM (HEC) polynomial x8 + x2 + x + 1
Maka G(x) = 9-bit string “100000111″.
- R=8 (CRC 8bit)
- Kalikan M(x) dengan 2R
- M(x) * 28 = 101011100000000
Menentukan checksum :
- Bagi M(x) dengan generator G(x)
- Sisanya adalah checksum (10100010)
- Tambahkan checksum ke data asal:
- 10100010 ke M(x)
- Menjadi : 101011110100010
- Data dan checksum dikirimkan.
- Pada sisi penerima, data dan checksum yang diterima dibagi dengan generator.
Jika sisanya 0, berarti tidak terjadi kesalahan
- Jika sisanya bukan 0, berarti terjadi kesalahan
- M(x) yang diterima : 101011110100010
- Sisa yang dihasilkan : 00000000
- Pesan yang diterima benar
No comments:
Post a Comment