🔢 mathematics

New bounds for codes over Gaussian integers based on the Mannheim distance

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

المؤلفون الأصليون: Minjia Shi, Xuan Wang, Junmin An, Jon-Lark Kim

نُشر 2026-03-27

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

CC BY 4.0

المؤلفون الأصليون: Minjia Shi, Xuan Wang, Junmin An, Jon-Lark Kim

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

تخيل أنك تدير خدمة توصيل ضخمة وعالية السرعة في مدينة لا تشبه شبكة من الشوارع، بل تبدو كلوحة شطرنج لانهائية مكونة من أعداد مركبة. هذا هو عالم الأعداد الغاوسية الصحيحة (Gaussian Integers).

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

لكن التكنولوجيا الحديثة (مثل الواي فاي أو الـ 4G/5G) ترسل البيانات بطريقة تسمح لها بالتحرك قطرياً أيضاً. الأمر يشبه إمكانية رمي الطرد باتجاه الشمال الشرقي أو الجنوب الغربي. طريقة "مانهاتن" القديمة سيئة جداً في قياس الأخطاء في هذا العالم القطري. إنها تشبه محاولة قياس المسافة بين نقطتين على خريت باستخدام مسطرة لا يمكنها إلا التحرك للأعلى والأسفل فقط.

هذه الورقة البحثية تدور حول ابتكار مسطرة جديدة تسمى مسافة مانهيم (Mannheim Distance) تعمل بشكل مثالي لهذا العالم القطري ثنائي الأبعاد، ثم استخدام هذه المسطرة لبناء أنظمة توصيل أكثر موثوقية (أكواد تصحيح الخطأ).

إليك تفصيل لما قام به الباحثون، باستخدام تشبيهات بسيطة:

1. المسطرة الجديدة: مسافة مانهيم

تخيل مسافة مانهيم كأنها "تعرفة تاكسي" في مدينة يمكنك فيها القيادة بشكل قطري.

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

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

2. تعبئة الكرات (حد تعبئة الكرات - The Sphere Packing Bound)

تخيل أنك تحاول تعبئة برتقالات (رسائل البيانات) في صندوق ضخم (قناة الاتصال).

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

3. نظام التوصيل "المثالي"

الكود المثالي (Perfect Code) هو "الكأس المقدسة" في عالم التوصيل. معناه أنك قمت بتعبئة البرتقالات بإحكام شديد بحيث لا توجد أي مساحة ضائعة في الصندوق، ومع ذلك لا تتلامس.

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

4. الأكواد ذاتية الثنائية (Self-Dual Codes) (الصورة المرآتية)

تخيل كوداً هو صورة مرآتية لنفسه. إذا قلبت البيانات، تبدو تماماً كما هي. هذه هي الأكواد ذاتية الثنائية (Self-Dual Codes). وهي مميزة لأنها متماثلة جداً وغالباً ما تكون قوية جداً.

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

5. وحدة فك التشفير (نظام تحديد المواقع للأخطاء - The Decoder)

أخيراً، قاموا ببناء نظام تحديد مواقع (GPS) لهذا النظام الجديد.

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

ملخص: لماذا يهم هذا الأمر؟

نحن نعيش في عالم من تقنية QAM (تعديل السعة التربيعي)، وهي التكنولوجيا التي تقف وراء الواي فاي، والـ 4G، والتلفزيون الرقمي. هذه التكنولوجيا ترسل البيانات في شبكة ثنائية الأبعاد (قطرية).

الرياضيات القديمة: عاملت هذه الشبكة ثنائية الأبعاد كأنها شارع أحادي البعد. لقد أهدرت المساحة ولم تستطع إصلاح أنواع معينة من الأخطاء.
هذه الورقة البحثية: تقدم الرياضيات الصحيحة للشبكة ثنائية الأبعاد. فهي تخبر المهندسين بالضبط كمية البيانات التي يمكنهم حشرها في إشارة وكيفية إصلاح الأخطاء التي كان من المستحيل تصحيحها سابقاً.

باختة، أخذ المؤلفون مشكلة رياضية مجردة ومعقدة وأعطونا خريطة أفضل ومسطرة أفضل للطرق الرقمية في المستقبل.

فيما يلي ملخص تقني مفصل للورقة البحثية بعنوان "حدود جديدة للأكواد فوق الأعداد الغاوسية بناءً على مسافة مانهايم" (New bounds for codes over Gaussian integers based on the Mannheim distance).

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

تركز نظرية الترميز الكلاسيكية بشكل أساسي على الأكواد فوق الحقول المنتهية باستخدام مسافة هامينج (Hamming distance). ومع ذلك، فإن مسافة هامينج (ومسافة لي المرتبطة بها) لا تناسب إشارات تعديل السعة التربيعي (QAM)، المنتشرة في أنظمة الاتصالات الحديثة (مثل LTE وWi-Fi وHSDPA). حيث توجد كوكبات QAM في فضاء إشارة ثنائي الأبعاد حيث تظهر الأخطاء كإزاحات في كل من المكونات الحقيقية والخيالية.

ولمعالجة ذلك، قدم "هوبر" أكواداً فوق الأعداد الغاوسية الصحيحة ( $\mathbb{Z}[i]$ ) المزودة بـ مسافة مانهايم. وبينما تم إجراء عمل كبير على بناء مثل هذه الأكواد (مثل أكواد OMEC، والأكواد الكمومية، والأكواد ذاتية الثنائية)، إلا أن هناك نقصاً في الدراسات النظرية الشاملة حول الحد الأدنى لمسافة مانهايم والدراسة المنهجية للأكواد المثلى التي تستوفي هذه الحدود. تهدف هذه الورقة إلى سد هذه الفجوة من خلال وضع نظائر لمتطلبات مسافة مانهايم للحدود الكلاسيكية واستقصاء وجود الأكواد المثلى.

2. المنهجية

يستخدم المؤلفون مزيجاً من نظرية الأعداد الجبرية، والحصر التوليفي، والجبر الخطي لاستخلاص الحدود وبناء الأكواد.

الإطار الجبري: تركز الدراسة على الأكواد الخطية فوق حلقة القسمة $G_\pi = \mathbb{Z}[i]/(\pi)$ $G_{π} = Z [i] / (π)$ ، حيث $\pi$ $π$ هو عدد غاوسي أولي.
- بالنسبة لـ $p \equiv 3 \pmod 4$ ، تكون الحلقة متماثلة مع $\mathbb{F}_{p^2}$ .
- بالنسبة لـ $p \equiv 1 \pmod 4$ ، تكون الحلقة متماثلة مع $\mathbb{F}_p$ .
تحليل المتريات: يُعرَّف وزن مانهايم لعنصر $\alpha \in G_\pi$ كـ $wt_\pi(\alpha) = |a| + |b|$ ، حيث $a+bi $هو الممثل الذي يقلل هذا المجموع. المسافة هي$ d_\pi(x, y) = wt_\pi(x-y)$.
تفكيك المجموعات الجزئية (Coset Decomposition): يستخدم المؤلفون تفكيك المجموعة الضربية $\mathbb{F}_p^*$ إلى مجموعات جزئية من المجموعة الفرعية $H = \{\pm 1, \pm \gamma\}$ (حيث $\gamma$ هو جذر رابع أولي). يسمح هذا بتصنيف العناصر حسب أوزان مانهايم الخاصة بها.
حصر كرات التعبئة (Sphere Packing & Enumeration): يستنتجون صيغة صريحة لحجم كرات مانهايم ( $V_\pi(s, n)$ ) لوضع حدود حصر الكرات.
متطابقة ماكدويل (MacWilliams Identity): تُستخدم نسخة من متطابقة ماكدويل خاصة بمانهايم لتحليل الأكواد ذاتية الثنائية، مما يربط مُعدد وزن الكود بوزن نظيره (dual).
استيفاء القيود: لإيجيد الحدود العليا للأكواد ذاتية الثنائية، يصيغ المؤلفون نظاماً من المعادلات الخطية مع قيود الأعداد الصحيحة غير السالبة على عدد الكلمات البرمجية ذات التكوينات المحددة (توزيعات المجموعات الجزئية).

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

أ. حجم كرات مانهايم وحد الحصر (Sphere Packing Bound)

تستنتج الورقة صيغة صريحة لعدد المتجهات ذات وزن مانهايم معين.

النتيجة: يتم وضع نسخة من حد حصر الكرات لمسافة مانهايم: $|C| \cdot V_\pi(e, n) \le p^n$ ، حيث $e = \lfloor (d_\pi - 1)/2 \rfloor$ .
الآثار المترتبة: يؤدي هذا إلى شروط ضرورية لوجود الأكواد المثالية (الأكواد التي تحقق الحد بالتساوي).
الأكواد المثالية لتصحيح خطأين: يثبت المؤلفون أنه إذا وجد كود مثالي لتصحيح خطأين فوق $G_\pi$ $G_{π}$ ، فيجب أن يحقق حجم الحقل $p^r = 8n^2 + 4n + 1$ $p^{r} = 8 n^{2} + 4 n + 1$ . ويظهرون أن الحلول الصحيحة الموجبة توجد فقط لـ $r=1$ $r = 1$ و $r=2$ $r = 2$ .
- تم تحديد أصغر المعاملات المرشحة كـ $[n, k, d_\pi] = [10, 8, 5]$ فوق $\mathbb{F}_{29}$ .

ب. حدود عامة لمعاملات الكود

يضع المؤلفون عدة حدود جديدة للأكواد الخطية فوق $G_\pi$ (تحديداً عندما $p \equiv 1 \pmod 4$ ):

العلاقة مع مسافة هامينج: يثبتون أن $d_\pi(n, k) \le \frac{4S(a,b)}{p-1} d_H(n, k)$ ، حيث $S(a,b)$ هو ثابت مشتق من مجموع أوزان مانهايم لقادة المجموعات الجزئية (coset leaders).
الإحكام (Tightness): يعرضون عائلات من الأكواد (بما في ذلك أكواد Simplex) التي تستوفي هذه الحدود، مما يثبت أنها محكمة لمعاملات محددة.
القيم المحددة: يتم اشتقاق صيغ صريحة لـ $d_\pi(n, 1)$ و $d_\pi(n, n-1)$ لبريمات محددة (مثل $\pi = 2+3i$ و $\pi = 1+4i$ ).

ج. الأكواد ذاتية الثنائية (Self-Dual Codes)

يُخصص جزء كبير من الورقة للأكواد ذاتية الثنائية فوق $\mathbb{F}_{13}$ و $\mathbb{F}_{17}$ (باعتبارها حلقات أعداد غاوسية صحيحة).

الحدود العليا: باستخدام متطابقة ماكدويل وتقنيات البرمجة الخطية (الحل من أجل حلول الأعداد الصحيحة غير السالبة لمعادلات مُعدد الوزن)، يستنتجون حدوداً عليا للمسافة الدنيا لمانهايم $d_\pi^{SD}(n)$ .
الأكواد المثلى: يقومون ببناء وتصنيف الأكواد ذاتية الثنائية المثلى للأطوال $n \le 14$ $n \leq 14$ .
- بالنسبة لـ $n=8$ فوق $\mathbb{F}_{13}$ ، فإن أقصى $d_\pi$ هو 6.
- بالنسبة لـ $n=8$ فوق $\mathbb{F}_{17}$ ، فإن أقصى $d_\pi$ هو 7.
الارتباط بـ MDS: يثبتون أنه إذا وجدت أكواد ذاتية الثنائية ذات مسافة عالية معينة (مثل $[10, 5, 9]$ فوق $\mathbb{F}_{13}$ )، فيجب أن تكون أكواداً ذات مسافة قصوى (MDS).

د. خوارماز الفك (Decoding Algorithms)

تقدم الورقة خوارزمية فك متلازمة (Syndrome Decoding Algorithm) للأكواد فوق حلقات باقٍ الأعداد الغاوسية.

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

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

وجود الأكواد المثالية: يمكن أن يوجد كود مانهايم مثالي لتصحيح خطأين فقط إذا كان $p^r = 8n^2 + 4n + 1$ . أصغر حقل كهذا هو $\mathbb{F}_{29}$ بالمعاملات $[10, 8, 5]$ .
إحكام الحدود: أظهر أن الحدود العليا المستنتجة لـ $d_\pi(n, k)$ محكمة لمعاملات محددة، لا سيالما لأكواد Simplex وبعض الأكواد ذاتية الثنائية.
تصنيف الأكواد ذاتية الثنائية: تم تقديم تصنيفات كاملة للأكود ذاتية الثنائية حتى الطول 8 فوق $\mathbb{F}_{13}$ و $\mathbb{F}_{17}$ ، مع تحديد مسافات مانهايم المثلى.
فعالية فك التشفير: تؤكد الأمثلة العددية أن مقياس مانهايم يسمح بتصحيح متجهات الخطأ التي قد تُعتبر غير قابلة للتصحيح (وزن $> \lfloor (d_H-1)/2 \rfloor$ ) بمقياس هامينج.

5. الأهمية

تطور هذه الورقة بشكل كبير الأساس النظري للترميز فوق الأعداد الغاوسية.

الدقة النظرية: إنها تتجاوز البناءات الارتجالية لتقديم حدود صارمة (حصر الكرات، تشبه حدود Singleton، وقائمة على MacWilliams) لمقياس مانهايم.
الصلة العملية: من خلال إثبات أن فك التشفير القائم على مانهايم يمكنه تصحيح الأخطاء التي لا يستطيع فك التشفير القائم على هامينج تصحيحها، تصادق الورقة على استخدام أكواد الأعداد الغاوسية الصحيحة لمخططات التعديل ثنائية الأبعاد الحديثة مثل QAM.
التحسين (Optimization): يوفر تحديد الأكود ذاتية الثنائية المثلى وشروط الأكود المثالية خارطة طريق لتصميم أكواد فعالة لتصحيح الأخطاء في أنظمة الاتصالات عالية السرعة.
التنفيذ الخوارزمي: يجسّر تضمين خوارماز الفك ومصفوفات المولد الصريحة للأكود المثلى الفجوة بين الحدود النظرية والتنفيذ العملي.

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