автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Быстрая нумерация комбинаторных объектов, находящая применение в системах передачи и хранения информации

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

Медведева Юлия Сергеевна

БЫСТРАЯ НУМЕРАЦИЯ КОМБИНАТОРНЫХ ОБЪЕКТОВ, НАХОДЯЩАЯ ПРИМЕНЕНИЕ В СИСТЕМАХ ПЕРЕДАЧИ И ХРАНЕНИЯ ИНФОРМАЦИИ

05.13.17 — теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

5 АВГ 2015

005571216

Новосибирск - 2015

005571216

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте вычислительных технологий Сибирского отделения Российской академии наук, г. Новосибирск.

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

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

Рябко Борис Яковлевич, доктор технических наук, профессор

Соловьева Фаина Ивановна, доктор физико-математических наук, профессор, ведущий научный сотрудник, ФГБУН Институт математики им. С. Л. Соболева Сибирского отделения РАН, г. Новосибирск, Кручинин Владимир Викторович, доктор технических наук, профессор кафедры промышленной электроники, ФГБОУ ВПО «Томский государственный университет систем управления и радиоэлектроники», г. Томск

ФГБОУ ВПО «Новосибирский государственный технический университет», г. Новосибирск

Защита диссертации состоится «2Л»С-Ситл 2015 г. в часов на

заседании диссертационного совета Д 219.005.02 при Федеральном государственном образовательном бюджетном учреждении высшего профессионального образования «Сибирский государственный университет телекоммуникаций и информатики» (ФГОБУ ВПО «СибГУТИ») по адресу: 630102, г. Новосибирск, ул. Кирова, 86.

С диссертацией можно ФГОБУ ВПО «СибГУТИ».

ознакомиться

библиотеке

Автореферат разослан «2.2» ииЭ/1^

2015 г.

Ученый секретарь диссертационного совета ^ - Резван И. И.

Д 219.005.02, к. т. н., доцент

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

Актуальность темы. Задача нумерации и денумерации комбинаторных объектов. Задача нумерационного кодирования в общем виде состоит в следующем: дан некоторый алфавит А и множество S слов длины n > 1, являющееся подмножеством всех слов длины п, состоящих из букв алфавита А. Метод нумерационного кодирования должен по данному слову w € S вычислять его номер code${w), т. е. число из промежутка [О, |5| — 1]. Метод нумерационного декодирования должен по данному номеру слова codes(w) находить слово w € S. Задача построения быстрых алгоритмов нумерации и денумерации имеет практическую и теоретическую значимость в кодировании данных на носителях и в каналах, имеющих ограничения, связанные с физическими свойствами носителя или канала, а также в сетевом кодировании и других областях теории информации; ей посвящены сотни статей и несколько монографий. В работе рассмотрено несколько важных классов комбинаторных объектов, для которых актуально построение быстрых алгоритмов нумерации, таких как слова с ограничениями на длины серий единиц, элементы грассманиана, слова языков Дика.

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

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

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

отклик канала, требуемая скорость передачи данных (или информационная плотность) и шумовые характеристики.

RLL-коды, в их общей форме, разрабатывались в 60-70 гг., например, в работе В. Каутца (Kautz W. Fibonacci codes for synchronization control // IEEE Transactions on Information Theory. 1965. T. 11. №2. C. 284-292), в работе Д. Т. Танга и J1. Р. Бала (Tang D. Т., Bahl L. R. Block codes for a class of constrained noiseless channels //Information and Control. 1970. T. 17. №5. C. 436-461), и продолжают вызывать интерес исследователей, в последние годы им было посвящено множество статей (Datta S., McLaughlin S. W. An enumerative method for runlength-limited codes: permutation codes // IEEE Transactions on Information Theory. 1999. T. 45. №6. C. 2199-2204; Milenkovic 0., Vasic B. Permutation (d, k)-codes: efficient enumerative coding and phrase length distribution shaping // IEEE Transactions on Information Theory. 2000. T. 46. №7. C. 2671-2675).

RLL-коды являются основой всех появившихся в последнее время дисковых стандартов хранения информации, таких как CD, DVD, BlueRay Disc.

Нумерация слов языков Дика. Задача быстрой нумерации слов языков Дика имеет практическую и теоретическую значимость. Решения предлагались, например, в работах Й. Либееншеля (Liebehenschel J. Lexicographical generation of a generalized Dyck language // SI AM Journal on Computing. 2003. T. 32. №4. C. 880-903; Liebehenschel J. Ranking and unranking of lexicographically ordered words: an average-case analysis // Journal of Automata, Languages and Combinatorics. 1997. T. 2. №4. C. 227-268). Предлагаемый в диссертации алгоритм нумерации экспоненциально быстрее известных ранее алгоритмов. Словами языков Дика над алфавитом мощности 2т являются последовательности правильно вложенных скобок т типов.

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

Необходимость быстрой нумерации и денумерации слов языков Дика возникает при работе трансляторов языков высокого уровня, для сжатия последовательностей правильно вложенных скобок и случайной генерации последовательностей правильно вложенных скобок (Рейнгольд Э. М., Нивергельт

Ю., Део Н. Комбинаторные алгоритмы: Теория и практика. Пер. с англ. Мир, 1980; Альфред В., Сети Р., Ульман Д. Д. Компиляторы: принципы, технологии и инструменты. Вильяме, 2001; Кричевский Р. Е. Сжатие и поиск информации. Радио и связь, 1989).

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

Нумерация элементов грассманиана. Задача быстрой нумерации элементов грассманиана имеет практическую значимость в сетевом кодировании. Решения предлагались во множестве работ (Kohnert А., Kurz S. Construction of large constant dimension codes with a prescribed minimum distance // Mathematical Methods in Computer Science. Springer Berlin Heidelberg, 2008. C. 31-42; Skachek V. Recursive code construction for random networks // IEEE Transactions on Information Theory. 2010. T. 56. №3. C. 1378-1382; Silberstein N., Etzion T. Enumerative coding for Grassmannian space // IEEE Transactions on Information Theory. 2011. T. 57. № 1. C. 365-374.) Предлагаемый в диссертации алгоритм нумерации экспоненциально быстрее известных ранее алгоритмов.

Пусть Fq — конечное поле размера q. Грассманианом называется множество всех к-мерных подпространств векторного пространства обозначаемое Gq(n,k), для любых к и п, 0 < к < п. Нумерационным кодированием элементов грассманиана Gq(n, к) является сопоставление каждому элементу грассманиана его номера, т. е. двоичного слова из промежутка [0, \Gq(n, к)\ — 1].

Задача кодирования элементов грассманиана рассматривалась во многих работах в течении последних сорока лет, например, в работе Д. Э. Кнута (Knuth D. Е. Subspaces, subsets, and partitions // Journal of Combinatorial

Theory, Sériés A. 1971. T. 10. №2. C. 178-180), В. Дж. Мартина, Kc. Дж. Жу (Martin W. J., Zhu X. J. Anticodes for the Grassman and bilinear forms graphs // Designs, Codes and Cryptography. 1995. T. 6. №1. C. 73-79).

В работе P. Кеттера, Ф. P. Кшишанга (Koetter R., Kschischang F. R. Coding for errors and erasures in random network coding // IEEE Transactions on Information Theory. 2008. T. 54. №8. C. 3579-3591) показано, как можно использовать коды с исправлением ошибок на множестве элементов грассмани-ана в случайном сетевом кодировании. Это приложение привело к появлению множества работ в данной области в последние годы.

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

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

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

Основные задачи работы: построение быстрого алгоритма нумерационного кодирования и декодирования последовательностей с ограничениями на длины серий; построение быстрого алгоритма нумерационного кодирования и декодирования слов языков Дика; построение быстрого алгоритма нумерационного кодирования и декодирования элементов грассманиана.

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

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

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

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

Все предлагаемые алгоритмы реализованы в виде программ.

Научная новизна. 1. Разработан новый быстрый алгоритм нумерационного кодирования двоичных слов длины п, имеющих ограничения на длины серий единиц. Сложность нумерации и денумерации слов в разработанном алгоритме меньше, чем у ранее известных алгоритмов, и равна O(log3nloglogn) битовых операций на одну букву слова. Ранее известные алгоритмы имеют линейную сложность нумерации и денумерации. Алгоритм получен на основе метода нумерации комбинаторных объектов Б. Я. Рябко (Рябко Б. Я. Быстрая нумерация комбинаторных объектов//Дискретная математика. 1998. Т. 10. №2. С. 101-119).

2. Разработан новый быстрый алгоритм нумерационного кодирования элементов грассманиана Gq(n, к), т. е. множества всех fc-мерных подпространств векторного пространства F™ над конечным полем размера q. Сложность нумерации и денумерации элементов грассманиана в новом алгоритме меньше, чем у ранее известных алгоритмов, и равна О(п2 log2 п log log п). Алгоритмы, известные ранее, имеют сложность 0(п3 log п log log п). Алгоритм создан с применением метода нумерации комбинаторных объектов Б. Я. Рябко.

3. Разработан новый быстрый алгоритм нумерационного кодирования слов языков Дика длины п. Сложность нумерации и денумерации слов в предлагаемом алгоритме меньше, чем у ранее известных алгоритмов, и равна О (log3 п log log п) битовых операций на одну букву слова. Алгоритмы, которые были предложены до этого, имеют линейную сложность нумерации и денумерации. Алгоритм построен с использованием метода нумерации комбинаторных объектов Б. Я. Рябко.

4. Разработана модификация общего метода быстрой денумерации комбинаторных объектов Б. Я. Рябко.

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

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

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

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

Быстрый алгоритм нумерационного кодирования элементов грассманиана имеет приложение в случайном сетевом кодировании. Модификация общего метода быстрой денумерации комбинаторных объектов Б. Я. Рябко может быть применена для разработки алгоритмов быстрой денумерации различных других комбинаторных объектов.

Реализация и внедрение результатов работы. Алгоритмы быстрого нумерационного кодирования комбинаторных объектов, разработанные в диссертационной работе, были использованы лабораторий вычислительных технологий ИВТ СО РАН для кодирования и декодирования сигналов при исследовании свойств волоконных оптических линий передачи данных с целью увеличения их пропускной способности.

Результаты работы внедрены в учебный процесс в Сибирском государственном университете телекоммуникаций и информатики на кафедре «Прикладная математика и кибернетика»:

— курс «Специальные методы кодирования источников» (аспирантура) по специальности 01.01.09 «Дискретная математика и математическая кибернетика» дополнен темой «Коды с ограничениями»,

— курс «Теория информации» (аспирантура) по специальности 01.01.09 «Дискретная математика и математическая кибернетика» дополнен темой «Коды с ограничениями»,

— курс «Специальные разделы теории передачи информации» (аспирантура) по специальности 05.12.13 «Системы, сети и устройства телекоммуникаций» дополнен темой «Коды с ограничениями»,

— курс «Специальные разделы теории передачи информации» (аспирантура) по специальности 05.12.13 «Системы, сети и устройства телекоммуникаций» дополнен темой «Коды с ограничением на длины серий: нумерационный подход».

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

мерово, 2008); международной конференции IEEE International Symposium on Information Theory (г. Сеул, Южная Корея, 2009); XI Международном семинаре «Дискретная математика и ее приложения» (г. Москва, 2012); международной конференции XIII International Symposium on Problems of Redundancy in Information and Control Systems (г. Санкт-Петербург, 2012); XIV Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (г. Томск, 2013).

Основные результаты использованы при выполнении следующих проектов и государственных программ:

— проект Федеральной целевой программы «Разработка теоретико-информационных методов оценки и повышения производительности компьютерных систем и сетей передачи данных», государственный контракт №01201361537,

— проект Федеральной целевой программы «Эффективные методы построения защищенных высокоскоростных каналов передачи цифровых данных для предоставления доступа к широкополосным мультимедийным услугам», государственный контракт №01201361538.

Публикации и личный вклад автора. По теме диссертации опубликованы 13 работ, в том числе 4 статьи — в изданиях, рекомендованных ВАК для представления основных результатов диссертации на соискание ученой степени доктора или кандидата наук, 5 — в сборниках и трудах международных и всероссийских конференций, 4 — в свидетельствах о регистрации программ. В совместных работах разработка вычислительных алгоритмов и интерпретация полученных результатов, включенных в диссертацию, принадлежат автору.

Структура и объем. Работа состоит из введения, четырех глав, заключения, списка литературы из 61 наименования и приложения. Объем диссертации составляет 113 страниц. Работа содержит две таблицы.

Содержание диссертации

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

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

ваемых в работе, приводятся известные общие методы нумерации комбинаторных объектов.

В § 1.1 описаны задача нумерации и денумерации комбинаторных объектов в общем виде и для рассматриваемых классов комбинаторных объектов.

В § 1.1.1 формулируется задача нумерации и денумерации комбинаторных объектов в общем виде. Задача нумерационного кодирования в общем виде состоит в следующем: дан некоторый алфавит А и множество S слов длины п > 1, являющееся подмножеством всех слов длины п, состоящих из букв алфавита А. Метод нумерационного кодирования должен по данному слову w £ S вычислять его номер codes(w), т. е. число из промежутка [0, |5| — 1]. Причем номер codes{w) записывается в двоичном виде и имеет длину [log |5|] бит. Все слова codes{w) должны быть различными при разных w € S. Метод нумерационного декодирования должен по данному номеру слова codes(w), т. е. числу из промежутка [0, — 1], записанному в двоичном виде и имеющему длину [log |5|] бит, находить слово w € S.

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

Последовательности называются «^-последовательностями, если длина любой серии нулей между единицами не меньше d и не больше к. Если, кроме этого, длина серии единиц между началом последовательности и первым нулем не больше I, а длина серии единиц между последним нулем и концом последовательности не больше г, то такая последовательность называется сШг-последовательностью. Перечислим в качестве примера все последовательности длины п = 5 с ограничением d = 0, к = 1, т. е. такие двоичные последовательности длины 5, в которых две единицы не могут идти подряд: 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10001, 10010, 10100, 10101.

Алгоритм нумерации ставит в соответствие слову из множества S dklr-слов длины п с заданными ограничениями d, к, I, г его номер, т. е. двоичное число из промежутка [0, — 1]. Алгоритм денумерации выполняет обратное действие, т. е. восстановление слова по его номеру.

В § 1.1.3 формулируется задача нумерации и денумерации слов языков Дика и дается обзор работ, в которых рассматривается эта задача.

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

все последовательности длины 6 правильно вложенных скобок одного типа:

((())). (00), (0)0, 0(0), ООО-

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

2т его номер, т. е. двоичное число из промежутка [0, \D2m\ - 1]. Алгоритм денумерации выполняет обратное действие, т. е. восстановление слова по его номеру.

В § 1.1.4 формулируется задача нумерации и денумерации элементов грас-сманиана и дается обзор работ, в которых рассматривается эта задача.

Пусть Fq — конечное поле размера q. Грассманианом называется множество всех /с-мсрных подпространств векторного пространства F™, обозначаемое Gq(n,k), для любых fc и п, 0 < к < п. Нумерационным кодированием элементов грассманиана Gq(n, к) является сопоставление каждому элементу грассманиана его номера, т. е. двоичного слова из промежутка [0, \Gq(n, fc)| — 1].

В § 1.2 рассматриваются известные общие методы нумерации комбинаторных объектов.

В § 1.2.1 описывается общий метод нумерации Т. Ковера, имеющий сложность 0(п) битовых операций на одну нумеруемую букву, где п — длина нумеруемого слова.

В работе Т. Ковера (Cover Т. Enumerative source encoding // IEEE Transactions on Information Theory. 1973. T. 19. №1. C. 73-77) был предложен общий метод нумерации слов. Пусть задано S С Ап — множество слов длины п из букв некоторого алфавита А с заданным на нем порядком. Номер слова w = х\... хп из заданного множества слов S длины п, упорядоченного лексикографически, можно найти по формуле

п

codes(w) = Ns(xix2 • • - Xj-\x), (!)

¿=1 x<Xi

где Ns(x\x2 ■ ■ ■ Xi-ix) — количество слов множества S, начинающихся с Х\Х2 ■ • • Xi-lX-

В § 1.2.2 описывается общий метод нумерации комбинаторных объектов Б. Я. Рябко, имеющий сложность 0(log тг log qmax log(n log qmax) log log(n log qmax)) битовых операций на одну нумеруемую букву, где п — длина нумеруемого слова.

В работе Б. Я. Рябко (Рябко Б. Я. Быстрая нумерация комбинаторных объектов) был предложен общий быстрый метод нумерации слов. Определим

величины P(xi\xi... rcj_i), q(xi\x\... а^) при 0 < г <

п

т>, ч Ns(xi) и, | ч Ns(x ix2...xi)

Р[Хi) = , P{Xi\XiX2 . . . Xi-1) = 4

Ns{X\X2 ■ ■ ■ Xi-l)

q(xi) = X]q(xi\xi ■ ■ • ^-i) = Y1 pbc\xi ■ ■ ■ x^ (2)

Можно видеть, что, согласно (1), справедливо

codes(x i...xn) = \S\{q{x{) + q{x2\xi)P{xi) + q{xz\xix2)P{x2\xi)P(xi) + ...).

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

codes(x i...xn) = |5|((g(xi) + q(x2\x1)P(x1)) + ((q(x3\x1x2)+

+Ф412Г! . . . X3)P{X3\X1X2))P(X2\X1)P(X1)) +...). (3)

Определим величины pjj, Ag при 0 < a < logn, 1 < b < n/2a следующим образом:

Рь = Р(хь\х 1... xb-1), A° = q{xb\xi... xb-i),

Рь = Plb-iPib\ К = ASL1! + Pib-.Kb1- (4)

Тогда AiosW = {{q{Xl) + ^^(m)) + ((g(x3|x1x2) +

q(x4\xi.. .x3)P(x3\xix2)) ■ P(x2\xi)P(xi)) + ...). Отсюда и из (3) вытекает

codes{x\x2 ... хп) = А1"8" |5|.

Алгоритм заключается в том, что сначала находятся значения P(xi\xi... Xi-i), q(xi\xi... Xi-x) при 0 < г < п, определенные в (2), после этого находится А1"®" последовательным вычислением значений Ag при 0 < а < logn, 1 < b < п/2а по формулам (4) и затем находится искомый номер codesiw) по формуле (), при этом значение |5| находится до начала нумерации и используется затем при всех последующих нумерациях. Обозначим через qmax максимальный знаменатель дробей Ns{xix2.. .Xi)/Ns{xix2.. .Xi-i), Xi... хп € S, г = 1 При

использовании алгоритма быстрого умножения Шенхаге—Штрассена, для которого М(п) = 0(п log п log log п), сложность нумерации равна O(lognlogq'mallog(nlogg'mox)loglog(nloggmal)) на одну букву кодируемого

В главе 2 построены быстрые алгоритмы нумерации и денумерации слов языков Дика.

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

В работе И. Либееншеля (Liebehenschel J. Ranking and unranking of lexicographically ordered words: an average-case analysis //Journal of Automata, Languages and Combinatorics. 1997. T. 2. №4. C. 227-268) предложен алгоритм нумерации слов языков Дика, основанный на методе Ковера. Обозначим через множество слов языка Дика над алфавитом, состоящим из 2т букв, длины п. Для простоты опишем алгоритм на примере слов над алфавитом, состоящим из двух букв. Для того чтобы использовать формулу (1) для нумерации слов множества нужно определить, чему равны значения Ищ (xi... хг) при 0 < i < п. Существует известное взаимнооднозначное соответствие между словами языка Дика из скобок одного типа, состоящими из п букв, и так называемыми путями Дика, непрерывными ломаными, состоящими из векторов (1, 1) и (1, —1), начинающимися в точке (0, 0) и заканчивающимися в точке (п, 0). Соответствие между путем Дика и словом языка Дика устанавливается следующим образом: вектору (1, 1) сопоставляется открывающая скобка, а вектору (1, —1) закрывающая скобка. Можно видеть, что существует соответствие между словами языка Дика, состоящими из п букв, начинающимися на х\... Xi и непрерывными ломаными, состоящими из векторов (1, 1) и (1, —1), начинающимися в точке (г, 2z — г) и заканчивающимися в точке (п, 0), где 2 — количество открывающих скобок в Х\Х2 Количество таких ломаных равно (n - i)\(2z - г + 1))/((п/2 - г)! (n/2 -i + z + 1)!, отсюда

д г ! \ (тг — i)\(2z — г +1)

ND,(X1X2 ...Xi) = r—i-- J 5

(n/2 — z)\(n/2 — i + z + 1)!

где z — количество открывающих скобок в х^х2 ... xt, при том, что xix2 ... Х{ может быть началом слова, соответствующего последовательности правильно вложенных скобок длины п. Если Х\Х2 ... х^ не может быть началом слов, соответствующих последовательности правильно вложенных скобок длины п, то, очевидно, ... Х{) = 0. При применении метода Ковера использу-

ется вспомогательная таблица, в которой хранятся все возможные значения Ndi{x\x2 ... Xi-ix) или все возможные значения X < XiNo^x\Х2 ... Xi-i\), 0 < i < п. Эта таблица строится один раз и затем используется для всех последующих поисков номера слов множества DВ случае множества

достаточно таблицы, в которой каждой паре г, 0 < г < тг, и z, 0 < л < г, сопоставляется значение (5). Размер такой таблицы равен 0(п3). Для получения номера слова w € по формуле (1) для каждого г, 0 < г < п, такого, что х, = 1, находится значение z, равное количеству открывающих скобок в слове х\... Xi-10, затем с помощью таблицы находится соответствующее паре гиг значение Nдг (х\... ж;), после этого складываются все найденные значения Nd^ (xi ... Xi). Для такого вычисления требуется совершить максимум п операций сложения слов длин от 1 до п. Таким образом, если использовать вспомогательную таблицу, сложность вычисления номера слова по методу Ковера равна 0(п2) или 0(п) битовых операций на один символ нумеруемого слова. Объем требуемой памяти составляет 0(п3) битов.

В § 2.2 построен быстрый алгоритм нумерации слов языков Дика над алфавитом {0, 1}. Построенный алгоритм имеет сложность О (log3 п log log п) на одну букву кодируемого слова длины п.

Для нумерации слов языков Дика длины п над алфавитом из двух букв применяется быстрый общий метод нумерации Б. Я. Рябко. При этом значения P(xi\xi... х^i) (0 < г < п) находятся следующим образом:

i l] l 2-- если Х{ = 1.

Мощность находится по следующей формуле:

\D2n\ =Сп = Сп'2 - Сп/2~1. Сложность

кодирования слова длины п языка Дика над алфавитом из двух букв равна 0(logпМ(пlog n)/n) (где М(п) время умножения двух слов длины п) битовых операций на одну букву кодируемого слова. При использовании алгоритма быстрого умножения Шенхаге—Штрассена, имеющего сложность М{п) = п log п log log п, сложность на одну кодируемую букву равна О (log3 п log log п). Объем памяти, требуемый для кодирования слова длины п языка Дика над алфавитом из двух букв, равен 0(п logп) бит.

В § 2.3 описана модификация общего метода денумерации Б. Я. Рябко и предлагается основанный на ней быстрый алгоритм денумерации слов языков Дика над алфавитом {0, 1}. Построенный алгоритм имеет сложность 0(log3nloglogn) на одну букву кодируемого слова длины п.

В § 2.4 построен быстрый алгоритм нумерации слов языков Дика над алфавитом мощности 2т. Построенный алгоритм имеет сложность 0(log3nloglogn) на одну букву кодируемого слова длины п.

В § 2.5 предлагается быстрый алгоритм денумерации слов языков Дика над алфавитом мощности 2т. Построенный алгоритм имеет сложность О (log3 п log log п) на одну букву кодируемого слова длины п.

В §2.6 приводятся выводы к главе 2.

В главе 3 строятся быстрые алгоритмы нумерации и денумерации элементов грассманиана.

В § 3.1 приведен известный метод нумерации элементов грассманиана, имеющий сложность 0(n3 log гг log log п) битовых операций на один нумеруемый элемент грассманиана Gq(n, к).

В работе Н. Зильберштейн, Т. Этциона (Silberstein N., Etzion Т. Enumerative coding for Grassmannian space) предложен алгоритм нумерации элементов грассманиана. Алгоритм основывается на методе Ковера. Любое к-мерное подпространство X 6 Gq(n, к) может быть представлено в виде матрицы кхп, строки которой составляют базис X. Такую матрицу кхп назовем матрицей ступенчатого вида по строкам, если соблюдены следующие условия: старший коэффициент каждой строки находится правее старшего коэффициента предыдущей, все старшие коэффициенты имеют значение 1, каждый старший коэффициент является единственным ненулевым элементом в своем столбце. Каждое подпространство X можно представить в виде единственной матрицы ступенчатого вида по строкам RE(X). Каждое fc-мерное подпространство X € Gq(n,k) имеет вектор идентификации v(X) — вектор длины п, состоящий из нулей и единиц, имеющий вес к, позиции единиц в котором совпадают с номерами столбцов, в которых находятся старшие коэффициенты RE(X). Расширенное представление подпространства X, обозначаемое ЕХТ(Х) является матрицей (к -f 1) х тг, верхней строкой которой является вектор идентификации v(X) = (v(X)n,... ,v(X)i), а оставшейся частью — матрица ступенчатого вида по строкам, представляющая X:

EXT(X)=(V-vm.

\ Лп ... X2 Ai J

Можно рассматривать матрицу ЕХТ(Х) как слово длины п над алфавитом, буквами которого являются векторы длины /с +1 над конечным полем размера q. При этом первой буквой этого слова будем считать первый столбец матрицы справа, второй буквой — второй столбец матрицы справа и т. д. Пусть х — вектор длины г над конечным полем размера q, равный (xi,x2,. ■ ■ ,хг). Обозначим через {ж} значение азд7"-1 + x2qT~2 + • • • + xTq°, т. е. число, которому равен вектор х, если рассматривать его как число в д-ичной систе-

ме исчисления. Зададим на алфавите, буквами которого являются векторы длины к + 1 над конечным полем размера д, порядок следующим образом: вектор х меньше вектора у, если {а:} < {у}. Множество слов, которые являются расширенными представлениями элементов Сч{п, к) обозначим через ЕХТ{(Зч(п,к)). Известно, что мощность грассманиана Сч{п, к) равна ,

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

- 1

4 г=0 *

Обозначим через у^ значение элемента У(Х){. Обозначим вес первых ]

элементов вектора v(X), т. е. w. странство, для которого

, = VJ

Ya=\vi- Пусть X € Gq{n,k) — подпро-

ЕХТ(Х) =

V2 Vi Х-1 Х\

Обозначим его номер среди элементов Сд(п, к), расположенных в лексикографическом порядке, через 1ехт(Х). Тогда справедливо следующее равенство:

1ехт(Х) = + (1 - )

3=1

п - J к — Wj-1

(6)

Алгоритм нумерации элементов грассманиана представляет собой вычисление номера элемента грассманиана по формуле (6). При этом гауссовские п-з

коэффициенты

к — Wj-i

3 = п, по формулам:

, 1 < j < п, предлагается вычислять, начиная с

О

к - w„-1

= 1,

п-з

к — Wj-i

-U +1)

к — Wj -ti + l) к — wj

J, если Wj = Wj. 1,

если Wj = Wj-i + 1.

Описанный алгоритм имеет вычислительную 0(пк(п — к) log п log log п) битовых операций.

сложность

На практике в сетевом кодировании выбираются такие значения п и к, что отношение п/к не зависит от п, т. е., на практике используется значение к = 0(п). Для таких значений пик сложность вычисления номера элемента грассманиана Gq(n, к) с помощью описанного алгоритма составляет О (п3 log п log log n).

В § 3.2 построен быстрый алгоритм нумерации элементов грассманиана. Построенный алгоритм имеет сложность 0(п2 log2 п log log п) битовых операций на один нумеруемый элемент грассманиана Gq(n,k).

Для нумерации элементов грассманиана Gq(n,k) применяется быстрый общий метод нумерации Б. Я. Рябко.

При этом значения Р{хi\xi... q{xi\x\... Xi-i) (0 < i < n) находятся

следующим образом:

) ( vi I vi-1 — "J "1 \_

I Xj Xj-1 ... X2 X\ J

,»->+1-1 I

если Vj = 0, если Vj = 1,

/ Vj I Vj_! ... V2 Vi

\ Xj-i ... X2 Xi J

q

• 1 g„_j+1_1—, если Vj = 1, если Vi = 0,

где Vi значение элемента ^ | есть д-ичный гауссовский коэффициент,

определяемый следующим образом:

9-1

М-п

- 1 ■ „в*"'"-1'

a wi — вес первых i элементов вектора v(X), т. е. u>i = YH=ivi-

Сложность кодирования элемента грассманиана Gq(n,k) равна 0(log пМ(п2)) битовых операций, где М(п) время умножения двух слов длины п. При использовании алгоритма быстрого умножения Шенхаге— Штрассена, для которого М(п) = п log п log log п, сложность нумерации равна 0(п2 log2 п log log п). Объем памяти, требуемый для нумерации элемента грассманиана Gq(n,k) равен 0{п2 log п) бит.

В § 3.3 предложен быстрый алгоритм денумерации элементов грассманиана. Построенный алгоритм имеет сложность О (п2 log2 п log log п) битовых операций на один денумеруемый элемент грассманиана Gq(n,k).

Алгоритм основан на модификации метода быстрой денумерации Б. Я. Рябко, описанной в § 2.2.

В §3.4 приводятся выводы к главе 3.

В главе 4 построены быстрые алгоритмы нумерации и денумерации слов с ограничениями на длины серий единиц.

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

В работе В. Каутца (Kautz W. Fibonacci codes for synchronization control) предложен метод нумерации слов с ограничениями на длины серий единиц. Например, для нумерации слов длины тг, в которых не встречаются серии из двух и более единиц (т. е. с ограничениями d = 0, к = 1), каждой из п позиций слова ставится в соответствие вес позиции, который находится следующим образом: для i-й позиции при i = 1, ..., п (позиции нумеруются справа налево) вес позиций равен (г + 1)-му числу Фибоначчи. Номер находится следующим образом: складываются веса тех позиций, в которых в нумеруемом слове находится единица. Например, если п = 5, то первому месту будет соответствовать ^2 = 1, второму — F-j = 2, третьему — = 3, четвертому —

= 5, пятому — Fq = 8. Находим номер слова 01001 следующим образом: складываем веса первой и четвертой позиций, т. к. в этих позициях находится единица. Получаем номер слова: ЛГ=1 + 5 = 6 = 0110г. Сложность кодирования и декодирования одной буквы данного метода равна 0(п) битовых операций. Объем памяти зависит полиномиально от длины слова, т. к. необходимо хранить п чисел, являющихся весами позиций и имеющих длину п бит. Идея алгоритмов в других работах по этой теме похожа.

В §4.2 построен быстрый алгоритм нумерации слов с ограничениями на длины серий единиц. Построенный алгоритм имеет сложность 0{п log3 тг log log п) битовых операций на одну букву кодируемого слова длины п.

Обозначим через S^kir множество двоичных слов длины гг, имеющих заданные ограничения d, к, I, г. Опишем алгоритм нумерационного кодирования слова w множества Sdkir- Для описания введем некоторые обозначения. Обозначим через 0 < L < I длину серии единиц в начале слова. Обозначим через 0 < R < г длину серии единиц в конце слова. Отбросим серию из L единиц слева, серию из R единиц и предваряющий ее ноль справа. Полученное слово можно единственным образом разделить на последовательность подслов

вида (01... 1), (1 < г < к. Обозначим через С*, <1 < г < к количество по-

лученных подслов вида (01... 1). Для нумерации нам потребуется таблица,

которая вычисляется один раз и затем используется при кодировании и декодировании. Таблица строится следующим образом: находятся все возможные для слов множества Баыг наборы {Ь, Я, Са, Са+1, • • • Ск)- Как можно видеть, возможными такие наборы будут при выполнении условий 0 < Ь < I, 0 < Я < г, Ь + СС1-((1+1) + Сс1+1-{(1+2) + --- + Ск-(к+1) + 1 + 11 = п. Обозначим через М(Ь, Я, Са, Са+1, ■ ■ ■, С к) подмножество слов множества Баыг, соответствующих набору (¿, Я, Са, Са+1, ..., Ск)- Справедливо равенство

|М(Ь, Я, С* Сл+ь ..., С7к)| = (Са + + • • • + Ск)\/{СЛ\ ад ... Ск\).

Каждая строка таблицы соответствует одному из возможных наборов (Ь, Я, С л, Са+1, ..., С к)- Возможные наборы при этом расположены в лексикографическом порядке. Первые к — ¿+ 3 элементов каждой строки — это значения Ь, Я, С а, Са+1, • • •, Ск- Последний элемент строки, который мы обозначим через К(Ь, Я, С^, Са+1, ... С^), вычисляется следующим образом. Для первой строки этот элемент равен нулю. Для остальных строк элемент равен сумме К{Ь, Я, Са, Са+1, Ск) и \М{Ь, Я, Са, Са+1, Ск)|, где значения Ь, Я, Са, Са+ь ..., Ск и К{Ь, Я, С а, Са+ь . • •, Ск) берутся из предыдущей строки таблицы.

Перейдем к описанию нумерации данного слова. Для нумеруемого слова находятся значения Ь < I, Я < г, Са, Са+1, ■ ■ ■, С к- По таблице находится значение К(Ь, Я, Са, Са+1, -■-, Ск), соответствующее найденному набору. При поиске значений С а, Са+1, •••> Ск из нумеруемого слова получили последовательность подслов вида (0 1... 1), <1 < г < к. Получаем из этой по-

следовательности слово алфавита А = {аа, аа+1,..., а^}, которое обозначим через а, заменив входящие в него подслова (0 1... 1), (0 1... 1), ..., (0 1... 1)

буквами аа, аа+1, ..., ак соответственно. Обозначим А(с^см,...,ск) множество слов алфавита А, состоящих из Са букв аа, Са+1 букв аа+1, ..., Ск букв

С помощью метода нумерации Б. Я. Рябко получаем номер слова а среди слов множества А^сл,см.....Ск)• При этом величины Р(хг\х\... Хг-1) при

0 < г < Са + Са+1 + ■ ■ ■ + Ск находятся следующим образом:

к

Р{Хг\х1...Х1-1) =

С/ - 771/ + 1

Са + Са+1 + --- + Ск-1+1'

где I — такое число, что Xi является буквой а/ алфавита А, а т^, rrid+ ъ ■■•> тк — количество букв a,i, а^+ъ ..., аь соответственно, содержащихся в префиксе х\ ...Х{. Складывая полученные значения K{L, R, Cd, Cd+i, ..., С\) и codeji(Cdcd+l ct)(a)' получаем номер слова w.

Сложность кодирования слов длины п с заданным количеством единиц на одну кодируемую букву равна О (log пМ(п log п)/п) битовых операций, где М(п log п) время умножения двух слов длины nlogn. При использовании алгоритма быстрого умножения Шенхаге—Штрассена, для которого М(п) = тг log п log log п, сложность нумерации равна О (log'1 п log log п). Объем памяти, требуемый для кодирования слова длины п с ограничениями на длины серий единиц d, к, I, г, равен О (nlogn) бит.

В § 4.3 предложен быстрый алгоритм денумерации слов с ограничениями на длины серий единиц. Построенный алгоритм имеет сложность 0(п log3 п log log п) битовых операций на одну букву кодируемого слова длины п.

В §4.4 приводятся выводы к главе 4.

В заключении приведены основные результаты.

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

Основные заключения и выводы

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

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

3. Разработан быстрый алгоритм нумерационного кодирования элементов грассманиана Gq(n, к), то есть множества всех ¿-мерных подпространств векторного пространства над конечным полем размера q. Сложность нумера-

ции и денумерации элементов грассманиана меньше, чем у ранее известных алгоритмов, и составляет 0(тг2 log2 n log log п). Ранее известные алгоритмы имеют сложность О (пл log п log log п).

4. Разработана модификация общего метода быстрой денумерации комбинаторных объектов Б. Я. Рябко.

Публикации автора по теме диссертации

Публикации в ведущих рецензируемых журналах:

1. Медведева, Ю. С. Быстрый алгоритм нумерации слов с заданными ограничениями на длины серий единиц / Ю. С. Медведева, Б. Я. Рябко // Проблемы передачи информации. — 2010. — Т. 46. — №4. — С. 130-139.

2. Медведева, Ю. С. Быстрая нумерация элементов грассманиана / Ю. С. Медведева // Вычислительные технологии. — 2013. — Т. 18. №3. — С. 22-33.

3. Медведева, Ю. С. Быстрый алгоритм нумерационного кодирования для основных задач теории информации / Ю. С. Медведева // Вестник СибГУТИ. - 2013. - № 14. - С. 83-105.

4. Медведева, Ю. С. Быстрая нумерация слов, порождаемых грамматиками Дика / Ю. С. Медведева // Математические заметки. — 2014. — Т. 96. — №1. - С. 51-69.

Публикации в сборниках и трудах конференций, свидетельства о регистрации программ для ЭВМ:

5. Медведева, Ю. С. Быстрый алгоритм нумерации слов с заданными ограничениями на длины серий единиц / Ю. С. Медведева // Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям — Кемерово, 2008.

6. Ryabko, В. Fast enumeration of run-length-limited words / В. Ryabko, Y. Medvedeva // IEEE International Symposium on Information Theory ISIT 2009. - IEEE, 2009. - C. 640-643.

7. Медведева, Ю. С. Быстрая нумерация элементов грассманиана / Ю. С. Медведева // Материалы XI Международного семинара «Дискретная математика и ее приложения». — Москва, 2012.

8. Medvedeva Y. Fast enumeration for Grassmannian space / Y. Medvedeva // 2012 XIII International Symposium on Problems of Redundancy in Information and Control Systems (RED). - IEEE, 2012. - C. 48-52.

9. Медведева, Ю. С. Быстрый алгоритм нумерационного кодирования для основных задач теории информации / Ю. С. Медведева // XIV Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. — Томск, 2013.

10. Программа для быстрой денумерации слов с заданным к-ограничением на количество подряд идущих единиц. Свидетельство о регистрации программы для ЭВМ №2013618963 от Федеральной службы по интеллектуальной собственности, патентам и товарным знакам.

11. Программа для быстрой нумерации слов с заданным к-ограничением на количество подряд идущих единиц. Свидетельство о регистрации программы для ЭВМ №2013618964 от Федеральной службы по интеллектуальной собственности, патентам и товарным знакам.

12. Программа для быстрой нумерации слов с заданным с!к1г-ограничением на количество подряд идущих единиц. Свидетельство о регистрации программы для ЭВМ №2013619199 от Федеральной службы по интеллектуальной собственности, патентам и товарным знакам.

13. Программа для быстрой денумерации слов с заданным <1к1г-ограничением на количество подряд идущих единиц. Свидетельство о регистрации программы для ЭВМ №2013619198 от Федеральной службы по интеллектуальной собственности, патентам и товарным знакам.

Медведева Юлия Сергеевна

Быстрая нумерация комбинаторных объектов, находящая применение в системах передачи и хранения информации

Автореферат диссертации на соискание ученой степени кандидата

технических наук

Формат 60x90/16 Тираж 100 экз. Подписано в печать 17.07.2015 Заказ № 2873 Типография «АИрппЬ 8 (383) 214-59-16 630004, г. Новосибирск, Вокзальная магистраль, 3