Теорема Шеннона об источнике шифрования
В теории информации теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Теорема показывает, что (когда в потоке независимо и одинаково распределённых (НОР) случайных переменных количество данных стремится к бесконечности) невозможно сжать данные настолько, что оценка кода (среднее число бит на символ) меньше, чем энтропия Шеннона исходных данных, без потери точности информации. Тем не менее, можно получить код, близкий к энтропии Шеннона без значительных потерь.
Теорема об источнике шифрования для кодов символов приводит верхнюю и нижнюю границу к минимально возможной длине зашифрованных слов как функция энтропии от входного слова (которое представлено как случайная переменная) и от размера требуемой азбуки.
Утверждение
Исходный код — это отображение (последовательность) из хранилища информации в последовательность алфавитных символов (обычно битов) таких что исходный символ может быть однозначно получен из двоичных разрядов (беспотерьный источник кодирования) или получен с некоторым различием (источник кодирования с потерями). Это идея сжатия данных.
Источник шифрования для кодов символов
В информатике теорема об источнике шифрования (Шеннон 1948) утверждает, что:
- «N случайная переменная с энтропией H(X) может быть сжата в более чем N H(X) битов с незначительным риском потери данных, если N стремится к бесконечности, но если сжатие происходит менее в чем N H(X) бит, то данные скорее всего будут потеряны. (MacKay 2003).»
Теорема об источнике шифрования для кодов символов
Пусть , значат два конечных алфавита и пусть и означают набор всех конечных слов из этих алфавитов (упорядоченных).
Предположим что X — случайная переменная, которая принимает значение из , а f — поддающийся расшифровке код из в , где . Пусть S представляет случайную переменную, заданную длиной слова f(X).
Если f является оптимальным в смысле, что она имеет минимальную длину слова для X, тогда
(Shannon 1948).
Доказательство теоремы об источнике шифрования
Задано являющееся НОР, его временной ряд X1, …, Xn также НОР с энтропией H(X) в случае дискретных значений, и с дифференциальной энтропией в случае непрерывных значений. Теорема об источнике шифрования утверждает, что для каждого для каждой оценки большей, чем энтропия ресурса, существует достаточно большое n и шифрователь, который принимает n НОР копий ресурса , , , и отображает его в двоичных бит таким способом, что исходный символ может быть восстановлен из двоичных бит, X вероятностью не менее чем .
Доказательство
Возьмем некоторое . формула для, , выглядит следующим образом:
AEP показывает что для достаточно больших n, последовательность сгенерированная из источника недостоверна в типичном случае — , сходящаяся. В случае для достаточно больших: n, (см AEP)
Определение типичных наборов подразумевает, что те последовательности, которые лежат в типичном наборе, удовлетворяют:
Заметьте, что:
- Вероятность того, что последовательность была получена из
больше чем
- начиная с вероятности полной совокупности является наиболее большим.
- . Fдля доказательства используйте верхнюю границу вероятности для каждого терма в типичном случае, и нижнюю границу для общего случая .
Начиная с битов достаточно, чтобы отличить любую строку
Алгоритм шифрования: шифратор проверяет является ли ложной входящая последовательность, если да, то возвращает индекс входящей частоты в последовательности, если нет, то возвращает случайное digit number. численное значение. В случае если входящая вероятность неверна в последовательности (с частотой примерно ), то шифратор не выдает ошибку. То есть вероятность ошибки составляет выше чем
Доказательство обратимости Доказательство обратимости базируется на том, что требуется показать что для любой последовательности размером меньше чем (в смысле экспоненты) будет покрывать частоту последовательности, ограниченную 1.
Доказательство теоремы об источнике шифрования для кодов символов
Пусть длина слова для каждого возможного (). Определим , где С выбирается таким образом, что: .
Тогда
где вторая строка является неравенством Гиббса, а пятая строка является неравенством Крафта , .
для второго неравенства мы можем установить
и так
а затем
и
Таким образом, минимальное S удовлетворяет
Примечания
- 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