مصفوفة التحقق من التكافؤ

في نظرية الترميز ، تُعرَّف مصفوفة التحقق من التكافؤ لرمز الكتلة الخطي C بأنها مصفوفة تصف العلاقات الخطية التي يجب أن تحققها مكونات كلمة الترميز. ويمكن استخدامها لتحديد ما إذا كان متجه معين يمثل كلمة ترميز، كما تُستخدم أيضًا في خوارزميات فك الترميز.

بصورة رسمية، فإن مصفوفة التحقق من التكافؤ H لرمز خطي C هي مصفوفة مولدة للرمز الثنائي C⊥ ^. وهذا يعني أن كلمة الرمز c تنتمي إلى C إذا وفقط إذا كان حاصل ضرب المصفوفة في المتجه ^H c⊤ = 0 ( يكتب بعض المؤلفين ^{[ 1 ]} هذا بصيغة مكافئة، c H⊤ = ⁰ ) .

تمثل صفوف مصفوفة فحص التكافؤ معاملات معادلات فحص التكافؤ. ^{[ 2 ]} أي أنها توضح كيف أن التراكيب الخطية لأرقام (مكونات) معينة من كل كلمة رمزية تساوي صفرًا. على سبيل المثال، مصفوفة فحص التكافؤ

${\displaystyle H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]}$،

يمثل بشكل مختصر معادلات التحقق من التكافؤ،

${\displaystyle {\begin{aligned}c_{3}+c_{4}&=0\\c_{1}+c_{2}&=0\end{aligned}}}$،

يجب أن يتحقق ذلك بالنسبة للمتجه${\displaystyle (c_{1},c_{2},c_{3},c_{4})}$أن تكون كلمة سر لـ C.

من تعريف مصفوفة فحص التكافؤ، يتبع مباشرة أن الحد الأدنى للمسافة في الكود هو الحد الأدنى للعدد d بحيث تكون كل d - 1 عمودًا من مصفوفة فحص التكافؤ H مستقلة خطيًا، بينما توجد d أعمدة من H مرتبطة خطيًا.

يمكن اشتقاق مصفوفة فحص التكافؤ لرمز معين من مصفوفة مولداته (والعكس صحيح). ^{[ 3 ]} إذا كانت مصفوفة مولدات رمز [ n , k ] في الشكل القياسي

${\displaystyle G={\begin{bmatrix}I_{k}|P\end{bmatrix}}}$،

ثم تُعطى مصفوفة فحص التكافؤ بواسطة

${\displaystyle H={\begin{bmatrix}-P^{\top }|I_{nk}\end{bmatrix}}}$،

لأن

${\displaystyle GH^{\top }=PP=0}$.

يتم إجراء النفي في الحقل المنتهي F _q . لاحظ أنه إذا كانت خاصية الحقل الأساسي تساوي 2 (أي أن 1 + 1 = 0 في ذلك الحقل)، كما هو الحال في الشفرات الثنائية ، فإن -P = P ، وبالتالي فإن النفي غير ضروري.

على سبيل المثال، إذا كان للرمز الثنائي مصفوفة المولد

${\displaystyle G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]}$،

ثم تكون مصفوفة التحقق من التكافؤ الخاصة بها هي

${\displaystyle H=\left[{\begin{array}{cc|ccc}-1&-1&1&0&0\\0&-1&0&1&0\\-1&0&0&0&1\\\end{array}}\right]}$.

يمكن التحقق من أن G هو${\displaystyle k\times n}$مصفوفة، بينما H عبارة عن${\displaystyle (nk)\times n}$مصفوفة.

لأي متجه x في فضاء المتجهات المحيط، يُطلق على s = H x اسم متلازمة x . يكون المتجه x كلمة رمزية إذا وفقط إذا كان s = 0. يُعد حساب المتلازمات أساس خوارزمية فك تشفير المتلازمات . ^{[ 4 ]}

• شفرة هامينغ

• هيل، ريموند (1986). مدخل إلى نظرية الترميز . سلسلة أكسفورد للرياضيات التطبيقية وعلوم الحاسوب. مطبعة جامعة أكسفورد . 69 صفحة . ISBN  0-19-853803-0.
• بليس، فيرا (1998)، مقدمة في نظرية رموز تصحيح الأخطاء (  الطبعة الثالثة)، وايلي إنترساينس، رقم ISBN 0-471-19047-0
• رومان، ستيفن (1992)، الترميز ونظرية المعلومات ، GTM ، المجلد  134، سبرينغر-فيرلاغ، ISBN 0-387-97812-7
• جيه إتش فان لينت (1992). مقدمة في نظرية الترميز . جي تي إم . المجلد  86 (  الطبعة الثانية). سبرينغر-فيرلاغ. ص 34. ISBN  3-540-54894-7.