2025-11-20T14:55:15.130233

On the Weight Spectrum of Rate-Compatible Polar Codes

Ye, Li, Liu et al.
The weight spectrum plays a crucial role in the performance of error-correcting codes. Despite substantial theoretical exploration of polar codes with mother code length, a framework for the weight spectrum of rate-compatible polar codes remains elusive. In this paper, we address this gap by presenting the theoretical results for enumerating the number of minimum-weight codewords for quasi-uniform punctured, Wang-Liu shortened, and bit-reversal shortened decreasing polar codes. Additionally, we propose efficient algorithms for computing the average spectrum of random upper-triangular pre-transformed shortened and punctured polar codes. Notably, our algorithms operate with polynomial complexity relative to the code length. Simulation results affirm that our findings yield a precise estimation of the performance of rate-compatible polar codes.
academic

حول طيف الوزن لأكواد القطبية المتوافقة مع المعدل

المعلومات الأساسية

  • معرّف الورقة: 2410.19242
  • العنوان: On the Weight Spectrum of Rate-Compatible Polar Codes
  • المؤلفون: Zicheng Ye, Yuan Li, Zhichao Liu, Huazi Zhang, Jun Wang, Guiying Yan, Zhiming Ma
  • التصنيف: cs.IT math.IT
  • وقت النشر: أكتوبر 2024
  • رابط الورقة: https://arxiv.org/abs/2410.19242

الملخص

يلعب طيف الوزن دوراً حاسماً في أداء أكواد تصحيح الأخطاء. على الرغم من الاستكشاف النظري الواسع لأكواد القطبية بطول الكود الأم، فإن إطار عمل طيف الوزن لأكواد القطبية المتوافقة مع المعدل لا يزال بعيد المنال. تعالج هذه الورقة هذه الفجوة من خلال تقديم نتائج نظرية لتعداد عدد كلمات الكود ذات الوزن الأدنى للأكواد القطبية المختصرة بحذف موحد شبه منتظم (QUP)، واختصار Wang-Liu، واختصار عكس البت. علاوة على ذلك، نقترح خوارزمية فعالة لحساب الطيف المتوسط للأكواد القطبية المختصرة والمحذوفة بتحويل مسبق مثلثي عشوائي. والجدير بالملاحظة أن خوارزميتنا لها تعقيد متعدد الحدود فيما يتعلق بطول الكود. تؤكد نتائج المحاكاة أن نتائجنا توفر تقديرات دقيقة للأداء في أكواد القطبية المتوافقة مع المعدل.

خلفية البحث والدافع

خلفية المشكلة

  1. قيود أكواد القطبية: تقتصر أكواد القطبية على طول كود أولي يكون قوة العدد 2 بسبب البنية الأساسية للمنتج الكرونيكري. ومع ذلك، تتطلب التطبيقات العملية عادة نقل رسائل بأطوال أكواد مختلفة، مما يتطلب تقنيات الحذف والاختصار لتوفير المرونة المطلوبة في طول الكود.
  2. أهمية طيف الوزن: يؤثر طيف الوزن بشكل كبير على أداء فك التشفير بأقصى احتمالية (ML)، ويمكن تقريبه من خلال حدود الاتحاد بناءً على عدد كلمات الكود منخفضة الوزن. ومع ذلك، فإن تعقيد حساب طيف الوزن الدقيق يزداد عادة بشكل أسي مع طول الكود.
  3. عدم كفاية الأبحاث الحالية: على الرغم من الأبحاث الواسعة حول طيف وزن أكواد القطبية بطول الكود الأم، لا يزال هناك نقص في إطار عمل منهجي لطيف وزن أكواد القطبية المتوافقة مع المعدل. الطرق الموجودة إما أن تكون معقدة جداً أو ذات نطاق تطبيق محدود.

دافع البحث

تهدف هذه الورقة إلى سد الفجوة في نظرية طيف وزن أكواد القطبية المتوافقة مع المعدل، وتوفير إطار عمل منهجي لتحليل طيف الوزن لأكواد القطبية المحذوفة بشكل موحد شبه منتظم (QUP)، واختصار Wang-Liu، واختصار عكس البت.

المساهمات الأساسية

  1. المساهمات النظرية: تقديم إطار عمل نظري شامل وصيغ لحساب عدد كلمات الكود ذات الوزن الأدنى للأكواد القطبية المختصرة بـ QUP، واختصار Wang-Liu، واختصار عكس البت.
  2. الابتكار الخوارزمي: تطوير خوارزمية بتعقيد متعدد الحدود لحساب طيف الوزن المتوسط للأكواد القطبية المختصرة والمحذوفة بتحويل مسبق مثلثي عشوائي.
  3. تقييم الأداء: التحقق من خلال المحاكاة من أن الطريقة المقترحة يمكنها تقدير أداء أكواد القطبية المتوافقة مع المعدل بدقة، خاصة في ظروف نسبة الإشارة إلى الضوضاء العالية.
  4. تحسين التعقيد: جميع الخوارزميات المقترحة لها تعقيد متعدد الحدود فيما يتعلق بطول الكود، مما يضمن قابلية التوسع والعملية للطريقة.

شرح الطريقة

تعريف المهمة

المهمة الأساسية للبحث هي حساب طيف الوزن لأكواد القطبية المتوافقة مع المعدل، خاصة عدد كلمات الكود ذات الوزن الأدنى. بالنظر إلى مجموعة المعلومات I ونمط مطابقة المعدل (نمط الحذف أو الاختصار)، الهدف هو تحديد توزيع وزن الكود.

الأساس النظري

التمثيل الأحادي لأكواد القطبية

يمكن وصف أكواد القطبية كأكواد أحادية في الحلقة F₂x₁,...,xₘ/(x₁²-x₁,...,xₘ²-xₘ). يُعرّف المجموعة الأحادية كما يلي:

M ≜ {x₁^(a₁)...xₘ^(aₘ) | (a₁,...,aₘ) ∈ F₂ᵐ}

أكواد أحادية متناقصة

مجموعة المعلومات I⊆M متناقصة إذا كان ∀f≼g و g∈I، فإن f∈I. حيث ≼ يمثل الترتيب الجزئي للأحاديات.

الخوارزميات الأساسية

1. أكواد القطبية المختصرة بعكس البت

النظرية 2: لتكن C(I,Y'ᵢ) كود قطبي متناقص مختصر من الرتبة r بطول N=2ᵐ، مع نمط اختصار Y'ᵢ. بالنسبة للأحادي f بدرجة r، عدد كلمات الكود بأقل وزن d=2^(m-r) هو:

|Tf(d,Y'ᵢ)| = λf(1 - βf(i)/2ʳ)

حيث βf(i) هو عدد عوامل f في Y'ᵢ.

الخوارزمية 1 تصف العملية:

  • التعقيد: O(|Y'||Iᵣ|) = O(N²)
  • لكل أحادي f بدرجة r، احسب عدد عوامله المختصرة
  • حدّث بشكل متكرر عدد كلمات الكود المتبقية

2. أكواد القطبية QUP

تؤسس اللمة 5 معادلات تكرارية لحساب Pf(d,a):

بالنسبة للأحادي f = xᵢ₁...xᵢₜ، عرّف Nf(w,a) كعدد كلمات الكود بوزن w في أول a بت، إذن:

  • عندما a ≤ 2^(it-1), w≠0: Nf(w,a) = Σₛ∈B(f,t) 2^αf(s)Nf(s)(w,a) + Nf(0)(w,a)
  • عندما 2^(it-1) < a ≤ 2^it: Nf(w,a) = Nf(2^(it-t) - w, 2^it - a)
  • عندما a > 2^it: Nf(w,a) = Nf(w - 2^(it-t), a - 2^it)

3. طيف الوزن المتوسط لأكواد القطبية المحولة مسبقاً

النظرية 7 توفر طيف الوزن المتوسط لأكواد القطبية المحولة مسبقاً:

E[N(d,T,X)] = Σ₁≤j≤K 2^(K-j)Ad(m,(0₁^(Ij-1),1),X) / 2^(N-Ij)

يتم تنفيذها من خلال الخوارزمية 3، بتعقيد O(N³).

نقاط الابتكار التقني

  1. إطار عمل موحد: توفير إطار عمل موحد لتحليل طيف الوزن لأنماط مطابقة معدل متعددة للمرة الأولى.
  2. تعقيد متعدد الحدود: تحقيق جميع الخوارزميات لتعقيد متعدد الحدود، متجاوزة حد التعقيد الأسي التقليدي.
  3. استخدام التماثل: الاستفادة الماهرة من خصائص تماثل الكود لتبسيط الحسابات، مثل اختصار Wang-Liu يمكن الحصول عليه من خلال تماثل QUP.
  4. التحليل التكراري: تحليل الكود بطول N إلى كودين فرعيين بطول N/2 لتقليل تعقيد الحساب.

إعداد التجربة

مجموعات البيانات والمعاملات

  • طول الكود: N = 32, 96, 768, 896 وغيرها
  • عدد البتات المعلوماتية: K = 24, 48, 72, 192, 384, 576 وغيرها
  • اختيار مجموعة المعلومات: بناءً على طريقة التقريب الغاوسي (GA)
  • التحويل المسبق: أكواد PC-polar (باستخدام مسجل إزاحة دوري بطول 5)

مؤشرات التقييم

  • أقل وزن dₘᵢₙ وعدد كلمات الكود بأقل وزن Aₘᵢₙ
  • حساب معدل خطأ الكتلة (BLER) من خلال حد الاتحاد
  • الأداء الفعلية لفك التشفير SCL (حجم القائمة 32)

الطرق المقارنة

  • طيف الوزن المجمع من فك التشفير SCL
  • طريقة الحساب الدقيق التقليدية بتعقيد أسي
  • النتائج التقريبية من الطرق الاحتمالية

نتائج التجربة

النتائج الرئيسية

الجدول 2 يعرض المقارنة بين الحساب النظري ونتائج SCL المجمعة:

  • عندما يكون عدد البتات المحذوفة قليلاً، الحد النظري السفلي يتطابق تماماً مع القيمة الفعلية
  • مع زيادة عدد البتات المحذوفة، قد يكون الحد السفلي أقل بكثير من القيمة الفعلية، لأن كلمات الكود عالية الوزن قد تصبح منخفضة الوزن بعد الحذف

الجدول 3 يعرض أقل وزن وعدد كلمات الكود بأقل وزن لأكواد مختلفة:

  • QUP: dₘᵢₙ = 12, Aₘᵢₙ = 56 (96,24 كود)
  • اختصار Wang-Liu: dₘᵢₙ = 16, Aₘᵢₙ = 292
  • اختصار عكس البت: dₘᵢₙ = 16, Aₘᵢₙ = 490

التحقق من الأداء

الأشكال 1-8 توضح المقارنة بين حد الاتحاد وأداء فك التشفير SCL:

  • في نسبة الإشارة إلى الضوضاء العالية، يتطابق الحد النظري للاتحاد بشكل وثيق مع أداء SCL الفعلية
  • بالنسبة لأكواد القطبية المحولة مسبقاً، يمكن لطيف الوزن المتوسط أيضاً التنبؤ بدقة بالأداء
  • يؤكد على دقة وعملية الطريقة المقترحة

تحليل التعقيد

  • الخوارزمية 1 (اختصار عكس البت): O(N²)
  • الخوارزمية 2 (QUP): O(N³)
  • الخوارزمية 3 (طيف المتوسط المحول مسبقاً): O(N³)

الأعمال ذات الصلة

أبحاث طيف وزن أكواد القطبية

  • اعتبر Bardet وآخرون أكواد القطبية كأكواد أحادية متناقصة، وطبقوا الاختبار الذاتي LTA لتحديد عدد كلمات الكود ذات الوزن الأدنى
  • أبحاث لاحقة حددت عدد كلمات الكود بوزن أقل من 1.5wₘᵢₙ و 2wₘᵢₙ

الطرق الخوارزمية

  • طريقة جمع كلمات الكود منخفضة الوزن من فك التشفير SCL
  • طرق التقريب الاحتمالي بتعقيد متعدد الحدود
  • طريقة تقاطع الشجرة لتقليل تعقيد الحساب

أكواد القطبية المحولة مسبقاً

  • طرق التحويل المسبق مثل CRC المساعد، والتحقق من التكافؤ، وأكواد PAC
  • إثبات نظري أن التحويل المسبق المثلثي لا يقلل مسافة الكود
  • صيغ تكرارية لطيف الوزن المتوسط

الخلاصة والنقاش

الاستنتاجات الرئيسية

  1. تأسيس إطار عمل نظري شامل لطيف وزن أكواد القطبية المتوافقة مع المعدل
  2. توفير خوارزميات فعالة بتعقيد متعدد الحدود
  3. التنبؤ النظري والأداء الفعلية متطابقة بشكل وثيق، خاصة في نسبة الإشارة إلى الضوضاء العالية

القيود

  1. بالنسبة لحالات الحذف الكبيرة، قد يكون الحد السفلي لعدد كلمات الكود ذات الوزن الأدنى غير محكم بما يكفي
  2. على الرغم من أن التعقيد متعدد الحدود، قد تواجه الأكواد الطويلة جداً تحديات حسابية
  3. التركيز الرئيسي على أكواد القطبية المتناقصة، مع قابلية محدودة للتطبيق على الأكواد غير المتناقصة

الاتجاهات المستقبلية

  1. تحسين تقديرات الحدود المحكمة لطيف وزن الأكواد المحذوفة
  2. التوسع إلى طرق بناء أكواد قطبية أكثر عمومية
  3. دراسة العلاقة بين طيف الوزن ومؤشرات الأداء الأخرى

التقييم المتعمق

المميزات

  1. الاكتمال النظري: توفير إطار عمل نظري موحد لأنماط مطابقة معدل متعددة للمرة الأولى، سد فجوة نظرية مهمة
  2. كفاءة الخوارزمية: تحقيق تعقيد متعدد الحدود يمثل نقطة تحول كبيرة، مما يجعل حساب طيف الوزن للأكواد الطويلة ممكناً
  3. التحقق التجريبي: محاكاة شاملة تؤكد دقة النظرية، خاصة توافق حد الاتحاد مع الأداء الفعلية
  4. القيمة العملية: يمكن تطبيق الطريقة مباشرة على التنبؤ بأداء أكواد القطبية وتحسين التصميم

أوجه القصور

  1. ارتخاء الحد السفلي: قد يكون الحد السفلي النظري أقل بكثير من القيمة الفعلية في حالات الحذف العالية
  2. نطاق التطبيق: ينطبق بشكل أساسي على أكواد القطبية المتناقصة، مما يحد من الشمولية
  3. التعقيد: على الرغم من أنه متعدد الحدود، فإن O(N³) قد يشكل تحدياً للأكواد الطويلة جداً

التأثير

  1. المساهمة الأكاديمية: توفير أداة تحليل مهمة لنظرية أكواد القطبية، تعزيز التطور النظري في هذا المجال
  2. القيمة العملية: توفير دعم نظري لتصميم وتحسين أكواد القطبية في أنظمة 5G/6G
  3. المنهجية: تصميم خوارزميات بتعقيد متعدد الحدود له قيمة استرشادية لمشاكل نظرية الترميز الأخرى

السيناريوهات المطبقة

  1. تصميم أنظمة الاتصالات: سيناريوهات 5G NR والاتصالات الفضائية التي تتطلب أكواد قطبية متوافقة مع المعدل
  2. تحليل الأداء: التطبيقات التي تتطلب التنبؤ السريع والدقيق بأداء أكواد القطبية
  3. تحسين الكود: بناء وتحسين معاملات أكواد القطبية بناءً على طيف الوزن

المراجع

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