كيف يعمل رمز Hamming؟

Question

عند إرسال البيانات، يتيح لك رمز Hamming Code إعادة إنشاء البيانات التي تم تالف عبر الأسلاك (رمز تصحيح الأخطاء).

كيف هذا العمل وما هي قيودها، إن وجدت؟

هل هناك أي حلول أفضل لتصحيح الخطأ (على عكس إعادة الإرسال)؟ هل هناك ظروف حيث إعادة الإرسال أفضل؟

Answer 1

دعونا نحاول شرح ذلك قليلا:

لدينا رقم 3 بت. يمكن تقديم الاحتمالات ككعب حيث يمثل كل بت محورا. الاحتمالات الثمانية موجودة على الزوايا.

000 --------001
 | \         | \
 | 100---------101
 |  |        |  |
 |  |        |  |
010-|-------011 |
   \|          \|
   110---------111

ينتج عن كل عيب (على سبيل المثال 101 دولارا) نوبة تحول على خط على المكعب.

إذا نستخدم قطعتين للبيانات والثالث لشيك التكافؤ (على سبيل المثال حتى التكافؤ). نحن نفقد 4 Datapooints. ولكن لديها ميزة يمكننا اكتشاف فشل بت واحد (والذي يحول حتى عدد حتى 1 في عدد غريب من تلك). يتم تمييز الأرقام الفردية مع *. ونحن نرى أن كل كلمة فردية (نقل خطأ غير خاطئ) محطومة حتى الكلمات (المنقولة بحق). لذلك إذا تلقينا 100، يمكننا أن نكون متأكدين من الخطأ.

ولكن (مع فشل بت واحد) يمكن أن يكون التمثيل الصحيح 000 أو 101 أو 110. حتى نتمكن من اكتشاف شيء ما كان خطأ ولكن لا يمكننا اكتشاف ما كان خطأ:

 000 -------*001
  | \         | \
  |*100---------101
  |  |        |  |
  |  |        |  |
*010-|-------011 |
    \|          \|
    110--------*111

وهذا ما يسمى خطأ بت الكائنات الكشف عن خطأ.

إذا كنا نستخدم بت آخر للتحقق وبالتالي إزالة واحدة للبيانات. لقد تركنا مع 1 قاعدة بيانات و 2 "فحص البتات". في هذه الحالة، يتيح لك افتراض 000 و 111 من تمثيلات بيانات صالحة والستة الأخرى ليست كذلك. الآن لدينا موقف مثير للاهتمام إذا نشأ قليلا أثناء النقل. إذا أرسلنا 000 وتلقي 010، فنحن نرى أن 010 لديه جار واحد صالح (000) واثنين منهم غير صالحين (110 و 011). الآن نحن نعلم أننا ننوي إرسال 000 ويمكننا تصحيح ذلك:

 000 -------*001
  | \         | \
  |*100--------*101
  |  |        |  |
  |  |        |  |
*010-|------*011 |
    \|          \|
   *110---------111

يسمى هذا رمز تصحيح خطأ واحد.

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

ووضعها بشكل عام.

إذا كان لديك N تحقق من البتات، فلديك رمز الكشف عن خطأ. إذا كان لديك 2n Check Bits، فلديك رمز تصحيح خطأ بعض الشيء.

بالطبع يجب عليك طلب رموز "صالحة" بحيث لا تحددها على بعضها البعض.

Answer 2

إليك نظرة عامة رفيعة المستوى.

Suppose that every time I send a message, I send thrie copies of the text.
Suppose that every time I send z message, I send three copies of the teyt.
Suppose that every tyme I send a message, I send three copies if the tezt.

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

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

من أجل التوضيح، دعنا نبدأ مع تكافؤ غريبة بسيطة، مضيفا قليلا للتأكد من أن العدد الإجمالي للأجزاء في رسالة غريبة. إذن الرسالة 10110110 يصبح 101101100 (خمسة 1 ثانية، لا حاجة إضافية واحدة) والرسالة 10010110 يصبح 100101101 (أربعة 1S، مطلوب 1 إضافية). إذا تلقيت رسالة 101101101 ونرى أن هناك ستة 1 ثانية، أنت تعرف أن هناك خطأ، لكن لا تعرف أين. لنفترض أننا نضيف المزيد من بتات التكافؤ، كل منها اعتمادا فقط على جزء من الرسالة، كما هو موضح أدناه من خلال نسخ البتات التي تم النظر فيها واستخدامها "-" في البتات:

10110110
1-1-0-1- => 0
-0-1-1-0 =>  1
10--01-- =>   1
--11--10 =>    0
1011---- =>     0
----0110 =>      1

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

10010110
1-0-0-1- => 1*
-0-1-1-0 =>  1
10--01-- =>   1
--01--10 =>    1*
1001---- =>     1*
----0110 =>      1

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

Answer 3

ستجد تفاصيل حول الطريقة التي يعمل بها هنا

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

Answer 4

المعلومات حول رمز Hamming متاح هنا و هنا.

أما بالنسبة للمحاسبة، هذه يفسر لماذا:

1. رموز تصحيح الأخطاء مثل Hamming مناسبة لقنوات البسيط حيث لا يمكن طلب عدم إعادة الإرسال.

2. غالبا ما يتم تفضيل اكتشاف الكشف عن الأخطاء، لأنه أكثر كفاءة.

للمقارنة، النظر في قناة مع معدل الخطأ في كل بت. دع كتلة الحجم يكون 1000 بت.

لتصحيح خطأ واحد (عن طريق الرمز Hamming)، هناك حاجة إلى 10 فحص فحص لكل كتلة. لنقل 1000 كتل، 10،000 بت فحص (النفقات العامة) مطلوبة. للكشف عن خطأ واحد، سيكفي بت التعادل الواحد لكل كتلة. لنقل 1000 قطعة، سيتعين إعادة تحويل كتلة Exter واحدة فقط (نظرا لمعدل الخطأ في كل بت)، مما يعطي النفقات العامة لعام 2001 فقط (= 1000 + 1001).

Answer 5

رمز Hamming هو خدعة رياضية لتصحيح ما يصل إلى 4 بت فقدت في انتقال تسلسلي. كما أنه يستخدم لصالح "تعادل بت" في رقائق الذاكرة الحديثة.

القيود في عدد البتات التي يمكن استعادتها، والتي ليست أكثر من 4. إذا فقدت أكثر من 4 بت، يلزم إعادة الإرسال.

تتطلب المواقف المختلفة تقنيات تصحيح الأخطاء المختلفة. يتم سرد بعض هذه التقنيات في الوظائف الأخرى هنا.

Answer 6

gamecat وماذا عن خطأ 2 بت الكشف عن رمز.

في هذه الحالة، دعا نقول 111 قد تغير إلى 100. ثم يمكننا أن نكون متأكدين من وجود 2 بت خاطئ ونحن نعرف ذلك لأن المسافة بين 111 و 100 عبارة عن 2 بت، ومسافة 000 و 100 هي 1 بت. لذلك إذا كنا نعلم أن هناك خطأ 2 بت، فيمكننا بالتأكيد ما هي القيمة الصحيحة.