Kode koreksi kesalahan dijelaskan

Tidak ada kanal yang sempurna. Sinar kosmik membalik bit di memori, goresan menghapus bagian cakram, dan sinyal radio memudar. Alih-alih berharap yang terbaik, sistem digital menambahkan redundansi dengan cara yang cerdas, sehingga penerima dapat mengetahui apa yang dikirim meskipun sebagian tiba dalam keadaan salah. Matematika kode-kode ini, yang dimulai pada akhir 1940-an, diam-diam melindungi hampir setiap bit yang kita simpan atau kirim.

Tiga lingkaran yang saling tumpang tindih berisi tujuh bit kata kode Hamming, dengan satu lingkaran disorot di tempat pemeriksaan paritas gagal
Tiga lingkaran yang saling tumpang tindih berisi tujuh bit kata kode Hamming, dengan satu lingkaran disorot di tempat pemeriksaan paritas gagal

Mendeteksi kesalahan dengan paritas

Perlindungan paling sederhana adalah satu bit paritas: tambahkan 1 atau 0 sehingga jumlah total angka 1 genap. Jika satu bit terbalik di perjalanan, jumlahnya menjadi ganjil dan penerima tahu ada yang salah. Paritas tidak dapat mengatakan bit mana yang salah, dan dua pembalikan saling meniadakan tanpa terdeteksi, tetapi paritas murah dan digunakan selama puluhan tahun dalam memori dan sambungan serial. Namun, mendeteksi kesalahan baru separuh pekerjaan: setelah itu data harus dikirim ulang.

Mengoreksi dengan pengulangan

Untuk mengoreksi kesalahan tanpa meminta ulang, penerima membutuhkan cukup redundansi untuk mengalahkannya dalam pemungutan suara. Mengirim setiap bit tiga kali, 000 atau 111, memungkinkan penerima mengambil suara terbanyak: satu pembalikan dalam satu kelompok tiga dikoreksi. Harganya mahal: tiga bit untuk setiap bit data, dan dua pembalikan dalam kelompok tiga yang sama tetap menang. Pertanyaan yang memulai teori pengodean adalah apakah ada cara yang lebih baik.

Kode Hamming

Pada tahun 1947 Richard Hamming bekerja di Bell Labs dengan komputer relai yang membaca program dari kartu berlubang. Ketika menemukan kesalahan pada akhir pekan, komputer itu langsung berhenti, dan Hamming kembali pada hari Senin hanya untuk mendapati proses yang sia-sia. Jika mesin dapat mendeteksi kesalahan, tanyanya, mengapa ia tidak dapat menemukan letaknya dan mengoreksinya? Jawabannya, yang diterbitkan pada tahun 1950, mengirim 4 bit data sebagai 7. Tiga bit paritas, di posisi 1, 2, dan 4, masing-masing memeriksa kelompok posisi berbeda yang saling tumpang tindih, dipilih sedemikian rupa sehingga setiap kesalahan tunggal merusak kombinasi pemeriksaan yang unik.

Sindrom

Penerima menghitung ulang ketiga pemeriksaan. Jika semuanya lolos, kata itu diterima. Jika ada yang gagal, menuliskan pemeriksaan yang gagal sebagai digit biner, dengan pemeriksaan 4 sebagai digit tertinggi, menghasilkan bilangan dari 1 sampai 7: sindrom, yang tepat sama dengan posisi bit yang terbalik. Membaliknya kembali memulihkan kata kode. Trik ini berhasil karena posisi-posisinya diberi nomor sedemikian rupa sehingga ekspansi biner masing-masing mendaftar pemeriksaan tempat ia berada, itulah sebabnya kode ini tampak begitu rapi ketika digambar sebagai tiga lingkaran yang saling tumpang tindih.

Jarak Hamming

Jarak Hamming antara dua kata adalah jumlah posisi tempat keduanya berbeda. Dalam kode (7,4), dua kata kode mana pun berjarak setidaknya 3. Kata dengan satu kesalahan masih berjarak 1 dari kata kode yang dikirim dan setidaknya 2 dari setiap kata kode lain, sehingga mendekode ke kata kode terdekat akan mengoreksinya. Secara umum, kode yang kata-kata kodenya berjarak setidaknya d mendeteksi d − 1 kesalahan dan mengoreksi (d − 1)/2 di antaranya, dibulatkan ke bawah. Menambahkan bit paritas keseluruhan menaikkan jaraknya menjadi 4, menghasilkan kode yang diperluas yang mengoreksi satu kesalahan dan mendeteksi dua.

Batas Shannon

Pada tahun 1948, dua tahun sebelum makalah Hamming, Claude Shannon membuktikan sebuah teorema yang mengejutkan. Setiap kanal berderau memiliki kapasitas, dan data dapat dikirim pada laju berapa pun di bawahnya dengan kesalahan sesedikit yang diinginkan, dengan menggunakan kode yang cukup panjang; di atasnya, kesalahan tidak dapat dihindari. Shannon menunjukkan bahwa kode semacam itu ada, tetapi tidak bagaimana membangunnya. Menemukan kode praktis yang mendekati batasnya membutuhkan setengah abad, dari kode Reed-Solomon pada tahun 1960 hingga kode turbo pada tahun 1993 dan penemuan kembali kode low-density parity-check.

Claude Shannon, yang pada 1948 di Bell Labs merinci berapa banyak informasi yang dikandung sebuah pesan dan mengukurnya dalam bit.
Claude Shannon, yang pada 1948 di Bell Labs merinci berapa banyak informasi yang dikandung sebuah pesan dan mengukurnya dalam bit.

Kode di sekitar kita

Kode Reed-Solomon memungkinkan CD tetap berputar meski tergores dan kode QR tetap terpindai meski hingga 30% simbolnya rusak. Memori server menggunakan kode Hamming yang diperluas untuk memperbaiki bit tunggal yang terbalik akibat sinar kosmik. Foto planet-planet luar dari Voyager dilindungi oleh kode Golay dan kemudian kode Reed-Solomon, sementara kode LDPC dan kode polar pada 5G dan Wi-Fi memeras hampir setiap bit yang diizinkan kanal. Bahkan kode batang pada buku dan digit terakhir nomor rekening bank adalah kode pendeteksi kesalahan sederhana.

Jelajahi

Buka simulator kode koreksi kesalahan untuk mengodekan empat bit data apa pun dengan kode Hamming (7,4), membalik bit dengan mengkliknya di lingkaran atau di baris, dan menyaksikan lingkaran yang gagal serta sindrom menunjuk ke kesalahan sebelum dekoder memperbaikinya. Nyalakan bit paritas tambahan untuk melihat kesalahan ganda terdeteksi, dan kirim pesan melalui kanal berderau untuk membandingkan apa yang tiba dengan dan tanpa kode.

Pertanyaan yang sering diajukan

Apa perbedaan antara deteksi kesalahan dan koreksi kesalahan?

Deteksi hanya memberi tahu penerima bahwa ada yang salah, sehingga penerima harus meminta data itu lagi; bit paritas atau checksum melakukan hal ini. Koreksi memungkinkan penerima merekonstruksi data asli tanpa meminta ulang, yang membutuhkan lebih banyak redundansi. Sistem yang tidak dapat meminta ulang, seperti wahana antariksa yang berjarak jutaan kilometer atau DVD, mengandalkan koreksi.

Mengapa tidak mengirim semuanya dua kali saja?

Dua salinan menunjukkan bahwa kesalahan terjadi tetapi tidak menunjukkan salinan mana yang benar, dan biayanya menjadi dua kali lipat. Tiga salinan memungkinkan pemungutan suara terbanyak tetapi biayanya menjadi tiga kali lipat. Kode Hamming mengoreksi satu kesalahan per blok tujuh bit dengan jumlah bit kurang dari dua kali lipat, dan kode yang lebih panjang jauh lebih baik lagi.

Siapa Richard Hamming?

Seorang matematikawan Amerika, 1915 sampai 1998, yang bekerja pada Proyek Manhattan dan kemudian selama tiga puluh tahun di Bell Labs. Selain kodenya, ia dikenal karena jendela Hamming dalam pemrosesan sinyal, jarak Hamming, dan kuliahnya yang berjudul You and Your Research. Ia menerima Penghargaan Turing pada tahun 1968.

Dapatkah sebuah kode mengoreksi kesalahan dalam jumlah berapa pun?

Hanya dengan redundansi yang cukup. Sebuah kode dapat mengoreksi hingga (d − 1)/2 kesalahan per blok, dengan d adalah jarak minimum antara kata-kata kode, dan kode yang lebih panjang dengan lebih banyak bit pemeriksa mencapai d yang lebih besar. Teorema Shannon menetapkan batas tertinggi: tidak ada kode yang dapat melampaui kapasitas kanal.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Buka simulator kode koreksi kesalahan