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.
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.
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:
Posting Komentar