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

एक मनमाने ढंग से भिन्न चैनल (एवीसी) एक संचार चैनल मॉडल है जिसका उपयोग कोडिंग सिद्धांत में किया जाता है, और इसे सबसे पहले ब्लैकवेल, ब्रिमन और थॉमसियन द्वारा पेश किया गया था। इस विशेष संचार चैनल में अज्ञात पैरामीटर हैं जो समय के साथ बदल सकते हैं और कोडवर्ड के प्रसारण के दौरान इन परिवर्तनों का एक समान पैटर्न नहीं हो सकता है। $\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_{i}$ सेट में $\textstyle S$ प्रत्येक समय इकाई में मनमाने ढंग से परिवर्तन हो सकता है $\textstyle i$. इस चैनल मॉडल को क्लाउड शैनन|शैनन के बाइनरी सममित चैनल (बीएससी) के विकल्प के रूप में विकसित किया गया था, जहां चैनल मॉडल की संपूर्ण प्रकृति ज्ञात है, जो वास्तविक संचार चैनल स्थितियों के लिए अधिक यथार्थवादी है।

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

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

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

$\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 {\bar {e}}(s)$ किसी राज्य अनुक्रम के लिए त्रुटि की औसत संभावना है $\textstyle s$. सबसे बड़ा सूचना सिद्धांत#दर $\textstyle R$ AVC की चैनल क्षमता को दर्शाता है, जिसे द्वारा दर्शाया गया है $\textstyle c$.

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

• और AVC सममित है यदि $\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$ यदि और केवल यदि AVC सममित नहीं है। अगर $\textstyle c>0$, तब $\displaystyle c=\max _{P}I(P)$.

समरूपता के लिए पहले भाग का प्रमाण: यदि हम इसे सिद्ध कर सकें $\textstyle I(P)$ जब AVC सममित नहीं है तो सकारात्मक है, और फिर इसे सिद्ध करें $\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(y|x,s)=W'(y|s)$ कुछ के लिए $\textstyle W')$

$\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 P(x)$ पर निर्भर करता है $\textstyle 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}$. तो अब एक सममित AVC की परिभाषा को इस प्रकार फिर से लिखा जा सकता है: $\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)$ हमने पहले गणना की थी, इसलिए AVC वास्तव में सममित है $\textstyle I(P)$ के बराबर है $\textstyle 0$. इसलिए, $\textstyle I(P)$ केवल तभी सकारात्मक हो सकता है जब AVC सममित न हो।

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

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

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

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

ऐसे AVC के लिए, मौजूद है:

- एक इनपुट बाधा $\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$. सबसे बड़ा सूचना सिद्धांत#रेट अभी भी AVC की चैनल क्षमता माना जाता है, और अब इसे इस रूप में दर्शाया जाता है $\textstyle c(\Gamma ,\Lambda )$.

लेम्मा 1: कोई भी चैनल कोडिंग कहां $\textstyle \Lambda$ से बड़ा है $\textstyle \Lambda _{0}(P)$ अच्छा चैनल कोडिंग नहीं माना जा सकता, क्योंकि इस प्रकार की चैनल कोडिंग में त्रुटि की अधिकतम औसत संभावना उससे अधिक या उसके बराबर होती है $\textstyle {\frac {N-1}{2N}}-{\frac {1}{n}}{\frac {l_{max}^{2}}{n(\Lambda -\Lambda _{0}(P))^{2}}}$, कहाँ $\textstyle l_{max}$ का अधिकतम मान है $\textstyle l(s)$. यह एक अच्छी अधिकतम औसत त्रुटि संभावना नहीं है क्योंकि यह काफी बड़ी है, $\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 \Lambda$ और मनमाने ढंग से छोटा $\textstyle \alpha >0$, $\textstyle \beta >0$, $\textstyle \delta >0$, किसी भी ब्लॉक लंबाई के लिए $\textstyle n\geq n_{0}$ और किसी भी प्रकार के लिए $\textstyle P$ शर्तों के साथ $\textstyle \Lambda _{0}(P)\geq \Lambda +\alpha$ और $\displaystyle \min _{x\in X}P(x)\geq \beta$, और कहाँ $\textstyle P_{X_{r}}=P$, कोडवर्ड के साथ एक चैनल कोडिंग मौजूद है $\textstyle x_{1},\dots ,x_{N}$, प्रत्येक प्रकार का $\textstyle P$, जो निम्नलिखित समीकरणों को संतुष्ट करता है: $\textstyle {\frac {1}{n}}\log N>I(P,\Lambda )-\delta$, $\displaystyle \max _{l(s)\leq \Lambda }{\bar {e}}(s)\leq \exp(-n\gamma )$, और जहां सकारात्मक $\textstyle n_{0}$ और $\textstyle \gamma$ पर ही निर्भर हैं $\textstyle \alpha$, $\textstyle \beta$, $\textstyle \delta$, और दिया गया AVC।

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

यादृच्छिक AVC की क्षमता

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

इससे पहले कि हम प्रमेय 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