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

Latest revision as of 17:15, 29 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 2: / Line 2: @@
 {{Information theory}}
-{{about|the theory of source coding in data compression|the term in computer programming|Source code}}
+{{about|डेटा संपीड़न में स्रोत कोडिंग का सिद्धांत|कंप्यूटर प्रोग्रामिंग में शब्द|स्रोत कोड}}
-[[सूचना सिद्धांत]] में, शैनन का स्रोत कोडिंग प्रमेय (या नीरव कोडिंग प्रमेय) संभावित डेटा संपीड़न की सीमा और शैनन एन्ट्रॉपी के परिचालन अर्थ को स्थापित करता है।
+[[सूचना सिद्धांत]] में, '''शैनन का सोर्स  कोडिंग थेरोम''' (या नीरव कोडिंग थेरोम) संभावित डेटा संपीड़न की सीमा और शैनन एन्ट्रॉपी के परिचालन अर्थ को स्थापित करता है।
-[[क्लाउड शैनन]] के नाम पर, स्रोत कोडिंग प्रमेय से पता चलता है कि (सीमा में, स्वतंत्र समान रूप से वितरित यादृच्छिक चर की एक धारा की लंबाई के रूप में | स्वतंत्र और समान रूप से वितरित यादृच्छिक चर (i.i.d.) डेटा अनंत तक जाता है) इसे संपीड़ित करना असंभव है डेटा ऐसा है कि कोड दर (प्रति प्रतीक बिट्स की औसत संख्या) स्रोत की शैनन एन्ट्रॉपी से कम है, यह लगभग निश्चित नहीं है कि जानकारी खो जाएगी। हालाँकि, नुकसान की नगण्य संभावना के साथ, कोड दर को मनमाने ढंग से [[शैनन एन्ट्रापी]] के करीब प्राप्त करना संभव है।
+[[क्लाउड शैनन]] के नाम पर, '''सोर्स  कोडिंग थेरोम''' से पता चलता है (सीमा में, स्वतंत्र और समान रूप से वितरित  यादृच्छिक चर (i.i.d.) डेटा की धारा की लंबाई अनंत तक जाती है) डेटा को इस तरह संपीड़ित करना असंभव है इसे संपीड़ित करना असंभव है कि कोड दर (प्रति प्रतीक बिट्स की औसत संख्या) सोर्स  की शैनन एन्ट्रॉपी से कम है, यह लगभग निश्चित नहीं है कि जानकारी लुप्त हों गयी है। चूँकि, नुकसान की नगण्य संभावना के साथ, कोड दर को अव्यवस्थिततः ढंग से [[शैनन एन्ट्रापी]] के समीप प्राप्त करना संभव होता है।
-प्रतीक कोड के लिए स्रोत कोडिंग प्रमेय इनपुट शब्द (जिसे एक यादृच्छिक चर के रूप में देखा जाता है) और आकार के [[एन्ट्रॉपी (सूचना सिद्धांत)]] के एक फ़ंक्शन के रूप में कोडवर्ड की न्यूनतम संभावित अपेक्षित लंबाई पर एक ऊपरी और निचली सीमा रखता है। लक्ष्य वर्णमाला.
+प्रतीक कोड के लिए सोर्स  '''कोडिंग थेरोम''' इनपुट शब्द की [[एन्ट्रॉपी (सूचना सिद्धांत)|एन्ट्रॉपी]] (जिसे एक यादृच्छिक चर के रूप में देखा जाता है) और लक्ष्य वर्णमाला के आकार का एक फलन के रूप में कोडवर्ड की न्यूनतम संभावित अपेक्षित लंबाई पर एक ऊपरी और निचली सीमा रखता है।
 == कथन ==
-स्रोत कोडिंग एक सूचना सूचना सिद्धांत # स्रोत सिद्धांत से प्रतीकों (एक अनुक्रम) से वर्णमाला प्रतीकों (आमतौर पर बिट्स) के अनुक्रम की मैपिंग है, ताकि स्रोत प्रतीकों को बाइनरी बिट्स (दोषरहित स्रोत कोडिंग) से बिल्कुल पुनर्प्राप्त किया जा सके या पुनर्प्राप्त किया जा सके कुछ विकृति के भीतर (हानिपूर्ण स्रोत कोडिंग)। डेटा संपीड़न के पीछे यही अवधारणा है।
+सोर्स  कोडिंग एक सूचना सोर्स  से प्रतीकों (एक अनुक्रम) को वर्णमाला प्रतीकों को (सामान्यतः  बिट्स) अनुक्रम की मैपिंग करता है, जिससे की सोर्स  प्रतीकों को बाइनरी बिट्स (दोषरहित सोर्स  कोडिंग) से बिल्कुल पुनर्प्राप्त किया जा सके या कुछ विरूपण के भीतर पुनर्प्राप्त किया जा सके (हानिपूर्ण सोर्स  कोडिंग)। डेटा संपीड़न के पीछे यही अवधारणा होती है।
-=== स्रोत कोडिंग प्रमेय ===
+=== सोर्स  कोडिंग थेरोम ===
-सूचना सिद्धांत में, स्रोत कोडिंग प्रमेय (शैनन 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'')}} बिट्स यह लगभग निश्चित है कि जानकारी खो जाएगी।</blockquote> <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 55: / 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 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 92: / Line 93: @@
 \end{align}</math>
+==गैर-स्थिर स्वतंत्र सोर्स ों तक विस्तार ==
-==गैर-स्थिर स्वतंत्र स्रोतों तक विस्तार ==
+=== असतत समय गैर-स्थिर स्वतंत्र सोर्स ों के लिए निश्चित दर दोषरहित सोर्स  कोडिंग ===
+विशिष्ट समुच्चय को {{math|''A''{{su|b=''n''|p=''ε''}}}} के रूप मे परिभाषित करें जैसा:
-=== असतत समय गैर-स्थिर स्वतंत्र स्रोतों के लिए निश्चित दर दोषरहित स्रोत कोडिंग ===
-विशिष्ट समुच्चय को परिभाषित करें {{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>. इस प्रकार, औसतन, {{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}} को बड़ा बनाकर ε और δ को मनमाने ढंग से छोटा किया जा सकता है।
 ==यह भी देखें==
 * [[चैनल कोडिंग]]
-* [[शोर-चैनल कोडिंग प्रमेय]]
+* [[शोर-चैनल कोडिंग प्रमेय|शोर-चैनल कोडिंग थेरोम]]
 *त्रुटि प्रतिपादक
 * एसिम्प्टोटिक समविभाजन संपत्ति (एईपी)
@@ Line 112: / Line 112: @@
 <ref name="MacKay">David J. C. MacKay. ''[http://www.inference.phy.cam.ac.uk/mackay/itila/book.html Information Theory, Inference, and Learning Algorithms]'' Cambridge: Cambridge University Press, 2003. {{ISBN|0-521-64298-1}}</ref>
 <ref name="Cover">{{cite book | last = Cover | first = Thomas M. | title = Elements of Information Theory | chapter = Chapter 5: Data Compression | year = 2006  | publisher = John Wiley & Sons | isbn = 0-471-24195-4|url=https://books.google.com/books?id=VWq5GG6ycxMC|pages=103–142}}</ref>}}
-[[Category: सूचना सिद्धांत]] [[Category: कोडिंग सिद्धांत]] [[Category: आधार - सामग्री संकोचन]] [[Category: प्रस्तुति परत प्रोटोकॉल]] [[Category: सैद्धांतिक कंप्यूटर विज्ञान में गणितीय प्रमेय]] [[Category: प्रमाण युक्त लेख]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
 [[Category:Created On 06/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:आधार - सामग्री संकोचन]]
+[[Category:कोडिंग सिद्धांत]]
+[[Category:प्रमाण युक्त लेख]]
+[[Category:प्रस्तुति परत प्रोटोकॉल]]
+[[Category:सूचना सिद्धांत]]
+[[Category:सैद्धांतिक कंप्यूटर विज्ञान में गणितीय प्रमेय]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 17:15, 29 July 2023

Contents

कथन

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

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 17:15, 29 July 2023

कथन

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

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories