قناة ثنائية متناظرة

يمكن إثبات النظرية مباشرةً باستخدام طريقة احتمالية . لنفترض دالة ترميز${\displaystyle E:\{0,1\}^{k}\to \{0,1\}^{n}}$يتم اختيار ذلك عشوائياً. هذا يعني أنه بالنسبة لكل رسالة${\displaystyle m\in \{0,1\}^{k}}$، القيمة${\displaystyle E(m)\in \{0,1\}^{n}}$يتم اختيارها عشوائياً (باحتمالات متساوية). بالنسبة لدالة ترميز معينة${\displaystyle E}$وظيفة فك التشفير${\displaystyle D:\{0,1\}^{n}\to \{0,1\}^{k}}$يتم تحديدها على النحو التالي: بالنظر إلى أي كلمة رمزية مستلمة${\displaystyle y\in \{0,1\}^{n}}$، نجد الرسالة${\displaystyle m\in \{0,1\}^{k}}$بحيث تكون مسافة هامينغ${\displaystyle \Delta (y,E(m))}$أصغر ما يمكن (مع كسر التعادلات بشكل تعسفي).${\displaystyle D}$تُسمى دالة فك التشفير ذات الاحتمالية القصوى .

ويستمر البرهان بإظهار أن هناك خيارًا واحدًا على الأقل من هذا القبيل${\displaystyle (E,D)}$يحقق هذا استنتاج النظرية، عن طريق التكامل على الاحتمالات. لنفترض${\displaystyle p}$و${\displaystyle \epsilon }$ثابتة. أولاً، سنبين أنه بالنسبة لقيمة ثابتة${\displaystyle m\in \{0,1\}^{k}}$و${\displaystyle E}$إذا تم اختيارها عشوائياً، فإن احتمال الفشل يزيد عن${\displaystyle {\text{BSC}}_{p}}$الضوضاء صغيرة بشكل أُسّي بالنسبة لـ n . عند هذه النقطة، يكون البرهان صالحًا لرسالة ثابتة.${\displaystyle m}$ثم نقوم بتعميم هذه النتيجة لتشمل جميع الرسائل${\displaystyle m}$نحقق ذلك بحذف نصف الكلمات المشفرة من الشفرة، انطلاقًا من فرضية أن برهان احتمال خطأ فك التشفير ينطبق على نصف الكلمات المشفرة على الأقل. تُسمى هذه الطريقة الأخيرة بالتنقية. وهذا ما يُعطي العملية برمتها اسم التشفير العشوائي مع التنقية .

استكمال البرهان (رسم تخطيطي)

يصلح${\displaystyle p}$و${\displaystyle \epsilon }$. بالنظر إلى رسالة ثابتة${\displaystyle m\in \{0,1\}^{k}}$نحتاج إلى تقدير القيمة المتوقعة لاحتمالية عدم عودة الكلمة المشفرة المستلمة مع الضوضاء .${\displaystyle m}$عند فك التشفير. أي أننا نحتاج إلى تقدير ما يلي: ${\displaystyle \mathbb {E} _{E}\left[\Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]\right].}$ يترك${\displaystyle y}$أن تكون كلمة المرور المستلمة. لكي تكون كلمة المرور التي تم فك تشفيرها${\displaystyle D(y)}$لا ينبغي أن يكون مساوياً للرسالة${\displaystyle m}$يجب أن يحدث أحد الأحداث التالية: ${\displaystyle y}$لا يقع داخل كرة هامينغ ذات نصف القطر${\displaystyle (p+\epsilon )n}$مركزها في${\displaystyle E(m)}$يُستخدم هذا الشرط بشكل أساسي لتسهيل العمليات الحسابية. هناك رسالة أخرى${\displaystyle m'\in \{0,1\}^{k}}$بحيث${\displaystyle \Delta (y,E(m'))\leqslant \Delta (y,E(m))}$بمعنى آخر، فإن الأخطاء الناتجة عن الضوضاء تجعل الكلمة المشفرة المرسلة أقرب إلى رسالة مشفرة أخرى. يمكننا تطبيق حد تشيرنوف لضمان عدم وقوع الحدث الأول؛ فنحصل على: ${\displaystyle Pr_{e\in {\text{BSC}}_{p}}[\Delta (y,E(m))>(p+\epsilon )n]\leqslant 2^{-{\epsilon ^{2}}n}.}$ هذا صغير بشكل كبير بالنسبة للأشياء الكبيرة${\displaystyle n}$(تذكر أن${\displaystyle \epsilon }$(ثابت). أما بالنسبة للحدث الثاني، فنلاحظ أن احتمال${\displaystyle E(m')\in B(y,(p+\epsilon )n)}$يكون${\displaystyle {\text{Vol}}(B(y,(p+\epsilon )n)/2^{n}}$أين${\displaystyle B(x,r)}$هي كرة هامينغ ذات نصف قطر${\displaystyle r}$متمركزة عند المتجه${\displaystyle x}$و${\displaystyle {\text{Vol}}(B(x,r))}$حجمها. باستخدام التقريب لتقدير عدد الكلمات المشفرة في كرة هامينغ، لدينا${\displaystyle {\text{Vol}}(B(y,(p+\epsilon )n))\approx 2^{H(p)n}}$وبالتالي فإن الاحتمال المذكور أعلاه يساوي${\displaystyle 2^{H(p)n}/2^{n}=2^{H(p)n-n}}$باستخدام حد الاتحاد ، يمكننا الآن تحديد الحد الأعلى لوجود مثل هذا${\displaystyle m'\in \{0,1\}^{k}}$بواسطة${\displaystyle \leq 2^{k+H(p)n-n}}$وهو${\displaystyle 2^{-\Omega (n)}}$، كما هو مطلوب من خلال اختيار${\displaystyle k}$.

استكمال الإثبات (مفصل)

من التحليل السابق، نحسب احتمال أن تكون الكلمة المشفرة المفككة بالإضافة إلى ضوضاء القناة مختلفة عن الرسالة الأصلية المرسلة. سنقدم بعض الرموز هنا. ليكن${\displaystyle p(y|E(m))}$يشير إلى احتمال استلام كلمة المرور${\displaystyle y}$بالنظر إلى كلمة السر${\displaystyle E(m)}$تم إرسالها. دع${\displaystyle B_{0}}$دل${\displaystyle B(E(m),(p+\epsilon )n).}$ ${\displaystyle {\begin{aligned}\Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]&=\sum _{y\in \{0,1\}^{n}}p(y|E(m))\cdot 1_{D(y)\neq m}\\&\leqslant \sum _{y\notin B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}+\sum _{y\in B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}\\&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}\end{aligned}}}$ نحصل على المتباينة الأخيرة من خلال تحليلنا باستخدام حد تشيرنوف المذكور أعلاه. الآن، بأخذ القيمة المتوقعة لكلا الطرفين، نحصل على: ${\displaystyle {\begin{aligned}\mathbb {E} _{E}\left[\Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]\right]&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}p(y|E(m))\mathbb {E} [1_{D(y)\neq m}]\\&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}\mathbb {E} [1_{D(y)\neq m}]&&\sum _{y\in B_{0}}p(y|E(m))\leqslant 1\\&\leqslant 2^{-{\epsilon ^{2}}n}+2^{k+H(p+\epsilon )n-n}&&\mathbb {E} [1_{D(y)\neq m}]\leqslant 2^{k+H(p+\epsilon )n-n}{\text{ (see above)}}\\&\leqslant 2^{-\delta n}\end{aligned}}}$ عن طريق اختيار القيمة المناسبة لـ${\displaystyle \delta }$بما أن الحد المذكور أعلاه ينطبق على كل رسالة، فإننا نحصل على ${\displaystyle \mathbb {E} _{m}\left[\mathbb {E} _{E}\left[\Pr _{e\in {\text{BSC}}_{p}}\left[D(E(m)+e)\right]\neq m\right]\right]\leqslant 2^{-\delta n}.}$ الآن يمكننا تغيير ترتيب الجمع في التوقع بالنسبة للرسالة واختيار دالة التشفير${\displaystyle E}$. لذلك: ${\displaystyle \mathbb {E} _{E}\left[\mathbb {E} _{m}\left[\Pr _{e\in {\text{BSC}}_{p}}\left[D(E(m)+e)\right]\neq m\right]\right]\leqslant 2^{-\delta n}.}$ وبالتالي، في الختام، باستخدام الطريقة الاحتمالية، لدينا دالة ترميز معينة.${\displaystyle E^{*}}$ووظيفة فك تشفير مقابلة${\displaystyle D^{*}}$بحيث ${\displaystyle \mathbb {E} _{m}\left[\Pr _{e\in {\text{BSC}}_{p}}\left[D^{*}(E^{*}(m)+e)\neq m\right]\right]\leqslant 2^{-\delta n}.}$ في هذه المرحلة، يعمل البرهان لرسالة ثابتة${\displaystyle m}$لكننا نحتاج إلى التأكد من أن الحد المذكور أعلاه ينطبق على جميع الرسائل${\displaystyle m}$في آن واحد . ولذلك، دعونا نرتب${\displaystyle 2^{k}}$يمكن تصنيف الرسائل حسب احتمالات خطأ فك التشفير. الآن، بتطبيق متباينة ماركوف ، يمكننا إظهار احتمال خطأ فك التشفير للرسالة الأولى.${\displaystyle 2^{k-1}}$الرسائل على الأكثر${\displaystyle 2\cdot 2^{-\delta n}}$وبالتالي، من أجل التأكد من أن الشرط المذكور أعلاه ينطبق على كل رسالة${\displaystyle m}$يمكننا ببساطة حذف الجزء الأخير${\displaystyle 2^{k-1}}$الرسائل من الترتيب المصنف. وهذا يمنحنا أساسًا وظيفة ترميز أخرى.${\displaystyle E'}$مع وظيفة فك تشفير مقابلة${\displaystyle D'}$باحتمالية خطأ في فك التشفير لا تتجاوز${\displaystyle 2^{-\delta n+1}}$بنفس المعدل. أخذ${\displaystyle \delta '}$أن يكون مساوياً لـ${\displaystyle \delta -{\tfrac {1}{n}}}$قمنا بتقييد احتمال خطأ فك التشفير إلى${\displaystyle 2^{-\delta 'n}}$تُكمل عملية التنقيح هذه عملية الإثبات.

قام فورني بإنشاء رمز متسلسل${\displaystyle C^{*}=C_{\text{out}}\circ C_{\text{in}}}$لتحقيق قدرة نظرية ترميز القناة المشوشة لـ${\displaystyle {\text{BSC}}_{p}}$في شفرته البرمجية،

• الشفرة الخارجية${\displaystyle C_{\text{out}}}$هو رمز بطول الكتلة${\displaystyle N}$وقيم${\displaystyle 1-{\frac {\epsilon }{2}}}$في الملعب${\displaystyle F_{2^{k}}}$، و${\displaystyle k=O(\log N)}$بالإضافة إلى ذلك، لدينا خوارزمية فك تشفير${\displaystyle D_{\text{out}}}$ل${\displaystyle C_{\text{out}}}$والتي يمكنها تصحيح ما يصل إلى${\displaystyle \gamma }$جزء من أسوأ حالات الأخطاء والتشغيل في${\displaystyle t_{\text{out}}(N)}$وقت.
• الشفرة الداخلية${\displaystyle C_{\text{in}}}$هو رمز بطول الكتلة${\displaystyle n}$الأبعاد${\displaystyle k}$ومعدل${\displaystyle 1-H(p)-{\frac {\epsilon }{2}}}$بالإضافة إلى ذلك، لدينا خوارزمية فك تشفير${\displaystyle D_{\text{in}}}$ل${\displaystyle C_{\text{in}}}$باحتمالية خطأ في فك التشفير لا تتجاوز${\displaystyle {\frac {\gamma }{2}}}$زيادة${\displaystyle {\text{BSC}}_{p}}$ويجري في${\displaystyle t_{\text{in}}(N)}$وقت.

بالنسبة للرمز الخارجي${\displaystyle C_{\text{out}}}$لو كان الأمر كذلك، لكان أول ما يتبادر إلى الذهن هو رمز ريد-سولومون. مع ذلك، سنرى أن بناء مثل هذا الرمز لا يمكن أن يتم في وقت متعدد الحدود . لهذا السبب يُستخدم رمز خطي ثنائي لـ${\displaystyle C_{\text{out}}}$.

بالنسبة للرمز الداخلي${\displaystyle C_{\text{in}}}$نجد رمزًا خطيًا من خلال البحث الشامل في الرمز الخطي ذي طول الكتلة${\displaystyle n}$والأبعاد${\displaystyle k}$، والذي يتوافق معدله مع قدرة${\displaystyle {\text{BSC}}_{p}}$، وفقًا لنظرية ترميز القناة المشوشة.

المعدل${\displaystyle R(C^{*})=R(C_{\text{in}})\times R(C_{\text{out}})=(1-{\frac {\epsilon }{2}})(1-H(p)-{\frac {\epsilon }{2}})\geq 1-H(p)-\epsilon }$وهو ما يكاد يفي بـ${\displaystyle {\text{BSC}}_{p}}$السعة. ونشير كذلك إلى أن ترميز وفك ترميز ${\displaystyle C^{*}}$يمكن إنجاز ذلك في وقت متعدد الحدود بالنسبة إلى${\displaystyle N}$في الواقع، التشفير${\displaystyle C^{*}}$يستغرق الأمر وقتاً${\displaystyle O(N^{2})+O(Nk^{2})=O(N^{2})}$علاوة على ذلك، تستغرق خوارزمية فك التشفير الموصوفة وقتًا${\displaystyle Nt_{\text{in}}(k)+t_{\text{out}}(N)=N^{O(1)}}$طالما${\displaystyle t_{\text{out}}(N)=N^{O(1)}}$؛ و${\displaystyle t_{\text{in}}(k)=2^{O(k)}}$.