Принципы обнаружения и исправления ошибок. – Ракаев

 

Идея обнаружения ошибок заключается в том, что для передачи сообщений используют не все N кодовых комбинаций, а только часть из них N₀, которые называются разрешёнными. Оставшиеся ΔN=N-N₀ комбинаций называют запрещёнными. Ошибки обнаруживают тогда, когда на приёмной стороне получают запрещённую комбинацию. Доля обнаруживаемых ошибок

ΔN/N=1-N₀/N.

Если ΔN=0 т.е. N= N₀, то код не способен обнаруживать ошибки и его называют примитивным (безызбыточным).

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

r_K=1-(log N₀)/(n log b).

Очевидно, что доля обнаруживаемых ошибок растёт с увеличением избыточности кода.

Исправление ошибок корректирующими кодами основано на определении "расстояния" между кодовыми комбинациями и отыскании минимального расстояния до разрешённой кодовой комбинации.

Расстоянием d_ij между кодовыми комбинациями K_i и K_j называют результат сложения по модулю b одноименных разрядов кодовых комбинаций

где и - k-й разряд кодовых комбинаций, n - значность кода.

При суммировании по модулю результат равен модулю суммы разрядов, если этот модуль меньше b. Если модуль суммы разрядов больше b, то результат получают вычитанием b из суммы.

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

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

Для равномерного двоичного кода кодовое расстояние - это число символов, на которое отличается одна комбинация от другой. Например, если K_i=10111, K_j=01010, то d_ij=4.

Методика исправления ошибок состоит в том, что, обнаружив ошибку, вычисляют расстояние от полученной запрещённой комбинации K_i до всех разрешённых K_j,j=1,…,N₀. В качестве переданной принимают ту из разрешённых комбинаций, до которой расстояние является наименьшим.

Например, если mind_ij= d_i5, j=1,…,N₀, то полагают, что была передана комбинация K₅.