Конструктивное определение циклического ( n , k ) – кода

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

Циклическим (n, k) – кодом называется множество многочленов степени не больше (n ‑1), каждый из которых нацело делится на (специально подобранный) порождающий многочлен G (x) степени (n - k), являющийся делителем бинома xⁿ +1.

Циклический код со словами длины n и с порождающим многочленом G (x) существует тогда и только тогда, когда G (x) делит xⁿ+1 [1]. В лекционном курсе было показано, что это требование делимости бинома xⁿ+1 на G (x) вытекает из специфики определения операции символического умножения многочленов (по модулю бинома xⁿ+1). Для того, чтобы максимизировать множество слов порождаемого кода при фиксированных значениях длины слов n и кодового расстояния d₀, многочлен G (x) должен быть неприводимым делителем степени (n-k).

Алгоритм кодирования

На практике чаще всего применяется алгоритм кодирования, который формирует систематический разделимый код. В основу такого алгоритма положена операция деления на G (x). Систематические разделимые коды привлекательны тем, что процедуру кодирования, т.е. преобразования информационного вектора A (длины k) в вектор кода V (длины n>k) удается свести лишь к формированию (n-k) контрольных бит.

Шаг 1.   Предварительно вектор A «отнормируем по формату» под длину n, воспользовавшись операцией умножения многочленов A (x) × x^n-k. Как было показано в лекционном курсе – это эквивалентно сдвигу вектора A на (n-k) позиций влево. Произведение многочленов на языке векторов имеет длину n. Существенно для последующего, что правые (n-k) позиций оказываются непременно нулевыми.

Шаг 2.   Произведение A (x) × x^{n - k} разделим на G (x). Ясно, что в общем случае оно не обязано делиться на G (x) нацело. Поэтому следует записать

A (x) × x^n-k= Q (x) × G (x)+ R (x),

где Q (x) - частное от деления;

R (x) - остаток. Это многочлен степени не больше (n - k ‑1), т. к. делитель имеет степень (n - k) по определению. Как вектор он имеет длину (n - k).

Шаг 3.   Перенесём остаток R (x) в левую часть равенства. Получим:

A (x) × x^n-k+ R (x)= Q (x) × G (x).

Теперь в левой части мы получаем многочлен, который нацело делится на G (x), а это по определению – многочлен, принадлежащий циклическому (n, k) – коду. В этой последней операции остаток R складывается с нулями (см. шаг1 алгоритма). Следовательно, конечный итог эквивалентен конкатенированию R к вектору А.

Алгоритм декодирования

Известно несколько алгоритмов декодирования циклических (n, k) – кодов. В данной лабораторной работе исследуется «декодирование по синдрому», роль которого (синдрома) играет остаток от деления декодируемого многочлена F (x) на G (x). Декодирование может производиться с целью только обнаруживать ошибки или с целью исправлять ошибки кратности до t включительно. В любом случае цель достигается в несколько шагов алгоритма.

Декодирование с обнаружением ошибок

Шаг 1.   Вычисление остатка R (x);

Шаг 2.   Анализ остатка «на ноль». Нулевой остаток означает, что ошибки не обнаружены;

Декодирование с исправлением ошибок

Шаг 1.   Вычисление остатка R (x);

Шаг 2.   Вычисление по найденному остатку предполагаемого (наиболее вероятного) многочлена ошибки Е (х);

Шаг 3.   Исправление декодируемого вектора F путем суммирования F + E = V;

Параметры исследуемых кодов

Чтобы трудоемкость лабораторных работ согласовать с отпущенным временем, исследуются короткие (по меркам практики) коды. Параметры кодов приведены в таблицах 1 – 3.

Согласуйте с преподавателем номер варианта, с которым Вы будете работать. Программы CODER и DECODER следует писать для одного варианта кода.

Таблица №1. Варианты заданий для (n, k) – кодов с длиной слова n=15

Таблица №2. Варианты заданий для (n, k) – кодов с длиной слова n=31

Таблица №3. Варианты заданий для (n, k) – кодов с длиной слова n=63

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США