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

This article is about डेटा संपीड़न में स्रोत कोडिंग का सिद्धांत. For कंप्यूटर प्रोग्रामिंग में शब्द, see स्रोत कोड.

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

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

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

कथन

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

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

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

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

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

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

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

जहाँ |Σ₂| = 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₁, ..., 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 ≤ i ≤ n होने देना s_i प्रत्येक संभव शब्द की लंबाई को निरूपित करें x_i. परिभाषित करना $q_{i}=a^{-s_{i}}/C$, कहाँ C को इसलिए चुना गया है q₁ + ... + 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 ≤ 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 को बड़ा बनाकर ε और δ को मनमाने ढंग से छोटा किया जा सकता है।

यह भी देखें

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