الرئيسيةعريقبحث

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

☰ جدول المحتويات

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

نظرة عامة

اكتشاف الاخطاء وتصحيحها (error detection and correction)

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

ويمكن تقسيم أنواع الأخطاء الممكن حدوثها إلى نوعين رئيسيين هما : 1)خطأ في بت واحد (single-bit error) 2)خطأ في مجموعة من البت (burst error)

خطأ في بت واحد (single-bit error) : وهو تعرض بت واحدة للتغير اثناء نقل البيانات اما من صفر إلى واحد او من واحد لتصبح قيمتها صفر داخل الوحدة الواحدة سواء أكانت بايت او كاراكتر خطأ فيي مجموعة من البت (burst error) : تعرض قيمتين أو أكتر للتغير داخل الوحدة الواحدة وتغيير قيمهم من صفر إلى واحد او العكس . يعتمد عدد القيم المتأثرة بحدوث الخطأ على عاملين رئيسيين هما :

-سرعة نقل البيانات (data rate) - المدة التي تعرضت لها البيانات لعوامل التغيير(noise length)

وتكون احتمالية حدوث الخطأ في أكثر من بت أكبر من احتمالية حدوث الخطأ في بت واحدة، وذلك لأنه غالبا ما تكون المدة التي تتعرض لها البيانات لعوامل تؤدي إلى تغييرها أكبر من المدة اللازمة لنقل بت واحدة ,[1] وهذا يعني أنه عندما تؤثر هذه العوامل على البيانات تؤثر على أكثر من قيمة . على سبيل المثال، اذا اردنا نقل البيانات بسرعة 1 كيلوبت بالثانية الواحدة وكان طول عوامل الضجيج التي ستعبر من خلالها هذه البيانات هو 1\100 ثانية، فان ذلك سيؤدي إلى تأثر 10 بت ( 1كيلو \ 100 ) ,[1] وهكذا.

الزيادة(redunduncy)

.

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

الترميز(coding)

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

التعريفات

التعريفات العامة لهذه المصطلحات هي:

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

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

نبذة تاريخية

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

مقدمة

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

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

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

التطبيق

يمكن تصحيح الأخطاء بوجه عام بإحدى طريقتين:

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

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

سبل الرصد

سبل التصحيح

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

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

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

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

رموز التكرار

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

ورموز التكرار لها فاعلية محدودة للغاية، وتفتح الباب أمام مشاكل كبيرة إذا كان الخطأ في المكان نفسه من كتل المجموعة (مثلاً إذا كان الترتيب في المثال السابق "1010 1010 1010" فلن يكتشف أحد الخطأ). والميزة في رموز التكرار هي أنها بسيطة للغاية، وتستخدم على أرض الواقع في نقل بعض محطات الأرقام.[8][9]

بتات التماثل

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

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

تدقيق المجموع

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

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

اختبارات التكرار الدوري (CRC)

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

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

يعتبر التماثل أيضًا حالة خاصة لاختبار التكرار الدوري، حيث ينتج القاسم البت الواحدة لاختبار التكرار الدوري x + 1.

دالة هاش التشفيرية

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

رموز تصحيح الخطأ

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

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

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

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

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

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

تتكون بروتوكولات طلب إعادة الإرسال تلقائيًا من ثلاثة أنواع بروتوكول قف وانتظر لطلب إعادة الإرسال تلقائيا وبروتوكول استمرار إرسال الإطارات لطب إعادة الإرسال تلقائيا وبروتوكول الإعادة المنتقاة لطلب إعادة الإرسال تلقائيا.

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

رمز تصحيح الخطأ

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

عادة، تميز رموز تصحيح الخطأ بين الرموز التحويلية ورموز المجموعة ::

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

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

الطريقة الهجين

طلب إعادة الإرسال الهجيني تلقائيا عبارة عن مجموعة مركبة من طلب إعادة الإرسال تلقائيًا وخاصية تصحيح الخطأ. هناك نظامين أساسيين:[10]

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

ويُجذب النظام السابق بطريقة خاصة لـقناة محو الخطأ عند استخدام رمز محو النسب الأقل.

التطبيقات

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

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

يجب أن تحتوي التطبيقات المستخدمة لطلب إعادة الإرسال تلقائيًا على أي قناة إرجاع. لا تستطيع التطبيقات غير المستخدمة لقناة الإرجاع استخدام طلب إعادة الإرسال تلقائيًا.

يتحتم على التطبيقات التي تتطلب معدلات خطأ منخفضة جدًا (مثل عمليات تحويل النقود رقميًا) استخدام طلب إعادة الإرسال تلقائيا.

الإنترنت

في المجموعة النموذجية لـ بروتوكول التحكم في النقل / بروتوكول الإنترنت، يتم إصلاح الأعطال على مستويات متعددة:

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

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

يرتبط التطور في رموز تصحيح الخطأ بتاريخ رحلات الفضاء العميق بسبب تخفيف التمويه الشديد لقوة الإشارة في المسافات بين الكواكب، والحد من القوة التي يمكن الحصول عليها على متن المسابير الفضائية. على الرغم من إرسال البعثات الأولية بياناتها غير المشفرة، بدأ منذ عام 1968 تصحيح الأخطاء الرقمية التي نفذت في شكل (فك رموز الشفرة على النحو الأمثل) الرموز التحويلية و رموز ريد مولر Reed-Muller.[11] وقد تلائم رمز ريد مولر جيدًا مع الضجيج التي تحدثه المركبة الفضائية التي تخضع لـ (التطابق النسبي للـ منحنى جرسي)، والتي نفذت على رحلات مركبة الفضاء مارينر في الفترة بين عام 1969 وعام 1977.

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

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

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

بث الأقمار الصناعية (البث الفيديو الرقمي)

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

نظرة عامة

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

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

غالبًا ما تستخدم رموز اكتشاف الخطأ وتصحيحه لتحسين الثقة في وسائل تخزين البيانات.

لقد ظهر "المسار المتماثل" في أول شريط مغناطيسي لتخزين البيانات في عام 1951. بينما استخدم "رمز المستطيل الأمثل" في أشرطة التسجيل المشفرة للمجموعة وليست فقط للاستكشاف ولكن لتصحيح الأخطاء أحادية البت أيضًا.

وتحتوي بعض صيغ الملفات وبخاصة الصيغ الأرشيفية على تدقيق مجموع (في معظم الأحيان اختبار التكرار الدوري 32) للكشف عن الفساد والتقصير ومن الممكن تكرار العمل و/أو ملفات التكافؤ لاستعادة أجزاء من البيانات التالفة.

يستخدم رموز ريد-سولومون في الأقراص المضغوطة لتصحيح الأخطاء التي تسببت عن طريق الخدش.

وتستخدم الأقراص الصلبة الحديثة رموز اختبار التكرار الدوري للكشف عن رموز ريد-سولومون وذلك بغرض تصحيح الأخطاء الطفيفة في القطاع المقروء، واستعادة البيانات من القطاعات التي بها "سوء رحيل" وتخزين تلك البيانات في قطاعات بديلة.[13]

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

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

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

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

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

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

بعض الأنظمة المدعمة لـ تنقية الذاكرة.

مقالات ذات صلة

ملاحظات

  1. Behrouz A. Forouzan, Data Communications,page 258
  2. Behrouz A. Forouzan, Data Communications , page 258
  3. Behrouz A. Forouzan , Data Communications , page 259
  4. See also Encyclopedia of Microcomputers: Volume 6, p. 343. نسخة محفوظة 29 مارس 2012 على موقع واي باك مشين.
  5. موسى بن ميمون, The Laws of Tefillin, Mezuzot, and Torah Scrolls, 1:2
  6. Menachem Cohen, The Idea of the Sanctity of the Biblical Text and the Science of Textual Criticism in HaMikrah V'anachnu, ed. Uriel Simon, HaMachon L'Yahadut U'Machshava Bat-Z'mananu and Dvir, Tel-Aviv, 1979. نسخة محفوظة 05 سبتمبر 2015 على موقع واي باك مشين.
  7. Fagan, Brian M., and Charlotte Beck, The Oxford Companion to Archeology, entry on the "Dead sea scrolls", Oxford University Press, 1996.
  8. Frank van Gerwen. "Numbers (and other mysterious) stations". مؤرشف من الأصل في 12 يوليو 201712 مارس 2012.
  9. Gary Cutlack (25 أغسطس 2010). "Mysterious Russian 'Numbers Station' Changes Broadcast After 20 Years". Gizmodo. مؤرشف من الأصل في 5 يوليو 201712 مارس 2012.
  10. A. J. McAuley, Reliable Broadband Communication Using a Burst Erasure Correcting Code, ACM SIGCOMM, 1990.
  11. K. Andrews et al., The Development of Turbo and LDPC Codes for Deep-Space Applications, Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007.
  12. W. Huffman, V. Pless, Fundamentals of error-correcting codes, Cambridge University Press, , 2003.
  13. My Hard Drive Died | Scott A. Moulton - تصفح: نسخة محفوظة 21 أكتوبر 2010 على موقع واي باك مشين.
  14. "Using StrongArm SA-1110 in the On-Board Computer of Nanosatellite". Tsinghua Space Center, جامعة تسينغ - هوا, Beijing. مؤرشف من الأصل في 11 سبتمبر 201616 فبراير 2009.

موسوعات ذات صلة :