Hamming kodu: Revizyonlar arasındaki fark

[[Telekomünikasyon]]da, ismini yaratıcısı [[Richard Hamming]]’den alan, doğrusal hata düzelten bir koddur. ''Hamming Kodu'' sadece tek bitlik hatayı saptayıp düzeltebilir. İki bitlik bir hatayı sadece saptayabilir ama düzeltemez. Buna karşın, basit eşlik kodu iki bitin transpoze olduğu yerde hata bulamaz; bulsa da düzeltemez.

 

Hamming 1940’larda [[Bell Laboratuarları]]’nda manyetiksel [[röle]] bazlı, zaman döngüsü saniye olan Bell Model V adlı bir [[bilgisayar]]da çalışmıştır. Giriş hataları okunabilen punch kartlarına yüklenirdi. Günler boyunca özel kodlar hataları bulur ve ışık yakardı ki operatörler problemi düzeltsin. Mesaiden sonraki periyotlarda ve hafta sonlarında, operatörler olmadığından makine diğer işlemlere geçerdi.

Hamming hafta sonları çalışırdı ve kart okuyucunun güvenilmez olduğundan programlarına ilk satırdan başlamak zorunda kalması onu deli ediyordu. Yıllar içinde hata düzeltme problemi üzerinde çalışarak çok güçlü bir dizi [[algoritma]] yarattı. [[1950]] yılında bugünkü adıyla aynı olan ve hala kullanılan ''Hamming Kodu'''nu yayımladı.

 

Hamming kodundan önce birkaç basit hata düzeltici kod kullanılmıştır. Ama aynı genel uzayda Hamming'in tekniğinden daha başarılı değillerdi.

 

 

Eşlik verilerdeki ''1'' numaralı bitin tek veya çift olduğunu anlamaya yarayan bir bit ekler. Tek bir bit iletim anında değişirse, eşlik değişir ve hata o noktada bulunabilir. Eşlik değeri 1 olursa verideki 1'lerin sayısı tektir, 0 ise çifttir. Yani veri ve eşlik bitleri bir arada çift sayıda 1’e sahip olmalıdır.

Eşlik denetimi çok sağlam bir yöntem değildir. Çünkü değişen bit sayısı çift olduğunda, kontrol biti doğru olacak ve hata görülmeyecektir. Dahası eşlik biti hangi bitin değiştiğini veya hata bulundurduğunu da anlamayacaktır. Veri tamamen çöpe atılmalıdır veya en baştan gönderilmelidir. Gürültülü iletim ortamında veri iletiminin başarılı olması çok uzun zaman alır ya da hiç olmaz. Eşlik denetimi çok iyi olmasa da, sadece bir bitin kaybolduğunda yerine konmasını sağlayabilir. Bunun için de hangi bitin kaybolduğunun bilinmesi gerekir.

 

 

1940’larda Bell beşin ikisi diye bilinen biraz daha karmaşık bir kod kullanmıştır. Bu kod bütün beş bitlik bloklarda iki tane bir olduğunu, blokta iki tane bir yoksa bir hata olduğunu gösterir. Beşin İkisi Kodu halen bir bitlik hataları bulabilir. Ama bir bit 1'den 0'a, başka bir bit 0'dan 1'e dönerse hata bulunamaz.

 

 

Kullanılan başka bir kod ise her veri bitinin birkaç kere tekrar edilerek doğru olduğunun ve doğru transfer edildiğinin garanti edilmesi üzerine kuruludur. Mesela gönderilen veri ''1'' olsun. n = 3 tekrar için ''111'' gönderilir. Bu üç bitten biri farklı ise hata oluşmuş demektir. Kanal yeterince temiz ise, çoğu seferde üçlünün sadece bir biti farklı olacaktır. 001, 010 ve 100 sıfıra; 110, 101 ve 011 bire tekabül edecektir ki bu sayılar orijinal bit için oy gibidir. Bu özelliği taşıyan ve orijinal mesajı hatalarını fark ederek yeniden yazabilen bu kodlara ''hata düzelten kod'' denir.

Dahası, tekrar kodu çok verimsizdir. Bizim örneğimizde bir kerede gidecek biti üç kere gönderecek zaman kaybına yol açmıştır. Tekrar sayısı arttıkça verim katlanarak düşecektir.

 

[[Dosya:Hamming code hesapları 9.jpg|thumb|200px|Hamming Kod Hesapları]]

 

11. biti değiştirmek ''10001100100'''ı tekrar ''10001100101'' yapar. Hamming Kodlarını çıkartınca geriye orijinal veri sözcüğümüz ''0110101'' kalır. Bir eşlik biti hatalı olur, diğerleri doğru olursa sorudaki eşlik biti yanlıştır ve kontrol ettiği bitler de hatalı olacaktır.

 

 

 

Günümüzde Hamming Kod, spesifik olarak Hamming’in 1950 yılında gösterdiği bir (7,4) kodla ilgilidir. Hamming Kodu her 4 bitlik mesaja 3 kontrol biti ekler. Hamming’in algoritması bir bitlik hatayı bulup düzeltir ve iki bitlik hatayı tespit edebilir. Orta durum nakillerinde, hatalar çok değilse Hamming Kodu efektiftir.

 

 

Hamming kodlar, ''Hamming Matrisleri'' adı verilen matris çarpımlarının eşlik biti fikrinin genişlemesiyle çalışır. Hamming (7,4) kodu için birbiriyle alakalı kod yaratıcı matris G ve eşlik denetleyicisi matris H kullanılır.

Eşlik hatası gözlenmez ama Hamming Kodu bir hata bulur ise, bunun 2 bitlik bir hata olduğu farz edilir fakat düzeltilemez.

 

[[:en:Hamming code]]