10.482. Из уравнения (10.45) определить производящую функцию Т (z).

10.483. Используя алгоритм 7.4, определить многочлены Л (z) и т) (z) - решения уравнения (10.47).

10.484. Используя процедуру Ченя, найти взаимные корни многочлена локаторов ошибок X (z).

10.485. Вычислить многочлен значений искажений по формуле

Q==(l+ 2 Tk£-z)X + z\

вытекающей непосредственно из уравнения (10.46).

10.486. Используя уравнение (10.32), определить величины всех искажений.

Алгоритм 10.48 позволяет исправлять любое сочетание из s стираний и t ошибок, если d > s + 2t. В этом смысле ошибки вдвое вреднее стираний. Интуитивно этот факт можно объяснить тем, что с каждой ошибкой связаны два неизвестных (локатор и величина), а со стиранием - только одно неизвестное (величина). Однако эта интуитивная интерпретация неверна, поскольку критерий s + 2t <cd справедлив и в двоичном случае, где ошибка всегда имеет известную величину, равную 1.

10.5. Декодирование более чем t ошибок

Хотя алгоритмы 10.33 и 10.48 могут быть применены для исправ-ления некоторых конфигураций искажений, приводящих иногда, к отказу от декодирования, мы в этом разделе ограничимся лишь: случаем простейшего алгоритма 10.15. Читатель, желающий распространить результаты этого раздела на БЧХ-коды общего типа и найти алгоритмы совместного декодирования стираний и ошибок,; может осуществить это непосредственно, хотя такая процедура будет весьма скучной и приведет к более слабым результатам.

Если в слове д-ичного БЧХ-кода с исправлением t ошибок будете искажено не более t символов, то алгоритм 10.15 позволит правиль-1 но локализовать и исправить эти ошибки. Шаг 10.152 этого алго-i ритма завершается определением с помощью алгоритма 7.4 много-1 члена локаторов и многочлена значений ошибок. В этом случае многочлен о() имеет D {2t) = deg о) различных взаимных корней, являющихся корнями ге-й степени из единицы. Декодер определяет! эти взаимные корни на шаге 10.153 рассматриваемой процедуры декодирования. На шаге 10.154 декодер находит

Если произошло не более t ошибок, то каждое Yi g GF (q) задает величину ошибки с локатором Xj.

Если же произошло больше чем t опшбок, то возможны многие другие исходы. Возможно (хотя и очень маловероятно), что алгоритм 7.4 завершится вычислением правильных многочлена локаторов и многочлена значений ошибок, хотя D {2t) = deg а) > t. Возможно также, что алгоритм 7.4 завершится допустимым многочленом локаторов ошибок и допустимым многочленом значений ошибок, соответствующими некоторому вектору ошибок с весом В этих случаях декодер без труда завершает шаги 10.153 и 10.154 процедуры декодирования и неправильно «исправляет» происшедшие по его мнению ошибки. Хотя в этой ситуации декодер ошибается, порицать его за эту ошибку нельзя, так как для полученного слова неправильно найденный вектор ошибок является более вероятным, чем фактический вектор ошибок с большим весом.

Более вероятными, чем рассмотренные ситуации, являются другие две возможности, приводящие к отказу от декодирования па шаге 10.153 или шаге 10.154. Алгоритм 7.4 может завершиться недопустимым многочленом а(), не имеющим deg а() различных корней - корней ге-й степени из единицы. В этом случае на шаге 10.153 происходит отказ от декодирования. Но даже если все корпи о (2) различные корни ге-й степени из единицы, то многочлен со) может быть недопустимым: хотя величины Yi, вычисляемые декодером на шаге 10.154, должны лежать в поле локаторов, содержащем корни ге-й степени из единицы над GF (q), они могут не лежать в поле символов GF (q) В случаях подобных отказов от декодирования (на шаге 10.153 или 10.154) декодер обнаруживает искажение более чем t символов.

Во многих случаях декодер может обнаружить недопустимость многочленов а() и о)() с помощью предварительных вычислений сразу после шага 10.152 и, таким образом, избежать сравнительно длинных вычислений в процедуре Ченя на шаге 10.153. Например, если deg а) <цВ (2t), то о) не может быть допустимым многочленом локаторов не 1-удлиненного БЧХ-кода. Хотя это свойство позволяет обнаружить очень малую часть возможных недопустимых многочленов о(), зато оно не требует никаких дополнительных вычислений.

В качестве второго «теста допустимости» декодер может использовать четность числа неприводимых делителей многочлена о над GF (q) (см. теоремы 6.68 или 6.69 и 6.695). Если число неприводимых делителей многочлена о) не сравнимо с D {2t) по mod 2, то о() недопустим. Эвристически можно полагать, что недопустимый

Yi =

oy(Xi)

Xi ll(Xi~Xj)

1) В частном случае кодов Рида - Соломона этот тип отказа от декодирования невозможен, так как поле символов совпадает с полем локаторов.

многочлен локаторов ошибок равновероятно может иметь как четное, так и нечетное число неприводимых делителей. Поэтому правило проверки допустимости, основанное на теореме Штикельбергера, позволяет распознать примерно половину из недопустимых многочленов локаторов ошибок. Для двоичных БЧХ-кодов с 1 < 2 <; 2"/2 \ это утверждение действительно справедливо; а для частного случая двоичных БЧХ-кодов с исправлением двух ошибок слабая модификация этого теста допустимости позволяет распознать все недопустимые многочлены локаторов ошибок и приводит к полному алгоритму декодирования по максимуму правдоподобия (алгоритм 16.481).

В качестве третьего теста допустимости декодер может использовать классы вычетов z, z, z, z, . . ., z"" mod o) (z). Умножая соответствующ,ие комбинации этих классов, декодер может определить класс вычетов z"** для некоторого tdego*). Рассматриваемый многочлен локаторов ошибок допустим тогда и только тогда, когда z"+ = z mod о) (z). Хотя это правило проверки допустимости пригодно для всех недопустимых многочленов локаторов ошибок, оно не позволяет определить недопустимость многочлена значений ошибок, в результате чего на шаге 10.486 декодер определит «значения ошибок», лежаш;ие в GF (q) \ GF (д).

Для определения допустимости обоих многочленов о() и со) и для введения корректирующих мер в случае недопустимости любого из них введем между шагами 10.152 и 10.153 алгоритма декодирования 10.15 дополнительный шаг.

10.1525. Дополнительный шаг. Вычислить производящую функцию определенную равенством

(10.51)

1 + 5> =

На время оставим вопрос о числе коэффициентов функции которые необходимо определить. Так как и) и о*) заданы, то ясно, что для i > D {2t) декодер должен вычислить

(10.52)

п(20 3=1

Если многочлен о) допустим, то о() = fj (1 - Zjz), где Xi -

различные корни п-й степени из единицы, и а() делит 1 - z". В этом случае

1-2"

О(20 =.

1 (20 =.3! = (2/)(о(20 2 Z"

Если deg(o(20<dego<20 = £)(20, то deg(20a(20и 5+1,= 5 для /с = 1, 2, 3, ... . Обратно, если = 5fдля /с = 1, 2, . .., D (2), то iSji+ft = iSfe для всех к, так как

D(2i) D(2t)

с(20 V С<20 „20 -у с(20 (2)() M2t)

bn+B(2i)+i= -" b„+B(2/)+i-jOj =- OB(20+i-jOj = D(2t)-i-i.

(доказательство индукцией по i). Так как Sn+h = Sik для всех к>0, то 1-f 5(20 = ф(2)д1 2") где degO<;«. Следовательно»

йз(2<)

ф(2<) 1-2П •

ИЛИ о(2)Ф<) = (0(2) (1 - z"). Значит, о) делит cof) (1 - z"). Согласно теоремам 7.42 и 7.411, многочлены ст) и со) взаимно просты. Следовательно, о*) делит (1 - z"). Мы доказали следующую теорему:

10.53. Теорема. Взаимные корни многочлена о) являются различными корнями п-й степени из единицы тогда и только тогда, когда Sia = Si* для к = I, 2, . . ., D {2t).

Таким образом, успех или отказ на шаге 10.153 можно предвосхитить с помощью анализа некоторых коэффициентов функции 5(2) на шаге 10.1525. Проводя дальнейший анализ этих коэффициентов, можно предвосхитить- успех или отказ процедуры декодирования на шаге 10.154.

10.54. Теорема. Если Xi, Х, , Хв(2П различны и

В(20

О(20 П (1-Z,Z), i=l

Хг П {Xi-Xj)

eGF{g)

тогда и только тогда, когда

5<1> = [5ГГ для /с=1, 2, ...,D{2t).

и для всех к

h=i г.

Xi 11 (Xi-Xj)

В ноле, содержащем GF{q), также справедливо равенство

i=l i=l

Если У; = yf , TO ДЛЯ всех к

i=l i=l

Обратно, если S = {Sly, то для /с = 1,2, ...,D выполняются оба условия

1УгХ = (5Р) и YiX = {Siy.

1=1 i=l

Единственное решение первой системы линейных уравнений имеет вид

Xil[{Xi-Xj) где Q определяется условиями degQ<:Z?, Q(0) = 1 и

оо D

[1 + Д {Sh) Д (1 - X!z) = Q modz-D+i.

Единственное решение второй (идентичной) системы уравнений

имеет аналогичный вид с заменой У; на У?, У,- GjP(g) для t = = 1, 2.....£>. и

Теоремы 10.53 и 10.54 показывают, что вычисление фyнкrии позволяет предсказать успех или отказ от процедуры декоди-

рования на шагах 10.153 и 10.154. Так как успех шага 10.153 нельзя гарантировать до вычисления коэффициентов S2i+i: • • •> Sn+D(2i), то необходимо оценить время, требующееся для их вычисления. На самом деле для вычисления нужных и + Z) {2t) - 2t коэффициентов требуется примерно такая же работа, как и для отыскания с помощью процедуры Ченя п соответствующих корней п-й степени из единицы. В этом смысле использование процедуры Ченя на шаге 10.153 дает всего 2t - D {2t) дополнительных вычислений. Однако правило 10.1525 обладает двумя важными преимуществами:

(1) В подавляющем большинстве случаев недопустимость многочленов о() и (д() может быть распознана с помощью вычисления всего нескольких коэффициентов

(2) Иногда удается использовать дополнительные корректирующие соображения.

Например, хотя декодеру не известна величина St+x, часто он знает величины St+K Для различных (малых) значений К, поскольку в силу условия сопряженности iSftg = 5 и в силу условия цикличности Sfi+n = Sh- После вычисления S(> декодеру известны величины А = St+K - S2t+K для различных значений/Г. Если Ак* ф О, то о() и (й() недопустимы. Иногда, кроме

того, эти величины Ак позволяют декодеру вычислить многочлены и и V и тем самым определить многочлен локаторов ошибок, так как, согласно теореме 7.43,

o = C/o(20-f 7т(20.

В общем случае введем следующее обозначение:

10.55. Определение.

,(20 S~S

(Заметим, что первый коэффициент Aiсовпадает Ai, определенной в алгоритме 7.4.) Полагая

„ со t/(o<2)-bFv2<). , „{20 й)<2) Л<20 L / м со" \ -F(co<2"t<2<-а2<)у<2<))

величиной

получим, что

а(2() ([7ai2f)--FT(2t))

Д(20 у V [1 о(20(С/о(20- Ft<2))]\

ft=0

Доказательство. Если o> = Ц (i-Xtz), то разложение

В ряд дроби cu(2o/(j(2<) имеет вид