Введение
1 Коды, исправляющие одиночные ошибки 31
1.1 Метод однородных упаковок и покрытий 31
1.2 Упаковки и покрытия одиночными фазированными пакетами 38
1.3 Асимптотика лучших упаковок и покрытий единичными шарами 42
1.4 Коды, исправляющие одиночные локализованные ошибки 51
2 Списочное декодирование кодов Рида-Маллера 55
2.1 Списочное декодирование линейной сложности двоичных кодов Рида-Маллера первого порядка 57
2.2 Мягкое списочное декодирование кодов Рида-Маллера первого порядка 70
2.2.1 Граница Джонсона для сферических кодов 72
2.2.2 Алгоритм КС (критерия сумм) декодирования кодов RM(1, т) в евклидовом пространстве 75
2.3 Списочное декодирование почти линейной сложности для двоичных кодов Рида-Маллера фискированного порядка . 81
2.3.1 Верхняя граница на мощность списка при частично известном весовом спектре кода 81
2.3.2 Списочное декодирование кодов Рида-Маллера второго порядка 85
2.3.3 Алгоритм КО (критерия отношений) списочного декодирования кодов Рида-Маллера фиксированного порядка 92
2.3.4 Алгоритм "двух попыток" списочного декодирования кодов Рида-Маллера фиксированного порядка 97
2.4 Построение и свойства недвоичных кодов Рида-Маллера 101
3 Применения теории кодирования к задачам защиты информации 106
3.1 Коды, обнаруживающие целенаправленные ошибки, или коды для безусловной аутентификации 106
3.1.1 Определения и предшествующие результаты 108
3.1.2 Аутентификационные схемы и коды, исправляющие ошибки 111
3.1.3 Одна конструкция аутентификационных кодов 114
3.2 Коды для защиты авторских прав, I - коды, идентифицирующие родителей 118
3.2.1 Одноуровневые схемы поиска пиратов и коды, иден тифицирующие родителей 120
3.2.2 Недвоичные коды, идентифицирующие пары по минимуму расстояния 124
3.2.3 Асимптотически хорошие идентифицирующие коды 129
3.2.4 Асимптотически хорошие идентифицирующие коды с полиномиальной сложностью 136
3.3 Коды для защиты авторских прав, II - коды цифровых отпечатков пальцев, устойчивые к коалициям 139
3.3.1 Постановка задачи 140
3.3.2 Асимптотически хорошие и полиномиально реализуемые коды цифровых отпечатков пальцев, устойчивые к коалициям 145
3.3.3 Асимптотически хорошие и полиномиально реализуемые коды цифровых отпечатков пальцев, устойчивые к парам 152
3.4 Центрированные коды, исправляющие ошибки, и комбинаторная стеганография 156
3.4.1 Коды-покрытия и пассивная комбинаторная модель 157
3.4.2 Шаровые коды, исправляющие ошибки, и активная комбинаторная модель 160
3.4.3 Шаровые коды, исправляющие ошибки, и одна модель "цифровых отпечатков пальцев" 163
Заключение 165
Литература 167
