У. Питерсон - Коды, исправляющие ошибки (1267328), страница 66
Текст из файла (страница 66)
(9.28) Эти уравнении зависимы, и, значит, произошло меньше трех ошибок. Полагая аз = О, находим, что оз = иса, после чего легко определить, что о~ = а'з. Номера позиций ошибок удовлетиоряют, как и прежде, уравнению Х2 + а мХ + а'а = О и, следовательно, равны двум его корням аа и ась. Значении Ус находятся нз уравнений (9.11): У,Х, + УзХ,=Во или азУ, +а'ау,=а", УсХс + УзХз ~— — Зм илн а'У~ + аму, = а" Эти уравнения можно легко решить, что дает Ус = а' и Уз — — сс" ° ошибок — значения ошибочных символов нужно просто изменить на противоположные.
В качестве второго примера рассмотрим код Рида †Соломо над ссг(2с), используя представление, данное в табл. 6.1. Предположим, что ошибка, равная и', произошла на позиции с номером аз, а ошибка, равная а",— на позиции с номером а'~. Тогда Я~ = асаз + апаш = (! О ! 1) = ас, 5',=о"о' +оном=(1111)=а", Яз — — а'аз + апааз =(1 1 00) = а', 8, = а"ам + апасо = (1 1 1 1) = а", Яз = асам + апаш = (1 0 0 1) = а'с, Яс=а'а'а+оном=(1001)=а" 9.б. усовершенствования процедуры исправления ошибок В равд.
9.4 показано, что исправление ошибок может быть осуствлено в четыре следующих этапа: ц вычисление синдрома 5ь 5м ..., 5э... 2) вычисление пь пм ..., оп по 5~, З) вычисление номеров позиций ошибок Х; по пб 4) вычисление значений ошибок у; по Х< и 5ь ™ усовершенствование вычислений на трех последних этапах позволило значительно уменьшить объем и сложность вычислений. В этом разделе усовершенствованные процедуры описываются для общего случая. Для двоичного случая четвертый этап не нужен. первый и третий этапы упрощаются уже потому, что двоичные схемы проще построить, чем недвоичные, а методы, представленные в этом разделе для та = 1, являются самыми лучшими из всех до сих пор найденных.
Второй этап в двоичном случае значительно упрощается (см. следующий раздел). Этап 2. Вычисление о; (20, 21Ц. Декодер должен определить из уравнений (9.!6) по вычисленным 5ь 1 ~1 ( 21м величины а,. для всех 1, ! (1 т ~ 1м Эта задача может быть решена итеративным способом. На и-м шаге декодер анализирует только первые и степенных сумм и пытается определить такое множество 1„значений о',"~, удовлетворяющих п — 1„уравнениям 5„+ 5„,о',ы + ... + 5, а<ю = О, л я (9.29) 5, ~+5, ем+ ...
+5,о)ы=О, которое будет наименьшим из возможных, и, следовательно, число уравнений будет максимальным. (Верхний индекс (и) служит для различения решений на различных шагах.) На и-м шаге может оказаться, что не удовлетворяется даже одно из уравнений вида (9.29).
В этом случае полагаем и — 1„= О, т. е. а = 1, и считаем любое множество 1 величин а; решением. Множество от удобно представлять многочленом паа(Х) = аы + паяХ+ и,'"'Х'+ ... + о',"'Х' где ф) =1. Этот многочлен имеет степень 1„или меньше; возможно, что о)м может быть равен нулю и, таким образом, истинная степень озо(Х) может быть меньше 1, На первый взгляд кажется, что 1„можно всегда считать равным степени минимального о~">(Х).
Однако это не так. В примере, приводимом в этом разделе ниже, при и = 3 и 1„= 2 минимальное решение а(Х) имеет степень 1 ч 1„. В этом случае 1г нельзя полагать равным 1, поскольку ока- зывается, что 82+ 81ав1 Ф О, Я, + Ю ав' = О. хотя Теперь предположим, что на п-м шаге декодер определил такой многочлен а~"!(Х) с минимальным 1, что система уравнений (9.29) удовлетворяется. На (и+1)-м шаге декодер пытается найти многочлен ао'+О(Х) наименьшей степени, коэффициенты которого удовлетворяют системе уравнений ~я+~ ~' Я .а<"+и=О, 1, + 1 <)<п+ 1. ю-о Определим и-е расхождение д„ как (9.31) любое решение для первых и степенных сумм, 1 ( т ( п, с расхождением д чь О.
Тогда многочлен ао (Х) 1 д-1Хл п$ ~ш) (Х) ы+и (Х) будет решением для первых и+ 1 степенных сумм. Кроме того, 1„+, —— гпах [1„, 1 + и — пт). Доказательство. Так как а<")(Х) — решение для первых и степенных сумм, то он удовлетворяет уравнениям (9.29), т. е. ) О ! +1~<1<я* (9.32) ~ д„~ О, 1 = и + 1. Если б = О, то системе уравнений (9.30) удовлетворяет многочлен о!"+'>(Х) = аа'>(Х).
Так как на и-м шаге о~ю(Х) по предположению является минимальным решением, то оно, конечно, будет минимальным и на (и+1)-м шаге. Однако, как правило, д Ф 0 и оь'+О(Х) нельзя так непосредственно определить по о<")(Х). Следующие две леммы полезны при определении аш+п(Х). Лемма 9.3. Предположим, что многочлен с (Х) — минимальное решение для первых и степенных сумм [т.
е. он удовлетворяет системе уравнений (9.29И и расхождение д„Ф О. Пусть а' '(Х)=1+ а~ ~Х+ а' 'Х'+ ... + а~ 'Х"— 2 м Аналогично, поскольку о~"'»(Х) — решение для первых т степенных сумм, то ~-8 о» 1 О. 1~-)-1(!-.=-т< „ (9.33) 1й О,; +, Если многочлен оы'ьо(Х) оы»(Х) решением для первых и+1 степенных сумм, то должны выполняться следующие равенства: 2' 3»-М"+"=О 1„, + 1»1»а+ 1. (9.34) Любая из этих сумм может быть представлена в виде (9.35) » О Так как о».".»=О при 1» О и 1>1„, а о»»=О при 1»О н с >1, то сумма (9.35) может быть записана как »и 8 +и-т ~" 3»,.о»ы» — й„с( ' 2 3»,.о) ',„. (9.36) с-о При 1 = и+ 1 первая сумма равна й, а вторая равна И . Поэтому выражение (9.36) сводится к й„— а„а '(а ) и, таким образом, равно нулю.
Первая сумма в (9.36)„согласно (9.32), равна нулю при условии, что 1 +1»1» и. Вторая сумма в (9.36), согласно (9.33), равна нулю при условии п — и»+1 +1»1» и — т+ о». Таким образом, выражение (9.36) равно нулю, если предположить, что шах(1„, и — т+1 )+1»1»п+1. Первым и'+1 — шах(1„,п — т+1 ) уравнениям (9.29) удовлетворяет многочлен оо'+»»(Х), степень которого формально определяется как 1+, — п»ах(1„,п — и»+1 ). Заметим, что коэффициенты старших порядков многочлена о»"+»»(Х) могут быть равны нулю, поэтому этот многочлен может удовлетворять также н другим из уравнений (9.29), т. е.
не будет минимальным. Ч. т. д. Лемма 9.4. Пусть ое'»(Х), 1„и д„чь'О определены так же, как и в лемме 9.3. Предположим, что о»'"+»»(Х) — любое решение системы уравнений (9.29), удовлетворяющее и+ 1 — 1 +» уравнениям. Пусть та же о'"+" (Х) — о'ы (Х) аХ" о' ' (Х), (9,37) где а ФО и о<">=1. Тогда многочлен о~"'~(Х) будет решением первых т — 1 уравнений (9.29), причем расхождение й чь 0 и 1 =1ьы — (и — т).
Доказательство. По условию ~в+! Я о)ч +н = О, 1-О , + 1(1~~а+1, (9.38) (9.39) Так как о1 ~(Х) — минимальное решение, то 1 +~ ~ 1„. Вычитан дли каждого 1, 1ь.м «1( и+ 1, из УРавнении (9.38) УРавнение (9.39), получаем ~в+ ~ (О С ~п Я, Го)" +и — оьв1 = ( ' ~+' ~ ~ " (9.40) Подставляя 1'=1 — (и — т), У=( — (и — т), 1 = 1„.Н вЂ” (и — т), получаем гм 0 1 1<'< у З,,~ .,+ —,.; )=~ 0 ' +1~1 ~ (9.40б) '.--- "'-- =1 .„~О,,-=.+1. Наконец, определим многочлен о (Х) так, чтобы его коэффициенты о<т>=(о<7+и — о'6' „)а '. Тогда ,х, (О ;-ь ~ * ' 1 — й„а-' й„чьО, 1'=т+1.
Согласно (941), многочлен оь"ЦХ) будет решением первых т — 1„, уравнений (9.29) и иметь расхождение Ы ~'О. Степень о~~)(Х), формально выведенная из определения многочлена, равна 1 = 1„+~ — (и — т). Заметим, что коэффициенты старших поряд. ков овч(Х) могут быть равны 0 и что некоторые уравнения (9.29), не вошедшие в (9.406), могут также удовлетворяться, т, е.
Ф">(Х) Теперь обозначим через а первый ненулевой коэффициент при З~ ~ в равенстве (9.40), где первые и — т коэффициентов равны нулю. (Заметим, что так как о1"+и= ф~=1, то и) т.) Тогда уравнения (9.40) сводятся к ет не быть минимальным. В любом случае степень оь")(Х) ажно считать равной 1 +) — (и — т). Ч. т.
д. Теорема 9ЛО. Пусть о~")(Х) — минимальное решение на и-м шаге и о) )(Х) — одно из предшествующих минимальных решений, -т(п, с й ФО, такое, что т — 1 имеет наибольшее значение. Тагда минимальное решение на (и+ 1)-м шаге будет равно оь+))(Х), где о)ь+н(Х)=ол)(Х) н 1ь+)=1 дь=О (9.42а) или '"+О(Х) — оы)(Х) й й-)Хь-ь~ ' )(Х) (9.426) ~~) =п)ах(1„, 1 +и — т), й„Ф О. (9.43) доказательство. Если а =О, то, очевидно, о(км)(Х)=оь)(Х), так как последний многочлен — минимальное решение. Теперь рассмотрим случай, когда й„Ф О. Так как о< )(Х) и о<")(Х) известны, то оь'+))(Х) определяется из (9.42б). По лемме 9.3 многочлен о) +')(Х) есть решение, и его степень определяется формулой (9.43). Остается показать, что это будет минимальное решение, Если т — 1 ) и — 1„, то по лемме 9.3 1„.н = 1„и оь'+))(Х) — минимальное решение на (а+ 1)-м шаге. С другой стороны, если т — 1 ( и — 1„, то 1„+) — — тах(1„, 1 + п — т) 1 + и — т ~ 1„.
Допустим, что существует многочлен Пь'"+') (Х) степени д где 1 = й(1 +п — т. Здесь необходимо рассмотреть два случая. Если а = 1„, тогда, согласно лемме 9.4, существует решенне о)"')(Х) с т' — 1 ° ) и — 1„. Но т — 1 ( и — 1„и т — 1 было выбрано как наибольшее из значений А — 1), для предыдущих решений. Если же й ~ 1„, то по лемме 9,4 й=1 ° + п — т'. Но так как т — 1 т' — 1 ., то й=п — (т' — 1 ))и — (т — 1м)= =1„+) ) с(. Итак, получилось противоречие. Следовательно, о~"+')(Х) есть минимальное решение. Ч. т. д. Теорема 9.10 позволяет определить минимальное решение на (а+1)-м шаге из уже известных решений для всех предшествующих шагов при условии, что по крайней мере одно из предыдущих расхождений не равно нулю. Чтобы завершить процедуру, необходимо найти такое рещение он)(Х), для которого д) Ф О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
