شرح شيفرات تصحيح الأخطاء
لا توجد قناة مثالية. فالأشعة الكونية تقلب بتات في الذاكرة، والخدوش تمحو أجزاء من القرص، والإشارات اللاسلكية تخفت. وبدلًا من التعويل على الحظ، تضيف الأنظمة الرقمية تكرارًا بطريقة ذكية، كي يتمكن المستقبِل من استنتاج ما أُرسل حتى لو وصل بعضه خاطئًا. والرياضيات التي تقوم عليها هذه الشيفرات، والتي بدأت في أواخر الأربعينيات، تحمي في صمت كل بت تقريبًا نخزّنه أو نرسله.
اكتشاف الأخطاء بالتكافؤ
أبسط أشكال الحماية بت تكافؤ واحد: أضف 1 أو 0 بحيث يكون العدد الكلي للآحاد زوجيًا. فإذا انقلب بت واحد في الطريق، صار العدد فرديًا وعرف المستقبِل أن شيئًا ما قد حدث. لا يستطيع التكافؤ أن يحدد أي بت هو الخاطئ، وقلبتان تلغي إحداهما الأخرى دون أن يُلاحَظ ذلك، لكنه رخيص، وقد استُخدم عقودًا في الذاكرة والوصلات التسلسلية. غير أن اكتشاف الخطأ ليس إلا نصف المهمة: إذ يجب بعده إرسال البيانات من جديد.
التصحيح بالتكرار
لتصحيح خطأ دون طلب الإرسال مجددًا، يحتاج المستقبِل إلى تكرار يكفي لأن يتغلب على الخطأ بالأغلبية. فإرسال كل بت ثلاث مرات، 000 أو 111، يتيح للمستقبِل أن يأخذ بالأغلبية: فتُصحَّح قلبة واحدة في الثلاثية. لكن الثمن باهظ: ثلاثة بتات لكل بت بيانات، وقلبتان في الثلاثية نفسها تنتصران مع ذلك. وكان السؤال الذي أطلق نظرية الترميز: هل يمكن فعل ما هو أفضل؟
شيفرة هامنغ
في عام 1947 كان ريتشارد هامنغ يعمل في مختبرات بل على حاسوب مرحّلات يقرأ البرامج من بطاقات مثقّبة. وحين كان يجد خطأً في عطلة نهاية الأسبوع كان يتوقف ببساطة، فيعود هامنغ يوم الاثنين ليجد تشغيلات ضائعة. فتساءل: إذا كانت الآلة قادرة على اكتشاف الخطأ، فلماذا لا تستطيع تحديد موضعه وتصحيحه؟ وكان جوابه، الذي نُشر عام 1950، أن تُرسل 4 بتات بيانات على هيئة 7. ثلاثة بتات تكافؤ، في المواضع 1 و2 و4، يفحص كل منها مجموعة مختلفة متداخلة من المواضع، اختيرت بحيث يكسر كل خطأ منفرد تركيبة فريدة من الفحوص.
المتلازمة
يعيد المستقبِل حساب الفحوص الثلاثة. فإذا نجحت كلها قُبلت الكلمة. وإذا فشل بعضها، فإن كتابة الفحوص الفاشلة أرقامًا ثنائية، مع جعل الفحص 4 الخانة العليا، تعطي عددًا من 1 إلى 7: هو المتلازمة، وهي بالضبط موضع البت المقلوب. وإعادة قلبه تستعيد كلمة الشيفرة. وتنجح هذه الحيلة لأن المواضع مرقّمة بحيث يسرد التمثيل الثنائي لكل منها الفحوص التي ينتمي إليها، ولهذا تبدو الشيفرة مرتبة إلى هذا الحد حين تُرسم ثلاث دوائر متداخلة.
مسافة هامنغ
مسافة هامنغ بين كلمتين هي عدد المواضع التي تختلفان فيها. وفي شيفرة (7,4) تبعد كل كلمتي شيفرة إحداهما عن الأخرى 3 على الأقل. فالكلمة التي فيها خطأ واحد تبقى على مسافة 1 من كلمة الشيفرة المرسلة وعلى مسافة 2 على الأقل من كل كلمة أخرى، لذا فإن فك ترميزها إلى أقرب كلمة شيفرة يصححها. وعمومًا، الشيفرة التي تبعد كلماتها بعضها عن بعض d على الأقل تكتشف d − 1 من الأخطاء وتصحح (d − 1)/2 منها، مقرّبًا إلى الأدنى. وإضافة بت تكافؤ كلي ترفع المسافة إلى 4، فتنتج الشيفرة الموسّعة التي تصحح خطأً واحدًا وتكتشف خطأين.
حد شانون
في عام 1948، قبل ورقة هامنغ بعامين، أثبت كلود شانون مبرهنة مذهلة. لكل قناة مشوشة سعة، ويمكن إرسال البيانات بأي معدل دونها مع أخطاء قليلة بالقدر الذي تريده، باستخدام شيفرات طويلة بما يكفي؛ أما فوقها فلا يمكن تجنب الأخطاء. أثبت شانون أن مثل هذه الشيفرات موجودة لكنه لم يبيّن كيف تُبنى. واستغرق العثور على شيفرات عملية تقترب من حده نصف قرن، من شيفرات ريد-سولومون عام 1960 إلى شيفرات توربو عام 1993 وإعادة اكتشاف شيفرات فحص التكافؤ منخفضة الكثافة.
شيفرات من حولنا
تتيح شيفرات ريد-سولومون للأقراص المدمجة أن تعمل رغم الخدوش، ولرموز QR أن تُمسح حتى مع تلف ما يصل إلى 30% من الرمز. وتستخدم ذاكرة الخوادم شيفرات هامنغ الموسّعة لإصلاح البتات المنفردة التي تقلبها الأشعة الكونية. وقد حُميت صور فوياجر للكواكب الخارجية بشيفرات غولاي ثم بشيفرات ريد-سولومون، وتعتصر شيفرات LDPC والشيفرات القطبية في 5G وWi-Fi كل بت تقريبًا تسمح به القناة. بل إن الرمز الشريطي على الكتاب والرقم الأخير من رقم الحساب المصرفي شيفرتان بسيطتان لاكتشاف الأخطاء.
استكشفها بنفسك
افتح محاكي شيفرات تصحيح الأخطاء لترمّز أي أربعة بتات بيانات بشيفرة هامنغ (7,4)، واقلب البتات بالنقر عليها في الدوائر أو في الصف، وراقب الدوائر الفاشلة والمتلازمة تشير إلى الخطأ قبل أن يصلحه المفكّك. فعّل بت التكافؤ الإضافي لترى الأخطاء المزدوجة تُكتشف، وأرسل رسالة عبر قناة مشوشة لتقارن ما يصل مع الشيفرة ومن دونها.
الأسئلة المتداولة
ما الفرق بين اكتشاف الأخطاء وتصحيحها؟
الاكتشاف يخبر المستقبِل فقط بأن شيئًا ما خاطئ، فيجب عليه أن يطلب البيانات مجددًا؛ وهذا ما يفعله بت التكافؤ أو المجموع الاختباري. أما التصحيح فيتيح للمستقبِل أن يعيد بناء الأصل دون أن يطلب، وهذا يحتاج إلى تكرار أكبر. والأنظمة التي لا تستطيع الطلب مجددًا، مثل مسبار فضائي على بعد ملايين الكيلومترات أو قرص DVD، تعتمد على التصحيح.
لماذا لا نرسل كل شيء مرتين فحسب؟
تُظهر نسختان أن خطأً قد وقع لكنهما لا تُظهران أي النسختين هي الصحيحة، وتضاعفان التكلفة. وتتيح ثلاث نسخ التصويت بالأغلبية لكنها تضاعف التكلفة ثلاث مرات. أما شيفرة هامنغ فتصحح خطأً منفردًا في كل كتلة من سبعة بتات بأقل من ضعف عدد البتات، والشيفرات الأطول تحقق ما هو أفضل بكثير.
من كان ريتشارد هامنغ؟
عالم رياضيات أمريكي (1915–1998)، عمل في مشروع مانهاتن ثم ثلاثين عامًا في مختبرات بل. وإلى جانب شيفراته، يُعرف بنافذة هامنغ في معالجة الإشارات، وبمسافة هامنغ، وبمحاضرته «You and Your Research» (أنت وبحثك). ونال جائزة تورنغ عام 1968.
هل تستطيع شيفرة أن تصحح أي عدد من الأخطاء؟
فقط إذا توفر تكرار كافٍ. تستطيع الشيفرة أن تصحح حتى (d − 1)/2 من الأخطاء في كل كتلة، حيث d هي المسافة الدنيا بين كلمات الشيفرة، والشيفرات الأطول ذات بتات الفحص الأكثر تبلغ قيمًا أكبر لـ d. وتضع مبرهنة شانون الحد النهائي: لا يمكن لأي شيفرة أن تتجاوز سعة القناة.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
افتح محاكي شيفرات تصحيح الأخطاء