способ реализации n-разрядной двоичной линейной рекурренты с характеристическим многочленом 1 xi1 ... xik xn
Классы МПК: | G06F7/00 Способы и устройства для обработки данных с воздействием на порядок их расположения или на содержание обрабатываемых данных |
Патентообладатель(и): | Березин Борис Владимирович |
Приоритеты: |
подача заявки:
1992-07-20 публикация патента:
30.03.1994 |
Изобретение относится к вычислительной технике и может быть использовано при реализации двоичных линейных рекуррент на элементной базе, ориентированной на многозначную логику. Данным способом n-разрядная двоичная линейная рекуррента одновременно сдвигается сразу на несколько разрядов с использованием операций n-битной логики. При этом количество требуемых n-битных операций для сдвига рекурренты сразу на несколько разрядов соразмерно с количеством двоичных операций, необходимых для сдвига рекурренты лишь на один разряд. В ряде случаев данным способом можно сразу сдвинуть рекурренту на n разрядов и полностью обновить ее состояние. 1 з. п. ф-лы.
Формула изобретения
1. СПОСОБ РЕАЛИЗАЦИИ N-РАЗРЯДНОЙ ДВОИЧНОЙ ЛИНЕЙНОЙ РЕКУРРЕНТЫ С ХАРАКТЕРИСТИЧЕСКИМ МНОГОЧЛЕНОМ 1 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xil xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> . . . xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xik 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 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 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xil xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> . . . xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xik 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 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n/2 осуществляют одновpеменный сдвиг pекуppенты на n - ik xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> t 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 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> x xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310t.gif" ALIGN="ABSMIDDLE"> ... xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> x 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 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n-ik разрядов, для чего сначала по модулю два суммируют k+1 исходных состояний реализующего рекурренту регистра, предварительно сдвинутых на 0, i1, . . . , ik разрядов в сторону младших разрядов, затем полученную сумму сдвигают на n-t разрядов в сторону старших разрядов и к результату прибавляют по модулю два исходное состояние регистра, предварительно сдвинутое на t разрядов в сторону младших разрядов. Цель также может быть достигнута тем, что при ik xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n/2 осуществляют одновременный сдвиг рекурренты на n-ik xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> t 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 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n/2, то предлагаемым способом можно сразу сдвинуть рекурренту на n разрядов и полностью обновить ее состояние. Двоичная линейная рекуррента, задаваемая характеристическим многочленом
1 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> x xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-3t.gif" ALIGN="ABSMIDDLE"> ... xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> x xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-4t.gif" ALIGN="ABSMIDDLE"> xn, (1) где 0 = i0 < i1 < . . . < ik < n; xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> - сложение по модулю два, переводит текущее состояние
А = (a1, a2, . . . , an), ai = 0,1, i = xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-5t.gif" ALIGN="ABSMIDDLE">,
в следующее состояние:
(a2, . . . , an, a1 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> a xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-6t.gif" ALIGN="ABSMIDDLE"> . . . xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> a 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 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n-ik тактов работы регистра вновь образованные биты зависят лишь от разрядов исходного состояния А, так как только в (n-ik+1)-й такт новый бит через (ik+1)-ю точку съема задействован в функции обратной связи. Поэтому состояние регистра через t xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE">n-ik тактов работы имеет вид
At xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-8t.gif" ALIGN="ABSMIDDLE">A 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 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE">n/2, то подобным образом рекурренту можно сдвинуть и на n разрядов, т. е. полностью обновить в ней информацию. Пусть В - состояние рекурренты через n-ik сдвигов, а С - ее состояние через n сдвигов. Тогда в силу (2) справедливы равенства
B= A xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-10t.gif" ALIGN="ABSMIDDLE"> xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-11t.gif" ALIGN="ABSMIDDLE">A xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-12t.gif" ALIGN="ABSMIDDLE">;
C= B xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-13t.gif" ALIGN="ABSMIDDLE"> xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-14t.gif" ALIGN="ABSMIDDLE">B xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-15t.gif" ALIGN="ABSMIDDLE">,
так как ik xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n-ik. Справедливы равенства
A xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-16t.gif" ALIGN="ABSMIDDLE"> = ( xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-17t.gif" ALIGN="ABSMIDDLE">, xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-18t.gif" ALIGN="ABSMIDDLE">);
A xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-19t.gif" ALIGN="ABSMIDDLE"> = ( xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-20t.gif" ALIGN="ABSMIDDLE">, xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-21t.gif" ALIGN="ABSMIDDLE">);
(A xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-22t.gif" ALIGN="ABSMIDDLE">) xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-23t.gif" ALIGN="ABSMIDDLE">= ( xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-24t.gif" ALIGN="ABSMIDDLE">, 0, . . . , 0 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-25t.gif" ALIGN="ABSMIDDLE">= (O, . . . , 0, xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-26t.gif" ALIGN="ABSMIDDLE">);
(A xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-27t.gif" ALIGN="ABSMIDDLE">) xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-28t.gif" ALIGN="ABSMIDDLE">= ( xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-29t.gif" ALIGN="ABSMIDDLE">, 0, . . . , 0) xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-30t.gif" ALIGN="ABSMIDDLE"> = (0, . . . , 0, xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-31t.gif" ALIGN="ABSMIDDLE">);
B xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-32t.gif" ALIGN="ABSMIDDLE">= ( xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-33t.gif" ALIGN="ABSMIDDLE">, xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-34t.gif" ALIGN="ABSMIDDLE">);
B xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-35t.gif" ALIGN="ABSMIDDLE">= ( xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-36t.gif" ALIGN="ABSMIDDLE">, xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-37t.gif" ALIGN="ABSMIDDLE">);
(B xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-38t.gif" ALIGN="ABSMIDDLE">) xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-39t.gif" ALIGN="ABSMIDDLE">= ( xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-40t.gif" ALIGN="ABSMIDDLE">, 0, . . . , 0) xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-41t.gif" ALIGN="ABSMIDDLE">= (0, . . . , 0, xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-42t.gif" ALIGN="ABSMIDDLE">);
(B xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-43t.gif" ALIGN="ABSMIDDLE">) xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-44t.gif" ALIGN="ABSMIDDLE">= ( xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-45t.gif" ALIGN="ABSMIDDLE">, 0, . . . , 0) xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-46t.gif" ALIGN="ABSMIDDLE">= (0, . . . , 0, xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-47t.gif" ALIGN="ABSMIDDLE">). Поэтому b1 = a xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-48t.gif" ALIGN="ABSMIDDLE"> ;
. . . . . . . . . . . . . . . . . . . . . . . . . . bik= an;
b xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-49t.gif" ALIGN="ABSMIDDLE">= a1 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> a xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-50t.gif" ALIGN="ABSMIDDLE"> . . . xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> a xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-51t.gif" ALIGN="ABSMIDDLE">;
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . bn= a xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-52t.gif" ALIGN="ABSMIDDLE"> a xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-53t.gif" ALIGN="ABSMIDDLE"> an;
C1= b xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-54t.gif" ALIGN="ABSMIDDLE">= a1 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> a xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-55t.gif" ALIGN="ABSMIDDLE"> . . . . xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> a xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-56t.gif" ALIGN="ABSMIDDLE">;
. . . . . C xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-57t.gif" ALIGN="ABSMIDDLE">= bn= a xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-58t.gif" ALIGN="ABSMIDDLE"> a xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-59t.gif" ALIGN="ABSMIDDLE"> ... an;
C xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-60t.gif" ALIGN="ABSMIDDLE">= b1 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> b xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-61t.gif" ALIGN="ABSMIDDLE"> ... xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> b xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-62t.gif" ALIGN="ABSMIDDLE">; (3)
. . . . . Cn= b xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-63t.gif" ALIGN="ABSMIDDLE"> b xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-64t.gif" ALIGN="ABSMIDDLE"> ... xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> b xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-65t.gif" ALIGN="ABSMIDDLE">. Отсюда
b1= a xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-66t.gif" ALIGN="ABSMIDDLE">, . . . , b xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-67t.gif" ALIGN="ABSMIDDLE">= an; b xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-68t.gif" ALIGN="ABSMIDDLE">= c1 , . . . , b xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-69t.gif" ALIGN="ABSMIDDLE">= c xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-70t.gif" ALIGN="ABSMIDDLE"> ,
так как ik xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010004/8773.gif" ALIGN="ABSMIDDLE"> n-ik. Следовательно, равенства (3) можно переписать в виде суммы столбцов xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-71t.gif" ALIGN="ABSMIDDLE"> xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-72t.gif" ALIGN="ABSMIDDLE"> xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-73t.gif" ALIGN="ABSMIDDLE"> xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-74t.gif" ALIGN="ABSMIDDLE"> xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-75t.gif" ALIGN="ABSMIDDLE"> =
т. е. через n сдвигов состояние рекуррентны будет
D xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-76t.gif" ALIGN="ABSMIDDLE">D xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-77t.gif" ALIGN="ABSMIDDLE"> где D= xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/2010310-78t.gif" ALIGN="ABSMIDDLE">A 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 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> x63 xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> x127 , то через 127 тактов ее состояние станет D xi1 ... xik xn, патент № 2010310" SRC="/images/patents/463/2010310/8853.gif" ALIGN="ABSMIDDLE"> D-64 , где D = A 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 Способы и устройства для обработки данных с воздействием на порядок их расположения или на содержание обрабатываемых данных