Richard Hamming: Hafta Sonu Çalışmayan Bilgisayardan Doğan Hata-Düzeltici Kodlar

Sinir bozucu hafta sonları

Richard Wesley Hamming 1947'de Bell Telephone Laboratories'a katıldı. İkinci Dünya Savaşı sırasında Los Alamos'ta Manhattan Projesi'nde IBM hesap makinelerini koşturmuştu — atom bombası fiziğinin hesaplarını yapan ekipte. Bell Labs ise barış zamanı bilgisayarının cenneti: Shannon, Bardeen, Shockley aynı koridorlarda.

Hamming Cuma akşamı hesap işini bilgisayara verir, eve giderdi. Bilgisayarın delikli kart okuyucusu bir hata yakaladığında tüm işi atar; Pazartesi sabahı boş çıktıyla karşılaşırdı. Tek bir bit hatası tüm hafta sonunu çöpe atıyordu.

Hamming sinirlendi. "Eğer makine hatayı fark edebiliyorsa, neden düzeltemiyor?" dedi. 1948-1950 arası hata-düzeltici kodları icat etti.

Hamming mesafesi

Önce sayma aracı. İki ikili dize arasındaki Hamming mesafesi, farklı oldukları bit sayısıdır. Örneğin:

$d(10110, 11100) = 3$

çünkü 2., 4., 5. bitler farklı.

Hata-düzeltme mantığı: kod kelimelerini birbirinden uzak seçin. Eğer kod kelimeleri arasındaki minimum mesafe $d$ ise, $\lfloor (d-1)/2 \rfloor$ hata düzeltilebilir: alınan kelimeye en yakın kod kelimesi neyse onu seçersiniz.

Hamming (7,4) kodu

Hamming'in 1950'de yayınladığı kod, 4 veri bitini 7 bitlik bir koda gömer. Üç ek eşlik biti eklenir; bu sayede minimum mesafe 3 olur ve 1 bitlik herhangi bir hata düzeltilebilir.

Konum trikleri: kodun 7 bitini 1'den 7'ye numaralayın. Pozisyonu 2'nin kuvveti olanlar (1, 2, 4) eşlik bitleridir; geri kalanlar (3, 5, 6, 7) veri bitleri.

• Eşlik biti $p_1$ (pozisyon 1): 1, 3, 5, 7 pozisyonlarının XOR'u (yani ikili gösteriminde 1. biti açık olan tüm pozisyonlar).
• Eşlik biti $p_2$ (pozisyon 2): 2, 3, 6, 7.
• Eşlik biti $p_4$ (pozisyon 4): 4, 5, 6, 7.

Eğer bir hata varsa, alıcı her eşlik bitini yeniden hesaplar. Hatalı olanların pozisyon numaralarını topladığında — hatanın bulunduğu pozisyonu doğrudan elde eder!

Örnek: $p_1$ ve $p_4$ hatalı, $p_2$ doğru. $1 + 4 = 5$. Pozisyon 5'teki biti çevir, kod düzelir.

Matematiğin "hata adresini" doğrudan üreten zarafeti.

Hamming kürelerinin sınırı

Hamming aynı dönemde kodlama teorisinin temel sınırını da yazdı: bir koddaki her kod kelimesinin etrafında $t$ yarıçaplı Hamming küreleri çakışmamalı. Bu küre sayısı toplamı $2^n$'i geçemez:

$|C| \cdot \sum_{i=0}^{t} \binom{n}{i} \leq 2^n$

Bu Hamming sınırı (singleton bound da denir), kaç kelimelik bir kodun $t$ hata düzeltebileceğinin üst limitini verir. Bu sınıra ulaşan kodlara mükemmel denir; Hamming (7,4) kodu mükemmeldir.

Hamming penceresi (sinyal işleme)

Hamming'in matematiksel mirası kodlamayla bitmez. Sinyalleri Fourier dönüşümüne sokmadan önce kenar sızıntısını azaltmak için kullanılan Hamming penceresi:

$w(n) = 0.54 - 0.46 \cos\left(\frac{2\pi n}{N-1}\right)$

Bugün her ses, görüntü ve telekomünikasyon işleminde — telefonunuzun mikrofonundan radyo astronomiye — kullanılır.

"You and Your Research"

Hamming'in en etkili mirası bir konuşmadır. 1986'da Bell Labs'ta verdiği "You and Your Research" dersi; bir nesil bilim insanına yön gösterdi:

"If you do not work on an important problem, it's unlikely you'll do important work."

"Önemli bir problem üzerinde çalışmıyorsanız, önemli iş yapmanız muhtemel değildir."

Konuşma şu soruyu sordurdu: "Alanınızın en önemli üç problemi nedir? Üzerinde neden bunlardan birini çalışmıyorsunuz?"

Makine öğrenmesi/teorik fizik öğrencileri arasında bugün hâlâ standart okuma.

Naval Postgraduate School yılları

Hamming 1976'da Bell Labs'tan emekli olunca ABD Donanma Lisansüstü Okulu'na (Monterey) profesör oldu; 1997'ye kadar bilgisayar bilimi öğretti. Çoğu derste klasik kitabı "Numerical Methods for Scientists and Engineers" kullandı; sayısal analiz pedagojisinin altın standartlarındandı.

Ölüm

7 Ocak 1998 — Monterey, Kaliforniya. 82 yaşında. Doğum gününden iki gün sonra kalp krizi.

Miras

• ACM Turing Ödülü (1968) — algoritmik metotlar ve sayısal analizdeki katkıları için (Knuth'un Turing ödülünden 6 yıl önce).
• IEEE Hamming Madalyası — 1988'den beri kodlama teorisinde verilir.
• Hamming kodu, Hamming mesafesi, Hamming sınırı, Hamming ağırlığı, Hamming penceresi.
• CD'lerin, USB'lerin, derin uzay sondalarının sinyal düzeltmesinde Hamming'in tohumları vardır (gerçi modern kodlar Reed-Solomon ve LDPC gibi daha gelişmiş yapılar kullanır — hepsi Hamming'in açtığı yoldan).

Bilgisayarın Pazartesi hatasından, dijital dünyanın iletişim temellerine. "Sinirlendiğim için icat ettim" dedi sonradan. Belki de tüm büyük buluşların özeti budur.