Кафедра Автоматики и Информационных Технологий

Лабораторная работа

"ПРОГРАММНЫЙ КОДЕР-ДЕКОДЕР ДЛЯ ЦИКЛИЧЕСКИХ (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. ............