رمز التغطية

في نظرية الترميز ، يكون رمز التغطية عبارة عن مجموعة من العناصر (تسمى كلمات الترميز ) في فضاء ما، مع خاصية أن كل عنصر من عناصر الفضاء يقع ضمن مسافة ثابتة من كلمة ترميز معينة.

يترك${\displaystyle q\geq 2}$،${\displaystyle n\geq 1}$،${\displaystyle R\geq 0}$أن تكون أعدادًا صحيحة . رمز${\displaystyle C\subseteq Q^{n}}$يُطلق على رمز التغطية R ذي الطول n على الأبجدية Q التي حجمها | Q | = q اسم q -ary R -covering code إذا كان لكل كلمة${\displaystyle y\in Q^{n}}$هناك كلمة سرية${\displaystyle x\in C}$ بحيث تكون مسافة هامينغ${\displaystyle d_{H}(x,y)\leq R}$بمعنى آخر، يجب أن تستنفد الكرات (أو المجالات الكروية أو مجالات الرخ) ذات نصف القطر R بالنسبة لمقياس هامينغ حول الكلمات المشفرة لـ C فضاء المقياس المحدود${\displaystyle Q^{n}}$نصف قطر تغطية الشفرة C هو أصغر قيمة لـ R بحيث تكون C شفرة تغطية من الرتبة R. كل شفرة مثالية هي شفرة تغطية ذات حجم أدنى.

C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} هو رمز تغطية ثنائي من النوع 5 بطول 4. ^{[ 1 ]}

تحديد الحد الأدنى للحجم${\displaystyle K_{q}(n,R)}$يُعدّ حساب قيمة رمز تغطية R من الرتبة q بطول n مسألةً بالغة الصعوبة. في كثير من الحالات، لا يُعرف سوى حدّين أعلى وأدنى، مع وجود فجوة كبيرة بينهما. كل بناء لرمز التغطية يُعطي حدًّا أعلى لـ K _q ( n , R ). تشمل الحدود الدنيا حدّ تغطية الكرة وحدود رودميتش. ${\displaystyle K_{q}(n,1)\geq q^{n-1}/(n-1)}$و${\displaystyle K_{q}(n,n-2)\geq q^{2}/(n-1)}$[ ^{2 ] ترتبط مشكلة التغطية ارتباطًا وثيقًا} بمشكلة التعبئة في${\displaystyle Q^{n}}$، أي تحديد الحجم الأقصى لرمز تصحيح الأخطاء من النوع q -ary e بطول n .

من الأمثلة الخاصة على ذلك مسألة مراهنات كرة القدم ، القائمة على مراهنات كرة القدم ، حيث يتمثل الهدف في ابتكار نظام مراهنة على n مباراة كرة قدم، بحيث لا يتجاوز عدد "الخسائر" فيه R بغض النظر عن النتيجة . وبالتالي، بالنسبة لـ n مباراة مع "خسارة" واحدة على الأكثر، يُبحث عن تغطية ثلاثية، K ₃ ( n ,1 ).

لو${\displaystyle n={\tfrac {1}{2}}(3^{k}-1)}$ثم يلزم 3n - k، لذا بالنسبة ^{لـ n =} 4 و k = 2، يلزم 9؛ وبالنسبة لـ n = 13 و k = 3، يلزم 59049. ^{[ 3 ]} أفضل الحدود المعروفة حتى عام 2011 ^{[ 4 ]} هي

يسرد العمل القياسي ^{[ 5 ]} حول رموز التغطية التطبيقات التالية.

• ضغط مع تشويه
• ضغط البيانات
• أخطاء فك التشفير والمحو
• البث في شبكات الربط البيني
• مسابقات كرة القدم ^{[ 6 ]}
• ذكريات تُكتب مرة واحدة
• مباراة بيرليكامب-غيل
• ترميز الكلام
• الاتصالات الخلوية
• مجاميع المجموعات الجزئية ورسوم كايلي البيانية

• الأدبيات المتعلقة بتغطية الرموز
• حدود على${\displaystyle K_{q}(n,R)}$