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

(51)М. Кл, С 06 Р 7/58 Йфуйарстмнньй кемнтет СССР во делам кэоаретеннй и отхрцтнй(72) Авторы изобретения азанский орцена Ленина и орцена Трудового К намени госуцарственный университет им, В.И.нина(7) Заявитель Ле ЕВДОСЛУЧАЙНЫХ ЧИСЕЛ 54 ГЕ НЕРАТО лительвано о об- сабычайных слепоор псеваослуаатчнк равноаослучайных потоксе имты И, ИЛИ 13. т изменить веного сигналаего помощью закон распрепе"20 элз ескнм решея управляемый держащий ген 1 Изобретение относится к вычис ной технике и 1 ожет бьггь использ при моделировании систем массово служивания и как цатчик случайных тий при стохастических испыганиях.Известны генераторы псевдослу чисел, содержащие генератор М-по вательности 11 и 2. Недостаток этих устройств заклю в том, что они являются не регулиИзвестен также генерат чайных чисел, соаержащий мерно распределенных псев чисел, регистр кода, цатчик пульсов, логические менЭто устройство позволяе роятность поюления еаинич на своих выходах, однако с нельзя получить заданный ления чисел.Наиболее близким техни нием к изобретению юляет датчик случайных чисел, со ратор равнсмерно распределенных случайных чисел и послецсвательно соединенные блок ввода функции расврецеленття, блок параллельного сравнения чисел и дешифратор, причем генератор равномерно расцрецеленных чисел соединен с дешифратором и блоком параллельного сравнения чисел(4)Нецостатком такого устройства является отсутствие среаств для формирования псевдослучайных процессов, описываемых разными матрицами переходных вероятностей и одним и тем же заданным вектором стационарного распределейия, что сужает область применения устройства, так как в ряце случаев, например при моделировании систем массового обслуживания, возникает необходимость формирования именно таких процессов.Цель изсбретения - формирование псевдослучайных процессов, описываемых разными матрицами переходньцс вероятностей и оцним и тем же заданным вектором стационарного распре целения, т.е. расширение функциональных возможностей.04 Э 72 Для достижения поставленной цели в известный генератор псевдослучайных чисел, содержащий генератор М-последовательности, выход которого соединен с первым входом блока сравнения, выход кото рого соединен со входом дешифратора, выход которого соединен с первыми входами элементов И группы, выход которьк является первым выхопом генератора, введены блок задания длины последовательности и 10 блок задания распределения и матрицы переходов, первые выход которого соединен с вторым входом блока сравнения, второй выход блока задания распределения и матрицы переходов соединен с управляю щим входом пешифратора, первый и второй входы блока задания распределения и матрицы переходов являются соответственно первым и вторым входами генератора, третий вход блока задания распре деления и матрицы переходов является третьим входом генератора и соепинен с первым входом генератора М-послеповатеьности и первым входом блока задания длины последовательности, первый выход 25 которого соединен с вторым входом генератора М-послеповательности; второй вьгх од блоке задания олины последовательности соединен со вторыми входами элементов И группы третий выход блока за- зо дания длины последовательности является вторым выходом генератора, а второй вход блока задания алины последовательности соединен с четвертым входом блока задания распределения и матрицы перехо 35 дов и является четвертым входом генератора.Кроме того, блок задания распределения и матрицы переходов содержит п 1 сумматоров (щ -число компонентов заданно ного вектора распрепселения), п 1 -триггеров и щ элемент фИСКЛЮЧА 1 СШЕЕ ИЛИф первые входы всех сумматорсв являются первым входом блока, вторым входом которого являются вторые входы сумма 45 торов, первые выходы которых образуют первый выход блока, второй выход кажкого 1-го сумматора (1 =1,2,п 1) соединен с единичным входом соответствующего-го триггера, нулевые входы которых соединены с третьим входом блока,тактовые входы триггеров соединены с четвертым входом блока, выход каждого ( -го триггера соединен с третьим входом соответствующего-го сумматора, с первым входом -го элемента фИСКЛЮ- ЧАЮШЕЕ ИЛИ" и вторым входом(-1)-го элемента фИСКЛЮЧАЮШЕЕ ИЛИ", выходыкоторых являются вторым выходом блока,2 фвторой вход 83-го элемента "ИСКЛЮЧАЮЙЕЕ ИЛИф соещгнен с источником логической единицы.Кроме того, дешифратор содержит пве группы по п 1 элементов фИСКЛЮЧАН:ШЕЕ ИЛИф, первые входы элементов "ИСКЛЮ ЧАЮШЕЕ ИЛИф первой группы образуют вход пешифратора, второй вход каждого 1 -го ( 1 -1,2,0) элемента фИСКЛЮ- ,ЧАКШЕЕ ИЛИф первой группы обьепинены с первым входом (+1)-го элемента ИСКЛЮЧАЮШЕЕ ИЛИэтой группы соответственно, второй вход% го элемента ФИСК, ЛЮЧАКШЕЕ ИЛИ" первой группы соединен. с первым входом первого элемента ИСКЛЮЧАКШЕЕ ИЛИ этой группы, а выход. кажпого-го элементафИСКЛЮЧАЮШЕЕ" ИЛИ" первой группы соединен с первым входом-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИф второй группы соответственно: вторые входы всех элементов "ИСКЛЮЧАЮШЕЕ ИЛИф второй группы образуют управляющий вход пеши раторв, а выходы всех элементов фИСКЛЮЧАЮШЕЕ ИЛИ" второй группы образуют вькод дешифратора.Кроме тогоблок задания алины последовательности, содержит целитель частоты, триггер, элемент НЕ, элемент задержки и пва элемента И, вькопы которых являются соответственно первым ивторым выходами блока, третьим выходом которого является единичный выход триггера, нулевой выход которого соединен с первыми входами элементов И, вторые входы которых соединены с выходом элемента. НЕ, вход которого совместно с единичным входом триггера и управляющим вхопом делителя частоты образует первый вход блока, второй вход которого соединен с третьим входом первого элемента И, через элемент задержки - с третьим входом второго элемента И и непосредственно - со входом дели-теля частоты, выхоп которого соединен с нулевым выходом триггера.На фиг, 1 приведена блок-схема-генератора:, на фиг. 2 приведена схема блока задания распределения и матрицы переходов;. на фиг. 3 - схема дещифратора; нв фиг. 4 - схема блока запания длины последовательности.Генератор содержит блок 1 задания распределения и матрицы переходов, блок 2 задания длины последовательности и последовательно соединенные генератор 3 М-последовательности, блок 4 параллельного сравнения, дешифратор 5 и блок 6 элементов И, группа выходов которого образует шину 7 и является первым выхо5 943 цом генератора. Первая группа входов блока 1 образует шину 8, является первым входом генератора и служит пля зацания матрицы переходов. Вторая группа вхопов блока 1 образует шину 9, являет ся вторым вхоцом генератора и служит пля зацания вектора распрецеления. Первая группа выходов блока 1 соединена с второй группой входов блока 4 параллельного сравнения, а вторая группа выхоцов 1 ф соединена с второй группой входов цешифратора 5. Третий вхоц блока 1, первый .вход блока 2 задания дгкны псследовательности и первый вход генератора 3 М- последовательности образуют шину 10 установки исходного состояния, которая является третьим вхоцом генератора, Первый выход блока 2 запания цлины последовательности соединен с вторым вхоцом генератора 3 М-послецовательности, вто- гО рой выход блока 2 соединен с вторым входом блока 6 элементов И, третий выход образует шину 11, которая является . вт орым выходом генератора и по к оторой на внешние устройства поступает сигнал об окончании процесса генерации. Второй вход блока 2 соецинен с четвертым входом блока 1 и шиной 12, которая является четвертым входом генератора и по которой поступают тактовые импульсы. Блок,5 О 1 задания распрецеления и матрицы пере хоцов состоит из сумматоров 13, ФЫ -триггеров 14.и щ элементов 15 гнИСКЛЮЧАКШЕЕ ИЛИ", причем первые вхоцы сумматоров 13 соецинены с шиной 55 8, вторые вхопы сумматоров 13 соединены с шиной 9, первые выходы сумматоров 13 соединены - первым вхоцом блока 1 задания распределения и матрицы переходов, а второй выхоц-го сумматора 4 О соединен с первым вхоцом 1-го триггера 14, выход которого соецинен с третьим входом 1-го сумматора 13, первым гвхсрдом-го элемента 15 ИСКЛЮЧАЮЩЕЕ ИЛИ" и вторым входом ( -1)-го элемен 45 та 15 "ИСКЛЮЧАЮШЕЕ ИЛИ причем второй вход щ -го элемента .15 "ИС .КЛЮЧАЮШЕЕ ИЛИ" соединен с источником уровня логической ециницы, Вторые входы триггеров 14 соединены с шиной50 10, третьи выхоцы триггеров 14 соецинены с шиной 12, а выхоцы элементов 15 "ИСКЛЮЧАЮШЕЕ ИЛИ" соединены с вторым выходом блока 1 зацания распределения и матрицы переходов. Дешифратор 5 содеркит П элементов 16 рИСКЛЮЧАЮ 55 ШЕЕ ИЛИф и щ элементов 17 атИСКЛЮЧАЮШЕЕ ИЛИ", причем первые входы элементов 16 каждого разряда соединены с янии О;, а символом(0) - относитель ную частоту наблюдения события, а за время прохождения генератором 3 всегокмножества 2 = 1 состояний. Тогда 722 6первым входом дешифратора 5, второй входэлемента 16 кажцого разряда соединен спервым входом элемента 16 последующегоразряда, а второй вход элемента 16 старшего разряда соепинен с первым входомэлемента 16 первого разряда, выхоц элемента 16 в каждом разряде соединен спервым входом элемента 17 ИСКЛЮЧАЮШЕЕ ИЛИф того же разряда, вторыевходы которых соецинены с вторым входомцешифратора 5, а выходы элементов 17ИСКЛЮЧАЮШЕЕ ИЛИ" соединены с выходом цещифратора 5. Блок 2 зацанияалины последовательности содержит регулируемый целитель частоты 18, триггер19, элемент 20 НЕ, элементы 21, 22 Ии элемент 23 задержки, вход которогосоединен с первым вхоцом элемента 21 И,первым вхопом регулируемого целителячастоты 18 и шиной 12. Вход элемента20 НЕ, первый вхоц триггера 19 и второй вход регулируемого делителя частоты18 соецинены с шиной 10. Выхоп элемента20 НЕ соединен с вторым вхоцом элемента 21 и первым входом элемента 22 И,второй вход которого соединен с выходомэлемента 23 задержки. Выход регулируемого целителя частоты 18 соединен с вторым входом триггера 19, первый выход которого соединен с третьим входом , элемента 21 И и третьим входом элемента 22 И. Второй. выход триггера 19 соединен с шиной 11, вьхоц элемента 21 Исоединен с первым выходом блока 2 зацания длины последовательности; а выхоцэлемента 22 и соединен с вторим выходом того же блока.Устройство работает слецующим образом,Генератор 3 М-последовательностикимеет 2,-1 состояний, гце к - чис, ло триггеров в регистре генератора 3.Эти состояния закодируем числами от 1до 2 -1 будем использовать все множество чисеЛ, Разобьем это множествонаФ непустых непересекающихся подмножеств С;3 . Если состоянию генератораЭ отнечает число С Н(ДД, нулем считате,что устройство в этот момент временинаходится в состоянии а;, ОбозначимчерезО;(1 ) событие, означающее, что вмомент Ф устройство находится в состо9 0437 ется по формуле (3),Элементы матрицы переходов могут быть вычислены по формуле (1).Устройство работает следующим образо ме 5Вектор стационарного распределения задают с помацью Р-разрядных двоичных чисел г,", которые поступают в блок 1 задания распределения и матрицы переходов по шине 9. Матрицу переходов зада ют с помацью к-разряцного двоичного числа Ь г, которое поступает в блок 1 по шине 8, В блоке 1 (см. фиг, 2) эти числа поступают на к -разрядные суммато ры 13, число которых равно й 1 . Если 1 Р+И 2 -1, на выходе переноса в -гоксумматора 13 появляется уровень логической единицы. Э -триггеры 14 перед началом работы устанавгжвают в исходное нулевое состояние сигналом, поступающим 20 по шине 10. Начало работы определяется моментом снятия сигнала установки исходного состояни. При этом тактовые импульсы, поступающие на синхровход триг: геров.14 по шине 12, устанавливают 2 З 1 -й триггер 14 в единичное состояние, есгжг+дт 2 - 1, или в нулевое состо- ккФ ние, если 1;+д 1 4 2 -1. С выхода-го триггера 14 сигнал поступает на вход переноса 1 -го сумматора 13. При этом 30 формирование суммы-м сумматором 13 осуществляется согласно формуле (3), Полученные значения поступают в блок 4 параллельного сравнения.Элементы 15 фИСКЛЮЧАКШЕЕ ИЛИ З 5 служат пля отыскания интервала г 1-г, в котором нарушается монотонность функ - ции распределения. При монотонной функции распределения на выходах-го и (1+1)-го триггеров 14 присутствует уро-ю вень логического нуля и; следовательнона выходе ( -го элемента 15 фИСКЛЮ- ЧАИБЕЕ ИЛИф также имеем уровень логического нуля. Ест же в- ч интерва ле монотонность функции распределения нарушается, то на выходе ( 1 +1)-го триггера 14 появляется уровень логической единицы, При этом на выходе 1 -го элемента 15 фИСКЛЮЧАЮШЕЕ ИЛИф также появляется уровень логической единицы, который поступает в дешифратор 5 и изменяет логическую функцию 1 -го выхода дещифратора 5.Генератор 3 М-последовательности фор мирует к-разрядные псевдослучайные двоичные числа, которые псстуают в блок 4 параллельного сравнения, где сравнивается со значениями интервалов разбиения множества чисел генератора 3. Блок 4 22 10 содержит п 1 схем сравнения и формирует функцию распределения, причем для-ой схемы сравнения имеет место соотношение (6), Кодовые комбинации, описывакицие функцию распределения, поступают на вход дешифратора 5, функциональная схема которого изображена на фиг. 3. Дешифратор 5 состоит из элементов 16 и 17 ИСКЛЮЧАЮЩЕЕ ИЛИф, причем группа элементов 16 фИСКЛЮЧАОЦЕЕ ИЛИф служит для дешифрации кодовых комбинаций блока 4, а группа элементов 17 фИСКЛЮЧАЮШЕЕ ИЛИ" служит для коррекции группы элементов 17, Логическая функция-го выхода дешифратора 5 описывается выражениями (4) и (5). Псевдослучайный прщесс, заданный с помощью чисел Г; и дг, формируется на выходах элементов 17 фифИСКЛЮЧАКШЕЕ ИЛИ. Матрица переходных вероятностей и вектор стационарного распределения этого прсцесса описываются выражениями (1) и (2) соответственно, если коычество чисел в сформированной псевдослучайной последовательности и количество использованных для этой цели состожий генератора 3 М-последовательности будут равны 2 -1 иж кратны этому числу.КВыполнение этого условия обеспечивает блок 2 задания дащы последовательности,функциональная схема которого изображена на фнг. 4, Перед началом работы регулируемый делитель частоты 18 устанавливают в исходное нулевое состояние,а на управляющие входы подают сигнал, задающие требуемый коэффициент деления. Управляющие сигналы и сигнал уставовки нулевого состояния поступают на шине 10. Одновременно по шине 10 поступают сигнал установки нулевого состояния триг-. гера 19 и сигнал блокировки, который инвертируется элементом 20 НЕ и запирает элементы 21, 22 И. Момент начала работы определяется моментом снятия сигна- . лов установки нулевого состояния и блокировки; Прн этом элементы 21, 22 И отпираются и на вход генератора 3 через элемент 21 И начинают поступать тактовые импульсы с шины 12. На выходе элемента 22 и тактовые импульсы появляются с задержкой, так как предварительно проходят через элемент 23 задеркки. Величину задержки определяют исходя из условия окончания переходных процессов в блоках 3,4,5. Задержанные тактовые импульсы используются для стробирования. выходов дешифратора 5, что осуществляет- ся с помощью блока 6 элементов И, Одновременно тактовые импульсы поступаютна вход регулируемого делителя частоты 18, который срабатывает на их задний фронт. После появления на выходной шине 7 всех 2 -1 псевдослучайных чисел, чтоКэквивалентно поступлению на вход регули руемого делителя частоты 18 соответствующего количества тактовых импул ьсов, регулируемый делитель частоты 18 вьщает сигнал, который устанавливает триггер 19 в единичное состояние, При этом элементы 21, 22 И, соединенные с ин версным выходом триггера 19, запираются и процесс генерации прекращается, а на шине 11 появляется сигнал окончания работы генератора. Этот сигнал может быть использован внешними устройствами пля формирования различью; команд, в том числе и для повторного пуска генератора.Генератор может быть переведен в ре жим рабаты известного устройства, когда не требуется выполнение условия и =-2 -1,Кгде и - количество чисел в сформирован ной псевдослучайной псслеповательнасти;,количество состояний генератора 3 М-последовательности, использованных для формирования 36последовательности,.Для этого достаточно изменить управ-.ляющие сигналы, которые задают коэффициент деления регулируемого делителя час.тоты 18 и поступают на его вхоп по ши- З 5не 10.Новые функциональные возможностипредлагаемого устройства могут быть использованы при оптимизации систем массового обслуживания. Применение предлага демого устройства рассмотрим на примеремоделирования обслуживания заявок на городские и пригородные транспортные средства.Транспорт выпускают на линию периопически, Статегию определения числа тран.спортных средств, выпускаемых в данныймомент времени, определяют исхопя изчисла неудовлетворенных заявок, за предыдущий момент времени. Поскольку речьидет о расписании, такая стратегия должнабыть выбрана заранее. Обозначим черезх(Ц, где 1 - Время, разность межпучислом заявок н имеющимися на линии транспортными средствами. Если случайный про 55цесс х( Ф ) стационарный, то существуетвектор стационарного распрепеленн.оа=(жоо),о,14 причем о = ОА, где А-матрица переходныхвероятностей,й к - вероятность в среднемтого, что не будут удовлетворены к заявок.Качество расписания определяется вектором а, однако динамику системы такойвектор определяет лишь.асимптотически.В связи с этим возникает задача моделирования семейства процессов, описываемых разными матрицами переходных вероятностей и одним и тем же векторомстационарного распределения, Целью мо-.делирования является выбор такой матрицы, при которой случайная функция имеет минимальную дисперсию, Эта цельможет быть достигнута с помощью преплагае мого устройства,Предлагаемое устройство,по сравнению с известным особенно эффективно втех случаях, когда требуется изменятьматрицу переходных вероятностей при сохранении з аданного вектора стационарногораспределения, Эффективность примененияустройства определяется простотой изменения матрицы переходных вероятностейпри сохранении вектора стационарногораспределения, При этом отпадает большойобьем работы по вычислению или отборутаких матриц переходных вероятностей,вектор стационарного распределения которых в пределах заданной точности может быть принят одинаковым. Кроме того применение устройства позволяет повысить точность моделирования, так какустройство формирует семейство процессов с тождественно равными векторамистационарного распрепеления. Уменьшениеобьема вспомогательных работ при одновременном увеличении точи ссти повышаетоперативность моделирования . Перечисленные положительные эффекты обеспечиваются новыми функциональными возможностямипредлагаемого устройства. формула изобре те пня 1, Генератор псевдослучайных чисел,содержащий генератор И-последовательности, вькод которого соединен с первым входом блока сравнения, выход которого соединен со входом пешифратора, выход которого соединен с первыми входами элементов И группы, выходы которых образуют первый выход генератора, о т л и ч аю щ и й с я тем, что, с целью расширения функциональных возможностей генератора за счет воспроизвепения различных матриц переходных вероятностей, он содержитт блок задания длины послеповательности и блок задания распределения и матрицы переходов, первый выход которого соединен со вторым входом блока сравнения,второй втоц блока задания распределения и матрицы перехоцов соединен с управляющим входом цешифратора, первый ивторой входы блока задания распределенияи матрщы переходов являются соответственно первым и вторым входамигенераторв, третий вход блока задания раслредейления и матрицы переходов является третьим входом генератора и соединен с первым входом генератора М-посждоввтельности и первым входом блока задания длины последовательности, первый выхоц кьторого соединен с вторым вхоцом генератора М-посждовательности, второй выходблока задания длины последовательностисоединен со вторыми входами эжментовИ группы, третий выход блока задания О длины послецовательности является вторымвыходом генератора, а второй вхоц блоказадания длины нослецовательности соединен с четвертым входом блока заданияраспределения и матрицы переходов и яв-ляется четвертым входом генератора,2, Генератор по п. 1, о т л и ч а ю - щ и й с я тем, что блок задания распределения и матрицы перехоцов содержитщ сумматоров ( п 1-число компонентов за- Зв данного вектора распределения), в три геров и п 1 элементов ИСКЛЮЧАКШЕЕ , ИЛИ, первые входы всех сумматоров являются первым входом блока, вторым вхоцом которого являются вторые входы сум-маторов, первые выходы которых образуют первый выхоц блока, второй выход каждого-го сумматора ( 1 -1,2,я) соещщен с ециничным входом соответству 1ющего-го триггера, нулевые входы кой торых соединены с третьим входом блока тактовые входы триггеров соецинены с четвертым входом блока, вькоц каждого-го триггера соединен с третьим вхо дом соответствующего . -го сумматора, с первым входом-го эжмента ИСКЛЮЧАКШЕЕ ИЛИ" и вторым входом (1 -1)-го элемента ИСКЛЮЧАКШЕЕ ИЛИ, выходы которых являются вторым выходом блока, второй вход щ -го эжмента ИСКЛЮЧАЮЮЕЕ ИЛИсоединен с источником логической единицы.3. Генератор по п. 1, о т л и ч а - ю щ и й с я тем, что дешифратор сопер 943722 14жит две группы по п эжментов И(ЪЛ 1 ОЧАЮЩЕЕ ИЛИ", первые вхопы элементов"ИСКЛЮЧАЮЩЕЕ ИЛИпервой группы И- разуют вход дешифратора, второй вход41 вжрого-го (-1,2 щ) элементаИСКЛЮЧАКШЕЕ ИЛИпервой группыобьепинен с первым входом ( 1 +1) гоэлемента ИСКЛЮЧАКШЕЕ ИЛИэтойгруппы соответственно, второй вход щ-гоэлемента ИСКЛЮЧАКШЕЕ ИЛИпервойгруппы соединен с первым входом первого элемента ИСКЛЮЧАКШЕЕ ИЛИпервой группы, а вьиод каждого ( -го элемента ИСКЛЮЧАКШЕЕ ИЛИ" первойгруппы соединен с первым входом 1 -гоэжмента ИСКЛЮЧАКШЕЕ ИЛИвторойгруппы соответственно, вторые входы всехэлементов ИСКЛЮЧАКШЕЕ ИЛИвторойгруппы образуют управляющий вход дешифратора, а выходы всех элементов ИСКЛЮЧАКШЕЕ ИЛИвторой группы образуютвыход цешифратора.4,Генераторпоц. 1, отличающ и й с я тем, что блок задания длиныпоследовательности содержит делитель частоты, триггер, эжмент НЕ, эжмент запержки и два,эжмента И, выходы которыхявляются соответственно первым и вторымвыходами блока, третьим выходом которого является единичный выход тригге.ра, нулевой выход которого соединен с первымивходами эжментов И, вторые входы которых соединены с выходом элемента НЕ,вход которого совместно с единичным вхопом триггера и управлякющм вхопом делителя частоты образует первый вход блока, второй вход которого соединен с третьим входом первого эжментв И, черезэлемент задержки - с третьим входомвторов эжментв И и непосредственносо входом делителя частоты, выкод которого соединен с нулевым входом триггера.Источники информации,принятйе во внимание ври экспертизе1. Авторское свидетельство СССР34 428373, кл.06 Р 1(02, 1973.2. Авторское свидетельство СССРМ 674007, кл, ( 06 Р 1(02,. 1976,3. Авторское свидетельство СССРМ 748394, кл. ( 06 Р 1(02, 1978.4, Авторское свидетельство СССРКф 213424, кл, С; 06 Р 1(02, 1966прототип) .511156 Тираж 731 НИИПИ Государственного комитета С поделам изобретений и открытий113035, Москва, Ж, Раушская наб аказВ вл ППП Патент, г. Ужгород, ул. Проектная Составитель А. Карасов Редактор А. Цолинич Техред М.Рейвес Корректор У. Пономаренко