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

ما هو الخطأ؟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ثلاثة أنواع من رموز اكتشاف الأخطاء هي:

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

فحص التكافؤ

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

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

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

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

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

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

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

تاريخ كود هامينج

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

تطبيق كود هامينج

فيما يلي بعض التطبيقات الشائعة لاستخدام كود هامينج:

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

مميزات كود هامينج

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

عيوب كود هامينج

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

كيفية ترميز رسالة في كود هامينج

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

• حساب العدد الإجمالي للبتات الزائدة.
• التحقق من موقف البتات الزائدة عن الحاجة.
• وأخيرًا، حساب قيم هذه البتات الزائدة عن الحاجة.

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

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

لنفترض أن الرسالة تحتوي على:

• n- عدد بتات البيانات
• p - عدد البتات الزائدة التي تضاف إليها بحيث يمكن أن يشير np إلى حالات مختلفة على الأقل (n + p + 1).

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

الخطوة 2) وضع البتات الزائدة في مكانها الصحيح.

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

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

يجب أن تكون البتات الزائدة عبارة عن بتات متماثلة مما يجعل عدد 1s إما زوجيًا أو فرديًا.

نوعان من التكافؤ هما؟

• يُطلق على العدد الإجمالي للبتات في الرسالة، والذي يتم حسابه على أساس زوجي، اسم التكافؤ الزوجي.
• إجمالي عدد البتات في الرسالة التي يتم جعلها غريبة يسمى التكافؤ الفردي.

هنا، يجب حساب كل البتات الزائدة، p1، على أنها تكافؤ. وينبغي أن يغطي جميع مواضع البت التي يجب أن يتضمن تمثيلها الثنائي الرقم 1 في الموضع الأول باستثناء موضع p1.

P1 هو بت التكافؤ لكل بتات البيانات في المواضع التي يتضمن تمثيلها الثنائي 1 في الموضع الأقل أهمية ولا يتضمن 1 مثل (3، 5، 7، 9، ….)

P2 هو بت التكافؤ لكل بتات البيانات في المواضع التي يتضمن تمثيلها الثنائي 1 في الموضع 2 من اليمين، ولا يشمل 2 مثل (3، 6، 7، 10، 11، ...)

P3 هو بت التكافؤ لكل بت في المواضع التي يتضمن تمثيلها الثنائي 1 في الموضع 3 من اليمين ولا يتضمن 4 مثل (5-7، 12-15،...)

فك تشفير رسالة في كود هامينج

يتلقى المتلقي الرسائل الواردة التي تتطلب إجراء عمليات إعادة الحساب للعثور على الأخطاء وتصحيحها.

تتم عملية إعادة الحساب بالخطوات التالية:

• حساب عدد البتات الزائدة عن الحاجة.
• تحديد المواقع بشكل صحيح لجميع البتات الزائدة عن الحاجة.
• فحص التكافؤ

الخطوة 1) حساب عدد البتات الزائدة عن الحاجة

يمكنك استخدام نفس الصيغة للتشفير، وعدد البتات الزائدة عن الحاجة

2^p ؟ ن + ع + 1

هنا، عدد بتات البيانات وp هو عدد البتات الزائدة عن الحاجة.

الخطوة 2) وضع كافة البتات الزائدة بشكل صحيح

هنا، p عبارة عن بتة زائدة عن الحاجة تقع في مواضع بت ذات قوى 2، على سبيل المثال، 1، 2، 4، 8، إلخ.

الخطوة 3) فحص التكافؤ

تحتاج بتات التكافؤ إلى الحساب بناءً على بتات البيانات والبتات الزائدة عن الحاجة.

p1 = التكافؤ (1، 3، 5، 7، 9، 11…)

p2 = التكافؤ (2، 3، 6، 7، 10، 11…)

p3 = التكافؤ (4-7، 12-15، 20-23...)

الملخص

• يمكن أن تتلف البيانات المرسلة أثناء الاتصال
• ثلاثة أنواع من أخطاء البت هي 1) أخطاء البت المفردة 2) أخطاء البت المتعددة 3) أخطاء البت المتتابعة
• يُعرف التغيير الذي تم إجراؤه في بت واحد في تسلسل البيانات بأكمله باسم "خطأ بت واحد".
• في تسلسل البيانات، إذا كان هناك تغيير في بتتين أو أكثر من تسلسل البيانات من المرسل إلى المستقبل، يُعرف ذلك باسم "أخطاء البتات المتعددة".
• يُعرف تغيير مجموعة البتات في تسلسل البيانات باسم "خطأ الاندفاع".
• اكتشاف الأخطاء هو وسيلة لاكتشاف الأخطاء الموجودة في البيانات المرسلة من جهاز الإرسال إلى جهاز الاستقبال في نظام اتصالات البيانات
• ثلاثة أنواع من رموز اكتشاف الأخطاء هي 1) فحص التكافؤ 2) فحص التكرار الدوري (CRC) 3) فحص التكرار الطولي (LRC)
• رمز Hamming هو رمز خطي مفيد لاكتشاف الأخطاء حتى خطأين فوريين في البت. إنه قادر على ارتكاب أخطاء بت واحد.
• كود Hamming عبارة عن تقنية تم إنشاؤها بواسطة RWHamming لاكتشاف الأخطاء.
• التطبيقات الشائعة لاستخدام كود Hamming هي ذاكرة الكمبيوتر عبر الأقمار الصناعية، وأجهزة المودم، والمعالج المضمن، وما إلى ذلك.
• إن أكبر فائدة لطريقة كود الاختراق تكون فعالة على الشبكات حيث يتم توفير تدفقات البيانات لأخطاء البت المفردة.
• أكبر عيب في طريقة كود هامينغ هو أنها يمكن أن تحل مشاكل البتات الفردية فقط.
• يمكننا إجراء عملية تشفير وفك تشفير الرسالة بمساعدة كود هامينغ.