У. Питерсон - Коды, исправляющие ошибки (1267328), страница 49
Текст из файла (страница 49)
5.2. Пример. Пусть д = 2 и а — примитивный элемент поля 6Е(2'). Тогда а'з = 1. Рассмотрим код, такой, что вектор Д(Х)) принадлежит ему тогда и только тогда, когда элементы а, ссз, а.', а', аз и а" являются корнями многочлена )(Х). Пусть через т;(Х) обозначена минимальная функция для а'. Тогда а, аз, аз и аз — корни многочлена т,(Х) и т1(Х) = тз(Х)= т,(Х) = т,(Х). Аналогично аз. аз, а'з, азз = аз в корни многочлена тз(Х). Это описание можно сократить, перечисляя только показатели степеней или циклические множества: 1 2 4 8 т,(Х)= т,(Х)=тз(Х) (степень 4), 3 6 12 9 тз(Х)=тз(Х) (степень 4), 6 Рб з(Х) (степень 2).
Отсюда д(Х) = т»(Х)та(Х)л»а(Х), и степень д(Х) равна 1О. Пример. Пусть»! = 2 и с» — примитивный элемент поля»хг (2а). Тогда оса» = 1. Рассмотрим код, содержащий вектор ([(Х)) тогда и только тогда, когда я, »ха, а~, ..., аш — корни многочлена !(Х).
Тогда аналогично предыдущему находим 1 2 4 8 16 и» (Х) =лт,(Х) = т»(Х) =т»»а(Х) (степень 5), 3 6 12 24 17 ата(Л)=»»»е(Х) (степень 5), 5 10 20 9 18»пе(Х)=»п»о(Х)=»пс(Х) (степень 5), Т 14 28 25 19 »нт(Х) (степень 5). При этом все элементы м, яа, »аа, ..., и»о находятся среди корней многочленов т»(Х), л»а(Х), та(Х), л»т(Х), и поэтому к(Х)=»п,(Х) эта(Х) я»а(Х)»нт(Х)р так что степень д(Х) равна 20.
Если известно, что элемент а» должен быть корнем многочлеиа 1(Х) кратности гь то в разложении миогочлена д(Х) минимальная функция и»(Л) для»а» должна повторяться г» раз. Можно показать, что многочлен Х" — 1 не имеет кратных корней, если п и»! взаимно прость» '). Если п= двп», где и» и»! взаимно просты, то по теореме 6.14 Х" — 1 =(Ххи — 1) Таким образом, все корни многочлена Х" — '1 всегда повторяются одно и то же число раз, а именно ср раз, где»! — наибольшая спетень числа»1, на которую делится и. Лля кратных корней значение и можно найти следующим образом.
Пусть и» вЂ” наименьшее общее кратное порядков элементов с»», аа, ..., с»,. Каждый из этих элементов — простой корень многочлена Х"' — !. Пусть г — наибольшая кратность среди кратностей всех корней, а з — наименьшее целое число, удовлетворяющее неравенству г„,»»!в. Тогда л = и»»)'. Ниже два способа практического отыскания минимальной функции для заданного элемента поля иллюстрируются на примере элемента аа, где а — корень примитивного многочлена Хф+ + Х+ 1.
(См. табл. 6.1.) 1. Элементы саа, »аа, с»»а и ас — корни многочлена г»га(Х), и, следовательно, та(Х) = (Х вЂ” аа) (Х вЂ” аа) (Х вЂ” аа) (Х вЂ” с»в). Производя с использованием табл. 6.1 умножение, находим та(Х) = =Х'+Ха+Х +Х+1. ')в ~„„, х — р фр„„, р„„, х- ВЗаИМНО ПРОСтн. СМв НаПРИМЕР, [7, СтР. 102", 23, СтР. аа). 2.
Известно, что степень многочлена тз(Х) равна 4. !!усть т(Х) = ае+ а~Х+ аэХэ+ азХз+ Х'. Подставляя аз = (1000) вместо Х, ив = (! ! ОЮ~ вместо ХЯ, аз =(1010) вместо Х~ и ам= = (1 1 1 1) вместо Х, получаем 0 1 1 0 0 1 О + ' 0 + ' 0 + 1 0 0 1 1 0 1 1 1 + =0 0 1 или а, +аз+ аз+ 1=0, аз+ 1=0, +1=0, а+ 1=0, откуда ае= а~ — — ая = аз = 1. Еще один способ отыскания мини- мальной функции приводится в книге (7) (теорема 5.25). 8.2. Матричное описание циклических кодов Наиболее элементарный способ представления циклических кодов с помощью матриц был проиллюстрирован в предыдущем разделе.
Если многочлен д(Х) =- а,Х" + а ~Х"-'+ ... + ае порождает код, то все векторы (Х"-'-'2(Х)), (Х" эд(Х)), ..., (д(Х)) являются кодовыми векторами. Таким образом, кодовыми векторами являются все строки следующей матрицы: а, а„ , . ... п„ 0 ..... О 0 а, а„ , .... а, 0 .... 0 (8.3) О 0 0 0 а,а,,....авО 0 а, ..... ае Очевидно, что строки этой матрицы линейно независимы, а ее ранг, совпадающий с размерностью кода, равен и — г, Следовательно, по теореме 2.9 простравство строк матрицы 6 представляет собой кодовое пространство. Как н прежде, условимся о следующем. В любом циклическом коде первые й символов, т.
е. коэффициенты при Х~'-', Х"-е, ... ..., Х"-", будут всегда выбираться в качестве информационных символов, а последние а — А символов, т. е. коэффициенты при Х"-"-', Х"-"-', ..., 1,— в качестве проверочных символов, Порождающая матрица любого циклического кода может быть следующим образом приведена к модифицированной прнведенноступенчатой форме.
Пусть г;(Х) — остаток от деления Х' на многочлен К(Х): Х' = и (Х) ас (Х) + г, (Х). являются кодовыми векторами. Если эти многочлены при ! = и — 1, п — 2, ..., п — й выбрать в качестве строк порождающей матрицы, то О=(1м — й где 1а — единичная матрица размерности й р',й, а — К вЂ” матрица размерности АК(п — й), 1-й строкой которой является вектор из коэффициентов многочлена — г„;(Х). Тогда по теореме 3.3 код является также нулевым пространством матрицы Н =(~; 1.—.), причем 1-я строка матрицы Нг является вектором коэффициентов многочлена г„!(Х) даже при !' ~ и — й.
Пример. Для двоичного циклического кода, порожденного многочленом !'(Х) = Х'+ Хт+ 1, г н = (8.4) (8.5) Приведенная здесь матрица 6~ построчно эквивалентна матрице (8,1), Она задает даже не эквивалентный, а точно такой же код. Теперь рассмотрим двойственный код, т. е. код, порождаемый з соответствии с теоремой 6.12 многочленом (Хт — 1)(д(Х) = Тогда многочлены Х' — г,(Х) =д(Х)д,(Х) Хе=у(Х)(Хз+ Хз+ Х) + Хз+ Х, Х =8(Х)(Х'+Х+ П +Х+1, Х4=у(Х)(Х+ 1) + Хз+ Х+!, Хз,(Х) (П Х2 Х'=8(Х)(0) + Х~ Х'=8(Х)(0) +Х, Хо з (Х) (0) +1, 1000110 0100011 0010 ! 11 0001101 110 01! 111 101 100 010 001 = (Х вЂ” 1) (Ха -!- Х -!- 1) = Х4 + Хэ + Х' + 1.
Для этого порождаю- щего многочлена Нэ = г (8,6) и 1001110 бе= 0100111 0011101 (8.7) Матрицы Н, и бэ совпадают, если в одной из них порядок расположения ст))ок и столбцов заменить на обратный. То же самое верно для матриц б~ н Нв Перестановка строк не изменяет про. странство строк нли нулевое пространство матрицы. Перестановка столбцов возникает из-за того, что произведение двух.многочленов равно нулю только в том случае, когда равно нулю скалярное произведение соответствующих векторов, порядок следования компонент в одном нз которых изменен на обратный. Будем снова предполагать, что многочлен г(Х) принадлежит кодовому пространству тогда н только тогда, когда элементы аь аъ ..., а, являются его корнями. Если 1(Х) =(„,Х"-'+(„аХ"-'+ ...
+(,, топри( =1,2,...,г 1(а)=~„,а","'+)„эо" ,~+ ... +~э=О, н это равенство может быть записано при помощи произведения матриц (Р„и Р„; "" )аИа7 '» аГ '.". от7=0. Это условие в точности эквивалентно условию, состоящему в том, что и; — корень многочлена !(Х), Б соответствии с теоремой 6.16 это условие совпадает также с условием, состоящим в том, что многочлен !(Х) делится на минимальную функцию т~(Х) для элемента ап Далее, то, что элементы аи ае, ..., а„являются кор- га(Х) = г~(Х) = г4(Х) = гъ (Х) = ге(Х) = г,(Х) = га(Х) = Хз ( Хз ( Х Х~+ Х+ 1, Ха+Хе +1, Хз Х' Х 1, !1!О 0111 1101 1000 0100 0010 0001 а" 'а" 2...а'ао ! оф оа" — 2., а! ао 2 ''" 2 (8.8) ао 1 а"-2... а! аа г г г Совокупность всех многочленов, одним из корней которых является элемент а2, совпадает с нуленым пространством матрицы (а!" ', а! 2, ..., ао!), (8.9) и поскольку эта совокупность многочленов совпадает с многочленами, которые делятся на минимальную функцию т2(Х) степени ио, то оии образуют идеал, размерность которого по теореме 6.11 равна п — иь Так как размерность нулевого пространства матрицы (8,9) равна и — п22, то из теоремы 6.11 или из теоремы 2.15 следует, что размерность пространства строк матрицы равна !и!.
Заметим, что коэффициенты кодовых многочленов принадлежат полю 6Р(д), а а! — элемент расширения поля, если только л22Ф1. Элементы расширении поля можно рассматривать как векторы с т„компонентами над основным полем. Следовательно, размерность пространства строк матрицы (8.9) над 6Р(д) равна п2!. Рассматриваемый ниже пример поясняет изложенное выше. Если а! и а; определяют один и тот же минимальный много- член т2(Х) = т2(Х), то соответствующие им нулевые пространства совпадают и, следовательно, соответствующие пространства строк определяют одно и то же пространство над полем 6Р(д).
Поэтому при построении матрицы Н (см. формулу (8.8)) в разложении многочлена д(Х) нужно использовать только один корень каждого неприводимого сомножителя. Пример. Рассмотрим снова двоичный циклический код. содеркащнй вектор (1(Х)) тогда и только тогда, когда элементы а, а2, ... ..., ао являются корнями многочлена 1(Х).
Здесь а — корень многочлена р(Х) = Х'+Х+ 1 и, следовательно, примитивный элемент 6Г(2'). В этом случае а (Х) = т, (Х) то (Х) то (Х), достаточно потребовать, чтобы корнями любого многочлена (Х), принадлежащего коду, были элементы а, ао и ао. Искомым ооцом является нулевое пространство матрицы Н, транспониро- нами маогочлена 1(Х), эквивалентно условию, состоящему в том, что соответствующий вектор принадлежит нулевому пространству матрицы ванная матрица к которой равна ом о[э „!2 о70 — 44!О аж= оО аэ!=! 42 !2 аз! = аО аОО = аО о! оз оО 1 оО о5 О ! или Нг= если подставить, пользуясь табл.
6.1, векторное представление элементов поля, Далее, Х'Π— ! = (Х вЂ” 1) (ХО+ Х + 1) (Х4+ ХО+ Х2+ Х + Ц Х Х(Х +ХО+ 1)(Х +Х+ !), и легко проверить, что если ОΠ— корень многочлена ХО+ Х+1, то эа — корень многочлена Х'+ ХО+ ХО+ Х+ 1, 422 — корень много- члена ХО+ Х+1. Поэтому ранг матрицы (ОО!4, а42,..., аО) равен 4 и ранг матрицы (4442, аОО,..., аО) также равен 4, поскольку степени минимальных функций для каждого из элементов ОО и 422 равны 4. Степень минимальной функции для элемента аО, однако, равна О, и ранг матрицы (4422,42'О,...,а ) должен быть равен 2. Очевидно, что это так; в матрице Нт девятый столбец состоит из нулей, а десятый н одиннадцатый столбцы полностью совпадают. 1001 111! 1101 10!0 11!1 1!00 1110 1000 0111 0001 1010 11!! 0101 1010 1011 1100 1100 1000 0110 000! 001! 111! 1000 1010 0100 1100 0010 1000 000! 000! 0111 0!10 0001 0111 0110 0001 01!1 0110 , 0001 0111 0110 0001 011! 0110 0001 Если требовать, чтобы многочлен 1(х) имел корень а; кратности гь то ПХ) и ги — 1 его первых формальных производных должны обращаться в нуль прн Х = аь Следовательно, если 1(Х)=а»,Х" '+а»,Х» '+ ...
+а„ то 1(а) =аи,аи '+а„-ха" 2+ ... +ао=О )'(а) =а, (и — 1)а" '2+а» 2(п — 2) а" 2+ ... +а, + О=О, 1 (а) = а , (п — 1) (п — 2) аи-' + ... + 2а, + О + О = О и т, д. Таким образом, каждый кодовый вектор должен принадлежать нулевому пространству следующих 22 векторов: ( аи-3 „и — 2 2 1) ( (п !)а»-2 (и 2)аи 2 ... 2а, 1 О) ((п — 1)(п — 2)а" 2, ... 2, О, О) н т. д. 3,3. Описание циклических кодов при помогци ассоциированных многочленов Существует другой важный способ описания циклических кодов [213), при котором каждый кодовый вектор получается в виде набора п значений некоторого многочлена, ассоциированного с этим кодовым вектором, при подстановке в многочлен значений 1, а, ..., а" — '.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
