Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

11.8. Один частный случай

Совершенный код Хэмминга имеет символов. При существует матрица (см. разд. 11.3):

Известно, что любая перестановка столбцов матрицы фактически не меняет код, а влияет лишь на то, как и где ищется столбец,

соответствующий синдрому, возникающему при появлении одиночной ошибки.

Предположим, что простой многочлен используется в качестве многочлена-основания. Пусть а — корень этого многочлена, так что или Используя это равенство, можно редуцировать третью и более высокие степени а к суммам более низких степеней. Таким образом, каждый многочлен от а можно представить в виде линейной комбинации элементов

Рассмотрим теперь трехмерные векторы-столбцы с компонентами расположенными снизу вверх. Будем сопоставлять такие векторы последовательным степеням а, начиная с нулевой степени. Заметим, что умножение на а сдвигает каждую компоненту на одну позицию вверх и что каждый раз, когда возникает третья степень а, используется соотношение так что в качестве компонент вектора остаются только I, а Различным степеням а отвечают такие векторы:

Таким образом, показано, что а является примитивным корнем простого многочлена, поскольку последовательные степени а порождают все семь различных ненулевых троек.

Если записать столбцы этой новой матрицы в виде

(для удобства порядок столбцов изменен на обратный), то видно, что получается перестроенная матрица из (11.8.1). При таком расположении столбцов нужно сравнивать вычисленный синдром на приемном конце с последовательными степенями а (их можно запомнить или порождать по мере необходимости). При совпадении синдрома с некоторым столбцом этот столбец представляется в виде соответствующей степени а, отвечающей данному синдрому. (Несколько другой, но эквивалентный код получается при использовании многочлена

Как осуществляется кодирование? Поскольку синдром должен означать отсутствие ошибок, нужно потребовать, чтобы посылаемые многочлены без остатка делились на многочлен Таким образом, поместим сообщение в позиции, соответствующие и временно поместим нули в остальные три позиции, соответствующие При делении полученного многочлена на многочлен-основание получим некоторый остаток. Если поместить этот остаток в последние три позиции нашего многочлена (или, если хотите, прибавить остаток к многочлену), то полученный многочлен будет делиться на основание без остатка. Именно в этом и состоит процедура кодирования: нужно поместить в последние три позиции остаток от деления на основание, после чего весь многочлен будет сравним с нулем по модулю простого многочлена.

Для того чтобы произвести декодирование на приемном конце, нужно просто разделить принятый многочлен на многочлен-основание. Полученный синдром (остаток), будучи записан как некоторая степень а, указывает столбец, в котором произошла ошибка. Следовательно, имеем новую точку зрения на рассмотренные ранее коды Хэмминга, которая позволяет идти дальше.

Пример процедуры кодирования. Посмотрим, как кодировать сообщение представленным выше кодом. Сообщение отвечает многочлену Разделим этот многочлен на и рассмотрим остаток

Поэтому закодированное сообщение имеет вид (

Предположим, что на подчеркнутом месте (т. е. в позиции, отвечающей произошла ошибка, так что принятое сообщение имеет вид Разделив полученное сообщение на тот же многочлен-основание, получим

Этот остаток представляет собой что соответствует четвертому символу справа (где произошла ошибка). Для того чтобы получить правильное сообщение, нужно добавить к этому символу 1, после чего, отбрасывая последние три символа, можно получить первоначальное сообщение.

Задачи

11.8.1. Найдите матрицу декодирования, соответствующую простому многочлену

11.8.2. Аналогично примеру из текста произведите кодирование и декодирование сообщения 1010 при ошибке в позиции, отвечающей

<< Предыдущий параграф Следующий параграф >>
Оглавление