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

---

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

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

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

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

Пусть ${\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).

---