جدول التحقق من صحة الفوائض
كل رمز خطي فوق GF(2) - المجال الذي يحتوي فقط على 0 و 1، حسابية modulo 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 من رقم العمود
``
عمود j من H هو تمثيل البيني للعدد j. هذا السبب وراء أن السندروم s = Hr يسمي مباشرة موقع الخطأ.
الخامس H: GF(2)^7 → GF(2)^3 هو خطية (ضرب المصفوفة modulo 2). نواتئها ker(H) = { r : Hr = 0 } هيexactly مجموعة الكلمات الصحيحة.
تعداد الأبعاد: 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 هو كلمة صحيحة.
ناقصات الكود
الكلمات المفتاحية C = ker(H) تشكل فرعًا من فروع GF(2)^7. كل كلمة أخرى في GF(2)^7 تنتمي إلى ناقص واحد من C.
تعريف الناقص: بالنسبة لكلمة ما e، يكون الناقص C + e = { c + e : c ∈ C }.
تتبادل الكلمات التابعة لنفس الناقص إذا وفقط إذا كانت فرقتهما كلمة مفتاحية — بطرق أخرى، إذا كانا يملكان نفس النمط المتربي: H(r₁) = H(r₂) iff H(r₁ − r₂) = 0 iff r₁ − r₂ ∈ C.
يؤدي الخطان المتربي H إلى توأمة GF(2)^7 / C ≅ GF(2)^3. مع |C| = 16 و|GF(2)^7| = 128: هناك ناقص واحد بالضبط 128/16 = 8 ناقصات، واحدة لكل قيمة نمط متربي في GF(2)^3.
المصفوفة القياسية: قائمة بزعيم الناقص واحد لكل ناقص — الكلمة التي تقل بها درجة هاميلينغ في ذلك الناقص. بالنسبة للتنقيص الوحيد، يتوافق كل نمط متربي غير الصفر بنمط أخطاء وزن 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.
لن = 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 هي بيع بين بين القسائم وقF(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 حيث تتشكل أسطرها قاعدة لنواة H.
في حالة الكود (7,4): G هي مصفوفة 4×7. أي كودورد c = mG حيث m ∈ GF(2)^4 هي فيектор الرسالة. أسطر G تمثل الكود؛ أسطر H تمثل مساحة الصفراء للكود.
العلاقة الرئيسية: HG^T = 0 (mod 2). كل سطر من G في نواة H؛ كل سطر من H يهدم كل سطر من G.
الكود المتبايني: C⊥ = نواة (G^T) = صورة (H^T). بالنسبة للكود (7,4) فإن الكود المتبايني هو كود (7,3) - [7,3,4] الكود مع حد أدنى للمسافة 4.
جغرافيا الدوال: C و C⊥ هما مساحات فرعية متعامدة في GF(2)^7. يتحول الفضاء بأكمله إلى الكود، وعوائل الكود، والمخطط المتبايني الذي يكشف عنه خريطة الأخطاء.