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

Теорема 35. Для любых элементов a, b произвольного поля характеристики p и любого положительного целого числа s справедливо равенство В заключение приведем сводку основных результатов, относящихся к полям Галуа и необходимых нам в дальнейшем:

1. Число элементов произвольного поля Галуа равно степени простого числа.

2. Для любого простого числа p и любого целого числа m 0 существует единственное с точностью до изоморфизма поле Галуа GF (pm ).

3. Наименьшим подполем поля GF (pm ) является поле GF (p).

4. Поле GF (pk ) является подполем поля GF (pm ) тогда и только тогда, когда k делит m.

5. Любое поле GF (pm ) содержит хотя бы один примитивный элемент.

6. Над каждым полем Галуа GF (p) существует хотя бы один примитивный многочлен любой положительной степени.

6.3. Примеры конечных полей Пример 4. Построим конечное поле GF (24 ) с помощью теоремы 30. Используем для этого неприводимый над GF (2) многочлен f (x) = x4 + x + 1.

Согласно теореме 30, поле GF (24 ) состоит из всех многочленов степени меньшей 4:

Определим на множестве элементов операции умножения и взятия обратного элемента. Особенно удобно производить эти операции с помощью представления всех ненулевых элементов поля GF (24 ) в виде степеней некоторого примитивного элемента. Выберем его. Нетрудно проверить, что в качестве можно взять x. Действительно, все его степени по модулю f (x) различны между собой:

и, следовательно, порядок x равен 15.

Представим поле с помощью таблицы. Здесь число i для элемента = i называется логарифмом (по основанию выбранного примитивного элемента ). Логарифм элемента 0 полагают обычно равным.

Сложение элементов поля является обычным сложением по модулю 2 и не зависит от выбора примитивного элемента в поле. Например:

Умножение ненулевых элементов поля, представленных в виде степеней примитивного элемента, проводится путем сложения показателей степеней по модулю 15.

Например:

Операция умножения, в отличие от сложения, зависит от выбора многочлена f (x).

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

Нахождение обратного элемента покажем на примере. Найдем обратный элемент для многочлена x3 + x2 + 1 = 13, т. е. такой ненулевой элемент k, что Для этого запишем Нетрудно проверить, что решение найдено верно:

(x3 + x2 + 1) · (x2 ) = x5 + x4 + x2 = ((x2 + x) + (x + 1) + x2 ) mod (f (x)) = 1 mod (f (x)).

Возможность находить для заданного ненулевого многочлена обратный обеспечивается неприводимостью многочлена f (x) (аналогично и в общем виде для любого поля над GF (q)).

Несложно убедиться, что в построенном поле элементы 2, 4 также примитивные, а элементы 3, 5 примитивными не являются. Например, степени элемента порождают не все поле, а только элементы Заметим, что многочлен f (x) в нашем случае примитивный, поскольку x, его корень по построению, является примитивным элементом.

Пример 5. Построим конечное поле GF (24 ) с помощью неприводимого над GF (2) многочлена f (x) = x4 + x3 + x2 + x + 1. Найдем некоторый примитивный элемент поля GF (24 ). Например, элемент x не является примитивным элементом, так как его порядок равен 5, что меньше 24 1 = 15. Действительно, В качестве примитивного элемента можно взять x + 1, несложно убедиться что его порядок равен 15.

Представим поле с помощью таблицы.

Таким образом, мы убедились, что с помощью различных многочленов можно найти различные (но эквивалентные) представления поля Галуа GF (24 ).

6.4. Число неприводимых многочленов Функция Мёбиуса определяется следующим образом:

(1)r, если d произведение r различных простых чисел;

µ(d) = Рассмотрим простое поле GF (p). Обозначим через Ip (m) число неприводимых над GF (p) многочленов степени m.

Теорема 36. Справедливо Упражнение 31. Установить изоморфизм полей, приведенных в примерах 4 и 5.

Упражнение 32. Доказать леммы 6 и 7 и теорему 35.

Упражнение 33. Найти все неприводимые над GF (2) многочлены степени, не превышающей 3.

Упражнение 34. Построить поле Галуа GF (22 ), используя неприводимый многочлен x2 + x + 1. Найти таблицы сложения и умножения элементов поля.

Упражнение 35. Построить два представления поля Галуа GF (23 ), используя один неприводимый многочлен x3 + x + 1 и разные примитивные элементы. Указать изоморфизм этих представлений.

Упражнение 36. Доказать, что многочлен M (x) = x5 + x2 + 1 неприводим над GF (2).

Упражнение 37. Построить поля Галуа:

а) GF (23 ), используя неприводимый многочлен x3 + x2 + 1. Показать изоморфизм между построенным полем и полем из упражнения 35;

б) GF (32 ), используя неприводимый многочлен x2 + x + 2;

в) GF (33 ), используя неприводимый многочлен x3 + 2x + 1.

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

1. Класс циклических кодов содержит много кодов с конструктивно задаваемым расстоянием; с кодовым расстоянием, близким к наилучшему, в особенности для кодов длины 100.

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

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

Циклические коды обладают несложными процедурами кодирования и декодирования, имеют хорошие алгебраические свойства, их группы автоморфизмов содержат циклические подстановки. Все совершенные линейные коды, коды Рида-Маллера и другие коды, построенные еще до того, как Прейндж ввел понятие циклического кода и описал общие свойства таких объектов, являются кодами, которые после перестановки координат и несущественной модификации оказываются циклическими (см. [5]). Многие важнейшие блоковые коды, открытые позже, также оказались либо циклическими, либо тесно связанными с ними.

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

Обозначим через F простое конечное поле GF (p), где p простое число. Напомним, что F [x] кольцо всех многочленов от переменной x с коэффициентами из поля F. Оно ассоциативно, коммутативно и содержит единицу. В кольце F [x] рассмотрим фактор-множество F [x]/(xn 1), состоящее из классов вычетов кольца F [x] по модулю многочлена xn 1. Множество F [x]/(xn 1) замкнуто относительно операций сложения + и умножения · и, следовательно, является кольцом. Заметим, что множество F [x]/(xn 1) не является полем, так как многочлен xn 1 приводим.

Все многочлены степени не больше n1 попадают в различные классы вычетов и их можно выбрать в качестве представителей этих классов. Кольцо классов вычетов F [x]/(xn 1) изоморфно n-мерному векторному пространству над F :

В дальнейшем мы не будем различать векторы и многочлены степени меньше n, но из контекста всегда будет понятно, речь идет о многочленах или о векторах. Пусть дан многочлен Обозначим через инверсию многочлена c(x), записав его коэффициенты при степенях x в обратном порядке.

Определение. Идеалом I кольца F [x]/(xn 1) называется такое его линейное подпространство, что для любых многочленов r(x) F [x]/(xn 1) и c(x) I многочлен r(x) · c(x) принадлежит I.

Теорема 37. Подпространство кольца F [x]/(xn 1) является циклическим кодом тогда и только тогда, когда оно образует идеал.

Доказательство. Существенным моментом в доказательстве этой теоремы является то, что в кольце F [x]/(xn 1) умножение многочлена на x соответствует циклическому сдвигу вектора в пространстве F n. Действительно, Таким образом, вектор переходит в вектор т. е. получаем циклический сдвиг в F n.

Достаточность. Пусть C циклический код. Тогда для любого кодового вектора c, его циклический сдвиг принадлежит C. Другими словами, для любого кодового многочлена c(x) произведение x · c(x) принадлежит коду. Отсюда следует, в силу линейности циклического кода, что f (x) · c(x) является кодовым многочленом, где f (x) произвольный многочлен из F [x]/(xn 1). Следовательно, C идеал в кольце F [x]/(x 1).

Необходимость. Пусть подпространство D кольца F [x]/(xn 1) образует идеал.

Рассмотрим многочлен c(x) D. По определению идеала, многочлен f (x) · c(x) принадлежит D для любого многочлена f (x) F [x]/(xn 1). Тогда x · c(x) принадлежит D. Кроме того, сумма любых двух элементов из D также лежит в D и, следовательно, D циклический код.

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

Определение. Циклическим кодом длины n называется идеал кольца F [x]/(xn 1).

7.2. Порождающий многочлен Выберем в циклическом коде C ненулевой многочлен наименьшей степени, обозначим его степень через r. Умножим многочлен на подходящий элемент поля F, чтобы он стал нормированным (или приведенным), т. е. чтобы коэффициент при старшей степени многочлена равнялся 1. В силу линейности кода C, полученный многочлен также принадлежит C. Обозначим его через g(x).

Утверждение 12. Циклический код содержит единственный ненулевой нормированный многочлен наименьшей степени.

Доказательство. Пусть существуют два нормированных многочлена f (x) и g(x) наименьшей степени r. Тогда многочлен f (x)g(x), принадлежащий коду, имеет степень меньше r, что приводит к противоречию.

Определение. Нормированный ненулевой многочлен наименьшей степени, принадлежащий циклическому коду, называется порождающим многочленом кода и обозначается через g(x).

Теорема 38. Циклический код состоит из всех многочленов вида где g(x) порождающий многочлен кода степени r, степень f (x) меньше (n r).

Доказательство. Согласно тому что циклический код образует идеал в кольце F [x]/(xn 1) (см. теорему 37), произведение любого многочлена f (x) из F [x]/(xn 1) на g(x) принадлежит коду. Тогда произведения g(x) на все многочлены степени, меньшей чем n r, принадлежат C.

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

Пусть c(x) кодовый. Разделим его в кольце F [x]/(xn 1) с остатком на многочлен g(x). Имеем где степень s(x) меньше степени g(x), а степень q(x) меньше n r. Многочлен является кодовым, так как слагаемые в правой части принадлежат коду C и он линеен. Но степень многочлена s(x) меньше степени g(x) наименьшей степени ненулевого многочлена в C. Отсюда s(x) = 0 и c(x) = q(x)g(x), т. е. c(x) имеет в кольце F [x]/(xn 1) искомое представление.

Теорема 39. Циклический код длины n с порождающим многочленом g(x) существует тогда и только тогда, когда g(x) делит xn 1.

Доказательство. Необходимость. Пусть дан циклический код C длины n с порождающим многочленом g(x). Рассмотрим в кольце многочленов F [x] деление многочлена xn 1 на g(x) с остатком:

где степень r(x) меньше степени g(x). Переходя в кольцо F [x]/(xn 1), получаем Отсюда r(x) = q(x)g(x). Из теоремы 37 следует, что многочлен q(x)g(x) принадлежит коду и, следовательно, многочлен r(x) кодовый, причем deg r(x) < deg g(x), что противоречит утверждению 12. Таким образом, r(x) = 0.

Достаточность. Пусть многочлен g(x) делит xn 1. Покажем, что тогда существует циклический код длины n с порождающим многочленом g(x). Поскольку степень g(x) равна r, то размерность кода должна быть равна n r.

Рассмотрим векторы, отвечающие многочленам где r = deg g(x). Будучи циклическими сдвигами вектора g(x), они должны принадлежать циклическому коду с порождающим многочленом g(x). Так как эти циклические сдвиги линейно независимы, то матрица где имеет ранг n r (т. е. имеем искомое количество кодовых слов в базисе линейного кода). Следует отметить, что в матрицу G не может быть включен многочлен xnr+i g(x), i 0, поскольку по модулю многочлена xn 1 он равен линейной комбинации уже выбранных в G многочленов.

Покажем, что линейный код с порождающей матрицей G является идеалом, порожденным многочленом g(x), в кольце F [x]/(xn 1) и, кроме того, многочлен g(x) имеет наименьшую ненулевую степень в этом идеале. Для этого представим вектор, отвечающий произвольному многочлену из F [x]/(xn 1) в виде линейной комбинации строк матрицы G, по теореме 38 этот многочлен кодовый. Действительно, имеем Остается показать, что не существует в этом коде ненулевого многочлена со степенью, меньшей степени многочлена g(x). Если найдется такой кодовый многочлен r(x), то он представим линейными комбинациями строк матрицы G, т. е. имеет вид r(x) = q(x)g(x) для некоторого многочлена q(x). Отсюда, переходя в кольцо F [x], получаем где по условию теоремы xn 1 делится на g(x). Это возможно только в случае r(x) = 0. Таким образом, циклический код с порождающим многочленом g(x) построен.

Следствие 9. Порождающая матрица циклического кода длины n с порождающим многочленом g(x) = g0 + g1 x +... + gr xr имеет вид Матрица G имеет n столбцов и n r строк.

7.3. Кодирование циклических кодов Определение. Код длины n размерности k называется систематическим, если после вычеркивания некоторых (n k) столбцов из его кодовой матрицы остаются в точности все различные векторы длины k.

Утверждение 13. Любой циклический код эквивалентен систематическому коду.

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

Рассмотрим несколько общих принципов кодирования циклических кодов.

Первый систематический кодер. Пусть циклический код C длины n имеет порождающий многочлен g(x) степени r. Тогда размерность k кода C равна nr. Для построения порождающей матрицы G осуществим деление с остатком многочленов на g(x). Имеем Поскольку каждый многочлен xni ri (x) для i = 1, 2,..., k делится на g(x), то он является кодовым по теореме 38. Степень остатка ri (x) не превышает r 1. Пусть многочлен ri (x) имеет вид Порождающая матрица строки которой отвечают многочленам xni ri (x) для i = 1, 2,..., k, имеет приведенно-ступенчатый вид. Таким образом, для данного циклического кода найдено систематическое представление.

Второй систематический кодер. Можно рассмотреть систематическое кодирование для циклического кода длины n с порождающим многочленом g(x) степени r без использования его порождающей матрицы. Пусть задана информационная последовательность k = n r. Рассмотрим многочлен Домножая его на xr, имеем многочлен Разделив многочлен xr f (x) на g(x) с остатком, получим где степень r(x) меньше r. Так как многочлен xr f (x)r(x) делится на g(x), то по теореме 38 он принадлежит коду. В силу того что r(x) не меняет последние k компонент вектора, отвечающего многочлену xr f (x) r(x), эти компоненты совпадают с компонентами информационной последовательности. Таким образом, если многочлен r(x) имеет вид то информационному блоку отвечает кодовое слово Несистематический кодер. Рассмотрим простое несистематическое кодирование для циклического кода длины n с порождающим многочленом g(x) степени r.

Пусть информационному блоку k = n r отвечает многочлен Сопоставим ему кодовый многочлен c(x) по правилу Упражнение 38. Найти два систематических кодера для кода длины 7 с порождающим многочленом g(x) = x3 + x + 1. С помощью второго систематического кодера закодировать вектор (1101).

7.4. Проверочный многочлен По теореме 39 порождающий многочлен g(x) делит многочлен xn 1.

Определение. Многочлен h(x) такой, что называется проверочным многочленом циклического кода. Его степень k равна n r.

Утверждение 14. Для произвольного кодового слова c(x) циклического кода с проверочным многочленом h(x) справедливо c(x) · h(x) = 0 по модулю многочлена xn 1.

Доказательство. Согласно теореме 38, любой кодовый многочлен c(x) циклического кода имеет вид q(x) · g(x) и, следовательно, в фактор-кольце F [x]/(xn 1) справедливо равенство Теорема 40. Проверочная матрица циклического кода длины n с проверочным многочленом h(x) = h0 + h1 x +... + hk xk имеет вид Доказательство. Согласно утверждению 14, для любого кодового слова c(x) циклического кода выполняется Тогда равен где индексы берутся по модулю n. Эти равенства задают проверочные уравнения, которым должен удовлетворять код. Рассмотрим матрицу Из уравнений (7.3) следует, что если вектор кодовый, то Так как deg h(x) = k = n deg g(x) есть размерность кода, и строки H линейно независимы, то условие (7.4) является также достаточным для того, чтобы вектор c принадлежал коду. Таким образом, H проверочная матрица циклического кода с проверочным многочленом h(x).

Пример 6. Для двоичного циклического [n, n1, 2]-кода с проверкой на четность справедливо Тогда матрицы являются соответственно порождающей и проверочной матрицами кода.

7.5. Декодирование циклического кода Пусть при передаче кодового вектора произошли ошибки и на приемном конце получен вектор где вектор ошибок. На языке многочленов имеем Так как a(x), согласно теореме 38, делится на g(x), многочлены c(x) и (x) имеют при делении на g(x) одинаковые остатки. Другими словами, вектор ошибок находится среди тех наборов, которым соответствуют многочлены, дающие при делении на g(x) тот же остаток, что и многочлен c(x), соответствующий принятому вектору.

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

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

Упражнение 39. Пусть для передачи информации использовался циклический код длины 7 с порождающим многочленом g(x) = x3 + x + 1. Декодировать слово y = (1011110).

7.6. Минимальный многочлен и его свойства В этом разделе рассмотрим минимальные многочлены и их свойства, эти многочлены потребуются для построения циклических кодов, оценки их кодового расстояния (см. далее гл. 8).

Определение. Минимальным многочленом элемента GF (pm ) называется нормированный многочлен M (x) с коэффициентами из GF (p) наименьшей степени такой, что M () = 0.

Пусть M (x) минимальный многочлен над GF (p) элемента из GF (pm ). Тогда имеют место следующие его свойства:

1. Многочлен M (x) неприводим.

2. Если f (x) такой многочлен, что f () = 0, то M (x) делит f (x).

3. Многочлен M (x) делит xp x.

4. Степень многочлена M (x) не превосходит m.

5. Степень многочлена M (x) делит m.

6. Степень минимального многочлена M (x) примитивного элемента равна m.

7. Если многочлен M (x) является минимальным для элемента, то он минимален и для элемента p.

Множество целых чисел по модулю pm 1 следующим образом распадается на подмножества, называемые циклотомическими классами по модулю pm 1: класс, содержащий число s, имеет вид где ms наименьшее положительное целое число такое, что Пусть M (i) (x) минимальный многочлен элемента i из GF (pm ), где примитивный элемент поля. Из свойства 7 следует, что все ненулевые элементы поля GF (pm ) вида k, показатели степеней которых лежат в одном циклотомическом классе, имеют один и тот же минимальный многочлен. Иначе говоря, над GF (p) выполнено равенство 8. Если число i принадлежит циклотомическому классу Cs, то в поле GF (pm ) справедливо разложение Из теоремы Ферма (см. теорему 33) и свойства 8 следует Теорема 41. Над GF (p) справедливо равенство где s пробегает все множество представителей циклотомических классов по модулю pm 1.

Теорема 42. Многочлен xp x равен произведению всех нормированных неприводимых над GF (p) многочленов, степени которых делят m.

Эти теоремы позволяют находить неприводимые и минимальные многочлены.

Вернемся к примеру 4 поля GF (24 ) из параграфа 6.3. Сначала выпишем все циклотомические классы по модулю 15:

Затем рассмотрим разложение многочлена x16 x на неприводимые многочлены:

Задавая поле GF (24 ) с помощью неприводимого многочлена x4 +x+1 и примитивного элемента = x, получаем Элемент Минимальный многочлен элемента По свойству 6 полей Галуа (см. разд.6.2.) многочлен, задающий поле, всегда может быть выбран примитивным. Для этого нужно выбрать минимальный многочлен примитивного элемента. Однако задача определения какой из неприводимых многочленов является примитивным, весьма трудна.

Упражнение 40. Доказать свойства 1–7 минимальных многочленов.

7.7. Число циклических кодов Свяжем изложенную ранее теорию полей Галуа с циклическими кодами. В разд.

7.2. было показано, что циклический код длины n над полем GF (p) существует для каждого многочлена g(x), делящего многочлен xn 1, где n = pm 1 для некоторого m > 0. Согласно теореме 41, имеем где число циклотомических классов по модулю n, на которые разбиваются числа от 0 до n 1. Произведение произвольного подмножества следующего множества многочленов дает порождающий многочлен g(x) для некоторого циклического кода. Тогда, за исключением тривиальных случаев g(x) = 1 и g(x) = xn 1, получаем, что число нетривиальных циклических кодов длины n не превышает числа 2 2.

Какие из этих циклических кодов имеют наибольшее расстояние? Ответ на этот вопрос не прост.

Еще раз вернемся к примеру 4 из разд. 6.3. В разложении многочлена x15 1 имеем пять сомножителей (см. разд. 7.6.). Следовательно, получаем 25 2 = 30 нетривиальных циклических кодов длины 15. Рассмотрим, например, код с порождающим многочленом Так как степень g(x) равна 8, то размерность кода k = n 8 = 7. Однако определить кодовое расстояние кода из простых соображений не удается.

Упражнение 41. Построить циклический код длины 7 с порождающим многочленом g(x) = (x3 + x + 1), найти его проверочный многочлен, определить параметры кода.

Упражнение 42. Что собой представляет циклический код длины 15 с порождающим многочленом g(x)? Найти его проверочный многочлен, определить параметры кода:

б) g(x) = x(x + 1)(x2 + x + 1)(x4 + x3 + 1)(x4 + x3 + x2 + x + 1);

в) g(x) = (x + 1)(x2 + x + 1)(x4 + x3 + 1);

в случаях б и в построить коды.

Коды БЧХ Пусть примитивный элемент поля GF (pm ). Согласно теореме 41, над полем Галуа GF (p) справедливо разложение где s пробегает все множество представителей циклотомических классов по модулю pm 1. Пусть g(x) порождающий многочлен степени r некоторого циклическоm го кода длины n = p 1. Тогда, в силу теоремы 39 и приведенного разложения многочлена xp 1 1 на множители, имеем для некоторых представителей циклотомических классов i1,..., it.

Определение. Корни порождающего многочлена g(x) называются нулями кода.

Теорема 43. О нулях кода. Пусть попарно различные элементы 1,..., r из GF (pm ) являются корнями порождающего многочлена g(x) степени r циклического кода. Многочлен f (x) с коэффициентами из GF (p) принадлежит этому коду тогда и только тогда, когда Доказательство.

Необходимость. Пусть f (x) кодовый многочлен. Тогда по теореме 38 имеем f (x) = g(x)q(x), где deg q(x) < nr. Подставляя i вместо x для i = 1,..., r, получаем где g(i ) = 0. Отсюда следует, что i корень f (x).

Достаточность. Пусть i корень f (x) для всех i = 1,..., r и справедливо где deg r(x) < r. Подставляя i, получаем где f (i ) = 0 и g(i ) = 0. Отсюда следует r(i ) = 0 для всех i = 1,..., r. Поскольку deg r(x) < r и все i различны, заключаем, что r(x) = 0. Из теоремы 38 следует, что f (x) кодовый.

8.2. Циклическое представление кода Хэмминга Теорема 44. Двоичный код Хэмминга является циклическим кодом с порождающим многочленом g(x) = M (1) (x).

Доказательство. Проверочная матрица двоичного кода Хэмминга Hn длины n = 2m 1, по определению, состоит из всех ненулевых векторов-столбцов длины m.

Пусть примитивный элемент поля Галуа GF (2m ). Тогда является порождающим элементом мультипликативной группы поля GF (2m ) и все элементы различны и могут быть представлены как ненулевые двоичные m-векторы. Таким образом, проверочную матрицу H двоичного кода Хэмминга с параметрами можно представить в виде где каждый элемент i должен быть заменен на соответствующий ему двоичный вектор-столбец длины m.

По определению, вектор c = (c0, c1,..., cn1 ) принадлежит коду Hn тогда и только тогда, когда выполнено т. е.

Другими словами, элемент является корнем многочлена c(x):

Последнее равенство, согласно свойству 2 минимальных многочленов (см. разд. 7.6.), имеет место в том и только том случае, когда минимальный многочлен M (1) (x) элемента делит многочлен c(x). Таким образом, код Hn состоит из всех многочленов, кратных многочлену M (1) (x).

корень примитивного минимального многочлена M (1) (x) = 1 + x + x3.

8.3. Определитель Вандермонда Для доказательcтва теоремы 45 о границе Боуза (см. следующий разд.) нам потребуется матрица Вандермонда.

Определение. Матрицей Вандермонда называется матрица где a1, a2,..., an элементы некоторого конечного поля.

Лемма 8 Вандермонда. Если все ai, i = 1,..., n различны, то det A = 0.

Доказательство. Индукцией по n докажем формулу Для n = 2 имеем det A = det = a2 a1. Формула (8.1) справедлива.

Предположим, что (8.1) выполнена для n 1. Докажем ее для n. Запишем Домножим каждый i-й столбец матрицы (кроме последнего) на a1 и прибавим его к (i + 1)-му столбцу. От этого, как известно, определитель матрицы не изменится.

Получим Раскладывая определитель по первой строке, имеем Вынесем из каждой j-й строки множитель (aj a1 ), тогда Отсюда, по предположению индукции, заключаем Таким образом, формула (8.1) доказана. Очевидно, что det A отличен от нуля тогда и только тогда, когда все ai различны.

Следующая теорема называется границей Боуза-Чоудхури-Хоквингема (кратко границей БЧХ) или теоремой о конструктивном расстоянии циклического кода. Эта теорема позволяет оценивать кодовое расстояние снизу.

Теорема 45. Граница БЧХ. Пусть g(x) порождающий многочлен циклического кода C длины n такой, что существуют целые числа b 0 и > 1 такие, что выполняется т. е. 1 подряд идущих степеней примитивного элемента поля GF (pm ) являются корнями g(x). Тогда кодовое расстояние d не меньше.

Замечание. Число называется конструктивным расстоянием кода.

Доказательство. Рассмотрим произвольный кодовый вектор c = (c0, c1,..., cn1 ) и соответствующий ему многочлен c(x). Поскольку элементы b, b+1,..., b+2 являются нулями кода C, то по теореме 43 о нулях кода имеем Отсюда получаем систему уравнений Иначе говоря, выполняется равенство не обязательно является полной проверочной матрицей кода C, поскольку порождающий многочлен g(x) возможно имеет и другие корни, отличные от b, b+1,..., b+2.

Кроме того, строки этой матрицы могут оказаться линейно зависимыми. Другими словами, код C, заданный проверочной матрицей H, будет содержать в качестве подкода код C, но возможно не будет совпадать с ним. Достаточно оценить кодовое расстояние кода C, так как оно, очевидно, не будет больше кодового расстояния кода C. Поэтому если мы покажем, что любые 1 или менее столбцов матрицы H линейно независимы, то кодовое расстояние кода C (а следовательно, и C) будет по меньшей мере согласно теореме 3 из разд. 1.2.

Предположим, что кодовый вектор c имеет вес w меньший, т. е. найдутся w линейно зависимых столбцов H и w <. Пусть ненулевые координаты вектора c имеют номера a1, a2,..., aw. Построим квадратную матрицу H из матрицы H следующим образом: выберем w первых строк из матрицы H и вычеркнем все столбцы с номерами, отличными от a1, a2,..., aw. Таким образом, матрица H имеет вид Из равенства (8.2) следует, что Последнее равенство возможно, только если матрица H вырождена, т. е. det H = 0.

Но с другой стороны, имеем так как определитель в последнем равенстве есть определитель Вандермонда со всеми различными элементами, и согласно лемме 8 он не равен нулю.

Из полученного противоречия следует, что в линейном коде C не существует кодового слова веса меньше. Следовательно, кодовое расстояние C не меньше.

Определение. Кодом БЧХ над полем GF (p) длины n = pm 1 с конструктивным расстоянием > 1 называется циклический код с порождающим многочленом наименьшей степени, нулями которого являются элементы где примитивный элемент поля GF (pm ) и b некоторое неотрицательное целое число.

Замечание. Для кодов БЧХ в литературе имеет место более общее определение.

Нами рассматриваются так называемые примитивные коды БЧХ, т. е. коды, длина которых равна n = pm 1. Далее термин примитивные будет опущен. Коды БЧХ при b = 1 иногда называют кодами БЧХ в узком смысле.

Справедливо следующее (эквивалентное) определение кодов БЧХ.

Определение. Кодом БЧХ над полем GF (p) длины n = pm 1 с конструктивным расстоянием > 1 называется циклический код с порождающим многочленом где b некоторое неотрицательное целое число.

Теорема 46 Код БЧХ над GF (p) длины n = pm 1 с порождающим многочленом для некоторого целого b 0 имеет параметры Доказательство. Согласно теореме 45 о границе БЧХ, кодовое расстояние кода не меньше. Из вида порождающего многочлена кода следует, что проверочная матрица кода БЧХ равна где каждый элемент должен быть заменен на соответствующий столбец из m элементов поля GF (p). Строки этой матрицы задают проверочные соотношения кода.

Общее число строк равно ( 1)m, но они могут оказаться линейно зависимыми, поэтому для числа проверок выполняется и, следовательно, для размерности кода имеем что завершает доказательство теоремы.

8.6. Двоичные коды БЧХ Отдельно рассмотрим случай двоичных кодов БЧХ в узком смысле, т. е. b = 1.

Теорема 47. Двоичный код БЧХ длины n = 2m 1 с порождающим многочленом имеет параметры Доказательство. При p = 2 в силу свойства 7 минимальных многочленов (см. разд. 7.6.) имеем Отсюда следует, что степень g(x) может быть понижена. А именно, определяя g(x), можно не рассматривать минимальные многочлены для степеней примитивного элемента с четными показателями.

Конструктивное расстояние данного в теореме кода БЧХ равно 2t. В силу отмеченного свойства минимальных многочленов, коды с конструктивными расстояниями 2t и 2t + 1 совпадают, для каждого из них порождающий многочлен имеет вид Таким образом, deg g(x) tm. Для размерности кода выполняется соответственно Проверочная матрица кода равна где каждый элемент должен быть заменен соответствующим двоичным векторомстолбцом длины m. Второй столбец содержит степени элемента :

показатели которых лежат в различных циклотомических классах по модулю 2m 1.

В разд. 8.2. показано, что двоичный код Хэмминга имеет циклическое представление. Этот факт также непосредственно следует из доказанной теоремы.

Следствие 10. Код БЧХ, исправляющий одну ошибку, имеет параметры порождающий многочлен g(x) = M (1) (x) и является кодом Хэмминга.

Следствие 11. Код БЧХ, исправляющий две ошибки, имеет параметры где m 3 нечетно и порождающий многочлен g(x) = M (1) (x) · M (3) (x).

Доказательство. Кодовое расстояние непосредственно следует из теоремы 47.

Докажем, что и k = n 2m. По теореме 47 имеем g(x) = НОК{M (1) (x), M (2) (x), M (3) (x), M (4) (x)} = НОК{M (1) (x), M (3) (x)}.

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

Поскольку примитивный элемент поля GF (2m ), то по свойству 6 минимальных многочленов степень M (1) (x) равна m. Так как m нечетно, имеем (3, 2m 1) = 1.

По лемме 7 из разд. 6.2. получаем, что порядок элемента 3 равен 2m 1. Таким образом, многочлен M (3) (x) примитивен и по свойству 6 его степень также равна m. Минимальные многочлены M (1) (x) и M (3) (x) неприводимы согласно свойству минимальных многочленов, поэтому и размерность кода k в точности равна n 2m.

Коды БЧХ (более точно: примитивные коды БЧХ) асимптотически плохие, а именно справедливо следующее утверждение.

Теорема 48 Для любой бесконечной последовательности [n, k, d]-кодов БЧХ над GF (q) скорость кода k/n и отношение d/n стремятся к нулю с ростом n.

8.7. Коды Рида-Соломона 8.7.1. Определение и свойства Коды Рида-Соломона это коды БЧХ над GF (q), q = pm, длина n которых равна q 1, q = 2, а порождающий многочлен имеет вид для некоторых b 0, > 1. Иногда удобно рассматривать b равным единице. Такие коды представляют собой значительный практический и теоретический интерес и обладают целым рядом хороших свойств. В следующей теореме, например, покажем, что для кода Рида-Соломона можно точно вычислить как кодовое расстояние, так и мощность.

Теорема 49. Код Рида-Соломона длины n имеет мощность q n+1 и кодовое расстояние d = n k + 1 =.

Доказательство. Поскольку порождающий многочлен кода Рида-Соломона длины q 1 имеет вид (8.3) для некоторых b 0, > 1, код Рида-Соломона это БЧХ-код с конструктивным расстоянием длины n = q 1, q = 2. Размерность этого циклического кода равна k = n deg g(x) = n + 1. Согласно границе Синглтона (см. теорему 4 разд. 1.2.), если B (n, k, d)-код, то n k d 1. Иными словами, d n k + 1. Отсюда для кода Рида-Соломона имеем d = n k + 1, а следовательно, этот код является M DS-кодом.

Достоинства кодов Рида-Соломона:

1. Коды Рида-Соломона удобно использовать, когда требуется код, длина которого меньше, чем размер поля, так как, являясь MDS-кодами, они имеют наибольшее возможное минимальное расстояние.

2. Они используются для получения двоичных кодов с очень большими минимальными расстояниями.

3. Коды Рида-Соломона используются при построении каскадных кодов с хорошими параметрами.

4. Они используются при построении кодов, исправляющих пакеты ошибок (см. подробнее разд. 8.7.2.).

Пример 8. Рассмотрим код Рида-Соломона над GF (5) длины 4 с конструктивным расстоянием 3. В качестве примитивного элемента поля GF (5) возьмем, например, = 2, тогда g(x) = (x )(x 2 ) = (x 2)(x 4) = x2 + 4x + 3. Код Рида-Соломона имеет 52 = 25 кодовых слов длины 4, среди них например, Упражнение 43. Найти все 25 кодовых слов этого кода.

Добавление к коду общей проверки на четность не всегда увеличивает его минимальное расстояние, если коды недвоичные и есть слова нечетного веса. Например, добавление общей проверки на четность к коду над GF (3) с кодовой матрицей не увеличивает кодовое расстояние. Однако для кодов Рида-Соломона с порождающим многочленом g(x) = (x ) · (x 2 ) ·... · (x 1 ) кодовое расстояние всегда увеличивается на 1.

Теорема 50. Пусть P многочленом Тогда расширение каждого кодового слова c = (c0, c1,..., cn1 ) посредством добавления общей проверки на четность над GF (p) приводит к коду с параметрами [n + 1, k, d + 1].

Доказательство. Пусть w(c) = d. Кодовому слову c соответствует многочлен c(x), и минимальный вес c увеличивается до d + 1, если Но c(x) = c0 + c1 x +... + cn1 xn1 и, следовательно, Покажем, что c(1) = 0. По теореме 38 (см. разд. 7.2.) имеем c(x) = a(x)g(x), где g(x) порождающий многочлен кода. По определению g(x), поскольку 0 не является его корнем заключаем, что g(1) = 0. Для a(x) имеем a(1) = 0, так как в противном случае многочлен c(x) делился бы на многочлен (x 1) и, согласно границе БЧХ (см. теорему 45), кодовое слово c имело бы вес не менее чем d + 1. Следовательно, c(1) = a(1)g(1) = 0, то есть кодовое расстояние полученного кода увеличивается на 1.

Упражнение 44. Построить код Рида-Соломона с параметрами [3, 2, 2] над полем Галуа где 2 + + 1 = 0 и рассмотреть расширенный код с параметрами [4, 2, 3].

8.7.2. Использование кодов Рида-Соломона для получения Элементы поля GF (pm ) могут быть представлены m-векторами над GF (p) (вспомним пример поля GF (24 ), где элементы поля были представлены двоичными векторами длины 4). Рассмотрим q-значный код Рида-Соломона с параметрами где q = pm. Произведя замену на p-значные векторы, получим p-значный код с параметрами Если q = 2m, то полученные двоичные коды имеют часто большое минимальное расстояние. Далее покажем это.

Пусть v1,..., vm базис векторного пространства GF (2m ) над GF (2), т. е. базис в m-мерном единичном кубе E m. Тогда любой элемент, принадлежащий GF (2m ), представим в виде где bi принадлежит GF (2). Рассмотрим отображение (b1,..., bm ). Это отображение переводит линейные коды над GF (2m ) в линейные над GF (2), т. е. сохраняет линейность, но необязательно при этом сохраняет цикличность!

Построим из кода Рида-Соломона двоичный код с большим кодовым расстоянием. Пусть вектор c = (c0,..., cn1 ) принадлежит [n, k, d]-коду Рида-Соломона над GF (2m ). Заменим элементы ci соответствующими двоичными m-векторами и к каждому такому m-вектору добавим общую проверку на четность. Получим двоичный код с параметрами Аналогичное преобразование можно применить к расширенному коду Рида-Соломона, что приводит к двоичному коду с параметрами Полученный код является каскадным кодом.

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

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

2) ошибки типа "потеря пакета".

Определение. Пакетом длины s называется вектор, все ненулевые элементы которого расположены среди s подряд идущих компонент, из которых первая и последняя являются ненулевыми.

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

Такой метод передачи данных использует код Рида-Соломона, а точнее двоичный код, полученный из кода Рида-Соломона. Иногда рассматриваются более сложные преобразования кода Рида-Соломона в двоичный с помощью процедуры перемежения, с применением двух кодеров, например, при использовании функции четности для любого двоичного набора длины m либо каскадирования. Однако двоичный код, полученный из кода Рида-Соломона, все же довольно плохо исправляет случайные ошибки. В этом случае может быть использован код Юстесена.

8.8. Коды Юстесена Рассмотрим код Рида-Соломона над полем GF (2m ) с параметрами примитивный элемент поля GF (2m ). Рассмотрим произвольный вектор Пусть кода Рида-Соломона и составим с помощью него вектор длины 2n над GF (2m ) следующего вида Заменяя в этом векторе каждый элемент ai из GF (2m ) отвечающим ему двоичным вектором длины m, получаем двоичный вектор длины 2mn. Полученное множество двоичных слов образует код Юстесена с параметрами который по построению является линейным кодом. Кодовое расстояние D определяется из следующего предложения.

Утверждение 15. Минимальное расстояние D кода Юстесена удовлетворяет неравенству где для кодового расстояния d исходного кода Рида-Соломона справедливо:

Доказательство. Любое ненулевое кодовое слово кода Юстесена содержит по крайней мере d различных двоичных векторов длины 2m, где u = 0 и v = 0. Очевидно, что количество различных векторов длины 2m малого веса невелико. Следовательно, вес любого ненулевого кодового слова кода Юстесена должен быть большим.

Минимальный вес ненулевого слова кода Юстесена не меньше суммы весов d ненулевых двоичных векторов длины 2m минимально возможного веса, а именно:

где в первом слагаемом под знаком суммы стоит количество единиц в наборе длины 2m, а во втором количество оставшихся столбцов в двоичном аналоге проверочной матрицы. Причем вес w определяется из соотношения Нетрудно видеть, что коды Юстесена являются каскадными кодами. Они также хороши тем, что являются асимптотически хорошими кодами.

Другие коды 9.1. Матрицы Адамара, коды Адамара 9.1.1. Матрицы Адамара Определение. Матрицей Адамара порядка n называется n n матрица H, элементами которой являются +1 и 1 такая, что где En единичная матрица размера n n.

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

Матрица H носит название матрицы Адамара, поскольку ее детерминант достигает границы, принадлежащей Адамару. Справедлива Теорема 51 (Адамар Ж., 1897). Если A = (aij ) произвольная вещественная (n n) матрица с элементами 1 aij 1, то | det A| nn/ (т. е. det2 A nn ).

Для матрицы Адамара справедливо det H · H T = (det H)2 = nn. Имеем т. е. H T · H = nEn. Отсюда следует также, что столбцы матрицы H обладают теми же свойствами, что и строки матрицы H.

Очевидно, что перестановка строк или столбцов матрицы H, а также умножение строк или столбцов матрицы H на 1, переводят H в другую матрицу Адамара H.

Такие матрицы Адамара будем называть эквивалентными. Это равносильно тому, что где P и Q мономиальные матрицы перестановки длины n с элементами +1 и 1.

Напомним, что матрица называется мономиальной, если в каждой строке и каждом столбце имеется точно один ненулевой элемент. В нашем случае для P и Q эти ненулевые элементы равны +1 или 1. Матрица P осуществляет перестановку и меняет знаки у строк H, а матрица Q у столбцов.

Для данной матрицы Адамара H всегда можно найти эквивалентную ей матрицу Адамара, первая строка и первый столбец которой целиком состоят из +1. Такая матрица Адамара называется нормализованной.

Пример 9. При n = 1 имеем H(1) = (1), Перестановка строк, кроме первой, и столбцов, кроме первого, не нарушают нормализованности матрицы Адамара. Но, вообще говоря, могут существовать эквивалентные нормализованные матрицы, которые не получаются одна из другой простой перестановкой строк и столбцов.

Упражнение 45. Показать, что матрицы Адамара порядков 2 и 4 существуют и единственны с точностью до эквивалентности.

Матрицы Адамара порядков 8 и 12 также единственны с точностью до эквивалентности. Существует пять неэквивалентных матриц Адамара порядка 16 и три неэквивалентных матрицы порядка 20. Для n = 24 число неэквивалентных матриц Адамара равно 60, для n = 28 таких матриц 487.

Теорема 52. Если существует матрица Адамара порядка n > 2, то n кратно 4.

Доказательство. Без ограничения общности предположим, что H представлена в нормализованном виде и пусть n > 2. Найдется матрица, эквивалентная матрице H, первые три строки которой имеют вид Тогда из ортогональности строк имеем следующую систему уравнений Решая эту систему, получаем i = j = k = l = n/4, откуда следует, что 4 делит n.

Гипотеза. Матрицы Адамара существуют для всех n 0(mod 4).

Существует большое количество методов построения матриц Адамара. Наименьший порядок, для которого матрица Адамара не построена, равен n = 428 = 4 · (2002 г.).

Приведем неполный спектр значений n, для которых построены матрицы Адамара:

2) n = pr + 1 0(mod 4) для простого p;

3) n = h(pr + 1), где h 2 порядок матрицы Адамара;

4) n = h(h 1), где h произведение чисел вида 1 и 2;

5) n = h(h + 3), где h и h + 4 произведения чисел вида 1 и 2;

6) n = h1 h2 (pr + 1)pr, где h1, h2 > 1 порядки матриц Адамара.

Рассмотрим два особенно важных в теории кодирования метода построения матриц Адамара.

9.1.2. Матрица Сильвестра Прямым, или кронекеровым, произведением двух матриц называется матрица A B порядка (mn mn):

Упражнение 46. Доказать свойства:

Теорема 53. Если существуют матрицы Адамара порядков m и n, то их прямое произведение есть матрица Адамара порядка m · n.

Доказательство. Пусть Hm и Hn две матрицы Адамара порядков m и n соответственно. Тогда Отсюда легко вытекает следующий метод построения матриц Адамара.

Теорема 54. Если Hn матрица Адамара порядка n, то матрица Адамара порядка 2n.

Пример 10. Матрица Адамара порядка 4, полученная из матрицы Адамара Начиная с тривиальной матрицы H(1) = (1), методом, описанным в теореме 54, получим последовательность матриц H(1), H(2), H(4),..., H(2k )... Такие матрицы называются матрицами Сильвестра. Они имеют порядки, равные степени двойки Упражнение 47. Построить матрицу Адамара H8.

9.1.3. Матрица Адамара по типу Пэйли Для описания конструкции Пэйли построения матриц Адамара, потребуются квадратичные вычеты и некоторые их свойства.

Определение. Пусть p > 2 простое число. Числа b 0(mod p) делятся на два класса, называемые квадратичными вычетами и квадратичными невычетами в зависимости от того, имеет сравнение решение по модулю p или не имеет.

Пример 11. При p = 7:

22 = 4(mod 7) вычет;

32 2(mod 7) вычет (число 2 представимо в виде 32, где 3 < 7);

невычет, так как сравнение x2 3(mod 7) не имеет решения, в чем легко убедиться простым перебором;

Новых вычетов не получили, следовательно, 1, 2 и 4 все вычеты по модулю 7.

Для того чтобы найти все вычеты по модулю p, нужно рассмотреть все числа 1, 2,..., p 1, но достаточно рассмотреть квадраты чисел от 1 до (p 1)/2, так как Свойства квадратичных вычетов 1. Произведение двух квадратичных вычетов или невычетов является квадратичным вычетом, произведение квадратичного вычета на невычет является невычетом.

2. Критерий Эйлера. Пусть p > 2 простое. Число a, взаимно простое с p, является квадратичным вычетом по модулю p тогда и только тогда, когда и является невычетом по модулю p тогда и только тогда, когда 3. Если p = 4k + 1, то число 1 является квадратичным вычетом, если p = 4k 1, то число 1 является невычетом.

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

4. Если примитивный элемент поля Галуа GF (p), где p простое, то, нетрудно показать, что квадратичные вычеты задаются четными степенями элемента.

Определение. Пусть p простое нечетное число. Функция (i), называемая символом Лежандра, определяется на множестве целых чисел следующим образом:

(i) = 1, если остаток от деления i на p является квадратичным вычетом по (i) = 1, если остаток от деления i на p является квадратичным невычетом Теорема 55. Для любого c 0(mod p) справедливо Доказательство. Так как произведение двух квадратичных вычетов или невычетов есть вычет, а произведение вычета на невычет есть невычет, то Если b = 0, то (0) = 0 и вклад в сумму слагаемого при b = Пусть b = 0 и пусть z такое число, что zb b + c(mod p). Если b пробегает множество {1, 2,..., p 1}, то z пробегает множество {0, 2, 3,..., p 1} (действительно, так как c 0(mod p), имеем z = 1). Разным числам b отвечают разные z. Пусть это не так, т. е.

Тогда z(b b ) b b (mod p), или (z 1)(b b ) 0(mod p), т. е. в силу b = b имеем z 1(mod p), что невозможно.

Рассмотрим исходную сумму:

для них равен 1.

Метод построения Пэйли дает построение матрицы Адамара порядка n = p+1, кратного 4 (или порядка n = pm + 1, кратного 4, если используются квадратичные вычеты над полем GF (pm )), где p простое.

Для конструкции Пэйли потребуется матрица Джекобстола Q = (qij ), которая является (p p)-матрицей, где qij = (j i), строки и столбцы матрицы Q пронумерованы числами 0, 1,..., p 1.

Пример 12. При p = 7 числа 1, 2 и 4 являются квадратичными вычетами, следовательно, (1) = (2) = (4) = 1. Матрица Джекобстола имеет вид При p = 4k 1 число 1 является квадратичным невычетом по свойству 2 и (1) = 1. Поэтому следовательно, матрица Q Имеет место следующее утверждение.

Лемма 9. Справедливо QQT = pE J и QJ = JQ = 0p, где J матрица, элементами которой являются единицы, а 0p матрица, состоящая из нулей.

Доказательство. Пусть P = (pij ) = QQT. Тогда Если i = j, то где b = k i и c = i j по предыдущей теореме.

Легко проверяется утверждение QJ = JQ = 0p (действительно, каждый столбец и строка матрицы Q содержит равное число (p 1)/2 элементов 1 и 1).

Построим, используя Q, матрицу H. Обозначим, как и прежде, через 1 и 0 векторы длины p, состоящие из единиц и нулей соответственно.

Теорема 56. Матрица является матрицей Адамара (типа Пэйли).

Доказательство. Рассмотрим произведение Используя предыдущую лемму и тот факт, что по определению матрицы Q выполняется Q + QT = 0, получаем Следовательно, Другими словами, получили нормализованную матрицу Адамара типа Пэйли порядка p + 1.

9.1.4. Коды Адамара Пусть Hn нормализованная матрица Адамара. Заменим всюду 1 на 0, а 1 на 1, тогда Hn превращается в двоичную матрицу Адамара An. Так как строки Hn ортогональны, то любые две строки матрицы An совпадают в n/2 позициях, следовательно, расстояние Хэмминга между ними равно n/2.

Из матрицы An построим три кода Адамара.

1. Код An с параметрами (n 1, n, n/2), состоящий из строк матрицы An с выколотой первой координатой.

Пример 13. Код Адамара A8 с параметрами (7, 8, 4), полученный из матрицы Адамара типа Пэйли. Кодовые слова это все циклические сдвиги вектора (1001011) и нулевой вектор длины 7. Иначе говоря, Пример 14. Код Адамара A12 с параметрами (11, 12, 5), полученный из матрицы Адамара типа Пэйли:

содержащий также нулевой вектор длины 11.

2. Код Bn с параметрами (n 1, 2n, (n/2) 1), состоящий из векторов кода An и их дополнений.

Пример 15. Код Адамара B12 с параметрами (11, 24, 5) со следующими кодовыми словами:

3. Код Cn, (n, 2n, n/2), состоящий из строк матрицы An и их дополнений.

Код An является симплексным. Это означает, что расстояние между любыми двумя кодовыми словами равно n/2.

Если H матрица Сильвестра, то An, Bn и Cn групповые коды. Если H матрица Адамара типа Пэйли, то полученные коды нелинейны для любого n > 8.

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

9.1.5. Связь кодов Адамара с кодом Хэмминга Рассмотрим связь кодов Адамара An, n = 2k 1 с кодом Хэмминга. Для этого вспомним определение ортогонального кода.

Определение. Если C линейный [n, k]-код над F, то дуальный или ортогональный к нему код C определяется как множество всех векторов, ортогональных всем кодовым словам кода C:

Если код C имеет проверочную матрицу H и порождающую G, то дуальный код C имеет проверочную матрицу G и порождающую H.

Теорема 57. Код, дуальный к коду Хэмминга, является кодом Адамара An, построенным из матрицы Сильвестра. Справедливо и обратное.

Доказательство будем проводить индукцией по m, где n = 2m 1.

Пусть m = 2. Рассмотрим код Хэмминга длины 3, заданный следующей проверочной матрицей Она является порождающей матрицей ортогонального кода к коду Хэмминга. Кодовые слова имеют вид Добавляя проверку на четность и заменяя 0 на 1 и 1 на -1, получаем т. е. матрицу Сильвестра (см. пример 10).

Пусть для n = 2m1 1 имеем: код, ортогональный коду Хэмминга, является кодом Адамара A2m1 с порождающей матрицей Hn, являющейся проверочной матрицей кода Хэмминга длины n. Покажем, что матрица вида является проверочной матрицей кода Хэмминга порядка 2n 1. Действительно, это так, поскольку число столбцов равно 2n 1 и все они являются различными векторами длины m (в Hn все столбцы различные векторы длины m 1).

порождают код с кодовой матрицей Добавляя вектор (0... 01... 1), получаем код, порожденный матрицей H, кодовая матрица которого имеет вид Отсюда, добавив столбец из нулей, имеем матрицу где H(n) матрица Сильвестра порядка n, следовательно, по теореме 54 матрица H(2n) также является матрицей Сильвестра.

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

Код Адамара An называется также симплексным, поскольку его вершины образуют в E n правильный симплекс расстояние между любыми двумя кодовыми словами одно и то же и равно 2. На рис. 9 приведен пример кода A3, вершины которого образуют правильный тетраэдр.

9.2. Коды Рида-Маллера Определение кодов Рида-Маллера (RM-кодов) удобнее всего приводить в терминах булевых функций. Рассмотрим произвольную булеву функцию f (x1,..., xm ) от m переменных, тождественно не равную нулю. В качестве кодовых слов кода РидаМаллера длины n = 2m будут выбраны двоичные векторы, являющиеся наборами значений булевых функций специального вида. Но прежде чем задать способ выбора этих функций, приведем некоторые определения и утверждения. Каждой строке таблицы истинности произвольной функции f, для которой значение функции равно единице, можно поставить в соответствие элементарную конъюнкцию длины m, равную единице на этом наборе, т. е. произведение всех переменных x1,..., xm, взятых с отрицанием или без. Дизьюнкция этих элементарных коньюнкций называется совершенной дизъюнктивной нормальной формой (СДНФ) булевой функции f.

Далее, используя закон де Моргана удалим все дизъюнкции в представлении функции f (x1,..., xm ), другими словами, функция f (x1,..., xm ) будет выражена через функции из множества {&, }. Так как f произвольная булева функция, тождественно не равная нулю, то отсюда следует, что система функций {&, } полна. Напомним, что система булевых функций {f1,..., fs,...} называется полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

Теорема 58 (Жегалкин). Каждая булева функция может быть однозначно представлена посредством полинома по модулю 2.

Этот полином носит название полинома Жегалкина.

Доказательство. Рассмотрим произвольную булеву функцию f (x1,..., xm ), представленную системой функций {&, }. Выражая всякий раз отрицание через сложение: x = x + 1 и опуская знаки &: x&y = xy, после раскрытия скобок и приведения подобных членов x + x = 0, xx = x, используя дистрибутивность, получим многочлен где ai1...is, a {0, 1} константы для различных i1,..., is. Полученный многочлен является полиномом Жегалкина. Теперь покажем, что произвольная булева функция однозначно представляется полиномом Жегалкина. Подсчитаем число различных полиномов Жегалкина Для фиксированного s, s m, имеем возможностей выбора произведения xi1 ·... · xis. Так как 0 s m, то всего возможно различных элементарных конъюнкций от переменных x1,..., xm, взятых без отрицания. Далее, так как коэффициенты ai1...is, a могут принимать два значения 0 или 1, получаем 22 различных полиномов Жегалкина, каждому из которых отвечает единственная булева функция. С другой стороны, число всех булевых функций от m переменных также равно 22.

Из теоремы Жегалкина получаем, что функции образуют базу пространства E 2 всех булевых функций от m переменных. Теперь перейдем к определению кодов Рида-Маллера.

Определение. Двоичный код Рида-Маллера RM(r, m) порядка r, 0 r m, это совокупность векторов длины 2m, отвечающих полиномам от m переменных степени не больше r.

Код Рида-Маллера RM(1, m) первого порядка ортогонален расширенному коду Хэмминга и совпадает с кодом Адамара Bm. В свою очередь, расширенный код Хэмминга является кодом Рида-Маллера RM(m 2, m) порядка m 2. Из определения кода Рида-Маллера порядка r вытекает, что он состоит из всех линейных комбинаций векторов, соответствующих произведениям Эти произведения задают базис кода Рида-Маллера порядка r. Отсюда следует, что размерность кода равна все кодовые слова имеют четный вес.

Код Рида-Маллера RM(r, m) любого порядка r, 0 r m, может быть описан с помощью конструкции Плоткина.

Теорема 59. Cправедливо Доказательство. Рассмотрим произвольное кодовое слово f из RM(r+1, m+1).

С одной стороны, оно представляет собой двоичный вектор длины 2m+1, с другой стороны многочлен от (m + 1) переменных, степень которого не больше r + 1.

Перепишем многочлен f (x1,... xm+1 ) следующим образом где степень g(x1,..., xm ) не больше r + 1, а степень h(x1,..., xm ) не больше r. Пусть g и h векторы длины 2m, отвечающие многочленам g(x1,..., xm ) и h(x1,..., xm ) соответственно, иными словами, g и h это наборы значений булевых функций (от переменных x1,..., xm ), представленных этими многочленами. Поскольку степень g(x1,..., xm ) не больше r + 1, то, по определению кода Рида-Маллера, вектор g принадлежит коду RM(r + 1, m) порядка r + 1. Аналогично, h принадлежит коду RM(r, m).

Рассмотрим многочлен g(x1,..., xm ) как многочлен от переменных x1,..., xm+1 :

Вектор длины 2m+1, отвечающий этому многочлену, равен (g, g). Действительно, из булевой функции g(x1,..., xm ) от m переменных мы получили булеву функцию g (x1,..., xm+1 ) от (m + 1) переменных, где переменная xm+1 является фиктивной.

Вторая половина таблицы истинности булевой функции g (x1,..., xm+1 ), отвечающая значению 1 переменной xm+1, дублирует первую.

Рассмотрим также многочлен h (x1,..., xm+1 ) как многочлен от переменных x1,..., xm+1, определенный с помощью многочлена h(x1,..., xm ) следующим образом Нетрудно видеть, что этому многочлену отвечает двоичный вектор длины 2m+1 вида (02, h). Таким образом, получили Теорема 60. Минимальное расстояние кода Рида-Маллера RM(r, m) порядка r, Доказательство. Доказательство будем проводить индукцией по m.

Пусть m = 1. В этом случае имеем следующие два тривиальных кода РидаМаллера порядков 0 и 1 соответственно:

RM(0, 1) = {(00), (11)} с кодовым расстоянием 2;

RM(1, 1) = {(00), (01), (11), (10)} с кодовым расстоянием 1.

Пусть для любого (m1) теорема верна и минимальное расстояние кода RM(r, m1) порядка r равно 2m1r для любого r, удовлетворяющего условию 0 r m 1.

Рассмотрим конструкцию Плоткина для кода RM(r, m), изложенную в предыдущей теореме:

По предположению индукции, кодовое расстояние кода RM(r 1, m 1) равно 2m1(r1) = 2mr, а кода RM(r, m 1) равно 2mr1. Нетрудно видеть, что для произвольных кодовых слов (u, u + v) и (u, u + v ) из RM(r, m) (см. доказательство теоремы Плоткина в гл. 1). Очевидно, что между кодовыми словами кода RM(r, m) достижимо расстояние, равное 2mr.

Таким образом, код Рида-Маллера RM(r, m) порядка r имеет параметры:

• кодовое расстояние d = 2mr.

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

Теорема 61. Для любых r, 0 r (m 1) код Рида-Маллера RM(m r 1, m) ортогонален коду Рида-Маллера RM(r, m).

Доказательство. Рассмотрим произвольные векторы f и g, где f RM(m r 1, m), g RM(r, m). По определению кодов Рида-Маллера, степени многочленов f (x1,...,, xm ) и g(x1,..., xm ) не превосходят mr 1 и r соответственно. Следовательно, степень многочлена f (x1,..., xm ) · g(x1,..., xm ) не превосходит m 1 и отвечающий этому многочлену вектор принадлежит коду RM(m 1, m). Поскольку в коде RM(m1, m) все вершины имеют четный вес, то есть скалярное произведение векторов f и g равно нулю, то получаем RM(m r 1, m) RM(r, m).

откуда следует, что что доказывает теорему.

9.2.1. Коды с параметрами кодов Рида-Маллера Выколотый код Рида-Маллера RM (r, m) получается удалением какой-либо координаты и имеет параметры Покажем, как, используя свитчинговые и каскадные конструкции, можно строить мощные классы кодов с параметрами кодов Рида-Маллера и выколотых кодов РидаМаллера. Двоичные коды (не обязательно линейные) с параметрами выколотого кода Рида-Маллера порядка r будем обозначать LRM (r, m) и называть выколотыми кодами Рида-Маллера. Линейный код RM (r, m) является частным случаем кодов LRM (r, m).

Сначала рассмотрим применение конструкции Васильева из теоремы 13. Посредством этого метода построения кодов можно получить много нелинейных выколотых кодов Рида-Маллера LRM (r, m)) порядка r.

Пусть LRM (r, m 1) и LRM (r 1, m 1) произвольные выколотые коды Рида-Маллера порядков r и r 1 соответственно длины n = 2m1 1. Справедливо следующее утверждение:

произвольная функция из кода LRM (r 1, m 1) в множество {0, 1}, является кодом с параметрами выколотого кода Рида-Маллера порядка r длины n = 2m 1, т. е. LRM (r, m)-кодом.

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

Замечание. Этот класс кодов оказался хорошим представителем для реализаций -схемами. А. К. Пулатовым была получена квадратичная нижняя оценка сложности -схем, реализующих коды с параметрами выколотых кодов Рида-Маллера.

Используя теорему 62, можно показать, что существуют нетривиальные разбиения выколотых кодов Рида-Маллера LRM (r, m 1) порядка r длины n = 2m на выколотые коды Рида-Маллера порядка r 1 длины n = 2m1 1:

(доказательство этого факта аналогично доказательству теоремы 21).

Теорема 63 (Соловьева Ф. И., 1981). Пусть даны произвольные разбиения выколотых кодов Рида-Маллера порядка r:

где t = 2. Пусть произвольная подстановка на t элементах. Тогда множество является LRM (r, m)-кодом.

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

Замечание. Легко видеть, что применение проверки на четность к LRM (r, m)-кодам позволяет получить широкие классы неэквивалентных нелинейных кодов с параметрами кодов Рида-Маллера порядка r длины n 16. Среди этих кодов могут оказаться коды с полезными свойствами, например с транзитивной группой автоморфизмов (код называется транзитивным, если его группа автоморфизмов действует транзитивно на всех его кодовых словах), а также коды, являющиеся Z4 -линейными (линейными над кольцом Z4 ). Последние могут найти применение в криптографии, например, в криптосистемах МакЭлиса с открытыми ключами.

9.3. Коды Препараты Определение. Максимальный двоичный код длины n = 4m, где m 2 с кодовым расстоянием d = 6 называется кодом Препараты. Его мощность равна 2n /n2.

Первый такой код (для каждой допустимой длины) построил Франко Препарата в 1968 г.

В 1971–1973 гг. Н. В. Семаков, В. А. Зиновьев и Г. В. Зайцев исследовали свойства кодов с параметрами кодов Препараты и связь их с двоичными совершенными кодами, исправляющими одну ошибку. Ими было показано, что коды Препараты, помимо максимальности, обладают некоторыми весьма нетривиальными свойствами, а именно эти коды равномерно упакованы и дистанционно инвариантны. Кроме того, было показано, что любой код Препараты является подкодом некоторого расширенного совершенного кода той же длины с расстоянием 4 (причем единственного) и в некотором смысле плотно упакован в нем.

В 1972 г. Я. М. Геталс и С. Л. Сновер показали, что линейных кодов Препараты не существует. В 1976 г. И. Думер и позднее, в 1983 г. Р. Д. Бакер, Я. Х. Ван Линт и Р. М. Вилсон построили семейство кодов Препараты, содержащее оригинальный код Препараты. В 1994 г. А. Р. Хэммонс, П. В. Кумар, А. Р. Кальдербанк, Н. Дж. А. Слоэн и П. Соле предложили конструкцию первого кода Препараты с групповой структурой Z4 -линейного кода Препараты.

Конструкция Думера-Бакера Соответствие между множествами и векторами элемент поля GF (2m ). Имеем Рассмотрим множество состоящее из логарифмов элементов поля по основанию (полагаем, как и раньше в гл. 6, что = 0). Произвольному подмножеству X множества элементов поля GF (2m ) взаимно однозначно сопоставим двоичный вектор c длины n + 1, координаты которого занумерованы с помощью множества I:

по правилу Другими словами, вектор c является характеристическим вектором множества X:

его ненулевые позиции указывают элементы поля, включаемые в множество X. Например, пустому множеству отвечает нулевой вектор. Введем некоторые обозначения для множеств X, Y GF (2m ):

как обычно через |X| обозначается мощность множества X;

XY симметрическая разность множеств X и Y. Заметим, что эта операция на множествах отвечает двоичному сложению соответствующих характеристических векторов;

X +a сдвиг множества X на элемент поля a, т. е. X + a = {x + a | x X};

aX умножение X на ненулевой элемент поля a, т. е. aX = {ax | x X}.

Используя соответствие (9.1), произвольный двоичный вектор длины 2(n + 1) = 2m+1 можно описать парой (X, Y ), где X, Y подмножества множества элементов поля GF (2 ). Далее мы не будем делать различия между парами множеств (X, Y ) и двоичными векторами длины 2m+1. Из контекста далее будет ясно, речь идет о множествах или о векторах.

Построение кодов Препараты Группа автоморфизмов поля GF (2m ) состоит из всех отображений вида где = 2k, k = 0, 1,..., m 1. Рассмотрим из них такие, что отображения взаимно однозначны. Другими словами, для этого выберем такие, что выполняются условия Считаем далее, что = 2k удовлетворяет условиям (9.2).

Теорема 64. Код P () длины 2m+1, состоящий из всех двоичных векторов, описываемых парами (X, Y ), удовлетворяющими условиям:

является кодом Препараты.

Для доказательства этой теоремы потребуется ввести некоторые дополнительные определения и изучить свойства кодов P (). Сначала приведем следующие простые свойства поля GF (2m ).

Лемма 10. Для любых элементов a, b поля GF (2m ) и любого = 2k имеет место тождество Доказательство. Согласно теореме 35 (см. разд. 6.2.), имеем Тогда, преобразовав (a + b)+1 к виду (a + b) (a + b), получим искомое тождество.

Несложно доказывается Лемма 11. Для любого множества X из носителя поля GF (2m ) и любого = 2k Напомним, что двоичный код называется дистанционно-инвариантным, если число кодовых слов, находящихся на некотором расстоянии l от фиксированной кодовой вершины, не зависит от выбора этой вершины, а зависит только от l.

Утверждение 16. Код P () дистанционно-инвариантен.

Доказательство. По построению код P () содержит вектор (, ). Пусть (X0, Y0 ) произвольный вектор из P (). Для доказательства утверждения достаточно построить взаимно однозначное соответствие между множествами кодовых векторов, находящихся на расстоянии l от вершин (, ) и (X0, Y0 ) соответственно, где l некоторое фиксированное расстояние.

Зададим следующее взаимно однозначное отображение:

по правилу Заметим, что расстояние от (X, Y ) до (X0, Y0 ) равно весу вектора (X X0, Y Y0 ) и равно расстоянию от (U, V ) до (, ). Покажем, что если (X, Y ) принадлежит коду, то и вектор (U, V ) ему принадлежит. В силу взаимной однозначности отображения f, этого будет достаточно для доказательства дистанционной инвариантности P ().

Пусть (X, Y ) кодовый вектор. Проверим, что вектор (U, V ) также кодовый, т. е.

для него выполняются условия (9.3):

2) Докажем равенство Действительно, имеем 3) Проверим выполнение равенства Преобразуя первое слагаемое, с учетом леммы 10, имеем Используя лемму 11, получаем Для второго слагаемого, используя лемму 10, имеем Таким образом, дистанционная инвариантность кода P () доказана.

Утверждение 17. Группа автоморфизмов кода P () содержит отображения:

Доказательство получается непосредственной проверкой выполнения условий (9.3) для образов кодового вектора (X, Y ) под действием отображений 1–4.

Утверждение 18. Код P () имеет кодовое расстояние 6.

Доказательство. Поскольку код P () содержит нулевую вершину и в силу утверждения 16 дистанционно инвариантен, достаточно показать, что минимальный ненулевой вес его кодовых слов равен 6.

Заметим, что все кодовые векторы (X, Y ), в силу п. 1 условия (9.3), имеют четный вес. Из пунктов 1 и 2 условия (9.3) следует, что в коде нет слов веса 2. Покажем, что в коде P () нет слов и веса 4. Предположим обратное. Возможны два случая:

Случай 1. Вектор ({a, b}, {c, d}) кодовый, где a = b и c = d.

Из утверждения 17 следует, что без ограничения общности в качестве a можно взять 0. Действительно, рассмотрим кодовое слово веса 4, полученное из выбранного действием автоморфизма (X, Y ) (X a, Y a). По п. 3 условия (9.3) имеем Тогда c+1 = d+1. Поскольку удовлетворяет условиям (9.2), отображение взаимно однозначно, и, следовательно, c = d, что противоречит выбору c и d.

Случай 2. Вектор ({a, b, c, d}, ) кодовый, где все элементы a, b, c, d различны.

В силу утверждения 17, считаем a = 0. Из пп. 2 и 3 условия (9.3) имеем Тогда, выражая из первого равенства d и подставляя во второе, с учетом леммы получаем В силу условия (9.2), отображение взаимно однозначно, поэтому b = c. Противоречие с выбором b, c.

Покажем теперь, что код P () содержит слово веса 6. Рассмотрим попарно различные элементы a, b, c поля GF (2m ). Определим d и e из системы уравнений Несложно убедиться, что вектор ({0, e}, {a, b, c, d}) удовлетворяет условиям (9.3) и, следовательно, является кодовым.

Утверждение 19. Мощность кода P () длины N = 2m+1 равна 2N /N 2.

Доказательство. Определим число пар (X, Y ), удовлетворяющих условиям (9.3).

Выберем множество X так, чтобы мощность |X| была четной. Это можно сделать 2 способами. Выберем множество Y из ненулевых элементов поля так, чтобы выполнялись пункты 2 и 3 условия (9.3). Затем, если необходимо, добавим в множество Y элемент 0, чтобы мощность |Y | была четной.

Пусть X =. Тогда для Y выполняется система равенств см. пункты 2 и 3 в условии (9.3). Эту систему над GF (2m ) можно рассматривать как систему из 2m уравнений над полем GF (2), заменив каждый элемент поля GF (2m ) на вектор-столбец длины m над GF (2).

Пусть примитивный элемент поля GF (2m ). Поскольку удовлетворяет условиям (9.2), элемент +1 имеет порядок 2m 1, и следовательно, также является примитивным элементом поля GF (2m ). Минимальные многочлены M (1) (x), M (+1) (x), согласно свойствам 1 и 6 из разд. 7.6., неприводимы и имеют степень m. Тогда множество Y, удовлетворяющее системе (9.5), соответствует кодовому слову циклического кода длины n = 2m 1 с порождающим многочленом M (1) (x) · M (+1) (x). Мощность такого циклического кода равна 2n2m.

Выберем другое множество X четной мощности. Тогда всевозможным множествам Y таким, чтобы выполнялись условия (9.3), будут соответствовать векторы некоторого смежного класса циклического кода длины n = 2m 1 с порождающим многочленом M (1) (x) · M (+1) (x). Значит для фиксированного множества X число способов выбора подходящего множества Y равно 22 12m.

Таким образом, число различных пар (X, Y ), удовлетворяющих условиям (9.3), а значит принадлежащих коду P (), равно Утверждение доказано.

Из утверждений 18 и 19 немедленно вытекает теорема 64.

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

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

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

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

Изложенный материал опробирован при чтении лекций в течение ряда лет в Новосибирском государственном университете. Автор выражает признательность всем студентам, которые помогали шлифовать в дискуссиях презентации многих тем, теорем, лемм, а также своим детям Ване Могильных и Маше Соловьевой за постоянную моральную поддержку в период написания этого пособия и помощь в напечатании лекций. Глубокая благодарность моим коллегам Валентину Афанасьеву, Алексею Пережогину, Владимиру Потапову, Денису Кротову за тщательное чтение пособия и полезные замечания, позволившие улучшить текст; моим рецензентам В. В. Зяблову, С. А. Малюгину, Ю. Л. Сагаловичу; моему ученику аспиранту Института математики СО РАН Антону Лосю за помощь в напечатании текста, сопровождение текста красивыми рисунками, считывание глав, оригинальную обложку; Н. Н. Токаревой, оказавшей всестороннюю техническую помощь при подготовке настоящего пособия в формировании буклета, в печатании текста, подготовке рисунков, основательной и творческой считке текста, в написании раздела 9.3, посвященного кодам Препараты;

О. Г. Заварзиной за подготовку верстки к печати.

Библиографический список основной литературы [1] Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки:

Пер. с англ. М.: Связь, 1979. 744 с.

[2] Берлекэмп Е. Р. Алгебраическая теория кодирования: Пер. с англ. М.: Мир, [3] Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ.

М.: Мир, 1986. 576 с.

[4] Галлагер Р. Г. Теория информации и надежная связь: М.: Сов. радио, 1974.

[5] Касами Т., Токура Н., Ивадари Е., Инагаки Я. Теория кодирования: Пер. с яп.

М.: Мир, 1978. 576 с.

[6] Колесник В. Д., Полтырев Г. Ш. Курс теории информации. М.: Наука, 1982.

[7] Конвей Дж. Н., Слоэн Н. Дж. А. Упаковки шаров, решетки и группы: Пер. с англ. М.: Мир, 1990. Т. 1, 2.

[8] Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, [9] Фано Р. М. Передача информации. Статистическая теория связи. М.: Мир, 1965.

[10] Шеннон К. Е. Работы по теории информации и кибернетике. М.: Иностр. лит., [11] Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980. 399 с.

[12] Handbook on coding theory, Amsterdam: North-Holland, 1998.

[13] Solov’eva F. I. "On perfect codes and related topics" Com2 Mac Lecture Note Series 13, Pohang 2004. 80 p. (доступна по адресу http://www.codingtheory.gorodok.net/literature/lecture-notes.pdf) Библиографический список дополнительной литературы [14] Аршинов М. Н., Садовский Л. Е. Коды и математика (рассказы о кодировании).

М.: Наука, 1983. 144 c.

[15] Васильев Ю. Л. О негрупповых плотно упакованных кодах. Проблемы кибернетики. М: Физматгиз, 1962. Вып. 8. С. 337–339.

[16] Гоппа В. Д. Введение в алгебраическую теорию информации. М.: Наука: Физматлит, 1995.

[17] Calderbank A. R. The Art of Signaling: Fifty Years of Coding Theory. IEEE Trans. Inform. Theory. 1998. Vol. 44, № 6. P. 2561–2595. (доступна по адресу http://citeseer.ist.psu.edu/calderbank98art.html) [18] Камерон П., Ван Линт Дж. Х. Графы. Коды и схемы: Пер. с англ. М.: Наука, [19] Cohen G., Honkala I., Litsyn S., Lobstein A. Covering codes. Netherlands: Elsevier, [20] Колмогоров А. Н. Теория информации и теория алгоритмов. М.: Наука, 1987.

[21] van Lint J. H. Introduction to Coding Theory. Springer; Verlag; Berlin; Heidelberg, [22] Марков А. А. Введение в теорию кодирования. М.: Наука: Физматлит, 1982.

[23] Реньи А. Дневник: Записки студента по теории информации: Пер. с венг. М.:

[24] van Tillborg H. Error correcting codes – a rst course. Sweden, Chartwell Bratt Ltd., [25] Яглом А. М., Яглом И. М. Вероятность и информация. М.: Наука, 1973.

[26] Сайт "Теория кодирования в Новосибирском государственном университете" по адресу http://www.codingtheory.gorodok.net.

[27] Сайт "Math Tree" : каталог математических интернет ресурсов (раздел "Теория кодирования") по адресу http://www.mathtree.ru.

Предметный указатель асимптотически хорошее семейство кодов, Адамара, базовое множество, граница Варшамова-Гилберта, Плоткина, Синглтона, Синглтона для нелинейных кодов, Хэмминга, группа автоморфизмов кода, симметрий кода, двоичный симметричный канал связи, 7 систематический, по максимуму правдоподобия, 22 эквивалентный, идеал, 61, квадратичный обобщенная каскадная, 59 вероятность, лемма типа Сильвестра, 95 полная система функций, кронекерово произведение, 95 обобщенная, мономиальная, 93 пропускная способность, порождающая, циклического кода, 73 расстояние Хэмминга, циклического кода, метод каскадный, свитчинга, многочлен минимальный, неприводимый, нормированный, порождающий, приведенный, примитивный, проверочный, нули кода, 81 совершенная дизъюнктивная нормальная стандартное расположение, теорема Васильева, 37, Глаголева, Моллара, Пулатова, Ферма, Шапиро и Злотника, Шеннона, о границе БЧХ, о связи проверочной и порождающей о существовании совершенных кодов, о циклическом представлении кода Хэмминга, формула Стирлинга, функция Мебиуса, характеристика поля, циклотомический класс, число неприводимых многочленов, циклических кодов, энтропия, свойства, Оглавление 3.3. Необходимые комбинаторно-вероятностные 8.7.2. Использование кодов Рида-Соломона для получения двоичных

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

Уч.-изд. л. 17,7. Усл. печ. л. 14,4. Тираж 200 экз.

Редакционно-издательский центр НГУ. 630090, Новосибирск-90, ул. Пирогова, 2.