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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз СоветскихСоциалистическихРеспублик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(61) Дополнительное к авт. свид-ву(22) Заявлено 220980 (2 )2985884/18-24 (1) М. КП,з с присоединением заявки Мо -С 06 Р 7/58 Государственный комитет СССР по делам изобретений и открытий(71) Заявитель Минский радиотехнический институт(54) МНОГОКАНАЛЬНЫЙ ПАРАЛЛЕЛЬНЫЙ ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для получения случайных чисел при решении задач методом Монте-Карло, для построения генераторов случайных процессов с заданными характеристиками, а также для идентификации систем автоматического управления. При этом весьма важным оказывается качество первичных равномернораспределенных чисел, их разрядность и количество каналов генератора,Известен генератор псевдослучайных чисел, содержащий два регистра сдвига и группу сумматоров по модулю два 1 .Недостатком этого генератора является сложность структурного построения, а также усложненная методика синтеза. Кроме того, необходимым требованием для построения генератора псевдослучайных чисел является требование выбора таких структур исходных последовательностей, у которых периоды являются взаимно простыми числами, что не всегда оказывается возможным.Известен также последовательный генератор псевдослучайных чисел, который с точки зрения простоты реальзации не имеет себе равных. Необходимое для построения генератора оборудование состоит из регистра сдвигас сумматором по модулю два, генератора тактовых импульсов, счетчика ивыходных вентилей 21,Недостатком данного генератораявляется меньшая в и раэ по сравнениюс тактовой частотой регистра сдвигачастота выдачи и разрядных псевдослучайных чисел. При больших и этонакладывает существенные ограниченияна скорость или связанную с ней точность стохастических вычислений.Наиболее близким к предлагаемомуявляется параллельный генераторпсевдослучайных чисел, состоящий из20щ-разрядного регистра сдвига с двухвходовым сумматором по модулю два,в групп двухвходовых элементов И иав-входовых сумматоров по модулю два,В основе построения данного генератора лежит идея использования в качестве независимых последовательностей, формируемых в разрядах генератора, различных участков одной итой же псевдослучайной последовательности максимальной длины. Достоинством этого метода является возможность, 947856генерирования различных участков исходной последовательности с помощью несложных схем - дополнительного набора сумматоров по модулю два. На выходах этих сумматоров генерируются идентичные, но сдвинутые относитель но друг друга, псевдослучайные двоичные последовательности 3 .Недостатком известного генератора псевдослучайных чисел является сложность синтеза и громоздкость подго товительных операций. Это объясняется тем фактом, что определение набора коэффициентов 8, по заданному сдвигу не имеет простого аналитического решения, Поэтому для определения коэффициентов используют непосредственное моделирование работы генератора на ЭВМ, причем в общем случае эта задача не поддается решению путем моделирования на ЭВМ. Только в частном случае, когда схема цепи обратной связи регистра сдвига состоит только иэ одного сумматора по модулю два с двумя входами, задача нахождения коэффициентов решается относительно несложно.Кроме того, невозможно построение параллельного генератора псевдослучайных чисел для общего случая, т,е. для порождающего многочлена произвольной степени с любым набором ко- эффициентов Ье , т.е. подобно оказывается возможным построение параллельного генератора только для простейшего случая, когда в цепь обратной связи включен двухвходовой сум матор по модулю два, что существенно сужает функциональные возможности подобных устройств.Цель изобретения - упрощение генератора, 40Поставленная цель достигается тем, что в генератор псевдослучайных чисел, содержащий щ триггеров, щщ-входовых сумматоров по модулю два и щ групп по щ в каждой группе двухвходовых элементов И, дополнительно введены и групп по щ в каждой группе щ-входовых сумматоров по модулю два и и групп по щ подгрупп, включающих по щ двухвходовых элементов И, причем к входам д-го щ-входового сумматора по модулю два подключены выходы двухвходовых элементов И -ой группы по щ двухвходовых элементов И, к первому входу 3-ой двухвходовой элемента И -ой группы по щ-двухвходовых элементов И подключен единичный выход 3-го триггера, к синхровходам которого подключен выход генератора тактовых импульсов, вторые входы двухвходовых элементов И 60 1-ой группы по щ-двухвходовых элементов. И образуют первую группу входов генератора, выходы двухвходовых элементов И 1-ой группы (1 1,2,п) -ой подгруппы по щ 65 двухвходовых элементов И подключены к входам -го щ-входового сумматора по модулю два 1-ой группы,а выход М-го (1 - входового сумматора по модулю два подключен кпервому входу 3-ой двухвходовогоэлемента И (1-3)-ой подгруппы 1-ойгруппы и к 0-входу 1-го триггера,единичный выход (щ+1-Е)-го триггераподключен к первому входу (щ+3-1)-ойдвухвходового элемента И (щ+1-1)-ойподгруппы 1-ой группы, вторые входы3-ых двухвходовых элементов И каждой подгруппы 1-ой группы образуютвторую группу входов генератора единичные выходы триггеров и выходыщ-входовых сумматоров по модулю дваи групп являются выходами генератора.На фиг.1 приведена функциональнаясхема генератора при щ =4; на фиг.2последовательность состояний регистрапри щ = 4,Функциональная схема генераторапсевдослучайных чисел состоит изщ .= 4 триггеров 1 регистра сдвига,щщ- входовых сумматоров 2 по модулюдва щ групп по щ двухвходовых элементов И 3, и групп по щщ-входовых сумматоров 4 по модулю два и и групп пощ подгрупп, включающих щ двухвходовых элементов И 5, причем к входам-го щ-входового сумматора 2 по модулю два подключены выходы двухвходовых элементов И -ой группы по щдвухвходовых элементов И 3, к первому входу 3-ой двухвходового элемента И -ой группы 3 подключен единичный выход 3-го триггера , к синхровходам которого подключен выход генератора тактовых импульсов, на вторые входы двухвходовых элементов Их-ой группы 3 поданы значения коэффициентов, принимающих значения Оили 1, а выходы двухвходовых элементов И 1-ой группы д-ой подгруппы пощ-двухвходовых элементов И 5 подключены к входам -го щ-входовогосумматора 4 по модулю два 1-ой группы, выход 1-го щ-входового сумматора2 по модулю два подключен к входу3-ой двухвходового элемента 3 И(1 с)-ой подгруппы 1-ой группы 5 ик П-входу 1-го триггера 1, единичныйвыход (щ+1-1)-го триггераподключен к первому входу (щ+3-Е)-ой двухвходового элемента И щ+1-3)-ой подгруппы 1-ой группы 5, на второй вход3-ой двухвходового элемента И каждойподгруппы 1-ой группы 5 поданы значения коэффициентов, принимающих значения О или 1, а единичные выходытриггеров 1 и выходы щ-входовых сумматоров по модулю два п групп 4 являются выходами устройства.Значение коэффициентов сс ЕО3 = 1,щ определяют из известных таблиц.50 55 Функционирование многоканального параллельного генератора псевдослучайных чисел происходит следующим образом.В исходном состоянии триггеры 1 генератора находятся в произвольном состоянии,.кроме нулевого кода 000 О, другими словами на триггерах регистра хранится с равной вероятностью любой код, кроме нулевого. В зависимости от начального кода на выходах сумматоров по модулю два образуются значения нуля или единицы. На выходах триггеров 1 регистра получается значение первого псевдослучайного числа по первому каналу, а на выходах ща-входовых сумматоров 2 по модулю два значение следующего псевдослучайного числа, получаемого по первому каналу, а на выходах щ-входовых сумматоров по модулю два по щ в и группах 4 образуются значения первого псевдослучайного числа по остальным и каналам. По приходе синхроимпульса на С-входы триггеров 1 информация с выходов сумматоров 2 по модулю два записывается на триггера 1, после чего на выходах сумматоров 2 и 4 по модулю два образуются новые коды, которые являются очередными значениями псевдослучайных чисел по остальным и 1 каналам (сумматоры 4) и последующим значениям по первому каналу (сумматоры 2). Подобным образом по приходе следующих синхроимпульсов процедура повторяется,Достоинством генератора является существенное расширение,его функциональных возможностей, что объясняется возможностью построения параллельного геиератора для общего случая,т.е. для порождающего многочлена произвольной степени с любым наборомкоэффициентов. В данном случае оказывается возможным построение генератора не только для частного случая, когда в цепь обратной связи включен двухвходовой сумматор по модулю два, но и для случая многовходового сумматора по модулю два в цепи обратной связи. Реализация генератора при неизмененной жесткой структуре требует только щ триггеров и и+1 группу по щ сумматоров по модулю два со среднимколичеством входов, равном щ триггеров, и выходы щ-входовых сумматбровпо модулю два и групп являются выходами устройства, так как при равенстве нулю какого-либо коэффициента по соответствующему входу сумматора эта связь отсутствует, а при раВенстве единице всегда присутствует,Применение предлагаемого многоканального псевдослучайного генера 0 15 20 25 30 35 40 45 тора позволяет повысить качествопсевдослучайных последовательностей,а тем самым точность решения задачметодом Монте-Карло. Формула изобретения Многоканальный параллельный генератор псевдослучайных чисел, содержащий щ триггеров, ащ-входовых: сумматоров по модулю два и щ групп по щ в каждой группе двухвходовых элементов И,причем к входам 1-го (1 = 1, 2щ) щ-входового сумматора по модулю два подключены выходы двухвходовых элементов И 1-й группы, к первому входу -го= 1,2щ) элемента И 1-й группы подключен единичный выход -го триггера, к синхровходу которого подключен выход генератора тактовых импульсов, вторые входы элементов И 1-й группы образуют первую группу входов генератора, о т л и ч а ю щ и й с я тем, что, с целью упрощения генератора, в него введены и групп по щ в каждой группе щ-входовых сумматоров по модулю два и и групп по щ подгрупп, включающих по щ-двухвходовых элементов И, причем выходы двухвходовых элементов И 1-ой группы (1 = 1,2,и) з.-й подгруппы по щ-двухвходовых элементов И подключены к входам 1-го щ-входового сумматора по модулю два 1-й группы, а выход 1-го (И = 1,2 щ) щ-входового сумматора по модулю два подключен к первому входу -го двухвходового элемента И (Е)-й подгруппы 1-й группы к О-входу 1-го триггера, кроме того, единичный выход (щ+1-Е)-го триггера подключен к первому входу (щ+)-1)-го двухвходового элемента И (щ+1-)-й подгруппы 1-й группы, вторые входы )-х двухвходовых элементов И каждой подгруппы 1-й группы образуют вторую группу входов генератора, единичные выходы триггеров и выходы щ-входовых сумматоров по модулю два и групп являются выходами генератора. Источники информации,принятые во внимание при экспертизе 1. Яковлев В.В. и Федоров Р.ф. Вероятностные вычислительные машины. Л., "Машиностроение", 1974, с.263. 2. Яковлев В.В.н Федоров Р.Ф. Вероятностные вычислительные машины. Л., "Машиностроение", 1974. с.247,3. Яковлев В.В. и Федоров Р.Ф. Вероятностные вычислительные машины. Л., "Машиностроение", 1974, с.254947856 а д о, а,си ига8 игг т ст цф 4 г а 4 з сгюрогг агфа,фРоуг азК Ф лг 1 Я 3 Ягг го о ойго о ц г о г ю 1 г г / Составитель А.КарасовРедактор Н.Ковалева Техред Т. Фанта Корректор О. Билак Заказ 5652/72 Тираж 731 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д.4/5 Филиал ППП "Патент", г.Ужгород, Ул.Проектная,4 Р;ю А,г А,Дю ,гггуи р,2 г,г диг. г