«Ф. И. Соловьева ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ Учебное пособие Рекомендовано учебно-методическим Советом по математике и механике УМО по классическому университетскому образованию в качестве учебного пособия для ...»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Механико-математический факультет

Ф. И. Соловьева

ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ

Учебное пособие

Рекомендовано учебно-методическим Советом по математике и механике УМО

по классическому университетскому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности “010100 Математика” Новосибирск 2006 2 УДК 519.725(075) ББК з-811.4 я 73-1 С603 Соловьева Ф. И. Введение в теорию кодирования: Учебное пособие / Новосиб.

гос. ун-т. Новосибирск, 2006. с. 127.

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

Рецензенты проф., д-р техн. наук В. В. Зяблов, ИППИ РАН д-р физ.-мат. наук С. А. Малюгин, ИМ СО РАН c Новосибирский государственный университет, c Ф. И. Соловьева Введение Коды возникли в глубокой древности фактически с появлением системы знаков для записи звуков, слов, информации, которые позднее развились в различные языки. Каждый язык представляет собой сложную систему кодирования, включая в свою конструкцию алфавит, слова, грамматику. Язык позволяет в окружающем шуме передавать информацию по возможности быстро, надежно, с достаточно высокой степенью избыточности.

Позднее появились (еще до нашей эры) криптограммы (по-гречески криптограмма – тайнопись). Такими кодами пользовались для засекречивания сообщений. Уже в V в. до н. э. знаменитый греческий историк Геродот приводил примеры писемкриптограмм, понятных только одному адресату. Спартанцы имели специальный механический прибор, при помощи которого записывались сообщения–криптограммы, позволяющие сохранить тайну. Собственную секретную азбуку имел Юлий Цезарь (широко известный шифр Цезаря). В Средние века и эпоху Возрождения над изобретением тайных шифров работали многие выдающиеся умы, в том числе философ Фрэнсис Бэкон, математики Франсуа Виет, Джероламо Кардано. Криптографией занимались в монастырях, при дворах королей. Вместе с искусством шифрования сообщений развивалось и искусство их дешифрования. Многие оптимистично полагали, что вряд ли существует такая криптограмма, которую нельзя разгадать. И только в прошлом веке Клод Шеннон (1949 г.) показал, что существует совершенно секретный шифр – шифр Вернама, называемый также лентой однократного действия или шифром-блокнотом.

В настоящее время теория кодирования имеет важное широкое практическое применение как средство экономной, удобной, быстрой, а также надежной передачи сообщений по линиям связи с различного вида шумами (телефон, телеграф, радио, телевидение, компьютерная, космическая связи и т. д.). Подлинный взрыв развития теории связи начался в послевоенные годы, с 1948–1949 гг., с появлением классических работ Клода Шеннона и Норберта Винера. Труды Н. Винера были порождены исследованиями военного времени по автоматическому управлению огнем, труды К. Шеннона знаменитые "Математическая теория связи" и "Связь при наличии шума" – исследованиями по шифрованию сообщений и их передачи по секретным каналам связи. Математические модели Н. Винера и К. Шеннона довольно сильно различались: сигнал по Н. Винеру может обрабатываться после воздействия шумом, по К. Шеннону сигнал можно обрабатывать как до, так и после передачи по каналу связи с шумами. В силу этого и других различий, Винеровские труды легли в основу теории автоматического управления, Шенноновские труды оказались основополагающими для задач эффективного использования каналов связи. Таким образом, с 1949 г., с фундаментальных работ К. Шеннона, началось бурное развитие теории кодирования как отдельной научной дисциплины, а также развитие таких тесно с нею связанных научных дисциплин, как сжатие информации и криптология.

В настоящем курсе лекций рассматриваются блоковые коды, предназначенные для исправления случайных ошибок в каналах связи с шумами, в основном будет изучаться модель двоичного симметричного канала связи, хотя многие результаты без труда могут быть обобщены для кодов над q-значными алфавитами. Мы только коснемся определений некоторых других типов ошибок. В курсе лекций будет изложена теория линейных кодов, в частности теория q-значных циклических кодов, имеющих широкое применение на практике для передачи сообщений в каналах связи с шумами, доказана известная теорема Шеннона о существовании хороших кодов в двоичных симметричных каналах связи с шумами, предложены различные методы построения кодов (среди них – свитчинговые и каскадные методы), а также рассмотрены известные классы кодов, таких как коды Рида – Маллера, Адамара, совершенные коды, коды Рида – Соломона, коды Юстесена, Препараты. При подготовке пособия были использованы источники [1–25].

Основные понятия и определения Пусть E n обозначает n-мерное метрическое пространство всех двоичных векторов длины n с метрикой Хэмминга (см. ниже примеры двумерных проекций E n при малых n на рис. 1 и общепринятую модель E n для произвольного n на рис. 2).

Произвольное подмножество C пространства E n называется двоичным кодом длины n, элементы кода называются кодовыми словами.

Хэммингово расстояние d(x, y) между векторами x, y E n определяется как число координат, в которых эти векторы различаются. Нетрудно показать, что оно является метрикой. Кодовое расстояние равно минимальному расстоянию Хэмминга между различными кодовыми словами.

Вес Хэмминга w(x) произвольного вектора x E n равен числу ненулевых координат x, т. е. w(x) = d(x, 0n ), где 0n – нулевой вектор длины n. Обозначим через 1n единичный вектор длины n (иногда далее длины нулевого и единичного векторов указываться не будут, но из контекста всякий раз будет ясно, какова их длина).

Множество называется носителем вектора x.

Известно, что группа автоморфизмов Aut(E n ) пространства E n исчерпывается подстановками на множестве координат и добавлением произвольного вектора v E n, т. е. для группы автоморфизмов Aut(E n ) пространства E n справедливо где – полупрямое произведение, Sn – симметрическая группа подстановок длины n.

Два кода – C и D – длины n называются эквивалентными, если существует автоморфизм (v, ) пространства E n, отображающий один код в другой, т. е. v + (C) = D.

Группа автоморфизмов Aut(C) произвольного кода C длины n состоит из всех автоморфизмов пространства E n, переводящих код в себя, т. е.

Множество называется группой симметрий кода C. Очевидно, что Sym(C) изоморфна подгруппе группы Aut(C).

Линейным (или групповым) кодом называется подмножество E n, являющееся линейным подпространством (подгруппой) в E n. Аналогично, линейным q–значным коn дом называется линейное подпространство n–мерного метрического пространства Eq всех векторов длины n с метрикой Хэмминга над полем Галуа GF (q), q = pk, q 2, где p–простое число (такой код может не являться групповым в Eq ).

В дальнейшем параметры линейного кода C длины n с кодовым расстоянием d будем обозначать через [n, k, d], где k – размерность кода; для нелинейного кода C параметры будем обозначать через (n, |C|, d).

Линейный код длины n называется циклическим, если для любого кодового слова (x1, x2,..., xn ) слово (x2,..., xn, x1 ) также является кодовым.

Для полноты изложения в дальнейшем некоторые из приведенных определений будут повторены.

Упражнение 1. Доказать, что расстояние Хэмминга является метрикой, а E n метрическим пространством:

а) d(x, y) 0, причем d(x, y) = 0 x = y (аксиома тождества);

б) d(x, y) = d(y, x) (аксиома симметрии);

в) d(x, y) + d(y, z) d(x, z) (аксиома треугольника) для x, y, z E n.

Упражнение 2. Найти число вершин и ребер в E n, Eq.

Упражнение 3. Найти число вершин:

а) в сфере радиуса r в E n, Eq ;

б) в шаре радиуса r в E, Eq.

Двоичный симметричный канал связи Пусть по каналу связи с шумом пересылаются двоичные сообщения из Новосибирска в Москву. Рассмотрим случай, когда входной алфавит A совпадает с выходным алфавитом B и равен {0, 1}. Пусть при посылке 0 принимается как 0, а 1 как 1, но иногда 0 может быть принят как 1 или 1 принята как 0. Пусть в среднем один из каждых 1 000 символов будет ошибочным. Это означает, что для каждого символа имеется вероятность p = 1/1 000 того, что в канале связи произойдет ошибка, т. е.

для переходных (условных) вероятностей P (|), где A P (|) = 1, имеем В данном случае переходные вероятности образуют симметричную матрицу и посему такая модель называется двоичным симметричным каналом связи. Сообщения должны передаваться как можно быстрее, экономнее и надежнее. Будем записывать сообщения в виде последовательностей из нулей и единиц. Закодируем эти сообщения в целях защиты их от ошибок, которые могут произойти в канале связи. Входная информация разбивается на блоки длины k. Каждый блок из k символов сообщения преобразуется кодером в слово x длины n :

Полученные слова образуют двоичный код и называются кодовыми словами. Схематично это представлено на рис. 3.

Рис. 3. Классическая схема системы связи по каналу связи с шумом Так как канал с шумом, то принятый вектор y может отличаться от кодового слова x на вектор e, называемый вектором ошибок y = x + e, e = (e1, e2,..., en ), где с вероятностью (1 p) имеем ei = 0 (в этом случае i-й символ правильный) и с вероятностью p имеем ei = 1 (i-й символ исказился). В общем случае вероятность p может быть произвольным числом, удовлетворяющим неравенству 0 < p < 1/2.

Опишем некоторые другие, отличные от симметричных типы ошибок. Если для переходных вероятностей имеются запреты, то канал связи получается с односторонними ошибками, если в алфавит (входной и (или) выходной) включен пустой символ, то получаем канал связи со вставками или выпадениями. Рассмотрим подробнее несколько случаев.

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

2. Несимметричная ошибка типа {0 1} (замещение вида 0 1) аналогична предыдущей и происходит в результате замыканий в канале.

3. Ошибка стирания {0 z, 1 z} возникает в случае, если сигнал, представляющий собой 0 или 1, искажается в канале так, что его нельзя интерпретировать ни как 0, ни как 1. Этот символ заменяется неопределенным символом, который обозначается через z.

4. Ошибка вида 0 (1 ) состоит в удалении одного из символов кодового слова x, в результате чего длина слова уменьшается на единицу. Такие ошибки называют выпадениями символов (в выходной алфавит включен пустой символ).

5. Ошибка вида 0 ( 1) состоит во вставке символа 0 (1) перед некоторым символом или после последнего символа слова x, в итоге длина кодового слова увеличится на единицу. Одиночные ошибки такого типа называют вставками символов.

Существуют также другие виды ошибок.

Линейные коды Напомним, что линейным (или групповым) двоичным кодом называется подмножество E n, являющееся линейным подпространством (подгруппой) в E n. Произвольный линейный код с параметрами [n, k, d] можно задать различными способами:

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

посредством кодовой матрицы порядка 2k n (строками матрицы являются кодовые слова);

порождающей матрицы порядка k n (в строки записаны кодовые слова, образующие базу линейного кода);

проверочной матрицы – матрицы H такой, что для любого кодового слова x = (x1, x2,..., xn ) выполняется здесь H – матрица порядка (n k) n. Последнее уравнение задает (n k) проверочных уравнений. Очевидно, что такое представление линейного кода также является аналитическим.

Следует отметить, что для данного линейного кода представление порождающей (проверочной) матрицей не единственно.

Опишем подробнее задание линейного кода посредством проверочной матрицы, имеющей канонический вид. Пусть от отправителя в кодер поступило сообщение u = (u1, u2,..., uk ). Сформируем кодовое слово x = (x1, x2,..., xn ). Положим первую часть кодового слова состоящей из символов самого сообщения (называемых информационными символами): x1 = u1, x2 = u2,..., xk = uk. Далее следуют n k символов, называемых проверочными xk+1,..., xn. Они выбираются таким образом, чтобы все кодовые слова удовлетворяли уравнению Пусть матрица H имеет вид [Ank,k |Enk ], называемый каноническим, где Ank,k – некоторая матрица порядка (n k) k из 0 и 1, Enk – единичная матрица порядка n k. Все операции выполняются над полем Галуа GF (2) характеристики 2.

Теорема 1. О связи проверочной и порождающей матриц. Если проверочная матрица линейного кода задана в каноническом виде H = [Ank,k |Enk ], то порождающая матрица этого кода имеет вид G = [Ek | ATnk,k ]. Верно обратное.

Доказательство. Рассмотрим произвольное кодовое слово где xk+1,..., xn – проверочные символы, а x1,..., xk – информационные, т. е. информационный блок имеет вид что можно записать в матричном виде Тогда из определения проверочной матрицы имеем HxT = 0, т. е.

для любого i = 1,..., n k. Отсюда Таким образом, Из последнего и из уравнения (1.1.) имеем Транспонируя, получаем: x = u G, где G = [Ek | AT Заметим, что теорема верна для q-значных кодов.

Упражнение 4. Найти число различных базисов в E n.

Упражнение 5. Найти число различных линейных двоичных кодов длины n размерности k.

Упражнение 6. Показать, что в двоичном линейном коде либо каждый кодовый вектор имеет четный вес, либо половина кодовых векторов имеет четные веса и половина нечетные.

Упражнение 7. Доказать, что ненулевой столбец кодовой матрицы линейного [n, k]-кода содержит ровно 2k1 единиц.

Упражнение 8. Доказать, что для любого линейного кода справедливо HGT = 0 для любых проверочной и порождающей матриц H и G этого кода соответственно.

1.2. Границы объемов кодов Рассмотрим несколько известных границ мощностей кодов.

Теорема 2. Граница Хэмминга. Для любого двоичного кода C длины n (не обязательно линейного) с кодовым расстоянием d выполняется неравенство Доказательство. Обозначим t = [(d1)/2]. Поскольку кодовое расстояние равно d, то шары радиуса t, описанные около кодовых слов x, не пересекаются. Очевидно, что все они имеют одинаковый объем, равный Следовательно, Подставляя |Stn (0n )| в неравенство (1.2.), получаем требуемое.

Определение. Код называется совершенным или плотно упакованным, если т. е. имеет место плотная упаковка E n шарами радиуса [(d 1)/2].

Справедливы следующие утверждения.

Утверждение 1. Кодовое расстояние [n, k, d]-линейного кода равно минимальному из весов его ненулевых кодовых слов.

Теорема 3. О столбцах проверочной матрицы. Если H – проверочная матрица кода длины n, то код имеет кодовое расстояние d тогда и только тогда, когда любые d 1 столбцов матрицы H линейно независимы и найдутся d линейно зависимых столбцов.

Доказательство. Необходимость.

Вектор x веса принадлежит коду тогда и только тогда, когда что эквивалентно линейной зависимости некоторых столбцов матрицы H. Обозначим i-й столбец матрицы H через hi, т. е.

Отсюда и из равенства (1.3) получаем откуда следует соотношение линейной зависимости hi1 +... + hiw = 0. По утверждению 1 кодовое расстояние кода равно минимальному из весов его ненулевых кодовых слов. По условию теоремы код имеет кодовое расстояние d, откуда получаем линейную зависимость некоторой совокупности d столбцов матрицы H.

Если существует d 1 линейно зависимых столбцов в матрице H, то найдется вектор веса d 1, принадлежащий коду C, противоречие.

Достаточность очевидна.

Непосредственным следствием теоремы 3 является следующая верхняя граница объема кода.

Теорема 4. Граница Синглтона. Для любого линейного [n, k, d]-кода выполняется n k d 1.

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

Теорема 5. Граница Синглтона для нелинейных q-значных кодов. Для любого (n, M, d)q -кода выполняется logq M n d + 1.

Доказательство. Удаляя в (n, M, d)q -коде последовательно любые d 1 координат, получим код длины n d + 1 с кодовым расстоянием по крайней мере 1 и мощности M.

(n, M, d)-кода C справедливо неравенство где M – мощность кода C.

Доказательство. Вычислим двумя способами сумму для различных кодовых слов u и v из C. Поскольку при u = v расстояние d(u, v) d, то сумма не меньше, чем M (M 1)d. С другой стороны, пусть A обозначает кодовую (M n)-матрицу, строками которой являются все кодовые слова. Предположим, что i-й столбец матрицы A содержит xi нулей и M xi единиц. Тогда вклад этого столбца в сумму S равен 2xi (M xi ). Суммируя по всем столбцам, получаем При четном M максимум этого выражения достигается при xi = M/2 для любого i, следовательно, эта сумма не превышает nM 2 /2, т. е. имеем отсюда Так как M четно, то При нечетном M эта сумма не превышает n(M 2 1)/2 и, следовательно, Отсюда с учетом [2x] 2[x] + 1 получаем Теорема 7. Граница Варшамова–Гилберта. Если выполняется неравенство то существует двоичный линейный код длины n с минимальным расстоянием по крайней мере d, имеющий не более чем r проверочных символов, т. е. [n, k, d ]–код, Доказательство. Теорема будет доказана, если построим (r n)-матрицу H такую, что любые ее d 1 столбцов линейно независимы. Тогда, применяя теорему 3, получаем требуемое утверждение. В качестве первого столбца матрицы H возьмем любой ненулевой вектор длины r. Предположим, что выбрали i столбцов матрицы H так, что любые d 1 из них линейно независимы. Имеем не более различных ненулевых линейных комбинаций из этих i столбцов, содержащих d или меньше столбцов. Если это число меньше, чем 2r 1 (числа всех ненулевых векторов длины r), то мы можем добавить еще один столбец, не равный ни одной из всех этих линейных комбинаций. При этом любые d 1 столбцов новой матрицы размера r (i + 1) по-прежнему остаются линейно независимы. Будем выполнять эту процедуру до тех пор, пока выполняется неравенство Упражнение 9. Обобщить для q-значных кодов границы:

а) Хэмминга;

б) Варшамова–Гилберта.

Упражнение 10. Доказать утверждение 1 и теорему 4.

1.3. Код Хэмминга и его свойства 1.3.1. Определение кода Хэмминга Для построения линейного кода Хэмминга с m проверками на четность, исправляющего одну ошибку, воспользуемся теоремой 3: определим код посредством проверочной матрицы, столбцами которой являются все ненулевые векторы длины m.

Очевидно, что любые два столбца этой матрицы линейно независимы и найдутся три линейно зависимых столбца, следовательно по теореме 3 кодовое расстояние равно и значит код исправляет одну ошибку. Этот код называется кодом Хэмминга, далее будем его обозначать Hn.

Параметры кода Хэмминга:

m = log(n + 1) (здесь и всюду далее log(·) является двоичным логарифмом, если не оговорено особо).

Утверждение 2. Код Хэмминга Hn является совершенным кодом, исправляющим одну ошибку.

Доказательство. Код Hn исправляет одну ошибку (по определению кода). По построению его мощность равна где m = log(n + 1). Следовательно, он достигает границы Хэмминга (см. теорему 2) и потому является совершенным.

Утверждение 3. Код Хэмминга единствен с точностью до изоморфизма.

1.3.2. Примеры кодов Хэмминга длины Рассмотрим три различных представления кода Хэмминга длины 7.

1. Код Хэмминга длины 7 задан проверочной матрицей в каноническом виде (см. [1], гл. 1), т. е. проверочная матрица имеет вид 2. Код Хэмминга длины 7 в циклическом виде. Определение. Линейный код C длины n называется циклическим, если для любого кодового слова x = (x1, x2,..., xn ) слово (x2, x3,..., xn, x1 ) принадлежит коду C.

Проверочная матрица кода Хэмминга длины 7 в циклическом представлении имеет вид:

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

1.3.3. Декодирование кода Хэмминга Код Хэмминга допускает самое простое декодирование. Рассмотрим представление кода Хэмминга Hn посредством проверочной матрицы, столбцы которой записаны в лексикографическом порядке:

здесь Hm – проверочная матрица кода Hn, m = log(n + 1), B(i) – двоичное представление числа i. Используя эту проверочную матрицу Hm, можно определить код Хэмминга следующим образом:

Определение. Вектор Sy = Hy T, где H проверочная матрица линейного кода, называется синдромом вектора y.

Пусть в канале связи при передаче вектора x произошла одна ошибка в i-й координате и получен вектор y. Воспользовавшись тем, что для любого кодового слова x кода Hn выполняется HxT = 0m, найдем синдром вектора y:

Синдром Sy равен столбцу, номер которого i является номером ошибочной координаты вектора y. Здесь ei – двоичный вектор длины n с единицей только в i-й координате.

Позднее (см. гл. 4, подразд. 4.5.1.) будет рассмотрен пример кода Хэмминга над полем Галуа GF (q) для произвольного q = pm, где p – любое простое число.

Упражнение 11. Доказать утверждение 3.

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

1. Метод комбинирования кодов Теорема 8. Пусть G1, G2 – порождающие матрицы для [n1, k, d1 ] и [n2, k, d2 ] – кодов соответственно. Тогда коды с порождающими матрицами представляют собой [n1 + n2, 2k, min{d1, d2 }]- и [n1 + n2, k, d]-коды соответственно, причем d d1 + d2.

2. Добавление общей проверки на четность Из двоичного кода C с параметрами (n, |C|, d), где d нечетно, образуем новый код C с параметрами (n + 1, |C|, d + 1), называемый расширенным кодом добавляя 0 в конце каждого кодового слова C четного веса и добавляя 1 в конце каждого кодового слова нечетного веса. Все кодовые слова кода C имеют, очевидно, четный вес. Код C удовлетворяет общему уравнению проверки на четность Для линейных кодов проверочная матрица кода C имеет вид где H – проверочная матрица исходного кода C. Такой код называется расширенным кодом.

3. Выкалывание кодовых координат Выкалывание кодовых координат представляет собой удаление одной и более координат во всех кодовых словах. Если исходный код C имел параметры: (n, |C|, d), то код C, полученный выкалыванием одной координаты из C, имеет следующие параметры: (n 1, |C |, d ), где |C | |C|, d 1 d d (заметим, что |C| = |C |, если d > 1).

4. Код с выбрасыванием Код с выбрасыванием получается из исходного удалением всех слов нечетного (или четного) веса. Из кода с параметрами (n, k, d) получается код (n, k, d ), где k k, d d и часто d > d (например, если d нечетное и удалены все слова нечетного веса).

Вообще говоря, можно рассматривать коды с выбрасыванием слов некоторого веса, например, малого или большого.

5. Пополнение кода Пополнение кода C с параметрами [n, k, d] добавлением новых слов представляет собой следующее: если в E n найдется вектор a такой, что d(C, a) d, то добавим к исходному коду множество C + a. При этом мы получим код той же длины n, размерности k + 1.

Упражнение 12. Оценить кодовое расстояние полученного кода.

6. Укорочение кода Укорочение кода состоит в следующем:

а) выбираем все кодовые слова, у которых координата i равна 0 (либо 1). Как правило, выбирается более мощная часть кодовой матрицы с фиксированной координатой i, если таковой нет, как, например, в линейных кодах, то выбираются все кодовые слова, у которых координата i равна 0;

б) удаляем эту координату в выбранных словах.

Из кода C с параметрами (n, |C|, d) получается (n 1, |C |, d )-код C, где |C | |C|/2, d d.

Упражнение 13. Построить расширенный код Хэмминга длины 8 добавлением общей проверки на четность. Доказать, что код имеет расстояние 4, обнаруживает ошибки и исправляет одну ошибку.

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

Утверждение 4. Для любых векторов x и y из E n справедливо и (n, M2, d2 )-коды соответственно. Тогда множество является (2n, M1 · M2, d = min{2d1, d2 })-кодом.

Доказательство. Пусть u = (x, x+y), v = (x, x +y ) произвольные различные кодовые слова кода C 2n, где x, x C, y, y D.

Пусть y = y, тогда, используя утверждение 4, получаем Упражнение 14. Доказать теорему 8.

Упражнение 15. Найти порождающую матрицу расширенного кода Хэмминга длины 16, построенного с помощью конструкции Плоткина. Какие коды для этого нужно использовать?

1.5. Теорема Глаголева В этом разделе множество строк порождающей матрицы кода будем называть базовым множеством. Для доказательства теоремы Глаголева потребуется следующий несложно доказываемый факт (см. также п. 5 предыдущего раздела).

Лемма 1. Если G линейный код с кодовым расстоянием d и если найдется такой вектор x, что d(G, x) d, то множество G (G + x) является линейным кодом с кодовым расстоянием d.

Теорема 10 (Глаголев В. В., 1971). Для любого двоичного линейного [n, k, d]-кода C существует линейный код C с теми же параметрами такой, что его базовое множество состоит из кодовых слов минимального веса d.

Доказательство. В качестве базового множества рассмотрим множество кода C. Здесь Td максимальное линейно независимое множество кодовых слов веса d; Td+1 множество кодовых слов веса d + 1, которое может быть выбрано в коде C так, что Td Td+1 максимальное линейно независимое множество кодовых слов веса не более d + 1. Аналогично выбираем остальные множества вплоть до Td+p кодовых слов веса d+p для некоторого p. Таким образом код C совпадает с линейной оболочкой множества Td Td+1... Td+p, т. е.

Рассмотрим произвольный вектор y из Td+1. Докажем, что расстояние между y и любым кодовым словом из Td больше d. Пусть это неверно и найдется вектор z Td такой, что d(y, z) = d. Тогда w(y + z) = d и в силу линейности кода C имеем y + z C. С другой стороны, в силу линейной независимости множества Td Td+ справедливо y + z Td. Следовательно, получили подмножество Td (y + z) в коде C, которое является линейно независимым множеством кодовых слов веса d и имеет мощность больше мощности множества Td, что противоречит выбору множества Td.

Следовательно, Возьмем любой вектор y веса d, предшествующий вектору y, т. е. y y. Это означает, что все единичные координаты вектора y находятся среди единичных координат кодового слова y. Используя неравенство (1.4), получаем Рассмотрим множество Td (Td + y ). Согласно лемме 1, его линейная оболочка является линейным кодом с кодовым расстоянием d. Далее аналогичным образом в тени некоторого кодового слова множества Td+1 найдем вектор y и рассмотрим множество Td {y, y }, которое позволяет построить новый линейный код с расстоянием d и т. д., переходя от множества Td+1 к множеству Td+2 и далее до множества Td+p, не более чем за k шагов построим линейный [n, k, d]-код C с базовым множеством, состоящим из кодовых слов минимального веса d.

Замечание. В 1992 г. Ю. Симонис получил аналогичный результат для q-значных линейных кодов над GF (q).

Следующее утверждение вытекает из теоремы Глаголева и утверждения 3 о единственности кода Хэмминга.

Следствие 1. Для произвольного кода Хэмминга существует базовое множество, состоящее из кодовых слов веса 3.

Упражнение 16. Доказать лемму 1.

Декодирование 2.1. Декодирование двоичных кодов Пусть сообщение u = (u1,..., uk ) закодировано кодовым словом x = (x1,..., xn ), которое передается по каналу связи с шумом. Принятый вектор y = (y1,..., yn ) может отличаться от x. Введем вектор ошибок где ei = 0 с вероятностью 1 p, ei = 1 с вероятностью p (исказился i-й символ), p произвольное число, удовлетворяющее 0 < p < 1/2.

Задача декодера решить на основании принятого слова y, какое сообщение u или, что, как правило, удобнее, какое кодовое слово x было передано. Если декодер найдет слово e, то легко вычислить кодовое слово x = y e. Но декодер часто не может определить в точности, чему равен вектор ошибок e. В этом случае его стратегия заключается в выборе наиболее вероятного вектора ошибок e.

Опишем декодирование в ближайшее кодовое слово или декодирование по максимуму правдоподобия (для двоичного симметричного канала связи эти методы декодирования совпадают, поскольку метрика Хэмминга согласована с двоичным симметричным каналом). Поскольку ошибки происходят независимо с вероятностью p, то для вектора ошибок e длины n имеем где e вектор ошибки длины n.

Так как p < 1/2, то 1 p > p и, очевидно, справедливо Другими словами, фиксированный вектор ошибок веса 1 более вероятен, чем вектор ошибок веса 2, и т. д. Отсюда напрашивается стратегия декодирования: y декодируется в ближайшее кодовое слово x или, что то же самое, выбирается вектор ошибок e наименьшего веса. Такая процедура декодирования называется декодированием по максимуму правдоподобия (т. е. в выборе наиболее вероятного вектора ошибок e для данного принятого вектора y) или декодированием в ближайшее кодовое слово.

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

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

Пусть C линейный двоичный [n, k]-код (все дальнейшие рассуждения в этом пункте справедливы для линейных кодов над полем из q 2 элементов). Для любого вектора a множество называется смежным классом (или сдвигом) кода C. Каждый смежный класс содержит 2k векторов, два вектора a, b принадлежат одному и тому же смежному классу тогда и только тогда, когда a b C. Любые два смежных класса либо не пересекаются либо совпадают (частичное пересечение невозможно). Этот факт легко доказывается от противного.

Таким образом, n-мерный единичный куб E n можно разбить на классы смежности по линейному коду C:

где m = 2nk 1.

Вектор y, принятый декодером, попадает в некоторый i-й класс смежности т. е. y = ai + x для некоторого x C. Если было передано слово x, то вектор ошибок вычисляется как т. е. вектор ошибок принадлежит тому же i-му классу смежности. Таким образом, если получили вектор y из i-го класса смежности, то возможными векторами ошибок будут все векторы i-го смежного класса. Отсюда вытекает следующая стратегия декодера: из смежного класса, содержащего вектор y, выбирается вектор e наименьшего веса. Если таких векторов несколько, то выбирается любой из них. Далее производится декодирование y как Вектор минимального веса из смежного класса называется лидером смежного класса.

Опишем таблицу, называемую стандартным расположением для кода. Стандартное расположение удобный способ описания работы декодера. В первую строку таблицы помещаются сообщения, во вторую кодовые векторы, причем в первом столбце стоит нулевой вектор: x = 0, x,..., x2. В третью строку под нулевым вектором помещается лидер a1 некоторого класса смежности по коду C и строка заполняется таким образом, чтобы под кодовым словом xi стояло слово a1 + xi. Следующие строки заполняются аналогично. Процесс продолжается до тех пор, пока не исчерпаются все векторы из E n.

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

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

Пример 1. Рассмотрим пример линейного [4, 2]-кода (см. [1], с. 26) с порождающей матрицей Таблица стандартного расположения без столбца синдромов для этого кода имеет вид Каким образом действует декодер?

• Ищет в таблице полученное на выходе канала связи слово y, например, y = (1101).

• Принимает решение, что вектор ошибок e это лидер класса смежности, содержащего вектор y, т. е. e = (1000).

• Далее вектор y декодируется в вектор x = y e = (1101) + (1000) = (0101) и делается вывод, что исходное сообщение было равно (01).

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

Если линейный код имеет небольшие параметры, то таблица стандартного расположения очень удобна для процесса декодирования. Но в большинстве случаев такая процедура неэффективна, так как требует большого объема вычислений. Например, если взять линейный код длины 100 и размерности 70, то таблица декодирования содержит 270 столбцов и 230 строк, т. е. имеет очень большие размеры.

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

2.2.2. Свойства синдрома 1. Если проверочная матрица имеет (n k) строк, то синдром Sy произвольного вектора y E n является вектором длины (n k).

2. Поскольку по определению линейного кода вектор y является кодовым тогда и только тогда, когда Hy T = 0, то справедливо Утверждение 5. Синдром Sy вектора y равен 0 тогда и только тогда, когда y является кодовым вектором.

3. Справедливо Утверждение 6. Для двоичного линейного кода синдром Sy принятого вектора y равен сумме тех столбцов проверочной матрицы H, где произошли ошибки.

Тогда, по определению синдрома и из утверждения 5, имеем Пусть e имеет "1" в координатах с номерами i1, i2,..., is, т. е.

Это означает, что произошли ошибки в i1, i2,..., is координатах. Таким образом, где hik это ik -й столбец матрицы H. Следовательно, т. е. действительно синдром выделяет те позиции вектора, где произошли ошибки.

4. Имеет место взаимно однозначное соответствие между синдромами и смежными классами.

Утверждение 7. Два вектора u и v принадлежат одному и тому же смежному классу тогда и только тогда, когда их синдромы равны.

Доказательство. Два элемента группы u и v принадлежат одному и тому же смежному классу по данной подгруппе тогда и только тогда, когда uv принадлежит этой подгруппе. В нашем случае подгруппой является код C, т. е. u v C. Тогда по определению линейного кода выполняется Отсюда Hv T = HuT.

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

Рассмотрим вычисление синдрома для приведенного выше примера. Сначала по порождающей матрице G найдем проверочную матрицу H:

Затем вычислим синдром для смежного класса с лидером (1000), он равен, т. е. первому столбцу матрицы H. Далее вычислим все синдромы и запишем их в таблицу синдромов.

Пусть получено слово y = (1100). Вычислим его синдром:

он равен третьему столбцу проверочной матрицы H. Ему отвечает лидер смежного класса (0010), он же является искомым вектором ошибок, т. е.

Отсюда делаем вывод, что было передано кодовое слово (1110).

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

2.3. Вероятность ошибки декодирования Определение. Вероятностью ошибки декодирования или вероятностью ошибки на слово Pош для данной схемы декодирования называется вероятность появления некодового слова на выходе декодера.

Пусть дан линейный код длины n мощности M с кодовыми словами где кодовые слова используются с равной вероятностью. Обозначим вероятность того, что на выходе декодера получено слово y = xi при переданном xi через Тогда т. е. вероятность ошибки на слово равна средней вероятности неправильного декодирования.

При декодировании, использующем стандартное расположение, правильное декодирование имеем тогда и только тогда, когда вектор ошибок совпадает с лидером смежного класса. Иначе говоря, вероятность ошибки в этом случае равна Если имеем i лидеров смежных классов веса i, i = 0,..., n, то вероятность правильного декодирования Pпр.дек. равна поскольку вероятность правильного декодирования кодового слова с некоторым вектором ошибок v веса i равна (см. разд. 2.1.).

Так как стандартное расположение обеспечивает декодирование по максимуму правдоподобия, то любая другая схема будет иметь вероятность правильного декодирования меньше, чем (2.1), а следовательно, и вероятность ошибки произвольная схема декодирования будет иметь не меньше, чем вероятность ошибки при декодировании, использующем стандартное расположение, поскольку получим Рассмотрим линейный код с минимальным расстоянием d = 2t + 1. По теореме он исправляет t ошибок и, следовательно, каждый вектор веса не больше t является лидером смежного класса, т. е.

Если вероятность p ошибки в канале очень мала, то (1 p) 1 и, следовательно, Отбрасывая в равенстве (2.2) все члены, начиная с i > t, получаем формулу, аппроксимирующую формулу (2.2) достаточно точно:

Аналогично в случае кодового расстояния d = 2t + 2 получаем следующую аппроксимацию формулы (2.2):

Если i = 0 при i > t = (d 1)/2, то формула (2.3) становится точной;

при i > t + 1 становится точной формула (2.4). В первом случае код называется совершенным, во втором квазисовершенным.

Геометрически это означает, что в первом случае имеем разбиение пространства E на непересекающиеся шары радиуса t (так как код может исправлять не больше, чем t ошибок). Во втором случае, поскольку код исправляет все ошибки веса не больше t, некоторые ошибки веса t + 1 и не может исправлять ни одной ошибки веса больше, чем t + 1, имеем покрытие пространства E n шарами радиуса t + 1. При этом шары радиуса t + 1 могут пересекаться.

Более тонкой мерой качества декодирования является вероятность ошибки на символ.

Пусть имеем линейный код мощности M = 2k с кодовыми словами x1,..., xM, где первые k символов xi,..., xi в каждом слове являются информационными. Пусть y = (y1,..., yn ) слово на выходе декодера.

Определение. Вероятность ошибки на символ Pсимв. равна средней вероятности того, что после декодирования информационный символ является ошибочным:

Вернемся к декодированию стандартным расположением. Так как все сообщения и ошибки в любом символе независимы и равновероятны (т. е. рассматривается симметричный канал), то достаточно рассмотреть произвольный кодовый вектор x = (x1,..., xn ). Пусть получен вектор y, тогда Пусть f (e) число неправильных информационных символов после декодирования при условии, что e вектор ошибок, тогда Рассмотрим наш пример: изучая таблицу стандартного расположения, приходим в выводу, что f (e) = 0 для всех векторов ошибок первого столбца, так как в первом столбце стоят лидеры смежных классов; f (e) = 1 для всех векторов ошибок как второго, так и третьего столбцов; f (e) = 2 для всех векторов четвертого столбца.

Отсюда по формуле (2.5) при p = 1/100 получаем Теорема Шеннона 3.1. Необходимые понятия Рассмотрим двоичный симметричный канал связи. Пусть для каждого символа имеется вероятность 0 < p < 1 того, что при передаче его по каналу связи произойдет ошибка. Пусть C двоичный код, содержащий M равновероятных кодовых слов x1,..., xM длины n, в котором каждое слово встречается с равной вероятностью. Напомним, что вероятностью ошибки на слово или вероятностью ошибки PC для данной схемы декодирования называется вероятность появления неправильного кодового слова на выходе декодера. Пусть Pi вероятность неправильного декодирования при условии, что передано кодовое слово xi. Тогда где Pi зависит от вероятности p. Рассмотрим совокупность L всех двоичных кодов длины n мощности M и определим Определение. Функция энтропии H(x) определяется равенством при 0 < x < 1, при x = 0 и x = 1 полагают H(0) = H(1) = 0.

Отметим, что log x здесь и далее рассматривается по основанию 2.

Определение. Пропускная способность двоичного симметричного канала с вероятностью 0 p 1 равна Определение. Скоростью (n, M, d)-кода называется величина (log M )/n.

Теорема 11 (Шеннон К., 1948). Пусть R любое число, удовлетворяющее условию 0 < R < C(p), и пусть Mn = 2[n·R]. Тогда Теорему Шеннона можно переформулировать следующим образом: для любой сколь угодно малой величины > 0 и любого 0 < R < C(p) существует двоичный код C длины n, мощности M и скорости R такой, что вероятность ошибки декодирования PC <, где M определяется из соотношения R = (log M )/n.

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

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

3.2. Свойства энтропии Рассмотрим бернуллиевский источник A: буквы входного алфавита ai, i = 1,..., k появляются независимо с независимыми вероятностями pi, удовлетворяющими условию Энтропия H(A) источника A по Шеннону определяется следующим образом:

В определенной выше энтропии H(x) имеем два исхода с вероятностями p и 1 p соответственно.

Рассмотрим несколько важных свойств энтропии.

Утверждение 8. Справедливо H(A) 0. Энтропия неотрицательна и равна нулю тогда и только тогда, когда одна из вероятностей равна единице, а остальные равны нулю.

Доказательство. Действительно, из 0 pi 1 имеем pi 1 и log pi 0, т. е.

log pi 0, отсюда pi log pi 0. Поскольку, по определению, pi log pi = 0 при pi = 0, то для любого pi 0 выполняется pi log pi 0 и, следовательно, При H(A) = 0 каждое слагаемое равно нулю, а значит, либо pi = 0, либо log pi = 0, т. е. pi = 1. Так как k pi = 1, то среди вероятностей pi принять значение 1 может лишь одна, остальные равны нулю. Таким образом, неопределенность события равна нулю тогда и только тогда, когда исход события заранее известен, в остальных случаях энтропия положительна.

Рассмотрим произвольную непрерывную выпуклую вверх функцию f (x), заданную на положительной полуоси. Для произвольных положительных чисел i, i = 1,..., k таких, что k i = 1 и любых x1,..., xk из участка выпуклости функi= ции f (x) выполняется неравенство Йенсена причем равенство имеет место тогда и только тогда, когда H(A) log k.

Доказательство. Рассмотрим функцию f (x) = log x. Она выпукла вверх при x > 0, поскольку ее вторая производная меньше нуля. Положим i = pi. Тогда с учетом k pi = 1 и неравенства Йенсена имеем справедливо причем равенство достигается только при qi = pi (таким образом значение энтропии минимизирует функцию f (q1,..., qk ) = k pi log qi ).

Доказательство. Рассмотрим доказательство этого свойства в случае, когда все pi положительны (при pi = 0 для некоторого i = 1,..., k, доказательство аналогично с некоторыми модификациями). Воспользуемся неравенством Йенсена при i = pi, xi = qi /pi, i = 1,..., k для функции f (x) = log x:

Отсюда имеем откуда вытекает требуемое. Неравенство Йенсена переходит в равенство только тогда, когда x1 =... = xk или в нашем случае при q1 /p1 =... = qk /pk, т. е. когда векторы (q1,..., qk ) и (p1,..., pk ) пропорциональны и, следовательно, в силу имеем qi = pi.

Утверждение 11. Для любых случайных опытов A и B справедливо причем равенство достигается только когда опыты A и B независимы. Для бернуллиевских источников справедливо для любого натурального N.

Здесь AB обозначает произведение источников A и B : пусть тогда где i, j {1, 2,..., k}; AN произведение N копий источника A.

В дальнейшем нас будет интересовать случай событий с двумя исходами, поскольку основная модель изучаемого нами канала связи двоичный симметричный канал. В этой ситуации имеем функцию H(x) одного аргумента. В силу утверждения 8, она равна нулю при x = 0 и x = 1, согласно утверждения 9, достигает максимума, равного единице, в точке x = 1/2. Кроме того, для нее выполняется соотношение следовательно, функция H(x) симметрична относительно прямой x = 1/2, см. ее график на рис. 4.

3.3. Необходимые комбинаторно-вероятностные I. Неравенство Чебышева. При передачe информации по двоичному симметричному каналу связи число ошибок в полученном слове является бернуллиевской случайной величиной, принимающей значения 0, 1,..., n, математическое ожидание E( ) которой равно np, а дисперсия D( ) равна np(1 p). Если в кодовом слове x = (x1,..., xn ) произошло t ошибок, то, в силу того что имеем биномиальное распределение, вероятность получить вектор ошибок e веса t равна т. е. зависит только от n и t.

Теорема 12. Неравенство Чебышева. Если случайная величина с математическим ожиданием E() и дисперсией D(), тогда для любого > 0 справедливо Выберем произвольное > 0. Для случайной величины обозначим через b следующую величину:

Тогда, используя неравенство Чебышева, получаем Откуда следует где Неравенство (3.2) означает: вероятность того, что в результате произошедших в канале ошибок полученное на приемном конце слово y находится от переданного кодового слова x на расстояние большее, чем, мала (не превышает /2).

Зафиксируем > 0, тогда для достаточно больших n величина не превосходит (n/2), поскольку p < 1/2.

II. Объем шара радиуса [pn]. Рассмотрим шар радиуса [pn] с центром в некоторой вершине x E n :

Оценим его объем с помощью функции энтропии H(p).

Лемма 2 Пусть 0 p 1. Тогда справедлива оценка Доказательство. Имеем Отсюда III. Объем шара радиуса = [E( ) + b]. Оценим объем шара радиуса = [E( ) + b] с центром в некоторой вершине, используя функцию энтропии H(p).

Доказательство. По лемме 2 имеем что доказывает лемму.

3.4. Доказательство теоремы Шеннона Введем функцию f (y, x). Пусть x, y E n, тогда Функция f (y, x) характеристическая функция принадлежности вектора y шару с центром в вершине x, т. е.

Доказательство теоремы Шеннона. Выберем сколь угодно малую величину > 0. Рассмотрим случайный двоичный код длины n мощности M, т. е. выберем случайным образом кодовые слова x1,..., xM. Декодируем полученный вектор y следующим образом: если существует в точности одно кодовое слово xi такое, что то y декодируем в xi, в противном случае регистрируем ошибку или, если должны произвести декодирование в любом случае, всегда декодируем в x1.

Пусть Pi, как и выше, вероятность того, что на выходе декодера получено слово, отличное от переданного слова xi. Для Pi имеем следующую оценку сверху:

найдется единственное кодовое слово xi такое, что d(xi, y), в противном случае Первая сумма в неравенстве (3.3) равна вероятности того, что полученное на приемном конце слово находится на расстоянии большем от переданного кодового слова x. Согласно неравенству (3.2), оно не превышает /2. Таким образом, Основная идея дальнейшего доказательства состоит в том, что величина меньше, чем ожидаемое значение, т. е. меньше математического ожидания PC над ансамблем L всех возможных кодов C длины n, мощности M, взятых случайно.

Отсюда имеем Таким образом, P (M, n, p) 2 M · 2n · |B |. Логарифмируя обе части, применяя лемму 3 и деля на n, получаем Подставляя M = Mn = 2[R·n] в правую часть (вспомним, что по условию число R сколь угодно близко к пропускной способности C(p) = 1 H(p)), получаем константа, равная C(p) R. Отсюда P (M, n, p) < 2 + 2n. Начиная с некоторого n будет выполняться 2n < 2, и, следовательно, P (M, n, p) <. Таким образом, Теорема доказана.

Свитчинговые методы 4.1. Коды Васильева В 1959 г. Г. С. Шапиро и Д. С. Злотник предположили, что не существует совершенных кодов, не эквивалентных коду Хэмминга. В 1962 г. Ю. Л. Васильев опроверг эту гипотезу, предложив богатый класс неэквивалентных совершенных двоичных кодов. Рассмотрим этот итеративный способ построения для кодов с произвольными кодовыми расстояниями. Беря в качестве исходных кодов коды со специфическими параметрами, можно получить такие хорошие коды, как совершенные или коды Рида-Маллера.

Рассмотрим произвольные двоичные коды B и C длины n с кодовыми расстояниями d1 и d2 соответственно, где d1 нечетно. Пусть произвольная функция из кода C в множество {0, 1}, |x| = x1 +... + xn (mod 2), где x = (x1,..., xn ).

Теорема 13 Множество является двоичным кодом длины 2n + 1, мощности |B| · |C| с кодовым расстоянием d min{2d1 + 1, d2 }.

Доказательство. Проверим параметры построенного кода, а именно его длину, мощность кода и кодовое расстояние.

1. Легко видеть, что 2n + 1 является длиной кода.

2. Поскольку x и y независимо пробегают множества B и C соответственно, мощность кода C 2n+1, очевидно, равна 3. Проверим, что кодовое расстояние равно d min{2d1 + 1, d2 }. Рассмотрим два произвольных различных кодовых слова:

Возможны случаи.

3a. Если y = y и x = x, то, с учетом того что d(x, x ) d1 и d1 нечетно, получаем 3b. Пусть y = y и x = x. Векторы y, y принадлежат коду C n, следовательно, d(y, y ) d2 и получаем 3c. Если y = y и x = x, то аналогично доказательству кодового расстояния в теореме Плоткина (см. теорему 9), используя предложение 4, получаем Теорема доказана.

Рассмотрим применение этой конструкции для построения совершенных двоичных кодов.

вершенный код длины (n 1)/2 = 2 1, m 2 и произвольная функция из кода C (n1)/2 в множество {0, 1}. Множество является совершенным двоичным кодом длины n с кодовым расстоянием 3.

Доказательство этой теоремы аналогично доказательству предыдущей. Код (4.2) будем далее называть кодом Васильева. Приведем несколько важных следствий, вытекающих из этой теоремы.

Следствие 2. При 0 конструкция Васильева, примененная к коду Хэмминга H(n1)/2 длины (n 1)/2, дает код Хэмминга длины n:

Следствие 3. Если (y) + (y ) = (y + y ) для некоторых y, y C (n1)/2, то код Васильева длины n является нелинейным.

Поскольку функция произвольна, то, принимая во внимание предыдущие итеративные шаги, т. е. подставляя в формулу (4.2) снова произвольный код Васильева длины (n1)/2, затем произвольный код Васильева длины (n3)/4 и т. д., получаем следующее утверждение.

Следствие 4. Число Dn различных кодов Васильева длины n удовлетворяет следующей нижней оценке:

для достаточно больших n.

Зная нижнюю оценку числа различных кодов длины n, легко вычислить нижнюю оценку числа неэквивалентных кодов с теми же параметрами. Для этого достаточно разделить число различных кодов на число различных автоморфизмов E n, равное 2n · n!, здесь 2n число различных сдвигов на векторы из E n и n! число различных подстановок на n координатах. Нетрудно из следствия 4 получить следующее утверждение.

Следствие 5. Для числа Nn неэквивалентных кодов Васильева длины n справедливо n+1 log(n+1) n+5 log(n+1) при достаточно больших n.

Эта оценка до 1996 г. оставалась лучшей нижней оценкой числа неэквивалентных совершенных кодов, несмотря на многочисленные усилия многих исследователей.

Для n = 7 существует единственный совершенный код длины 7, для n = 15 существует 11 неэквивалентных кодов Васильева длины 15 и, по крайней мере, 963 неэквивалентных кода, полученных каскадной конструкцией (см. [13]; о каскадных конструкциях см. следующую главу). Следует отметить, что классификация совершенных кодов даже длины 15 до сих пор не найдена. Обзоры результатов по совершенным кодам могут быть найдены в работах [13, 19].

Упражнение 18. Доказать следствие 4.

Упражнение 19. Доказать следствие 5, используя формулу Стирлинга 4.2. Конструкция Моллара Рассмотрим конструкцию Моллара для двоичных кодов. Пусть P t и C m произвольные двоичные коды длин t и m соответственно с кодовыми расстояниями не менее 3, содержащие нулевые векторы. Пусть В этом разделе будем использовать следующую матричную запись для вектора x:

i-я строка матрицы X равна xi1 xi2... xim, где i = 1,..., t. Функции p1 (x) и p2 (x), определенные следующим образом:

где i = m xij и j = t xij, называются обобщенными проверками на четj=1 i= ность. Пусть f Теорема 15 (Моллар М., 1986). Множество является двоичным кодом длины n = tm + t + m, с кодовым расстоянием 3.

Доказательство. Легко проверить, что код C n имеет длину n = tm + t + m и мощность Пусть два произвольных вектора из кода C n. Покажем, что d(u, u ) 3.

Возможны приведенные ниже случаи.

1. При x = x имеем p1 (x) = p1 (x ), p2 (x) = p2 (x ) и, следовательно, при y = y имеем Аналогично при z = z, y = y. В случае y = y, z = z убеждаемся, что нулевой вектор принадлежит коду C n.

2. Если d(x, x ) = 1, то Пусть y = y, тогда и имеем d(u, u ) 3. Пусть y = y, тогда и снова имеем d(u, u ) 3.

3. В случае d(x, x ) = 2 расстояния d(p1 (x), p1 (x )) и d(p2 (x), p2 (x )) равны 0 или 2, но одновременно оба не могут быть равны нулю. Отсюда получаем, что равенства не выполняются одновременно и, следовательно, d(u, u ) 3.

Замечания 1. В случае, когда P t и C m произвольные совершенные двоичные коды длин t = 2r 1 и m = 2s 1 соответственно, код C n является совершенным двоичным кодом.

2. При m = 1, t = 2r 1 конструкция Моллара совпадает с конструкцией Васильева.

3. Существуют совершенные коды Моллара, неэквивалентные совершенным кодам Васильева.

4.3. Общая идея метода свитчинга Основная идея метода свитчинга состоит в следующем: в произвольном двоичном коде C длины n рассмотрим некоторое подмножество M кодовых слов. Если найдется в E n подмножество M, отличное от множества M, и множество C = (C \ M ) M является двоичным кодом с параметрами, совпадающими с параметрами кода C, то будем говорить, что код C получен из кода C свитчингом множества M на множество M. Результирующий код отличен или неэквивалентен исходному.

Удобно рассмотреть общую идею метода свитчинга на примере совершенных кодов. Пусть дано подмножество M в пространстве E n. Множество M получено из множества M инвертированием i-й координаты, i N = {1, 2,..., n}, всех слов M.

Обозначим его M = M + i. Множество M называется i-компонентой кода C, если K(M ) = K(M + i), где K(M ) окрестность порядка 1 множества M. Легко видеть, что код C = (C \ M ) (M + i) также является совершенным кодом. Будем говорить, что код C получен из кода C свитчингом i-компоненты M, (рис. 5).

Рассмотрим основную идею более общего свитчингового подхода построения кодов (также на примере совершенных кодов), называемого методом -компонент.

Пусть N. Множество M назовем -компонентой кода C, если для всех i множество M является, в свою очередь, i-компонентой C. Сначала для каждой -компоненты выбираем свое направление i из множества направлений и заменяем (делаем "свитчинг") произвольное число i-компонент в каждой -компоненте на новые i-компоненты такой же мощности. Затем производим замену полученных новых -компонент на другие -компоненты, делая свитчинги по неиспользованным из множества направлениям. В итоге результирующий код остается по-прежнему совершенным, но отличным или даже неэквивалентным исходному. Метод -компонент оказался особенно подходящим в применении его к коду Хэмминга, поскольку позволяет, разрушая групповую структуру кода Хэмминга, тем не менее следить за структурой нелинейного совершенного кода, получаемого вследствие серии свитчингов.

Впервые свитчинговый способ построения кодов был предложен Ю. Л. Васильевым. Можно показать, что конструкция Моллара также является свитчинговой конструкцией. В 1996 г. С. В. Августиновичем и Ф. И. Соловьевой был предложен способ построения совершенных двоичных кодов посредством метода -компонент (примененного к коду Хэмминга), который после 30-летнего перерыва дал первое существенное улучшение нижней оценки числа неэквивалентных совершенных кодов.

С помощью этого подхода была решена серия проблем, касающихся структуры совершенных кодов: например, обнаружены совершенные коды с тривиальной группой автоморфизмов, доказано существование несистематических совершенных кодов, кодов полного ранга. Ф. И. Соловьевой доказано существование совершенных двоичных кодов с i-компонентами различной мощности и структуры. Метод -компонент получил дальнейшее развитие в работах С. А. Малюгина, Д. С. Кротова, С. В. Августиновича (см. подробнее [13]).

4.4. Некоторые свойства совершенных кодов 4.4.1. Дистанционная инвариантность Код называется дистанционно инвариантным, если число Ai (n) всех кодовых слов на расстоянии i от фиксированного кодового слова не зависит от выбора этого кодового слова.

В 1957 г. С. П. Ллойд и независимо в 1959 г. Г. С. Шапиро и Д. С. Злотник доказали, что произвольный совершенный код является дистанционно инвариантным.

В этом и следующем параграфах приведем с доказательствами несколько красивых теорем о свойствах совершенных кодов с кодовым расстоянием 3, принадлежащих Г. С. Шапиро и Д. С. Злотнику.

Теорема 16 (Шапиро Г. С., Злотник Д. С., 1959). Пусть C произвольный совершенный код с кодовым расстоянием 3. Число кодовых слов на расстоянии k от данного кодового слова x C не зависит от выбора этого кодового слова и от выбора кода и зависит только от расстояния k.

Доказательство. Обозначим число кодовых слов на расстоянии k от кодового слова x через Ak. Без ограничения общности рассмотрим код, содержащий вектор x = 0n, где n длина кода C. Построим систему линейных уравнений для Ak, k = 0,..., n. Все числа Ak однозначно будут вычислены из этой системы.

Рассмотрим k-й слой Ek (все векторы веса k) в кубе E n. Согласно свойству плотn ной упакованности кода C, все векторы из Ek разобьются на следующие три подмножества:

1) кодовые слова веса k. Их число в точности равно Ak ;

2) векторы, которые принадлежат сферам, окружающим все кодовые слова из Ek1, имеется (n k + 1) · Ak1 таких векторов;

3) векторы, принадлежащие сферам с центрами в кодовых словах из Ek+1, имеется (k + 1) · Ak+1 таких векторов.

Отсюда получаем следующую систему из n + 1 линейных уравнений с n + 1 неизвестными:

здесь числа Ak с отрицательными индексами полагаются равными нулю (см. рис. 6).

Используя производящую функцию можно найти точный вид Ak, k = 0, 1,..., n, а именно:

и тем самым убедиться, что система имеет единственное решение.

Складывая последние два равенства, получаем что дает возможность сделать представленный ниже вывод.

Следствие 6. Произвольный совершенный код длины n, содержащий нулевой вектор, имеет равномерное распределение по парам соседних слоев E2k и E2k+1, Из этой теоремы вытекают также следующие полезные свойства.

Следствие 7. Для каждого кодового слова x C, где C произвольный соn вершенный код длины n, антиподальный ему вектор x + 1 также принадлежит коду C.

Это свойство антиподальности оказалось чрезвычайно важным для исследования многих нетривиальных свойств совершенных двоичных кодов.

Следствие 8. Число кодовых слов веса (n 1)/2 произвольного совершенного кода длины n, содержащего нулевой вектор, равно 4.4.2. О существовании совершенных кодов Здесь рассмотрим несколько теорем о существовании совершенных кодов. Доказательство следующей очень важной теоремы весьма нетривиально и может быть найдено в работе [1].

Теорема 17. О существовании совершенных кодов (Зиновьев В. А., Леонтьев В. К., Тиетвайнен А., 1972). Нетривиальный совершенный код над любым полем Галуа GF (q) должен иметь те же самые параметры, что и один из кодов Хэмминга или Голея, т. е.:

1) q-значный (n = (q m 1)/(q 1), n m, 3)-код;

2) двоичный [23, 12, 7]-код Голея;

3) троичный [11, 6, 5]3 -код Голея.

Оба кода Голея единственны с точностью до эквивалентности и существует много неэквивалентных совершенных q-значных кодов, q 2 (см. также следствие 5).

Под тривиальным совершенным кодом понимается код, состоящий либо из одного кодового слова, либо из двух антиподальных (в случае, если n нечетно). В 1949 г.

М. Ж. И. Голей построил двоичный совершенный [23, 12, 7]-код.

Теорема 18 (Шапиро Г. С., Злотник Д. С., 1959). Единственными совершенными двоичными кодами с расстоянием 7 является код с параметрами кода Голея длины 23 и тривиальный код длины 7.

Доказательство. Если существует совершенный двоичный код длины n, размерности k, с кодовым расстоянием 7, то и, следовательно, где r = n k. Умножая на 6 и преобразовывая левую часть последнего равенства, получаем Следовательно, первый или второй сомножители в левой части этого равенства делятся на 3.

Имеется два случая.

1. Пусть 3|(n2 n + 6). Тогда и, значит, выполняется При l = 3 имеем тривиальный код длины n = 7. Пусть l > 3 и n > 7. Из равенства (4.4) имеем Здесь первый сомножитель в левой части сравним с нулем по модулю 2, второй с единицей по тому же модулю. Анализируя сомножители правой части, приходим к заключению, что 23 = 2rl+1 и, следовательно, r l + 1 = 3. Отсюда что противоречит n > 7 (n должно быть целым числом).

2. Пусть 3|(n + 1). В этом случае имеем откуда Для равенства должно выполняться 2l3 = 1. Отсюда l = 3 и n + 1 = 3· 23 = 24. Иными словами, получаем возможность для существования кода длины 23, с кодовым расстоянием 7, что завершает доказательство теоремы.

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

Лемма 4 (Зигель). Пусть f (x) многочлен, принимающий целые значения при целых значениях переменной x. Если f (x) не является степенью линейного многочлена, умноженного на константу, то наибольший простой делитель числа f (n) неограниченно возрастает при n.

Теорема 19 (Шапиро Г. С., Злотник Д. С., 1959). Количество совершенных двоичных кодов длины n, с кодовым расстоянием d 5 конечно.

Доказательство. Чтобы доказать теорему, мы должны убедиться, что многочлен f (x), определенный как не является степенью линейного многочлена при t 2 (здесь правая часть равенства (4.5) является числом векторов в шаре радиуса t в x-мерном кубе E x ), где d = 2t + 1 кодовое расстояние. Тогда, согласно лемме 4, из равенства (4.5) получаем, что число f (n) имеет простой множитель, больший двух при n достаточно большом, и, следовательно, не может быть равным степени двойки; значит, 2n /f (n) = 2k ни для какого k. Это означает, что граница Хэмминга не может быть достигнута и не существует совершенного кода длины n с расстоянием d.

Докажем теорему от противного. Пусть где a, b, c некоторые рациональные числа. Вычислим f (0) из последнего соотношения:

т. е. f (x) можно переписать в виде где r = c/b рациональное число.

Подставляя x = 1 в равенство (4.5), получаем С другой стороны, из представления (4.7) имеем Таким образом, (1 + r)t = 2, откуда 1 + r = t 2 рационально. Это противоречие доказывает теорему.

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

Лемма 5 (Августинович С. В., 1995). Произвольный совершенный двоичный код длины n, содержащий нулевой вектор, однозначно определяется множеством своих кодовых слов веса (n 1)/2.

Доказательство. Как и прежде, обозначим все двоичные векторы веса k через Ek и рассмотрим множество X n1 = C E n всех кодовых слов веса (n 1)/ в совершенном коде C, содержащем 0. Прежде всего, следует заметить, что если известно множество X n1, то, согласно следствию 7, множество X n1 является подмножеством кода C, где X n1 множество всех антиподальных слов множеству слов X n1.

Пусть существует по крайней мере два продолжения множества X n1 X n1 до совершенных кодов:

где A = B.

Легко видно, что d(A, B) 3. Используя этот факт, можно построить совершенный код (рис. 7).

Из A = B имеем A = B и, следовательно, найдется вектор y B такой, что y A. Отсюда, из соотношения 4.9 и свойства антиподальности совершенного кода (см. следствие 7), получаем y A. Снова в силу антиподальности совершенного кода из равенства 4.9 имеем y D, следовательно, y A, противоречие.

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

Теорема 20 (Августинович С. В., 1995). Число Nn различных совершенных двоичных кодов длины n удовлетворяет неравенству Доказательство. Из леммы 5 легко получить следующую верхнюю оценку числа различных совершенных двоичных кодов длины n:

Используя дважды формулу Стирлинга и следствие 8, получаем Замечания 1. Сравнивая эту оценку с лучшей нижней оценкой числа различных совершенных двоичных кодов, убеждаемся в большом разрыве между ними.

2. Тривиальная верхняя оценка имеет вид Упражнение 20. Доказать, используя приведенный выше вариант формулы Стирлинга, неравенство Упражнение 21. Доказать, используя формулу Стирлинга, что число A n1 из следствия 8 удовлетворяет неравенству где c некоторая константа.

Упражнение 22. Доказать, используя формулу Стирлинга, неравенство (4.10).

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

Нерешенная проблема Найти новую верхнюю оценку числа различных совершенных двоичных кодов длины n 15.

Каскадные методы 5.1. Основная идея каскадного способа построения Каскадный метод построения кодов впервые был предложен в 1966 г. Г. Д. Форни, затем, в начале 70-х гг., теория каскадных и обобщенных каскадных кодов была развита В. В. Зябловым, Э. Л. Блохом, В. А. Зиновьевым.

Рассмотрим основную идею каскадного способа построения кодов.

Пусть A является q-значным (n, |A|, d)-кодом, т. е. кодом длины n, мощности |A|, с кодовым расстоянием d. Пусть B q -значный (N, |B|, d )-код, где |B| = q. Обозначим кодовые слова кода B следующим образом: B = {b(0),..., b(q 1)}. Для любого кодового слова a = (a1,..., an ) A построим вектор a(B) = b(a1 )|... |b(an ), где символ | обозначает конкатенацию векторов. Множество C = {a(B) : a A} является q -значным кодом. Легко найти параметры этого кода: длина равна nN, мощность |C| = |A| и кодовое расстояние d(C) dd. Коды A, B и C называются, соответственно, внешним, внутренним и каскадным кодами.

В этой главе будет приведено несколько каскадных методов построения кодов (иногда для простоты изложения рассматривается случай кодов с малыми кодовыми расстояниями), принадлежащих различным авторам. Сначала рассмотрим наиболее простые каскадные методы построения кодов, затем более сложные. В конце главы изложим обобщенную каскадную конструкцию В. А. Зиновьева для нелинейных кодов (обобщенная каскадная конструкция для линейных кодов была предложена ранее В. В. Зябловым и Э. Л. Блохом).

5.2. Коды Соловьевой (1981) Для определения каскадной конструкции, предложенной Ф. И. Соловьевой в 1981 г., потребуются разбиения n-куба E n на совершенные коды.

Разбиения E n на совершенные коды. Рассмотрим произвольный совершенный код C с кодовым расстоянием 3 длины n = 2m 1 при m 2. Используя свойство плотной упакованности совершенного кода в E n, легко получить следующее тривиальное разбиение E n на аналоги классов смежности по совершенному коду C:

где ei вектор с единственной ненулевой координатой i. Приведем нетривиальную конструкцию широкого класса нетривиальных разбиений E n на совершенные коды для любой допустимой длины кода n > 7, используя конструкцию Васильева. Обозначим этот класс через Pn.

Теорема 21 (Соловьева Ф. И., 1981). Существует класс Pn различных разбиений куба E n на совершенные коды длины n 15, где Доказательство проведем индукцией по m, где m = log(n + 1).

Для m = 2 существует лишь тривиальное разбиение, поскольку для n = 3 суэто код Хэмминга H 3. К. Т. Фелпсом ществует единственный совершенный код показано, что при n = 7 существует 11 неэквивалентных разбиений E 7 на различные коды Хэмминга длины 7.

Рассмотрим произвольное разбиение E (n1)/2, m 1 = log((n + 1)/2), на совершенные коды длины (n 1)/2:

Перейдем к случаю m. Используя конструкцию Васильева, из каждого кода Ci, i {0, 1,..., (n 1)/2}, построим следующие два совершенных кода длины n. Первый код имеет вид второй где, как и в конструкции Васильева, функция i является произвольной функцией из кода Ci в множество {0, 1}. Легко показать, что любые два построенных кода не пересекаются.

Число различных разбиений не меньше числа выборов различных функций i для каждого i = 0, 1,..., (n 1)/2. Следовательно, что завершает доказательство.

В дальнейшем в этой главе под совершенными кодами подразумеваются совершенные коды с расстоянием 3.

Теорема 22 (Соловьева Ф. И., 1981). Пусть произвольные разбиения куба E на совершенные коды длины n и произвольная подстановка на множестве n + 1 координат. Тогда множество является совершенным двоичным кодом длины 2n + 1.

Доказательство. Легко видеть, что длина кода равна 2n + 1 = 2m+1 1, где n = 2m 1. Мощность кода равна Проверим, что кодовое расстояние равно 3. Пусть u = (x, y, |y|) и v = (x, y, |y |) произвольные различные кодовые слова кода C. Возможны три случая.

d(u, v) 3.

2. Случай x = x, y = y аналогичен предыдущему.

3a. Пусть x = x, y = y и x, x Cin. Тогда d(x, x ) 3 и, следовательно, d(u, v) 3.

y D(i) и y D(j). Если |y| = |y |, то d(y, y ) 2, d(x, x ) 1 и, значит, d(u, v) 3.

При |y| = |y | имеем d(y, y ) 1, d((y, |y|), (y, |y |)) 2, d(x, x ) 1 и снова d(u, v) 3.

Теорема доказана.

Конструкция легко обобщается с помощью общей проверки на четность на случай расширенных совершенных кодов. Иллюстрацию к теореме 22 для случая, когда Ci и D(i) расширенные коды, n = 2m см. на рис. 8.

Замечания 1. Несложно показать, что эта конструкция является каскадной.

2. Конструкцию можно обобщить следующим образом: вместо двух разбиений пространства E n на совершенные коды рассмотреть разбиения двух различных кодов C1 и C2 на непересекающиеся подкоды с параметрами некоторых кодов C3 и C соответственно (см., например, теорему 63 в разд. 9.2.). В случае разбиений кодов C1 и C2 на смежные классы по кодам C3 и C4 (т. е. тривиальных разбиений) эта конструкция называется конструкцией X4 (см. [1, гл. 18]).

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

4. Класс совершенных кодов, описанный в этом разделе, не эквивалентен классу кодов Васильева. В 1984 г. К. Т. Фелпс обобщил эту конструкцию. В 2000 г. он доказал, что существует по крайней мере 963 и не более 15 408 неэквивалентных кодов Соловьевой длины 15. В 2004 г. В. А. Зиновьев и Д. В. Зиновьев доказали, что существует в точности 758 совершенных кодов длины 15 ранга 13. В 2006 г.

С. А. Малюгин построил 55 совершенных кодов длины 15 ранга 15.

Упражнение 24. Доказать, что Cin Cj = для любых i, j {1, 2,..., (n 1)/2}, i = j в теореме 21.

Упражнение 25. Построить класс разбиений куба E n на совершенные двоичные коды, используя теорему 22.

Упражнение 26. Обобщить каскадную конструкцию теоремы 22 для расширенных совершенных кодов.

Упражнение 27. Как построить код Хэмминга, используя конструкцию теоремы 22?

5.3. Коды Романова Рассмотрим применение каскадной конструкции для кодов, не являющихся совершенными, на примере кода длины 16, который имеет максимальную мощность среди всех кодов такой длины, исправляющих одну ошибку.

Хорошо известно, что существует разбиение множества D3 всех двоичных слов длины 9 веса 3 на семь систем троек Штейнера порядка 9. Обозначим эти системы троек Штейнера через Si, i = 1,..., 7. Таким образом, имеем Рассмотрим также разбиение куба E 7 на классы смежности по коду Хэмминга H 7 :

Пусть Si множество всех антиподальных слов к словам множества Si, т. е.

Теорема 23 (Романов А. М., 1983). Множество C 16, определенное как является кодом, исправляющим одну ошибку длины 16 мощности 2720.

Доказательство опустим, поскольку оно аналогично доказательству теоремы 22.

Применение конструкции Плоткина к этому коду позволяет получить хорошие коды длины n, где 2m n 2m + 2m4.

Подставляя полный четновесовой код D длины 17 и расширенный код Романова C длины 17 в конструкцию Плоткина, получаем код длины 34 со следующими хорошими параметрами:

Укорачивая этот код дважды, получаем коды длин 33 и 32 со следующими параметрами:

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

Теорема 24 (Романов А. М., 1983). Для любого целого числа n, удовлетворяющего 2m n 2m + 2m4 1, существует нелинейный (n, · 2nm1, 3) код, где = 85/64.

Следует отметить, что для кодов длины больше 16 существуют другие коды с хорошими параметрами, исправляющие одну ошибку. Например код Этциона длины 17, мощности 5312, с кодовым расстоянием 3 и код Хямяляйнена длины 18, мощности 10496, с кодовым расстоянием 3 (см. [19]). Используя конструкцию Плоткина и эти коды, можно аналогичным образом получить бесконечные классы кодов с хорошими параметрами.

Упражнение 28. Доказать теорему 23.

5.4. Коды Хямяляйнена Для изложения конструкции Хямяляйнена нам потребуется q-значный код Хэмминга.

5.4.1. Код Хэмминга над GF (q) Основная идея построения проверочной матрицы q-значного кода Хэмминга, где q > 2, такая же, как и для двоичного кода Хэмминга. В качестве столбцов проверочной матрицы возьмем все q-значные векторы длины m такие, что любые два из них линейно независимы и найдутся три линейно зависимых. В отличие от двоичного случая, мы не можем брать все ненулевые векторы длины m, поскольку некоторые из них могут быть линейно зависимыми. Например, векторы (11011) и (22022) линейно зависимы над полем Галуа GF (3). В целях устранения этой ситуации возьмем, например, в качестве столбцов проверочной матрицы все ненулевые столбцы такие, что первая ненулевая координата в каждом из них равна 1. Количество ненулевых векторов длины m над GF (q) равно q m 1. Нетрудно показать, что среди них имеем векторов с предписанным свойством. Следовательно, длина q-значного кода Хэмминга с m проверочными символами равна n = (q m 1)/(q 1), мощность кода равна q nm и по построению кодовое расстояние 3. Таким образом, мы построили код с параметрами Обозначим его через Hq.

Пример 2. Построим код Хэмминга над GF (3) с двумя проверочными символами. Рассмотрим проверочную матрицу в каноническом виде Она задает троичный код Хэмминга H3 длины 4. Переходя от этой проверочной матрицы к порождающей матрице в каноническом виде построим все кодовые слова. Они имеют вид где x1, x2 строки матрицы G и 1, 2 GF (3) :

Упражнение 29. Показать, что произвольный q-значный код с параметрами кода Хэмминга является совершенным.

5.4.2. Конструкция Хямяляйнена Основная идея конструкции Хямяляйнена состоит в следующем: сначала в пятизначном коде Хэмминга H5 с параметрами [6, 54, 3]5 ищется с помощью метода включений и исключений подкод максимально возможной мощности над алфавитом из четырех элементов, затем к этому подкоду применяется каскадирование с помощью классов смежности по двоичному коду Хэмминга длины 3. Рассмотрим детально эту красивую комбинаторную конструкцию.

Пусть код Хэмминга H5 длины n = 6 над полем Галуа GF (5), задан своей порождающей матрицей в каноническом виде:

Произвольное кодовое слово имеет вид где u1, u2, u3, u4 строки из G и i {0, 1, 2, 3, 4}, i = 1, 2, 3, 4. Мощность кода равна 54. Зафиксируем произвольный элемент k из множества {1, 2, 3, 4}. Удалим из кода H5 все кодовые слова, содержащие координату, равную k. Используя метод включений и исключений, вычислим число таких кодовых слов в коде Хэмминга H5 :

Имеется только один вектор с пятью координатами, равными k. Например, при k = 4, это вектор (424444). Полученный подкод фактически является сужением кода Хэмминга H5 над алфавитом из четырех элементов {0, 1, 2, 3}. Он имеет 164 кодовых слова и кодовое расстояние, равное 3.

Для получения кода длины 18 применим следующую каскадную конструкцию к полученному подкоду: вместо элемента 0 подставим слова двоичного кода Хэмминга H3 длины 3:

вместо каждого элемента из множества {1, 2, 3} возьмем слова класса смежности по коду H3 таким образом, что любым двум элементам будут отвечать различные классы смежности. В результате получим двоичный код с параметрами (18, 10496, 3), т. е. длины 18, мощности с кодовым расстоянием 3.

Таким образом, мы доказали следующее утверждение.

Теорема 25 (Хямяляйнен Х., 1988). Существует двоичный код с параметрами (18, 10496, 3).

Укорачивая одну координату в этом коде, получаем код, мощность которого меньше мощности известного кода Этциона длины 17 (описание кода Этциона можно найти в работе [12]).

Упражнение 30. Доказать, что подкод кода Хэмминга H5 над подалфавитом {1, 2, 3, 4}, который не содержит элемента 0, состоит из 160 кодовых слов. Именно по этой причине в конструкции Хямяляйнена существенно, что k = 0.

5.5. Каскадная конструкция Зиновьева (1988) Рассмотрим каскадную конструкцию, предложенную В. А. Зиновьевым в 1988 г.

Изложим ее для совершенных кодов (независимо этот метод построения в 1989 г.

был предложен Ф. И. Соловьевой). Эта конструкция может быть рассмотрена как обобщение конструкции Хямяляйнена, изложенной в предыдущем разделе.

Пусть A произвольный q-значный совершенный код с параметрами (n, |A|, 3), q = 2k, (например, код Хэмминга) над полем GF (2k ), k > 1 с двумя проверочными символами. Его длина равна n = 2k + 1. Пусть объединение двоичных совершенных кодов C0, C1,..., Cr задает разбиение векторного пространства E r, r = 2k 1.

Теорема 26 (Зиновьев В. А., 1988). Множество C N, определенное как является двоичным совершенным кодом длины N = nr = 22k 1, k > 1.

Доказательство. Длина кода, очевидно, равна Мощность кода несложно вычислить:

где N = 22k 1.

Убедимся, что кодовое расстояние равно 3. Рассмотрим два произвольных кодовых слова из A. Если x = y, то d(x, y) 3 и, значит, найдутся по крайней мере три координаты i, j, k, в которых различаются кодовые слова x и y. Следовательно, существуют три пары кодов в разбиении E n такие, что Отсюда следует Пусть x = y. Тогда имеем следующее множество кодовых векторов кода C N :

Учитывая, что каждое множество Cxi является совершенным двоичным кодом, получаем, что расстояние между любыми двумя различными векторами этого множества равно по крайней мере 3.

5.6. Каскадная конструкция Фелпса (1984) Пусть C1, C2,..., Cr и C1, C2,..., Cr произвольные разбиения полных четновесового кода и нечетно-весового кодов пространства E r (множество всех векторов пространства E r четного и нечетного веса соответственно) на расширенные совершенные двоичные коды длины r соответственно, пусть C m произвольный расширенный совершенный двоичный код длины m в E, в этом разделе пусть r = 2k, m = 2p. Для каждого вектора µ из C m возьмем r-значный код Cµ с кодовым расстоянием 2, длины m, |Cµ | = rm1 (Cµ является M DS-кодом). Напомним, что M DS-код C длины m, объема |C|, с кодовым расстоянием d над GF (r) это код, достигающий границы Синглтона, т. е. m logr |C| = d 1.

Теорема 27 (Фелпс К. Т., 1984). Множество C n, определенное как является совершенным расширенным двоичным кодом длины n = mr.

Далее код C m будем называть базовым кодом.

Доказательство. Для доказательства теоремы используем другое, эквивалентное данному выше определение кода C n :

Очевидно, что длина кода равна n = mr.

Также несложно вычислить мощность кода:

Здесь n = mr.

Несложно заметить, что для двух различных кодовых слов v и v кода C n таких, что µ = µ, j = j выполняется d(v, v ) 4.

Убедимся, что для кодового расстояния справедливо для любых µ, µ C m и j, j Cµ таких, что пары (µ, j) и (µ, j ) различны.

Возможны приведенные ниже случаи.

1. Предположим, µ = µ, j = j.

Тогда d(j, j ) 2 и найдутся координаты s, t такие, что js = js, jt = jt. Отсюда, учитывая, что Cjss и Cjss одновременно являются четно- или нечетно-весовыми совершенными расширенными двоичными кодами (аналогично для кодов Cjtt и Cj t ), имеем d(Cjss, Cjss ) 2 и d(Cjtt, Cj t ) 2. Следовательно, Векторы µ и µ принадлежат базовому коду C m, т. е. d(µ, µ ) 4 и найдутся четыре координаты t, s, e и l, в которых различаются µ и µ. Следовательно, имеются четыре пары совершенных кодов Cjii и Cj i, i {t, s, e, l} такие, что В итоге имеем d 4.

Замечания 1. Выкалывание произвольной координаты кода C n приводит к совершенному двоичному коду длины mr 1.

2. Для m = 2 код C m является тривиальным “расширенным совершенным” кодом, состоящим из одного вектора (01). Код Cµ является r-значным кодом длины 2, с кодовым расстоянием 2, которому отвечает подстановка на r элементах Таким образом, теорема 27 является обобщением теоремы 22.

3. Число неэквивалентных совершенных расширенных кодов длины n полученных по теореме 27 будет не менее 4. Обобщение конструкции Фелпса было дано Д. С. Кротовым в 2000 г.

5.7. Обобщенная каскадная конструкция Пусть B является qB -значным nB, K1, dB,1 кодом. Предположим, что код B разбивается на q1 подкодов:

где Bi является qB -значным (nB, K2, dB,2 ) кодом, i = 0, 1,..., q1 1.

Предположим далее, что Bi разбивается на q2 подкодов: для i = 0, 1,..., q имеем где Bi,j является qB -значным nB, K3, dB,3 кодом, K3 = q3.

Пусть произвольное кодовое слово b B имеет номер k в Bi,j, тогда тройка однозначно характеризует вектор b, это можно записать как b = b(i, j, k).

Для каждого = 1, 2, 3, рассмотрим q -значный nA, KA,, dA, код A и его произвольное кодовое слово a = (a1,..., anA ) A. Для любого s = 1,..., nA тройка (a1, a2, a3 ) дает кодовое слово b = b(a1, a2, a3 ) из B.

Теорема 28 (Зиновьев В. А., 1975). Множество C является qB -значным кодом длины nC = nA nB, мощности KA,1 KA,2 KA,3, с кодовым расстоянием Рассмотрим двоичный случай. Пусть B = E nB, B = E• B (E nB \ E• B ), где E• B полный четно-весовой код B, nB = 2. Рассмотрим произвольные разбиения кодов E• B и E n \ E• B на 2m расширенных совершенных кодов длины nB.

Пусть A1 произвольный расширенный совершенный двоичный код (nA, 2nA 1u, 4), nA = 2u. Пусть A2 является nB -значным (nA, nBA 1, 2) кодом (MDS кодом с расстоянием 2) и A3 является q3 -значным (nA, q3, 1) кодом, где q3 = 2nB 1m.

Используя конструкцию последней теоремы, формула (5.1) позволяет получить расширенный совершенный двоичный код C длины 2m+n.

Теорема 29 (Зиновьев В. А., Лобстейн А., 1997). Код C является расширенным совершенным двоичным кодом C длины 2m+n.

Замечания 1. Перечисление расширенных совершенных двоичных кодов длины 16, полученных обобщенной каскадной конструкцией, было получено В. А. Зиновьевым и Д. В. Зиновьевым в 2002 г., а именно ими было доказано, что существует 285 неэквивалентных таких кодов.

2. Следует отметить, что конструкция Фелпса может быть описана в терминах обобщенной каскадной конструкции Зиновьева.

Поля Галуа 6.1. Основные определения В этой главе приведем необходимые определения и утверждения о полях Галуа (см. [1, 2, 8, 21, 24]), которые потребуются в дальнейшем для изложения теории циклических кодов.

Определение. Алгебраическая система < F ; +, · > называется полем, если:

(i) < F ; + > является коммутативной группой по сложению (с единичным элементом 0), (ii) < F \ {0}; · > является коммутативной группой по умножению (с единичным элементом 1), (iii) Выполнены законы дистрибутивности: для любых элементов a, b, c F справедливо Порядком поля называется число его элементов. Поле F называется конечным, если оно имеет конечный порядок. В противном случае поле называется бесконечным.

Примерами бесконечных полей являются < Q; +, · >, < R; +, · >, < C; +, · >, где Q, R, C обозначают множества рациональных, вещественных и комплексных чисел соответственно, а операции + и · являются обычными операциями сложения и умножения. Примером конечного поля является кольцо вычетов < Zp ; +, · > целых чисел по модулю простого числа p. Далее такое поле будем называть простым и обозначать через Fp.

Определение. Характеристикой поля F называется наименьшее положительное целое число p такое, что в поле F справедливо равенство Поскольку в поле нет делителей нуля, характеристика p всегда является простым числом. Если такого числа не существует, то говорят, что поле F имеет характеристику 0. Очевидно, любое конечное поле имеет характеристику отличную от нуля.

Определение. Подкольцо < I; +, · > произвольного кольца < R; +, · > называется идеалом, если для любых элементов u I, v R выполняется u · v I и v · u I.

Например, подкольцо < pZ; +, · > является идеалом кольца целых чисел < Z; +, · >.

Пусть < F ; +, · > некоторое поле. Рассмотрим кольцо F [x] всех многочленов от переменной x с коэффициентами из поля F. Пусть s(x) произвольный многочлен из F [x]. Тогда множество образует идеал кольца F [x]. Верно и обратное, любой идеал кольца F [x] представим в виде совокупности произведений многочленов (6.1) для подходящего многочлена s(x). Без ограничения общности можно считать, что s(x) многочлен наименьшей степени в идеале (s(x)). Пользуясь алгоритмом Евклида для многочленов, можно показать, что в любом идеале такой многочлен s(x) существует и единствен. Рассмотрим фактор-кольцо F [x]/(s(x)) кольца всех многочленов F [x] по модулю идеала (s(x)).

Элементами фактор-кольца F [x]/(s(x)) являются всевозможные многочлены степени меньшей, чем степень s(x), а операции сложения и умножения в фактор-кольце производятся по модулю многочлена s(x). Если степень многочлена s(x) равна m и поле F конечно, то фактор-кольцо F [x]/(s(x)) содержит в точности |F |m элементов.

Определение. Многочлен f (x) из кольца F [x] называется неприводимым над полем F, если он нормированный (со старшим коэффициентом, равным 1) и не может быть представлен в виде произведения двух многочленов из F [x] меньших степеней.

Справедлива следующая Теорема 30. Пусть f (x) многочлен степени m с коэффициентами из простого поля Fp и (f (x)) идеал, порожденный многочленом f (x) в кольце Fp [x].

Фактор-кольцо Fp [x]/(f (x)), состоящее из pm элементов, является полем тогда и только тогда, когда многочлен f (x) неприводим над Fp.

Пример 3. Пусть p = 2, F2 = {0, 1}. Рассмотрим многочлен f (x) = 1 + x3 + x4.

Несложно проверить, что он неприводим над F2. Действительно, так как элементы 0 и 1 не являются корнями, то f (x) не имеет линейных многочленов x и x + 1 в качестве делителей. Легко проверить, что единственный неприводимый над F2 многочлен второй степени x2 +x+1 также не делит f (x). Следовательно, многочлен f (x) неприводим и по теореме 30 фактор-кольцо F2 [x]/(f (x)) является конечным полем с 24 элементами. Все 16 его элементов представимы как многочлены степени меньшей 4 с операциями сложения над F2 и умножения по модулю f (x). Например, Теорема 30 приводит к ряду вопросов:

1. Существует ли неприводимый над Fp многочлен степени m для произвольных простого числа p и положительного целого числа m?

2. Сколько существует неприводимых над Fp многочленов степени m?

3. Существуют ли другие конечные поля?

Ответы на эти вопросы будут приведены в следующем разделе.

6.2. Строение конечных полей Теорема 31. Для любого простого числа p и любого положительного целого числа m существует единственное с точностью до изоморфизма поле порядка pm.

Конечное поле порядка pm называется полем Галуа и обозначается GF (pm ) в честь первого исследователя таких полей Эвариста Галуа.

Порядком произвольного элемента некоторого конечного поля называется наименьшее целое положительное число k такое, что k = 1. Непосредственно из определения следует, что в конечном поле GF (pm ) для элемента порядка k все элементы 1,, 2,..., k1 различны. Поэтому порядок каждого элемента поля GF (pm ) конечен и не превышает числа pm 1. Элемент поля GF (pm ) называется примитивным, если его порядок равен pm 1. Многочлен, корнем которого является примитивный элемент, называется примитивным многочленом. Заметим, что не всякий неприводимый многочлен является примитивным.

Пусть (a, b) означает наибольший общий делитель чисел a и b. Имеют место следующие утверждения.

Лемма 6. Пусть элементы и коммутативной группы имеют порядки k и l соответственно, причем (k, l) = 1. Тогда порядок элемента равен kl.

Лемма 7. Пусть порядок элемента коммутативной группы равен k. Тогда порядок элемента l равен (k,l).

Справедлива Теорема 32. Ненулевые элементы поля GF (pm ) образуют циклическую группу порядка pm 1 относительно умножения.

Доказательство. Пусть n максимальный порядок ненулевых элементов поля GF (pm ) и элемент порядка n, т. е. n = 1. Отсюда следует, что n pm 1, так как все n степеней элемента различны между собой и не равны 0.

Пусть произвольный элемент поля порядка k, т. е. k = 1. Покажем, что тогда k | n (т. е. k делит n). Предположим противное: k n. Рассмотрим элемент (k,n). По лемме 7 его порядок равен (k,n), т. е.

Числа (k,n) и n взаимно просты, следовательно, по лемме 6 порядок элемента · (k,n) равен (n,k), т. е.

Но число (n,k) строго больше n, что противоречит выбору n. Отсюда заключаем, что k | n. Другими словами, любой ненулевой элемент поля является корнем многочлена xn 1 = 0. Поскольку степень этого многочлена равна n, то он имеет не больше, чем n различных корней в данном поле GF (pm ), поэтому pm 1 n.

Таким образом, показано, что в поле GF (pm ) найдется элемент порядка n = pm 1. Все ненулевые элементы GF (pm ) являются различными степенями.

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

Теорема 33 (Теорема Ферма). Каждый элемент поля GF (pm ) удовлетворяет уравнению т. е. в поле GF (pm ) справедливо разложение Следующая теорема говорит о том, что конечных полей порядка, отличного от p, не существует.

Теорема 34. Пусть F конечное поле порядка q характеристики p. Тогда для некоторого положительного целого числа m справедливо равенство q = pm.

Доказательство. Покажем, что поле F может быть построено как линейное mмерное пространство над GF (p) для некоторого положительного целого числа m.

Поскольку характеристика поля F равна p, можно показать, что поле F содержит GF (p) в качестве наименьшего подполя. Пусть m мощность базиса поля F над GF (p), т. е. произвольный элемент u F может быть представлен в виде для некоторых ai GF (p) и элементы v i GF (q), i = 1,..., m линейно независимы над GF (p). Тогда верно q pm. С другой стороны, так как элементы v 1,..., v m образуют базис поля F, все элементы u вида (6.2) различны при различных a1,..., am и принадлежат полю F. Следовательно, q pm. Таким образом, доказано q = pm.