Bell Labs, 1947
Richard Hamming bergabung dengan Bell Telephone Laboratories pada tahun 1946. Komputer relay di sana hanya berjalan pada hari kerja, ketika teknisi dapat menghidupkan ulang mereka setelah kesalahan. Akhir pekan, mesin berhenti setiap kali ada masalah — membiarkan pekerjaan antri hingga hari Senin.
Hamming marah. 'Jika mesin dapat mendeteksi kesalahan,' pikirnya, 'mengapa tidak dapat mencari lokasinya dan memperbaikinya?' Frustrasi ini, digabungkan dengan pemahaman mendalam tentang aritmetika biner dan pemeriksaan paritas, mengatur panggung.
Wawasan Pertama: Kode Persegi Panjang
Ide pertama Hamming: susun bit pesan dalam persegi panjang m×n, tambahkan pemeriksaan paritas ke setiap baris & setiap kolom. Satu kesalahan menghasilkan tepat satu pemeriksaan baris yang gagal & satu pemeriksaan kolom yang gagal. Perpotongan mereka memberi nama posisi kesalahan.
Rasio redundansi: (m+1)(n+1) / mn. Kalkulus memberi tahu Anda bahwa persegi meminimalkan ini untuk ukuran pesan tetap. Tetapi ketika m & n tumbuh, kesalahan ganda menjadi lebih mungkin — pertimbangan teknik tanpa jawaban universal.
Meminimalkan Redundansi Persegi Panjang
Persegi panjang 4×4 membawa 16 bit pesan dengan 4 pemeriksaan baris & 4 pemeriksaan kolom, ditambah 1 bit paritas sudut = 9 bit pemeriksaan untuk 16 bit pesan.
Rasio redundansi: (m+1)(n+1) / mn = 25/16 ≈ 1,56.
Untuk persegi panjang 10×10: 100 bit pesan, 121 total bit, redundansi ≈ 1,21.
Sindrom sebagai Bilangan Biner
Beberapa minggu setelah wawasan kode persegi panjang, Hamming berkendara menuju New York melalui perdesaan New Jersey, secara mental meninjau kesuksesannya. Kode segitiga terjadi kepadanya — redundansi yang lebih baik. Kemudian kubus. Kemudian 4-dimensi, 5-dimensi...
Setiap dimensi ekstra meningkatkan redundansi. Hiperkubus bersisi 2 dalam dimensi n hanya menggunakan pemeriksaan paritas n+1 untuk simpul 2^n. Tetapi apakah ini optimal?
Argumen Penghitungan
Bit paritas n+1 menghasilkan sindrom: bilangan biner (n+1)-bit. Sindrom itu perlu mengidentifikasi hasil berbeda 2^n + 1: masing-masing dari posisi kesalahan 2^n, ditambah hasil khusus 'tidak ada kesalahan'.
2^(n+1) = 2·2^n — hampir cukup. Meleset dengan faktor 2. Hamming menyimpan masalah.
Wawasan Kunci
Kemudian, Hamming kembali dengan ide baru: gunakan sindrom itu sendiri sebagai bilangan biner yang menamai posisi kesalahan. Posisi 1 = biner 001, posisi 2 = biner 010, posisi 3 = biner 011, dll. Cadangkan semua-nol untuk 'tidak ada kesalahan'.
Ini mengubah sindrom dari output pemeriksaan paritas menjadi alamat. Pemeriksaan paritas dirancang untuk menghasilkan alamat yang tepat ketika bit tunggal mana pun membalik.
Merancang Kode (7,4)
Untuk kode 7-bit (3 bit paritas, 4 bit pesan), posisi 1 sampai 7 dalam biner adalah: 001, 010, 011, 100, 101, 110, 111.
Pemeriksaan paritas 1 mencakup posisi di mana bit 0 = 1: posisi 1, 3, 5, 7.
Pemeriksaan paritas 2 mencakup posisi di mana bit 1 = 1: posisi 2, 3, 6, 7.
Pemeriksaan paritas 3 mencakup posisi di mana bit 2 = 1: posisi 4, 5, 6, 7.
Bit paritas menempati posisi pangkat-2: 1, 2, 4. Bit pesan menempati sisanya: 3, 5, 6, 7.
Jika bit 6 membalik, pemeriksaan paritas 2 & 3 gagal (110 dalam biner = 6). Sindrom membaca 110 = 6. Balik posisi 6. Selesai.
Koreksi Kesalahan Tunggal, Deteksi Kesalahan Ganda
Kode Hamming (7,4) memperbaiki kesalahan tunggal. Tetapi bagaimana jika dua bit membalik? Tanpa perlindungan ekstra, decoder menerapkan aturan sindrom dan 'memperbaiki' katakode ke pesan yang salah — koreksi salah diam.
SECDED: Satu Bit Paritas Lagi
Tambahkan satu bit paritas p₀ mencakup seluruh katakode (semua 7 bit). Sekarang sindrom memiliki 4 entri: 3 pemeriksaan asli ditambah p₀.
``
old syndrome new p₀ arti
000 0 benar
000 1 kesalahan hanya pada p₀
xxx 1 kesalahan tunggal, old syndrome memberi namanya
xxx 0 kesalahan ganda — tandainya
``
Empat kasus ini lengkap. Kesalahan ganda membalik dua bit: old syndrome tidak akan membaca 000 (kedua bit bersama merusak dua pemeriksaannya), tetapi p₀ membalik dua kali dan kembali ke 0. Pola xxx + 0 tidak terbantahkan.
Mengapa SECDED Berhasil
Aturan SECDED memanfaatkan struktur modular paritas. Dengan paritas genap, flip tunggal apa pun mengubah p₀. Flip ganda apa pun meninggalkan p₀ tidak berubah. Jadi p₀ menghitung kesalahan modulo 2.
Gambar Geometris
Hamming tiba di tempat yang sama dari arah yang berbeda: geometri analitik. Wakili setiap string n-bit sebagai simpul hiperkubus n-dimensi. Flip bit tunggal menggerakkan titik satu panjang tepi sepanjang satu sumbu. Dua flip: dua tepi. Metriknya adalah jarak Hamming.
Tentukan bola Hamming dengan radius t di sekitar katakode c: semua titik dalam flip bit t dari c. Untuk koreksi kesalahan tunggal, t = 1.
Kondisi untuk koreksi kesalahan tunggal: bola dengan radius 1 di sekitar setiap pasangan katakode berbeda tidak boleh tumpang tindih. Jika tumpang tindih, kata yang diterima dalam tumpang tindih dapat memiliki katakode apa pun dan decoder gagal.
Ini diterjemahkan langsung ke jarak minimum: dua bola dengan radius 1 tidak tumpang tindih jika dan hanya jika katakode minimal 3 terpisah (d_min ≥ 3).
Kode (7,4) mencapai d_min = 3. Batas Hamming: 2^7 / (1 + 7) = 16 = 2^4. Tepat 16 katakode. Satu kode sempurna: 16 bola dengan radius 1 ubin {0,1}^7 tanpa celah atau tumpang tindih.
Penilaian Teknik
Hamming jelas: kode koreksi kesalahan melibatkan penilaian teknik, bukan matematika murni.
Panjang pesan: pesan yang lebih panjang memungkinkan pengkodean yang lebih efisien (bit paritas log n untuk n bit pesan). Tetapi pesan yang lebih panjang juga menumpuk lebih banyak kebisingan, meningkatkan risiko kesalahan ganda tergelincir melalui sebagai koreksi tunggal palsu.
Tingkat koreksi vs. deteksi: menukar satu koreksi kesalahan untuk dua deteksi kesalahan ekstra. Pemisahan optimal tergantung pada karakteristik kebisingan saluran.
Nilai pemeliharaan lapangan: seiring peralatan menjadi lebih kompleks, teknisi lapangan tidak dapat mendiagnosis setiap kegagalan dari prinsip pertama. Sistem diagnosis diri secara dramatis mengurangi keterampilan yang diperlukan untuk pemeliharaan. Hamming menyebutnya salah satu manfaat paling penting, seringkali lebih penting daripada keuntungan keandalan mentah.
Gaya: Keberuntungan Berpihak pada Pikiran yang Siap
Hamming menutup Bab 12 dengan tantangan langsung. Dia menggambarkan penemuan ini memerlukan tiga hingga enam bulan kerja, sebagian besar pada saat-saat ganjil sambil melakukan tugas utamanya di Bell Labs.
Dia mengidentifikasi tiga hal yang membuatnya mungkin:
1. Persiapan: keakraban mendalam dengan pemeriksaan paritas, aritmetika biner, & teori grup, sebelum masalah muncul.
2. Meninjau kesuksesan: secara kebiasaan mengulangi solusi masa lalu untuk menginternalisasi gaya mereka. Kode segitiga terjadi kepadanya sambil secara mental meninjau kode persegi panjang dalam perjalanan.
3. Tidak puas dengan 'terlihat baik': dia terbakar sekali dengan menerima optimalitas yang jelas. Dia mendorong sampai dia bisa membuktikan kode itu terbaik.