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

Теорема 7.4.1 (алгоритм Берлекэмпа-Месси). Пусть заданы Si,..., Sit ti3 некоторого поля, и пусть при начальных условиях Л(° (х) = 1, В° (х) = 1 и = О выполняются следующие рекуррентные "равенства, используемые для вычисления Af (х):

L, б. С- - lr-i) -Ь (1 - ) Lr „

А<о (X) Вх)

1 -Д,х ДГб. (1 -б,)х

Л(-)(х) В-> (х)

г == \ , 2t, где б;. = 1, если одновременно ф О и 2Lr ] <: <: г - 1, и 6,. - О в противном случае. Тогда Л*- (х) является многочленом наименьшей степени, коэффициенты которого удовлетворяют равенствам t\f* = \ и

Sr + I AfSr-s - О, г = L2, + 1.....2t.

В этой теореме Д,. может равняться нулю, но только в том случае, когда б = 0. Положим тогда по определению Дб, = 0.

В каждой итерации для умножения матриц требуется не более 2t умножений, а для вычисления Д,. - не более t умножений. Всего производится 2t итераций, так что делается не более 6 умножений. Следовательно, использование этого алгоритма обычно эффективнее обращения матрицы, в котором требуется порядка f операций.

Доказательство теоремы 7.4.1 сводится к двум приведенным ниже леммам. Сначала в лемме 7.4.2 находится неравенство, связывающее L,. и L,. i. Затем в лемме 7.4.3 используется указанный в теореме 7.4.1 алгоритм для построения по регистру сдвига минимальной длины, генерирующему последовательность Si, S,. i, регистра сдвига, генерирующего последовательность Si, S,.. Из леммы 7.4.3 будет следовать, что вытекающее из теоремы 7.4.1 построение приводит к регистру сдвига минимальной длины, поскольку его параметры будут удовлетворять границе из леммы 7.4.2.

Лемма 7.4.2. Пусть (L.i, Ac-i (х)) - регистр сдвига с линейной обратной связью минимальной длины, генерирующий ПОС4едовап1ельносп].ь S, Si, а {L, Л"" (х)) - регистр сдвига

Sj-hbuSj u, / = L fl, Теперь установим противоречие. С одной стороны,

Sr = - ZI b]iSr h = 2j 2] CjSr..fj b k=\ li=l 1=1

где справедливость разложения S,. k следует из того, что г - k пробегает содержащиеся среди чисел L + 1, г- 1 целые значения от г - 1 до г - L, поскольку по предположению fL-\-L-{-l.C другой стороны,

где справедливость разложения S,. i следует из.того, что r - i пробегает содержащиеся среди чисел L + l,..-,r - 1 целые значения от г - 1 до г - L, а это опять следует из.предположения г L + L + 1. Изменение порядка суммирования в пра-

с линейной связью минимальной длины, генерируюший S, S,., и Л() (х) Ф Л(-) (х). Тогда

max [Lr :, г - L,. i].

Доказательство. Неравенство, которое требуется доказать, разбивается на два неравенства:

Lr i и L,.r - L,. i.

Первое неравенство очевидно, поскольку если регистр сдвига с линейной обратной связью генерирует некоторую последовательность, то он генерирует и любую меньшую последовательность, являющуюся началом исходной. Если L,. ] г, то второе неравенство также становится очевидным. Поэтому предположим, что Lr i < / и что второе неравенство не выполняется, и попытаемся прийти к противоречию. Из предположения следует, что Lr < г - 1 - Lr i. Для сокращения записи введем следующие обозначения- с {х) = Л(- (х), b (х) = Л* (х), L = Lj и L = Lr- В новых обозначениях исходные предположения примут вид rLL-r 1 W. L< г. Кроме того, из условий леммы следует, что

гФ - 2] CiSr.i,

Sj-ljCtSjt, / = L + 1,..../--1,

(=1 {=0

о, == Lr i,. . 1,

Дг, / = г.

вой части последнего равенства приводит к выражению для S,., полученному в правой части предыдущего равенства. Таким образом, получаем доказывающее лемму противоречие S,. Ф S. □

Если удастся построить регистр сдвига с длиной, удовлетворяющей соотношению из леммы 7.4.2 с заменой знака нестрогого неравенства знаком равенства, то тем самым будет построен регистр минимальной длины. Следующая лемма показывает, что такое построение дается теоремой 7.4.1.

Лемма 7.4.3. Предположим, что (Li, А (х)), i = I, г,

является последовательностью регистров сдвига минимальной длины с линейной обратной связью, таких, что Л (х) генерирует Sy, Si. Если Л(0 (х) Ф Л"-) (х), то

Lr = max [L,. i, г -

и любой регистр сдвига, генерируюиий Sy, S,. и имеющий длину, совпадающую с величиной правой части последнего равенства, является регистром сдвига минимальной длины. Такой регистр сдвига определяется теоремой 7.4.1.

Доказательство. Согласно лемме 7.4.2, не может быть меньше величины в правой части последнего равенства. Если удастся построить какой-либо регистр сдвига, который генерирует требуемую последовательность и длина которого совпадает с указанной величиной, то он будет регистром сдвига минимальной длины. Доказательство будет проводиться по индукции. Мы построим регистр сдвига, удовлетворяющий теореме, в предположении, что такие регистры последовательно построены для всех k г - 1. Для каждого k, k = \, г - 1, будем обозначать через (Lfc, Л* (х)) регистр сдвига минимальной длины, генерирующий Sy, S,i. Примем за предположение индукции, что

Lfc = max [Lft i, k - Lfe ,l, k= 1,..., n - 1,

каждый раз, когда Л/ (х) Ф ЛС (х). Это верно для k = О, поскольку == О и Li = 1. Значение k в последней итерации, приведшей к изменению длины, будем обозначать через т. Последнее означает, что при завершении (г - 1)-й итерации пг является целым числом, таким, что

Теперь имеет место следующее равенство: