Коды с гарантированным обнаружением и исправлением ошибок.

Избыточный код V может использоваться в канале связи с помехами не только для декодирования (распознавания) действительно передававшихся сообщений, т.е. фактически для исправления ошибок, но и для обнаружения ошибок. Естественным алгоритмом декодирования с обнаружением ошибок является принятие решения об отсутствии ошибок, когда принятая комбинация “у” совпадает с одной из разрешённых кодовых комбинациях, т.е. у = х_i V, и обнаружение ошибок, если у х_i. для всех x_i V. Очевидно, что в этом случае возможны ошибки декодирования, а именно принятие решения об отсутствии ошибки, в то время как они в действительности имеют место.

Определение 7. Будем говорить, что код V гарантированно обнаруживает или исправляет ошибки кратности не больше t при использовании некоторого алгоритма обнаружения или исправления ошибок, если кодовые слова после применения этих алгоритмов не будут содержать необнаруженных или неисправленных ошибок, когда кратность ошибки в канале связи не превосходит t.

Определение 1. Расстоянием Хэмминга ρ(х,х') между двумя комбинациями х и х' Х^п будем называть число позиций этих комбинаций, в которых отдельные кодовые символы х и х' не совпадают. Очевидно, что 1 ρ(х,х') для любых х и что р(х,х) = 0 для любых х .

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

Определение 3. Весом Хэмминга |х| блока (вектора) х (аналогично для у и е) будем называть число ненулевых символов этих блоков.

Определение 4. Кратностью ошибки е будем называть его вес Хэмминга |е|. (т.е. число ошибок, которое произошло при передаче блока х.)

Определение 6. Минимальным кодовым расстоянием d для заданного кода V будем называть минимальное расстояние по Хэммингу между всеми парами его несовпадающих кодовых комбинаций

Теорема 7.3. Если код имеет минимальное расстояние d, то он гарантированно обнаруживает ошибки кратности не более чем t₀= d -1

Дата добавления: 2015-12-07