Error Detection and Correction

Fahmi Herlambang

1701339964

Error Detection and Correction

Pentransmisian data dalam jaringan terdapat kemungkinan terjadinya data corrupt atau error yang disebabkan berbagai faktor yang mengubah satu atau lebih bit dari data yang ditransfer, karena itulah sistem membutuhkan adanya mekanisme deteksi dan koreksi error.

Tipe-Tipe Error

Ketika terjadi arus data dari satu poin ke poin laiinua dapat terjadi perubahan yang tidak diprediksi yang disebabkan interference, interference ini beerperan mengubah bentuk dari signal.

Single-bit error ialah ketika terdapat 1 bit yang berubah dari 0 ke 1 atau sebaliknya.

Burst error ialah error yang ketika 2 atau lebih bit yang berubah dari 1 ke 0 atau sebaliknya.

Redudansi

Konsep utama dari deteksi dan koreksi error ialah redudansi, dengan redudansi kita dapat mengecek error dengan cara menambahkan bit pada saat mengirim dan mengurangi bit saat diterima untuk dapat diperiksa kesalahannya.

Block Coding

Dalam block coding kita memisahkan pesan atau data kedalam suatu blok yang dikenal dengan datawards.Cyclic Redudancy Check

Kita dapat membuat cyclic code untuk mengkoreksikan error. Subset dari cyclic code yang digunakan ialah CRC (Cyclic Redudancy Check) yang biasa dipakai dalam LAN dan WAN.

Dalam encoder, codeword memiliki k bit (4 di sini); codeword memiliki n bit (7 di sini). Ukuran codeword ini ditambah dengan menambahkan n - k (3 disini) Os ke sisi kanan kata. Hasil n-bit dimasukkan ke generator. Generator menggunakan pembagi ukuran n - k + 1 (4 di sini), yang telah ditetapkan dan disepakati. Generator membagi codeword augmented oleh pembagi (modulo-2 divisi). Hasil bagi divisi tersebut akan dibuang, sisanya (r2rlrO) ditambahkan ke codeword untuk membuat codeword.

Decoder menerima codeword (mungkin rusak dalam masa transisi). Salinan semua n bit diumpankan ke checker, yang merupakan replika dari generator. Sisanya diproduksi oleh checker adalah sindrom n - k (3 di sini) bit, yang diumpankan ke logika keputusan analyzer. Analisa ini memiliki fungsi sederhana. Jika bit sindrom all-Os, 4 bit paling kiri dari codeword diterima sebagai codeword (diartikan sebagai tidak ada kesalahan); jika tidak, 4 bit yang dibuang (error).

- Encoder

Encoder mengambil codeword dan menambah dengan n - jumlah k dari Os. Kemudian membagi ditambah codeword oleh pembagi, seperti yang ditunjukkan pada Gambar 10.6.

Proses modulo-2 divisi biner adalah sama dengan proses pembagian yang kita gunakan untuk angka desimal. Namun, penambahan dan pengurangan dalam hal ini adalah sama, kita menggunakan operasi XOR untuk melakukan keduanya.

Seperti dalam pembagian desimal, proses ini dilakukan secara bertahap. Dalam setiap langkah, salinan pembagi di XOR kan dengan 4 bit dividen. Hasil operasi XOR (Sisanya) adalah 3 bit (dalam hal ini), yang digunakan untuk langkah berikutnya setelah 1 extra bit ditarik ke bawah untuk membuatnya 4 bit. Ada satu hal penting yang perlu kita ingat dalam jenis divisi. Jika bit paling kiri dari dividen (atau bagian yang digunakan dalam setiap langkah) adalah 0, langkah tidak dapat menggunakan pembagi biasa, kita perlu menggunakan pembagi all-Os.

Ketika tidak ada bit yang tersisa untuk pull down, kita memiliki hasilnya. 3-bit sisanya membentuk bit cek (r2 'rl, dan ro), lalu ditambahkan ke codeword untuk membuat codeword.

- Decoder

Codeword dapat berubah selama masa transmisi. Decoder melakukan pembagian yang sama seperti proses encoder. Sisa dari pembagian itu disebut sindrom. Jika sindrom itu all-Os, maka tidak ada kesalahan yang terjadi, codeword dipisahkan dari codeword yang diterima dan diterima oleh receiver. Jika tidak, semuanya akan dibuang dikarenakan adanya error.

Polinomial

Cara yang lebih baik untuk memahami kode siklik dan bagaimana dapat dianalisis adalah dengan membuatnya menjadi polinomial.

Pola Os dan 1s dapat direpresentasikan sebagai polinomial dengan koefisien 0 dan 1. kekuatan masing-masing istilah menunjukkan posisi bit, koefisien menunjukkan nilai bit. Gambar 10.8 menunjukkan pola biner dan representasi polinomial tersebut. Pada Gambar 1O.8a kita menunjukkan bagaimana menerjemahkan pola biner ke polinomial; pada Gambar 1O.8b kami menunjukkan bagaimana polinom dapat dipersingkat dengan menghapus semua persyaratan dengan koefisien nol dan mengganti xl oleh x dan xO oleh

- Tingkat Polinomial

Tingkat atau derajat polinomial adalah kekuatan tertinggi di polinomial. Sebagai contoh, derajat polinomial x6 + x + 1 adalah 6. Perhatikan bahwa derajat polinomial adalah kurang 1 dari jumlah bit dalam pola. Pola bit dalam hal ini memiliki 7 bit.

Forward Error CorrectionKetika terjadi error pada multimedia yang bersifat real-time dibutuhkan tehnik agar data yang dikirimkan tidak terjadi pengulanan pengiriman ataupun delay, salah satu caranya ialah dengan teknik forward error correction, berikut beberapa pengaplikasian dari FEC.

Hamming Distance

Untuk mendeteksi error jarak yang dibutuhkan ialah lebih dari dmin = S + 1. Hal ini menunjukkan bahwa untuk mendeteksi kesalahan t, kita perlu memiliki dalam = 2t + 1. Dengan kata lain, jika kita ingin memperbaiki 10 bit dalam paket, kita perlu membuat jarak Hamming minimum 21 bit, yang berarti banyak bit redundant perlu dikirim dengan data. Untuk memberikan contoh, perhatikan kode BCH terkenal. Dalam kode ini, jika data 99 bit, kita perlu mengirim 255 bit (tambahan 156 bit) untuk memperbaiki hanya 23 bit kesalahan yang mungkin. Sebagian besar waktu kita tidak mampu redundansi tersebut.

XOR

Dengan menerapkan exclusive-OR operasi pada item N data (PI ke PN), kita dapat membuat salah satu item data dengan melakukan XOR pada semua item, mengganti satu yang akan dibuat oleh hasil sebelumnya operasi (R). Ini berarti bahwa kita dapat membagi paket ke N potongan, menciptakan eksklusif OR semua potongan dan mengirim potongan N1. Jika potongan apapun hilang atau rusak, dapat dibuat di lokasi penerima. Sekarang pertanyaannya adalah apa yang harus nilai N menjadi. Jika N = 4, itu berarti bahwa kita perlu mengirim 25 persen data tambahan dan dapat memperbaiki data jika hanya satu dari empat potongan hilang.

Retransmission

Inti dari mekanisme kontrol error adalah transmisi segmen. Ketika segmen dikirim, ia akan disimpan dalam antrian sampai dikenal. Ketika timer transmisi berakhir atau ketika pengirim menerima tiga duplikat ACK untuk segmen pertama dalam antrian, segmen tersebut akan dikembalikan.

- Transmisi setelah RTO

Pengiriman TCP mempertahankan satu timeout pengiriman ulang (RTO) untuk setiap koneksi. Ketika waktu jatuh tempo, yaitu kali keluar, TCP akan mengirim ulang segmen di depan antrian (segmen dengan nomor urut terkecil) dan merestart timer.

Perhatikan bahwa lagi kita asumsikan Sf