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

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

Многочлен в поле двоичных чисел называется неприводимым, если он делится без остатка только на себя или на единицу; что касается многочленов, приведенных в табл. 1.1, то это определение справедливо тольк

о для конечного поля двоичных чисел.

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

1.2.4 Методы построения циклических кодов

В качестве информационных символов k для построения циклических кодов берут комбинации двоичного кода на все сочетания. В общем случае, если заданную кодовую комбинацию Q(X) умножить на образующий многочлен Р(Х), получится циклический код, обладающий теми или иными корректирующими свойствами в зависимости от выбора Р(Х). Однако в этом коде контрольные символы m будут располагаться в самых разнообразных местах кодовой комбинации. Такой код не является систематическим, что затрудняет его схемную реализацию. Ситуацию можно значительно упростить, если контрольные символы приписать в конце кода, то есть после информационных символов. Для этой цели целесообразно воспользоваться следующим методом.

1. Умножаем кодовую комбинацию G(X), которую мы хотим закодировать, на одночлен , имеющий ту же степень, что и образующий многочлен Р(Х).

2. Делим произведение на образующий многочлен Р():

(1.1)

где Q(X) — частное от деления; R(X) — остаток.

Умножая выражение (1.1) на Р(Х) и перенося R(X) в другую часть равенства, согласно правилам алгебры двоичного поля, т. е. без перемены знака на обратный, получаем

(1.2)

Таким образом, согласно равенству (1.2), циклический код, т. е. закодированное сообщение F(X), можно образовать двумя способами:

1 ) умножением одной из комбинаций двоичного кода на все сочетания [комбинация Q(X) принадлежит к той же группе того же кода, что и заданная комбинация G(X)] на образующий многочлен Р(Х);

2) умножением заданной кодовой комбинации G(X) на одночлен , имеющий ту же степень, что и образующий многочлен Р(Х), с добавлением к этому произведению остатка R(X), полученного после деления произведения на образующий многочлен Р(Х).

Пример 1.1. Требуется закодировать одну из комбинаций двоичного кода 1101, что соответствует .

Не останавливаясь на выборе образующего многочлена Р(Х), о чем будет сказано далее, возьмем из табл. 1.1 многочлен Р(Х3)=Х3+Х+1→11→1011.

Умножая G(X) на , который имеет третью степень, получим

.

От умножения степень каждого многочлена повысилась, что эквивалентно приписыванию трех нулей к многочлену, выраженному в двоичной форме.

Разделив произведение на образующий многочлен , согласно (1.1) получим

или в двоичном эквиваленте

Таким образом, в результате деления получаем частное Q(X) той же степени, что и G(X):

и остаток:

.

В итоге комбинация двоичного кода, закодированная циклическим кодом, согласно (1.2) примет вид

F(X)= 1111•1011 = 1101000 + 001 = 1101001.

Действительно, умножение 1111•1011 (первый способ) дает тот же результат, что и сложение 1101000 + 001 (второй способ).

Циклические коды, обнаруживающие одиночную ошибку (d=2). Код, образованный многочленом Р(Х)=Х+1, обнаруживает не только одиночную ошибку, но и любое нечетное число ошибок.

Предположим, что необходимо закодировать сообщение G(Х)=Х3+ +Х2+X+1→1101 с помощью образующего многочлена P(Х)=Х+1→11.

Умножим G(X) на Хm, что эквивалентно добавлению нуля справа, так как m=1, поскольку Р(Х) имеет первую степень: (Х3+Х2+1)X= Х4+Х3+X→11010.

Разделив полученное выражение на Р(Х), найдем, что остаток R(X)=1. Следовательно, кодовый многочлен циклического кода в соответствии с уравнением (1.2) будет иметь вид

F(X)= G(X)Хm + R(X)= Х4 + Х3 +X + 1→ 11010 + 1 = 11011.

Таким образом, в этом закодированном сообщении 11011 n = 5, k=4 и m=1, то есть информационным символом является комбинация 1101, а контрольным — единица в младшем разряде.

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

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

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

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

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

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

нирован

ная матрица

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

5. 000009. 13.

6. 10. 14.

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