رمز رابتور

📅 آخر تحديث: ٣٠ يوليو ٢٠٢٦
✍️ نُشر في: ٣٠ يوليو ٢٠٢٦
الموسوعة الحرة

في علم الحاسوب ، تُعدّ رموز رابتور ( rap id tor nado ؛ [ 1 ] انظر رموز تورنادو ) أول فئة معروفة من رموز النافورة ذات التشفير وفك التشفير الخطي. ابتكرها أمين شوكرولاهي في عامي 2000/2001، ونُشرت لأول مرة في عام 2004 كملخص موسع. تُمثل رموز رابتور تحسينًا نظريًا وعمليًا هامًا لرموز LT ، التي كانت أول فئة عملية من رموز النافورة .

تُشفّر رموز رابتور، كما هو الحال مع رموز النافورة عمومًا، كتلة بيانات مصدرية مُعطاة تتكون من عدد k من رموز المصدر متساوية الحجم، إلى سلسلة غير محدودة من رموز التشفير، بحيث يسمح استقبال أي k رمز تشفير أو أكثر باستعادة كتلة البيانات المصدرية باحتمالية غير صفرية. تزداد احتمالية استعادة كتلة البيانات المصدرية مع ازدياد عدد رموز التشفير المُستلمة عن k ، لتصبح قريبة جدًا من 1 بمجرد أن يصبح عدد رموز التشفير المُستلمة أكبر بقليل جدًا من k . على سبيل المثال، مع أحدث جيل من رموز رابتور، وهي رموز رابتور كيو، تقل احتمالية فشل فك التشفير عند استلام k رمز تشفير عن 1%، وتقل احتمالية فشل فك التشفير عند استلام k+2 رمز تشفير عن واحد في المليون. يمكن أن يكون حجم الرمز أي حجم، من بايت واحد إلى مئات أو آلاف البايتات.

قد تكون رموز رابتور منهجية أو غير منهجية . في الحالة المنهجية، تُضمَّن رموز كتلة المصدر الأصلية، أي رموز المصدر، ضمن مجموعة رموز التشفير. من أمثلة رموز رابتور المنهجية استخدامها في مشروع شراكة الجيل الثالث في البث اللاسلكي الخلوي المتنقل والبث المتعدد، وكذلك في معايير DVB-H لبث بيانات IP إلى الأجهزة المحمولة. كما تم تعريف رموز رابتور المستخدمة في هذه المعايير في معيار IETF RFC 5053 . 

تُعدّ الرموز الإلكترونية مثالاً على رمز النافورة غير المنهجي.

رمز رابتور كيو

يُعدّ كود RaptorQ، المُعرّف في معيار IETF RFC 6330 ، الإصدار الأكثر تطوراً من Raptor . وهو كود منهجي، يُمكن تنفيذه بطريقة تُحقق أداءً خطياً في التشفير وفك التشفير، ويتمتع بخصائص استعادة شبه مثالية، ويدعم ما يصل إلى 56403 رمزاً مصدرياً، كما يُمكنه دعم عدد غير محدود عملياً من رموز التشفير. 

يُحدد رمز RaptorQ، المُعرّف في معيار IETF RFC 6330، كجزء من معيار الجيل التالي للتلفزيون ( ATSC 3.0 ) لتمكين بث فيديو عالي الجودة (تلفزيون متنقل موثوق) ونقل ملفات البث بكفاءة وموثوقية (بث البيانات). وبالتحديد، يُحدد رمز RaptorQ في A/331 ضمن معيار ATSC 3.0. [ 2 ] راجع قائمة معايير ATSC للاطلاع على قائمة بأجزاء معيار ATSC 3.0. يتجاوز الجيل التالي للتلفزيون (ATSC 3.0) التلفزيون التقليدي ليُوفر إنترنت البث الذي يُتيح خدمات نقل البيانات العامة.

ملخص

تتكون رموز رابتور من خلال دمج رمزين.

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

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

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

في حالة رموز رابتور غير المنهجية، يتم استخدام بيانات المصدر المراد ترميزها كمدخل لمرحلة ما قبل الترميز.

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

فك التشفير

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

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

التعقيد الحسابي

تتطلب رموز رابتور وقتًا قدره O(حجم الرمز) لتوليد رمز ترميز من كتلة مصدر، وتتطلب وقتًا قدره O(حجم كتلة المصدر) لاستعادة كتلة مصدر من k رمز ترميز على الأقل.

احتمالية الاسترداد والتكاليف العامة

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

يحتوي كود RaptorQ المحدد في IETF RFC 6330 على المفاضلة التالية بين احتمالية الاسترداد وتكاليف الاسترداد:

  • احتمالية استعادة أكبر من 99% مع تكلفة إضافية قدرها 0 رمز (الاستعادة من k رمز تشفير مستلم).
  • احتمالية استرداد أكبر من 99.99% مع زيادة في الحمل بمقدار رمز واحد (الاسترداد من k+1 رمز ترميز تم استلامه).
  • احتمالية استرداد أكبر من 99.9999% مع زيادة في الحمل بمقدار رمزين (الاسترداد من k+2 رمز تشفير تم استلامها).

تنطبق هذه البيانات على كامل نطاق قيم k المدعومة في معيار IETF RFC 6330، أي k = 1، ...، 56403. راجع معيار IETF RFC 6330 لمزيد من التفاصيل. [ 3 ]

أصدرت شركة كوالكوم بيانًا بشأن حقوق الملكية الفكرية لبرنامج رابتور المحدد في معيار IETF RFC 5053، وبيانًا آخر بشأن حقوق الملكية الفكرية لبرنامج رابتور كيو الأكثر تطورًا المحدد في معيار IETF RFC 6330. ويعكس هذان البيانان التزام كوالكوم بترخيص معيار MPEG DASH . وقد اعتمدت مجموعة واسعة من الشركات، بما في ذلك الشركات الأعضاء في منتدى صناعة DASH، معيار MPEG DASH.

انظر أيضاً

ملحوظات

  1. ^ أمين شكراللهي (31 يناير 2011). تطوير رموز رابتور (الكلام). تمت الدعوة للحديث في Kungliga Tekniska högskolan . تم الاسترجاع 24 فبراير 2012 .
  2. ↑ معيار مرشح ATSC: الإشارة، والتسليم، والمزامنة، والحماية من الأخطاء (A/331) (PDF) (تقرير). لجنة أنظمة التلفزيون المتقدمة. 22 مارس 2017. ATSC S33-174r6.
  3. ↑ لوبي م، شوكرولاهي أ، واتسون م، ستوكهامر ت، ميندر ل (أغسطس 2011). طلب ​​تعليقات: 6330. مخطط تصحيح الأخطاء الأمامية لـ RaptorQ لتسليم الكائنات (تقرير). ISSN 2070-1721 . 

مراجع

للمزيد من القراءة