شفرة النافورة

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

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

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

التطبيقات

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

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

ومن التطبيقات الأخرى استخدام ARQ الهجين في سيناريوهات البث المتعدد الموثوقة : يمكن أن تكون معلومات التكافؤ التي يطلبها جهاز الاستقبال مفيدة لجميع أجهزة الاستقبال في مجموعة البث المتعدد.

في المعايير

تُعدّ رموز رابتور حاليًا أكثر رموز النافورة كفاءةً، ^{[ 2 ]} إذ تتميز بخوارزميات تشفير وفك تشفير خطية عالية الكفاءة، ولا تتطلب سوى عدد قليل وثابت من عمليات XOR لكل رمز مُولّد، سواءً للتشفير أو فك التشفير. ^{[ 3 ]} يحدد معيار IETF RFC 5053 بالتفصيل رمز رابتور منهجيًا ، والذي تم اعتماده في العديد من المعايير خارج نطاق IETF، مثل معيار 3GPP MBMS لتوزيع ملفات البث وخدمات البث المباشر، ومعيار DVB-H IPDC لتقديم خدمات IP عبر شبكات DVB ، ومعيار DVB-IPTV لتقديم خدمات التلفزيون التجاري عبر شبكة IP. يمكن استخدام هذا الرمز مع ما يصل إلى 8192 رمزًا مصدرًا في كتلة مصدر واحدة، وما يصل إلى 65536 رمزًا مُشفّرًا مُولّدًا لكتلة مصدر واحدة. يبلغ متوسط الحمل الزائد النسبي للاستقبال في هذا الكود 0.2% عند تطبيقه على كتل مصدرية تحتوي على 1000 رمز مصدري، ويقل هذا الحمل عن 2% باحتمالية 99.9999%. ^{[ 4 ]} يُعرَّف الحمل الزائد النسبي للاستقبال بأنه بيانات التشفير الإضافية المطلوبة لاستعادة البيانات المصدرية الأصلية، ويُقاس كنسبة مئوية من حجم البيانات المصدرية. على سبيل المثال، إذا كان الحمل الزائد النسبي للاستقبال 0.2%، فهذا يعني أنه يمكن استعادة بيانات مصدرية بحجم 1 ميجابايت من 1.002 ميجابايت من بيانات التشفير.

تم تحديد رمز RaptorQ، وهو رمز Raptor أكثر تطورًا يتميز بمرونة أكبر واستهلاك أقل للبيانات، في معيار IETF RFC 6330. يمكن استخدام رمز RaptorQ مع ما يصل إلى 56,403 رمزًا مصدريًا في كتلة مصدرية، وما يصل إلى 16,777,216 رمزًا مشفرًا لكل كتلة مصدرية. يستطيع هذا الرمز استعادة كتلة مصدرية من أي مجموعة من الرموز المشفرة تساوي عدد الرموز المصدرية في الكتلة المصدرية باحتمالية عالية، وفي حالات نادرة من مجموعة رموز مشفرة تزيد قليلًا عن عدد الرموز المصدرية في الكتلة المصدرية. يُعد رمز RaptorQ جزءًا لا يتجزأ من عملية إنشاء ROUTE المحددة في معيار ATSC A-331 (ATSC 3.0).

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

تُستخدم رموز المحو في تطبيقات تخزين البيانات نظرًا لما توفره من توفير كبير في عدد وحدات التخزين لتحقيق مستوى معين من التكرار والموثوقية. قد تختلف متطلبات تصميم رموز المحو لتخزين البيانات، وخاصةً لتطبيقات التخزين الموزعة، اختلافًا كبيرًا عن سيناريوهات الاتصال أو تدفق البيانات. أحد متطلبات الترميز لأنظمة تخزين البيانات هو الشكل المنهجي، أي أن رموز الرسالة الأصلية تُعد جزءًا من الرموز المُرمّزة. يُمكّن الشكل المنهجي من قراءة رموز الرسالة دون فك تشفيرها من وحدة التخزين. بالإضافة إلى ذلك، نظرًا لأن عرض النطاق الترددي وحمل الاتصال بين عُقد التخزين قد يُمثلان عنق زجاجة، فإن الرموز التي تسمح بأقل قدر من الاتصال تُعد مفيدة للغاية، خاصةً عند تعطل إحدى العُقد والحاجة إلى إعادة بناء النظام لتحقيق مستوى التكرار الأولي. في هذا الصدد، يُتوقع أن تسمح رموز النافورة بعملية إصلاح فعالة في حالة حدوث عطل: فعند فقدان رمز مُرمّز واحد، لا ينبغي أن يتطلب الأمر الكثير من الاتصال والحساب بين الرموز المُرمّزة الأخرى لاستعادة الرمز المفقود. في الواقع، قد يكون زمن استجابة الإصلاح في بعض الأحيان أكثر أهمية من توفير مساحة التخزين. من المتوقع أن تُعالج رموز النوافير القابلة للإصلاح ^[⁵^] أهداف تصميم رموز النوافير لأنظمة التخزين. يمكن الاطلاع على دراسة تفصيلية حول رموز النوافير وتطبيقاتها في ^[⁶^{] .}

تم اقتراح نهج مختلف للتخزين الموزع باستخدام رموز النافورة في نظام التخزين السحابي السائل. ^{[ 7 ]}^{[ 8 ]} يعتمد نظام التخزين السحابي السائل على استخدام رمز محو كبير مثل رمز RaptorQ المحدد في IETF RFC 6330 (والذي يوفر حماية أفضل بكثير للبيانات مقارنة بالأنظمة الأخرى)، واستخدام عملية إصلاح في الخلفية (مما يقلل بشكل كبير من متطلبات عرض النطاق الترددي للإصلاح مقارنة بالأنظمة الأخرى)، واستخدام تنظيم بيانات متدفقة (مما يسمح بالوصول السريع إلى البيانات حتى عندما لا تكون جميع الرموز المشفرة متاحة).

انظر أيضاً

ملحوظات

↑ ج. بايرز، م. لوبي ، م. ميتزنماخر ، أ. ريج (1998). "نهج النافورة الرقمية للتوزيع الموثوق للبيانات الضخمة" (PDF) .{{cite web}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
↑ "تقنية كوالكوم رابتور - تصحيح الأخطاء الأمامية" . 30 مايو 2014. مؤرشف من الأصل بتاريخ 29 ديسمبر 2010. تم الاطلاع عليه بتاريخ 7 يونيو 2011 .
↑ ( شوكرولاهي 2006 )
↑ تي. ستوكهامر، أ. شوكرولاهي، م. واتسون، م. لوبي، تي. غاسيبا (مارس 2008). فورث، ب.؛ أحسن، س. (محرران). "تصحيح الأخطاء الأمامية لطبقة التطبيق في البث متعدد الوسائط عبر الهاتف المحمول". دليل البث عبر الهاتف المحمول: DVB-H، DMB، ISDB-T وMedia FLO . مطبعة CRC .{{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
↑ أستيريس، ميغاستينيس؛ ديماكيس، ألكسندروس ج. (2012). "رموز النافورة القابلة للإصلاح". مجلة IEEE للمجالات المختارة في الاتصالات . 32 (5): 1037-1047 . arXiv : 1401.0734 . doi : 10.1109/JSAC.2014.140522 . S2CID 1300984 .
↑ أرسلان، سويب س. (2014). "التكرار التدريجي، ورموز النافورة، والمواضيع المتقدمة". arXiv : 1402.6016 [ cs.IT ].
↑ لوبي، مايكل؛ بادوفاني، روبرتو؛ ريتشاردسون، توماس جيه؛ ميندر، لورنز؛ أغاروال، بوجا (2019). "تخزين السحابة السائلة". معاملات ACM في التخزين . 15 : 1-49 . arXiv : 1705.07983 . doi : 10.1145/3281276 . S2CID 738764 .
^ لوبي، م. بادوفاني، ر.؛ ريتشاردسون، T.؛ ميندر، ل.؛ أغاروال، ب. (2017). “التخزين السحابي السائل”. أرخايف : 1705.07983v1 [ cs.DC ].

مراجع

أمين شوكرولاهي ومايكل لوبي (2011). "شفرات رابتور". أسس واتجاهات في الاتصالات ونظرية المعلومات . 6 ( 3-4 ). دار نشر ناو: 213-322 . doi : 10.1561/0100000060 . S2CID 1731099 .
لوبي، مايكل (2002). "رموز LT". وقائع الندوة السنوية الثالثة والأربعين لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، 2002. الصفحات 271-282 . doi : 10.1109/sfcs.2002.1181950 . ISBN 0-7695-1822-2. S2CID 1861068 .
أ. شوكرولاهي (2006)، "رموز رابتور"، معاملات IEEE في نظرية المعلومات ، 52 (6): 2551-2567 ، Bibcode : 2006ITIT...52.2551S ، doi : 10.1109/tit.2006.874390 ، S2CID 61814971 .
ب. مايمونكوف (نوفمبر 2002). "الرموز الإلكترونية" (ملف PDF) . (تقرير فني) .
ديفيد جيه سي ماكاي (2003). نظرية المعلومات، والاستدلال، وخوارزميات التعلم . مطبعة جامعة كامبريدج. رمز Bibcode : 2003itil.book.....M . ISBN 0-521-64298-1.
م. لوبي ، أ. شوكرولاهي ، م. واتسون، ت. ستوكهامر (أكتوبر 2007)، مخطط تصحيح الأخطاء الأمامية لـ Raptor لتسليم الكائنات ، RFC 5053 {{citation}}: CS1 maint: multiple names: authors list ( link ) .
م. لوبي ، أ. شوكرولاهي ، م. واتسون، ت. ستوكهامر، ل. ميندر (مايو 2011)، مخطط تصحيح الأخطاء الأمامية RaptorQ لتسليم الكائنات ، RFC 6330 {{citation}}: CS1 maint: multiple names: authors list ( link ) .

[1] ج. بايرز، م. لوبي ، م. ميتزنماخر ، أ. ريج (1998). "نهج النافورة الرقمية للتوزيع الموثوق للبيانات الضخمة" (PDF) .{{cite web}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

[2] "تقنية كوالكوم رابتور - تصحيح الأخطاء الأمامية" . 30 مايو 2014. مؤرشف من الأصل بتاريخ 29 ديسمبر 2010. تم الاطلاع عليه بتاريخ 7 يونيو 2011 .

[3] ( شوكرولاهي 2006 )

[4] تي. ستوكهامر، أ. شوكرولاهي، م. واتسون، م. لوبي، تي. غاسيبا (مارس 2008). فورث، ب.؛ أحسن، س. (محرران). "تصحيح الأخطاء الأمامية لطبقة التطبيق في البث متعدد الوسائط عبر الهاتف المحمول". دليل البث عبر الهاتف المحمول: DVB-H، DMB، ISDB-T وMedia FLO . مطبعة CRC .{{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

[5] أستيريس، ميغاستينيس؛ ديماكيس، ألكسندروس ج. (2012). "رموز النافورة القابلة للإصلاح". مجلة IEEE للمجالات المختارة في الاتصالات . 32 (5): 1037-1047 . arXiv : 1401.0734 . doi : 10.1109/JSAC.2014.140522 . S2CID 1300984 .

[6] أرسلان، سويب س. (2014). "التكرار التدريجي، ورموز النافورة، والمواضيع المتقدمة". arXiv : 1402.6016 [ cs.IT ].

[7] لوبي، مايكل؛ بادوفاني، روبرتو؛ ريتشاردسون، توماس جيه؛ ميندر، لورنز؛ أغاروال، بوجا (2019). "تخزين السحابة السائلة". معاملات ACM في التخزين . 15 : 1-49 . arXiv : 1705.07983 . doi : 10.1145/3281276 . S2CID 738764 .

[8] لوبي، م. بادوفاني، ر.؛ ريتشاردسون، T.؛ ميندر، ل.؛ أغاروال، ب. (2017). “التخزين السحابي السائل”. أرخايف : 1705.07983v1 [ cs.DC ].

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[

[

[ 7 ]

[ 8 ]