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

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

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

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

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

Недостатком данного генератора является меньшая в п раз по сравнению

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

Наиболее близким к предлагаемому является параллельный генератор псевдослучайных чисел, состоящий из т-рйзрядного регистра сдвига с двух20входовым сумматором по модулю два, m групп двухвходовых элементов И и mm-входовых сумматоров по модулю два. В основе построения данного генератора лежит идея использования в ка25честве независимых последовательностей, формируемых в разрядах генератора, различных участков одной и той же псевдослучайной последовательности максимальной длины. Достоинст30вом этого метода является возможность) генерирования различных участков исходной последовательности с помощью несложных схем - дополнительного набора сумматоров по модулю два. На выходах этих сумматоров генерируются идентичные, но сдвинутые относительно друг друга, псевдослучайные двоич ные последовательности З. Недостатком известного генератора псевдослучайных чисел является сложность синтеза и громоздкость подготовительных операций. Это объясняется тем фактом, что определение набора коэффициентов по заданному сдвигу не имеет простого аналитического решения. Поэтому дляопределения коэффициентов используют непосредственное моделирование работы ге нератора на ЭВМ, причем в общем случае эта задача не поддается решению путем моделирования на ЭВМ. Только в частном случае, когда схема цепи обратной связи регистра сдвига состо ит только из одного сумматора по модулю два с двумя входами, задача нахождения коэффициентов решается отно сительно несложно. Кроме того, невозможно построение параллельного генератора псевдослучайных чисел для общего случая, т.е для порождающего многочлена произвольной степени с любым набором коэффициентов 8 т.е. подобно оказывается возможным построение параллельного генератора только для простейшего случая, когда в цепь обратной связи включен двухвходовой сумматор по модулю два, что существенно сужает функциональные возможности подобных устройств. Цель изобретения - упрощение генератора. Поставленная цель достигается тем что в генератор псевдослучайных чисел, содержащий m триггеров, mm-входовых сумматоров по модулю два и m групп по m в каждой группе двухвходо вых элементов И, дополнительно введены п групп по m в каждой группе т-входовых сумматоров по модулю два и п групп по m подгрупп, включающих по m двухвходо.вых элементов И, причем к входам i-ro m-входового сумма тора по модулю два подключены выходы двухвходовых элементов И i-ой группы по m двухвходовых элементов И, к первому входу j-ой двухвходовой элемента И i-ой группы по т-дву входовых элементов и подключен единичный выход j-ro триггера, к синхровходам которого подключен выход генератора тактовых импульсов, вторые входы двухвходовых элементов И i-ой группы по т-двухвходовых элементов. И образуют первую группу входов генератора, выходы двухвходовых элементов Н Р-ой группы (t 1,2..,,п) i-ой подгруппы по m двухвходовых элементов И подклю- j чены к входам i-ro m-входового сум- матора по модулю два Е-ой группы, а выход k-ro (k - входового сумматора по модулю два подключен к первому входу j-оЙ двухвходового элемента И (-)-ой подгруппы t-ой группы и к и-входу k-ro триггера, единичный выход ni+l-k)-ro триггера подключен к первому входу (m+j-k)-oй двухвходового элемента И (т+1-1)-ой подгруппы Е-ой группы, вторые входы j-ых двухвходовых элементов И каждой подгруппы Е-ой группы образуют вторую группу входов генератора единичные выходы триггеров и выходы т-входовых сумматоров по модулю два п групп являются выходами генератора. На фиг.1 приведена функциональная схема генератора при m 4; на фиг.2 последовательность состояний регистра при m 4. Функциональная схема генератора псевдослучайных чисел состоит из m 4 триггеров 1 регистра сдвига, mm-: входовых сумматоров 2 по модулю два m групп по m двухвходовых элементов И 3, п групп по mm-входовых сумматоров 4 по модулю два и п групп по m подгрупп, включающих m двухвходовых элементов И 5, причем к входам i-ro m-входового сумматора 2 по модулю два подключены выходы двухвходовых элементов И i-ой группы по m двухвходовых элементов И 3, к первому входу j-ой двухвходового элемента И i-ой группы 3 подключен единичный выход j-ro триггера 1, к синхровходам которого подключен выход генератора тактовых импульсов, на вторые входы двухвходовых элементов И i-ой группы 3 поданы значения коэффициентов, принимающих значения О или 1, а выходы двухвходовых элементов И 6-ой группы i-ой подгруппы по т-двухвходовых элементов И 5 подключены к входам i-ro m-входового сумматора 4 по модулю два Е-ой группы, выход k-ro m-входового сумматора 2 по модулю два подключен к входу j-ой двухвходового элемента 3 И (k-j)-oй подгруппы Е-ой группы 5 и к D-входу k-ro триггера 1, единичный выход (m + 1-k)-ro триггера подключен к первому входу (ш+j-k)-oй двухвходового элемента И (m+1-j)-oй подгруппы t-гой группы 5, на второй вход j-ой двухвходового элемента И кс1ждой подгруппы Е-ой группы 5 поданы значения коэффициентов, принимающих значения О или 1, а единичные выходы триггеров 1 и выходы т-входовых сумматоров по модулю два п групп 4 являются выходами устройства. Значение коэффициентов efO.-i} , j l,m определяют из известных таблиц.

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

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

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

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

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

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

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

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

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

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

1.Яковлев В.В. и Федоров Р.Ф. Вероятностные вычислительные машины. Л., Машиностроение, 1974, с.263.

2.Яковлев В.В. VI Федоров Р.Ф. Вероятностные вычислительные машины. Л., Машиностроение, 1974. с.247.

3.Яковлев В.В. и Федоров Р.Ф. Вероятностные вычислительные машины. Л., Машиностроение, 1974, с.254 (прототип).

°.i

OfJ

«

Ol.l

OuzOa 3 Oy

0,1

Oi.t

b±. {i( iJ.j)I.ojLQ} 0-Q-U QJ- LJJJ..,

-V If

.i

Q.i.u .

oi,zai,3

(ригЛ

Фиг.2