Hamming Kodu

Telekomünikasyonda, ismini yaratıcısı Telekomünikasyon ('uzak iletişim'), Fransızca ''télécommunication'' sözcüğünden geçmiştir Duyum, yazı, resim, simge ya da her çeşit bilginin tel, radyo, optik ile başka elektromanyetik dizgelerle iletilmesi, bunların yayımı ya da alınması

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

==Tarihçe==
Hamming 1940`larda Richard Wesley Hamming (11 Şubat 1915 – 7 Ocak 1998), yaptığı çalışmalar ile bilgisayar bilimleri ve telekomünikasyon alanlarını bir hayli etkilemiş bir matematikçimatematikçidir Katkıları arasında Hamming KodHamming kodu (Hamming matrisiHamming matrisini kullanır), Hamming penceresi (detayları ``Digital Filters`` kitabının 58 kısmında anlatılır), Hamming sayıları, küre paketleme (veya hamming sınırı) ve Hamming mesafesi]

Bell Laboratuarları`nda manyetiksel röle bazlı, zaman döngüsü saniye olan Bell Model V adlı bir Röle Elektrik devrelerinde akım ve voltaj değerleri yardımı ile akım yolunu açıp kapatarak sistemin çalışma mantığını düzenleyen elektromekanik cihaz Röle, prensip olarak bir veya birkaç elektromagnet bobin ve bu bobinin hareket ettirdiği kol ve kola bağlı kontak düzeni olan kapalı kutu biçimindedir Rölenin kapalı olması çevre tozlarının hassas olan kontak yüzeylerine yapışmasını önlemek içindir

bilgisayarda ç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 Bilgisayar çok sayıda aritmetiksel veya mantıksal işlemlerden oluşan bir işi, önceden verilmiş bir programa göre yapıp sonuçlandıran elektronik araç, elektronik beyin Kullanıcıdan aldığı verilerle mantıksal ve aritmetiksel işlemleri yapan; yaptığı işlemlerin sonucunu saklayabilen; sakladığı bilgilere istenildiğinde ulaşılabilen elektronik bir makinedir

algoritma yarattı Algoritma Alm Algorithmus (m), Fr Algoritme (m), İng Algorithm Matematikte sayılarla yapılan her türlü hesaplamanın sistematik metoduna verilen genel isim

1950 yılında bugünkü adıyla aynı olan ve hala kullanılan ``Hamming Kodunu yayımladı

==Hamming`den Önceki Kodlar==

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===

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

===Beşin İkisi Kodu===

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

===Tekrarlama===

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
Ama bu kodlar her hatayı düzeltemez Bizim örneğimizde 2 biti değiştirirsek alıcı ``001`` elde eder Sistem hatayı görür ama orijinal bitin ``0`` olduğu sonucuna varır ki bu da yanlıştır Her biti kopyalama sayımızı artırırsak mesela 4 kez, bu sefer bütün 2 bitlik hataları bulabilir ama düzeltemeyiz 5 kereye çıkarırsak 2 bitlik hataları düzeltebiliriz ama 3 bitlik hataları düzeltemeyiz
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

==Hamming Kodları==

Hamming Kod HesaplarıHamming Kod HesaplarıHamming Kod Hesapları
Bir mesaj içinde daha fazla hata düzelten bit olursa, bu bitler değişik yanlış bitlerin oluşturduğu değişik hataları bulabilecek şekilde ayarlanabilirse, kötü bitler bulunabilir Yedi bitlik bir mesajda yedi olası hatalı bit vardır Üç tane kontrol biti hatayı bulmakla kalmaz, yerini de saptayabilir


Hamming olan kodlama sistemlerinin, beşin ikisi dâhil, üzerinde çalışıp, bu fikirleri genelleştirmiştir Başlangıç olarak sistemi açıklamak için bir terminoloji yaratmıştır Bu terminoloji içinde veri bitleri sayısı ve hata düzelten bitlerin bulunduğu blokları da kapsar Örnek olarak, eşlik içerisinde her veri sözcüğü için tek bit bulundurur ASCII karakterlerinin 7 bit olduğunu varsayarsak, Hamming (8,7) kodu, toplamda sekiz bit, yedisi veri olmak üzere tanımlamıştır Tekrarlama örneği bu kurama göre olacaktır Bilgi oranı, ikinci sayının birinciye bölünmesiyle bulunur


Hamming iki ve daha fazla bitin değişmesi problemini uzaklık olarak tanımlamıştır (Halen "Hamming Uzaklığı" olarak bilinir) Eşlik, herhangi iki bit değişimi görülmez olunca, uzaklık "2" olur


Hamming bu uzaklığı ve bilgi oranını olabildiğince artırmaya çalışmıştır 1940`lar boyunca var olan kodlar üzerinde önemli iletmeler gerçekleştiren birkaç kod yöntemi geliştirmiştir Bütün sistemlerin anahtar noktası eşlik bitlerinin bütün bitlerin ve verinin üzerinden kontrol ederek geçmesidir


Örnek Hamming Kodu Kullanımı


``0110101`` yedi bitlik veri sözcüğümüz olsun Hamming Kodların nasıl hesaplandığı ve hatayı nasıl buldukları aşağıdaki tabloda gösterilmiştir Data bilgileri için ``d``, eşlik bitleri için ``p`` kullanılmaktadır
İlk olarak veri bitleri uygun yerlere konur ve eşlik bitleri her seferinde çift eşlik
kullanılarak hesaplanır

:{ class=wikitable
+ align=bottomCalculation of Hamming code parity bits
-
! !!p1!!p2!!d1!!p3!!d2!!d3!!d4!!p4!!d5!!d6!!d7style= background-color: #CCCCCC
!Veri (eşlik biti olmadan): !! !! !!0!! !!1!!1!!0!! !!1!!0!!1
-
!p1
1 0 1 0 1 1
-
!p200 10 01
-
!p3 0110
-
!p4 0101style=background-color: #CCCCCC
!Veri (eşlik bitiyle birlikte):
10001100101
}

Yeni veri sözcüğümüz (eşlik biti ile) ``10001100101`` olmuştur Son bitin hatalı olduğunu farz edelim ve bu bit 1`den 0 â??a değişmiş olsun Yeni veri sözcüğümüz ``10001100100dır ve bu sefer Hamming Kodun nasıl elde edildiğini çift eşlik biti her hata sapladığında, eşlik bitini ``1`` olarak değiştirip analiz edelim

:{ class=wikitable
+ align=bottomChecking of parity bits (switched bit highlighted)
-
! !!p1!!p2!!d1!!p3!!d2!!d3!!d4!!p4!!d5!!d6!!d7!!Pari ty check!!Parity bitstyle=background-color: #CCCCCC
!Alınan veri sözcüğü: !!1!!0!!0!!0!!1!!1!!0!!0!!1!!0!!0!! !!
-
!p1
1 0 1 0 1 style=background-color: #DDDDDD0style=background: #ff9090 Kalır1
-
!p200 10 0 style=background-color: #DDDDDD0style=background: #ff9090 Kalır1
-
!p3 0110 style=background-color: #90ff90Geçer0
-
!p4 010 style=background-color: #DDDDDD0style=background: #ff9090 Kalır1
}

Son adımda her eşlik bitinin değerini ölçelim Değerin sayı karşılığı 11 çıkar Yani 11 biti hatalıdır ve değiştirilmesi gerekir

:{ class=wikitable
-
! !!p4!!p3!!p2!!p1!!
-
!İkilik tabanda
1011
-
!Onluk tabanda
!8!! !!2!!1!!Σ = 11
}

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


Son olarak, x ve y konumlarındaki iki bit yer değiştirmiş olsun x ve y ikilik gösterimlerinin 2k konumlarındaki bitleri aynı ise, o konuma tekabül eden eşlik biti ikisini de kontrol eder ve aynı kalır xâ?*y olan bazı eşlik bitleri yüzünden bu konumlara tekabül eden bitler değişir Sonuçta Hamming Kodu iki bitlik hataları bulur ama bunları bir bitlik hatalardan ayırt edemez

==Hamming(7,4) Kodu==


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 matrisleri===

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
Resim:Hamming_code_hesapları_41jpg
Resim:Hamming_code_hesapları_42jpg


G matrisinin ilk 4 sırası 4x4 birim matrisi I4, son 3 sıra ise 4 kaynak bitinden 3 eşlik bitine 4x3`lük matrisi gösterir G`nin sütun vektörleri H`nin çekirdeğinin temelini oluşturur Çarpım yapılırken birim matris veriyi iletir Yukarıdaki açıklamadan farklı olarak, veri bitleri ilk 4 konumdayken, eşlik bitleri son 3 konumdadır Bu matrisler gerçek Hamming matrislerinden farklı olsa da, bunlar Hamming Kodu daha kolay anlaşılır hale getiren gerekli detaylardır


Benzer olarak H`nin 3 sütunu 3x3 birim matris I3`ü gösterirken, ilk 4 sütun kaynak veri bitleri ve eşlik denetleyicilerinden oluşan 4x3 matrisi verir 4 blokluk yararlı veri bitini ve birikmiş diğer 3 göz ardı edilmiş biti kullanırız (4+3=7 (7,4)) Veriyi göndermek için göndermek istediğimiz veri bloğunu vektör olarak düşünürüz Mesela ``1011`` için:
Resim:Hamming_code_hesapları_51jpg


Kanal kodlama

Diyelim ki gürültülü komünikasyon kanalında veri iletmek istiyoruz G ve p`nin çarpımını alır, modül 2 girişi ile X kod sözcüğünü elde ederiz
Resim:Hamming_code_hesapları_6jpg


Eşlik kontrolü

İletim sırasında hata olmaz ise r kod sözcüğü, x ile tıpatıp aynı olur
r = x
Alıcı H ve r`yi çarparak z sendrom vektörünü elde eder z vektörü hata varsa nerede olduğunu gösterir Bu çarpım;
Resim:Hamming_code_hesapları_7jpg

Z vektörü 0 olduğundan, alıcı verinin hatasız olduğunu anlar Bu sonuç veri vektörü G ile çarpıldığında , alt uzay vektöründe bir değişime uğradığı gözlemine dayanır Transfer sırasında hiçbir şey olmazsa, r H`nin çekirdeği olarak kalır ve çarpım hep sıfırı verir


Hata Düzeltilmesi

Diyelim ki bir hata oluştu Matematiksel olarak; r = x + eiyazılabilir
Mod 2`ye göre, i konumda 1 olan bir sıfır vektörü, 1`den başlar Yukarıdaki tanım i Konumda bir hata olduğunu gösterir

Şimdi bu vektörü H ile çarparsak :
Resim:Hamming_code_hesapları_8jpg

x iletilen veri olduğundan hatasızdır ki bu H ve x`in çarpımının sıfır olduğunu gösterir Sonuç olarak;
Resim:Hamming_code_hesapları_9jpg

Şimdi H ve P standart baz vektörlerinin çarpımı H`nin hata bulunan sütununu bulur H`yi parçalı biçimde yarattığımızdan, hatalı sütunu 2`lik sayı olarak yazabiliriz Mesela (1,0,1) H`nin bir sütunudur ve 5 konuma tekabül eder ki hata ordadır ve düzeltilebilir

Alttaki şekli inceleyelim:
Resim:Hamming_code_hesapları_10jpg

Şimdi ;
Resim:Hamming_code_hesapları_11jpg

H`nin 2 sütununa denk gelir 2 konumda bir hata bulunmuştur ve düzeltilebilir

Bu yolu kullanarak tek bitlik hataların düzeltilebileceğini göstermek zor değildir Bunun dışında, Hamming Kodu tek veya çift bit hataları bulabilir ama hata oluştuğunda H`nin çarpımı neredeyse hiçbir zaman sıfırdan farklı olmaz Ama Hamming (7,4) bir ve iki bitlik hataları birbirinden ayıramaz


Ekstra Eşlik Biti


Hamming kodları ekstra eşlik bitiyle kullanılabilir Ek bir bütün bitlere Hamming Kodu bütün bitleri kontrol ettikten sonra uygulanıp eklenir Bu geçerli kodların Hamming uzaklığını 3`ten 4`e uzatır
Sonra bütün 1,2,3 bitlik hatalar bulunabilir Artı 2 bitlik hatalar 1 ve 3 bitlik hatalardan ayırt edilebilir 1 bitlik hatalar düzeltilebilir
Eşlik hatası gözlenmez ama Hamming Kodu bir hata bulur ise, bunun 2 bitlik bir hata olduğu farz edilir fakat düzeltilemez

Kaynaklar ve dış bağlantılar==:en:Hamming code


Bu makale, online kullanıcı topluluğu tarafından oluşturulan ve düzenlenen özgür ansiklopedi projesi Wikipedia'nın Türkçe versiyonu Vikipedi'deki Hamming Kodu maddesinden kopyalanmıştır Bu makale, GNU Özgür Belgeleme Lisansı ilkeleri kapsamında özgürce kullanılabilir