هامينج Code: اكتشاف الأخطاء وتصحيحها مع أمثلة

ما هو الخطأ؟

Transmitقد تتعرض البيانات المدخلة للتلف أثناء الاتصال، إذ من المرجح أن تتأثر بالتشويش الخارجي أو الأعطال المادية الأخرى. في مثل هذه الحالة، لا يمكن أن تتطابق البيانات المدخلة مع البيانات المخرجة، ويُعرف هذا التباين بـ "الخطأ".

قد تؤدي أخطاء البيانات إلى فقدان بيانات مهمة أو حساسة. يتم نقل معظم البيانات في الأنظمة الرقمية عبر نقل البتات، حتى أن تغييرًا طفيفًا في بت واحد قد يؤثر على أداء النظام بأكمله. في سلسلة البيانات، إذا تم تغيير الرقم 1 إلى 0، أو العكس، يُطلق على ذلك "خطأ في البت".

أنواع الأخطاء

هناك ثلاثة أنواع رئيسية من أخطاء البت التي تحدث عند نقل البيانات transmitيتم نقل البيانات من المرسل إلى المتلقي. يوضح الرسم البياني أدناه كيف يؤثر كل نوع على تسلسل البيانات:

• أخطاء بت واحدة
• أخطاء بت متعددة
• أخطاء الانفجار

أخطاء بت واحدة

يُعرف التغيير الذي يطرأ على بت واحد في سلسلة البيانات بأكملها باسم "خطأ البت الواحد". ونادرًا ما يحدث هذا الخطأ، إذ يقتصر حدوثه غالبًا على أنظمة الاتصالات المتوازية، لأن البيانات تُنقل بتًا بتًا على خطوط منفصلة، ​​مما يزيد من احتمالية تشويش أحد الخطوط بينما تبقى الخطوط الأخرى سليمة.

أخطاء بت متعددة

عندما يتغير اثنان أو أكثر من بتات سلسلة البيانات بين transmitيُعرف هذا الخطأ باسم "خطأ متعدد البتات" بالنسبة للطرف الآخر والمستقبل.

يحدث هذا النوع من الأخطاء في كل من شبكات نقل البيانات التسلسلية والمتوازية.

أخطاء الانفجار

يُعرف التغيير الذي يطرأ على مجموعة من البتات المتتالية في تسلسل البيانات باسم "خطأ الاندفاع". ويتم قياس طول خطأ الاندفاع من أول بت تم تغييره إلى آخر بت تم تغييره.

ما هو اكتشاف الأخطاء وتصحيحها؟

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

اكتشاف الخطأ هي طريقة لاكتشاف الأخطاء الموجودة في البيانات transmitتيد من أ transmitter إلى جهاز استقبال في البيانات نظام.

تُستخدم رموز التكرار لاكتشاف هذه الأخطاء عن طريق إضافة بتات إضافية إلى البيانات عندما تكون transmitيتم استخراج هذه البيانات الإضافية من المصدر. وتُسمى هذه الأجزاء الإضافية "رموز كشف الأخطاء". أما الأنواع الثلاثة الأكثر شيوعًا لرموز كشف الأخطاء فهي:

• فحص التكافؤ
• التحقق من التكرار الدوري (CRC)
• فحص التكرار الطولي (LRC)

فحص التكافؤ

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

فحص التكرار الطولي

في هذه التقنية لكشف الأخطاء، تُنظَّم مجموعة من البتات في جدول. تحسب طريقة LRC بت التكافؤ لكل عمود، وتُرسَل هذه المجموعة من بتات التكافؤ مع البيانات الأصلية. تساعد مجموعة بتات التكافؤ المُستقبِل على التحقق من التكرار واكتشاف الأخطاء.

فحص دوري التكرار

يقوم فحص التكرار الدوري بإلحاق سلسلة من البتات الزائدة بنهاية وحدة البيانات بحيث تصبح وحدة البيانات الناتجة قابلة للقسمة تمامًا على رقم ثنائي ثانٍ محدد مسبقًا.

عند الوصول إلى الوجهة، تُقسّم البيانات الواردة على نفس العدد. إذا لم يكن هناك باقٍ، يُفترض أن وحدة البيانات صحيحة ويتم قبولها. وإلا، فهذا يشير إلى أن وحدة البيانات قد تضررت أثناء الإرسال، ويجب رفضها.

ما هو هامينغ Code?

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

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

تاريخ هامينغ Code

• رمز هامينغ هو تقنية ابتكرها آر دبليو هامينغ لاكتشاف الأخطاء وتصحيحها.
• يمكن تطبيقه على وحدات البيانات من أي طول ويستخدم العلاقة بين بتات البيانات وبتات التكرار.
• عمل هامينغ على مشكلة تصحيح الأخطاء وطوّر مجموعة متزايدة القوة من الخوارزميات.
• في عام 1950، نشر رمز هامينغ، الذي لا يزال يستخدم على نطاق واسع حتى اليوم في تطبيقات مثل ذاكرة تصحيح الأخطاء (ECC).

تطبيقات هامينغ Code

فيما يلي بعض التطبيقات الشائعة لرمز هامينغ:

• الأقمار الصناعية
• ذاكرة الحاسوب (ECC RAM)
• أجهزة المودم
• بلازما كام
• فتح الموصلات
• سلك محمي
• المعالجات المدمجة

مزايا هامينغ Code

• يُعدّ رمز هامينغ فعالاً على الشبكات التي تتعرض فيها تدفقات البيانات لأخطاء بت واحد.
• فهو لا يكتشف خطأ البت فحسب، بل يساعدك أيضًا في تحديد البت الذي يحتوي على الخطأ حتى يمكن تصحيحه.
• إن سهولة استخدام رموز هامينغ تجعلها مناسبة تمامًا لذاكرة الكمبيوتر وتصحيح الأخطاء الفردية.

عيوب هامينغ Code

• هو رمز لكشف الأخطاء وتصحيحها على مستوى بت واحد. إذا تم اكتشاف وجود أخطاء في عدة بتات، فقد يؤدي ذلك إلى قلب بت آخر كان صحيحًا في الواقع، مما يزيد من تلف البيانات.
• لا تستطيع خوارزمية رمز هامينغ حل سوى المشكلات المتعلقة ببت واحد.

كيفية ترميز رسالة في هامينغ Code

تتضمن عملية تشفير الرسالة التي يستخدمها المرسل الخطوات الثلاث التالية:

• احسب العدد الإجمالي للبتات الزائدة.
• حدد موضع البتات الزائدة.
• احسب قيمة كل بت زائد.

عندما يتم تضمين البتات الزائدة داخل الرسالة، يتم إرسال كلمة الترميز الكاملة إلى جهاز الاستقبال.

الخطوة 1) احسب العدد الإجمالي للبتات الزائدة.

افترض أن الرسالة تحتوي على n بتات البيانات و p تمت إضافة أجزاء زائدة بحيث يصبح المجموع 2^p يمكن أن يشير إلى ما لا يقل عن (ن + ص + ١) حالة مختلفة.

هنا، يمثل (n + p) موقع الخطأ في كل موضع من مواضع البتات (n + p)، وتشير حالة إضافية واحدة إلى عدم وجود خطأ. لأن بتات التكافؤ p يمكن أن تشير إلى 2^p الدول، 2^p يجب أن يكون على الأقل مساوياً لـ (ن + ص + 1).

الخطوة 2) ضع الأجزاء الزائدة في مواضعها الصحيحة.

تُوضع البتات الزائدة (p) في مواقع البتات التي تمثل قوى العدد 2، على سبيل المثال، 1 و2 و4 و8 و16. ويُشار إليها بالرمز p.₁ (في الموضع ١)، ص₂ (في الموضع ١)، ص₃ (في الموضع 4)، وهكذا.

الخطوة 3) احسب قيمة كل بت زائد.

كل بت زائد هو بت تكافؤ يجعل عدد الآحاد في مجموعته إما زوجيًا أو فرديًا. نوعا التكافؤ هما:

• التكافؤ التام: يتم جعل العدد الإجمالي للرقم 1 في المواضع المغطاة زوجيًا.
• الزوجية الفردية: يتم جعل العدد الإجمالي للرقم 1 في المواضع المغطاة فرديًا.

يغطي كل بت من بتات التكافؤ مجموعة محددة من المواضع، يتم تحديدها من خلال التمثيل الثنائي لأرقام المواضع:

• p₁ يتحقق من كل موضع تحتوي قيمته الثنائية على 1 في البت الأقل أهمية - المواضع 1، 3، 5، 7، 9، 11، وهكذا.
• p₂ يتحقق من كل موضع يحتوي على قيمة ثنائية 1 في البت الثاني من اليمين - المواضع 2، 3، 6، 7، 10، 11، وهكذا.
• p₃ يتحقق من كل موضع يحتوي على قيمة ثنائية 1 في البت الثالث من اليمين - المواضع من 4 إلى 7، ومن 12 إلى 15، وهكذا.

مثال محلول (7،4): ضع في اعتبارك بتات البيانات الأربعة 1011يلزم وجود ثلاث بتات للتكافؤ (2³ = 8 ≥ 4 + 3 + 1)، مما يعطي كلمة رمزية مكونة من سبعة بتات مرتبة على النحو التالي p₁ p₂ d₁ p₃ d₂ d₃ d₄بوضع البيانات، تصبح المواضع 3، 5، 6، 7 هي 1، 0، 1، 1. باستخدام التكافؤ الزوجي: p₁ يغطي المواضع 1 و3 و5 و7 (البتات 1 و0 و1 → p₁ = 0)؛ ص₂ يغطي 2، 3، 6، 7 (البتات 1، 1، 1 → p₂ = 1)؛ ص₃ يغطي 4، 5، 6، 7 (البتات 0، 1، 1 → p₃ = 0). الـ transmitلذلك فإن كلمة مرور تيد هي 0110011.

كيفية فك تشفير رسالة بلغة هامينغ Code

يستقبل جهاز الاستقبال الرسالة الواردة ويُجري عمليات إعادة حسابية لاكتشاف الأخطاء وتصحيحها. وتتضمن عملية إعادة الحساب الخطوات التالية:

• احسب عدد البتات الزائدة.
• ضع جميع الأجزاء الزائدة في الموضع الصحيح.
• قم بإجراء فحص التكافؤ.

الخطوة 1) احسب عدد البتات الزائدة. استخدم نفس الصيغة المستخدمة في الترميز: 2^p ≥ n + p + 1، حيث n هو عدد بتات البيانات و p هو عدد البتات الزائدة.

الخطوة 2) ضع جميع الأجزاء الزائدة في الموضع الصحيح. كل بت زائد يقع في موضع بت يمثل قوة العدد 2 - على سبيل المثال، 1، 2، 4، و8.

الخطوة 3) قم بإجراء فحص التكافؤ. يتم إعادة حساب بتات التكافؤ من بتات البيانات والبتات الزائدة المستلمة:

• p₁ = parity(1, 3, 5, 7, 9, 11, …)
• p₂ = parity(2, 3, 6, 7, 10, 11, …)
• p₃ = parity(4–7, 12–15, 20–23, …)

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

الأسئلة الشائعة