Основы теории информации и криптографии
Вид материала | Учебное пособие |
СодержаниеПолиномиальные коды |
- «Основы криптографической защиты информации», 173.19kb.
- О спектральных свойствах дискретного преобразования фурье, 34.99kb.
- Задача надежной защиты информации от несанкционированного доступа является одной, 269.92kb.
- Методические указания по изучению теоретической части Чебоксары 2009, 330.7kb.
- Программа дисциплины теоретические основы информатики (дпп. Ф. 08) для специальности, 125.07kb.
- Рабочей программы учебной дисциплины (модуля) Основы математической обработки информации, 44.43kb.
- Темы курсовых работ по дисциплине «Криптографические методы защиты информации», 14.86kb.
- Примерная программа наименование дисциплины: «Теоретико-числовые методы в криптографии», 222.72kb.
- «Основы обработки графической информации с помощью пк. Графический редактор Paint», 95.66kb.
- Учебная программа по дисциплине криптографические методы защиты информации федосеев, 33.76kb.
Полиномиальные коды
При полиномиальном кодировании каждое сообщение отождествляется с многочленом, а само кодирование состоит в умножении на фиксированный многочлен. Полиномиальные коды - блочные и отличаются от рассмотренных ранее только алгоритмами кодирования и декодирования.
Пусть


Например, последовательности 10011 при


Зафиксируем некоторый многочлен степени


Полиномиальный код с кодирующим многочленом








Пример. Рассмотрим кодирующий многочлен




Полиномиальный код с кодирующим многочленом





Т е. ненулевые элементы в



Например,



или отображению:








Полиномиальные коды являются групповыми.
Это следует из того, что коды, получаемые матричным кодированием, - групповые.
Рассмотрим





Действительно,






Таким образом, обнаружение ошибки при использовании полиномиального кода с кодирующим многочленом

Коды Хэмминга можно строить как полиномиальные, например, кодирующий многочлен


Вообще же, если кодирующий многочлен




Пусть
















Кодирующий многочлен


В 1971 году финскими и советскими математиками было доказаноссылка скрыта, что кроме кодов Хэмминга и Голея других совершенных кодов нет.
Наиболее интересными среди полиномиальных кодов являются циклические коды, в которых вместе с любым кодовым словом вида


Упражнение 43 По кодирующему многочлену

Упражнение 44 Принадлежат ли коду Голея кодовые слова 10000101011111010011111 и 11000111011110010011111?
10. Лекция: Понятие о кодах Боуза-Чоудхури-Хоккенгема
Рассказывается методика построения кодов, минимальное расстояние между кодовыми словами которых равно заданному числу. Математическое обосновании кодов Боуза-Чоудхури-Хоккенгема, упражнения для самопроверки. Рассматриваются циклические избыточные коды(CRC) и их применение на практике
Остался открытым вопрос о методике построения кодов, минимальное расстояние между кодовыми словами которых равно заданному числу. В 1960 году независимо Боуз (Bose), Чоудхури (Chaudhuri) и Хоккенгем (Hocquengem) открыли способ построения полиномиальных кодов, удовлетворяющих таким требованиям. Эти коды получили названия кодов Боуза-Чоудхури-Хоккенгема или БЧХ-кодов (BCH codes). БЧХ-коды могут быть не только двоичными, например, на практике достаточно широко используются недвоичные коды Рида-Соломона (Reed, Solomon), но далее будут рассматриваться только двоичные.
Многочлен






Например, многочлен








Кодирующий многочлен









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

Пример. Нужно построить БЧХ-код с длиной кодовых слов











Степень полученного многочлена равна 8, следовательно, построенный БЧХ-код будет



Можно построитьссылка скрыта двоичный БЧХ-код с кодовыми словами длины



Первый БЧХ-код, примененный на практике, был


БЧХ-коды умеренной длины не слишком далеки от совершенных или квазисовершенных кодов. Коды Хэмминга, например, являются БЧХ-кодами, а БЧХ-коды с минимальным весом кодового слова 5 - квазисовершенны. Но с ростом длины кодовых слов качество БЧХ-кодов падает. Код Голея, например, - это не код БЧХ.
Упражнение 45 Найти кодирующий многочлен БЧХ-кода






