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

Актуальность работы. В течение последних 30 лет мы являемся свидетелями революции в цифровой аудио и видео записи. Компакт-диск и DVD сделались предметом широкого потребления. Они стали стандартом де-факто для хранения и переноса значительных объёмов информации. Быстро растёт популярность дисковых массивов данных и сетевых хранилищ. Миллионы жёстких дисков круглосуточно вращаются в высокопроизводительных серверах, обеспечивая доступ половины населения Земли к сети Интернет. Все эти продукты массовой памяти были бы невозможны без применения передовых систем канального кодирования.

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

В 1965 г. американский специалист в области теории информации У. Каутц (W. Kautz) предложил нумерационную процедуру кодирования для канала с одним ограничением (d или к). В 1970 г. Д. Тонг (D. Tang) и JI. Бал (L. Bahl) распространили идею Каутца на кодирование канала с (d, к) — ограничениями. В 1971 г. В. Ф. Бабкин, затем в 1973 г. Т. Ковер (Т. Cover) предложили универсальную схему нумерационного кодирования для источников. Метод Бабкина и Ковера оказался чрезвычайно удачным и, благодаря усилиям таких учёных как К. Имминк (К. A. S. Immink), В. Д. Колесник, Ч. Шалкенс (Т. Tjalkens), Ф. Браун.

V. Braun), позволил дополнительно ввести стыковочные ограничения (Z, г) и стал активно применяться для блокового кодирования каналов с (d, k, l, r) — ограничениями.

Этот метод дал начало многочисленным теоретическим исследованиям в области кодирования последовательностей с ограничениями. Кроме того, он позволил распространить существующие достижения, полученные для кодирования источника на кодирование канала с (d, к) -или (d, k, l, r) — ограничениями. Нумерационная техника явно показала комбинаторную природу этого канала. Она позволила получить рекуррентные уравнения и производящие функции для перечисления последовательностей с ограничениями, что в свою очередь, дало возможность изучать асимптотику и получать оценки для канала.

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

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

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

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

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

• выделить и рассмотреть специальные классы ограничений, а именно:

— ограничения на длины серий и вес;

— ограничения на длины серий нулей и накопленный заряд;

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

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

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

Научная новизна. Научная новизна диссертации заключается в том, что в ней впервые:

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

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

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

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

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

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

Научные положения, выносимые на защиту. На защиту выносятся следующие положения:

• кодирование двоичных последовательностей с к, I, г) — ограничениями на длины серий нулей с линейной трудоёмкостью;

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

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

• нумерационные алгоритмы кодирования и декодирования последовательностей с ограничениями.

Апробация работы. Результаты диссертационной работы докладывались на российских и международных конференциях: 1) 7th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-7), Ban-sko, Bulgaria, June 18 — 24, 2000; 2) IEEE International Symposium on Information Theory, Lausanne, Switzerland, June 6 — July 5, 2002; 3) lOth International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-10), Zvenigorod, Russia, September 3 — 9, 2006. 4) 7th East-West Design & Test Symposium (EWDTS 2009), Moscow, Russia, September 18 — 21, 2009.

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

Структура и объем диссертации

Диссертация состоит из введения, трёх глав, заключения и списка литературы из 56 наименований. Общий объём работы составляет 114 страниц. Диссертация содержит 6 рисунков и 16 таблиц общим объёмом 8 страниц.

3.7. Выводы к главе 3.

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

Заключение

.

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

1. Известный для кодирования (с£, к) — последовательностей метод Бала-Тонга с двумя наборами весовых коэффициентов, имеющий линейную вычислительную сложность, распространён на кодирование к, 1, г) — последовательностей при сохранении линейной трудоёмкости.

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

3. Для (с1,к, г) — и (с1,к, 1, г) — последовательностей расширен класс ограничений, а именно введены дополнительные ограничения:

• на вес;

• на накопленный заряд.

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

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

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

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

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