Пример пространства состояний (трехмерный куб).
Пример пространства состояний (четырехмерный куб).
Предположим что мы имеем два правильных состояния: 000 и 111. Ошибка исправляется в сторону ближайшего значимого значения. (код корректирует единичную ошибку). дистанция = 3.
У кода исправляющего одинарную ошибку и замечающего двойную дистанция будет равна 4: (Берем опять гиперкуб размерности 4 с кодами 0000 и 1111) дистанция 4 +--------------------------------------+ | | одинарная двойная одинарная код ----- ошибка ----- ошибка ----- ошибка ---- код 0000 0001 0011 1011 1111 <------------ -------------> исправляется исправляется @HR У кода исправляющего двойные ошибки дистанция будет 5. (Берем опять гиперкуб размерности 5 с кодами 00000 и 11111) дистанция 5 +---------------------------------------------------+ | | одинарная двойная двойная одинарная код ----- ошибка ----- ошибка ----- ошибка ---- ошибка ---- код 00000 00001 00011 01011 11011 11111 <-------------------------- --------------------------> исправляется исправляется
И вообще чтобы увеличить количество исправляемых ошибок на 1 надо увеличить дистанцию на 2. d D C 1 0 0 Код невозможен 2 1 0 Parity bit 3 1 1 detect 1, correct 1 3 2 0 detect 2, correct 0 4 3 0 detect 3, correct 0 4 2 1 detect 2, correct 1 5 4 0 detect 4, correct 0 5 3 1 detect 3, correct 1 5 2 2 detect 2, correct 2 .........
Для обнаружения N ошибок: dmin = N + 1 Для исправления N ошибок: dmin = 2*N + 1 Для исправления N ошибок и обнаружения M ошибок: dmin = 2*N + M + 1 d N M 1 0 0 отличие одной комбинации от другой 2 0 1 выявление одиночной ошибки 3 1 0 исправление одиночной ошибки 3 0 2 выявление двойной ошибки 4 1 1 4 0 3 выявление тройной ошибки 5 2 0 исправление двойной ошибки 5 1 2 исправление одиночной ошибки + выявление двойной ошибки 5 0 4 выявление четверной ошибки Но знание бита где произошла ошибка - расширяет наши возможности по коррекции.
