مصفوفة فحص التكافؤ
كل رمز خطي على GF(2) — الحقل الذي يحتوي فقط على 0 و1، الحسابات بالقياس 2 — له مصفوفة فحص التكافؤ H. بالنسبة لرمز Hamming (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 من رقم الموضع
``
العمود j من H هو التمثيل الثنائي لـ 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 (بالقياس 2). هذه هي المعادلة المحددة لرمز خطي.
مثال: c = 0011001. تحقق من Hc بالقياس 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 هو رمز صحيح.
فئات جانبية من الرمز
الرموز 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.
المصفوفة الجدولية: قائمة بقائد جانبي واحد لكل فئة جانبية — الكلمة بأقل وزن Hamming في تلك الفئة. لتصحيح الخطأ الواحد، كل متلازمة غير صفرية تتوافق بشكل فريد مع نمط خطأ وزن 1 (واحد واحد في أحد المواضع السبعة). لهذا السبب 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 كرة Hamming بنصف قطر 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) (رمز Golay الثنائي)، وبشكل تافه 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 (بالقياس 2). كل صف من G في ker(H)؛ كل صف من H يبطل كل صف من G.
الرمز الثنائي: C⊥ = ker(G^T) = image(H^T). بالنسبة لرمز (7,4)، الثنائي هو رمز (7,3) — رمز [7,3,4] بأقل مسافة 4.
هندسة الثنائية: C و C⊥ هما فضاءات متعامدة من GF(2)^7. الفضاء الكامل يتحلل إلى الرمز وفئاته الجانبية والهيكل الثنائي الذي تشفره خريطة المتلازمة.