logo
ТИКЛекции

Так как частное q(X) имеет такую же степень, как и кодовая комбинация g(X) , то q(X) является кодовой комбинацией того же k - значного кода.

С учетом эквивалентности операций сложения и вычитания по модулю 2,

можно записать

6. Формирование передаваемой кодовой комбинации циклического кода (кодового полинома) - F(x):

7. Передача кодовой комбинации циклического кода в канал.

8. Анализ принятого сообщения F1(x).

Принятое сообщение:

F1(x) = F(x) E(x),

где E(x) - код ошибки.

Многочлен F1(x) делится на образующий полином P(x). Если деление производится без остатка, то ошибок нет, в противном случае номер искаженного байта определяется путем анализа остатка. Без остатка делятся на образующий многочлен только те многочлены, которые принадлежат данному коду, т. е. образующий полином позволяет выбрать из множества кодовых комбинаций, только разрешенные. В циклических кодах остатки от деления многочленов являются опознавателями ошибок.

Пример 1. Закодировать сообщение G(x) = 1001 циклическим кодом, обеспечивающим обнаружение двукратных и исправление однократных ошибок. Показать процесс исправления ошибки в принятой комбинации.

Решение:

1. По заданому k = 4, для S = 1 определим длину кодовой комбинации -n и количество контрольных разрядов -m кода по формуле:

m = [log2 {(k+1)+ [log2(k+1)]}] = [log2 {(4+1)+ [log2(4+1)]}] = 3.

При этом n = k + m = 7, т. е. получим (7, 4) -код.

2. Строим информационный полином соответствующий информационному слову длиной k- бит

G(x) = x3+1=1001.

3. Осуществляем сдвиг кода влево на m = n - k = 3 разрядов, т. е. полином G(x) умножается на xm

G(x) xm = ( x3+1)x3 = x6+ x3 =1001000.

  1. Выбирается образующий полином -P(x) по таблице неприводимых многочленов. Для исправления одиночной ошибки (d0 = 3) образующий полином должен быть степени m = n - k = 3, количеством ненулевых членов не менее d0 = 3 и входящих в разложение двучлена

x7 +1 = (x+1)(x3+ x2+1)(x3+ x+1).

Выбираем образующий полином P(x) = x3 +x +1.

5. Определим остаток R(x) от деления G(x)x m на образующий полином P(x)

x6+x3 x3+x+1 1001000 1011

x6+x4+x3 x3+x 1011 1010

x4 1000

 x4+x2 +x  1011

x2 +x 110

Остаток R(x) = x2 +x = 110.

6. Строим передаваемый кодовый полином F(x)

F(x) = xm G(x) R(x) = x6+x3 +x2+x = 1 0 0 1 1 1 0.

7. Рассмотрим процедуру декодирования, обнаружения и исправления ошибки в принятой кодовой комбинации.

Предположим, ошибка произошла в четвертом разряде кодовой комбинации, при этом принятое сообщение имеет вид:

F1(x) = F(x)+E(x) = 1 0 0 0 1 1 0.

Разделим многочлен F1(x), соответствующий полученной кодовой комбинации на образующий полином, при этом вес остатка (количество единиц в коде остатка) должен быть меньше или равен количеству исправляемых ошибок W S .

F 1(x) = 1000110 1011

 1011 1011

01111

 1011

1000

 1011

011 -> остаток W S.

Производим циклический сдвиг и повторяем деление, эту процедуру повторяем до тех пор, пока не выполнится условие W S.

1) 0001101 1011 2) 0011010 1011 3) 0110100 1011 4)1101000 1011

 1011  1011  1011  1011

110 1100 1100 1100

 1011  1011  1011

W S 111 1110 1110

 1011  1011

W S 101 001

W S W = S

Суммируем остаток с последним делимым

1101000

 001

1101001

Осуществляем обратный циклический сдвиг на 4 разряда полученной комбинации 1101001

1- 1110100

2- 0111010

3- 0011101

4- 1001110

Отбросив контрольные разряды, получаем переданное информационное слово.

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

Решение: Для передачи 4-х разрядного информационного слова с исправлением одиночной ошибки необходимо использовать (7,4) –код. При этом можно выбрать образующий полином P(x) = x3 +x +1=1011. Умножая образующий многочлен на многочлен полного 4-х разрядного кода, получим следующие кодовые комбинации:

1) 1011 2) 1011 3) 1011 4) 1011 5) 1011

0001 0010 0011 0100 0101

0001011 0010110 1011 0101100 1011

1011 1011

0011101 0100111

6) 1011 7) 1011 8) 1011 9) 1011 10) 1011

0110 0111 1000 1001 1010

10110 1011 1011000 1011 10110

1011 1011 1011 1011

0111010 1011 1010011 1001110

0110001

11) 1011 12) 1011 13) 1011 14) 1011 15) 1011

1011 1100 1101 1110 1111

1011 101100 1011 10110 1011

1011 1011 10110 1011 1011

1011 1110100 1011 1011 1011

1000101 1111111 1100010 1011

1101001