პარიტეტის შემოწმების მატრიცა
GF(2) ველის ყველა წრფივი კოდი — ველი მხოლოდ 0 და 1 ციფრებით, არითმეტიკა მოდულო 2 — აქვს პარიტეტის შემოწმების მატრიცა H. (7,4) ჰამინგის კოდისთვის, H არის 3×7 მატრიცა, რომლის სვეტები წარმოადგენს 1-დან 7-მდე რიცხვების ორობით გამოსახულებას:
``
H = [ 0 0 0 1 1 1 1 ] ← პოზიციის ნომრის ბიტი 2
[ 0 1 1 0 0 1 1 ] ← პოზიციის ნომრის ბიტი 1
[ 1 0 1 0 1 0 1 ] ← პოზიციის ნომრის ბიტი 0
``
H-ის სვეტი j არის j რიცხვის ორობითი წარმოდგენა. ეს არის ის, თუ რატომ სინდრომი s = Hr პირდაპირ აღნიშნავს შეცდომის პოზიციას.
გამოსახულება H: GF(2)^7 → GF(2)^3 არის წრფივი გამოსახულება (მატრიცის გამრავლება მოდულო 2). მისი ბირთვი ker(H) = { r : Hr = 0 } არის ზუსტად მოქმედი კოდური სიტყვების სიმრავლე.
განზომილების დათვლა: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. მაშასადამე, არსებობს 2^4 = 16 კოდური სიტყვა. ეს გადამოწმებს 4 ინფორმაციული ბიტის არსებობას.
კოდი როგორც ბირთვი
სიტყვა c ∈ {0,1}^7 არის მოქმედი კოდური სიტყვა თუ და მხოლოდ თუ Hc = 0 (mod 2). ეს არის წრფივი კოდის განმარტებითი განტოლება.
მაგალითი: c = 0011001. შეამოწმეთ Hc mod 2:
``
მწკრივი 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
მწკრივი 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
მწკრივი 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. ამიტომ 0011001 არის (7,4) ჰამინგის კოდის მოქმედი კოდური სიტყვა.
კოდის კოსეტი
კოდური სიტყვები C = ker(H) ქმნიან ქვეჯგუფს GF(2)^7. GF(2)^7-ის ყველა სხვა სიტყვა ეკუთვნის ზუსტად ერთ კოსეტს C.
კოსეტის განმარტება: ნებისმიერი სიტყვა e, კოსეტი C + e = { c + e : c ∈ C }.
ორი სიტყვა ეკუთვნიან იმავე კოსეტს თუ და მხოლოდ თუ მათი სხვაობა არის კოდური სიტყვა — ეკვივალენტურად, თუ მათ აქვთ იგივე სინდრომი: H(r₁) = H(r₂) თუ H(r₁ − r₂) = 0 თუ r₁ − r₂ ∈ C.
სინდრომის გამოსახულება H ინდუცირებს იზომორფიზმს GF(2)^7 / C ≅ GF(2)^3. |C| = 16 და |GF(2)^7| = 128: არის ზუსტად 128/16 = 8 კოსეტი, ერთი თითოეულ სინდრომის მნიშვნელობისთვის GF(2)^3-ში.
სტანდარტული მასივი: თითოეული კოსეტის ერთი კოსეტი ლიდერი — მინიმალური ჰამინგის წონის სიტყვა ამ კოსეტში. ერთი შეცდომის გამოსწორებისთვის, თითოეული არა-ნულოვანი სინდრომი უნიკალურად შეესაბამება წონა-1 შეცდომის ნიმუშს (ერთი 1 7 პოზიციიდან ერთში). ეს არის ის, თუ რატომ 7 შეცდომის ნიმუში + 1 არა-შეცდომა = 8 კოსეტი = 2^3.
დეკოდირება კოსეტი ლიდერის გამოყენებით
დეკოდირების ალგორითმი: მიიღეთ r → გამოთვალეთ s = Hr → ძებნა კოსეტი ლიდერი e_s (კანონიკური შეცდომა სინდრომი s) → გამოტანა r − e_s = r + e_s (იგივე GF(2)-ში).
(7,4) კოდი 8 კოსეტი ლიდერი: 0000000 (სინდრომი 000), 1000000 (სინდრომი 001), 0100000 (სინდრომი 010), 0010000 (სინდრომი 011), 0001000 (სინდრომი 100), 0000100 (სინდრომი 101), 0000010 (სინდრომი 110), 0000001 (სინდრომი 111).
რატომ (7,4) სრულყოფილია
კოდი C ⊆ GF(2)^n მინიმალური მანძილი 3 ასწორებს ყველა ერთი შეცდომა. თითოეული კოდური სიტყვა c აქვს ჰამინგის სფერი რადიუსი 1: ცენტრი c მისი n უშუალო მეზობელი (წონა-1 შეცდომის ნიმუშები). სფერის მოცულობა = 1 + n.
n = 7: სფერის მოცულობა = 8. 16 კოდური სიტყვა: 16 × 8 = 128 = 2^7. სფერი დაფარავს GF(2)^7 სრულყოფილი — არა დაკმაყოფილებული წერტილი, არა ორჯერ დაკმაყოფილებული წერტილი.
ეს არის სრულყოფილი კოდის განმარტება: M · Vol(n, t) = 2^n. სრულყოფილი ერთი-შეცდომის-გამოსწორი კოდი (t=1) არსებობს მხოლოდ კონკრეტული პარამეტრებისთვის: (7,4), (15,11), (23,12) (ორობითი გოლეი კოდი), და ტრივიალურად n = 2^r − 1, k = n − r ნებისმიერი r ≥ 2.
გეომეტრია: GF(2)^7 იშლება ზუსტად 8 ორბიტად კოდის კოსეტი დანაყოფის მოქმედების ქვეშ. თითოეული ორბიტა არის კოსეტი; თითოეული კოსეტი აქვს უნიკალური სინდრომი. სინდრომის გამოსახულება H არის ბიჯეკცია კოსეტიდან GF(2)^3.
დათვლის არგუმენტი
სრულყოფილი ერთი-შეცდომის-გამოსწორი კოდი n = 2^r − 1 ბიტი r პარიტეტის შემოწმების ბიტი:
- კოდური სიტყვების რაოდენობა: M = 2^k = 2^(n−r)
- სფერის მოცულობა: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- მხარდამჭერი მოცულობა: M × Vol = 2^(n−r) × 2^r = 2^n ✓
ფაქტი რომ Vol(n,1) = 2^r როდესაც n = 2^r − 1 ის, რა ქმნის სრულყოფილი კოდები შესაძლო ამ სიგრძეზე. სხვა სიგრძეზე, 1 + n არა 2-ის ხელმძღვანელი, და სრულყოფილი ერთი-შეცდომის-გამოსწორი ორობითი კოდი ვერ აკეთებს არსებობას.
წამომქმედი მატრიცა & ორმაგობა
პარიტეტის შემოწმების მატრიცა H განმარტავს კოდი ბირთვის საშუალებით. მისი ორმაგი: წამომქმედი მატრიცა G რომლის მწკრივი ქმნიან ker(H) ბაზას.
(7,4) კოდი: G არის 4×7 მატრიცა. ნებისმიერი კოდური სიტყვა c = mG ზოგიერთი საინფორმაციო ვექტორი m ∈ GF(2)^4. G მწკრივი გაშლიან კოდი; H მწკრივი გაშლიან კოდის ნულ სივრცე.
კი ურთიერთობა: HG^T = 0 (mod 2). G-ის ყოველი მწკრივი ხელმძღვანელი ker(H); H-ის ყოველი მწკრივი აღმოხდა G-ის ყოველი მწკრივი.
ორმაგი კოდი: C⊥ = ker(G^T) = image(H^T). (7,4) კოდი, ორმაგი არის [7,3,4] კოდი — [7,3,4] კოდი მინიმალური მანძილი 4.
ორმაგობის გეომეტრია: C და C⊥ ორთოგონალური ქვე-სივრცე GF(2)^7. მთელი სივრცე იშლება კოდი, მისი კოსეტი, და ორმაგი სტრუქტურა რომელი სინდრომი გამოსახულება კოდირებს.