رمز جاستيسن

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 60 صور
الموسوعة الحرة

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

قبل اكتشاف رمز تصحيح الأخطاء الخاص بـ Justesen، لم يكن معروفًا وجود أي رمز تصحيح أخطاء يحتوي على جميع هذه المعلمات الثلاث كثوابت.

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

تُشتق رموز جوستيسن من خلال دمج رموز ريد -سولومون ومجموعة ووزنكرافت .

تحقق رموز ريد-سولومون المستخدمة معدلًا ثابتًا ومسافة نسبية ثابتة على حساب حجم أبجدي خطي في طول الرسالة.

مجموعة Wozencraft هي عائلة من الرموز التي تحقق معدلًا ثابتًا وحجم أبجدية ثابت، لكن المسافة النسبية ثابتة فقط بالنسبة لمعظم الرموز في هذه العائلة.

يقوم ربط الرمزين أولاً بتشفير الرسالة باستخدام رمز ريد-سولومون، ثم يقوم بتشفير كل رمز من رموز الكلمة المشفرة باستخدام رمز من مجموعة Wozencraft - باستخدام رمز مختلف من المجموعة في كل موضع من الكلمة المشفرة.

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

تعريف

رمز جوستيسن هو عبارة عن سلسلة من(شمال،ك،د)qك{\displaystyle (N,K,D)_{q^{k}}}الكود الخارجيجouت{\displaystyle C_{out}}ومختلفة(ن،ك،د)q{\displaystyle (n,k,d)_{q}}الرموز الداخليةجأنانأنا{\displaystyle C_{in}^{i}}، ل1≤أنا≤شمال{\displaystyle 1\leq i\leq N}.

وبشكل أدق، فإن تسلسل هذه الرموز، المشار إليه بـجouت∘(جأنان1،...،جأنانشمال){\displaystyle C_{out}\circ (C_{in}^{1},...,C_{in}^{N})}يتم تعريفها على النحو التالي. بالنظر إلى رسالةم∈[qك]ك{\displaystyle m\in [q^{k}]^{K}}، نقوم بحساب الكلمة المشفرة الناتجة عن رمز خارجيجouت{\displaystyle C_{out}}:جouت(م)=(ج1،ج2،..،جشمال){\displaystyle C_{out}(m)=(c_{1},c_{2},..,c_{N})}.

ثم نطبق كل رمز من الرموز الداخلية الخطية N على كل إحداثية من إحداثيات كلمة الرمز هذه لإنتاج كلمة الرمز النهائية؛ أي،جouت∘(جأنان1،..،جأنانشمال)(م)=(جأنان1(ج1)،جأنان2(ج2)،..،جأنانشمال(جشمال)){\displaystyle C_{out}\circ (C_{in}^{1},..,C_{in}^{N})(m)=(C_{in}^{1}(c_{1}),C_{in}^{2}(c_{2}),..,C_{in}^{N}(c_{N}))}.

بالرجوع إلى تعريف الشفرة الخارجية والشفرات الداخلية الخطية، يصبح تعريف شفرة جوستيسن منطقيًا لأن كلمة الشفرة الخارجية عبارة عن متجه ذيشمال{\displaystyle N}العناصر، ولديناشمال{\displaystyle N}الرموز الداخلية الخطية التي يجب تطبيقها على تلكشمال{\displaystyle N}عناصر.

هنا بالنسبة لرمز جوستيسن، الرمز الخارجيجouت{\displaystyle C_{out}}يتم اختيارها لتكون رمز ريد سولومون على حقلFqك{\displaystyle \mathbb {F} _{q^{k}}}تم تقييمها على مدىFqك-{0}{\displaystyle \mathbb {F} _{q^{k}}-\{0\}}معدل​R{\displaystyle R}،0{\displaystyle 0}<R{\displaystyle R}<1{\displaystyle 1}.

الكود الخارجيجouت{\displaystyle C_{out}}المسافة النسبيةدلتاouت=1-R{\displaystyle \delta _{out}=1-R}وطول الكتلةشمال=qك-1{\displaystyle N=q^{k}-1}مجموعة الرموز الداخلية هي مجموعة Wozencraft{جأنانα}α∈Fqك*{\displaystyle \{C_{in}^{\alpha }\}_{\alpha \in \mathbb {F} _{q^{k}}^{*}}}.

ملكية رمز جاستيسن

بما أن الرموز الخطية في مجموعة وونزنكرافت لها المعدل12{\displaystyle {\frac {1}{2}}}، رمز جاستيسن هو الرمز المتسلسلج*=جouت∘(جأنان1،جأنان2،..،جأنانشمال){\displaystyle C^{*}=C_{out}\circ (C_{in}^{1},C_{in}^{2},..,C_{in}^{N})}بالمعدلR2{\displaystyle {\frac {R}{2}}}لدينا النظرية التالية التي تُقدّر المسافة بين الرموز المتسلسلةج*{\displaystyle C^{*}}.

نظرية

يتركε>0.{\displaystyle \varepsilon >0.}ثمج*{\displaystyle C^{*}}تبلغ المسافة النسبية على الأقل(1-R-ε)حq-1(12-ε).{\displaystyle (1-R-\varepsilon )H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right).}

دليل

من أجل إثبات الحد الأدنى لمسافة رمز ماج*{\displaystyle C^{*}}نثبت أن مسافة هامينغ لزوج من الكلمات المشفرة المختلفة لها حد أدنى. لذا، لنفترضΔ(ج1،ج2){\displaystyle \Delta (c^{1},c^{2})}ليكن مسافة هامينغ بين كلمتين مشفرتينج1{\displaystyle c^{1}}وج2{\displaystyle c^{2}}. لأي شيء معين

م1≠م2∈(Fqك)ك،{\displaystyle m_{1}\neq m_{2}\in \left(\mathbb {F} _{q^{k}}\right)^{K},}

نريد حدًا أدنى لـΔ(ج*(م1)،ج*(م2)).{\displaystyle \Delta (C^{*}(m_{1}),C^{*}(m_{2})).}

لاحظ أنه إذاجouت(م)=(ج1،⋯،جشمال){\displaystyle C_{out}(m)=(c_{1},\cdots ,c_{N})}، ثمج*(م)=(جأنان1(ج1)،⋯،جأنانشمال(جشمال)){\displaystyle C^{*}(m)=(C_{in}^{1}(c_{1}),\cdots ,C_{in}^{N}(c_{N}))}لذا بالنسبة للحد الأدنىΔ(ج*(م1)،ج*(م2)){\displaystyle \Delta (C^{*}(m_{1}),C^{*}(m_{2}))}، نحتاج إلى مراعاة مسافةجأنان1،⋯،جأنانشمال.{\displaystyle C_{in}^{1},\cdots ,C_{in}^{N}.}

يفترض

جouت(م1)=(ج11،⋯،جشمال1)جouت(م2)=(ج12،⋯،جشمال2){\displaystyle {\begin{aligned}C_{out}(m_{1})&=\left(c_{1}^{1},\cdots ,c_{N}^{1}\right)\\C_{out}(m_{2})&=\left(c_{1}^{2},\cdots ,c_{N}^{2}\right)\end{aligned}}}

تذكر أن{جأنان1،⋯،جأنانشمال}{\displaystyle \left\{C_{in}^{1},\cdots ,C_{in}^{N}\right\}}هي مجموعة ووزنكرافت . وبسبب "نظرية مجموعة ووزنكرافت"، يوجد على الأقل(1-ε)شمال{\displaystyle (1-\varepsilon )N}الرموز الخطيةجأنانأنا{\displaystyle C_{in}^{i}}التي لها مسافةحq-1(12-ε)⋅2ك.{\displaystyle H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}لذا إذا كان الأمر يتعلق ببعض1⩽أنا⩽شمال،جأنا1≠جأنا2{\displaystyle 1\leqslant i\leqslant N,c_{i}^{1}\neq c_{i}^{2}}والرمزجأنانأنا{\displaystyle C_{in}^{i}}المسافة⩾حq-1(12-ε)⋅2ك،{\displaystyle \geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k,}ثم

Δ(جأنانأنا(جأنا1)،جأنانأنا(جأنا2))⩾حq-1(12-ε)⋅2ك.{\displaystyle \Delta \left(C_{in}^{i}\left(c_{i}^{1}\right),C_{in}^{i}\left(c_{i}^{2}\right)\right)\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}

علاوة على ذلك، إذا كان لديناتي{\displaystyle T}أرقام1⩽أنا⩽شمال{\displaystyle 1\leqslant i\leqslant N}بحيثجأنا1≠جأنا2{\displaystyle c_{i}^{1}\neq c_{i}^{2}}والرمزجأنانأنا{\displaystyle C_{in}^{i}}المسافة⩾حq-1(12-ε)⋅2ك،{\displaystyle \geqslant H_{q}^{-1}({\tfrac {1}{2}}-\varepsilon )\cdot 2k,}ثم

Δ(ج*(م1)،ج*(م2))⩾حq-1(12-ε)⋅2ك⋅تي.{\displaystyle \Delta \left(C^{*}(m_{1}),C^{*}(m_{2})\right)\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot T.}

والآن تتمثل المهمة الأخيرة في إيجاد حد أدنى لـتي{\displaystyle T}. يُعرِّف:

S={أنا : 1⩽أنا⩽شمال،جأنا1≠جأنا2}.{\displaystyle S=\left\{i\ :\ 1\leqslant i\leqslant N,c_{i}^{1}\neq c_{i}^{2}\right\}.}

ثمتي{\displaystyle T}عدد الرموز الخطيةجأنانأنا،أنا∈S{\displaystyle C_{in}^{i},i\in S}وجود المسافةحq-1(12-ε)⋅2ك.{\displaystyle H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}

والآن نريد أن نقدّر|S|.{\displaystyle |S|.}بوضوح|S|=Δ(جouت(م1)،جouت(م2))⩾(1-R)شمال{\displaystyle |S|=\Delta (C_{out}(m_{1}),C_{out}(m_{2}))\geqslant (1-R)N}.

بسبب نظرية مجموعة ووزنكرافت ، يوجد على الأكثرεشمال{\displaystyle \varepsilon N}الرموز الخطية التي تقل مسافتها عنحq-1(12-ε)⋅2ك،{\displaystyle H_{q}^{-1}({\tfrac {1}{2}}-\varepsilon )\cdot 2k,}لذا

تي⩾|S|-εشمال⩾(1-R)شمال-εشمال=(1-R-ε)شمال.{\displaystyle T\geqslant |S|-\varepsilon N\geqslant (1-R)N-\varepsilon N=(1-R-\varepsilon )N.}

وأخيراً، لدينا

Δ(ج*(م1)،ج*(م2))⩾حq-1(12-ε)⋅2ك⋅تي⩾حq-1(12-ε)⋅2ك⋅(1-R-ε)⋅شمال.{\displaystyle \Delta (C^{*}(m_{1}),C^{*}(m_{2}))\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot T\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot (1-R-\varepsilon )\cdot N.}

وينطبق هذا على أي شيء عشوائيم1≠م2{\displaystyle m_{1}\neq m_{2}}. لذاج*{\displaystyle C^{*}}يتمتع بالمسافة النسبية على الأقل(1-R-ε)حq-1(12-ε)،{\displaystyle (1-R-\varepsilon )H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right),}وهذا يكمل البرهان.

تعليقات

نريد أن ندرس "الرمز الصريح للغاية". لذا، السؤال هو: ما هو "الرمز الصريح للغاية"؟ بشكل عام، بالنسبة للرمز الخطي، ترتبط خاصية "الصراحة" بتعقيد بناء مصفوفة المولد G الخاصة به.

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

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

إذن، يتضح لنا حتى الآن أن ترميز وونزنكرافت وريد-سولومون واضحان للغاية. وبالتالي، نصل إلى النتيجة التالية:

النتيجة: الكود المتسلسلج*{\displaystyle C^{*}}هو رمز جيد تقاربياً (أي معدلR{\displaystyle R}> 0 والمسافة النسبيةدلتا{\displaystyle \delta }> 0 لـ q الصغيرة) وله بناء صريح للغاية.

مثال على رمز جوستيسن

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

ليكن R رمز ريد-سولومون بطول N = 2 m − 1، ورتبة K ، ووزن أدنى N − K + 1.      

رموز R هي عناصر من F = GF(2 m ) ويتم الحصول على الكلمات المشفرة عن طريق أخذ كل متعدد حدود ƒ على F من الدرجة الأقل من K وإدراج قيم ƒ على العناصر غير الصفرية من F بترتيب محدد مسبقًا.

ليكن α عنصرًا أوليًا من F. بالنسبة لكلمة رمزية a = ( a₁ , ..., aₙ ) من R ، ليكن b متجهًا طوله 2N على F معطى بالعلاقة التالية :  

ب=(أ1،أ1،أ2،α1أ2،...،أشمال،αشمال-1أشمال){\displaystyle \mathbf {b} =\left(a_{1},a_{1},a_{2},\alpha ^{1}a_{2},\ldots ,a_{N},\alpha ^{N-1}a_{N}\right)}

ولنفترض أن c هو متجه طوله 2Nm تم الحصول عليه من b عن طريق التعبير عن كل عنصر من F كمتجه ثنائي طوله m . شفرة جوستيسن هي الشفرة الخطية التي تحتوي على جميع هذه المتجهات c .

تتضمن معلمات هذا الكود الطول 2 م N ، والبعد م K ، والمسافة الدنيا على الأقل

∑أنا=1ℓأنا(2مأنا)،{\displaystyle \sum _{i=1}^{\ell }i{\binom {2m}{i}},}

أينℓ{\displaystyle \ell }هو أكبر عدد صحيح مُرضٍ∑أنا=1ℓ(2مأنا)≤شمال-ك+1{\displaystyle \sum _{i=1}^{\ell }{\binom {2m}{i}}\leq N-K+1}(انظر MacWilliams/MacWilliams للاطلاع على الدليل.)

انظر أيضاً

مراجع