Быстрая нумерация комбинаторных объектов, находящая применение в системах передачи и хранения информации тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Медведева, Юлия Сергеевна

• Медведева, Юлия Сергеевна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Медведева, Юлия Сергеевна

Оглавление

Введение

1 Постановка задачи и известные общие методы

1.1 Задача нумерации и денумерации комбинаторных объектов

1.1.1 Задача нумерации и денумерации комбинаторных объектов в общем виде

1.1.2 Нумерация слов с ограничением на длины серий единиц

1.1.3 Нумерация слов языков Дика

1.1.4 Нумерация элементов грассманиана

1.2 Известные общие методы нумерации комбинаторных объектов

1.2.1 Метод Т. Ковера

1.2.2 Метод Б. Я. Рябко

2 Нумерация слов языков Дика

2.1 Известный алгоритм нумерации слов языков Дика

2.2 Быстрый алгоритм нумерации слов языка Дика над алфавитом {0,1}

2.3 Быстрый алгоритм денумерации слов языка Дика над алфавитом {0,1}

2.4 Быстрый алгоритм нумерации слов языков Дика над алфави-

том мощности 2т

2.5 Быстрый алгоритм денумерации слов языков Дика над алфавитом мощности 2т

2.6 Выводы

3 Нумерация элементов грассманиана

3.1 Известный алгоритм нумерации элементов грассманиана

3.2 Быстрый алгоритм нумерации элементов грассманиана

3.3 Быстрый алгоритм денумерации элементов грассманиана

3.4 Выводы

4 Нумерация ¿Шг-последовательностей

4.1 Известный алгоритм нумерации сШг-последовательностей

4.2 Быстрый алгоритм нумерации ¿Шг-последовательностей

4.3 Быстрый алгоритм денумерации сШг-последовательностей

4.4 Выводы

Заключение

Список литературы

Приложение А

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

Введение

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

Актуальность темы исследования. Задача нумерационного кодирования в общем виде состоит в следующем: дан некоторый алфавит А и множество 5 слов длины п > 1, являющееся подмножеством всех слов длины п, состоящих из букв алфавита А. Метод нумерационного кодирования должен по данному слову ии £ 5 вычислять его номер 000163(1^), т. е. число из промежутка [0, |5| — 1]. Причем номер сос1е5{и)) записывается в двоичном виде и имеет длину 15|] бит. Все слова сос1ез(и)) должны быть различными при разных и> Е Метод нумерационного декодирования должен по данному номеру слова сойез{и1), т. е. числу из промежутка [0, \3\ — 1], записанному в двоичном виде и имеющему длину |£|] бит, находить слово т е 5. Задача построения быстрых алгоритмов нумерации и денумерации имеет практическую и теоретическую значимость в кодировании данных на носителях и в каналах, имеющих ограничения, связанные с физическими свойствами носителя или канала, а также в сетевом кодировании и других областях теории

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

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

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

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

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

RLL-коды, в их общей форме, разрабатывались в 60-70 гг. в работах [20], [21], [22], [23], [24], [25], [26], [27]. RLL-коды продолжают вызывать интерес исследователей, в последние годы им было посвящено множество статей, таких как [28], [29], [30], [31], [18], [19]. RLL-коды являются основой всех появившихся в последнее время дисковых стандартов хранения информации, таких как CD, DVD, BlueRay Disc.

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

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

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

Необходимость быстрой нумерации и денумерации слов языков Дика воз-

пикает при работе трансляторов языков высокого уровня, для сжатия последовательностей правильно вложенных скобок и случайной генерации последовательностей правильно вложенных скобок [17], [14], [15].

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

Нумерационные коды и алгоритмы генерации слов языков Дика рассматривались в работах [34], [35].

Нумерация элементов грассманиана. Пусть ^ — конечное поле размера ц. Грассманианом называется множество всех ^-мерных подпространств векторного пространства обозначаемое к), для любых к и п, 0 < к < п. Нумерационным кодированием элементов грассманиана Сч(п, к) является сопоставление каждому элементу грассманиана его номера. Алгоритм денуме-рации выполняет обратное действие, т. е. восстановление слова по его номе-

ру. Задача быстрой нумерации элементов грассманиана имеет практическую значимость в сетевом кодировании. Эта задача рассматривалась во многих работах в течении последних сорока лет, например в работах [36], [37], [38], [39], [40], [41], [42]. В работе [43] показано, как можно использовать коды с исправлением ошибок на множестве элементов грассманиана в случайном сетевом кодировании. Это приложение привело к появлению множества работ в данной области: [44], [45], [46], [47], [48], [49], [50], [51], [52], [53], [54], [55].

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

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

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

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

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

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

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

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

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

Научная новизна. 1. Разработан новый быстрый алгоритм нумерационного кодирования двоичных слов длины п, имеющих ограничения на длины серий единиц. Сложность нумерации и денумерации слов в разработанном алгоритме меньше, чем у ранее известных алгоритмов, и равна 0(log3nloglogn) битовых операций на одну букву слова. Ранее известные алгоритмы имеют линейную сложность нумерации и денумерации. Алгоритм получен на основе метода нумерации комбинаторных объектов Б. Я. Рябко [57].

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

горитмы, известные ранее, имеют сложность 0(n3 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 работы — в изданиях, рекомендованных ВАК для представления основных результатов диссертации на соискание ученой степени доктора или кандидата наук [1], [2], [3], [4], 5 работ — в сборниках и трудах международных и всероссийских конференций [5], [6], [7], [8], [9], 4 работы — в свидетельствах о регистрации программ [10], [11], [12], [13].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

операций на один нумеруемый элемент грассманиана Gq(n, к).

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

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

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

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

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

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

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

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

Глава 1

Постановка задачи и известные общие методы

1.1 Задача нумерации и денумерации комбинаторных объектов

1.1.1 Задача нумерации и денумерации комбинаторных объектов в общем виде

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

т. е. числу из промежутка [0, l-S*! — 1], записанному в двоичном виде и имеющему длину [log l^l] бит, находить слово w € S. Задача построения быстрых алгоритмов нумерации и денумерации имеет практическую и теоретическую значимость в кодировании данных на носителях и каналах, имеющих ограничения, связанные с физическими свойствами носителя или канала, а также в сетевом кодировании; ей посвящены сотни статей и несколько монографий.

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

1.1.2 Нумерация слов с ограничением на длины серий единиц.

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

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

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

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

RLL-коды в их общей форме разрабатывались в 60-70 гг. в работах [20], [21], [22], [23], [24], [25], [26], [27]. RLL-коды продолжают вызывать интерес исследователей, в последние годы им было посвящено множество работ, таких как [28], [29], [30], [31], [18], [19]. RLL-коды являются основой всех появившихся в последнее время дисковых стандартов хранения информации, таких как CD, DVD, BlueRay Disc.

1.1.3 Нумерация слов языков Дика.

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

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

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

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

Необходимость быстрой нумерации и денумерации слов языков Дика возникает при работе трансляторов языков высокого уровня, для сжатия последовательностей правильно вложенных скобок и случайной генерации последовательностей правильно вложенных скобок [17], [14], [15].

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

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

Нумерационные коды и алгоритмы генерации слов языков Дика рассматривались в работах [34], [35].

1.1.4 Нумерация элементов грассманиана.

Пусть Рч — конечное поле размера q, где д — степень простого числа. Грас-сманианом называется множество всех /г-мерных подпространств векторного пространства обозначаемое к), для любых целых к и п, 0 < к < п. Нумерационным кодированием элементов грассманиана С9(п, к) является сопоставление каждому элементу грассманиана его номера, т. е. двоичного слова из промежутка [0, |(39(п, к) | — 1].

Эта задача рассматривалась во многих работах в течении последних сорока лет, например, в работах [36], [37], [38], [39], [40], [41], [42]. В работе [43] показано, как можно использовать коды с исправлением ошибок на множестве элементов грассманиана в случайном сетевом кодировании. Это прило-

Список литературы диссертационного исследования кандидат наук Медведева, Юлия Сергеевна, 2015 год

Список литературы

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

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

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

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

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. Программа для быстрой нумерации слов с заданным dklr-ограничением на количество подряд идущих единиц. Свидетельство о регистрации программы для ЭВМ №2013619199 от Федеральной службы по интеллектуальной собственности, патентам и товарным знакам.

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

14. Альфред, В. Компиляторы: принципы, технологии и инструменты / В. Альфред, Р. Сети, Д. Д. Ульман. — М.: Вильяме, 2001.

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

16. Шень, А. Программирование: теоремы и задачи / А. Шень. — М.: Издательство Московского центра непрерывного математического образования, 1995.

17. Комбинаторные алгоритмы: Теория и практика: Пер. с англ / Э. М. Рейнгольд, Ю. Нивергельт, Н. Део и др. — М.: Мир, 1980.

18. Курмаев, О. Ф. Кодирование последовательностей с ограниченными длинами серий / О. Ф. Курмаев // Проблемы передачи информации.— 2001. - Т. 37. — № 3. — С. 34-43.

19. Курмаев, О. Ф. Нумерационное кодирование последовательностей с ограничениями на длины серий нулей и вес / О. Ф. Курмаев // Проблемы передачи информации. — 2002. — Т. 38. — № 4. — С. 3-9.

20. Berkoff, М. Waveform compression in nrzi magnetic recording / M. Berkoff // Proceedings of the IEEE. — 1964. — T. 52. - № 10. — C. 1271-1272.

21. Freiman, C. V. Optimum block codes for noiseless input restricted channels /

C. V. Freiman, A. D. Wyner // Information and Control. — 1964. — T. 7. — № 3.- C. 398-415.

22. Kautz, W. Fibonacci codes for synchronization control / W. Kautz // Information Theory, IEEE Transactions on. - 1965. - T. 11. - № 2. - C. 284-292.

23. Gabor, A. Adaptive coding for self-clocking recording / A. Gabor // Electronic Computers, IEEE Transactions on. - 1967. - № 6. - C. 866-868.

24. Shaft, P. Bandwidth compaction codes for communications / P. Shaft // Communications, IEEE Transactions on. — 1973. - T. 21. — № 6. — C. 687-695.

25. Tang, D. T. Block codes for a class of constrained noiseless channels /

D. T. Tang, L. R. Bahl // Information and Control.- 1970,- T. 17.-№ 5.- C. 436-461.

26. Tang, D. T. Run-length-limited coding for modified raised-cosine equalization channel / D. T. Tang // US Patent 3,647,964.- 1972.

27. Franaszek, P. A. Sequence-state coding for digital transmission / P. A. Franaszek // Bell System Technical Journal. — 1968. — T. 47. - № 1. -C. 143-157.

28. Beenker, G. A generalized method for encoding and decoding run-length-limited binary sequences (corresp.) / G. Beenker, K. Immink // Information Theory, IEEE Transactions on. - 1983. - T. 29. — № 5. - C. 751-754.

29. Mansuripur, M. Enumerative modulation coding with arbitrary constraints and postmodulation error correction coding for data storage systems /

M. Mansuripur // Optical Data Storage / International Society for Optics and Photonics. - 1991. - C. 72-86.

30. Datta, S. An enumerative method for runlength-limited codes: permutation codes / S. Datta, S. W. McLaughlin // Information Theory, IEEE Transactions on. - 1999. - T. 45. — № 6. - C. 2199-2204.

31. Milenkovic, O. Permutation (d, k) codes: efficient enumerative coding and phrase length distribution shaping / O. Milenkovic, B. Vasic // Information Theory, IEEE Transactions on. - 2000. - T. 46. - № 7. - C. 2671-2675.

32. Alonso, L. Random generation of trees: random generators in computer science / L. Alonso, R. Schott. — Springer, 1994.

33. Barcucci, E. Random generation of trees and other combinatorial objects / E. Barcucci, A. Del Lungo, E. Pergola // Theoretical Computer Science.— 1999. - T. 218. - № 2. - C. 219-232.

34. Liebehenschel, J. Lexicographical generation of a generalized dyck language / J. Liebehenschel // SIAM Journal on Computing. — 2003. — T. 32. — № 4. — C. 880-903.

35. Liebehenschel, J. Ranking and unranking of lexicographically ordered words: an average-case analysis / J. Liebehenschel // Journal of Automata, Languages and Combinatorics. — 1997. — T. 2. — № 4. — C. 227-268.

36. Knuth, D. E. Subspaces, subsets, and partitions / D. E. Knuth // Journal of Combinatorial Theory, Series A. - 1971.- T. 10,- № 2, — C. 178-180.

37. Thomas, S. Designs over finite fields / S. Thomas // Geometriae Dedicata. — 1987. - T. 24. - № 2. - C. 237-242.

38. Martin, W. J. Anticodes for the grassman and bilinear forms graphs / W. J. Martin, X. J. Zhu // Designs, Codes and Cryptography.— 1995.— T. 6. — № 1. — C. 73-79.

39. Thomas, S. Designs and partial geometries over finite fields / S. Thomas // Geometriae Dedicata. - 1996. - T. 63. - № 3. - C. 247-253.

40. Ahlswede, R. On perfect codes and related concepts / R. Ahlswede, H. K. Ay-dinian, L. H. Khachatrian // Designs, Codes and Cryptography. — 2001.— T. 22. - № 3. - C. 221-237.

41. Schwartz, M. Codes and anticodes in the grassman graph / M. Schwartz, T. Etzion // Journal of Combinatorial Theory, Series A. — 2002.— T. 97,— № 1.- C. 27-42.

42. Braun, M. Systematic construction of q-analogs of t-(v, k, A)-designs / M. Braun, A. Kerber, R. Laue // Designs, codes and Cryptography. — 2005. — T. 34. — № 1.— C. 55-70.

43. Koetter, R. Coding for errors and erasures in random network coding / R. Koetter, F. R. Kschischang // Information Theory, IEEE Transactions on. - 2008. - T. 54. - № 8. - C. 3579-3591.

44. Xia, S. Johnson type bounds on constant dimension codes / S. Xia, F. Fu // Designs, Codes and Cryptography. — 2009. - T. 50.— № 2, — C. 163-172.

45. Etzion, T. Error-correcting codes in projective space / T. Etzion, A. Vardy // Information Theory, IEEE Transactions on.- 2011,- T. 57.- № 2.— C. 1165-1173.

46. Manganiello, F. Spread codes and spread decoding in network coding / F. Manganiello, E. Gorla, J. Rosenthal // Information Theory, 2008. ISIT 2008. IEEE International Symposium on / IEEE. - 2008. - C. 881-885.

47. Silva, D. A rank-metric approach to error control in random network coding / D. Silva, F. R. Kschischang, R. Koetter // Information Theory, IEEE Transactions on. - 2008. - T. 54. - № 9. - C. 3951-3967.

48. Silva, D. On metrics for error correction in network coding / D. Silva, F. R. Kschischang // Information Theory, IEEE Transactions on. — 2009,— T. 55. - № 12. - C. 5479-5490.

49. Gadouleau, M. Constant-rank codes and their connection to constant-dimension codes / M. Gadouleau, Z. Yan // Information Theory, IEEE Transactions on. — 2010. — T. 56. — № 7. — C. 3207-3216.

50. Gadouleau, M. On the decoder error probability of bounded rank-distance decoders for maximum rankdistance codes / M. Gadouleau, Z. Yan // Information Theory, IEEE Transactions on. - 2008. - T. 54. - № 7. - C. 3202-3206.

51. Gadouleau, M. Construction and covering properties of constant-dimension codes / M. Gadouleau, Z. Yan // Information Theory, 2009. ISIT 2009. IEEE International Symposium on / IEEE. — 2009. — C. 2221-2225.

52. Etzion, T. Error-correcting codes in projective spaces via rank-metric codes and ferrers diagrams / T. Etzion, N. Silberstein // Information Theory, IEEE Transactions on. - 2009. - T. 55. - № 7. — C. 2909-2919.

53. Kohnert, A. Construction of large constant dimension codes with a prescribed minimum distance / A. Kohnert, S. Kurz // Mathematical Methods in Computer Science. — Springer, 2008, — C. 31-42.

54. Skachek, V. Recursive code construction for random networks / V. Skachek // Information Theory, IEEE Transactions on.— 2010,— T. 56.— № 3,— C. 1378-1382.

55. Silberstein, N. Enumerative coding for grassmannian space / N. Silberstein, T. Etzion // Information Theory, IEEE Transactions on. — 2011. — T. 57. — № 1.- C. 365-374.

56. Van Lint, J. H. A Course in Combinatorics. 2001 / J. H. Van Lint, R. M. Wilson. — Cambridge: Cambridge University Press.

57. Рябко, Б. Я. Быстрая нумерация комбинаторных объектов / Б. Я. Рябко // Дискретная математика,— 1998.— Т. 10.— № 2.— С. 101-119.

58. Cover, Т. Enumerative source encoding / Т. Cover // Information Theory, IEEE Transactions on. - 1973. - T. 19. - № 1. — C. 73-77.

59. Schönhage, D. Schnelle multiplikation grosser zahlen / D. Schönhage, V. Strassen // Computing. - 1971, — T. 7. — № 3-4, — С. 281-292.

60. Fiirer, M. Faster integer multiplication / M. Fiirer // SI AM Journal on Computing. - 2009. - T. 39. - № 3. - C. 979-1005.

61. Knuth, D. E. The art of computer programming / D. E. Knuth. — Pearson Education, 2005.