مرجع
آخر الزيارات

خاصية تصحيح الخطأ

1٬997 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: خاصية تصحيح الخطأ وتختصر إلى (FEC) وهي مصطلح في الاتصال عن بعد، ونظرية المعلومات، ونظرية التكويد هذه التقنية تستعمل للسيطرة على الأخطاء وإصلاحها أثناء نقل البيانات عبر قنوات إتصال غير موثوق بها أو صاخبة (noisy communication channels)، حيث…. في هذه المقالة 12 قسماً: «الفك المحلي للرموز واختبارها»، «مصحح الخطأ ريد-سولومون» و«كيف تعمل» وغيرها.
المحتويات
  1. الفك المحلي للرموز واختبارها
  2. مصحح الخطأ ريد-سولومون
  3. كيف تعمل
  4. 3 (مُصحح الخطأ الواحد) التكرار الثلاثي القياسي
  5. 8 (TECFED) رمز جولاي الثنائي ممتد
  6. كود التكرار، مثل التكرار المعياري الثلاثي
  7. كود توربو
  8. رموز توربو
  9. أنواع خاصية تصحيح الخطأ
  10. كود المجموعة
  11. كود هامينج
  12. معدل الضجيج وعلاقته بتقليل الأخطاء

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

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

إضافةً إلى ذلك، وقد كان لعالم الرياضيات الأمريكي ريتشارد هامينغ السَبق في هذا المجال في الأربعينيات، حيث اخترع أول رمزٍ لتصحيح الخطأ عام 1950: وهو رمز (7,4) هامينج «Hamming (7,4) code»، ويتيح التكرار للمُستَلم أن يتعرف على الأخطاء المحدودة التي قد توجد في أي مكان في الرسالة، ويسمح كذلك في أغلب الأوقات بتصحيح هذه الأخطاء دون إعادة الإرسال، كما تُمكّن خاصية تصحيح الخطأ المُستقبل من تصحيح الأخطاء دون الحاجة للجوء إلى قناة عكسية لطلب إعادة إرسال البيانات، ولكن بتكلفة عرض نطاق ترددي أعلى لقناة مُثبتة. ولذلك يتم تطبيق خاصية تصحيح الخطأ عندما تكون إعادة الإرسال مكلّفة أو مستحيلة مثل: خطوط الإتصال أحادية-الاتجاه، وعندما يكون البث لأكثر من مستلم في الإرسال المتعدد (multicast). وتتم إضافة المعلومات الخاصة بخاصية تصحيح الخطأ إلى أجهزة التخزين الشامل لتسهيل استعادة البيانات التالفة، وتُستعمل بشكلٍ أوسع في أجهزة المودم.

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

الفك المحلي للرموز واختبارها

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

  • قائمة رموز تصحيح الخطأ
  • رمز المسافة
  • 2 (مُكتشف الخطأ الواحد) تكافؤ

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

مصحح الخطأ ريد-سولومون

كود تراكم التكرار (Repeat-accumulate code)

كود ريد-مولر (Reed–Muller code)

كيف تعمل

من جانب آخر، وكمثالٍ بسيط على خاصية تصحيح الخطأ تُرسل كل وحدة بيانات ثلاث مرات، وهو ما يُعرف ب (3,1) رمز التكرار. حيث يستطيع المُستلم أن يرى 8 نسخ من المخرج خلال القناة الصاخبة، راجع الجدول أدناه.

علاوةً على ذلك، وحدتين من المعلومات المحذوفة من الثلاثية (هذه الحالات غير موجودة بالجدول).

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

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

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

وحدة معلومات واحدة من الثلاثية التي وقع بها الخطأ، أو

3 (مُصحح الخطأ الواحد) التكرار الثلاثي القياسي

  • 3 (مُصحح الخطأ الواحد) مقارب جدًا لهامينج هامينج(7,4)
  • 4 (رموز هامينج بتكافؤ إضافي (SECDED)) هامينج ممتد
  • 7 (مُصحح خطأ ثلاثي) يماثل رمز جولاي الثنائي

8 (TECFED) رمز جولاي الثنائي ممتد

  • أكواد إيه إن (AN codes)
  • كود بي سي إتش (BCH code)
  • كود بيرجر
  • كود الوزن الثابت
  • الكود التحويلي

كود التكرار، مثل التكرار المعياري الثلاثي

وفي هذا السياق، كود تورنادو (Tornado code)، وهو على وجه التقريب أفضل رموز تصحيح المحو، وهو مبشر لكود آخر وهو كود فاونتين

كود توربو

  • كود والش-هادامارد (Walsh–Hadamard code)
  • انظر كذلك
  • كشف الأخطاء وتصحيحها

رموز توربو

وفي هذا الصدد، تعد سي دي إم أي 2000 (TIA IS-2000) واحدة من أقدم التطبيقات التجارية لترميز توربو وهي تكنولوجيا الهواتف الرقمية المطورة بواسطة شركة كوالكوم والتي تبيعها شركات فيرايزون وايرلس، و Sprint Nextel، وشركات أخرى. يُستعمل كذلك ترميز توربو لتطوير CDMA2000 1x بصفة خاصة في الدخول على شبكة الإنترنت، التطور الأمثل للبيانات (1xEV-DO) (TIA IS-856). مثلاً: 1x, EV-DO الذي طورته شركة كوالكوم، وتبيعه شركة فيرايزون وايرلس، وشركة Sprint Nextel ، وشركات أخرى (الاسم التجاري الذي تطلقه شركة Verizon على 1xEV-DO هو وصول النطاق العريض (Broadband Access)، واسم الاستهلاك والاسم التجاري الذي تطلقه شركة Sprint على 1xEV-DO هو رؤية القوة (Power Vision) وموبايل المدى الواسع (Mobile Broadband))

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

أنواع خاصية تصحيح الخطأ

ومن جهة أخرى، تتمثل الفئتان الأساسيتان من رموز خاصية تصحيح الخطأ في التالي: فئة رمز القالب (block code) الرمز التحويلي (convolutional code).

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

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

مراجعة التكافؤ قليل الكثافة (LDPC)

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

ومن جهة أخرى، توجد أنواع كثيرة لرمز القالب، ولكن الرمز الأكثر ملاحظةً بين الأنواع الكلاسيكية هو مصحح الخطأ ريد-سولومون (Reed-Solomon error correction) بسبب كثرة استخدامه في القرص المضغوط، وفي الدي في دي (DVD)، وفي مشغل القرص الصلب. ومن الأمثلة الأخرى لرموز القوالب، رمز جولاي (Golay)، رمز بي سي إتش (BCH code)، التكافؤ متعدد الأبعاد (Multidimensional parity)، ورمز هامينج.

إضافةً إلى ذلك، تُستعمل رموز مراجعة التكافؤ قليل الكثافة الآن في مستويات اتصال عالية السرعة كثيرة، مثل الجيل الثاني من الأقمار الصناعية للبث الرقمي للفيديو (DVB-S2) (بث رقمي للفيديو)، ووايماكس (المستوى IEEE 802.16e لاتصالات الموجات الكهرومغناطيسية القصيرة)، وشبكة اتصالات محلية لاسلكية عالية السرعة (LAN) (IEEE 802.11n)، و10GBase-T Ethernet (802.3an)، وG.hn/G.9960 (مستوى ITU-T للشبكة على خطوط القوة، خطوط التليفون، والكابل متحد المحور). خُصصت رموز مراجعة التكافؤ قليل الكثافة الأخرى لمعايير الاتصال اللاسلكية مثل الجيل الثالث من مشروع المشاركة (3GPP) (MBMS) (انظر رموز فاونتين (fountain codes)).

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

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

إضافةً إلى ذلك، تم تصميم بعض خواص تصحيح الخطأ لتقوم بتصحيح إدراج وحدة المعلومات ومسحها، مثل رموز ماركر (Marker Codes) ورموز ووترمارك (Watermark Codes).

علاوةً على ذلك، ولكن نظرًا للمجهود الكبير التي تتطلبه الأطروحة في مجال الحوسبة لتنفيذ مدخل الرموز ومفكك الرموز مقدمة رموز ريد-سولومون،

من جانب آخر، يستعمل رمز هامينج إي سي سي (Hamming ECC) عادةً لتصحيح أخطاء بطاقة الذاكرة ناند (NAND flash). ويوفر ذلك مصحح خطأ وحدة معلومات واحدة ومكتشف خطأ وحدتي معلومات. تناسب رموز هامينج خلية المستوى الواحد الموثوقة بشكل أكبر (SLC) NAND فقط. تتطلب الخلية متعددة المستويات (MLC) الأكثر كثافة في ذاكرة ناند رمزًا أقوى لتصحيح الأخطاء المتعددة مثل البي سي إتش أو الريد سولومون.

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

من جهة ثانية، كان روبرت جي جالاجر (Robert G. Gallager) هو أول من قدم رموز مراجعة التكافؤ قليل الكثافة كأطروحة في رسالة الدكتوراه عام 1960،

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

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

فقد تم تجاهلها كثيرًا حتى فترة قريبة.

علاوةً على ذلك، تعمل فئة رموز القوالب على قوالب (حزم) ثابتة الحجم من وحدات المعلومات أو الرموز (symbols) التي تم تحديد حجمها مسبقًا. يمكن أن يتم حل رموز القوالب العملية في الوقت المتعدد الحدود (polynomial time) إلى طول قوالبها.

وفي السياق ذاته، في الطبقات العليا، يكون حل خاصية تصحيح الخطأ لمشكلة مستويات بث أجهزة المحمول هو رمز الرابتور (Raptor code) أو الرابتور كيو (RaptorQ).

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

تستعمل رموز خاصية تصحيح الخطأ المتصلة لتحسين الأداء

كود المجموعة

  • كود جولاي، الذي ينشق منه كود جولاي الثنائي الذي له أهمية عملية
  • كود جوبا (Goppa code)، الذي يستعمل في McEliece cryptosystem
  • كود هادامرد (Hadamard code)
  • كود هاجلبارجر (Hagelbarger code)

كود هامينج

من جهة ثانية، كود تحويل لوبي (LT code)، وهو الأفضل على وجه التقريب كود تصحيح خطأ ليس له معدل محو (كود فاونتين)

  • كود أساسه مربع اللاتينية للضجيج الملون (منتشر انتشاراً واسعًا في خطوط القوة)
  • كود ليكسيكوجرافيك (Lexicographic code)
  • الكود الطويل (Long code)
  • كود الوزن الثابت (m of n codes)
  • كود الإنترنت (Online code)، وهو الأفضل على وجه التقريب كود تصحيح خطأ ليس له معدل محو
  • كود رابتور (Raptor code)، وهو الأفضل على وجه التقريب كود تصحيح خطأ ليس له معدل محو

وعلى صعيد آخر، كود مراجعة التكافؤ قليل الكثافة، ويُسمى كذلك كود جالاجير (Gallager code)، وهو نسخة كود الرسم المتناثر (sparse graph code) الأصلية

معدل الضجيج وعلاقته بتقليل الأخطاء

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

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

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

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

من جهة ثانية، يستعمل طلب التكرار الآلي الهجين (hybrid automatic repeat-request) خاصية تصحيح أخطاء ثابتة طالما تستطيع هذه الخاصية التعامل مع معدل الأخطاء، ولكن إذا أصبح معدل الأخطاء عالياً جدًا، يتم التحويل إلى طلب التكرار الآلي (Automatic Repeat Request)ARQ ،

كذلك، هذا هو اتجاه الكل أو لا شيء — حيث أصبح التأثير الرقمي — أفضل حيث تستعمل رموز أقوى وهذا أفضل من المفهوم النظري نظرية ترميز قنوات الضجيج (Shannon limit).

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

ومع ذلك، تتكيف بعض الأنظمة مع ظروف أخطاء القناة المُعطاة:

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.