Введение к работе
Актуальность темы. В системах импульсной регистрации сигналов, например, в телефонии или в непрерывных технологических процессах, создаются большие потоки информации, которые необходимо хранить определенное время.1,2'3 Хранение таких массивов информации затрудняется вследствие ограшгченности объема памяти современных компьютеров. Отличительной чертой рассматриваемых источников информации является отсутствие в них с высокой вероятностью явной избыточности. Поскольку известные и эффективные методы сжатия, базирующиеся на статистических и словарных подходах, как правило, уменьшают явную избыточность4,5,6"7,8, то они не дают достаточного эффекта сжатия информации, полученной в результате работы систем импульсной регистрации, и стимулируют разработку и исследование новых методов сжатия рассматриваемой информации.
Известно, что предварительное сжатие позволяет существенно улучшить характеристики системы связи.9 В зависимости от различных типов источников информащіи разработано множество методов кодирования. Здесь следует отметить работы Д. Хаффмена3, К. Шеннона4, Р. Фано5, Б. Фитингофа10, Р. Кричевского8, Р. Галлагера11, Л. Дэвисона12, Т. Ковера13, П. Элайеса14, А. Лемпелла, Д. Зива6,7, Т. Белла15, Я. Виттена16, Д. Риссанена17 и др.
1 Н.А.Куцевич. Программное обеспечение систем контроля и управления и Windows-технологии.// Мир
компьютерной автоматизации. 1999, А'?3. С.9-17.
2 Т.Зеленова. Принципы построения современных телефонных систем.// Мир компьютерной автоматизации.
1998, ЖЗ.-С.7-12.
А.ПКулаичев. Компьютерный контроль процессов и анализ сигналов.- М.:Информатика и компьютеры, 1999.- 330с.
4 Д.А.Хаффмен. Метод построения кодов с минимальной избыточностью.// Кибернетический сборник. -
1963, вьш.З.
5 КШеннон. Работы по теории информации и кибернетике. М.: ИЛ., 1963.- 828с.
6 Р.Фано. Передача информации. Статиспгческая теория связи. М.: Наука, 1965.
7 Ziv J., Lempel A. An Universal Algorithm for Sequental Data Compression.// ШЕЕ Transactions of Information
Theory.-1977.-Vol.23.-№3.
8 Ziv J., Lempel A. Compression of Individual Sequences via Variable Rate Coding.// IEEE Transactions of
Information Theory. -1978. - Vol.23. - №3.
' Р.Е.Кричевскпй. Сжатие и поиск информации. М.: Радио и связь. 1989.
10 Б.М.Фитингоф. Сжатие дискретной информации.// Проблемы передачи информации,- 1967.- Т.З, №3,
с.28-36.
11 Р.Галлагер. Теория информации и надежная связь. М.: Наука, 1974.
п Davisson L. Universal Noiseless Coding.// IEEE Trans. Inf. Th,- 1973.- Vol.19, №6- P.783-795. " Cover T.M. Enumerative Source Encoding.// ГЕЕЕ Trans. Inf. Th.-1973.- VoU9, №1.-P.73-77. "Elias P. Minima* Optimal Universal Codeword Sets.// IEEE Тгап5.-1983.-Уо1.Я-29. №4.-P.491- 502.
Как правило, в результате сжатия уменьшается явная информационная избыточность. Недостижимость значением коэффициента сжатия своей нижней грани свидетельствует о том, что существует некий скрытый вид избыточности, который остался за пределами возможностей методов сжатия. Выявление явной и, в особенности, скрытой избыточности информации с целью приближения значения коэффициента сжатия к нижней грани, т.е. получение наибольшего эффекта сжатия, является сегодня актуальной задачей.
Несмотря на достижения в области методов сжатия и кодирования, существует ряд нерешенных проблем. Наряду с разработкой новых алгоритмов сжатия с высокими показателями, важным является построение модели источника информации и определение условий эффективного применения разрабатываемого метода сжатия.
Целью диссертационной работы является разработка нового эффективного метода сжатия информации, основанного на специальных преобразованиях исходного представления информации и на уменьшении скрытой избыточности применительно к системам импульсной регистрации. Для достижения поставленной цели в диссертационной работе необходимо решить следующие основные задачи:
провести анализ методов сжатия информации, полученной в результате работы систем импульсной регистрации;
разработать метод кодирования дискретной информации, генерирующий кодовые слова с неразделимой избыточной частью;
построить модель сжатия рассматриваемого источника информации, обеспечивающую более высокий показатель качества сжатия;
определить условия эффективного использования разработанного метода и возможные области его применения.
Научная новизна Разработан новый метод кодирования вероятностного источника информации определенной природы возникновения, представляющей собой данные работы системы импульсной регистрации.
15 Bell T.C. Better OPM/L Compression.// ШЕЕ Transactions of Communication. - 1986. - Vol.34.- Р.П76 -
1182.
" Witten Ian. H, Neal Radford M., Cleary John G. Arithmetic coding for data compression.// Communications of
the ACM. - 1987. - Vol.30. - N6.
17 Rissanen J., Langdon G. Arithmetic coding.// ШМ J. Res. Dev.-1979.- Vol.23, Лі>2.- P.149-162.
Отличительной чертой разработанного метода является положенная в его основу матрица определенной структуры в сочетании с оптимальным ранжированием по специально разработанному критерию. Разработанный метод позволяет осуществлять преобразование исходного представления рассматриваемой информации к виду с меньшей избыточностью, чем при использовании подходов статистического и словарного кодирования. Данный метод кодирования источника информации при относительной частоте появления регистрационного сигнала v, не принадлежащей интервалу (0.5-е, 0.5+е), где е=0.05 позволяет сокращать степень явной и скрытой избыточности. Зависимость коэффициента сжатия от v аппроксимирована квадратичной функций с точностью до 10"6. Метод дает более высокий показатель качества сжатия по сравнению со стандартными алгоритмами статистического и словарного кодирования. Дано математическое обоснование разработанного метода, приведены оценки его сложности, обоснован эффект сжатия. Доказана теоретическая возможность эффективного сжатия рассматриваемого источника информации без использования вспомогательной памяти. Наряду с получением высоких показателей сжатия доказаны такие свойства метода матрично-рангового кодирования, как возможность построения на его основе блоковых кодов со скоростью передачи информации, приближающейся к верхней границе Плоткина и обладающих способностью помехозащиты. Предложена альтернативная схема построения кода, генерируемого методом матрично-рангового кодировашія, которая может служить теоретическим обоснованием для проектирования устройств вычислительной техники с контролем выполняемых операций. Кроме того, одной из возможных областей применения построенного кода является генерация управляемых перестановок в скоростных блочных недетерминированных шифрах.
Практическая ценность. На основе разработанного метода кодирования информации создан комплекс программ, позволяющий эффективно сжимать данные, полученные в результате работы систем регистрации сигналов. Сфера применимости может включать сжатие регистрационной импульсной информации сбоев аппаратуры вычислительной техники, а также может использоваться для обработки данных систем связи. Разработан алгоритм эффективного применения предлагаемого метода для сжатия информации. Кроме того, предложенный алгоритм генерации блоковых кодов, имеющих
высокие показатели скорости передачи, а также обладающих способностью обнаруживать ошибки, может быть использован при создании систем помехоустойчивой передачи информации по параллельному несимметричному каналу связи. Разработанный метод матрично-рангового кодирования может являться теоретической основой для проектирования следующих устройств: устройства помехоустойчивой передачи информации по параллельному несимметричному каналу связи; помехоустойчивые суммирующие и вычитающие счетчики и сумматоры; устройства для реализации управляемых перестановок в аппаратно-ориентированных скоростных блочных недетерминированных шифрах.
Разработанные алгоритмы и программное обеспечение внедрены в практическую деятельность на ГУПНПО «Марс» (г. Ульяновск) и используются при проектировании изделия «Сангенит» в процессе обработки информации, являющейся результатом работы системы регистрации сбоев аппаратуры вычислительной техники, а также нашли применение при разработке курса «Теория информации» в УлГУ и «Сети и телекоммуникации» в УлГТУ. Имеется документальное подтверждение о внедрении.
На защиту выносятся:
-
Метод матрично-рангового кодирования дискретной информации.
-
Алгоритм сжатия потока регистрационной информации, который позволяет достичь более высокого показателя качества сжатия по сравнению с рассматриваемыми стандартными алгоритмами статистического и словарного кодирования.
-
Применение метода матрично-рангового кодирования для проектирования устройств вычислительной техники, в частности, разработаны следующие алгоритмы:
алгоритм помехоустойчивой передачи информации по параллельному несимметричному каналу связи;
алгоритм работы помехоустойчивого суммирующего счетчика, вычитающего счетчика, сумматора;
алгоритм генерации управляемой перестановки в агшаратно-ориентированном скоростном блочном недетерминированном шифре.
Апробация работы Результаты диссертационной работы докладывались и обсуждались на следующих семинарах и конференциях:
29-я молодежная конференция «Проблемы теоретической и прикладной математики» (Екатеринбург, 1998);
6-я Санкт-Петербургская международная конференция «Региональная информатика-98» (Санкт-Петербург, 1998);
Всероссийская научно-практическая конференция «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, 1998);
2-я Всероссийская научно-техническая конференция «Информационные технологии в электротехнике и электроэнергетике» (Чебоксары, 1998);
3-я Всероссийская научно-техническая конференция «Методы и средства измерения физических величин» (Нижний Новгород, 1998);
Международная конференция по мягким вычислениям и измерениям (Санкт-Петербург, 1998);
научные семинары механико-математического факультета Ульяновского государственного университета (г. Ульяновск, 1998, 1999);
Структура и объем работы По теме диссертации опубликовано 9 работ. Диссертация состоит из введения, четырех глав, заключения, приложения и списка литературы из 97 наименований источников. Общий объем диссертации составляет 145 страниц.