Среди систематических кодов особое место занимают циклические, у которых строки образующих матриц могут быть получены циклическим сдвигом одной комбинации, называемой образующей для данного кода. Сдвиг осуществляется справа налево, причем крайний левый символ каждый раз переносится в конец комбинации. Например, совокупность кодовых комбинаций, получающихся циклическим сдвигом одной шестиразрядной комбинации 010001, имеет вид: 010001, 100010, 000101, 001010, 010100, 101000. Как видно из этого примера, число возможных циклических кодов (n, k) значительно меньше числа различных групповых (n, k) кодов.
При описании циклических кодов удобно использовать запись любого n-разрядного двоичного числа в виде многочлена (n – 1) – й степени, содержащего фиктивную переменную х с показателем степени (n – 1) и коэффициентами при x (0 или 1 для двоичного кода). Например, двоичная кодовая комбинация 10101 может быть записана в виде многочлена G(x) = 1 • х4 + 0 • х3 + 1 • х2 + 0 • х1 + 1 • х0=
=1 • х4 + 1 • х2 + 1 • х0. Многочлен в таком виде называется нормированным, поскольку коэффициент при старшей степени равен единице. Таким образом, действия над кодовыми комбинациями сводятся к действиям над многочленами.
Вышеупомянутый циклический сдвиг некоторого образующего многочлена степени (n – 1) соответствует простому умножению на х. Умножив, например, многочлен (х3 + х2 + 1), соответствующий комбинации 0001101, на х, получим многочлен (х4 + х3 + х), соответствующий комбинации 0011010. Нетрудно убедиться, что кодовая комбинация, получающаяся сложением этих двух комбинаций, также будет соответствовать результату умножения многочлена (х3 + х2 + 1) на многочлен (х + 1), если приведение подобных членов осуществлять по модулю 2. Действительно, (х3 + х2 + 0 + 1) • (х + 1) = (х3 + х2 + 0 + 1) Å (х4 + х3 + 0 + х) = (х4 + 0 + х3 + 0 + х) и 0001101 Å 011010 = 0010111. Из приведенного примера видно, что при соответствующем выборе образующего многочлена любая разрешенная кодовая комбинация циклического кода может быть получена в результате умножения образующего многочлена на некоторый другой многочлен. Это значит, что любой многочлен циклического кода делится на образующий многочлен без остатка. При этом не один многочлен, соответствующий запрещенной кодовой комбинации, на образующий многочлен без остатка не делится. Это свойство позволяет обнаружить ошибку, а по виду остатка определить и вектор (код) ошибки. Поскольку умножение, и деление многочленов весьма просто осуществляется на регистрах сдвига с обратными связями, то это обстоятельство явилось причиной широкого применения циклических кодов.
Поскольку каждая разрешенная комбинация n-разрядного циклического кода является произведением двух многочленов, один из которых является образующим, то эти комбинации можно рассматривать как подмножество множества всех произведений многочленов степени не выше n – 1.
Следует заметить, что операция умножения многочленов по обычным арифметическим правилам с приведением подобных членов по модулю 2 может привести к нарушению условия замкнутости. Действительно, в результате умножения могут быть получены многочлены более высокой степени, чем (n - 1), вплоть до 2(n – 1), а соответствующие им кодовые комбинации будут иметь число разрядов, превышающее п, и, следовательно, не будут относиться к рассматриваемому множеству. Поэтому операция символического умножения выполняется в следующем порядке:
1. Многочлены перемножаются по обычным правилам, но с приведением подобных членов по модулю 2.
2. Если старшая степень произведения не превышает (n - 1), то оно является результатом символического умножения.
3. Если старшая степень произведения больше или равна n, то многочлен произведения делится на заранее определенный многочлен степени n и результатом символического умножения считается остаток отделения.
Степень остатка не будет превышать (n – 1), и следовательно, этот многочлен будет принадлежать к рассматриваемому множеству n-разрядных кодовых комбинаций. Для того чтобы найти вид этого многочлена (n-й степени), остаток в виде многочлена степени (n - 1) умножается на х. Чтобы результат умножения и теперь соответствовал кодовой комбинации, образующейся путем циклического сдвига исходной кодовой комбинации, в нем необходимо заменить х на 1. Такая замена эквивалентна делению полученного при умножении многочлена на (хn + 1) с записью в качестве результата остатка от деления, что обычно называется взятием остатка или приведением по модулю (хn + 1) (сам остаток в этом случае называется вычетом). Искомым многочленом n-й степени является, следовательно, многочлен (хn + 1).
Итак, при заданных операциях сложения и умножения все множество многочленов степени не выше (n - 1), соответствующее множеству n-разрядных кодовых комбинаций, образует кольцо. Подмножество всех многочленов, кратных некоторому многочлену наименьшей степени g(x), называется идеалом, а многочлен g(x) – порождающим многочленом идеала. При этом количество различных элементов в идеале определяется видом его порождающего многочлена. Если за порождающий многочлен взять 0, то весь идеал будет составлять только этот многочлен, так как умножение его на любой другой многочлен дает 0. Если за порождающий многочлен принять 1 (g(x) = 1), то в идеал войдут все многочлены кольца. В общем случае число элементов идеала, порожденного простым многочленом степени (n - k), составляет 2k.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
