Лабораторная работа № 4. Линейные циклические коды

Цель работы: Исследовать построение и возможности корректирования линейных систематических циклических кодов.

Методика выполнения задания :

ВНИМАНИЕ: Задания даны в Вариантах для групп А, Б и В

1.Выбор своего варианта в группе.

j₁ = (ФИО) соответствует позиции ошибочного символа и вычисляется как :

mod n (cумма количества букв)

где n- количество информационных символов в задании

j ₂= Порядковый номер по списку - соответствует варианту задания.

Лабораторная работа состоит из двух заданий.

Исходными данными являются:

для заданий № 1 – количество информационных разрядов (Вариант А);

- для задания №2– информационное слово, образующий полином.

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

ВАРИАНТ А

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

Пример решения для k = 7:

1. Определим количество проверочных разрядов. Для k = 7 и d₀ = S+1 = 3;

m = [log₂ {(k+1)+ [log₂(k+1)]}]=[log₂ {(7+1)+ [log₂(7+1)]}] = 4.

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

2. По таблице неприводимых многочленов выбираем образующий полином Р(х) = x⁴ +x³+1 = 1 1 0 0 1, т. е. степени большей или равной m и числом ненулевых членов больше или равно d₀.

3. Строим транспонированную единичную матрицу I_k^T

.

4. Определяем элементы дополнительной матрицы, как остатки от деления последней строки транспонированной матрицы на образующий полином. При этом число остатков должно быть не меньше k, число разрядов в остатке равно m, а число единиц в каждом остатке не менее d₀ -1. Если после приписывания 0 к остатку получаем число короче делителя, то получаем два остатка с нулем до и после остатка.

1000000 11001

11001

10010

11001

10110

11001

11110

11001

1010

Строим образующую матрицу G(n, k)

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

Пример решения для G(x) = 1001:

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

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

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

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

G(x) = x³+1=1001.

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

G(x) x^m = ( x³+1)x³ = x⁶+ x³ =1001000.

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

x⁷ +1 = (x+1)(x³+ x²+1)(x³+ x+1).

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

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

x⁶+x³ x³+x+1 1001000 1011

x⁶+x⁴+x³ x³+x 1011 1010

x⁴ 1000

 x⁴+x² +x  1011

x² +x 110

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

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

F(x) = x^m G(x) R(x) = x⁶+x³ +x²+x = 1 0 0 1 1 1 0.

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

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

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

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

F ¹(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- 001110

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