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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

В информатике Теорема об источнике шифрования (Шеннон 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. Пусть 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 являющееся НОР, его временной ряд X1, …, Xn также НОР с энтропией 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}

Примечания[править | править исходный текст]