У. Питерсон - Коды, исправляющие ошибки (1267328), страница 48
Текст из файла (страница 48)
Это описание служит введением к изучению важных циклических кодов, представленных в последующих главах. 8.1. Циклические коды и идеалы Подпространство 1т наборов длины и называется циклическим подпространством или циклическим кодом, если для любого вектора ч = (а„ь а„м ..., аь) из подпространства р вектор т' = = (аь, а -ь а ь ..., а~), получаемый в результате циклического сдвига компонент вектора ч на единицу вправо, также принадлежит подпространству 1~. В этой главе наборы длины и будут рассматриваться как элементы алгебры многочленов по модулю Х" — 1, которую обозначим через А,, Элементами алгебры являются классы вычетов многочленои, которые здесь обозначаются через (1(Х)). Там, где не делается специалыюй оговорки, будет предполагаться, что в качестве )(Х) всегда выбирается многочлен наименьшей степени в классе вычетов.
Тогда степень 1(Х) всегда меньше и, и все различные многочлены степеней, меньших и, принадлежат различным классам вычетов, т. е. имеется взаимно однозначное соответствие между многочленами степеней, меньших п, и классами вычетов. Если задан многочлен а(Х), степень которого больше и, то много- член наименьшей степени в том же самом классе вычетов находится делением многочлена а,(Х) на многочлен Х" — 1. Остаток от деления н будет интересующим нас многочленом. Каждому набору (а„ь а„м ..., аь) длины и соответствует многочлен 1(Х)=а„~Х -'+а„зХ" з+ ...
+аз степени, мень- шей и; соответствующим классом вычетов является класс (а„,Х -'+ам яХп-а+ ... +аь). Этот класс вычетов н соответствуюшнй вектор из и компонент будем рассматривать просто как различные способы представления одного и того же математического объекта — элемента алгебры А„ многочленов по модулю Хь Алгебраическое описание циклического кода дается следующей теоремой: Теорема 8.1. В алгебре многочленов по модулю Х" — 1 надпространство является циклическим подпространством тогда и только тогда„когда оно является идеалом.
Доказательство. Ключевым моментом в доказательстве этой теоремы является то, что умножение на (Х) эквивалентно циклическому сдвигу вектора, так как Х (а„,Х" ' + а„,Х" '+ ° ° ° + ао) = =а,~ 1(Х" — 1) + аь зх" 1+ ... + аьх+а„ и, следовательно, (Х)(а„- Х" '+ а.,Х" '+ ... +аь)= — (а -2Х +а„аХ + ... +аьх+а„1). Если подпространство У вЂ” идеал и элемент ч принадлежит У, то произведение (Х)ч также принадлежит 1', н поскольку (Х)ч — циклический сдвиг вектора ч, то У вЂ” циклическое подпространство.
Предположим теперь, что У вЂ” циклическое подпространство. Тогда для любого вектора ч, принадлежашего У, произведение (Х)ч принадлежит У, и, следовательно, для любого 1 произведение (Х)Ж = (Х~)ч также принадлежит У. Поскольку У вЂ” подпространство, то любая линейная комбинация с„(Х' ')в+с„-з(Х" )ч+ ... +сьч= =(с„1Х" +сп ах" + ... +се)ч будет принадлежать У. Таким образом, произведение любого элемента из У на любой элемент алгебры А принадлежит У; итак, подпространство У должно быть идеалом. Ч. т. д.
Структура идеала алгебры А„описана в равд. 6А. Это описание в основном сводится к следующему. Пусть д(х) — нормированный многочлен наименьшей степени, такой, что класс вычетов (к (Х)) принадлежит идеалу 1. Если ДХ) — многочлен степени, меньшей чем и, который делится на у(Х), то класс вычетов (1(Х)) пРинадлежит У, н, наоборот, если (((Х)) принадлежит идеалу (, то многочлен 1(Х) делится на многочлен Х(х). Кроме того, многочлен Х" — 1 делится на д(Х), и любой нормированный многочлен, на который делится Х" — 1, порождает свой идеал 7 в алгебре А„.
Ч(ногочлен д(Х) называется многочленом, порождающим идеал. Итак, циклический ход полностью задается многочленом д(Х), на хоторый делится многочлен Х" — 1. С другой стороны, этот же код может быть полностью определен условием, что он является кулевым пространством идеала, порожденного миогочленом 'т(Х) =(Х" — 1)/а(Х). Если д(Х) — многочлен степени г, то по геореме 6.11 размерность кода равна Ь =и — г. Элемент ()(Х)) тринадлежит коду тогда и только тогда, когда многочлен 1(Х) депится на а(Х).
Многочлен Ь(Х) называется проверочным многочленом для кода С, порожденного многочленом а(Х). Поскольку Х" — 1 делится на Ь(Х), то многочлен Ь(Х) может быть использован в качестве многочлена, порождающего цихлический код. Этот последний код знвивалентен коду, двойственному н коду С, и в теории циклических кодов его обычно называют просто кодом, двойственным х коду С.
Пример. Пусть задан многочлен Х' — ! = (Х вЂ” 1) (Хк+ Х+ +1)(Ха+Хе+1) над полем Галуа ПР(2). Многочлен д(Х)= = Ха+ Хе+ 1 порождает циклический (7,4)-ход. Элементы (Хзд (Х)) = (! ! О ! О О О), (Х д(Х))=(О ! 10100), (ХЫ(Х)) =(О 011010), (а(х))=(ооо! 10!), 1101000 0110100 0011010 0001101 (8. 1) (Х'Ь(Х)) =(1110100), (ХЬ (Х)) = (О 1 1 1 0 ! 0), (Ь(Х)) =(001 1 101). Поскольку, хак указывалось в равд. 6.4, условия равенства нулю произведения многочленов и схаляриого произведения соответствующих векторов не совпадают, то рассматриваемый код является нулевым пространством матрицы Н, образованной векторами (Х Ь(Х)), (ХЬ(Х)) и (Ь(Х)), компоненты которых записаны в обратном порядке: можно выбрать в качестве базисных векторов, и, следовательно, матрицу С можно выбрать в качестве порождающей матрицы для этого кода.
Этот ход является нулевым пространством идеала, порожденного многочленом Ь(Х) = (Х вЂ” 1) (Ха+ Х+ 1) = Х'+ Хк+ + Хз+ 1! 0010111 0101110 1011100 (8.2) Легко проверить, что СНт = О. Этот код эквивалентен (7,4)-коду уэмминга, что вытекает из того факта, что все столбцы матрицы Н различны. Другой способ задания циклических кодов основан на использовании корней (которые, возможно, лежат в расширении поля) многочлена д(Х). порождающего идеал. Предположим, во-первых, что все корни соь аь ..., а, многочлена д(Х) различны.
Тогда циклический код полностью определяется следующим условием: вектор ()(Х)) принадлежит кодовому пространству тогда и только тогда, когда аь ае, ..., а„— корни многочлена Г(Х). Связь этого метода задания циклического кода с предыдущим устанавливается теоремой 6.16. Если обозначить через те(Х) минимальную функцию для аь то вектор (1(Х)) является кодовым вектором тогда и только тогда, когда многочлен )(Х) делится на т1(Х), та(Х), ... ..., т,(Х) и, следовательно, на их наименьшее общее кратное. Поэтому код является идеалом, порожденным многочленом') д(Х)=НОК(пт,(Х), и,(Х), ..., лт„(Х)).
Так как многочлен Х" — 1 должен делиться на многочлен я(Х), то элементы иь ат, ..., п. должны быть корнями многочлена Х" — 1, н, следовательно, число и должно делиться на порядок каждого из элементов щ. Таким образом, п можно выбирать равным наименьшему общему кратному порядков элементов аь так как при таком выборе и каждый элемент а; является корнем многочлена Х" — 1, и в соответствии с утверждением теоремы 6.16 этот многочлен делится на д(Х) без остатка.
Если корни задаются как степени одного и того же элемента и порядка е, т. е. если установлено, что а, =а ', где ьи — заданные целые числа, то число сомножителей н степень каждого из них в разложении многочлена д(Х) для целых е н ие могут быть найдены по следующей схеме. По теореме 6.26 все корни минимальной функции те(Х) содержатся в последовательности а"', а". и е' и, ..., так что все корни те(Х) — различные элементы этой последовательности. Показатели степеней в этой последовательности — различные вычеты по модулю е чисел вь и;д, ивуе, и;да, ..., и число различных вычетов равно степени и; минимальной функции те(Х).
Вполне возможно, что элементы ак и а"! имеют одну и ту же минимальную функцию ие(Х) = и;(Х). В этом случае совокупности корней функции те(Х) и т;(Х) будут совпадать и в качестве сомножителя в разложении многочлена й(Х) следует взять только одну из этих функций. Совокупность показателей, ') КОК вЂ” наибольшее общее кратное. — Прим. ред. связанных с многочленом т;(Х), называется циклическим множе- ством этого многочлена.
Пример. Код, рассмотренный в предыдущем примере, можно определить условием, чтобы каждый кодовый многочлен содержал среди своих корней любой корень сс многочлена Хз+Хз+1. С другой стороны, предположим, что известно только, что каждый кодовый многочлен должен содержать среди своих корней а некоторый примитивный элемент поля 6Е(2з). Все примитивные элементы поля 6Р(2з) являются корнями либо многочлена Х'+ +Х'+ 1, либо многочлена Х'+Х+1. Поэтому искомый код— это либо код, рассмотренный в предыдущем примере, либо эквивалентный ему код, порождаемый многочленом Хз+ Х+!. Код, корнями каждого кодового вектора которого являются единица и а — корень многочлена Хз+ Хз+ 1 — порождается многочленом п(Х) =(Х вЂ” 1) (Хз+Хз+ 1). Пример.
Рассмотрим менее тривиальный пример. Пусть р=азз, где а — примитивный элемент 6г(2п). Исследуем двоичный код, для которого р, рз, рз и р4 — корни всех кодовых многочленов. Так как 89 Р',23 = 2п — 1, то ))зз = 1. Пусть т(Х) — минимальная функция для )3. Тогда корни многочлена т(Х) образуют последовательность Р Яз Яз Яз ~~з Язз Яз !Рз ()зз Яг1з Ям Яз Яз !пз (()з4 и) Итак, т(Х) — минимальная функция для Д, 1зз, рз и рз, и много- член принадлежит кодовому пространству тогда и только тогда, когда он делится на т(Х). Различным выборам примитивного элемента а из 6Р(2н) соответствуют различные значения (1, каждое из которых является корнем одного из двух многочленов: Хп + Х'+ Хг + Хз + Хз + Х + 1 или Хп + Х'з + Хз + Хз + Х4 -1- + Хз + 1, Оба получающихся кода эквивалентны (23, 12) -коду Голея, рассмотренному в равд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
