حد جيلبرت-فارشاموف للرموز الخطية

يرتبط حد جيلبرت-فارشاموف للرموز الخطية بحد جيلبرت-فارشاموف العام ، الذي يعطي حدًا أدنى لأقصى عدد من العناصر في رمز تصحيح الأخطاء ذي طول كتلة معين ووزن هامينغ أدنى على حقل.${\displaystyle \mathbb {F} _{q}}$يمكن ترجمة ذلك إلى بيان حول الحد الأقصى لمعدل ترميز ذي طول محدد ومسافة دنيا. يؤكد حد جيلبرت-فارشاموف للرموز الخطية وجود رموز خطية من الرتبة q لأي مسافة دنيا نسبية أقل من الحد المعطى، والتي تتميز في الوقت نفسه بمعدل عالٍ. يستخدم برهان الوجود الطريقة الاحتمالية ، وبالتالي فهو ليس برهانًا بنائيًا. يُعد حد جيلبرت-فارشاموف الأكثر شهرة من حيث المسافة النسبية للرموز على أبجديات ذات حجم أقل من 49. بالنسبة للأبجديات الأكبر، تحقق رموز الهندسة الجبرية أحيانًا توازنًا أفضل تقاربًا بين المعدل والمسافة مما يقدمه حد جيلبرت-فارشاموف. ^{[ 1 ]}

نظرية: ليكن${\displaystyle q\geqslant 2}$لكل${\displaystyle 0\leqslant \delta <1-{\tfrac {1}{q}}}$و${\displaystyle 0<\varepsilon \leqslant 1-H_{q}(\delta ),}$يوجد${\displaystyle q}$رمز خطي من الرتبة -ary بمعدل${\displaystyle R\geqslant 1-H_{q}(\delta )-\varepsilon }$والمسافة النسبية${\displaystyle \delta .}$

هنا${\displaystyle H_{q}}$هل دالة الإنتروبيا من الرتبة q معرفة على النحو التالي:

${\displaystyle H_{q}(x)=x\log _{q}(q-1)-x\log _{q}x-(1-x)\log _{q}(1-x).}$

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

دليل عالي المستوى:

لإثبات وجود الشفرة الخطية التي تستوفي تلك القيود، تُستخدم الطريقة الاحتمالية لإنشاء الشفرة الخطية العشوائية. تحديدًا، يتم اختيار الشفرة الخطية عن طريق اختيار مصفوفة مولدة.${\displaystyle G\in \mathbb {F} _{q}^{k\times n}}$والتي تمثل مدخلاتها عناصر مختارة عشوائياً من${\displaystyle \mathbb {F} _{q}}$إن أقصر مسافة هامينغ لرمز خطي تساوي أقصر وزن لكلمة رمزية غير صفرية، لذا لإثبات أن الرمز الناتج عن${\displaystyle G}$مسافة دنيا${\displaystyle d}$يكفي أن نبين أنه لأي${\displaystyle m\in \mathbb {F} _{q}^{k}\smallsetminus \left\{0\right\},\operatorname {wt} (mG)\geq d}$سنثبت أن احتمال وجود كلمة رمزية غير صفرية ذات وزن أقل من${\displaystyle d}$صغير بشكل كبير في${\displaystyle n}$ثم باستخدام الطريقة الاحتمالية، يوجد رمز خطي يحقق النظرية.

إثبات رسمي:

باستخدام الطريقة الاحتمالية، لإثبات وجود رمز خطي له مسافة هامينغ أكبر من${\displaystyle d}$سنبين أن احتمال أن تكون المسافة بين الرموز الخطية العشوائية أقل من${\displaystyle d}$صغير بشكل كبير في${\displaystyle n}$.

يتم تعريف الشفرة الخطية بواسطة مصفوفة المولد الخاصة بها ، والتي نختارها لتكون عشوائية.${\displaystyle k\times n}$مصفوفة مولدة؛ أي مصفوفة من${\displaystyle kn}$العناصر التي يتم اختيارها بشكل مستقل وموحد على مستوى المجال${\displaystyle \mathbb {F} _{q}}$.

تذكر أنه في الشفرة الخطية ، تساوي المسافة الحد الأدنى لوزن كلمة الشفرة غير الصفرية.${\displaystyle \operatorname {wt} (y)}$ليكن وزن كلمة السر${\displaystyle y}$. لذا

${\displaystyle {\begin{aligned}P&=\Pr _{{\text{random }}G}({\text{linear code generated by }}G{\text{ has distance}}<d)\\[6pt]&=\Pr _{{\text{random }}G}({\text{there exists a non-zero codeword }}y{\text{ in a linear code generated by }}G{\text{ such that }}\operatorname {wt} (y)<d)\\[6pt]&=\Pr _{{\text{random }}G}\left({\text{there exists }}0\neq m\in \mathbb {F} _{q}^{k}{\text{ such that }}\operatorname {wt} (mG)<d\right)\end{aligned}}}$

تنتج المساواة الأخيرة من التعريف: إذا كانت كلمة السر${\displaystyle y}$ينتمي إلى رمز خطي تم إنشاؤه بواسطة${\displaystyle G}$، ثم${\displaystyle y=mG}$لبعض المتجهات${\displaystyle m\in \mathbb {F} _{q}^{k}}$.

باستخدام متباينة بول ، لدينا:

${\displaystyle P\leqslant \sum _{0\neq m\in \mathbb {F} _{q}^{k}}\Pr _{{\text{random }}G}(\operatorname {wt} (mG)<d)}$

الآن بالنسبة لرسالة معينة${\displaystyle 0\neq m\in \mathbb {F} _{q}^{k},}$نريد أن نحسب

${\displaystyle W=\Pr _{{\text{random }}G}(\operatorname {wt} (mG)<d).}$

يترك${\displaystyle \Delta (m_{1},m_{2})}$لنفترض أن مسافة هامينغ تساوي رسالتين${\displaystyle m_{1}}$و${\displaystyle m_{2}}$ثم لأي رسالة${\displaystyle m}$لدينا:${\displaystyle \operatorname {wt} (m)=\Delta (0,m)}$. لذلك:

${\displaystyle W=\sum _{\{y\in \mathbb {F} _{q}^{n}|\Delta (0,y)\leqslant d-1\}}\Pr _{{\text{random }}G}(mG=y)}$

بسبب عشوائية${\displaystyle G}$،${\displaystyle mG}$هو متجه عشوائي منتظم من${\displaystyle \mathbb {F} _{q}^{n}}$. لذا

${\displaystyle \Pr _{{\text{random }}G}(mG=y)=q^{-n}}$

يترك${\displaystyle \operatorname {Vol} _{q}(r,n)}$ليكن حجم كرة هامينغ ذات نصف القطر${\displaystyle r}$ثم: ^{[ 2 ]}

${\displaystyle P\leqslant q^{k}W=q^{k}\left({\frac {\operatorname {Vol} _{q}(d-1,n)}{q^{n}}}\right)\leqslant q^{k}\left({\frac {q^{nH_{q}(\delta )}}{q^{n}}}\right)=q^{k}q^{-n(1-H_{q}(\delta ))}}$

باختيارك${\displaystyle k=(1-H_{q}(\delta )-\varepsilon )n}$تصبح المتباينة أعلاه

${\displaystyle P\leqslant q^{-\varepsilon n}}$

أخيراً${\displaystyle q^{-\varepsilon n}\ll 1}$وهو صغير أُسّيًا بالنسبة لـ n، وهذا ما كنا نريده سابقًا. ثم باستخدام الطريقة الاحتمالية، يوجد رمز خطي${\displaystyle C}$مع المسافة النسبية${\displaystyle \delta }$وقيم${\displaystyle R}$على الأقل${\displaystyle (1-H_{q}(\delta )-\varepsilon )}$وهذا يكمل البرهان.

1. إنّ بناء فارشاموف المذكور أعلاه ليس صريحًا؛ أي أنه لا يحدد الطريقة الحتمية لبناء الشفرة الخطية التي تحقق حد جيلبرت-فارشاموف. يتمثل أحد الأساليب البسيطة في البحث في جميع مصفوفات المولدات.${\displaystyle G}$من الحجم${\displaystyle kn}$في الملعب${\displaystyle \mathbb {F} _{q}}$للتحقق مما إذا كان الرمز الخطي المرتبط بـ${\displaystyle G}$يحقق مسافة هامينغ المتوقعة. يتطلب هذا البحث الشامل وقت تشغيل أُسّي في أسوأ الحالات.
2. يوجد أيضًا بناء لاس فيغاس الذي يأخذ رمزًا خطيًا عشوائيًا ويتحقق مما إذا كان لهذا الرمز مسافة هامينغ جيدة، ولكن هذا البناء لديه أيضًا وقت تشغيل أسي.
3. بالنسبة لقيم q غير الأولية الكبيرة بما فيه الكفاية، ولنطاقات معينة من المتغير δ، يتم تجاوز حد جيلبرت-فارشاموف بواسطة حد تسفاسمان-فلادوت-زينك . ^{[ 3 ]}

• حد جيلبرت-فارشاموف الناتج عن بناء جيلبرت للرمز العام
• هامينغ باوند
• الأسلوب الاحتمالي

• المحاضرة ١١: حدود جيلبرت-فارشاموف. دورة نظرية الترميز. الأستاذ أتري رودرا
• المحاضرة التاسعة: حدود حجم كرة هامينغ. دورة نظرية الترميز. الأستاذ أتري رودرا
• ملاحظات حول نظرية الترميز: حدود جيلبرت-فارشاموف. فينكاتيسان جوروسوامي