فك التشفير المعمم للمسافة الدنيا

في نظرية الترميز ، يوفر فك التشفير ذو المسافة الدنيا المعممة (GMD) خوارزمية فعالة لفك تشفير الرموز المتسلسلة ، والتي تعتمد على استخدام وحدة فك تشفير الأخطاء والمحو للرمز الخارجي .

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

• مسافة هامينغ  : بالنظر إلى متجهين${\displaystyle u,v\in \Sigma ^{n}}$مسافة هامينغ بين${\displaystyle u}$و${\displaystyle v}$، ويرمز إليه بـ${\displaystyle \Delta (u,v)}$، ويُعرَّف بأنه عدد المواضع التي${\displaystyle u}$و${\displaystyle v}$يختلف.
• المسافة الدنيا: دع${\displaystyle C\subseteq \Sigma ^{n}}$كن رمزًا . أقصر مسافة للرمز${\displaystyle C}$يُعرَّف بأنه${\displaystyle d=\min \Delta (c_{1},c_{2})}$أين${\displaystyle c_{1}\neq c_{2}\in C}$
• دمج الرموز: معطى${\displaystyle m=(m_{1},\cdots ,m_{K})\in [Q]^{K}}$لنفترض وجود رمزين نسميهما الرمز الخارجي والرمز الداخلي

${\displaystyle C_{\text{out}}=[Q]^{K}\to [Q]^{N},\qquad C_{\text{in}}:[q]^{k}\to [q]^{n},}$

ومسافاتهم هي${\displaystyle D}$و${\displaystyle d}$يمكن تحقيق الكود المتسلسل عن طريق${\displaystyle C_{\text{out}}\circ C_{\text{in}}(m)=(C_{\text{in}}(C_{\text{out}}(m)_{1}),\ldots ,C_{\text{in}}(C_{\text{out}}(m)_{N}))}$أين${\displaystyle C_{\text{out}}(m)=((C_{\text{out}}(m)_{1},\ldots ,(m)_{N})).}$وأخيراً سنأخذ${\displaystyle C_{\text{out}}}$أن يكون رمز RS ، الذي يحتوي على وحدة فك تشفير للأخطاء والمحو، و${\displaystyle K=O(\log N)}$وهذا بدوره يعني أن MLD على الكود الداخلي سيكون متعدد الحدود في${\displaystyle N}$وقت.

• فك التشفير بأقصى احتمال (MLD): MLD هي طريقة لفك تشفير رموز تصحيح الأخطاء، حيث تُخرج الكلمة المشفرة الأقرب إلى الكلمة المستلمة في مسافة هامينغ. ويُرمز إلى دالة MLD بـ${\displaystyle D_{MLD}:\Sigma ^{n}\to C}$يُعرَّف على النحو التالي. لكل${\displaystyle y\in \Sigma ^{n},D_{MLD}(y)=\arg \min _{c\in C}\Delta (c,y)}$.
• دالة كثافة الاحتمال  : توزيع احتمالي${\displaystyle \Pr }$في فضاء العينة${\displaystyle S}$هي خريطة من أحداث${\displaystyle S}$إلى أعداد حقيقية بحيث${\displaystyle \Pr[A]\geq 0}$لأي مناسبة${\displaystyle A,\Pr[S]=1}$، و${\displaystyle \Pr[A\cup B]=\Pr[A]+\Pr[B]}$لأي حدثين متنافيين${\displaystyle A}$و${\displaystyle B}$
• القيمة المتوقعة : القيمة المتوقعة لمتغير عشوائي منفصل${\displaystyle X}$يكون

${\displaystyle \mathbb {E} [X]=\sum _{x}\Pr[X=x].}$

ضع في اعتبارك الكلمة المستلمة${\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}$والتي تضررت بسبب قناة مشوشة . فيما يلي وصف الخوارزمية للحالة العامة. في هذه الخوارزمية، يمكننا فك تشفير y بمجرد تحديد موضع محو في كل موضع تالف وتشغيل خوارزمية فك تشفير الأخطاء والمحو لـ${\displaystyle C_{\text{out}}}$على المتجه الناتج.

Randomized_Decoder Given  :${\displaystyle \mathbf {y} =(y_{1},\dots ,y_{N})\in [q^{n}]^{N}}$.

1. لكل${\displaystyle 1\leq i\leq N}$، احسب${\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}$.
2. تعيين${\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{\tfrac {d}{2}})}$.
3. لكل${\displaystyle 1\leq i\leq N}$، كرر  : باحتمالية${\displaystyle 2\omega _{i} \over d}$، تعيين${\displaystyle y_{i}''\leftarrow$ ?,} وإلا يتم تعيينه${\displaystyle y_{i}''=y_{i}'}$.
4. تشغيل الأخطاء وخوارزمية المسح لـ${\displaystyle C_{\text{out}}}$على${\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}$.

النظرية 1. ليكن y كلمة مستلمة بحيث توجد كلمة رمزية${\displaystyle \mathbf {c} =(c_{1},\cdots ,c_{N})\in C_{\text{out}}\circ {C_{\text{in}}}\subseteq [q^{n}]^{N}}$بحيث${\displaystyle \Delta (\mathbf {c} ,\mathbf {y} )<{\tfrac {Dd}{2}}}$ثم تُخرج خوارزمية GMD الحتمية مخرجاتها${\displaystyle \mathbf {c} }$.

لاحظ أن خوارزمية فك التشفير البسيطة للرموز المتسلسلة يمكنها تصحيح ما يصل إلى${\displaystyle {\tfrac {Dd}{4}}}$أخطاء.

اللمة 1. لنفترض صحة الفرضية الواردة في النظرية 1. وإذا${\displaystyle \mathbf {y} ''}$لديه${\displaystyle e'}$الأخطاء و${\displaystyle s'}$عمليات المحو (مقارنة بـ${\displaystyle \mathbf {c} }$) بعد الخطوة 1 ، ثم${\displaystyle \mathbb {E} [2e'+s']<D.}$

ملاحظة. إذا${\displaystyle 2e'+s'<D}$ثم ستُخرج الخوارزمية في الخطوة 2${\displaystyle \mathbf {c} }$تنصّ اللمة أعلاه على أن هذا هو الحال في المتوسط. تجدر الإشارة إلى أن هذا لا يكفي لإثبات النظرية 1 ، ولكنه قد يكون حاسماً في تطوير نسخ مستقبلية من الخوارزمية.

برهان اللمة 1. لكل${\displaystyle 1\leq i\leq N,}$يُعرِّف${\displaystyle e_{i}=\Delta (y_{i},c_{i}).}$وهذا يعني أن

$${\displaystyle \sum _{i=1}^{N}e_{i}<{\frac {Dd}{2}}\qquad \qquad (1)}$$ التالي لكل${\displaystyle 1\leq i\leq N}$، نُعرّف متغيرين مؤشرين :

$${\displaystyle {\begin{aligned}X{_{i}^{?}}=1&\Leftrightarrow y_{i}''=?\\X{_{i}^{e}}=1&\Leftrightarrow C_{\text{in}}(y_{i}'')\neq c_{i}\ {\text{and}}\ y_{i}''\neq$$ ندعي أننا انتهينا إذا استطعنا إثبات أنه لكل${\displaystyle 1\leq i\leq N}$:

$${\displaystyle \mathbb {E} \left[2X{_{i}^{e}+X{_{i}^{?}}}\right]\leqslant {2e_{i} \over d}\qquad \qquad (2)}$$ من الواضح، بحسب التعريف

$${\displaystyle e'=\sum _{i}X_{i}^{e}\quad {\text{and}}\quad s'=\sum _{i}X_{i}^{?}.}$$ علاوة على ذلك، وبسبب خطية التوقع، نحصل على

$${\displaystyle \mathbb {E} [2e'+s']\leqslant {\frac {2}{d}}\sum _{i}e_{i}<D.}$$ لإثبات (2) نأخذ في الاعتبار حالتين:${\displaystyle i}$تم فك تشفير الكتلة رقم -th بشكل صحيح ( الحالة 1 )، ${\displaystyle i}$تم فك تشفير الكتلة رقم -th بشكل غير صحيح ( الحالة 2 ):

الحالة 1:${\displaystyle (c_{i}=C_{\text{in}}(y_{i}'))}$

لاحظ أنه إذا${\displaystyle y_{i}''=?}$ثم${\displaystyle X_{i}^{e}=0}$، و${\displaystyle \Pr[y_{i}''=?]={\tfrac {2\omega _{i}}{d}}}$يشير إلى${\displaystyle \mathbb {E} [X_{i}^{?}]=\Pr[X_{i}^{?}=1]={\tfrac {2\omega _{i}}{d}},}$و${\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=0}$.

علاوة على ذلك، لدينا بحكم التعريف

$${\displaystyle \omega _{i}=\min \left(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{\tfrac {d}{2}}\right)\leqslant \Delta (C_{\text{in}}(y_{i}'),y_{i})=\Delta (c_{i},y_{i})=e_{i}}$$الحالة الثانية:${\displaystyle (c_{i}\neq C_{\text{in}}(y_{i}'))}$

في هذه الحالة،${\displaystyle \mathbb {E} [X_{i}^{?}]={\tfrac {2\omega _{i}}{d}}}$و${\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=1-{\tfrac {2\omega _{i}}{d}}.}$

منذ${\displaystyle c_{i}\neq C_{\text{in}}(y_{i}'),e_{i}+\omega _{i}\geqslant d}$ويأتي هذا في أعقاب تحليل حالة آخر ^{[ 1 ]} عندما${\displaystyle (\omega _{i}=\Delta (C_{\text{in}}(y_{i}'),y_{i})<{\tfrac {d}{2}})}$أو لا.

وأخيراً، هذا يعني

$${\displaystyle \mathbb {E} [2X_{i}^{e}+X_{i}^{?}]=2-{2\omega _{i} \over d}\leq {2e_{i} \over d}.}$$ في الأقسام التالية، سنوضح أخيرًا أن النسخة الحتمية من الخوارزمية المذكورة أعلاه يمكنها فك تشفير فريد لـ${\displaystyle C_{\text{out}}\circ C_{\text{in}}}$تصل إلى نصف مسافة التصميم.

لاحظ أنه في الإصدار السابق من خوارزمية GMD في الخطوة "3"، لسنا بحاجة فعليًا إلى استخدام عشوائية "جديدة" لكل${\displaystyle i}$والآن نتوصل إلى نسخة عشوائية أخرى من خوارزمية GMD تستخدم نفس العشوائية لكل${\displaystyle i}$تعتمد هذه الفكرة على الخوارزمية الموضحة أدناه.

تم إعطاء وحدة فك التشفير العشوائية المعدلة : ${\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}$، يختار${\displaystyle \theta \in [0,1]}$عشوائياً. ثم كل لكل${\displaystyle 1\leq i\leq N}$:

1. تعيين${\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}$.
2. الحوسبة${\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})}$.
3. لو${\displaystyle \theta <{\tfrac {2\omega _{i}}{d}}}$، تعيين${\displaystyle y_{i}''\leftarrow$ ?,} وإلا يتم تعيينه${\displaystyle y_{i}''=y_{i}'}$.
4. تشغيل الأخطاء وخوارزمية المسح لـ${\displaystyle C_{\text{out}}}$على${\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}$.

لإثبات اللمة 1 ، نستخدم العشوائية فقط لإظهار أن

$${\displaystyle \Pr[y_{i}''=?]={2\omega _{i} \over d}.}$$ في هذه النسخة من خوارزمية GMD، نلاحظ أن

$${\displaystyle \Pr[y_{i}''=?]=\Pr \left[\theta \in \left[0,{\tfrac {2\omega _{i}}{d}}\right]\right]={\tfrac {2\omega _{i}}{d}}.}$$تنتج المساواة الثانية أعلاه من اختيار${\displaystyle \theta }$يمكن أيضًا استخدام برهان اللمة 1 لإثبات${\displaystyle \mathbb {E} [2e'+s']<D}$بالنسبة للإصدار الثاني من خوارزمية GMD. في القسم التالي، سنرى كيفية الحصول على نسخة حتمية من خوارزمية GMD عن طريق اختيار${\displaystyle \theta }$من مجموعة ذات حجم متعدد الحدود بدلاً من المجموعة اللانهائية الحالية${\displaystyle [0,1]}$.

يترك${\displaystyle Q=\{0,1\}\cup \{{2\omega _{1} \over d},\ldots ,{2\omega _{N} \over d}\}}$بما أن لكل${\displaystyle i,\omega _{i}=\min(\Delta (\mathbf {y_{i}'} ,\mathbf {y_{i}} ),{d \over 2})}$لدينا

$${\displaystyle Q=\{0,1\}\cup \{q_{1},\ldots ,q_{m}\}}$$ أين${\displaystyle q_{1}<\cdots <q_{m}}$بالنسبة للبعض${\displaystyle m\leq \left\lfloor {\frac {d}{2}}\right\rfloor }$لاحظ أنه لكل${\displaystyle \theta \in [q_{i},q_{i+1}]}$، تُخرج الخطوة الأولى من الإصدار الثاني من الخوارزمية العشوائية نفس${\displaystyle \mathbf {y} ''.}$لذا، نحتاج إلى النظر في جميع القيم الممكنة لـ${\displaystyle \theta \in Q}$وهذا يعطي الخوارزمية الحتمية أدناه.

Deterministic_Decoder Given  :${\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}$لكل${\displaystyle \theta \in Q}$كرر ما يلي.

1. الحوسبة${\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}$ل${\displaystyle 1\leq i\leq N}$.
2. تعيين${\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})}$لكل${\displaystyle 1\leq i\leq N}$.
3. لو${\displaystyle \theta <{2\omega _{i} \over d}}$، تعيين${\displaystyle y_{i}''\leftarrow$ ?,} وإلا يتم تعيينه${\displaystyle y_{i}''=y_{i}'}$.
4. تشغيل خوارزمية تصحيح الأخطاء والمحو لـ${\displaystyle C_{\text{out}}}$على${\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}$. يترك${\displaystyle c_{\theta }}$كن كلمة السر في${\displaystyle C_{\text{out}}\circ C_{\text{in}}}$بما يتوافق مع مخرجات الخوارزمية، إن وجدت.
5. من بين جميع${\displaystyle c_{\theta }}$أخرج القيمة 4، ثم أخرج القيمة الأقرب إلى${\displaystyle \mathbf {y} }$

يمكن تشغيل كل حلقة من 1 إلى 4 في وقت متعدد الحدود ، ويمكن أيضًا حساب الخوارزمية المذكورة أعلاه في وقت متعدد الحدود. على وجه التحديد، كل استدعاء لفك تشفير الأخطاء والمحو لـ${\displaystyle <dD/2}$الأخطاء${\displaystyle O(d)}$الوقت. وأخيرًا، زمن تشغيل الخوارزمية المذكورة أعلاه هو${\displaystyle O(NQn^{O(1)}+NT_{\text{out}})}$أين${\displaystyle T_{\text{out}}}$هو وقت تشغيل وحدة فك تشفير الأخطاء الخارجية وعمليات المسح.

• الرموز المتسلسلة
• تصحيح الأخطاء من ريد سولومون
• خوارزمية ويلش بيرلكامب

• ملاحظات محاضرات جامعة بافالو حول نظرية الترميز - أتري رودرا
• ملاحظات محاضرات معهد ماساتشوستس للتكنولوجيا حول نظرية الترميز الأساسية - مادو سودان
• جامعة واشنطن – فينكاتيسان جوروسوامي
• جي. ديفيد فورني. فك التشفير باستخدام طريقة المسافة الدنيا المعممة. معاملات IEEE في نظرية المعلومات ، 12: 125-131، 1966