Recursively Extended Permutation Codes under Chebyshev Distance

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

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

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

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

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

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

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