Русская Википедия:Теорема Шеннона об источнике шифрования
В теории информации теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Теорема показывает, что (когда в потоке независимо и одинаково распределённых (НОР) случайных переменных количество данных стремится к бесконечности) невозможно сжать данные настолько, что оценка кода (среднее число бит на символ) меньше, чем энтропия Шеннона исходных данных, без потери точности информации. Тем не менее, можно получить код, близкий к энтропии Шеннона без значительных потерь.
Теорема об источнике шифрования для кодов символов приводит верхнюю и нижнюю границу к минимально возможной длине зашифрованных слов как функция энтропии от входного слова (которое представлено как случайная переменная) и от размера требуемой азбуки.
Утверждение
Исходный код — это отображение (последовательность) из хранилища информации в последовательность алфавитных символов (обычно битов) таких что исходный символ может быть однозначно получен из двоичных разрядов (беспотерьный источник кодирования) или получен с некоторым различием (источник кодирования с потерями). Это идея сжатия данных.
Источник шифрования для кодов символов
В информатике теорема об источнике шифрования (Шеннон 1948) утверждает, что:
- «N случайная переменная с энтропией H(X) может быть сжата в более чем N H(X) битов с незначительным риском потери данных, если N стремится к бесконечности, но если сжатие происходит менее в чем N H(X) бит, то данные скорее всего будут потеряны. (MacKay 2003).»
Теорема об источнике шифрования для кодов символов
Пусть <math>\Sigma_1</math>, <math>\Sigma_2</math> значат два конечных алфавита и пусть <math>\Sigma_1^*</math> и <math>\Sigma_2^*</math> означают набор всех конечных слов из этих алфавитов (упорядоченных).
Предположим что X — случайная переменная, которая принимает значение из <math>\Sigma_1</math>, а f — поддающийся расшифровке код из <math>\Sigma_1^*</math> в <math>\Sigma_2^*</math>, где <math>|\Sigma_2| = a</math>. Пусть S представляет случайную переменную, заданную длиной слова f(X).
Если f является оптимальным в смысле, что она имеет минимальную длину слова для X, тогда
- <math> \frac{H(X)}{\log_2 a} \leq \mathbb{E}S < \frac{H(X)}{\log_2 a} + 1</math>
(Shannon 1948).
Доказательство теоремы об источнике шифрования
Задано <math>X</math> являющееся НОР, его временной ряд X1, …, Xn также НОР с энтропией H(X) в случае дискретных значений, и с дифференциальной энтропией в случае непрерывных значений. Теорема об источнике шифрования утверждает, что для каждого <math> \epsilon > 0 </math> для каждой оценки большей, чем энтропия ресурса, существует достаточно большое n и шифрователь, который принимает n НОР копий ресурса , <math> X^{1:n} </math>, , и отображает его в <math> n.(H(X)+\epsilon) </math> двоичных бит таким способом, что исходный символ <math> X^{1:n} </math> может быть восстановлен из двоичных бит, X вероятностью не менее чем <math> 1 - \epsilon </math>.
Доказательство
Возьмем некоторое <math> \epsilon > 0 </math>. формула для, <math>A_n^\epsilon</math>, выглядит следующим образом:
<math> 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\}</math>
AEP показывает что для достаточно больших n, последовательность сгенерированная из источника недостоверна в типичном случае — <math>A_n^\epsilon</math>, сходящаяся. В случае для достаточно больших: n, <math>P(A_n^\epsilon)>1-\epsilon</math> (см AEP)
Определение типичных наборов подразумевает, что те последовательности, которые лежат в типичном наборе, удовлетворяют:
- <math>
2^{-n(H(X)+\epsilon)} \leq p(x_1, x_2, ..., x_n) \leq 2^{-n(H(X)-\epsilon)} </math>
Заметьте, что:
- Вероятность того, что последовательность была получена из <math>X</math>
<math>{A_\epsilon}^{(n)}</math> больше чем <math>1-\epsilon</math>
- <math>\left| {A_\epsilon}^{(n)} \right| \leq 2^{n(H(X)+\epsilon)}</math> начиная с вероятности полной совокупности <math>{A_\epsilon}^{(n)}</math> является наиболее большим.
- <math>\left| {A_\epsilon}^{(n)} \right| \geq (1-\epsilon)2^{n(H(X)-\epsilon)}</math>. Fдля доказательства используйте верхнюю границу вероятности для каждого терма в типичном случае, и нижнюю границу для общего случая <math>{A_\epsilon}^{(n)}</math>.
Начиная с <math>\left| {A_\epsilon}^{(n)} \right| \leq 2^{n(H(X)+\epsilon)}, n.(H(X)+\epsilon)\; </math> битов достаточно, чтобы отличить любую строку
Алгоритм шифрования: шифратор проверяет является ли ложной входящая последовательность, если да, то возвращает индекс входящей частоты в последовательности, если нет, то возвращает случайное <math> n.(H(X)+\epsilon) </math> digit number. численное значение. В случае если входящая вероятность неверна в последовательности (с частотой примерно <math>1-\epsilon</math>), то шифратор не выдает ошибку. То есть вероятность ошибки составляет выше чем <math>\epsilon</math>
Доказательство обратимости Доказательство обратимости базируется на том, что требуется показать что для любой последовательности размером меньше чем <math>A_n^\epsilon</math> (в смысле экспоненты) будет покрывать частоту последовательности, ограниченную 1.
Доказательство теоремы об источнике шифрования для кодов символов
Пусть <math>s_i</math> длина слова для каждого возможного <math>x_i</math> (<math>i = 1, \ldots, n</math>). Определим <math>q_i = a^{-s_i}/C</math>, где С выбирается таким образом, что: <math>\sum q_i = 1</math>.
Тогда
- <math>
\begin{align}
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{align} </math>
где вторая строка является неравенством Гиббса, а пятая строка является неравенством Крафта <math>C = \sum_{i=1}^n a^{-s_i} \leqslant 1</math>, <math>\log C \leq 0</math>.
для второго неравенства мы можем установить
- <math>s_i = \lceil - \log_a p_i \rceil,</math>
и так
- <math>-\log_a p_i \leqslant s_i < -\log_a p_i + 1,</math>
а затем
- <math>a^{-s_i} \leqslant p_i</math>
и
- <math>\sum a^{-s_i} \leqslant \sum p_i = 1.</math>
Таким образом, минимальное S удовлетворяет
- <math>
\begin{align}
\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{align} </math>
Примечания
- Шаблон:Книга
- C. E. Shannon, «A Mathematical Theory of Communication», Bell System Technical Journal, vol. 27, pp. 379—423, 623—656, July, October, 1948
