(L, „ Л(-)(х)).

Основная идея алгоритма Берлекэмпа-Мессй состоит в нахождении способа построения нового регистра минимальной длины (Lr, Ле (х)), генерирующего последовательность 5,5,. i, Sr-Это будет сделано с использованием предыдущего регистра сдвига, в котором при необходимости будут надлежащим образом изменены длина и весовые множители.

При г-й итерации вычислим следующий выход (г - 1)-го регистра сдвига:

Поскольку п - 1 больше, чем степень ЛС-, многие слагаемые в сумме будут равны нулю, и, таким образом, ее можно записать как сумму от 1 до deg ЛС-) (х). Однако обозначения будут менее громоздкими, если сумма будет записываться так, как указано выше.

Вычитая Sr из требуемого выхода 5,., получаем величину Д, называемую г-й невязкой:

Ar = Sr- 5, = 5, -I- S Af-"S, ,-, или, что эквивалентно,

Если Дг равняется нулю, то положим (L, ACJ (х)) = (L,. i, A(-i) (х)), и г-я итерация будет закончена. В противном случае следующим образом изменим весовые множители в цепи обратной связи регистра сдвига:

Л(0 (х) = Л(-п (х) f хДС"-! (v),

где А - элемент поля, / - целое число, а AC-i) (х) - один из многочленов регистра сдвига, встречавшихся в одной из

ющий первые г компонент синдрома. Регистр сдвига (L,., Л*) (х)) является регистром сдвига минимальной длины, генерирующим Si, S,- Он не обязательно должен быть единственным: может существовать несколько таких регистров сдвига, но все они имеют одинаковую длину. К началу г-й итерации уже будет задан список регистров сдвига

предыдущих итераций. Теперь, используя новый многочлен, снова вычислим невязку (обозначим ее Аг)

Д; = I ASr,- = I ArS.-/ + А I Л)"-"5. ; ь

,-=0 /=0 /=0

Теперь все готово для определения величин т, I и А. Выберем т меньше г и такое, что A, 0. Выберем также I = г - т

и Л = -АтАл. Тогда

а; = а,-4д,„ = о,

и, следовательно, новый регистр сдвига будет генерировать последовательность Si, Sr i, S,.. Однако нам нужен не любой такой регистр сдвига, а регистр сдвига с минимальной длиной. У нас остался произвол в выборе т, для которого Д Ф 0. Выбрав в качестве т номер ближайшей итерации, в которой выполнялось условие Lm > m-i. получим в каждой итерации регистр минимальной длины, однако такое усовершенствование требует для своего выполнения дополнительного времени.

Практическая реализация того, что было изложено до настоящего момента, представлена на рис. 7.3. Два регистра сдвига при итерациях т и г изображены на рис. 7.3, а. В качестве т-й итерации выбирается та, при которой регистр сдвига (Lm i, Л"" (х)) не способен генерировать компоненту синдрома S, и минимальная длина регистра сдвига, генерирующего требуемую компоненту синдрома при т-й итерации, больше Lm i. Будем также считать, что регистр сдвига (L,. i, А-) (х)) не способен генерировать Sri в противном случае он остается без изменения.

На рис. 7.3, б регистр сдвига (L-i, АС"-! . превращен во вспомогательный регистр путем увеличения его длины, изменения его связей и такой его перестройки, которая позволяет скомпенсировать неспособность регистра (L,. i, А- (х)) генерировать S,.. Отметим, что вспомогательный регистр имеет дополнительный отвод с весовым множителем единица, соответствующим коэффициенту Лс"\ На протяжении первых г - 1 итераций в остальных отводах цепи обратной связи формируется отрицательное значение этой соответствующей дополнительному отводу величины, и поэтому на выходе вспомогательного регистра формируется последовательность нулей, не оказывающая влияния на генерируемые компоненты синдрома. При г-й итерации эти величины взаимно не уничтожаются, и выход вспомогательного регистра оказывается ненулевым. Коэффициент А выбирается таким образом, чтобы его добавление к г-му выходному сигналу обратной связи главного регистра приводило бы к получению нужной компоненты синдрома Sr.

Рис. 7.3. Конструкция Берлекэмпа-Месси.

На рис. 7.3, в показано, как два регистра сдвига, изображенные на рис. 7.3, б, сливаются в один регистр, что в силу принципа суперпозиции не меняет общего поведения схемы. Это дает регистр (L,., ЛС (л)). Иногда L, = L,, i, иногда > В последнем случае при проведении дальнейших итераций т заменяется на г,