🚴🏿 🕤 🍛 تصحيح الأخطاء المتعددة عند ترميز الرسائل 💻 🏤 🦑

في أنظمة المعلومات ، يكون تبادل الرسائل في شبكات الاتصال أو الحوسبة مصحوبًا بتأثيرات مزعجة للبيئة أو متطفل ، مما يؤدي إلى ظهور تشوهات في الإشارة وأخطاء في الرموز أثناء الإرسال الرقمي. يتم مكافحة هذه الظاهرة باستخدام رموز التصحيح. وصفت سابقًا كود هامنج ، وأوضحت كيفية إصلاح خطأ واحد في كلمة السر. بطبيعة الحال ، نشأ السؤال حول المواقف التي بها عدد كبير من الأخطاء. سننظر اليوم في حالة وجود خطأين في كلمة المرور (خطأ متعدد). من ناحية ، كل شيء من الناحية النظرية بسيط ومفهوم إلى حد ما ، ولكن من ناحية أخرى ، ليس واضحًا على الإطلاق. يعتمد عرض المادة على أعمال إي. بيرلكامب.

أحكام نظرية

أدت فكرة استخدام التكرار المنظم في الرسائل إلى قيام R. Hamming ببناء كود التصحيح الموصوف هنا . يتميز كود التصحيح الخطي (n ، k) بمصفوفة فحص (m × n) H. متطلبات المصفوفة بسيطة: يتطابق عدد الصفوف مع عدد رموز الفحص ، ويجب أن تكون أعمدتها مختلفة عن الصفر ، وكلها مختلفة. علاوة على ذلك ، تصف قيم الأعمدة أرقام المواضع المشغولة في كلمة المرور بأحرف الكلمة التي تشكل عناصر الحقل الأخير.

في كثير من الأحيان ، يستخدم مفكك الشفرة حساب متلازمة محسوبة لتلك الكلمة لتحديد ما إذا كانت الكلمة المرسلة خاطئة. المتلازمة تساوي مجموع أعمدة هذه المصفوفة مضروبًا في مكونات متجه الخطأ. إذا احتوت H على سطور m وكان الرمز يسمح لك بتصحيح أخطاء فردية ، فإن طول الكتلة (كلمة المرور) لا يتجاوز

n \leq 2^{m} - 1

$n≤2^m-1$ ... من المهم أيضًا جدوى المسافة المطلوبة لكلمات الكود من بعضها البعض.

تصل رموز المطرقة إلى هذا الحد. يمكن ترقيم كل موضع لكلمة شفرة هامنج بمتجه ثنائي يتزامن مع العمود المقابل من المصفوفة H. في هذه الحالة ، ستتطابق المتلازمة مباشرة مع رقم الموضع الذي حدث فيه الخطأ (إذا كان هناك خطأ واحد فقط) أو مع المجموع الثنائي للأرقام (إذا كان هناك عدة أخطاء).

ترقيم المتجهات فكرة مثمرة للغاية. علاوة على ذلك ، سوف نفترض

n \leq 2^{m} - 1

$n≤2^m-1$ وأن الموضع i للكلمة مرقم i.

يُطلق على الترقيم الثنائي (مثل هذا التمثيل) محدد موقع الموضع. لنفترض أنك تريد إصلاح جميع الأخطاء المزدوجة والمفردة. على ما يبدو ، سيتطلب هذا تكرارًا كبيرًا في التعليمات البرمجية ، أي يجب أن تحتوي المصفوفة H على صفوف أكثر (ضعف العدد). لذلك ، سنشكل مصفوفة H تتكون من 2 م من الصفوف ومعها

n \leq 2^{m} - 1

$n≤2^m-1$ الأعمدة ، ومن الحكمة اختيار أعمدة مختلفة. بالنسبة للصفوف m الأولى ، سنأخذ المصفوفة السابقة لكود Hamming. هذه هي ناقلات الكلمة الأساسية لكلمة الفضاء.

مثال 1

لنفترض أن m = 5 و n = 31. سيكون من المرغوب فيه الحصول على رمز (n، k) يصحح الأخطاء المزدوجة ، مع مصفوفة تحقق التكافؤ H بالشكل:

بالنسبة للوظائف fj (ξ) المشار إليها في المصفوفة ، من المستحسن الحصول على وظيفة ترسم خرائط مجموعة من ناقلات 5 الأبعاد في حد ذاته. ستحدد الصفوف الخمسة الأخيرة من المصفوفة شفرة Hamming إذا وفقط إذا كانت الوظيفة f عبارة عن انحياز (تبديل).

إذا سمحت لك الأسطر الخمسة الأولى والأخيرة الخمسة بشكل منفصل بتصحيح أخطاء فردية ، فربما تسمح لك معًا بتصحيح خطأين.

يجب أن نتعلم كيف نجمع ونطرح ونضرب ونقسم المتجهات الثنائية 5 الأبعاد ، وتمثيلها بواسطة كثيرات الحدود من الدرجة على الأكثر 4 ، من أجل إيجاد الوظيفة المطلوبة fj (ξ).

مثال 2

00000 ← ← 0

00010 ← ← 1

00011 ← ← x

...

11011 \leftarrow\to х^{4} + х^{3} + х + 1

$11011 ←→ ^4 +^3++1$

يتوافق مجموع وفرق كثيرات الحدود مع مجموع المتجهات واختلافها:

0 ± 0 = 0 ، 0 ± 1 = 1 ، 1 ± 0 = 1 ، 1 ± 1 = 0 ، علامات ± لها نفس المعنى في الحالة الثنائية. ليس الأمر كذلك مع الضرب ، يمكن أن يتجاوز الأس الناتج عن الضرب 4.

مثال 3

(х^{3} + х + 1) х^{4} + х^{3} + х + 1) = х^{7} + х^{6} + х^{5} + 3 х^{4} + 2 х^{3} + х^{2} + 2 х + 1 =

$(^3++1)^4+^3++1)=^7+^6+^5+3^4+2^3+^2+2+1=$

= х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1

$=^7+^6+^5+^4+^2+1$ ...

هناك حاجة إلى طريقة لخفض الدرجات الأكبر من 4.

تسمى (الاختزال) بناء وحدة البقايا وهي متعددة الحدود غير القابلة للاختزال M (x) من الدرجة 5 ؛ تتكون الطريقة في الانتقال من كثيرات الحدود للمنتجات إلى باقيها بعد القسمة على

M (x) = x^{5} + x^{2} + 1

$M(x)=x^5+x^2 + 1$

لهذا السبب

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 = (х^{2} + х + 1) (х^{5} + х^{2} + 1) + х^{3} + х^{2} + х

$^7+^6+^5+^4+^2+1 =(^2+ + 1)(^5 +^2 +1) +^3 +^2 +$ أو

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 \equiv (х^{3} + х^{2} + x) m o d (х^{5} + х^{2} + 1) .

$^7+^6+^5+^4+^2+1 ≡(^3+^2 + x)mod(^5 +^2 +1).$

يقرأ الرمز "مشابه لـ".

بشكل عام A (x) ≡a (x) mod M (x)

إذا وفقط إذا كان هناك كثير الحدود C (x) مثل أن

A (x) = M (x) C (x) + a (x) يتم تقليل معاملات كثيرات الحدود بالوحدة الثانية:

A (x) ≡ a (x) mod (2، M (x)).

خصائص المقارنات الهامة

إذا كان a (x) ≡A (x) mod M (x) و b (x) ≡ B (x) mod M (x) ، ثم

a (x) ± b (x) ≡ A (x) ± B (x) ) mod M (x) و

(x) b (x) - (x) B (x) mod M (x).

علاوة على ذلك ، إذا كانت درجات كثيرات الحدود a (x) و A (x) أقل من درجة M (x) ،

فإنه يتبع من الصيغة a (x) ≡ A (x) mod (2، M (x)) أن a (x) = أ (س).

توجد فئتان مختلفتان من المخلفات في الدرجة degM (x) - أي ، بقدر ما توجد كثيرات حدود مختلفة من الدرجة أقل من م ، أي كم عدد مخلفات القسمة المختلفة التي يمكن أن تكون. التقسيم أكثر صعوبة.

خوارزمية التقسيم

للأرقام.

بالنسبة إلى a و M ، هناك أرقام محددة بشكل فريد q و A ، مثل a = qM + A ، 0 ≤ A ≤ M ،

بالنسبة إلى كثيرات الحدود التي لها معاملات من حقل معين.

في حالة وجود a (x) و M (x) ، هناك كثيرات حدود محددة بشكل فريد q (x) و A (x) مثل a (x) = q (x) M (x) + A (x) ، degA (x) ) <درجة M (x).

يتم توفير إمكانية قسمة كثيرات الحدود بواسطة الخوارزمية الإقليدية.

بالنسبة للأرقام ، يتم وصف مثال على GCD ممتد هنا .

بالنسبة إلى a و b ، يوجد رقمان A و B بحيث تكون aA + bB = (a ، b) ، حيث (a ، b) هي GCD للأرقام a و b.

بالنسبة إلى كثيرات الحدود ذات المعاملات من حقل معين.

في حالة وجود a (x) و b (x) ، توجد كثيرات الحدود A (x) و B (x) بحيث تكون

a (x) A (x) + b (x) B (x) = (a (x)، b (خ)) ،

حيث (a (x)، b (x)) هو القاسم المشترك المقيس لـ a (x) و b (x) من الدرجة الأكبر.

إذا كان لكل من a (x) و M (x) قاسم مشترك d (x) ≠ 1 ، فإن القسمة على a (x) mod M (x) ليست ممكنة دائمًا.

من الواضح أن القسمة على أ (س) تعادل الضرب في أ (س).

بما أنه إذا (أ (س) ، ب (س)) = 1 = GCD ، فوفقًا لخوارزمية إقليدس ، هناك A (x) و B (x) مثل a (x) A (x) + b (x) ب (س) = 1 ، بحيث أ (س) أ (س) ≡ 1 مود ب (س). التحقق من أن كثرة الحدود الثنائية غير قابلة للاختزال على المجال GF (

2^{5}

$2^5$ ) ، عن طريق القسمة المباشرة على جميع القواسم الممكنة ذات الدرجات الأقل من درجة M (x).

مثال 4 .

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ مقسومًا على x و (x + 1) على

القواسم الخطية. نتيجة القسمة ليست صفرا. اقسم على القواسم المربعة

х^{2}, х^{2} + х = х (х + 1), х^{2} + 1, х^{2} + 2 х + 1 = (х + 1)^{2}, х^{2} + х + 1.

$^2 , ^2 +=( +1),^2 +1, ^2 +2 +1= ( +1)^2, ^2 + + 1.$ ... يعطون أرصدة غير صفرية. لا توجد قواسم من الدرجة ≥ 3 ، لأن حاصل ضربهم يعطي الدرجة ≥ 6.

وبالتالي ، يمكن إضافة كثيرات الحدود وطرحها ومضاعفتها وتقسيمها

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ ...

ننتقل إلى البحث عن دالة لمصفوفة فحص التكافؤ H تحدد كود تصحيح خطأ مزدوج بطول الكتلة 31 ومعدل 21/31 ؛ 31-21 = 10 = 2t - رموز التحقق = 10. يجب أن يكون لهذه الوظيفة جذورها أعداد المواضع الخاطئة في كلمة الرمز ، أي عندما يتم استبدال أرقام المواضع في هذه الوظيفة ، فإنها تحولها إلى صفر.

وظيفة البحث

لنفترض أن β1 و β2 هي الأرقام من الشخصيات المشوهة (المواقف) للكلمة. باستخدام تدوين ثنائي الأرقام β1 و β2 ، هذه الأرقام يمكن أن تكون ممثلة على النحو الطبقات بقايا MODULO M (خ) أي حدد التطابق βi → β ⁽ⁱ⁾ (x) - كثيرات الحدود الثنائية من الدرجة <5.

تحدد شروط الاختبار الخمسة الأولى β1 + β2 ؛ يجب أن تحدد المجموعة الثانية من معادلات الاختبار f (1) + f (β2) .

فك يجب تحديد β1 و β2 وفقا لنظام معين:

ماذا ينبغي أن يكون وظيفة و (خ) ؟

أبسط وظيفة هي الضرب بواسطة ثابت f (β) ≡ αβ () modM (x) .

ولكن بعد ذلك ξ2 = αξ1 ، أي معادلات النظام تعتمد. لن تمنح شروط الاختبار الخمسة الجديدة وحدة فك التشفير أي شيء جديد.

وبالمثل ، فإن الوظيفة f (β) = β + α لا تغير الموقف ، لأن ξ2 = ξ1 .

تجربة وظائف الطاقة: خذ أولاً

f (β) = β^{2}

$f(β) = β^2$ ... علاوة على ذلك ،

هذه المعادلات تعتمد أيضًا منذ ذلك الحين

ξ 1^{2} = (β 1 + β 2)^{2} = β 1^{2} + 2 β 1 β 2 + β 2^{2} = β 1^{2} + β 2^{2} = ξ 2

$ξ1^2 =(β1 + β2)^2=β1^2 + 2β1β2 + β2^2 = β1^2 + β2^2 =ξ2$

إذن المعادلة الثانية هي مربع المعادلة الأولى.

محاولة

f (β) = β^{3}

$f(β) = β^3$ ... تغيير شكل معادلة وحدة فك التشفير:

الموقع

ξ 2 = β 1^{3} + β 2^{3} = (β 1 + β 2) (β 1^{2} - β 1 β 2 + β 2^{2}) = ξ 1 (β 1 β 2 - ξ 1^{2}) .

$ξ2 =β1^3 + β2^3=(β1 + β2)(β1^2 -β1β2+ β2^2)=ξ1(β1β2-ξ1^2).$

وذلك ل ξ1 ≠ 0 لدينا

ذلك، β1 و β2 تلبية المعادلة

وبالتالي، إذا حدثت أخطاء بالضبط اثنين، ثم تحديد المواقع التي تلبي هذه المعادلة.

نظرًا لأن هذه المعادلة لها جذران بالضبط في مجال متعدد الحدود الثنائي M (x) ، يمكن لوحدة فك التشفير دائمًا العثور على محددات الموقع المطلوبين.

في حالة حدوث خطأ واحد فقط ، فإن 1 = ξ1 و $β1^2 = ξ2$ ... لذلك ، في هذه الحالة ، يفي الخطأ الوحيد بالمعادلة β + ξ1 = 0 أو 1+ ξ1β ^-1 = 0 .

أخيرًا ، يقوم مفكك التشفير دائمًا بفك التشفير ، إذا لم تحدث أخطاء ، في هذه الحالة ξ1 + ξ2 = 0 .

من الأنسب (في الممارسة العملية) العمل ليس مباشرة مع كثير الحدود الذي جذوره هي محددات الخطأ ، ولكن مع كثير الحدود التي تكون جذورها مشتركة مع محددات المواقع ؛ أولئك. هي معاملات مضاعفة لهم.

من الواضح أنه مع عدم وجود أكثر من خطأين ، يمكن لوحدة فك التشفير تحديد أرقام الخطأ. إذا تم تشويه ثلاثة رموز أو أكثر ، فسيحدث خطأ في فك التشفير أو فشل في فك التشفير.

لذا فإن الوظيفة

f (x) = x^{3}

$f(x) = x^3$ مناسبة لبناء الصفوف الخمسة السفلية من مصفوفة الفحص H لكود ثنائي بطول كلمة تشفير 31 و 10 رموز فحص ، وتصحيح جميع الأخطاء المزدوجة.

تحدد عمليات التحقق الخمسة الأولى مجموع أرقام الخطأ (S1) ؛ تحدد الشيكات الخمسة الثانية مجموع مكعبات رقم الخطأ (S3).

يتكون إجراء فك التشفير من ثلاث خطوات رئيسية:

يتم فحص كل كلمة مرور مستلمة ويتم حساب S1 و S3 ؛
ابحث عن كثير حدود محدد موقع الخطأ في σ (ض) ؛
يتم حساب القيم المتبادلة للجذور σ (ض) وتغيير الرموز في المواضع المقابلة للكلمة الناتجة.

تصحيح الأخطاء المتعددة عند ترميز الرسائل

أحكام نظرية

خصائص المقارنات الهامة

خوارزمية التقسيم

وظيفة البحث

More articles: