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

11.10. Декодирование кодов с исправлением одиночных ошибок

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

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

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

Возвращаясь к разд. 11.8, можно увидеть, что так что По синдрому (остатку), который равен можно получить цепочку равенств

которую нужно продолжать до тех пор, пока не будет получен остаток Отсюда находится

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

Поэтому нужно начать с этого остатка, который равен некоторой неизвестной степени а, скажем

Будем последовательно проводить умножение на Это эквивалентно сдвигу всех символов на одну позицию вниз. Если символ 1 сдвигается вниз из самой нижней позиции, то используется соотношение Таким образом,

до тех пор, пока не будет получена степень

В рассматриваемом случае так что нужно добавить 1 к символу, соответствующему

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

Можно также начать со старшей степени а и идти вниз до тех пор, пока не получится нужное совпадение. В этом случае можно использовать сдвиг в прямом направлении.

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

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