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

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 49 صور
الموسوعة الحرة

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

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

ملخص

تُحدد هذه النظرية، التي وضعها كلود شانون عام ١٩٤٨، أقصى كفاءة ممكنة لأساليب تصحيح الأخطاء في مقابل مستويات التشويش والتشويش وتلف البيانات . ولنظرية شانون تطبيقات واسعة النطاق في كلٍ من الاتصالات وتخزين البيانات . وتُعد هذه النظرية ذات أهمية تأسيسية في مجال نظرية المعلومات الحديثة . وقد قدم شانون مُلخصًا فقط للبرهان، بينما ورد أول برهان دقيق للحالة المنفصلة في ( فاينشتاين ١٩٥٤ ) .

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

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

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

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

بيان رياضي

رسم بياني يوضح نسبة سعة القناة ( المحور الصادي ) التي يمكن استخدامها للحمولة بناءً على مدى ضوضاء القناة (احتمالية انعكاس البتات؛ المحور السيني ).

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

→رسالةدبليوالمشفرون→هـنجoدهـدsهـquهـنجهـXنقناةص(y|x)→RهـجهـأناvهـدsهـquهـنجهـYنجهاز فك التشفيرزن→هـsتأنامأتهـدمهـssأزهـدبليو^{\displaystyle {\xrightarrow[{\text{الرسالة}}]{W}}{\begin{array}{|c| }\hline {\text{المشفّر}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {تسلسل atop المشفّر} }]{X^{n}}}{\begin{array}{|c| }\hline {\text{القناة}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {تسلسل atop المستلم} }]{Y^{n}}}{\begin{array}{|c| }\hline {\text{المفكك}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {رسالة atop المقدرة} }]{\hat {W}}}}

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

Pهـ=برو{دبليو^≠دبليو}.{\displaystyle P_{e}={\text{Pr}}\left\{{\hat {W}}\neq W\right\}.}

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

1. لكل قناة منفصلة عديمة الذاكرة، تُعرَّف سعة القناة بدلالة المعلومات المتبادلة.أنا(X؛Y){\displaystyle I(X;Y)}مثل
 ج=رشفةصXأنا(X؛Y){\displaystyle \ C=\sup _{p_{X}}I(X;Y)}[ 2 ]
يتمتع بالخاصية التالية. لأيϵ>0{\displaystyle \epsilon >0}وR<ج{\displaystyle R<C}، بالنسبة للكبير بما فيه الكفايةشمال{\displaystyle N}يوجد رمز بطولشمال{\displaystyle N}وقيم≥R{\displaystyle \geq R}وخوارزمية فك تشفير، بحيث يكون الحد الأقصى لاحتمالية خطأ الكتلة هو≤ϵ{\displaystyle \leq \epsilon }.
2. إذا كان هناك احتمال لخطأ في البتصب{\displaystyle p_{b}}مقبول، تصل الأسعار إلىR(صب){\displaystyle R(p_{b})}قابلة للتحقيق، حيث
R(صب)=ج1-ح2(صب).{\displaystyle R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.}
وح2(صب){\displaystyle H_{2}(p_{b})}دالة الإنتروبيا الثنائية
ح2(صب)=-[صبسجل2⁡صب+(1-صب)سجل2⁡(1-صب)]{\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}}معدلات أكبر منR(صب){\displaystyle R(p_{b})}غير قابلة للتحقيق.

(MacKay (2003), p.  162; cf Gallager (1968), ch.5; Cover and Thomas (1991), p.  198; Shannon (1948) thm. 11)

مخطط الإثبات

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

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

إمكانية تحقيق ذلك للقنوات المنفصلة عديمة الذاكرة

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

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

بناءً على حجة متعلقة بـ AEP، بالنظر إلى قناة، الطولن{\displaystyle n}سلاسل من رموز المصدرX1ن{\displaystyle X_{1}^{n}}والطولن{\displaystyle n}سلاسل مخرجات القنواتY1ن{\displaystyle Y_{1}^{n}}يمكننا تعريف مجموعة نموذجية مشتركة على النحو التالي:

أε(ن)={(xن،yن)∈Xن×Yن{\displaystyle A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}}
2-ن(ح(X)+ε)≤ص(X1ن)≤2-ن(ح(X)-ε){\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}}
2-ن(ح(Y)+ε)≤ص(Y1ن)≤2-ن(ح(Y)-ε){\displaystyle 2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}}
2-ن(ح(X،Y)+ε)≤ص(X1ن،Y1ن)≤2-ن(ح(X،Y)-ε)}{\displaystyle {2^{-n(H(X,Y)+\varepsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon )}\}}

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

خطوات

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

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

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

يُعرِّف:هـأنا={(X1ن(أنا)،Y1ن)∈أε(ن)}،أنا=1،2،...،2نR{\displaystyle E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,\dots ,2^{nR}}

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

P(خطأ)=P(خطأ|دبليو=1)≤P(هـ1ج)+∑أنا=22نRP(هـأنا)≤P(هـ1ج)+(2نR-1)2-ن(أنا(X؛Y)-3ε)≤ε+2-ن(أنا(X؛Y)-R-3ε).{\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}}}

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

عكس ضعيف للقنوات المنفصلة عديمة الذاكرة

لنفترض رمزًا لـ2نR{\displaystyle 2^{nR}}كلمات التشفير. ليكن W مؤشرًا مرسومًا بشكل منتظم على هذه المجموعة.Xن{\displaystyle X^{n}}وYن{\displaystyle Y^{n}}لتكن الكلمات المشفرة المرسلة والكلمات المشفرة المستلمة، على التوالي.

  1. نR=ح(دبليو)=ح(دبليو|Yن)+أنا(دبليو؛Yن){\displaystyle nR=H(W)=H(W|Y^{n})+I(W;Y^{n})}باستخدام الهويات التي تتضمن الإنتروبيا والمعلومات المتبادلة
  2. ≤ح(دبليو|Yن)+أنا(Xن(دبليو)؛Yن){\displaystyle \leq H(W|Y^{n})+I(X^{n}(W);Y^{n})}بما أن X دالة لـ W
  3. ≤1+Pهـ(ن)نR+أنا(Xن(دبليو)؛Yن){\displaystyle \leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})}باستخدام متباينة فانو
  4. ≤1+Pهـ(ن)نR+نج{\displaystyle \leq 1+P_{e}^{(n)}nR+nC}وذلك لأن السعة تعظم المعلومات المتبادلة.

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

محول قوي للقنوات المنفصلة عديمة الذاكرة

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

Pهـ≥1-4أن(R-ج)2-هـ-ن(R-ج)2{\displaystyle P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-{\frac {n(R-C)}{2}}}}

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

تحسينات طول الكتلة المحدودة

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

نظرية ترميز القناة للقنوات غير الثابتة عديمة الذاكرة

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

ثم تُعطى سعة القناة بواسطة

ج=ليممعلوماتالأعلىص(X1)،ص(X2)،...1ن∑أنا=1نأنا(Xأنا؛Yأنا).{\displaystyle C=\lim \inf \max _{p^{(X_{1})},p^{(X_{2})},...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i}).}

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

مخطط البرهان

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

تظهر الجوانب الفنية لمصطلح "النهاية" عندما1ن∑أنا=1نجأنا{\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}لا تتقارب.

انظر أيضاً

ملحوظات

  1. ↑ ساي-يونغ تشونغ؛ فورني، جي دي ؛ ريتشاردسون، تي جيه؛ أوربانك، آر. (فبراير 2001). "حول تصميم رموز التحقق من التكافؤ منخفضة الكثافة ضمن نطاق 0.0045 ديسيبل من حد شانون" (ملف PDF) . رسائل اتصالات IEEE . 5 (2): 58-60 . Bibcode : 2001IComL...5...58C . doi : 10.1109/4234.905935 . S2CID 7381972 . 
  2. ↑ للاطلاع على وصف وظيفة "sup"، انظر Supremum
  3. ↑ غالاغر، روبرت (1968). نظرية المعلومات والاتصالات الموثوقة . وايلي. ISBN 0-471-29048-3.
  4. ↑ هاياشي، ماساهيتو (نوفمبر 2009). "نهج طيف المعلومات لمعدل الترميز من الدرجة الثانية في ترميز القناة". معاملات IEEE في نظرية المعلومات . 55 (11): 4947-4966 . arXiv : 0801.2242 . doi : 10.1109/TIT.2009.2030478 .

مراجع