Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
2
СЖАТИЕ И ЗАЩИТА ИНФОРМАЦИИ НА ОСНОВЕ ДВОИЧНЫХ БИНОМИАЛЬНЫХ КОДОВ
3
Найти оптимальный код со средней длиной Постановка задачи
4
Идея решения задачи ОСНОВЫВАЕТСЯ НА РАЗЛОЖЕНИИ ЧИСЛА НА КЛАССОВ ЭКВИВАЛЕНТНОСТИ
5
Источник исходных сообщений преобразуется в n + 1 источник равновесных кодовых комбинаций. Источник в тактовый момент времени с вероятностью, i = 1, 2, …,, генерирует i-ю равновесную кодовую комбинацию с k единицами.
7
Анализ идеи
10
Энтропия источника числа единиц В
13
Избыточность источника В
14
Энтропия источника
15
Энтропия источника А
16
Избыточность источника А
19
Методы оптимального равновесного кодирования Основной метод 1. Подсчитывается число единиц k = 0, 1, …, n в кодируемом исходном двоичном сообщении длины n, генерируемом источником. 2. Суммируются вероятности, i = 1, 2, …,, сообщений с k единицами, k= 0, 1, …, n, входящих в исходное множество, состоящее из сообщений источника. В результате находятся вероятности генерирования источником чисел, содержащих k единиц.
20
Продолжение метода 3. На основе классического кода Шеннона-Фано или Хаффмена по полученным в пункте 2 значениям вероятностей производится оптимальное кодирование сообщения о числе единиц, генерируемое источником. 4. Находятся вероятности генерирования сообщений источником.
21
Продолжение метода 5. С помощью классического метода производится оптимальное кодирование сообщения источника. 6. Кодовая комбинация числа единиц источника и сообщение источника объединяются (сцепляются), и как единое сжатое сообщение поступает к приемнику.
22
Модифицированный метод Отличие данного алгоритма от основного происходит только по пункту 3 3. Производится равномерное кодирование сообщения о числе единиц, генерируемых источником В, кодовым словом длиною бит. При
23
Комбинаторный метод
25
Энтропия комбинаторного источника А
26
Энтропия комбинаторного источника В
27
. Комбинаторный метод 1. Подсчитывается число единиц k в кодируемом исходном двоичном сообщении длины n. Тем самым оно преобразуется в равновесную кодовую комбинацию с числом единиц k. 2. Число единиц кодируется двоичной кодовой комбинацией длиной равной округленному значению в большую сторону.
28
Продолжение 3. Равновесная кодовая комбинация преобразуется в ее двоичный номер длиной, равной округленному в большую сторону значению. 4. Полученные кодовые представления числа единиц и номера равновесной кодовой комбинации объединяются в одно двоичное сообщение, и в таком виде передаются к приемнику.
29
Выводы Таким образом, в работе на основе классических оптимальных кодов Шеннона- Фано и Хаффмена предложен метод оптимального равновесного кодирования и его модификации, дающие возможность эффективно сжимать двоичные сообщения большой длины. 29
30
Первый метод по аналогии с известными классическими методами для своей реализации требует знания распределения вероятностей возможных сообщений на выходе их источника и обладает эффективностью сжатия на уровне классических кодов. Сложность и время оптимального кодирования при этом уменьшается 30
31
Продолжение Второй метод работает при условии биномиальныйыйого распределения вероятностей двоичных символов в сообщениях или близком к нему, и тогда не требуются знания вероятностей сообщений. Его особенность – это возможность использования для своей реализации комбинаторных методов преобразования информации, что ускоряет и упрощает процедуру оптимального кодирования. Эффективность сжатия при этом в ряде случаев приближается к уровню классических оптимальных кодов. 31
32
Продолжение Характерным свойством данных методов оптимального кодирования является наличие в них для каждого из сообщений индивидуального ключа, без которого невозможно его восстановление. Это позволяет говорить об определенном уровне защиты передаваемой информации, использующей равновесное оптимальное кодирование. 32
33
БИНОМИАЛЬНЫЕ СИСТЕМЫ СЧИСЛЕНИЯ С ДВОИЧНЫМ АЛФАВИТОМ 33
34
34 СТРУКТУРА БИНОМИАЛЬНОЙ СИСТЕМЫ СЧИСЛЕНИЯ
35
35 ДВОИЧНАЯ БИНОМИАЛЬНАЯ НУМЕРАЦИОННАЯ ФУНКЦИЯ
36
36 БИНОМИАЛЬНЫЕ ЧИСЛА Неравномер. биномиальныйый. числа Равномер. биномиальныйый. числа Код с постоянным весом Универсальный промышленный код прямой инверсный
37
37 ОГРАНИЧЕНИЯ
38
Спасибо за внимание
Еще похожие презентации в нашем архиве:
