Теорема Шеннона об источнике шифрования

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

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

Утверждение

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

Источник шифрования для кодов символов

В информатике Теорема об источнике шифрования (Шеннон 1948) утверждает что:

«N случайная переменная с энтропией H(X) может быть сжата в более чем NH(X) битов с незначительным риском потери данных если N стремится к бесконечности, но если сжатие происходит менее в чем NH(X)) бит, то данные скорее всего будут потеряны. (MacKay 2003).»

Теорема об источнике шифрования для кодов символов

Пусть $\Sigma_1$, $\Sigma_2$ значат два конечных алфавита, и пусть $\Sigma_1^*$ и $\Sigma_2^*$ означают набор всех конечных слов из этих алфавитов (упорядоченных).

Предположим что X — случайная переменная которая принимает значение из $\Sigma_1$ а f — поддающийся расшифровке код из $\Sigma_1^*$ в $\Sigma_2^*$ где $|\Sigma_2|=a$. Let S Пусть s представляет случайную переменную заданную длиной слова f(X).

Если f является оптимальным в смысле что она имеет минимальную длину слова для X, тогда

$\frac{H(X)}{\log_2 a} \leq \mathbb{E}S < \frac{H(X)}{\log_2 a} +1$

(Shannon 1948)

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

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

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

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

$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, последовательность сгенерированная из источника недостоверна в типичном случае — $A_n^\epsilon$, сходящаяся. В случае для достаточно больших: n, $P(A_n^\epsilon)>1-\epsilon$ (см AEP)

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

$2^{-n(H(X)+\epsilon)} \leq p(x_1, x_2, ..., x_n) \leq 2^{-n(H(X)-\epsilon)}$

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

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

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

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

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

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

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

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

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

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

Тогда

$\begin{matrix} 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 \\ && \\ &\leq& \mathbb{E}S \log_2 a \\ \end{matrix}$

где вторая строка является неравенством Гиббса, а пятая строка является неравенством Крафта $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{matrix} \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{matrix}$

Примечания

• 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