أس الخطأ

تنص نظرية ترميز القناة على أنه لأي قيمة ε > 0 ولأي معدل بيانات أقل من سعة القناة، توجد آلية ترميز وفك ترميز يمكن استخدامها لضمان أن يكون احتمال خطأ الكتلة أقل من ε > 0 لكتلة رسالة طويلة بما فيه الكفاية X. كذلك، لأي معدل بيانات أكبر من سعة القناة، يؤول احتمال خطأ الكتلة عند جهاز الاستقبال إلى واحد عندما يؤول طول الكتلة إلى اللانهاية.

بافتراض إعداد ترميز القناة على النحو التالي: يمكن للقناة إرسال أي مما يلي${\displaystyle M=2^{nR}\;}$يتم إرسال الرسائل عن طريق نقل الكلمة المشفرة المقابلة (التي يبلغ طولها n ). يتم اختيار كل مكون في دفتر الشفرات بشكل مستقل ومتطابق التوزيع وفقًا لتوزيع احتمالي معين بدالة كتلة احتمالية Q. عند فك التشفير، يتم استخدام طريقة فك التشفير بأقصى احتمال.

يترك${\displaystyle X_{i}^{n}}$كن${\displaystyle i}$كلمة المرور العشوائية رقم في دفتر الشفرات، حيث${\displaystyle i}$ينتقل من${\displaystyle 1}$ل${\displaystyle M}$لنفترض أنه تم اختيار الرسالة الأولى، لذا كلمة المرور${\displaystyle X_{1}^{n}}$يتم نقلها. بالنظر إلى أن${\displaystyle y_{1}^{n}}$عند استلامها، يكون احتمال اكتشاف كلمة المرور بشكل خاطئ هو${\displaystyle X_{2}^{n}}$يكون:

${\displaystyle P_{\mathrm {خطأ} \ 1\to 2}=\sum _{x_{2}^{n}}Q(x_{2}^{n})1(p(y_{1}^{n}\mid x_{2}^{n})>p(y_{1}^{n}\mid x_{1}^{n})).}$

الوظيفة${\displaystyle 1(p(y_{1}^{n}\mid x_{2}^{n})>p(y_{1}^{n}\mid x_{1}^{n}))}$له حد أعلى

${\displaystyle \left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}}$

ل${\displaystyle s>0\;}$هكذا،

${\displaystyle P_{\mathrm {error} \ 1\to 2}\leq \sum _{x_{2}^{n}}Q(x_{2}^{n})\left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}.}$

بما أن هناك إجمالي M رسالة، وأن المدخلات في دفتر الرموز مستقلة ومتطابقة التوزيع، فإن احتمال أن${\displaystyle X_{1}^{n}}$يتم الخلط بينها وبين أي رسالة أخرى${\displaystyle M}$اضرب التعبير أعلاه. باستخدام حد الاتحاد، احتمال الخلط${\displaystyle X_{1}^{n}}$أي رسالة تكون محدودة بما يلي:

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\left(\sum _{x_{2}^{n}}Q(x_{2}^{n})\left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}\right)^{\rho }}$

لأي${\displaystyle 0<\rho <1}$. حساب المتوسط ​​لجميع تركيبات${\displaystyle x_{1}^{n},y_{1}^{n}}$:

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\sum _{y_{1}^{n}}\left(\sum _{x_{1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{1-s\rho }\right)\left(\sum _{x_{2}^{n}}Q(x_{2}^{n})[p(y_{1}^{n}\mid x_{2}^{n})]^{s}\right)^{\rho }.}$

اختيار${\displaystyle s=1-s\rho }$وبدمج المجموعين على${\displaystyle x_{1}^{n}}$في الصيغة أعلاه:

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\sum _{y_{1}^{n}}\left(\sum _{x_{1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{\frac {1}{1+\rho }}\right)^{1+\rho }.}$

باستخدام طبيعة استقلالية عناصر الكلمة المشفرة، وطبيعة القناة المنفصلة عديمة الذاكرة:

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\prod _{i=1}^{n}\sum _{y_{i}}\left(\sum _{x_{i}}Q_{i}(x_{i})[p_{i}(y_{i}\mid x_{i})]^{\frac {1}{1+\rho }}\right)^{1+\rho }}$

باستخدام حقيقة أن كل عنصر من عناصر الكلمة المشفرة موزع بشكل متطابق وبالتالي فهو ثابت:

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\left(\sum _{y}\left(\sum _{x}Q(x)[p(y\mid x)]^{\frac {1}{1+\rho }}\right)^{1+\rho }\right)^{n}.}$

باستبدال M بـ 2 ^نانو راديان وتحديد

${\displaystyle E_{o}(\rho ,Q)=-\ln \left(\sum _{y}\left(\sum _{x}Q(x)[p(y\mid x)]^{1/(1+\rho )}\right)^{1+\rho }\right),}$

يصبح احتمال الخطأ

${\displaystyle P_{\mathrm {error} }\leq \exp(-n(E_{o}(\rho ,Q)-\rho R)).}$

س و${\displaystyle \rho }$ينبغي اختيارها بحيث يكون الحدّ أضيق ما يمكن. وبالتالي، يمكن تعريف أس الخطأ على النحو التالي:

${\displaystyle E_{r}(R)=\max _{Q}\max _{\rho \in [0,1]}E_{o}(\rho ,Q)-\rho R.\;}$

تنص نظرية ترميز المصدر على أنه لأي${\displaystyle \varepsilon >0}$وأي مصدر مستقل ومتطابق التوزيع ذي زمن منفصل مثل${\displaystyle X}$وبالنسبة لأي معدل أقل من إنتروبيا المصدر، يكون هناك معدل كبير بما فيه الكفاية${\displaystyle n}$وجهاز تشفير يأخذ${\displaystyle n}$تكرار المصدر بشكل مستقل ومتطابق،${\displaystyle X^{1:n}}$ويربطها بـ${\displaystyle n.(H(X)+\varepsilon )}$بتات ثنائية بحيث تكون رموز المصدر${\displaystyle X^{1:n}}$يمكن استعادتها من البتات الثنائية باحتمالية لا تقل عن${\displaystyle 1-\varepsilon }$.

يترك${\displaystyle M=e^{nR}\,\!}$ليكن العدد الإجمالي للرسائل الممكنة. بعد ذلك، قم بربط كل تسلسل من تسلسلات مخرجات المصدر الممكنة بإحدى الرسائل عشوائيًا باستخدام توزيع منتظم وبشكل مستقل عن أي شيء آخر. عند إنشاء مصدر، يتم إرسال الرسالة المقابلة.${\displaystyle M=m\,}$ثم تُرسل الرسالة إلى الوجهة. ويتم فك تشفيرها إلى إحدى سلاسل المصدر المحتملة. ولتقليل احتمالية الخطأ، يقوم جهاز فك التشفير بفك التشفير إلى تسلسل المصدر.${\displaystyle X_{1}^{n}}$الذي يحقق أقصى قدر${\displaystyle P(X_{1}^{n}\mid A_{m})}$، أين${\displaystyle A_{m}\,}$يشير إلى الحدث الذي تم إرسال الرسالة إليه${\displaystyle m}$تم إرسالها. هذه القاعدة تعادل إيجاد تسلسل المصدر${\displaystyle X_{1}^{n}}$من بين مجموعة تسلسلات المصدر التي تُطابق الرسالة${\displaystyle m}$الذي يحقق أقصى قدر${\displaystyle P(X_{1}^{n})}$ويعود هذا الانخفاض إلى حقيقة أن الرسائل تم تعيينها بشكل عشوائي ومستقل عن أي شيء آخر.

وهكذا، كمثال على حدوث خطأ، افترض أن تسلسل المصدر${\displaystyle X_{1}^{n}(1)}$تمت مطابقة الرسالة${\displaystyle 1}$وكذلك كان تسلسل المصدر${\displaystyle X_{1}^{n}(2)}$. لو${\displaystyle X_{1}^{n}(1)\,}$تم إنشاؤه في المصدر، ولكن${\displaystyle P(X_{1}^{n}(2))>P(X_{1}^{n}(1))}$ثم يحدث خطأ.

يترك${\displaystyle S_{i}\,}$يشير إلى الحدث الذي يكون فيه تسلسل المصدر${\displaystyle X_{1}^{n}(i)}$تم توليدها في المصدر، بحيث${\displaystyle P(S_{i})=P(X_{1}^{n}(i))\,.}$ثم يمكن تقسيم احتمال الخطأ إلى:${\displaystyle P(E)=\sum _{i}P(E\mid S_{i})P(S_{i})\,.}$وبالتالي، يمكن تركيز الاهتمام على إيجاد حد أعلى لـ${\displaystyle P(E\mid S_{i})\,}$.

يترك${\displaystyle A_{i'}\,}$يشير إلى الحدث الذي يكون فيه تسلسل المصدر${\displaystyle X_{1}^{n}(i')}$تمت مطابقة الرسالة مع نفس رسالة التسلسل المصدر${\displaystyle X_{1}^{n}(i)}$وذلك${\displaystyle P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i))}$وبالتالي، السماح${\displaystyle X_{i,i'}\,}$يشير إلى الحدث الذي تكون فيه سلسلتا المصدر${\displaystyle i\,}$و${\displaystyle i'\,}$لدينا خريطة لنفس الرسالة، وهذا ما نستنتجه.

${\displaystyle P(A_{i'})=P\left(X_{i,i'}\bigcap P(X_{1}^{n}(i')\right)\geq P(X_{1}^{n}(i)))\,}$

وباستخدام حقيقة أن${\displaystyle P(X_{i,i'})={\frac {1}{M}}\,}$وهو مستقل عن كل شيء آخر، امتلك ذلك

${\displaystyle P(A_{i'})={\frac {1}{M}}P(P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i)))\,.}$

يمكن تحديد حد أعلى بسيط للمصطلح الموجود على اليسار على النحو التالي:

${\displaystyle \left[P(P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i)))\right]\leq \left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\,}$

لبعض الأعداد الحقيقية العشوائية${\displaystyle s>0\,.}$يمكن التحقق من هذا الحد الأعلى من خلال ملاحظة أن${\displaystyle P(P(X_{1}^{n}(i'))>P(X_{1}^{n}(i)))\,}$إما يساوي${\displaystyle 1\,}$أو${\displaystyle 0\,}$لأن احتمالات تسلسل الإدخال المعطى محددة تمامًا. وبالتالي، إذا${\displaystyle P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i))\,,}$ثم${\displaystyle {\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\geq 1\,}$وبالتالي، فإن المتباينة صحيحة في تلك الحالة. وتتحقق المتباينة في الحالة الأخرى أيضًا لأن

${\displaystyle \left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\geq 0\,}$

لجميع سلاسل المصدر الممكنة. وبالتالي، يتم دمج كل شيء وإدخال بعض${\displaystyle \rho \in [0,1]\,}$، احصل على ذلك

${\displaystyle P(E\mid S_{i})\leq P(\bigcup _{i\neq i'}A_{i'})\leq \left(\sum _{i\neq i'}P(A_{i'})\right)^{\rho }\leq \left({\frac {1}{M}}\sum _{i\neq i'}\left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\right)^{\rho }\,.}$

حيث تنتج المتباينات من تباين في حد الاتحاد. وأخيرًا، بتطبيق هذا الحد الأعلى على المجموع لـ${\displaystyle P(E)\,}$احصل على ذلك:

${\displaystyle P(E)=\sum _{i}P(E\mid S_{i})P(S_{i})\leq \sum _{i}P(X_{1}^{n}(i))\left({\frac {1}{M}}\sum _{i'}\left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\right)^{\rho }\,.}$

حيث يمكن الآن أخذ المجموع على الكل${\displaystyle i'\,}$لأن ذلك لن يؤدي إلا إلى زيادة الحد. مما سيؤدي في النهاية إلى ذلك

${\displaystyle P(E)\leq {\frac {1}{M^{\rho }}}\sum _{i}P(X_{1}^{n}(i))^{1-s\rho }\left(\sum _{i'}P(X_{1}^{n}(i'))^{s}\right)^{\rho }\,.}$

والآن، ولتبسيط الأمور، دعونا${\displaystyle 1-s\rho =s\,}$لهذا السبب.${\displaystyle s={\frac {1}{1+\rho }}\,.}$باستبدال هذه القيمة الجديدة لـ${\displaystyle s\,}$في الحد المذكور أعلاه لاحتمالية الخطأ، وباستخدام حقيقة أن${\displaystyle i'\,}$هو مجرد متغير وهمي في المجموع، ويعطي ما يلي كحد أعلى لاحتمالية الخطأ:

${\displaystyle P(E)\leq {\frac {1}{M^{\rho }}}\left(\sum _{i}P(X_{1}^{n}(i))^{\frac {1}{1+\rho }}\right)^{1+\rho }\,.}$

${\displaystyle M=e^{nR}\,\!}$وكل مكون من مكونات${\displaystyle X_{1}^{n}(i)\,}$مستقلة. وبالتالي، فإن تبسيط المعادلة أعلاه ينتج

${\displaystyle P(E)\leq \exp \left(-n\left[\rho R-\ln \left(\sum _{x_{i}}P(x_{i})^{\frac {1}{1+\rho }}\right)(1+\rho )\right]\right).}$

يجب تعظيم الحد الموجود في الأس على${\displaystyle \rho \,}$وذلك لتحقيق أعلى حد أقصى لاحتمالية الخطأ.

تأجير${\displaystyle E_{0}(\rho )=\ln \left(\sum _{x_{i}}P(x_{i})^{\frac {1}{1+\rho }}\right)(1+\rho )\,,}$لاحظ أن أس الخطأ في حالة ترميز المصدر هو:

${\displaystyle E_{r}(R)=\max _{\rho \in [0,1]}\left[\rho R-E_{0}(\rho )\right].\,}$