Поле ,

Элемент является корнем многочлена

Остальными корнями этого многочлена являются элементы

Эти элементы далее не рассматриваем.

Найдем минимальный многочлен элемента . Исполь­зуя таблицу поля, вычислим последовательные степени :

Умножая эти равенства на указанные слева коэффициенты и при­равнивая нулю коэффициенты при , …, в правой части, по­лучаем линейную систему для :

а₂=0

Учитывая, что а₀ = 1 (иначе получится приводимый многочлен) без труда находим решение

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

Найдем минимальный многочлен элемента Действуя

аналогично имеем

Система

=0

Снова полагая а₀ = 1, находим решение

Таким образом, минимальным многочленом элемента явля­ется многочлен Он совпадает с минимальным много­членом элемента а из поля рь Следовательно, нужный изомор­физм получится, если положить Образ любого элемента можно вычислить с помощью соотношения (1).

Задачи для самостоятельного решения

1. Установить изоморфизм полей

и .

2. Установить изоморфизм полей

и .

Домашнее задание

1. Установить изоморфизм полей

и .

2. Установить изоморфизм полей

и .

Занятие 15

Линейные коды

План занятия

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

2. Подробное решение типовой задачи

3. Самостоятельное решение задач

4. Получение домашнего задания

Типовая задача

Построить линейный код Хемминга длины 7, исправляющий одну ошибку.

Решение

7-разрядный код Хэмминга представляет собой линейный код с проверочной матрицей:

.

Его слова являются решениями линейной однородной системы или

Ее общее решение имеет вид

Придавая значения 0,1, получим 16 слов кода

Кодовое расстояние для линейного кода вычисляется по формуле , где - вес Хэмминга слова , равный числу единиц в нем. В нашем случае , поэтому этот код исправляет одну ошибку.

Задачи для самостоятельного решения

Построить линейный код Хемминга длины 15, исправляющий одну ошибку.

Домашнее задание

Построить линейный код Хемминга длины 31, исправляющий одну ошибку.

Занятия 16, 17

Построение БЧХ-кодов

План занятия

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

2. Подробное решение типовой задачи

3. Самостоятельное решение задач

4. Получение домашнего задания

Типовая задача

Построить БЧХ-код со следующими параметрами: длина кодовых слов – 23, количество исправляемых ошибок – 2. Для построения кода необходимо 1) вычислить основные параметры кода: мощность и кодовое расстояние; 2) найти порождающий и проверочный многочлены кода; 3) описать алгоритм кодирования и построить схему, производящую кодирование, используя сдвиговые регистры и функциональные элементы; 4) описать алгоритм декодирования.

Решение

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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