كود تحويل Luby

الموسوعة الحرة

في علوم الحاسوب ، تُعدّ رموز تحويل لوبي ( رموز LT ) أول فئة من رموز النافورة العملية التي تُعتبر رموز تصحيح محو شبه مثالية . ابتكرها مايكل لوبي عام 1998 ونُشرت عام 2002. [ 1 ] ومثل بعض رموز النافورة الأخرى ، تعتمد رموز LT على الرسوم البيانية الثنائية المتفرقة لموازنة عبء الاستقبال مع سرعة التشفير وفك التشفير. وتكمن السمة المميزة لرموز LT في استخدامها خوارزمية بسيطة للغاية تعتمد على عملية "أو" الحصرية (⊕{\displaystyle \oplus }) لترميز الرسالة وفك ترميزها. [ 2 ]

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

الجيل التالي من رموز LT هو رموز Raptor (انظر على سبيل المثال IETF RFC 5053 أو IETF RFC 6330)، والتي تتميز بتشفير وفك تشفير خطي. تعتمد رموز Raptor أساسًا على رموز LT، أي أن تشفيرها يستخدم مرحلتين، حيث تكون المرحلة الثانية تشفيرًا خطيًا. وبالمثل، يعتمد فك تشفير رموز Raptor بشكل أساسي على فك التشفير الخطي، ولكن يتم دمج فك التشفير الخطي مع تقنيات فك تشفير أكثر تطورًا. يتميز رمز RaptorQ المحدد في IETF RFC 6330، وهو أكثر رموز Fountain تطورًا، باحتمالات وأداء فك تشفير فائقين مقارنةً باستخدام رمز LT فقط.

المزايا

تعتمد الطريقة التقليدية لنقل البيانات عبر قناة المسح على الاتصال المستمر ثنائي الاتجاه.

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

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

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

كما ذكر أعلاه، فإن كود RaptorQ المحدد في IETF RFC 6330 يتفوق على كود LT عمليًا.

ترميز LT

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

  • يتم اختيار درجة d ، 1  ≤ d ≤ n ، للحزمة التالية بشكل عشوائي.   
  • يتم اختيار عدد محدد من الكتل من الرسالة بشكل عشوائي.
  • إذا كانت M i هي الكتلة رقم i من الرسالة، فسيتم حساب جزء البيانات من الحزمة التالية على النحو التالي
مأنا1⊕مأنا2⊕⋯⊕مأناد{\displaystyle M_{i_{1}}\oplus M_{i_{2}}\oplus \cdots \oplus M_{i_{d}}\,}
حيث { i 1 , i 2 , ..., i d } هي المؤشرات المختارة عشوائياً للكتل d المضمنة في هذه الحزمة.   
  • يتم إلحاق بادئة بالحزمة المشفرة، تحدد عدد الكتل n الموجودة في الرسالة، وعدد الكتل d التي تم إدخالها باستخدام عملية XOR في جزء البيانات من هذه الحزمة، وقائمة المؤشرات { i 1 , i 2 , ..., i d }.   
  • وأخيرًا، يتم تطبيق شكل من أشكال التعليمات البرمجية للكشف عن الأخطاء (ربما يكون بسيطًا مثل فحص التكرار الدوري ) على الحزمة، ثم يتم إرسال الحزمة.

تستمر هذه العملية حتى يشير جهاز الاستقبال إلى أنه قد تم استلام الرسالة وفك تشفيرها بنجاح.

فك تشفير LT

تستخدم عملية فك التشفير عملية " أو الحصرية " لاسترداد الرسالة المشفرة.

  • إذا لم تكن الحزمة الحالية نظيفة، أو إذا كانت تكرر حزمة تمت معالجتها بالفعل، فسيتم تجاهل الحزمة الحالية.
  • إذا كانت الحزمة المستلمة بشكل نظيف من الدرجة d  >  1، فسيتم معالجتها أولاً مقابل جميع الكتل التي تم فك تشفيرها بالكامل في منطقة انتظار الرسائل (كما هو موضح بشكل كامل في الخطوة التالية)، ثم يتم تخزينها في منطقة تخزين مؤقت إذا كانت درجتها المختزلة أكبر من 1.
  • عند استلام حزمة بيانات جديدة ونظيفة من الدرجة d  =  1 (الكتلة Mi ) (أو عند انخفاض درجة الحزمة الحالية إلى 1 في الخطوة السابقة)، تُنقل إلى منطقة انتظار الرسائل، ثم تُطابق مع جميع الحزم من الدرجة d  >  1 الموجودة في المخزن المؤقت. تُدمج هذه الحزمة باستخدام عملية XOR مع جزء البيانات لأي حزمة مخزنة مؤقتًا تم ترميزها باستخدام Mi ، وتُنقص درجة تلك الحزمة المطابقة، وتُعدّل قائمة المؤشرات لتلك الحزمة لتعكس تطبيق Mi.
  • عندما تقوم هذه العملية بفك قفل كتلة من الدرجة d  =  2 في المخزن المؤقت، يتم تقليل تلك الكتلة إلى الدرجة 1 ويتم نقلها بدورها إلى منطقة انتظار الرسائل، ثم تتم معالجتها مقابل الحزم المتبقية في المخزن المؤقت.
  • عندما يتم نقل جميع كتل الرسالة n إلى منطقة انتظار الرسائل، يقوم جهاز الاستقبال بإرسال إشارة إلى جهاز الإرسال تفيد بأنه تم فك تشفير الرسالة بنجاح.

تنجح عملية فك التشفير هذه لأن أ ⊕{\displaystyle \oplus } A  =  0 لأي سلسلة بتات A. بعد دمج d − 1 كتلة مميزة باستخدام عملية XOR في حزمة من الدرجة d ، فإن المحتوى الأصلي غير المشفر للكتلة غير المطابقة هو كل ما يتبقى. بالرموز لدينا  

(مأنا1⊕⋯⊕مأناد)⊕(مأنا1⊕⋯⊕مأناك-1⊕مأناك+1⊕⋯⊕مأناد)=مأنا1⊕مأنا1⊕⋯⊕مأناك-1⊕مأناك-1⊕مأناك⊕مأناك+1⊕مأناك+1⊕⋯⊕مأناد⊕مأناد=0⊕⋯⊕0⊕مأناك⊕0⊕⋯⊕0=مأناك\displaystyle \begin{aligned}\qquad (M_{i_{1}}\oplus \dots \oplus M_{i_{d}})\oplus (M_{i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}})\\&=M_{i_{1}}\oplus M_{i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k-1}}\oplus M_{i_{k}}\oplus M_{i_{k+1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}}\oplus M_{i_{d}}\\&=0\oplus \dots \oplus 0\oplus M_{i_{k}}\oplus 0\oplus \dots \oplus 0\\&=M_{i_{k}}\,\end{aligned}}}

الاختلافات

توجد عدة اختلافات ممكنة لعمليات التشفير وفك التشفير الموضحة أعلاه. على سبيل المثال، بدلاً من إضافة قائمة بمؤشرات كتل الرسائل الفعلية { i 1 , i 2 , ..., i d } إلى بداية كل حزمة، قد يرسل المُشفِّر ببساطة "مفتاحًا" قصيرًا يُستخدم كبذرة لمولد الأرقام العشوائية الزائفة (PRNG) أو جدول الفهارس المستخدم لإنشاء قائمة المؤشرات. وبما أن المُستقبِل المُجهز بنفس مولد الأرقام العشوائية أو جدول الفهارس يمكنه إعادة إنشاء قائمة المؤشرات "العشوائية" من هذه البذرة بشكل موثوق، يمكن إتمام عملية فك التشفير بنجاح. بدلاً من ذلك، من خلال دمج رمز LT بسيط ذي درجة متوسطة منخفضة مع رمز قوي لتصحيح الأخطاء، يمكن إنشاء رمز رابتور يتفوق عمليًا على رمز LT المُحسَّن. [ 3 ]   

تحسين رموز LT

يوجد مُعامل واحد فقط يُمكن استخدامه لتحسين ترميز LT المباشر: دالة توزيع الدرجة (الموصوفة بأنها مُولِّد أرقام شبه عشوائية للدرجة d في قسم ترميز LT أعلاه). عمليًا، تُؤخذ الأرقام "العشوائية" الأخرى (قائمة المؤشرات { i 1 , i 2 , ..., i d } ) دائمًا من توزيع منتظم على [0, n )، حيث n هو عدد الكتل التي قُسِّمت إليها الرسالة. [ 4 ]      

ناقش لوبي نفسه [ 1 ] " توزيع السوليتون المثالي " المحدد بواسطة

P{د=1}=1نP{د=ك}=1ك(ك-1)(ك=2،3،...،ن).{\displaystyle {\begin{aligned}\mathrm {P} \{d=1\}&={\frac {1}{n}}\\[2pt]\mathrm {P} \{d=k\}&={\frac {1}{k(k-1)}}\qquad (k=2,3,\dots ,n).\,\end{aligned}}}

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

انظر أيضاً

ملاحظات ومراجع

  1. 1 2 م. لوبي، "رموز LT"، الندوة السنوية الثالثة والأربعون لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، 2002.
  2. ↑ تتميز عملية XOR الحصرية ،التي يرمز لها بـ ⊕ ، بخاصية مفيدة للغاية وهي أن A ⊕ A =0، حيث A عبارة عن سلسلة عشوائية من البتات .    
  3. ↑ رموز النافورة ، بقلم دي جيه سي ماكاي، نُشرت لأول مرة في IEEE Proc.-Commun.، المجلد 152، العدد 6، ديسمبر 2005.
  4. 1 2 تحسين توزيع درجة رموز LT باستخدام نهج أخذ العينات المهمة ، بقلم إيسا هييتيا، وتوماس تيرونين، وجورما فيرتامو (2006).