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

• Автор: Курмаев, Олег Феатьевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 114 с. : ил.

Содержание
Введение

Глава 1. Кодирование последовательностей с ограниченными длинами серий.

1.1. Предисловие

1.2. Последовательности с ограниченными длинами серий . .

1.3. Нумерация и денумерация

1.4. Поразрядное уравновешивание для ,с,г последовательностей .

1.5. Поразрядное уравновешивание для с,с,,г последовательностей .

1.6. Выводы к главе 1

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

2.1. Предисловие

2.2. Определение числа последовательностей
2.3. Вычисление весовых коэффициентов разрядов .
2.4. Определение минимально и максимально возможного веса последовательности .
2.5. Алгоритмы нумерации и денумерации .
2.6. Выводы к главе 2
Глава 3. Двоичные последовательности с ограничениями на длины серий нулей, вес или заряд
3.1. Предисловие
3.2. Определение количества последовательностей.
3.3. Явный метод определения числа последовательностей . .
3.4. Производящие функции для перечисления с1, к, г последовательностей с постоянным весом ИЛИ постоянным зарядом.
3.5. Алгоритмы нумерации и денумерации 1к,1,г последовательностей с постоянным весом или зарядом
3.6. Замечания к главе 3
3.7. Выводы к главе 3 .
Заключение
Литература


Расширение области применения кодов с ограничениями, например, на задачи многоканальной связи, также требует дополнительных исследований. Цель работы. Цель настоящей диссертации состоит о разработке и исследовании кодовой конструкции для последовательностей с ограничениями на длины серий, вес или заряд. Задачи исследования. Методы исследования. В качестве научного аппарата диссертационного исследования использовались методы дискретной математики, комбинаторного анализа, теории функций комплексного переменного, теории информации и кодирования, теории сложности алгоритмов. Экспериментальные исследования проводились с помощью численного моделирования в среде “Maple”, а также с использованием специальных программ, написанных автором на ANSI С. Научная новизна. Теоретическая и практическая ценность работы. Работа носит теоретический характер. Результаты исследований возможно распространить на помехоустойчивое кодирование канала, на получение оценок ёмкости и скорости кода, а также алгоритмической сложности кодирования. Отдельный интерес представляет взаимная рекурсия, полученная для определения числа двоичных последовательностей с ограничением на длины серий нулей и заряд. В частности, важно доказательство факта, что данная рекурсия не может быть выражена в замкнутой форме. Конструкции кодов, предложенные в данной работе, позволяют получить последовательности с заданными спектральными свойствами для применения в системах массовой памяти. Практическую ценность представляют также алгоритмы нумерационного кодирования данного класса кодов. Научные положения, выносимые на защиту. Апробация работы. Information Theory, Lausanne, Switzerland, June 6 - July 5, ; 3) th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-), Zvenigorod, Russia, September 3 - 9, . East-West Design & Test Symposium (EWDTS ), Moscow, Russia, September - , . Основные результаты работы неоднократно обсуждались и были одобрены на семинаре по теории кодирования Института проблем передачи информации РАН. Структура и объем диссертации. Диссертация состоит из введения, трёх глав, заключения и списка литературы из наименований. Общий объём работы составляет 4 страниц. Диссертация содержит 6 рисунков и таблиц общим объёмом 8 страниц. Во введении обоснована актуальность темы, сформулирована цель и определены задачи исследования, дано краткое изложение полученных результатов и содержание диссертации. Вводная часть первой главы — обзорная. В ней дано определение кодов с ограничениями на длины серий. Рассмотрена история метода нумерационного кодирования. Первая глава также содержит обзор важных публикаций по данной теме. Для блокового кодирования рассмотрены дополнительные стыковочные ограничения на границах блоков. В этой же главе дано определение метода нумерационного кодирования, рассмотрена нумерация и денумерация двоичных последовательностей с ограничениями на длины серий нулей с учётом стыковочных ограничений. Доказана возможность использования метода поразрядного уравновешивания для процедур нумерации и денумерации. Во второй главе вводится понятие двоичных последовательностей заданного веса с независимыми ограничениями на длины серий нулей и единиц. Рекуррентно определяется число таких последовательностей и строится таблица распределения последовательностей заданного веса. Далее, алгоритмы нумерации и денумерации из предыдущей главы модифицируются применительно к этим последовательностям. В третьей главе снова рассматриваются двоичные последовательности с ограничением на длины серий нулей, но вводятся дополнительные ограничения. Это ограничение на вес, аналогичное таковому из предыдущей главы. Для биполярного (т. N1^) образа последовательности вводится ограничение на накопленную сумму (заряд). Рекуррентно определяется число таких последовательностей с заданным весом и таких же последовательностей с заданным зарядом. На основе рекуррентных соотношений для определения числа последовательностей с заданным весом или зарядом, выводятся явные формулы. На основе явных формул, выводятся производящие функции, перечисляющие указанные последовательности.