Анализ, классификация и моделирование алгоритмов сжатия

• Автор: Шубович, Валерий Геннадьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Ульяновск
• Количество страниц: 210 с. : ил

Введение.

Глава 1. Анализ теоретических и экспериментальных основ

моделирования алгоритмов сжатия.

1.1. Задачи, для решения которых используется сжатие данных.

1.2. Анализ избыточности источников сообщений.

1.3.Теоретические подходы к сжатию источников информации. Моделирование и основные методы
1.4. Анализ и обоснование критериев оценки эффективности алгоритмов сжатия Теоретические подходы к сжатию

источников информации

1.5. Определение требований к критериям оценки АС.

1.6. Пример получения зависимости ТсДКс.

1.7. Модель разбиения пространства объектов по вектору признаков

Выводы по первой главе.
Глава 2. Оценка эффективности и классификация алгоритмов
обратимого сжатия
2.1. Обоснование новых критериев и классификация алгоритмов
сжатия на основе файловых признаков
2.2. Классификация алгоритмов сжатия по временным критериям .
2.3. Оценка сложности вектора признаков АС
2.4. Анализ результатов классификации
Выводы по второй главе. . III
Глава 3.Моделирование алгоритма сжатая на основе выделения
граничной точки
3.1. Постановка общей задачи сжатия табличных данных
3.2. Оценка аппаратных затрат на реализацию сжатой таблицы
3.3. Метод сжатия на основе выделения граничной точки
3.4. Анализ функции Рх.
3.5. Нахождение граничной точки.
3.6. Избыточность множеств X, У и формирование 5 и X.
3.7. Формирование множеств О и К
3.8. Нахождение граничных точек.
3.9. Определение нагрузки на разрядный вход регистра результата. Периодичность узловых значений
3 Графическая интерпретация метода
3 Выбор функциональной системы генератора функции 4 х
Выводы по третьей главе .
Глава 4. Анализ результатов исследования и практические
рекомендации .
4.1. Применение таблиц замены для разработки алгоритма обратимого сжатия данных
4.2. Оценка эффективности нового алгоритма сжатия
4.3. Уточнение функций классификаций
Выводы по четвертой главе.
Заключение
Библиографический список использованной литературы.
Приложения
ПЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ
ОБОЗНАЧЕНИЙ, СИМВОЛОВ, ЕДИНИЦ И ТЕРМИНОВ
АС алгоритм сжатия
АОСД алгоритм обратимого сжатия данных
АСУ автоматизированная система управления
АДП аппроксимативное деление пополам
ААДП алгоритм аппроксимативного деления пополам АСИСО алгоритм обраимого сжатия посредством иерархического сопоставления образов ИСО иерархическое сопоставление образов
ИАСД иерархический алгоритм сжатия данных
ПАДП процедура аппроксимативного деления пополам ПСС правила сокращения сложности
ПАСД последовательный алгоритм сжатия данных
СД сжатие данных
ССД средства сжатия данных
ТЗ таблица замены
УТЗ укомплектованная таблица замены
сеГ нижний индекс при знаке равенства означает по
определению
ВВЕДЕН И Е
Одним из важных аспектов проблем передачи, хранения и обработки информации является задача сжатия данных.
Большие объемы хранимой информации определяют задачи экономного расходования ресурсов ЭВМ, компактного представления данных на различных магнитных носителях, что, несомненно, вызывает потребность в поиске путей сокращения временных затрат на получение извлечение информации из сжатых структур. Временные показатели алгоритмов сжатия играют важную роль в системах реального масштаба времени, в рамках которых приходится решать задачи сжатия информации, где протекание процессов сжатия и восстановления исходных данных имеюз ограничения по времени например, в системах распознания летательных объектов свойчужой, управления движением самолетов при посадке и т.д.
К сожалению, в настоящее время отсутствует единая методика тестирования алгоритмов сжатия АС, число которых ежегодно растет. Нет единого подхода к обоснованному выбору критериев оценки эффективности АС, отсутствуют сами критерии, использование которых позволило бы решать задачи классификации моделей алгоритмов сжатия. Все это только вносит определенные трудности при выборе АС для моделирования различных технических систем кодирования и передачи информации по каналам связи, а также для их использования в решении практических задач сжатия в определенных предметных областях.
Актуальность


I компьютерная томография использует объемный синтез изображений, причем требования по быстродействию к цифровой обработке намного превосходят все существующие в настоящее время 2 такие же требования по быстродействию предъявляются и к решению задачи спутниковых фотографий, в которой наиболее сложной частью является совмещение нескольких изображений ДО. Цифровая обработка сейсмической информации для разведки земных недр занимает практически все процессорное время нескольких компьютеров. Вычислительные мощности, потребляемые в сейсморазведке, возрастают на порядок каждые три года ДО. ЭВМ. ОЗУ является самым дорогостоящим видом памяти ЭВМ, понятна актуальность использования методов сжатия сейсмической информации ДО. Перечислим задачи, относящиеся к замкнутым системам. Широко используются табличные автоматы в системах управления по разомкнутой схеме технологическими процессами переработки сырья ДО, для управления химической частью штапельного производства, промывными фильтрами целлюлознобумажного производства, управления процессом гидролиза в производстве растительных сахаров ДО, процессом экстрактивной ректификации синтетического каучука ДО, управления непрерывной вытяжкой стеклянных труб. Как указывается в 7Д ресурсов одной управляющей микроЭВМ хватает только для управления станками, содержащими не более трех координат. Использование же нссчольких ЭВМ приводит к избыточности. К классу задач, связанных с размещением р памяти ЭВМ больших массивов информации, относятся задачи размещения баз данных, баз знаний, САПР, систем искусственного интеллекта, систем семантической обработки речевых сигналов, систем автоматизации эксперимента и т. Например, в современных базах данных объемы хранимых данных достигают миллионов и миллиардов байт, а это оказывает существенное влияние на стоимость хранения данных и ухудшает временные показатели работы в реальном масштабе времени. В л показано, что стоимость математического обеспечения, необходимого для выполнения процессов уплотнения, является умеренной, а затраты на него окупаются в течении одного или двух месяцев эксплуатации базы данных. В таблице 1 представлены задачи, для решения которых используется сжатие данных, для которых выделены их важнейшие параметры характеристики и указаны необходимые ресурсы. Общими свойствами перечисленных задач см. Противоречивость требований увеличение объема памяти для хранения данных, с одной стороны, и скорости обработки информации с другой стороны, а также повышение технологичности системы обуславливает необходимость поиска новых принципов функциональноструктурной организации систем, разработки новых подходов к их проектированию с учетом возможностей, предоставляемых современной микроэлектронной технологией. Отмеченные выше факторы и являются практическим стимулом для выполнения диссертационной работы. Телеметрия сигналы Большой, . Распознапанис текстов, чертежей. Малый, . Сжатие речевых сигналов Малый. Спектральным анализ Малый. Обработка сейсмической информации Средний. Обработка экспериментальных данных в ядерных экспериментах Средний, 0. Управление непрерывным технологическим процессом Средний. Мб Малое СК. Моделирование катастроф Большой. Мб Среднее С С . Военные задачи системы быстрого реагирования, распознавания летательных объектов свончужой Малый. Системы моделирования процессов в мировом океане Большой. Мб Среднее С. Системы наблюдения за небесными светилами за Солнцем Малый, . Системы цифровой обработки радиолокационных сигналов Малый, . Навигационные системы Малый. Системы передачи данных модемы и др. Малый, Мб Малое ОК. Медицинская диагностика ЭКГ и др. Малый, . Нефтеразведка Средний, 0. Хранение баз данных различных предметных областей Средний, 0. Системы машинного перевода Малый, 3. Системы автоматизации эксперимента Малый, . Обработка сигналов со спутников Средний, 0. Системы управления космическими аппаратами Средний, 0. Обработка текстов Малый, до Мб Среднее ОК. Примечание. МбайтУаа Гбайт Малый при Гаа0 Мбайт. Введенные обозначения для графы Необходимые ресурсы СК суперкомпьютер С сеть ОК обычный компьютер.