Deteksi dan Koreksi Error

BAB 10 Deteksi dan Koreksi Error

Setelah membaca bab ini, diharapkan pembaca memperoleh wawasan tentang: 9 beberapa jenis kesalahan (error); 9 teknik deteksi error; 9 teknik memperbaiki error.

2

Deteksi dan Koreksi Error

10.9 Jarak Hamming Dalam block coding transmisi data dilakukan dengan membagi deretan bit menjadi block yang terdiri dari sejumlah bit (k) yang disebut dengan words serta menambahkan sejumlah bit tambahan (redundancy/r) ke dalam setiap block sehingga panjang dari block yang akan ditransmisikan menjadi: n = k + r Ædisebut dengan codewords. Salah satu konsep penting dalam blok kode untuk transmisi data adalah jarak hamming (hamming distance), yang diartikan sebagai jumlah perbedaan antara dua buah deretan bit (words) yang mempunyai ukuran sama. Jika terdapat 2 buah deretan bit misalnya x dan y maka jarak hamming dapat disimbolkan dengan: d(x,y) Jarak hamming cukup mudah untuk diimplementasikan, yaitu dengan menggunakan operasi XOR pada dua buah words, dan menghitung jumlah bit 1 dari hasil operasi. Contoh : Tentukan jarak hamming dari pasangan words berikut. 1) d (000, 011) akan menghasilkan 2, karena terdapat hasil 011 (dimana jumlah bit 1 berjumlah 2) 2) d (10101, 11110) menghasilkan 3, karena terdapat hasil 01011 (dimana jumlah bit 1 berjumlah 3)

•

Jarak hamming akan menghasilkan bilangan lebih besar dari 0 (nol).

__________________________________________________________________ Lecturer : M. Miftakul Amin, S. Kom., M. Eng. Program Studi Teknik Komputer Politeknik Negeri Sriwijaya Palembang

Komunikasi Data

3

10.10 Minimum Hamming Distance Jarak hamming digunakan untuk melakukan proses deteksi dan koreksi error pada data yang ditransmisikan. Jarak minimum hamming distance merupakan jarak hamming terkecil antara semua kemungkinan pasangan words. Tabel 1. Pasangan Word

Pada block code pada Table 1, dapat ditentukan minimum hamming distance sebagai berikut: d (000, 011) = 2 d (000, 101) = 2 d (000, 110) = 2 d (011, 101) = 2 d (011, 110) = 2 d (101, 110) = 2 sehingga dapat ditentukan bahwa dMIN = 2 Selanjutnya dapat dilakukan proses yang sama untuk menentukan dMIN dari Tabel 2. Tabel 2 Pasangan Codeword 5 digit


4


Hasil dari perhitungan hamming distance diperoleh hasil seperti Gambar 1, sehingga dapat disimpulkan dMIN = 3 karena nilai terkecil dari hamming distance adalah 3.

Gambar 1 Hasil Perhitungan Hamming Distance •

Untuk menjamin deteksi hingga s kesalahan dalam semua kasus, minimum jarak hamming dalam sebuah block code harus dMIN = s + 1. Artinya minimum hamming distance hanya mampu mendeteksi error dMIN – 1 pada data yang ditransmisikan.

Jika terdapat dMIN = 2, hal ini mengindikasikan bahwa block code menjamin hanya terjadi single-bit error. Sebagai contoh pada Tabel 1, data ke-3 pada codeword 101 ditransmisikan dan satu error terjadi, maka codeword yang diterima tidak sama dengan codeword yang valid di dalam daftar codeword pada Tabel 1. Jika terjadi 2 error, dapat saja codeword yang diterima cocok dengan codeword valid tapi dampaknya adalah error tidak dapat dideteksi. Contoh lain pada Tabel 2, nilai dari dMIN = 3, sehingga block code hanya mampu mendeteksi error sebanya 2 bit. Sebagai contoh:

Data 00000 ditransmisikan kemudian terdapat 2 bit error missal 00011 atau 01100, atau 11000, atau 10100 Maka dapat dipastikan data yang diterima merupakan data yang tidak valid sehingga receiver mendeteksi terjadinya error pada data yang dikirim. Tetapi jika data yang diterima terjadi error lebih dari 2 akan mengakibatkan error tidak terdeteksi. Kondisi lain jika terjadi error sebanyak 3 buah, maka dapat mengakibatkan terjadinya error yang tidak terdeteksi, karena data yang error bisa jadi merupakan codeword yang lain. __________________________________________________________________ Lecturer : M. Miftakul Amin, S. Kom., M. Eng. Program Studi Teknik Komputer Politeknik Negeri Sriwijaya Palembang

Komunikasi Data

5

Hubungan antara minimum hamming distance dengan deteksi error dapat digambarkan seperti sebuah geometri pada Gambar 2. Diasumsikan terdapat data codeword yang valid sebagai titik pusat dengan jari-jari s. Terdapat error dari mulai pusat lingkaran sampai batas jari-jari. Sehingga semua codeword yang valid harus berada di luar lingkaran.

Gambar 2 Hubungan Minimum Hamming Distance dan Deteksi Error


6


10.11 Linear Block Code Linear block code didefinisikan sebagai operasi XOR pada dua buah codeword yang valid akan menghasilkan codeword lain yang valid juga. Penggunaan liner block code dalam upaya untuk memudahkan dalam deteksi dan koreksi error. Sebagai contoh Tabel 1, apakah termasuk linear block code? Untuk menjawab pertanyaan ini dapat dilakukan proses operasi XOR pada masingmasing codeword.

Contoh: Codeword 1 dan 2 Æ 000 + 011 = 011 Æhasilnya codeword 2 Codeword 2 dan 3 Æ 011 + 101 = 110 Æhasilnya codeword 4 Codeword 3 dan 4 Æ 101 + 110 = 011 Æhasilnya codeword 2

Dengan hasil yang ditampilkan dapat dikatan bahwa codeword pada Tabel 1 merupakan linear block code.


Komunikasi Data

7

10.12 Metode Checksum Konsep dari metode Checksum tidaklah rumit. Pola deteksi error menggunakan checksum juga menggunakan bit tambahan (redundancy). Contoh penggunaan checksum adalah sebagai berikut:

Contoh 1) Terdapat 5 buah bilangan yang terdiri dari 4 bit yang akan ditransmisikan. Pada saat 5 buah bilangan dikirim, ditambahkan 1 buah bilangan sebagai hasil penjumlahan (sum) dari kelima bilangan yang dikirim. Bilangan tersebut adalah: 7, 11, 12, 0, 6 dan tambahan satu bilangan 36, sehingga data yang dikirimkan adalah 7, 11, 12, 0, 6, 36. Ketika data sampai di receiver, kelima buah bilangan tersebut diterima dan dijumlahkan, jika hasil penjumlahan sama dengan 36 maka diasumsikan data valid. Kelima data tersebut akan diterima dan hasil penjumlahan (36) akan dibuang.

Contoh 2) Pada kasus di contoh 1) kita juga dapat mengirimkan hasil penjumlahan berupa bilangan negative (komplemen) yang disebut dengan checksum. Sehingga deretan data yang dikirim adalah 7, 11, 12, 0, 6, -36. Selanjutnya ketika data sampai pada sisi receiver semua data akan dijumlahkan termasuk checksum, jika diperoleh nilai penjumlahan sama dengan 0 (nol) maka diasumsikan tidak terjadi error.

•

Metode Checksum menggunakan konsep redundancy untuk mendeteksi error.


8


Pada dua contoh kasus yang telah dibahas sebelumnya terdapat kekurangan dimana semua data yang dikirim terdiri dari 4 digit, artinya maksimal hanya nilai 15 (1111 biner = 15 desimal) kecuali untuk hasil checksum. Sehingga diperlukan sebuah metode jika terdapat data yang nantinya akan dikirim lebih dari 15, yaitu menggunakan arimatika komplemen satu. Pada aritmatika komplemen satu caranya adalah dengan merepresentasikan bilangan antara 0 sampai 2n – 1 dengan menggunakan n bit. Jika terdapat bilangan yang lebih dari n bit, maka bit yang lebih pada sisi kiri akan ditambahkan pada sisi kanan istilah ini dikenal dengan nama wrapping.

Contoh: Bagaimana kita dapat merepresentasikan bilangan 21 dalam aritmatika komplemen satu dengan hanya menggunakan 4 bit? Jawab: Bilangan decimal 21 memilki biner 10101 (memiliki jumlah bit 5), sehingga bit 1 pada sisi kiri akan dijumlahkan ke 4 bit di sebelah kanannya, menjadi: 10101 1 0101 1 ------ + 0110 Æ decimal 6

Sehingga dapat dikatakan nilai dari 21 jika digunakan operasi aritmatika komplemen satu hasilnya adalah 6.

Pada aritmatika komplemen satu bilangan negatif dapat direpresentasikan dengan mengubah bit (bit 0 diubah menjadi 1, atau bit 1 diubah menjadi bit 0), dengan kata lain memiliki hasil yang sama dengan mengurangkan sebuah bilangan dengan 2n – 1.


Komunikasi Data

9

Contoh: Bagaimana kita merepresentasikan bilangan -6 menggunakan aritmatika komplemen satu menggunakan 4-bit? Jawab: Cara 1) Bilangan positif 6 adalah 0110, dengan melakukan pengubahan bit maka menjadi 1001, jika kita menggunakan hasil 1001 sebagai bilangan positif maka akan menghasilkan decimal 9, dengan kata lain komplemen dari bilangan 6 adalah 9.

Cara 2) Cara lain adalah dengan mengurangkan bilangan 6 dengan 2n – 1 yaitu 15 – 6 = 9.

Bagaimanakah menggunakan aritmatika komplemen satu untuk menyelesaikan metode checksum pada transmisi data 7, 11, 12, 0 dan 6 seperti dapat dilihat pada Gambar 3.

Gambar 3 Proses Aritmatika Komplemen Satu


10


Pada Gambar 3 dapat dilihat bahwa hasil penjumlahan dari 6 bilangan adalah 36 (pada dasarnya data yang dikirim adalah 5 bilangan, bilangan ke-6 yaitu 0 merupakan inisialisasi untuk ditempati dengan hasil checksum pada sisi pengirim). Hasil penjumlahan (dalam hal ini adalah 36) selanjutnya dilakukan operasi aritmatika komplemen 1 sehingga menghasilkan 6 (sebagai wrapped checksum). Untuk memperoleh checksum maka hasil aritmatika komplemen 1 yaitu 6 dikurangkan dengan 15 sehingga 15 – 6 = 9. Selanjutnya data yang dikirim sebagai paket data adalah 7, 11, 12, 0, 6, 9 sehingga data yang dikirim berjumlah 6 bilangan termasuk bilangan 9 sebagai checksum yang nantinya digunakan untuk melakukan deteksi error. Pada sisi penerima seluruh data akan diterima dan dijumlahkan termasuk checksum sehingga berjumlah 45, karena 45 menggunakan lebih dari 4 bit yaitu 6 bit maka dilakukan proses wrapping sehingga diperoleh hasil 15 (sebagai wrapped sum) selanjutnya 15 dikurangkan dengan 2n – 1 menjadi 15 – 15 hasilnya adalah 0 (nol) yang mengindikasikan tidak terjadi error.

10.13 Metode Internet Checksum Secara tradisional internet menggunakan 16-bit checksum. Metode ini menggunakan algoritma sebagai berikut: Pada sisi sender/pengirim. -------------------------------1. Data yang akan dikirim dipecah ke dalam 16 bit 2. Nilai dari checksum diberi nilai 0 (nol) sebagai initial checksum 3. Semua bit termasuk initial checksum dijumlahkan menggunakan penjumlahan komplemen satu. 4. Selanjutnya proses penjumlahan (sum) selesai dan untuk menjadi checksum dikurangkan dengan 15. 5. Checksum dikirim beserta data.


Komunikasi Data

11

Pada sisi receiver/penerima -------------------------------1. Data yang diterima (termasuk checksum) dipecah ke dalam 16 bit 2. Semua data dijumlahkan menggunakan penambahan komplemen satu 3. Penjulahan selesai dan menghasilkan checksum baru 4. Jika nilai checksum adalah 0 (nol), data akan diterima jika sebaliknya data akan ditolak Contoh pada Gambar 4 merupakan implementasi dari metode internet checksum. Diasumsikan akan ditransmisikan data text yang terdiri dari 8 karakter yaitu FOROUZAN. Karena terdapat keharusan harus diubah menjadi 16 bit, maka dibagi 8 karakter bit masing-masing terdiri belum 2 byte atau 16 bit. Dalam kode ASCII 8 bit karakter F diubah menjadi heksadesimal 0x46, karakter O 0x6F, demikian juga untuk karakter yang lain.

Gambar 4. Metode Internet Checksum Jika data yang akan dikirimkan adalah Ox4567 dan OxBA98 hasil dari checksum adalah Ox0000:


12


"Latihan 1. Tentukan Hamming Distance dari deretan codeword berikut a) d (10000, 00000) b) d (10101, 10000) c) d (1111, 1111) d) d (000, 000) 2. Pengirim ingin mentransmisikan 4 item data yaitu Ox3456, OxABCC, Ox02BC, OxEEEE. Jawab beberapa pertanyaan berikut menggunakan metode internet checksum. a) Tentukan checksum pada sisi pengirim b) Tentukan checksum pada sisi receiver jika tidak ditemukan error c) Tentukan checksum pada sisi receiver jika data ke-2 yaitu OxABCC berubah menjadi OxABCE d) Tentukan checksum pada sisi receicer jika data ke-2 yaitu OxABCC berubah menjadi OxABCE dan data ke-2 dari Ox02BA berubah menjadi Ox02BC menjadi Ox02BA.

"Sumber Rujukan Forouzan, A., Behrouz. 2007. Data Communication and Networking 4th Edition. Boston: Mc Graw Hill.


Deteksi dan Koreksi Error

Recommend Documents