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

كشف الأخطاء وتصحيحها (بالإنجليزية: Error detection and correction) ويختصر إلى ECC ، في نظرية المعلومات ونظرية الترميز وبعض تطبيقات علم الحاسوب والاتصال عن بعد، تعد عملية كشف الأخطاء وتصحيحها أو التحكم في الأخطاء بمثابة تقنية تتيح إمكانية التوصيل الموثوق لـ البيانات الرقمية بدلاً من قنوات الاتصال غير الموثوقة. وتطبق هذه التقانات حصرا على الشبكات الرقمية دون الشبكات التماثلية وتلك إحدى المعايير التي رسخت بناء الشبكات الرقمية وأزاحت الشبكات التماثلية. وتتعرض كثير من قنوات الاتصال لـ ضجيج القناة  مما قد يتسبب في حدوث أخطاء أثناء نقل البيانات من المصدر إلى المتلقي. وتساعد تقنيات كشف الأخطاء في اكتشاف تلك الأخطاء، بينما تسهم تقنيات تصحيح الأخطاء في إعادة إنشاء البيانات الأصلية.

نظرة عامة

اكتشاف الاخطاء وتصحيحها (error detection and correction)
   في اي شبكة يجب ان تكون لديها قابيلة لنقل البيانات بدقة مقبولة وبنسبة خطأ معقولة , معظم تطبيقات عصرنا الحالي بحاجة إلى درجة ععالية من الكفاءة لضمان وصول البيانات كما ارسلت دون حدوث تغيير عليها .
   فأثناء إرسال البيانات من نقطة لاخرى هناك احتمالية لتعرض هذه البيانات للتلف اثناء رحلتها , فهناك العديد من العوامل التي بامكانها التأثير على البيانات او على جزء منها وتغييره , لهذا نحن بحاجة غالبا إلى اليات لاكتشاف هذه الأخطاء وتصحيحها .
   بعض التطبيقات ممكن ان تحتمل نسبة خطأ بسيطة لا تؤثر على البيانات بشكل كبير مثل مقاطع الفيديو (حيث يتم تمثيل الفيديو بعدد هائل جدا من البكسل وهي اصغر وحدة في الصورة ويتم تمثيل هذه البكسل بعدد معين من البت ) لهذا عند حدوث خطأ في مكان معين لن يؤثر بدرجة كبيرة على الصورة العامة , وهناك تطبيقات أخرى لا تحتمل الخطأ بتاتا كنقل نص او مقاطع صوتية فأي خطأ فيها يؤدي إلى تغيير في البيانات ويؤثر عليها .
  عند وصول البيانات لطبقة الربط (datalink layer) يتم فحص هذه البيانات وفي حال تم اكتشاف حدوث خطأ يتم معالجته قبل نقل هذه البيانات إلى نقطة أخرى .
ويمكن تقسيم أنواع الأخطاء الممكن حدوثها إلى نوعين رئيسيين هما :
1)خطأ في بت واحد (single-bit error) 
2)خطأ في مجموعة من البت (burst error)
   خطأ في بت واحد (single-bit error) : وهو تعرض بت واحدة للتغير اثناء نقل البيانات اما من صفر إلى واحد او من واحد لتصبح قيمتها صفر داخل الوحدة الواحدة سواء أكانت بايت او كاراكتر 
   خطأ فيي مجموعة من البت (burst error) : تعرض قيمتين أو أكتر للتغير داخل الوحدة الواحدة وتغيير قيمهم من صفر إلى واحد او العكس .
     يعتمد عدد القيم المتأثرة بحدوث الخطأ على عاملين رئيسيين هما :
-سرعة نقل البيانات (data rate)
- المدة التي تعرضت لها البيانات لعوامل التغيير(noise length)
   وتكون احتمالية حدوث الخطأ في أكثر من بت أكبر من احتمالية حدوث الخطأ في بت واحدة , وذلك لأنه غالبا ما تكون المدة التي تتعرض لها البيانات لعوامل تؤدي إلى تغييرها أكبر من المدة اللازمة لنقل بت واحدة , وهذا يعني أنه عندما تؤثر هذه العوامل على البيانات تؤثر على أكثر من قيمة .
   على سبيل المثال , اذا اردنا نقل البيانات بسرعة 1 كيلوبت بالثانية الواحدة وكان طول عوامل الضجيج التي ستعبر من خلالها هذه البيانات هو 1\100 ثانية , فان ذلك سيؤدي إلى تأثر 10 بت ( 1كيلو \ 100 ) , وهكذا.

الزيادة(redunduncy)

.
   الزيادة (redunduncy) :
    الزيادة هو مفهوم مهم واساسي في عملية اكتشاف وتصحيح الأخطاء الناتجة عن تعرض البيانات لعوامل التغيير أثناء نقلها من نقطة إلى أخرى , حيث يتم في هذه المرحلة زيادة بت اضافية على االبيانات من طرف المرسل وحذفها من طرف المستقبل , نستدل من خلالها على بعض الأخطاء الممكن حدوثها .
    تصحيح الأخطاء أصعب من اكتشافها , فاكتشاف الأخطاء أمر بسيط يتطلب فقط معرفة اذا كان هناك خطأ أم لا بغض النظر عن عدد البت المتأثرة بالخطأ بالتالي سواء أكان خطأ في بت واحد (single-bit error) او في مجموعة من البت (burst error) لا يهم , أما عملية تصحيحها فان ذلك يتطلب معرفة عدد القيم المتأثرة والأهم هو تحديد أماكنها في الرسالة ويعتمد ذلك على عدد الأخطاء وحجم الرسالة .
    على سبيل المثال اذا اردنا تصحيح خطأ واحد في رسالة سعتها 8 بت فهناك ثمانية احتمالات لمكان الخطأ , واذا اردنا تصحيح خطأ وقع في 2 بت برسالة حجمها 8 بت فهناك احتمالية لوجود الخطأ في 28 موقع مختلف (تباديل 8 في 2) , الان بامكانك تخيل صعوبة المستقبل بايجاد 10 اخطاء في رسالة سعتها 1000 بت .

الترميز(coding)

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

نبذة تاريخية

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

مقدمة

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

أنظمة اكتشاف الأخطاء

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

طلب إعادة الإرسال تلقائيًا

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

التطبيقات

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

الاتصالات اللاسلكية في الفضاء العميق

يرتبط التطور في رموز تصحيح الخطأ بتاريخ رحلات الفضاء العميق بسبب تخفيف التمويه الشديد لقوة الإشارة في المسافات بين الكواكب، والحد من القوة التي يمكن الحصول عليها على متن المسابير الفضائية. على الرغم من إرسال البعثات الأولية بياناتها غير المشفرة، بدأ منذ عام 1968 تصحيح الأخطاء الرقمية التي نفذت في شكل (فك رموز الشفرة على النحو الأمثل) الرموز التحويلية و رموز ريد مولر Reed-Muller. وقد تلائم رمز ريد مولر جيدًا مع الضجيج التي تحدثه المركبة الفضائية التي تخضع لـ (التطابق النسبي للـ منحنى جرسي)، والتي نفذت على رحلات مركبة الفضاء مارينر في الفترة بين عام 1969 وعام 1977.
وقد صممت رحلات فوياجر 1 وفوياجر 2 التي بدأت في عام 1977 لالتقاط صور ملونة بين المعلومات العلمية عن الكوكبين المشتري وزحل. وأدى ذلك إلى زيادة متطلبات الترميز، ومن ثم، تم دعم مركبة الفضاء عن طريق (خوارزمية فيتربي) لفك الرموز التحويلية التي يمكن أن تكون عبارة عن متسلسل مع غولاي(24,12,8) ترميز الخارجي. وتقوم فوياجر 2 بالتحقيق من الدعم الإضافي لتنفيذ رمز ريد-سولومون: المتسلسل من رمز ريد-سولومون-فيتيربي (أر إس في) والذي يسمح بتصحيح الخطأ بالقوة، وتمكين رحلة المركبة الفضائية من الامتداد إلى أورانوس ونبتون.
وتوصي اللجنة الاستشارية لنظم البيانات الفضائية حاليًا باستخدام رموز تصحيح الخطأ مع الأداء المماثل كحد أدنى لرمز ريد-سولومون-فيتيربي فوياجر 2. وقد تزايد فقدان مصداقية الرموز المتسلسلة مع الرحلات الفضائية، ويحل محلها رموز أكثر قوة منها مثل رموز تربو أو رموز المتكافئ المنخفض الكثافة.
وتقترح الأنواع المختلفة للفضاء العميق والرحلات المدارية التي أجريت محاولة الحصول على "مقاس واحد يناسب جميع" أنظمة تصحيح الخطأ التي ستشكل مشكلة مستمرة لبعض الوقت في المستقبل. في حين تختلف طبيعة الرحلات القريبة من الأرض وسيط ضجيج عن تلك التي تتم من المركبة الفضائية في رحلة التجارب بين الكواكب. إضافة إلى ذلك، فكلما زادت المسافة بين المركبة الفضائية والأرض، تصبح مشكلة تصحيح الضجيج أكبر.

تخزين البيانات

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

ذاكرة تصحيح الخطأ

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