🔢 mathematics

Low-Pathwidth GRAND: Exact Likelihood-Ordered Enumeration for BPSK Transmission over Correlated Gaussian Noise

تقدم هذه الورقة خوارزمية LP-GRAND، وهي خوارزمية فك تشفير دقيقة قائمة على أقصى احتمالية لـ BPSK عبر ضجيج غاوسي مترابط تستفيد من بنية عرض المسار المنخفض لمصفوفة دقة الضجيج لحصر أنماط الضجيج وفق ترتيب الاحتمالية عبر البرمجة الديناميكية، مما يضمن أداء فك تشفير مثالي حيث تفشل التقريبات التقليدية.

المؤلفون الأصليون: Behrooz Razeghi

نُشر 2026-07-31

📖 7 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Behrooz Razeghi

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

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

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

تقدم هذه الورقة البحثية وحدة فك تشفير جديدة وعالية الدقة تسمى Low-Pathwidth GRAND (LP-GRAND). فكر فيها كأنها محقق بارع لا يكتفي بتخمين الضجيج فحسب، بل يرسم خريطة لـ "رسم بياني للتفاعل" (interaction graph) الخاص بالضجيج بالكامل ليجد الترتيب المثالي لفحص الاحتمالات. يوضح المؤلفون أنه من خلال التعامل مع الضجيج كشكل رياضي محدد (مشهد طاقة تربيعي) واستخدام "تريليس" (trellis) ذكي (خريطة خطوة بخطوة)، يمكنهم سرد كل نمط ضجيب محتمل بالترتيب الدقيق للاحتمالية، حتى عندما يكون الضجيج مرتبطًا بشدة. لقد أثبتوا رياضيًا أنه إذا اتبعت هذه القائمة دون تخطي أي شيء، فإن أول رسالة صالحة تجدها ستكون هي الإجابة الأفضل بالتأكيد. وفي عمليات المحاكاة مع أكواد معينة، وجد هذا الأسلوب الجديد الرسالة الصحيحة بشكل أكثر تكرارًا وأسرع من الاختصارات القائمة على "القطع"، مما يثبت أن تخصيص الوقت لرسم الروابط المعقدة يؤتي ثماره.

الفكرة الجوهرية: رسم خريطة متاهة الضجيج

لفهم كيفية عمل LP-GRAND، دعنا نتخيل الضجيج كمتاهة ضخمة متعددة الأبعاد. في عالم "عديم الذاكرة" (memoryless) البسيط، تكون كل المسارات في المتاهة مستقلة؛ يمكنك اختيار الانعطاف يسارًا أو يمينًا في أي نقطة دون القلق بشأن المنعطف السابق. أما في العالم "المرتبط"، فإن المتاهة تكون ملتوية. فالانعطاف يسارًا في الخطوة 5 قد يجبرك على الانعطاف يمينًا في الخطوة 6. هذا الالتواء هو ما يجعل الرياضيات صعبة.

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

يستخدم LP-GRAND هذا السلم لإجراء بحث "الأفضل أولاً" (best-first search). فهو لا يسير في السلم فحسب؛ بل يحسب "تكلفة الطاقة" لكل مسار محتمل. كلما انخفضت الطاقة، زاد احتمال ذلك النمط من الضجيج. ومن خلال استخدام تقنية تسمى البرمجة الديناميكية اللاحقة (suffix dynamic programming)، يمكن لفك التشفير التطلع للأمام ومعرفة أي المسارات هي الأرخص للاستكشاف تاليًا. الأمر يشبه امتلاك نظام ملاحة (GPS) لا يخبرك فقط بالمسافة إلى المخرج، بل يخبرك بالترتيب الدقيق لزيارة كل مسار ممكن لضمان العثور على أقصر طريق أولاً.

لماذا فشلت الاختصارات القديمة؟

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

تجادل الورقة صراحةً ضد هذه "التقريبات القائمة على الكتل". يوضح المؤلفون أنه عندما يكون الضجيج مرتبطًا، فإن هذه الاختصارات تفقد "التفاعلات بين الإحداثيات" (cross-coordinate interactions)—وهي الطرق الدقيقة التي يؤثر بها جزء من الضجيج على جزء آخر. وفي اختباراتهم، أدت هذه الاختصارات غالبًا إلى تخمين نمط الضجيج الخاطئ أولاً، مما أدى إلى أخطاء في فك التشفير. وتوضح الورقة أنه بينما تكون هذه الاختصارات أسرع في الحساب، إلا أنها ليست مثالية من حيث "الاحتمالية القصوى" (Maximum Likelihood - ML)، مما يعني أنها لا تضمن العثور على الإجابة الأفضل مطلقًا. في المقابل، يرفض LP-GRAND اختصار الطرق؛ فهو يحسب الطاقة الدقيقة للضجيج المرتبط بالكامل، مما يضمن أن أول رسالة صالحة يجدها هي الأكثر احتمالًا من الناحية الرياضية.

النتائج: تطابق مثالي

لم يكتف المؤلفون بالنظرية؛ بل اختبروا وحدة فك التشفير الخاصة بهم بصرامة. أجروا عمليات محاكاة على نوعين مختلفين من الأكواد: كود صغير [20, 12] وكود أكبر [64, 52].

في اختبارات الكود الصغير، قارنوا LP-GRAND بالبحث "الشامل" (exhaustive search)—وهي طريقة تفحص كل رسالة ممكنة واحدة تلو الأخرى للعثور على الأفضل. هذه الطريقة الشاملة هي المعيار الذهبي ولكنها عادة ما تكون بطيئة جدًا للاستخدام الفعلي. وعلى مدار 10,000 إطار من البيانات، وافق LP-GRAND البحث الشامل بنسبة 100% من الوقت. لقد وجد نفس الرسالة "الأفضل" في كل مرة، مما يثبت أن ترتيبه لأنماط الضجيج كان مثاليًا رياضيًا.

بالنسبة للأكواد الأكبر [64, 52]، قارنوا LP-GRAND بالاختصارات الشهيرة القائمة على الكتل (مثل ORBGRAND-AI و ExactBlockProduct). عند جودة إشارة تبلغ 2 ديسيبل (dB)، حقق LP-GRAND معدل خطأ في الكتلة (BLER) أقل من جميع الأساليب الأخرى. بعبارة بسيطة، ارتكب أخطاء أقل. على سبيل المثال، مع كود عشوائي محدد، سجل LP-GRAND معدل خطأ قدره حوالي 0.022، بينما سجل أفضل تقريب قائم على الكتل معدل خطأ قدره 0.040. وهذا يعني أن LP-GRAND كان أكثر موثوقية بمقدار الضعف تقريبًا في هذه الاختبارات.

سحر "عرض المسار" (Pathwidth)

السر وراء وحدة فك التشفير هذه هو مفهوم عرض المسار (pathwidth). تخيل اتصالات الضجيج كرسم بياني حيث ترتبط النقاط (البتات) بخطوط. إذا كان الرسم البياني عبارة عن خط مستقيم طويل، فإن عرض المسار يكون صغيرًا. إذا كان عبارة عن كرة متشابكة من الخيوط، فإن عرض المسما يكون ضخمًا. أظهر المؤلفون أنه إذا كانت مصفوفة الضجيج تمتلك "نصف عرض نطاق" (half-bandwidth) (بمعنى أنها تربط فقط البتات القريبة من بعضها البعض)، فإن عرض المسار يكون صغيرًا بما يكفي لبناء "تريليس" يمكن إدارته.

لقد اختبروا ذلك على رسوم بيانية ذات أشكال مختلفة، مثل المسارات، والسلالم، والأشجار الثنائية. بالنسبة لأشكال "المسار" و"السلم"، والتي تمثل نوع الضجيج الموجود في العديد من القنوات الواقعية، عمل فك التشفير بشكل مثالي. حتى أنهم اختبروا سيناريو تم فيه إعادة ترتيب اتصالات الضجيج (permuted) بحيث لم تعد في ترتيب منظم. ومن خلال استخدام خدعة إعادة الترتيب الذكية المسماة Reverse Cuthill–McKee (RCM)، تمكنوا من إيجاد عرض مسار منخفض وتشغيل فك التشفير بكفاءة. في أحد الاختبارات مع كود مكون من 64 بت تمت إعادة ترتيبه، وجد LP-GRAND الرسالة الصحيحة في جميع الـ 50 إطارًا التي تم اختبارها، بينما ارتكبت الأساليب القائمة على الكتل أخطاء في 17 إلى 25 إطارًا.

الخلاصة

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

ملخص تقني: خوارزمية LP-GRAND (ذات عرض المسار المنخفض)

بيان المشكلة
تتناول الورقة البحثية تحدي فك التشفير بتقدير الاحتمال الأقصى (ML) لإرسال تعديل إزاحة الطور الثنائي (BPSK) عبر قنوات ذات ضجيج غاوسي مترابط. يحقق نظام "التخمين العشوائي لفك تشفير الضجيج المضاف" (GRAND) القياسي ذو المدخلات اللينة (soft-input) ضمانات ML للكتل ذات الطول المحدود، وذلك عبر استعلام أنماط تأثير الضجيج المرشحة بترتيب تنازلي لتوقعات احتمالاتها الشرطية. ومع ذلك، في حالة الضجيج المترابط، لا يتوزع الاحتمال الشرطي المطابق عبر الإحداثيات بشكل مستقل؛ بل يحتوي على حدود تفاعل بين الإحداثيات.

تعتمد متغيرات GRAND الحالية، مثل ORBGRAND وامتداداتها القائمة على الكتل (ORBGRAND-AI)، على مقاييس موثوقية جمعية أو تقريبات استقلال الكتل. تفشل هذه الطرق في الحفاظ على ترتيب الاحتمالية الدقيق المطلوب لفك تشفير ML لأنها تغفل تفاعلات الإحداثيات المتقاطعة المتأصلة في مقياس اللوغاريتم السالب للقدرة (negative log-likelihood). ونتيجة لذلك، فإن أول تطابق مع كتاب الشفرة (codebook hit) الذي تجده هذه التقريبات ليس مضمونًا ليكون هو الكلمة المشفرة (codeword) ذات الاحتمال الأقصى. وبينما يمكن تحقيق الترتيب الدقيق لنماذج محددة مثل التداخل بين الرموز (ISI) عبر SGRAND-ISI، إلا أن الحل العام لمصفوفات الدقة (precision matrices) المتفرقة (sparse) كان مفقودًا.

المنهجية
يقترح المؤلفون LP-GRAND (خوارزمية GRAND ذات عرض المسار المنخفض)، وهو فك تشفير يولد أنماط تأثير الضجيج المرشحة بالترتيب الدقيق المستحث بواسطة احتمالية غاوس (Gaussian likelihood) المطابقة لأي مصفوفة دقة متناظرة وموجبة محددة $Q = \Sigma^{-1}$ .

صياغة بولية تربيعية كاذبة (Quadratic Pseudo-Boolean Formulation):
يتم اشتقاق الجزء المعتمد على المرشح من اللوغاريتم السالب للقدرة الغاوسية كدالة طاقة بولية تربيعية كاذبة تعتمد على الملاحظة، $W_r(z)$ . بالنسبة لنمط ضجيج مرشح $z \in \{0, 1\}^n$ ، تكون الطاقة هي:
$W_r(z) = \sum_{i=1}^n \alpha_i z_i + \sum_{1 \le i < j \le n} \beta_{ij} z_i z_j$
يحتوي رسم التفاعل البياني لهذه الطاقة على حافة $\{i, j\}$ إذا وفقط إذا كان الإدخال المقابل في مصفوفة الدقة $Q_{ij} \neq 0$ . وبالتالي، فإن نمط التشتت (sparsity pattern) لـ $Q$ يحدد هيكل دالة الطاقة.
التمثيل الرسومي عبر التفكيك المساري (Path Decomposition):
لتعداد الأنماط بترتيب غير متزايد للطاقة، تبني LP-GRAND تمثيلاً رسومياً طبقيًا (شبكة أو رسم بياني موجه غير حلقي DAG) بناءً على تفكيك مساري لرسم التفاعل البياني.

إذا كان لمصفوفة الدقة نصف عرض (half-bandwidth) لا يتجاوز $\nu$ ، فإن رسم التفاعل يقبل تفكيكاً مسارياً بعرض $w \le \nu$ .
ينتج عن هذا التفكيك رسماً بيانياً طبقياً يحتوي على ما لا يزيد عن $2^{w+1}$ من الحالات (تعيينات الحقائب) لكل طبقة.
بالنسبة للمصفوفات النطاقية (banded matrices)، يقل هذا إلى شبكة (trellis) قياسية تحتوي على $2^\nu$ من الحالات لكل طبقة.

خوارزمية التعداد الدقيق:
يستخدم فك التشفير البرمجة الديناميكية اللاحقة (suffix dynamic programming) مدمجة مع التعداد الكامل للمسارات بنظام البحث الأفضل أولاً (best-first complete-path enumeration) (باستخدام طابور أولوية) على الرسم البياني الطبقي المنشأ.

تقوم البرمجة الديناميكية اللاحقة بحساب الحد الأدنى من التكلفة للوصول إلى المصدر (sink) من أي حالة مسبقاً، مما يسمح بعملية تقليم فعالة تعتمد على البحث والتقليم (branch-and-bound).
يقوم مُعدد "الأفضل أولاً" باستخراج المسارات بترتيب غير متزايد للتكلفة الإجمالية.
تقوم الخوارزمية باستعلام اختبار عضوية كتاب الشفرة $\Phi(y \oplus z)$ لكل نمط $z$ يتم إصداره. أول نمط يحقق $\Phi(y \oplus z) = 1$ هو الذي يتم إرجاعه.

المساهمات الرئيسية

ترتيب ML الدقيق: تثبت الورقة أنه لأي كتاب شفرة ثنائي غير فارغ بكلمات مشفرة متساوية الاحتمال، فإن تعداد أنماط تأثير الضجيج بترتيب غير متزايد لـ $W_r(z)$ يضمن أن أول تطابق مع كتاب الشفرة هو كلمة مشفرة ذات احتمال أقصى (ML). وهذا ينطبق في الحسابات الحقيقية دون التخلي عن عملية البحث.
التعامل العام مع المصفوفات المتفرقة: على عكس الطرق السابقة المقيدة بنماذج قنوات محددة (مثل القنوات عديمة الذاكرة أو ISI محدد)، تقوم LP-GRAND ببناء الترتيب الدقيق مباشرة من مصفوفة دقة متفرقة مقدمة، بشرط أن يقبل رسم التفاعل الخاص بها تفكيكاً مسارياً ذا عرض محدود.
البناء الخوارزمي: يقدم المؤلفون طريقة بنائية لبناء التمثيل الرسومي الطبقي من تفكيك مساري صالح. ويوضحون أنه بالنسبة لتفكيك مساري بعرض $w$ ، فإن التمثيل الرسومي يحتوي على ما لا يزيد عن $2^{w+1}$ من الحالات لكل طبقة، مما ينمو خطياً مع طول الكتلة $n$ لثابت $w$ .
تحليل المتانة: تثبت الورقة الشروط التي يتم بموجبها الحفاظ على الترتيب الزوجي الصارم للمرشحين تحت كمية التكميم (coefficient quantization) وعدم تطابق مصفوفة الدقة، مما يضمن الحفاظ على الترتيب الدقيق للمقياس المعدل.

النتائج التجريبية
قام المؤلفون بالتحقق من صحة LP-GRAND من خلال تقييمات عددية واسعة النطاق:

التحقق من الدقة: بالنسبة لأطوال كتل صغيرة ( $n \in \{8, 10, 12\}$ ) وتضاريس متنوعة (banded, path, ladder, binary tree)، طابقت سلسلة مخرجات LP-GRAND الترتيب الشامل لجميع المرشحين $2^n$ بترتيب غير متزايد للطاقة. كان أقصى فرق مطلق بين تكاليف المسار الرسومي والتقييم التربيعي المباشر في حدود $10^{-16}$ .
التوافق مع ML: بالنسبة لكودين ثابتين $[20, 12]$ (كود خطي عشوائي وكود CRC-8) عبر 10,000 إطار، اتفقت LP-GRAND تماماً مع فك التشفير الشامل للكلمات المشفرة (exhaustive codeword ML decoding).
الأداء مقابل التقريبات: بالنسبة لستة أكواد ثابتة $[64, 52]$ عند $E_b/N_0 = 2$ ديسيبل اسمي مع ضجيج مترابط ( $\rho=0.5$ )، حققت LP-GRAND معدل خطأ في الكتلة (BLER) أقل من كل من ExactBlockProduct (تقريب الاستقلال القائم على الكتل) و ORBGRAND-AI.
الكفاءة: تطلبت LP-GRAND استعلامات عضوية صالحة أقل بكثير للعثور على أول كلمة مشفرة مقارنة بالتقريبات. على سبيل المثال، عند $R_c = 0.75$ ، سجلت LP-GRAND متوسط 132.3 استعلاماً مقابل 227.5 لـ ExactBlockProduct و 350.6 لـ ORBGRAND-AI.
الرسوم البيانية غير النطاقية (Non-Banded): تعاملت الطريقة بنجاح مع قناة Gauss-Markov تم تغيير ترتيب إحداثياتها، حيث كان نصف عرض النطاق (half-bandwidth) لترتيب الإحداثيات هو 56، ولكن ترتيب Reverse Cuthill-McKee (RCM) قلل عرض الجبهة (frontier width) المستحث إلى 1، مما سمح بتعداد فعال.

الأهمية والادعاءات
تزعم الورقة أن LP-GRAND توفر أول فك تشفير دقيق، غير مرتبط بكود معين (code-agnostic)، ذو مدخلات لينة لـ BPSK عبر ضجيج غاوسي مترابط يضمن فك تشفير ML تحت التعداد الكامل. ومن خلال الاستفادة من التفكيكات المسارية لرسم التفاعل الناتج عن مصفوفة الدقة، تتجنب الخوارزمية تقريبات الاستقلال التي تضعف ضمان ML في متغيرات GRAND الموجودة. يوضح العمل أن التعداد المرتب بدقة للاحتمالية هو أمر ممكن حسابياً للمصفوفات المتفرقة ذات عرض المسار المنخفض، مما يوفر بديلاً صارماً للمفككات التي تعتمد على التخمين أو التقريب في بيئات الضجيج المترابط. ويؤكد المؤلفون أنه بينما يكون حجم الرسم البياني محدوداً بعرض المسار، فإن عدد الاستعلامات المطلوبة للوصول إلى أول تطابق يعتمد على كتاب الشفرة وتحقق القناة، وليس فقط على عرض الرسم البياني.