1. Преследуемые цели
Проведение лабораторных работ по данной тематике преследует следующие цели:
- закрепление теоретического материала, касающегося основных положений математической теории линейных (n, k) – кодов;
- осознание механизма кодирования пакетов данных при передаче файлов;
- практическое освоение алгоритмов кодирования и декодирования применительно к циклическим (n, k) – кодам.
Возможно вы искали - Курсовая работа: Программный комплекс учёта работы предприятия по озеленению
2. Необходимые сведения из теории
Известно, что циклические коды из всех помехоустойчивых кодов находят наибольшее применение на практике.
Циклические коды представляют собой подкласс (подмножество) линейных (n, k) – кодов. Это значит, что все положения теории, которые справедливы для нециклических линейных (n, k) – кодов, справедливы и для кодов циклических. Но циклические коды обладают рядом дополнительных положительных свойств, в частности, они «остро реагируют» на близко расположенные в кодовом слове ошибки, так называемые «пачки ошибок». Кроме того, для них найдены чрезвычайно простые алгоритмы кодирования и декодирования. Все это и обеспечило им широкое применение на практике. Их применение оговорено многими международными стандартами, регламентирующими работу каналов передачи.
Для описания циклических кодов параллельно используется представление кодовых слов и двоичным вектором, и многочленом от некоторой формальной переменной x . Постоянно приходится переходить от одной формы представления к другой. Одну и ту же двоичную последовательность обозначим V , если она рассматривается как вектор, или V (x), если она интерпретируется как многочлен.
2.1 Конструктивное определение циклического ( n , k ) – кода
Похожий материал - Реферат: Программы DOS
Циклическим (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 ) позиций оказываются непременно нулевыми.
Очень интересно - Курсовая работа: Программы в среде Turbo Pascal
Шаг 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 );