ما هو فحص التكافؤ منخفض الكثافة في شبكات الحاسوب LDPC

تم تطوير “LDPC” بواسطة “Robert G. Gallager” في عام 1960م لذلك تُعرف هذه الرموز أيضاً باسم رموز “Gallager”.

ما هو كود فحص التكافؤ منخفض الكثافة LDPC

كود فحص التكافؤ منخفض الكثافة “LDPC”: هو رمز كتلة لتصحيح الخطأ الخطي ومناسب لتصحيح الخطأ في أحجام الفدرات الكبيرة المرسلة عبر قنوات صاخبة للغاية.

• “LDPC” هي اختصار لـ “Low Density Parity Check Code”.

أساسيات فحص التكافؤ منخفض الكثافة LDPC

أولاً: الترميز بواسطة أكواد التحقق من التكافؤ منخفض الكثافة

يتم تحديد كود فحص التكافؤ منخفض الكثافة “LDPC” بواسطة مصفوفة فحص التكافؤ تحتوي في الغالب على أصفار وكثافة منخفضة تبلغ “1 ثانية”، حيث تمثل صفوف المصفوفة المعادلات وتمثل الأعمدة البتات في كلمة المرور أي رموز الكود، كما يتم تمثيل رمز “LDPC” بواسطة حيث يكون طول الكتلة هو عدد “1s” في كل عمود وهو عدد “1s” في كل صف، مع الاحتفاظ بالخصائص التالية:

• j هو الرقم الثابت الصغير لـ 1 في كل عمود، حيث “j> 3”.

• k هو الرقم الثابت الصغير لـ 1 في كل صف، حيث “k> j”.

• في مصفوفة التحقق من التكافؤ في كود هامينج، تكون مصفوفة التحقق من التكافؤ التالية رمز هامينج الذي يحتوي على “n = 7″، مع “4 بتات” معلومات متبوعة بـ “3 بتات” تعادلية زوجية أي أرقام التحقق قطرياً 1.

ثانياً: فك رموز LDPC

هناك طريقتان محتملتان لفك تشفير رموز “LDPC”، وهي:

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

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

ملاحظة:الفئتان الفرعيتان من هذه الأساليب هما انتشار المعتقدات وفك الاحتمالية القصوى، وعلى الرغم من أنّ خوارزميات فك التشفير هذه معقدة إلّا أنّها تحقق نتائج أفضل من الأولى.

كيفية تمثيل فحص التكافؤ منخفض الكثافة LDPC

يوجد أساساً احتمالان مختلفان لتمثيل أكواد “LDPC”، مثل كل رموز الكتلة الخطية يمكن وصفها عبر المصفوفات والاحتمال الثاني هو تمثيل رسومي.

أولاً: تمثيل المصفوفة

المصفوفة المحددة في المعادلة عبارة عن مصفوفة تحقق من التكافؤ بالبعد “n x m” مثلاً لكود “8،4″ ويمكن الآن تحديد رقمين يصفان هذه المصفوفة، و”Wt” لعدد 1 في كل صف و “Wc” للأعمدة ولكي يطلق على مصفوفة كثافة منخفضة، يجب استيفاء الشرطين “Wc << n” و”Wt << m”، وللقيام بذلك يجب أن تكون مصفوفة فحص التكافؤ عادةً كبيرة جداً، لذلك لا يمكن تسمية نموذج المصفوفة فعلياً بكثافة منخفضة.

ثانياً: التمثيل البياني

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

يُطلق على نوعي العقد في الرسم البياني الدباغ “tanner” اسم العقد المتغيرة (العقد v) وفحص العقد (العقد c)، وفي مثال على رسم تانر البياني ويمثل نفس رمز المصفوفة يتم إنشاء مثل هذا الرسم البياني إلى حد ما مباشرة إلى الأمام، وتتكون من عقد فحص m (عدد بتات التكافؤ) وn عقد متغيرة (عدد البتات في كلمة مشفرة)، ومعادلات رمز “LDPC” بسيط مع “n = 12”.

أساسيات فحص التكافؤ منخفض الكثافة LDPC

توجد ميزة رموز “LDPC” لأداء بالقرب من حد “Shannon” للقناة فقط لأطوال الكتل الكبيرة، وعلى سبيل المثال كانت هناك عمليات محاكاة تعمل في الداخل، و”0.04 ديسيبل” من حد شانون بمعدل خطأ بت “10 ^ (- 6) بطول كتلة 10 ^ (7)”، وحقيقة مثيرة للاهتمام هي أنّ هذه الرموز عالية الأداء غير منتظمة.

كما يؤدي طول الكتلة الكبير أيضًا إلى فحص تكافؤ كبير ومصفوفات مولد ويعتمد تعقيد ضرب كلمة مشفرة في مصفوفة على مقدار الآحاد في المصفوفة، حيث إذا وضعنا المصفوفة المتناثرة H بالشكل [P ^ (T) I] عبر حذف “Gaussian”، يمكن حساب مصفوفة المولد G على أنّها “G = [IP]”، والمصفوفة الفرعية P ليست قليلة بشكل عام لذا فإنّ تعقيد التشفير سيكون عالياً جداً.

ونظراً لأنّ التعقيد ينمو في “O (n ^ 2)” حتى المصفوفات المتفرقة لا تؤدي إلى أداء جيد إذا كان طول الكتلة مرتفعاً جداً، لذلك يتم استخدام خوارزميات فك التشفير التكراري والتشفير بحيث تقوم هذه الخوارزميات بإجراء حسابات محلية وتمرير تلك النتائج المحلية عبر الرسائل، وعادة ما تتكرر هذه الخطوة عدة مرات، وكما يشير مصطلح “الحسابات المحلية” بالفعل إلى أنّ استراتيجية فرق تسد التي تفصل مشكلة معقدة إلى مشاكل فرعية يمكن التحكم فيها قد تحققت.

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

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

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