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

3 СЮ 6 06 Р 7 ЙТЕТ СООФ Й ОЯФьФий мяти, вто ,чен к вых пульсов, единен с ,дания ядр ,рого блок торого со . блока зад ООИЮОпещи нщОПИСАНИЕ Ин детакцону ениДвтильств(22) 11 а 12.81146) 15.0483. Бюл. М 1472) В.И.Новиков, А.Р.Якубенко, С.ф,Костюк И А.М.Кузьмич (71) Минский радиотехнический институт531 681325 (088 а 8)56) 1. Авторское свидетельство СССРВ 378826, кл. б 06 Р 7/58, 1973.2. Авторское свидетельство СССР М 488212, кл. С, 06 Р 7/58, 1975.3. Авторское свидетельство СССР М 732947, кл. С 06 Р 7/58, 1980прототип54) 157.) ГЕНЕРАТОР СЛУЧАИНЫХ ПРОПЕССОВ, содержащий генератор тактовых импульсов выход которого соединен с входом генератора равнбмерно распределенных случайных чисел, выход ко-. торого соединен с первым входом блока сравнения, второй вход которого подключен к выходу первого блока па мяти, о т л и ч а ю а и 4 с я тем, что, с целью расширения функциональных возможностей генератора за счет увеличения класса воспроизводиьжх статистических характеристик, он содержит регистр команд, блок задания адреса и второй блок памяти, первый выход которого является выходом генератора и подключен к первому входу блока задания адреса, выход которого соединен с входом первого блока памяти, выход блока сравнения соединен с первым входом второго блока парой вход которого подклюоду генератора тактовых имвыход регистра команд со- Щ вторым входом блока заеса и с третьим входом вто- фф а памяти, второй выход. ко- ЮУ единен с третьим входом ання адреса.Изобретение относится к областивычислительной: техники предназначено для моделирования потоков случайных чиселс требуемымй законамираспределения, марковских процессов и может быть использовано припостроении вероятностных вычислительных устройств; а также в качестве специализированного стохастического блока, подключенного квычислительным машинам общего назначения,Известно устройство, содержащеегенератор равномерно распределенныхслучайных чисел, схему сравнения,блок памяти, генератор тактовых ймпульсов, специализированный дешифратор, регистр формирования случайного числа, входные и выходныевентили 11,Недостатком устройства являетсяузкая специализация, так как онопозволяет Формировать только случайные числа с требуемыми законамнраспределения, но не позволяет фор-;мировать более сложные случайные про.цессы, например марковские,Известно устройство, содержащееблок управления, генератор равномер.но распределенных случайных чисел,блок сравнения, блок памяти трирегистра 23.Устройство позволяет формироватьв режиме разделения времени несколько последовательностей случайных чисел с заданными законами распределения и марковские процессы.Недостатком данного устройстваявляется невозможность программногоуправления при постоянном объеме памяти числом моделируемых законовраспределения и разрядностью форми-руемых случайных чисел, связностьюцепей Маркова и числом их состояний,что ограничивает еГо функциональныевозможности,Наиболее близким к предлОженному,по технической сущности являетсягенератор случайных процессов, содержащий генератор тактовых импульсов, регистр сдвига, три элемента И,генератор равномерно распределенныхслучайных чисел, два блока элементов НЕ, блок элементов И, шифратор,коммутатор, элемент НЕ, регистр адреса, блок памяти, блок сравнения Ц.Известный генератор может формировать в режиме разделения временипотоки случайных чисел с заданными законами распределения, последовательности кодов, задающих цепиМаркова.Недостатками устройства являются,невоэможноСть Формирования полумарковских случайных процессов; слу-.чайных процессов с заданной функцией нестационарностисложность управления устройством (настройкой ).55 60 65 довательность случайных чисел х с заданной функцией распределения г(к),УсФройство запускается на генерацию каждого числа сигналов (импульсом), приходящим на вход блока 3 памяти. Процедура получения щ-разрядного случайного числа х состоит из последовательного Формирования значений г , 1 = 1, т , разрядов1случайного числа путем сравнения на каждом 3 -м шаге равномерно распределенного числа ; и значения условной функции распределения Рг;",х ф - 1), определяющей вероятЦель, Изобретения - расширениефункциональных воэможностей устройства за счет увеличения классавоопроиэводиМых статистических характеристик.Поставленная цель достигаетсятем что в генератор случайных про.цессов, содержащий генератор тактовых импульсов выход которого соединен с входом генератора равно мерно распределенных случайных чисел, выход которого соединен с первым входом блока сравнения, второй вход которого подключен к Выходупервого блока памяти, введены ре гистр команд, блок задания адресаи второй блок памяти, ПервЫй выходкоторого является выходом генератора и подключен к первому входу блока задания аДреса выход которогоСоединен с, входом первого блока памяти, выХод блока сравнения соединен с первым входом второго блока памяти, второй Вход которогоподключен к выходу генератора тактовых импульсов, выход регистра ко,манд соединен с вторым входом блоказадания адреса и с третьим входомвторого блока памяти, второй выходкоторого соединен с третьим входомблока задания адреса.На Фиг. 1 приведена структурнаясхема генератора; на фиг. 2 - структуриая схема блока задания адреса;на Фиг. 3 - структурнай схема второгоблока памяти.Генератор содержит генератор 1равномерно распределенных случайныхчисел, блок 2 сравнения, блок 3 памяти, блок 4 задания адреса, блок 5памяти, генератор б тактовых импуль 40 сов, регистр 7 команд.Блок 4 задания адреса содержиткоммутатор 8, блок элементов И 9,регистр 10, блок 11 элементов ИЛЙ.БлоК 3 памяти содержит первый ре 45 гистр 12, второй регистр 13, блокэлементов ИЛИ 14,Б основу работы устройства положен метод условных вероятностей,заключающийся В преобразовании последовательности равномерно распределенных случайных чиселв послемое регистра 13, в регистр 12 записывается указатель А, содержа 1 ций единицу только в разряде, соответствующем старшему разряду форми- руемого случайного числа. Так, если необходимо Формировать числа разностью щ = 4 при разрядности регистра 13.п = 3, двоичное значение Ар = 00001000, при в = 6 А = = 00100000, На каждом М-м такте блок 2 к моменту появления импульса генератора б в соответствии с 11 вырабатывает значение г. Если при п = 8 и щ = 6 на первом такте = 1, то по сигналу генератора б содержимое регистра 12, равное 00100000, записывается по Я-входам в регистр 13, если г = О, то запись не выполняется, т.е. в конце такта содержимое регистра 13 равно 0000000. По заданному фронту импульса генератора 6 содержимое регистра 12 сдвигается на рдин разряд и становится равным 00010000. Если блок 2 вырабатывает значение г 2, то аналогично описанному в регистре 13 Формируется число, равное ООтг 0000. Таким образом, после ш = б тактов содержимое регистра 13 равно 00 г.г 2 гг,г 5 гб, где шесть младших разрядов содержат искомую случайную величину. При этом по заднему Фронту последнегб шестого импульса генеРатора б из младшего раэ" ряда регистра 12 выдвигается единйца, содержимое регистра становится равным нулю, а на втором выходе ре.гнстра возникает сигнал переноса, который служит указателем момента окончания формирования случайного :числа. Последующие импульсы генератора б никакого влияния на содержимое регистров 12 и 13 не оказывают.Для настройки устройства ва Формирование случайных величин с заданными вероятностными характеристиМами в блок 5 памяти записываются множества значений условных функций распределения Г (г/х , где 3 в . номер распределЕния. На каждом 1-м такте работы устройства из блока 5 выполия. ется считывание значения Р 1(г /х .ф адрес которого определяется логичес ким сложением начального адреса загрузки распредеЛения А, текущего содержимого регистров 12 и 13, а при формировании состояний марковского процесса - и предыдущего состояния Я процесса, хранящегося в регистре 10. При Формировании случайных чисел содержимое регистра 10 должно быть нулевым.Адрес памяти Формируется в блоке .4, который содержит блок 11, выполненный на трехвходовых элементах ИЛИ, на первые, вторые и третьи входы которых поступают соответствен.Но логическая сумма содержимого реность того, что г примет значение,равное единице, при условии, чтона предыдущих 1 -1 шагах сформировано значение х- 1. При этом, ес-.ли выполняетсяР(г/х- 1);, (1)то г 4 = 1, в противном случае г0Формирование значений гв соот 1ветствии с ( 1 ) является Функциейблока 2, который иа каждом такте. работы устройства сравнивает равномернораспределенное число , поступающеес выхода генератора 1 на его первыйвход, со значением условной Функциираспределения Г(г 1/х 1 - 1), поступа 15ющим с выхода блока памяти 5 на еговторой вход,Расширение функциональных воэможностей в предлагаемом устройстведостигается благодаря командйому управлению видом формируемого случайного Процесса и разрядностью формируеьых слуЧайных величин. Регистромкоманд стохастического генератораявляется регистр 7. Собственно ко- .манда состоит иэ четырех полей,первое из которых содержит указатель разрядности А формируемыхслучайных величин, который переда-.ется в блок 3, второе, третье ичетвертое поля содержат соответственНо НаЧалЬНый адрЕс заГрузки Ай эиачений условных функций распределе.ния Р (г/х ) н блок . 5 памяти, ука.-;затель сдвига А, маску А.Случайное ш-раУрядное число фор- Ммируется в блоке 3 в Ж младший разрядах регистра 13 за цикл, содержащйй щ тактов. Для этого регистр 12имеет первый информационный вход,второй вход синхронизации записи, 40третий вход сдвига на один разрядв сторону младших, первый йнформаци.онный выход, второй выход переносаиэ младшего разряда при сдвиге. Регистр 13 имеет, первый вход разреше- Цния записи по я-входам, третий входсинхронизации записи, четвертыйинформационный вход записи йо Я-вхо.дам, вМЬрой вХод сброса; Так какЯвходы триггеров регистра 13 соедЫиены с выходами соответствующих раз":нии управляющих сигналов на первыйи второй входы регистра 13 бн выполняет операцию логического сложениясвоего предыдущего содержимого ссодержимым регистра 12 Блок 14выполнен на двухвходовых элементахИЛИ и выПолняет операцию логического сложения содержимого регистров.12 и 13. 60Процедура формирования случайного числа выполняется следующймобразом.По сигналу, поступающему на входблока 3, сбрасывается в нуль содержи"651012256 гистров 12 и 13 и с выхода блока 3,начальный адрес загрузки Ан из регистра команд 7, предшествующеесостояние .марковского процесса 8из регистра 10 , блок 9 двухвходовых элементов И, на первые и вторыевходы которых поступают соответстЮенно маска А 4 из регистра команд7 и число с выхода коммутатора 8,который поступающее на его первыйвход число передает на. вход со сдвигом в сторону старших разрядов, вели В Распределение Адрес ячейкидвоичный 0101 0110 0111 0001 0010 0011 0100 ОООО Содержимоеячейки Рф(г (000) Р (ООО) Р (010) Ф (,г) Р багз(ОО)4500) Р(к (1 ИЦ е и. свободные РаспределениеЪ Адрес ячейкидвоичный 1101 1110 1111 1001 1010 1011 1100 1000 Содержимоеячейки Р" к,(00) Р(г) Р" (г, (10) лом 1 и вырабатывает г. По сигналу генератора 6 в регистр 13 записывается код Ог 00, содержимое ре 1гистра 12 сдвигается на один разряд,генератор 1 формирует число . На вто"ром такте блок 4 вырабатывает адрес,равный Ог,10, из блока 5 выполняется считывание значений условной функции распределения Р (г)г 100), блокВ2 формирует г и т.д. После третьеготакта трех мпадших разрядах регистра 12 сформировано искомое случайноечисло,Если необходимо Формирование случайных чисел с распределением А,то в реГистр команд 7 записываетсяАн = 1000, что соответствует начальному адресу загрузки распределенияА в блок:. 5, А = 0010, А = 0000. В40 .начале такта генератор 1 формируетчисло, по сигналу на входе сбрафсывается в нуль регистр 13, в регистре 12 записывается А. Аналогично предыдущему блок 4 Формирует65 адреС, который в этом случае равен В обозначении Р г(х - 1) А,В"Аиндексы распределения, 1 - номер такта, х - двоичное значение случайного числа, сФормированного в регистре 13 на т) -м такте.Пусть далее регистр 10 обнуляется, в регистр команд 7 записывается А = 0000, что соответствует начальному адресу загрузки распределения В в блок 5, указатель разрядности Ар = 0100, маска А = ОООО .(,Указатель сдвига А при нулевой маске безразличен).В начале такта генератор 1 вырабатывает число , по импУльсУ, .поступающему на вход блока 3, сбрасывается в нуль регистр 13, в ре-. гистр 12 записывается А. Блок 4 Формирует адрес памяти, который.об-разуется в результате логического сложения содержимого регистров 10, 12 и 13 и поляА, команды,.и иа пер-, вом шаге:.равен ОООО. Иэ блока 5 счи. тывается Р 8(г). Блок 2 сравниваетс РВ(г)в соответстВии с правичина которого определяется указателем числа сдвигов А , поступающим на его второй вход из регистра команд 7.Устройство при формировании последовательности.двухразрядных случайных чисел, задаваемой условной Функцией распределения Г г /х ), работает следующим образом.Пусть раэрядность регистра 13 и = 4 и загрузка блока памяти 5 вы". полнена согласно табл. 1,Т а б л и ц а 11012256 10 00000 00100 01000 01110 10000. 10100 11000 11100 Начальныйадресобластидвоичный Множества г)1,3 - двоичное гг г,Нх /х ) роен на воспроизведение нескольких цепей Маркова. В этом случае номер цепи указывается полем А команды. Так,.если необходимо моделировать две двухсвязных цепи Маркова с матрицами рАРЗЬ, РВР 3)с, 0 = 1,4, то объем блока 5.должен быть не менее 128 ячеек. ЗначенияА3 могут записываться с начального адреса 0000000, значения Н 1;3 ) - с адреса 1000000. Для ФОрмирОваиия Состояний цепи В в регистр 7 необходимо записать команду, содержащую Ан = 1000000,0000010, А =А = 0000010.Устройство при моделировании полумарковского случайного проВ РЕгнстр комаид 7 записыва-ется Ан = 10000, А ь = 00010,А,= 01100, А = 00010. В регистр1 записывается код Огг 200, гдег г - начальное состояние процесо2 Пса. По сигналу на входе 15 начинается цикл формирования очередного состояния процесса, сбрасывается в нульрегистр 13, в регистр 12 запйсывается Ар. Блбк 4 формирубт адрес,равный 1 гого 10, по которому считывается Н(г . За два такта в Регистре 13 формируется следующее состояние процесса ОООг г . Нй выходе бло 1 11 ,)ка 11 присутствует число 1 гогог" г 12 л 2которое сдвигается коммутатороМ 8,логически умножается на маску А бло ком 9. Полученный код ОгогООО по сиг.1 2налу с второго выхода регистра 12записывается в регистр 10. На этомформирование очередного состояниямарковского процесса оканчивается. Далее в регистр 7 записываетсяА,1 = 00000, А = 01100, А = 00000,А = 00010. По сигналу на входе 1 Яначинается цикл Формирований временинахождения процесса в текущем состоянии. Сбрасывается в нуль регистр13, в регистр 12 записывается А,бл 1 ок 4 формирует адрес равныйОгг 210. Аналогично предыдущему врегистре 13 формируется число, яв цесса, описываемого матрицей переходных вероятностей РЗЬ,Ь = 1,4 и множеством функцийраспределения Г 3 1) времени нахождения процесса в состояниивремя нахождения процесса в любом из состояний кодИруется двухразрядным двоичным числом ) работает следующим образом,Перед началом работы устройствакаждой Функции Г 3 1 ) в каждойстроке матрицы Р ставится в соот. ветствие условная функция распределения Г (г/х ) и Н (г/х ). Значения условных Функций распределениязаписываются в блок памяти 5, например, согласно табл. 3.Т а б л и ц а 3 ляющееся временем нахождеИия процесса в состоянии г"г 2, В конце1 2цикла по сигналу на втором .выходерегистра 12 сформированное к это"му моменту на выходе блока 9 число лОг.г 000 записывается в регистр 10,1 1На этом Формирование времени нахождения процесса в текущем состоянииоканчивается.Перед началом моделирования следующего состояния процесса восстаНавливается содержимое регистра 7(А = 10000, Ар = 00010, А, = 00010,А = 01100). По сигналу на входе 15приводятся в исходное состояние регистры 13 и 12, блок 4 формируетадрес 1 г 2 г 10, из блока 5 считывается ЙЬ)и т;д,ПредЛоженный генератор может бЫть использован при формировании случайных чисел с заданной функцией нестационарности,. определяемой последовательностью ( программой ) изменения во времени Функций распределения.Пусть в процессе формирования двухзарядных случайных чисел необходимо в соответствии с заданной программой чередовать распределения Г) г/х),3= Г,в. В этом случае загрузка блока 5 может быть выполнена согласно табл, 4,1012256 Таблица 4 еи пп п и и п пп М и Иачалъныйадресобластидвоичный 00100 01000, 01100 10000 10100 11000 111000 пппюппппппппппепппппйй пЕфпппее еа мпаэ ЮпеайЬпп Б регистр 7 записывается коиан 1 да указывающая начальный ащео загрузки первого распределения, п роблесеформйрования случайного числа йе от" личается от рассмотренного ранее.В момент смены распределений в регистре 7 записывается новая команда, указывающая начальный адрес очеред його распределения.Ври использовании в составе . фсложной Многокомпонентной системы; .например модели стохастической сетй генератор яВляется узлом, Поставляющим случайные числа в различ . иые блоки модели. Запросы от блокой ф модели поступают в случайные моментывремени, при этом каждый 3-й запростребует формирования случаййогО чис. ла или последовательности чисел ссоответствующим ему распределениеМ й Р (г /х). В .этоМ режиме каждому виду запросов ставится в соответствие определеннай команда. ОбслуживанйезапРоса сводится к записи в регистр7 команд, соответствующей данному фзапросу, и Формированию случайных чисел в соответствии с установлен Ной командой. Причем, запросу может соответствовать команда, задающая режим Формирования состоя-, ний марковского илиполумарковского слуЧайных процессов.При работе во всех рассмотренных выше режимах возможна ситцация, когда в блоке 5 загружено йесколько множеств Г и вознИкает Необходимость заме 4 г множества РД, загруженного с адреса А, на множество Р . Б предлагаемом уст ройстве в отличие от,прототипа данная процедура выполняется весь- М ма просто ввиду того, что значения множества Гк) расположены в одной области памяти блока 5. Операция загрузки Рсводится к записи предварительно упорядочен ных элементов множества в Р) блок 5, начиная с адреса Ай в ,порядке возрастания адресов. Для этого в регист 7 записывается команда с Ан = А = А, сбрасывают- у ся в нуль региотры 10, 12 и 13,После записи каждого элемента Р(г/х,содержимое регистра 10 увеличивается на единицу, в результатечего адресуется следующая ячейка. блока памяти. 5.В основу алгоритмаработы устройства может быть положен методОбратных Функций или его комбинаци я с методом условных вероятностей.,Реализация блоков предлагаемо-го устройства не имеет отличительных особенностей. Все блоки (.кроМе блока 7) устройства могут бытьВыполнены на микросхемах 155 серии согласно РТМ. Используются готовые Функциональные узлы, имеющиеся в этой серии. Предпочтительнее использовать генератор равномерно распределенных чисел комбинированного типа. Блок сравнения 2 выполняется как комбинационный сумматор на микросхемах 155 ИМЗ,Или 155 ИМЗ.Блок памяти 5 (в за.висимости от Объема требуемОй памяти) может быть реализован на микРоскемах 155 РУ 2, 54 КР 1 А, 541 КР 1 Е,Ж, И, К, генератор тактовых импульсов легко реализуется на микросхе. -мах 155 ЛАЗ, регистр команд 7 можетбыть как наборным (,тумблерным ), таки в интегральном исполнении 155 ИР 1,155 ИР 13. Коммутатор В собирается,М микросхем 155 КП 5 ( 155 КП 7), блоксхем И 9 - из микросхем 155 ЛЙ 1. Регистры 10 .и 12 выполняются на 155 ИР 1,а регистр 13 - на 155 ИРТЭ согласноРТМ, Блок схем ИЛИ 14 набран измиКросхем 155 ЛЛ 1, блок схем ИЛИ 11Из Микросхем 155 ЛЛ 1, 155 ЛРЗ, Так .Как деталиэацня блоков устройства вы.полнена до Функциональных узлов, имеющихся в составе серии, то реализаЦия блоков по приведенным данным невызываеТ затруднения.Таким образом, предложенный стохастический генератор обладает рядомтехнических преимуществ перед известными, так как позволяет Формироватьпотоки случайных чисел с заданнымиактор Л. Веселовс шетник Заказ 2766/6 704венного комитретений и откРаушская наб Тнр ИИПИ Государ по делам иэ Москва, Ж-ЗПодписноа СССРтий 113035 филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 функциями распределения, последова-. тельности состояний односвяэных и многосвязных. Мепей Маркова, временных параметров и состояний полумарковских процессов, потоки случайных чисел с заданной нестационарнастью программой изменения функций распределения,. При этом за счет страничнойорганизации и разме. щения значений условной функции распределения, относящейся к одному распределению, в одной или нескольких смежных станицах памяти существенно упрощается процедура настройки устройства на формирование случайных последовательностей с заданными вероятностнымн свойствами.Предложенное устройство реализует принцип командиого управления(в общем случае такая задача решается с помощью классического микропрограммного автомата, что требуетбольших, аппаратурных затрат ),Экономический эффект от использования предложенного устройства вместо пакета программ состоит в экономии машинного, времени в результате сокращения времени моделирова ния исходных случайных процессов и,соответственно, сокращения времени решения задачи (время генерации од ного случайного числа в случае применения устройства практически рав. но времени обращения в канале ЭВМи, в зависимости от коэффициента его использования, может колебать" ся от десятков до сотен тысяч рублей в год.