Многоканальный параллельный генератор псевдослучайных чисел

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 2209,80 (21) 2985884/18-24 (Я 1 ) М. КЛ. з с присоединением заявки МВ—

С 06 F 7/58

Государственный комитет

СССР по делам изобретений и открытий (23) Приоритет—

{ЗЗ) УДК 681. 325 (088. 8) Опубликовано 300782, Бюллетень М28

Дата опубликован я описания 300782 (72) Автор изобретения

В.Н.Ярмолик

Вс".4.;."" ": g v

1 мнил: ., 1 (71) Заявитель

Минский радиотехнический институт (54) МНОГОКАНАЛЬНЫЙ ПАРАЛЛЕЛЬНЫЙ ГЕНЕРАТОР

ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

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

Известен генератор псевдослучайных чисел, содержащий два регистра сдвига и группу сумматоров по модулю два 1 .

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

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

Недостатком данного генератора является меньшая в и раэ по сравнению с тактовой частотой регистра сдвига частота выдачи и разрядных псевдослучайных чисел. При больших и это накладывает существенные ограничения на скорость или связанную с ней точность стохастических вычислений.

Наиболее близким к предлагаемому является параллельный генератор псевдослучайных чисел, состоящий из

m-разрядного регистра сдвига с двухвходовым сумматором по модулю два, m групп двухвходовых элементов И и

mm-входовых сумматоров по модулю два.

В основе построения данного генератора лежит идея использования в качестве независимых последовательностей, формируемых в разрядах генератора, различных участков одной и той же псевдослучайной последовательности максимальной длины. Достоинством этого метода является возможность, 947856 генерирования различных участков исходной последовательности с помощью несложных схем — дополнительного набора сумматоров по модулю два. На выходах этих сумматоров генерируются идентичные, но сдвинутые относитель- 5 но друг друга, псевдослучайные дноичные последовательности (3) .

Недостатком известного генератора псевдослучайных чисел является сложность синтеза и громоздкость подго- 10 товительных операций. Это объясняется тем фактом, что определение набора коэффициентов 8,< по заданному сдвигу не имеет простого аналитического решения. Поэтому для.определения коэффициентов используют непосредственное моделирование работы генератора на ЭВМ, причем в общем случае эта задача не поддается решению путем моделирования на ЭВМ. Только в частном случае, когда схема цепи обратной связи регистра сдвига состоит только иэ одного сумматора по модулю два с двумя входами, задача нахождения коэффициентов решается относительно несложно. Кроме того, невозможно построение параллельного генератора псевдослу- 1 чайных чисел для общего случая, т.е. для порождающего многочлена произвольной степени с любым набором ко- эффициентов 5„<, т.е. подобно оказывается возможным построение параллельного генератора только для простейшего случая, когда в цепь обратной связи включен двухвходовой сум- 35 матор по модулю два, что существенно сужает функциональные возможности подобных устройств.

Цель изобретения — упрощение генератора. 40

Поставленная цель достигается тем, что в генератор псевдослучайных чисел, содержащий m триггеров, mm-входовых сумматоров по модулю дна и m групп по а в каждой группе двухвходо-45 вых элементов И, дополнительно введены и групп по ш в каждой группе

m-входовых сумматоров по модулю два и и групп no m подгрупп, включающих

- по я двухвходовых элементов И, причем к входам i-го m-входового сумматора по модулю два подключены ныходы двухвходовых элементов И i-ой группы по m двухвходовых элементов

И, к первому входу j-ой двухвходоной элемента И i-ой группы по m-двух-55 входовых элементов И подключен единичный выход j-го триггера, к синхронходам которого подключен выход генератора тактовых импульсов, вторые входы днухвходовых элементов И 60

1-ой группы IIo m-днухвходовых элементов. И образуют первую группу входов генератора, выходы двухвходовых элементов И f-ой группы (L

1,2...,п) i-ой подгруппы по m 65 двухвходовых элементов И подключены к входам i-ro m-входового сумматора по модулю два f-ой группы, а выход k-го (k - входового сумматора по модулю два подключен к первому входу j îé двухнходового элемента И (k-j)-ой подгруппы k-ой группы и к D-нходу k-го триггера, единичный выход (m+1-k)-го триггера подключен к первому входу (m+j-k)-ой двухвходового элемента И (m+1-j)-ой подгруппы E-ой группы, вторые входы

1-ых двухвходовых элементов И каждой подгруппы (-ой группы образуют вторую группу входов генератора единичные выходы триггеров и выходы

m-входовых сумматоров по модулю два и групп являются ныходами генератора.

На фиг.1 приведена функциональная схема генератора при m =4; на фиг.2 последовательность состояний регистра при тп = 4.

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

m .= 4 триггеров 1 регистра сдвига, mm-: нходовых сумматоров 2 по модулю два m групп по m двухвходовых элементов И 3, ll групп по п..п-входоных сумматоров 4 по модулю два и и групп по

m подгрупп, включающих m двухвходовых элементов H 5, причем к входам

i-ro m-входового сумматора 2 по модулю два подключены выходы днухнходовых элементов И i-ой группы по и! двухвходовых элементов И 3, к первому входу j-ой днухвходового элемента И i-ой группы 3 подключен единичный выход 1-го триггера, к синхровходам которого подключен ныход генератора тактовых импульсов, на вторые входы двухвходовых элементов И

i-ой группы 3 поданы значения коэффициентов, принимающих значения 0 или 1, а выходы двухвходоных элементов И 6-ой группы i-ой подгруппы по

m-двухнходовых элементов И 5 подключены к входам i-ro m-нходового сумматора 4 по модулю дна R-ой группы, выход k-rom-входового сумматора

2 по модулю два подключен к входу

j-ой двухвходового элемента 3 И (k-j)-ой подгруппы 6-ой группы 5 и к D-нходу k-го триггера 1, единичный выход (m+1-k)-го триггера подключен к первому входу (m+j-k) îé двухвходового элемента И (m+1-j) oé подгруппы 1-ой группы 5, на второй вход

j îé двухвходоного элемента И каждой подгруппы 3-ой группы 5 поданы значения коэффициентов, принимающих значения 0 или 1, а единичные выходы триггеров 1 и выходы m-входовых сумматоров по модулю два п групп 4 являются выходами устройства.

Значение коэффициентов сс„ Е(0,4$, 1,m определяют из изнестных таблиц.

947856

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

В исходном состоянии триггеры генератора находятся в произвольном состоянии,.кроме нулевого кода 000...

О, другими словами на триггерах регистра хранится с равной вероятностью любой код, кроме нулевого. В зависимости от начального кода на выходах сумматоров по модулю два образуются значения нуля или единицы. На выходах триггеров 1 регистра получается значение первого псевдослучайного числа по первому каналу, а на выходах mm-входовых сумматоров 2 по модулю два значение следующего псевдослучайного числа, получаемого по первому каналу, а на выходах m-входовых сумматоров по модулю два по m в п группах 4 образуются значения первого псевдослучайного числа по остальным и каналам. По приходе синхроимпульса на С-входы триггеров 1 информация с выходов сумматоров 2 по модулю два записывается на триггера

1, после чего на выходах сумматоров

2 и 4 по модулю два образуются новые коды, которые являются очередными значениями псевдослучайных чисел по остальным и 1 каналам (сумматоры

4) и последующим значениям по первому каналу (сумматоры 2). Подобным образом по приходе следующих синхроимпульсов процедура повторяется.

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

Применение предлагаемого многоканального псевдослучайного генераt0

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

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

Многоканальный параллельный генератор псевдослучайных чисел, содержащий m триггеров, mm-входовых: сумматоров по модулю два и m групп по m в каждой группе двухвходовых элементов И, причем к входам i-го (i = 1, 2,...,m) m-входового сумматора по модулю два подключены выходы двухвходовых элементов И i-й группы, к первому входу j-го (j = 1,2,...,m) элемента И i-й группы подключен единичный выход j-ro триггера, к синхровходу которого подключен выход ге- . нератора тактовых импульсов, вторые входы элементов И i-й группы образуют первую группу входов генератора, отличающийся тем, что, с целью упрощения генератора, в него введены и-групп по в в каждой группе m-входовых сумматоров по модулю два и и групп по а подгрупп, включающих по m-двухвходовых элементов И, причем выходы двухвходовых элементов

И K-ой группы (K = 1,2...,n) i-й подгруппы по m-двухвходовых элементов И подключены к входам i-го m-входового сумматора по модулю два (-й группы, а выход k-го (k = 1,2,...,m)

m-входового сумматора по модулю два подключен к первому входу j-го двухвходового элемента И (k-j)-й подгруппы 1-й группы к D-входу k-го триггера, кроме того, единичный выход (m+1-k)-го триггера подключен к первому входу (m+j-k)-ro двухвходового элемента И (m+1-j)-й подгрУппы

f-й группы, вторые входы j-x двухвходовых элементов И каждой подгруппы 1-й группы образуют вторую группу входов генератора, единичные выходы триггеров и выходы m-входовых сумматоров по модулю два и групп являются выходами генератора.

Источники информации, принятые во внимание при экспертизе

1. Яковлев В.В. и Федоров P.Ô.

Вероятностные вычислительные машины.

Л., "Машиностроение", 1974, с.263.

2. Яковлев В.В.н Федоров P.Ô.

Вероятностные вычислительные машины.

Л., "Машиностроение", 1974. с.247.

3. Яковлев В.B. и Федоров P.Ô.

Вероятностные вычислительные машины.

Л., "Машиностроение", 1974, с.254 (прототип).

947856 си

mi

Е т ст

>1 .У «ЗЗ ВЛЗР а<>Е 1< а

at

1И А А б1 ... 1 t 1 f000t1001L101 0111 f fj

Составитель А.Карасов

Редактор Н.Ковалева Техред Т. Фанта Корректор О. Билак

Заказ 5652/72 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий. 113035, Москва, Ж-35, Раушская наб., д.4/5

Филиал ППП "Патент", r.Óæãoðoä, ул.Проектная,4

Дз (г (Фиг.2

c y

eт г