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

Revision as of 12:39, 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 11: / Line 11: @@
 == कथन ==
-स्रोत कोडिंग एक सूचना सूचना सिद्धांत # स्रोत सिद्धांत से प्रतीकों (एक अनुक्रम) से वर्णमाला प्रतीकों (आमतौर पर बिट्स) के अनुक्रम की मैपिंग है, ताकि स्रोत प्रतीकों को बाइनरी बिट्स (दोषरहित स्रोत कोडिंग) से बिल्कुल पुनर्प्राप्त किया जा सके या पुनर्प्राप्त किया जा सके कुछ विकृति के भीतर (हानिपूर्ण स्रोत कोडिंग)। डेटा संपीड़न के पीछे यही अवधारणा है।
+स्रोत कोडिंग एक सूचना स्रोत से प्रतीकों (एक अनुक्रम) को वर्णमाला प्रतीकों को (सामान्यतः  बिट्स) अनुक्रम की मैपिंग करता है, जिससे की स्रोत प्रतीकों को बाइनरी बिट्स (दोषरहित स्रोत कोडिंग) से बिल्कुल पुनर्प्राप्त किया जा सके या कुछ विरूपण के भीतर पुनर्प्राप्त किया जा सके (हानिपूर्ण स्रोत कोडिंग)। डेटा संपीड़न के पीछे यही अवधारणा होती है।
 === स्रोत कोडिंग प्रमेय ===
-सूचना सिद्धांत में, स्रोत कोडिंग प्रमेय (शैनन 1948)<ref name="Shannon"/>अनौपचारिक रूप से कहा गया है कि (मैकके 2003, पृष्ठ 81,<ref name="MacKay"/>कवर 2006, अध्याय 5<ref name="Cover"/>):
+सूचना सिद्धांत में, स्रोत कोडिंग प्रमेय (शैनन 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'')}} बिट्स यह लगभग निश्चित है कि जानकारी हों जाती है।
-<ब्लॉककोट>{{mvar|N}} स्वतंत्र और समान रूप से वितरित यादृच्छिक चर|i.i.d. एन्ट्रॉपी (सूचना सिद्धांत) के साथ प्रत्येक यादृच्छिक चर {{math|''H''(''X'')}} से अधिक में संपीड़ित किया जा सकता है {{math|''N&thinsp;H''(''X'')}} सूचना हानि के नगण्य जोखिम वाले [[ अंश ]]्स, जैसे {{math|''N'' → ∞}}; लेकिन इसके विपरीत, यदि उन्हें कम से कम में संपीड़ित किया जाता है {{math|''N&thinsp;H''(''X'')}} बिट्स यह लगभग निश्चित है कि जानकारी खो जाएगी। <math>NH(X)</math> h> कोडित अनुक्रम संपीड़ित संदेश को द्विअर्थी तरीके से दर्शाता है, इस धारणा के तहत कि डिकोडर स्रोत को जानता है। व्यावहारिक दृष्टिकोण से, यह परिकल्पना हमेशा सत्य नहीं होती है। नतीजतन, जब एन्ट्रापी एन्कोडिंग लागू होती है तो संचरित संदेश होता है <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=∗}}}} उन अक्षरों से (क्रमशः) [[क्लेन स्टार]] को निरूपित करें।
+मान लीजिए {{math|Σ<sub>1</sub>, Σ<sub>2</sub>}} दो परिमित अक्षरों को दर्शाते हैं और मान लेते हैं {{math|Σ{{su|b=1|p=∗}}}} और {{math|Σ{{su|b=2|p=∗}}}}उन अक्षरों से (क्रमशः) सभी परिमित शब्दों के समुच्चय को निरूपित करें।
-लगता है कि {{mvar|X}} एक यादृच्छिक चर है जो मान लेता है {{math|Σ<sub>1</sub>}} और जाने {{math|&thinsp;''f''&thinsp;}} एक वेरिएबल-लेंथ कोड बनें#विशिष्ट रूप से डिकोड करने योग्य कोड कोड से {{math|Σ{{su|b=1|p=∗}}}} को {{math|Σ{{su|b=2|p=∗}}}} कहाँ {{math|{{!}}Σ<sub>2</sub>{{!}} {{=}} ''a''}}. होने देना {{mvar|S}} कोडवर्ड की लंबाई द्वारा दिए गए यादृच्छिक चर को निरूपित करें {{math|&thinsp;''f''&thinsp;(''X'')}}.
+मान लीजिए कि {{mvar|X}}  एक यादृच्छिक चर होता है जो मान लेते हैं {{math|Σ<sub>1</sub>}} और {{math|&thinsp;''f''&thinsp;}} एक चर लंबाई कोड को विशिष्ट रूप से डिकोड करने योग्य कोड से {{math|Σ{{su|b=1|p=∗}}}} को {{math|Σ{{su|b=2|p=∗}}}}
-अगर {{math|&thinsp;''f''&thinsp;}} इस अर्थ में इष्टतम है कि इसमें न्यूनतम अपेक्षित शब्द लंबाई है {{mvar|X}}, फिर (शैनन 1948):
+जहाँ {{math|{{!}}Σ<sub>2</sub>{{!}} {{=}} ''a''}} होता है। मान लीजिए ''S'' कोडवर्ड  {{math|&thinsp;''f''&thinsp;(''X'')}} की लंबाई द्वारा दिए गए यादृच्छिक चर को दर्शाता है।
+यदि {{math|&thinsp;''f''&thinsp;}} इस अर्थ में इष्टतम है कि इसमें {{mvar|X}} के लिए न्यूनतम अपेक्षित शब्द लंबाई होती है, तो (शैनन 1948):
 :<math> \frac{H(X)}{\log_2 a} \leq \mathbb{E}[S] < \frac{H(X)}{\log_2 a} +1 </math>
-कहाँ <math>\mathbb{E}</math> अपेक्षित मान ऑपरेटर को दर्शाता है।
+जहाँ <math>\mathbb{E}</math> अपेक्षित मान संक्रियक को दर्शाता है।
 == प्रमाण: स्रोत कोडिंग प्रमेय ==
-दिया गया {{mvar|X}} एक स्वतंत्र समान रूप से वितरित यादृच्छिक चर है|i.i.d. स्रोत, इसकी [[समय श्रृंखला]] {{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}}, और जाने
+साध्यता का प्रमाण. कुछ {{math|''ε'' > 0}}, और मान लेते है
 :<math>p(x_1, \ldots, x_n) = \Pr \left[X_1 = x_1, \cdots, X_n = x_n \right].</math>
@@ Line 37: / 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 स्रोत (एईपी) से पता चलता है कि यह काफी बड़े पैमाने पर है {{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 प्रमाण के लिए स्रोत)
 विशिष्ट सेटों की परिभाषा का तात्पर्य है कि वे अनुक्रम जो विशिष्ट सेट में स्थित हैं, संतुष्ट करते हैं:
@@ Line 45: / Line 46: @@
 ध्यान दें कि:
-*क्रम की संभावना <math>(X_1,X_2,\cdots X_n)</math> से खींचा जा रहा है {{math|''A''{{su|b=''n''|p=''ε''}}}} से बड़ा है {{math|1 − ''ε''}}.
+*क्रम की संभावना <math>(X_1,X_2,\cdots X_n)</math> से खींचा जा रहा है {{math|''A''{{su|b=''n''|p=''ε''}}}} से बड़ा होता है {{math|1 − ''ε''}}.
 *<math>\left| A_n^\varepsilon \right| \leq 2^{n(H(X)+\varepsilon)}</math>, जो बायीं ओर (निचली सीमा) से आता है <math> p(x_1,x_2,\cdots x_n)</math>.
 *<math>\left| A_n^\varepsilon \right| \geq (1-\varepsilon) 2^{n(H(X)-\varepsilon)}</math>, जो ऊपरी सीमा से अनुसरण करता है <math> p(x_1,x_2,\cdots x_n)</math> और पूरे सेट की कुल संभावना पर निचली सीमा {{math|''A''{{su|b=''n''|p=''ε''}}}}.
@@ Line 74: / Line 75: @@
 :<math>s_i = \lceil - \log_a p_i \rceil </math>
-ताकि
+जिससे की
 :<math> - \log_a p_i \leq s_i < -\log_a p_i + 1 </math>
@@ Line 91: / Line 92: @@
 & = \frac{H(X)}{\log_2 a} +1 \\
 \end{align}</math>
 ==गैर-स्थिर स्वतंत्र स्रोतों तक विस्तार ==
@@ Line 99: / Line 99: @@
 :<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>. इस प्रकार, औसतन, {{math|{{overline|''H<sub>n</sub>''}}(''X'') + ''ε''}} से अधिक संभावना के साथ एन्कोडिंग के लिए बिट्स पर्याप्त हैं {{math|1 − ''δ''}}, कहाँ {{mvar|ε}} और {{mvar|δ}} बनाकर मनमाने ढंग से छोटा किया जा सकता है {{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 12:39, 17 July 2023

Contents

कथन

स्रोत कोडिंग प्रमेय

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 12:39, 17 July 2023

कथन

स्रोत कोडिंग प्रमेय

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories