Методы декодирования циклических кодов и обнаружения ошибок

Обнаружение ошибок. Идея обнаружения ошибок в принятом циклическом коде заключается в том, что при отсутствии ошибок закодированная комбинация F(X) делится на образующий многочлен Р(Х) без остатка. При этом контрольные символы m отбрасываются, а информационные символы k используются по назначению. Если произошло искажение принятой комбинации, то эта комбинация F(X) преобразуется в комбинацию Н(Х), которую можно представить как сумму двух многочленов:

H(X)=F(X) + E(X),(1.11)

где Е(Х)—многочлен ошибок, содержащий столько единиц, сколько элементов в принятой комбинация не совпадает с элементами переданной комбинации.

Пусть, например, была передана комбинация кода (7,4) ==1101001, закодированная с помощью Р(Х)=1011. Если она принята правильно, то деление на Р(Х) даст остаток, равный нулю. Если же комбинация принята как Н(Х)=1101011, то при делении на Р(Х) образуется остаток 010, что свидетельствует об ошибке, и принятая комбинация бракуется.

Обнаружение и исправление ошибок. Существует несколько вариантов декодирования циклических кодов. Один из них заключается в следующем.

1. Вычисление остатка (синдрома). Так же как и в кодах с обнаружением ошибок, принятую комбинацию делят на образующий многочлен Р(Х). Остаток R(X)=0 означает, что комбинация принята без ошибок. Наличие остатка свидетельствует о том, что комбинация принята искаженной. Дальнейшая процедура исправления ошибок протекает таким образом.

2. Подсчет веса остатка W. Если вес остатка равен или меньше числа исправляемых ошибок, т.е. , то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию.

3. Циклический сдвиг на один символ влево. Если W>s, то производят циклический сдвиг на один символ влево и полученную комбинацию снова делят на образующий многочлен. Если вес полученного остатка , то циклически сдвинутую комбинацию складывают с остатком и затем циклически сдвигают ее в обратную сторону вправо на один символ (возвращают на прежнее место). В результате получают исправленную комбинацию.

4. Дополнительные циклические сдвиги влево. Если после циклического сдвига на один символ по-прежнему W>s, то производят дополнительные циклические сдвиги влево. При этом после каждого сдвига сдвинутую комбинацию делят на Р(Х) и проверяют вес остатка. При  выполняют действия, указанные в п. 3, с той лишь разницей, что обратных циклических сдвигов вправо делают столько, сколько их было сделано влево.

Пример 1.4. Принят код 1101110, закодированный образующим многочленом Р(Х)=1011 и с s = l. Проверить наличие ошибки и в случае обнаружения исправить ее.

Делим комбинацию 1101110 на 1011 и находим, что остаток R(X)=111. Так как это не удовлетворяет равенству W=s, сдвигаем комбинацию 1101110 циклически на один символ влево. Получаем 1011101. В результате деления этой комбинации на Р(Х) находим остаток R1(X)=101. Вес этого остатка равен двум, т.е. больше s. Осуществляем новый циклический сдвиг влево. Получаем 0111011. Деление на Р(Х) дает остаток R2(X)=001, вес которого равен s. Складываем: 0111011  001 = 0111010. Теперь осуществляем два циклических сдвига последней комбинации вправо: после первого она принимает вид 0011101, после второго — 1001110, т.е. получается уже исправленная комбинация. Проверка показывает, что эта комбинация делится на Р(Х) без остатка.

Математическая модель

Исходя из технического задания d = 4, а согласно формуле

d = r + s + 1, где

d — минимальное кодовое расстояние;

r — число обнаруживаемых ошибок;

s — число исправляемых ошибок.

имеем 2 варианта:

1) r = 2, s = 1 – обеспечивает обнаружение двух ошибок и исправление одной;

2) r = 3, s = 0 – обеспечивает обнаружение тройных ошибок;

Выбираем вариант 1, так как вариант номер 2 не допустим по ТЗ (нет исправления ошибок).

Имеем алфавит в 256 символов, что потребует 9 разрядов, так как комбинацию 00000000 использовать не будем. Имеем k = 9.

Опеределим число контрольных символов :

n = k + m

Так как k = 9, то

Тогда для :

n = 9 + 5 = 14

Найдём образующий многочлен:

Выберем  из таблицы 1.1. Пусть