Constructing linear codes from digraphs and groups

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

لبناء هذه الأكواد، غالباً ما يستخدم العلماء أداتين قويتين: الزمر (Groups) (وهي تشبه كتب القواعد للتماثل، حيث تخبرك كيف تعيد ترتيب الأشياء دون كسر النمط) والرسوم البيانية (Graphs) (وهي مجرد خرائط من النقاط المتصلة بخطوط). أحد أنواع الخرائط الشهيرة يسمى رسم كايلي البياني (Cayley graph)، ويتم بناؤه باتباع مجموعة محددة من القواعد من زمرة معينة. في عام 2012، اكتشف الباحثون أن استخدام هذه الخرائط الخاصة يمكن أن ينتج نوعاً جديداً من الأكواد فائقة الكفاءة. لكن كانت هناك عقبة: هذه الخرائط بُنيت بناءً على قواعد صارمة جداً، مما حد من أنواع الأكواد التي يمكنك صنعها. كان الأمر يشبه امتلاك وصفة رائعة، لكن لا يُسمح لك باستخدام مكونات إلا من علامة تجارية واحدة محددة.

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

المخطط الجديد: من القواعد الصارمة إلى الخرائط المرنة

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

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

أدرك المؤلفان أنه إذا كانت الخريطة تمتلك خاصية "التشابه" هذه، فلا داعي لأن تكون رسم كايلي بياني لبناء كود رائع. وهذا أدى إلى اختراعين رئيسيين لهما:

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

قواعد اللعبة

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

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

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

لعبة الأرقام: ما مدى جودتها؟

لم يتوقف المؤلفان عند الجانب النظري؛ بل حسبوا مدى جودة هذه الأكواد فعلياً. لقد نظروا إلى إحصائيتين رئيسيتين:

• المعدل (Rate): مقدار المعلومات المفيدة التي يمكنك إرسالها مقارنة بالحجم الإجمالي للرسالة.
• المسافة النسبية (Relative Distance): عدد الأخطاء التي يمكن للكود إصلاحها.

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

ولإثبات نجاح ذلك في العالم الحقيقي، قاموا ببناء عائلة لانهائية من هذه الأكواد الجديدة. استخدموا نوعاً معيناً من الرسوم البيانية الموجهة بناءً على زمرة تسمى $PSL_2(q)$ (وهي زمرة من المصفوفات) ورقم أولي $p = 4093$. وأظهروا أنه بالنسبة لعدد لانهائي من الأعداد الأولية $q$، يمكنهم بناء أكواد بـ:

• معدل لا يقل عن $2/(p+1)$، وهو ما يعادل تقريباً $0.0005$.
• مسافة نسبية لا تقل عن $0.001$.

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

ما التالي؟ أسئلة مفتوحة

ينتهي البحث بتحدٍ موجه إلى مجتمع الرياضيات. لقد بنى المؤلفون جسراً إلى عالم جديد من الأكواد، ولكن لا تزال هناك مناطق غير مستكشفة. لقد طرحوا ثلاثة أسئلة محددة:

1. هل يمكننا العثور على عائلة لانهائية من الأكواد المتماثلة التي لا تُبنى من رسوم كايلي البيانية؟ (هم يشتبهون في أن الإجابة نعم، لكنهم لم يثبتوا ذلك بعد).
2. هل يمكننا العثود على عائلة لانهائية من الأكواد المتماثلة المبنية من رسوم بيانية موجهة حقيقية (proper digraphs)؟ "الرسم البياني الموجه الحقيقي" هو خريطة حيث يوجد على الأقل طريق واحد ذو اتجاه واحد (إذا كان بإمكانك الذهاب من أ إلى ب، فلا يمكنك بالضرورة العودة من ب إلى أ). هذا أمر صعب لأن معظم الخرائط المتماثلة المعروفة هي ثنائية الاتجاه.
3. هل يمكننا بناء كود متماثل يكون فيه الكود "الخارج" والكود "الداخل" مختلفين عن بعضهما البعض؟

كما أشار المؤلفون إلى أن طريقتهم يمكنها إعادة إنتاج عمليات بناء أخرى معروفة، مثل الضرب المباشر (direct product) للأكواد (دمج كودين لتكوين كود واحد كبير). في الواقع، أظهروا أن رسم بيتيرسن البياني (Peterser graph) (وهو رسم بياني محدد، غير كايلي، يحتوي على 10 نقاط) يمكن استخد يتم استخدامه لبناء كود عالي التماثل ولكنه لا يمكن بناؤه ككود كايلي. هذا مثال ملموس على تطبيق نظريتهم: كود أفضل أو مختلف عما يمكن للقواعد الصارمة القديمة إنتاجه.

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