Разделы сайта

Анализ возможности использования корректирующих кодов

Корректирующая способность циклического кода определяется видом образующего многочлена. Исходным при выборе этого многочлена является кодовое расстояние α, которым должен обладать формируемый циклический код. Величина α определяет необходимое количество проверочных символов в комбинации - степень образующего многочлена р (х). Многочлен р (х), кроме того, должен являться одним из неприводимых многочленов (многочленов, не делящихся ни на какой другой многочлен), являющихся сомножителями разложения бинома

(2.18)

В таблице 3, заимствованной из [16], представлены все неприводимые многочлены до шестой степени включительно и некоторые многочлены от седьмой до десятой степени.

Рассмотрим в качестве примера процессы кодирования и декодирования циклическим кодом, содержащим к =4 информационных символов и имеющим кодовое расстояние α =3, то есть исправляющим однократные или обнаруживающим двукратные ошибки.

Для обеспечения α =3 кодовая комбинация должна содержать q =3 проверочных символа. При этом значностъ кода n=k+q=4+3=7. Из таблицы 3 выбираем образующий многочлен

p (x) = x3+x+1.

Предположим, что необходимо закодировать комбинацию 1011. Комбинации соответствует многочлен G (x) = x3+x+1. В соответствии со вторым из рассмотренных способов кодирования умножим этот многочлен на x3

x3G (x) = x6+x4+x3.

Разделим x3G (x) на р (х) и найдем остаток R (x)

Остаток R (x) = x2. Искомый многочлен F (x) = x3G (x) +R (x) =x6+x4+x3+x2, что соответствует двоичной комбинации 1011100.

Допустим, что при передаче оказался искаженным символ в шестом разряде комбинации, то есть принята комбинация 1111100. В процессе декодирования производится деление многочлена, соответствующего принятой комбинации, на образующий многочлен. Выполним это деление, пользуясь только коэффициентами многочленов:

Остаток, отличный от нуля, свидетельствует о наличии ошибки в принятой комбинаций. В рассматриваемом примере остаток может состоять из трех элементов (максимальная степень R (x) равна 2), которые в зависимости от номера искаженного символа образуют одну из семи комбинаций, не считая нулевой - 000. Следовательно, по виду остатка можно определить номер любого из 7 символов принятой комбинации, который окажется искаженным, и внести исправления.

Кодирующее устройство циклического кода состоит из двух основных узлов, один из которых обеспечивает умножение исходного многочлена на xq, а во втором производится деление произведения xqG (x) на P (x).

Первый узел представляет собой сдвигающий регистр, не отличающийся какими-либо особенностями. Деление на неприводимый многочлен Р (х) рассмотрим подробнее. Из примера (2.19) видно, что деление заключается в последовательном сложении по модулю два делителя вначале со старшими членами делимого, затем со старшими членами (начиная с первого значащего члена) получившегося остатка, и так до тех пор, пока степень остатка не станет меньше степени делителя.

Такая последовательность операций при делении любого многочлена на многочлен P (x) может быть осуществлена сдвигающим регистром с обратными связями, образованными сумматорами по модулю два.

На рисунке 14 представлены функциональные схемы регистров с обратными связями, соответствующие различным неприводимым многочленам Р (х). Регистры содержат q ячеек (степень многочлена Р (x)) и (z-1) встроенных сумматоров по модулю два, где z - количество членов многочлена Р (х).

На каждую ячейку регистра подаются тактовые импульсы. На схеме эти цепи не показаны. Если записать многочлен P (x), начиная с младшего члена, перед которым поставить знак плюс, и старший член вместе со знаком плюс отбросить, то местоположение сумматоров по модулю два на функциональной схеме будет определяться этой записью. Сумматор для сложения старших разрядов многочлена P (x) и последовательности информационных символов не нужен, так как результат сложения старших разрядов делимого и делителя равен нулю (2.19).

P (x) =x2+x+1

P (x) = x3+x2+1

P (x) = x4+x+1

Рисунок 14

На рис.15 представлена схема кодирующего устройства циклического кода (7/4) с образующим многочленом P (x) =x3+x2+1.

Рисунок 15

Схема работает следующим образом. Информация на вход кодирующего устройства поступает в последовательном коде. Для деления многочлена xqG (x) в рассматриваемом примере требуется 7 тактов. В течение первых трех тактов оба регистра заполняются информационными символами (эта операция эквивалентна умножению G (x) на xq). Затем в течение последующих 4 тактов происходит деление информационной последовательности на образующий многочлен, и на выход поступают все 4 информационных символа комбинаций. Ключ 1 при этом закрыт, а ключ 2 открыт.

Перейти на страницу: 1 2 3 4 5 6 7

Самое читаемое:

Исследование наноструктурированной поверхности на АСМ Solver HV
Целью курсовой работы является изучение принципов сканирующей зондовой микроскопии, получение навыков работы на АСМ SOLVERHV. Преимущество АСМ SOLVER HV состоит в том, что система позволяет проводить параллельно с изучением топографии поверхности исследуемого образца физические, магнитные, электрические и электростатические хара ...