On the equivalence between additive and linear codes

إليك ملخص تقني مفصل للورقة البحثية بعنوان "حول التكافؤ بين الأكواد الجمعية والخطية" (On the equivalence between additive and linear codes) للباحثين كانتات عبد الخاليف ودوي هو.

1. بيان المشكلة

حظيت الأكواد الجمعية (Additive codes) فوق الحقل $\mathbb{F}_{q^2}$ (تحديداً الأكواد الرباعية حيث $q=2$) باهتمام كبير لقدرتها المحتملة على التفوق على الأكواد الخطية من حيث المسافة الدنيا. ومع ذلك، يوجد غموض جوهري: غالباً ما يكون من غير الواضح ما إذا كان الكود "الجمعي الصرف" (Strictly additive) المكتشف حديثاً (والذي لا يكافئ أي كود خطي) هو كود جديد حقاً أم أنه مجرد كود خطي متخفٍ تحت تمثيل مختلف.

تعتمد الطرق الموجودة للتمييز بين الأكواد الجمعية الصرفة والأكواد الخطية بشكل كبير على التقنيات الهندسية (مثل الأقواس الزائفة والانتشارات الديسغارثية)، وهي تقنيات معقدة وغير قابلة للتطبيق عالمياً. يعالج المؤلفون السؤال المفتوح التالي: بالنظر إلى مصفوفة مولدة لكود جمعي، كيف يمكن اختبار ما إذا كان يكافئ كوداً خطياً فوق $\mathbb{F}_{q^2}$ بطريقة حتمية؟

2. المنهجية

طوّر المؤلفون إطاراً جبرياً بحتاً يعتمد على المصفوفة المولدة للكود، متجنبين الحاجة إلى البناءات الهندسية.

2.1 الإطار الرياضي

• التمثيل: يُنظر إلى الكود الجمعي $C \subseteq \mathbb{F}_{q^2}^n$ كفضاء جزئي خطي فوق $\mathbb{F}_q$ ببعد $k$ في $\mathbb{F}_{q^2}^n$. تقوم الدالة $\phi: \mathbb{F}_{q^2}^n \to \mathbb{F}_q^{2n}$ بتحويل الكود إلى فضاء جزئي خطي فوق $\mathbb{F}_q$.
• تعريف التكافؤ: يكون الكودان متكافئين مونوميالياً (Monomially equivalent) إذا أمكن تحويل أحدهما إلى الآخر عبر تبديل الإحداثيات والضرب في مصفوفات $2 \times 2$ قابلة للعكس ($A_i \in GL_2(\mathbb{F}_q)$) تعمل على أزواج الإحداثيات.
• التمثيل المنتظم: يستخدم المؤلفون التمثيل المنتظم للحقل $\mathbb{F}_{q^2}$. ليكن $\omega$ عنصراً أولياً مع كثير حدود أدنى $x^2 + c_1x + c_0$. الضرب في $\omega$ يقابل مصفوفة مرافقة $M_\omega$.
• الشرط الجوهري: يكون الكود الجمعي $C$ ذو المصفوفة المولدة $G$ مكافئاً لكود خطي إذا وفقط إذا وُجدت مصفوفة قابلة للعكس $R \in GL_k(\mathbb{F}_q)$ ومصفوفة قطرية كتلية $A = \text{diag}(A_1, \dots, A_n)$ بحيث:
  $$RG = G(AM_\omega A^{-1})$$
  تعني هذه المعادلة أن الكود مغلق تحت الضرب القياسي بـ $\omega$ (ضمن حدود التكافؤ).

2.2 الخوارزمية الحتمية (الخوارزمية 1)

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

1. فحص الرتبة (Rank Check):

   • تقسيم المصفوفة المولدة $G$ إلى $n$ من الأعمدة الكتلية $G_i$ بحجم $k \times 2$.
   • إذا كانت أي $G_i$ هي المصفوفة الصفرية، يتم ثقب (Puncture) هذا الإحداثي.
   • مبرهنة 3.2: إذا كانت أي من الكتل المتبقية $G_i$ ذات رتبة 1، فإن الكود هو جمعي صرف (ليس مكافئاً لكود خطي). وذلك لأن أي تحويل خطي يحافظ على فضاء جزئي أحادي البعد يجب أن يمتلك قيمة ذاتية في $\mathbb{F}_q$، بينما التحويل المطلوب $R$ لكود خطي يجب ألا يمتلك قيم ذاتية في $\mathbb{F}_q$.

2. اختبار الفراغ (Nullity Test):

   • إنشاء نظام خطي كبير $S\mathbf{x} = 0$ مشتق من الشرط $RG_i = G_i T_i$ (حيث $T_i$ مرافقة لـ $M_\omega$).
   • حساب الفراغ (Nullity) (بعد الفضاء الصفري) للمصفوفة $S$، ويُرمز له بـ $d$.
   • مبرهنة 3.3: إذا كان $d$ فردياً، فإن الكود جمعي صرف. يعتمد الإثبات على حقيقة أنه لو كان الكود خطياً، لكان الفضاء الحل لـ $R$ يشكل حقلاً متماثلاً مع $\mathbb{F}_{q^2}$، مما يعني أن البعد يجب أن يكون زوجياً.

3. البحث في الفضاء الصفري:

   • إذا كان الفراغ زوجياً ولم توجد كتل برتبة 1، تبحث الخوارزمية في الفضاء الصفري لـ $S$ عن مصفوفة $R$ صالحة تحقق شرط التكافؤ.

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

1. التوصيف الجبري: تقدم الورقة أول اختبار حتمي وجبري (المبرهنة 3.1) لتحديد ما إذا كان الكود الجمعي مكافئاً لكود خطي، باستخدام المصفوفة المولدة فقط.
2. الشروط الضرورية:
   • شرط القيمة الذاتية (المبرهنة 3.2): إذا كانت كتلة المولد ذات رتبة 1، فلا يمكن أن يكون الكود خطياً.
   • شرط الزوجية (المبرهنة 3.3): إذا كان فراغ المصفوفة $S$ فردياً، فلا يمكن أن يكون الكود خطياً.
3. القابلية العامة للتطبيق: بخلاف الطرق الهندسية السابقة، ينطبق هذا النهج على أي كود جمعي وهو فعال حسابياً باستخدام أدوات الجبر الخطي القياسية (تم تنفيذه هنا باستخدام MAGMA).

4. النتائج والتطبيقات

طبق المؤلفون خوارزميتهم للتحقق من عدة مجموعات من الأكواد الواردة في الأدبيات الحديثة:

• الأكواد الجمعية الرباعية من [14]:

  • اختبروا الأكواد من الجدول II لـ Guan et al. [14].
  • النتيجة: جميع الأكواد المختبرة (بما في ذلك النسخ الممتدة والمزيدة) كانت تمتلك فراغاً فردياً للمصفوفة $S$.
  • الاستنتاج: هذه الأكواد جمعية صرفة وليست مكافئة لأي كود خطي. وهذا يحل الغموض حول ما إذا كانت هذه الأكود عالية الأداء هي مجرد أكواد خطية متخفية.

• أكواد المتمم المزدوج الجمعي (ACD Codes):

  • الحالة 1 (جمعية صرفة): اختبروا أكواد ACD من [14, Table IV] و [18, Table 2].
    • تأكد أن الأكواد من [18] (بناء مجموع Plotkin) هي جمعية صرفة.
    • تأكد أن الأكود من [14, Table IV] (الأسطر 5، 6، 10) هي جمعية صرفة عبر اختبار الفراغ.
  • الحالة 2 (مكافئة لخطية):
    • حللوا كود ACD من [14, Table IV, Line 1] بمعاملات $[22, 10, 9]_2^2$.
    • كان اختبار الفراغ غير حاسم (الفراغ = 2، وهو زوجي).
    • من خلال حل النظام، وجدوا مصفوفة تحويل $A$ تثبت أن هذا الكود مكافئ لكود هيرميتي LCD خطي بمعاملات $[22, 10, 9]_4$.
    • الأهمية: هذا الاكتشاف يحسن أفضل الحدود المعروفة للأكواد الخطية الهيرميتية LCD، مما يظهر أن بناءً "جمعياً" يمكن أن ينتج كوداً خطياً متفوقاً.

5. الأهمية

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

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