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

طلب إعادة الإرسال التلقائي (ARQ) هو أسلوب للتحكم في الأخطاء أثناء نقل البيانات، يستخدم رموز كشف الأخطاء، ورسائل التأكيد و/أو رسائل التأكيد السلبي، وفترات المهلة الزمنية لضمان نقل البيانات بشكل موثوق. التأكيد هو رسالة يرسلها المُستقبِل للإشارة إلى استلامه إطار البيانات بشكل صحيح .

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

ثلاثة أنواع من بروتوكولات ARQ هي: بروتوكول ARQ للتوقف والانتظار ، وبروتوكول ARQ للرجوع إلى N ، وبروتوكول ARQ للتكرار الانتقائي .

يُعدّ بروتوكول ARQ مناسبًا إذا كانت سعة قناة الاتصال متغيرة أو غير معروفة ، كما هو الحال في الإنترنت. مع ذلك، يتطلب ARQ توفر قناة خلفية ، وقد يؤدي إلى زيادة زمن الاستجابة نتيجةً لإعادة الإرسال، كما يتطلب صيانة مخازن مؤقتة ومؤقتات لإعادة الإرسال، الأمر الذي قد يُرهق الخادم وسعة الشبكة الإجمالية في حالة ازدحام الشبكة . ^{[ 10 ]}

على سبيل المثال، يتم استخدام ARQ على وصلات بيانات الراديو ذات الموجات القصيرة في شكل ARQ-E ، أو يتم دمجه مع تعدد الإرسال كـ ARQ-M .

تصحيح الأخطاء الأمامي (FEC) هو عملية إضافة بيانات زائدة، مثل رمز تصحيح الأخطاء (ECC)، إلى الرسالة بحيث يمكن للمستقبل استعادتها حتى عند حدوث عدد من الأخطاء (بحسب قدرة الرمز المستخدم)، سواء أثناء الإرسال أو التخزين. ولأن المستقبل لا يحتاج إلى طلب إعادة إرسال البيانات من المرسل، فلا حاجة إلى قناة خلفية في تصحيح الأخطاء الأمامي. تُستخدم رموز تصحيح الأخطاء في الاتصالات منخفضة الطبقة ، مثل شبكات الهاتف المحمول ، والاتصالات عالية السرعة عبر الألياف الضوئية ، وشبكات الواي فاي ^{[ 11 ] [ 12 ]} ، وكذلك للتخزين الموثوق في وسائط مثل ذاكرة الفلاش ، والقرص الصلب ، وذاكرة الوصول العشوائي (RAM) ^{[ 13 ]} .

عادةً ما يتم التمييز بين رموز تصحيح الأخطاء ورموز الالتفاف ورموز الكتل :

• تُعالج رموز الالتفاف على أساس بت-بت. وهي مناسبة بشكل خاص للتنفيذ في الأجهزة، ويسمح مُفكِّك فيتربي بفك التشفير الأمثل .
• تُعالج رموز الكتل على أساس كل كتلة على حدة . من الأمثلة المبكرة على رموز الكتل رموز التكرار ، ورموز هامينغ ، ورموز التحقق من التكافؤ متعددة الأبعاد . وقد تبعتها مجموعة من الرموز الفعالة، أبرزها رموز ريد-سولومون نظرًا لانتشار استخدامها الواسع حاليًا. أما رموز التوربو ورموز التحقق من التكافؤ منخفضة الكثافة (LDPC) فهي تركيبات حديثة نسبيًا تُوفر كفاءة شبه مثالية .

تُعدّ نظرية شانون نظريةً مهمةً في تصحيح الأخطاء الأمامية، وتصف الحد الأقصى لمعدل المعلومات الذي يُمكن عنده تحقيق اتصال موثوق عبر قناة ذات احتمال خطأ مُحدد أو نسبة إشارة إلى ضوضاء مُعينة. يُعبّر عن هذا الحد الأعلى الصارم بدلالة سعة القناة . وبشكلٍ أكثر تحديدًا، تنص النظرية على وجود رموز بحيث يُمكن، مع زيادة طول التشفير ، تقليل احتمال الخطأ على قناة منفصلة عديمة الذاكرة إلى أدنى حد ممكن، شريطة أن يكون معدل الترميز أقل من سعة القناة. يُعرّف معدل الترميز بأنه النسبة k/n بين k رمز مصدر و n رمز مُشفّر.

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

يُعدّ نظام ARQ الهجين مزيجًا من نظام ARQ وتصحيح الأخطاء الأمامية. وهناك منهجان أساسيان: ^{[ 10 ]}

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

يُعد النهج الأخير جذابًا بشكل خاص على قناة المحو عند استخدام رمز محو بدون معدل .

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

رمز التكرار هو نظام ترميز يُكرر البتات عبر قناة لتحقيق اتصال خالٍ من الأخطاء. عند إرسال تدفق بيانات، تُقسّم البيانات إلى كتل من البتات. تُرسل كل كتلة عددًا محددًا مسبقًا من المرات. على سبيل المثال، لإرسال نمط البتات 1011 ، يمكن تكرار كتلة الأربع بتات ثلاث مرات، مما ينتج عنه 1011 1011 1011. إذا استُقبل نمط الاثني عشر بت هذا على أنه 1010 1011 1011 - حيث تختلف الكتلة الأولى عن الكتلتين الأخريين - فهذا يعني حدوث خطأ.

يُعدّ رمز التكرار غير فعّال للغاية، وقد يكون عرضةً للمشاكل إذا حدث الخطأ في نفس الموضع تمامًا لكل مجموعة (على سبيل المثال، سيتم اكتشاف 1010 1010 1010 في المثال السابق على أنها صحيحة). تكمن ميزة رموز التكرار في بساطتها الشديدة، وهي تُستخدم بالفعل في بعض عمليات بث محطات الأرقام . ^{[ 14 ] [ 15 ]}

بت التكافؤ هو بت يُضاف إلى مجموعة من بتات المصدر لضمان أن يكون عدد البتات المُفعّلة (أي البتات التي قيمتها 1) في الناتج زوجيًا أو فرديًا. وهي آلية بسيطة للغاية يمكن استخدامها للكشف عن خطأ واحد أو أي عدد فردي آخر (مثل ثلاثة، خمسة، إلخ) في المخرجات. يؤدي وجود عدد زوجي من البتات المقلوبة إلى ظهور بت التكافؤ صحيحًا حتى وإن كانت البيانات خاطئة.

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

توجد أيضًا تقنيات أخرى لتجميع البتات.

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

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

يُعدّ فحص التكرار الدوري (CRC) دالة تجزئة غير آمنة مصممة للكشف عن التغييرات العرضية في البيانات الرقمية في شبكات الحاسوب. وهو غير مناسب للكشف عن الأخطاء المُدخلة عمدًا. يتميز بتحديد متعدد حدود مولد ، يُستخدم كمقسوم عليه في عملية قسمة مطولة على حقل منتهٍ ، حيث تُعتبر بيانات الإدخال هي المقسوم . أما الباقي فيُصبح هو النتيجة.

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

يمكن اعتبار بت التكافؤ بمثابة حالة خاصة من بت CRC أحادي البت.

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

تُوفّر التوقيعات الرقمية ضمانات قوية بشأن سلامة البيانات، سواءً أكانت التغييرات التي طرأت عليها عرضية أم متعمدة. ولعلّ أبرز ما يُميّز التوقيعات الرقمية هو كونها جزءًا من بروتوكول HTTPS لتصفح الإنترنت بشكل آمن.

يمكن استخدام أي رمز تصحيح أخطاء للكشف عن الأخطاء. يستطيع الرمز ذو مسافة هامينغ الدنيا ( d ) الكشف عن ما يصل إلى d - 1 خطأ في كلمة رمزية. يُعد استخدام رموز تصحيح الأخطاء القائمة على المسافة الدنيا مناسبًا للكشف عن الأخطاء إذا رُغِبَ في وضع حد أدنى صارم لعدد الأخطاء المراد اكتشافها.

تُعدّ الرموز ذات مسافة هامينغ الدنيا d = 2 حالات مُنحلة من رموز تصحيح الأخطاء، ويمكن استخدامها للكشف عن الأخطاء الفردية. وتُعدّ بتة التكافؤ مثالاً على رمز يكشف عن خطأ فردي.

في حزمة بروتوكولات TCP/IP النموذجية ، يتم تنفيذ التحكم في الأخطاء على مستويات متعددة:

• تستخدم كل حزمة بيانات إيثرنت آلية كشف الأخطاء CRC-32 . ويتم تجاهل الحزم التي تحتوي على أخطاء مكتشفة بواسطة جهاز الاستقبال.
• يحتوي رأس بروتوكول IPv4 على مجموع اختباري يحمي محتويات الرأس. يتم إسقاط الحزم ذات المجاميع الاختبارية غير الصحيحة داخل الشبكة أو عند جهاز الاستقبال.
• تم حذف المجموع الاختباري من رأس IPv6 من أجل تقليل تكاليف المعالجة في توجيه الشبكة ولأن تقنية طبقة الارتباط الحالية يفترض أنها توفر اكتشافًا كافيًا للأخطاء (انظر أيضًا RFC 3819).
• يحتوي بروتوكول UDP على مجموع اختباري اختياري يغطي حمولة البيانات ومعلومات العنونة في رؤوس UDP وIP. يتم تجاهل الحزم ذات المجموع الاختباري غير الصحيح بواسطة مكدس الشبكة . يُعد المجموع الاختباري اختياريًا في IPv4، وإلزاميًا في IPv6. عند حذفه، يُفترض أن طبقة ربط البيانات توفر مستوى الحماية المطلوب من الأخطاء.
• يوفر بروتوكول TCP مجموعًا اختباريًا لحماية الحمولة ومعلومات العنونة في رؤوس TCP وIP. يتم تجاهل الحزم ذات المجاميع الاختبارية غير الصحيحة بواسطة مكدس الشبكة، ويتم إعادة إرسالها في النهاية باستخدام ARQ، إما بشكل صريح (مثل من خلال المصافحة الثلاثية ) أو ضمنيًا بسبب انتهاء المهلة .

ارتبط تطوير رموز تصحيح الأخطاء ارتباطًا وثيقًا بتاريخ مهمات الفضاء السحيق نظرًا للتضاؤل ​​الشديد في قوة الإشارة عبر المسافات بين الكواكب ومحدودية الطاقة المتاحة على متن المركبات الفضائية. فبينما كانت المهمات المبكرة ترسل بياناتها غير مشفرة، بدأ تطبيق تصحيح الأخطاء الرقمي عام 1968 باستخدام رموز التفافية (مفككة بشكل غير مثالي) ورموز ريد-مولر . ^{[ 18 ]} وقد كان رمز ريد-مولر مناسبًا تمامًا للضوضاء التي تتعرض لها المركبة الفضائية (والتي تتطابق تقريبًا مع منحنى الجرس )، وتم تطبيقه على مركبة مارينر الفضائية واستُخدم في مهمات بين عامي 1969 و1977.

صُممت مهمتا فوياجر 1 وفوياجر 2 ، اللتان انطلقتا عام 1977، لتوفير صور ملونة ومعلومات علمية من كوكبَي المشتري وزحل . ^{[ 19 ]} وقد نتج عن ذلك زيادة في متطلبات التشفير، ولذا، زُوِّدت المركبتان الفضائيتان برموز التفافية ( مُفكَّكة باستخدام فيتربي على النحو الأمثل ) يمكن دمجها مع رمز غولاي الخارجي (24، 12، 8) . كما دعمت فوياجر 2 تطبيقًا لرمز ريد -سولومون . وقد أتاح رمز ريد-سولومون-فيتربي (RSV) المدمج تصحيحًا قويًا للأخطاء، ومكّن المركبة الفضائية من القيام برحلة ممتدة إلى أورانوس ونبتون . وبعد ترقيات نظام تصحيح الأخطاء في عام 1989، استخدمت كلتا المركبتين رمز RSV الخاص بفوياجر 2 .

توصي اللجنة الاستشارية لأنظمة بيانات الفضاء حاليًا باستخدام رموز تصحيح الأخطاء ذات أداء مماثل لرمز RSV الخاص بمركبة فوياجر 2 كحد أدنى. وتتراجع شعبية الرموز المتسلسلة في مهمات الفضاء، ويتم استبدالها برموز أكثر قوة مثل رموز Turbo أو رموز LDPC .

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

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

تُستخدم رموز كشف الأخطاء وتصحيحها غالبًا لتحسين موثوقية وسائط تخزين البيانات. ^{[ 20 ]} احتوت أول وسائط تخزين بيانات على أشرطة مغناطيسية عام 1951 على مسار تكافؤ قادر على كشف أخطاء البت الواحد. لا يقتصر دور رمز المستطيل الأمثل المستخدم في أشرطة التسجيل المشفرة بالمجموعات على كشف أخطاء البت الواحد فحسب، بل يقوم أيضًا بتصحيحها. تتضمن بعض تنسيقات الملفات ، وخاصة تنسيقات الأرشيف ، مجموعًا اختباريًا (غالبًا CRC-32) لكشف التلف والاقتطاع، ويمكنها استخدام ملفات التكرار أو ملفات التكافؤ لاستعادة أجزاء من البيانات التالفة. تُستخدم رموز ريد-سولومون في الأقراص المدمجة لتصحيح الأخطاء الناتجة عن الخدوش.

تستخدم محركات الأقراص الصلبة الحديثة رموز ريد-سولومون لاكتشاف الأخطاء الطفيفة في قراءة القطاعات وتصحيحها، واستعادة البيانات التالفة من القطاعات المعطوبة وتخزينها في القطاعات الاحتياطية. ^{[ 21 ]} تستخدم أنظمة RAID مجموعة متنوعة من تقنيات تصحيح الأخطاء لاستعادة البيانات عند تعطل محرك الأقراص الصلبة بشكل كامل. تدعم أنظمة الملفات مثل ZFS و Btrfs ، بالإضافة إلى بعض تطبيقات RAID ، تنظيف البيانات وإعادة تركيبها، مما يسمح باكتشاف القطاعات التالفة واستعادتها (إن أمكن) قبل استخدامها. ^{[ 22 ]} يمكن إعادة كتابة البيانات المستعادة إلى نفس الموقع الفعلي تمامًا، أو إلى قطاعات احتياطية في مكان آخر على نفس قطعة الجهاز، أو يمكن إعادة كتابتها على جهاز بديل.

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

تستخدم وحدات التحكم في الذاكرة المصححة للأخطاء تقليديًا رموز هامينغ ، على الرغم من أن بعضها يستخدم التكرار الثلاثي المعياري . يسمح التداخل بتوزيع تأثير شعاع كوني واحد قد يُخلّ بتوازن عدة بتات متجاورة فعليًا عبر كلمات متعددة، وذلك بربط البتات المتجاورة بكلمات مختلفة. طالما أن اضطراب الحدث الفردي (SEU) لا يتجاوز عتبة الخطأ (مثل خطأ واحد) في أي كلمة معينة بين عمليات الوصول، فإنه يمكن تصحيحه (مثلًا، بواسطة رمز تصحيح خطأ أحادي البت)، ويمكن الحفاظ على وهم نظام ذاكرة خالٍ من الأخطاء. ^{[ 23 ]}

بالإضافة إلى المكونات المادية التي توفر الميزات اللازمة لتشغيل ذاكرة ECC، تحتوي أنظمة التشغيل عادةً على آليات إبلاغ تُستخدم لإرسال إشعارات عند استعادة الأخطاء العابرة بسلاسة. ومن الأمثلة على ذلك نظام EDAC الفرعي في نواة لينكس (المعروف سابقًا باسم Bluesmoke )، الذي يجمع البيانات من المكونات المُفعّلة لفحص الأخطاء داخل نظام الحاسوب؛ فإلى جانب جمع الأحداث المتعلقة بذاكرة ECC والإبلاغ عنها، يدعم هذا النظام أيضًا أخطاء التحقق من المجموع الاختباري الأخرى، بما في ذلك تلك التي يتم اكتشافها على ناقل PCI . ^{[ 24 ] [ 25 ] [ 26 ]} كما تدعم بعض الأنظمة أيضًا تنظيف الذاكرة لاكتشاف الأخطاء وتصحيحها مبكرًا قبل أن تصبح غير قابلة للاستعادة.