Решение. Кодом длины п называется произвольное подмножество

Кодом длины п называется произвольное подмножество . Различаются коды по двум их основным харак­теристикам:

- , этот параметр определяет скорость передачи инфор­мации по каналу связи: если канал передает 1 бит за единицу времени, то кодированную информацию канал будет передавать с меньшей скоростью бит за единицу времени.

- — кодовое расстояние, этот параметр определяет возможности исправления ошибок кодом С: если (С) > 2е, то код исправляет е ошибок.

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

Такой структурой для кодов Боуза, Чаудхури, Хоквингема (БЧХ-кодов) является кольцо многочленов

(1)

 

Элементами кольца являются всевозможные многочлены степени не выше п — 1 с коэффициентами 0,1 (остатки от деления на х^п + 1). Операции над многочленами производятся по обычным правилам с заменой результата остатком от деления на х^п + 1.

В виду очевидной биекции

двоичных слов и многочленов не будем их далее различать и гово­рить, например, так: код состоит из многочленов ..., имея в виду соответствующие двоичные слова.

БЧХ-код определяется как совокупность всевозможных мно­гочленов кольца (1), кратных некоторому фиксированному мно­гочлену :

Многочлен называется порождающим. Многочлен может быть любым, но нетрудно убедиться, что произведение дает различные элементы кольца (1) только для много­членов , степень () которых удовлетворяет неравенству

Таким образом, определение БЧХ-кода можно уточнить (1):

Порождающий многочлен БЧХ-кода является делителем многочлена х^п + 1. Многочлен называется проверочным: код можно определить как совокупность всех та­ких многочленов, которые будучи умноженными на проверочный многочлен дают ноль.

Корректирующие возможности БЧХ-кода определяются кор­нями порождающего многочлена. Так как х^п + 1, то корнями порождающего многочлена являются так называемые корни п-й степени из единицы, то есть элементы такие, что . Корни -й степени из единицы имеются в некотором поле, так как для каждого многочлена можно построить поле его разложения. Среди корней -й степени из единицы имеется при­митивный , его степени

все различны и дают все решения уравнения х^п — 1.

Основная теорема о БЧХ-кодах: если корнями порождаю­щего многочлена являются элементы

то БЧХ-код будет исправлять е ошибок.

Возвращаемся к решению задачи. Построение кода разби­вается на ряд этапов.

1. Определение поля, содержащего корни 23-й сте­пени из 1.

Предварительно определяется мультипликативный порядок числа 2 по модулю 23. Имеем по модулю 23:

То, что 2¹¹ = 1 23 означает, что 23 . Действительно,

Рассмотрим поле . Его можно построить как , где - корень неприводимого многочлена 11-й степени. Им является многочлен . Итак, если поле определить как , , то будет примитивным элементом поля, то есть иметь 2047-й порядок.

Рассмотрим в построенном поле элемент . Имеем . Следовательно, - корень 23-й степени из единицы, причем примитивный, что следует из примитивности .