Matriks Pemeriksa Paritas
Setiap kode linear atas GF(2) — bidang dengan hanya 0 dan 1, aritmetika modulo 2 — memiliki matriks pemeriksa paritas H. Untuk kode Hamming (7,4), H adalah matriks 3×7 yang kolomnya adalah representasi biner dari 1 hingga 7:
``
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
``
Kolom j dari H adalah representasi biner dari j. Ini mengapa sindrom s = Hr secara langsung menamakan posisi kesalahan.
Peta H: GF(2)^7 → GF(2)^3 adalah peta linear (perkalian matriks mod 2). Kernelnya ker(H) = { r : Hr = 0 } adalah tepat himpunan codeword yang sah.
Penghitungan dimensi: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. Jadi ada 2^4 = 16 codeword. Ini mengkonfirmasi 4 bit pesan.
Kode sebagai Kernel
Sebuah kata c ∈ {0,1}^7 adalah codeword yang sah jika dan hanya jika Hc = 0 (mod 2). Ini adalah persamaan yang menentukan kode linear.
Contoh: c = 0011001. Periksa Hc mod 2:
``
Baris 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Baris 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Baris 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. Jadi 0011001 adalah codeword yang sah untuk kode Hamming (7,4).
Coset dari Kode
Codeword C = ker(H) membentuk subgrup dari GF(2)^7. Setiap kata lain dalam GF(2)^7 berada dalam tepat satu coset dari C.
Definisi coset: untuk kata apapun e, coset C + e = { c + e : c ∈ C }.
Dua kata berada dalam coset yang sama jika dan hanya jika perbedaannya adalah codeword — ekuivalen, jika mereka memiliki sindrom yang sama: H(r₁) = H(r₂) iff H(r₁ − r₂) = 0 iff r₁ − r₂ ∈ C.
Peta sindrom H menginduksi isomorfisme GF(2)^7 / C ≅ GF(2)^3. Dengan |C| = 16 dan |GF(2)^7| = 128: ada tepat 128/16 = 8 coset, satu untuk setiap nilai sindrom dalam GF(2)^3.
Larik standar: daftar satu pemimpin coset per coset — kata dengan berat Hamming minimum dalam coset itu. Untuk perbaikan kesalahan tunggal, setiap sindrom bukan nol secara unik bersesuaian dengan pola kesalahan berat-1 (satu 1 di salah satu dari 7 posisi). Itu mengapa 7 pola kesalahan + 1 tidak-ada-kesalahan = 8 coset = 2^3.
Dekoding via Pemimpin Coset
Algoritma dekoding: terima r → hitung s = Hr → cari pemimpin coset e_s (kesalahan kanonik untuk sindrom s) → keluarkan r − e_s = r + e_s (sama dalam GF(2)).
Untuk kode (7,4), 8 pemimpin coset adalah: 0000000 (sindrom 000), 1000000 (sindrom 001), 0100000 (sindrom 010), 0010000 (sindrom 011), 0001000 (sindrom 100), 0000100 (sindrom 101), 0000010 (sindrom 110), 0000001 (sindrom 111).
Mengapa (7,4) Sempurna
Kode C ⊆ GF(2)^n dengan jarak minimum 3 memperbaiki semua kesalahan tunggal. Setiap codeword c memiliki bola Hamming dengan jari-jari 1: pusat c dan tetangganya sebanyak n (pola kesalahan berat-1). Volume bola = 1 + n.
Untuk n = 7: volume bola = 8. Dengan 16 codeword: 16 × 8 = 128 = 2^7. Bola-bola mengubin GF(2)^7 dengan sempurna — tidak ada titik yang tertinggal, tidak ada titik yang tertutup dua kali.
Ini adalah definisi dari kode sempurna: M · Vol(n, t) = 2^n. Kode sempurna perbaikan kesalahan-tunggal biner (t=1) hanya ada untuk parameter spesifik: (7,4), (15,11), (23,12) (kode Golay biner), dan secara trivial n = 2^r − 1, k = n − r untuk r ≥ 2 apapun.
Geometrinya: GF(2)^7 terdekomposisi menjadi tepat 8 orbit di bawah aksi kode sebagai partisi coset. Setiap orbit adalah coset; setiap coset memiliki sindrom unik. Peta sindrom H adalah bijeksi dari coset ke GF(2)^3.
Argumen Penghitungan
Untuk kode perbaikan kesalahan-tunggal sempurna pada n = 2^r − 1 bit dengan r bit pemeriksa paritas:
- Jumlah codeword: M = 2^k = 2^(n−r)
- Volume bola: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Total tertutup: M × Vol = 2^(n−r) × 2^r = 2^n ✓
Fakta bahwa Vol(n,1) = 2^r ketika n = 2^r − 1 adalah apa yang membuat kode sempurna mungkin pada panjang-panjang ini. Pada panjang lain, 1 + n bukan pangkat 2, dan kode biner perbaikan kesalahan-tunggal sempurna tidak dapat ada.
Matriks Generator & Dualitas
Matriks pemeriksa paritas H mendefinisikan kode melalui kernel. Dualnya: matriks generator G yang baris-barisnya membentuk basis untuk ker(H).
Untuk kode (7,4): G adalah matriks 4×7. Setiap codeword c = mG untuk beberapa vektor pesan m ∈ GF(2)^4. Baris-baris G menjangkau kode; baris-baris H menjangkau ruang null dari kode.
Hubungan kunci: HG^T = 0 (mod 2). Setiap baris G ada dalam ker(H); setiap baris H mengeliminasi setiap baris G.
Kode dual: C⊥ = ker(G^T) = image(H^T). Untuk kode (7,4), dualnya adalah kode (7,3) — kode [7,3,4] dengan jarak minimum 4.
Geometri dualitas: C dan C⊥ adalah subruang ortogonal dari GF(2)^7. Seluruh ruang terdekomposisi menjadi kode, coset-cosetnya, & struktur dual yang peta sindrom enkode.