शैनन का सोर्स कोडिंग थेरोम: Difference between revisions

Revision as of 13:57, 17 July 2023

सूचना सिद्धांत में, शैनन का सोर्स कोडिंग थेरोम (या नीरव कोडिंग थेरोम) संभावित डेटा संपीड़न की सीमा और शैनन एन्ट्रॉपी के परिचालन अर्थ को स्थापित करता है।

क्लाउड शैनन के नाम पर, सोर्स कोडिंग थेरोम से पता चलता है (सीमा में, स्वतंत्र और समान रूप से वितरित यादृच्छिक चर (i.i.d.) डेटा की धारा की लंबाई अनंत तक जाती है) डेटा को इस तरह संपीड़ित करना असंभव है इसे संपीड़ित करना असंभव है कि कोड दर (प्रति प्रतीक बिट्स की औसत संख्या) सोर्स की शैनन एन्ट्रॉपी से कम है, यह लगभग निश्चित नहीं है कि जानकारी लुप्त हों गयी है। चूँकि, नुकसान की नगण्य संभावना के साथ, कोड दर को अव्यवस्थिततः ढंग से शैनन एन्ट्रापी के समीप प्राप्त करना संभव होता है।

प्रतीक कोड के लिए सोर्स कोडिंग थेरोम इनपुट शब्द की एन्ट्रॉपी (जिसे एक यादृच्छिक चर के रूप में देखा जाता है) और लक्ष्य वर्णमाला के आकार का एक फलन के रूप में कोडवर्ड की न्यूनतम संभावित अपेक्षित लंबाई पर एक ऊपरी और निचली सीमा रखता है।

कथन

सोर्स कोडिंग एक सूचना सोर्स से प्रतीकों (एक अनुक्रम) को वर्णमाला प्रतीकों को (सामान्यतः बिट्स) अनुक्रम की मैपिंग करता है, जिससे की सोर्स प्रतीकों को बाइनरी बिट्स (दोषरहित सोर्स कोडिंग) से बिल्कुल पुनर्प्राप्त किया जा सके या कुछ विरूपण के भीतर पुनर्प्राप्त किया जा सके (हानिपूर्ण सोर्स कोडिंग)। डेटा संपीड़न के पीछे यही अवधारणा होती है।

सोर्स कोडिंग थेरोम

सूचना सिद्धांत में, सोर्स कोडिंग थेरोम (शैनन 1948)^[1] अनौपचारिक रूप से बताता है कि (मैकके 2003, पृष्ठ 81,^[2] कवर 2006, अध्याय 5^[3]): $N$ आई.आई.डी. एन्ट्रापी H(X) वाले प्रत्येक यादृच्छिक चर को सूचना हानि के नगण्य जोखिम के साथ N H(X) बिट्स से अधिक में संपीड़ित किया जा सकता हैजैसे $N \to \infty$ ; किन्तु इसके विपरीत, सके विपरीत, यदि उन्हें $N H (X)$ बिट्स यह लगभग निश्चित है कि जानकारी हों जाती है।

$NH(X)$ कोडित अनुक्रम संपीड़ित संदेश को द्विअर्थी विधि से दर्शाता है, इस धारणा के तहत कि डिकोडर सोर्स को जानता है। व्यावहारिक दृष्टिकोण से, यह परिकल्पना सदैव सत्य नहीं होती है। परिणामस्वरूप, जब एन्ट्रापी एन्कोडिंग लागू होती है तो संचरित संदेश होता है। $NH(X)+(inf.source)$ . सामान्यतः पर, सोर्स की विशेषता बताने वाली जानकारी प्रेषित संदेश की प्रारम्भिक में डाली जाती है।

प्रतीक कोड के लिए सोर्स कोडिंग थेरोम

मान लीजिए $Σ 1, Σ 2$ दो परिमित अक्षरों को दर्शाते हैं और मान लेते हैं $Σ * 1$ और $Σ * 2$ उन अक्षरों से (क्रमशः) सभी परिमित शब्दों के समुच्चय को निरूपित करें।

मान लीजिए कि $X$ एक यादृच्छिक चर होता है जो मान लेते हैं $Σ 1$ और $f$ एक चर लंबाई कोड को विशिष्ट रूप से डिकोड करने योग्य कोड से $Σ * 1$ को $Σ * 2$

जहाँ $|Σ 2 | = a$ होता है। मान लीजिए S कोडवर्ड $f (X)$ की लंबाई द्वारा दिए गए यादृच्छिक चर को दर्शाता है।

यदि $f$ इस अर्थ में इष्टतम है कि इसमें $X$ के लिए न्यूनतम अपेक्षित शब्द लंबाई होती है, तो (शैनन 1948):

{\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} [S]<{\frac {H(X)}{\log _{2}a}}+1

जहाँ $\mathbb {E}$ अपेक्षित मान संक्रियक को दर्शाता है।

प्रमाण: सोर्स कोडिंग थेरोम

मान लीजिए $X$ एक आई.आई.डी. सोर्स , इसकी समय श्रृंखला $X 1, ..., X n$ आई.आई.डी. होती है असतत-मूल्य वाले मामले में एन्ट्रापी $H (X)$ और निरंतर-मूल्य वाले अंतर एन्ट्रापी के साथ सोर्स कोडिंग थेरोम में कहा गया है कि किसी भी $ε > 0$ , अर्थात किसी भी सूचना सिद्धांत दर के लिए $H (X) + ε$ के लिए जो सोर्स की एन्ट्रापी से बड़ी होती है, पर्याप्त बड़ा $n$ और एक एनकोडर होता है जो $n$ आई.आई.डी. होता है। सोर्स की पुनरावृत्ति, $X 1: n$ , और इसे मैप करता है $n (H (X) + ε)$ बाइनरी बिट्स जैसे कि सोर्स प्रतीक $X 1: n$ कम से कम $1 - ε$ की संभावना के साथ बाइनरी बिट्स से पुनर्प्राप्त करने योग्य होते हैं ।

साध्यता का प्रमाण. कुछ $ε > 0$ , और मान लेते है

p(x_{1},\ldots ,x_{n})=\Pr \left[X_{1}=x_{1},\cdots ,X_{n}=x_{n}\right].

विशिष्ट सेट, $A ε n$ , को इस प्रकार परिभाषित किया गया है:

A_{n}^{\varepsilon }=\left\{(x_{1},\cdots ,x_{n})\ :\ \left|-{\frac {1}{n}}\log p(x_{1},\cdots ,x_{n})-H_{n}(X)\right|<\varepsilon \right\}.

असतत-समय i.i.d. के लिए एसिम्प्टोटिक समविभाजन संपत्ति#AEP सोर्स (एईपी) से पता चलता है कि यह काफी बड़े पैमाने पर है $n$ , संभावना है कि सोर्स द्वारा उत्पन्न अनुक्रम विशिष्ट सेट में निहित है, $A ε n$ , जैसा कि परिभाषित किया गया है एक दृष्टिकोण। विशेष रूप से, पर्याप्त रूप से बड़े के लिए $n$ , $P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })$ मनमाने ढंग से 1 के समीप और विशेष रूप से, इससे अधिक बनाया जा सकता है $1-\varepsilon$ (देखना है की असतत समय i.i.d. के लिए स्पर्शोन्मुख समविभाजन संपत्ति AEP प्रमाण के लिए सोर्स होते है )

विशिष्ट सेटों की परिभाषा का तात्पर्य है कि वे अनुक्रम जो विशिष्ट सेट में स्थित हैं, संतुष्ट करते हैं:

2^{-n(H(X)+\varepsilon )}\leq p\left(x_{1},\cdots ,x_{n}\right)\leq 2^{-n(H(X)-\varepsilon )}

ध्यान दें कि:

क्रम की संभावना $(X_{1},X_{2},\cdots X_{n})$ से खींचा जा रहा है $A ε n$ से बड़ा होता है $1 - ε$ .
$\left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}$ , जो बायीं ओर (निचली सीमा) से आता है $p(x_{1},x_{2},\cdots x_{n})$ .
$\left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}$ , जो ऊपरी सीमा से अनुसरण करता है $p(x_{1},x_{2},\cdots x_{n})$ और पूरे सेट की कुल संभावना पर निचली सीमा $A ε n$ .

तब से $\left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )},n(H(X)+\varepsilon )$ इस सेट में किसी भी स्ट्रिंग को इंगित करने के लिए बिट्स पर्याप्त हैं।

एन्कोडिंग एल्गोरिदम: एन्कोडर जांच करता है कि इनपुट अनुक्रम विशिष्ट सेट के भीतर है या नहीं; यदि हाँ, तो यह विशिष्ट सेट के भीतर इनपुट अनुक्रम के सूचकांक को आउटपुट करता है; यदि नहीं, तो एनकोडर एक मनमाना आउटपुट देता है $n (H (X) + ε)$ अंकों की संख्या। जब तक इनपुट अनुक्रम विशिष्ट सेट के भीतर रहता है (कम से कम संभावना के साथ)। $1 - ε$ ), एनकोडर कोई त्रुटि नहीं करता है। तो, एनकोडर की त्रुटि की संभावना ऊपर से सीमित है $ε$ .

वार्तालाप का प्रमाण. इसका विपरीत यह दर्शाकर सिद्ध किया जाता है कि आकार का कोई भी सेट इससे छोटा है $A ε n$ (प्रतिपादक के अर्थ में) दूर से बंधे संभाव्यता के एक सेट को कवर करेगा $1$ .

प्रमाण: प्रतीक कोड के लिए सोर्स कोडिंग थेरोम

के लिए $1 \leq i \leq n$ होने देना $s i$ प्रत्येक संभव शब्द की लंबाई को निरूपित करें $x i$ . परिभाषित करना $q_{i}=a^{-s_{i}}/C$ , कहाँ $C$ को इसलिए चुना गया है $q 1 + ... + q n = 1$ . तब

{\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&=\mathbb {E} S\log _{2}a\\\end{aligned}}

जहां दूसरी पंक्ति गिब्स की असमानता से आती है और पांचवीं पंक्ति क्राफ्ट की असमानता से आती है:

C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1

इसलिए $log C \leq 0$ .

दूसरी असमानता के लिए हम निर्धारित कर सकते हैं

s_{i}=\lceil -\log _{a}p_{i}\rceil

जिससे की

-\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1

इसलिए

a^{-s_{i}}\leq p_{i}

और

\sum a^{-s_{i}}\leq \sum p_{i}=1

और इसलिए क्राफ्ट की असमानता के कारण उन शब्द लंबाई वाला एक उपसर्ग-मुक्त कोड मौजूद है। इस प्रकार न्यूनतम $S$ संतुष्ट करता है

{\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&={\frac {H(X)}{\log _{2}a}}+1\\\end{aligned}}

गैर-स्थिर स्वतंत्र सोर्स ों तक विस्तार

असतत समय गैर-स्थिर स्वतंत्र सोर्स ों के लिए निश्चित दर दोषरहित सोर्स कोडिंग

विशिष्ट समुच्चय को $A ε n$ के रूप मे परिभाषित करें जैसा:

A_{n}^{\varepsilon }=\left\{x_{1}^{n}\ :\ \left|-{\frac {1}{n}}\log p\left(X_{1},\cdots ,X_{n}\right)-{\overline {H_{n}}}(X)\right|<\varepsilon \right\}.

फिर, दिया गया $δ > 0$ के लिए, पर्याप्त बड़े $n$ के लिए, $Pr(A ε n) > 1 - δ$ अब हम केवल विशिष्ट सेट में अनुक्रमों को एन्कोड करते हैं, और सोर्स कोडिंग में सामान्य विधियों से पता चलता है कि इस सेट की कार्डिनैलिटी इससे छोटी होती है कि इस प्रकार, औसतन, $2^{n({\overline {H_{n}}}(X)+\varepsilon )}$ से अधिक संभावना के साथ एन्कोडिंग के लिए पर्याप्त हैं, जहां $n$ को बड़ा बनाकर ε और δ को मनमाने ढंग से छोटा किया जा सकता है।

यह भी देखें

चैनल कोडिंग
शोर-चैनल कोडिंग थेरोम
त्रुटि प्रतिपादक
एसिम्प्टोटिक समविभाजन संपत्ति (एईपी)

संदर्भ

↑ C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948
↑ David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
↑ Cover, Thomas M. (2006). "Chapter 5: Data Compression". Elements of Information Theory. John Wiley & Sons. pp. 103–142. ISBN 0-471-24195-4.

[Shannon-1] C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948

[MacKay-2] David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1

[Cover-3] Cover, Thomas M. (2006). "Chapter 5: Data Compression". Elements of Information Theory. John Wiley & Sons. pp. 103–142. ISBN 0-471-24195-4.

[1]

[2]

[3]

@@ Line 4: / Line 4: @@
 {{about|डेटा संपीड़न में स्रोत कोडिंग का सिद्धांत|कंप्यूटर प्रोग्रामिंग में शब्द|स्रोत कोड}}
-[[सूचना सिद्धांत]] में, '''शैनन का स्रोत कोडिंग प्रमेय''' (या नीरव कोडिंग प्रमेय) संभावित डेटा संपीड़न की सीमा और शैनन एन्ट्रॉपी के परिचालन अर्थ को स्थापित करता है।
+[[सूचना सिद्धांत]] में, '''शैनन का सोर्स  कोडिंग थेरोम''' (या नीरव कोडिंग थेरोम) संभावित डेटा संपीड़न की सीमा और शैनन एन्ट्रॉपी के परिचालन अर्थ को स्थापित करता है।
-[[क्लाउड शैनन]] के नाम पर, '''स्रोत कोडिंग प्रमेय''' से पता चलता है (सीमा में, स्वतंत्र और समान रूप से वितरित  यादृच्छिक चर (i.i.d.) डेटा की धारा की लंबाई अनंत तक जाती है) डेटा को इस तरह संपीड़ित करना असंभव है इसे संपीड़ित करना असंभव है कि कोड दर (प्रति प्रतीक बिट्स की औसत संख्या) स्रोत की शैनन एन्ट्रॉपी से कम है, यह लगभग निश्चित नहीं है कि जानकारी लुप्त हों गयी है। चूँकि, नुकसान की नगण्य संभावना के साथ, कोड दर को अव्यवस्थिततः ढंग से [[शैनन एन्ट्रापी]] के समीप प्राप्त करना संभव होता है।
+[[क्लाउड शैनन]] के नाम पर, '''सोर्स  कोडिंग थेरोम''' से पता चलता है (सीमा में, स्वतंत्र और समान रूप से वितरित  यादृच्छिक चर (i.i.d.) डेटा की धारा की लंबाई अनंत तक जाती है) डेटा को इस तरह संपीड़ित करना असंभव है इसे संपीड़ित करना असंभव है कि कोड दर (प्रति प्रतीक बिट्स की औसत संख्या) सोर्स  की शैनन एन्ट्रॉपी से कम है, यह लगभग निश्चित नहीं है कि जानकारी लुप्त हों गयी है। चूँकि, नुकसान की नगण्य संभावना के साथ, कोड दर को अव्यवस्थिततः ढंग से [[शैनन एन्ट्रापी]] के समीप प्राप्त करना संभव होता है।
-प्रतीक कोड के लिए स्रोत '''कोडिंग प्रमेय''' इनपुट शब्द की [[एन्ट्रॉपी (सूचना सिद्धांत)|एन्ट्रॉपी]] (जिसे एक यादृच्छिक चर के रूप में देखा जाता है) और लक्ष्य वर्णमाला के आकार का एक फलन के रूप में कोडवर्ड की न्यूनतम संभावित अपेक्षित लंबाई पर एक ऊपरी और निचली सीमा रखता है।
+प्रतीक कोड के लिए सोर्स  '''कोडिंग थेरोम''' इनपुट शब्द की [[एन्ट्रॉपी (सूचना सिद्धांत)|एन्ट्रॉपी]] (जिसे एक यादृच्छिक चर के रूप में देखा जाता है) और लक्ष्य वर्णमाला के आकार का एक फलन के रूप में कोडवर्ड की न्यूनतम संभावित अपेक्षित लंबाई पर एक ऊपरी और निचली सीमा रखता है।
 == कथन ==
-स्रोत कोडिंग एक सूचना स्रोत से प्रतीकों (एक अनुक्रम) को वर्णमाला प्रतीकों को (सामान्यतः  बिट्स) अनुक्रम की मैपिंग करता है, जिससे की स्रोत प्रतीकों को बाइनरी बिट्स (दोषरहित स्रोत कोडिंग) से बिल्कुल पुनर्प्राप्त किया जा सके या कुछ विरूपण के भीतर पुनर्प्राप्त किया जा सके (हानिपूर्ण स्रोत कोडिंग)। डेटा संपीड़न के पीछे यही अवधारणा होती है।
+सोर्स  कोडिंग एक सूचना सोर्स  से प्रतीकों (एक अनुक्रम) को वर्णमाला प्रतीकों को (सामान्यतः  बिट्स) अनुक्रम की मैपिंग करता है, जिससे की सोर्स  प्रतीकों को बाइनरी बिट्स (दोषरहित सोर्स  कोडिंग) से बिल्कुल पुनर्प्राप्त किया जा सके या कुछ विरूपण के भीतर पुनर्प्राप्त किया जा सके (हानिपूर्ण सोर्स  कोडिंग)। डेटा संपीड़न के पीछे यही अवधारणा होती है।
-=== स्रोत कोडिंग प्रमेय ===
+=== सोर्स  कोडिंग थेरोम ===
-सूचना सिद्धांत में, स्रोत कोडिंग प्रमेय (शैनन 1948)<ref name="Shannon"/> अनौपचारिक रूप से बताता है कि (मैकके 2003, पृष्ठ 81,<ref name="MacKay"/> कवर 2006, अध्याय 5<ref name="Cover"/>): {{mvar|N}} आई.आई.डी. एन्ट्रापी ''H(X)'' वाले प्रत्येक यादृच्छिक चर को सूचना हानि के नगण्य जोखिम के साथ ''{{math|''N&thinsp;H''(''X'')}}''  बिट्स से अधिक में संपीड़ित किया जा सकता हैजैसे {{math|''N'' → ∞}}; किन्तु इसके विपरीत, सके विपरीत, यदि उन्हें {{math|''N&thinsp;H''(''X'')}} बिट्स यह लगभग निश्चित है कि जानकारी हों जाती है।
+सूचना सिद्धांत में, सोर्स  कोडिंग थेरोम (शैनन 1948)<ref name="Shannon"/> अनौपचारिक रूप से बताता है कि (मैकके 2003, पृष्ठ 81,<ref name="MacKay"/> कवर 2006, अध्याय 5<ref name="Cover"/>): {{mvar|N}} आई.आई.डी. एन्ट्रापी ''H(X)'' वाले प्रत्येक यादृच्छिक चर को सूचना हानि के नगण्य जोखिम के साथ ''{{math|''N&thinsp;H''(''X'')}}''  बिट्स से अधिक में संपीड़ित किया जा सकता हैजैसे {{math|''N'' → ∞}}; किन्तु इसके विपरीत, सके विपरीत, यदि उन्हें {{math|''N&thinsp;H''(''X'')}} बिट्स यह लगभग निश्चित है कि जानकारी हों जाती है।
-<math>NH(X)</math> कोडित अनुक्रम संपीड़ित संदेश को द्विअर्थी विधि से दर्शाता है, इस धारणा के तहत कि डिकोडर स्रोत को जानता है। व्यावहारिक दृष्टिकोण से, यह परिकल्पना सदैव सत्य नहीं होती है। परिणामस्वरूप,  जब एन्ट्रापी एन्कोडिंग लागू होती है तो संचरित संदेश होता है।  <math>NH(X)+(inf. source)</math>. सामान्यतः पर, स्रोत की विशेषता बताने वाली जानकारी प्रेषित संदेश की प्रारम्भिक में डाली जाती है।
+<math>NH(X)</math> कोडित अनुक्रम संपीड़ित संदेश को द्विअर्थी विधि से दर्शाता है, इस धारणा के तहत कि डिकोडर सोर्स  को जानता है। व्यावहारिक दृष्टिकोण से, यह परिकल्पना सदैव सत्य नहीं होती है। परिणामस्वरूप,  जब एन्ट्रापी एन्कोडिंग लागू होती है तो संचरित संदेश होता है।  <math>NH(X)+(inf. source)</math>. सामान्यतः पर, सोर्स  की विशेषता बताने वाली जानकारी प्रेषित संदेश की प्रारम्भिक में डाली जाती है।
-=== प्रतीक कोड के लिए स्रोत कोडिंग प्रमेय ===
+=== प्रतीक कोड के लिए सोर्स  कोडिंग थेरोम ===
 मान लीजिए {{math|Σ<sub>1</sub>, Σ<sub>2</sub>}} दो परिमित अक्षरों को दर्शाते हैं और मान लेते हैं {{math|Σ{{su|b=1|p=∗}}}} और {{math|Σ{{su|b=2|p=∗}}}}उन अक्षरों से (क्रमशः) सभी परिमित शब्दों के समुच्चय को निरूपित करें।
@@ Line 30: / Line 30: @@
 जहाँ <math>\mathbb{E}</math> अपेक्षित मान संक्रियक को दर्शाता है।
-== प्रमाण: स्रोत कोडिंग प्रमेय ==
+== प्रमाण: सोर्स  कोडिंग थेरोम ==
-मान लीजिए {{mvar|X}} एक आई.आई.डी. स्रोत, इसकी [[समय श्रृंखला]] {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} आई.आई.डी. होती है असतत-मूल्य वाले मामले में एन्ट्रापी {{math|''H''(''X'')}} और निरंतर-मूल्य वाले अंतर एन्ट्रापी के साथ स्रोत कोडिंग प्रमेय में कहा गया है कि किसी भी  {{math|''ε'' > 0}}, अर्थात किसी भी सूचना सिद्धांत दर के लिए {{math|''H''(''X'') + ''ε''}} के लिए जो स्रोत की एन्ट्रापी से बड़ी होती है, पर्याप्त बड़ा {{mvar|n}} और एक एनकोडर होता है जो  {{mvar|n}} आई.आई.डी. होता है। स्रोत की पुनरावृत्ति, {{math|''X''<sup>1:''n''</sup>}}, और इसे मैप करता है {{math|''n''(''H''(''X'') + ''ε'')}} बाइनरी बिट्स जैसे कि स्रोत प्रतीक {{math|''X''<sup>1:''n''</sup>}} कम से कम {{math|1 − ''ε''}} की संभावना के साथ बाइनरी बिट्स से पुनर्प्राप्त करने योग्य होते हैं ।
+मान लीजिए {{mvar|X}} एक आई.आई.डी. सोर्स , इसकी [[समय श्रृंखला]] {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} आई.आई.डी. होती है असतत-मूल्य वाले मामले में एन्ट्रापी {{math|''H''(''X'')}} और निरंतर-मूल्य वाले अंतर एन्ट्रापी के साथ सोर्स  कोडिंग थेरोम में कहा गया है कि किसी भी  {{math|''ε'' > 0}}, अर्थात किसी भी सूचना सिद्धांत दर के लिए {{math|''H''(''X'') + ''ε''}} के लिए जो सोर्स  की एन्ट्रापी से बड़ी होती है, पर्याप्त बड़ा {{mvar|n}} और एक एनकोडर होता है जो  {{mvar|n}} आई.आई.डी. होता है। सोर्स  की पुनरावृत्ति, {{math|''X''<sup>1:''n''</sup>}}, और इसे मैप करता है {{math|''n''(''H''(''X'') + ''ε'')}} बाइनरी बिट्स जैसे कि सोर्स  प्रतीक {{math|''X''<sup>1:''n''</sup>}} कम से कम {{math|1 − ''ε''}} की संभावना के साथ बाइनरी बिट्स से पुनर्प्राप्त करने योग्य होते हैं ।
 साध्यता का प्रमाण. कुछ {{math|''ε'' > 0}}, और मान लेते है
@@ Line 39: / Line 39: @@
 :<math>A_n^\varepsilon =\left\{(x_1, \cdots, x_n) \ : \ \left|-\frac{1}{n} \log p(x_1, \cdots, x_n) - H_n(X)\right| < \varepsilon \right\}.</math>
-असतत-समय i.i.d. के लिए एसिम्प्टोटिक समविभाजन संपत्ति#AEP स्रोत (एईपी) से पता चलता है कि यह काफी बड़े पैमाने पर है {{mvar|n}}, संभावना है कि स्रोत द्वारा उत्पन्न अनुक्रम विशिष्ट सेट में निहित है, {{math|''A''{{su|b=''n''|p=''ε''}}}}, जैसा कि परिभाषित किया गया है एक दृष्टिकोण। विशेष रूप से, पर्याप्त रूप से बड़े के लिए {{mvar|n}}, <math>P((X_1,X_2,\cdots,X_n) \in A_n^\varepsilon)</math> मनमाने ढंग से 1 के समीप और विशेष रूप से, इससे अधिक बनाया जा सकता है <math>1-\varepsilon</math> (देखना है की असतत समय i.i.d. के लिए स्पर्शोन्मुख समविभाजन संपत्ति AEP प्रमाण के लिए स्रोत होते है )
+असतत-समय i.i.d. के लिए एसिम्प्टोटिक समविभाजन संपत्ति#AEP सोर्स  (एईपी) से पता चलता है कि यह काफी बड़े पैमाने पर है {{mvar|n}}, संभावना है कि सोर्स  द्वारा उत्पन्न अनुक्रम विशिष्ट सेट में निहित है, {{math|''A''{{su|b=''n''|p=''ε''}}}}, जैसा कि परिभाषित किया गया है एक दृष्टिकोण। विशेष रूप से, पर्याप्त रूप से बड़े के लिए {{mvar|n}}, <math>P((X_1,X_2,\cdots,X_n) \in A_n^\varepsilon)</math> मनमाने ढंग से 1 के समीप और विशेष रूप से, इससे अधिक बनाया जा सकता है <math>1-\varepsilon</math> (देखना है की असतत समय i.i.d. के लिए स्पर्शोन्मुख समविभाजन संपत्ति AEP प्रमाण के लिए सोर्स  होते है )
 विशिष्ट सेटों की परिभाषा का तात्पर्य है कि वे अनुक्रम जो विशिष्ट सेट में स्थित हैं, संतुष्ट करते हैं:
@@ Line 56: / Line 56: @@
 वार्तालाप का प्रमाण. इसका विपरीत यह दर्शाकर सिद्ध किया जाता है कि आकार का कोई भी सेट इससे छोटा है {{math|''A''{{su|b=''n''|p=''ε''}}}} (प्रतिपादक के अर्थ में) दूर से बंधे संभाव्यता के एक सेट को कवर करेगा {{math|1}}.
-== प्रमाण: प्रतीक कोड के लिए स्रोत कोडिंग प्रमेय ==
+== प्रमाण: प्रतीक कोड के लिए सोर्स  कोडिंग थेरोम ==
 के लिए {{math|1 ≤ ''i'' ≤ ''n''}} होने देना {{math|''s<sub>i</sub>''}} प्रत्येक संभव शब्द की लंबाई को निरूपित करें {{math|''x<sub>i</sub>''}}. परिभाषित करना <math>q_i = a^{-s_i}/C</math>, कहाँ {{mvar|C}} को इसलिए चुना गया है {{math|''q''<sub>1</sub> + ... + ''q<sub>n</sub>'' {{=}} 1}}. तब
@@ Line 93: / Line 93: @@
 \end{align}</math>
-==गैर-स्थिर स्वतंत्र स्रोतों तक विस्तार ==
+==गैर-स्थिर स्वतंत्र सोर्स ों तक विस्तार ==
-=== असतत समय गैर-स्थिर स्वतंत्र स्रोतों के लिए निश्चित दर दोषरहित स्रोत कोडिंग ===
+=== असतत समय गैर-स्थिर स्वतंत्र सोर्स ों के लिए निश्चित दर दोषरहित सोर्स  कोडिंग ===
 विशिष्ट समुच्चय को {{math|''A''{{su|b=''n''|p=''ε''}}}} के रूप मे परिभाषित करें जैसा:
 :<math>A_n^\varepsilon = \left \{x_1^n \ : \ \left|-\frac{1}{n} \log p \left (X_1, \cdots, X_n \right ) - \overline{H_n}(X)\right| < \varepsilon \right \}.</math>
-फिर, दिया गया {{math|''δ'' > 0}} के लिए, पर्याप्त बड़े  {{mvar|n}} के लिए, {{math|Pr(''A''{{su|b=''n''|p=''ε''}}) > 1 − ''δ''}} अब हम केवल विशिष्ट सेट में अनुक्रमों को एन्कोड करते हैं, और स्रोत कोडिंग में सामान्य विधियों  से पता चलता है कि इस सेट की कार्डिनैलिटी इससे छोटी होती है कि इस प्रकार, औसतन,  <math>2^{n(\overline{H_n}(X)+\varepsilon)}</math>से अधिक संभावना के साथ एन्कोडिंग के लिए पर्याप्त हैं, जहां {{mvar|n}} को बड़ा बनाकर ε और δ को मनमाने ढंग से छोटा किया जा सकता है।
+फिर, दिया गया {{math|''δ'' > 0}} के लिए, पर्याप्त बड़े  {{mvar|n}} के लिए, {{math|Pr(''A''{{su|b=''n''|p=''ε''}}) > 1 − ''δ''}} अब हम केवल विशिष्ट सेट में अनुक्रमों को एन्कोड करते हैं, और सोर्स  कोडिंग में सामान्य विधियों  से पता चलता है कि इस सेट की कार्डिनैलिटी इससे छोटी होती है कि इस प्रकार, औसतन,  <math>2^{n(\overline{H_n}(X)+\varepsilon)}</math>से अधिक संभावना के साथ एन्कोडिंग के लिए पर्याप्त हैं, जहां {{mvar|n}} को बड़ा बनाकर ε और δ को मनमाने ढंग से छोटा किया जा सकता है।
 ==यह भी देखें==
 * [[चैनल कोडिंग]]
-* [[शोर-चैनल कोडिंग प्रमेय]]
+* [[शोर-चैनल कोडिंग प्रमेय|शोर-चैनल कोडिंग थेरोम]]
 *त्रुटि प्रतिपादक
 * एसिम्प्टोटिक समविभाजन संपत्ति (एईपी)

Anonymous

Search

शैनन का सोर्स कोडिंग थेरोम: Difference between revisions

Namespaces

More

Page actions

Revision as of 13:57, 17 July 2023

Contents

कथन

सोर्स कोडिंग थेरोम

प्रतीक कोड के लिए सोर्स कोडिंग थेरोम

प्रमाण: सोर्स कोडिंग थेरोम

प्रमाण: प्रतीक कोड के लिए सोर्स कोडिंग थेरोम

गैर-स्थिर स्वतंत्र सोर्स ों तक विस्तार

असतत समय गैर-स्थिर स्वतंत्र सोर्स ों के लिए निश्चित दर दोषरहित सोर्स कोडिंग

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

शैनन का सोर्स कोडिंग थेरोम: Difference between revisions

Revision as of 13:57, 17 July 2023

कथन

सोर्स कोडिंग थेरोम

प्रतीक कोड के लिए सोर्स कोडिंग थेरोम

प्रमाण: सोर्स कोडिंग थेरोम

प्रमाण: प्रतीक कोड के लिए सोर्स कोडिंग थेरोम

गैर-स्थिर स्वतंत्र सोर्स ों तक विस्तार

असतत समय गैर-स्थिर स्वतंत्र सोर्स ों के लिए निश्चित दर दोषरहित सोर्स कोडिंग

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories