نظرية ترميز القناة الضوضائية

Information theory
Entropy Differential entropy Conditional entropy Joint entropy Mutual information Directed information Conditional mutual information Relative entropy Entropy rate Limiting density of discrete points
Asymptotic equipartition property Rate–distortion theory
Shannon's source coding theorem Channel capacity Noisy-channel coding theorem Shannon–Hartley theorem
v t e

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

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

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

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

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

يمكن حساب سعة القناة من الخصائص الفيزيائية للقناة؛ بالنسبة لقناة محدودة النطاق مع ضوضاء غاوسية، باستخدام نظرية شانون-هارتلي . ${\displaystyle C}$

إن المخططات البسيطة مثل "إرسال الرسالة 3 مرات واستخدام أفضل مخطط تصويت 2 من 3 إذا اختلفت النسخ" هي طرق تصحيح أخطاء غير فعّالة، وغير قادرة على ضمان إمكانية توصيل كتلة من البيانات خالية من الأخطاء بشكل مقارب. إن التقنيات المتقدمة مثل أكواد ريد-سولومون ، ومؤخرًا أكواد التحقق من التكافؤ منخفض الكثافة (LDPC) وأكواد التوربو ، تقترب كثيرًا من الوصول إلى حد شانون النظري، ولكن على حساب التعقيد الحسابي العالي. باستخدام هذه الأكواد عالية الكفاءة ومع قوة الحوسبة في معالجات الإشارات الرقمية اليوم ، أصبح من الممكن الآن الوصول إلى حد قريب جدًا من حد شانون. في الواقع، ثبت أن أكواد LDPC يمكن أن تصل إلى 0.0045 ديسيبل من حد شانون (لقنوات الضوضاء البيضاء الغاوسية الثنائية المضافة (AWGN)، بأطوال كتل طويلة جدًا). ^​​[1]

النموذج الرياضي الأساسي لنظام الاتصالات هو التالي:

${\displaystyle {\xrightarrow[{\text{Message}}]{W}}{\begin{array}{|c| }\hline {\text{Encoder}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Encoded \atop sequence} }]{X^{n}}}{\begin{array}{|c| }\hline {\text{Channel}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {Received \atop sequence} }]{Y^{n}}}{\begin{array}{|c| }\hline {\text{Decoder}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Estimated \atop message} }]{\hat {W}}}}$

يتم إرسال رسالة W عبر قناة مشوشة باستخدام وظائف التشفير وفك التشفير. يقوم المشفر بربط W بتسلسل محدد مسبقًا من رموز القناة بطول n . في أبسط نموذج لها، تقوم القناة بتشويه كل من هذه الرموز بشكل مستقل عن الرموز الأخرى. يتم تغذية خرج القناة - التسلسل المستقبل - إلى جهاز فك التشفير الذي يربط التسلسل بتقدير للرسالة. في هذا الإعداد، يتم تعريف احتمال الخطأ على النحو التالي:

${\displaystyle P_{e}={\text{Pr}}\left\{{\hat {W}}\neq W\right\}.}$

نظرية (شانون، 1948):

1. لكل قناة منفصلة بدون ذاكرة، سعة القناة ، المحددة من حيث المعلومات المتبادلة على النحو التالي:${\displaystyle I(X;Y)}$

${\displaystyle \ C=\sup _{p_{X}}I(X;Y)}$^[2]

يحتوي على الخاصية التالية. لأي و ، لكبير بما فيه الكفاية ، يوجد رمز للطول والمعدل وخوارزمية فك التشفير، بحيث يكون أقصى احتمال لخطأ الكتلة هو .${\displaystyle \epsilon >0}$${\displaystyle R<C}$${\displaystyle N}$${\displaystyle N}$${\displaystyle \geq R}$${\displaystyle \leq \epsilon }$

2. إذا كان احتمال خطأ البت مقبولاً، فيمكن تحقيق معدلات تصل إلى، حيث${\displaystyle p_{b}}$${\displaystyle R(p_{b})}$

${\displaystyle R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.}$

وهي دالة الانتروبيا الثنائية${\displaystyle H_{2}(p_{b})}$

${\displaystyle H_{2}(p_{b})=-\left[p_{b}\log _{2}{p_{b}}+(1-p_{b})\log _{2}({1-p_{b}})\right]}$

3. بالنسبة لأي معدل أكبر من غير الممكن تحقيقه.${\displaystyle p_{b}}$${\displaystyle R(p_{b})}$

(ماكاي (2003)، ص 162؛ راجع جالاجر (1968)، الفصل 5؛ كوفر وتوماس (1991)، ص 198؛ شانون (1948)، المجلد 11)

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

المخططات التالية هي مجرد مجموعة واحدة من العديد من الأساليب المختلفة المتاحة للدراسة في نصوص نظرية المعلومات.

يتبع هذا الدليل الخاص بإمكانية الإنجاز أسلوب الإثباتات التي تستخدم خاصية التقسيم المقارب (AEP). يمكن العثور على أسلوب آخر في نصوص نظرية المعلومات باستخدام أسس الخطأ .

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

من خلال وسيطة متعلقة بـ AEP، مع الأخذ في الاعتبار القناة، وسلاسل الطول من رموز المصدر ، وسلاسل الطول من مخرجات القناة ، يمكننا تعريف مجموعة نموذجية مشتركة من خلال ما يلي: ${\displaystyle n}$${\displaystyle X_{1}^{n}}$${\displaystyle n}$${\displaystyle Y_{1}^{n}}$

${\displaystyle A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}}$

${\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}}$

${\displaystyle 2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}}$

${\displaystyle {2^{-n(H(X,Y)+\varepsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon )}\}}$

نقول أن التسلسلين هما نموذجيان بشكل مشترك إذا كانا يقعان في المجموعة النموذجية المشتركة المحددة أعلاه. ${\displaystyle {X_{1}^{n}}}$${\displaystyle Y_{1}^{n}}$

خطوات

1. بأسلوب حجة الترميز العشوائي، نقوم بشكل عشوائي بإنشاء كلمات رمزية بطول n من توزيع الاحتمالات Q.${\displaystyle 2^{nR}}$
2. يتم الكشف عن هذا الرمز للمرسل والمستقبل. ومن المفترض أيضًا أن يكون الشخص على دراية بمصفوفة الانتقال للقناة المستخدمة.${\displaystyle p(y|x)}$
3. يتم اختيار الرسالة W وفقًا للتوزيع المنتظم لمجموعة الكلمات المشفرة. أي .${\displaystyle Pr(W=w)=2^{-nR},w=1,2,\dots ,2^{nR}}$
4. يتم إرسال الرسالة W عبر القناة.
5. يستقبل المستقبل تسلسلًا وفقًا لـ${\displaystyle P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))}$
6. عند إرسال كلمات المرور هذه عبر القناة، نتلقى ، ونفك تشفيرها إلى تسلسل مصدر ما إذا كان هناك كلمة مرور واحدة فقط نموذجية بشكل مشترك مع Y. إذا لم تكن هناك كلمات مرور نموذجية بشكل مشترك، أو إذا كان هناك أكثر من كلمة، يتم إعلان خطأ. يحدث خطأ أيضًا إذا كانت كلمة المرور التي تم فك تشفيرها لا تتطابق مع كلمة المرور الأصلية. يُطلق على هذا فك تشفير المجموعة النموذجية .${\displaystyle Y_{1}^{n}}$

احتمال الخطأ في هذا المخطط ينقسم إلى قسمين:

1. أولاً، يمكن أن يحدث خطأ إذا لم يتم العثور على تسلسلات X نموذجية مشتركة لتسلسل Y المستلم
2. ثانياً، يمكن أن يحدث خطأ إذا كانت تسلسل X غير الصحيح مشتركًا مع تسلسل Y المستلم.

• من خلال عشوائية بناء الكود، يمكننا أن نفترض أن متوسط ​​احتمال الخطأ الذي يتم حسابه على جميع الكودات لا يعتمد على المؤشر المرسل. وبالتالي، بدون فقدان العمومية، يمكننا أن نفترض أن W = 1.
• من AEP المشترك، نعلم أن احتمال عدم وجود X نموذجي مشترك يصبح 0 مع نمو n. يمكننا تحديد احتمال الخطأ هذا بـ .${\displaystyle \varepsilon }$
• أيضًا من AEP المشترك، نعلم أن احتمال أن يكون معينًا والناتج عن W = 1 نموذجيين بشكل مشترك هو .${\displaystyle X_{1}^{n}(i)}$${\displaystyle Y_{1}^{n}}$${\displaystyle \leq 2^{-n(I(X;Y)-3\varepsilon )}}$

يُعرِّف:${\displaystyle E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,\dots ,2^{nR}}$

حيث أن الحدث هو أن الرسالة i تكون نموذجية بشكل مشترك مع التسلسل المستلم عند إرسال الرسالة 1.

${\displaystyle {\begin{aligned}P({\text{error}})&{}=P({\text{error}}|W=1)\leq P(E_{1}^{c})+\sum _{i=2}^{2^{nR}}P(E_{i})\\&{}\leq P(E_{1}^{c})+(2^{nR}-1)2^{-n(I(X;Y)-3\varepsilon )}\\&{}\leq \varepsilon +2^{-n(I(X;Y)-R-3\varepsilon )}.\end{aligned}}}$

يمكننا أن نلاحظ أنه عندما نتجه إلى ما لا نهاية، فإذا كانت القناة، فإن احتمال الخطأ سوف يصبح 0. ${\displaystyle n}$${\displaystyle R<I(X;Y)}$

أخيرًا، وبما أن متوسط ​​كتاب التعليمات البرمجية يُظهِر أنه "جيد"، فإننا نعلم أن هناك كتاب تعليمات برمجية يكون أداؤه أفضل من المتوسط، وبالتالي يلبي حاجتنا إلى احتمالية خطأ منخفضة بشكل تعسفي في التواصل عبر القناة الصاخبة.

افترض وجود مجموعة من الكلمات المشفرة. دع W تكون مرسومةً بشكل موحد على هذه المجموعة كمؤشر. دع و تكون الكلمات المشفرة المرسلة والكلمات المشفرة المستقبلة على التوالي. ${\displaystyle 2^{nR}}$${\displaystyle X^{n}}$${\displaystyle Y^{n}}$

1. ${\displaystyle nR=H(W)=H(W|Y^{n})+I(W;Y^{n})}$استخدام الهويات التي تنطوي على الإنتروبيا والمعلومات المتبادلة
2. ${\displaystyle \leq H(W|Y^{n})+I(X^{n}(W);Y^{n})}$بما أن X هي دالة لـ W
3. ${\displaystyle \leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})}$باستخدام متباينة فانو
4. ${\displaystyle \leq 1+P_{e}^{(n)}nR+nC}$من خلال حقيقة أن القدرة على تبادل المعلومات هي الحد الأقصى.

النتيجة المترتبة على هذه الخطوات هي أن . مع اقتراب طول الكتلة إلى ما لا نهاية، نحصل على حدود بعيدة عن 0 إذا كانت قيمة R أكبر من قيمة C - يمكننا الحصول على معدلات خطأ منخفضة بشكل تعسفي فقط إذا كانت قيمة R أقل من قيمة C. ${\displaystyle P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}}$${\displaystyle n}$${\displaystyle P_{e}^{(n)}}$

تنص نظرية عكسية قوية، أثبتها وولفويتز في عام 1957، ^[3] على أن،

${\displaystyle P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-{\frac {n(R-C)}{2}}}}$

لبعض الثوابت الإيجابية المحدودة . في حين تنص العكسية الضعيفة على أن احتمال الخطأ محدود بعيدًا عن الصفر حيث يذهب إلى ما لا نهاية، تنص العكسية القوية على أن الخطأ يذهب إلى 1. وبالتالي، هناك عتبة حادة بين الاتصال الموثوق به تمامًا والاتصال غير الموثوق به تمامًا. ${\displaystyle A}$${\displaystyle n}$${\displaystyle C}$

نحن نفترض أن القناة ليس لها ذاكرة، ولكن احتمالات انتقالها تتغير مع الوقت، بطريقة معروفة لدى المرسل وكذلك المستقبل.

ثم يتم تحديد سعة القناة بواسطة

${\displaystyle C=\lim \inf \max _{p^{(X_{1})},p^{(X_{2})},...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i}).}$

يتم الوصول إلى الحد الأقصى عند توزيعات تحقيق السعة لكل قناة على حدة. أي حيث تكون سعة القناة i . ${\displaystyle C=\lim \inf {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}$${\displaystyle C_{i}}$

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

تدخل التقنية الخاصة بـ lim inf حيز التنفيذ عندما لا تتقارب. ${\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}$

• خاصية التقسيم المقارب المتساوي (AEP)
• عدم المساواة في فانو
• نظرية معدل التشويه
• نظرية شانون في ترميز المصدر
• نظرية شانون-هارتلي
• كود توربو

• Aazhang, B. (2004). "نظرية شانون لترميز القناة الصاخبة" (PDF) . الاتصالات .
• الغلاف، TM ؛ توماس، JA (1991). عناصر نظرية المعلومات . وايلي. ISBN 0-471-06259-6.
• فانو، ر.م. (1961). نقل المعلومات؛ نظرية إحصائية للاتصالات . مطبعة معهد ماساتشوستس للتكنولوجيا. رقم ISBN 0-262-06001-9.
• فينشتاين، أميل (سبتمبر 1954). "نظرية أساسية جديدة لنظرية المعلومات". معاملات المجموعة المهنية لنظرية المعلومات التابعة لمعهد البحوث الاقتصادية . 4 (4): 2-22. رمز Bibcode : 1955PhDT........12F. doi : 10.1109/TIT.1954.1057459. hdl : 1721.1/4798 .
• لوندهايم، لارس (2002). "حول شانون وصيغة شانون" (PDF) . تيليكرونيك . 98 (1): 20-29.

• ماكاي، ديفيد جيه سي (2003). نظرية المعلومات والاستدلال وخوارزميات التعلم. مطبعة جامعة كامبريدج. رقم ISBN 0-521-64298-1. [مجانا على الانترنت]
• شانون، سي إي (1948). "نظرية رياضية في الاتصال". مجلة بيل التقنية للنظام . 27 (3): 379-423. doi :10.1002/j.1538-7305.1948.tb01338.x.
• شانون، سي إي (1998) [1948]. نظرية رياضية في الاتصال. مطبعة جامعة إلينوي.
• وولفويتز، ج. (1957). "ترميز الرسائل المعرضة لأخطاء عشوائية". مجلة إلينوي للرياضيات . 1 (4): 591-606. doi : 10.1215/ijm/1255380682 .