Теория кодирования

Сидельников В.М.

Теория кодирования

МОСКВА

ФИЗМАТЛИТ ®

УДК 519.725
ББК 32.811.4
С 34

С и д е л ь н и к о в В. М.
Теория кодирования. — М.: ФИЗМАТЛИТ,
2008. — 324 с. — ISBN 978-5-9221-0943-7.

В книге рассмотрены методы построения и свойства кодов, корректирующих ошибки. Начальные главы содержат подробное изложение нескольких
традиционных направлений классической теории кодирования и могут быть
положены в основу университетского курса лекций. Во второй части книги
представлены результаты, которые почти никогда не затрагивались в учебной
литературе по теории кодирования.
Как первая, так и вторая части книги включают в себя большое число
оригинальных результатов автора, в течение нескольких лет читавшего лекции
по отдельным разделам теории кодирования студентам и аспирантам МГУ
им. М. В. Ломоносова.
Для студентов университетов и аспирантов, обучающихся по специальностям «Математика» и «Прикладная математика».

ISBN 978-5-9221-0943-7

c⃝ ФИЗМАТЛИТ, 2008

c⃝ В. М. Сидельников, 2008

ОГЛАВЛЕНИЕ

Введение . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8

Г л а в а 1. Базовые понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
§ 1.1. Пространство Хемминга . .. . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.1.1. Метрика Хемминга (11).
1.1.2. Линейный код (12).
1.1.3. Двойственный код (13).
1.1.4. Пространство, образованное равновесными двоичными векторами (15).
§ 1.2. Сфера в n-мерном евклидовом пространстве. .. . . . . . . . . . . . .
15
1.2.1. Метрика на сфере (15).
1.2.2. Ортогональные и унитарные преобразования (17). 1.2.3. Орбитный код (18).
§ 1.3. Изометрическое вложение орбитного кода на унитарной сфере
в орбитный код на евклидовой сфере. .. . . . . . . . . . . . . . . . . .
19
§ 1.4. Изометрическое расположение кода в пространстве Хемминга на
сфере евклидова пространства . .. . . . . . . . . . . . . . . . . . . . . .
23
1.4.1. Вложение двоичного пространства Джонсона в евклидову
сферу (33).

Г л а в а 2. Оценки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
§ 2.1. Верхняя оценка числа элементов кода . .. . . . .. . . . . . . . . . . . .
35
2.1.1.
Оценка
Хемминга
(35).
2.1.2. Оценки
сверху
для
числа
элементов
равновесных
кодов (37).
2.1.3. Оценка
Элайса–Бассалыго (38).
2.1.4. Оценка Плоткина и матрицы
Адамара (38).
2.1.5. Оценки Синглтона и Грайсмера (43).
2.1.6. Оценка для числа элементов антиподального кода (45).
§ 2.2. Оценки существования кода . .. . . . . . . . . . . . . . . . . . . . . . .
47
2.2.1. Оценка Варшамова–Гилберта (47).
2.2.2. Асимптотические границы (48).
2.2.3. Основные задачи теории кодирования (51).

Г л а в а 3. Центральные функции на линейном пространстве Хемминга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
§ 3.1. Специальные функции . .. . . . . . . . . . . . . . . .. . . . . . . . . . . .
53
3.1.1. Характеры (53).
3.1.2. Автоморфизмы группы G (54).
3.1.3. Скалярное произведение (55).
3.1.4. Классы сопряженных элементов (56). 3.1.5. Центральные функции относительно
подгруппы H группы Aut(G) (56).
§ 3.2. Ортогональные многочлены . .. . . . . . . . . . . . . . . . . . . . . . . .
60

Оглавление

3.2.1. Элементарная абелева группа (60).
3.2.2. Примарная
группа порядка pl (63). 3.2.3. Многочлены Кравчука и мономиальная группа (64).
3.2.4. Симметрическая группа в качестве
группы H и полная весовая функция кода (66).
3.2.5. Ортогональные многочлены для примарного кольца вычетов (68).
3.2.6. Многочлены Кравчука как зональные сферические функции (69).

Г л а в а 4. Оценка линейного программирования . . . . . . . . . . . . . .
72
§ 4.1. Положительно определенные функции. .. . . . . . . . . . . . . . . . .
72
§ 4.2. Оценка линейного программирования . .. . . . . . . . . . . . . . . . .
75
4.2.1. Оценка Дельсарта (75). 4.2.2. Выбор многочлена в оценке
(4.2.6) (77).

Г л а в а 5. Коды Рида–Соломона и БЧХ-коды . . . . . . . . . . . . . . . .
83
§ 5.1. Коды Рида–Соломона . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
5.1.1. Определение кода Рида–Соломона (83). 5.1.2. Элементарные свойства кодов Рида–Соломона (85).
§ 5.2. Циклические коды . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
5.2.1. Циклические коды RSq(n, d) типа 1 (89). 5.2.2. Представление вектора циклического кода в виде рекуррентной последовательности (90).
5.2.3. Представление векторов циклического
кода в виде значений функции «след» (92).
5.2.4. Представление элементов циклического кода в виде элементов группового
кольца циклической группы над конечным полем (94).
§ 5.3. Коды Боуза–Чоудхури–Хоквингема (БЧХ-коды) . .. . . . . . . . . .
101
5.3.1. Группа автоморфизмов БЧХ-кода (101). 5.3.2. Параметры
БЧХ-кода (102).
5.3.3. Циклические коды Боуза–Чоудхури–
Хоквингема (105).
5.3.4. Точное значение размерности БЧХкода при не слишком больших значениях d (106).
§ 5.4. Обобщенные коды Рида–Соломона RSq(n, d) . . . . . . . . . . . . .
108
5.4.1. Обобщенные БЧХ-коды (108). 5.4.2. Циклический обобщенный БЧХ-код длины n = q + 1 (109).
5.4.3. Коды Гоппы (110).
§ 5.5. Автоморфизмы кода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
113
5.5.1. Группа
автоморфизмов
кода
(114).
5.5.2. Подгруппы
группы
автоморфизмов
кодов
Рида–Сололомона
RSq(n, d), n = q − 1, q (116).
§ 5.6. Группа обобщенных автоморфизмов кода . .. . . . . . . . . . . . . . .
117
5.6.1. Группа дробно-линейных преобразований (118).
§ 5.7. Число обобщенных кодов Рида–Соломона . .. . . . . . . . . . . . . .
120
5.7.1. Число
проверочных
матриц
кода
RSq(n, d)
(120).
5.7.2. Число обобщенных кодов Рида–Соломона (120).

Г л а в а 6. Декодирование кодов Рида–Соломона . . . . . . . . . . . . . .
123
§ 6.1. Что такое алгоритм декодирования? . .. . . . . . . . . . . . . . . . . .
123

Оглавление
5

6.1.1. Вводные понятия (126).
§ 6.2. Синдромный метод декодирования RM-кодов . .. . . . . . . . . . . .
128
6.2.1. Предварительные замечания (128).
6.2.2. Вспомогательные утверждения (129).
6.2.3. Многочлен локаторов ошибок (131).
6.2.4. Алгоритм Берлекэмпа (132).
6.2.5. Формула
Кристофеля–Дарбу (137).
6.2.6. Как вычислить число u
ошибок, поразивших кодовый вектор? (139). 6.2.7. Один несиндромный алгоритм декодирования кода Рида–Соломона (140).
6.2.8. Краткий обзор некоторых результатов по декодированию
кодов Рида–Соломона (141).

Г л а в а 7. Коды Рида–Маллера . . . . . . . . . . . . . . . . . . . . . . . . . .
147
§ 7.1. Булевы функции и многочлены Жегалкина . .. . . . . . . . . . . . .
147
7.1.1. Элементарные свойства кода Рида–Маллера (150).
§ 7.2. Декодирование кода Рида–Маллера . .. . . . . . . . . . . . . . . . . .
153
7.2.1. Алгоритм декодирования RM-кода первого порядка по
максимуму правдоподобия и «быстрое» умножение вектора на
матрицу Адамара (155).
7.2.2. Полиномиальный алгоритм декодирования RM-кода порядка r > 1 (157).
7.2.3. Основная
идея полиномиального
декодирования
RM-кода r-го
порядка (159).
7.2.4. Декодирование кода RM1,m первого порядка (161).
7.2.5. Декодирование кода RM2,m (162).
7.2.6. Эффективность алгоритма декодирования в случае r = 2 (165).
7.2.7. Оценка вероятности ошибки декодирования кода по критерию максимального правдоподобия (167).
§ 7.3. Другие способы представления векторов RM-кода. .. . . . . . . . .
171

Г л а в а 8. Некоторые частные классы кодов . . . . . . . . . . . . . . . . .
174
§ 8.1. Вспомогательные результаты. Вычисление некоторых тригонометрических сумм . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
174
§ 8.2. Код Кердока . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
179
§ 8.3. Код Препарата. .. . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
183
§ 8.4. Циклический линейный код, порождаемый булевыми функциями
ранга 2. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
187
§ 8.5. Авто- и взаимная корреляции последовательностей . .. . . . . . . .
188
§ 8.6. Коды с кодовым расстоянием 5 или 6 . .. . . . . . . . . . . . . . . . .
197
8.6.1. БЧХ-коды с кодовым расстоянием 5 (197).
8.6.2. Троичный БЧХ-код, исправляющий две ошибки (198).
8.6.3. Троичный код работы, исправляющий две ошибки (199). 8.6.4. Коды
Геворкяна (201).

Г л а в а 9. Весовой спектр линейного кода. . . . .. . . . . . . . . . . . . . .
205
§ 9.1. Соотношение МакВильямс . .. . . . . . . . . . . . . . . . . . . . . . . .
205
§ 9.2. Спектр линейного кода и многочлены Кравчука . .. . . . . . . . . .
208
9.2.1. Соотношение МакВильямс для весовой функции линейного кода (208).
9.2.2. Соотношение МакВильямс для полной

Оглавление

весовой функции линейного кода (209).
9.2.3. Использование
соотношения МакВильямс для вычисления спектра кода (211).
9.2.4. Функция типа χ2 для элементов спектра кода K (215).
9.2.5. Выражение функции Ξ(K) через спектр двойственного
кода (215). 9.2.6. Среднее функции Ξ(K) (218). 9.2.7. Пример
вычисления спектра кода K с помощью функции Ξ(K) (218).
§ 9.3. Спектр БЧХ-кодов . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
220

Г л а в а 10. Схемы отношений. . . . . . . . . . . . . . . . . . . . . . . . . . . .
225
§ 10.1. Введение . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
225
10.1.1. Некоторые общие свойства схемы отношений (227).
§ 10.2. Построение схем отношений . .. . . .. . . . . . . . . . . . . . . . . . . .
228
10.2.1. Схемы отношений SH(G) (229). 10.2.2. Примеры (231).
§ 10.3. Схемы отношений на Gn. . . . . . . . . . . . . . . . . . . . . . . . . . .
232
§ 10.4. Алгебра Боуза–Меснера ассоциативной схемы . .. . . . . . . . . . .
235
10.4.1. Некоторые сведения из теории представления конечных
групп (235).
10.4.2. Базисы алгебры Боуза–Меснера (237).
10.4.3. Вычисление коэффициентов Pk(j) для ассоциативной
схемы SH(G), у которой H = Inn(G). Продолжение примера 10.2.2. (241). 10.4.4. G — группа (Fp, +). Продолжение примера 10.2.1 (243). 10.4.5. Схемы отношений Хемминга (245).
§ 10.5. Метрики на схеме отношений CH(G) . . . . . . . . . . . . . . . . . .
245
10.5.1. Скалярное произведение на группе (247).
10.5.2. Продолжение примера 10.2.1. (247).
10.5.3. Продолжение примера
10.2.2 (248). 10.5.4. Метрики на группе G (249). 10.5.5. Метрика на группе Gn (251). 10.5.6. Краткий обзор результатов по
схемам отношений (252).

Г л а в а 11. Квантовые коды . . . . . . . . . . . . . . . . . . . . . . . . . . . .
255
§ 11.1. Основные понятия . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
255
11.1.1. Определения (256). 11.1.2. О некоторых конечных группах порядка 8 (258). 11.1.3. Операторы (259).
§ 11.2. Некоторые конструкции квантовых кодов. .. . . . . . . . . . . . . . .
261
11.2.1. Квантовые коды, образованные собственными векторами
коммутативной подгруппы HL группы E⊗n (261). 11.2.2. Квантовый «код Хэмминга» длины n = 2m (264). 11.2.3. Квантовый
код с кодовым расстоянием 5 (266).

Г л а в а 12. Открытые системы шифрования на основе кодов, корректирующих ошибки, и как некоторые из них можно расколоть . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
269
§ 12.1. Введение . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
269
§ 12.2. Роль декодирования в кодовых системах открытого шифрования
270
§ 12.3. Системы открытого шифрования на основе кода, корректирующего ошибки. .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .
272

Оглавление
7

12.3.1. Система
открытого
шифрования
МакЭлиса
(272).
12.3.2. Система открытого шифрования Нидеррайтера (274).
12.3.3. Сравнение систем открытого шифрования МакЭлиса
и Нидеррайтера (276).
12.3.4. Некоторые свойства систем
открытого шифрования МакЭлиса и Нидеррайтера (276).
§ 12.4. Как раскалывается система открытого шифрования Нидеррайтера, построенная с помощью обобщенного кода Рида–Соломона?
Общие подходы . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
277
§ 12.5. Алгоритм определения секретного ключа системы открытого
шифрования, использующего обобщенный код Рида–Соломона
279
12.5.1. Как
определить
первые
три
элемента
ωj ?
(279).
12.5.2. Определение элементов ωj, j > 3 (280). 12.5.3. Определение элементов zj и матрицы h (282). 12.5.4. Заключительные
замечания (284).

Г л а в а 13. Совершенная секретность в полилинейных системах
распределения ключей . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
286
§ 13.1. Модель системы распределения ключей . .. . . . . . . . . . . . . . .
286
13.1.1. Введение (286).
13.1.2. Вводные
замечания (287).
13.1.3.
Математическая
модель
системы
распределения
ключей (288).
§ 13.2. Определение полилинейной (t, w)-системы распределения ключей S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
289
13.2.1. Свойства ключевой системы (291).
§ 13.3. Конструкция полилинейной (t, w)-системы распределения ключей . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
292
§ 13.4. Основной результат . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
294
13.4.1. Возможные конструкции множеств Q (297).
§ 13.5. Системы распределения ключей Блундо и другие . .. . . . . . . . .
298
§ 13.6. Нижние оценки числа ключей у пользователей (w, t)-системы
распределения ключей . .. . . . . . . . . . . . . . . . . . . . . . . . . . .
299

Г л а в а 14. Дизъюнктные и разделяющие коды . . . . . . . . . . . . . . .
302
§ 14.1. Дизъюнктные коды (superimposed codes) . .. . . . . . . . . . . . . . .
302
14.1.1. Разделяющие коды (304). 14.1.2. Построение разделяющих (w, 1)-кодов (307).
§ 14.2. Каскадная конструкция дизъюнктных кодов . .. . . . . . . . . . . . .
308
§ 14.3. Максимальные дизъюнктные l-коды . .. . . . . . . . . . . . . . . . . .
311
14.3.1. Максимальный дизъюнктный l-код Qq,l
с q элементами (311).
§ 14.4. Криптографические приложения дизъюнктных кодов . .. . . . . . .
316

Введение

В настоящей книге изучаются методы построения и свойства кодов,
корректирующих ошибки. Она будет интересна математикам и специалистам по информационным технологиям, имеющим некоторую математическую подготовку, которые хотят достаточно глубоко изучить
отдельные разделы теории кодирования и некоторые ее приложения.
Вместе с тем начальные главы книги дают в достаточно элементарной форме полное представление об основных понятиях и главных
результатах в теории кодов, корректирующих ошибки. Эти главы могут
быть положены в основу университетского курса лекций по теории
кодирования.
В первой части книги дано подробное изложение нескольких традиционных и давно сложившихся направлений классической теории
кодирования. К ним относятся линейные и циклические коды, оценки объема кода, декодирование некоторых кодов, описание интересных в том или ином смысле классов кодов и многое другое. Хотя
этим направлениям уже посвящено несколько очень хороших учебников и монографий, в настоящей книге найдется достаточно много
новых и интересных результатов, не вошедших в эти издания. Во
многих случаях изложение даже хорошо известных результатов дается с новой точки зрения, которая, как полагает автор, расширит
кругозор читателя.
Вторая, б´ольшая часть книги включает в себя изложение результатов, которые почти никогда не затрагивались в учебной и монографической литературе по теории кодирования. К таким направлениям
автор относит декодирование кодов Рида–Маллера и отчасти кодов
Рида–Соломона, весовой спектр линейного кода, квантовые и дизъюнктные коды, приложения теории кодирования к криптографии, такие
как совершенная секретность в полилинейных системах распределения
ключей и стойкость некоторых известных кодовых систем открытого
шифрования.
Как первая, так и вторая части включают в себя достаточно большое число оригинальных результатов автора.
Изложение, особенно в первой части книги, является вполне доступным для студентов начальных курсов математического факультета

Введение
9

университета, на это автор обращал особое внимание. Читателю для
понимания текста необходимо знать некоторые элементарные и общеизвестные результаты алгебры (линейная алгебра, конечные поля,
группы, кольца, многочлены и т.п.), геометрии (метрика, евклидова
сфера и т.п.), а также и начальные знания по некоторым другим
разделам математики в объеме примерно двух первых курсов математического факультета. Понятия более специального плана всегда имеют
подробное определение и объяснение. Вместе с тем текст не всегда
является очень легким для понимания. Это прежде всего относится
к главам второй части книги.
Автор в течение нескольких лет читал лекции по отдельным разделам теории кодирования студентам и аспирантам Московского государственного университета им. М. В. Ломоносова.
Традиционно к теории кодирования относят весьма широкий круг
исследований, тяготеющих к дискретной математике. Из этого широкого круга только весьма малая часть отражена в данной книге. В частности, не рассматриваются неравномерные, алгебро-геометрические,
сверточные и некоторые другие коды. По всем упомянутым кодам изданы прекрасные монографии (см., например, [24], [17]). Естественно,
автор во второй половине книги писал только о тех направлениях теории кодирования, которые представляют для него наибольший научный
интерес.
Книга имеет не очень большое пересечение с известными автору
книгами по теории кодирования. Даже прекрасная книга МакВильямс
и Слоэн «Теория кодов, исправляющих ошибки» [68], с достаточно
большим охватом материала, не сильно перекрывается с содержанием
данной книги.
Следует особо сказать, что теория кодирования имеет множество
приложений, причем не только к технике передачи информации по
каналам связи с шумами. Имеются самые неожиданные приложения,
например, с помощью теории кодов можно построить так называемую
полилинейную систему распределения ключей, свойства которой, с одной стороны, похожи на свойства системы Диффи–Хеллмана, а с другой, обеспечивают совершенную секретность ключа, что не присуще
системе Диффи–Хеллмана. Об этом подробно написано в главе 13.
По представлениям автора, теория кодирования является одним из
немногих инкубаторов, в которых возникают новые содержательные
математические задачи в нескольких достаточно абстрактных направлениях математики: алгебре, теории чисел и геометрии. К примеру,
направление исследований, связанное с алгебро-геометрическими кодами, которые были открыты в конце 70-х годов прошлого столетия
отечественным ученым В.Д. Гоппой (см. например, [55]), к настоящему
времени превратилось в крупное направление математики, развивающееся на стыке алгебраической геометрии и теории кодирования [50].

Введение

Во многих местах книги после формулировки достаточно простых
утверждений фигурирует вставка «(упражнение)», которая означает,
что это утверждение читатель может доказать самостоятельно.
Как полагает автор, это позволяет, во-первых, сократить объем
текста и, во-вторых, упростить его восприятие квалифицированным
читателем. Следует также сказать, что некоторые из этих упражнений
автор предлагал студентам в качестве темы для курсовой работы.

Г л а в а 1

БАЗОВЫЕ ПОНЯТИЯ

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

§ 1.1. Пространство Хемминга

1.1.1. Метрика Хемминга.
Мы рассматриваем конечное q-элементное множество X = {a0, ... , aq−1}. Множество Xn состоит из всех
n-ок (n-мерных векторов) с координатами из множества X. Очевидно,
|Xn| = qn. Элементы Xn будем обозначать полужирными начальными
буквами латинского алфавита: a = (a0, ... , an), b = (b0, ... , bn) и т.д.
На множестве Xn мы определим метрику Хемминга d(·, ·) следующим образом:

d(a, b) = числу чисел j, для которых aj ̸= bj.
(1.1.1)

Как легко убедиться, функция d(·, ·) действительно является метрикой в обычном понимании этого термина. В частности, для нее
выполнено «неравенство треугольника»: d(a, b) ⩽ d(a, c) + d(c, b) для
всех c ∈ Xn (упражнение).
Пространство Xn вместе с метрикой d будем называть метрическим
пространством Хемминга. Оно является одним из стандартных пространств, на котором рассматривается теория кодов, корректирующих
ошибки.

Кодовое расстояние. Кодом K называется произвольное подмножество элементов метрического пространства Xn.
Определение 1.1.1. Кодовым расстоянием d = d(K) кода K называется минимальное расстояние между двумя различными элементами (векторами) кода K :

d(K) = min
a,b∈K
a̸=b
d(a, b).
(1.1.2)

Гл. 1. Базовые понятия

1.1.2. Линейный код.
Обычно в качестве X рассматривается
множество с какой-либо алгебраической структурой. В частности, в качестве X берется конечное поле или конечное кольцо. Эта структура
необходима для построения содержательной теории кодирования на
пространстве Xn.
Мы начнем изучение, предположив, что X — конечное поле Fq, q =
= p l, где p — простое число. В этом случае Xn можно рассматривать
как n-мерное пространство над полем Fq. Его мы будем обозначать
через Fn
q .
Интересным является случай q = 2. В этом случае пространство
Xn называется двоичным линейным пространством Хемминга.
В то же время естественно рассматривать и более общий случай:
X — это конечная группа или конечное кольцо. В частности, наиболее
широко рассматривался случай, в котором X — кольцо вычетов по
модулю 4 или, в несколько более общем случае, X — кольцо Галуа.
Заметим, что почти все рассматриваемые далее определения (линейный
и двойственный коды, вес и многие другие) достаточно очевидным
образом
могут
быть
введены
и
в
подобных
пространствах
Xn.

Определение 1.1.2.
Произвольное подпространство пространства Fn
q называется линейным кодом. Для него мы оставляем прежнее
обозначение K.
Через k = dim K мы обозначаем размерность линейного кода K.
Пусть ω = {ω1, ... , ωk} — базис пространства K. В теории кодирования
принято называть матрицу A = A(K), строками которой являются векторы {ω1, ... , ωk}, порождающей матрицей кода K.
Любой вектор x кода K может быть представлен в виде

x = zA,
(1.1.3)

где z — k-мерный вектор пространства Fk
q.
Если матрица A выписана в явном виде, то мы говорим, что код K
задан порождающей матрицей A.
Как достаточно легко установить (упражнение), линейный код имеет
(qk − 1)(qk − q) ... (qk − qk−1)
(1.1.4)

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

(qn − 1)(qn − q) ... (qn − qk−1)
(qk − 1)(qk − q) ... (qk − qk−1) .
(1.1.5)

Определение 1.1.3. Функция wt(a), равная числу отличных от нуля координат вектора a, называется весом Хемминга или просто
весом вектора a.

1.1. Пространство Хемминга
13

Функция wt(a) является часто используемой в теории кодирования
функцией. Например, с ее помощью упрощается вычисление кодового
расстояния для линейных кодов K ⊂ Fn
q .
Лемма 1.1.1. Кодовое расстояние линейного кода K ⊂ Fn
q
равно
минимальному весу ненулевого вектора в линейном подпространстве K. Другими словами,

d(K) =
min
a∈K, a̸=0 wt(a).
(1.1.6)

Доказательство непосредственно вытекает из очевидного равенства d(a, b) = wt(c), где c = a − b ∈ K.
□
Заметим, что для вычисления кодового расстояния кода общего
вида необходимо вычислить совокупность взаимных расстояний между всеми парами векторов a, b, т. е. необходимо вычислить значения
функции двух аргументов. Лемма 1.1.1 позволяет свести вычисление
кодового расстояния линейного кода к вычислению совокупности весов
ненулевых элементов линейного подпространства K, т. е. к вычислению
минимального значения функции одного аргумента.

1.1.3. Двойственный код.
В этом параграфе мы изучаем линейные коды K ⊆ Fn
q над конечным полем Fq, q = p l. Скалярное произведение ⟨x, y⟩ в поле Fq векторов x = (x1, ... , xn) и y = (y1, ... , yn)
линейного пространства Fn
q мы определим следующим образом:

⟨x, y⟩ = x1y1 + ... + xnyn (все операции в поле Fq).
(1.1.7)

Два вектора x, y называются ортогональными, если ⟨x, y⟩ = 0.
Определение 1.1.4 (двойственный код). Код K⊥, образованный
всеми векторами, которые являются ортогональными ко всем векторам
кода K, называется двойственным к коду K.
Очевидно, что K⊥ ⊥ = K.
Лемма 1.1.2. Код K⊥ является линейным кодом над полем Fq и имеет размерность n − k, где k = dim K.
Доказательство. Очевидно, что если векторы x, y ортогональны
вектору a, то их сумма с коэффициентами из Fq также ортогональна a.
Отсюда, в частности, следует, что код K⊥ состоит из всех векторов x,
которые ортогональны каждой строке порождающей матрицы A кода K.
Другими словами, векторы x ∈ K⊥ являются решениями линейной
системы однородных уравнений:

xAT = 0,
(1.1.8)

где AT — транспонированная матрица A.
Как хорошо известно [59], множество решений однородной системы линейных уравнений с n неизвестными (координаты вектора x)
и k уравнениями (1.1.8) представляет собой линейное пространство
размерности n − k′, если k′ — ранг матрицы A. Ранг (k × n)-матрицы A

Гл. 1. Базовые понятия

равен k, ибо ее строками, по определению, являются базисные векторы
пространства K.
□
Определение 1.1.5 (проверочной матрицы кода K). Порождающая
[(n − k) × n]-матрица B кода K⊥ называется проверочной матрицей
кода K .
Подобное название объясняется тем, что для каждого вектора x
кода K выполнено
xBT = 0.
(1.1.9)

В частности, произведение A · BT является нулевой (k × k)-матрицей.
Соотношение (1.1.9) в теории кодирования принято рассматривать
как набор из n − k линейных проверок, наложенных на координаты
вектора x. Каждая проверка, определяемая одной из строк матрицы B,
представляет собой однородное линейное уравнение, связывающее координаты вектора x.
Множество решений уравнения (1.1.9) совпадает с кодом K. Имея
в виду этот факт, говорят, что код K определяется проверочной матрицей B.
Теорема 1.1.1. Предположим, что любые d − 1 столбцов проверочной матрицы B линейно независимы над полем Fq.
Тогда кодовое расстояние d(K) кода K, определяемого проверочной матрицей B, не меньше чем d.
Если в дополнение вышеуказанному условию существует линейно зависимый комплект из d столбцов проверочной матрицы B, то
d(K) = d.
Наоборот. Если код имеет кодовое расстояние не меньше чем d,
то любые d − 1 столбцов его проверочной матрицы B являются
линейно независимыми.
Доказательство. Ввиду леммы 1.1.1 достаточно показать, что вес
любого ненулевого вектора x кода K не меньше d.
Предположим обратное, т. е. предположим, что существует кодовый
вектор x, вес которого меньше d. Так как xBT = 0, то комплект
столбцов матрицы B, номера которых совпадают с номерами ненулевых
координат вектора x, является линейно зависимым. Это противоречит
условию теоремы. Поэтому d(K) ⩾ d.
Предпоследнее и последнее утверждения теоремы очевидны.
□
Эта простая теорема очень широко используется. Обычно по умолчанию ввиду теоремы 1.1.1 предполагается, что для построения линейного кода с кодовым расстоянием d достаточно построить матрицу,
у которой каждый комплект из d − 1 столбцов является линейно независимым.
В качестве примера применения теоремы 1.1.1 рассмотрим двоичный линейный код Хемминга. Проверочная матрица BH этого кода
имеет размеры m × (2m − 1) (m строк и 2m − 1 столбцов) и образована
всеми ненулевыми столбцами aT , a ∈ Fm
2 , высоты m с координатами
из поля F2. Число таких столбцов, очевидно, равно 2m − 1.

1.2. Сфера в n-мерном евклидовом пространстве
15

Лемма 1.1.3. Кодовое расстояние двоичного линейного кода Хемминга BH длины 2m − 1 с числом элементов 2n−m = 2n−log2(n+1)
(см. лемму 1.1.2) равно 3.
Доказательство. Так как любые два столбца матрицы BH различны, то они линейно независимы над полем F2. Заметим, что это
утверждение неверно для полей с числом элементов более 2.
С другой стороны, сумма любых двух столбцов BH является одним
из столбцов BH. Следовательно, эти три столбца являются линейно
зависимыми.
Из теоремы 1.1.1 следует утверждение леммы.
□
Код Хемминга обладает рядом замечательных свойств, в частности,
он является совершенным. Это его свойство и
некоторые другие мы
будем рассматривать ниже.
Кроме кода Хемминга, обычно рассматривают так называемый расширенный код Хемминга длины 2m с проверкой на четность. Проверочная матрица этого кода образована проверочной матрицей кода
Хемминга, к которой добавлен нулевой столбец, а затем и строка,
состоящая из всех единиц. Этот код, как нетрудно проверить, имеет
кодовое расстояние 4, длину 2m и размерность (число информационных разрядов) 2m − m − 1 (упражнение).

1.1.4. Пространство, образованное равновесными двоичными
векторами.
Обычно пространство из заголовка называют пространством Джонсона и обозначают символом Jw,n, где w — вес каждого
вектора длины n этого пространства. Кодовое расстояние Хемминга
между векторами a и b из Jw,n всегда четное и, очевидно, равно

d(a, b) = 2w − 2u,
(1.1.10)

где u — число j, таких что aj = bj = 1. Функцию j(a, b) = 1

2d(a, b)
называют расстоянием Джонсона между векторами a, b ∈ Jw,n.
В пространстве Джонсона изучаются примерно те же задачи, что
и в пространстве Хемминга.

§ 1.2. Сфера в n-мерном евклидовом пространстве

Другим стандартным метрическим пространством, которое мы будем подробно изучать в настоящей книге, является (n − 1)-мерная
сфера Sn−1 в евклидовом пространстве Rn. Чтобы охарактеризовать
круг рассматриваемых далее задач, необходимо короткое введение.
К нему мы и переходим.

1.2.1. Метрика на сфере.
Рассмотрим n-мерное евклидово пространство Rn со скалярным произведением

(x, y) = x1y1 + ... + xnyn.
(1.2.1)