parity bits ve hamming code

Biraz zaman buldum ve hamming code anlatayım diye düşündüm.

Ne işe yarar?
Veri transfer ederken küçük hatalar oluşur ve bunların tespiti ve düzeltilmesi, gerekirse yeniden yollanması gerekir. Benim anlatacağım yöntemde 1 bit hatalı ise tespit edilip düzeltiliyor.

Nedir?
Göndereceğimiz dataword 8 bit olacak ve ek olarak 4 parity bitimiz ile toplam 12 bitlik dataword gönderiyoruz. Yani aslında göndermek istediğimiz data 8 bit, geri kalan 4 bit sadece tespit ve düzeltebilme amaçlı.

Anlatmaya hemen örnek ile başlamak en iyisi.

Göndermek istediğimiz dataword 11001010 olsun. Bu datawordu yeni hesaplayacağımız parity bitler ile birlikte yazacağız. Parity bitleri 2 nin kuvvetleri olan pozisyonlara gelecek.

xx1x100x1010

2 nin kuvvetleri olan pozisyonlara şimdilik x koyduk (yani 1, 2, 4, 8 inci pozisyonlara). Bu pozisyonlara parity bitleri hesaplayıp yazacağız şimdi.

Birinci pozisyon için 3, 5, 7, 9, 11 deki sayılara bakıp even parity ye göre yazıyoruz.
Yani (1+1+0+1+1) % 2 = 0. Yani dataworddeki ilk bit 0 olacak. Aynı şekilde diğerlerini de hesaplayalım:
İkinci pozisyon için 3, 6, 7, 10 11.
Yani (1+0+0+0+1) % 2 = 0.
Dördüncü pozisyon için 5, 6, 7, 12.
Yani (1+0+0+0) % 2 = 1.
Sekizinci için 9, 10, 11, 12.
Yani (1+0+1+0) % 2 = 0.

Bu dört parity bitimizi de hesapladıktan sonra datawordümüzün son durumu

001110001010

Evet bunu anladık ama o pozisyonlar nereden geldi dediğinizi duyabiliyorum :) Onları şimdi anlatıp yazının akışını bozmak istemiyorum ama buna yorum olarak anlatacağım.

Son hesapladığımız 12 bit uzunluğundaki datawordümüzü göndereceğiz ve alıcı taraf dataya bakıp (8 bitlik) yeniden parity bitlerini hesaplayacak ve farklılığa göre anlayacak.
Bu giden datawordün mesela 3. bitinin yanlış olarak gittiğini (1 değil de 0 olarak) varsayalım. Alıcı tarafın elindeki dataword şöyle

000110001010

Şimdi alıcı taraf tekrar parityleri hesaplayacak.

xx0x100x1010

Yine aynı şekilde o pozisyonlara bakıp birinci, ikinci, dördüncü ve sekizinci pozisyondaki bitleri hesaplıyoruz yani parity bitlerini.
(0+1+0+1+1) % 2 = 1
(0+0+0+0+1) % 2 = 1
(1+0+0+0) % 2 = 1
(1+0+1+0) % 2 = 0
Şimdi hesapladığımız parity bitler 1110 yaptı. Oysa bize gelen datawordde 0010 idi. Şimdi bu iki parityde bitleri karşılaştırıp, farklı olanlar için 1, aynı olanlar için 0 yazacağımız yeni bir sayı yaratacağız. Yani XOR layacağız.

1110
0010
____(xor)
1100

Ürettiğimiz sayı 1100. Bunu tersten yazıyoruz yani 0011.
0011 ikilik sistemde bir sayı, bunu onluk sisteme çevirirsek 3 olur. Bu da bize 12 bitlik datawordümüzde kaçıncı bitin hatalı gelmiş olduğunu gösterir. Hatırlıyorsanız yukarda 3. biti bozmuştuk zaten. Hatayı tespit ettik, düzeltmek içinse tek yapmamız gereken 3. biti değiştirmek.

Bize üçüncü sınıfta verilen "Data Communications" dersinin bir ödevi de bunun kodunu yazmaktı C ile. Kodu buradan indirebilirsiniz. Dosyadan 12 bitlik datawordler okuyup, hatalıysa düzeltip ekrana basıyor.