автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Методы эффективной рандомизации сообщений, базирующиеся на омофонном и арифметическом кодировании

• - г ч На правах рукописи

( ; и4 и и

Фионов Андрей Николаевич

УДК 621.391

МЕТОДЫ ЭФФЕКТИВНОЙ РАНДОМИЗАЦИИ СООБЩЕНИЙ, БАЗИРУЮЩИЕСЯ НА ОМОФОННОМ И АРИФМЕТИЧЕСКОМ КОДИРОВАНИИ

Специальность 05.12.13 — Системы и устройства радиотехники

и связи

АВТОРЕФЕРАТ

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

Новосибирск 1998

Работа выполнена на кафедре прикладной математики и кибернетики Сибирского Государственного Университета Телекоммуникаций и Информатики (СибГУТИ)

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

профессор Рябко Б. Я.

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

профессор Трофимов В. К.

кандидат физико-математических наук, старший научный сотрудник Соловьева Ф. И.

Ведущее предприятие: Научный Совет по комплексной

проблеме "Кибернетика" РАН (Москва)

Защита диссертации состоится "5О" оЫТХ&рИ 1998 г. часов на заседании специализированного совета Д 118.07.01 в Сибирском Государственном Университете Телекоммуникаций и Информатики по адресу: 630102, г. Новосибирск, ул. Кирова, 86

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

Автореферат разослан

« 21 » QUxXxIpj 2998 г.

Ученый секретарь специализированного совета Д 118.07.01 член-корр. МАИ, к.т.н., профессор . ___^-Б. И. Крук

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

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

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

Построение и исследование методов рандомизации сообщений привлекает внимание многих специалистов. Статические методы разрабатывались и изучались в работах К. Гюнтера (Ch. Günther), Дж. Месси (J. Massey), К. Гирмана (Ch. Gehrmann), В. Пенцхорна (W. Penzhorn) и многих других. Методам универсального и адаптивного кодирования посвящены многочисленные исследования. Основные результаты в этой области принадлежат как отечественным исследователям В. Ф. Бабкину, Р. Е. Кри-чевскому, Б. Я. Рябко, В. К. Трофимову, Б. М. Фитингофу, Ю. М. Штарькову, так и зарубежным исследователям Я. Зиву (J. Ziv), Дж. Клири (J. Cleary), А. Лемпелу (А. Lempel), Й. Рисса-нену (J. Rissanen), И. Уиттену (I. Witten), П. Элайесу (Р. Elias) и др.

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

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

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

Дель работы:

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

. но малых избыточности и числа используемых случайных символов.

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

Задачи исследования Для достижения указанных целей в рамках диссертационной работы решаются следующие задачи.

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

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

3. Синтез двух выше указанных методов для обеспечения одновременно заданных, произвольно низких избыточности и числа случайных символов, используемых при кодировании.

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

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

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

Научная новизна результатов работы:

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

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

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

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

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

5. Разработан метод кодирования для источников с неизвестной статистикой, основанный на мнимом скользящем окне и арифметическом кодировании, позволяющй на порядок снизить необходимый объем памяти кодера и декодера по сравнению с ранее известными методами.

Практическая ценность результатов:

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

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

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

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

Внедрение результатов работы Основные результаты получены в рамках работы по проекту №96-01-00052 "Асимптотически оптимальные коды для стационарных источников информации", финансируемому Российским фондом фундаментальных исследований, и в процессе выполнения НИР Государственного

комитета РФ по связи и информатизации "Аспект-Сибирь" по теме "Разработка высокоскоростных методов сжатия данных".

Планируется практическая реализация разработанных методов при решении задач защиты информации в Internet в рамках проекта №98-01-00772 "Теоретическое обоснование и реализация эффективных доказуемо-стойких методов защиты информации для полнотекстовых баз данных в среде Internet", финансируемого Российским фондом фундаментальных исследований.

Результаты диссертации используются в учебном процессе при чтении курсов "Основы криптографии" и "Теория вычислительных процессов и систем", а также при выполнении дипломных проектов в СибГУТИ.

Апробация работы и публикации Основные результаты работы докладывались и обсуждались на следующих российских и международных конференциях: Российская научно-техническая конференция "Информатика и проблемы телекоммуникаций" (Новосибирск, 1996); Международная научно-техническая конференция "Информатика и проблемы телекоммуникаций" (Новосибирск, 1997); Международная конференция по исследованию операций (Новосибирск, 1998); Международный семинар "Распределенная обработка информации" (Новосибирск, 1998); 7th International Symposium on Algorithms and Computation ISAAC'96 (Osaka, Japan, 1996); 8th International Symposium on Algorithms and Computation ISAAC'97 (Singapore, 1997); IEEE International Symposium on Information Theory ISIT'97 (Ulm, Germany, 1997); IEEE International Symposium on Information Theory ISIT'98 (Cambridge, USA, 1998);

По теме диссертации опубликовано 14 печатных работ, в том числе 5 статей, подготовлено 2 отчета о НИР.

Основные положения, выносимые на защиту:

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

логарифмического роста времени кодирования и декодирования.

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

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

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

5. Использование структуры данных "мнимое скользящее окно" в сочетании с арифметическим кодированием позволяет на порядок снизить необходимый объем памяти кодера и декодера при обеспечении заданной, произвольно низкой избыточности в случае кодирования источника с неизвестной статистикой,

Структура и объем работы Диссертация состоит из введения, пяти глав, заключения и списка литературы. Диссертация содержит 149 страниц машинописного текста, 10 рисунков и 7 таблиц. Список литературы включает 77 наименований.

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

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

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

Задача полной рандомизации сообщений ставится следующим образом. Пусть дан источник, порождающий буквы из алфавита А = {а^аг,... ,а„} с вероятностями р(а х), р(а ..., р(а„) (для простоты изложения сначала рассматриваются источники без памяти, затем дается обобщение на случай марковских источников). Необходимо так закодировать сообщение источника, чтобы символы кодовой последовательности, выбираемые из алфавита {0,1}, были равновероятны и независимы. Среди различных подходов к решению этой задачи наибольший интерес исследователей привлекает омофонное кодирование (называемое

омофонной подстановкой). Суть этого подхода удобно рассмотреть на примерах.

Пусть А = {а, Ь}, р(а) = 3/4, р(Ь) = 1/4. Следующая таблица задает омофонный код с постоянной длиной кодового слова (через ы обозначены омофоны, замещающие реальные символы при кодировании).

Символ Омофон Кодовое слово Вероятность выбора

а VI 00 1/3

V2 01 1/3

10 1/3

Ъ щ 11 1

Представленный код был известен еще со времен Гаусса. Его основным недостатком является сильное "растяжение" сообщения, т. к. длина кодового слова определяется логарифмом минимальной вероятности символа.

К. Гюнтер предложил использовать код с переменной длиной кодового слова, задаваемый следующим образом:

Символ Омофон Кодовое слово Вероятность выбора

а Щ 0 2/3

10 1/3

Ъ И 1

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

1>1 I 6

О «2 10

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

Для измерения степени "растяжения" сообщения при омо-фонном кодировании используется понятие избыточности (г), определяемой как разность между средней длиной кодового слова и энтропией источника. Другой практически важной характеристикой является среднее число случайных бит (т?), используемых при кодировании одного символа.

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

г < 2 бит/символ, т] < 4 бит/символ.

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

извольно малой избыточности (данная задача является классической для теории информации). Решение этой задачи возможно на основе блокового кодирования. При кодировании блока длины Ь оптимальный метод обеспечивает избыточность на символ г < 2/Ь, и избыточность может быть сделана сколь угодно малой при увеличении Ь. Однако, требуемые в этом случае объем памяти (5) или время (Т) растут экспоненциально,

5 = 0 (|А|1/г) или Т = 0 (|А|1/г) при г —► О, ту 2г.

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

Определим кумулятивные вероятности для символов алфавита источника:

СЦад = 0, <2Ы = 5>(аД г = 2,3,..., п. (1)

У<>

Введем вспомогательную величину

ф{и) = <?(и) + р(и).

Аналогичным образом определим величины С}{и) и 0(17) для блока символов V = щщ

Величины С}(и) и 0(17) могут быть вычислены с помощью быстрого метода, предложенного Б. Я. Рябко. Любое число, принадлежащее интервалу [<5(£/), > однозначно определя-

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

1. Вычисляются величины £?(£/) и <5((У) (посредством быстрого метода, обобщенного на случай произвольных рациональных вероятностей символов).

2. Строится случайная двоичная дробь С (17) < 1, удовлетворяющая неравенству 0(17) < С(17) < 0(17) (т. е. кодовое слово).

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

Основные свойства метода, сформулированные в работе в виде теорем и следствий, сводятся к следующему. Метод решает задачу полной рандомизации. Избыточность кода не превышает 3 бит на блок, и при кодировании блока используется не более 12 случайных бит (в среднем). При увеличении размера блока избыточность стремится к нулю, при этом сложность кодера и декодера характеризуется оценками

5 = 0(1 /г), Т = 0(1о§21/г к^к^1/г), г-> 0, 77-+4г.

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

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

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

Для иллюстрации основных идей метода рассмотрим пример. Пусть, по-прежнему, дан бернуллиевский источник, порождающий буквы из алфавита А = {а, 6} с вероятностями ^(а) = 3/4, р(Ь) = 1/4. Рассмотрим кодирование блока II = аааЬ, порожденного этим источником. Покажем схематично процесс кодирования, а затем дадим необходимые пояснения.

[О, 16) [0, 12) [0, 9) -1* [0, б|) —*

Г [0, 6) с вер. 24/27 * \ [6, б|) с вер. 3/27

[О, 6) [О, 12) [9, 12) -Н* [4, 16) —►

_^ Г [4, 8) -»01 с вер. 1/3

\ [8, 16) 1 с вер. 2/3

[6, б|) ^ [0,12) — ...

Исходный интервал [0, 24) предполагает использование 4-битной арифметики при вычислениях (как будет показано ниже, от точности представления границ интервала зависит избыточность кода). Первая буква сообщения а сужает интервал до 3/4 его первоначального размера, пропорционально той доле, которую буква а занимает в распределении вероятностей. Вторая и третья буквы продолжают сужение текущего интервала аналогичным образом, образуя интервалы для диграмы аа и триграмы ааа. Но интервал для ааа имеет дробную правую границу, что приводит к невозможности дальнейшего использования 4-битной целочисленной арифметики. Поэтому интервал разделяется на

два омофонных интервала, только один из которых выбирается для последующего сужения. Размеры омофонных интервалов соотносятся как 24/4 и 3/4 и их сумма есть 27/4, откуда следуют вероятности выбора.

Предположим, что был выбран интервал [0, 6). Следующая операция — это масштабирование. Т. к. интервал [0, 6) занимает 3/4 интервала [0, 8), т. е. левой половины исходного интервала, то на выход кодера передается 0, определяющий левую половину, и левая половина рассматривается как новый исходный интервал, с увеличением [0, 6) в два раза, до [0, 12), чтобы сохранить пропорции. Буква Ь сужает этот интервал до 1/4 его размера, [9, 12), и после масштабирования получается заключительный интервал для блока [4, 16). Последняя операция — это омофонная подстановка для заключительного интервала, которая выполняется путем его разбиения на подынтервалы, каждый из которых кодируется целым числом бит.

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

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

Для избыточности на символ получена оценка

г < Ш2~1 + З/Ь,

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

Сложность метода определяется использованием ¿-битной

арифметики и характеризуется оценками

S = 0(t), T = 0(t log t log log ¿) при t oo, или, рассматриваемая как функция избыточности,

S = 0(logl/r), Г = О(log 1/гloglog 1 /гlogloglog 1 /г) при г —»■ 0, Tj —► 2 + г.

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

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

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

Если размер блока составляет m символов, то ожидаемое число используемых случайных бит в расчете на один символ будет примерно 2/т, и при увеличении размера блока может быть сделано сколь угодно малым. Выбирал необходимую точность представления границ интервала t, получаем заданную избыточность. Методика выбора параметров mut при кодировании блока или сообщения длины L формулируется следующим образом.

Чтобы обеспечить заданные верхние границы для избыточности (г*) и для числа случайных бит (ту*), сначала выберем т, удовлетворяющее неравенству

2/т < 7]* - г* - 9/£, и затем выберем t такое, что

й- < "(г'-З/Ц

8пт

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

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

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

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

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

Методам универсального и адаптивного кодирования посвящены многочисленные исследования. Известны методы, позволяющие получать заданную низкую избыточность при относительно невысокой вычислительной сложности. Это, прежде всего, адаптивные методы, построенные на основе скользящих окон и арифметического кодирования. У лучших из этих методов объем памяти кодера и декодера обратно пропорционален избыточности, а время кодирования (и декодирования) при уменьшении избыточности растет примерно в логарифмическом масштабе. Особенностью адаптивных методов, основанных на арифметическом кодировании, является зависимость скорости их работы от размера алфавита источника. Для известных методов время кодирования (и декодирования) возрастает линейно при увеличении размера алфавита. Это объясняется тем, что скользящее окно дает оценки вероятностей символов (меняющиеся после кодирования каждого символа), в то время как арифметический кодер требует кумулятивных вероятностей, вычисляемых по формуле (1).

В четвертой главе предлагается метод адаптивного ариф-

метического кодирования источников с большими алфавитами, для которого время кодирования и декодирования растет как логарифм от размера алфавита. Решение состоит в том, что в памяти кодера (и декодера) хранятся не только оценки вероятностей СИМВОЛОВ Р1, ръ , ..., Р„, НО И суммы пар р\ +Р2 > Ръ+Ра , • ■ •, суммы

четверок рН-----\-pii Рь Н-----Ьрв, ..., и т. д. Такая организация

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

<3(а8) = (р1 + р2 + рз + щ) + (рз + Рб) + Р7

требует сложения трех чисел.

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

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

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

Чтобы устранить указанный недостаток, предлагается ис-

пользовать специальную структуру данных, названную "мнимым скользящим окном" (концепция мнимого скользящего окна была предложена в работах Б. Я. Рябко). Этот подход позволяет сохранить все свойства скользящего окна и, в то же время, избавить кодер и декодер от хранения в памяти самого окна.

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

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

Г. /П1 т п\

b < Const log 71 -)- п log — J , то мнимое окно обеспечивает

S < const ^nlog —^ .

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

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

Для метода блокового омофонного кодирования справедливы следующие оценки объема памяти кодера и декодера (5) и времени кодирования и декодирования (Г):

5 = 0(l/r), Т = 0(log21 /г log log 1/r)

при Г —♦ О, 7? < 4г.

Для метода арифметического кодирования с разделением интервала

5 = О (log 1/r), Г = О (log 1/r log log 1/r loglog log 1/r)

при г —0, т] <2 + r.

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

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

S = 0(logl/r) при г —> О, Т = 0(log |Л|) при \А\ оо, где |А| обозначает размер алфавита.

ПУБЛИКАЦИИ

1. Ryabko В. Y., Fionov A. N. A fast and efficient homophonic coding algorithm//Algorithms and Computation. Berlin: Springer,

1996. P. 427-438 (Lecture Notes in Comput. Sci.: V. 1178).

2. Рябко Б. Я., Фионов А. Н. Быстрый метод полной рандомизации сообщений // Пробл. передачи информ. 1997. Т. 33, №3. С. 3-14.

3. Фионов А. Н. Эффективный метод рандомизации сообщений на основе арифметического кодирования // Дискретный анализ и исследование операций. 1997. Т. 4, №2. С. 51-74.

4. Рябко Б. Я., Федотов А. М., Фионов А. Н. Надежные системы защиты электронных публикаций, базирующиеся на эффективном омофонном кодировании // Вычислительные технологии. 1997. Т. 2, №3. С. 68-72.

5. Ryabko В. Ya., Fionov А. N. Homophonic coding with logarithmic memory size // Algorithms and Computation. Berlin: Springer, 1997. P. 253-262 (Lecture Notes in Comput. Sci.; V. 1350).

6. Фионов A.H. Быстрый метод полной рандомизации сообщений // Российская научно-техн. конф. "Информатика и проблемы телекоммуникаций". Тезисы докладов. Новосибирск, 1996. Т. 1. С. 70.

7. Фионов А. Н. Эффективная рандомизация сообщений на основе арифметического кодирования // Международная научно-техн. конф. "Информатика и проблемы телекоммуникаций". Материалы конференции. Новосибирск, 1997. С. 157-158.

8. Ryabko В., Fionov A. Decreasing redundancy oi homophonic coding // Proc. IEEE Int. Symp. Inform. Theory. Ulm, July

1997. P. 94.

9. Рябко В. Я., Федотов А. М., Фионов А. Н. Современные средства криптографической защиты информации в сетях передачи данных // Международная конф. "Современные информационные технологии". Материалы конференции. Новосибирск, 1998. С. 42-44.

10. Рябко В. Я., Фионов А. Н., Федотов А. М. Конфиденциальность взаимодействий в открытых информационных сетях // Международный семинар "Перспективы развития современных средств и систем телекоммуникаций". Материалы семинара. Новосибирск, 1998. С. 38-42.

11. Fionov А. N. Computationally efficient randomization of messages // Международная Сибирская конф. по исслед. операций. Материалы конференции. Новосибирск, 1998. С. 159.

12. Ryabko В. Ya., Fionov А. N. Efficient algorithm of adaptive arithmetic coding // Международная Сибирская конф. по исслед. операций. Материалы конференции. Новосибирск, 1998. С. 151.

13. Fionov А. N. Using homophonic decoding for random number generation // Международный семинар "Распределенная обработка информации". Материалы семинара. Новосибирск, 1998. С. 63-67.

14. Ryabko В., Fionov A. Fast homohponic coding with logarithmic memory size // Proc. IEEE Int. Symp. Inform. Theory, Cambridge, August 1998. P. 52.



ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО СВЯЗИ И ИНФОРМАТИЗАЦИИ

СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ

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

Фионов Андреи Николаевич

УДК 621.391

и

и

МЕТОДЫ ЭФФЕКТИВНОМ РАНДОМИЗАЦИИ СООБЩЕНИИ, БАЗИРУЮЩИЕСЯ НА ОМОФОННОМ И АРИФМЕТИЧЕСКОМ КОДИРОВАНИИ

Специальность 05.12.13 — Системы и устройства радиотехники

и связи

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

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

академик МАИ, доктор технических наук, профессор Б. Я.. Рябко

Новосибирск 1998

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 5

1 РАНДОМИЗАЦИЯ СООБЩЕНИЙ, ОСНОВАННАЯ

НА БЛОКОВОМ КОДИРОВАНИИ 13

1.1. Введение......................................................13

1.2. Основные идеи омофонного кодирования и обзор известных методов............................................14

1.3. Основные понятия и идеи..................................23

1.4. Посимвольное омофонное кодирование при двоично-рациональных вероятностях символов..................31

1.4.1. Обозначения ........................................31

1.4.2. Кодирование ........................................32

1.4.3. Декодирование..............................35

1.4.4. Основные свойства метода........................36

1.5. Блоковое омофонное кодирование при двоично-рациональных вероятностях символов........................39

1.5.1. Определения и обозначения......................39

1.5.2. Кодирование блока ................................40

1.5.3. Декодирование блока..............................40

1.5.4. Сложность блокового кодирования..............42

1.6. Посимвольное омофонное кодирование при произвольных рациональных вероятностях символов ... 44

1.6.1. Кодирование ........................................44

1.6.2. Декодирование......................................47

1.6.3. Основные свойства метода........................51

1.7. Блоковое омофонное кодирование при произвольных рациональных вероятностях символов............53

1.7.1. Кодирование блока ................................53

1.7.2. Декодирование блока..............................54

1.7.3. Сложность блокового кодирования..............55

Выводы..............................................................57

2 РАНДОМИЗАЦИЯ СООБЩЕНИЙ, ОСНОВАННАЯ НА АРИФМЕТИЧЕСКОМ КОДЕ 58

2.1. Введение.......................... . 58

2.2. Основные идеи арифметического кодирования с разделением интервала........................................60

2.3. Арифметическое кодирование с разделением интервала ............................................................66

2.3.1. Обозначения и определения......................66

2.3.2. Масштабирование интервала....................68

2.3.3. Разделение интервала..............................71

2.3.4. Алгоритм кодирования............................72

2.3.5. Алгоритм декодирования..........................75

2.3.6. Избыточность и сложность кодирования ... 79

2.4. Реализация случайного выбора интервала............85

Выводы..............................................................90

3 ОБОБЩЕННЫЙ МЕТОД ПОЛНОЙ РАНДОМИЗАЦИИ И ЕГО ОСНОВНЫЕ ПРИЛОЖЕНИЯ 91

3.1. Введение......................................................91

3.2. Синтез блокового и арифметического омофонного кодирования..................................................92

3.3. Приложение омофонного кодирования к задачам криптографии ....................................................95

3.4. Применение омофонного декодирования в задачах генерации случайных чисел..............................98

3.4.1. Постановка задачи..................................98

3.4.2. Основная идея метода...............100

Выводы...............................102

4 АДАПТИВНОЕ АРИФМЕТИЧЕСКОЕ КОДИРОВАНИЕ ИСТОЧНИКОВ С БОЛЬШИМИ АЛФАВИТАМИ 103

4.1. Введение...........................103

4.2. Обзор методов адаптивного кодирования.......106

4.3. Избыточность арифметического кодирования .... 110

4.3.1. Арифметическое кодирование......... . 111

4.3.2. Арифметическое декодирование ........112

4.3.3. Избыточность и вычислительная сложность арифметического кодирования .........113

4.4. Быстрое адаптивное кодирование с использованием скользящего окна......................117

4.4.1. Определение скользящего окна.........117

4.4.2. Эффективное кодирование источников с большими алфавитами.................119

4.4.3. Избыточность и сложность адаптивного кодирования ......................123

Выводы...............................130

5 ЭФФЕКТИВНОЕ ПО ПАМЯТИ АДАПТИВНОЕ КО-

ДИРОВАНИЕ 131

5.1. Введение...........................131

5.2. Адаптивное кодирование на основе мнимого скользящего окна.........................132

5.2.1. Описание схемы кодирования..........132

5.2.2. Точность представления статистики источника134

5.2.3. Реализация случайного выбора символа . . . 138

5.2.4. Основные свойства метода, основанного на мнимом скользящем окне.............141

5.2.5. Замечания о способах получения случайных

бит..........................142

5.3. Адаптивное кодирование марковских источников . . 142 Выводы...............................145

ЗАКЛЮЧЕНИЕ 146

ЛИТЕРАТУРА 149

ВВЕДЕНИЕ

Актуальность темы

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

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

Построение и исследование методов рандомизации сообщений привлекает внимание многих специалистов. Статические методы разрабатывались и изучались в работах К. Гюнтера (Ch. Günther), Дж. Месси (J. Massey), К. Гирмана (Ch. Gehrmann),

В. Пенцхорна (W. Penzhorn) и многих других. Методам универсального и адаптивного кодирования посвящены многочисленные исследования. Основные результаты в этой области принадлежат как отечественным исследователям В. Ф. Бабкину, Р. Е. Кри-чевскому, Б. Я. Рябко, В. К. Трофимову, Б. М. Фитингофу, Ю. М. Штарькову, так и зарубежным исследователям Я. Зиву (J. Ziv), Дж. Клири (J. Cleary), А. Лемпелу (А. Lempel), И. Рисса-нену (J. Rissanen), И. Уиттену (I. Witten), П. Элайесу (Р. Elias) и

ДР-

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

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

Цель работы

1. Построение эффективных методов полной рандомизации сообщений, характеризуемых неэкспоненциально растущими

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

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

Задачи исследования

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

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

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

3. Синтез двух выше указанных методов для обеспечения одновременно заданных, произвольно низких избыточности и числа случайных символов, используемых при кодировании.

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

5. Построение и применение эффективных структур данных для оценивания статистики произвольного источника с за-

данной точностью.

Методы исследования

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

Научная новизна результатов работы

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

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

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

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

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

5. Разработан метод кодирования для источников с неизвестной статистикой, основанный на мнимом скользящем окне и арифметическом кодировании, позволяющй на порядок снизить необходимый объем памяти кодера и декодера по сравнению с ранее известными методами.

Практическая ценность результатов

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

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

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

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

Основные положения, выносимые на защиту

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

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

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

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

5. Использование структуры данных "мнимое скользящее окно" в сочетании с арифметическим кодированием позволяет на порядок снизить необходимый объем памяти кодера и декодера при обеспечении заданной, произвольно низкой из-

быточности в случае кодирования источника с неизвестной статистикой.

Структура и объем работы

Диссертация состоит из введения, пяти глав, заключения и списка литературы.

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

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

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

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

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

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

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

Диссертация содержит 149 страниц машинописного текста, 10 рисунков и 7 таблиц. Список литературы включает 77 наименований.

Глава 1

РАНДОМИЗАЦИЯ СООБЩЕНИЙ, ОСНОВАННАЯ НА БЛОКОВОМ КОДИРОВАНИИ

1.1. Введение

Как отмечалось во введении к диссертации, для решения многих важных практических задач требуются методы кодирования, преобразующие сообщения источника в последовательность равновероятных и независимых кодовых символов. Такие методы относятся к классу методов рандомизации (или случайного кодирования). На протяжении всей работы мы будем рассматривать только двоичные коды, т. е. в качестве кодовых символов будем использовать буквы алфавита В = {0,1} (двоичные коды имеют наибольшее практическое значение, в то же время обобщение методов на случай произвольных кодовых алфавитов не представляет принципиальной трудности). При использовании двоичных кодов задача полной рандомизации может быть сформулирована следующим образом. Пусть источник информации порождает (бесконечное) сообщение X = Х1Х2Х3 .. . , символы ко-

торого выбираются из некоторого алфавита А источника. Полная рандомизация определяется как преобразование сообщения X в однозначно декодируемую последовательность С1С2С3 ... , построенную из букв кодового алфавита В, при котором

Pr{c¿ = 0} = Pr{c¿ = 1} = 1/2, i = 1,2,3,... (1.1)

и

P(ck\c\c2 . . . Ck-1) = -P(q) ДЛЯ любого к > 1 (1-2)

(т. е. все кодовые символы равновероятны и независимы).

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

1.2. Основные идеи омофонного кодирования и обзор известных методов

Идея омофонного кодирования была известна еще Гауссу и использовалась им в криптографических целях (см., например, [41] и [46]). Чтобы пояснить суть этого подхода, приведем пример из [37]. Допустим, бернуллиевский источник порождает буквы из алфавита А = {а, 6} с вероятностями р(а) = 3/4, р(Ь) = 1/4. Закодируем каждый символ сообщения источника в соответствии с табл. 1.1.

Символ Омофон Кодовое слово Вероятность выбора

а VI 00 1/3

01 1/3

10 1/3

Ъ Щ 11 1

Табл. 1.