Лабораторная работа: Программный кодер-декодер для циклических (n,k)-кодов
1. Преследуемые цели
Проведение лабораторных работ по данной тематике преследует следующие цели:
- закрепление теоретического материала, касающегося основных положений математической теории линейных (n, k) – кодов;
- осознание механизма кодирования пакетов данных при передаче файлов;
- практическое освоение алгоритмов кодирования и декодирования применительно к циклическим (n, k) – кодам.
2. Необходимые сведения из теории
Известно, что циклические коды из всех помехоустойчивых кодов находят наибольшее применение на практике.
Циклические коды представляют собой подкласс (подмножество) линейных (n, k) – кодов. Это значит, что все положения теории, которые справедливы для нециклических линейных (n, k) – кодов, справедливы и для кодов циклических. Но циклические коды обладают рядом дополнительных положительных свойств, в частности, они «остро реагируют» на близко расположенные в кодовом слове ошибки, так называемые «пачки ошибок». Кроме того, для них найдены чрезвычайно простые алгоритмы кодирования и декодирования. Все это и обеспечило им широкое применение на практике. Их применение оговорено многими международными стандартами, регламентирующими работу каналов передачи.
Для описания циклических кодов параллельно используется представление кодовых слов и двоичным вектором, и многочленом от некоторой формальной переменной x . Постоянно приходится переходить от одной формы представления к другой. Одну и ту же двоичную последовательность обозначим V , если она рассматривается как вектор, или V (x), если она интерпретируется как многочлен.
2.1 Конструктивное определение циклического ( n , k ) – кода
Циклическим (n , k ) – кодом называется множество многочленов степени не больше (n ‑1 ), каждый из которых нацело делится на (специально подобранный) порождающий многочлен G ( x ) степени (n - k ), являющийся делителем бинома xn +1 .
Циклический код со словами длины n и с порождающим многочленом G (x) существует тогда и только тогда, когда G (x) делит xn +1 [1] . В лекционном курсе было показано, что это требование делимости бинома xn +1 на G (x) вытекает из специфики определения операции символического умножения многочленов (по модулю бинома xn +1 ). Для того, чтобы максимизировать множество слов порождаемого кода при фиксированных значениях длины слов n и кодового расстояния d0 , многочлен G (x) должен быть неприводимым делителем степени (n-k).
2.2 Алгоритм кодирования
На практике чаще всего применяется алгоритм кодирования, который формирует систематический разделимый код. В основу такого алгоритма положена операция деления на G (x). Систематические разделимые коды привлекательны тем, что процедуру кодирования, т.е. преобразования информационного вектора A (длины k ) в вектор кода V (длины n>k ) удается свести лишь к формированию (n-k ) контрольных бит.
Шаг 1. Предварительно вектор A «отнормируем по формату» под длину n, воспользовавшись операцией умножения многочленов A (x) × xn-k . Как было показано в лекционном курсе – это эквивалентно сдвигу вектора A на (n-k ) позиций влево. Произведение многочленов на языке векторов имеет длину n. Существенно для последующего, что правые (n-k ) позиций оказываются непременно нулевыми.
Шаг 2. Произведение A ( x ) × xn - k разделим на G ( x ). Ясно, что в общем случае оно не обязано делиться на G ( x ) нацело. Поэтому следует записать
A (x) × xn-k =Q (x) × G (x)+R (x),
где Q ( x ) - частное от деления;
R ( x ) - остаток. Это многочлен степени не больше (n - k ‑1 ), т. к. делитель имеет степень (n - k ) по определению. Как вектор он имеет длину (n - k ).
Шаг 3. Перенесём остаток R ( x ) в левую часть равенства. Получим:
A (x) × xn-k +R (x)=Q (x) × G (x ).
Теперь в левой части мы получаем многочлен, который нацело делится на G (x) , а это по определению – многочлен, принадлежащий циклическому (n, k ) – коду. В этой последней операции остаток R складывается с нулями (см. шаг1 алгоритма). Следовательно, конечный итог эквивалентен конкатенированию R к вектору А .
2.3 Алгоритм декодирования
Известно несколько алгоритмов декодирования циклических (n , k ) – кодов. В данной лабораторной работе исследуется «декодирование по синдрому», роль которого (синдрома) играет остаток от деления декодируемого многочлена F ( x ) на G (x). Декодирование может производиться с целью только обнаруживать ошибки или с целью исправлять ошибки кратности до t включительно. В любом случае цель достигается в несколько шагов алгоритма.
2.3.1 Декодирование с обнаружением ошибок
Шаг 1. Вычисление остатка R ( x );
Шаг 2. Анализ остатка «на ноль». Нулевой остаток означает, что ошибки не обнаружены;
2.3.2 Декодирование с исправлением ошибок
Шаг 1. Вычисление остатка R ( x );
--> ЧИТАТЬ ПОЛНОСТЬЮ <--