مختبرات Bell، 1947
انضم Richard Hamming إلى مختبرات Bell Telephone في عام 1946. كانت أجهزة الكمبيوتر ذات المرحلات تعمل فقط في أيام الأسبوع، عندما يمكن للفنيين إعادة تشغيلها بعد الأخطاء. في نهايات الأسبوع، توقفت الآلات كلما حدث شيء خاطئ — مما ترك المهام في قائمة الانتظار حتى يوم الاثنين.
كان Hamming غاضباً. 'إذا كانت الآلة تستطيع كشف خطأ،' فكر، 'فلماذا لا تستطيع تحديد موقعه وتصحيحه؟' اجتمع هذا الإحباط مع معرفة عميقة بالحسابات الثنائية وفحوصات التكافؤ، وهيأ المرحلة.
الرؤية الأولى: الأكواد المستطيلة
كانت الفكرة الأولى لـ Hamming: ترتيب بتات الرسالة في مستطيل m×n، وإضافة فحص تكافؤ لكل صف وكل عمود. ينتج عن خطأ واحد بالضبط فشل فحص صف واحد وفشل فحص عمود واحد. يسمي تقاطعهما موقع الخطأ.
نسبة الزيادة: (m+1)(n+1) / mn. يخبرك حساب التفاضل والتكامل أن مربعاً يقلل هذا لحجم رسالة ثابت. لكن مع نمو m و n، يصبح الخطأ المزدوج أكثر احتمالاً — حكم هندسي ليس له إجابة عامة.
تقليل زيادة الكود المستطيل
يحمل مستطيل 4×4 بتات رسالة 16 مع 4 فحوصات صفية و 4 فحوصات عمودية، بالإضافة إلى 1 بت تكافؤ زاوي = 9 بتات فحص لـ 16 بت رسالة.
نسبة الزيادة: (m+1)(n+1) / mn = 25/16 ≈ 1.56.
لمستطيل 10×10: 100 بت رسالة، 121 بت إجمالي، زيادة ≈ 1.21.
المتلازمة كرقم ثنائي
بعد بضعة أسابيع من رؤية الكود المستطيل، كان Hamming يقود باتجاه نيويورك عبر أراضي نيو جيرسي، ويستعيد ذهنياً نجاحاته. حدثته فكرة الكود المثلث — زيادة أفضل. ثم المكعب. ثم 4 أبعاد، 5 أبعاد...
حسّن كل بُعد إضافي نسبة الزيادة. مكعب فائق بجانب 2 في n أبعاد يستخدم فقط n+1 فحوصات تكافؤ لـ 2^n رؤوس. لكن هل كان هذا الأمثل؟
حجة العد
تنتج n+1 بت تكافؤ متلازمة: رقم ثنائي بـ (n+1) بت. يجب أن تحدد تلك المتلازمة 2^n + 1 نتائج مميزة: كل من مواقع الأخطاء 2^n، بالإضافة إلى النتيجة الخاصة 'بدون خطأ'.
2^(n+1) = 2·2^n — قريب تقريباً. بعيد بمعامل 2. رفع Hamming المشكلة جانباً.
الرؤية المفتاحية
عاد Hamming لاحقاً بفكرة جديدة: استخدم المتلازمة نفسها كرقم ثنائي يسمي موقع الخطأ. الموقع 1 = ثنائي 001، الموقع 2 = ثنائي 010، الموقع 3 = ثنائي 011، إلخ. احجز جميع الأصفار لـ 'بدون خطأ'.
هذا يحول المتلازمة من مخرجات فحوصات التكافؤ إلى عنوان. تُصمّم فحوصات التكافؤ لإنتاج بالضبط العنوان الصحيح عندما ينقلب أي بت واحد.
تصميم كود (7,4)
لكود 7 بت (3 بتات تكافؤ، 4 بتات رسالة)، المواقع 1 حتى 7 بصيغة ثنائية هي: 001، 010، 011، 100، 101، 110، 111.
فحص التكافؤ 1 يغطي المواقع حيث البت 0 = 1: المواقع 1، 3، 5، 7.
فحص التكافؤ 2 يغطي المواقع حيث البت 1 = 1: المواقع 2، 3، 6، 7.
فحص التكافؤ 3 يغطي المواقع حيث البت 2 = 1: المواقع 4، 5، 6، 7.
بتات التكافؤ تحتل مواقع قوى العدد اثنين: 1، 2، 4. بتات الرسالة تحتل الباقي: 3، 5، 6، 7.
إذا انقلب البت 6، فشلت فحوصات التكافؤ 2 و 3 (110 بصيغة ثنائية = 6). تقرأ المتلازمة 110 = 6. انقلب الموقع 6. تم.
تصحيح الخطأ الواحد، كشف الخطأ المزدوج
كود (7,4) من Hamming يصحح الأخطاء الفردية. لكن ماذا لو انقلب بتان؟ بدون حماية إضافية، يطبق المفكك قاعدة المتلازمة و 'يصحح' الكلمة الرمزية إلى الرسالة الخاطئة — سوء تصحيح صامت.
SECDED: بت تكافؤ إضافي
أضف بت تكافؤ واحد p₀ يغطي الكلمة الرمزية بأكملها (جميع 7 بتات). الآن المتلازمة لها 4 إدخالات: الفحوصات الثلاث الأصلية بالإضافة إلى p₀.
``
المتلازمة القديمة p₀ الجديد المعنى
000 0 صحيح
000 1 خطأ في p₀ فقط
xxx 1 خطأ واحد، تسمية المتلازمة القديمة
xxx 0 خطأ مزدوج — علمه
``
الحالات الأربع شاملة. خطأ مزدوج ينقلب بتين: المتلازمة القديمة لن تقرأ 000 (كلا البتين معاً يفسدان اثنين من فحوصاتها)، لكن p₀ ينقلب مرتين ويعود إلى 0. النمط xxx + 0 لا يخطئ.
لماذا يعمل SECDED
تستغل قاعدة SECDED البنية المعيارية للتكافؤ. مع التكافؤ الزوجي، أي انقلاب واحد يغير p₀. أي انقلاب مزدوج يترك p₀ دون تغيير. لذلك p₀ يحسب الأخطاء معامل 2.
الصورة الهندسية
وصل Hamming إلى نفس المكان من اتجاه مختلف: الهندسة التحليلية. مثّل كل سلسلة n-بت كرأس من مكعب فائق n-الأبعاد. انقلاب بت واحد يحرك نقطة واحدة بطول الحافة على طول محور واحد. انقلابان: حافتان. المقياس هو مسافة Hamming.
حدّد كرة Hamming بنصف قطر t حول كلمة رمزية c: جميع النقاط ضمن t انقلابات بت من c. لتصحيح الخطأ الواحد، t = 1.
الشرط لتصحيح الخطأ الواحد: كرات نصف قطرها 1 حول كل زوج من الكلمات الرمزية المميزة يجب ألا تتقاطع. إذا تقاطعت، قد تنتمي كلمة مستقبلة في التقاطع إلى كلمة رمزية أو أخرى والمفكك يفشل.
هذا يترجم مباشرة إلى أدنى مسافة: كرتا نصف قطرهما 1 لا تتقاطع إذا وفقط إذا كانت الكلمات الرمزية متباعدة بمسافة 3 على الأقل (d_min ≥ 3).
يحقق كود (7,4) d_min = 3. حد Hamming: 2^7 / (1 + 7) = 16 = 2^4. بالضبط 16 كلمة رمزية. كود مثالي: الكرات 16 بنصف قطر 1 ترصف {0,1}^7 بدون فجوات أو تقاطعات.
الأحكام الهندسية
كان Hamming صريحاً: تتضمن أكواد تصحيح الأخطاء أحكاماً هندسية، وليس رياضيات بحتة.
طول الرسالة: الرسائل الأطول تسمح بترميز أكثر كفاءة (بتات تكافؤ log n لـ n بت رسالة). لكن الرسائل الأطول تتراكم أيضاً ضوضاء أكثر، مما يرفع خطر انزلاق خطأ مزدوج عبر تصحيح خاطئ واحد.
مستوى التصحيح مقابل الكشف: المقايضة بتصحيح خطأ واحد مقابل كشفين خطأ إضافيين. يعتمد الانقسام الأمثل على خصائص ضوضاء القناة.
قيمة الصيانة في الميدان: مع نمو المعدات أكثر تعقيداً، لا يمكن لفنيي الميدان تشخيص كل فشل من المبادئ الأولى. يقلل نظام التشخيص الذاتي بشكل كبير المهارة المطلوبة للصيانة. دعا Hamming هذا واحداً من الفوائد الأكثر أهمية، غالباً أكثر أهمية من كسب الموثوقية الخام.
الأسلوب: الحظ يحب العقل المستعد
أغلق Hamming الفصل 12 بتحدٍ مباشر. وصف الاكتشاف بأنه يتطلب ثلاثة إلى ستة أشهر من العمل، بشكل أساسي في اللحظات الغريبة أثناء القيام بواجباته الرئيسية في مختبرات Bell.
حدّد ثلاثة أشياء جعلته ممكناً:
1. التحضير: معرفة عميقة بفحوصات التكافؤ و الحسابات الثنائية و نظرية المجموعات، قبل ظهور المشكلة.
2. استعراض النجاحات: عادة إعادة تشغيل الحلول السابقة عقلياً لاستيعاب أسلوبها. حدثت فكرة الكود المثلثي له أثناء استعراض الكود المستطيل عقلياً في تنقل.
3. عدم الاكتفاء بـ 'يبدو جيداً': حرق أصابعه مرة واحدة بقبول الأمثلية الواضحة. دفع حتى يتمكن من إثبات أن الكود كان أفضل.