Hamming kodu

Telekomünikasyonda, ismini yaratıcısı Richard Hamming’den alan, doğrusal hata düzelten bir koddur. Hamming Kodu tek bitlik hataları saptayıp düzeltebilir. Veya aynı kod bir veya iki bitlik hataları saptamak üzere kullanılabilir. Buna karşın, basit eşlik kodu iki bitin transpoze olduğu yerde hata bulamaz; bulsa da düzeltemez.

Tarihçe değiştir

Hamming 1940’larda Bell Laboratuvarları’nda manyetiksel röle bazlı, zaman döngüsü saniye olan Bell Model V adlı bir 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 algoritma yarattı. 1950 yılında bugünkü adıyla aynı olan ve hala kullanılan Hamming Kodu'nu yayımladı.

Hamming'den Önceki Kodlar değiştir

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 değiştir

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 değiştir

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 değiştir

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ı değiştir

$Hx+He_{i}=0+He_{i}=He_{i}$

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ı değiştir

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.

Hamming Kodunda Kullanılan Eşlik bitlerinin Hesaplanması
	p₁	p₂	d₁	p₃	d₂	d₃	d₄	p₄	d₅	d₆	d₇
Veri (eşlik biti olmadan):			0		1	1	0		1	0	1
p₁	1		0		1		0		1		1
p₂		0	0			1	0			0	1
p₃				0	1	1	0
p₄								0	1	0	1
Veri (eşlik bitiyle birlikte):	1	0	0	0	1	1	0	0	1	0	1

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 10001100100'dı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.

Eşlik bitlerinin Denetlenmesi (değişmiş bit koyu renkli)
	p₁	p₂	d₁	p₃	d₂	d₃	d₄	p₄	d₅	d₆	d₇	Parity check	Parity bit
Alınan veri sözcüğü:	1	0	0	0	1	1	0	0	1	0	0
p₁	1		0		1		0		1		0	Kalır	1
p₂		0	0			1	0			0	0	Kalır	1
p₃				0	1	1	0					Geçer	0
p₄								0	1	0	0	Kalır	1

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

	p₄	p₃	p₂	p₁
İkilik tabanda	1	0	1	1
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 değiştir

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 değiştir

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.

$G:={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\0&1&1&1\\1&0&1&1\\1&0&1&1\end{pmatrix}}$

$H:={\begin{pmatrix}0&1&1&1&1&0&0\\1&0&1&1&0&1&0\\1&1&0&1&0&0&1\end{pmatrix}}$

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:

$p={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}$

Kanal kodlama değiştir

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.

$G_{p}={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\0&1&1&1\\1&0&1&1\\1&0&1&1\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}1\\0\\1\\1\\0\\1\\0\end{pmatrix}}=x$

Eşlik kontrolü değiştir

İ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;

$H_{r}={\begin{pmatrix}0&1&1&1&1&0&0\\1&0&1&1&0&1&0\\1&1&0&1&0&0&1\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\1\\0\\1\\0\end{pmatrix}}={\begin{pmatrix}0\\0\\0\end{pmatrix}}=z$

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 değiştir

Diyelim ki bir hata oluştu. Matematiksel olarak; r = x + e_iyazı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 :

$H_{r}=H\left(x+e_{i}\right)=Hx+He_{i}$

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;

$Hx+He_{i}=0+He_{i}=He_{i}$

Ş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:

Şimdi ;

$H_{r}={\begin{pmatrix}0&1&1&1&1&0&0\\1&0&1&1&0&1&0\\1&1&0&1&0&0&1\end{pmatrix}}{\begin{pmatrix}1\\1\\1\\1\\0\\1\\0\end{pmatrix}}={\begin{pmatrix}1\\0\\1\end{pmatrix}}=z$

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 değiştir

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 değiştir

en:Hamming code