Hamming kodu - Hamming code

İkili Hamming kodları
Hamming(7,4) kodu ( r = 3 ile )
Adı üstünde	Richard W. Hamming
sınıflandırma
Tip	Doğrusal blok kodu
Blok uzunluğu	2 r − 1 burada r ≥ 2
Mesaj uzunluğu	2 r - r - 1
Oran	1 - r/(2 r − 1)
Mesafe	3
alfabe boyutu	2
gösterim	[2 r − 1, 2 r − r − 1, 3] 2 -kod
Özellikler
mükemmel kod
v T e

Gelen bilgisayar bilimleri ve telekomünikasyon , Hamming kodları ailesidir doğrusal hata düzeltme kodları . Hamming kodları, bir bitlik ve iki bitlik hataları algılayabilir veya düzeltilmemiş hataları algılamadan bir bitlik hataları düzeltebilir. Buna karşılık, basit eşlik kodu hataları düzeltemez ve yalnızca tek sayıda hatalı biti algılayabilir. Hamming kodları mükemmel kodlardır , yani blok uzunlukları ve minimum üç mesafe ile kodlar için mümkün olan en yüksek oranı elde ederler . Richard W. Hamming , 1950'de delikli kart okuyucuların neden olduğu hataları otomatik olarak düzeltmenin bir yolu olarak Hamming kodlarını icat etti . Orijinal makalesinde, Hamming genel fikrini detaylandırdı, ancak özellikle dört bit veriye üç eşlik biti ekleyen Hamming(7,4) koduna odaklandı .

Gelen matematiksel terimler, Hamming kodları ikili doğrusal bir kod sınıfıdır. Her r ≥ 2 tamsayı için blok uzunluğu n = 2 ^r − 1 ve mesaj uzunluğu k = 2 ^r − r − 1 olan bir kod vardır . Dolayısıyla, Hamming kodlarının oranı R = k / n = 1 − r / (2 ^r − 1) 'dir , bu, minimum üç mesafeli kodlar için mümkün olan en yüksek değerdir (yani, herhangi bir noktadan gitmek için gereken minimum bit değişikliği sayısı). kod kelimesi üçtür) ve blok uzunluğu 2 ^r − 1 . Parite kontrol matrisi Hamming kodu uzunluğu her sütun listesi ile oluşturulur r sıfır olmayan vardır, bu araçlar ikili kod Hamming kodu olan kısaltılmış Hadamard kod . Parite denetimi matrisi, herhangi iki sütunun ikili olarak doğrusal olarak bağımsız olma özelliğine sahiptir .

Hamming kodlarının verilere eklediği sınırlı fazlalık nedeniyle, yalnızca hata oranı düşük olduğunda hataları tespit edebilir ve düzeltebilirler. Bu, bit hatalarının son derece nadir olduğu ve Hamming kodlarının yaygın olarak kullanıldığı bilgisayar belleğinde (genellikle RAM) durumdur ve bu düzeltme sistemine sahip bir RAM, bir ECC RAM'dir ( ECC belleği ). Bu bağlamda, genellikle fazladan bir eşlik bitine sahip genişletilmiş bir Hamming kodu kullanılır. Genişletilmiş Hamming kodları, kod çözücünün en fazla bir bitlik hata oluştuğunda ve herhangi bir iki bitlik hata oluştuğunda ayırt etmesini sağlayan dört Hamming mesafesi elde eder. Bu anlamda, genişletilmiş Hamming kodları, SECDED olarak kısaltılan tek hata düzeltme ve çift hata algılamadır .

Tarih

Hamming kodlarının mucidi Richard Hamming , 1940'ların sonlarında Bell Laboratuarlarında , saniye cinsinden döngü sürelerine sahip elektromekanik röle tabanlı bir makine olan Bell Model V bilgisayarında çalıştı . Giriş, bir inçin sekizde yedisi genişliğinde, sıra başına en fazla altı deliği olan delikli kağıt bant üzerine beslendi . Hafta içi, rölelerde hata tespit edildiğinde, makine durur ve operatörlerin sorunu giderebilmesi için yanıp söner. Mesai saatleri dışında ve hafta sonları, operatörün olmadığı zamanlarda, makine sadece bir sonraki işe geçti.

Hamming hafta sonları çalışıyordu ve tespit edilen hatalar nedeniyle programlarını sıfırdan yeniden başlatmak zorunda kalmaktan giderek daha fazla hüsrana uğradı. Kaydedilmiş bir röportajda Hamming, "Ben de 'Lanet olsun, makine bir hata algılayabiliyorsa, neden hatanın yerini bulamıyor ve düzeltemiyor?' dedim. Sonraki birkaç yıl boyunca, giderek daha güçlü bir algoritma dizisi geliştirerek hata düzeltme sorunu üzerinde çalıştı. 1950'de, bugün ECC belleği gibi uygulamalarda kullanımda olan, şimdi Hamming kodu olarak bilinen şeyi yayınladı .

Hamming'den önceki kodlar

Hamming kodlarından önce bir dizi basit hata tespit kodu kullanıldı, ancak hiçbiri aynı uzay yükünde Hamming kodları kadar etkili değildi.

parite

Eşlik tek ekler biraz önceki veri olanlar (birinin değerleri ile bit pozisyonları) sayısı olup olmadığını gösterir da veya tek . İletimde tek sayıda bit değiştirilirse, mesaj pariteyi değiştirir ve hata bu noktada tespit edilebilir; ancak değişen bit, eşlik bitinin kendisi olabilir. En yaygın kural, bir eşlik değerinin verilerde tek sayıda bir olduğunu ve sıfır eşlik değerinin çift sayıda bir olduğunu göstermesidir. Değişen bit sayısı çift ise, kontrol biti geçerli olacak ve hata tespit edilmeyecektir.

Ayrıca parite, tespit edebilse bile, hatayı hangi bitin içerdiğini göstermez. Veriler tamamen atılmalı ve sıfırdan yeniden iletilmelidir. Gürültülü bir iletim ortamında başarılı bir iletim uzun zaman alabilir veya hiç gerçekleşmeyebilir. Bununla birlikte, eşlik denetiminin kalitesi düşük olsa da, yalnızca tek bir bit kullandığından, bu yöntem en az ek yükü sağlar.

Beşte iki kod

Beşte ikisi kodu, tam olarak üç 0 ve iki 1'den oluşan beş bit kullanan bir kodlama şemasıdır. Bu, 0-9 arasındaki rakamları temsil etmeye yetecek kadar on olası kombinasyon sağlar. Bu şema, tüm tek bit hatalarını, tüm tek numaralı bit hatalarını ve bazı çift numaralı bit hatalarını (örneğin her iki 1 bitin çevrilmesi) algılayabilir. Ancak yine de bu hataların hiçbirini düzeltemez.

Tekrarlama

O sırada kullanılan başka bir kod, doğru bir şekilde gönderildiğinden emin olmak için her veri bitini birden çok kez tekrarladı. Örneğin, gönderilecek veri biti 1 ise, n = 3 tekrar kodu 111'i gönderir. Alınan üç bit aynı değilse, iletim sırasında bir hata oluştu. Kanal yeterince temizse, çoğu zaman her üçlüde yalnızca bir bit değişecektir. Bu nedenle, 001, 010 ve 100'ün her biri 0 bit'e karşılık gelirken, 110, 101 ve 011 1 bit'e karşılık gelir ve aynı olan daha fazla sayıda basamak ('0' veya '1') ne olduğunu gösterir. veri biti olmalıdır. Hataların varlığında orijinal mesajı yeniden oluşturma yeteneğine sahip bir kod, hata düzeltme kodu olarak bilinir . Bu üçlü tekrar kodu, iki eşlik biti ve 2 ² − 2 − 1 = 1 veri biti olduğundan m = 2 olan bir Hamming kodudur .

Ancak bu tür kodlar tüm hataları doğru şekilde onaramaz. Örneğimizde, kanal iki bit çevirirse ve alıcı 001 alırsa, sistem hatayı algılar, ancak orijinal bitin 0 olduğu sonucuna varır, bu yanlıştır. Bit dizisinin boyutunu dörde çıkarırsak, tüm iki bitlik hataları tespit edebiliriz ancak bunları düzeltemeyiz (eşlik bitlerinin sayısı eşittir); beş bitte, tüm iki bitlik hataları hem tespit edebilir hem de düzeltebiliriz, ancak üç bitlik hataların hepsini değil.

Ayrıca, eşlik bit dizisinin boyutunu artırmak verimsizdir, orijinal durumumuzda verimi üç kat azaltır ve daha fazla hatayı tespit etmek ve düzeltmek için her bir bitin çoğaltılma sayısını artırdıkça verimlilik büyük ölçüde düşer.

Açıklama

Bir mesaja daha fazla hata düzeltme biti dahil edilirse ve bu bitler, farklı yanlış bitler farklı hata sonuçları üretecek şekilde düzenlenebilirse, bozuk bitler tanımlanabilir. Yedi bitlik bir mesajda, yedi olası tek bitlik hata vardır, bu nedenle üç hata kontrol biti potansiyel olarak yalnızca bir hatanın meydana geldiğini değil, aynı zamanda hangi bitin hataya neden olduğunu da belirtebilir.

Hamming, beşte ikisi de dahil olmak üzere mevcut kodlama şemalarını inceledi ve kavramlarını genelleştirdi. Başlangıç ​​olarak, bir bloktaki veri bitlerinin ve hata düzeltme bitlerinin sayısı da dahil olmak üzere sistemi tanımlamak için bir terminoloji geliştirdi . Örneğin eşlik, herhangi bir veri kelimesi için tek bir bit içerir, bu nedenle, ASCII kelimelerinin yedi bit olduğu varsayıldığında , Hamming bunu , yedisi veri olmak üzere toplam sekiz bitlik bir (8,7) kod olarak tanımladı . Tekrarlama örneği , aynı mantığı izleyerek (3,1) olacaktır . Kod oranı eden tekrar, örneğin, 1/3, birinci bölü saniye numarasıdır.

Hamming ayrıca iki veya daha fazla bitin çevrilmesiyle ilgili sorunları fark etti ve bunu "mesafe" olarak tanımladı (şimdi ondan sonra Hamming mesafesi olarak adlandırılıyor ). Parite 2'lik bir mesafeye sahiptir, bu nedenle bir bitlik çevirme algılanabilir ancak düzeltilemez ve herhangi iki bitlik çevirme görünmez olacaktır. (3,1) tekrarının mesafesi 3'tür, çünkü görünür hata olmadan başka bir kod sözcüğü elde etmek için üç bitin aynı üçlüde çevrilmesi gerekir. Bir bitlik hataları düzeltebilir veya iki bitlik hataları algılayabilir, ancak düzeltemez. Bir (4,1) tekrar (her bit dört kez tekrarlanır) 4'lük bir mesafeye sahiptir, bu nedenle üç bitin çevrilmesi algılanabilir, ancak düzeltilemez. Aynı grupta üç bit çevrildiğinde, düzeltmeye çalışmanın yanlış kod sözcüğü üreteceği durumlar olabilir. Genel olarak, k mesafesine sahip bir kod, k − 1 hatalarını saptayabilir ancak düzeltemez .

Hamming aynı anda iki sorunla ilgilendi: mesafeyi mümkün olduğunca artırmak, aynı zamanda kod hızını mümkün olduğunca artırmak. 1940'larda, mevcut kodlarda çarpıcı iyileştirmeler olan birkaç kodlama şeması geliştirdi. Tüm sistemlerinin anahtarı, eşlik bitlerinin üst üste binmesiydi, böylece verileri olduğu kadar birbirlerini de kontrol etmeyi başardılar.

Genel algoritma

Aşağıdaki genel algoritma, herhangi bir sayıda bit için tek hata düzeltme (SEC) kodu üretir. Ana fikri hata düzeltme bitleri seçmektir endeks-XOR (yani XOR Biz hata olarak (ikilik sistemde) vb pozisyonları 1, 10, 100, kullanmak 0. bir 1 içeren tüm bit pozisyonları) 'dir - hata düzeltme bitlerini, tüm mesajın indeks-XOR'u 0 olacak şekilde ayarlamanın mümkün olduğunu garanti eden düzeltme bitleri. Alıcı, indeks-XOR 0'a sahip bir dize alırsa, herhangi bir bozulma olmadığı sonucuna varabilirler ve aksi takdirde, indeks-XOR, bozuk bitin indeksini gösterir.

Aşağıdaki açıklamadan bir algoritma çıkarılabilir:

1. Bitleri 1'den başlayarak numaralandırın: bit 1, 2, 3, 4, 5, 6, 7, vb.
2. Bit numaralarını ikili olarak yazın: 1, 10, 11, 100, 101, 110, 111, vb.
3. İkinin gücü olan tüm bit konumları (konumlarının ikili biçiminde tek bir 1 biti vardır) eşlik bitleridir: 1, 2, 4, 8, vb. (1, 10, 100, 1000)
4. Konumlarının ikili biçiminde iki veya daha fazla 1 bit içeren diğer tüm bit konumları veri bitleridir.
5. Her veri biti, bit konumunun ikili biçimi tarafından belirlendiği gibi, 2 veya daha fazla eşlik bitinden oluşan benzersiz bir sete dahil edilir.
   1. Eşlik biti 1, en az anlamlı bit kümesine sahip tüm bit konumlarını kapsar : bit 1 (eşlik bitinin kendisi), 3, 5, 7, 9, vb.
   2. Eşlik biti 2, ikinci en az anlamlı bit setine sahip tüm bit konumlarını kapsar : bitler 2-3, 6-7, 10-11, vb.
   3. Eşlik biti 4, üçüncü en az anlamlı bit setine sahip tüm bit konumlarını kapsar : bitler 4–7, 12–15, 20–23, vb.
   4. Eşlik biti 8, dördüncü en az anlamlı bit setine sahip tüm bit konumlarını kapsar : bit 8–15, 24-31, 40–47, vb.
   5. Genel olarak her eşlik biti, eşlik konumunun bitsel AND'sinin ve bit konumunun sıfır olmadığı tüm bitleri kapsar.

Kodlanacak veri baytı 10011010 ise, veri sözcüğü (eşlik bitlerini temsil etmek için _ kullanılarak) __1_001_1010 olur ve kod sözcüğü 011100101010 olur.

Çift veya tek parite seçimi önemsizdir, ancak hem kodlama hem de kod çözme için aynı seçim kullanılmalıdır.

Bu genel kural görsel olarak gösterilebilir:

Bit konumu		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	…
Kodlanmış veri bitleri		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
Parite bit kapsamı	p1
	p2
	p4
	p8
	p16

Gösterilen yalnızca 20 kodlanmış bittir (5 parite, 15 veri), ancak model süresiz olarak devam eder. Görsel incelemeden görülebilen Hamming Kodları ile ilgili en önemli şey, verilen herhangi bir bitin benzersiz bir eşlik bitleri kümesine dahil edilmesidir. Hataları kontrol etmek için tüm eşlik bitlerini kontrol edin. Hata sendromu adı verilen hata modeli, hatalı biti tanımlar. Tüm eşlik bitleri doğruysa, hata yoktur. Aksi takdirde, hatalı eşlik bitlerinin konumlarının toplamı hatalı biti tanımlar. Örneğin, 1, 2 ve 8 konumlarındaki eşlik bitleri bir hatayı gösteriyorsa, o zaman bit 1+2+8=11 hatalıdır. Yalnızca bir eşlik biti bir hatayı gösteriyorsa, eşlik bitinin kendisi hatalıdır.

İle m parite bitleri, 1 bit kadar kaplanabilir. Eşlik bitlerini indirdikten sonra, bitler veri olarak kullanılmak üzere kalır. As m değişir, hepimiz mümkün Hamming kodları almak: ${\ Displaystyle 2^{m}-1}$${\ Displaystyle 2^{m}-m-1}$

parite bitleri	Toplam bit	Veri bitleri	İsim	Oran
2	3	1	Hamming(3,1) (Üçlü tekrar kodu )	1/3 ≈ 0.333
3	7	4	çekiçleme(7,4)	4/7 ≈ 0,571
4	15	11	Hamming(15,11)	11/15 ≈ 0.733
5	31	26	çekiçleme(31,26)	26/31 ≈ 0.839
6	63	57	Hamming(63,57)	57/63 ≈ 0.905
7	127	120	Çekiçleme(127,120)	120/127 ≈ 0.945
8	255	247	Çekiçleme(255,247)	247/255 ≈ 0.969
…
m	${\görüntüleme stili n=2^{m}-1}$	${\görüntüleme stili k=2^{m}-m-1}$	çekiçleme${\görüntüleme stili (2^{m}-1,2^{m}-m-1)}$	${\ Displaystyle (2^{m}-m-1)/(2^{m}-1)}$

Ek pariteli Hamming kodları (SECDED)

Hamming kodlarının minimum mesafesi 3'tür; bu, kod çözücünün tek bir hatayı algılayıp düzeltebileceği, ancak bazı kod sözcüklerinin çift bitlik hatasını farklı bir kod sözcüğün tek bitlik hatasından ayırt edemeyeceği anlamına gelir. Bu nedenle, bazı çift bitlik hataların kodu, tek bitlik hatalarmış gibi hatalı bir şekilde çözülecek ve bu nedenle, herhangi bir düzeltme yapılmadığı sürece algılanmayacaktır.

Bu eksikliği gidermek için Hamming kodları ekstra bir eşlik biti ile genişletilebilir. Bu yolla, Hamming kodunun minimum mesafesini 4'e çıkarmak mümkündür, bu da kod çözücünün tek bitlik hataları ve iki bitlik hataları ayırt etmesine olanak tanır. Böylece kod çözücü, tek bir hatayı tespit edip düzeltebilir ve aynı zamanda bir çift hatayı tespit edebilir (ama doğru değil).

Kod çözücü hataları düzeltmeye çalışmazsa, üçlü bit hatalarını güvenilir bir şekilde algılayabilir. Kod çözücü hataları düzeltirse, bazı üçlü hatalar tekli hatalarla karıştırılacak ve yanlış değere "düzeltilecektir". Bu nedenle hata düzeltme, kesinlik (üçlü bit hatalarını güvenilir bir şekilde tespit etme yeteneği) ile esneklik (tek bitlik hatalar karşısında çalışmaya devam etme yeteneği) arasında bir dengedir.

Bu genişletilmiş Hamming kodu, SECDED ( tek hata düzeltme, çift hata algılama ) olarak bilinen bilgisayar bellek sistemlerinde popülerdir . Özellikle popüler olan (72,64) kodu, kesilmiş (127,120) Hamming kodu artı ek bir eşlik bitidir ve (9,8) parite koduyla aynı alan ek yüküne sahiptir.

[7,4] Hamming kodu

Dört veri biti ve üç eşlik bitinin ve hangi eşlik bitlerinin hangi veri bitlerine uygulandığının grafiksel gösterimi

1950'de Hamming, [7,4] Hamming kodunu tanıttı. Üç eşlik biti ekleyerek dört veri bitini yedi bit olarak kodlar. Tek bitlik hataları algılayabilir ve düzeltebilir. Genel bir eşlik bitinin eklenmesiyle, çift bit hatalarını da algılayabilir (ancak düzeltemez).

G ve H İnşaatı

Matris , lineer ( n , k ) kodunun (kanonik) üreteç matrisi olarak adlandırılır , ${\displaystyle \mathbf {G} :={\begin{pmatrix}{\begin{array}{c|c}I_{k}&-A^{\text{T}}\\\end{dizi}} \end{pmatrix}}}$

ve eşlik kontrol matrisi olarak adlandırılır . ${\displaystyle \mathbf {H} :={\başlangıç{pmatrix}{\begin{array}{c|c}A&I_{nk}\\\end{dizi}}\end{pmatrix}}}$

Bu, standart (veya sistematik) biçimde G ve H'nin yapısıdır . Formdan bağımsız olarak, doğrusal blok kodları için G ve H aşağıdakileri sağlamalıdır:

${\displaystyle \mathbf {H} \,\mathbf {G} ^{\text{T}}=\mathbf {0} }$, bir tamamen sıfır matris.

[7, 4, 3] = [ n , k , d ] = [2 ^m − 1, 2 ^m −1− m , 3] olduğundan. Parite kontrol matrisi , H Hamming kodu uzunluğu her sütun listesi ile oluşturulur m çiftler halinde bağımsızdır.

Böylece H , sol tarafı sıfırdan farklı n-tüplerin tümü olan bir matristir, burada matrisin sütunlarındaki n-tuple'ların sırası önemli değildir. Sağ taraf sadece ( n - k ) - birim matrisidir .

Böylece G elde edilebilir H sol tarafının devrik alarak H kimliğin k ile kimlik matrisin sol taraftaki G .

Kod oluşturucu matrisi ve eşlik denetimi matrisi : ${\displaystyle \mathbf {G} }$ ${\displaystyle \mathbf {H} }$

${\displaystyle \mathbf {G} :={\başlangıç{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&1&1&1&1\\\end{pmatrix}} _{4,7$

ve

${\displaystyle \mathbf {H} :={\başlangıç{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\\\end{pmatrix}}_{3,7}.}$

Son olarak, bu matrisler aşağıdaki işlemlerle eşdeğer sistematik olmayan kodlara dönüştürülebilir:

• Sütun permütasyonları (sütunları değiştirme)
• Temel satır işlemleri (bir satırın doğrusal bir satır kombinasyonu ile değiştirilmesi)

kodlama

Örnek

Yukarıdaki matristen 2 ^k = 2 ⁴ = 16 kod sözcüğümüz var. İkili veri bitlerinin bir satır vektörü olsun . 16 olası veri vektöründen herhangi biri için kod sözcüğü , toplama işleminin modulo-2 yapıldığı standart matris ürünü tarafından verilir . ${\displaystyle {\vec {a}}}$${\displaystyle {\vec {a}}=[a_{1},a_{2},a_{3},a_{4}],\quad a_{i}\in \{0,1\}}$${\görüntüleme stili {\vec {x}}}$${\displaystyle {\vec {a}}}$${\displaystyle {\vec {x}}={\vec {a}}G}$

Örneğin, izin verin . Jeneratör matrisini yukarıdan kullanarak elde ederiz (toplaya modulo 2 uyguladıktan sonra), ${\displaystyle {\vec {a}}=[1,0,1,1]}$${\görüntüleme stili G}$

${\displaystyle {\vec {x}}={\vec {a}}G={\başlangıç{pmatrix}1&0&1&1\end{pmatrix}}{\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&1&0&1\\0&0&1&1&1\&1 \\end{pmatrix}}={\begin{pmatrix}1&0&1&1&2&3&2\end{pmatrix}}={\begin{pmatrix}1&0&1&1&0&1&0\end{pmatrix}}}$

[7,4] Ek bir eşlik biti ile Hamming kodu

Aynı [7,4] örnek, ekstra eşlik biti ile yukarıdan. Bu diyagramın, bu örnek için H matrisine karşılık gelmesi amaçlanmamıştır.

[7,4] Hamming kodu, (7,4) kodlanmış kelimenin üstüne fazladan bir eşlik biti eklenerek kolayca bir [8,4] koduna genişletilebilir (bkz. Hamming(7,4) ). Bu, revize edilmiş matrislerle özetlenebilir:

${\displaystyle \mathbf {G} :={\başlangıç{pmatrix}1&1&1&0&0&0&0&1\\1&0&0&1&1&0&0&1\\0&1&0&1&0&1&0&1\\1&1&0&1&0&0&1&0\}_{pmatrix}{pmatrix}$

ve

${\displaystyle \mathbf {H} :={\başlangıç{pmatrix}1&0&1&0&1&0&1&0\\0&1&1&0&0&1&1&0\\0&0&0&1&1&1&1&0\\1&1&1&1&1&1&1\end}_{pmatrix}{pmatrix}.{pmatrix}$

H'nin standart biçimde olmadığına dikkat edin. G'yi elde etmek için, sistematik biçimde H'ye eşdeğer bir matris elde etmek için temel satır işlemleri kullanılabilir:

${\displaystyle \mathbf {H} =\left({\begin{array}{cccc|cccc}0&1&1&1&1&0&0&0\\1&0&1&1&0&1&0&0\\1&1&0&1&0&0&1&0\\1&1&1&1&1&0\\1&1&1&1&1&0\end}}{&1&0&0}}$

Örneğin, bu matristeki ilk satır, sistematik olmayan biçimde H'nin ikinci ve üçüncü satırlarının toplamıdır. Yukarıdan Hamming kodları için sistematik yapı kullanılarak, A matrisi açıktır ve G'nin sistematik formu şu şekilde yazılır:

${\displaystyle \mathbf {G} =\left({\begin{array}{cccc|cccc}1&0&0&0&0&1&1&1\\0&1&0&0&1&0&1&1\\0&0&1&0&1&1&0&1\\0&0&0&1&1\end}}{&1&1&1&1}.$

G'nin sistematik olmayan formu, bu matrise uyacak şekilde satır indirgenebilir (temel satır işlemleri kullanılarak).

Dördüncü satırın eklenmesi, tüm kod sözcüğü bitlerinin (veri ve eşlik) toplamını dördüncü eşlik biti olarak etkin bir şekilde hesaplar.

Örneğin, 1011 (bu bölümün başındaki G'nin sistematik olmayan formu kullanılarak) 01 1 0 011 0 olarak kodlanmıştır , burada mavi rakamlar veridir; kırmızı rakamlar [7,4] Hamming kodundaki eşlik bitleridir; ve yeşil rakam [8,4] kodu tarafından eklenen eşlik bitidir. Yeşil rakam, [7,4] kod sözcüklerinin paritesini çift yapar.

Son olarak, minimum mesafenin [7,4] kodunda 3'ten [8,4] kodunda 4'e yükseldiği gösterilebilir. Bu nedenle kod [8,4] Hamming kodu olarak tanımlanabilir.

[8,4] Hamming kodunu çözmek için önce eşlik bitini kontrol edin. Eşlik biti bir hatayı gösteriyorsa, tek hata düzeltmesi ([7,4] Hamming kodu), eşlik bitini gösteren "hata yok" ile hata konumunu gösterecektir. Eşlik biti doğruysa, tek hata düzeltmesi (bit düzeyinde) özel veya iki hata konumunu gösterecektir. Konumlar eşitse ("hata yok"), o zaman çift bitlik bir hata oluşmamıştır veya kendini iptal etmiştir. Aksi takdirde, bir çift bit hatası oluştu.

Ayrıca bakınız

Notlar

Referanslar

Dış bağlantılar

• Hamming Kodlarının Görsel Açıklaması
• Hamming mesafelerini hesaplamak için CGI betiği (R. Tervo, UNB, Kanada'dan)
• Hamming kodunu hesaplama aracı