Интернет магазин китайских планшетных компьютеров



Компьютеры - Теорема Шеннона об источнике шифрования

22 января 2011
канализационные насосы sololift

Оглавление:
1. Теорема Шеннона об источнике шифрования
2. Доказательство теоремы об источнике шифрования
3. Доказательство теоремы об источнике шифрования для кодов символов



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

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

Утверждение

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

Источник шифрования для кодов символов

В информатике Теорема об источнике шифрования утверждает что:

«N случайная переменная с энтропией H может быть сжата в более чем NH битов с незначительным риском потери данных если N стремится к бесконечности, но если сжатие происходит менее в чем NH) бит, то данные скорее всего будут потеряны..»

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

Пусть Σ1, Σ2 значат два конечных алфавита, и пусть \Sigma_1^* и \Sigma_2^* означают набор всех конечных слов из этих алфавитов.

Предположим что X — случайная переменная которая принимает значение из Σ1 а f — поддающийся расшифровке код из \Sigma_1^* в \Sigma_2^* где | Σ2 | = a. Let S Пусть s представляет случайную переменную заданную длиной слова f.

Если f является оптимальным в смысле что она имеет минимальную длину слова для X, тогда

 \frac{H}{\log_2 a} \leq \mathbb{E}S < \frac{H}{\log_2 a} +1



Просмотров: 2616


<<< Сжатие с использованием вейвлет