كيفية تصحيح رسالة باستخدام رمز Hamming

Question

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

شكرا.

Answer 1

انها كل شيء عن hamming المسافة.

مسافة Hamming بين قيمين أساسيين هي عدد البتات التي تختلف فيها. لذلك إذا قمت بنقل A، لكنني أتلقى B، فإن عدد البتات التي يجب أن تكون تحولت في ناقل الحركة هي مسافة Hamming بين A و B.

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

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

لذلك، يهدف رمز Hamming عادة إلى تصحيح أخطاء 1 بت و / أو اكتشاف أخطاء 2 بت (انظر مقالة ويكيبيديا لمزيد من التفاصيل عن النوعين الرئيسيين). يمكن إنشاء الرموز التي يصحح / كشف الأخطاء الأكبر، ولكن لا تستخدم AFAIK أكبر قدر ممكن.

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

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

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

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

Answer 2

على وجه التحديد من ويكيبيديا, ، الخوارزمية هي على النحو التالي:

1. عدد البتات بدءا من 1: بت 1، 2، 3، 4، 5، إلخ.
2. اكتب أعداد البت في ثنائي. 1، 10، 11، 100، 101، إلخ.
3. جميع المواقف الصغيرة التي هي صلاحيات اثنين (لها واحد فقط 1 بت في الشكل الثنائي من موقعها) هي بتات التكافؤ.
4. جميع مراكز البت الأخرى، مع اثنين أو أكثر من بت في الشكل الثنائي من موقعها، هي بتات البيانات.
5. يتم تضمين كل بت بيانات في مجموعة فريدة من 2 بت التعادل، كما يحددها الشكل الثنائي لموقف البت.
   1. تغطية Bit 1 1 يغطي مواقع BIT التي لديها مجموعة بت الأقل أهمية: بت 1 (تعادل بت التعادل نفسه)، 3، 5، 7، 9، إلخ.
   2. تاسيح BIT 2 يغطي مواقع BIT التي تحتوي على أقل مجموعة بت الأقل أهمية: بت 2 (تعادل بت التعادل نفسه)، 3، 6، 7، 10، 11، إلخ.
   3. تاسيح BIT 4 يغطي مواقع BIT التي لديها مجموعة من الأقل أهمية أقل أهمية: Bits 4-7، 12-15، 20-23، إلخ.
   4. تاسيح البت 8 يغطي جميع مواقع البت التي لديها مجموعة من الأقل أهمية في البت: البتات 8-15، 24-31، 40-47، إلخ.
   5. بشكل عام يغطي كل بت التكافؤ جميع البتات حيث يكون منصب الثنائي والمعادين وموقف البت غير صفر.

Answer 3

ال ويكيبيديا المادة يفسر ذلك تماما.

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