У. Питерсон - Коды, исправляющие ошибки (1267328), страница 78
Текст из файла (страница 78)
Следовательно, этот вектор является кодовым вектором минимального веса примитивного кода, его ненулевые символы должны быть равны друг другу, а номера их позиций должны образовывать линейное подпространство поля 6Г(д ). Ч.т.д. Следствие 10.2. Кодовьси вектор обобщенного кода Рида— Маллера длины и =(а — 1)/(»/ — 1) с Ь = д — 1 и и= с есть вектор минимального веса тогда и только тогда, когда все его ненулевые символы равны друг другу, а номера их позиций соответствуют точкам некоторого проективного подпространства размерности гп — с — 1.
Доказательство. Рассмотрим выражение (10.38): А,»», — — и"'Аь Так как а — примитивный корень 6Г(д"'), то и — примитивный корень 6Р(г/). Следовательно, множество векторов Аз+,, 1= О, 1, ..., д — 2, состоит из всех ненулевых скалярных кратных какого-либо одного вектоРа, скажем Аь 0 =1( п. Это множество соответствует некоторой точке проективного пространства, и в этом смысле для каждого Аь 0 « /( п, в проективном пространстве найдется некоторая точка.
По теореме 10.11 ненулевые символы любого кодового вектора минимального веса равны„а их номера позиций соответствуют линейному подпространстиу поля 6Г(д ) размерности и — с. Тогда из определения проективного надпространства непосредственно следует, что номера позиций ненулевых символов (из числа первых и символов) образуют проективное надпространство размерности т — с — 1. С другой стороны, пред- положим, что все ненулевые символы некоторого кодового вектора длины и равны друг другу, а их номера позиций соответствуют проективному подпространству размерности т — с — 1. Согласно теореме 10.12, этот вектор будет вектором наименьшего веса не- примитивною кода, поскольку при повторении д — 1 раз он превращается в некоторый вектор минимального веса обобщенного примитивного кода Рида — Маллера длины д"' — 1 с р = с. 10.6.
Полииомиальные коды Класс кодов, называемых полиномнальными, включает в себя как частные случаи большинство известных наиболее важных циклических кодов: БЧХ-коды, включая «оды Хэмминга и Рида— Соломона; коды Рида — Маллера; проективно-геометрические коды; евклидово-геометрические коды. Этому большому классу кодов посвящена оставшаяся часть этой главы.
Сначала вводится поня. тие подкода с символами из подполя основного поля символов кода. Затем полнномиальные коды определяются как подкоды обобщенных кбдов Рида — Маллера. В конце главы показывается, что РС- и ЕО-коды относятся к классу полнномиальных кодов, и в связи с этим выводятся их новые свойства. Если т' — некоторый код с символами из Ог"(д'), то Ог"(д)- подходом кода»' называется множество всех векторов (т, символы которых являются элементами Ог"(д). Легко проверить, что это множество будет подпространством. Теорема 10.13.
Пусть д(Х) порождает код с символами из ОГ(д') и у'(Х) порождает Ог(у) — подход этого кода. Тогда р— корень д'(Х) в том и только в том случае, когда р» — корень д(Х) при некотором й 0 ~ 1( з. Доказательство. По определению подкода многочлен и'(Х) должен принадлежать первоначальному коду, и поэтому каждый корень д(Х) будет также корнем д'(Х). Кроме того, если (~— корень д'(Х), то элементы р», р»', ... также будут корнями у (Х), поскольку коэффициенты д'(Х) принадлежат Ог" (д). Теперь, если »3 — 1 р» — корень д(Х), то р» и ф ) =р =(3 будут корнями у'(Х). С другой стороны, если корнями некоторого многочлена являются все р, такие, что р» при некотором 1 есть корень д(Х), то среди корней этого многочлеиа будут, в частности, все корни д(Х), а коэффициенты многочлена суть элементы ОГ(д).
Следовательно, этот многочлен принадлежит подкоду и должен делиться на 6'(Х), а д'(Х) не может иметь других корней. Ч. т, д, Примером подкода над подполем может служить БЧХ-код. Любой (п,й)-код БЧХ с конструктивным расстоянием 4, есть подкод над подполем (и, А')-кода Рида — Соломона с тем же конструктивным расстоянием дь и А < й', если подкод — собственный. Полиномиальный код определяется как Ог'(д)-подкод обобщенного кода Рида — Маллера над Ог(д*), По-другому его можно определить как множество всех векторов над ОР(ч), соответствующие многочлены которых принадлежат Р(т, д;р, Ь).
Код задается пятью параметрами: д — число элементов в поле символов кода; ц' — число- элементов в поле символов обобщенного кода Рида — Маллера, подкодом которого является описываемый код; !и — параметр, связанный с номерами позиций и длиной кода (в качестве номеров позиций символов кодового вектора выби- Р аются элементы Ог(д ), и, следовательно, д'™ — 1 делится на длину и кола); Ь вЂ” делитель 4' — 1 (длина кода и = (д ' — 1)!Ь н степень каждого слагаемого многочлена, соответствующего кодовому вектору, должна делиться на Ь); !с — порядок кода. Соответствующие многочлены в Х = (Хь, Хь...,Х„,) имеют степень рЬ. Следующая теорема есть прямое следствие теорем 1О.
!3 и 10.9. Теорема 10.!4. Пусть а — примитивный элемент ОР(д ), Тогда ак будет корнем порождающего многочлена д(Х) полиномиального кода тогда и только тогда, когда на Ь делится Ь и ппп РУ,.(~щ')=1Ь, О<!<'(™ь "~ — Р. Поскольку полиномиальные коды — это подкоды обобщенных кодов Рида — Маллера, то теорема !0.10 дает для полиномиальных кодов простую нижнюю границу минимального расстояния.
Подкодами полиномиальных кодов оказываются многие изученные ранее коды. Обобщенные коды Рида — Маллера образуют по определению подкласс полиномиальных кодов прн в = 1, т. е. когда подполе совпадает с самим полем символов. Коды Рида— Соломона являются частным случаем обобщенных кодов Рида— Маллера при Ь = т = 1. Следовательно, их можно также считать полиномиальными кодами. Примитивные БЧХ-коды — это Ог (д)- подкоды кодов Рида — Соломона, и поэтому они тоже являются полиномиальными кодами с Ь = и = 1, но с з, возможно большим единицы.
Эти утверждения можно проверить исследованием с помощью теоремы 10.9 корней порождающих многочленов. Ниже в этой главе обсуждается связь между полиномиальными кодами и евклидова-геометрическими и проективно-геометрическими кодами. Рассмотрим полиномиальные коды с Ь = 1 и р = П(у" — 1) Из теоремы 10.11 непосредственно следует, что любой вектор, все ненулевые симьолы которого равны, а номера их позиций лежат на (т' — 0)-мерной евклидовой плоскости, содержащей нулевую точку, будет кодовым и любой кодовый вектор минимального веса будет иметь такой вид.
Кроме того, из теорем 8.16 и 10.14 следует, что удлиненные полиномиальные коды инвариантны относительно аффинного преобразования. Аффинным преобразованием можно отобразить любую плоскость, не содержащую нулевой точки, в плоскость, содержащую ее, и обратно.
Таким образом, кодовыми векторами будут и плоскости„не содержащие нулевой точки. Проверочными векторами кодов, двойственных полиномиальным кодам с Ь = 1 и 1! = 0(д' — 1), будут все (и — Т!)-мерные плоскости. В следующей теореме показывается, что, если д — простое число, эти коды по существу такие иге, как коды, определенные в равд.
10.2 как евклидова-геометрические. Теорема 10.15. Евклидова-геометрический код порядка г является двойственным полиномиальному коду с параметром 1! = = (гп — 1 — г) (р' — 1). Доказательство. По теореме !0.4 элемент аь будет корнем проверочного многочлена евклидова-геометрического кода тогда и только тогда, когда гс,(Ь) =!'. Согласно же теореме 10.14, аь будет корнем порождающего полнномиальный код многочлена только тогда, когда ппп (ч' . (Ьр') < (г + 1) (р' — 1). (10.53) 0~! <я Необходимо показать, что оба неравенства вытекают одно из другого. Это можно сделать с помощью следующих лемм: Лемма 10.7.
Если !5' . (Ь) ) р' — 1, то существуют Ь и Ьь, такие, что Ь = Ь,+Ьы !г' (Ь,)=р' — 1, и при сложении р'-ичньх представлений чисел Ь, и Ьь не возникает переносов. Доказательство. Пусть Ь = Ьь+Ь|р'+ ... + Ь !р! '!'. Выберем Ьа = Ьао + Ьа!О~ + ° ° ° + Ьа~т — ц!р~'™ таким, чтобы все Ьа4~~Ь! и п~-! Х Ь.!= р' — 1. Пусть тогда Ьь = Ььо+ Ьмр'+ ° ° + Ьыт-пр1~ И' и Ьы = = Ь,— Ььь Отсюда при выбранных Ь, и Ьь непосредственно следует утверждение леммы. Ч.
т, д. Лемма 10.8. Неравенство !с,(Ь) ( г имеет место тогда и только тогда, когда пип В',. (Ьр') < (т + 1) (р' — 1). о<с< Доказательство. Предположим, что гс,,(Ь)= й Тогда, согласно определению з-веса, выполняются следующие соотношения: Ь=Ь,+Ь,+Ьх+ ... +Ь, (10.54) при а) Ьа)ОиЬс>О,если!<с<!; б) Ь, кратно р' — 1, если ! ( с ~ 1; в) в арифметике по основанию р' при нахождении суммы (10.54) не возникает переносов; г) не сУществУет сУммы вида (10.54), удовлетворяющей уел виям «а — в» с большим значением й Тогда, согласно лемме 10.7, йг, (Ь ) < р' ! н )ус, (Ь ) при 1 < с ( й В противном случае компоненту Ь, можно было бы расчленить и образовать сумму, противоречащую условию «г».
(громе того, из условия «в» следует, что (Ь) йГр' (Ьа) + (Ррв (Ьс) + ' ' + ~р (Ьс) = йг,. (ЬЬ,)+ !(р' — !) (10.55) и 1(р' — Ц ~ ~Ю' ° (Ь) ( (1+ 1) (р' — 1). (10.56) Таким образом, если пс,(Ь) <г, то Ю' ° (Ь) < (с" +1) (р' — 1) и, разумеется, ппп Ю' (Ьр') <(г+ 1)(р' — 1). «~с(в Допустим теперь, что сп!и 1(Г в(Ьрс) < (г+ 1) (р' — 1) и пс,(Ь) =Ь а(с<в Тогда сг' (Ьр') при 1(~с" (Еделится на р' — 1. Пусть (Р' (Ьср )= =Ьс(р' — 1).
Учитывая условие „в", имеем ~~; (Ьр') = %'; (Ь,р') + РР; (Ь,р') + . " + и'; (Ьср')= с = !Р (ЬР')+ (Р' — 1) ~, Ьс ~ 1(Р' — 1). (10.57) Отсюда следует, что если Яс в(Ьр') ((г+ 1) (р' — 1), то св,(Ь) = = ! ( г. Ч. т. д. Доказательство теоремы вытекает из леммы ! 0.8.
Теперь возникает вопрос: действительно ли евклидово-геометРический код, определяемый теоремами 10.4 или 10.15, является наибольшим кодом, содержащим в своем нулевом пространстве все евклидовы плоскости размерности г+1 или более) Для обсуждавшихся до сих пор кодов с символами из простого поля Делсарт ]50] показал, что полиномиальный код теоремы 1015 поРождается своими векторами минимального веса, которые и яв. лаются этими плоскостями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
