نظرية شانون لترميز المصدر

في نظرية المعلومات ، تحدد نظرية ترميز المصدر لشانون (أو نظرية الترميز عديم الضوضاء ) الحدود الإحصائية لضغط البيانات الممكن للبيانات التي يكون مصدرها متغيرًا عشوائيًا مستقلًا وموزعًا بشكل متطابق ، والمعنى العملي لإنتروبيا شانون .

تُبيّن نظرية ترميز المصدر ، التي سُميت نسبةً إلى كلود شانون ، أنه في حالة اقتراب طول سلسلة من بيانات المتغيرات العشوائية المستقلة والمتطابقة التوزيع (iid) من اللانهاية، يستحيل ضغط هذه البيانات بحيث يكون معدل الترميز (متوسط ​​عدد البتات لكل رمز) أقل من إنتروبيا شانون للمصدر، دون أن يكون من شبه المؤكد فقدان المعلومات. مع ذلك، من الممكن الحصول على معدل ترميز قريب جدًا من إنتروبيا شانون، باحتمالية فقدان ضئيلة للغاية.

تضع نظرية ترميز المصدر لرموز الرموز حدًا أعلى وحدًا أدنى على الحد الأدنى المتوقع لطول الكلمات المشفرة كدالة لإنتروبيا كلمة الإدخال (التي تعتبر متغيرًا عشوائيًا ) وحجم الأبجدية المستهدفة.

تجدر الإشارة إلى أنه بالنسبة للبيانات التي تُظهر تبعيات أكثر (والتي لا يكون مصدرها متغيرًا عشوائيًا مستقلًا ومتطابق التوزيع)، فإن تعقيد كولموغوروف ، الذي يُحدد الحد الأدنى لطول وصف الكائن، يُعدّ أكثر ملاءمةً لوصف حدود ضغط البيانات. يأخذ إنتروبيا شانون في الاعتبار انتظام التكرار فقط، بينما يأخذ تعقيد كولموغوروف في الاعتبار جميع الانتظامات الخوارزمية، لذا يكون الأخير أصغر عمومًا. من ناحية أخرى، إذا تم توليد كائن ما بواسطة عملية عشوائية بحيث لا يمتلك سوى انتظام التكرار، فإن الإنتروبيا تقترب من التعقيد باحتمالية عالية (شين وآخرون، 2017). ^{[ 1 ]}

ترميز المصدر هو عملية تحويل (سلسلة من) الرموز من مصدر معلومات إلى سلسلة من رموز الأبجدية (عادةً بتات) بحيث يمكن استعادة رموز المصدر بدقة من رموز الأبجدية (ترميز المصدر بدون فقدان) أو استعادتها مع بعض التشوه (ترميز المصدر مع فقدان). هذه إحدى طرق ضغط البيانات .

بفرض أن X مصدر مستقل ومتطابق التوزيع ، فإن سلسلته الزمنية X₁ , ..., Xₙ مستقلة ومتطابقة التوزيع أيضًا، مع _{إنتروبيا H} ( X ) في حالة القيم المنفصلة، ​​وإنتروبيا تفاضلية في حالة القيم المتصلة. تنص نظرية ترميز المصدر على أنه لأي قيمة ε > 0 ، أي لأي معدل H ( X ) + ε أكبر من إنتروبيا المصدر، يوجد عدد كبير بما يكفي n ومشفّر يأخذ n تكرارًا مستقلًا ومتطابق التوزيع للمصدر X₁ ^{: ₙ} ، ويحوله إلى n ( H ( X ) + ε ) بت ثنائي، بحيث يمكن استعادة رموز المصدر X₁ ^{: ₙ} من البتات الثنائية باحتمالية لا تقل عن 1 − ε .

إثبات إمكانية التحقيق. لنثبت قيمة ε > 0 ، ولنفرض

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

تُعرَّف المجموعة النموذجية ، A ^ε _{n ، على النحو التالي:}

${\displaystyle 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\}.}

تُظهر خاصية التوزيع المتساوي التقاربي (AEP) أنه بالنسبة لقيم n الكبيرة بما فيه الكفاية ، فإن احتمال وجود متتالية مُولَّدة من المصدر في المجموعة النموذجية A ^ε _n ، كما هو مُعرَّف، يقترب من الواحد. على وجه الخصوص، بالنسبة لقيم n الكبيرة بما فيه الكفاية ،${\displaystyle P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })}$يمكن جعلها قريبة بشكل تعسفي من 1، وتحديدًا أكبر من${\displaystyle 1-\varepsilon }$(انظر AEP للحصول على دليل).

يشير تعريف المجموعات النموذجية إلى أن المتتاليات التي تقع في المجموعة النموذجية تحقق ما يلي:

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

• احتمالية حدوث متتالية${\displaystyle (X_{1},X_{2},\cdots X_{n})}$يتم سحبها من A ^ε _n أكبر من 1 − ε .
• ${\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}}$، وهو ما يتبع من الجانب الأيسر (الحد الأدنى) لـ${\displaystyle p(x_{1},x_{2},\cdots x_{n})}$.
• ${\displaystyle \left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}}$، وهو ما يترتب على الحد الأعلى لـ${\displaystyle p(x_{1},x_{2},\cdots x_{n})}$ والحد الأدنى للاحتمالية الكلية للمجموعة A ^ε _n .

منذ${\displaystyle \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 ممكن .${\displaystyle q_{i}=a^{-s_{i}}/C}$حيث يتم اختيار C بحيث يكون q1 ₊ ... + qn ₌ 1. إذن

${\displaystyle {\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}}}$

حيث يتبع السطر الثاني من متباينة جيبس ​​ويتبع السطر الخامس من متباينة كرافت :

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

لذا فإن log C ≤ 0 .

بالنسبة للمتباينة الثانية، يمكننا أن نضع

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

لهذا السبب.

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

وهكذا

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

و

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

وبالتالي، وفقًا لمتباينة كرافت، يوجد رمز خالٍ من البادئات له أطوال الكلمات تلك. ومن ثم، فإن أصغر قيمة لـ S تحقق ما يلي :

${\displaystyle {\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}}}$

• ترميز القنوات
• أس الخطأ
• نظرية ترميز القناة المشوشة