Parite Kontrol Matrisi
Her GF(2) üzerinde lineer kod — sadece 0 ve 1'in olduğu alan, 2 modlu aritmetik — bir parite kontrol matrisi H'ye sahiptir. (7,4) Hamming kodu için, H 3x7 matrisdir ve sütunları 1'den 7'ye kadar olan ikili temsilidir:
``
H = [ 0 0 0 1 1 1 1 ] ← Pozisyon numarasındaki 2. basamağı
[ 0 1 1 0 0 1 1 ] ← Pozisyon numarasındaki 1. basamağı
[ 1 0 1 0 1 0 1 ] ← Pozisyon numarasındaki 0. basamağı
``
H'nın j. sütunu, j'nin ikili temsilidir. Bu nedenle, sendrom s = Hr doğrudan hata pozisyonunu adlandırır.
H: GF(2)^7 → GF(2)^3 lineer harita (matris çarpımı mod 2)'dir. Its kernel ker(H) = { r : Hr = 0 } tam olarak geçerli kod sözcüklerinin kümesidir.
Boyut sayımı: dim(ker H) = 7 - rank(H) = 7 - 3 = 4. Bu nedenle, 2^4 = 16 kod sözcüğü vardır. Bu, 4 ileti baytı olduğunu doğrular.
Kodun Kernelsi Olarak Kullanımı
c ∈ {0,1}^7 bir geçerli kod sözcüğü ise ve sadece ve sadece Hc = 0 (mod 2)'dir. Bu, lineer kodların tanımlayıcı denklemidir.
Örnek: c = 0011001. Parite kontrol matrisini mod 2 kullanarak kontrol edin:
``
Satır 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Satır 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Satır 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.
Kodların Kosetleri
Kod sözcükleri C = ker(H) GF(2)^7 grubunun bir alt grubunu oluşturur. GF(2)^7'nin her diğer kelimesi C'nin tam bir kosetine aittir.
Koset Tanımı: herhangi bir kelime e için, koset C + e = { c + e : c ∈ C }.
İki kelime aynı kosete aittir eğer ve yalnızca farkları kod sözcüğüse eğer - yani, aynı sendromlara sahipse: H(r₁) = H(r₂) iff H(r₁ − r₂) = 0 iff r₁ − r₂ ∈ C.
Sendrom haritası H, GF(2)^7 / C ≅ GF(2)^3'yi bir eşleme sağlar. |C| = 16 ve |GF(2)^7| = 128: Herhangi bir sendrom değeri GF(2)^3'de tam 8 koset bulunmaktadır.
Standart Dizi: her bir kosette en düşük Hamming ağırlığına sahip bir lider kelime listelemek. Tek hata düzeltme için, sıfır olmayan her bir sendrom, 7 pozisyonda tek bir 1'in olduğu hata örüntüsüne karşılık gelir. Bu nedenle, 7 hata örüntüsü + 1 hata yok = 8 koset = 2^3.
Koset Liderleri ile Öğesi
Düzeltme algoritması: r'yi al → s = Hr'yi hesapla → s sendromuna karşılık gelen koset liderini e_s (s için en yaygın tek hata) bul → r - e_s = r + e_s (GF(2) içinde aynıdır).
(7,4) kod için, 8 koset lideri vardı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) Neden Mükemmel
En küçük mesafesi 3 olan kod C ⊆ GF(2)^n, tek hataları düzeltir. Her kod sözcüğü c, Hamming topu oluşturur: merkez c ve ağırlık-1 hata örüntüleri olan n'imci komşu (top hacmi).
n = 7 için top hacmi = 8. 16 kod sözcüğü ile: 16 × 8 = 128 = 2^7. Toplar ikiye boyutlu alanı mükemmel bir şekilde döşer - hiçbir nokta kalmaz, hiçbir nokta iki kere kaplanır.
Bu, mükemmel kodların tanımını oluşturur: M · Vol(n, t) = 2^n. Tek hata düzeltme kodları (t=1) sadece belirli parametreler için mevcuttur: (7,4), (15,11), (23,12) (iki boyutlu Golay kodu) ve trivially n = 2^r − 1, k = n − r için herhangi r ≥ 2.
Görev: GF(2)^7, kodu coset bölümleri olarak olan eksende tam olarak 8 orbite ayrılır. Her orbit, bir coset; her coset, bir benzersiz sendroma sahiptir. Sendrom haritası H, cosetleri GF(2)^3'ye GF(2)^3'ye bire bir birleşim sağlar.
Sayım Argumenti
n = 2^r − 1 bitli bir tek hata düzeltme kodunda r kontrol biti ile:
- Kod sözcüklerinin sayısı: M = 2^k = 2^(n−r)
- Top hacmi: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Toplam kapalı alan: M × Vol = 2^(n−r) × 2^r = 2^n ✓
Vol(n,1) = 2^r olduğunda n = 2^r − 1, mükemmel kodların mümkün olmasını sağlar. Diğer uzunluklarda 1 + n, 2'nin bir kuvveti değildir ve iki boyutlu binary single-error-correcting perfect codes olamaz.
Jeneratör Matrisi & Duality
Parite kontrol matrisi H, kodu kernal aracılığıyla tanımlar. Dualet: bir jeneratör matrisi G, whose rows form a basis for ker(H).
(7,4) kod için: G, 4×7 bir matrisdir. Her kod sözcüğü c = mG şeklinde bazı mesaj vektörü m ∈ GF(2)^4 için doğrudur. G'nin satırları kodu oluşturur; H'nin satırları kodu olan null space'ı oluşturur.
Ana ilişki: HG^T = 0 (mod 2). G'nin her satırı H'nin kernalinde; G'nin her satırı H'nin her satırını sıfırlar.
Dualet kod: C⊥ = ker(G^T) = image(H^T). (7,4) kod için, dualet [7,3,4] kodu - minimum mesafe 4 olan bir (7,3) kodudür.
Duality'nin geometrisi: C ve C⊥, GF(2)^7 içindeki dik iki uzaysa. Tüm alan, kodu, kozetlerini ve sendrom haritasını kodlayan dual yapıya bölünür.