Способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1 xi1 ... xik xn

Способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1 xi1 ... xik xn

Реферат

 

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

Изобретение относится к вычислительной технике и может быть использовано при реализации двоичных линейных реку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= A A; C= B B, так как 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.

Формула изобретения

1. СПОСОБ РЕАЛИЗАЦИИ N-РАЗРЯДНОЙ ДВОИЧНОЙ ЛИНЕЙНОЙ РЕКУРРЕНТЫ С ХАРАКТЕРИСТИЧЕСКИМ МНОГОЧЛЕНОМ 1 xⁱl . . . xⁱk xⁿ , где 0 < i₁ < . . . <i _{< n на основе суммиpования по модулю 2 состояний pеализующего pекуppенту pегистpа, отличающийся тем, что осуществляют одновpеменный сдвиг pекуppенты на t n - ik pазpядов, для чего сначала по модулю 2 суммиpуют (k + 1) исходных состояний pеализующего pекуppенту pегистpа, пpедваpительно сдвинутых на 0, i1, . . . , ik 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ядов.