автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Метод матрично-рангового кодирования и его применение

• 'Л

На правах рукописи

Терентьева Юлия Юрьевна

МЕТОД МАТРИЧНО-РАНГОВОГО КОДИРОВАНИЯ И ЕГО ПРИМЕНЕНИЕ

05.13.18 - теоретические основы математического моделирования, численные методы и комплексы программ

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Ульяновск, 2000

Работа выполнена в Ульяновском государственном университете

Научный руководитель доктор технических наук,

профессор А.А.Смагин

Официальные оппоненты доктор технических наук,

профессор В.А.Песошин; кандидат технических наук, доцент О.А.Тихонов

Ведущая организация

НПО «Марс» /г. Ульяновск/

Защита состоится 28 февраля 2000 г. в 14.00 на заседании диссертационного совета К 053.37.06 по защите кандидатских диссертаций в Ульяновском государственном университете (432700, г.Ульяновск, ул. Набережная реки Свияги, 40, ауд. 703).

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета.

Автореферат разослан « гч » _ 2000 г. Отзывы на

автореферат просим присылать по адресу: 432700, г.Ульяновск, ул. Л.Толстого, 42, УлГУ, научная часть.

Ученый секретарь диссертационного совета

к.ф.-м.н.

Е.П.Чирко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В системах импульсной регистрации сигналов, например, в телефонии или в непрерывных технологических процессах, создаются большие потоки информации, которые необходимо хранить определенное время.1,2'3 Хранение таких массивов информации затрудняется вследствие ограниченности объема памяти современных компьютеров. Отличительной чертой рассматриваемых источников информации является отсутствие в них с высокой вероятностью явной избыточности. Поскольку известные и эффективные методы сжатия, базирующиеся на статистических и словарных подходах, как правило, уменьшают явную избыточность4,5,6"7,8, то 01га не дают достаточного эффекта сжатия информации, полученной в результате работы систем импульсной регистрации, и стимулируют разработку и исследование новых методов сжатия рассматриваемой информации.

Известно, что предварительное сжатие позволяет существенно улучшить характеристики системы связи.9 В зависимости от различных типов источников информации разработано множество методов кодирования. Здесь следует отметить работы Д. Хаффмена3, К. Шеннона4, Р. Фано5, Б. Фитингофа10, Р. Кричевского8, Р. Гаплагера11, Л. Дэвисона12, Т. Ковера13, П. Элайеса14, А. Лемпелла, Д. Зива6,7, Т. Белла15, Я. Витгена16, Д. Риссанена17 и др.

1 Н.А.Куцевич. Программное обеспечение систем контроля и управления и Windows-технологии.// Мир компьютерной автоматизации. 1999, А'гЗ. С.9-17.

2 Т.Зеленова. Принципы построения современных телефонных систем.// Мир компьютерной автоматизации.

1998, №3.-0.7-12.

3 А.ПКулаичев. Компьютерный контроль процессов и анализ сигналов.- М.:Информатика и компьютеры,

1999,- 330с.

4 Д.А.Хаффмен. Метод построения кодов с минимальной избыточностью.// Кибернетический сборник. -1963, вып.З.

5 КШеннон. Работы по теории информации и кибернетике. М.: ИЛ., 1963,- 828с.

6 Р.Фано. Передача информации. Статистическая теория связи. М.: Наука, 1965.

7 Ziv J., Lempel A. An Universal Algorithm for Sequental Data Compression.// ШЕЕ Transactions oflnformation 1 Theory. - 1977,- Vol.23.- №3. i

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.

13 Cover T.M. Enumerative Source Encoding.// IEEE Trans. Inf. Th.- 1973,- Vol.19, №1.-P.73-77.

"Elias P. Minima* Optimal Universal Codeword Sets.// IEEE Тгап5.-1983.-Уо1.Я-29. №4.-P.491- 502.

Как правило, в результате сжатия уменьшается явная информационная избыточность. Недостижимость значением коэффициента сжатия своей нижней грани свидетельствует о том, что существует некий скрытый вид избыточности, который остался за пределами возможностей методов сжатия. Выявление явной и, в особенности, скрытой избыточности информации с целью приближения значения коэффициента сжатия к нижней грани, т.е. получение наибольшего эффекта сжатия, является сегодня актуальной задачей.

Несмотря на достижения в области методов сжатия и кодирования, существует ряд нерешенных проблем. Наряду с разработкой новых алгоритмов сжатия с высокими показателями, важным является построение модели источника информации и определение условий эффективного применения разрабатываемого метода сжатия.

Целью диссертационной работы является разработка нового эффективного метода сжатия информации, основанного на специальных преобразованиях исходного представления информации и на уменьшении скрытой избыточности применительно к системам импульсной регистрации. Для достижения поставленной цели в диссертационной работе необходимо решить следующие основные задачи:

• провести анализ методов сжатия информации, полученной в результате работы систем импульсной регистрации;

• разработать метод кодирования дискретной информации, генерирующий кодовые слова с неразделимой избыточной частью;

• построить модель сжатия рассматриваемого источника информации, обеспечивающую более высокий показатель качества сжатия;

• определить условия эффективного использования разработанного метода и возможные области его применения.

Научная новизна Разработан новый метод кодирования вероятностного источника информации определенной природы возникновения, представляющей собой данные работы системы импульсной регистрации.

15 Bell т.е. Bcttcr OPM/L Compression.// ШЕЕ Transactions of Communication. - 1986. - Vol.34.- P.1176 -1182.

16 Witten Ian. H, Neal Radford M., Cleary John G. Arithmetic coding for data compression.// Communications of the ACM. - 1987. - Vol.30. - N6.

" Rissanen J., Langdon G. Arithmetic coding.// IBM J. Res. Dev.- 1979,- Vol.23, Xs2.- P.149-162.

Отличительной чертой разработанного метода является положенная в его основу матрица определенной структуры в сочетании с оптимальным ранжированием по специально разработанному критерию. Разработанный метод позволяет осуществлять преобразование исходного представления рассматриваемой информации к виду с меньшей избыточностью, чем при использовании подходов статистического и словарного кодирования. Данный метод кодирования источника информации при относительной частоте появления регистрационного сигнала V, не принадлежащей интервалу (0.5-е, 0.5+е), где <2=0.05 позволяет сокращать степень явной и скрытой избыточности. Зависимость коэффициента сжатия от V аппроксимирована квадратичной функций с точностью до 10"6. Метод дает более высокий показатель качества сжатия по сравнению со стандартными алгоритмами статистического и словарного кодирования. Дано математическое обоснование разработанного метода, приведены оценки его сложности, обоснован эффект сжатия. Доказана теоретическая возможность эффективного сжатия рассматриваемого источника информации без использования вспомогательной памяти. Наряду с получением высоких показателей сжатия доказаны такие свойства метода матрично-рангового кодирования, как возможность построения на его основе блоковых кодов со скоростью передачи информации, приближающейся к верхней границе Плоткина и обладающих способностью помехозащиты. Предложена альтернативная схема построения кода, генерируемого методом матрично-рангового кодировашгя, которая может служить теоретическим обоснованием для проектирования устройств вычислительной техники с контролем выполняемых операций. Кроме того, одной из возможных областей применения построенного кода является генерация управляемых перестановок в скоростных блочных недетерминированных шифрах.

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

высокие показатели скорости передачи, а также обладающих способностью обнаруживать ошибки, может быть использован при создании систем помехоустойчивой передачи информации по параллельному несимметричному каналу связи. Разработанный метод матрично-рангового кодирования может являться теоретической основой для проектирования следующих устройств: устройства помехоустойчивой передачи информации по параллельному несимметричному каналу связи; помехоустойчивые суммирующие и вычитающие счетчики и сумматоры; устройства для реализации управляемых перестановок в аппаратно-ориентированных скоростных блочных недетерминированных шифрах.

Разработанные алгоритмы и программное обеспечение внедрены в практическую деятельность на ГУПНПО «Марс» (г. Ульяновск) и используются при проектировании изделия «Сангенит» в процессе обработки информации, являющейся результатом работы системы регистрации сбоев аппаратуры вычислительной техники, а также нашли применение при разработке курса «Теория информации» в УлГУ и «Сети и телекоммуникации» в УлГТУ. Имеется документальное подтверждение о внедрении.

На защиту выносятся:

1. Метод матрично-рангового кодирования дискретной информации.

2. Алгоритм сжатия потока регистрационной информации, который позволяет достичь более высокого показателя качества сжатия по сравнению с рассматриваемыми стандартными алгоритмами статистического и словарного кодирования.

3. Применение метода матрично-рангового кодирования для проектирования устройств вычислительной техники, в частности, разработаны следующие алгоритмы:

• алгоритм помехоустойчивой передачи информации по параллельному несимметричному каналу связи;

• алгоритм работы помехоустойчивого суммирующего счетчика, вычитающего счетчика, сумматора;

• алгоритм генерации управляемой перестановки в апларатно-ориентированном скоростном блочном недетерминированном шифре.

Апробация работы Результаты диссертационной работы докладывались и обсуждались на следующих семинарах и конференциях:

• 29-я молодежная конференция «Проблемы теоретической и прикладной математики» (Екатеринбург, 1998);

• 6-я Санкт-Петербургская международная конференция «Региональная информатика-98» (Санкт-Петербург, 1998);

• Всероссийская научно-практическая конференция «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, 1998);

• 2-я Всероссийская научно-техническая конференция «Информационные технологии в электротехнике и электроэнергетике» (Чебоксары, 1998);

• 3-я Всероссийская научно-техническая конференция «Методы и средства измерения физических величин» (Нижний Новгород, 1998);

• Международная конференция по мягким вычислениям и измерениям (Санкт-Петербург, 1998);

• научные семинары механико-математического факультета Ульяновского государственного университета (г. Ульяновск, 1998, 1999);

Структура и объем работы По теме диссертации опубликовано 9 работ. Диссертация состоит из введения, четырех глав, заключения, приложения и списка литературы из 97 наименований источников. Общий объем диссертации составляет 145 страниц.

СОДЕРЖАНИЕ РАБОТЫ

Введение содержит обоснование актуальности темы диссертации. Формулируются цель и задачи исследования, научная новизна и практическое значение, перечислены положения, выносимые на защиту, приведена структура диссертации.

Первая глава является постановочной и содержит элементы обзора и классификации методов сжатия. Рассмотрены основные подходы к решению проблемы сжатия информации. Проведен анализ избыточности источников информации, а также избыточности кодов, используемых для их

кодирования. Полученные результаты анализа рассматриваемого источника информации позволяют сделать вывод о том, что при разбиении исходной последовательности на блоки длиной 16 и выше с вероятностью не менее 0.99 можно судить об отсутствии преобладания каких-либо блоков, отличных от тривиальных. Поэтому к данному источнику информации применение методов статистического и словарного кодирования, которые в разных модификациях используются в упоминаемых алгоритмах сжатия, может оказаться не самым эффективным. Таким образом, существующая проблема стимулирует разработку метода сжатия специальной двоичной последовательности, полученной в результате работы системы импульсной регистрации.

Вторая глава посвящена разработке теоретических основ создаваемого метода. Построен алгоритм кодирования. Введено определение (2.1) ближайшего предшествования для двух кодовых слов, доказана теорема о ближайшем предшествовании (2.1), являющаяся инструментом для проведения доказательств свойств метода матрично-рангового кодирования и теоретическим обоснованием для ряда создаваемых алгоритмов, на базе которых возможно проектирование устройств вычислительной техники, а также шифрующих устройств.

Определение2.1. Код а = (al,a2,...ari), a, e|0,lj, / = 1,2,..,и, является ближайшим предшествованием коду b =(b},b2,...bn), bi е{0,l},i = 1,2, если выполняются следующие условия:

\) существует номер k ( 1 <к<п) такой, что ak<bk, и не существует номера m (i<m<k) такого, что ат>Ът. Определенное отношение предшествования обозначим а <Ь . 2)не существует кода с = (срс^.с,,), где с, e{o,l}, такого, что а<с и с <Ь. Отношение ближайшего предшествования обозначим а =>Ъ .

п п

Теорема 2.1 .Два кода а и b таких, что ^а, = , связаны отношением

ы /=1

ближайшего предшествования а =>Ь тогда и только тогда, когда выполняется равенство

Доказана теорема 2.2 о биективности преобразования, обосновывающая корректное проведение операций кодирования \ декодирования.

Теорема 2.2. Пусть 1,2,.., 2}, Б2{п, г) - множество двоичных слов

длины п, каждое из которых содержит ровно г ненулевых компонент. Операция декодирования у/1 метода матрично-рангового кодирования задает биективное отображение множества кодов г) во множество

Дано матричное описание разработанного метода, оценка его сложности, согласно которой метод кодирования имеет неэкспоненциальную трудоемкость (сложность представляет собой степенную функцию длины блока при различных основных способах реализации алгоритма). Трудоемкость кодирования и декодирования оценивается парой чисел (у„, г„), где уп - число двоичных ячеек памяти, которое содержит кодирующее (декодирующее) устройство, 2„ - число операций сложения п - разрядных чисел, необходимое для реализации алгоритма кодирования (декодирования) кодового слова длины п. Рассмотрены три основных способа реализации алгоритма:

1) Кодирующая матрица хранится в памяти кодирующего (декодирующего) устройства.

2) Элементы таблицы вычисляются по мере необходимости с помощью рекуррентных соотношений.

3) Кодирование (декодирование) выполняется непосредственно без привлечения матрицы.

Для указанных случаев найдены оценки сложности алгоритма в следующей теореме (2.3).

Теорема 2.3. Для трудоемкости кодирования (декодирования) (Н - ранг кодового слова, Я<п) при п —>сс имеют место асимптотические оценки:

1) у„ ~ п2Я, 2„ ~ Я; (2)

2) у„ ~ пЯ, гп ~ пЯ/1; (3)

3) уп~п, гп~ 2пК2; (4)

Выявлено и доказано свойство, характеризующее избыточность кодов метода матрично-рангового кодирования, в следующем утверждении:

Утверждение 2.1. Пусть с =(с,с2...е„) представляет собой некоторый

п

двоичный код, \\1'\с), Л72 = ]Гб;2"~'. Тогда при и —»со справедлива следующая асимптотическая оценка.

тах7Г ~ \ (5)

N п н> ю I да

В качестве критерия оптимальности, обеспечивающего минимальную среднюю длину кодовых слов для кодируемых чисел из установленного диапазона, выбраны следующие условия:

Кор№) = агЕтаХ/2(Я)

я

/2(Я) = 2/(Д= а^тш !(«,*))

¡=0 *

(6)

Задача выбора оптимального ранга решается в п.2.3. Доказывается ряд утверждений относительно свойств длины кодовых слов, генерируемых методом матрично-рангового кодирования. В следующем утверждении (2.2) доказывается свойство монотонного неубывания длины кодовых слов от кодируемого числа при фиксированном ранге. На рисунках 1 и 2 приводится графическая интерпретация функции длины кодового слова К) в зависимости от двух параметров - кодируемого числа и ранга.

Утверждение2.2. ЦК К)<Щ+1, К). (7)

При фиксированном значении кодируемого числа определяется функция: gы^R) = ЦN,R). Обозначим £'(ЛГ) = пуп(К). Пусть Ь-некоторая длина кода

(т.е. произвольное значение ЦЛ^й)). Неявным образом определяется функция .

= Л +1

Рис. 1. График функции длины тп?. Ь(И,К).

В рамках введенных обозначений доказаны свойства кодов разрабатываемого метода в следующих утверждениях:

Утверждение 2.3. ИЬ(Я) = . Утверждение 2.4. аг^тт^ДЛ) = Утверждение 2.5. И , (2) < Я , (7. + 1)

ш

(9) (10) (П)

На основе доказанных свойств строится алгоритм нахождения оптимального ранга для заданного множества 5,(7) при определенном критерии оптимальности (6). В утверждении 2.6 получена асимптотическая оценка избыточности г(Лг), определяемая следующим образом:

г(Л0 = |(Л0-^2(ЛГ + 1)]. (12)

Утверждение 2.6. При неограниченном увеличении N имеет место следующая оценка

г{И) = 0(1пЛГ). (13)

Рис. 2. Функции длины кода Ь(ЫД) в виде гистограммы.

В третьей главе проведено построение алгоритма сжатия рассматриваемого источника информации. Доказана возможность получения эффекта сжатия, зависящего от энтропии рассматриваемого источника информации, в следующей теореме.

Теорема 3.1. Ит- = Щр), (14)

я-»»

где п - длина исходной последовательности, п- средняя длина последовательности, полученной в результате преобразований на основе

т

метода матрично-рангового кодирования, Н(р) = -^р,1о%1р,- энтропия

/-1

источника (т= 2).

На рис.3 приводится график зависимости предельного значения коэффициента сжатия |д от относительной частоты единицы V.

Показана основанная на доказанной теореме о ближайшем предшествовании (2.1) возможность реализации алгоритма сжатия без привлечения дополнительной памяти (со значительным увеличением объема затрачиваемых временных ресурсов).

Рис. 3. График зависимости предельного значения коэффициента сжатия ц от отноаггельной частоты единицы V.

Проведены необходимые эксперименты реализации разработанного

алгоритма сжатия источников, порождаемых системами импульсной

регистрации. Графическая интерпретация результатов экспериментов

представлена на рис.4 и рис.5 графиками зависимости коэффициента сжатия

п Я

ц = — от относительной частоты появления сигнала V = —. п п

О 0.1 0 2 0.3 0.4 0.5

Рис. 4. Зависимость коэффициента сжатия ц от относительной частоты единицы V при использовании различных методов словарного и статистического кодирования для рассматриваемых источников информации.

Рис. 5. Зависимость коэффициента сжатия р. от относительной частоты единицы v при использовании различных методов словарного и статистического кодирования и метода простой нумерации позиций для рассматриваемых источников информации.

Имеют место следующие обозначения: 1- сжатие с использованием метода матрично-рангового кодирования; 2-AIN(1996), 3-LHA(1992), 4-ARJ (1997), 5- RAR (1998), 6- PKZIP (1998), 7- YAC (1995), 8- ICOMP (1995), 9- метод простой нумерации позиций. Разработанный метод кодирования источника при относительной частоте появления регистрационного сигнала V, не принадлежащей интервалу (0.5-е, 0.5+е), где е=0.05 позволяет сокращать степень явной и скрытой избыточности. Значение коэффициента сжатия свидетельствует о более эффективном применении разработанного метода сжатия по сравнению со стандартными алгоритмами статистического и словарного кодирования для рассматриваемых источников информации. Проведена аппроксимация методом наименьших квадратов: точностью до 10"6 коэффициент сжатия ц квадратично зависит от v. В таблице 1 приведены экспериментальные данные по коэффициенту сжатия при обработке данных систем импульсной регистрации разработанным методом сжатия и стандартными алгоритмами, в таблице 2 - временные затраты, в таблице 3 - изменение избыточности рассматриваемого источника сообщений в результате сжатия.

V МНП АШ (1996) АКТ (1997) 1СОМР (1995) ША (1992) ркгш (1998) 1Ш1 (1998) УАС (1995) ММРК

0.01 0.118 0.231 0.251 0.482 0.182 0.264 0.226 0.290 0.083

0.02 0.234 0.312 0.336 0.579 0.271 0.352 0.323 0.401 0.143

0.03 0.326 0.368 0.387 0.634 0.320 0.405 0.374 0.445 0.185

0.04 0.493 0.453 0.478 0.739 0.412 0.489 0.461 0.546 0.253

0.05 0.606 0.496 0.518 0.778 0.453 0.535 0.498 0.589 0.291

0.06 0.756 0.547 0.571 0.869 0.503 0.586 0.564 0.649 0.339

0.07 0.824 0.584 0.605 0.898 0.530 0.622 0.598 0.671 0.365

0.08 0.920 0.604 0.624 0.920 0.557 0.640 0.615 0.704 0.393

0.09 1.133 0.668 0.691 1.002 0.625 0.709 0.685 0.769 0.454

0.10 1.249 0.698 0.721 1.050 0.655 0.736 0.724 0.799 0.484

0.11 1.428 0.732 0.758 1.098 0.691 0.770 0.763 0.837 0.529

0.12 1.434 0.734 0.759 1.103 0.692 0.775 0.767 0.844 0.532

0.13 1.474 0.742 0.763 1.108 0.697 0.788 0.777 0.850 0.540

0.15 1.818 0.803 0.824 1.210 0.758 0.843 0.849 0.915 0.616

0.17 2.010 0.846 0.863 1.247 0.797 0.880 0.876 0.940 0.654

0.20 2.379 0.896 0.914 1.320 0.848 0.931 0.928 0.991 0.722

0.23 2.817 0.945 0.968 1.365 0.910 0.990 0.970 1.034 0.790

0.25 3.016 0.977 0.998 1.392 0.932 1.017 0.983 1.050 0.815

0.27 3.215 0.995 1.018 1.414 0.952 1.034 0.996 1.062 0.840

0.30 3.692 1.048 1.070 1.428 1.004 1.082 1.040 1.110 0.894

0.33 4.012 1.073 1.094 1.436 1.028 1.111 1.072 1.126 0.922

0.35 4.154 1.086 1.103 1.439 1.033 1.116 1.078 1.143 0.934

0.39 4.526 1.110 1.103 1.445 1.037 1.116 1.096 1.171 0.959

0.40 4.691 1.112 1.103 1.445 1.037 1.116 1.098 1.173 0.969

0.43 4.917 1.123 1.103 1.446 1.037 1.116 1.112 1.182 0.984

0.45 5.287 1.126 1.103 1.446 1.037 1.116 1.115 1.184 0.993

0.49 5.864 1.130 1.103 1.446 1.037 1.116 1.121 1.190 1.001

0.50 6.033 1.131 1.103 1.446 1.037 1.116 1.123 1.190 1.002

Таблица 1. Результаты проведения экспериментов. В первой графе относительная частота появления сигнала V. Таблица содержит значения коэффициентов сжатия ц при использовании указанных методов. МНП - метод нумерации позиций, ММРК - алгоритм сжатия на основе метода матрично-рангового кодирования..

V МИЛ ММРК RAR PKZIP LHA YAC АШ

0.01 2-10'2 7-10'1 2-10' 3-1 о2 5-101 4.610 5-Ю"2

0.1 5-Ю"' 1.3 1.1 1.3 1.4 4.8-10 1.8

0.2 6.8 5.1 2.1 3.5 2.2 5.0-10 3.7

0.3 3.7-10 8.2 3.5 4.3 3.7 5.110 4.4

0.4 5.3-10 1.35-103 3.7 4.7 4.1 6.310 4.7

0.5 1.03-102 2.47-103 4.3 5.1 4.5 6.3-10 5.9

Таблица 2. Время сжатия (в секундах). Эксперименты проводились на Pentium ММХ 233 МГц 32 Мб ОП, ОС Windows 98, объем - 100Кбайт.

V Избыточ. AIN ARJ LHA RAR PKZIP МНП. ММРК

0,01 0,83139 0,02791 0,09172 0,02559 0,06346 0,11945 0,02456 0,01769

0,05 0,57926 0,03344 0,09945 0,02965 0,04566 0,06456 0,02967 0,01999

0,1 0,38843 0,05654 0,04148 0,02776 0,02730 0,06948 0,13755 0,02414

0,15 0,28793 0,08564 0,08567 0,08678 0,07567 0,07566 0,13844 0,05425

0,2 0,20435 0,09524 0,09777 0,09078 0,09642 0,08442 0,14234 0,07436

0,25 0,13778 0,10056 0,10547 0,11677 0,13221 0,14566 0,14234 0,08768

0,3 0,09852 0,09456 0,09078 0,09678 0,09566 0,13455 0,15234 0,06567

0,35 0,06689 0,06345 0,06345 0,05678 0,05789 0,56777 0,15655 0,04577

0,4 0,04163 0,03179 0,03435 0,03674 0,03567 0,03156 0,15434 0,02345

0,45 0,02480 0,02107 0,02178 0,02076 0,02007 0,02127 0,27345 0,01967

0,5 0,02299 0,01798 0,03208 0,02318 0,02395 0,03736 0,29233 0,01589

Таблица 3. Изменение избыточности источника после применения методов сжатия. Во второй графе таблицы приведены начальные данные избыточное™ сжимаемой информации.

Четвертая глава посвящена рассмотрению возможностей дополнительного использования разработанного метода матрично-рангового кодирования. Областями применения данного метода могут являться системы связи, функционирующие в режиме помехоустойчивой передачи информации, новые варианты реализации элементарных операций, обладающие помехозащищенностью. В частности, разработано устройство вычислительной техники - суммирующий счетчик с контролем. Показана возможность разработки вычитающих счетчика с контролем, а также

сумматоров с контролем. Другой областью применения являются криптографические преобразования, к числу которых относятся управляемые перестановки для аппаратно-ориентированных скоростных блочных недетерминированных шифров.

В п.4.1 проводится разработка блоковых кодов на основе метода матрично-рангового кодирования, дается оценка скорости кода, доказывается ее асимптотическое приближение к верхней границе Плоткина. На рис.6 представлены графики зависимостей скоростей кодов от длины кодовых слов.

И 1

- /

■/

}

!

во [-

а

Рис. б. А - верхняя граница Плоткина для скоростей передачи информации, В - график скорости передачи кода, построенного на основе метода матрично-рангового кодирования.

Доказано свойство помехоустойчивости кодов, генерируемых методом матрично-рангового кодирования:

Утверждение 4.1. Двоичные коды неотрицательных десятичных целых чисел, полученные методом матрично-рангового кодирования, позволяют обнаружить по меньшей мере одну ошибку.

Построенные блоковые коды используются при моделировании процесса передачи информации в условиях несимметричного параллельного канала связи, обеспечивающего сохранение достоверности в режиме адаптивного кодирования. Данная модель предусматривает возможность не только

обнаружения, но и исправления ошибок, возникающих при передаче по зашумленному параллельному несимметричному каналу связи. Показывается преимущество построенных кодов перед кодами с той же избыточностью, обусловленной минимальным хэмминговым расстоянием между кодовыми словами, при наличии рассматриваемого канала связи.

Одним из возможных применений метода матрично-рангового кодирования является построение математической модели помехоустойчивого счетчика, позволяющего производить необходимые действия с одновременным обнаружением и, при небольшой модификации модели, исправлением ошибок. Разработаны обоснованные доказанной теоремой (2.1) о ближайшем предшествовании и доказанным свойством помехозащищенности алгоритмы работы помехоустойчивого суммирующего и вычитающего счетчика. Приведена оценка сложности работы счетчика, обусловленная средним количеством операций бинарного сравнения. Согласно доказанному утверждению, сложность определяется возрастающей функцией двух переменных - длины и ранга кодового слова, являющегося показателем значения счетчика. Построена схема аппаратной реализации суммирующего счетчика с контролем, на которую получено положительное решение по заявке на патент РФ.

Другим возможным приложением предложенного метода кодирования дискретных данных являются разработанная процедура реализации криптографического примитива. Доказанные свойства метода матрично-рангового кодирования явились предпосылкой для разработки элементов криптографических преобразований (п.4.6). Построена схема формирования управляемой перестановки для аппарагно-ориентированного скоростного блочного недетерминировашюго шифра.

В заключении перечислены основные результаты диссертационной работы и области их применения.

В приложении содержатся таблицы - результаты экспериментов, сравнительные таблицы, графики, иллюстрирующие исследуемые зависимости, а также схема разработанного устройства вычислительной техники - суммирующего счетчика с ко1гтролем выполняемых операций.

Основные результаты и выводы. Основные научные положения и результаты, сформулированные, обоснованные и полученные в настоящей работе, заключаются в следующем:

1. Разработан и математически обоснован метод матрично-рангового кодирования дискретной информации, имеющей определенную природу возникновения, которая представляет собой данные системы импульсной регистрации. Получена оценка сложности алгоритма кодирования / декодирования, являющаяся степенной функцией длины кодируемого сообщения. Избыточность кода имеет логарифмический порядок роста относительно кодируемого числа. Доказаны свойства длины кода при условии варьирования значением кодируемого числа и рангом. Введен критерий оптимальности ранга и исследованы его свойства.

2. На основе метода матрично-рангового кодирования разработан алгоритм сжатия информации, генерируемой системой импульсной регистрации. Доказана возможность получения эффекта сжатия при определегашх условиях. Доказана теоретическая возможность эффективного сжатия рассматриваемой информации без использования вспомогательной памяти.

3. Проведено моделирование процесса сжатия информации от источника, порождаемого системой импульсной регистрации. При относительной частоте появления регистрационного сигнала V, не принадлежащей интервалу (0.5-е, 0.5+е), где е=0.05, разработанный метод позволяет сокращать степень явной и скрытой избыточности. Зависимость коэффициента сжатия от V аппроксимирована квадратичной функций с точностью до 10"6. Проведенное сравнение использования алгоритмов сжатия, основанных на статистических и словарных подходах, показало, что разработанный метод дает более высокий показатель качества сжатия применительно к рассматриваемым источникам.

4. Доказана возможность построения на основе метода матрично-рангового

кодирования блоковых кодов со скоростью передачи информации,

приближающейся к верхней границе Плоткина и обладающих способностью помехозащиты. Разработана схема альтернативного построения кода методом матрично-рангового кодирования, которая может

служить теоретическим обоснованием для разработки устройств вычислительной техники с контролем выполняемых операций, а также устройств шифрования. Проведено моделирование и разработана схема устройства суммирующего счетчика с контролем, на которую получено положительное решение по заявке на патент РФ. Предложен новый способ генерации управляемых перестановок в скоростных блочных недетерминированных шифрах.

Основные результаты работы изложены в следующих

публикациях:

1. Смагин А.А., Тергнтъева Ю.Ю. Способ преобразования дискретной информации// Фундаментальные проблемы математики и механики: Ученые записки УлГУ. Вып.1. Часть 2. Ульяновск: УлГУ, 1996. С.101-108.

2. Терентъева Ю.Ю. О возможностях метода матрично-рангового кодирования// Тезисы 29-й молодежной конференции «Проблемы теоретической и прикладной математики». Екатеринбург, 1998. С.75-76.

3. Терентъева Ю.Ю. Об одном методе кодирования дискретной информации // Тезисы 2-й Всероссийской научно-технической конференции «Информационные технологии в электротехнике и электроэнергетике». Чебоксары, 1998. С.213-215.

4. Терентъева Ю.Ю. О некоторых областях применения метода матрично-рангового кодирования // Тезисы Международной конференции по мягким вычислениям и измерениям. Санкт-Петербург, 1998, том 1. С.180-181.

5. Терентъева Ю.Ю. Об одном способе криптографической защиты текста// Тезисы 6-й Санкт-Петербургской международной конференции «Региональная информатика-98». Санкт-Петербург, 1998. С.131.

6. Терентъева Ю.Ю. Диагностирование канала связи при одновременной передаче дискретных данных // Тезисы Всероссийской научно-

го

практической конференции «Современные проблемы создания и эксплуатации радиотехнических систем». Ульяновск, 1998. С.88-89.

7. Тереитъева Ю.Ю., Шубович ВТ. Преобразование измерительной информации для хранения и передачи ее по каналу связи// Тезисы 3-й Всероссийской научно-технической конференции «Методы и средства измерения физических величин». Нижний Новгород, 1998, часть 8. С.6.

8. Терентьева 10.10., Смагин А.А., Шубович В.Г. Метод универсального кодирования бинарных последовательностей. Деп. в Центр, справочн. информ. фонде Министерства обороны РФ, Москва, 1999. Серия Б. Выпуск 48. 22с.

9. Положительное решение по заявке на изобретение: Смагин А.А., Терентьева Ю.Ю. Суммирующий счетчик постоянного веса. №99110954/ 09(011670), приоритет 26.05.99.

ВВЕДЕНИЕ

ГЛАВА

Избыточность и основные принципы ее минимизации

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]. Сжатие информации - проблема, имеющая достаточно давнюю историю, гораздо более давнюю, нежели история развития вычислительной техники, которая обычно шла параллельно с историей развития проблемы кодирования и шифрования информации. В зависимости от различных типов источников разработано множество методов кодирования. Здесь следует отметить работы Д. Хаффмена, К. Шеннона, Р. Фано, Б. Фитингофа, Ю. Штарькова, Р. Кричевского, Р. Галлагера, Л. Дэвисона, Т. Ковера, П. Элайеса, А. Лемпелла, Д. Зива, Т. Белла, Я. Виттена, Д. Риссанена и др [2-14].

Актуальность проблемы сжатия имеет место также в связи с увеличением объемов передаваемой и хранимой информации. Подобная задача возникает достаточно часто. В системах импульсной регистрации сигналов, например, в телефонии или в непрерывных технологических процессах, создаются большие потоки информации, которые необходимо хранить определенное время [15-17]. Хранение таких массивов информации затрудняется вследствие ограниченности объема памяти современных компьютеров. Отличительной чертой рассматриваемых источников информации является отсутствие в них явной избыточности с высокой долей вероятности. Поэтому использование наиболее известных и эффективных методов сжатия, базирующихся на статистических и словарных подходах, не дают достаточного эффекта сжатия и стимулируют разработку и исследование новых методов сжатия рассматриваемой информации.

Как правило, в результате сжатия уменьшается явная информационная избыточность. Недостижимость значением коэффициента сжатия своей нижней грани свидетельствует о том, что существует некий скрытый вид избыточности, который остался за пределами возможностей методов сжатия. Выявление явной и, в особенности, скрытой избыточности информации с целью приближения значения коэффициента сжатия к нижней грани, т.е. получение наибольшего эффекта сжатия, является сегодня актуальной задачей.

Несмотря на достижения в области методов сжатия и кодирования, существует ряд нерешенных проблем. Наряду с разработкой новых алгоритмов сжатия с высокими показателями, важным является построение модели источника информации и определение условий эффективного применения разрабатываемых и существующих методов сжатия.

Целью диссертационной работы является разработка нового эффективного метода сжатия информации, основанного на специальных преобразованиях исходного представления информации и на уменьшении скрытой избыточности применительно к системам импульсной регистрации. Для достижения поставленной цели необходимо провести анализ методов сжатия информации, полученной в результате работы систем импульсной регистрации; разработать метод кодирования дискретной информации, генерирующий кодовые слова с неразделимой избыточной частью; построить модель сжатия рассматриваемого источника информации, обеспечивающую более высокий показатель качества сжатия; определить условия эффективного использования разработанного метода и возможные области его применимости.

Научная новизна диссертационной работы определяется следующими факторами. Разработан новый метод кодирования вероятностного источника информации, представляющей собой данные работы системы импульсной регистрации. Отличительной чертой разработанного метода является положенная в его основу матрица определенной структуры в сочетании с оптимальным ранжированием по специально разработанному критерию.

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

Практическая ценность работы определяется тем, что на основе разработанного метода кодирования информации создан комплекс программ, позволяющий эффективно сжимать данные, полученные в результате работы систем регистрации сигналов. Сфера применимости может включать сжатие регистрационной импульсной информации сбоев аппаратуры вычислительной техники, а также может использоваться для обработки данных систем связи. Разработана методика эффективного применения предлагаемого метода для сжатия информации. Кроме того, предложенный алгоритм генерации блоковых кодов, имеющих высокие показатели скорости передачи, а также обладающих способностью обнаруживать ошибки, может быть использован при создании систем помехоустойчивой передачи информации по параллельному несимметричному каналу связи. Разработанный метод матрично-рангового кодирования может являться также теоретической основой при проектировании следующих устройств: устройства помехоустойчивой передачи информации по параллельному несимметричному каналу связи; помехоустойчивые суммирующие и вычитающие счетчики и сумматоры; устройства для реализации управляемых перестановок в аппаратно-ориентированных скоростных блочных недетерминированных шифрах.

Разработанные алгоритмы и программное обеспечение внедрены в практическую деятельность на ГУПНПО «Марс» г. Ульяновска и используются при проектировании изделия «Сангенит» в процессе обработки информации, являющейся результатом работы системы регистрации сбоев аппаратуры вычислительной техники, а также нашли применение при разработке курса «Теория информации» в УлГУ и «Сети и телекоммуникации» в УлГТУ. В приложении имеется документальное подтверждение о внедрении.

Результаты диссертационной работы докладывались и обсуждались на следующих семинарах и конференциях:

• 29-я молодежная конференция «Проблемы теоретической и прикладной математики» (Екатеринбург, 1998);

• 6-я Санкт-Петербургская международная конференция «Региональная информатика-98» (Санкт-Петербург, 1998);

• Всероссийская научно-практическая конференция «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, 1998);

• 2-я Всероссийская научно-техническая конференция «Информационные технологии в электротехнике и электроэнергетике» (Чебоксары, 1998);

• 3-я Всероссийская научно-техническая конференция «Методы и средства измерения физических величин» (Нижний Новгород, 1998);

• Международная конференция по мягким вычислениям и измерениям (Санкт-Петербург, 1998);

• научные семинары механико-математического факультета Ульяновского государственного университета (г. Ульяновск, 1998,1999);

По теме диссертации опубликовано 9 работ [18-26]. Диссертация состоит из введения, четырех глав, заключения, приложения и списка литературы из

Заключение

Основные научные положения и результаты, сформулированные, обоснованные и полученные в настоящей работе, заключаются в следующем:

1. Разработан и математически обоснован метод матрично-рангового кодирования дискретной информации, имеющей определенную природу возникновения, которая представляет собой данные системы импульсной регистрации. Получена оценка сложности алгоритма кодирования / декодирования, являющаяся степенной функцией длины кодируемого сообщения. Избыточность кода имеет логарифмический порядок роста относительно кодируемого числа. Доказаны свойства длины кода при условии варьирования значением кодируемого числа и рангом. Введен критерий оптимальности ранга и исследованы его свойства.

2. На основе метода матрично-рангового кодирования разработан алгоритм сжатия информации, генерируемой системой импульсной регистрации. Доказана возможность получения эффекта сжатия при определенных условиях. Доказана теоретическая возможность эффективного сжатия рассматриваемой информации без использования вспомогательной памяти.

3. Проведено моделирование процесса сжатия информации от источника, порождаемого системой импульсной регистрации. При относительной частоте появления регистрационного сигнала V, не принадлежащей интервалу (0.5-е, 0.5+е), где е=0.05, разработанный метод позволяет сокращать степень явной и скрытой избыточности. Зависимость коэффициента сжатия от V аппроксимирована квадратичной функций с точностью до 10"6. Проведенное сравнение использования алгоритмов сжатия, основанных на статистических и словарных подходах, показало, что разработанный метод дает более высокий показатель качества сжатия применительно к рассматриваемым источникам.

4. Доказана возможность построения на основе метода матрично-рангового кодирования блоковых кодов со скоростью передачи информации, приближающейся к верхней границе Плоткина и обладающих способностью помехозащиты. Разработана схема альтернативного построения кода методом матрично-рангового кодирования, которая может служить теоретическим обоснованием для разработки устройств вычислительной техники с контролем выполняемых операций, а также устройств шифрования. Проведено моделирование и разработана схема устройства суммирующего счетчика с контролем, на которую получено положительное решение по заявке на патент РФ. Предложен новый способ генерации управляемых перестановок в скоростных блочных недетерминированных шифрах.

1. Р.Е.Кричевский. Сжатие и поиск информации,- М.: Радио и связь. 1989.168 с.

2. Д.А.Хаффмен. Метод построения кодов с минимальной избыточностью.// Кибернетический сборник. 1963, вып.З,- 243 с.

3. К.Шеннон. Работы по теории информации и кибернетике.- М.: ИЛ., 1963.829 с.

4. Р.Фано. Передача информации. Статистическая теория связи,- М.: Наука, 1965.-455 с.

5. Ziv J., Lempel A. An Universal Algorithm for Sequental Data Compression// IEEE Transactions of Information Theory. 1977,- Vol.23.- №3,- P. 123-156.

6. Ziv J., Lempel A. Compression of Individual Sequences via Variable Rate Coding// IEEE Transactions of Information Theory. 1978. - Vol.23. - №3,-P. 45-98.

7. Б.М.Фитингоф. Сжатие дискретной информации// Проблемы передачи информации,- 1967. Т.З, №3.- С.28-36.

8. Р.Галлагер. Теория информации и надежная связь,- М.: Наука, 1974.- 458 с.

9. Davisson L. Universal Noiseless Coding// IEEE Trans. Inf. Th.- 1973,- Vol.19, №6,- P.783-795.

10. Cover T.M. Enumerative Source Encoding// IEEE Trans. Inf. Th.- 1973.-Vol.19, №1,- P.73-77.

11. Elias P. Minimax Optimal Universal Codeword Sets// IEEE Trans.-1983.-Vol.JT-29. №4,- P.491-502.

12. Bell T.C. Better OPM/L Compression // IEEE Transactions of Communication. 1986.-Vol.34.-P.1176- 1182.

13. Witten Ian. H., Neal Radford M., Cleary John G. Arithmetic coding for data compression// Communications of the ACM. 1987. - Vol.30. - №6,- P.344-365.

14. Rissanen J., Langdon G. Arithmetic coding // IBM J. Res. Dev.- 1979,- Vol.23, №2,- P.149-162.

15. Кулаичев А.П. Компьютерный контроль процессов и анализ сигналов. -М.: Информатика и компьютеры, 1999,- 330 с.

16. Куцевич Н.А. Программное обеспечение систем контроля и управления и Windows-технологии.// Мир компьютерной автоматизации. 1999, №3,- С.9-17.

17. Зеленова Т. Принципы построения современных телефонных систем.// Мир компьютерной автоматизации. 1998, №3,- С.7-12.

18. Смагин A.A., Терентьева Ю.Ю. Способ преобразования дискретной информации.// Фундаментальные проблемы математики и механики: Ученые записки УлГУ. Вып.1. Часть 2. Ульяновск: УлГУ, 1996,- С. 101-108.

19. Терентьева Ю.Ю. О возможностях метода матрично-рангового кодирования.// Тезисы 29-й молодежной конференции «Проблемы теоретической и прикладной математики», Екатеринбург, 1998,- С.75-76.

20. Терентьева Ю.Ю. Об одном методе кодирования дискретной информации.// Тезисы 2-й Всероссийской научно-технической конференции «Информационные технологии в электротехнике и электроэнергетике», Чебоксары, 1998,- С.213-215.

21. Терентьева Ю.Ю. О некоторых областях применения метода матрично-рангового кодирования.// Тезисы Международной конференции по мягким вычислениям и измерениям, Санкт-Петербург, 1998, том 1.-С. 180-181.

22. Терентьева Ю.Ю. Об одном способе криптографической защиты текста.// Тезисы 6-й Санкт-Петербургской международной конференции «Региональная информатика-98», Санкт-Петербург, 1998,- С. 131.

23. Терентьева Ю.Ю. Диагностирование канала связи при одновременной передаче дискретных данных.// Тезисы Всероссийской научно-практической конференции «Современные проблемы создания и эксплуатации радиотехнических систем», Ульяновск, 1998,- С.88-89.

24. Терентьева Ю.Ю., Смагин A.A., Шубович В.Г. Метод универсального кодирования бинарных последовательностей. Деп. в Центр, справочн. информ. фонде Министерства обороны РФ, Москва, Серия Б, Выпуск 48, 1999,-22 с.

25. Положительное решение по заявке на изобретение: Смагин A.A., Терентьева Ю.Ю. Суммирующий счетчик постоянного веса. № 99110954/ 09(011670), приоритет 26.05.99.

26. А.Эндрю. Искусственный интеллект,- М.: Мир, 1985,- 264 с.

27. Лорьер Ж.-Л. Системы искусственного интеллекта./ Пер. с фр. под ред. В.Л.Стефанюка,- М.:Мир, 1991,- 568 с.

28. Яглом A.M., Яглом И.М. Вероятность и информация,- М: Физматгиз, I960,-315 с.

29. Цымбал В.П. Задачник по теории информации и кодированию.- Киев. Изд-во «Вища школа», 1976,- 275 с.

30. L.Davisson. Mimmax Noiseless Universal Coding for Markov Sources // IEEE Trans. Inf. Theory, 1983, vol.29.- P.211-215.

31. L.Davisson, R.McElice, M.Pursley, M.Wallace. Efficient Universal Noiseless Source Codes // IEEE Trans. Inf. Theoiy, 1981, vol.27.- P.269-279.

32. Ornstain D.S., Weiss B. Entropy and data compression schemes // IEEE Trans. Inf. Theory.- 1993,- 39, №1,- P.78-83.

33. Capocelli Renato M., De Santis A., Periano G. Binary prefix codes, ending in a '1' // IEEE Trans. Inf. Theory. 1994, vol. 40, №4,- P.1296-1302.

34. Shtarkov Y. Coding of Discrete Source with Unknown Statistics // Colloquia Math. Soc. JBoyai, 1977, vol.16.- P.559-574.

35. Shtarkov Y. Universal Sequential Coding of Single Massages// Probl. Inform. Transm., 1987, vol.23.- P.175-186.

36. T.Linder, G.Lugosi, K.Zeger. Rates of Convergence in the Source Coding Theorem, in Empirical Quantizer Design, and the Universal Lossy Source Coding// IEEE Trans. Inf. Theory, 1994, vol.40.- P.1728-1740.

37. R.Rrichevsky, V.Trofimov. The performance of universal encoding// IEEE Trans. Inform. Theory, 1981, vol.27.- P.199-207.

38. M.Weinberger, A.Lempel, J.Ziv. A Sequential Algorithm for the Universal Coding of Finite Memory Sources // IEEE Trans. Inf. Theory, 1992, vol.38.-P.1002-1014.

39. G.Luchard, W.Spankowski. On the average redundancy rate of Lempel-Ziv code // IEEE Trans. Inform. Theory, 1997, vol. 43,- P.2-8.

40. E.Plotnik, M.Weinberger, J.Ziv, «Upper bounds on the probability of sequences emitted by finite-state sources and on the redundancy of the Lempel-Ziv algorithm», IEEE Trans. Inform. Theory, 1992, vol.38.- P.66-72.

41. A.D.Wyner, A.W.Wyner. Improved redundancy of a version of the Lempel-Ziv algorithm // IEEE Trans. Inform. Theory, 1995, vol.41.- P.723-731.

42. E.Yang, J.Kieffer. On the redundancy of the fixed-database Lempel-Ziv algorithm // IEEE Trans. Inform. Theory, 1997, vol.43.- P. 1101-1111.

43. J.Kieffer, E.Yang, G.Nelson, P.Cosman. Lossless compression via multilevel pattern matching // IEEE Trans. Inf. Theory, 1997, vol.43.- P.546-558.

44. Усенко С.И. Об опыте применения сжатия данных// Методы представления знаний в инф. технологиях./ АН УССР, Инст. кибернетики,-Киев, 1991,- С.49-53.

45. C.Liu, P.Narayan. Order Estimation and Sequential Universal Data Compression of a Hidden Markov-Source by the Method of Mixtures.// IEEE Trans. Inf. Theory, 1994, vol.40.- P. 1167-1180.

46. Д.Мастрюков. Алгоритмы сжатия информации. Часть 1. Сжатие по Хаффмену// Монитор. 1993, №8,- С. 14-24.

47. Д.Мастрюков. Алгоритмы сжатия информации. Часть 2. Арифметическое кодирование// Монитор, 1994, №1.- С.20-26.

48. Д.Мастрюков. Алгоритмы сжатия информации. Часть 3. Алгоритмы группы L// Монитор, 1994, №2,- С.10-18.

49. Горин А.К., Поляков Г.А. Сравнительная оценка эффективности методов сжатия данных// Вопросы прикл. матем. и матем. моделир. / Дшпропетр. Держав, ун-т.- Днепропетровск, 1997,- С.36-38.

50. Смирнов Н.В., Дунин-Барковский И.В. Курс теории вероятностей и математической статистики,- М.: Наука, 1969,- С.268-276.

51. Г.Корн, Т.Корн. Справочник по математике (для научных работников и инженеров).- М.: Наука, 1970,- 720 с.

52. Г.Биркгоф, Т.Барти. Современная прикладная алгебра,- М.: Мир, 1976. -С.243.

53. Б.В.Гнеденко. Курс теории вероятностей,- М.: Наука, 1969,- 453 с.

54. Кричевский Р.Е. Связь между избыточностью кодирования и достоверностью сведений об источнике // Проблемы передачи информации, 1968, 4, 3,- С.48-57.

55. Фитингоф Б.М. Оптимальное кодирование при неизвестной и меняющейся статистике сообщений // Проблемы передачи информации, 1966, 2, 2,- С.3-11.

56. Д.Химмельблау. Прикладное нелинейное программирование,- М.: Мир, 1975.- 534 с.

57. У.Питерсон, Э.Уэлдон. Коды, исправляющие ошибки,- М.: Мир, 1976.594 с.

58. J.K.Wolf. On Codes Derivable from the Tensor Product of Check Matrices // IEEE Trans. Inf. Theory, 1965, №2,- P.281-283.

59. Берлекэмп Э. Алгебраическая теория кодирования,- М: Мир, 1971,- 477 с.

60. Блейхут Р. Теория и практика кодов, контролирующих ошибки,- М: Мир, 1986,- 576 с.

61. G.Solomon, J.J.Stiffler. Algebraically Punctured Cyclic Codes// Information and Control, 1965, №2,- P.170-179.

62. Кугураков B.C. Оценки избыточности кодов с мажоритарным и перестановочным декодированием // Дисс. на соиск. уч. степ, к.ф.-м.н./ М., 1981.

63. Keiffer J.С. A survey of the theory of source coding with a fidelity criterion // IEEE Trans. Inf. Theory.- 1993,- 39, №5,- P.1473-1490.

64. Fu Fang-Wei, Xia Shu-Tao. Binary constant-weight codes for error detection// IEEE Trans. Inf. Theory.- 1998,- 44, №3,- P. 1294-1299.

65. Fu Fang-Wei, Vinck A.J. Han, Shen Shi-Yi. On the construction of constant-weight codes // IEEE Trans. Inf. Theory.- 1998,- 44, №1,- P.238-333.

66. Larison P. Bounds on constant weight codes correcting localized errors // IEEE Trans. Inf. Theory.- 1994- 30, №2,- P.517-521.

67. Берман С.Д. Полупростые циклические и абелевы коды // Кибернетика, 1967, №3,- С.34-48.

68. Capocelli R. М. On the redundancy of optimal codes with limited word length // IEEE Trans. Inf. Theory.- 1992,- 38, №2, pt.l.- P.439-445.

69. Abdel-Ghaffar Khaled A.S. On unit constrained-length convolutional codes // IEEE Trans. Inf. Theory.- 1992,- 38, №1,- P.200-206.

70. Mandelbaum D. Arithmetic Codes with Large Distance// IEEE Trans. Inf. Theory, 1967, №2,- P.237-242.

71. Колесник В.Д., Мирончиков В.Т. Некоторые циклические коды и схемы декодирования по большинству проверок // Проблемы передачи информации, 1965, вып.2,- С.3-17.

72. Колесник В.Д., Мирончиков Е.Т. Декодирование циклических кодов,- М.: Связь, 1968,- 154 с.

73. Hsu Н.Т., Kasami Т. Error Correcting Codes for a Compound Channel // IEEE Trans. Inf. Theory, 1967, №1,- P.135-139.

74. Сагалович Ю.Л. Алгебра, коды, диагностика,- М.: Мир, 1993,- 364 с.

75. Зиновьев В.А., Лицын С.Н. Таблица наилучших известных двоичных кодов,- М.: Мир, 1984,- 233 с.

76. Андрианов В.И., Сасковец В.Н. Двоичные дециклические коды // Кибернетика, 1966, №1,- С.57-64.

77. S.Y.Tong. Syncronization Recovery Techniques for Binary Cyclic Codes // BSTJ, 1966, №4,- P.561-596.

78. J.M.Goethals. Cyclic-Error-Locating Codes// Information and Control, 1967, vol.10, №4,-P.378-385.

79. Кодирование информации: двоичные коды. Справочник. Харьков, ВШ, 1978,- 197 с.

80. Calderbank A.R., Delsarte P. On error-correcting codes and invariant linear forms // SLAM J. Discrete Math.- 1993,- 6, №1,- P.3-23.

81. Бородин Л.Ф. Эквидистантные и другие оптимальные и близкие к оптимальным коды// Радиотехника и электроника, 1960, т.5, вып.6.- С.15-27.

82. Зигангиров Д.К. Сверточные коды и широкополосные системы связи// Дисс. на соиск. уч. степ. к.т.н./М., 1993.

83. Tilborg Н.С.А. Fire codes revised// Descrete Math., 1992, vol. 106,- P.479-482.

84. Альсведе P., Бассалыго JI.A., Пинскер M.C. Двоичные коды, исправляющие локализованные ошибки и дефекты // Проблемы передачи информации, 1994,- 30, №2,- С.10-13.

85. Панченко В.И. Конструкции близких к оптимальным малоизбыточных кодов // Дисс. на соиск. уч. степ, к.ф.-м.н./ М., 1989.

86. Рахматкариев Э.У. Анализ избыточности помехоустойчивых кодов // Кодирование в сложных системах,- М.: Наука, 1974,- С.115-153.

87. W.H.Kautz. Constant Weight Counter and Decoding Trees // IRE Trans. Electron. Computers, EC-9, I960,- P.231-244.

88. G.B.Fitzpatrick. Binary Ring Counters of Given Period. J. ACM, 7, 1960,-P.287-297.

89. M.P.Marcus. Cascaded Binary Counters with Feedback // IEEE Trans. Electron. Computers, EC-12, №4, 1963,- P.361-364.

90. M.E.Homan. A 4 Megacycle 18 Bit Checked Binary Counter// Pt.l. Trans. AIEE Commun. Electron., 1961, vol. 81,- P.516-522.

91. Андреев H.H. О некоторых направлениях исследований в области защиты информации// Междун. конф. «Безопасность информации». Москва. 14-18 апр. 1997. Сб. матер. М., 1997,- С.94-97.

92. Молдовян Н.А. Скоростные блочные шифры. С.-Пб., Изд-во СПбГУ, 1998.-230 с.

93. Молдовян H.A. Проблематика и методы криптографии. С.-Пб., Изд-во СПбГУ, 1998,- 212 с.

94. Молдовян A.A., Молдовян H.A., Псевдовероятностные скоростные блочные шифры для программной реализации // Кибернетика и системный анализ. Киев, 1997, №4,- С.133-141.

95. Stinsom D.R. Cryptography Theory and Practice.-N.Y.: CRC Press. Inc., 1995.434 p.

96. Молдовян A.A., Молдовян H.A., Вероятностные механизмы в недетерминированных блочных шифрах // Безопасность информационных технологий. М.: МИФИ, 1997, №3,- С.58-61.