Генератор псевдослучайных чисел Советский патент 1991 года по МПК G06F7/58 

Изобретение относится к вычислительной технике и может быть использовано при статистическом моделировании, решении задач методом Монте-Карло.

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

На фиг. 1 представлена блок-схема генератора псевдослучайных чисел, на фиг. 2-4 - примеры возможных вариантов конкретных конфигураций генераторов и корреляционные функции генерируемых последовательностей.

Генератор псевдослучайных чисел содержит группу из D-триггеров 1j. (j T7n), группу из п элементов И 2j, группу из п сумматоров 3 J по модулю два, группу из п элементов 4; задержки, задатчик 5 характеристик генерируемой последовательности, дополнительную группу из п. элементов И 6j, многовходовый сумматор 7 по модулю два, выходы 8 генератора.

Кроме того, на фиг.2а и 4а изображены Т-триггеры 9.

СП

В основе работы генератора лежит метод формирования псевдослу-, . чайных двоичных последовательностей, основанный на использовании регистра сдвига с сумматорами по модулю два

в цепи обратной связи. Свойства любого такого генератора могут быть описаны с помощью характеристического многочлена вида:

Ср(х) х © xf, x © ... .,.+ tf n-i © 1,

где коэффициенты р(к (k 1,2, k-1) принимают значения 0 или 1, причем значение 1 соответствует использованию k-ro разряда регистра сдвига в организации цепи обратной связи, п - число разрядов генератора; ф знак суммирования по модулю два.

В генераторе D-триггер 1J, элемент И 21, сумматор по модулю два 3j и элемент задержки 4: соответствующих групп элементов в совокупности образуют управляемый триггер, который при подаче на первый вход элемента И сигнала 1 с первой группы выходов задатчика характеристик генерируемой последовательности работает в режи- ме Т-триггера. Известно, что замена в регистре сдвига D-триггера на Т- триггер приводит к изменению характеристического многочлена, причем это изменение сводится к замене функции х на (х ® 1 ).

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

Генератор работает следующим об - разом..

Предварительно в задатчик характеристик генерируемой последовательности вводится информация, определяющая вид обратной связи и режим работ триггеров регистра сдвига. Кроме того триггеры устанавливаются в некоторое начальное (ненулевое) состояние (цепи установки и синхронизации на фиг.1 не показаны). С приходом каждого очередного тактбвого импульса генератор переходит в следующее состояние.

На фиг.2а-4а приведены образцы вариантов конкретных конфигураций генераторов, которые получаются при записи определенных кодовых комбинаций в задатчик характеристик генерируемой последовательности, на фиг.2б-4б - антикорреляционные функции этих последовательностей. Во всех случаях принято п 7.

Структура генератора, представленная на фиг.2, образуется, когда на выходах первой группы задатчика 5 имеют место сигналы 1, 1, 1, 1, 1, 1, 1, так что элементы 9, 92... ...97 представляют собой Т-триггеры; при этом на второй группе выходов присутствует кодовая комбинация 1, 1, 1, 1, 1, 0, 1„ Структура генератора, изображенная на фиг. 3, имеет место при следующих кодовых комбинациях на выходах задатчика 5: на выходах первой группы О, О, О, О, О, О, 0, на выходах второй группы О, О, О, О, О, 1, 1. Аналогично для получения генератора со структурой, представленной на фиг.4, должны быть заданы кодовые комбинации, на выходах первой группы выходов задатчика О, О, О, О, 1, 1, 1, на выходах второй группы 0, 0, 1, 1, 1, 0, 1.

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

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

Генератор псевдослучайных чисел, содержащий группу из п (п - число разрядов генератора) D-триггеров, группу из п элементов И, группу из п элементов задержки, группу из п сумматоров по модулю два, задатчик характеристик генерируемой последовательности чисел, первая группа выходов которого соединена с первыми входами элементов И группы, выход каждого i-ro(i 1,n) элемента И группы соединен с первым входом 1-го сумматора по модулю два группы, выход которого соединен с установочным входом 1-го D-триггера группы, Прямой выход которого соединен с входом 1-го элемента задержки, выход которого является выходом 1-го разряда генератора и соединен с вторыми входами 1-го элемента И группы и (i+0-го сумматора по модулю два, отличающийся тем, что, с целью расширения количества вариантов генерируемых последова

Изобретение относится к вычислительной технике и может быть использовано при статистическом моделировании, решении задач методом Монте-Карло. Цель изобретения - расширение количества вариантов генерируемых псевдослучайных последовательностей и управление их корреляци- онными свойствами. Генератор псевдослучайных: чисел содержит группу из п (п - число разрядов генератора) D-триггеров, группу из п элементов И, группу из п элементов задержки, группу из п сумматоров по модулю два, задатчик характеристик генерируемой последовательности, дополнительную группу из п элементов И и многовходовой сумматор по модулю два. Цель изобретения достигается введением дополнительной группы из п элементов И и многовходового сумматора по модулю два с соответствующими соединениями, что позволяет формировать различные псевдослучайные последовательности при одновременном управлении их автокорреляционными- функциями. 4 ил. $

9 9

4 5

10 Фиг. 2

Фиг.З

О 1

4 5

ff

10

Фаг. 4