Bell Laboratuvarları, 1947
Richard Hamming 1946'da Bell Telefon Laboratuvarları'na katıldı. Oradaki röle bilgisayarları sadece hafta içi çalışıyordu, teknisyenler hatalardan sonra onları yeniden başlatabilirlerdi. Hafta sonları, bir şey yanlış gittiğinde makineler duruyordu — işler Pazartesiye kadar beklemeye kalmıştı.
Hamming çok öfkeliydi. 'Eğer makine bir hatayı tespit edebiliyorsa,' diye düşündü, 'neden onu bulamıyor ve düzeltimiyor?' Bu hayal kırıklığı, ikili aritmetik ve eşlik kontrollerine derin aşinalığıyla birleşerek sahneyi hazırladı.
İlk İçgörü: Dikdörtgen Kodlar
Hamming'in ilk fikri: ileti bitlerini m×n dikdörtgeninde düzenlemek, her satıra & her sütuna eşlik kontrolü eklemek. Tek bir hata tam olarak bir başarısız satır kontrolü & bir başarısız sütun kontrolü üretir. Kesişimleri hatanın konumunu adlandırır.
Artıklık oranı: (m+1)(n+1) / mn. Matematik size sabit ileti boyutu için bir karenin bunu en aza indirdiğini söyler. Ancak m & n büyüdükçe, çift bir hata daha olası hale gelir — evrensel bir cevabı olmayan bir mühendislik yargısı.
Dikdörtgen Artıklığını En Aza İndirmek
4×4 bir dikdörtgen 16 ileti bitini 4 satır kontrolü & 4 sütun kontrolü ile taşır, artı 1 köşe eşlik biti = 16 ileti biti için 9 kontrol biti.
Artıklık oranı: (m+1)(n+1) / mn = 25/16 ≈ 1.56.
10×10 bir dikdörtgen için: 100 ileti biti, 121 toplam bit, artıklık ≈ 1.21.
Sendrom Olarak İkili Sayı
Dikdörtgen kod öngörüsünden birkaç hafta sonra, Hamming New York'a doğru New Jersey çiftliklerinden geçerken, geçmiş başarılarını zihninde gözden geçiriyor. Üçgen kod ona geldi — daha iyi artıklık. Sonra küp. Sonra 4-boyutlu, 5-boyutlu...
Her ekstra boyut artıklığı iyileştirdi. n boyutundaki 2 kenarlı hiperkup sadece 2^n köşe için n+1 eşlik kontrolü kullanır. Ama bu optimal miydi?
Sayma Argümanı
n+1 eşlik biti sendrom üretir: bir (n+1)-bitlik ikili sayı. Bu sendrom 2^n + 1 farklı sonucu tanımlaması gerekir: 2^n hata konumunun her biri, artı özel 'hata yok' sonucu.
2^(n+1) = 2·2^n — neredeyse yeterli. Oranın 2 katı kadar eksik. Hamming sorunu erteledi.
Anahtar İçgörü
Daha sonra Hamming yeni bir fikir ile geri döndü: sendromi kendisini hata konumunu adlandıran ikili sayı olarak kullan. Konum 1 = ikili 001, konum 2 = ikili 010, konum 3 = ikili 011, vb. Tümü-sıfırları 'hata yok' için ayır.
Bu sendromi eşlik kontrollerinin çıktısından bir adrese dönüştürür. Eşlik kontrollerine herhangi tek bir bit değiştiğinde tam olarak doğru adresi üretecek şekilde tasarlanır.
(7,4) Kodunu Tasarlamak
7 bitlik bir kod için (3 eşlik biti, 4 ileti biti), konumlar 1 ile 7 ikili olarak: 001, 010, 011, 100, 101, 110, 111.
Eşlik kontrolü 1, bit 0 = 1 olan konumları kapsar: konumlar 1, 3, 5, 7.
Eşlik kontrolü 2, bit 1 = 1 olan konumları kapsar: konumlar 2, 3, 6, 7.
Eşlik kontrolü 3, bit 2 = 1 olan konumları kapsar: konumlar 4, 5, 6, 7.
Eşlik bitleri 2'nin kuvveti konumlarını işgal eder: 1, 2, 4. İleti bitleri gerisini işgal eder: 3, 5, 6, 7.
Bit 6 değişirse, eşlik kontrolleri 2 & 3 başarısız olur (110 ikili = 6). Sendrom 110 = 6 okur. Konum 6'yı çevir. Bitti.
Tek Hatayı Düzelt, Çift Hatayı Tespit Et
(7,4) Hamming kodu tek hatayı düzeltir. Ama iki bit değişirse? Fazladan koruma olmadan, kod çözücü sendrom kuralını uygular ve kod sözcüğünü yanlış iletiyi — sessiz bir yanlış düzeltmeye 'düzeltir'.
SECDED: Bir Tane Daha Eşlik Biti
Tüm kod sözcüğünü (tüm 7 biti) kapsayan tek bir eşlik biti p₀ ekleyin. Şimdi sendromun 4 girdisi var: orijinal 3 kontrol artı p₀.
``
eski sendrom yeni p₀ anlam
000 0 doğru
000 1 sadece p₀'da hata
xxx 1 tek hata, eski sendrom adını söyler
xxx 0 çift hata — işaretle
``
Dört durum kapsamlıdır. Çift bir hata iki biti değiştirir: eski sendrom 000 okumayacaktır (her iki bit birlikte iki kontrolünü bozar), ama p₀ iki kez değişir ve 0'a geri döner. xxx + 0 deseni ayırt edilemez.
SECDED Neden Çalışır
SECDED kuralı eşliğin modüler yapısını kullanır. Çift eşlikle, herhangi bir tek çevir p₀'yı değiştirir. Herhangi bir çift çevir p₀'yı değiştirilmemiş bırakır. Yani p₀, hataları modulo 2'ye sayar.
Geometrik Resim
Hamming farklı bir yönden aynı yere vardı: analitik geometri. Her n bitlik dizgiyi n boyutlu hiperkübün bir köşesi olarak temsil edin. Tek bir bit çevirme bir noktayı bir eksil boyunca bir kenar mesafesi taşır. İki çevir: iki kenar. Metrik Hamming uzaklığıdır.
Kod sözcüğü c etrafında Hamming topu tanımlayın yarıçap t: c'ye t bit çevirme içindeki tüm noktalar. Tek hata düzeltme için, t = 1.
Tek hata düzeltme koşulu: her çift farklı kod sözcüğün etrafında yarıçap 1 topları örtüşmemelidir. Örtüşürlerse, alınan bir sözcük topla her iki kod sözcüğüne ait olabilir ve kod çözücü başarısız olur.
Bu doğrudan minimum uzaklığa çevirir: yarıçap 1 iki top örtüşmez ve ve ancak kod sözcükleri en az 3 kadar ayrı ise (d_min ≥ 3).
(7,4) kodu d_min = 3'ü başarır. Hamming sınırı: 2^7 / (1 + 7) = 16 = 2^4. Tam olarak 16 kod sözcüğü. Bir kusursuz kod: 16 yarıçap 1 topları {0,1}^7'yi aralarında boşluk veya örtüşme olmadan döşer.
Mühendislik Yargıları
Hamming açıktı: hata düzeltme kodları saf matematik değil, mühendislik yargılarını içerir.
İleti uzunluğu: daha uzun iletiler daha verimli kodlamaya izin verir (n ileti biti için günlük n eşlik biti). Ama daha uzun iletiler ayrıca daha fazla gürültü biriktirir, çift bir hatanın yanlış tek düzeltme olarak kaçması riskini yükseltir.
Düzeltme vs. tespit seviyesi: bir hata düzeltmeyi iki ekstra hata tespit için ticareti yapın. Optimal bölünme kanalın gürültü karakteristiğine bağlıdır.
Saha bakım değeri: cihaz daha karmaşık büyüdükçe, saha teknisyenleri her hatayı ilkeler ilkesinden tanılayamaz. Kendini tanılayan bir sistem saha bakımı için gereken beceriyi dramatik olarak azaltır. Hamming bunu en önemli yararlardan biri olarak adlandırdı, genellikle ham güvenilirlik kazancından daha önemliydi.
Stil: Talih Hazırlanan Zihni Seçer
Hamming, Bölüm 12'yi doğrudan bir zorlama ile kapatmıştır. Keşfi üç ile altı ay çalışma gerektirdiğini, çoğunlukla Bell Labs'taki ana görevlerini taşırken tuhaf anlar içinde tanımladı.
Mümkün kılan üç şey tanımladı:
1. Hazırlık: eşlik kontrollerine, ikili aritmetike, & grup teorisine derin aşinalık, problem ortaya çıkmadan önce.
2. Geçmiş başarıları gözden geçirmek: geçmiş çözümlerin stilini içselleştirmek için alışkanlıkla tekrar oynatmak. Üçgen kod ona dikdörtgen kodunu zihninde gözden geçirirken bir ulaşımda geldi.
3. 'İyi görünüyor' ile tatmin olmamak: bir kez açık optimaliteyi kabul ederek parmağını yakıttı. Kodu en iyi olduğunu kanıtlayabilene kadar itti.