رمز الإعصار

في نظرية الترميز ، تُعدّ رموز تورنادو فئة من رموز المحو التي تدعم تصحيح الأخطاء . تتطلب رموز تورنادو عددًا ثابتًا من الكتل الزائدة (C) مقارنةً برموز ريد-سولومون الأكثر كفاءة في استخدام البيانات ، ولكنها أسرع بكثير في التوليد وقادرة على تصحيح الأخطاء بشكل أسرع. تُعدّ تطبيقات رموز تورنادو البرمجية أسرع بحوالي 100 مرة في حالة الأطوال الصغيرة، وحوالي 10000 مرة في حالة الأطوال الأكبر، مقارنةً برموز ريد-سولومون. ^{[ 1 ]} منذ ظهور رموز تورنادو، ظهرت العديد من رموز المحو المشابهة، وأبرزها رموز أونلاين ، ورموز LT، ورموز رابتور .

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

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

يُحدد المستخدم عدد كتل الاستعادة. ثم يُحدد عدد المستويات وعدد الكتل في كل مستوى. ويُحدد عدد الكتل في كل مستوى بمعامل B أقل من واحد. فإذا كان عدد كتل الإدخال N، فإن مستوى الاستعادة الأول يحتوي على B*N كتلة، والثاني على B×B×N، والثالث على B×B×B×N، وهكذا.

تستخدم جميع مستويات الاسترداد، باستثناء المستوى الأخير، خوارزمية LDPC، التي تعمل بتقنية XOR (الجمع الحصري). تعمل XOR على القيم الثنائية، 1 و0. تكون نتيجة عملية XOR B هي 1 إذا كانت قيمتا A وB مختلفتين، و0 إذا كانتا متطابقتين. إذا عُلمت نتيجة (A XOR B) مع A، يمكنك تحديد قيمة B. (A XOR B XOR A = B). وبالمثل، إذا عُلمت نتيجة (A XOR B) مع B، يمكنك تحديد قيمة A. وينطبق هذا على قيم متعددة، فإذا عُلمت نتيجة (A XOR B XOR C XOR D) مع أي ثلاث قيم، يمكن استرداد القيمة المفقودة.

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

بما أن عملية xor هي عملية سريعة، وكتل الاسترداد هي عملية xor لمجموعة فرعية فقط من الكتل الموجودة في المدخلات (أو على مستوى استرداد أقل)، فإنه يمكن إنشاء كتل الاسترداد بسرعة.

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

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

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

كانت رموز الأعاصير مسجلة ببراءات اختراع داخل الولايات المتحدة الأمريكية. ^{[ 2 ]} تصف براءتا الاختراع US6163870 A (المقدمة في 6 نوفمبر 1997) وUS 6081909 A (المقدمة في 6 نوفمبر 1997) رموز الأعاصير، وقد انتهت صلاحيتهما في 6 نوفمبر 2017. كما تشير براءتا الاختراع US6307487 B1 (المقدمة في 5 فبراير 1999) وUS6320520 B1 (المقدمة في 17 سبتمبر 1999) إلى رموز الأعاصير، وقد انتهت صلاحيتهما في 5 فبراير 2019 و17 سبتمبر 2019 على التوالي.

ابتكر مايكل لوبي رموز تورنادو. ^{[ 3 ] [ 4 ]}

• رمز المحو
• رمز رابتور

• بايرز، جيه دبليو، ولوبي، إم، وميتزنماخر، إم، وريج، إيه (أكتوبر 1998). "نهج النافورة الرقمية لتوزيع البيانات الضخمة بشكل موثوق". وقائع مؤتمر SIGCOMM '98 . مؤتمر ACM SIGCOMM '98 حول التطبيقات والتقنيات والهياكل والبروتوكولات الخاصة باتصالات الحاسوب. الصفحات 56-67 . doi : 10.1145/285237.285258 . 
• لوبي م ، ميتزنماخر م ، شوكرولاهي أ ، سبيلمان د ، ستيمان ف (1997). "رموز عملية مقاومة للفقد". وقائع الندوة السنوية التاسعة والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '97 . الصفحات 150-159 . doi : 10.1145/258533.258573 . ISBN  0-89791-888-6.
• لوبي م ، ميتزنماخر م ، شوكرولاهي أ (1998). "تحليل العمليات العشوائية عبر تقييم شجرة أن-أو". وقائع الندوة السنوية التاسعة لجمعية آلات الحوسبة وجمعية الرياضيات الصناعية والتطبيقية حول الخوارزميات المنفصلة : 364-373 .
• ميتزنماخر، م. (2004). "النوافير الرقمية: دراسة استقصائية ونظرة مستقبلية". مهندس التصنيع . ص 271-276 . doi : 10.1109/ITW.2004.1405313 . ISBN  0-7803-8720-1.

وصف سهل القراءة من جامعة كارنيجي ميلون (PostScript)وآخر من لوبي في المعهد الدولي لعلوم الحاسوب (PostScript).