أساليب فك التشفير

في نظرية الترميز ، فك الترميز هو عملية ترجمة الرسائل المستلمة إلى كلمات رمزية ضمن رمز معين . وقد ظهرت العديد من الطرق الشائعة لربط الرسائل بالكلمات الرمزية، والتي تُستخدم غالبًا لاستعادة الرسائل المرسلة عبر قناة مشوشة ، مثل قناة ثنائية متناظرة .

${\displaystyle C\subset \mathbb {F} _{2}^{n}}$يُعتبر رمزًا ثنائيًا بطول${\displaystyle n}$؛${\displaystyle x,y}$ستكون عناصر من${\displaystyle \mathbb {F} _{2}^{n}}$؛ و${\displaystyle d(x,y)}$هي المسافة بين تلك العناصر.

قد يتلقى المرء الرسالة${\displaystyle x\in \mathbb {F} _{2}^{n}}$ثم يقوم المراقب المثالي بفك التشفير لتوليد الكلمة المشفرة${\displaystyle y\in C}$تؤدي هذه العملية إلى هذا الحل:

${\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}$

على سبيل المثال، يمكن للشخص اختيار كلمة السر${\displaystyle y}$من المرجح أن يتم استقبال ذلك على أنه الرسالة${\displaystyle x}$بعد الإرسال.

بافتراض وجود متجه مستلم${\displaystyle x\in \mathbb {F} _{2}^{n}}$يختار فك التشفير باستخدام طريقة الاحتمالية القصوى كلمة رمزية${\displaystyle y\in C}$الذي يحقق أقصى قدر

${\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}$،

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

$\begin{aligned}\mathbb{P}(x{\mbox{ received}}\mid y{\mbox{ sent}})&{}={\frac{\mathbb{P}(x{\mbox{ received}},y{\mbox{ sent}})}{\mathbb{P}(y{\mbox{ sent}})}}\\&{}=\mathbb{P}(y{\mbox{ sent}}\mid x{\mbox{ received}})\cdot{\frac{\mathbb{P}(x{\mbox{ received}})}{\mathbb{P}(y{\mbox{ sent}})}}.\end{aligned}}}$

بعد الإصلاح${\displaystyle \mathbb {P} (x{\mbox{ received}})}$،${\displaystyle x}$تمت إعادة هيكلتها و ${\displaystyle \mathbb {P} (y{\mbox{ sent}})}$ثابت لأن جميع الكلمات المشفرة لها نفس احتمالية الإرسال. لذلك، ${\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}$ يتم تعظيمها كدالة للمتغير${\displaystyle y}$متى بالضبط ${\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}$ يتم تحقيق أقصى قدر من الفعالية، ويتبع ذلك الادعاء.

كما هو الحال مع فك التشفير المثالي للمراقب، يجب الاتفاق على اتفاقية لفك التشفير غير الفريد.

يمكن أيضًا نمذجة مشكلة فك التشفير ذات الاحتمالية القصوى كمشكلة برمجة عددية صحيحة . ^{[ 1 ]}

تُعد خوارزمية فك التشفير ذات الاحتمالية القصوى مثالاً على مشكلة "تهميش دالة الضرب" التي يتم حلها بتطبيق قانون التوزيع المعمم . ^{[ 2 ]}

بافتراض وجود متجه مستلم${\displaystyle x\in \mathbb {F} _{2}^{n}}$تختار خوارزمية فك التشفير ذات المسافة الدنيا كلمة رمزية${\displaystyle y\in C}$لتقليل مسافة هامينغ :

${\displaystyle d(x,y)=|\{i:x_{i}\not =y_{i}\}|}$

أي اختر كلمة السر${\displaystyle y}$هذا أقرب ما يمكن إلى${\displaystyle x}$.

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

${\displaystyle d(x,y)=d,\,}$

ثم:

${\displaystyle {\begin{aligned}\mathbb {P} (y{\mbox{ received}}\mid x{\mbox{ sent}})&{}=(1-p)^{nd}\cdot p^{d}\\&{}=(1-p)^{n}\cdot \left({\frac {p}{1-p}}\right)^{d}\\\end{aligned}}}$

والتي (بما أن p أقل من النصف) يتم تعظيمها عن طريق تقليل d .

يُعرف فك التشفير باستخدام أقصر مسافة أيضًا باسم فك التشفير باستخدام أقرب جار . ويمكن تسهيله أو أتمتته باستخدام مصفوفة قياسية . يُعد فك التشفير باستخدام أقصر مسافة طريقةً مناسبةً لفك التشفير عند استيفاء الشروط التالية:

1. الاحتمالية${\displaystyle p}$إن حدوث الخطأ لا يعتمد على موضع الرمز.
2. الأخطاء أحداث مستقلة - فالخطأ في موضع واحد في الرسالة لا يؤثر على المواضع الأخرى. 

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

كما هو الحال مع طرق فك التشفير الأخرى، يجب الاتفاق على اتفاقية لفك التشفير غير الفريد.

فك التشفير بالمتلازمة هو أسلوب عالي الكفاءة لفك تشفير الشفرة الخطية عبر قناة مشوشة ، أي قناة تكثر فيها الأخطاء. وباختصار، يعتمد فك التشفير بالمتلازمة على فك التشفير بأقل مسافة باستخدام جدول بحث مُصغّر . وهذا ما تسمح به خطية الشفرة. ^{[ 3 ]}

لنفترض أن${\displaystyle C\subset \mathbb {F} _{2}^{n}}$هو رمز خطي بطول${\displaystyle n}$والمسافة الدنيا${\displaystyle d}$مع مصفوفة التحقق من التكافؤ${\displaystyle H}$ثم من الواضح${\displaystyle C}$قادر على التصحيح حتى

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }$

الأخطاء التي ارتكبتها القناة (لأنها لا تزيد عن${\displaystyle t}$في حالة حدوث أخطاء، فإن فك التشفير بأقل مسافة سيظل يفك تشفير الكلمة المشفرة المرسلة بشكل غير صحيح).

لنفترض الآن أن كلمة سرية${\displaystyle x\in \mathbb {F} _{2}^{n}}$يتم إرسالها عبر القناة ونمط الخطأ${\displaystyle e\in \mathbb {F} _{2}^{n}}$يحدث ذلك. ثم${\displaystyle z=x+e}$يتم استلامها. تقوم عملية فك التشفير العادية ذات الحد الأدنى للمسافة بالبحث عن المتجه${\displaystyle z}$في جدول بحجم${\displaystyle |C|}$للحصول على أقرب تطابق - أي عنصر (ليس بالضرورة فريدًا)${\displaystyle c\in C}$مع

${\displaystyle d(c,z)\leq d(y,z)}$

للجميع${\displaystyle y\in C}$يستفيد فك تشفير المتلازمة من خاصية مصفوفة التكافؤ التي:

${\displaystyle Hx=0}$

للجميع${\displaystyle x\in C}$متلازمة المتلقين​${\displaystyle z=x+e}$يُعرَّف بأنه:

${\displaystyle Hz=H(x+e)=Hx+He=0+He=He}$

لإجراء فك تشفير ML في قناة متناظرة ثنائية ، يجب البحث في جدول محسوب مسبقًا بحجم${\displaystyle 2^{n-k}}$رسم الخرائط${\displaystyle He}$ل${\displaystyle e}$.

لاحظ أن هذا أقل تعقيدًا بكثير من فك تشفير المصفوفة القياسي .

ومع ذلك، بافتراض أن الأمر لا يزيد عن${\displaystyle t}$حدثت أخطاء أثناء الإرسال، ويمكن للمستقبل البحث عن القيمة${\displaystyle He}$في جدول أصغر حجماً

${\displaystyle {\begin{matrix}\sum _{i=0}^{t}{\binom {n}{i}}\\\end{matrix}}}$

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

أبسط شكل يعود إلى برانج: ليكن${\displaystyle G}$كن${\displaystyle k\times n}$مصفوفة مولدة لـ${\displaystyle C}$يُستخدم للترميز. حدد${\displaystyle k}$أعمدة من${\displaystyle G}$عشوائياً، ونرمز بـ${\displaystyle G'}$المصفوفة الفرعية المقابلة لـ${\displaystyle G}$باحتمال معقول${\displaystyle G'}$سيتمتع برتبة كاملة، مما يعني أنه إذا سمحنا${\displaystyle c'}$ليكن المتجه الفرعي للمواقع المتناظرة لأي كلمة رمزية${\displaystyle c=mG}$ل${\displaystyle C}$للحصول على رسالة${\displaystyle m}$يمكننا التعافي${\displaystyle m}$مثل${\displaystyle m=c'G'^{-1}}$لذا، إذا حالفنا الحظ في أن هذه${\displaystyle k}$مواقع الكلمة المستلمة${\displaystyle y}$إذا لم تحتوي على أخطاء، وبالتالي كانت مواضعها مساوية لمواضع الكلمة المشفرة المرسلة، فيمكننا فك التشفير.

لو${\displaystyle t}$في حال حدوث أخطاء، فإن احتمال اختيار الأعمدة بهذه الطريقة الموفقة يُعطى بالصيغة التالية:${\displaystyle \textstyle {\binom {n-t}{k}}/{\binom {n}{k}}\approx \exp(-tk/n)}$.

وقد تم تحسين هذه الطريقة بطرق مختلفة، على سبيل المثال من قبل ستيرن ^{[ 4 ]} وكانتو وسيندرييه . ^{[ 5 ]}

الاحتمال الأقصى للاستجابة الجزئية ( PRML ) هي طريقة لتحويل الإشارة التناظرية الضعيفة من رأس القرص المغناطيسي أو محرك الشريط إلى إشارة رقمية.

يستخدم مُفكِّك فيتربي خوارزمية فيتربي لفك تشفير سلسلة بتات مُشفَّرة باستخدام تصحيح الخطأ الأمامي القائم على رمز التفافي . تُستخدم مسافة هامينغ كمقياس لمفكِّكات فيتربي ذات القرار الحاسم، بينما تُستخدم المسافة الإقليدية التربيعية كمقياس لمفكِّكات فيتربي ذات القرار المرن.

خوارزمية فك تشفير القرار الأمثل (ODDA) لنظام TWRC غير المتماثل. ^{[ 6 ]}

• إنذار عدم الاكتراث
• اكتشاف الأخطاء وتصحيحها
• إدخال ممنوع

• هيل، ريموند (1986). مدخل إلى نظرية الترميز . سلسلة أكسفورد للرياضيات التطبيقية وعلوم الحاسوب. مطبعة جامعة أكسفورد . ISBN 978-0-19-853803-5.
• بليس، فيرا (1982). مقدمة في نظرية رموز تصحيح الأخطاء . سلسلة وايلي-إنترساينس في الرياضيات المتقطعة. جون وايلي وأولاده . ISBN 978-0-471-08684-0.
• فان لينت، جاكوبوس هـ. (1992). مقدمة في نظرية الترميز . نصوص الدراسات العليا في الرياضيات (GTM). المجلد  86 (  الطبعة الثانية). سبرينغر-فيرلاغ . ISBN 978-3-540-54894-2.