В теории информации , источник Шеннона теорема кодирование (или бесшумная теорема кодирования ) устанавливает пределы возможного сжатия данных , а также оперативный смысл энтропии Шеннона .
Теорема исходного кодирования, названная в честь Клода Шеннона , показывает, что (в пределе, поскольку длина потока независимых и одинаково распределенных данных случайных величин (iid) стремится к бесконечности) невозможно сжать данные так, чтобы кодовая скорость (среднее количество битов на символ) меньше энтропии Шеннона источника, при этом практически нет уверенности в том, что информация будет потеряна. Однако можно получить скорость кода, произвольно близкую к энтропии Шеннона, с пренебрежимо малой вероятностью потерь.
Теорема исходного кодирования для кодов символов устанавливает верхнюю и нижнюю границы минимально возможной ожидаемой длины кодовых слов как функции энтропии входного слова (которое рассматривается как случайная величина ) и размера целевого алфавита.
Заявления
Источник кодирования является отображением из (последовательности) символов из информационного источника к последовательности символов алфавита (обычно биты) таким образом, что символы источника может быть точно восстановлены из двоичных бит (кодирование источника без потерь) или восстанавливается в течение некоторого искажения ( исходное кодирование с потерями). Это концепция сжатия данных .
Теорема исходного кода
В теории информации теорема кодирования источника (Shannon 1948) [1] неформально утверждает, что (MacKay 2003, pg. 81, [2] Cover 2006, Chapter 5 [3] ):
N i.id случайных величин, каждая с энтропией H ( X ), может быть сжато до более чем N H ( X ) битов с пренебрежимо малым риском потери информации при N → ∞ ; но, наоборот, если они сжаты до менее чем N H ( X ) битов, практически наверняка информация будет потеряна.
Теорема исходного кодирования для символьных кодов
Пусть Σ 1 , Σ 2 обозначают два конечных алфавита и пусть Σ∗
1и Σ∗
2обозначают набор всех конечных слов из этих алфавитов (соответственно).
Предположим, что X - случайная величина, принимающая значения в Σ 1, и пусть f - однозначно декодируемый код из Σ ∗
1в Σ∗
2где | Σ 2 | = а . Пусть S обозначает случайную величину, заданную длиной кодового слова f ( X ) .
Если f оптимален в том смысле, что он имеет минимальную ожидаемую длину слова для X , то (Shannon 1948):
Где обозначает оператор ожидаемого значения .
Доказательство: теорема о кодировании источника.
Если X является источником iid , его временные ряды X 1 , ..., X n являются iid с энтропией H ( X ) в дискретном случае и дифференциальной энтропией в случае с непрерывными значениями. Теорема кодирования источника утверждает, что для любого ε > 0 , то есть для любой скорости H ( X ) + ε, большей, чем энтропия источника, существует достаточно большое n и кодировщик, который принимает n iid повторений источника, X 1: n , и отображает его в n ( H ( X ) + ε ) двоичных битов, так что исходные символы X 1: n восстанавливаются из двоичных битов с вероятностью не менее 1 - ε .
Доказательство достижимости. Зафиксируем некоторое ε > 0 и пусть
Типовой набор, Аε
n, определяется следующим образом:
Свойство асимптотической равнораспределенности (AEP) показывает, что для достаточно большого n вероятность того, что последовательность, сгенерированная источником, принадлежит типичному набору Aε
n, как определено, приближается к одному. В частности, при достаточно больших п , можно сделать сколь угодно близким к 1 и, в частности, больше, чем (См. Доказательство в AEP ).
Определение типичных наборов подразумевает, что те последовательности, которые лежат в типичном наборе, удовлетворяют:
Обратите внимание, что:
- Вероятность последовательности взят из Aε
nбольше 1 - ε . - , что следует из левой части (оценка снизу) для .
- , что следует из оценки сверху для и нижняя граница полной вероятности всего множества Aε
n.
С битов достаточно, чтобы указать на любую строку в этом наборе.
Алгоритм кодирования: кодировщик проверяет, находится ли входная последовательность в пределах типичного набора; если да, он выводит индекс входной последовательности в типичном наборе; в противном случае кодировщик выдает произвольное n ( H ( X ) + ε ) разрядное число. Пока входная последовательность находится в пределах типичного набора (с вероятностью не менее 1 - ε ), кодировщик не делает ошибок. Таким образом, вероятность ошибки кодировщика ограничена сверху величиной ε .
Доказательство обратного. Обратное доказывается, показывая, что любой набор размера меньше, чем Aε
n(в смысле экспоненты) охватывал бы набор вероятностей, ограниченный от 1 .
Доказательство: теорема кодирования источника для символьных кодов.
Для 1 ≤ i ≤ n пусть s i обозначает длину слова каждого возможного x i . Определять, где C выбрано таким, чтобы q 1 + ... + q n = 1 . потом
где вторая строка следует из неравенства Гиббса, а пятая строка следует из неравенства Крафт :
так что журнал C ≤ 0 .
Для второго неравенства можно положить
чтобы
и другие
а также
и поэтому по неравенству Крафт существует код без префиксов, имеющий такую длину слова. Таким образом, минимальный S удовлетворяет
Распространение на нестационарные независимые источники
Кодирование источника без потерь с фиксированной скоростью для нестационарных независимых источников с дискретным временем
Определить типовой набор Aε
n в виде:
Тогда для данного δ > 0 и достаточно большого n Pr ( Aε
n)> 1 - δ . Теперь мы просто кодируем последовательности в типичном наборе, и обычные методы в кодировании исходного кода показывают, что мощность этого набора меньше, чем. Таким образом, в среднем H n ( X ) + ε битов достаточно для кодирования с вероятностью больше 1 - δ , где ε и δ можно сделать сколь угодно малыми, увеличив n .
Смотрите также
Рекомендации
- ^ CE Shannon , " Математическая теория коммуникации ", Bell System Technical Journal , vol. 27, стр. 379–423, 623–656, июль, октябрь 1948 г.
- ^ Дэвид JC MacKay. Теория информации, логический вывод и алгоритмы обучения Кембридж: Cambridge University Press, 2003. ISBN 0-521-64298-1
- ^ Обложка, Томас М. (2006). «Глава 5: Сжатие данных». Элементы теории информации . Джон Вили и сыновья. ISBN 0-471-24195-4.