Тема 8. Циклические коды
Циклическим кодом называется код, в котором кодовая комбинация, полученная путем циклического сдвига кодовой комбинации, является также разрешенной кодовой комбинацией. Такой код называется также полиномиальным или кодом с циклическими, избыточными проверками (ЦИП). Циклический сдвиг осуществляется справа налево, при этом крайний левый символ переносится в конец комбинации. Циклический код является: линейным, блочным, корректирующим, равномерным, систематическим. Каждый блок кодируется самостоятельно.
В циклических кодах кодовые комбинации представляются в виде полиномов (многочленов), что позволяет свести действия над кодовыми комбинациями к действиям над многочленами (используя аппарат полиномиальной алгебры).
8.1. Операции над циклическими кодами
При описании
циклических кодов
- разрядные кодовые комбинации
представляются в виде полиномов фиктивной
переменной
.
Показатели степени у
соответствуют номерам разрядов (начиная
с нулевого), а коэффициенты при
будут
двоичные числа 0 и 1.Например, кодовая
комбинация 01011 запишется в виде:
Наибольшую степень в слагаемом с ненулевым коэффициентом называют степенью полинома. Действия над кодовыми комбинациями сводятся к операциям над многочленами.
Сдвиг справа налево (циклический сдвиг) осуществляется путем умножения полинома на множитель x:
G(x) = x4 +x2+1 => 0010101;
G(x)x = x5+x3+x => 0101010.
2. Операции сложения и вычитания выполняются по модулю 2 и являются эквивалентными (1 1 = 0 и 1 = -1) и ассоциативными:
G1(x)+G2(x)=>G3(x); G1(x) –G2(x)=>G3(x); G2(x)+G1(x)=>G3(x).
Можно
при сложении двоичных чисел переносить
слагаемые из одной части в другую без
изменения знака. Поэтому равенство
можно записать как
,
и как
,
т.е. а и
имеют
одинаковую четность. Если:
G1(x) = x5 +x3+x;
G2(x) = x4 +x3 +1 то G3(x) = x5 +x4+x+1.
3. Операция деления является обычным делением многочленов, только вместо вычитания используется сложение по модулю 2:
G1(x) = x6+x4+x3;
G2(x) = x3+x2+1.
Результатом деления многочленов является частное Q(x) и остаток R(x).
.
Например:
x6+x4+x3
x3+x2+1
1011000 1101 1100
x6+x5+x3
x3 +x2
1101
1100
1101
x5 + x4 1100 1100
x5
+ x4 +x2
1101
11000
x2 100 1100
1011100
100
1011000
При этом: Q(x)= x3 +x2 = 1100; R(x) = x2 = 100.
Все операции над циклическими кодами легко реализуются аппаратно на регистрах сдвига с обратными связям.