Блоковые коды, исправляющие ошибки, и их применения к задачам защиты информации

• Автор: Кабатянский, Григорий Анатольевич
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 186 с.

Оглавление
Введение

1 Коды, исправляющие одиночные ошибки

1.1 Метод однородных упаковок и покрытий

1.2 Упаковки и покрытия одиночными фазированными пакетами

1.3 Асимптотика лучших упаковок и покрытий единичными шарами

1.4 Коды, исправляющие одиночные локализованные ошибки

2 Списочное декодирование кодов РидаМаллера

2.1 Списочное декодирование линейной сложности двоичных кодов РидаМаллера первого порядка .

2.2 Мягкое списочное декодирование кодов РидаМаллера первого порядка

2.2.1 Граница Джонсона для сферических кодов

2.2.2 Алгоритм КС критерия сумм декодирования кодов ПМ1,т в евклидовом пространстве
2.3 Списочное декодирование почти линейной сложности для двоичных кодов РидаМаллера фискированного порядка .
2.3.1 Верхняя граница на мощность списка при частично известном весовом спектре кода
2.3.2 Списочное декодирование кодов РидаМаллера второго порядка.
2.3.3 Алгоритм КО критерия отношений списочного декодирования кодов РидаМаллера фиксированного порядка
2.3.4 Алгоритм двух попыток списочного декодирования кодов РидаМаллера фиксированного порядка
2.4 Построение и свойства недвоичных кодов РидаМаллера
3 Применения теории кодирования к задачам защиты информации
3.1 Коды, обнаруживающие целенаправленные ошибки, или
коды для безусловной аутентификации.
3.1.1 Определения и предшествующие результаты
3.1.2 Аутентификационные схемы и коды, исправляющие ошибки.
3.1.3 Одна конструкция аутентификационных кодов . .
3.2 Коды для защиты авторских прав, 1 коды, идентифицирующие родителей
3.2.1 Одноуровневые схемы поиска пиратов и коды, идентифицирующие родителей
3.2.2 Недвоичные коды, идентифицирующие пары по минимуму расстояния
3.2.3 Асимптотически хорошие идентифицирующие коды
3.2.4 Асимптотически хорошие идентифицирующие коды с полиномиальной сложностью
3.3 Коды для защиты авторских прав, II коды цифровых
отпечатков пальцев, устойчивые к коалициям
3.3.1 Постановка задачи.
3.3.2 Асимптотически хорошие и полиномиально реализуемые коды цифровых отпечатков пальцев, устойчивые к коалициям .
3.3.3 Асимптотически хорошие и полиномиально реализуемые коды цифровых отпечатков пальцев, устойчивые к парам
3.4 Центрированные коды, исправляющие ошибки, и комбинаторная стеганография
3.4.1 Кодыпокрытия и пассивная комбинаторная модель
3.4.2 Шаровые коды, исправляющие ошибки, и активная комбинаторная модель.
3.4.3 Шаровые коды, исправляющие ошибки, и одна модель цифровых отпечатков пальцев
Заключение
Литература


Еще больше различие в асимптотическом поведении наилучших упаковок и покрытий при линейном от п радиусе t = тп шара, где т -константа, 0 < г < 1. Хорошо известно (см. Так как объем шара радиуса I = тп при т > 1 — q~l равен qn . Отметим, что почти все линейные коды асимптотически лежат на границе В-Г [], [], []. Более того, для большинства “массивных” классов кодов (например, АГ-коды, каскадные коды, укороченные циклические коды, квазициклические коды и многие другие) справедливо, что почти все коды в классе лежат на границе ВГ или выше. Тем не менее, для циклических кодов, пожалуй, самого исследованного класса кодов, неизвестна справедливость даже более слабого утверждения -существование циклических кодов, для которых при фиксированной скорости передачи относительное расстояние отделено от нуля (линейный код называется циклическим, если для любого кодового слова его циклический сдвиг также является кодовым словом). Среди немногих результатов вокруг этой проблемы отмечу собственный результат [5], что если рассматривать коды над непростым полем (q = рт} т > 1) и ослабить требования линейности кода до требования быть аддитивной подгруппой всего пространства, то такие “хорошие” коды существуют. В теории кодирования верхним границам на максимальную мощность и скорость кода с заданным расстоянием уделялось особое внимание, в частности, как средству доказательства оптимальности кодов. Синглетона (см. Рида-Соломона [], являющихся важнейшим и простейшим частным случаем АГ-кодов. Из этой границы и границы В-Г следует, что асимптотически скорость наилучших кодов отделена от нуля в интервале 0 < 6 = d/n < 1 - q~ и только в нем. Как ведет себя скорость оптимальных кодов, когда относительное расстояние o кода меняется в диапазоне (0,1 - q~l), является главной загадкой теории кодирования! Отметим, что если справедлива известная гипотеза о существовании п х п-матриц Адамара для всех п = 0 mod 4, то в двоичном случае граница Плоткина всегда достигается при d > п/2 - это замечательный результат В. И. Левенштейна [], закрывающий проблему вычисления A2(n,d) при этих значениях п и d. Вернемся к рассмотрению асимптотических верхних границ. Л,(п. Я^п. А,? Граница Элайеса-Бассалыго, см. Хэмминга, и Плоткина, в их асимптотической форме. Следующее улучшение асимптотических верхних границ потребовало принципиально новых комбинаторных понятий, разработанных Дельсартом [] под названием ассоциативные схемы отношений, и новой техники с использованием свойств дискретных ортогональных многочленов []. Б-Г. Особо выделим то, что двоичный случай во многом отличается от общего, недвоичного. А именно, заменим на 0 и 1 на ±1 по правилу х —> х = (—1)х. При такой замене (отображении) код С длины п становится сферическим кодом Ск с Мп, лежащим на евклидовой сфере 8'1_1(/п) радиуса у/п, а расстояние Хэмминга <^(х. Г7 - Я2(х? Из этого соотношения и известной для сферических кодов границы Ранкина [] следует граница Плоткина (), а «из хороших двоичных кодов можно строить хорошие решетки (конструкция Лича-Слоэна, [], []), в частности, из кода Голея - знаменитую решетку Лича. Эта связь между двоичными кодами и расположениями точек в евклидовом пространстве была предметом многочисленных исследований. Отметим работу [], в которой несуществование некоторых расположений линий в евклидовом пространстве доказывалось алгебраическими методами, независимо открытыми в комбинаторике, см. Далее связь между пространствами Евклида и Хэмминга была углублена в работе В. И.Левенштейна и автора [6], в которой была построена теория “непрерывных ассоциативных схем отношений" - аналог теории Дельсарта [] для компактных римановых многообразий ранга 1, и, в частности, для сферы в евклидовом пространстве. Блихфельда рп < З“*1/2*^1))".