Оценка корректирующей способности блокового кода
Оценка корректирующей способности блокового (n, k) кода
Кодовое (хемминговое) расстояние - число несовпадающих разрядов двух кодовых комбинаций.
Минимальное кодовое расстояние (d) - минимальное расстояние, взятое по всем парам разрешенных кодовых комбинаций.
Кратность ошибки (r) - число искаженных символов кодовой комбинации.
Вес кодовой комбинации - число единиц в двоичной кодовой комбинации.
Вектор ошибки - двоичный код, содержащий 1 в искаженных и 0 в остальных разрядах.
Доля обнаруживаемых ошибок 2k(2n-2k)/(2k2n) = 1 - 2k-n
Число кодовых комбинаций: любых 2n , разрешенных 2к, запрещенных 2n - 2k .
Число вариантов передачи кода 2к 2n. Ошибка обнаруживается, если при передаче разрешенной комбинации получена запрещенная комбинация. Число таких вариантов 2k(2n-2k).
Рекомендуемые материалы
Доля исправляемых ошибок среди обнаруживаемых 2k(2n-k-1)/2k(2n-2k)=2-k. Запрещенную кодовую комбинацию заменяют ближайшей разрешенной комбинацией. Ближайшими к разрешенной комбинации являются 2n-k-1 запрещенных кодовых комбинаций. Ошибка будет исправлена, если принятая запрещенная комбинация окажется «ближайшей» к переданной разрешенной комбинации. Число таких случаев 2k(2n-k-1).
Установим связь кодового расстояния d и кратности обнаруживаемых и исправляемых ошибок. Все возможные кодовые комбинации можно представить точками или векторами в многомерном пространстве. Точки подмножества запрещенных комбинаций, соответствующих разрешенной комбинации, можно считать расположенными на сферах радиусов 1, 2, и т.д., равных кодовому расстоянию до разрешенной комбинации. Как видно из рисунка, где кодовое расстояние d =6, можно обнаружить ошибки кратности r =5 и исправить ошибки кратности s =2. В общем случае должны выполняться условия:
Вместе с этой лекцией читают "3.6 Точечные случайные процессы. Формула Ито для считающих процессов. Компенсаторы".
d ³ r + 1 для обнаружения ошибки кратности r,
d ³ 2s + 1 для исправления ошибки кратности s,
d ³ r + s + 1 (r ³ s) для обнаружения и одновременного исправления ошибок кратности r и s.
Для исправления ошибки контрольная кодовая комбинация должна указывать место ошибки. Следовательно, число различных контрольных кодовых комбинаций должно быть не менее количества различных ошибок.. Число ошибок кратности r равно числу сочетаний Сnr . При s = 1 (исправление ошибки кратности 1) должно выполняться условие 2n-k-1 > Cn1 = n, при s = 2 - условие 2n-k-1 > Cn1+ Cn2, в общем случае – условие
Эта оценка Хемминга определяет минимальную избыточность, необходимую для исправления ошибок. Коды с минимальной избыточностью, для которых неравенство превращается в равенство, называются совершенными.