СЖАТИЕ И ЗАЩИТА ИНФОРМАЦИИ НА ОСНОВЕ ДВОИЧНЫХ БИНОМИАЛЬНЫХ КОДОВ

Найти оптимальный код со средней длиной Постановка задачи

Идея решения задачи ОСНОВЫВАЕТСЯ НА РАЗЛОЖЕНИИ ЧИСЛА НА КЛАССОВ ЭКВИВАЛЕНТНОСТИ

Источник исходных сообщений преобразуется в n + 1 источник равновесных кодовых комбинаций. Источник в тактовый момент времени с вероятностью, i = 1, 2, …,, генерирует i-ю равновесную кодовую комбинацию с k единицами.

Анализ идеи

Энтропия источника числа единиц В

Избыточность источника В

Энтропия источника

Энтропия источника А

Избыточность источника А

Методы оптимального равновесного кодирования Основной метод 1. Подсчитывается число единиц k = 0, 1, …, n в кодируемом исходном двоичном сообщении длины n, генерируемом источником. 2. Суммируются вероятности, i = 1, 2, …,, сообщений с k единицами, k= 0, 1, …, n, входящих в исходное множество, состоящее из сообщений источника. В результате находятся вероятности генерирования источником чисел, содержащих k единиц.

Продолжение метода 3. На основе классического кода Шеннона-Фано или Хаффмена по полученным в пункте 2 значениям вероятностей производится оптимальное кодирование сообщения о числе единиц, генерируемое источником. 4. Находятся вероятности генерирования сообщений источником.

Продолжение метода 5. С помощью классического метода производится оптимальное кодирование сообщения источника. 6. Кодовая комбинация числа единиц источника и сообщение источника объединяются (сцепляются), и как единое сжатое сообщение поступает к приемнику.

Модифицированный метод Отличие данного алгоритма от основного происходит только по пункту 3 3. Производится равномерное кодирование сообщения о числе единиц, генерируемых источником В, кодовым словом длиною бит. При

Комбинаторный метод

Энтропия комбинаторного источника А

Энтропия комбинаторного источника В

. Комбинаторный метод 1. Подсчитывается число единиц k в кодируемом исходном двоичном сообщении длины n. Тем самым оно преобразуется в равновесную кодовую комбинацию с числом единиц k. 2. Число единиц кодируется двоичной кодовой комбинацией длиной равной округленному значению в большую сторону.

Продолжение 3. Равновесная кодовая комбинация преобразуется в ее двоичный номер длиной, равной округленному в большую сторону значению. 4. Полученные кодовые представления числа единиц и номера равновесной кодовой комбинации объединяются в одно двоичное сообщение, и в таком виде передаются к приемнику.

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

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

Продолжение Второй метод работает при условии биномиальныйыйого распределения вероятностей двоичных символов в сообщениях или близком к нему, и тогда не требуются знания вероятностей сообщений. Его особенность – это возможность использования для своей реализации комбинаторных методов преобразования информации, что ускоряет и упрощает процедуру оптимального кодирования. Эффективность сжатия при этом в ряде случаев приближается к уровню классических оптимальных кодов. 31

Продолжение Характерным свойством данных методов оптимального кодирования является наличие в них для каждого из сообщений индивидуального ключа, без которого невозможно его восстановление. Это позволяет говорить об определенном уровне защиты передаваемой информации, использующей равновесное оптимальное кодирование. 32

БИНОМИАЛЬНЫЕ СИСТЕМЫ СЧИСЛЕНИЯ С ДВОИЧНЫМ АЛФАВИТОМ 33

34 СТРУКТУРА БИНОМИАЛЬНОЙ СИСТЕМЫ СЧИСЛЕНИЯ

35 ДВОИЧНАЯ БИНОМИАЛЬНАЯ НУМЕРАЦИОННАЯ ФУНКЦИЯ

36 БИНОМИАЛЬНЫЕ ЧИСЛА Неравномер. биномиальныйый. числа Равномер. биномиальныйый. числа Код с постоянным весом Универсальный промышленный код прямой инверсный

37 ОГРАНИЧЕНИЯ

Спасибо за внимание