Jumat, 21 Mei 2010 di 08.26 Diposkan oleh arytresna 0 Comments

Dalam teori informasi dan pengkodean teori dengan aplikasi dalam ilmu komputer dan telekomunikasi, deteksi error dan koreksi atau kontrol kesalahan adalah teknik yang memungkinkan pengiriman data digital yang handal melalui saluran komunikasi tidak bisa diandalkan. Banyak saluran komunikasi tunduk pada saluran kebisingan, dan dengan demikian kesalahan mungkin diperkenalkan selama transmisi dari sumber ke penerima. teknik deteksi kesalahan mendeteksi Kesalahan memungkinkan seperti, sementara koreksi kesalahan memungkinkan rekonstruksi data asli.

Definisi umum dari istilah adalah sebagai berikut:
* Deteksi Kesalahan adalah deteksi kesalahan yang disebabkan oleh kebisingan atau gangguan lain selama transmisi dari transmitter ke receiver [1].
* Koreksi Kesalahan adalah deteksi kesalahan dan rekonstruksi, data asli bebas dari kesalahan.
Koreksi kesalahan umumnya dapat direalisasi dalam dua cara berbeda:
* Otomatis mengulang permintaan (ARQ) (kadang-kadang juga disebut sebagai mundur koreksi kesalahan): ini merupakan kendali kesalahan teknik dimana skema deteksi error dikombinasikan dengan permintaan untuk pengiriman ulang data yang salah. Setiap blok data yang diterima diperiksa menggunakan kode kesalahan deteksi digunakan, dan jika memeriksa gagal, transmisi kembali data yang diminta - ini dapat dilakukan berulang kali, sampai data dapat diverifikasi.
* Forward koreksi kesalahan (FEC): Pengirim mengkodekan data menggunakan kode error-correcting (ECC) sebelum transmisi. Informasi tambahan (redundancy) ditambahkan oleh kode ini digunakan oleh penerima untuk memulihkan data asli. Secara umum, data direkonstruksi adalah apa yang dianggap paling "mungkin" data asli.
ARQ dan FEC dapat digabungkan, sehingga kesalahan kecil diperbaiki tanpa transmisi, dan kesalahan utama dikoreksi melalui permintaan untuk pengiriman ulang: ini disebut hibrida otomatis mengulang-permintaan (HARQ).
Isi .

* 1 Pendahuluan
* Skema deteksi 2 Kesalahan
o 2,1 kode Pengulangan
o 2,2 Paritas bit
o 2,3 Checksum
2,4 o cek redundansi siklik (CRC)
2,5 o fungsi hash Cryptographic
2,6 o Kesalahan-kode koreksi
* 3 Kesalahan koreksi
o 3,1 Otomatis ulangi permintaan
3,2 o Kesalahan-kode koreksi
o 3,3 Hybrid skema
* 4 Aplikasi
4,1 o Internet
4,2 o Deep-ruang telekomunikasi
o 4,3 penyiaran satelit (DVB)
o penyimpanan Data 4,4
o Kesalahan-koreksi 4,5 memori
* 5 Lihat juga
* 6 Catatan
* 7 Referensi
* 8 Pranala luar

Gagasan umum untuk mencapai deteksi kesalahan dan koreksi adalah dengan menambahkan beberapa redundansi (yakni, beberapa data tambahan) ke pesan, penerima yang dapat digunakan untuk memeriksa konsistensi pesan dikirimkan, dan untuk memulihkan data bertekad untuk menjadi salah. Kesalahan-deteksi dan skema koreksi dapat berupa sistematis atau non-sistematis: Dalam skema sistematis, pemancar mengirimkan data asli, dan melekat tetap jumlah bit cek (atau data paritas), yang berasal dari bit data dengan beberapa algoritma deterministik. Jika deteksi kesalahan hanya diperlukan, penerima hanya dapat menerapkan algoritma yang sama dengan bit data yang diterima dan membandingkan outputnya dengan memeriksa bit diterima, jika nilai tidak cocok, kesalahan telah terjadi di beberapa titik selama transmisi. Dalam sistem yang menggunakan kode non-sistematis pesan asli diubah menjadi pesan disandikan yang setidaknya sama banyak bit pesan asli.
Kesalahan kinerja yang baik memerlukan skema kontrol yang akan dipilih berdasarkan karakteristik saluran komunikasi. model saluran umum meliputi memori-kurang model mana kesalahan terjadi secara acak dan dengan probabilitas tertentu, dan model dinamis di mana kesalahan terjadi terutama dalam semburan. Akibatnya, kesalahan-mendeteksi dan memperbaiki kode secara umum dapat dibedakan antara random-error-detecting/correcting dan burst-error-detecting/correcting. Beberapa kode juga dapat cocok untuk campuran dari kesalahan acak dan kesalahan meledak.
Jika kapasitas saluran tidak dapat ditentukan, atau sangat bervariasi, skema-deteksi kesalahan dapat digabungkan dengan sistem transmisi ulang data yang salah. Hal ini dikenal sebagai permintaan mengulang otomatis (ARQ), dan terutama digunakan di Internet. Sebuah pendekatan alternatif untuk pengendalian kesalahan hibrida mengulang permintaan otomatis (HARQ), yang merupakan kombinasi dari ARQ dan koreksi kesalahan coding.
Kesalahan deteksi umumnya direalisasikan dengan menggunakan fungsi hash yang cocok (atau algoritma checksum). Sebuah fungsi hash menambahkan tag tetap-panjang pesan, yang memungkinkan penerima untuk memverifikasi pesan yang disampaikan oleh recomputing tag dan membandingkannya dengan salah satu yang disediakan.
Ada besar ada berbagai desain fungsi hash yang berbeda. Namun, beberapa penggunaan luas terutama karena kesederhanaan mereka baik atau kesesuaian mereka untuk mendeteksi kesalahan jenis tertentu (misalnya, kinerja cek redundansi siklik dalam mendeteksi kesalahan burst).
Acak-error-correcting kode didasarkan pada jarak minimum coding dapat memberikan alternatif yang sesuai untuk fungsi hash ketika jaminan ketat pada jumlah minimal kesalahan akan dideteksi diinginkan. Pengulangan kode, dijelaskan di bawah ini, adalah contoh khusus dari kode koreksi kesalahan: meskipun agak tidak efisien, mereka menemukan aplikasi untuk kedua koreksi kesalahan dan deteksi karena kesederhanaan mereka.
Sebuah kode pengulangan merupakan skema pengkodean yang mengulangi bit di saluran komunikasi untuk mencapai bebas dari kesalahan. Mengingat aliran data yang akan dikirim, data dibagi menjadi blok bit. Setiap blok ditransmisikan beberapa kali jumlah yang telah ditetapkan. Misalnya, untuk mengirim pola bit "1011", blok empat-bit dapat diulang tiga kali, sehingga menghasilkan "1011 1011 1011". Namun, jika pola dua belas-bit telah diterima sebagai "1010 1011 1011" - dimana blok pertama adalah tidak seperti dua lainnya - dapat ditentukan bahwa kesalahan telah terjadi.
Pengulangan kode tidak sangat efisien, dan dapat rentan terhadap masalah jika kesalahan terjadi di tempat yang sama persis untuk setiap kelompok (misalnya, "1010 1010 1010" pada contoh sebelumnya akan terdeteksi sebagai benar). Keuntungan dari kode pengulangan adalah bahwa mereka sangat sederhana, dan sebenarnya digunakan di beberapa stasiun transmisi nomor [rujukan?].
A bit paritas adalah sedikit yang ditambahkan ke sekelompok bit sumber untuk memastikan bahwa jumlah bit-bit (yaitu bit dengan nilai 1) dalam hasilnya genap atau ganjil. Ini adalah skema yang sangat sederhana yang dapat digunakan untuk mendeteksi tunggal atau angka ganjil lainnya (yaitu, tiga, lima, dll) kesalahan dalam output. Bahkan jumlah membalik bit akan membuat bit paritas muncul benar meskipun data tersebut salah.
Extensions dan variasi pada mekanisme bit paritas adalah cek redundansi horizontal, cek redundansi vertikal, dan "ganda," "ganda," atau "diagonal" paritas (digunakan dalam RAID-DP).
Sebuah checksum pesan adalah jumlah aritmatika modular kata-kata kode pesan panjang kata yang tetap (misalnya, nilai byte). Jumlahnya mungkin dinegasikan melalui sebuah one's-melengkapi sebelum transmisi untuk mendeteksi kesalahan yang menyebabkan semua-nol pesan.
skema Checksum termasuk bit paritas, digit cek, dan cek redundansi longitudinal. skema checksum Beberapa, seperti algoritma Luhn dan algoritma Verhoeff, secara khusus dirancang untuk mendeteksi kesalahan umum diperkenalkan oleh manusia dalam menulis atau mengingat nomor identifikasi.
Sebuah cek redundansi siklik (CRC) adalah kode siklik tunggal-meledak-kesalahan mendeteksi dan hash aman non-fungsi yang dirancang untuk mendeteksi perubahan kecelakaan pada data digital dalam jaringan komputer. Hal ini ditandai dengan spesifikasi dari generator polinomial disebut, yang digunakan sebagai pembagi dalam divisi panjang polinomial atas lapangan terbatas, mengambil data input sebagai dividen, dan di mana sisanya menjadi hasilnya.
kode siklik memiliki sifat yang menguntungkan dalam bahwa mereka sangat cocok untuk mendeteksi kesalahan burst. CRC sangat mudah diimplementasikan dalam perangkat keras, dan karena itu umum digunakan dalam jaringan digital dan perangkat penyimpanan seperti hard disk drive.
Bahkan paritas adalah kasus khusus dari cek redundansi siklik, di mana bit-tunggal CRC dihasilkan oleh pembagi x +1.
Sebuah fungsi hash kriptografi dapat menyediakan jaminan yang kuat tentang data integritas, asalkan perubahan data hanya kebetulan (yaitu, akibat kesalahan transmisi). Setiap modifikasi data kemungkinan akan terdeteksi melalui nilai hash mismatching. Selanjutnya, mengingat beberapa nilai hash, adalah layak untuk menemukan data input beberapa (lain dari yang diberikan) yang akan menghasilkan nilai hash yang sama. kode otentikasi pesan, juga disebut menekan tombol fungsi hash kriptografi, memberikan perlindungan tambahan terhadap modifikasi yang disengaja oleh penyerang.
[Sunting] Kesalahan-kode koreksi
Setiap kode error-correcting dapat digunakan untuk mendeteksi kesalahan. Sebuah kode dengan jarak Hamming minimum, d, dapat mendeteksi sampai dengan d-1 kesalahan dalam sebuah kata kode. Menggunakan jarak minimum berbasis mengoreksi kesalahan-kesalahan kode untuk deteksi bisa cocok jika batas ketat pada jumlah minimum kesalahan akan dideteksi diinginkan.
Kode dengan jarak Hamming minimum d = 2 adalah merosot kasus-kode koreksi kesalahan, dan dapat digunakan untuk mendeteksi kesalahan tunggal. Bit paritas adalah contoh dari satu kode-kesalahan-deteksi.
Kode Berger adalah contoh awal kesalahan searah (mengoreksi) kode yang dapat mendeteksi sejumlah kesalahan pada saluran asimetris, asalkan hanya transisi bit dibersihkan untuk mengatur atau set bit bit bit untuk dibersihkan dapat terjadi.
Ulangi otomatis permintaan (ARQ) merupakan kendali kesalahan metode untuk transmisi data yang menggunakan kode kesalahan-deteksi, pengakuan dan / atau negatif pesan pengakuan, dan timeout untuk mencapai transmisi data yang dapat diandalkan. Sebuah pengakuan adalah pesan yang dikirim oleh penerima untuk mengindikasikan bahwa telah benar menerima frame data.
Biasanya, ketika pemancar tidak menerima pengakuan sebelum timeout terjadi (yaitu, dalam jumlah yang wajar waktu setelah mengirimkan bingkai data), itu frame mentransmisikan kembali sampai benar baik diterima atau kesalahan masih melampaui jumlah yang telah ditetapkan retransmisi .
Tiga jenis protokol ARQ adalah Stop-dan-tunggu ARQ, Go-Back-N ARQ, dan ARQ Ulangi Selektif.
ARQ sesuai jika saluran komunikasi memiliki kapasitas yang bervariasi atau tidak dikenal, seperti yang terjadi di Internet. Namun, ARQ memerlukan ketersediaan saluran kembali, hasil di latency mungkin meningkat karena retransmisi, dan membutuhkan pemeliharaan buffer dan timer untuk transmisi ulang, yang dalam kasus kepadatan jaringan dapat menempatkan beban pada server dan kapasitas jaringan secara keseluruhan. [2]
Kode error-correcting (ECC) atau forward error correction (FEC) kode program merupakan suatu sistem menambahkan data berlebihan, atau data paritas, pesan, seperti yang dapat ditemukan oleh penerima bahkan ketika sejumlah kesalahan (sampai kemampuan kode yang sedang digunakan) diperkenalkan, baik selama proses transmisi, atau pada penyimpanan. Sejak penerima tidak harus meminta pengirim untuk transmisi data, back-saluran tidak diperlukan di forward error correction, dan oleh karena itu cocok untuk komunikasi simpleks seperti penyiaran. Error-correcting kode ini sering digunakan dalam komunikasi bawah-lapisan, serta untuk penyimpanan yang dapat diandalkan di media seperti CD, DVD, hard disk, dan RAM.




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.
Dalam TCP khas / IP stack, error control dilakukan di beberapa tingkatan:
* Setiap frame Ethernet membawa CRC-32 checksum. Frame yang diterima dengan checksum yang salah akan dibuang oleh perangkat keras penerima.
* Header IPv4 berisi checksum melindungi isi header. Paket dengan mismatching checksum yang menjatuhkan dalam jaringan atau di penerima.
* Checksum itu dihilangkan dari header IPv6 untuk meminimalkan biaya pemrosesan pada jaringan routing dan karena link lapisan teknologi saat ini diasumsikan untuk menyediakan deteksi kesalahan yang cukup (lihat juga RFC 3819).
* UDP memiliki pilihan checksum yang meliputi payload dan informasi pengalamatan dari header UDP dan IP. Paket dengan checksum yang salah akan dibuang oleh jaringan sistem operasi stack. checksum bersifat opsional dalam IPv4, hanya, karena lapisan checksum IP sudah dapat menyediakan tingkat perlindungan yang diinginkan kesalahan.
* TCP menyediakan checksum untuk melindungi payload dan menyikapi informasi dari header TCP dan IP. Paket dengan checksum yang salah akan dibuang dalam jaringan stack, dan akhirnya mendapatkan dipancarkan kembali menggunakan ARQ, baik secara eksplisit (seperti melalui triple-Jack) atau secara implisit karena timeout.
Pengembangan kode koreksi kesalahan-erat disertai dengan sejarah-misi dalam ruang karena pengenceran ekstrim kekuatan sinyal jarak antarplanet, dan ketersediaan daya terbatas naik pesawat antariksa. Sedangkan misi awal mereka uncoded mengirim data, mulai dari tahun 1968 koreksi kesalahan digital diimplementasikan dalam bentuk (sub-optimal decode) konvolusional kode dan kode Reed-Muller. [3] Kode Reed-Muller sangat cocok untuk kebisingan pesawat tunduk pada (kira-kira yang cocok dengan kurva Bell), dan dilaksanakan pada pesawat ruang angkasa Mariner untuk misi antara tahun 1969 dan 1977.
Voyager 1 dan Voyager 2 misi, yang dimulai pada tahun 1977, yang dirancang untuk memberikan pencitraan warna antara informasi ilmiah dari Jupiter dan Saturnus [4] Hal ini mengakibatkan persyaratan coding meningkat,. Dan dengan demikian spacecrafts didukung oleh (optimal Viterbi-decode) konvolusional kode yang bisa concatenated dengan Golay luar (24,12,8) kode. Voyager 2 probe tambahan mendukung implementasi dari kode Reed-Solomon: di concatenated Reed-Solomon-Viterbi (RSV) kode diperbolehkan untuk koreksi kesalahan yang sangat kuat, dan memungkinkan diperpanjang perjalanan pesawat ruang angkasa ke Uranus dan Neptunus.
The CCSDS saat ini merekomendasikan penggunaan kode koreksi kesalahan dengan kinerja yang sama dengan kode 2 Voyager RSV sebagai minimum. kode Concatenated semakin jatuh dari nikmat dengan misi luar angkasa, dan akan diganti dengan kode yang lebih kuat, seperti kode Turbo atau kode LDPC.
Berbagai jenis ruang dalam dan misi orbital yang dilakukan menunjukkan bahwa mencoba untuk menemukan "satu ukuran cocok untuk semua" kesalahan sistem koreksi akan menjadi masalah yang sedang berlangsung untuk beberapa waktu ke depan. Untuk misi dekat ke bumi sifat saluran suara yang berbeda dari sebuah pesawat ruang angkasa pada pengalaman misi antarplanet. Selain itu, sebagai sebuah pesawat ruang angkasa meningkatkan jarak dari bumi, masalah mengoreksi untuk kebisingan semakin besar.
Permintaan bandwidth transponder satelit terus berkembang, didorong oleh keinginan untuk memberikan televisi (termasuk saluran-saluran baru dan High Definition TV) dan data IP. Transponder ketersediaan dan keterbatasan bandwidth yang telah membatasi pertumbuhan ini, karena kapasitas transponder ditentukan oleh skema modulasi yang dipilih dan Forward koreksi kesalahan (FEC) tingkat.
Ikhtisar
* QPSK digabungkan dengan Salomo Reed tradisional dan kode Viterbi telah digunakan selama hampir 20 tahun untuk pengiriman TV satelit digital.
* Skema modulasi order tinggi seperti 8PSK, 16QAM dan 32QAM telah memungkinkan industri transponder satelit untuk meningkatkan efisiensi dengan beberapa kali lipat.
* Peningkatan tingkat informasi dalam transponder datang dengan mengorbankan peningkatan daya pembawa untuk memenuhi persyaratan ambang batas untuk antena yang ada.
* Pengujian dilakukan dengan menggunakan chipset terbaru menunjukkan bahwa kinerja dicapai dengan menggunakan Turbo Codes mungkin bahkan lebih rendah daripada angka 0.8 dB diasumsikan dalam desain awal.
Kesalahan deteksi dan koreksi kode sering digunakan untuk meningkatkan keandalan media penyimpanan data.
Sebuah lagu paritas "" hadir pada penyimpanan data pita magnetik pertama pada tahun 1951. The "optimal Persegi Kode" digunakan dalam kaset rekaman grup mendeteksi kode tidak hanya tetapi juga mengoreksi kesalahan bit tunggal.
Beberapa format file, terutama format arsip, termasuk checksum (paling sering CRC32) untuk mendeteksi korupsi dan pemotongan dan dapat mempekerjakan redundansi dan / atau file paritas untuk memulihkan bagian data rusak.
Reed Solomon kode digunakan dalam compact disc untuk memperbaiki kesalahan yang disebabkan oleh goresan.
Modern hard drive menggunakan kode CRC untuk mendeteksi dan kode Reed-Solomon untuk memperbaiki kesalahan kecil di sektor dibaca, dan untuk memulihkan data dari sektor yang telah "pergi buruk" dan menyimpan data di sektor cadang .
sistem RAID menggunakan berbagai teknik koreksi kesalahan, untuk memperbaiki kesalahan ketika harddisk benar-benar gagal.
memori DRAM dapat memberikan peningkatan perlindungan terhadap kesalahan yang lembut dengan mengandalkan kode koreksi kesalahan. memori kesalahan-koreksi tersebut, dikenal sebagai ECC atau memori EDAC-dilindungi, terutama diinginkan untuk aplikasi toleransi kegagalan tinggi, seperti server, serta sedalam-ruang aplikasi karena radiasi meningkat.
Kesalahan-koreksi kontroler memori tradisional menggunakan kode Hamming, redundansi meskipun menggunakan beberapa modular triple.
Interleaving memungkinkan mendistribusikan pengaruh sinar kosmik tunggal yang berpotensi mengganggu tetangga beberapa bit secara fisik di beberapa kata dengan menghubungkan bit tetangga untuk kata-kata yang berbeda. Selama satu aktivitas marah (Seu) tidak melebihi ambang batas kesalahan (misalnya, kesalahan tunggal) dalam setiap kata tertentu antara akses, dapat dikoreksi (misalnya, oleh satu kesalahan-bit koreksi code), dan ilusi sistem memori kesalahan-bebas dapat dipertahankan.

Reaksi: 

0 Responses so far.

Poskan Komentar