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

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

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

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

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

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

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

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

Предположим что X — случайная переменная, которая принимает значение из ${\displaystyle \Sigma _{1}}$, а f — поддающийся расшифровке код из ${\displaystyle \Sigma _{1}^{*}}$ в ${\displaystyle \Sigma _{2}^{*}}$, где ${\displaystyle |\Sigma _{2}|=a}$. Пусть S представляет случайную переменную, заданную длиной слова f(X).

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

${\displaystyle {\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} S<{\frac {H(X)}{\log _{2}a}}+1}$

(Shannon 1948).

Задано ${\displaystyle X}$ являющееся НОР, его временной ряд X₁, …, X_n также НОР с энтропией H(X) в случае дискретных значений, и с дифференциальной энтропией в случае непрерывных значений. Теорема об источнике шифрования утверждает, что для каждого ${\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