Принципы исправления ошибок

Допустим, что нужно передать определенное количество цифр по каналу, в котором возможно возникновение ошибок, например 5, 6, 8. Если по каким либо причинам одна из цифр изменится, получатель не сможет обнаружить (и исправить) ошибку. Простейший путь обеспечения возможности обнаружения и исправления ошибки – это суммирование всех чисел и передача, кроме них самих, их суммы (19) по тому же каналу. Проверив сумму, получатель обнаружит ошибку. Он не сможет ее исправить и должен будет сделать повторный запрос. При этом только одна из цифр может быть ошибочной. Если ошибочны более чем одна цифра, то не во всех случаях ошибка может быть обнаружена. Улучшенный вариант может быть получен, если снова сложить все 4 цифры и передать вторую проверочную сумму.

Из примера можно сделать 2 важных вывода:

-если необходима более надежная передача, то на это надо тратить больше времени;

-существует определенное ограничение на количество ошибочных цифр, которые можно обнаружить.

В примере показана возможность только обнаружения ошибки, однако существует возможность ее исправления.

Пусть необходимо передать  чисел: .

Добавим  проверочных чисел: , которые называются символами проверки на четность.

Отношение  - называется скоростью кода.

В нашем примере .

Исправление ошибки возможно, если разумным образом добавлены  проверочных символов.

Пусть  и выберем проверочные символы так, чтобы:

;

.

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

Тогда

,

где  - ошибочно принятый символ;

 - возникшая в нем ошибка.

Получатель вычисляет следующие две проверки, так называемые «синдромы»:

;

.

Если при передаче ошибки нет, т. е. , то просто .

Если , то с помощью подстановки находим

; и .

Таким образом, ошибку можно исправить, поскольку , а ошибочная позиция .

Из примера следует:

-можно не только обнаруживать ошибки, но и исправлять их;

-можно применить различные стратегии декодирования: только обнаружение ошибок; исправление ошибок, если это возможно.

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

Таким образом, для исправления t ошибок кодовое слово должно содержать  проверочных символов. При этом нужно иметь 2t независимых уравнений для нахождения значений ошибок и их позиций.

В реально применяемых кодах используется арифметика конечных полей, или полей Галуа. Корректирующие коды часто основаны на коде Рида – Соломона.

⇐ Предыдущая23242526272829303132Следующая ⇒

Поделиться: