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

Союз СоввтсиниСоцналистнчеснииРвслублни ВТОРСКОМУ СВИДЕТЕЛЬСТВ/18(5 )М. Кл. 6 Об Г 7/ исоединением заявки М вуаврстеаеый кавите С.ССР ав ливан извбретеиий и атирытий3) Прнорите убликовано 23.04,82, Бюллетень 8 15 ата опубликования описания . 25. 04. 82 УДК 681. 325(088.8) и Г;И. .Жухови(71) Заявитель Минский радиотехнический инстит 154) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИС дные и выт с Изобретение относится к вычисли ельной технике, а именно к стохатическим устройствам для моделиро" вания случайных чисел, величин и процессов, и может быть использовано в стохастических вычислительных машинах в качестве модуля для генерирования потоков случайных чисел с заданными вероятностными характеристиками и марковского случайного,процесса с конечным множеством состояний, е автоматизированных моделирующих комплексах для решения задач мето дом статистических испытаний и в автоматизированных системах испытания объектов на случайные воздействия.Известно устройство, позволяющее формировать потоки случайных чисел с произвольными требуемыми законами распределения и содержащее генератор равномерно распределенных случайных чисел, схему сравнения, блок памяти, генератор тактов, специализированный дешифратор, регистр формирова ния случаиного числа, вхоходные вентили 111.Известно устройство, позволяющееформировать случайные числа с произвольными требуемыми законами распределения, содержащее многоканальныйгенератор случайных импульсных потоков, схемы И, схему ИЛИ, вероятностный вентиль, регистр формирования случайного числа, схемы И реч гистра, устройство формирования адреса памяти, блэк памяти и генераторраспределитель тактовых импульсов 21,Недостатком известных устройствявляется низкое быстродействие, оп ределяемое в основном временем считывания информации из блока памяти.Наиболее близким к изобретениюявляется генератор случайных чисел,содержащий блок управления, датчик .равномерно распределенных случайныхчисел, схему сравнения, регистр маски, регистр цисла, запоминающее устоойство и блок адреса на регистре51 О15 20 25ЭО 35 40 45 50 55 соединен с третьим выходом блока управления, а первый выход блока задания адреса соединен с первым адресным входом первого блока памяти, введены коммутатор, второй и третий блоки памяти, первый адресный вход второго блока памяти соединен с первым выходом блока задания адреса, второй выход которого соединен с входом третьего блока памяти, первый выход которого соединен с вторыми адресными входами первого и второго блоков памяти, а второй выход третьего блока памяти подключен к входублока управления и управляющим входам первого блока памяти и коммутатора, первый информационный вход которого соединен с выходом первого блока памяти, второй информационный вход коммутатора соединен с выходом второго блока памяти, а выход коммутатора соединен с вторым входом блока сравнения, вход установки режима и вход запуска блока задания адреса являются соответственно первым и вторым входами устройства.Кроме того, блок задания адреса содержит первый регистр сдвига, элемент задержки, элемент ИЛИ, второй регистр сдвига, у которого входы установки в единицу нулевого, в-го, 2 е-го; , (и-в)-го разрядов и установки в нуль остальных разрядов соединены и подключены к выходу элемента ИЛИ, вход сдвига второго регистра сдвига подключен к управляющему входу блока задания адреса, информационные входы младших щ разрядов являются ин- Формационным входом блока задания адреса, выход нулевого разряда второго регистра сдвига подключен к управляющему входу первого регистра сдвига и к входу элемента задержки, выходы первого, второго, , (и)-го разрядов второго регистра сдвига являются первым выходом блока задания адреса и подключены к информационным входам соответственно первого, второго, ,(и)-го разрядов первого регистра сдвига выходы которого являются вторым выходом блока задания адреса, управляющий вход второго регистра сдвига соединен с входом установки режима блока задания адреса, вход запуска блока задания адреса соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом элемента задержки.Укаэанные изменения приводят кувеличению быстродействия устройства за счет организации двухуровневой памяти, где первый уровень сос тавляют сверхбыстродействующие вто-.рое и третье запоминающие устройствасравнительно малого объема, а второй уровень - первое запоминающееустройство большого объема и сравнительно невысокого быстродействия. 1 ОНа фиг. 1 приведена структурнаясхема генератора; на фиг. 2 - функциональная схема блока адреса; нафиг. 3 - функциональная схема блокауправления; на фиг. 4 - временная 15диаграмма сигналов на входе и выходах блока управления,Генератор содержит датчик 1 равномерно распределенных случайныхчисел, блок 2 сравнения, коммутатор 203; первый блок 4 памяти, второйблок 5 памяти, блок 6 задания адреса, блок 7 управления и третий блок8 памяти.Блок 6 задания адреса содержит 25первый регистр 9 сдвига и второйрегистр 10 сдвига, элемент 11 задержки и элемент ИЛИ 12. Блок 6 имеетвход .13 установки режима и вход 14запуска. ЭОБлок 2 управления содержит элементИ 15, элемент 16 задержки, триггер17 с установочными входами, генератор 18 импульсов и элемент 19 задержки с двумя выходами.Э 5Рассиотрим функции, выполняемыеструктурными компонентами устройства.Датчик 1 формирует независимые,распределенные на интервале 0-1 случайные числа. Очередное число вырабатывается датчиком по сигналу на еговходе.Коммутатор 2 выполняет подключение к входу схемы 2 сравнения при45одиночном сигнале на управляющем входе выхода блока 4 и при нулевом сигнале на управляющем входе выходаблока.5.Блоки 5 и 8 памяти сверхбыстродействующие, блок 4 памяти - обычное за 50поминающее устройство, например, наферритовых сердечниках. Блоки 4 и.5памяти имеют первые адресные входы,определяющие адрес ячейки внутристраницы, и вторые адресные входы,55определяющие собственно адрес страницы. Блок 4 памяти имеет также управляющий вход, единичный сигнал на котором разрешает работу устройствав режиме считывания. Блок 8 памяти имеетдва выхода, При считывании информации изячеек устройства 8 и разрядов счи"танного кода поступают на первый выход, а (и+1)-й разряд - на второйвыход блока 8,Блок 6 содержит первый и -разрядный регистр 9, второй (и+1)-разрядный регистр 10, элемент 11 задержки и элемент ИЛИ 12.Вход 13 установки режима позволяет настраивать блок 6 либо на формирование случайных п- разрядныхчисел (нулевой сигнал на входе 13),либо на формирование состояний однородного марковского процесса,имеющего два состояния (единичныйсигнал на входе 13). Вход 14 запуска предназначен для установки начального состояния регистра 10.Регистр 10 служит для формированияслучайного числа (или случайного состояния марковского процесса) и имеетБ-входы установки в единицу О-го,е-го, 2 е-го, , (и-е)-го разряда,В-входы установки в нуль остальныхразрядов, информационные О-входымладших е разрядов и управляющийС-вход сдвига в сторону старшихе разрядов. В процессе моделированиясодержимое регистра 10 (раэряды1-и ) определяет адрес ячейки внутри страницы.Регистр 9 предназначен для хранения в процессе моделирования либономераформируемого распределенияслучайных чисел Ч 1 х), лиЬо преды-дущего состояния марковского процесса и имеет информационные О-входы 0-го, 1-го,(и)-го разрядов, управляемый С-вход занесенияинформации, управляющий Ч-вход разрешения занесения информации.В процессе моделирования содержимое регистра 9 определяет адресстраницы запоминающего устройства,Блок 2 сравнения на каждом -мтакте работы устройства формируете разрядов случайного числа в результате сравнения по методу обратных Функций равномерно распределененого случайного числаи 1=2 -1значений дискретной условной функции распределения Р(х /х ), гдех 1 - значение случайного числа,сформированного на 1-1 предыдущихтактах работы устройства. Блок 7управления служит для генерирования92273 7тактовых импульсов У, У, У. Вкачестве примера конкретного выполнения на фиг. 3 приведена функциональная схема блока 7, а на фиг. 4"временные диаграммы сигналов на еговходе и выходах.В момент запуска триггер 17 устанавливается в единичное состояние.Запускаются генератор 18, вырабатывается сигнал "1", поступающий наэлемент 19 задержки, на выходах которого последовательно возникаютсигналы У и У (фиг. 4, моментСо-С ), Если сигнал"П имеет нулевоезначение, то элемент И 15 закрыт, 13триггер 17 состояния не изменяет,и по очередному сигналу Угенератора 18 сигнал повторяется. Такойцикл блока 7 будет называть быстрым.Если сигнал "П" имеет единичное 20значение, то импульс У проходит че-.рез элемент И 15 на вход элемента16 задержки и одновременно сбрасывает триггер 17. Работа генератора18 прерывается (момент Сна фиг. 4), 2В момент С 1 выходной сигнал элемента 16 задержки устанавливает триггер17 в единичное состояние, запускается генератор 18, вырабатывается Уи т.д. Такой цикл будет называть мед зфленным,Работу устройства для вероятностного моделирования рассмотрим напримере генерирования последовательности случайных чисел, распределенных на интервале 10-15), разрядностиа 4, подчиняющихся Функции распределения, которая представлена значениями в равноотстоящих точках квантования Х=0,16, При этом на каждом тактеработы устройства формируется а=2разряда чисел. На первом такте Ц 1)оаботы устройства формируется кодстарших нулевого и первого разрядовчисла, при этом используются значения дискретной условной функции распределения Г(х/0)=Ч(х"), а собственно Формирование выполняется согласно правиламО, при О=Ч(0) с с Ч(4);4, при Ч(4)4М(8)13, при Ч(8) с 1 с Ю(12)112, при Ч(12) с Ч (16) =1На втором такте (2) Формируется код второго и третьего разрядовЫцисла, пои этом используются энацейчУиФЧ("ч)-ч(х") 8 8 где х=х "+1, 1 с =0,4. Так, если х" =8, то формирование х выполняется согласно правилам 8, при О=Р(8 /8 )Р(98); 9, при Г(9 /8 )м с Г(10/8"); 10, при Г(138" Ме(11 й/8), 11, при Г(11/8 )фГ(12/8")1 Устройство может быть настроено на 2" независимых распределений Ч (х) или на однородный марковский процесс с 2 состояниями, При этом, для хранения множества значений условных функций распределения Гс(х/х"), соответствующих либо распределению Мс(х), либо Й-й строке матрицы переходных вероятностей марковского процесса, отводится одна страница или в блоке 4 памяти или в блоке 5 памяти. Загрузка выполнлется таким образом, что в блоке 5 памяти записываются значения Г(х/х 1 " ), обращение к.которым в процессе моделирования наиболее вероятно, оставшиеся значения Гс(х/хзаписываются в блоке 4 памяти.Пусть блок 5 памяти имеет четыре страницы, в запоминающее устройство"12 страниц, Пусть устройство настроено на моделирование 2 =16 независимых распределений либо марковского процесса с 16-ю состояниями, причем загрузка выполнена таким образом, что значения Г(х/х ) для 1=3, 7, 8, 12 записаны в блок 5 памяти, а для остальных 1- в блок 4 памяти. При этом соответствие номераадресу страницы блока 5 памяти или блока 4 памяти приведено соответственно в табл. 1 и 2.блок 8 памяти выполняет функции преобразования номера 1 с в адрес страницы блоков 4 или 5 памяти. Каждая ячейка блока 8 памяти содержит адрес страницы блоков 4 или 5 памяти и признак "П", единичное значение которого указывает, что страница находится в блоке 4, а нулевое значение указывает, что страница находится в блоке 5. На адресный вход блока 8 памяти с выхода блока 6 адреса поступает номер 1 с, в результате чего из %-й ячейки выполняется считывание номера страницы, Для случая, когда блоки 4 и 5 памяти загружены согласно табл. 1 и 2, загрузка блока 8 памяти должна соответствовать табл. 3.Расположение значений Е(х /х " ) внутри страницы может быть различ9 92273ным и определяется организацией блока 6 адресаВ предлагаемом устройстве значения Г(х/х ") располагаются по адресам 1, определяемым по формуле 5=С 1 х (1е=з 15 Иэ восьмой ячейки блока памяти 8 считывается адрес страницы 2 и признак "П"=0, по которому запрещается считывание информации из блока 4, выход блока 5 памяти подключается коммутатором 3 к входу схемы 2 сравнения, устанавливается быстрый цикл блока 7 управления, Из ячейки с двоичным адресом 0100 второй страницы блока 5 считываются значения 1 ГВ,(х"/О) . По У формируется равномерно распределенное число, по У выполняется сравнениеи значение Г 8(х /0) и т.д. аналогично предыдушрму за ис" клюцением того, что считывание зна" чений ГВ(х/х") выполняется иэ 1где г=п/в - число тактов ) работыустройства для формирования и-разрядного числа при моделированиина каждом такте щ разрядов числа.При п=4 и а=2 расположение значений Г(х/х" )1 внутри страницысоответствует табл,Рассмотрим работу устройства примоделировании независимых последовательностей случайных чисел, подчиняющихся 2 =16 функциям распределения, при этом загрузка запоминаю щих устройств 5, 4 и 8 выполненасогласно табл. 1"; 2 и 3 соответственно,На вход 13 установки режима блока6 поступает нулевой сигнал, опреде ляющий режим моделирования случайныхчисел.Пусть в регистре 9 установленномер распределения К=13.30По сигналу, поступающему на входзапуска блока 6, в регистре 10 устанавливается двоичный код 10100, содержимое младших разрядов которого(0100) передается на первый выходблока 6 и является адресом ячейкивнутри страницы памяти. Так как в регистре 9 установлен номер К=13 (момент времени й,1 на фиг. 4), то изтринадцатой ячейки блока 8 памятивыполняется считывание адреса страницы 9 и признака нПнв 1, разрешающе го считывание информации из блокаКоммутатор 3 подключает выходблока 4 к информационному входу блока 2 сравнения, блок 7 управлениянастраивается на медленный цикл, таккак предполагается считывание значений Г (х/х " ) из сравнительномедленного блока 4 памяти. В момент50времени С 5 вырабатывается сигнал У 1,по которому равномерно распределенное числопоступает с выхода датчика 1 на первый информационный входблока 2 сравнения, Одновременно навторой информационный вход блока 255сравнения с выхода блока 4 поступаютзначения 1 Г (х"/О), считанные изячейки с двоичным адресом 0100 девя-,8 10той страницы блока 4 памяти, По У выполняется сравнение числаи значений Г 15 (х" /0), в результате чего формируется двоичный код цоц 1 старших нулевого и первого разрядов случайного числа, который поступает на информационный вход блока 6, По У выполняется сдвиг содержимого регйстра 10 на в=2 разряда в сторону старших с записью в младшие, освобождаемые при сдвиге разряды, значений ц ц, в результате чего в регистре 10 устанавливается двоич- ный код 100.К моменту временииэ ячейки с двоичным адресом 00 о одевятой страницы блока 4 выполняется считывание значений 1 Г,(х/х") . В мо" мент 5 вырабатывается У,. формируется очередное равномерно распределенное случайное число. По У выполняется сравнение числас значениями Г (х/х )1, в результате чего формируется двоичный код цр,5 младших разрядов случайного чисга; По У выголняется сдвиг содержимого регистра 10, в результате чего в нем устанавливается двоичный код 0 Ч,ЧЧ,Ч где Чо Ч Чи Ч- собственно сформированное случайное число, а сигнал с 0-го выхода регистра 10 является признаком окончания формирования случайного числа. Срабатывает элемент 11 задержки, с выхода которого задержанный сигнал через элемент ИЛИ 12 устанавливает в регистре начальный двоичный код 10100, Далее цикл работы устройства повторяется.Пусть в регистре 9 установлен номер распределения К=8, в регистре 10 - начальный двоичный код 10100.112 2738 11 92блока 5, и цикл "работы блока 7 управления быстрый.Рассмотрим работу устройства,примоделировании однородных марковскихпроцессов с 2 16 состояниями, приеэтом загрузка запоминающих устройств5 4 и 8 выполнена согласно табл. 1,2 и 3 соответственно.На вход 13 установки режима блока6 поступает единичный сигнал, определяющий режим моделирования случай"ного марковского процесса.Пусть в регистре 9 установленоначальное состояние процесса 1=7.По списку, поступающему на вход 14дапуска блока 6, в регистре 10 устанавливается начальный двоичный код,10100. Из седьмой ячейки блока 8 считывается адрес страницы 1 и признак "П"щ 0 по которому запрещается чтение информации иэ запоминающего устройства 4, выход блока 5 памяти подключается коммутатором 3 к информационному входу схемы 2 сравнения, устанавливается быстрый цикл блска 7 управления. Иэ ячейки с двоичным адресом О 00 блока 5 счи"тываются значения Г(х/0) .Далее аналогично предыдущему вырабатываются сигналы У, У и У 5, в . результате 2 " циклов работы устройства в регистре 10 формируется двоичный код ОЧ,ЧЧЧ" Код ОЧоЧЧРЗ является очередным состоянием марковского процесса. Сигнал с нулевого выхода регистра 10 поступает на . С-вход регистра 9, и так как на Ч-входе регистра 0 присутствует разрешающий сигнал то код ЧОЧ 1 ЧЧ переписывается в регистр 9. далее срабатывает элемент 11 задержки, сигнал. с выхода которого через элемент ИЛИ 12 устанавливает в регистре Оначальный код 10100.Пусть сформированный код ЧЧЧЧ =щМ 5. Иэ пятой ячейки запоминающего 1 устройства 8 считывается адрес страницы 4 и признак нПнв 1 по которому разрешается считывание информации иэ блока 4 памяти, выход блока 4 подключается коммутатором 3 к выходу блока 2 сравнения, устанавливается медленный режим работы блока 7, Далее аналогично предыдущему формируется следующее состояние марковского процесса при условии, что считывание значений Г(х/х ")1 выпол 5 10 15 20 И 30 55 40 45 50 няется иэ четверти страницы устройства 4 при медленном цикле работыблока 7. Сформированное состояниепроцесса переписывается в регистр9, устанавливается начальный код10100 в регистре 10 и т.д.Если первый блок 4 памяти является каналом многоканальной памятиЭВМ, то работа устройства в целомне отличается от рассмотренной, заисключением того, что в ячейки блока8 памяти, содержащие значение признака "П=1, загружаются адреса областей оперативной памяти ЭВМ, в которых записаны значения Г(х 4 /х-" ,При считывании содержимого ячейкиблока 8 признак "П"=1 поступает навход запроса канала оперативной памяти, в результате чего канал выделяется для работы с устройством. Иэ ячейки с адресами, определяемыми кодамина адресных входах канала, считываются значения В(х/х-". Кактолько признак "П"=О, канал оперативной памяти освобождается,Перед началом моделирования выполняется загрузка блока 8 в соответствии с размещением значений Г(х/х)в оперативной памяти ЭВМ, Ограничений на расположение значенийГ(х/х " Ц в оперативной памяти ЭВМ не накладывается, что позволяет для управления устройством использовать программы с нефиксированным расположением в оперативнойпамяти ЭВМ.Таким образом, предлагаемое устройство обладает рядом техническихпреимуществ перед известными, таккак сочетает высокое быстродействиес эффективным использованием памяти,что достигается за счет применениябыстродействующего блока 5 памятидля хранения значении Г(х /х " )для тех М вероятность обращения ккоторым в процессе моделированиянаиболее высока, и сравнительномедленного блока 4 памяти для хранения значений 1 Г 1(х /х ) дляостальных М,Устройство целесообразно использовать совместно с ЭВМ, при этом управление им осуществляется программно, а программы управления могут загружаться в любую область оперативной памяти ЗВМ.ГИЛИ, второй регистр сдвига, входыустановки в единицу нулевого, а-го,2 а-го(и-в)-го разрядов и установки в нуль остальных разрядов которого соединены и подключены к выходу элемента ИЛИ, вход сдвига второгорегистра сдвига подключен к управляющему входу блока задания адреса,информационные входы младших в разрядов являются информационным входомблока задания адреса, выход нулевогоразряда второго регистра сдвига подключен к управляющему входу первогорегистра сдвига и к входу элементазадержки, выходы первого, второго(и"1)-го разрядов второго регистрасдвига являются первым выходом бло-ка задания адреса и подключены к ин.формационным входам соответственнопервого, второго (п 1)-го разря 2738 16дов первого регистра сдвига, выходыкоторого являются вторым выходомблока задания адреса, управляющийвход второго регистра сдвига соединен с входом установки режима блоказадания адреса, вход запуска блоказадания адреса соединен с первым вхо.дом элемента ИЛИ, второй вход которо.го соединен с выходом элемента за держки,Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРа И 378826, кл. 6 06 Г 1/02, 19712. Авторское свидетельство СССРМ 430368, кл, С 06 Г .1/02 19723Авторское свидетельство СССРй 488212, кл. С 06 Г 15/20, 1973ПодписноеСР каэ 25 2/ Тираж ВНИИПИ Государственно по делам изобретени 113035, Москва, Ж