2.2 Матричное представление циклических кодов

Комбинации циклического кода можно записать в виде производящей матрицы, содержащей k строк и n столбцов.

Для формирования строк производящей матрицы по первому способу образования кода берут те комбинации Q(x), которые содержат единицу в одном разряде – Q_i(x).

Затем находят остатки:

Q

R_i(x) =

_i(x)  x^r

P(x)

Соответствующая строка матрицы записывается в виде: Q(x)  x^r + R_i(x).

Матрица при этом разбивается на две подматрицы: G_n,k = | E_k^T, C_r,k|.

Производящая матрица дает возможность получить первые k комбинаций кода. Остальные 2^k–k–1 комбинации получаются суммированием по модулю 2 строк производящей матрицы во всех возможных сочетаниях.

Пример 4:

Р(х) = х3 + х + 1; Р(1,0) = 1011; n = 7; k = 4.

Тогда:

Q_i(x) : Q₁ = 0001; Q₂ = 0010; Q₃ = 0100; Q₄ = 1000.

Q

= ;

₁(x)  x^r 0001  1000

P(x) 1011

Разделив, получим R₁(x)  011.

Первая строка матрицы – 0001011.

П роделав эту операцию 4 раза, получим:

0001 | 011

0

G_7,4 =

010 | 110

0100 | 111

1000 | 101

E_k^T C_k,r

2.3 Выбор образующего полинома

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

Образующий полином Р(х) степени r должен входить в качестве сомножителя в разложение двучлена

xⁿ + 1 = x^2m-1 + 1 (51)

Доказано, что для любых целых положительных m и t_и существует циклический код значности

n = 2^m – 1 (52)

с кодовым расстоянием

d_min  2t_и + 1 (53)

При этом число проверочных символов r = n-k не превышает величины m  t_и, т.е. r  m  t_и. Такой код исправляет ошибки кратности t_и и менее и обнаруживает ошибки кратности 2t_и и менее. Кроме того, код обнаруживает все пакеты ошибок, длина которых равна или меньше r. Соотношения (52) – (54) можно использовать для выбора Р(х). Из таблиц неприводимых полиномов нужной степени в качестве образующего выбирают тот, который дает наибольшее число остатков. При степени многочлена m= n-k он может дать 2^n-k – 1 ненулевых остатков (нулевой остаток характеризует безошибочную передачу).

В общем случае при построении циклического (n,k) кода с исправлением в кодовой комбинации t_и ошибок в качестве образующего полинома степени r выбирается произведение из t_и сомножителей старших степеней, входящих в разложение двучлена вида x^2m-1 + 1.

2.4 Обнаружение и исправление ошибок

Для обнаружения и исправления ошибочного разряда производят следующие операции.

1 Принятую комбинацию делят на образующий полином.

2 Подсчитывают количество единиц в остатке (вес  остатка). Если t_и, принятую комбинацию складывают по модулю 2 с полученным остатком. Сумма дает исправленную комбинацию. Если t_и, то

3 Производят циклический сдвиг влево на один разряд. Комбинацию, полученную после сдвига, делят на Р(х). Если в результате повторного деления t_и, делимое суммируют с остатком, затем

4 Производят циклический сдвиг вправо на один разряд комбинации, полученной в результате суммирования последнего делимого с последним остатком. Полученная комбинация уже не содержит ошибок. Если после первого циклического сдвига и последующего деления вес остатка t_и, то

5 Повторяют операцию п.3 до тех пор, пока не будет достигнуто t_и. В этом случае комбинацию, полученную в результате последнего циклического сдвига, суммируют с остатком от деления этой комбинации на образующий многочлен, а затем

6 Производят циклический сдвиг вправо на столько разрядов, на сколько сдвинута суммируемая с последним остатком комбинация относительно принятой комбинации. В результате получается исправленная комбинация.

Пример 5:

При передаче комбинации 1001110 циклического кода, исправляющего одиночные ошибки (t_и = 1), полученного с помощью образующего полинома Р(х) = х³ + х + 1, произошла ошибка в четвертом разряде. Принятая комбинация имеет вид 1000110. Процесс исправления ошибки следующий.

1. Делим принятую комбинацию на Р(х). Р(х) = 1011.

1 000110 1011

1 011

1111

1011

1000

1011

11

2. Вес остатка  = 2; >t_и.

3. Производим циклический сдвиг на один разряд влево и деление на Р(х).

0 001101 1011

1011

110

4. Повторяем п.3, пока t_и.

а ) 0011010 1011 б) 0110100 1011 в) 1101000 1011

1011 1011 1011

1100 1100 1100

1011 1011 1011

111 1110 1110

1011 1011

101 1010

1011

1

>t_и >t_и =t_и

6. Складываем по модулю 2 последнее делимое с остатком.

1



101000

1

1101001

7. Производим циклический сдвиг комбинации, полученной в результате суммирования последнего делимого с последним остатком вправо на 4 разряда:

1110100  0111010  0011101  1001110.

Последняя комбинация безошибочная.