Циклические коды. 
Теория информационных процессов и систем + доп. 
Материалы в эбс

Название кодов произошло от их свойства, заключающегося в том, что каждая кодовая комбинация может быть получена путем циклической перестановки символов комбинации, принадлежащей этому же коду. Это значит, что если, например, комбинация а₀ а_г а₂ … а"_! является разрешенной, то комбинация а_п__а а₀а₁а₂ … а_п_₂ также является разрешенной. Циклические коды обычно имеют полиномиальное представление, означающее, что бинарные элементы кодового слова а"__а а_п_₂ … а₂ СЦ а₀ интерпретируются как коэффициенты полинома от некоторой фиктивной переменной х: а_п_₁х^п~¹ + а_п_₂х^п'² + … + а2Х² + a^x + а₀.

Например, кодовое слово 11 010 представляется в виде полинома х⁴ + х³ + х.

Наибольшая степень х в слагаемом с ненулевым коэффициентом называется степенью полинома. Таким образом, в полиноме степени п — 1 старший коэффициент а_п__г равен 1.

Действия над кодовыми комбинациями сводятся к действиям над полиномами. Причем операция сложения производится по модулю 2. Множество таких полиномов и действий над ними образуют так называемое поле Галуа порядка 2 (обозначается GF ( 2)).

Циклический сдвиг коэффициентов полинома степени п — 1 можно выполнить, умножая полином на х с одновременным сложением с двучленом х^п + 1. Действительно, пусть /(х) = 1-х" ^-1 + а"_₂х" ^-2 +…+а₂х² +а₁х + а₀. Коэффициенты полинома Дх) запишем в виде кортежа {1,сЦ-2>—->^а2>^а1>^ао}' .

Выполним над полиномом операцию умножения на х и сложения с двучленом х" +1. Тогда.

Кортеж коэффициентов нового полинома выглядит так: {а_п_₂,…, а₂, а₁, а₀, 1}. Таким образом, мы убедились, что указанная операция эквивалентна циклическому сдвигу коэффициентов.

Следовательно, если в качестве исходного взять некоторый полином g (x), то процесс получения разрешенных кодовых комбинаций можно представить в следующем виде:

При таком способе построения полином g (x) называется порождающим (иногда используют термин производящий полином). Если потребовать, чтобы порождающий полином g (x) был делителем двучлена (х" + 1), то все разрешенные комбинации приобретают свойство делимости Hag (x). Из этого следует, что можно легко проверить, является ли комбинация разрешенной, для этого достаточно проверить ее делимость на полином g (x).

Основные свойства циклических кодов.

• 1. В циклическом (п, /с)-коде каждый кодовый полином должен иметь степень не более п — 1.
• 2. Для каждого циклического кода существует собственный единственный полином g (x) степени (п — к) вида

называемый порождающим полиномом кода.

• 3. Каждый разрешенный кодовый полином ц (х) является кратным g (x), т. е. и (х) = q (x) • g (x).
• 4. Порождающий полином g (x) является делителем двучлена (х^,! + 1).