Генератор псевдослучайных чисел

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

„„SU„„1631541 ц))$ G 06 F 7/58

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4677215/24 . (22) 13.03.89 (46} 28.02.91. Бюл. М 8 (72) О.И.Далин и А.С.Медведев (53) 68 1.30(088.8) (56) Авторское свидетельство СССР

У 468231, кл. G 06 F 7/58, 1973.

Авторское свидетельство СССР

Р 1280619, кл. G 06 Г 7/58, 1982. (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ

ЧИСЕЛ (57} Изобретение относится к вычислительной технике и может быть использовано при статистическом моделировании, решении задач методом

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

Монте-Карло.

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

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

D-триггеров, группу из и элементов

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

Генератор псевдослучайных чисел содержит группу из D-триггеров 1 (j = 1,n), группу из и элементов И 21, группу из и сумматоров 3 по модулю два, группу из п элементов 4 saдержки, задатчик 5 характеристик генерируемой последовательности, дополнительную группу из и. элементов

И 6, многовходовый сумматор 7 по модулю два, выходы 8 генератора.

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

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

И-!

Ц)(х) х О+ С(,х Я... ...+М,Х Q+1, где коэффициенты P(„(k = 1,2, k-1) принимают значения О или 1, причем значение 0(» " 1 соответствует использованию k-ro разряда регистра сдвига в организации цепи обратной связи, n — число разрядов генератора; ® знак суммирования по модулю два.

В генераторе D-триггер 1, элемент И 2, сумматор по модулю два 3 и элемент задержки 41 соответствующих групп элементов в совокупности образуют управляемый триггер, который при подаче на первый вход элемента И сигнала "1" с первой группы выходов задатчика характеристик генерируемой последовательности работает в режиме Т-триггера. Известно, что замена в регистре сдвига D-триггера на Ттриггер приводит к изменению характеристического многочлена, причем это изменение сводится к замене функ-gp ции х> на (х Q 11).

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

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

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

55 переходит в следующее состояние.

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

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

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

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

И дополнительной группы, второй вход каждого i-ro элемента И дополнительной группы соединен с выходом

i-ro элемента задержки группы а

ВЫХОД вЂ” С 1-М ВХОДОМ МНОГОВХОДОВОГО

: сумматора по модулю два группы, выход которого соединен с вторым входом первого сумматора по модулю два

1р группы °

1631 541

1И авиа. 4

Составитель Г.Филаретов

Редактор Л.Пчолинская Техред Л.Сердюкова Корректор С.Черни

Заказ 547 Тираж 390 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101