رموز فحص التكافؤ منخفضة الكثافة (LDPC)
- قدّمه
- Robert Gallager
- السنة
- 1962
- النوع
- linear error-correcting code
- العائلة
- Coding theory
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
رموز LDPC، التي اخترعها روبرت غالاغر عام 1962 وأعاد اكتشافها ماكاي في التسعينيات، هي رموز خطية لتصحيح الأخطاء تُعرّف بواسطة مصفوفات فحص تكافؤ متفرقة. تحقق هذه الرموز أداءً ضمن 0.4 ديسيبل من حد شانون مع فك تشفير تكراري يعتمد على انتشار الاعتقاد، وقد أصبحت المعيار للشبكات اللاسلكية الحديثة (WiFi-6، 5G NR، البث التلفزيوني الرقمي). على عكس رموز توربو، تتميز رموز LDPC ببنية نظرية رسوم بيانية أكثر أناقة وتحليل نظري أكثر نضجًا.
الفكرة الحدسية وراء الطريقة
تستخدم الرموز الخطية القياسية مصفوفات فحص تكافؤ كثيفة، مما يجعل فك التشفير مكثفًا حسابيًا. رموز LDPC تعكس هذا: مصفوفة فحص التكافؤ متفرقة (معظم الإدخالات صفرية)، لذا فإن كل فحص تكافؤ يتضمن عددًا قليلاً فقط من البتات. عند المستقبل، يتم بناء رسم بياني ثنائي حيث تمثل العقد المتغيرة البتات المرسلة وتمثل عقد الفحص قيود التكافؤ. يصبح فك التشفير تمرير رسائل تكراريًا على هذا الرسم البياني: تجمع كل عقدة متغيرة معلومات من جيرانها، وتحدث اعتقادها حول قيمة البت، وترسل تقديرات محسنة مرة أخرى. يضمن التفرق تقاربًا سريعًا وأداءً قريبًا من حد شانون.
التاريخ
اخترع غالاغر رموز LDPC في عام 1962، لكن النظرية تأخرت عن التنفيذ العملي. في عام 1995، أعاد ماكاي اكتشافها وأظهر أداءها القريب من حد شانون عبر المحاكاة. طورت الأبحاث المكثفة في العقد الأول من القرن الحادي والعشرين خوارزميات فعالة للترميز وفك التشفير وبناء الرسوم البيانية. تم اعتماد رموز LDPC في WiFi-6 (802.11ax، 2021) ومعيار 5G NR (2018). لقد أصبحت أكثر انتشارًا من رموز توربو في الأنظمة الجديدة نظرًا لأدائها الأفضل وبنيتها الأنظف.
متى تُستخدم
تُفضل رموز LDPC على رموز توربو في الأنظمة الحديثة نظرًا لأدائها الأفضل وبنيتها الأبسط. استخدم LDPC لنطاقات SNR الواسعة (لا يوجد منحدر عتبة)؛ فهي تعمل جيدًا من SNR المنخفض إلى العالي. LDPC هو المعيار لـ WiFi-6 والأقمار الصناعية و 5G NR. تجنب LDPC فقط إذا كانت التوافقية القديمة تتطلب رموز توربو. LDPC مناسبة أيضًا للحزم القصيرة جدًا (>30 بت) حيث أن بنية الرمز قابلة للفصل.
الحدود والاعتبارات
- يصبح بناء الرسم البياني وتخزين المصفوفة معقدين للرموز الطويلة جدًا (>10 آلاف بت)
- الأداء حساس للهياكل الرسومية صغيرة الحجم (الأطواق، المجموعات الممتصة)؛ يتطلب تصميمًا دقيقًا
- يفترض انتشار الاعتقاد رسمًا بيانيًا حلقيًا، لكن الرسوم البيانية تحتوي على دورات؛ لا يضمن التقارب إلى الحل الأمثل
- تنمو زمن استجابة فك التشفير (التكرارات) لوغاريتميًا مع SNR؛ ليس زمن استجابة صفريًا مثل بعض الرموز الكلاسيكية
- يؤثر تكميم الرسائل (في الأجهزة ذات النقطة الثابتة) على الأداء؛ يلزم تخصيص دقيق للبتات
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- أداء ضمن 0.4 ديسيبل من حد شانون (أفضل قليلاً من رموز توربو)
- بنية نظرية رسوم بيانية أبسط؛ تحليل نظري أوضح من رموز توربو
- فك التشفير التكراري يتجنب سلوك العتبة الشبيه بالمنحدر (على عكس توربو)
- تصميم رمز مرن عبر بناء الرسم البياني؛ سهل التكييف مع تطبيقات محددة
- أجهزة فك تشفير متوازية فعالة؛ تمرير الرسائل يناسب تنفيذ VLSI/GPU
- يعمل بشكل جيد لكل من الكلمات الرمزية الطويلة والقصيرة نسبيًا
التطبيقات
- WiFi-6 (802.11ax): شبكات محلية لاسلكية عالية الإنتاجية مع توفير LDPC لتسليم البيانات الموثوق به
- 5G NR: ترميز القناة لكل من قنوات البيانات والتحكم، لتحل محل رموز توربو من 4G
- اتصالات الأقمار الصناعية: البث التلفزيوني الرقمي (DVB-S2) ومهام الفضاء السحيق باستخدام LDPC ذات الكلمات الرمزية الطويلة
- اتصالات خطوط الطاقة (PLC): نقل بيانات قوي عبر الشبكات الكهربائية المشوشة
- أنظمة ذاكرة الفلاش: تصحيح الأخطاء لتخزين فلاش NAND دون تآكل من التحديث المتكرر
كيف يعمل
كيف يعمل
يتم ترميز بتات المعلومات باستخدام مصفوفة فحص تكافؤ متفرقة H؛ البتات المرمزة هي الحل للمعادلة H*c = 0 (mod 2)، حيث c هي الكلمة الرمزية.
يتم هيكلة مصفوفة فحص التكافؤ H لتكون متفرقة (على سبيل المثال، كل صف/عمود له وزن منخفض ثابت يتراوح بين 3-5). يتم استغلال هذه البنية للترميز الفعال.
يتم إرسال البتات المرمزة عبر قناة مشوشة؛ البتات المستلمة هي قيم ناعمة (نسب الاحتمال أو نسب لوغاريتم الاحتمال).
يتم بناء رسم بياني ثنائي: العقد اليسرى = العقد المتغيرة (البتات)، العقد اليمنى = عقد الفحص (معادلات التكافؤ). تربط الحواف المتغيرات بالفحوصات التي تظهر فيها.
انتشار الاعتقاد التكراري: تجمع العقد المتغيرة الرسائل من عقد الفحص، وتحدث تقديرات البت، وترسل رسائل محسنة مرة أخرى. بعد التكرارات، يتم اتخاذ قرارات صارمة؛ إذا تم استيفاء فحوصات التكافؤ، يكون فك التشفير ناجحًا.
الأخطاء الشائعة
- استخدام رسم بياني متفرق سيء التصميم مع دورات قصيرة؛ تتسبب الدورات القصيرة في تذبذب انتشار الاعتقاد
- الإفراط في التكرار بعد التقارب؛ التكرارات غير الضرورية تهدر الطاقة دون تحسين
- افتراض أن فك تشفير الحد الأدنى للمجموع جيد مثل فك تشفير مجموع المنتج؛ التقريبات لها فقدان في الأداء، خاصة عند SNR المنخفض
- إهمال تأثيرات الطول المحدود؛ قد تكون الرسوم البيانية المصممة للتحليل التقاربي ضعيفة الأداء على الحزم القصيرة
- عدم مراعاة التكميم في تنفيذ الأجهزة؛ تختلف محاكاة النقطة العائمة عن واقع النقطة الثابتة
الأسئلة الشائعة
ما الذي يجعل فك تشفير LDPC فعالاً للغاية مقارنة بالرموز الخطية العامة؟
يعني تفرق مصفوفة فحص التكافؤ أن كل بت يشارك في عدد قليل فقط من فحوصات التكافؤ. عند فك التشفير، يكون تمرير الرسائل على الرسم البياني الثنائي خطيًا في عدد الحواف، وليس طول الرمز. بالنسبة للرموز الكثيفة، سيتطلب فك التشفير قلب المصفوفة، وهو مكعب في طول الرمز. يجعل التفرق فك التشفير شبه خطي وعمليًا للرموز الطويلة.
ما هي المجموعة الممتصة ولماذا هي مهمة؟
المجموعة الممتصة هي مجموعة فرعية صغيرة من الرسم البياني يمكنها أن تحبس فك تشفير انتشار الاعتقاد، مما يمنع التقارب إلى الحل الصحيح. إنها مصدر رئيسي لأرضية الخطأ (الانخفاض غير الأسي في BER عند SNR المنخفض). يتجنب مصممو الرموز المجموعات الممتصة القصيرة من خلال بناء الرسم البياني بعناية؛ تحدد أدوات التحليل (مثل تحليل مجموعة التوقف) الهياكل الإشكالية.
كيف تقارن LDPC بالرموز القطبية؟
كلاهما يحقق أداءً قريبًا من حد شانون. تتميز الرموز القطبية ببنية تكرارية وأمثلية قابلة للإثبات تحت فك تشفير الإلغاء المتتالي عند طول رمز لا نهائي. رموز LDPC أكثر مرونة ولها أداء أفضل بطول محدود تجريبيًا. يستخدم 5G NR الرموز القطبية لقنوات التحكم (الحزم القصيرة) و LDPC لقنوات البيانات (الحزم الطويلة)، مستفيدًا من نقاط قوة كل رمز.
لماذا يعتبر محيط الرسم البياني مهمًا في رموز LDPC؟
المحيط هو طول أقصر دورة في الرسم البياني الثنائي. تتسبب الدورات القصيرة (محيط < 6) في استخدام انتشار الاعتقاد لمعلومات مترابطة (تتكرر الرسائل)، مما يقلل من الأداء. تعمل الرموز ذات المحيط العالي (محيط ≥ 6) على كسر الارتباطات بشكل أفضل. غالبًا ما يتم تصميم الرموز لزيادة المحيط إلى أقصى حد مع مراعاة قيود التفرق.
طرق ذات صلة
المصادر
Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.
افتح مرجع DOIتم النسخ.Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.
افتح مرجع DOIتم النسخ.