Невязка $δ$ в алгоритме Берлекэмпа-Месси

У меня есть вопрос относительно Алгоритм Берлекампа-Месси. Может ли кто-нибудь помочь мне понять идею/интуицию этого алгоритма?

Согласно пояснению в Википедия, на каждой итерации алгоритм пытается вычислить невязку $δ$.

Если $δâ 0$, алгоритм обновит полином локатора ошибок, используя полином обновления $В(х)$. Однако на данный момент я знаю, что результирующий полином локатора ошибок сделает $δ$ в текущей итерации становятся равными нулю. Но как насчет всех $δ$ в предыдущих итерациях? Очень трудно представить себе, что алгоритм на самом деле делает все предыдущие $δ=0$.

На самом деле BMA — это рекурсивный алгоритм, и несоответствие $$d_{n+1}=\шляпа{s}_{n+1}-s_{n+1}$$это разница между

• Какой текущий полином $ С ^ {\ {п \}} $ определяется BMA на основе последовательности $(s_0,\cdots,s_n)$ предсказывает как следующий символ $\шляпа{s}_{n+1}$, и
• Фактический символ $s_{n+1}$.

Это то, что используется для обновления полинома при необходимости. Тогда по индукции все невязки равны нулю.

Алгоритм Берлекампа-Месси представляет собой процедуру для LFSR. синтез; Это. находит самый короткий LFSR, который создаст данную последовательность $s_0, s_1, s_2, \cdots$. Алгоритм повторяющийся (не рекурсивный, так как он не вызывает сам себя) в том, что он проверяет последовательность по одному символу за раз, пока не обработает всю заданную последовательность. В конце $я$-я итерация, алгоритм рассмотрел $s_0, s_1, \cdots, s_{i-1}$ (осмотр $s_i, s_{i+1}, \cdots$ еще впереди) и синтезировал самый короткий LFSR, который будет генерировать $s_0, s_1, \cdots, s_{i-1}$. Затем, в начале $(я+1)$-я итерация, алгоритм определяет, является ли $s_i$ будет сгенерирован LFSR, который он только что нашел, вычислив, что следующий вывод $\шляпа{s}_i$ будет из только что синтезированного LFSR, и сравнив его с тем, что мы хочу LFSR для генерации, а именно данный $s_i$. Разница называется несоответствие $\delta_i$ и если $\delta_i$ оказывается ненулевым, т. ранее-синтезированный LFSR обновлен так что обновленный LFSR будет вычислять $s_0, s_1, \cdots, s_{i-1}, {\mathbf s_i}$ (выделение добавлено). Это обновление может увеличить длину LFSR, а также изменить ответвления обратной связи или просто изменить ответвления обратной связи. Можно доказать, что если итерация привела к увеличению длины LFSR и изменению отводов, то на следующей итерации могли измениться только отводы обратной связи; LFSR не может увеличиваться в длину.

Короче говоря, не нужно беспокоиться о том, что произойдет с предыдущими несоответствиями; текущий LFSR гарантированно сгенерирует всю изученную до сих пор последовательность без каких-либо расхождений в процессе генерации.