Предисловие | 9
|
Глава 1. Основы теории самокорректирующихся кодов | 11
|
1.1. Передача информации по каналу связи. Помехи, ошибки | 11
|
1.2. Расстояние Хэмминга | 12
|
1.3. Кодовое расстояние | 13
|
1.4. Обнаружение и корректирование ошибок | 13
|
1.5. Линейный код | 15
|
1.6. Порождающая матрица | 15
|
1.7. Кодирование и декодирование с помощью порождающей матрицы | 16
|
1.8. Двойственный код | 17
|
1.9. Проверочная матрица | 18
|
1.10. Синдром | 19
|
1.11. Кодовое расстояние линейного кода | 19
|
1.12. Связь кодового расстояния со свойствами столбцов проверочной матрицы | 20
|
1.13. Вектор ошибок. Исправление небольшого числа ошибок | 20
|
1.14. Линейные коды с кодовым расстоянием 1 и 2 | 21
|
1.15. Линейные коды с кодовым расстоянием 3 | 24
|
1.16. Двоичный код Хэмминга. Кодирование, исправление ошибок и декодирование с помощью двоичного кода Хэмминга | 25
|
Глава 2. Верхние оценки мощности кодов | 28
|
2.1. Проблема верхних оценок мощности кодов | 28
|
2.2. Рекуррентные оценки | 30
|
2.3. Оценка Хэмминга (граница сферической упаковки) | 32
|
2.4. Достижимость оценки Хэмминга на коде Хэмминга | 34
|
2.5. Совершенные коды | 34
|
2.6. Оценка Синглтона | 35
|
2.7. Оценка Джонсона | 36
|
2.8. Следствие из оценки Джонсона | 39
|
2.9. Связь между максимальными мощностями кода на всем множестве наборов и на его подмножестве | 40
|
2.10. Оценка Элайеса–Бассалыго | 41
|
2.11. Оценка Плоткина | 41
|
2.12. Следствия из оценки Плоткина | 42
|
2.13. Достижимость оценки Плоткина на коде, двойственном к коду Хэмминга | 43
|
Глава 3. Матрицы Адамара | 45
|
3.1. Делимость порядка матрицы Адамара на 4 | 46
|
3.2. Связь матриц Адамара и кодов с большими кодовыми расстояниями. Достижимость оценки Плоткина на кодах, построенных с помощью матрицы Адамара | 46
|
3.3. Эквивалентность матриц Адамара и кодов, на которых достигается равенство в следствии из оценки Плоткина | 48
|
3.4. Теорема Левенштейна | 49
|
3.5. Кронекерово произведение матриц | 51
|
3.6. Кронекерово произведение матриц Адамара есть матрица Адамара | 52
|
3.7. Матрица Адамара–Сильвестра | 52
|
3.8. Квадратичные вычеты | 53
|
3.9. Символы Лежандра | 54
|
3.10. Построение матриц Адамара с помощью символов Лежандра | 55
|
3.11. Построение матриц Адамара всех порядков до 100, делящихся на 4, кроме 92 | 57
|
3.12. Построение матриц Адамара методом Вильямсона | 59
|
Глава 4. Оценки разных параметров кодов | 62
|
4.1. Оценка Грайсмера | 62
|
4.2. Достижимость оценки Грайсмера на коде, двойственном к двоичному коду Хэмминга | 65
|
4.3. Коды Макдональда. Достижимость оценки Грайсмера на кодах Макдональда | 66
|
4.4. Максимальная размерность линейного кода. Рекуррентные оценки | 67
|
4.5. Точное значение максимальной размерности линейного двоичного кода в случае больших кодовых расстояний | 68
|
4.6. Оценка Варшамова–Гильберта | 70
|
4.7. Оценка Гильберта (сферическая нижняя оценка) | 71
|
4.8. Оценка Варшамова | 71
|
4.9. Двоичная энтропия | 73
|
4.10. Выражение биномиальных коэффициентов через энтропию | 74
|
4.11. Скорость кода | 75
|
4.12. Асимптотические оценки скорости кода через оценки Хэмминга, Элайеса–Бассалыго, Варшамова–Гильберта, их сравнение между собой | 76
|
Глава 5. Коды Голея | 80
|
5.1. Несуществование совершенных двоичных кодов с параметрами d = 7, n > 7, n 6= 23 | 80
|
5.2. Расширенный двоичный код Голея, его кодовое расстояние | 81
|
5.3. Двоичный код Голея как совершенный код | 84
|
5.4. Расширенный троичный код Голея, его кодовое расстояние | 84
|
5.5. Троичный код Голея как совершенный код | 87
|
Глава 6. Распределение весов кода | 88
|
6.1. Число наборов веса 7 и 8 в двоичном коде Голея | 88
|
6.2. Распределение весов кода | 90
|
6.3. Теорема Шапиро–Злотника | 90
|
6.4. Тождества Мак-Вильямс | 91
|
Глава 7. Код Рида–Маллера | 96
|
7.1. Булевы функции | 96
|
7.2. Полином Жегалкина | 97
|
7.3. Код Рида–Маллера, его кодовое расстояние | 99
|
7.4. Дуальный код к коду Рида–Маллера | 100
|
7.5. Связь кода Рида–Маллера первого порядка с матрицей Адамара–Сильвестра | 100
|
7.6. Мажоритарное декодирование кодов Рида–Маллера | 101
|
7.7. Радиус покрытия кода | 103
|
7.8. Радиус покрытия кода Рида–Маллера первого порядка. Его значение для криптографии | 105
|
7.9. Быстрое умножение строки на матрицу Адамара–Сильвестра | 112
|
Глава 8. Коды Рида–Соломона | 114
|
8.1. Матрица Вандермонда, ее невырожденность | 114
|
8.2. Коды Рида–Соломона трех типов, их параметры. Достижимость оценки Синглтона на кодах Рида–Соломона | 115
|
8.3. Коды, двойственные к кодам Рида–Соломона второго и третьего типа | 118
|
8.4. Циклические коды | 120
|
8.5. Представление наборов линейных циклических кодов в виде многочленов | 120
|
8.6. Линейный циклический код как идеал в кольце классов вычетов многочленов | 121
|
8.7. Порождающий многочлен | 121
|
8.8. Проверочный многочлен | 123
|
8.9. Многочлен ошибок. Синдромный многочлен. Кодирование, исправление ошибок и декодирование линейных циклических кодов на языке многочленов | 124
|
8.10. Код Рида–Соломона первого типа как циклический код | 127
|
8.11. Порождающий многочлен кода Рида–Соломона первого типа | 128
|
Глава 9. Коды БЧХ | 129
|
9.1. Подполе и расширение поля. Коды Боуза–Чоудхури–Хоквингема (БЧХ), их проверочная матрица, оценки кодового расстояния и размерности | 129
|
9.2. Коды Хэмминга и Рида–Соломона первого типа как частные случаи кода БЧХ | 135
|
9.3. Взаимосвязь множества наборов кода БЧХ над F q с множеством наборов соответствующего кода Рида–Соломона над F q m | 136
|
9.4. Код БЧХ как циклический код | 138
|
9.5. Примеры кодов БЧХ | 138
|
9.6. Минимальные многочлены и сопряженные корни, порождающий многочлен кода БЧХ | 141
|
9.7. Алгоритм декодирования Питерсона–Горенстейна–Цирлера для кодов БЧХ, его трудоемкость | 144
|
Глава 10. Алгоритм Берлекэмпа–Месси | 149
|
10.1. Проблема быстрого решения системы линейных уравнений специального вида при исправлении ошибок в коде БЧХ | 149
|
10.2. Сведение к задаче нахождения регистра сдвига с линейной обратной связью минимальной длины, генерирующего данную последовательность | 150
|
10.3. Леммы о длине минимального регистра сдвига | 152
|
10.4. Алгоритм Берлекэмпа–Месси, его трудоемкость | 158
|
10.5. Синдромный многочлен и многочлен значений ошибок для кода БЧХ | 160
|
10.6. Алгоритм Форни нахождения значений ошибок | 161
|
Глава 11. Открытые системы шифрования на основе кодов, корректирующих ошибки | 165
|
11.1. Система открытого шифрования Мак-Элиса | 166
|
11.2. Система открытого шифрования Нидеррайтера | 168
|
11.3. Сравнение систем открытого шифрования Мак-Элиса и Нидеррайтера | 170
|
Глава 12. Ортогональные массивы | 172
|
12.1. Ортогональные массивы. Их параметры | 172
|
12.2. Корреляционно-иммунные функции | 173
|
12.3. Связь силы ортогонального массива, построенного по линейному коду, с кодовым расстоянием дуального кода | 174
|
12.4. Существование ортогональных массивов из выполнения условия границы Варшамова–Гильберта | 176
|
12.5. Ортогональный массив, построенный с помощью кода Рида–Соломона | 176
|
12.6. Конструкция Буша | 177
|
12.7. Рекуррентные соотношения для максимального числа столбцов в ортогональных массивах | 178
|
12.8. Неравенства Буша | 179
|
12.9. Неравенство Рао | 183
|
12.10. Неравенство Бирбрауэра–Фридмана | 185
|
12.11. Теорема Халявина | 190
|
12.12. Коды аутентификации. Их построение с помощью ортогональных массивов | 194
|
Глава 13. Дизъюнктные коды | 197
|
13.1. Построение системы разделения ключей с помощью дизъюнктных кодов | 199
|
13.2. Разделяющие коды | 200
|
13.3. Каскадная конструкция дизъюнктных кодов | 201
|
Глава 14. Задачи | 204
|
14.1. Основы теории самокорректирующихся кодов | 204
|
14.2. Верхние оценки мощности кодов | 209
|
14.3. Матрицы Адамара | 212
|
14.4. Оценки разных параметров кодов | 212
|
14.5. Коды Голея | 215
|
14.6. Распределение весов кода | 216
|
14.7. Код Рида–Маллера | 218
|
14.8. Коды Рида–Соломона | 221
|
14.9. Коды БЧХ | 224
|
14.10. Алгоритм Берлекэмпа–Месси | 229
|
14.11. Открытые системы шифрования на основе кодов, корректирующих ошибки | 238
|
14.12. Ортогональные массивы | 243
|
14.13. Дизъюнктные коды | 245
|
Литература | 248
|
Книга написана на основе специальных курсов лекций «Теория кодирования и ее применения в криптографии» и «Теория кодирования и ее приложения к криптографии (дополнительные главы)», читавшихся автором более десяти лет на механико-математическом факультете МГУ, начиная с 2008 года. Ранее курсы под теми же названиями долгие годы читал профессор Владимир Михайлович Сидельников, сделавший в этих областях много крупных открытий, а незадолго до смерти осенью 2008 года Владимир Михайлович на время своей болезни попросил автора продолжить чтение курса.
Книга дает необходимые общие сведения из теории самокорректирующихся кодов, уделяя при этом особое внимание приложениям в криптографии и смежных областях. Большая глава посвящена матрицам Адамара, являющимся важным теоретическим аппаратом исследований как в теории кодирования, так и в многочисленных приложениях. Подробно обсуждаются коды Рида–Маллера, строящиеся с помощью булевых функций и имеющие связь с нелинейностью булевых функций, — важным свойством, требующимся от булевых функций при их использовании в качестве узла криптосистем. Дается необходимый аппарат работы с коэффициентами Уолша или, как их еще называют, спектральными коэффициентами.
Алгоритм Берлекэмпа–Месси является алгоритмом двойного назначения, он одновременно и эффективно решает задачу декодирования кодов БЧХ, и не менее эффективно позволяет восстановить регистр сдвига с линейной обратной связью наименьшей длины, генерирующий имеющийся в распоряжении кусок последовательности. Такие регистры используются при генерировании псевдослучайных последовательностей и являются важной составной частью многих криптосистем. Надо сказать, что в литературе алгоритм Берлекэмпа–Мэсси изложен в разных местах и по-разному, причем часто это изложение достаточно тяжело для восприятия. Автор взял за основу изложение алгоритма Берлекэмпа–Мэсси в книге Блэйхута [3], однако, к сожалению, в нем присутствовало большое число опечаток и логических ошибок, которые, как автор надеется, удалось методически грамотно откорректировать.
Обсуждаются основанные на самокорректирующихся кодах криптосистемы с открытым ключом, в том числе криптосистемы МакЭлиса и Нидеррайтера. Стойкость таких криптосистем основана на сложности решения задач декодирования кодов общего вида, поэтому знания и дальнейших теоретические исследования задач эффективного декодирования могут как влиять на стойкость криптосистем, так и давать дополнительный толчок к их совершенствованию. Большая глава посвящена ортогональным массивам, — объекту, который имеет множественное применение в математике и ее приложениях. Изначально ортогональные массивы возникли в статистике в задачах планирования экспериментов, быстро установили связи с теорией комбинаторных дизайнов, аппарат исследования ортогональных массивов оказался тесно увязан с теорией распределений весов кода и дуального кодового расстояния. Двоичные ортогональные массивы без повторяющихся строк оказались эквивалентны корреляционно-иммунным булевым функциям, противодействующим корреляционным и другим видам криптографических атак, а также использующимся в кодах аутентификации. Последняя глава теоретической части рассказывает о дизъюнктных кодах, применяемых в системах разделения доступа.
Завершает книгу большой набор задач, как правило, прошедших апробацию в ходе образовательного процесса. Студенты внесли огромный вклад как в совершенствование и корректирование задач, так и своими замечаниями по теоретическому материалу, за что автор им безмерно благодарен.
Автор благодарен за полезные обсуждения в различных областях теории кодирования и ее приложений коллегам с кафедры дискретной математики механико-математического факультета и других кафедр МГУ им. М. В. Ломоносова, из института математики им. С. Л. Соболева, института прикладной математики им. М. В. Келдыша, института проблем передачи информации им. А. А. Харкевича, МФТИ, МГТУ им. Н. Э. Баумана и других научных и образовательных учреждений.
Безусловно, огромное влияние на автора оказало общение с покойными Владимиром Михайловичем Сидельниковым и Владимиром Иосифовичем Левенштейном, особенно ярким является воспоминание о том, как мы втроем возвращались в 2003 году на электричке с конференции в Ратмино под Дубной.