Selasa, 13 Maret 2012

Deteksi dan Koreksi Kesalahan Komunikasi Data

Nama  : Agus Mandiri
NIM    :10018104
Kelas   : B
Tugas  : Komunikasi Data dan Jaringan Komputer
Deteksi dan Koreksi Kesalahan Komunikasi Data(Eror Correction and Detection)
Kesalahan adalah proses alami yang dapat terjadi pada tiap bagian dari sistem komunikasi data. Namun demikian perlu adanya langkah-langkah bagi perbaikan melalui evaluasi terhadap penyebab terjadinya kesalahan dan menyelidiki kemungkinan-kemungkinan terjadinya kesalahan dalam proses transmisi maupun data terminal.
Salah satu sistem kontrol kesalahan yang sederhana ataupun yang sangat kompleks dapat disisipkan pada bagian-bagian yang telah terdeteksi pada langkah pertama tadi. Akan tetapi ada pertimbangan lain yang turut dipertimbangkan, misalnya perlunya penekanan pada biaya untuk operasi kontrol kesalahan ini jangan sampai melebihi dari biaya sehingga membuat sistem yang dibangun menjadi mahal.
Pada umumnya kesalahan-kesalahan yang terjadi dalam komunikasi data pada umumnya dapat diperkirakan atau dengan kata lain kesalahan-kesalahan yang tidak terdeteksi pada suatu bagian dalam sistem transmisi data mungkin dapat dideteksi pada bagian lain. Dengan alasan untuk meningkatkan efektifitas komunikasi data, para perancang sistem kontrol kesalahan berusaha merancang sistem kontrol dengan memberikan proteksi maximum terhadap informasi redundant yang seminim mungkin.
Pendeteksi Error

1. Bit Parity

Deteksi bit error yang paling sederhana parity bit pada akhir tiap word dalam frame. Terdapat dua jenis parity bit ini :
• Even parity : jumlah dari binary '1' yang genap --> dipakai untuk transmisi asynchronous.
• Odd parity : jumlah dari binary '1' yang ganjil --> dipakai untuk transmisi synchronous.
Atau menggunakan operasi exclusive-OR dari bit-bit tersebut dimana akan menghasilkan binary '0' untuk even parity dan menghasilkan binary '1' untuk odd parity.
Catatan :
• exclusive-OR dari 2 digit binary adalah 0 bila kedua digitnya adalah 0 atau keduanya = 1; jika digitnya beda maka hasilnya = 1.
Problem dari parity bit :
• Impulse noise yang cukup panjang merusak lebih dari satu bit, pada data rate yang tinggi.

2. CYCLIC REDUNDANCY CHECKS (CRC)

Diberikan suatu k-bit frame atau message, transmitter membentuk serangkaian n-bit, yang dikenal sebagai frame check sequence (FCS). Jadi frame yang dihasilkan terdiri dari k+n bits. Receiver kemudian membagi frame yang datang dengan beberapa angka dan jika tidak ada remainder (sisa) dianggap tidak ada error.
Beberapa cara yang menjelaskan prosedur diatas, yaitu :
a. Modulo 2 arithmetic
Menggunakan penjumlahan binary dengan tanpa carry, dimana hanya merupakan operasi exclusive-OR.
b. Polynomials
Dalam bentuk variabel x dengan koef isien-koefisien binary. Koefisien-koefisien tersebut berhubungan dengan bit -bit dalam binary sehingga proses CRC-nya dapat dijabarkan sebagai :
1. X M(X) = Q(X) + R(X)
--------- ---------------
P(X) P(X)
2. T(X) = X M(X)+ R(X)
Error E(X) hanya tidak akan terdeteksi bila dapat dibagi dengan P(X). Error-error yang dapat dideteksi yang tidak dapat dibagi oleh P(X) :
 Semua error bit tunggal.
ü
 Semua error bit ganda, sepanjang P(X) mempunyai faktor paling sedikit 3 syarat.
ü
 Jumlah error genap apapun, sepanjang P(X) mengandung faktor (X + 1).
ü
ü Burst error apapun dengan panjang burst lebih kecil daripada panjang FCS.
 Burst error yang paling besar.
ü
C. Automatic Repeat Request (ARQ)
1. Stop-and-Wait ARQ
Stop-and-Wait ARQ didasarkan atas teknik flow control stop-and-wait. Stasiun source mentransmisikan sebuah frame tunggal dan kemudian harus menunggu balasan berupa acknowledgement (ACK). Tidak ada frame yang dikirim sampai jawaban dari stasiun tujuan tiba di stasiun sumber.

Ada dua jenis kesalahan yang dapat terjadi. Pertama, frame yang tiba di tujuan bisa mengalami kerusakan. Receiver mendeteksi kerusakan tersebut dengan menggunakan teknik pendeteksian kesalahan yang berkaitan dengan pembuangan frame lebih awal. Untuk menghitung kemungkinan ini, stasiun sumber dilengkapi dengan sebuah pencatat waktu. Setelah frame ditransmisikan/stasiun sumber menunggu balasan. Bila tidak ada balasan yang diterima sampai waktu yang ditentukan pencatat habis, maka akan dikirimkan frame yang sama. perhatikan bahwa metode ini mengharuskan transmitter mempertahankan tiruan frame yang ditransmisikan sampai balasan diterima oleh frame tersebut.

Jenis kesalahan yang kedua adalah kerusakan pada balasan. Amati situasi berikut. Stasiun A mengirim, sebuah frame. Frame ini diterima dengan baik oleh stasiun B, yang meresponnya dengan memberi balasan (ACK). ACK mengalami kerusakan saat singgah dan tidak diakui oleh A, yang karenanya keluar dari jalur waktu dan kembali mengirim frame yang sama. Duplikat frame ini tiba dan diterima oleh B. Dengan begitu B menerima dua duplikat frame yang sama seolah-olah keduanya terpisah. Untuk mengatasi problem ini, frame bergantian diberi label 0 atau 1, dan balasan positifnya dalam bentuk ACK 0 dan ACK 1. Sesuai dengan aturan jendela penggeseran, ACK 0 membalas penerimaan frame bernomor 1 dan menunjukkan bahwa receiver siap untuk frame bemomor 0.

Gambar diatas  memberi contoh penggunaan stop-and-wait ARQ, menunjukkan transmisi deretan frame dari sumber A menuju tujuan B. Gambar tersebut juga menunjukkan kedua jenis kesalahan yang baru saja digambarkan. Frame ketiga yang ditransmisikan oleh A hilang atau rusak dan karenanya tidak ada ACK yang dikembalikan oleh B. A mengalami time out dan kembali mentransn-dsikan frame yang sama. Saat B menerima dua frame dalam sebuah barisan dengan label yang sama, B membuang frame kedua namun mengirimkan ACK0 kembah ke masing-masing stasiun.

Kode-kode Pengkoreksian Error
Para perancang jaringan telah membuat dua strategi dasar yang berkenaan dengan error. Cara pertama adalah dengan melibatkan informasi redundan secukupnya bersama-sama dengan setiap blok data yang dikirimkan untuk memungkinkan penerima menarik kesimpulan tentang apa karakter yang ditransmisikan yang seharusnya ada. Cara lainnya adalah dengan hanya melibatkan redundansi secukupnya untuk menarik kesimpulan bahwa suatu error telah terjadi, dan membiarkannya untuk meminta pengiriman ulang. Strategi pertama menggunakan kode-kode pengkoreksian error (error-correcting codes), sedangkan strategi kedua menggunakan kode-kode pendeteksian error (error-detecting codes).
Untuk bisa mengerti tentang penanganan error, kita perlu melihat dari dekat tentang apa yang disebut error itu. Biasanya, sebuah frame terdiri dari m bit data (yaitu pesan) dan r redundan, atau check bits. Ambil panjang total sebesar n (yaitu, n=m+r). Sebuah satuan n-bit yang berisi data dan checkbit sering kali dikaitkan sebagai codeword n-bit.
Sifat-sifat pendeteksian error dan perbaikan error suatu kode tergantung pada jarak Hamming-nya. Untuk mendeteksi d error, anda membutuhkan kode dengan jarak d+1 karena dengan kode seperti itu tidak mungkin bahwa error bit tunggal d dapat mengubah sebuah codeword yang valid menjadi codeword valid lainnya. Ketika penerima melihat codeword yang tidak valid, maka penerima dapat berkata bahwa telah terjadi error pada transmisi. Demikian juga, untuk memperbaiki error d, anda memerlukan kode yang berjarak 2d+1 karena hal itu menyatakan codeword legal dapat terpisah bahkan dengan perubahan d, codeword orisinil akan lebih dekat dibanding codeword lainnya, maka perbaikan error dapat ditentukan secara unik.
Sebagai sebuah contoh sederhana bagi kode pendeteksian error, ambil sebuah kode dimana parity bit tunggal ditambahkan ke data. Parity bit dipilih supaya jumlah bit-bit 1 dalam codeword menjadi genap (atau ganjil). Misalnya, bila 10110101 dikirimkan dalam parity genap dengan menambahkan sebuah bit pada bagian ujungnya, maka data itu menjadi 101101011, sedangkan dengan parity genap 10110001 menjadi 101100010. Sebuah kode dengan parity bit tunggal mempunyai jarak 2, karena sembarang error bit tunggal menghasilkan sebuah codeword dengan parity yang salah. Cara ini dapat digunakan untuk mendeteksi erro-error tunggal.
Sebagai contoh sederhana dari kode perbaikan error, ambil sebuah kode yang hanya memiliki empat buah codeword valid :
 0000000000,0000011111,1111100000 dan 1111111111
Kode ini mempunyai jarak 5, yang berarti bahwa code tersebut dapat memperbaiki error ganda. Bila codeword 0000011111 tiba, maka penerima akan tahun bahwa data orisinil seharusnya adalah 0000011111. Akan tetapi bila error tripel mengubah 0000000000 menjadi 0000000111, maka error tidak akan dapat diperbaiki.
Kode-kode Pendeteksian Kesalahan
Kode pendeteksian error kadang kala digunakan dalam transmisi data. Misalnya, bila saturan simplex, maka transmisi ulang tidak bisa diminta. Akan tetapi sering kali deteksi error yang diikuti oleh transmisi ulang lebih disenangi. Hal ini disebabkan karena pemakaian transmisi ulang lebih efisien. Sebagai sebuah contoh yang sederhana, ambil sebuah saluran yang errornya terisolasi dan mempunyai laju error 10 –6 per bit.
Aggap ukuran blok sama dengan 1000 bit. Untuk melaksanakan koreksi error blok 1000 bit, diperlukan 10 bit check; satu megabit data akan membutuhkan 10.000 bit check. Untuk mendeteksi sebuah blok dengan error tunggal 1-bit saja, sebuah bit parity per blok akan mencukupi. Sekali setiap 1000 blok dan blok tambahan (1001) akan harus ditransmisikan. Overhead total bagi deteksi error + metoda transmisi ulang adalah hanya 2001 bit per megabit data, dibanding 10.000 bit bagi kode Hamming.
Kendali kesalahan
Tujuan dilakukan pengontrolan terhadap error adalah untuk menyampaikan frame-frame tanpa error, dalam urutan yang tepat ke lapisan jaringan. Teknik yang umum digunakan untuk error control berbasis pada dua fungsi, yaitu:
Error detection, biasanya menggunakan teknik CRC (Cyclic Redundancy Check)
Automatic Repeat Request (ARQ), ketika error terdeteksi, pengirim meminta mengirim ulang frame yang terjadi kesalahan.
Mekanisme Error control meliputi
* Ack/Nak : Provide sender some feedback about other end
* Time-out: for the case when entire packet or ack is lost
* Sequence numbers: to distinguish retransmissions from originals
Untuk menghindari terjadinya error atau memperbaiki jika terjadi error yang dilakukan adalah melakukan perngiriman message secara berulang, proses ini dilakukan secara otomatis dan dikenal sebagai Automatic Repeat Request (ARQ).
Pada proses ARQ dilakukan beberapa langkah di antaranya (1):
* Error detection
* Acknowledgment
* Retransmission after timeout
* Negative Acknowledgment
Kesalahan-kode koreksi biasanya dibedakan antara kode konvolusional dan kode blok:
kode Konvolusional * harus diproses secara sedikit-demi-sedikit. Mereka terutama cocok untuk implementasi di hardware, dan dekoder Viterbi decoding memungkinkan optimal.
* Blok kode tersebut diproses secara blok demi blok. Awal contoh kode blok adalah kode pengulangan, Hamming kode dan multidimensi paritas-memeriksa kode. Mereka diikuti oleh sejumlah kode yang efisien, Reed-Solomon kode menjadi yang paling penting karena mereka saat ini digunakan secara luas. kode Turbo dan paritas-cek low-density kode (LDPC) relatif konstruksi baru yang dapat memberikan efisiensi hampir optimal.
Teorema Shannon merupakan teorema penting dalam maju koreksi kesalahan, dan menjelaskan informasi tarif maksimum di mana komunikasi yang dapat diandalkan mungkin melalui saluran yang memiliki probabilitas kesalahan tertentu atau rasio signal-to-noise (SNR). Batas atas ketat ini dinyatakan dalam hal kapasitas saluran. Lebih khusus, teorema ini mengatakan bahwa terdapat kode yang seperti pengkodean panjang dengan meningkatnya kemungkinan kesalahan pada saluran memoryless diskrit dapat dibuat sewenang-wenang kecil, menyatakan bahwa tarif kode lebih kecil dari kapasitas saluran. Tingkat kode didefinisikan sebagai fraksi k / n simbol sumber k dan n simbol dikodekan.
Kode tingkat maksimum aktual diperbolehkan tergantung pada kode kesalahan-koreksi yang digunakan, dan mungkin lebih rendah. Hal ini karena bukti Shannon hanya alam eksistensial, dan tidak menunjukkan bagaimana untuk membangun kode yang baik optimal dan efisien encoding dan decoding algoritma.
Hybrid ARQ adalah kombinasi ARQ dan forward error correction. Ada dua pendekatan dasar [2]:
Pesan * selalu ditransmisikan dengan data paritas FEC (dan redundansi kesalahan deteksi). Sebuah penerima decodes pesan menggunakan informasi paritas, dan pengiriman ulang permintaan menggunakan ARQ hanya jika data paritas tidak cukup untuk decoding sukses (diidentifikasi melalui pemeriksaan integritas gagal).
Pesan * ditularkan tanpa data paritas (hanya dengan kesalahan-deteksi informasi). Jika sebuah penerima mendeteksi kesalahan, maka permintaan FEC informasi dari pemancar menggunakan ARQ, dan menggunakannya untuk merekonstruksi pesan asli.
Pendekatan terakhir ini sangat menarik di saluran penghapusan bila menggunakan kode penghapusan rateless.
Aplikasi yang membutuhkan latency rendah (seperti percakapan telepon) tidak dapat menggunakan Otomatis permintaan Ulangi (ARQ), mereka harus menggunakan Forward Error Correction (FEC). Pada saat sistem ARQ menemukan kesalahan dan mengirimkan kembali itu, data yang dikirimkan kembali akan tiba terlambat untuk menjadi apapun yang baik.
Aplikasi mana pemancar segera lupa informasi segera setelah dikirim (seperti kamera televisi yang paling) tidak dapat menggunakan ARQ, mereka harus menggunakan FEC karena ketika kesalahan terjadi, data asli tidak lagi tersedia. (Ini juga mengapa FEC digunakan dalam sistem penyimpanan data seperti RAID dan didistribusikan menyimpan data).
Aplikasi yang menggunakan ARQ harus memiliki saluran kembali. Aplikasi yang tidak memiliki saluran kembali tidak dapat menggunakan ARQ.
Aplikasi yang membutuhkan tingkat kesalahan sangat rendah (seperti transfer uang digital) harus menggunakan ARQ.
Referensi;

Tidak ada komentar: