Содержание к диссертации
Введение
1. ОБЗОР И АНАЛИЗ МЕТОДОВ И СРЕДСТВ СЖАТИЯ ИНФОРМАЦИИ 9
1.1. Информационные основы безызбыточного кодирования данных
1.2. Зависимость эффективности вычислительной системы от организации памяти и принципов передачи информации между устройствами «
І.2.І. Анализ эффективности организации иерархической памяти с использованием модели массового обслуживания
1.3. Уравнение баланса системы 27
1.4. Классификация методов сжатия и краткая их характеристика 29
1.4.1. Статистические методы сжатия 29
1.4.2. Корреляционные методы сжатия 34
1.4.3. Комбинированные методы сжатия 37
1.5. Выводы 43
2. МЕТОДЫ СЖАТИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ 45
2.1. Метод сжатия совмещенных последовательностей . 45
2.1.1. Обоснование метода сжатия 45
2.1.2. Генерация совмещенных последовательностей помощью сдвигового регистра
2.1.3. Операторная модель регистра сдвига 53
2.1.4. Штричная форма представления регистра сдвига
2.2. Синтез накопителей на сдвиговых регистрах .
2.2.1. Основные определения
2.2.2. Методика синтеза накопителей на сдвиговых регистрах
2.3. Полиномиальный метод сжатия
2.4. Выводы
3. РЕАЛИЗАЦИЯ МЕТОДОВ СЖАТИЯ
3.1. Реализация принципа сжатия совмещенных последовательностей
3.1.1. Исследование методов организации ЗУ с последовательным доступом 79
3.1.2. Организация ЗУ с параллельной выборкой 94
3.2. Реализация полиномиального метода сжатия ПІ
3.2.1. Применение полиномиального метода сжатия для ттт
реализации управления
3.3. Выводы
4. АВТОМАТИЗИРОВАННЫЕ СРЕДСТВА ОЦЕНИВАНИЯ СЖАТИЯ
КОДИРОВАНИЯ ИНФОРМАЦИИ 321
4.1. Методика оценивания
4.2. Применение и организация моделирования 222
4.2.1. Исследование метода сжатия совмещенных послетодовательностей
4.2.2. Оценка полиномиального метода сжатия 133
4.2.3. Оценивание автоматного метода сжатия 336
4.2.4. Оценивание сжатия методом Хаффмана 152
4.3. Организация системы оценивания 156
4.4. Выводы 162
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЯ
- Информационные основы безызбыточного кодирования данных
- Генерация совмещенных последовательностей помощью сдвигового регистра
- Реализация принципа сжатия совмещенных последовательностей
- Применение и организация моделирования
Информационные основы безызбыточного кодирования данных
Вычислительные системы оперируют с дискретной информацией. По определению [49] информация - это отображение разнообразия, присущего объектам и явлениям реального мира.
Системы, в которых используется кодирование информации с использованием алфавита из А символов с числом разрядов Я- , должны потенциально обладать объемом памяти Л 1- для хранения всевозможных видов данных. Однако,в действительности в течение относительно длительных промежутков времени система оперирует ограниченным числом данных /V , и нижняя граница объема памя ти, при условии, что каждое данное представляет специфический объект, отличающийся от всех /V -I остальных, и без учета прин ципа преобразования,равна Htoo H. Это значение естественно v следует из общего закона [85] ,ег,.х При общих вычислениях, когда все данные представляют собой различные числа, следует ориентироваться на нижнюю границу с количеством разрядов на каждый символ
Характерные для ряда задач наборы данных могут иметь избыточное кодирование, так как далеко не все цифры (символы) и их сочетания одинаково часто используются, а некоторые из них вообще не встречаются [63, 88] . Это имеет место для широко распространенного кодирования символов 8 - разрядными кодами (байтами). В этом случае сообщение длины t. может иметь . При заданном f/j одну и ту же информацию можно хранить (передавать) меньшим числом разрядов.
Разность Итак - НІ называют избыточной информацией.
Между различными значениями может быть установлена корреля- , ция, что позволяет прогнозировать или генерировать следующее значение.
Условно методы сжатия, использующие эти закономерности, можно разделить на статистические, учитывающие частотные свойства символов или их наборов, и корреляционные, учитывающие связи между данными. При этом можно оптимизировать кодирование и сократить объем памяти, необходимый для хранения. Восстанавливая (декодируя) символ для представления его в форме,удобной для анализа и преобразования на основе известной корреляции, представленной некоторой функцией fi+i = Fffl... )% можно следующее значение вычислить, не обращаясь к памяти.
Генерация совмещенных последовательностей помощью сдвигового регистра
Решение поставленной задачи основано на свойствах устройства с обратными связями генерировать различные последовательности двоичных символов в зависимости от его исходного состояния.
Идей, сжатия заключается в том, что в накопителе памяти, например, ПЗУ (рис.2.15), хранятся не все разряды двоичного слова, а только его часть, из которого в процессе считывания формируется недостающаяся часть слова. С этой целью в качестве выходного регистра памяти можно использовать сдвиговый регистр с обратными связями по модулю два.
Задача решается следующим образом [65].
Пусть в памяти необходимо хранить массив из Т П- разрядных двоичных слов.
Реализация принципа сжатия совмещенных последовательностей
Представление данных в виде "сжатой" последовательности позволяет использовать сдвиговые регистры в качестве накопителей запоминающих устройств. Принцип построения накопителей ЗУ основан на методике, разработанной в п.2.2.2.
Если известны начальное состояние регистра и порядок следования слов, то в качестве адреса можно использовать номер слова в последовательности. При этом адрес в двоичной форме будет представлен ? == 1 о$2 71 — разрядным словом.
Вариант схемной реализации рассмотренного способа обращения представлен на рис.3.16.После каждого такта сдвига на сдвиговом регистре записывается новое слово, а на счетчике - адрес, соответствующий этому слову. При совпадении текущего адреса с адресом, записанным на регистре адреса, происходит считывание информации.
class4 АВТОМАТИЗИРОВАННЫЕ СРЕДСТВА ОЦЕНИВАНИЯ СЖАТИЯ
КОДИРОВАНИЯ ИНФОРМАЦИИ class4
Применение и организация моделирования
Рассмотренные методы оценивания реализованы в виде комплекса программ. Структура комплекса приведена на рис.4.15 и разделяется на несколько уровней иерархии:
- уровень приближенного оценивания по вероятностной модели;
- уровень статистического оценивания;
- уровень точной модели.
Для приближенных методов разработана вероятностно-марковская модель, которая позволяет оценить эффективность сжатия-части или всего массива по принципу автоматного метода. С этой целью разработана программа сбора статистики повторяемости символов в массиве. Блок-схема программы приведена на рис.4.16.
На каждом уровне, кроме последнего, методы упорядочены с учетом снижения значений эффективности сжатия в соответствии с выполненными впредыдущих параграфах исследованиями.
Следующий порядок принят на первом и втором уровнях: вначале выполняется приближенное оценивание массива (или его части) по вероятностно-марковской модели, если результаты удовлетворительные - осуществляется переход на второй уровень. Анализируется сжимаемый массив. Массив, содержащий большое количество повторяемых символов (до 30-40$), подвергается статистическому оцениванию автоматным способом, иначе-по коду Хаффмана.
Ба нижнем, наиболее трудоемком уровне оценивания, порядок определяется сложностью модели - сначала наименее сложные: полиномиальный и метод совмещенных последовательностей, затем моделирование по Хаффману и автоматный метод.
