Циклические коды

Название кодов произошло от их свойства, заключающегося в том, что каждая кодовая комбинация может быть получена путем циклической перестановки символов комбинации, принадлежащей этому же коду. Это значит, что если, например, комбинация а0 аг а2 ... а„_! является разрешенной, то комбинация ап_а а0а1а2 ... ап_2 также является разрешенной. Циклические коды обычно имеют полиномиальное представление, означающее, что бинарные элементы кодового слова а„_а ап_2 ... а2 СЦ а0 интерпретируются как коэффициенты полинома от некоторой фиктивной переменной х: ап_1хп~1 + ап_2хп'2 + ... + а2Х2 + a^x + а0.

Например, кодовое слово 11010 представляется в виде полинома х4 + х3 + х.

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

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

Циклический сдвиг коэффициентов полинома степени п - 1 можно выполнить, умножая полином на х с одновременным сложением с двучленом хп + 1. Действительно, пусть /(х) = 1-х"-1 + а„_2х"-2 +...+а2х21х + а0. Коэффициенты полинома Дх) запишем в виде кортежа {1,сЦ-2>--->а2>а1>ао}' .

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

Кортеж коэффициентов нового полинома выглядит так: п_2,...,а210,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).
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >