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

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

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

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

Утверждение[править | править код]

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

Источник шифрования для кодов символов[править | править код]

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

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

Теорема об источнике шифрования для кодов символов[править | править код]

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

Предположим что X — случайная переменная, которая принимает значение из $\Sigma _{1}$ , а f — поддающийся расшифровке код из $\Sigma _{1}^{*}$ в $\Sigma _{2}^{*}$ , где $|\Sigma _{2}|=a$ . Пусть 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) в случае дискретных значений, и с дифференциальной энтропией в случае непрерывных значений. Теорема об источнике шифрования утверждает, что для каждого $\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{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}}

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