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

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

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

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

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

कथन

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

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

सूचना सिद्धांत में, स्रोत कोडिंग प्रमेय (शैनन 1948)अनौपचारिक रूप से कहा गया है कि (मैकके 2003, पृष्ठ 81,कवर 2006, अध्याय 5):

<ब्लॉककोट>N स्वतंत्र और समान रूप से वितरित यादृच्छिक चर|i.i.d. एन्ट्रॉपी (सूचना सिद्धांत) के साथ प्रत्येक यादृच्छिक चर H(X) से अधिक में संपीड़ित किया जा सकता है N H(X) सूचना हानि के नगण्य जोखिम वाले अंश ्स, जैसे N → ∞; लेकिन इसके विपरीत, यदि उन्हें कम से कम में संपीड़ित किया जाता है N H(X) बिट्स यह लगभग निश्चित है कि जानकारी खो जाएगी। $NH(X)$ h> कोडित अनुक्रम संपीड़ित संदेश को द्विअर्थी तरीके से दर्शाता है, इस धारणा के तहत कि डिकोडर स्रोत को जानता है। व्यावहारिक दृष्टिकोण से, यह परिकल्पना हमेशा सत्य नहीं होती है। नतीजतन, जब एन्ट्रापी एन्कोडिंग लागू होती है तो संचरित संदेश होता है $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 एक स्वतंत्र समान रूप से वितरित यादृच्छिक चर है|i.i.d. स्रोत, इसकी समय श्रृंखला 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 )}$. इस प्रकार, औसतन, H_n(X) + ε से अधिक संभावना के साथ एन्कोडिंग के लिए बिट्स पर्याप्त हैं 1 − δ, कहाँ ε और δ बनाकर मनमाने ढंग से छोटा किया जा सकता है n बड़ा.

यह भी देखें

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