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

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

ообщение, которое было закодировано (1101), является одной из 16 комбинаций четырехразрядного кода. Если требуется передать все эти сообщения в закодированном виде, то каждое из них следует кодировать так же, как и комбинацию 1101. Однако проделывать дополнительные 15 расчетов (в общем случае 2k расчетов) нет необходимости. Это можно сделать проще, путем составления образующей (порождающей) матрицы.

Образующая матрица составляется из единичной транспонированной матрицы и матрицы дополнений.

Число столбцов транспонированной единичной матрицы равно числу информационных символов k. Матрица дополнений получается из остатков от деления единицы с нулями на образующий многочлен Р(Х), выраженный в двоичном эквиваленте. Число остатков равно числу информационных символов.

Как следует из результатов деления единицы с нулями на Р(Х)=Х+1>11, все остатки оказываются равными единице. Поэтому образующая матрица имеет вид

Единичная Матрица

транспо дополнений

нирован

ная матрица

Четыре кодовые комбинации, из которых состоит образующая матрица, являются первыми кодовыми комбинациями циклического кода. Пятая комбинация нулевая, а так как в четырехразрядном непомехозащищенном коде всего N=24 =16 комбинаций, то остальные 11 ненулевых комбинаций находят суммированием по модулю 2 всевозможных комбинаций строк образующей матрицы:

5. 000009. 13.

6. 10. 14.

7. 11. 15.

8. 12. 16.

Сгруппируем полученные комбинации следующим образом:

1.	00011	2.	00101	12.	01111
6.	00110	7.	01010	16.	11110
9.	01100	10.	10100	13.	11101
11.	11000	3.	01001	14.	11011
4.	10001	8.	10010	15.	10111

Видно, что в первом столбце от комбинации к комбинации две рядом стоящие единицы сдвигаются на один символ влево, во втором столбце циклически сдвигаются две единицы, не стоящие рядом друг с другом, а в третьем столбце происходит циклический сдвиг четырех единиц. Этот циклический сдвиг одной комбинации по отношению к другой и определил название кодов -- циклические.

Заметим, что циклический сдвиг является результатом умножения кодовой комбинации на X. Действительно, вторую комбинацию можно записать как 00101> Х2 + 1, седьмую -- как (Х2 + 1)Х = X3 + X>01010 и т. п. Если при умножении на X степень становится равной Xm+l, то полученный результат нужно разделить на Х+1. Например, если комбинацию 10101> Х4+ +Х2 + 1 умножить на X, то получим Х5 + Х3 + X. Деля полученное выражение на Х5 + 1, найдем остаток Х3 + Х + 1 > 01011. Многочлен 01011 и является результатом циклического сдвига на один разряд влево многочлена 10101.

Рассмотрение полученных комбинаций показывает, что все они имеют четное число единиц. Действительно, контрольные символы оказываются равными единице при нечетном числе единиц в исходной комбинации и нулю при четном числе единиц. Таким образом, циклический код с обнаружением одиночной ошибки является обычным кодом с четным числом единиц.

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

1. Выбор числа контрольных символов. Есть два способа выбора числа m. При первом способе исходят из того, что число контрольных символов m= = n -- k зависит от числа информационных символов, а значит, и от длины всей кодовой комбинации. Выбор m производится, как и для кода Хэмминга, с исправлением одиночной ошибки. Условие может быть записано в виде

(1.3)

где Е" -- знак округления в сторону большего значения.

При втором способе число контрольных символов определяется по эмпирической формуле

m=Е" Iog2[(k +1) + E" Iog2 (k + 1)]. (1.4)

В основу выбора m в последнем выражении положено значение числа информационных разрядов. Это удобно, так как первое, что известно в начале кодирования, -- именно число разрядов информационных символов. Уравнение (1.4) дает тот же результат, что и (1.3).

Из (1.3) вытекает, что наиболее экономичными являются коды, для которых log2(n +1) выражается целым числом, то есть когда длина кодовой комбинации

n = 2m - 1,(1.5)

где m должно быть целым числом. Так, при k=11, n=15 и m=4 без всяких округлений. Но при k=12, n=17, так как m = 5 выбрано с округлением в сторону большего значения, что увеличивает избыточность кода: в первом случае И=4/15=0,266, во втором И=5/17=0,295.

2. Выбор образующего многочлена Р(Х). Степень образующего многочлена l не может быть меньше числа контрольных символов m. Это значит, что если m=3, то из табл. 1.1 можно выбрать любой образующий многочлен Р(Х) начиная с третьей степени и выше. Для упрощения технической реализации кодирования степень Р(Х) следует выбирать равной числу m, т. е. l=m. Если в таблице имеется ряд многочленов с данной степенью, то из них следует выбрать самый короткий. Однако число ненулевых членов многочлена Р(Х) не должно быть меньше кодового расстояния d.

3. Нахождение элементов дополнительной матрицы. Дополнительную матрицу находят путем деления единицы с нулями на выбранный многочлен R(X) и выписывания всех промежуточных остатков. При этом должны быть соблюдены следующие условия:

а) число остатков должно быть равно числу информационных символов k;

б) для дополнительной матрицы пригодны лишь остатки с весом W, не меньшим числа обнаруживаемых ошибок r, т. е. в данном случае не меньшим 2 (W?2); так обнаруживается не менее двух ошибок.

Из условий а) и б) определяется количество нулей, приписываемых к единице при делении ее на многочлен Р(Х);

в) так как элементы дополнительной матрицы являются для данной комбинации контрольными символами, то число разрядов дополнительной матрицы равно числу контрольных символов m. Вследствие того, что степень образующего многочлена выбирают равной m, число разрядов дополнительной матрицы равно также степени образующего многочлена. Например, если m=3, а остаток равен 11, то он должен быть записан как 011. Из сказанного вытекает, что разрядность остатка равна степени образующего многочлена.

4. Составление образующей матрицы. Берут транспонированную единичную матрицу и справа приписывают к ней элементы дополнительной матрицы. Пример составления образующей матрицы был дан при рассмотрении циклического кода с обнаружением одиночной ошибки.

5. Нахождение всех комбинаций циклического кода данной группы. Это достигается суммированием по модулю 2 всевозможных сочетаний строк образующей матрицы, как было показано при рассмотрении циклического кода с обнаружением одиночной ошибки.

Пример 1.2. Образовать циклический код, позволяющий обнаруживать двукратные ошибки или исправлять одиночную ошибку из всех комбинаций двоичного кода на все сочетания с числом информационных символов k = 4.

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

m = Е" Iog2 [(4 + 1 ) + E"log2 (4 + 1 )] = Е" Iog2 (5 + 3)= 3.

Из табл.1.1 выбираем один из образующих многочленов третьей степени. Пусть Р(Х)=Х3 + Х + 1> 1011. Находим остатки от деления единицы с нулями на Р(Х), которые соответственно равны 011, 110, 111, 101. Остатков должно быть четыре согласно числу информационных символов. Выписывая транспонированную единичную матрицу и приписывая к ней справа матрицу дополнений в виде остатков, получаем образующую матрицу

k4	k3	k2	k1	m3	m2	m1
a1	0	0	0	1	0	1	1
a2	0	0	1	0	1	1	0
a3	0	1	0	0	1	1	1
a4	1	0	0	0	1	0	1

Так как все члены единичной матрицы являются комбинациями заданного четырехразрядного двоичного кода, то четыре комбинации образующей матрицы представляют собой четыре комбинации требуемого циклического кода. Остальные 11 комбинаций циклического кода (начиная с пятой) могут быть получены путем суммирования по модулю 2 этих четырех комбинаций образующей матрицы так, как было проделано для кода с d=2:

10.

11.

12.

13.

Заметим, что комбинация 13 была получена при выводе уравнения (1.2). Если сложить комбинации , то получим циклический код 1011000, в котором контрольными символами являются одни нули. Нулевая комбинация может быть также использована: у нее все символы -- нули.

Как следует из табл. 1.1, в качестве образующего можно было бы взять и многочлен Р(Х)=Х3 + Х2 + 1> 1101. В этом случае образующая матрица приняла бы вид

a10001101

a20010111

a30100011

a41000110

Многочлен Р(Х)=Х3 + Х + 1> 1011 называется обратным или двойственным многочленом многочлена Р(Х)=Х3 + Х2 + 1> 1101. Действительно, сравнивая записанные в двоичной форме выражения обоих многочленов, видим, что нули и единицы в обратном многочлене расположены зеркально относительно основного многочлена, т. е. младший разряд становится старшим. Так, многочлен 1110101 является обратным многочлену 1010111. Двойственный многочлен можно записать в виде

Р*(Х)=Хn-1Р(Х-1). (1.6)

В нашем примере Р*(Х)= Х3(Х-3 + Х-2 + 1) = Х3 + Х + 1. Использование двойственных многочленов расширяет возможности построения циклических кодов, так как если Р(Х) -- неприводимый многочлен, то и многочлен Р*(Х) также неприводим.

Циклическое кодирование можно осуществлять не только путем составления образующей матрицы из транспонированной матрицы и матрицы дополнения. Тот же результат достигается, если каждый из членов единичной транспонированной матрицы умножить на образующий многочлен. Так, если образующий многочлен Р(Х)=Х3 + Х + 1> 1011, то умножение транспонированной единичной матрицы на этот многочлен даст

0001X1011=0001011

0010Х1011=0010110

0100X1011=0101100

1000X1011=1011000

Заметим, что, например, умножение 0100X1011 эквивалентно 1011X X100=101100. Нуль слева (0101100) приписывается для комплектности кода. Результатом умножения явился циклический сдвиг образующего многочлена. Сложением полученных комбинаций можно образовать те же комбинации, что и с помощью двух предыдущих образующих матриц.

Нами был выбран в качестве исходного четырехэлементный двоичный код на все сочетания (k = 4), что позволило образовать 24=16 комбинаций циклического кода. Эти комбинации являются разрешенными, так как после кодирования разрядность кода из-за наличия контрольных символов m = 3 увеличилась до n = 7. Из 128 комбинаций семиразрядного двоичного кода 112 будут неразрешенными. При этом сравнение комбинаций, полученных с помощью образующей матрицы обоими многочленами, показывает, что из 32 комбинаций совпадают только нулевые и составленные из одних единиц.

Таким образом, из двоичного кода на все сочетания (k=4) были образованы два циклических кода с помощью различных образующих многочленов: Р(X)=1011 и P(X)=1101. При этом, несмотря на то что в каждом коде комбинации различны, оба кода вполне правомочны, так как комбинации в каждом из них отличаются друг от друга на кодовое расстояние d=3. В то же время сравнение кодов, составленных образующей матрицей [многочлен Р(Х)=Х3 + Х + 1] и умножением транспонированной матрицы на тот же многочлен, показывает полную идентичность комбинации этих кодов.

Теперь, когда ясна роль образующего многочлена при составлении циклических кодов, вырисовываются также следующие его свойства, которые могут помочь при изучении более сложных циклических кодов.

Первое свойство образующего многочлена заключается в том, что все разрешенные комбинации делятся на него без остатка. Это свойство следует из (1.2), и его можно проверить, разделив любую комбинацию кода на образующий ее многочлен. Таким образом, многочлен Р(Х) как бы позволяет образовать или выбрать из большего числа комбинации, удовлетворяющие только заданному закону построения кода, т. е. разрешенные. Поэтому многочлен Р(Х) и называется образующим.

Второе свойство образующего многочлена таково, что на него делится без остатка не только разрешенная комбинация, имеющая степень n -- 1, но и двучлен Хn + 1. В нашем примере n = 7. При делении числа 10000001 на 1011 получается частное 10111 без остатка. Это значит, что образующий многочлен входит в качестве сомножителя в разложение двучлена Хn + 1, который с учетом равенства (1.5) можно записать в виде . Так для двучлена составляющие сомножители разложения должны быть неприводимыми многочленами, степени которых являются делителями числа m = 3. К числам, на которые m = 3 делится без остатка, относятся 1 и 3. Из табл. 1.1 выпишем все неприводимые многочлены первой и третьей степеней, которые и явятся сомножителями в разложении двучлена Х7+1:

Х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, где

Страницы: 1, 2, 3

Меню

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