Обнаружение одиночных ошибок. Исправление одиночных или обнаружение двойных ошибок. Адхамов З.Ш N3200

Обнаружение одиночных ошибок. Любая принятая по каналу связи кодовая комбинация h(x), возможно содержащая ошибку, может быть представлена в виде суммы по модулю два неискаженной комбинации кода f(x) и вектора ошибки (х): h(x) = f(x) (x) При делении h(x) на образующий многочлен g(x) остаток, указывающий на наличие ошибки, обнаруживается только в том случае, если многочлен, соответствующий вектору ошибки, не делится на g(x): f(x) неискаженная комбинация кода и, следовательно, на g(x) делится без остатка Полученный циклический код с проверкой на четность способен обнаруживать не только одиночные ошибки в отдельных разрядах, но и ошибки в любом нечетном числе разрядов.

Исправление одиночных или обнаружение двойных ошибок. Прежде чем исправить одиночную ошибку в принятой комбинации из n разрядов, необходимо определить, какой из разрядов был искажен. При степени многочлена m = n-k он может дать 2 n-k - 1 ненулевых остатков (нулевой остаток является опознавателем безошибочной передачи). Следовательно, необходимым условием исправления любой одиночной ошибки является выполнение неравенства 2 n-k – 1 C 1 n = n где C 1 n - общее число разновидностей одиночных ошибок в кодовой комбинации из n символов; отсюда находим степень образующего многочлена кода m = n – k log2(n+1) и общее число символов в кодовой комбинации.

Наибольшие значения k и n для различных m можно найти пользуясь таблицей 1. Таблица 1. M N K

Надо добавить, что в качестве образующего следует выбирать такой неприводимый многочлен g(x) (или произведение таких многочленов), который, являясь делителем двучлена x n + 1, не входит в разложение ни одного двучлена типа x λ + 1, степень которого λ меньше n. В этом случае говорят, что многочлен g(x) принадлежит показателю степени n.

В таблице 2 приведены основные характеристики некоторых кодов, способных исправлять одиночные ошибки или обнаруживать все одиночные и двойные ошибки. Таблица 2. Показатель неприводимого о многочлена Образующий многочлен Число остатков Длина кода x2 + x + 1 x3 + x + 1 x3 + x2 + 1 x4 + x3 + 1 x4 + x + 1 x5 + x2 + 1 x5 + x

Это циклические коды Хэмминга для исправления одной ошибки, в которых в отличие от групповых кодов Хэмминга все проверочные разряды размещаются в конце кодовой комбинации. Эти коды могут быть использованы для обнаружения любых двойных ошибок. Многочлен, соответствующий вектору двойной ошибки, имеет вид ξ(х) = x i – x j, или ξ(x) = x i (x j-i + 1) при j>i. Так как j – i<n, a g(x) не кратен х и принадлежит показателю степени n, то ξ(x) не делится на g(x), что и позволяет обнаружить двойные ошибки.