Ma trận Kiểm tra Chẵn lẻ
Mỗi mã tuyến tính trên GF(2) — trường chỉ có 0 và 1, số học modulo 2 — đều có một ma trận kiểm tra chẵn lẻ H. Đối với mã Hamming (7,4), H là ma trận 3×7 có các cột là biểu diễn nhị phân của 1 đến 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
``
Cột j của H là biểu diễn nhị phân của j. Đây là lý do tại sao hội chứng s = Hr trực tiếp chỉ ra vị trí lỗi.
Ánh xạ H: GF(2)^7 → GF(2)^3 là một ánh xạ tuyến tính (nhân ma trận mod 2). Kernel của nó ker(H) = { r : Hr = 0 } chính là tập hợp các từ mã hợp lệ.
Đếm chiều: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. Vì vậy có 2^4 = 16 từ mã. Điều này xác nhận 4 bit tin nhắn.
Mã như một Kernel
Một từ c ∈ {0,1}^7 là một từ mã hợp lệ nếu và chỉ nếu Hc = 0 (mod 2). Đây là phương trình xác định của một mã tuyến tính.
Ví dụ: c = 0011001. Kiểm tra Hc mod 2:
``
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. Vì vậy 0011001 là một từ mã hợp lệ.
Cosets của Mã
Các từ mã C = ker(H) tạo thành một nhóm con của GF(2)^7. Mỗi từ khác nằm trong chính xác một coset của C.
Định nghĩa Coset: với bất kỳ từ e, coset C + e = { c + e : c ∈ C }.
Hai từ thuộc cùng một coset nếu và chỉ nếu hiệu của chúng là một từ mã — tương đương, nếu chúng có cùng hội chứng: H(r₁) = H(r₂) iff H(r₁ − r₂) = 0 iff r₁ − r₂ ∈ C.
Ánh xạ hội chứng H cảm ứng một đẳng cấu GF(2)^7 / C ≅ GF(2)^3. Với |C| = 16 và |GF(2)^7| = 128: có chính xác 128/16 = 8 cosets, một cho mỗi giá trị hội chứng trong GF(2)^3.
Mảng tiêu chuẩn: liệt kê một lãnh đạo coset cho mỗi coset — từ có trọng Hamming tối thiểu trong coset đó. Đối với sửa lỗi đơn, mỗi hội chứng khác không tương ứng duy nhất với một mẫu lỗi trọng 1 (một 1 duy nhất ở một trong 7 vị trí). Đó là lý do tại sao 7 mẫu lỗi + 1 không lỗi = 8 cosets = 2^3.
Giải mã thông qua Lãnh đạo Coset
Thuật toán giải mã: nhận r → tính s = Hr → tra cứu lãnh đạo coset e_s (mẫu lỗi chính tắc cho hội chứng s) → xuất r − e_s = r + e_s (cùng trong GF(2)).
Đối với mã (7,4), 8 lãnh đạo coset là: 0000000 (hội chứng 000), 1000000 (hội chứng 001), 0100000 (hội chứng 010), 0010000 (hội chứng 011), 0001000 (hội chứng 100), 0000100 (hội chứng 101), 0000010 (hội chứng 110), 0000001 (hội chứng 111).
Tại sao (7,4) là Hoàn hảo
Một mã C ⊆ GF(2)^n với khoảng cách tối thiểu 3 sửa tất cả các lỗi đơn. Mỗi từ mã c có một quả cầu Hamming bán kính 1: tâm c & n hàng xóm gần nhất (mẫu lỗi trọng 1). Thể tích quả cầu = 1 + n.
Đối với n = 7: thể tích quả cầu = 8. Với 16 từ mã: 16 × 8 = 128 = 2^7. Các quả cầu lót GF(2)^7 hoàn hảo — không có điểm nào được để lại, không có điểm nào được phủ hai lần.
Đây là định nghĩa của một mã hoàn hảo: M · Vol(n, t) = 2^n. Các mã nhị phân sửa lỗi đơn hoàn hảo (t=1) tồn tại chỉ với các tham số cụ thể: (7,4), (15,11), (23,12) (mã Golay nhị phân), & một cách tầm thường n = 2^r − 1, k = n − r với bất kỳ r ≥ 2.
Hình học: GF(2)^7 phân rã thành chính xác 8 quỹ đạo dưới tác động của mã như một phân vùng coset. Mỗi quỹ đạo là một coset; mỗi coset có một hội chứng duy nhất. Ánh xạ hội chứng H là một bijection từ cosets đến GF(2)^3.
Đối số Đếm
Đối với một mã sửa lỗi đơn hoàn hảo trên n = 2^r − 1 bit với r bit kiểm tra chẵn lẻ:
- Số từ mã: M = 2^k = 2^(n−r)
- Thể tích quả cầu: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Tổng phủ: M × Vol = 2^(n−r) × 2^r = 2^n ✓
Thực tế là Vol(n,1) = 2^r khi n = 2^r − 1 là điều làm cho mã hoàn hảo có thể tồn tại ở các độ dài này. Ở các độ dài khác, 1 + n không phải là lũy thừa của 2, & mã nhị phân sửa lỗi đơn hoàn hảo không thể tồn tại.
Ma trận Sinh & Tính kép
Ma trận kiểm tra chẵn lẻ H xác định mã thông qua kernel. Mã kép của nó: một ma trận sinh G có các hàng tạo thành cơ sở cho ker(H).
Đối với mã (7,4): G là ma trận 4×7. Bất kỳ từ mã c = mG với vectơ tin nhắn m ∈ GF(2)^4 nào. Các hàng của G bao trùm mã; các hàng của H bao trùm không gian rỗng của mã.
Mối quan hệ chính: HG^T = 0 (mod 2). Mỗi hàng của G nằm trong ker(H); mỗi hàng của H triệt tiêu mỗi hàng của G.
Mã kép: C⊥ = ker(G^T) = image(H^T). Đối với mã (7,4), mã kép là mã (7,3) — mã [7,3,4] với khoảng cách tối thiểu 4.
Hình học của tính kép: C & C⊥ là các không gian con trực giao của GF(2)^7. Toàn bộ không gian phân rã thành mã, các cosets của nó, & cấu trúc kép mà ánh xạ hội chứng mã hóa.