У. Питерсон - Коды, исправляющие ошибки (1267328), страница 77
Текст из файла (страница 77)
д. Теорема 19.9. Обобщенньхе коды Рида — Маллерп явля»отса циклическими, и аь — корень порождающего многочлена кода с параметрами т, д, (х и Ь тогда и только тогда, когдп (»» (й) делится на Ь и О» Цт»(Ь)(т(д — !) — рЬ. До азательство. Рассмотрим многочлен т-! л ь!»! т т ,, ! у,(х>-(К -х) -(ь '-'х,) Ж вЂ” ! /»! ,,ь, = П ~ ~'„, а(! '!» Х!) .
(10.41) »-о Степень /»(Х) равна !(т«(Ь). Согласно формулам (!0.34) и (10.35), ,(/») — (1, и", сР», ..., а! -'!". Пусть произвольному многочлену /(Х) в Р(т, д, р„Ь) соответствует т(/)=(им оь, о„!). Тогда «-! п — ! ъ (7)ч(/»)т= Х о«ам= Л /(А!)/»(А!). (!0,42) Теперь предположим, что 1«"д(6) делится на Ь и при этом «!т (Ь) меньше т(д — 1) — !»Ь. Так как степень ! каждого слагаемого /(Х) такова, что вес !!'«(!) делится на Ь и не превосходит рЬ, то степень ! каждого слагаемого /(Х)/»(Х) имеет вес !р' (!), меньший п«(д — !). Кроме того, поскольку /»(0) = О, то /(0)/»(О) = О. Поэтому, согласно лемме !О.б, каждое слагаемое в правой части выражения (10.42) равно нулю н а» должен быть корнем кодового многочлена о,Х +о Х™2+... Так как это справедливо для любого /(Х) в Р(т,д, Ь, !»), то а" должен быть корнем порождающего многочлена.
Число таких корней равно размерности нулевого пространства, задаваемого определением кода, и, следовательно, тем самым описаны все корни. Ч. т. д. Теорема 10.10. Минимальный вес обоби!енного кода Рида— Миллера равен [(0+1)дд — 1)/Ь, где Я и Д вЂ” соответственно частное и остаток от деления т(д — !) — !»Ь на д — 1, и код является подкодом Б«/Х с тем же конструктивным расстоянием.
Доказательство. Каждое число, меньшее Яда+до — 1, имеет вес, меньший т(д — 1) — р.Ь, и, следовательно, существует по крайней мере ([Я+!)дч — Ц/Ь) — 1 последовательных степеней а», являющихся корнями п(Х). Отсюда н из границы БЧХ следует, что минимальный вес равен по меньшей мере [(/г+!)дч — Ц/Ь. П~сть а — некоторый примитивный корень ««Р(д ) и у = = а!« — «1/и-Н. Тогда у — примитивный корень 6Р (д).
Пусть а = (д — Ц/Ь и з = (д — 1)/Ь. Поскольку наименьшее Ь, такое, что «! = !. то «1=а"=у' — примитивный корень Ь-й степени вз ь единицы и многочлен Х» — у'» имеет следующие корни: Х= у1, «!у!, ..., «! -!у!=у!, у!+*, ..., у!+! -н . (!0.43) Рассмотрим многочлен (р ! — я)!» 1»(Хо)= П '«Хо — у ). (10А4) 1-! Нуль и элементы т!, «1у!.. ' «!» «у! при (д — 1 — рг)/Ь </~(д — 1)/Ь не являются его корнями. Таким образом, существует 1«/Ь множеств по Ь ненулевых корней, и каждое множество корней со- стоит из всех произведений одного произвольного корня на степени ть Рассмотрим [ |ь(Х) =[ (Х„)(Х| ' — 1)(Хч ' — 1)...
(Х~~,, — 1). (10.45) Понятно, что [ ц,(Х) — некоторый элемент Р(|п,д,р, Ь). Координатными векторами Аь не представляющими собой решения 1 ы(Х), будут те векторы, у которых аь; не является корнем [ь(Хь) н все Хь Хь ..., Х о | равны нулю, но Х о„..., Х„, | произвольные. Существует (Й+ 1)до — ! таких векторов, исключая нулевой. Эти векторы также принадлежат классам, состоящим из Ь векторов каждый. Вектор такого класса равен произведению любого другого вектора этого класса на некоторую степень элемента г!. В каждом классе, согласно формуле (10.38), содержится один и только один вектор А; с 1, меньшим и. Следовательно,каждый вектор «([ьы) =[[ны(Аь) [яь(А|).
", [зь(А.-|)) должен иметь точно [(1г+ 1)дч — !)/Ь ненулевых компонент, и этому числу равен минимальный вес «([ |„) кода. Ч. т. д. Теорема 10.11. В обобщенном примитивном коде Рида — Моллера (Ь =! и и = д — 1) порядка с(у — !) номера позиций кодового вектора минимального веса образуют (пт' — с)-мерное линейное подпространство поля 6Р(д ) и все ненулевые символы этого вектора имеют одинаковое значение, и обратно, любой вектор, такой, что все его ненулевые символы равны, а их номера позиций образуют (|и — с)-мерное подпространство поля 6Г(д ), является кодовым вектором минимального веса примитивного кода Рида — Маллера порядка с(у — 1).
Доказательство. Пусть Р— некоторое (т — с)-мерное подпространство поля 6Р(ц ) над 6Р(у) и У в его нулевое пространство. Обычным образом определим скалярное произведение векторов. Тогда, если А=(аьаь...,а ) — некоторый элемент «' и В = (Ь!, Ьы..., Ь„) — элемент 6, то А ° В = а, Ь! + а,Ь, + ... + а Ь = О. Пусть теперь В|, В|ь ..., В.— базис пространства 6. Рассмотрим многочлен [(Х) =С,Ц(1-(В| Х) -', (10.46) где Сь~ 6Р(д).
Так как мпогочлен )(Х) имеет степень с(у — !), то он принадлежит Р(т,у,с(з — !),!) и «([) будет кодовым вектором обобщенного примитивного кода Рида — Ь4аллера порядка с(д — 1). Для каждого А|, не принадлежащего т', [(А|) = О, но для каждого Аь лежащего в т', 1(А;)=Сь. Таким образом, вторая часть теоремы доказана. 8, -е, + (д -' — 1) о,, = О, Яс ..о,=О, . 1оа=О, (10.47) Чст-с ~п т-е, т-а-! ~=0. Заметим, что, так как Х, не равны нулю, то о,, ~ О.
Следую- щее уравнение поэтому имеет вид Би~7п — с 1 т — е 1+~ т — а ~О т — е т — с-к — О так что о, т,, может быть не равно нулю. Учитывая формулы (10.47), получаем следующие уравнения: чист-с 1 ст-е-~о1+ сст — е 1пст-е ~т-е-1+1=0, Ц т-с 1п т — с,т-с-1+1=0, ~ст — а ~п,~т — с ст — е-1+и=О, (10 АЗ) т — с 1п т-с т-с — а 1=Ос 5 -с ~ист-с 1 чт-е--и+ ест-с 1н, си-с т-а-2= 0. Следующая функция оь которая может быть ненулевой, — это о, х. Продолжая таким образом, можно показать, что функцйи о; могут быть ненулевыми лишь при (=с) — д' и 1, меньшем т — с. Поэтому 1(Х) =~Х вЂ” Х,) (Х вЂ” Х,)... (Х вЂ” Х...) = , т-с )' оХс с-п ат — с т-с-1 =Х о те сп е 1Х от — с -Ч и — 1 (10.49) ПУсть Хн Х„..., Хс е, — номеРа позиций некотоРого кодового вектора минимального веса, Зь Зм ...
— степенные симметрические функции и он ам ..., о,,— элементарные симметрические функции. По теореме 10.9 функция Зс равна нулю, если м(!) -. (гл — с) (д — 1). При целых 1 в интервале от 1 до 2(д 1) функция Яс может быть не равна нулю только для чисел вида — 1 — д', где 1 — некоторое целое число. Это обстоятельство позволяет значительно упростить тождества Ньютона. Тождества, пронумерованные числами от с7 ' — 1 до 24 — ' — 2 — с! имеют вид Теорема 10.11 обобщается на случай Ь ) 1 следующим образом. Теорема 10.12.
Кодовый вектор обобщенного непримитивного кода Рида — Маллера длины и = (д — 1)сЬ, Ь ) 1 и рЬ = с(д — !) будет векторолс минимального веса тогда и только тогда, когда: 1) все его ненулевые символы равны друг другу; 2) этот и-мерный вектор, повторенный Ь раз, образует пЬ = =(д — 1)-мерный вектор, номера позиций которого составляют (т — с)-мерное надпространство поля СсГ(ц ).
Доказательство. Предположим, что все ненулевые символы не. которого вектора равны друг другу, а номера позиций этого вектора, повторенного Ь раз, образуют линейное подпространство. Тогда полученный пЬ =(д'" — 1)-мерный вектор будет вектором минимального веса кода Рида — Маллера с р с(д — 1) и Ь =!. Ему соответствует многочлен — 2 у(х)= Х ссхн', и по теореме 10.8 ( -с-с) С,=( — 1)'"(су — 1) Х чсАсо с-о (10.50) (10.51) Так как ч; есть (д — 1)-мерный вектор, состоящий из Ь повторений некоторого п-мерного вектора, то — с ь — с (ос 0 Сс = ( — 1) (у — 1) Х Х чсо осАс+ос ' '1 !=о с=о и с учетом чсчы = чс имеем о-! б-с С,=( — 1)™(у" — Ц Х., Х Ас',„-'-'.
с-о с-о и Х1(Х) — многочлен, корни которого по теореме 6.30 являются элементами линейного подпространства поля ссс (сс). Согласно уже доказанной второй части теоремы, если заданы любое Со и подпростраиство )с поля бР(д ), то найдется кодовый вектор, номера позиций которого будут точками подпространства, а значении символов на всех этих позициях равны Со. Предположим теперь, что существует кодовый вектор с такими же номерами позиций, но не с одинаковыми значениями символов. Пусть Со— значение первого символа этого вектора.
Вычитая из первого вектора второй, получим ненулевой кодовый вектор меньшего веса, что невозможно. Следовательно, у любого кодового вектора минимального веса все символы должны быть равны друг другу. Ч. т. д, далее, используя формулу (10.38), получаем »-1 ь — ! С =.( — 1)ы(д'" 1) 2" и А(» -ь-й) ~- с„(»"-~-~1 ! О с=о (10.52) Последняя сумма в этом выражении равна нулю, если только 1п(у — 1 — /) не кратно д — 1, т. е.
если 1 не кратно Ь. Поэтому в равенстве (10,50) вес каждого показателя 1 кратен Ь. Отсюда следует, что многочлен /(Х) соответствует некоторому и-мерному вектору ч(/) обобщенного кода Рида — Маллера с Ь ) 1. Так как по теореме 10.11 вес (д — 1)-мерного вектора равен д — 1, то вес и-мерного вектора равен (д ' — 1)/6. Согласно теореме 10.11, последнее число равно минимальному весу кода, и поэтому указанный и-мерный вектор — кодовый вектор минимального веса.
Предположим теперь, что ч(/) — кодовый вектор минимального веса обобщенного кода Рида — Маллера с Ь ) 1 и и = с(д — 1)/6. Соответствующий многочлен есть некоторый элемент пространства Р(п,д, Ь, и), содержащегося в Р(г/' — 1, д, Ь, р), и, следовательно, соответствующий (д — 1)-мерный вектор принадлежит обобщенному примитивному коду Рида — Маллера. По теореме 10.10 вес и-мерного вектора равен (д' — 1)/6, и из формулы (10.38) тогда следует, что вес (д — 1)-мерного вектора в Ь раз больше, т. е. равен с — 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
