Метод матрично-рангового кодирования и его применение

• Автор: Терентьева, Юлия Юрьевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Ульяновск
• Количество страниц: 145 с. : ил.

1.1 Избыточность источников сообщений

1.2 Избыточность сжимающих отображений стационарных источников .

1.3 Основные подходы к сжатию источников информации

1.4 Анализ рассматриваемого источника информации.

1.5 Постановка задачи

ГЛАВА

Разработка и исследование

метода матричнорангового кодирования

2.1 Матрица кода. Алгоритм кодирования. Алгоритм декодирования. . .

2.2 Матричное представление алгоритмов.

2.3 Оценка сложности.

2.4 Теорема о ближайшем предшествовании
2.5 Доказательство биективности разработанного преобразования
2.6 Оптимальный ранг. Алгоритм нахождения оптимального ранга. .
2.7 Избыточность длины кодового слова
2.8 Некоторые свойства длины кода
ГЛАВА
Разработка алгоритма сжатия
на основе метода матричнорангового кодирования
3.1 Алгоритм сжатия
3.2 Альтернативный способ реализации алгоритма сжатия
без привлечения дополнительной памяти
3.3 Теорема о коэффициенте сжатия
3.4 Теорема об асимптотической оптимальности кодирования 3.1 .
3.5 Обсуждение результатов экспериментов
ГЛАВА
Применение метода матричнорангового кодирования
4.1 Разработка блоковых кодов.
4.2 Моделирование процесса передачи информации блоковыми кодами
при несимметричном параллельном канале связи
4.3 Математические модели устройств,
реализующих элементарные операции.
4.4 Схема формирования управляемой перестановки для построения аппаратноориентированного скоростного блочного недетерминированного шифра.
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ
ЛИТЕРАТУРА


Проблема минимизации избыточности занимает важное место в теории информации. Выявление природы возникновения избыточности с целью выбора определенного метода сжатия представляет собой отдельную задачу. Решение этой задачи обычно сводится к выбору существующих моделей источников 1, адекватных рассматриваемому с какойто вероятностью. Для каждой модели источника существует определение энтропии, которая, согласно основной теореме К. Шеннона 3, задает предельное значение коэффициента сжатия. Как правило, методы сжатия уменьшают явную избыточность, заложенную в выбранной модели источника. Недостижимость коэффициентом сжатия своей нижней грани свидетельствует о том, что существует некий скрытый вид избыточности, который остался за пределами возможностей методов сжатия. Это может таюке быть показателем того, что выбранная модель источника не является адекватной, и возникает проблема наиболее эффективного представления данных. Другими словами, в зависимости от выбираемой модели источника явная избыточность может оказаться скрытой и наоборот. Выявление скрытой избыточности представляет собой достаточно сложную задачу и может решаться путем преобразований например, эквивалентных исходного представления информации к более компактному представлению, причем такие преобразования в настоящее время носят эвристический характер и вследствие этого часто дают хорошие эффекты. Таким образом, тот факт, насколько реальный поток информации соответствует описывающей его модели, определяет выбор метода сжатия и эффект уменьшения явной и скрытой избыточности.