Hamming Kodlama

1. GİRİŞ

Hamming kodlama sistemi telekomünikasyonda kullanılan bir çeşit doğrusal hata kontrol ve düzeltme yöntemidir. Hamming kelimesi bu yöntemi bulan kişi olan Richard Hamming’ den gelmektedir. Hamming kodlama yöntemi ile verileri paketlerindeki tek bitlik hatalar bulunup düzeltilebilir. Yine bu yöntem ile iki bitlik hataları da tespit edebiliriz fakat düzeltemeyiz.

2. TARİHÇE

Richard Hamming 1940 yılında Bell Laboratuarlarında Bell Model V adı verilerin bir çeşit elektromekanik makine üzerinde çalışmaktaydı. Bu makine verileri Hollerith card ya da şimdilerde IBM card olarak da bilinen kağıttan kartlar üzerinden okumaktaydı. Özel bir kod sistemi bu kartları kontrol eder ve bir hata bulduğunda makinenin ışığı yanıp sönüyordu, böylelikle o sırada çalışmakta olan operatör bu hatayı düzeltebilmekteydi. Fakat çalışma saatleri dışında ve hafta sonları, yani makinenin başında çalışan bir operatör bulunmadığı zamanlarda veriler kontrol edilmeksizin makine çalışmaya devam etmekteydi.

Hamming hafta içi çalışmaktaydı ve her hafta başında bu güvenilmez makine yüzünden çalışmalarına yeniden başlamak zorunda kaldığı için bu konudaki kızgınlığı giderek artmaktaydı. Sonraki birkaç sene boyunca hata kontrolü problemi ile ilgili çalışmalar yaptı ve git gide bu konuda daha etkili algoritmalar geliştirdi. Sonunda 1950 yılında kendi simini verdiği, bu gün bile halen kullanılmakta olan “Hamming Kodlama” yöntemini açıkladı.

3. HAMMING’ DEN ÖNCEKİ YÖNTEMLER

3.1. Parity ( Eşitlik ) Yöntemi

Parity yönteminde veri paketine datamızda ki 1’ lerin sayısının tek mi çift mi olduğunu gösteren tek bir bit eklenir. Eğer iletim sırasında bir bit değişirse bu parity bitinin de değişmesine neden olacaktır ve bu noktada hata tespiti yapılabilir. Parity bitinin genel kullanımı şu yöndedir; eğer datamızda tek sayıda 1 varsa parity bitimiz 1, çift sayıda 1 var ise 0 ayarlanır. Sonuçta datamız parity biti ile birlikte çift sayıda 1 içerir.

Parity hata kontrolü pek de etkili bir yöntem değildir çünkü datamızda çift sayıda bit değişirse parity bitimiz de geçerliliğini koruyacaktır ve bu da hatanın tespitini olanaksız kılar. Bunun dışında parity biti hata tespit edilse bile hatanın hangi bitte olduğunu gösteremez. Bu durumda data tamamen çıkarılıp başlangıcından itibaren yeniden aktarılmak zorundadır. Bu yüzden gürültülü bir iletim ortamında verini iletilmesi çok uzun zaman alabilir hatta ve hatta hiçbir zaman gerçekleşmeyebilir.

3.2. Two-out-of-five Code (Beşte İkilik Kodlama)

1940’larda Bell firması “beşte ikilik kodlama” olarak da bilinen daha karışık bir hata kontrol yöntemi geliştirdi. Bu yöntemde “5li blok” olarak da bilinen her beş bitlik grup tam olarak iki adet 1 içerir. Böylece eğer bir 5li blokta 2 adet bir yoksa bilgisayar hata olduğunu anlamaktaydı. Fakat bu yöntemde hala sadece tek bitlik hataları tespit edebilmekteydi. Örneğin aynı blok içerisinde bir bit 0’dan 1’e, başka bir bit de 1’den 0’a dönüştüğünde bu blok içerisindeki 1’lerin ve 0’ların sayısı değişmeyeceğinden hata sitem tarafından fark edilmemekteydi.

3.3. Repetition (Tekrar) Yöntemi

Zamanında kullanılan bir diğer hata kontrolü yöntemi ise bitlerin tekrar edilmesiydi. Bu yöntemde veri iletilirken doğru gönderildiğinden emin olmak için her bir bit birkaç defa tekrar edilirdi. Örneğin gönderilesi gereken bit 1 olsun; n = 3 (tekrar sayısı) için “111” gönderilirdi. Eğer alına 3 bit de aynı değilse hata tespit edilmiş olurdu. Eğer iletim hattı yeterince temiz olursa çoğunlukla her üçlüden sadece biri bozulmaktaydı. Bu yüzden “001”, “010” ve “100” dan her biri 0’ı; “110”, “101” ve “011” den her biri ise 1 i temsil etmekteydi. Yani bir nevi bu üçlü gruplar aslında hangi biti temsil ettiklerini “oylamaktaydı”. Bu şekilde hataları yakalayıp orijinal mesajı tekrar oluşturabilen bir kodlama yöntemine “hata-düzelten” ( error-correcting ) yöntem olarak da adlandırılabilir. Parity ve beşte ikilik hata kontrol yöntemlerinin aksine tekrar yöntemi hata-düzelten bir yöntemdir.

Fakat yine de böyle bir yöntem hataları tam doğru bir şekilde düzeltemez. Örnekte bahsettiğimiz gibi 1’i temsilen gönderilen “111” bitlerinden aynı anda ikisi birden bozulup “001” şeklinde iletilirse karşı taraf bunun 0’ı temsil ettiğini düşünüp alınan veriyi 0 olarak işleyecektir. Eğer tekrar sayısını 4’ e çıkarırsak 2 bitlik hataları da tespit edebiliriz fakat (oylama sonucunda “beraberlik” elde ettiğimizden ) bunları düzeltemeyiz. Bu yüzden tekrar sayısını 5’e çıkarabiliriz. Böylelikle 2 bitlik hatalarda bulunup düzeltilebilir, fakat 3 bitlikler düzeltilemez…

Sonuç olarak bu yöntem son derece gereksizdir çünkü tek bir bitlik hatanın tespiti için bile 3 kat fazla veri göndermemiz gerekir ki bu sadece 1 bitlik hataların tespiti için. Daha fazla hata bulup düzeltmek istediğimiz de tekrar sayıları da katlanarak artmaktadır. Bu da hem alıcı ve gönderici sistemler için hem kullanılan iletim kanalı için fazladan kayda değer bir yük demektir.

4. HAMMING KODLAMA

Eğer daha fazla hata kontrolü biti dataya eklenir ve bu bitler her bir hatalı bit farklı hata sonuçları üretecek şekilde ayarlanabilirse hatalı bit bulunur ve düzeltilebilir. 7bitlik bir veri olası 7 tane farklı tek bitlik hata durumu vardır ve bu farklı durumlar toplam 3 bitlik hata kontrol bitleri kullanarak ifade edilebilir. Böylece hatalı bir durum yakalandığında hatanın hangi bitten kaynaklandığını da muhtemelen 3bitlik kontrol bitleri yardımıyla öğrenilebilir.

Hamming, beşte ikilik de dahil olmak üzere, mevcut hata kontrolü yöntemleri üzerinde çalıştı ve içeriklerini genelleştirerek kendi yöntemi üzerinde düşünmeye başladı. İşe sistemi tanımlamak için blokların içerdiği data bitlerinin ve kontrol bitlerinin sayısını gösteren bir terminoloji geliştirerek başladı. Örneğin parity yönteminde gönderile her veri paketi için bir bitlik kontrol biti eklenmekteydi, bunun 7 bitlik bir ASCII kodu olduğunu varsayalım. Hamming bunu 7’si data olmak üzere toplam 8 bitten oluşan bir (8,7) olarak tanımladı. Yine aynı şekilde düşünecek olursak repetition yöntemi de bir (3,1) dir. Bilgi oranı ( information ratio ) ise ikinci sayı birinciye bölünerek elde edilebilir. Örneğin yine repetition yöntemi için bu oran 1/3’ tür.

Hamming ayrıca iki veya daha fazla bitin değişmesiyle meydana gelen hataları da fark etti ve bunu “mesafe” ( distance ) olarak tanımlamıştır ki bu terim de kendisinden sonra “Hamming’s distance” olarak anılmaktadır. Yine diğer hata düzeltme yöntemlerinden örnek verecek olursak, parity yönteminin mesafesi 2dir. Çünkü eğer 2 bitlik bir değişme olursa bu hata yöntem için görülemez hale gelir. (3,1) repetition yönteminin mesafesi ise 3 tür, çünkü hatanın anlaşılamayacağı yeni bir 3lü blok oluşması için 3 bitin birden değişmesi gerekir.

Hamming bu iki temel sorun üzerinde yoğunlaştı. Amacı mesafeyi mümkün olduğunca arttırırken bir yandan da bilgi oranını olabildiğince yüksek tutmaktı. 1940’lı yıllar boyunca yaptığı çalışmalarında mevcut hata kontrolü yöntemlerine göre çarpıcı yeniliklere sahip birkaç yöntem geliştirdi. Oluşturduğu sistemlerin hepsinin püf noktası parity bitlerinin aynı anda hem birbirlerini hem datayı kontrol edebilecek şekilde örtüşerek kullanılmasıydı.

Hamming’in son olarak oluşturduğu “Hammig Kodlama” yönteminde parity
bitlerinin kullanılması için geliştirdiği algoritma basitti;

1. İkinin katı olan bütün bit pozisyonları parity bitleri için kullanılacak.
( ör: 1,2,4,8,16,32,64,128….vb. )

2. Diğer tüm pozisyonlar paketlenecek datalar için kullanılacak.
(ör: 3,5,6,7,9,10,11,12,13,14,15,17…..vb. )

3. Her bir parity biti veri paketindeki bazı diğer bitlerin kontrolünü yapar. Parity bitinin pozisyonu kontrol edeceği ya da atlayacağı bitlerin sıkılığını belirtir.
· 1. pozisyonda (n = 1): 0 bit atla (0 = n-1), 1 bit kontrol et (n), 1 bit atla (n),
1 bit kontrol et (n), 1 bit atla (n)…. vb.
· 2. pozisyonda (n = 2): 1 bit atla ( 1 = n-1 ), 2 bit kontrol et (n), 2 bit atla (n),
2 bit kontrol et (n), 2 bit atla (n)…. vb.
· 4. pozisyonda (n=4): 3 bit atla ( 3 = n-1 ), 4 bit kontrol et (n), 4 bit atla (n),
4 bit kontrol et (n), 4 bit atla (n)…. vb.
· 8. pozisyonda (n=8): 7 bit atla ( 7 = n-1 ), 8 bit kontrol et (n), 8 bit atla (n),
8 bit kontrol et (n), 8 bit atla (n)… vb.
· 16. pozisyonda (n=16): 15 bit atla ( 15 = n-1 ), 16 bit kontrol et (n), 16 bit
atla (n), 16 bit kontrol et (n), 16 bit atla (n)…. vb.
· 32. pozisyonda (n=32): 31 bit atla ( 31 = n-1 ), 32 bit kontrol et (n), 32 bit
atla (n), 32 bit kontrol et (n), 32 bit atla (n)…. vb.

4.1. (11,7) Hamming Code Kullanımı Örneği

Daha önce açıklandığı gibi (11,7) lik gösterim 7’si data olan toplam 11 bitlik bir veri paketini ifade etmektedir. Örneğin bu 7 bitlik datamız “0110001” olsun. Hamming kodlama siteminde parity bitlerinin nasıl hesaplanıp, hata tespitinde kullanıldığını aşağıdaki tablolarda görebilirsiniz. Bu tablolarda d data bitlerini, p ise parity bitlerini ifade etmek için kullanılmıştır.

Öncelikle data bitleri uygun pozisyonlarına yerleştirilir. Daha sonra pairty bitleri ilk pozisyondan itibaren hesaplanarak sırayla eklenir.

Eklenen parity bitleri ile birlikte yeni datamız “00001101001” oldu. Veri iletilirken baştan 3. bitin bozulduğunu ve karşı tarafa “0” değil de “1” olarak iletildiğini varsayalım. Bu durumda “00001101001” olan datamız alıcı terminal tarafından “00101101001” olarak algılanacaktır. Aşağıda hamming kodlama yöntemiyle paketlene datada hatalı bitin nasıl tespit edileceğini göstermektedir.

Yeni veri paketinde parity bitler teker teker kontrol edilip doğru olanlar için “0”, yanlış olanlar için “1” yazılır.

Son olarak da elde ettiğimiz bu 4 bitlik veri düşük anlamlı p1 olacak şekilde sağdan sola doğru sıralanır ve 4 bitlik “0011” elde edilir. Artık hatalı olan bitin yerini tespit edebiliriz;

Böylelikle hatalı bitin 3. sıradaki olduğunu tespit etmiş olduk. Bu sayede “00101101001” olan hatalı veriyi, sorun olduğunu bildiğimiz 3. biti değiştirerek tekrar ilk hali olan “00001101001” e dönüştürebiliriz.

5. (7,4) HAMMING KODLAMA

Günümüzde Hamming kodlama deyince akıllara ilk olarak 1950 yılında açıklanan (7,4) lük Hamming kodlama yöntemi gelmektedir. Bu Hamming kodlama yönteminde her 4 bitlik data için 3 bit kontrol biti eklenir. Hamming’ in geliştirdiği bu (7,4) algoritması her hangi bir tek bitlik hatayı düzeltebilir ya da bütün tek veya iki bitlik hataları tespit edebilir.

5.1 Hamming Matrisleri

Hamming kodu parity matrislerini çoklayarak genişletilmesinden oluşan ve
“Haming matrisi” adı verilrn matrislerle çalışır. (7,4) lük Hamming kodlama da birbirleriyle bağlantılı olan 2 çeşit matris kullanırız; Kod üretici matris G ve
Parity kontrol matrisi H.

ve

G matrisinin ilk 4 satırı, 4*4’lük Identity matrisi ( I ) iken son 3 satırı ise 4 veri bitinin 3 parity biti ile 4*3 lük matriste adreslenişinden elde edilir. G’ deki satır vektörleri ise H matrisinin kernelinin temellerini oluşturur. Identity matrisi çarpama işlemi sırasında data vektörünü aktarır. Yukarıdaki açıklamanın aksine data bitleri ilk 4 pozisyondadır, parity bitleri ise son 3 pozisyona yerleştirilmiştir. Ayrıca bu matrisler asıl Hamming matrislerinden biraz farklı olsa da, Hamming kodlamayı anlamamızı kolaylaştıracak temel özelliklerini taşımaktadır.

H matrisinin oluşturulması da G matrisine benzerlik göstermektedir. H matrisinde her satırın son 3 sütunu 3*3’lük Identity matrisidir. İlk 4 sütun ise yine G matrisinde de kullandığımız ve data bitleri ve parity bitlerinin adreslenmesinden oluşan 4*3’ lük matristir.

Yukarda bahsedildiği ve isminden de anlaşılabileceği gibi bu yöntemde 4 bit veri iletilir. Örneğin göndereceğimiz 4 bitlik data “1001” olsun. Bu datayı göndermek için kullanacağımız vektör;

olur.

5.2. Kanal kodlama

Datamızı paketlemek için G matrisini kullanırız. 7*4’lük G matrisi ile asıl datamızı taşıyan 4*1’lik p matrisinin mod2 ye göre çarpılmasından elde edeceğimiz 7*1’lik bir x matrisi (7,4) lük Hamming kodlama yöntemi ile paketlenmiş veriyi oluşturacaktır.

5.3. Parity Kontrolü

Eğer veri iletimi sırsında bir hata oluşmazsa alınan veri matrisi r, iletilen veri matrisi x’ e eşit olmalı ( r = x )

Alıcı terminal, eğer varsa hatalı bitin tespiti için kullanacağı z matrisini elde etmek için H ve r matrislerini çarpar. Matrislerin çarpımı yine mod2 ye göre yapılır çünkü bitlerle çalışıyoruz. (her bir bit sadece 0 ya da 1 değerlerinde birini alabilir.)

5.4. Hatanın Düzeltilmesi

Eğer iletim sırasında tek bitlik bir hata meydana gelirse r ve x matrisleri farklı olacaktır ve bu farkı şu matematiksel ifade ile gösterebiliriz;

r = x + e_i

e_i burada n. pozisyonunda “1” bulunan bir zero ( sıfır ) vektörüdür. Aşağıdaki ifadeler n. sıradaki tek bitlik hatanın belirlenişini gösterir;

Eğer r matrisini H matrisi ile çarparsak;

Hr = H ( x + e_i ) = Hx + He_i

İfadesini elde ederiz. Bu ifadede x asıl iletilen data olduğu için H matrisi ile çarpımı sıfır olacaktır. Buna göre;

Hx + He_i = 0 + He_i = He_i

3*7 lik H matrisi ile 7*1’lik e_i nin çarpımı olan z matrisi bize hatalı olan bitin konumunu bildirecektir. Burada iletim süresince x matrisinde de oluşan hata e_i, örneğin i =3 için r matrisine şu şekilde yansır;

Şimdi ise bu hatalı r matrisini H ile çarptığımız zaman elde edeceğimiz z matrisi bize hatalı olan bitin konumunu verir;

Burada z matrisinin gösterdiği 3*1’lik ifade H matrisindeki sütunlardan birine eşittir. İşte bu sütunun sırası aynı zamanda bize iletilen datada ki bozulan bitin sırasıdır. Yukarıdaki örnek için hatalı bit;

3. sıradakidir. Bunu bildiğimiz için 3. sıradaki biti çevirerek asıl datamıza ulaşırız;

KAYNAKLAR

· http://en.wikipedia.org/wiki/Hamming_code
· David J.C. MacKay (2003) “Information theory, inference and learnin algorithms”, CUP

Hazırlayan : Arda Öztürk