У. Питерсон - Коды, исправляющие ошибки (1267328), страница 68
Текст из файла (страница 68)
Остальная часть этого раздела посвящена доказательству последнего утверждения. В двоичном случае уравнения 19.11), связывающие синдром с номерами и значениями ошибок, упрощаются, поскольку все ошибки имеют значение 1. Таким образом, при тв — — 1 51 х„Хр 1 ~~1 ~(21о. Величины 5; являются в этом случае симметрическими функциями от Х, которые называются степенными симметрическими функциами.
СиндРом дает пеРвые 2го степенных симметРических фУнкцнй. Степенные симметрические функции 51 связаны с элементар. ными симметрическими функциями о; тождествами Ньютона' ) 5,— о,=О, 5,— 5а,+2о,=О, 5з — 5зо, + 5,оз — Зоз —— О, 5,— 5за, +5,о,— 5,о,+4о4=0, (9.54) В двоичном случае 2-й этап процедуры декодирования завершается решением этих уравнений, конечно, если нх можно решить.
Теперь, если произошло и, и ~ 1ы ошибок, то о; = 0 для всех з ) ч. Следующая теорема показывает, что уравнения (9.54) при заданных 5, могут быть решены относительно аз з). Теорема 9 11. Матрица размерности ч К т 0 О 0 ... 0 5 5, 1 О ... О 54 5з 5з 5~ ° (9.55) 5зъ — 4 52' з 52% 6 521 7 ''' 5ч 3 5з з 5з -з 5з 4 5з -з ° ° ° 5 .-~ 0 0 0 0 1 0 о, з и поэтому матрица Мч должна быть вырожденной. Ч. т. д.
Лемма 9.6. Если 5; — степенные суммы и переменных Х„... ..., Хч, то определитель матрицы М„равен [ М. [= П(Хз+ Хз). /<! ') Си., например, книги [224, 255, 3101. ' Аналогичные результаты дли полей действительных чисел см., например, в [941, невырождена, если степенные симметрические функции 5, зависят от и или и†1 различных элементов поля, и вырождена, если 5; зависят от меныиего чем и†1 числа различных элементов поля. Для доказательства потребуются следующие две леммы: Лемма 9.5. Если степенные симметрические функции 5; являются суммами меньшего чем и — 1 числа степеней р злйчаах элементов поля, то матрица Мч ввгрождена.
Доказательство. Согласно тождествам Ньютона (9.54), доказательство. Если Хг — — Хь то все степенные суммы содержат два одинаковых слагаемых, которые взаимно уничтожаются, „оскольку поле имеет характеристику 2. Тогда по существу ие 5~лес т — 2 различных элементов участвуют в образовании степениьгх сумм и в соответствии с леммой 9.5 определитель будет равен нулю. Поэтому при всех 1 и 1 Х;+Х; входит множителем в определитель и левая часть доказываемого равенства должна делиться на правую. Как левая, так и правая части являются однородными функциями степени т(т — 1)/2; следовательно, они должны различаться самое большее на постоянный множитель.
для определения этого постоянного множителя достаточно рассмотреть просто частный случай. Пусть число т — нечетное и Хг являются корнями уравнения Х' — 1= О. Тогда Г О, если )~ Опюбт„ Ех,'=л,~ ' х 1, если 1 Огпобч. В каждой строке и в каждом столбце матрицы М, 1формула (9.55)) содержится по одной единице, и, следовательно, в этом случае ~М,~ = 1. При четном т предположение, что Х~ составляют множество корней уравнения Х" — Х=О, приводит к тому >ке результату. Постоянный множитель, который может быть только либо О, либо 1, должен быть равен, таким образом, 1. Ч.
т. д. Теперь утверждение теоремы 9.11 следует из того факта, что если определитель 1М,~ равен нулю, то необходимо, чтобы некоторое Х, равнялось Х.. Так как все ненулевые Х; различны, то Х~ = Х~ = О и на самом деле произошло меньше чем т — 1 ошибок. Ч. т. д. Этот результат показывает, что, если произошло 1, или меньше ошибок, для определения о, по Б; следует попытаться решить первые 1а уравнений (9.54). Если произошло 1а или 1а — 1 ошибок, решение получается обращением Мг,.
Если это не так, то число уравнений уменьшается на 2 и процедура повторяется. В конечном счете таким образом будет получено решение. К счастью, к уравнениям (9.54) применим один нз вариантов итеративного алгоритма, описанного в равд. 9.5, и необходимость в последовательных попытках решения этих уравнений отпадает. Рассмотрим первые го уравнений ао+ а« оз ао + Яза« + 3«аз + аз =О, =О, (9.56) Зо<,-газ+ аз<,-«а«+ ...
+ зз«,-з-.ча =О, Зз<о «аз+~но-за«+ ... +5з<о «,а,=О, где ао — — 1. Вообще говоря, если ч может быть произвольно большим, эти уравнения имеют много решений. Однако если ч не больше 1о, то, как следует из теоремы 9.11, существует только одно решение, т. е. все другие решения состоят из более чем 1о, а фактически из более чем 21о — ч элементов а«. Удобно представлять а< с помощью многочлена о(Х)=аз+ а,Х+азХз+ ... + а«Х'. Тогда задача, декодера сводится к нахождению многочлена наименьшей степени а(Х) с ао —— 1, такого, что его коэффициенты удовлетворяют системе уравнений (9.56).
Это может быть сделано итеративно. На и-м шаге декодер рассматривает только первые п уравнений и определяет многочлен минимальной степени а<" (Х)=во+а«<">Х+ аз<">Х + ... + а<<">Хо будет решением для первых (п+ 1) степеннь<х сумм. Кроме того, степень а<"+»(Х) равна 1„+,— — >пах11„1 +2(п — т)). такой, что его коэффициенты удовлетворяют системе уравнений (9.56). Степень 1„не больше и. На (п+ 1)-м шаге этот результат и предшествующее минимальное решение используются для нахождении следующего минимального решения о<"+" (Х).
При достижении состояния ч получаем минимальное решение, так как, согласно теореме 9.11, существует только одно решение степени ч. Это решение остается неизменным при и, больших ч и меньших или равных 1о. При доказательстве приведенных выше утверждений полезны следующие леммы: Лемма 9.7. Пусть а«"> (Х) — минимальное решение степени 1„п первых п уравнений (9.56) и <1„Ф О вЂ” значение левой части (и+ 1)-го уравнения. Назовем эту величину и-м расхождением.
Пусть а< > (Х)= =1+а<«>(Х)+ ... +а< >Х«'" — л<обое решение первых т < и уравнений с т-м расхождением <( ФО. Тогда многочлен а< >(Х)+<1„<1 «Хз< ~~по >(Х)= < +>>(Х) (9.57) доказательство. Так как а(и)(Х) является решением первых п уравнений (9.56), то 10, 1=1,2,..., )п~ .С ~ф + ал (9.58) (1и* 1=а+ 1.
где а[ ) = О, если с > 12 и аь(") = 1. Аналогично, поскольку а('ч(Х) — решение первых т уравнений с й Ф О, то 2)-1 ГО, '=,2,...,т, где абаи) =О, если 1> 1 . Теперь рассмотрим 21 — 1 )', асахи)'-1'-1+ а2)-1 = С 1 2! — 1 — Ч' С Гаси) .-~ й й )а[ ) ! ~ 2) — 1-1 + и т 2)-2 (и-Си)-1-1)+ 1 1 1(и) + й й-[а(и!) 2)-1 с а)п1 + а(п) ~22-1 с й [1-1( %' 5 сои) [ а(си) + и и! ~ Х~ 1 И-2(п-тЪ-1 — 1+ 2)-1-2(п-!и) 1=1 Это выражение, согласно соотношениям (9.58) и (9.59), при а("ч 0 и с(0 будет равно нулю, если 1= 1, 2, ..., и, а также если 1= и+ 1, и поэтому а[и+1)(Х) будет решением первых и+1 уравнений (9.56). Степень первого слагаемого в формуле (9.57) равна 1, а степень второго составляет 1 +2(п — т).
Очевидно, что если 1 + + 2(п — т) > 1„, то степень а("+') (Х) равна 1 + 2(п — т); если же 1 + 2(п — т) меньше 1ии то степень а["+')(Х) есть 1 . В случае равенства степень не превосходит 1, но поскольку а(и)(Х) — решение минимальной степени, то степень а(и+1)(Х) не может быть меньше 1„. Ч. т. д. Лемма 9.8. Пусть а(и)(Х) — минимальное решение степени и й Ф О. Предположим, что а(и+1)(Х) — произвольный многочлен, удовлетворяющий первьсм и+1 уравнениям (9.56). Пусть (и+1] (Х) (и) (Х) Х2 (и-и!) [ы) (Х) где а Ф 0 и а(""=1. Тогда л[ногочлен а(""(Х) является решением для первых т уравнений с й Ф 0 и =1и+, — 2(п — т), если 12„1>1„ 1„< ~ — 2(п — т), если 12+, =1. 2( — ! ~, З,оф+((,.+о(м+(((=О, 1=1, 2, ..., а+1, ! ! и — ! о, Х'"-- "- -1 ..~0, 1=1 2,...,п, 1=а+ 1. После вычитания получаем р(- ! 1 О, 1 = 1, 2, ..., а, ~ Я([а1)+н,— о("! 1+оф+((! — о<"! (=~ (1ьО 1 а ) ! 1 л 1 (9.60) Следовательно, на а-м шаге уравнениям (9.66) удовлетворяет с ненулевым расхождением множество чисел о! = о("+'! — о(!"! Э исключая ор — о("+'! — о("! = О.
Вообще, если 1 нечетное и первые 1 коэффициентов равны нулю, то уравнения (9.66) требуют, чтобы (1+ 1)-й коэффициент также равнялся нулю. Пусть и— наименьшее целое число, такое, что первые 2(п — и) коэффициентов о! равны нулю, и пусть а — первый ненулевой коэффициент. Тогда формула (9.60) примет вид Теперь положим и( (=а-(о ! (+(и-!ри !1 =а ((1„ и сделаем замену в (9.61): 1' =1 — (а — и) В результате получим с о(!р! -(- о(~р! Теперь, если 1„+, ) 1„, то, очевидно, 1 =1+! — 2(а — и). Если 1+! = 1„н коэффициенты старших порядков о4">(Х) и о("+(>(Х) различны, то линейная комбинация этих двух решений будет еще одним решением степени, меньшей 1„что невозможно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
