Передача информации по каналу с решающей обратной связью (стр. 6 из 11)
Х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. Складываем: 0111011
001 = 0111010. Теперь осуществляем два циклических сдвига последней комбинации вправо: после первого она принимает вид 0011101, после второго — 1001110, т.е. получается уже исправленная комбинация. Проверка показывает, что эта комбинация делится на Р(Х) без остатка.1.3 Математическая модель
Исходя из технического задания 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. Пусть 
1.4 Построение образующей матрицы
Из выше полученных расчетов мы знаем, что число информационных символов (бит) равно 9. Следовательно размерность единичной матрицы будет 9. Число проверочных символов m = 5, следовательно получим дополнительную матрицу, имеющую 9 строк и 5 столбцов.