Передача информации по каналу с решающей обратной связью

Х7+1= (Х+1)(Х3 + Х +1)(Х3 + Х2 + 1)(1.7)

Один из неприводимых многочленов третьей степени и должен быть выбран для кодирования, если k=4. Заметим, что такое разложение двучлена Хn+1 является одним из методов выбора образующего многочлена.

В рассмотренном примере при k=4 и m=3 n=k+m=7. В литературе циклические коды такого типа называются кодами (7,4). Из примера не следует, что для всех

циклических кодов с обнаружением двойной ошибки образующий многочлен будет всегда иметь третью степень. Чем больше длина кода, тем выше степень образующего многочлена, что объясняется увеличением числа контрольных символов. Так, при k=26 согласно уравнению (1.4) m = 5. Это значит, что степень образующего многочлена должна быть не меньше пятой. Такой код обозначают как код (31,26).

Циклические коды с d=4. Эти коды могут обнаруживать одиночные, двойные и тройные ошибки или обнаруживать двойные и исправлять одиночные ошибки.

1. Выбор числа контрольных символов. Число контрольных символов в этом коде должно быть на единицу больше, чем для кода с d=3:

(1.8)

Для нахождения можно воспользоваться уравнением (1.4). Если число контрольных символов определяется, как в коде Хэмминга, то уравнение (1.3) примет вид

(1.9)

2. Выбор образующего многочлена. Образующий многочлен : равен произведению двучлена (Х+1) на многочлен

(1.10)

Это объясняется тем, что двучлен (Х+1) позволяет обнаружить все одиночные и тройные ошибки, а многочлен Р(Х) — двойные ошибки. Так, для кода (7,3), обнаруживающего все трехкратные ошибки, можно было бы выбрать .

В общем случае степень l многочлена равна числу m. Дальнейшая процедура кодирования остается такой же, как и при образовании кода с обнаружением двойной ошибки.

Пример 1.3. Требуется закодировать сообщение 10101010101010 циклическим кодом с d = 4:

G(X)= Х13 + Х11 + Х9 + Х7 + Х5 + Х3+ Х →10101010101010.

Определяем число контрольных символов по уравнению (1.4):

Из уравнения (1.8) следует, что . Выбираем из табл. 1.1 образующий многочлен для d=3. Пусть . Тогда

Так как необходимо закодировать только одно сообщение G(X), а не весь ансамбль двоичных кодов с k=14, то будем придерживаться процедуры кодирования, выполняемой по уравнению (1.2). Выбираем одночлен . Тогда

Разделив полученное выражение на , находим остаток:

Следовательно, передаваемая закодированная комбинация будет иметь вид F(X) = (Х19 + Х17 + Х15 + Х13 + Х11 + Х9 + Х7) + (Х4 + Х3 + Х2 + X + 1) .

10101010101010 011111

Информационные Контрольные

символы символы

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

Обнаружение ошибок. Идея обнаружения ошибок в принятом циклическом коде заключается в том, что при отсутствии ошибок закодированная комбинация 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. Складываем: 0111011001 = 0111010. Теперь осуществляем два циклических сдвига последней комбинации вправо: после первого она принимает вид 0011101, после второго — 1001110, т.е. получается уже исправленная комбинация. Проверка показывает, что эта комбинация делится на Р(Х) без остатка.

 Скачать реферат