Конструктивное определение циклического ( n , k ) – кода

 

Циклическим (n, k) – кодом называется множество многочленов степени не больше (n ‑1), каждый из которых нацело делится на (специально подобранный) порождающий многочлен G (x) степени (n - k), являющийся делителем бинома xⁿ +1.

Циклический код со словами длины n и с порождающим многочленом G (x) существует тогда и только тогда, когда G (x) делит xⁿ+1 [1]. В лекционном курсе было показано, что это требование делимости бинома xⁿ+1 на G (x) вытекает из специфики определения операции символического умножения многочленов (по модулю бинома xⁿ+1). Для того, чтобы максимизировать множество слов порождаемого кода при фиксированных значениях длины слов n и кодового расстояния d₀, многочлен G (x) должен быть неприводимым делителем степени (n-k).

 

Алгоритм кодирования

 

На практике чаще всего применяется алгоритм кодирования, который формирует систематический разделимый код. В основу такого алгоритма положена операция деления на G (x). Систематические разделимые коды привлекательны тем, что процедуру кодирования, т.е. преобразования информационного вектора A (длины k) в вектор кода V (длины n>k) удается свести лишь к формированию (n-k) контрольных бит.

Шаг 1.   Предварительно вектор A «отнормируем по формату» под длину n, воспользовавшись операцией умножения многочленов A (x) × x^n-k. Как было показано в лекционном курсе – это эквивалентно сдвигу вектора A на (n-k) позиций влево. Произведение многочленов на языке векторов имеет длину n. Существенно для последующего, что правые (n-k) позиций оказываются непременно нулевыми.

Шаг 2.   Произведение A (x) × x^{n - k} разделим на G (x). Ясно, что в общем случае оно не обязано делиться на G (x) нацело. Поэтому следует записать

A (x) × x^n-k= Q (x) × G (x)+ R (x),

 

где Q (x) - частное от деления;

R (x) - остаток. Это многочлен степени не больше (n - k ‑1), т. к. делитель имеет степень (n - k) по определению. Как вектор он имеет длину (n - k).

Шаг 3.   Перенесём остаток R (x) в левую часть равенства. Получим:

A (x) × x^n-k+ R (x)= Q (x) × G (x).

 

Теперь в левой части мы получаем многочлен, который нацело делится на G (x), а это по определению – многочлен, принадлежащий циклическому (n, k) – коду. В этой последней операции остаток R складывается с нулями (см. шаг1 алгоритма). Следовательно, конечный итог эквивалентен конкатенированию R к вектору А.

 

Алгоритм декодирования

 

Известно несколько алгоритмов декодирования циклических (n, k) – кодов. В данной лабораторной работе исследуется «декодирование по синдрому», роль которого (синдрома) играет остаток от деления декодируемого многочлена F (x) на G (x). Декодирование может производиться с целью только обнаруживать ошибки или с целью исправлять ошибки кратности до t включительно. В любом случае цель достигается в несколько шагов алгоритма.

 

Декодирование с обнаружением ошибок

Шаг 1.   Вычисление остатка R (x);

Шаг 2.   Анализ остатка «на ноль». Нулевой остаток означает, что ошибки не обнаружены;

 

Декодирование с исправлением ошибок

Шаг 1.   Вычисление остатка R (x);

Шаг 2.   Вычисление по найденному остатку предполагаемого (наиболее вероятного) многочлена ошибки Е (х);

Шаг 3.   Исправление декодируемого вектора F путем суммирования F + E = V;

Параметры исследуемых кодов

 

Чтобы трудоемкость лабораторных работ согласовать с отпущенным временем, исследуются короткие (по меркам практики) коды. Параметры кодов приведены в таблицах 1 – 3.

Согласуйте с преподавателем номер варианта, с которым Вы будете работать. Программы CODER и DECODER следует писать для одного варианта кода.

 

Таблица №1. Варианты заданий для (n, k) – кодов с длиной слова n=15

Вари-анты	Параметры n, k	Расстояние кода d0	Порождающий многочлен G (x)	G (x) в двоичном и HEX‑форматах
1	2	3	4	5
1.1	(15,11)	3	G 1(x)=x^4+x+1	1 0011«13h
1.2	(15,7)	5	G 2(x)=x^8+x^7+x^6+x^4+1	1 1101 0001«1D1h
1.3	(15,5)	7	G 3(x)=x^10+x^8+x^5+x^4+x^2+x+1	101 0011 0111«537h

 

Таблица №2. Варианты заданий для (n, k) – кодов с длиной слова n=31

Вари-анты	Параметры n, k	Расстояние кода d0	Порождающий многочлен G (x)	G(x) в двоичном и HEX‑форматах
1	2	3	4	5
2.1	(31,26)	3	G 1(x)=x^5+x^2+1	10 0101«25h
2.2			G 2(x)=x^5+x^4+x^2+x+1	11 0111«37h
2.3			G 3(x)=x^5+x^4+x^3+x+1	11 1011«3Bh
2.4			G 4(x)=x^5+x^3+1	10 1001«29h
2.5	(31,21)	5	G 5(x)=x^10+x^9+x^8+x^6+x^5+x^3+1	111 0110 1001«769h
2.6			G 6(x)=x^10+x^7+x^5+x^4+x^2+x+1	100 1011 0111«4B7h
2.7	(31,16)	7	G 7(x)=x^15+x^11+x^10+x^9+x^8+x^7++x^5+ +x^3+x^2+x+1	1000 1111 1010 1111«8FAFh
2.8			G 8(x)=x^15+x^14+x^13+x^12+x^11+ +x^10+x^9+x^8+x^7+x^6+1	1111 1111 1100 0001«FFC1h

Таблица №3. Варианты заданий для (n, k) – кодов с длиной слова n=63

Вари-анты	Параметры n, k	Расстояние кода d0	Порождающий многочлен G (x)	G (x) в двоичном и HEX‑форматах
1	2	3	4	5
3.1	(63,57)	3	G1 (x)= x^6+x+1	100 0011«43h
3.2	(63,51)	5	G 2(x)=Ååх^i, i=12,10,8,5,4,3,0	1 0101 0011 1001«1539h
3.3	(63,45)	7	G 3(x)=Ååх^i, i=18,17,16,15,9,7,6,3,2,1,0	111 1000 0010 1100 1111««782СFh
3.4	(63,39)	9	G 4(x)=Ååх^i, i=24,23,22,20,19,17,16,13, 10,9,8,6,5,4,2,1,0	1 1101 1011 0010 0111 0111 0111««1DB2777h
3.5	(63,36)	11	G 5(x)=Ååх^i, i=27,22,21,19,18,17,15, 8,4,1,0	1 000 0110 1110 1000 0001 0001 0011«86Е8113h
3.6	(63,30)	13	G 6(x)=Ååх^i, i=33,32,30,29,28,27,26,23,22, 20,15,14,13,11,9,8,6,5,1,0	11 0111 1100 1101 0000 1110 1011 0110 0011««37СD0EB63h
3.7	(63,24)	15	G 7(x)=Ååх^i, i=39,38,37,36,34,33,31,28,27, 25,22,19,17,11,6,3,0	111 1011 0100 1101 0010 0101 0000 0100 0100 1001 ««7B4D250449h