| Подпространство V наборов длины п называется циклическим подпространством или циклическим кодом, если для любого вектора v = (an-i, ап-2, а0)
из подпространства V вектор v' = = (do, an-i, an-2, Ci)
, получаемый в результате циклического сдвига компонент вектора v на единицу вправо, также принадлежит подпространству V.
В этой главе наборы длины п будут рассматриваться как элементы алгебры многочленов по модулю Хп — 1, которую обозначим через Ап. Элементами алгебры являются классы вычетов многочленов, которые здесь обозначаются через {f{X)}. Там, где не делается специальной оговорки, будет предполагаться, что в качестве f(X) всегда выбирается многочлен наименьшей степени в классе вычетов. Тогда степень f(X) всегда меньше п, и все раз-Личные многочлены степеней, меньших п, принадлежат различным классам вычетов, т. е. имеется взаимно однозначное соответствие между многочленами степеней, меньших п, и классами вычетов. Если задан многочлен а(Х), степень которого больше п, то многочлен наименьшей степени в том же самом классе вычетов находится делением многочлена а.(Х) на многочлен Хп— 1. Остаток от деления и будет интересующим нас многочленом.
Каждому набору (ап-и ап-2, а0) длины п соответствует многочлен f(X) = аn + ... + а0 степени, меньшей п; соответствующим классом вычетов является класс {ап~\Хп~1 ~Ь ап-2Хп~2 + ... + flo}- Этот класс вычетов и соответствующий вектор из п компонент будем рассматривать просто как различные способы представления одного и того же математического объекта — элемента алгебры Ап многочленов по модулю Хn— 1.
Алгебраическое описание циклического кода дается следующей теоремой:
Теорема 8.1. В алгебре многочленов по модулю Хп—1 подпространство является циклическим подпространством тогда и только тогда, когда оно является идеалом.
Доказательство. Ключевым моментом в доказательстве этой теоремы является то, что умножение на {X} эквивалентно циклическому сдвигу вектора.
Если подпространство V — идеал и элемент v принадлежит V, то произведение {X}v также принадлежит V, и поскольку {Х}\ — циклический сдвиг вектора v, то V—циклическое подпространство.
Предположим теперь, что V — циклическое подпространство. Тогда для любого вектора v, принадлежащего V, произведение {Х}\ принадлежит V, и, следовательно, для любого /' произведение {X}i\ = [Хз}\ также принадлежит V. Поскольку V—подпространство, то любая линейная комбинация.
будет принадлежать V. Таким образом, произведение любого элемента из V на любой элемент алгебры Ап принадлежит V; итак, подпространство V должно быть идеалом и т. д. Если вы очень сильно заняты работой и нет времени на квартиру, тогда закажите тут - http://remontctroi.ru/ недорого.
Структура идеала алгебры Ап описана в разд. 6.4. Это описание в основном сводится к следующему. Пусть g(X)—нормированный многочлен наименьшей степени, такой, что класс вычетов ig{X)} принадлежит идеалу /. Если f(X)—многочлен степени,меньшей чем п, который делится на g(X), то класс вычетов {f(X)} принадлежит /, и, наоборот, если (f(X)} принадлежит идеалу /, то Многочлен f(X) делится на многочлен g(X). Кроме того, многочлен
Xn—1 делится на g(X), и любой нормированный многочлен, на который делится Хп—1, порождает свой идеал / в алгебре Ап. Многочлен g(X) называется многочленом, порождающим идеал. |
Главная
Каталог файлов
