Терминология и общие сведения
Как получить патент на изобретение
Роспатент - методические рекомендации
Международная патентная классификация

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

Классы МПК:G06F7/00 Способы и устройства для обработки данных с воздействием на порядок их расположения или на содержание обрабатываемых данных
Патентообладатель(и):Березин Борис Владимирович
Приоритеты:
подача заявки:
1992-07-20
публикация патента:

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

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

1. СПОСОБ РЕАЛИЗАЦИИ N-РАЗРЯДНОЙ ДВОИЧНОЙ ЛИНЕЙНОЙ РЕКУРРЕНТЫ С ХАРАКТЕРИСТИЧЕСКИМ МНОГОЧЛЕНОМ 1способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xilспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> . . . способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xikспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xn , где 0 < i1 < . . . <i < n на основе суммиpования по модулю 2 состояний pеализующего pекуppенту pегистpа, отличающийся тем, что осуществляют одновpеменный сдвиг pекуppенты на t способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> 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способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xilспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> . . . способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xikспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xnl, где 0 < i1 < . . . < ik < n на основе суммиpования по модулю 2 состояний pеализующего pекуppенту pегистpа, отличающийся тем, что пpи ik способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n/2 осуществляют одновpеменный сдвиг pекуppенты на n - ik способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> t способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n pазpядов, для чего сначала по модулю 2 суммиpуют (k + 1) исходных состояний pеализующего pекуppенту pегистpа, пpедваpительно сдвинутых на 0, i1, . . . , ik pазpядов в стоpону младших pазpядов, затем из полученного п-pазpядного двоичного числа сдвигом на t - n, 2n - t - i1, . . . , 2n - t - i2 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ядов.

Описание изобретения к патенту

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

Известен способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом

1способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310t.gif" ALIGN="ABSMIDDLE"> ... способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-2t.gif" ALIGN="ABSMIDDLE"> xn, 0< i1 < . . . . < ik < n,

путем побитового сдвига n-разрядного двоичного регистра в сторону младших разрядов (с потерей выдвинутых за пределы регистра разрядов) и записи на освободившееся место суммы по модулю два первого, (i1 + 1)-го, . . . , (ik+1)-го битов исходного состояния регистра.

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

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

Цель достигается тем, что при реализации n-разрядной рекурренты осуществляют одновременный сдвиг ее на t способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n-ik разрядов, для чего сначала по модулю два суммируют k+1 исходных состояний реализующего рекурренту регистра, предварительно сдвинутых на 0, i1, . . . , ik разрядов в сторону младших разрядов, затем полученную сумму сдвигают на n-t разрядов в сторону старших разрядов и к результату прибавляют по модулю два исходное состояние регистра, предварительно сдвинутое на t разрядов в сторону младших разрядов.

Цель также может быть достигнута тем, что при ik способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n/2 осуществляют одновременный сдвиг рекурренты на n-ik способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> t способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> 2(n-ik) разрядов, для чего сначала по модулю два суммируют k+1 исходных состояний реализующего рекурренту регистра, предварительно сдвинутых на 0, i1, . . . , ik разрядов в сторону младших разрядов, затем из полученного n-разрядного двоичного числа сдвигом на t-n, 2n-t-i1, . . . , 2n-t-ik разрядов в сторону младших разрядов, если число отрицательное, и в сторону старших разрядов, если число положительное, получают k+1 n-разрядных чисел, которые складывают по модулю два, и к полученной сумме прибавляют по модулю два исходное состояние регистра, сдвинутое на t разрядов в сторону младших разрядов.

Одновременный сдвиг двоичной линейной рекурренты сразу на несколько разрядов осуществляется при помощи операций n-битной логики, причем количество требуемых для этого операций соразмерно с количеством двоичных операций, используемых в известном способе, для сдвига рекуррентны лишь на один разряд. Кроме того, если точки съема на регистре сдвига расположены так, что ik способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n/2, то предлагаемым способом можно сразу сдвинуть рекурренту на n разрядов и полностью обновить ее состояние.

Двоичная линейная рекуррента, задаваемая характеристическим многочленом

1способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-3t.gif" ALIGN="ABSMIDDLE"> ... способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-4t.gif" ALIGN="ABSMIDDLE"> xn, (1) где 0 = i0 < i1 < . . . < ik < n; способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> - сложение по модулю два, переводит текущее состояние

А = (a1, a2, . . . , an), ai = 0,1, i = способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-5t.gif" ALIGN="ABSMIDDLE">,

в следующее состояние:

(a2, . . . , an, a1способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-6t.gif" ALIGN="ABSMIDDLE"> . . . способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-7t.gif" ALIGN="ABSMIDDLE">).

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

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

В течение t способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n-ik тактов работы регистра вновь образованные биты зависят лишь от разрядов исходного состояния А, так как только в (n-ik+1)-й такт новый бит через (ik+1)-ю точку съема задействован в функции обратной связи. Поэтому состояние регистра через t способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE">n-ik тактов работы имеет вид

Atспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-8t.gif" ALIGN="ABSMIDDLE">Aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-9t.gif" ALIGN="ABSMIDDLE">. (2)

Формула (2) задает следующий порядок действий для получения состояния регистра через t тактов. Сначала по модулю два суммируются (k+1) исходных состояний А, предварительно сдвинутых на 0, i1, . . . , ikразрядов в сторону младших разрядов, затем полученная сумма сдвигается на n-t разрядов в сторону старших разрядов и к результату по модулю два прибавляется исходное состояние А, предварительно сдвинутое на t разрядов в сторону младших разрядов. Как видно, в описанной последовательности действий операций с отдельными разрядами нет. Кроме того, сдвигая рекурренту сразу на несколько разрядов, ускоряют в ней процесс обновления информации.

Если выполняется ограничение ik способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE">n/2, то подобным образом рекурренту можно сдвинуть и на n разрядов, т. е. полностью обновить в ней информацию.

Пусть В - состояние рекурренты через n-ik сдвигов, а С - ее состояние через n сдвигов. Тогда в силу (2) справедливы равенства

B= Aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-10t.gif" ALIGN="ABSMIDDLE"> способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-11t.gif" ALIGN="ABSMIDDLE">Aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-12t.gif" ALIGN="ABSMIDDLE">;

C= Bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-13t.gif" ALIGN="ABSMIDDLE"> способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-14t.gif" ALIGN="ABSMIDDLE">Bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-15t.gif" ALIGN="ABSMIDDLE">,

так как ik способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n-ik.

Справедливы равенства

Aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-16t.gif" ALIGN="ABSMIDDLE"> = (способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-17t.gif" ALIGN="ABSMIDDLE">, способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-18t.gif" ALIGN="ABSMIDDLE">);

Aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-19t.gif" ALIGN="ABSMIDDLE"> = (способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-20t.gif" ALIGN="ABSMIDDLE">, способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-21t.gif" ALIGN="ABSMIDDLE">);

(Aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-22t.gif" ALIGN="ABSMIDDLE">)способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-23t.gif" ALIGN="ABSMIDDLE">= (способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-24t.gif" ALIGN="ABSMIDDLE">, 0, . . . , 0способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-25t.gif" ALIGN="ABSMIDDLE">= (O, . . . , 0, способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-26t.gif" ALIGN="ABSMIDDLE">);

(Aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-27t.gif" ALIGN="ABSMIDDLE">)способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-28t.gif" ALIGN="ABSMIDDLE">= (способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-29t.gif" ALIGN="ABSMIDDLE">, 0, . . . , 0)способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-30t.gif" ALIGN="ABSMIDDLE"> = (0, . . . , 0, способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-31t.gif" ALIGN="ABSMIDDLE">);

Bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-32t.gif" ALIGN="ABSMIDDLE">= (способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-33t.gif" ALIGN="ABSMIDDLE">, способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-34t.gif" ALIGN="ABSMIDDLE">);

Bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-35t.gif" ALIGN="ABSMIDDLE">= (способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-36t.gif" ALIGN="ABSMIDDLE">, способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-37t.gif" ALIGN="ABSMIDDLE">);

(Bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-38t.gif" ALIGN="ABSMIDDLE">)способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-39t.gif" ALIGN="ABSMIDDLE">= (способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-40t.gif" ALIGN="ABSMIDDLE">, 0, . . . , 0)способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-41t.gif" ALIGN="ABSMIDDLE">= (0, . . . , 0, способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-42t.gif" ALIGN="ABSMIDDLE">);

(Bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-43t.gif" ALIGN="ABSMIDDLE">)способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-44t.gif" ALIGN="ABSMIDDLE">= (способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-45t.gif" ALIGN="ABSMIDDLE">, 0, . . . , 0)способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-46t.gif" ALIGN="ABSMIDDLE">= (0, . . . , 0, способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-47t.gif" ALIGN="ABSMIDDLE">).

Поэтому b1 = aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-48t.gif" ALIGN="ABSMIDDLE"> ;

. . . . . . . . . . . . . . . . . . . . . . . . . .

bik= an;

bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-49t.gif" ALIGN="ABSMIDDLE">= a1способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-50t.gif" ALIGN="ABSMIDDLE"> . . . способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-51t.gif" ALIGN="ABSMIDDLE">;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

bn= aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-52t.gif" ALIGN="ABSMIDDLE"> aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-53t.gif" ALIGN="ABSMIDDLE"> an;

C1= bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-54t.gif" ALIGN="ABSMIDDLE">= a1способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-55t.gif" ALIGN="ABSMIDDLE"> . . . . способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-56t.gif" ALIGN="ABSMIDDLE">;

. . . . .

Cспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-57t.gif" ALIGN="ABSMIDDLE">= bn= aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-58t.gif" ALIGN="ABSMIDDLE"> aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-59t.gif" ALIGN="ABSMIDDLE"> ... an;

Cспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-60t.gif" ALIGN="ABSMIDDLE">= b1способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-61t.gif" ALIGN="ABSMIDDLE"> ... способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-62t.gif" ALIGN="ABSMIDDLE">; (3)

. . . . .

Cn= bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-63t.gif" ALIGN="ABSMIDDLE"> bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-64t.gif" ALIGN="ABSMIDDLE"> ... способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-65t.gif" ALIGN="ABSMIDDLE">.

Отсюда

b1= aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-66t.gif" ALIGN="ABSMIDDLE">, . . . , bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-67t.gif" ALIGN="ABSMIDDLE">= an; bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-68t.gif" ALIGN="ABSMIDDLE">= c1 , . . . , bспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-69t.gif" ALIGN="ABSMIDDLE">= cспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-70t.gif" ALIGN="ABSMIDDLE"> ,

так как ik способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n-ik.

Следовательно, равенства (3) можно переписать в виде суммы столбцов способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-71t.gif" ALIGN="ABSMIDDLE"> способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-72t.gif" ALIGN="ABSMIDDLE"> способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-73t.gif" ALIGN="ABSMIDDLE"> способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-74t.gif" ALIGN="ABSMIDDLE"> способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-75t.gif" ALIGN="ABSMIDDLE"> =

т. е. через n сдвигов состояние рекуррентны будет

D способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-76t.gif" ALIGN="ABSMIDDLE">Dспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-77t.gif" ALIGN="ABSMIDDLE"> где D= способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-78t.gif" ALIGN="ABSMIDDLE">Aспособ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-79t.gif" ALIGN="ABSMIDDLE"> (4)

Формула (4) задает следующий порядок действий для получения состояния регистра через n тактов. Сначала по модулю два суммируются k+1 исходных состояний А, предварительно сдвинутых на 0, i1, . . . , ik разрядов в сторону младших разрядов. Затем из полученного n-разрядного двоичного числа сдвигом на 0, n-i1, . . . , n-ik разрядов в сторону старших разрядов получают k+1 n-разрядных чисел, складывая которые по модулю два, получают искомое результирующее состояние регистра.

Например, если 127-разрядная рекуррента задается характеристическим многочленом 1 способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> x63способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> x127 , то через 127 тактов ее состояние станет D способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> D-64 , где D = A способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1<img src= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> A63, где А = (а1, . . . , а127) - исходное состояние, т. е. для получения состояния рассматриваемой рекурренты через 127 тактов надо сложить по модулю два исходное состояние с самим собой, сдвинутым на 63 разряда в сторону младших разрядов, а вновь полученное двоичное число снова сложить с самим собой, сдвинутым на 64 разряда в сторону старших разрядов.

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

Класс G06F7/00 Способы и устройства для обработки данных с воздействием на порядок их расположения или на содержание обрабатываемых данных

обнаружение квантового исключения с плавающей десятичной точкой -  патент 2526004 (20.08.2014)
способ перемножения десятичных чисел -  патент 2525477 (20.08.2014)
устройство формирования переноса в сумматоре -  патент 2525111 (10.08.2014)
функциональная структура младшего разряда сумматора fcd( )ru для аргументов слагаемых ±[1,2nj]f(2n) и ±[1,2mj]f(2n) формата "дополнительный код ru" (варианты русской логики) -  патент 2524562 (27.07.2014)
параллельный сумматор-вычитатель на нейронах со сквозным переносом -  патент 2523942 (27.07.2014)
способ формирования логико-динамического процесса преобразования условно минимизированных структур аргументов аналоговых сигналов слагаемых ±[ni]f(+/-)min и ±[mi]f(+/-)min в функциональной структуре сумматора ±f1( ru)min без сквозного переноса f1(± ) и технологическим циклом t 5 f(&)-и пять условных логических функций f(&)-и, реализованный с применением процедуры одновременного преобразования аргументов слагаемых посредством арифметических аксиом троичной системы счисления fru(+1,0,-1) и функциональные структуры для его реализации (вариант русской логики) -  патент 2523876 (27.07.2014)
устройство фильтрации динамических цифровых изображений в условиях ограниченного объема априорных данных -  патент 2522043 (10.07.2014)
способ и аппаратура для обеспечения поддержки альтернативных вычислений в реконфигурируемых системах-на-кристалле -  патент 2519387 (10.06.2014)
логический преобразователь -  патент 2518669 (10.06.2014)
логический преобразователь -  патент 2517720 (27.05.2014)