خاصية تصحيح الخطأ
| نظرية المعلومات |
|---|
 |
 | هذه المقالة بحاجة لمراجعة خبير مختص في مجالها. |
خاصية تصحيح الخطأ (بالإنجليزية: Forward error correction) وتختصر إلى (FEC) وهي مصطلح في الاتصال عن بعد، ونظرية المعلومات، ونظرية التكويد[1] هذه التقنية تستخدم للسيطرة على الأخطاء وإصلاحها أثناء نقل البيانات عبر قنوات إتصال غير موثوق بها أو صاخبة (noisy communication channels)، حيث تُعد الفكرة الرئيسية لهذه الخاصية هي أن المُرسل يُشفر رسالته بطريقة التكرار باستخدام رمز تصحيح الخطأ (ECC). وقد كان لعالم الرياضيات الأمريكي ريتشارد هامينغ السَبق في هذا المجال في الأربعينيات، حيث اخترع أول رمزٍ لتصحيح الخطأ عام 1950: وهو رمز (7,4) هامينج «Hamming (7,4) code»، ويتيح التكرار للمُستَلم أن يتعرف على الأخطاء المحدودة التي قد توجد في أي مكان في الرسالة، ويسمح أيضًا في أغلب الأوقات بتصحيح هذه الأخطاء دون إعادة الإرسال، كما تُمكّن خاصية تصحيح الخطأ المُستقبل من تصحيح الأخطاء دون الحاجة للجوء إلى قناة عكسية لطلب إعادة إرسال البيانات، ولكن بتكلفة عرض نطاق ترددي أعلى لقناة مُثبتة. ولذلك يتم تطبيق خاصية تصحيح الخطأ عندما تكون إعادة الإرسال مكلّفة أو مستحيلة مثل: خطوط الإتصال أحادية-الاتجاه، وعندما يكون البث لأكثر من مستلم في الإرسال المتعدد (multicast). وتتم إضافة المعلومات الخاصة بخاصية تصحيح الخطأ إلى أجهزة التخزين الشامل لتسهيل استعادة البيانات التالفة، وتُستخدم بشكلٍ أوسع في أجهزة المودم.
ويتم تطبيق معالجة خاصية تصحيح الخطأ في المُستلم على تيار رقمي أو على إزالة التضمين التابعة لحامل مُعَدل رقميًا. وبالنسبة للأخير، تُعد خاصية تصحيح الخطأ جزءًا من المحول القياسي إلى الرقمي الأولي عند المُستقبل. ينفذ مفكك الرموز الذي يستخدم خوارزمية فيتربي (Viterbi decoder) خوارزمية سهلة الفهم لفك ترنيم البيانات الرقمية من على الإشارة القياسية التي أفسدها الضجيج. يستطيع العديد من واضعي رموز خاصية تصحيح الخطأ إظهار إشارة تدل على معدل الأخطاء الصغيرة (BER) والتي يمكن أن تستخدم كتغذية مرجعية موالِفة لإلكترونيات الاستلام القياسية.
يتم تحديد أقصى عدد من أخطاء الأجزاء المفقودة التي يمكن تصحيحها أثناء تصميم رمز خاصية تصحيح الخطأ، لذلك تختلف رموز خواص تصحيح الخطأ لتتناسب مع جميع الظروف.
كيف تعمل[عدل]
كما يضاف إلى خاصية تصحيح الخطأ تكرار المعلومات المرسلة باستخدام خوارزمية مُجهزة سابقًا. قد تكون وحدة المعلومات المكررة وظيفةً صعبة على كثير من وحدات المعلومات الأصلية. قد تظهر المعلومات الأصلية حرفيًا أو لا تظهر في المخرج المشفر؛ فالشفرات التي تقوم بإدراج المُدخلات غير المعدلة في المُخرجات هي انتظامية، بينما تكون الشفرات التي لا تقوم بعملية الإدراج للمُدخلات في المُخرجات غير انتظامية.
وكمثالٍ بسيط على خاصية تصحيح الخطأ تُرسل كل وحدة بيانات ثلاث مرات، وهو ما يُعرف ب (3,1) رمز التكرار. حيث يستطيع المُستلم أن يرى 8 نسخ من المخرج خلال القناة الصاخبة، راجع الجدول أدناه.
| الثلاثية المُستلمة | تم تفسيرها كالتالي |
|---|---|
| 000 | 0 (خالٍ من الخطأ) |
| 001 | 0 |
| 010 | 0 |
| 100 | 0 |
| 111 | 1 (خالٍ من الخطأ) |
| 110 | 1 |
| 101 | 1 |
| 011 | 1 |
وهذا يسمح بأن يتم تصحيح الخطأ في أي نموذج من النماذج الثلاثة عن طريق «تصويت الأغلبية» أو «التصويت الديمقراطي». تصل قدرة التصحيح في خاصية تصحيح الخطأ سالفة الذكر إلى:
- وحدة معلومات واحدة من الثلاثية التي وقع بها الخطأ، أو
- وحدتين من المعلومات المحذوفة من الثلاثية (هذه الحالات غير موجودة بالجدول).
وبالرغم من سهولة تنفيذه وانتشاره، إلا أن هذا التكرار المعياري الثلاثي يعتبر رمزًا غير كفؤ نسبيًا لخاصية تصحيح الخطأ. تقوم رموز خاصية تصحيح الخطأ الأفضل بفحص وحدات المعلومات المستلمة سابقًا، فيمكن أن تقوم بفحص الاثنتي عشرة وحدة الأخيرة، أو حتى المائة وحدة الأخيرة لتتمكن من فك رموز الوحدات الصغيرة الجديدة (في مجموعات من 2 إلى 8 وحدات).
معدل الضجيج وعلاقته بتقليل الأخطاء[عدل]
يمكن أن يُقال على خاصية تصحيح الخطأ أنها تعمل «بمعدل الضوضاء»، حيث إن كل وحدة معلومات تؤثر على كثير من الرموز المرسلة، ففساد بعض الرموز بسبب الضجيج يتيح عادةً لبيانات المستخدم الأصلية بأن تُستخرج من الرموز المستلمة الأخرى غير الفاسدة والتي تعتمد أيضًا على نفس بيانات المستخدم.
- بسبب هذا التأثير الناتج عن «تجمع المخاطر»، تقرر أنظمة الاتصال الرقمية التي تستخدم خاصية تصحيح الخطأ أن تحدد حداً أدنى لمستوى تناسب الإشارة-مع-الضجيج وتعمل فيما فوقه وليس أقل منه مطلقًا.
- هذا هو اتجاه الكل أو لا شيء — حيث أصبح التأثير الرقمي — أفضل حيث تستخدم رموز أقوى وهذا أفضل من المفهوم النظري نظرية ترميز قنوات الضجيج (Shannon limit).
- يقلل تداخل البيانات المشفرة لخاصية تصحيح الخطأ خصائص الكل أو لا شيء لرموز خاصية تصحيح الخطأ المرسلة عندما يحدث انفجار أخطائي لأخطاء القناة. ومع ذلك، يوجد لهذه الطريقة شروط، حيث يفضّل تطبيقها على بيانات المدى الضيق.
تستخدم معظم أنظمة الاتصال عن بعد رمز قناة ثابت مُصمم لقبول أسوأ الحالات من معدل أخطاء وحدات المعلومات، ثم تفشل في العمل نهائيًا إذا كان معدل الأخطاء أسوء من المتوقع. ومع ذلك، تتكيف بعض الأنظمة مع ظروف أخطاء القناة المُعطاة: يستخدم طلب التكرار الآلي الهجين (hybrid automatic repeat-request) خاصية تصحيح أخطاء ثابتة طالما تستطيع هذه الخاصية التعامل مع معدل الأخطاء، ولكن إذا أصبح معدل الأخطاء عالياً جدًا، يتم التحويل إلى طلب التكرار الآلي (Automatic Repeat Request)ARQ ، يستخدم التعديل والترميز التكيفي مجموعة من معدلات خاصية تصحيح الخطأ، ويضيف المزيد منها للحزمة عندما تكون معدلات الخطأ أعلى في القناة، أو يتخلص منها عند عدم الحاجة إليها.
أنواع خاصية تصحيح الخطأ[عدل]
تتمثل الفئتان الأساسيتان من رموز خاصية تصحيح الخطأ في التالي: فئة رمز القالب (block code) الرمز التحويلي (convolutional code).
- تعمل فئة رموز القوالب على قوالب (حزم) ثابتة الحجم من وحدات المعلومات أو الرموز (symbols) التي تم تحديد حجمها مسبقًا. يمكن أن يتم حل رموز القوالب العملية في الوقت المتعدد الحدود (polynomial time) إلى طول قوالبها.
- تعمل الرموز التحويلية على تيارات وحدات المعلومات أو الرموز ذات الطول الثابت لا تتغير. ويتم فكها غالبًا بواسطة خوارزمية فيتربي، ويمكن أيضًا استخدام خوارزميات أخرى أحيانًا. حيث أن خوارزمية فيتربي لفك الرموز تعطي الكفاءة الأفضل والأقرب لفك الرموز وتزيد من طول الرمز التحويلي الثابت، ولكن بتكلفة الوقت الأسي المتزايد. يمكن تحويل الرمز التحويلي إلى رمز قالب عن طريق "tail-biting"، إذا كان هناك رغبة في ذلك.
توجد أنواع كثيرة لرمز القالب، ولكن الرمز الأكثر ملاحظةً بين الأنواع الكلاسيكية هو مصحح الخطأ ريد-سولومون (Reed-Solomon error correction) بسبب كثرة استخدامه في القرص المضغوط، وفي الدي في دي (DVD)، وفي مشغل القرص الصلب. ومن الأمثلة الأخرى لرموز القوالب، رمز جولاي (Golay)، رمز بي سي إتش (BCH code)، التكافؤ متعدد الأبعاد (Multidimensional parity)، ورمز هامينج.
يستخدم رمز هامينج إي سي سي (Hamming ECC) عادةً لتصحيح أخطاء بطاقة الذاكرة ناند (NAND flash).[2] ويوفر ذلك مصحح خطأ وحدة معلومات واحدة ومكتشف خطأ وحدتي معلومات. تناسب رموز هامينج خلية المستوى الواحد الموثوقة بشكل أكبر (SLC) NAND فقط. تتطلب الخلية متعددة المستويات (MLC) الأكثر كثافة في ذاكرة ناند رمزًا أقوى لتصحيح الأخطاء المتعددة مثل البي سي إتش أو الريد سولومون[3][محل شك].
عادةً ما يتم تنفيذ رموز القوالب الكلاسيكية باستخدام خوارزميات القرار الصعب ،[4] مما يعني أنه يتم اتخاذ قرار صعب لكل إشارة إدخال وإخراج وهذا القرار هو الحيرة بين الإرسال إلى وحدة معلومات واحدة أو إلى لا شيء. والعكس أن خوارزميات القرار السهل مثل الإشارات القياسية لعملية مفكك الرمز فيتربي، والتي تسمح بمعدل تصحيح أخطاء أعلى من تفكيك الرمز عن طريق خوارزميات القرار الصعب.
تطبق جميع رموز القوالب الكلاسيكية تقريبًا الخصائص الجبرية الخاصة بمجال يسمى المجال المحدود.
في الطبقات العليا، يكون حل خاصية تصحيح الخطأ لمشكلة مستويات بث أجهزة المحمول هو رمز الرابتور (Raptor code) أو الرابتور كيو (RaptorQ).
غالبًا ما تصحح خاصية تصحيح الخطأ، انعكاسات وحدة المعلومات فقط وليس إدراجها أو مسحها. وفي هذا الضبط، تكون مسافة هامينج هي الطريقة المناسبة لقياس معدل خطأ وحدة المعلومات. تم تصميم بعض خواص تصحيح الخطأ لتقوم بتصحيح إدراج وحدة المعلومات ومسحها، مثل رموز ماركر (Marker Codes) ورموز ووترمارك (Watermark Codes). وفي حالة استخدام مثل هذه الرموز تكون مسافة ليفينشتاين (Levenshtein distance) هي الأكثر مناسبةً لقياس معدل خطأ وحدة المعلومات.[5]
تستخدم رموز خاصية تصحيح الخطأ المتصلة لتحسين الأداء[عدل]
غالبًا ما يتم الجمع بين رموز القوالب الكلاسيكية (الجبرية) والرموز التحويلية في خطط ترميز متصلة، يقوم فيها الرمز التحويلي القصير ذو الطول الثابت ومفكك فيتربي، بأغلب الوظائف، ويتخلص فيها رمز القالب (عادةً ريد-سولومون) ذو الحجم الرمزي وطول القالب الأكبر، من أي أخطاء قام بها مفكك الرمز التحويلي. عملية واحدة لهذه العائلة من رموز تصحيح الخطأ يمكن أن تخلف معدلات أخطاء منخفضة جدًا، ولكن يُنصح بتكرار العملية في حالة الإرسال على المدى البعيد (مثل: عمق المسافة).
الرموز المتصلة مناسبة للتطبيق العملي في الأقمار الصناعية واتصالات المسافات البعيدة حيث استخدمت رحلة 2 هذه التقنية أول مرة عام 1986 أثناء الذهاب إلى كوكب أورانوس. استخدمت سفينة جاليليو (Galileo) الفضائية الرموز المتصلة وقامت بتكرار العملية لتقوم بتعويض معدلات الخطأ العالية جدًا بسبب ظروف انعدام الهواء.
مراجعة التكافؤ قليل الكثافة (LDPC)[عدل]
تُعتبر رموزمراجعة التكافؤ قليل الكثافة (LDPC) مجموعة من رموز القوالب الخطية عالية الكفاءة المُعاد اكتشافها. فهذه الرموز تستطيع أن تؤدي أداءً قريبًا من أداء حدود شانون (Shannon limit) قدرة القناة (الحد الأقصى نظريًا) باستخدام مفهوم تفكيك الرموز بالقرار السهل، في زمن خطي معين مناسب لطول القالب. يعتمد التنفيذ العملي بشدة على استخدام النظائر.
كان روبرت جي جالاجر (Robert G. Gallager) هو أول من قدم رموز مراجعة التكافؤ قليل الكثافة كأطروحة في رسالة الدكتوراه عام 1960، ولكن نظرًا للمجهود الكبير التي تتطلبه الأطروحة في مجال الحوسبة لتنفيذ مدخل الرموز ومفكك الرموز مقدمة رموز ريد-سولومون، فقد تم تجاهلها كثيرًا حتى فترة قريبة.
تُستخدم رموز مراجعة التكافؤ قليل الكثافة الآن في مستويات اتصال عالية السرعة كثيرة، مثل الجيل الثاني من الأقمار الصناعية للبث الرقمي للفيديو (DVB-S2) (بث رقمي للفيديو)، ووايماكس (المستوى IEEE 802.16e لاتصالات الموجات الكهرومغناطيسية القصيرة)، وشبكة اتصالات محلية لاسلكية عالية السرعة (LAN) (IEEE 802.11n)، و10GBase-T Ethernet (802.3an)، وG.hn/G.9960 (مستوى ITU-T للشبكة على خطوط القوة، خطوط التليفون، والكابل متحد المحور). خُصصت رموز مراجعة التكافؤ قليل الكثافة الأخرى لمعايير الاتصال اللاسلكية مثل الجيل الثالث من مشروع المشاركة (3GPP) (MBMS) (انظر رموز فاونتين (fountain codes)).
رموز توربو[عدل]
ترميز توربو هو نظام فك رموز يستخدم خوارزمية القرار السهل بالتكرار ويجمع بين اثنين أو أكثر من الرموز التحويلية البسيطة نسبيًا ومُرتِب لإنتاج رمز قالب يستطيع العمل خلال عدد من وحدات الديسبل من حدود شانون. يماثل أداء ترميز تربو الآن أداء رموز مراجعة التكافؤ قليل الكثافة سابقًا.
تعد سي دي إم أي 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))
الفك المحلي للرموز واختبارها[عدل]
أحيانًا تستدعي الضرورة فك رموز وحدات المعلومات مفردة من الرسالة فقط، أو التحقق مما إذا كانت الإشارة المستلمة تمثل كلمة مشفرة، دون النظر إلى الإشارة كاملةً. ويكون ذلك مهمًا في ضبط تدفق، حيث تكون الكلمات المشفرة أكبر من إمكانية فكها بالسرعة المعتادة، وتتمثل الحاجة في وحدات بت صغيرة من الرسالة. أصبحت هذه الرموز أيضًا أداة مهمة في نظرية التعقيدات الحسابية، في تصميم احتمالية مراجعة البرهان.
يقصدبالرموز القابلة للفك محليا رموز تصحيح الخطأ التي يمكن أن يتم فيها اكتشاف وحدات المعلومات المفردة في الرسالة عن طريق النظر فقط إلى عدد صغير (ثابت تقريبًا) من مواقع الكلمة المشفرة، حتى بعد تلف بعض مواقع الكلمة المشفرة. الرموز القابلة للاختبار محليًاهي رموز تصحيح الخطأ التي يمكن فيها اكتشاف ما إذا كانت الإشارة قريبة من الكلمة المشفرة بالنظر إلى عدد صغير من مواقع الإشارة فقط.
قائمة رموز تصحيح الخطأ[عدل]
رمز المسافة 2 (مُكتشف الخطأ الواحد) تكافؤ 3 (مُصحح الخطأ الواحد) التكرار الثلاثي القياسي 3 (مُصحح الخطأ الواحد) مقارب جدًا لهامينج هامينج(7,4) 4 (رموز هامينج بتكافؤ إضافي (SECDED)) هامينج ممتد 7 (مُصحح خطأ ثلاثي) يماثل رمز جولاي الثنائي 8 (TECFED) رمز جولاي الثنائي ممتد
- أكواد إيه إن (AN codes)
- كود بي سي إتش (BCH code)
- كود بيرجر
- كود الوزن الثابت
- الكود التحويلي
- كود المجموعة
- كود جولاي، الذي ينشق منه كود جولاي الثنائي الذي له أهمية عملية
- كود جوبا (Goppa code)، الذي يستخدم في McEliece cryptosystem
- كود هادامرد (Hadamard code)
- كود هاجلبارجر (Hagelbarger code)
- كود هامينج
- كود أساسه مربع اللاتينية للضجيج الملون (منتشر انتشاراً واسعًا في خطوط القوة)
- كود ليكسيكوجرافيك (Lexicographic code)
- الكود الطويل (Long code)
- كود مراجعة التكافؤ قليل الكثافة، ويُسمى أيضًا كود جالاجير (Gallager code)، وهو نسخة كود الرسم المتناثر (sparse graph code) الأصلية
- كود تحويل لوبي (LT code)، وهو الأفضل تقريبًا كود تصحيح خطأ ليس له معدل محو (كود فاونتين)
- كود الوزن الثابت (m of n codes)
- كود الإنترنت (Online code)، وهو الأفضل تقريبًا كود تصحيح خطأ ليس له معدل محو
- كود رابتور (Raptor code)، وهو الأفضل تقريبًا كود تصحيح خطأ ليس له معدل محو
- مصحح الخطأ ريد-سولومون
- كود ريد-مولر (Reed–Muller code)
- كود تراكم التكرار (Repeat-accumulate code)
- كود التكرار، مثل التكرار المعياري الثلاثي
- كود تورنادو (Tornado code)، وهو تقريبًا أفضل رموز تصحيح المحو، وهو مبشر لكود آخر وهو كود فاونتين
- كود توربو
- كود والش-هادامارد (Walsh–Hadamard code)
انظر أيضًا[عدل]
المراجع[عدل]
- ^ Charles Wang, Dean Sklar, Diana Johnson (Winter 2001/2002). "Forward Error-Correction Coding". Crosslink — The Aerospace Corporation magazine of advances in aerospace technology. The Aerospace Corporation. ج. 3 ع. 1. مؤرشف من الأصل في 2012-03-14.
How Forward Error-Correcting Codes Work
{{استشهاد بدورية محكمة}}: تحقق من التاريخ في:|تاريخ=(مساعدة) وروابط خارجية في|اقتباس= - ^ http://www.eetasia.com/ART_8800575062_499486_AN_7549c493.HTM "The Hamming algorithm is an industry-accepted method for error detection and correction in many SLC NAND flash-based applications." نسخة محفوظة 2016-08-21 على موقع واي باك مشين.
- ^ http://www.spansion.com/Support/Application%20Notes/Types_of_ECC_Used_on_Flash_AN.pdf "Both Reed-Solomon algorithm and BCH algorithm are common ECC choices for MLC NAND flash. ... Hamming based block codes are the most commonly used ECC for SLC.... both Reed-Solomon and BCH are able to handle multiple errors and are widely used on MLC flash." نسخة محفوظة 2016-06-14 على موقع واي باك مشين.
- ^ Baldi M., Chiaraluce F. (2008). "A Simple Scheme for Belief Propagation Decoding of BCH and RS Codes in Multimedia Transmissions". International Journal of Digital Multimedia Broadcasting. ج. 2008: 957846. DOI:10.1155/2008/957846. مؤرشف من الأصل في 2019-12-18.
{{استشهاد بدورية محكمة}}: صيانة الاستشهاد: دوي مجاني غير معلم (link) - ^ Shah، Gaurav؛ Molina، Andres؛ Blaze، Matt (2006). "Keyboards and covert channels" (PDF). Proceedings of the 15th conference on USENIX Security Symposium. مؤرشف من الأصل (PDF) في 2019-07-09.
