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

Курмаев Олег Феатьевич

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

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

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

7 ДПР 2011

Москва - 2011

4841955

Работа выполнена в Московском государственном институте электронной техники (Национальном исследовательском университете).

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

доктор технических наук, профессор В. А. Кустов

Официальные оппоненты:

доктор физико-математических наук, профессор

Дьячков Аркадий Георгиевич

кандидат физико-математических наук Лебедев Владимир Сергеевич

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

Санкт-Петербургский государственный университет аэрокосмического приборостроения

Защита состоится « 2011 г. и часов на заседании

1.0(6.077.

диссертационного совета Д.002.077.01 при Институте проблем передачи информации им. А. А. Харкевича РАН, расположенном по адресу: 127994, г. Москва, ГСП-4, Большой Каретный переулок, д. 19, стр. 1

С диссертацией можно ознакомиться в библиотеке ИППИ РАН.

Автореферат разослан « » _2011 г.

Ученый секретарь

диссертационного совета Д.002.077.01, доктор физико-математических наук

Цитович И. И.

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертационной работы докладывались на российских и международных конференциях: 1) 7th International Workshop оп Algebraic and Combinatoriai Coding Theory (ACCT-7), Bansko, 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), Zveni-gorod, Russia, September 3 - 9, 2006. 4) 7th East-West Design & Test Symposium (EWDTS 2009), Moscow, Russia, September 18 - 21, 2009.

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

Публикации. По теме диссертации опубликовано семь печатных работ — [1—7] общим объёмом 2,9 п.л. Из них три работы — [2, 4, 7], общим объёмом 2,5 п.л, в реферируемом журнале из перечня ВАК.

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

Содержание работы

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

В первой главе вводится определение двоичных последовательностей с ограничениями на длины серий нулей: Двоичная последовательность х е {0,1}п длины п, в которой две соседние единицы разделены серией нулей, имеющей длину не менее d и не более к, называется последовательностью с (d, к) - ограничениями на длины серий нулей. Чтобы эти ограничения не нарушались на стыках блоков при блоковом кодировании, вводятся дополнительные ограничения: I - на максимальную длину первой серии нулей и г -на максимальную длину последней серии нулей. Такая последовательность называется последовательностью с (d, к, 1,г) - ограничениями на длины серий нулей. Двоичные (d,k,l,r) - последовательности, начинающиеся с единицы, будем называть последовательностями с (d, к, г) - ограничениями.

Для изложения результатов далее понадобятся следующие обозначения и определения. Обозначим через У множество последовательностей с (d, к, г) -ограничениями, а через — множество последовательностей с (d,k,l,r) -ограничениями. Пусть на S? установлен лексикографический порядок. Тогда под нумерацией будем подразумевать определение номера данной последовательности в упорядоченном списке = {ха < < ■ ■ ■ < Дену-мерация — это отображение целого числа N, 0 < N < \Уп\ — 1, задающего номер в списке, в соответствующую последовательность из Уп. Нумерацию и денумерацию будем называть нумерационным кодированием.

Общий алгоритм нумерационного кодирования был .описан в работах Бабкина1 и Ковера 2. Он опирается на подсчёт числа последовательностей, предшествующих данной последовательности х = (х\}. ..,х„) в установленном лексикографическом порядке, посредством определения числа последовательностей W(p), имеющих префикс р =■ (xi,... ,ij_i,0). Временная сложность этого алгоритма зависит от сложности вычисления весовых коэффициентов W(p), но не ниже 0(п). При этом метод Бабкина и Ковера подразумевает произвольную сложность вычисления W(p) от 0(1) до 0(2").

Далее в первой главе показано, что если весовой коэффициент разряда не зависит от префикса р, то он не зависит и от разрядности п, а зависит только от ограничений (d,k,l,r) и позиции разряда j, отсчитываемой от разряда "с наименьшим весом, т. е. сложность вычисления весовых коэффициентов есть константа. При этом нумерация и денумерация сводится к поразрядному уравновешиванию. Порядок следования разрядов в последовательности при поразрядном уравновешивании изменён на обратный, принятый при записи в позиционной системе счисления, т. е. разряду с меньшим весом соответствует меньший номер. Вес очередного разряда при этом wn = \Уп-\\, что позволяет применять для нахождения этих величин те же рекуррентные формулы, что и для метода Ковера.

Емкостная сложность алгоритма поразрядного уравновешивания составляет 0(п).

Возможность использования поразрядного уравновешивания с использованием фиксированного набора весов wn и смещений (порогов) /п определяется следующими теоремами:

Теорема 1. Всякой последовательности х = (хп,xn-i,...,€ Уп можно поставить во взаимно-однозначное соответствие целое неотрицательное число N(x) 6 [0, \Уп\ — I], определяемое следующим образом:

п

N(x) = (i) ¿=i

для (d,k,r) - последовательностей и

Теорема 2. Всякой последовательности х = (x„,xn-i,... ,х{) 6 можно поставить во взаимно-однозначное соответствие целое неотрицательное число N(x) е [О, \Уп\ — 1), определяемое следующим образом:

¿=1

1 В. Ф. Бабкин. Метод универсального кодирования источника независимых сообщений неэкспоненциаль-

ной трудоемкости // Пробл. передачи информ. 1971. Т. 7, № 1. С. 13-21. '. 2 Т. М. Cover. Enumerative source coding // IEEE Trans. Inf. Theory. 1973. Jan. Vol. IT-19, no. 1. P. 73-77.

для (d,k,l,r) - последовательностей.

Доказательство теорем 1 и 2 основано на следующей лемме:

Лемма 1. Для любого N € [/;, +/» — !] : N - fi+k > 0, 1 < г < п, выполняются условия:

N-Wi- Oi_ 1 >0, 2 < г < 1 + (к + 1), N — щ — /¿_! > 0, l + (fc + l)<i<n

и

N-Wi- fi+k-(d-t) <0, 1 + d-t<i<n, 0 <t<d, где смещение /„ определяется рекуррентно как

/п-1 + fn~{d+\) ~ /n-l-(fc+l)> 1 + 2(fc + 1) < n, вес wn определяется как

„, _ / fn+k ~ ап+к, 1<п<1 + {к + 1), п {fn+k-fn-u 1 + (Ä + l)<n,

а величина ап, введённая в [1] учитывает наличие ограничения г следующим образом:

_ Г 0, п mod (fc + 1) < г + 1, йп ~ \ 1, п mod (fc + 1) > г + 1.

Из теоремы 1 и уравнения (1) следует, что алгоритмы нумерации и де-нумерации (d,k,l,r) - последовательностей, совпадают с алгоритмами Бала-Тонга3 нумерации и денумерации (d, к) - последовательностей.

Во второй главе вводятся двоичные последовательности с ограничениями на длины серий нулей, единиц и вес. Такие последовательности были впервые рассмотрены в 2002 году в [3]. Здесь потребовалось определение новых ограничений:

1. (¿А,кл) - ограничения: длина любой серии нулей между сериями единиц в ж не менее dа и не более кл\

2. (dß, kg) - ограничения: длина любой серии единиц между сериями нулей в а: не менее dg и не более кв',

3. левые (d^, fc^) - ограничения: длина серии нулей между началом последовательности и первой единицей в ж не менее ¿ьа и не более kiA', .

4. левые - ограничения: длина серии единиц между началом последовательности и первым нулём в ж не менее dbB и не более к^в',

3 D. Т. Tang, L. R. Bahl. Block Codes for a Class of Constrained Noiseless Channels // Inform, and Control. 1970. Vol. 17, no. 5. P. 436-461.

5. правые (с^Аи) * ограничения: длина серии нулей между последней единицей и концом последовательности х не менее <3дл и не более кцА\

6. правые (¿в, кв) - ограничения: длина серии единиц между последним нулём и концом последовательности х не менее с?дв и не более кцв-

Для множества этих ограничений введём обозначение ££ = {(¿л.Лл^д./сьд, ¿ла, кцл, с1в, кв, йьв, кьв, ¿лв, клв}.

Кроме того, для указанных последовательностей вводится ограничение на вес V = чт0 позволяет расширить приложение таких кодов как

для управления спектром, так и для обнаружения и исправления ошибок.

Обозначим через А£ число таких последовательностей, которые начинаются с серии нулей, для которой йьа — ¿л. = Обозначим через число таких последовательностей, которые начинаются с серии единиц, для которой ¿1в = йв, кьв = кв. Аналогичным образом, обозначим через число таких последовательностей, которые начинаются с серии нулей, определяемой ограничениями ¿ьа и к^А- Наконец, обозначим через В£ число таких последовательностей, которые начинаются с серии единиц, определяемой ограничениями йьв и к^в-

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

Число последовательностей А"п и определяется рекуррентно в соответствии с утверждениями 1 и 2, а именно:

Если был хоть один переход от серии единиц к серии нулей, или наоборот, то справедливы:

Утверждение' 1. Количество последовательностей А£ может быть определено следующим образом: Если V — 0, то

Н

в°= 1, В°=1, 1/ = п = 0.

А0 -

п —

1, ¿КА<П< кпд,

О, в противном случае.

Если и ф О, то

п < (1а, ¿а < п.

и

Утверждение 2. Количество последовательностей может быть определено следующим образом: Если V — п, то

¿яв <п< ккв, в противном случае.

В2 =

Если V -ф п, то

В1 =

О, п <

-лт.т(п,кв)

у-мтщплв; .V-} , <

Если идёт первая серия нулей, то справедливо

Утверждение 3. Количество последовательностей может быть определено следующим образом: Если V = О, то

А0 -

Т1 —

1, тах(с2£л, с^л) < п < тт(кЬА, кКА), О, в противном случае.

Если V то

\ 0, п < ¿1А,

Если идёт первая серия единиц, то справедливо

Утверждение 4. Количество последовательностей может быть определено следующим образом: Если V — п, то

К =

[ 1, та, ё,пв) < п < тт^ьв, кпв), I 0, в противном случае.

Если V фп, то

О, п < йьв,

При этом полагаем, что ¿а > 1, кА > 0, ¿1а > 1, > 0, йдл > 1, кцА >0, (1в> 1, кв > 0, бьв > 1, кьв > 0, (¿дв > 1 и кцв > 0.

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

Следствие 1. При любых возможных; ограничениях на длины серий и вес, весовые коэффициенты разрядов последовательности \¥%(х1,х2, ■ ■ ■ ...,Xj-l,0) зависят только от длины последовательности п, её веса и, элементов множества ограничений ££ \ {кьв}, позиции разряда (длины префикса) у и длины серии, непосредственно предшествующей разряду

В третьей главе рассматриваются двоичные последовательности с ограничениями на длины серий нулей, вес и или заряд а = где V] = Причём акцент сделан на получение явного вида для рекуррентных уравнений, определяющих число таких последовательностей, начинающихся с 1, с заданным весом — А"п или с заданным зарядом — :

Вначале положим, что существует единственная последовательность нулевой длины и нулевого веса, начинающаяся с 1. Тогда Лд = 1.

Далее, указанные рекуррентные соотношения определяются следующими утверждениями:

Утверждение 5. Количество последовательностей А£ может быть определено следующим образом: Если V — то

' 1, 1<п<г + 1, О, в противном случае.

А1 =

Если у>1, то

А"-]0, п < (2+1,

Утверждение 6. Количество последовательностей может быть определено следующим образом: Если а = —п, то

с-п= 11, п<г + 1,

Если а ^ — п, то

I 0, в противном случае.

О, п<й + 1,

с°п 7> <1+1 < п. (3)

При этом полагаем, что й > 0, к > й, г > 0.

Явный вид (2) определяет следующая лемма 2, которая доказывается индукцией по V.

Лемма 2. Число А£ равновесных последовательностей может быть явно выражено как

К = В-1Ж71) - ; „ > 1( (4)

з=о

где д = & - с! + 1.

Аналогичная лемма даёт явную формулу для вычисления в виде суммы 12 слагаемых с соответствующими знаками:

12

<£ = £(-i)L'/2JW

/=i

Обозначим эти слагаемые через С(7)£ и определим'их как

Г п+сг 1

I 2(d+l) | ,т-р п+а .

£ (Ей

т~0

j=0 т

(5)

j=0

где

Pi =

0, 1 = 1,2,7,8,

1, I = 3,4, [0, 7 = 1,3,5,7,9,11

-d, 1 = 5,6, P2 = < l + (r + l), 7 = 2,4,

(k + l)-d, 7 = 9,10, U 7 = 6,8,10,12,

(r + l)-d, 7 = 11,12,

М =

10, 1 = 1,2,3,4,

1,

7 = 5,6,7,8,9,10,11,12.

Явные выражения (4) и (5) стали основой для получения производящих функций, перечисляющих множества <1кг - последовательностей с ограничениями на вес или заряд. Существует два типа последовательностей А% и Бесконечные последовательности первого типа это Ад,^,... затем

СМ,... или ____Конечные последовательности второго типа это

А^,А1, ...,А" или С~п, С~п+2,..., С™. Колесник и Крачковский рассматривали4 рекурсивное вычисление производящей функции первого типа для пе-

4 V. D. Kolesnik, V. Yu. Krachkovsky. Generating Functions and Lower Bounds on Rates for Limited Error-Correcting Codes // IEEE Trans. Int. Theory. 1991. May. Vol. IT-37, no. 3. P. 778-788.

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

Рассмотрим бесконечную последовательность А%,____Определим

производящую функцию для этой последовательности как

оо

Av{t) = J2Antn>

п=0

Подставляя сюда явное выражение (4) для А^ и изменяя порядок суммирования, получаем производящую функцию в замкнутой форме.

Рассмотрим конечный степенной ряд

п

i/=l ;

Подставляя сюда выражение (6), .получаем производящую функцию двух переменных t и у. Далее потребуется n-кратное дифференцирование по t с помощью интегральной формулы Коши для производных, затем применение теоремы о полной сумме вычетов даёт

к+2 Tr+1 _ 1

т=1, тфз

где ть т2.....тк+2 корни 1 - т - yrd+1 + утк+2, причём тг = 1.

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

00 со

Ca(í) = Y^ Cntn/2> или Ca{t) = C^(n_1)/2, t 6 M. (7)

n=0 n= 1 '

n even n odd

Попытка получить (7) в замкнутом виде предполагает подстановку (5) с последующим изменением порядка суммирования, что ранее позволило

5 P. Lee. Combined Error-Correcting/Modulation Recording Codes: Dr. scient, thesis // University of California. San Diego, 1988. Mar.

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

* = х е М. (8)

х +1

Лемма 3. Производящая функция

может быть выражена в интегральной форме:

Лй+1)

2к+и+1 2жг

í-11 Г£4-1Уе+"

(С - х)"+1

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

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

¿¿+1 +к+2 Ь<1 = -¿К—IV и Ък ~ '

2(1-*) 2(1-*)'

Поскольку мы ввели (8), то теперь мы установим аналогичное отображе-

! на всей комплексной плоскости, а именно, положим г =

Попытка получить замкнутое выражение для (7) дала следующий резуль-

тат:

= (ТТ^7М + ——^---•

где и обозначают следующие интегралы:

Л,4 =

- 6

(—1)" Г ТГ-Р1+Р2

2тг

Я

Ь (9)

X | — | | СОЭ (п(р) — (1 — р,тч) ап (пу) ]

г] * " - )

14

X

Щ соэ (гир) - (1 - ц вт (п<р) 1

где, в свою очередь,

1р = — агссоэ

2 «2 - 1)

это фаза, а

п =

сг-рх +р2 Я.

есть число членов в конечных рядах, которые образуются при переходе к упомянутому выше диагональному суммированию. Далее Е\ и Я2 определяются как

Ро,...,Ра это многочлены степени 2 от комплексной переменной

Ро = £-х-{Ьл + Ьк) (£2-1),

Р^е-аг-^-Ь*)

Р2 ~ — х ~ {Ьк — Ьц) (£2 — 1), •

= £-х- (У(1 - + Ьь) (е - 1),

р4=$ - ® - (ьа+ък (1 - ) (е -1),

Пределы интегрирования есть корни выражения под радикалом в (11).

2 (У^ + УЬ)2_'

2 {^Лн — у/Ьк)2

Я^мРг+т^Рз, Я2 = д(</г)9Р2 + Р4,

а знаменатели <2 и Л это

УР02 -4ЬА(е2-!)2-

(11)

Теперь можно сформулировать наиболее важный результат диссертационной работы:

Теорема 3. Рекуррентное соотношение вида (3) не имеет замкнутой формы.

Доказательство следует из того факта, что интегралы (9) и (10) суть эллиптические, что в свою очередь следует из анализа (11) в заданных пределах интегрирования.

Производящая функция последовательности С~п, С~п+2, имеет за-

мкнутую форму.

Рассмотрим конечный ряд

Сп(у) = £ C„V/2 или Сп(у) = £ Cj-W,

а——п сг=—74

a even a odd

где у еШ.

Здесь также вместо С£ рассматривается (5). По аналогии с (8) следует положить у = Результат есть выражение

п+(<т mod 2)

Сп{у) = (71)П"И-Иу- 2

X (х - l)»-»+1(i + l)1"^ ((1 - М) Jl + J2) , где х переопределена как

1 + 2/ •

х = 1-•

1-2/

Л и Ji обозначают здесь интегралы для которых получены замкнутые фор-

11

мы:

2(—1 - ж)"-г,1~Р2+1 2(1 -2(4+2)

2,+2)

3=1 й п

т=1,

" 6+1 ^-i V

иначе,

где

Н =

1л

иначе.

101 = 1,

а 6. • • •. Ь(к+2) есть корни

таты и сделаны выводы.

Основные результаты работы

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

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

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

- на вес;

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

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

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

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

ниями.

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

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

Список публикаций

1. О. Kurmaev. Weights Calculation for Enumerative Encoding of dkrl -Sequences // Proc. ACCT'2000. Bansko, Bulgaria, Jun. 18-24. 2000. P. 199-206.

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

3. О. Kurmaev. An enumerative method for encoding and decoding constant-weight run-length limited binary sequences // IEEE Intl. Symposium on Information Theory. Lausanne, Switzerland. Jun. 30 - Jul. 5. 2002. P. 328.

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

5. О. Kurmaev. Weight and charge distribution of binary run-length limited codes // Proceedings of Tenth International Workshop on Algebraic and Combinatorial Coding Theory. Zvenigorod, Russia. 2006. Sep. 3-9. 2006. P. 174-178.

6. O. Kurmaev. An Algorithm for Testing Run-Length Constrained Channel Sequences // Proc. EWDTS'2009. Moscow. - Russia. Sep. 18-21. 2009. P. 391-392.

7. О. Ф. Курмаев. Нумерация двоичных последовательностей с ограничениями на длины серий и вес // Пробл. передачи информ. 2011. Т. 47, № 1. С. 78-95.

Формат 60x84 1/16. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ № 36.

Отпечатано в типографии ИПК МИЭТ.

124498, Москва, Зеленоград, проезд 4806, д. 5, МИЭТ.

Введение

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

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

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

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

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

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

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

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

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

2.2. Определение числа последовательностей.

2.3. Вычисление весовых коэффициентов разрядов

2.4. Определение минимально и максимально возможного веса последовательности

2.5. Алгоритмы нумерации и денумерации

2.6. Выводы к главе

Глава 3. Двоичные последовательности с ограничениями на длины серий нулей, вес или заряд

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

3.2. Определение количества последовательностей.

3.3. Явный метод определения числа последовательностей

3.4. Производящие функции для перечисления (¿,к,г) - последовательностей с постоянным весом или постоянным зарядом.

3.5. Алгоритмы нумерации и денумерации (с1,к,1,г) - последовательностей с постоянным весом или зарядом

3.6. Замечания к главе

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

Актуальность работы. В течение последних 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. Разработаны алгоритмы нумерационного кодирования и декодирования исследуемых последовательностей.

1. К. A. S. 1.mink. Codes for Mass Data Storage Systems. 2 ed. Eindhoven, The Netherlands: Shannon Foundation Publishers, 2004.

2. K. A. S. Immink, P. H. Siegel, J. K. Wolf. Codes for digital recorders // IEEE Trans. Inf. Theory. 1998. V. 44, №. 6. P. 2260-2299.

3. К. Шеннон. Работы по теории информации и кибернетике. М.: Издательство иностранной литературы, 1963.

4. Р. Н. Siegel. Recording codes for digital magnetic storage // IEEE Trans. Magn. 1985. V. Mag-21, №. 5. P. 1344-1349.

5. P. A. Franaszek. Sequence-state Methods for Run-length-limited Coding // IBM J. Res. Dev. 1970. V. 14, №. 4. P. 376-383.

6. P. A. Franaszek. Run-Length-Limited Variable Length Coding with Error Propagation Limitation. U.S. Patent 3,689,899, Sep. 1972.

7. T. Horiguchi, K. Morita. On optimization of modulation codes in digital recording // IEEE Trans. Magn. 1976. V. Mag-12, №. 6. P. 740-742.

8. A. M. Patel. Zero-Modulation Encoding in Magnetic Recording // IBM J. Res. Dev. 1975. V. 19, №. 4. P. 366-378.

9. D. T. Tang, L. R, Bahl. Block Codes for a Class of Constrained Noiseless Channels // Inform, and Control. 1970. V. 17, №. 5. P. 436-461.

10. G. F. M. Beenker, K. A. S. Immink. A Generalized Method For Encoding and Decoding Run-Length-Limited Binary Sequences // IEEE Trans. Inf. Theory. 1983. V. IT-29, №. 3. P. 751-754.

11. П. И. Васильев, В. Д. Колесник. Коды с ограниченными длинами серий // Помехоустойчивое кодирование и надёжность ЭВМ / Под109ред. В. В. Зяблова; Академия наук СССР, Институт проблем передачи информации. М.: Наука, 1987. С. 95-109.

12. Н. С. Ferreira. Lower bounds on the minimum Hamming distance achievable with runlength constrained or DC-free block codes and the synthesis of a (16,8) dmin = 4 DC-free block code // IEEE Trans. Magn. 1984. V. Mag-20, №. 5. P. 881-883.

13. P. Lee. Combined Error-Correcting/Modulation Recording Codes: Dr. scient. thesis / University of California. San Diego, 1988.14. 0. Ytrehus. Codes for error control: Ph.D. thesis / University of Bergen. Norway, 1989.

14. K. A. S. Abdel-Ghaffar, J. H. Weber. Bounds and constructions for runlength-limited error-control block codes // IEEE Trans. Inf. Theory. 1991. V. IT-37, №. 3. P. 789-800.

15. P. P. Варшамов, Г. M. Тененгольц. Код, исправляющий одиночные не-симметрические ошибки // Автоматика и телемеханика. 1965. Т. 26, № 2. С. 288-292.

16. V. D. Kolesnik, V. Yu. Krachkovsky. Generating Functions and Lower Bounds on Rates for Limited Error-Correcting Codes // IEEE Trans. Inf. Theory. 1991. V. IT-37, №. 3. P. 778-788.

17. E. Zehavi, J. K. Wolf. On Runlength Codes // IEEE Trans. Inf. Theory. 1988. V. IT-34, №. 1. P. 45-54.

18. П. И. Васильев. Блоковое кодирование с ограниченными длинами серий для систем цифровой магнитной записи: Автореф. дис. канд. техн. наук: 05.13.01 / ЛИАП. Ленинград, 1991.

19. V. I. Levenshtein, A. J. Н. Vink. Perfect (d, к)-Codes Capable of Correcting Single Peak-Shifts 11 IEEE Trans. Inf. Theory. 1993. V. IT-39, №. 2. P. 656-662.

20. V. Braun, К. A. S. Immink. An Enumerative Coding Technique for DC-Free Runlength-Limited Sequences // IEEE Trans. Commun. 2000. V. 48, №. 12. P. 2024-2031.

21. H. Nyquist. Certain topics in telegraph transmission theory // Trans. AIEE. 1928. V. 47. P. 617-644.

22. E. Gorog. Redundant alphabets with desirable frequency spectrum properties // IBM J. Res. Dev. 1968. V. 12, №. 3. P. 234-241.

23. I. C. Mallinson, I. W. Miller. Optimal codes for digital magnetic recording // Radio Elec. Eng. 1977. V. 47. P. 172-176.

24. A. Gabor. Adaptive coding for self-clocking recording // IEEE Trans. Electron. Comput. 1967. V. EC-16, №. 6. P. 866-868.

25. G. L. Pierobon. Codes for zero spectral density at zero frequency // IEEE Trans. Inf. Theory. 1984. V. IT-30, №. 2. P. 435-439.

26. K. Norris, D. S. Bloomberg. Channel capacity of charge-constrained run-length limited codes 11 IEEE Trans. Magn. 1981. V. Mag-17, №. 6. P. 3452-3455.

27. K. A. S. Immink. Properties and Constructions of binary channel codes: Ph.D. thesis / Eindhoven University of Technology. The Netherlands, 1985.

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

29. В. Ф. Бабкин. Метод универсального кодирования источника независимых сообщений неэкспонендиальной трудоёмкости // Пробл. передачи информ. 1971. Т. 7, № 1. С. 13-21.

30. T. M. Cover. Enumerative source coding // IEEE Trans. Inf. Theory. 1973. V. IT-19, №. 1. P. 73-77.

31. T. J. Tjalkens. On the Principal State Method for Run-Length Limited Sequences // IEEE Trans. Inf. Theory. 1994. V. IT-40, №. 3. P. 934-941.

32. O. Kurmaev. An Algorithm for Testing Run-Length Constrained Channel Sequences // Proc. EWDTS'2009. Moscow. Russia. Sep. 18-21. 2009. P. 391-392.

33. J. P. M. Schalkwijk. An algorithm for source coding // IEEE Trans. Inf. Theory. 1972. V. IT-18, №. 3. P. 395-399.

34. D. E. Knuth. Efficient balanced codes // IEEE Trans. Inf. Theory. 1986. V. IT-32, №. 1. P. 51-53.

35. H. D. L. Hollmann, K. A. S. Immink. Performance of Efficient Balanced Codes /¡IEEE Trans. Inf. Theory. 1991. V. IT-37, №. 3. P. 913-918.

36. K. A. S. Immink. A Practical Method for Approaching the Channel Capacity of Constrained Channels // IEEE Trans. Inf. Theory. 1997. V. IT-43, №. 5. P. 1389-1399.

37. D. A. Huffman. A Method for the Construction of Minimum-Redundancy Codes 11 Proc. IRE. 1952. V. 40. P. 1098-1101.

38. O. Kurmaev. Weight and charge distribution of binary run-length limited codes // Proceedings of Tenth International Workshop on Algebraic and Combinatorial Coding Theory. Zvenigorod, Russia. 2006. Sep. 3-9. 2006. P. 174-178.

39. Дж. Риордан. Введение в комбинаторный анализ. М.: Изд-во иностр. лит-ры, 1963.

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

41. Г. Сегё. Ортогональные многочлены. М.: Гос. изд-во физ.-мат. литры, 1962.

42. М. Абрамовиц, И. Стиган. Справочник по специальным функциям с формулами, графиками и математическими таблицами. М.: Наука, 1979.

43. S. Shamai, E. Zehavi. Bounds on the capacity of the bit-shift magnetic recording channel // IEEE Trans. Inf. Theory. 1991. V. IT-37, №. 3. P. 863-872.

44. H. C. Ferreira, S. Lin. Error and Erasure Control (d, k) Block Codes // IEEE Trans. Inf. Theory. 1991. V. IT-37, №. 5. P. 1399-1408.

45. K. A. S. Immink. DC-Free Codes of Rate (n 1 )/n, n Odd // IEEE Trans. Inf. Theory. 2000. V. IT-46, №. 2. P. 633-634.

46. E. Gilbert. Synchronization of binary messages // IRE Trans. Inform. Theory. 1960. V. 6, №. 4. P. 470-477.

47. Y. Choi, W. Szpankowski. Pattern Matching in Constrained Sequences // IEEE Intl. Symposium on Information Theory (ISIT 2008). Toronto, Canada. Jul. 6-11. 2008. P. 2141-2145.

48. K. I. Kerpez, A. Gallopoulos, C. Heegard. Maximum entropy charge-constrained run-length codes // IEEE J. Sel. Areas Commun. 1992. V. SAC-10, №. 1. P. 242-253.