अर्बिट्ररीली वरयींग चैनल

अर्बिट्ररीली वरयींग चैनल (एवीसी) संचार चैनल मॉडल है जिसका उपयोग कोडिंग सिद्धांत में किया जाता है, और इसे सबसे पहले ब्लैकवेल, ब्रिमन और थॉमसियन द्वारा प्रस्तुत किया गया था। इस विशेष संचार चैनल में अज्ञात मापदंड हैं जो समय के साथ परिवर्तित हो सकते हैं और कोडवर्ड के प्रसारण के समय इन परिवर्तनों का समान क्रम नहीं हो सकता है। इस चैनल के $\textstyle n$ उपयोगों को स्टोकेस्टिक आव्यूह $\textstyle W^{n}:X^{n}\times$$\textstyle S^{n}\rightarrow Y^{n}$ का उपयोग करके वर्णित किया जा सकता है, जहां $\textstyle X$ इनपुट वर्णमाला है, $\textstyle Y$ आउटपुट वर्णमाला है, और $\textstyle W^{n}(y|x,s)$ स्थितियो $\textstyle S$ के दिए गए समुच्चय पर संभावना है, कि प्रेषित इनपुट $\textstyle x=(x_{1},\ldots ,x_{n})$ प्राप्त आउटपुट की ओर ले जाता है इस प्रकार $\textstyle y=(y_{1},\ldots ,y_{n})$ समुच्चय $\textstyle S$ में स्थिति $\textstyle s_{i}$ प्रत्येक समय इकाई $\textstyle i$ पर अर्बिट्ररीली वरयींग हो सकती है। इस चैनल को शैनन के बाइनरी सिमेट्रिक चैनल (बीएससी) के विकल्प के रूप में विकसित किया गया था, जहां चैनल की संपूर्ण प्रकृति को वास्तविक नेटवर्क चैनल स्थितियों के लिए अधिक यथार्थवादी माना जाता है।

क्षमताएं और संबंधित प्रमाण

नियतात्मक एवीसी की क्षमता

एवीसी की चैनल क्षमता कुछ मापदंडों के आधार पर भिन्न हो सकती है।

$\textstyle R$ एक नियतात्मक एवीसी चैनल कोडिंग के लिए एक प्राप्य सूचना सिद्धांत है यदि यह $\textstyle 0$ से बड़ा है, और यदि प्रत्येक धनात्मक $\textstyle \varepsilon$ और $\textstyle \delta$ के लिए, और बहुत बड़े $\textstyle n$, लंबाई-$\textstyle n$ ब्लॉक कोड के लिए है उपस्थित हैं जो निम्नलिखित समीकरणों को संतुष्ट करते हैं: $\textstyle {\frac {1}{n}}\log N>R-\delta$ और $\displaystyle \max _{s\in S^{n}}{\bar {e}}(s)\leq \varepsilon$ , जहां $\textstyle N$ $\textstyle Y$ में उच्चतम मान है और जहां $\textstyle N$ एक स्थिति अनुक्रम $\textstyle {\bar {e}}(s)$ के लिए त्रुटि की औसत संभावना है। सबसे बड़ी दर $\textstyle R$, एवीसी की क्षमता को दर्शाती है, जिसे $\textstyle c$ द्वारा दर्शाया गया है

जैसा कि आप देख सकते हैं, केवल उपयोगी स्थितियाँ तब होती हैं जब एवीसी की क्षमता $\textstyle 0$ से अधिक होती है, क्योंकि तब चैनल त्रुटियों के बिना प्रत्याभूत मात्रा में डेटा $\textstyle \leq c$ संचारित कर सकता है। जिससे हम एक प्रमेय से प्रारंभ करते हैं जो दिखाता है कि एवीसी में $\textstyle c$ कब धनात्मक है और इसके पश्चात् में विचार किए गए प्रमेय विभिन्न परिस्थितियों के लिए $\textstyle c$ की सीमा को कम कर देता है।

प्रमेय 1 प्रारंभ करने से पहले, कुछ परिभाषाओं पर ध्यान देने की आवश्यकता है:

• एक एवीसी सममित है यदि $\displaystyle \sum _{s\in S}W(y|x,s)U(s|x')=\sum _{s\in S}W(y|x',s)U(s|x)$ प्रत्येक $\textstyle (x,x',y,s)$ के लिए जहां $\textstyle x,x'\in X$, $\textstyle y\in Y$, और $\textstyle U(s|x)$ एक चैनल फलन है $\textstyle U:X\rightarrow S$
• $\textstyle X_{r}$, $\textstyle S_{r}$, और $\textstyle Y_{r}$ क्रमशः समुच्चय $\textstyle X$, $\textstyle S$, और $\textstyle Y$ में सभी यादृच्छिक चर हैं।
• $\textstyle P_{X_{r}}(x)$ इस प्रायिकता के समान है कि यादृच्छिक चर $\textstyle X_{r}$ $\textstyle x$ के समान है
• $\textstyle P_{S_{r}}(s)$ इस प्रायिकता के समान है कि यादृच्छिक चर $\textstyle S_{r}$ $\textstyle s$ के समान है
• $\textstyle P_{X_{r}S_{r}Y_{r}}$ का संयुक्त संभाव्यता द्रव्यमान फलन (पीएमएफ) है और $\textstyle P_{X_{r}}(x)$, $\textstyle P_{S_{r}}(s)$, और $\textstyle W(y|x,s)$ को औपचारिक रूप से $\textstyle P_{X_{r}S_{r}Y_{r}}$ के रूप में परिभाषित किया गया है
• $\textstyle P_{X_{r}S_{r}Y_{r}}(x,s,y)=P_{X_{r}}(x)P_{S_{r}}(s)W(y|x,s)$.
• $\textstyle H(X_{r})$ $\textstyle X_{r}$ की एन्ट्रापी है
• $\textstyle H(X_{r}|Y_{r})$ उस औसत संभावना के समान है कि $\textstyle X_{r}$ उन सभी मानों के आधार पर एक निश्चित मान होगा जिनके लिए $\textstyle Y_{r}$ संभवतः समान हो सकता है।
• $\textstyle I(X_{r}\land Y_{r})$ और $\textstyle X_{r}$ और $\textstyle Y_{r}$ की पारस्परिक जानकारी है और $\textstyle H(X_{r})-H(X_{r}|Y_{r})$ के समान है
• $\displaystyle I(P)=\min _{Y_{r}}I(X_{r}\land Y_{r})$ जहां न्यूनतम सभी यादृच्छिक चर $\textstyle Y_{r}$ पर है जैसे कि $\textstyle X_{r}$, $\textstyle S_{r}$, और $\textstyle Y_{r}$ को $\textstyle P_{X_{r}S_{r}Y_{r}}$ के रूप में वितरित किए गए हैं

प्रमेय 1: $\textstyle c>0$ यदि और केवल यदि एवीसी सममित नहीं है। यदि $\textstyle c>0$, तब $\displaystyle c=\max _{P}I(P)$.

समरूपता के लिए पहले भाग का प्रमाण: यदि हम सिद्ध कर सकते हैं कि एवीसी सममित नहीं होने पर $\textstyle I(P)$ धनात्मक है, और फिर सिद्ध करें कि $\textstyle c=\max _{P}I(P)$, तो हम सक्षम होंगे प्रमेय 1 को सिद्ध करने के लिए। मान लें कि $\textstyle I(P)$ $\textstyle 0$ के समान है। इस प्रकार $\textstyle I(P)$ की परिभाषा से, यह $\textstyle X_{r}$ और $\textstyle Y_{r}$ को स्वतंत्र यादृच्छिक चर बना देगा, कुछ $\textstyle S_{r}$ के लिए, क्योंकि इसका कारण यह होगा कि किसी भी यादृच्छिक चर की एन्ट्रॉपी दूसरे यादृच्छिक चर के मान पर निर्भर नहीं होगी। समीकरण $\textstyle P_{X_{r}S_{r}Y_{r}}$ का उपयोग करके हम $\textstyle P_{X_{r}}=P$ प्राप्त कर सकते हैं,

$\displaystyle P_{Y_{r}}(y)=\sum _{x\in X}\sum _{s\in S}P(x)P_{S_{r}}(s)W(y|x,s)$

$\textstyle \equiv ($चूँकि $\textstyle X_{r}$ और $\textstyle Y_{r}$ कुछ $\textstyle W')$ के लिए स्वतंत्र यादृच्छिक चर $\textstyle W(y|x,s)=W'(y|s)$ हैं$\textstyle )$

$\displaystyle P_{Y_{r}}(y)=\sum _{x\in X}\sum _{s\in S}P(x)P_{S_{r}}(s)W'(y|s)$

$\textstyle \equiv ($क्योंकि $\textstyle x$ केवल $\textstyle P(x)$ पर निर्भर करता है$\textstyle )$

$\displaystyle P_{Y_{r}}(y)=\sum _{s\in S}P_{S_{r}}(s)W'(y|s)\left[\sum _{x\in X}P(x)\right]$

$\textstyle \equiv ($क्योंकि $\displaystyle \sum _{x\in X}P(x)=1)$

$\displaystyle P_{Y_{r}}(y)=\sum _{s\in S}P_{S_{r}}(s)W'(y|s)$

तो अब हमारे निकट $\textstyle Y_{r}$ पर एक संभाव्यता वितरण है जो $\textstyle X_{r}$ से स्वतंत्र है। जिससे अब एक सममित एवीसी की परिभाषा को इस प्रकार फिर से लिखा जा सकता है: $\displaystyle \sum _{s\in S}W'(y|s)P_{S_{r}}(s)=\sum _{s\in S}W'(y|s)P_{S_{r}}(s)$ क्योंकि $\textstyle U(s|x)$ और $\textstyle W(y|x,s)$ दोनों फलन $\textstyle x$ पर आधारित हैं, उन्हें केवल $\textstyle s$ और $\textstyle y$ पर आधारित फलन से परिवर्तित कर दिया गया है। जैसा कि आप देख सकते हैं, दोनों पक्ष अब $\textstyle P_{Y_{r}}(y)$ के समान हैं, जिसकी हमने पहले गणना की थी, इसलिए एवीसी वास्तव में सममित है जब $\textstyle I(P)$ $\textstyle 0$ के समान है। इसलिए, $\textstyle I(P)$ केवल तभी धनात्मक हो सकता है जब एवीसी सममित नही होता है।

क्षमता के लिए दूसरे भाग का प्रमाण: पूर्ण प्रमाण के लिए नीचे संदर्भित पेपर "अर्बिट्ररीली वरयींग चैनल की क्षमता: धनात्मकता, बाधाएं" देखें।

इनपुट और स्थिति बाधाओं के साथ एवीसी की क्षमता

अगला प्रमेय इनपुट और/या स्थिति बाधाओं के साथ एवीसी के लिए चैनल क्षमता से सामना करता है। यह बाधाएं एवीसी पर ट्रांसमिशन और त्रुटि की संभावनाओं की बहुत बड़ी श्रृंखला को कम करने में सहायता करती हैं, जिससे यह देखना कम सरल हो जाता है कि एवीसी कैसे व्यवहार करता है।

इससे पहले कि हम प्रमेय 2 पर आगे बढ़ें, हमें कुछ परिभाषाएँ और लेम्मा (गणित) परिभाषित करने की आवश्यकता है:

ऐसे एवीसी के लिए, उपस्थित है:

- इनपुट बाधा $\textstyle \Gamma$ समीकरण के आधार पर $\displaystyle g(x)={\frac {1}{n}}\sum _{i=1}^{n}g(x_{i})$, जहाँ $\textstyle x\in X$ और $\textstyle x=(x_{1},\dots ,x_{n})$.

- स्थिति बाधा $\textstyle \Lambda$, समीकरण के आधार पर $\displaystyle l(s)={\frac {1}{n}}\sum _{i=1}^{n}l(s_{i})$, जहाँ $\textstyle s\in X$ और $\textstyle s=(s_{1},\dots ,s_{n})$.

- $\displaystyle \Lambda _{0}(P)=\min \sum _{x\in X,s\in S}P(x)l(s)$

$\textstyle I(P,\Lambda )$ पहले बताए गए $\textstyle I(P)$ समीकरण के समान है $\displaystyle I(P,\Lambda )=\min _{Y_{r}}I(X_{r}\land Y_{r})$, किन्तु अब समीकरण में किसी भी स्थिति $\textstyle s$ या $\textstyle S_{r}$ को $\textstyle l(s)\leq \Lambda$ स्थिति प्रतिबंध का पालन करना होगा।

मान लें कि $\textstyle g(x)$, $\textstyle X$ पर एक गैर-ऋणात्मक-मूल्यवान फलन है और $\textstyle l(s)$ $\textstyle S$ पर एक दिया गया गैर-ऋणात्मक-मूल्यवान फलन है और दोनों के लिए न्यूनतम मान $\textstyle 0$ है। साहित्य में मेरे पास है इस विषय पर पढ़ें, इस प्रकार $\textstyle g(x)$ और $\textstyle l(s)$ (चर $\textstyle x_{i}$, के लिए) दोनों की स्पष्ट परिभाषाओं का कभी भी औपचारिक रूप से वर्णन नहीं किया गया है। इनपुट बाधा $\textstyle \Gamma$ और स्थिति बाधा $\textstyle \Lambda$ की उपयोगिता इन समीकरणों पर आधारित होती है।

इनपुट और/या स्थिति बाधाओं वाले एवीसी के लिए, दर $\textstyle R$ अब $\textstyle x_{1},\dots ,x_{N}$ प्रारूप के कोडवर्ड तक सीमित है जो $\textstyle g(x_{i})\leq \Gamma$ को संतुष्ट करते हैं गामा, और अब स्थिति $\textstyle s$ उन सभी स्थितिों तक सीमित है जो $\textstyle l(s)\leq \Lambda$ को संतुष्ट करते हैं। सबसे बड़ी दर अभी भी एवीसी की क्षमता मानी जाती है, और अब इसे $\textstyle c(\Gamma ,\Lambda )$ के रूप में दर्शाया जाता है

लेम्मा 1: कोई भी कोड जहां $\textstyle \Lambda$ $\textstyle \Lambda _{0}(P)$ से बड़ा है, उसे "अच्छा" कोड नहीं माना जा सकता है, क्योंकि उन प्रकार के कोड में त्रुटि की अधिकतम औसत संभावना $\textstyle l(s)$ से अधिक या उसके समान होती है। $\textstyle {\frac {N-1}{2N}}-{\frac {1}{n}}{\frac {l_{max}^{2}}{n(\Lambda -\Lambda _{0}(P))^{2}}}$, जहां $\textstyle l_{max}$ का अधिकतम मान है। यह एक अच्छी अधिकतम औसत त्रुटि संभावना नहीं है क्योंकि यह अधिक बड़ी है, $\textstyle {\frac {N-1}{2N}}$ $\textstyle {\frac {1}{2}}$ के निकट है, और दूसरा भाग समीकरण का भाग बहुत छोटा होगा क्योंकि $\textstyle (\Lambda -\Lambda _{0}(P))$ मान का वर्ग किया गया है, और $\textstyle \Lambda$ को $\textstyle \Lambda _{0}(P)$ से बड़ा माना गया है ). इसलिए, त्रुटि के बिना कोडवर्ड प्राप्त करना बहुत ही असंभव होगा। यही कारण है कि $\textstyle \Lambda _{0}(P)$ स्थिति प्रमेय 2 में उपस्थित है।

प्रमेय 2: किसी भी ब्लॉक लंबाई $\textstyle \alpha >0$, $\textstyle \beta >0$, $\textstyle \delta >0$ के लिए और किसी भी प्रकार $\textstyle P$ के लिए नियमो $\textstyle n\geq n_{0}$ के लिए एक धनात्मक $\displaystyle \min _{x\in X}P(x)\geq \beta$ और अर्बिट्ररीली से छोटा $\textstyle \Lambda _{0}(P)\geq \Lambda +\alpha$ दिया गया है। $\textstyle x_{1},\dots ,x_{N}$ $\textstyle {\frac {1}{n}}\log N>I(P,\Lambda )-\delta$, और जहां धनात्मक $\textstyle n_{0}$ और $\textstyle \gamma$ केवल $\textstyle \alpha$, $\textstyle \beta$, $\textstyle \delta$ और दिए गए एवीसी पर निर्भर करते हैं।

प्रमेय 2 का प्रमाण: पूर्ण प्रमाण के लिए नीचे संदर्भित पेपर "अर्बिट्ररीली वरयींग चैनल की क्षमता: धनात्मकता, बाधाएं" देखें।

यादृच्छिक एवीसी की क्षमता

इस प्रकार अगला प्रमेय सूचना एन्ट्रॉपी चैनल कोडिंग वाले एवीसी के लिए होगा। ऐसे एवीसी के लिए चैनल कोडिंग लंबाई-एन ब्लॉक कोड के वर्ग के मानो के साथ यादृच्छिक चर है, और इन चैनल कोडिंग को कोडवर्ड के वास्तविक मूल्य पर निर्भर/विश्वास करने की अनुमति नहीं है। इन चैनल कोडिंग में इसकी यादृच्छिक प्रकृति के कारण किसी भी चैनल मॉडल के लिए समान अधिकतम और औसत त्रुटि संभावना मूल्य होता है। इस प्रकार की चैनल कोडिंग एवीसी के कुछ गुणों को अधिक स्पष्ट बनाने में भी सहायता करती है।

इससे पहले कि हम प्रमेय 3 पर आगे बढ़ें, हमें पहले कुछ महत्वपूर्ण शब्दों को परिभाषित करना होगा:

$\displaystyle W_{\zeta }(y|x)=\sum _{s\in S}W(y|x,s)P_{S_{r}}(s)$

$\textstyle I(P,\zeta )$ पहले उल्लिखित $\textstyle I(P)$ समीकरण के समान है, $\displaystyle I(P,\zeta )=\min _{Y_{r}}I(X_{r}\land Y_{r})$, किन्तु अब प्रायिकता द्रव्यमान फलन $\textstyle P_{S_{r}}(s)$ को समीकरण में जोड़ा गया है, जिससे न्यूनतम $\textstyle I(P,\zeta )$ एक नया रूप आधारित हो गया है $\textstyle P_{X_{r}S_{r}Y_{r}}$ का, जहां $\textstyle W_{\zeta }(y|x)$ के स्थान पर $\textstyle W(y|x,s)$ प्रतिस्थापित करता है

प्रमेय 3: एवीसी की सूचना एन्ट्रापी चैनल कोडिंग के लिए चैनल क्षमता $\displaystyle c=max_{P}I(P,\zeta )$ है .

प्रमेय 3 का प्रमाण: पूर्ण प्रमाण के लिए नीचे संदर्भित रैंडम कोडिंग के अनुसार कुछ चैनल कक्षाओं की क्षमता वाला पेपर देखें।

यह भी देखें

• बाइनरी सममित चैनल
• बाइनरी इरेज़र चैनल
• जेड-चैनल (सूचना सिद्धांत)
• चैनल मॉडल
• सूचना सिद्धांत
• कोडिंग सिद्धांत

संदर्भ

• Ahlswede, Rudolf and Blinovsky, Vladimir, "Classical Capacity of Classical-Quantum Arbitrarily Varying Channels," https://ieeexplore.ieee.org/document/4069128
• Blackwell, David, Breiman, Leo, and Thomasian, A. J., "The Capacities of Certain Channel Classes Under Random Coding," https://www.jstor.org/stable/2237566
• Csiszar, I. and Narayan, P., "Arbitrarily varying channels with constrained inputs and states," http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=2598&isnumber=154
• Csiszar, I. and Narayan, P., "Capacity and Decoding Rules for Classes of Arbitrarily Varying Channels," http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=32153&isnumber=139
• Csiszar, I. and Narayan, P., "The capacity of the arbitrarily varying channel revisited: positivity, constraints," http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=2627&isnumber=155
• Lapidoth, A. and Narayan, P., "Reliable communication under channel uncertainty," http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=720535&isnumber=15554