Код Боуза — Чоудхури — Хоквингема

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:48, 14 мая 2016.

БЧХ-код

TemplateDifinitionIcon.svg Определение «Определение - Коды Боуза — Чоудхури — Хоквингхема (БЧХ-коды)»
БЧХ-код — в теории кодирования это широкий класс циклических кодов, применяемых для защиты информации от ошибок. Отличается возможностью построения кода с заранее определёнными корректирующими свойствами, а именно, минимальным кодовым расстоянием.

Главной задачей является построение кода с заданным кодовым расстоянием (заданными корректирующими свойствами). Построим циклический линейный код над конечным полем , который задается следующими параметрами: - длина кода, - конструктивное расстояние, - целое число. Корректирующее свойство кода зависит только от и . Циклический линейный код задается полиномом. Также можно задать код при помощи некоторых выделенных корней этого полинома. Пусть существует - элементы некоторого расширения . Рассмотрим любое . Следовательно для существует минимальный многочлен , - неприводим, .
Все многочлены определены над . Для них можно построить .
Корнями являются все . Возьмем как порождающий многочлен для циклического кода.

TemplateDifinitionIcon.svg Определение «Определение - Циклический код, заданный корнями»
Циклический код, порождаемый , называется циклическим кодом, заданным корнями , если только они и все сопряженные с ними являются конями .

Если - порождающий многочлен циклического кода , то код .

TemplateTheoremIcon.svg Теорема Утверждение
Доказательство


Для нахождения порождающего многочлена необходимо выполнить несколько этапов:

  1. выбрать , то есть поле , над которым будет построен код;
  2. выбрать длину кода из условия , где  — целые положительные числа;
  3. задать величину конструктивного расстояния;
  4. построить циклотомические классы элемента поля над полем , где  — примитивный элемент ;
  5. поскольку каждому такому циклотомическому классу соответствует неприводимый полином над , корнями которого являются элементы этого и только этого класса, со степенью равной количеству элементов в классе, то выбрать таким образом, чтобы суммарная длина циклотомических классов была минимальна
  6. вычислить порождающий полином , где  — полином, соответствующий -ому циклотомическому классу.
TemplateExampleIcon.svg Пример Пример: Примитивный 2-ичный (15,7,5) код.

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

имеет в качестве корней элементы и является порождающим полиномом БЧХ-кода с параметрами .


TemplateExampleIcon.svg Пример Пример: 16-ричный (15,11,5) код (код Рида — Соломона).

Пусть и  — примитивный элемент . Тогда

.

Каждому элементу поля можно сопоставить 4 битам, поэтому одно кодовое слово эквивалентно битам, таким образом набору из 44 бит ставится в соответствие набор из 60 бит. Можно сказать, что такой код работает с полубайтами информации.


Проверочная матрица БЧХ-кода

Построим проверочную матрицу для БЧХ-кода. Имеем b и неявный .

  1. Выбираем минимальный , такой что
  2. - поле, в нем существует , такое что
    Существует примитивный элемент , такой что , тогда полагаем
  3. Строим матрицу вида

    Над матрица имеет размер . Над .

Частные случаи

  1. БЧХ-код в узком смысле
  2. - примитивный элемент и код - примитивный
  3. и код называется кодом Рида-Соломона (РС-код)


Пример кода БЧХ

Дано: , , , .

  • Код примитивный: .
  • , следовательно, потребуется расширение поля порядка 4.
  • , :
ATK 4.6.2 17.png
  • Мы скоро докажем, что , поэтому .
  • Корни : .
  • ,
.
  • .

Проверочная матрица над полем–расширением:

но

,
где , поэтому матрицу можно заменить матрицей вида
ATK 4.6.2 18.png

Теорема о конструктивном расстоянии

TemplateDifinitionIcon.svg Определение «Определение - Матрица Вандермонда»
Матрицей Вандермонда называется квадратная матрица следующего вида:

, где - элементы произвольного поля.

TemplateTheoremIcon.svg Теорема Лемма Вандермонда
Рассмотрим матрицу размером :


Доказательство
По индукции:



Допустим, что для это верно. Рассмотрим для . Разложим определитель по последней строке.

где - соответствующие миноры.

- норм., - корни


TemplateTheoremIcon.svg Теорема Теорема о конструктивном расстоянии
Пусть - БЧХ-код с конструктивным расстоянием . Тогда .
Доказательство

Рассмотрим проверочную матрицу кода над полем :

Достаточно доказать, что любые столбцов матрицы линейно независимы (над ).

  • Выберем произвольные столбцов матрицы с номерами .
  • Рассмотрим подматрицу матрицы , образованную этими столбцами:

По лемме Вандермонда:



  • Значит, выбранные столбцы линейно независимы.


Кодирование и декодирование БЧХ кодов

Кодирование

Для кодирования кодов БЧХ применяются те же методы, что и для кодирования и декодирования циклических кодов

Декодирование. Алгоритм Питерсона-Горештейна-Цирлера

Пусть - вектор ошибки, - количество ошибок, . Рассмотрим вектор ошибки , как многочлен . Так как ненулевых символов, данное выражение можно представить в виде:


где - позиции ошибок.
TemplateDifinitionIcon.svg Определение «Определение - Локатор ошибки»
Локатор ошибки однозначно определяет позицию ошибки. Множество локаторов ошибок однозначно определяет все позиции ошибок.
TemplateDifinitionIcon.svg Определение «Определение - Многочлен локаторов ошибки»
Многочлен вида называется многочленом локаторов ошибок.

Основные шаги алгоритма Питерсона-Горештейна-Цирлера:

  1. Вычисление синдрома
  2. Вычисление многочлена локаторов ошибок
  3. Вычисление локаторов
  4. Нахождение позиций ошибок
  5. Вычисление значений ошибок
  6. Корректирование ошибок

Рассмотрим подробнее некоторые из пунктов алгоритма.

Вычисление значений ошибок

Допустим известно и значение синдрома. Построим проверочную матрицу.


Представим вектор как многочлен . Тогда

Обозначим . Возьмем любое . Представим полином ошибки в сокращенном виде

, соответствует .

Получаем СЛУ относительно , остальные коэффициенты известны. Необходимо показать, что матрица вида не вырождена и равна:

так как

только если , но так как это локаторы, отвечающие за разные позиции ошибок,

Значит система разрешима и имеет одно решение.

Вычисление многочлена локаторов ошибок

Необходимо найти все коэффициенты в многочлене . При этом известно .
Подставим вместо . Домножим на .



Просуммируем при фиксированном уравнения по всем .

где - синдромы

- известен, если

Получаем линейную систему относительно с известными коэффициентами.

Необходимо .




Для этого требуется показать, что матрица не вырождена:

Рассмотрим матрицы и вида

. Проверим поэлементно:

где , так как - диагональная

Сложность алгоритма Питерсона-Горештейна-Цирлера

  1. Вычисление синдромов:
  2. Нахождение истинного значения через вычисление определителя матрицы синдромов размера :
  3. Решение линейной системы: .
  4. Процедура Ченя: .
  5. Вычисление позиций ошибок — задача дискретного логарифмирования: перебором .
  6. Если код недвоичный, то решение системы: . Для двоичного кода вычисление не требуется, так как вариант ошибки только один.
  7. Деление многочленов: , но можно .

Итоговая сложность .

где - верхняя граница для количества исправляемых ошибок

Литература

Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М. : Связь, 1979. — С. 744, ил.