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

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

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

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

УтверждениеПравить

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

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

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

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

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

Пусть ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_1$$\Sigma_1$ , ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_2$$\Sigma _{2}$  значат два конечных алфавита и пусть ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_1^{\ast <!--\; \ast \; -->}$$\Sigma _{1}^{*}$  и ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_2^{\ast <!--\; \ast \; -->}$$\Sigma _{2}^{*}$  означают набор всех конечных слов из этих алфавитов (упорядоченных).

Предположим что X — случайная переменная, которая принимает значение из ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_1$$\Sigma_1$ , а f — поддающийся расшифровке код из ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_1^{\ast <!--\; \ast \; -->}$$\Sigma _{1}^{*}$  в ${\mathrm{\Sigma <!--\; \Sigma \; -->}}_2^{\ast <!--\; \ast \; -->}$$\Sigma _{2}^{*}$ , где $|{\mathrm{\Sigma <!--\; \Sigma \; -->}}_2|=a$$|\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₁, …, X_n также НОР с энтропией H(X) в случае дискретных значений, и с дифференциальной энтропией в случае непрерывных значений. Теорема об источнике шифрования утверждает, что для каждого $\mathrm{ϵ<!--\; ϵ\; -->}>0$$\epsilon >0$  для каждой оценки большей, чем энтропия ресурса, существует достаточно большое n и шифрователь, который принимает n НОР копий ресурса , $X^{1:n}$$X^{1:n}$ , , и отображает его в $n.(H(X)+\mathrm{ϵ<!--\; ϵ\; -->})$$n.(H(X)+\epsilon )$  двоичных бит таким способом, что исходный символ $X^{1:n}$$X^{1:n}$  может быть восстановлен из двоичных бит, X вероятностью не менее чем $1-<!--\; -\; -->\mathrm{ϵ<!--\; ϵ\; -->}$$1-\epsilon$ .

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

Возьмем некоторое $\mathrm{ϵ<!--\; ϵ\; -->}>0$$\epsilon >0$ . формула для, $A_n^{\mathrm{ϵ<!--\; ϵ\; -->}}$$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^{\mathrm{ϵ<!--\; ϵ\; -->}}$$A_{n}^{\epsilon }$ , сходящаяся. В случае для достаточно больших: n, $P(A_n^{\mathrm{ϵ<!--\; ϵ\; -->}})>1-<!--\; -\; -->\mathrm{ϵ<!--\; ϵ\; -->}$$P(A_{n}^{\epsilon })>1-\epsilon$  (см AEP)

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

$2^{-<!--\; -\; -->n(H(X)+\mathrm{ϵ<!--\; ϵ\; -->})}\le <!--\; \le \; -->p(x_1,x_2,...,x_n)\le <!--\; \le \; -->2^{-<!--\; -\; -->n(H(X)-<!--\; -\; -->\mathrm{ϵ<!--\; ϵ\; -->})}$$2^{-n(H(X)+\epsilon )}\leq p(x_{1},x_{2},...,x_{n})\leq 2^{-n(H(X)-\epsilon )}$ 

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

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

${A_{\mathrm{ϵ<!--\; ϵ\; -->}}}^{(n)}$${A_{\epsilon }}^{(n)}$  больше чем $1-<!--\; -\; -->\mathrm{ϵ<!--\; ϵ\; -->}$$1-\epsilon$ 

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

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

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

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

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

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

Пусть $s_i$$s_{i}$  длина слова для каждого возможного $x_i$$x_{i}$  ($i=1,\dots <!--\; \dots \; -->,n$$i = 1, \ldots, n$ ). Определим $q_i=a^{-<!--\; -\; -->s_i}/C$$q_{i}=a^{-s_{i}}/C$ , где С выбирается таким образом, что: $\sum <!--\; \sum \; -->q_i=1$$\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=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{a}^{-<!--\; -\; -->s_i}⩽<!--\; ⩽\; -->1$$C=\sum _{i=1}^{n}a^{-s_{i}}\leqslant 1$ , $\log <!--\; \; -->C\le <!--\; \le \; -->0$$\log C\leq 0$ .

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

$s_i=\lceil <!--\; \lceil \; -->-<!--\; -\; -->{\log }_a<!--\; \; -->p_i\rceil <!--\; \rceil \; -->,$$s_{i}=\lceil -\log _{a}p_{i}\rceil ,$ 

и так

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

а затем

$a^{-<!--\; -\; -->s_i}⩽<!--\; ⩽\; -->p_i$$a^{-s_{i}}\leqslant p_{i}$ 

и

$\sum <!--\; \sum \; -->a^{-<!--\; -\; -->s_i}⩽<!--\; ⩽\; -->\sum <!--\; \sum \; -->p_i=1.$$\sum a^{-s_{i}}\leqslant \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}}$ 

ПримечанияПравить

• 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