Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Поскольку Vj Ф 0 при 1 ^ ^ е, величины t/f1 являются корнями
многочлена a (D) при 1 ^ j ^ е. Так как, во-первых, степень а (D) не превышает е, во-вторых, а (D) имеет те же е корней, что и а (D), и, в-третьих, ст0 = ст0, то выполняется равенство а (D) = а (D). Поскольку степень а (D) равна е, мы получим е = е, что завершает доказательство. |
Теперь опишем весьма простой итеративный алгоритм нахождения
Согласно предыдущей теореме, если число ошибок не превышает
[_(d—1)/2__|, то определим a(D) через синдромные многочлены S(D),
разрешив уравнение [a (D)S (D)]de~~2 = 0 для минимального е и для
*> Этот алгоритм принадлежит Бердекэмпу (1967). Мы опишем здесь модификацию алгоритма Берлекэмпа, принадлежащую Месси (1968), и будем ближе придерживаться трактовки Месси.
(6.7.28)
г=о
По определению St, это означает
1 = 0 1 = 0 /= 1
2.
(6.7.29)
(6.7.30)
a(D).
Итеративный алгоритм*) для нахождения a(D)
263
многочлена a (D), о0 = 1, степени, не превышающей е. Эту задачу легче всего описать в терминах регистра сдвига с линейной обратной связью (РСЛОС), представленного на рис. 6.7.1.
Первоначально в регистре хранится последовательность элементов S0, Sj, ..., Si_i из данного поля. Затем регистр вычисляет новый
элемент Si через величины обратных связей —Сь ..., —Сх согласно соотношению
S/=-S,_,C1-S/_2C2-...-S0C/. (6.7.31)
Числа Сх, ..., Ci являются элементами того же поля, что и St. Затем регистр сдвигается на одну позицию вправо, после чего слева в регистр
"у" Y
st-t Sl-2 Sl-3
Рис. 6.7.1. Регистр сдвига с линейной обратной связью (РСЛОС).
вводится Si. При каждом из последовательных сдвигов вправо вычисляется новый элемент, определяемый соотношением
Si=—Sl-lC1—Si-2Cz—...—St-,C[-, i>l. (6.7.32)
Назовем длиной РСЛОС число разрядов в регистре сдвига (/ в обозначениях рис. 6.7.1). Назовем также многочленом связей РСЛОС многочлен С (D) = 1 + CJ) + C2D2 + ... + CtDl, где Съ С2, ..., Ci — показанные на рис. 6.7.1 величины обратных связей, взятые со знаком минус. Поскольку РСЛОС полностью (если не считать первоначально хранящуюся в нем последовательность элементов) описывается заданием длины регистра и многочленом связей, то для обозначения РСЛОС с длиной регистра I и многочленом связей С (D) будем использовать название [С (D), /]-регистр. Некоторые или все величины обратных связей —Съ —С2, ..., —С; могут равняться нулю; поэтому С (D) может быть произвольным многочленом, степень которого не превышает I, причем С0 = 1. Наконец, для любого многочлена S (D) (конечного или бесконечного) будем говорить, что tC(D), /]-регистр генерирует [S (?>)]{; тогда и только тогда, когда регистр, первоначально хранивший S0, ¦¦¦, ь порождает оставшиеся элементы (если они есть) Si, ..., SL методом, определяемым соотношением (6.7.32). Поскольку (6.7.32) эквивалентно утверждению, что коэффициент при D1 в произведении С (D)S (D) равен 0, то [С (D), Л-регистр генерирует [S (D)]^ тогда и только тогда, когда
264
[С (Z?)S(D)]f = 0.
(6.7.33)
Теперь вырисовывается связь между устройством регистра сдвига с линейной обратной связью и задачей нахождения a (D). Задача состоит в отыскании такого [а (D), е]-регистра с минимальной длиной е, который генерировал бы [5(D)]^_2. Заметим, что определение [cr(D), el-регистра включает в себя ограничение степени о (D) максимальной величиной е и условие сг0 = 1. Ниже дан алгоритм нахождения такого самого короткого регистра. Будет показано, что этот алгоритм работает в случае произвольного многочлена 5 (D) над произвольным полем. Алгоритм состоит в нахождении последовательности регистров, первый из которых является самым коротким регистром, генерирующим S0, второй — самым коротким регистром, генерирующим S0 + + SjD, и т. д. Регистр, воспроизводящий алгоритм генерирования [S (D)]”-1, назовем [Сп (D), /п]-регистром. Грубо говоря, алгоритм работает следующим образом: при заданном [Cn (D), /п]-регистре, генерирующем [S (D)]^-1, алгоритм проверяет, генерирует ли [Сп ф),1п]-регистр также [S (D)]", т. е. выполняется ли [Сп (D)S (?>)]?„ = 0.
Так как по предположению [Сп (D)S (D)]?~‘ = 0, то вопрос состоит в том, равен ли нулю коэффициент при Dn у многочлена Сп (D)S (D). Эта сумма называется следующей разностью, dn, алгоритма; выражая Сп (D) через 1 + Сп XD + Сп 2D2 + ..., имеем
Обозначим через Sn коэффициент при Dn, генерируемый регистром согласно (6.7.32); тогда получим dn — Sn — Sh, так что dn равно разности между благоприятным значением следующего выходного символа Sn и действительным выходным символом регистра S'n. Если dn = 0, алгоритм увеличивает п на 1, сохраняя неизменным регистр. Если dn Ф 0, к многочлену связи добавляется поправочный член, так, чтобы Sn генерировалось правильно.
