Отсюда ясно, что любая разрешенная кодовая комбинация циклического кода может быть получена в результате умножения образующего многочлена на некоторый другой многочлен с приведением результата по модулю xn + l. Иными словами, при соответствующем выборе образующего многочлена любой многочлен циклического кода будет делиться на него без остатка.
Ни один многочлен, соответствующий запрещенной кодовой комбинации, на образующий многочлен без остатка не делится. Это свойство позволяет обнаружить ошибку. По виду остатка можно определить и вектор ошибки.
Умножение и деление многочленов весьма просто осуществляется на регистрах сдвига с обратными связями, что и явилось причиной широкого применения циклических кодов.
Так как каждая разрешенная комбинация n-разрядного циклического кода есть произведение двух многочленов, один из которых является образующим, то эти комбинации можно рассматривать как подмножества всех произведений многочленов степени не выше n-1. Это наталкивает на мысль использовать для построения этих кодов еще одну ветвь теории алгебраических систем, а именно теорию колец.
Как следует из приведенного ранее определения, для образования кольца на множестве n-разрядных кодовых комбинаций необходимо задать две операции: сложение и умножение.
Операция сложения многочленов уже выбрана нами с приведением коэффициентов по модулю два.
Определим теперь операцию умножения. Нетрудно видеть, что операция умножения многочленов по обычным правилам с приведением подобных членов по модулю два может привести к нарушению условия замкнутости. Действительно, в результате умножения могут быть получены многочлены более высокой степени, чем n-1, вплоть до 2(n-1), а соответствующие им кодовые комбинации будут иметь число разрядов, превышающее n и, следовательно, не относятся к рассматриваемому множеству. Поэтому операция символического умножения задается так:
1) многочлены перемножаются по обычным правилам, но с приведением подобных членов по модулю два;
2) если старшая степень произведения не превышает n-1, то оно и является результатом символического умножения;
3) если старшая степень произведения больше или равна n, то многочлен произведения делится на заранее определенный многочлен степени nи результатом символического умножения считается остаток от деления.
Степень остатка не превышает n-1, и, следовательно, этот многочлен принадлежит к рассматриваемому множеству k-разрядных кодовых комбинаций.
При анализе циклического сдвига с перенесением единицы в конец кодовой комбинации установлено, что таким многочленом n-й степени является многочлен хn+ 1.
Действительно, в результате умножения многочлена степени n-1 на х получим
G(x) = (xn-1 + xn-2 + … + x + 1)x = xn + xn-1 + … + x
Следовательно, чтобы результат умножения и теперь соответствовал кодовой комбинации, образующейся путем циклического сдвига исходной кодовой комбинации, в нем необходимо заменить хnна 1. Такая замена эквивалентна делению полученного при умножении многочлена на xn+ 1 с записью в качестве результата остатка от деления, что обычно называют взятием остатка или приведением по модулю xn+ 1 (сам остаток при этом называют вычетом).
Выделим теперь в нашем кольце подмножество всех многочленов, кратных некоторому многочлену g(x). Такое подмножество называют идеалом, а многочлен g(x)-порождающим многочленом идеала.
Количество различных элементов в идеале определяется видом его порождающего многочлена. Если на порождающий многочлен взять 0, то весь идеал будет составлять только этот многочлен, так как умножение его на любой другой многочлен дает 0.
Если за порождающий многочлен принять 1[g(x) = 1], то в идеал войдут все многочлены кольца. В общем случае число элементов идеала, порожденного простым многочленом степени n-k, составляет 2k.
Теперь становится понятным, что циклический двоичный код в построенном нами кольце n-разрядных двоичных кодовых комбинаций является идеалом. Остается выяснить, как выбрать многочлен g(x), способный породить циклический код с заданными свойствами.
Согласно определению циклического кода все многочлены, соответствующие его кодовым комбинациям, должны делиться на g(x) без остатка. Для этого достаточно, чтобы на g(x) делились без остатка многочлены, составляющие образующую матрицу кода. Последние получаются циклическим сдвигом, что соответствует последовательному умножению g(x) на х с приведением по модулю xn + 1.
Следовательно, в общем случае многочлен gi(x) является остатком от деления произведения g(x)·хiна многочлен xn + 1и может быть записан так:
gi(x)=g(x)xi + c(xn + 1)
где с =1, если степень g(x) хiпревышает п-1; с = 0, если степень g(x) хiне превышает п-1.
Отсюда следует, что все многочлены матрицы, а поэтому и все многочлены кода будут делиться на g(x) без остатка только в том случае, если на g(x) будет делиться без остатка многочлен xn + 1.
Таким образом, чтобы g(x) мог породить идеал, а, следовательно, и циклический код, он должен быть делителем многочлена xn + 1.
Поскольку для кольца справедливы все свойства группы, а для идеала - все свойства подгруппы, кольцо можно разложить на смежные классы, называемые в этом случае классами вычетов по идеалу.
Первую строку разложения образует идеал, причем нулевой элемент располагается крайним слева. В качестве образующего первого класса вычетов можно выбрать любой многочлен, не принадлежащий идеалу. Остальные элементы данного класса вычетов образуются путем суммирования образующего многочлена с каждым многочленом идеала.
Если многочлен g(x) степени m = n-kявляется делителем xn + 1, то любой элемент кольца либо делится на g(x) без остатка (тогда он является элементом идеала), либо в результате деления появляется остаток r(х), представляющий собой многочлен степени не выше m-1.
Элементы кольца, дающие в остатке один и тот же многочлен ri(x), относятся к одному классу вычетов. Приняв многочлены r(х) за образующие элементы классов вычетов, разложение кольца по идеалу с образующим многочленом g(x) степени mможно представить табл. 4.12, где f(x)-произвольный многочлен степени не выше n-m-1.
Таблица 4.12.
| 0 | g(x) | x·g(x) | (x+1)·g(x) | … | f(x)·g(x) |
| r1(x)r2(x)……rn(x) | g(x) + r1(x)g(x) + r2(x)……g(x) + rn(x) | x·g(x) + r1(x)x·g(x) + r2(x)……x·g(x) + rn(x) | (x+1)·g(x) + r1(x)(x+1)·g(x) + r2(x)……(x+1)·g(x) + rn(x) | …………… | f(x)·g(x) + r1(x)f(x)·g(x) + r2(x)……f(x)·g(x) + rn(x) |
Как отмечалось, групповой код способен исправить столько разновидностей ошибок, сколько различных классов насчитывается в приведенном разложении. Следовательно, корректирующая способность циклического кода будет тем выше, чем больше остатков может быть образовано при делении многочлена, соответствующего искаженной кодовой комбинации, на образующий многочлен кода.
Наибольшее число остатков, равное 2m- 1 (исключая нулевой), может обеспечить только неприводимый (простой) многочлен, который делится сам на себя и не делится ни на какой другой многочлен (кроме 1).
4.10 Выбор образующего многочлена по заданному объему кода и заданной корректирующей способности
По заданному объему кода однозначно определяется число информационных разрядов k. Далее необходимо найти наименьшее n, обеспечивающее обнаружение или исправление ошибок заданной кратности. В случае циклического кода эта проблема сводится к нахождению нужного многочлена g(x).
Начнем рассмотрение с простейшего циклического кода, обнаруживающего все одиночные ошибки.
Любая принятая по каналу связи кодовая комбинация h(x), возможно содержащая ошибку, может быть представлена в виде суммы по модулю два неискаженной комбинации кода f(x) и вектора ошибки ξ(x):
h(x) = f(x) Å ξ(x)
При делении h(x) на образующий многочлен g(x) остаток, указывающий на наличие ошибки, обнаруживается только в том случае, если многочлен, соответствующий вектору ошибки, не делится на g(x): f(x)-неискаженная комбинация кода и, следовательно, на g(x) делится без остатка.
Вектор одиночной ошибки имеет единицу в искаженном разряде и нули во всех остальных разрядах. Ему соответствует многочлен ξ(x) = xi. Последний не должен делиться на g(x). Среди неприводимых многочленов, входящих в разложении хn+1, многочленом наименьшей степени, удовлетворяющим указанному условию, является x + 1. Остаток от деления любого многочлена на x + 1 представляет собой многочлен нулевой степени и может принимать только два значения: 0 или 1. Все кольцо в данном случае состоит из идеала, содержащего многочлены с четным числом членов, и одного класса вычетов, соответствующего единственному остатку, равному 1. Таким образом, при любом числе информационных разрядов необходим только один проверочный разряд. Значение символа этого разряда как раз и обеспечивает четность числа единиц в любой разрешенной кодовой комбинации, а, следовательно, и делимость ее на xn + 1.