WikiSort.ru - Не сортированное

В теории информации теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.

Теорема показывает, что (когда в потоке независимо и одинаково распределённых (НОР) случайных переменных количество данных стремится к бесконечности) невозможно сжать данные настолько, что оценка кода (среднее число бит на символ) меньше, чем энтропия Шеннона исходных данных, без потери точности информации. Тем не менее, можно получить код, близкий к энтропии Шеннона без значительных потерь.

Теорема об источнике шифрования для кодов символов приводит верхнюю и нижнюю границу к минимально возможной длине зашифрованных слов как функция энтропии от входного слова (которое представлено как случайная переменная) и от размера требуемой азбуки.

Утверждение

Исходный код — это отображение (последовательность) из хранилища информации в последовательность алфавитных символов (обычно битов) таких что исходный символ может быть однозначно получен из двоичных разрядов (безпотерьный источник кодирования) или получен с некоторым различием (источник кодирования с потерями). Это идея сжатия данных.

Доказательство теоремы об источнике шифрования

Задано ${\displaystyle X}$ являющееся НОР, его временной ряд X₁, …, X_n также НОР с энтропией H(X) iв случае дискретных значений, и с дифференциальной энтропией в случае непрерывных значений. Теорема об источнике шифрования утверждает что для каждого ${\displaystyle \epsilon >0}$ для каждой оценки большей, чем энтропия ресурса, существует достаточно большое n и шифрователь, который принимает n НОР копий ресурса , ${\displaystyle X^{1:n}}$ , , и отображает его в ${\displaystyle n.(H(X)+\epsilon )}$ двоичных бит таким способом, что исходный символ ${\displaystyle X^{1:n}}$ может быть восстановлен из двоичных бит, X вероятностью не менее чем ${\displaystyle 1-\epsilon }$ .

Доказательство

Возьмем некоторое ${\displaystyle \epsilon >0}$ . формула для, ${\displaystyle A_{n}^{\epsilon }}$ , выглядит следующим образом:

${\displaystyle A_{n}^{\epsilon }=\;\left\{x_{1}^{n}:\left|-{\frac {1}{n}}\log p(X_{1},X_{2},...,X_{n})-H_{n}(X)\right|<\epsilon \right\}}$

AEP показывает что для достаточно больших n, последовательность сгенерированная из источника недостоверна в типичном случае — ${\displaystyle A_{n}^{\epsilon }}$ , сходящаяся. В случае для достаточно больших: n, ${\displaystyle P(A_{n}^{\epsilon })>1-\epsilon }$ (см AEP)

Определение типичных наборов подразумевает, что те последовательности, которые лежат в типичном наборе, удовлетворяют:

${\displaystyle 2^{-n(H(X)+\epsilon )}\leq p(x_{1},x_{2},...,x_{n})\leq 2^{-n(H(X)-\epsilon )}}$

Заметьте, что:

• Вероятность того, что последовательность была получена из ${\displaystyle X}$

${\displaystyle {A_{\epsilon }}^{(n)}}$ больше чем ${\displaystyle 1-\epsilon }$

• ${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )}}$ начиная с вероятности полной совокупности ${\displaystyle {A_{\epsilon }}^{(n)}}$ является наиболее большим.

• ${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\geq (1-\epsilon )2^{n(H(X)-\epsilon )}}$ . Fдля доказательства используйте верхнюю границу вероятности для каждого терма в типичном случае, и нижнюю границу для общего случая ${\displaystyle {A_{\epsilon }}^{(n)}}$ .

Начиная с ${\displaystyle \left|{A_{\epsilon }}^{(n)}\right|\leq 2^{n(H(X)+\epsilon )},n.(H(X)+\epsilon )\;}$ битов достаточно, чтобы отличить любую строку

Алгоритм шифрования: шифратор проверяет является ли ложной входящая последовательность, если да, то возвращает индекс входящей частоты в последовательности, если нет, то возвращает случайное ${\displaystyle n.(H(X)+\epsilon )}$ digit number. численное значение. В случае если входящая вероятность неверна в последовательности (с частотой примерно ${\displaystyle 1-\epsilon }$ ), то шифратор не выдает ошибку. То есть вероятность ошибки составляет выше чем ${\displaystyle \epsilon }$

Доказательство обратимости Доказательство обратимости базируется на том, что требуется показать что для любой последовательности размером меньше чем ${\displaystyle A_{n}^{\epsilon }}$ (в смысле экспоненты) будет покрывать частоту последовательности, ограниченную 1.

Доказательство теоремы об источнике шифрования для кодов символов

Пусть ${\displaystyle s_{i}}$ длина слова для каждого возможного ${\displaystyle x_{i}}$ (${\displaystyle i=1,\ldots ,n}$ ). Определим ${\displaystyle q_{i}=a^{-s_{i}}/C}$ , где С выбирается таким образом, что: ${\displaystyle \sum q_{i}=1}$ .

Тогда

${\displaystyle {\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\leqslant \\&\leqslant -\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\leqslant \\&\leqslant -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\leqslant \\&\leqslant \mathbb {E} S\log _{2}a,\\\end{aligned}}}$

где вторая строка является неравенством Гиббса, а пятая строка является неравенством Крафта ${\displaystyle C=\sum _{i=1}^{n}a^{-s_{i}}\leqslant 1}$ , ${\displaystyle \log C\leq 0}$ .

для второго неравенства мы можем установить

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

и так

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

а затем

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

и

${\displaystyle \sum a^{-s_{i}}\leqslant \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}}}$

Примечания

• Cover, Thomas M. Chapter 5: Data Compression // Elements of Information Theory. — John Wiley & Sons, 2006. — ISBN 0-471-24195-4.
• C. E. Shannon, «A Mathematical Theory of Communication», Bell System Technical Journal, vol. 27, pp. 379—423, 623—656, July, October, 1948