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

7. 11. 15.

8. 12. 16.

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

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

Заметим, что циклический сдвиг является результатом умножения кодовой комбинации на 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.

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