Eşlik Kontrol Matrisi
GF(2) üzerindeki her doğrusal kod — sadece 0 ve 1'den oluşan cisim, modulo 2 aritmetiği — bir eşlik kontrol matrisine H sahiptir. (7,4) Hamming kodu için H, sütunları 1'den 7'ye kadarki sayıların ikili gösterimleri olan 3×7 bir matristir:
``
H = [ 0 0 0 1 1 1 1 ] ← bit 2 of position number
[ 0 1 1 0 0 1 1 ] ← bit 1 of position number
[ 1 0 1 0 1 0 1 ] ← bit 0 of position number
``
H'nin j. sütunu j'nin ikili gösterimidir. Sendrom s = Hr'nin hata konumunu doğrudan belirtmesinin nedeni budur.
Harita H: GF(2)^7 → GF(2)^3 doğrusal bir haritadır (modulo 2 matris çarpımı). Çekirdeği ker(H) = { r : Hr = 0 }, tam olarak geçerli kod sözcükleri kümesidir.
Boyut sayısı: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. Bu nedenle 2^4 = 16 kod sözcüğü vardır. Bu, 4 ileti bitini doğrular.
Kod Çekirdeği Olarak
Bir sözcük c ∈ {0,1}^7, ancak ve ancak Hc = 0 (mod 2) ise geçerli bir kod sözcüğüdür. Bu, doğrusal bir kodun tanımlayıcı denklemidir.
Örnek: c = 0011001. Hc mod 2'yi kontrol edin:
``
Row 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Row 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Row 3: 1·0+0·0+1·1+0·1+1·0+0·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
``
Hc = 000. Bu nedenle 0011001 geçerli bir kod sözcüğüdür.
Kodun Kosetleri
Kod sözcükleri C = ker(H), GF(2)^7'nin bir alt grubunu oluşturur. GF(2)^7'deki diğer her sözcük tam olarak C'nin bir kosetine aittir.
Koset tanımı: herhangi bir sözcük e için, koset C + e = { c + e : c ∈ C }.
İki sözcük aynı kosete aittirlerse, ancak ve ancak farkları bir kod sözcüğüyse — eşdeğer olarak, aynı sendroma sahiplerse: H(r₁) = H(r₂) ancak ve ancak H(r₁ − r₂) = 0 ancak ve ancak r₁ − r₂ ∈ C.
Sendrom haritası H bir izomorfizmi indükler GF(2)^7 / C ≅ GF(2)^3. |C| = 16 ve |GF(2)^7| = 128 ile: tam olarak 128/16 = 8 koset vardır, GF(2)^3'deki her sendrom değeri için bir tane.
Standart dizi: her koset başına bir koset lideri listesi — o kosette minimum Hamming ağırlığının sözcüğü. Tek hata düzeltmesi için, her sıfır olmayan sendrom benzersiz olarak bir ağırlık-1 hata deseni (yedi konumdan birinde tek bir 1) karşılık gelir. Bu nedenle 7 hata deseni + 1 hata yok = 8 koset = 2^3.
Koset Liderleriyle Dekodlama
Dekodlama algoritması: r alınır → s = Hr'yi hesapla → koset lideri e_s'yi bul (sendrom s için standart hata) → r − e_s = r + e_s çıktısını ver (GF(2)'de aynı).
(7,4) kodu için, 8 koset lideri şunlardır: 0000000 (sendrom 000), 1000000 (sendrom 001), 0100000 (sendrom 010), 0010000 (sendrom 011), 0001000 (sendrom 100), 0000100 (sendrom 101), 0000010 (sendrom 110), 0000001 (sendrom 111).
(7,4)'ün Neden Mükemmel Olduğu
Minimum uzaklığı 3 olan kod C ⊆ GF(2)^n tüm tek hataları düzeltir. Her kod sözcüğü c'nin Hamming küresi yarıçapı 1: merkez c ve n tane yakın komşusu (ağırlık-1 hata desenleri). Küre hacmi = 1 + n.
n = 7 için: küre hacmi = 8. 16 kod sözcüğü ile: 16 × 8 = 128 = 2^7. Küreler GF(2)^7'yi mükemmel şekilde kaparlar — hiçbir nokta açıkta değil, hiçbir nokta iki kez kaplanmamış.
Bu, mükemmel kod'un tanımıdır: M · Vol(n, t) = 2^n. Mükemmel tek-hata-düzeltme kodları (t=1) sadece belirli parametreler için vardır: (7,4), (15,11), (23,12) (ikili Golay kodu) ve önemsiz şekilde n = 2^r − 1, k = n − r herhangi bir r ≥ 2 için.
Geometri: GF(2)^7, kod tarafından harekete geçiş altında tam olarak 8 yörüngeye ayrışır, bir koset bölümü olarak. Her yörünge bir kosettir; her koset benzersiz bir sendroma sahiptir. Sendrom haritası H, kosetlerden GF(2)^3'e bir bijeksiyondur.
Sayma Argümanı
n = 2^r − 1 bit üzerinde r eşlik kontrol biti olan mükemmel tek-hata-düzeltme kodu için:
- Kod sözcüğü sayısı: M = 2^k = 2^(n−r)
- Küre hacmi: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Toplam kaplanmış: M × Vol = 2^(n−r) × 2^r = 2^n ✓
n = 2^r − 1 olduğunda Vol(n,1) = 2^r olması, mükemmel kodların bu uzunluklarda mümkün olmasını sağlayan şeydir. Diğer uzunluklarda, 1 + n 2'nin bir kuvveti değildir ve mükemmel tek-hata-düzeltme ikili kodları var olamaz.
Jeneratör Matrisi & İkilik
Eşlik kontrol matrisi H, çekirdeği aracılığıyla kodu tanımlar. İkili: ker(H) için bir temel oluşturan satırlarına sahip bir jeneratör matrisi G.
(7,4) kodu için: G 4×7 bir matristir. Herhangi bir kod sözcüğü c = mG bazı ileti vektörü m ∈ GF(2)^4 için. G'nin satırları kodu kapsarlar; H'nin satırları kodun null uzayını kapsarlar.
Anahtar ilişki: HG^T = 0 (mod 2). G'nin her satırı ker(H)'dedir; H'nin her satırı G'nin her satırını yok eder.
İkili kod: C⊥ = ker(G^T) = image(H^T). (7,4) kodu için, ikili bir (7,3) koddur — minimum uzaklığı 4 olan [7,3,4] bir koddur.
İkilik geometrisi: C ve C⊥, GF(2)^7'nin diktir alt uzaylar. Tüm uzay, kod, kosetleri ve sendrom haritasının kodladığı ikili yapıya ayrışır.