СПОСОБ РЕАЛИЗАЦИИ N-РАЗРЯДНОЙ ДВОИЧНОЙ ЛИНЕЙНОЙ РЕКУРРЕНТЫ С ХАРАКТЕРИСТИЧЕСКИМ МНОГОЧЛЕНОМ 1⊕ x1⊕ ...⊕ xk⊕ x Российский патент 1994 года по МПК G06F7/00 

Изобретение относится к вычислительной технике и может быть использовано при реализации двоичных линейных рекуpрент на элементной базе, ориентированной на многозначную логику.

Известен способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом
1⊕ x ... ⊕ x xⁿ, 0< i₁ < . . . . < i_k < n,
путем побитового сдвига n-разрядного двоичного регистра в сторону младших разрядов (с потерей выдвинутых за пределы регистра разрядов) и записи на освободившееся место суммы по модулю два первого, (i₁ + 1)-го, . . . , (i_k+1)-го битов исходного состояния регистра.

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

Целью изобретения является ускорение процесса работы рекурренты и исключение при этом операций над отдельными битами.

Цель достигается тем, что при реализации n-разрядной рекурренты осуществляют одновременный сдвиг ее на t ≅ n-i_k разрядов, для чего сначала по модулю два суммируют k+1 исходных состояний реализующего рекурренту регистра, предварительно сдвинутых на 0, i1, . . . , i_k разрядов в сторону младших разрядов, затем полученную сумму сдвигают на n-t разрядов в сторону старших разрядов и к результату прибавляют по модулю два исходное состояние регистра, предварительно сдвинутое на t разрядов в сторону младших разрядов.

Цель также может быть достигнута тем, что при i_k ≅ n/2 осуществляют одновременный сдвиг рекурренты на n-i_k ≅ t ≅ 2(n-i_k) разрядов, для чего сначала по модулю два суммируют k+1 исходных состояний реализующего рекурренту регистра, предварительно сдвинутых на 0, i₁, . . . , i_k разрядов в сторону младших разрядов, затем из полученного n-разрядного двоичного числа сдвигом на t-n, 2n-t-i₁, . . . , 2n-t-i_k разрядов в сторону младших разрядов, если число отрицательное, и в сторону старших разрядов, если число положительное, получают k+1 n-разрядных чисел, которые складывают по модулю два, и к полученной сумме прибавляют по модулю два исходное состояние регистра, сдвинутое на t разрядов в сторону младших разрядов.

Одновременный сдвиг двоичной линейной рекурренты сразу на несколько разрядов осуществляется при помощи операций n-битной логики, причем количество требуемых для этого операций соразмерно с количеством двоичных операций, используемых в известном способе, для сдвига рекуррентны лишь на один разряд. Кроме того, если точки съема на регистре сдвига расположены так, что i_k ≅ n/2, то предлагаемым способом можно сразу сдвинуть рекурренту на n разрядов и полностью обновить ее состояние.

Двоичная линейная рекуррента, задаваемая характеристическим многочленом
1⊕ x ... ⊕ x xⁿ, (1) где 0 = i₀ < i₁ < . . . < i_k < n; ⊕ - сложение по модулю два, переводит текущее состояние
А = (a₁, a₂, . . . , a_n), a_i = 0,1, i = ,
в следующее состояние:
(a₂, . . . , a_n, a₁⊕ a . . . ⊕ a).

Обозначим через A^t n-разрядное двоичное число, полученное путем сдвига А на t разрядов в сторону младших разрядов с потерей выдвинутых разрядов. Старшие t разрядов числа A^t нулевые.

Обозначим через A^-t n-разрядное двоичное число, полученное путем сдвига А на t разрядов в сторону старших разрядов с потерей выдвинутых разрядов. Младшие t разрядов числа A^-t нулевые. Очевидно, что Aⁿ и A^-n - n-разрядные нули.

В течение t ≅ n-i_k тактов работы регистра вновь образованные биты зависят лишь от разрядов исходного состояния А, так как только в (n-i_k+1)-й такт новый бит через (i_k+1)-ю точку съема задействован в функции обратной связи. Поэтому состояние регистра через t ≅n-i_k тактов работы имеет вид
A^t⊕ A. (2)
Формула (2) задает следующий порядок действий для получения состояния регистра через t тактов. Сначала по модулю два суммируются (k+1) исходных состояний А, предварительно сдвинутых на 0, i₁, . . . , i_kразрядов в сторону младших разрядов, затем полученная сумма сдвигается на n-t разрядов в сторону старших разрядов и к результату по модулю два прибавляется исходное состояние А, предварительно сдвинутое на t разрядов в сторону младших разрядов. Как видно, в описанной последовательности действий операций с отдельными разрядами нет. Кроме того, сдвигая рекурренту сразу на несколько разрядов, ускоряют в ней процесс обновления информации.

Если выполняется ограничение i_k ≅n/2, то подобным образом рекурренту можно сдвинуть и на n разрядов, т. е. полностью обновить в ней информацию.

Пусть В - состояние рекурренты через n-i_k сдвигов, а С - ее состояние через n сдвигов. Тогда в силу (2) справедливы равенства
B= AA;
C= BB,
так как i_k ≅ n-i_k.

Справедливы равенства
A = (, );
A = (, );
(A)= (, 0, . . . , 0= (O, . . . , 0, );
(A)= (, 0, . . . , 0) = (0, . . . , 0, );
B= (, );
B= (, );
(B)= (, 0, . . . , 0)= (0, . . . , 0, );
(B)= (, 0, . . . , 0)= (0, . . . , 0, ).

Поэтому b₁ = a ;
. . . . . . . . . . . . . . . . . . . . . . . . . .

b_ik= a_n;
b= a₁⊕ a . . . ⊕ a;
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

b_n= a a a_n;
C₁= b= a₁⊕ a . . . . ⊕ a;
. . . . .

C= b_n= a a ... a_n;
C= b₁⊕ b ... ⊕ b; (3)
. . . . .

C_n= b b ... ⊕ b.

Отсюда
b₁= a, . . . , b= a_n; b= c₁ , . . . , b= c ,
так как i_k ≅ n-i_k.

Следовательно, равенства (3) можно переписать в виде суммы столбцов ₌
т. е. через n сдвигов состояние рекуррентны будет
D D где D= A (4)
Формула (4) задает следующий порядок действий для получения состояния регистра через n тактов. Сначала по модулю два суммируются k+1 исходных состояний А, предварительно сдвинутых на 0, i₁, . . . , i_k разрядов в сторону младших разрядов. Затем из полученного n-разрядного двоичного числа сдвигом на 0, n-i₁, . . . , n-i_k разрядов в сторону старших разрядов получают k+1 n-разрядных чисел, складывая которые по модулю два, получают искомое результирующее состояние регистра.

Например, если 127-разрядная рекуррента задается характеристическим многочленом 1 ⊕ x⁶³⊕ x¹²⁷ , то через 127 тактов ее состояние станет D ⊕ D^-64 , где D = A ⊕ A⁶³, где А = (а₁, . . . , а₁₂₇) - исходное состояние, т. е. для получения состояния рассматриваемой рекурренты через 127 тактов надо сложить по модулю два исходное состояние с самим собой, сдвинутым на 63 разряда в сторону младших разрядов, а вновь полученное двоичное число снова сложить с самим собой, сдвинутым на 64 разряда в сторону старших разрядов.

(56) Гили А. Линейные последовательностные машины. М. : Наука, 1974, с. 41-45.

Изобретение относится к вычислительной технике и может быть использовано при реализации двоичных линейных рекуррент на элементной базе, ориентированной на многозначную логику. Данным способом n-разрядная двоичная линейная рекуррента одновременно сдвигается сразу на несколько разрядов с использованием операций n-битной логики. При этом количество требуемых n-битных операций для сдвига рекурренты сразу на несколько разрядов соразмерно с количеством двоичных операций, необходимых для сдвига рекурренты лишь на один разряд. В ряде случаев данным способом можно сразу сдвинуть рекурренту на n разрядов и полностью обновить ее состояние. 1 з. п. ф-лы.

1. СПОСОБ РЕАЛИЗАЦИИ N-РАЗРЯДНОЙ ДВОИЧНОЙ ЛИНЕЙНОЙ РЕКУРРЕНТЫ С ХАРАКТЕРИСТИЧЕСКИМ МНОГОЧЛЕНОМ 1⊕ xⁱl⊕ . . . ⊕ xⁱk⊕ xⁿ , где 0 < i₁ < . . . <i_k < n на основе суммиpования по модулю 2 состояний pеализующего pекуppенту pегистpа, отличающийся тем, что осуществляют одновpеменный сдвиг pекуppенты на t ≅ n - i_k pазpядов, для чего сначала по модулю 2 суммиpуют (k + 1) исходных состояний pеализующего pекуppенту pегистpа, пpедваpительно сдвинутых на 0, i₁, . . . , i_k pазpядов в стоpону младших pазpядов, затем полученную сумму сдвигают на (n - t) pазpядов в стоpону стаpших pазpядов и к pезультату пpибавляют по модулю 2 исходное состояние pегистpа, пpедваpительно сдвинутое на t pазpядов в стоpону младших pазpядов. 2. Способ pеализации n-pазpядной двоичной линейной pекуppенты с хаpактеpистическим многочленом 1⊕ xⁱl⊕ . . . ⊕ xⁱk⊕ xⁿl, где 0 < i₁ < . . . < i_k < n на основе суммиpования по модулю 2 состояний pеализующего pекуppенту pегистpа, отличающийся тем, что пpи i_k ≅ n/2 осуществляют одновpеменный сдвиг pекуppенты на n - i_k ≅ t ≅ n pазpядов, для чего сначала по модулю 2 суммиpуют (k + 1) исходных состояний pеализующего pекуppенту pегистpа, пpедваpительно сдвинутых на 0, i₁, . . . , i_k pазpядов в стоpону младших pазpядов, затем из полученного п-pазpядного двоичного числа сдвигом на t - n, 2n - t - i₁, . . . , 2n - t - i₂ pазpядов в стоpону младших pазpядов, если число отpицательное, и в стоpону стаpших pазpядов, если число положительное, получают (k + 1) n-pазpядных чисел, котоpые складывают по модулю 2 и к полученной сумме пpибавляют по модулю 2 исходное состояние pегистpа, сдвинутое на t pазpядов в стоpону младших pазpядов.