Обнаружение и исправление независимых ошибок произвольной кратности
Обнаружение ошибок кратности три и ниже
Образующие многочлены кодов, способных обнаруживать одиночные, двойные и тройные ошибки, можно определить, базируясь на следующем указании Хэмминга. Если известен образующий многочлен р(хт) кода длины п, позволяющего обнаруживать ошибки некоторой кратности z, то образующий многочлен g(x) кода, способного обнаруживать ошибки следующей кратности (z + 1), может быть получен умножением многочлена р(хт) на многочлен х + 1, что соответствует введению дополнительной проверки на четность. При этом число символов в комбинациях кода за счет добавления еще одного проверочного символа увеличивается до n + l.
В табл. 4.15 приведены основные характеристики некоторых кодов, способных обнаруживать ошибки кратности три и менее.
Таблица 4.15.
Показатель неприводимого многочлена
Образующий многочлен
Число информационных символов
Длина кода
(x+1)(x3 + x + 1)
(x+1)(x4+ x + 1)
(x+1)(x5+ x + 1)
Важнейшим классом кодов, используемых в каналах, где ошибки в последовательностях символов возникают независимо, являются коды Боуза-Чоудхури-Хоквингема. Доказано, что для любых целых положительных чисел m и s<n/2 существует двоичный код этого класса длины п = 2т-1 с числом проверочных символов не более ms, который способен обнаруживать ошибки кратности 2s или исправлять ошибки кратности s. Для понимания теоретических аспектов этих кодов необходимо ознакомиться с рядом новых понятий высшей алгебры.
Для произвольного линейного блокового (п, k)-кода, рассчитанного на исправление пакетов ошибок длины b или менее, основным соотношением, устанавливающим связь корректирующей способности с числом избыточных символов, является граница Рейджера: n – k ³ 2b
При исправлении линейным кодом пакетов длины b или менее с одновременным обнаружением пакетов длины l ³ b или менее требуется по крайней мере b + l проверочных символов.
Из циклических кодов, предназначенных для исправления пакетов ошибок, широко известны коды Бартона, Файра и Рида-Соломона.
Первые две разновидности кодов служат для исправления одного пакета ошибок в блоке. Коды Рида-Соломона способны исправлять несколько пачек ошибок.
Особенности декодирования циклических кодов, исправляющих пакеты ошибок, рассмотрены далее на примере кодов Файра.