Bell Labs, 1947
Richard Hamming bergabung dengan Bell Telephone Laboratories pada tahun 1946. Komputer relay di sana dijalankan hanya pada hari kerja, ketika teknisi dapat menghidupkan kembali mereka setelah kesalahan. Akhir pekan, mesin berhenti ketika sesuatu salah - meninggalkan pekerjaan yang antri hingga Senin.
Hamming marah. 'Jika mesin bisa mendeteksi kesalahan,' ia pikir, 'mengapa tidak bisa menemukannya dan memperbaikinya?' Frustrasi ini, yang dicampur dengan keahlian yang dalam dengan aritmatika biner dan pemeriksaan paritas, menetapkan panggung.
Pertama Wawasan: Kode Kotak-kotak
Pertama ide Hamming: susun bit pesan dalam bentuk m×n kotak, tambahkan pemeriksaan paritas ke setiap baris dan setiap kolom. Kesalahan tunggal menghasilkan pemeriksaan baris yang gagal dan satu pemeriksaan kolom yang gagal. Intersekusi mereka menamai posisi kesalahan.
Rasio redundansi: (m+1)(n+1) / mn. Kalkulus memberi tahu Anda bahwa persegi panjang minimalis ini untuk ukuran pesan tetap. Tapi seiring berjalannya m dan n, kemungkinan kesalahan ganda menjadi lebih besar - suatu keputusan teknik tanpa jawaban universal.
Mengurangi Rasio Redundansi Persegi Panjang
Sebuah kotak 4×4 mengangkut 16 bit pesan dengan 4 pemeriksaan baris & 4 pemeriksaan kolom, plus 1 bit paritas sudut = 9 bit pemeriksaan untuk 16 bit pesan.
Rasio redundansi: (m+1)(n+1) / mn = 25/16 ≈ 1.56.
Untuk kotak 10×10: 100 bit pesan, 121 bit total, redundansi ≈ 1.21.
Syndrom sebagai Bilangan Biner
Beberapa minggu setelah kode persegi berhasil, Hamming sedang pergi menuju New York melalui lahan pertanian New Jersey, sambil mengulas kembali kesuksesannya secara mental. Kode segitiga terpikir olehnya — lebih baik redundansi. Kemudian kubus. Lalu 4-dimensional, 5-dimensional...
Setiap dimensi tambahan meningkatkan redundansi. Kubus berdimensi n dengan sisi 2 hanya menggunakan n+1 pengecekan paritas untuk 2^n titik. Tapi apakah ini optimal?
Argumen Penghitungan
n+1 bit paritas menghasilkan sindrom: sebuah bilangan biner (n+1). Sindrom tersebut harus dapat mengidentifikasi 2^n + 1 hasil yang berbeda: setiap posisi kesalahan 2^n, plus hasil khusus 'tanpa kesalahan'.
2^(n+1) = 2·2^n — hampir cukup. Kursng oleh faktor 2. Hamming menutup masalah tersebut.
Intuisi Kunci
Kemudian, Hamming kembali dengan ide baru: gunakan sindrom itu sendiri sebagai bilangan biner yang menamai posisi kesalahan. Posisi 1 = 001 biner, posisi 2 = 010 biner, posisi 3 = 011 biner, dst. Sisihkan semua nol untuk 'tanpa kesalahan'.
Ini mengubah sindrom dari output pengecekan paritas menjadi alamat. Pengecekan paritas dirancang untuk menghasilkan alamat yang tepat ketika satu bit saja yang berganti.
Mengatur Kode (7,4)
Untuk kode 7-bit (3 bit paritas, 4 bit pesan), posisi 1 hingga 7 dalam biner adalah: 001, 010, 011, 100, 101, 110, 111.
Pengecekan paritas 1 menutupi posisi di mana bit 0 = 1: posisi 1, 3, 5, 7.
Pengecekan paritas 2 menutupi posisi di mana bit 1 = 1: posisi 2, 3, 6, 7.
Pengecekan paritas 3 menutupi posisi di mana bit 2 = 1: posisi 4, 5, 6, 7.
Bit paritas mengisi posisi kuasa dua: 1, 2, 4. Bit pesan mengisi sisanya: 3, 5, 6, 7.
Jika bit 6 berganti, pengecekan paritas 2 & 3 gagal (110 dalam biner = 6). Sindrom membaca 110 = 6. Balikkan posisi 6. Selesai.
Singel Error Correct, Double Error Detect
Kode Hamming (7,4) memperbaiki kesalahan tunggal. Namun, apa jika dua bit terbalik? Tanpa perlindungan tambahan, decoder menerapkan aturan sindrom dan 'memperbaiki' codeword ke pesan yang salah — penyesuaian diam.
SECDED: Satu Paritas Tambahan
Tambahkan satu paritas tunggal p₀ yang meliputi seluruh codeword (semua 7 bit). Sekarang sindrom memiliki 4 entri: tiga pemeriksaan asli plus p₀.
``
old sindrom new p₀ meaning
000 0 benar
000 1 kesalahan hanya pada p₀
xxx 1 kesalahan tunggal, nama lama sindromnya
xxx 0 kesalahan ganda — beri tanda
``
Empat kasus tersebut adalah yang menyeluruh. Kesalahan ganda membalik dua bit: sindrom lama tidak akan membaca 000 (kedua bit bersama-sama merusak dua dari pemeriksaannya), tetapi p₀ terbalik dua kali dan kembali ke 0. Pola xxx + 0 tidak dapat disangkal.
Mengapa SECDED Berfungsi
Aturan SECDED memanfaatkan struktur modular paritas. Dengan paritas genap, setiap flipp tunggal mengubah p₀. Setiap flipp ganda meninggalkan p₀ tetap. Jadi p₀ menghitung kesalahan modulo 2.
Gambar Geometris
Hamming tiba di tempat yang sama dari arah yang berbeda: geometri analitik. Representasikan setiap string n-bit sebagai titik verteks dari kubus n-dimensional. Flip satu bit memindahkan titik satu jarak-sisi sepanjang satu sumbu. Dua flips: dua sisi. Jarak metrik adalah jarak Hamming.
Definisi bola Hamming dengan jari-jari t sekitar suatu kode c: semua titik dalam t flip-bit dari c. Untuk pemindaian kesalahan tunggal, t = 1.
Kondisi untuk pemindaian kesalahan tunggal: bola-bola dengan jari-jari 1 sekitar setiap pasang kode unik tidak boleh bertumpang tindih. Jika bertumpang tindih, kata pengimaan menerima kata yang diterima dalam tumpang tindih dapat termasuk dalam kode mana pun dan decoder gagal.
Ini langsung diterjemahkan ke jarak minimum: dua bola dengan jari-jari 1 tidak bertumpang tindih jika dan hanya jika kode-kode tersebut setidaknya 3 apart (d_min ≥ 3).
Kode (7,4) mencapai d_min = 3. Batas Hamming: 2^7 / (1 + 7) = 16 = 2^4. Tepat 16 kode. Sebuah kode sempurna: 16 bola dengan jari-jari 1 mengisi {0,1}^7 tanpa celah atau tumpang tindih.
Pengampuannya
Hamming jelas: kode error-correcting melibatkan pengampuan, bukan matematika murni.
Panjang pesan: pesan yang lebih panjang memungkinkan pengodean yang lebih efisien (log n bit paritas untuk n bit pesan). Namun, pesan yang lebih panjang juga mengumpulkan lebih banyak noise, meningkatkan risiko kesalahan ganda melewati sebagai perbaikan palsu tunggal.
Tingkat perbaikan vs. deteksi: menukar satu koreksi kesalahan untuk dua deteksi kesalahan tambahan. Perbandingan optimal tergantung pada karakteristik noise saluran.
Nilai perawatan lapangan: seiring pertumbuhan kompleksitas perangkat, teknisi lapangan tidak dapat mengdiagnosis setiap kegagalan dari prinsip pertama. Sistem yang dapat mendiagnosis diri sendiri secara drastis mengurangi keahlian yang diperlukan untuk perawatan. Hamming menyebut hal ini sebagai manfaat yang paling penting, seringkali lebih penting dari peningkatan keandalan yang bersih.
Gaya: Kesempatan Menguntungkan Minda yang Telah Disiapkan
Hamming menutup Bab 12 dengan tantangan langsung. Dia mendeskripsikan penemuan yang membutuhkan tiga hingga enam bulan kerja, sebagian besar pada saat-saat aneh sambil melaksanakan tugas utamanya di Bell Labs.
Dia mengidentifikasi tiga hal yang membuatnya mungkin:
1. Persiapan: keahlian mendalam dengan pengecekan paritas, aritmatika biner, & teori grup, sebelum masalah muncul.
2. Mengulangi kesuksesan: secara rutin memainkan kembali solusi lampau untuk menginternalisasi gayanya. Kode segitiga muncul di dalamnya saat mengingat kode segiempat selama perjalanan menuju kereta.
3. Tidak puas dengan 'terlihat baik': dia pernah terbakar jari karena menerima kesempurnaan yang tampak. Dia terus mendorong sampai dia bisa membuktikan bahwa kode tersebut adalah yang terbaik.