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

1

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

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

ния случайного числа, входные и выходные вентили tn.

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

Недостатком известных устройств является низкое быстродействие, оп15ределяемое в основном временем считывания информации из блока памяти.

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

20 равномерно распределенных случайных чисел, схему сравнения, регистр маски, регистр числа, запоминающее устоойство и блок а-дреса на регистре имеющем младшую и старшую адреса, часть. Устройство позволяет формировать последовательности случайных- чисел с требуемыми законами распределения, а также марковские процессы. При этом реализуется метод обратных функций, основанный на сравнении равномерно распределенных случайных чисел с значениями воспроизво димой функции распределения F(x), отыскании интервала, для которого FCxiOfJ fCx t), и выдаче соответствующего данному интервалу значения х;. Устройство позволяет модели ровать 2 различных законов распределения, где п-разрядность старшей части нэегистра адреса. Выбор закона осуществляется записью номера требу емого закона в старшую часть регистра адреиса. На каждом такте работы устройств выполняется считывание кодов из запоминающего устройства, формировани равномерно распределенного случайного числа, сравнение кодов, запись в регистр блока адреса. Наибольшие временные задержки во никают при обращении к запоминающему устройству, которое имеет емкост порядка десятков и сотен тысяч байтов 3. Однако из-за конструктивных особенностей запоминающие устройства т кого объема имеют сравнительно невы сокое быстродействие, снижает быстродействие данного устройства. Цель изобретения - повышение быс тродействия устройства за счет орга низации двухуровневой памяти, для чего на первом уровне используется сверхбыстродействующее запоминающее устройство сравнительно небольшого объема, а на втором - запоминающее устройство большого объема и сравнительно невысокого быстродействия. Для достижения поставленной цели в генератор случайных чисел, содержащий датчик равномерно распределен ных случайных чисел, вход которого соединен с первым выходом блока управления, а выход датчика равномерно распределенных случайных чисел соединен с первым входом блока сравнения, второй вход которого подключен к второму выходу блока управления, а выход блока сравнения подключен к информационному входу блока задания адреса, управляющий вход которого 4 соединен с третьим выходом блока управления, а первый выход блока задания адреса соединен с первым адресным входом первого блока памяти, введены коммутатор, второй и третий блоки памяти, первый адресный вход второго блока памяти соединен с первым выходом блока задания адреса, второй выход которого соединен с входом третьего блока памяти, первый выход которого соединен с вторыми адресными входами первого и второго блоков памяти, а второй выход третьего блока памяти подключен к входу блока управления и управляющим входам первого блока памяти и коммутатора, первый информационный вход которого соединен с выходом первого блока памяти, второй информационный вход коммутатора соединен с второго блока памяти, а выход коммутатора соединен с вторым входом блока сравнения , вход установки режима и вход запуска блока задания адреса являются соответственно первым и вторым входами устройства. Кроме того, блок задания адреса содержит первый регистр сдвига, элемент задержки, элемент ИЛИ, второй регистр сдвига, у которого входы установки в единицу нулевого, т-го, 2т-го; ..., ( разрядов и установки в нуль остальных разрядов соединены и подключены к выходу элемента ИЛИ, вход сдвига второго регистра сдвига подключен к управляющему входу блока задания адреса, информационные входы младших tri разрядов являются информационным входом блока задания адреса, выход нулевого разряда второго регистра сдвига подключен к управляющему входу первого регистра сдвига и к входу элемента задержки, выходы первого, второго, ..., (n-l)-ro разрядов второго регистра сдвига являются первым выходом блока задания адреса и подключены к информационным входам соответственно первого, второго, ...,(п-1)-го разрядов первого регистра сдвига выходы которого являются вторым выходом блока задания адреса, управляющий вход второго регистра сдвига соединен с входом установки режима блока задания адреса, вход запуска блока задания адреса соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом элемента задержки. Указанные изменения приводят к увеличению быстродействия устройства за счет организации двухуровневой памяти, где первый уровень со тавляют сверхбыстродействующие второе и третье запоминающие устройств cpaвниteльнo малого объема, а второй уровень - первое запоминающее устройство большого объема и сравнительно невысокого быстродействия. На фиг. 1 приведена структурная схема генератора; на фиг. 2 - функциональная схема блока адреса; на фиг, 3 функциональная схема блока управления; на фиг. - временная диаграмма сигналов на входе и выходах блока управления. Генератор . содержит датчик 1 рав номерно распределенных случайных чисел, блок 2 сравнения, коммутатор 3, первый блок k памяти, второй блок 5 памяти, блок 6 задания адреса, блок 7 управления и третий блок 8 памяти. Блок 6 задания адреса содержит первый регистр 9 сдвига и второй регистр 10 сдвига, элемент 11 задер ки и элемент ИЛИ 12. Блок 6 имеет вход 13 установки режима и вход 1 запуска. Блок 2 управления содержит элеме И 15, элемент 16 задержки, триггер 17 с установочными входами, генератор 18 импульсов и элемент 19 задер ки с двумя выходами. Рассмотрим функции, выполняемые структурными компонентами устройства. Датчик 1 формирует независимые, распределенные на интервале 0-1 слу чайные числа. Очередное число выраба тывается датчиком по сигналу на его входе. Коммутатор 2 выполняет подключение к входу схемы 2 сравнения при одиночном сигнале на управляющем вхо де выхода блока Ц и при нулевом сигнале на управляющем входе выхода блока 5 Блоки 5 и 8 памяти сверхбыстродей ствующие, блок памяти - обычное запоминающее устройство, например, на ферритовых сердечниках. Блоки и.5 памяти имеют первые адресные входы, определяющие адрес ячейки внутри страницы, и вторые адресные входы, определяющие собственно адрес страницы. Блок Ц памяти имеет также управляющий вход, единичный сигнал на 8 6 котором разрешает работу устройства в режиме считывания. Блок 8 памяти имеет два выхода. При считывании информации из ячеек устройства 8 п разрядов считанного кода поступают на первый выход, а (п+-1)й разряд - на второй выход блока 8. Блок 6 содержит первый п -разрядный регистр 9, второй (п+1)-разрядный регистр 10, элемент 11 задержки и элемент ИЛИ 12. Вход 13 установки режима позволяет настраивать блок 6 либо на формирование случайных п-разрядных чисел (нулевой сигнал на входе 13) либо на формирование состояний однородного марковского процесса, имеющего два состояния (единичный сигнал на входе 13). Вход 1 запуска предназначен для установки начального состояния регистра 10. Регистр 10 служит для формирования случайного числа (или случайного состояния марковского процесса) и .имеет S-входы установки в единицу 0-го, т-го, 2т-го, ... (п-т)-го разряда, R-входы установки в нуль остальных разрядов, информационные 0-входы младших m разрядов и управляющий С-вход сдвига в сторону старших m разрядов. В процессе моделирования содержимое регистра 10 (разряды 1-п ) определяет адрес ячейки внутри страницы. Регистр 9 предназначен для хранения в процессе моделирования либо номера V. формируемого распределения случайных чисел ix), лиЬо предыдущего состояния марковского процесса и имеет информационные D-BXOды 0-го, 1-го, ... (п-1)-го разрядов, управляемый С-вход занесения информации, управляющий V-вход разрешения занесения информации. В процессе моделирования содержимое регистра 9 определяет адрес страницы запоминающего устройства. Блок 2 сравнения на каждом j-м такте работы устройства формирует m разрядов случайного числа в результате сравнения по методу обратных функций равномерно распределенного случайного числа и значений дискретной условной функции распределения F(), где значение случайного числа. сформированного на j-1 предыдущих тактах работы устройства. Блок 7 управления служит для генерирования тактовых импульсов Y, Y, Yj, качестве примера конкретного выполнения на фиг. 3 приведена функциональная схема блока 7 а на фиг. Itвременные диаграммы сигналов на его входе и выходах. В момент запуска триггер 17 устанавливается в единичное состояние. Запускаются генератор 18, вырабатывается сигнал 1, поступающий на элемент 19 задержки, на выходах которого последовательно возникают сигналы Yn и Y (фиг., момент tQ-t). Если сигнал П имеет нулевое значение, то элемент И 15 закрыт, триггер 17 состояния не изменяет, и по очередному сигналу Y генератора 18 сигнал повторяется. Такой цикл блока 7 будет называть быстрым Если сигнал П имеет единичное значение, тЬ импульс У. проходит через элемент И 15 на вход элемента 16 задержки и одновременно сбрасывает триггер 17. Работа генератора 18 прерывается (момент t , фиг. Ц} В момент t -j выходной сигнал элемента 16 задержки устанавливает триггер 17 в единичное состояние, запус аетсЯ генератор 18, вырабатывается и т.д. Такой цикл называть мед лениым. Работу устройства для вероятностного моделирования рассмотрим на примере генерирования последовательности случайных чисел, распределенных на интервале 10-153. разрядности пе(, подчиняющихся ФУНКЦИИ распределения, которая представлена значения ми в равноотстоящих точках квантования ,1б. При этом на каждом такте работы устройства формируется разряда чисел. На первом такте () работы устройства формируется код старших нулевого и первого разрядов числа, при этом используются значения дискретной условной функции распределения F(x/o)/(x), а собственно формирование выполняется согла но правилам О, при (0) Ч(4); . I , при ЧС), (8); 8, при Ч(8.)Л 4(12); J2, при 4(12)t| (1б)1. На втором такте (J-2) формирует- ся код второго и третьего разрядо числа, пои этом используются значе f()..: l(ic+4)-4lX) 8 Где x x+k, ,. Так, если , то формирование х выполняется согласно правилам 8, при (8j/8) Э. при F( (); 10, при F( FdiVa-); In, при F(nV8K f5 F{12V8)1 Устройство может быть настроено на 2 независимых распределений f (х) или на однородный марковский процесс с 2 состояниями. При этом, для хранения множества значений условных функций распределения fF| (х-/х , соответствующих либо распределению Ч(х), либо k-й строке матрицы переходных вероятностей марковского процесса, отводится одна страница или в блоке памяти или в блоке 5 памяти. Загрузка выполняется таким образом, что в блоке 5 памяти записываются значения lF,( Л , обращение к которым в процессе моделирования наиболее вероятно, оставшие{FjxVx - ) ся значения И записываются в блоке k памяти. Пусть блок 5 памяти имеет четыре страницы, в запоминающее устройство -12 страниц. Пусть устройство настроено на моде; ирование 2 1б независимых распределений либо марковскоГО процесса с 1б-ю состояниями, причем загрузка выполнена таким образом, чТо значения ft(x./)) для 7. 8, 12 записаны в блок 5 памяти, а для остальных - в блок Ц памяти. При этом соответствие номера Ч адресу страницы блока 5 памяти или блока памяти приведено соответственно в табл. 1 и 2. Блок 8 памяти выполняет функции преобразования номера i в адрес страницы блоков k или 5 памяти. Каждая ячейка блока 8 памяти содержит адрес страницы блоков k иЛи 5 памяти и признак П, единичное значение которого указывает, что ст|эаница находится в блоке k, а нулевое значение указывает, что страница находится в блоке 5. На адресный вход блока 8 памяти с выхода блока 6 адреса поступает номер k, в результате чего из ячейки выполняется считывание номера страницы. Для случая, когда блоки i и 5 памяти загружены согласно табл. 1 и 2, загрузка блока 8 памяти должна соответствовать табл. 3Расположение значений F (xVx- ) внутри страницы может быть различным и определяется организацией бло ка 6 адреса. В предлагаемом устройстве значения {р()j располагаются по адрес.ам i , определяемым по фоомуле , I где - число тактов j работы устройства для формирования п-разрядного числа при моделировании на каждом такте m разрядов числа. При п и расположение значений ) внутри страницы соответствует таб,л.. Рассмотрим работу устройства при моделировании независимых последовательностей случайных чисел, подчиняющихся функциям распределения, при этом загрузка запоминающих устройств 5 и 8 выполнена согласно табл. Ц 2 и 3 соответственно, На вход 13 установки режима блок 6 поступает нулевой сигнал, опреде ляющий режим моделирования случайны чисел. Пусть в регистре 9 установлен номер распределения . По сигналу, поступающему на вход запуска блока 6, в регистре 10 уста навливается двоичный код 10100, содержимое младших разрядов которого (0100) передается на первый выход блока 6 и является адресом ячейки внутри страницы памяти. Так как в р гистре 9 установлен номер (момент времени t,j на фиг. ), то из тринадцатой ячейки блока 8 памяти выполняется считывание адреса страницы 9 и признака , разрешающе го считывание информации из блока Ц. Коммутатор 3 подключает выход блока 4 к информационному входу бло ка 2 сравнения, блок 7 управления настраивается на медленный цикл, та как предполагается считывание значений F (xVx ) из сравнительн медленного блока Ц памяти. В момент времени t вырабатывается сигнал У по которому равномерно распределенное число поступает с выхода датчика 1 на первый информационный вхо блока 2 сравнения. Одновременно на второй информационный вход блока 2 сравнения с выхода блока k поступаю значения {р j()J, счи танные из ячейки с двоичным адресом 0100 девя ТОЙ страницы 6jriOKa памяти. По У( выполняется сравнение числа и значений {F ;|j ()J , в результате чего формируется двоичный код старших нулевого и первого разрядов случайного числа, который поступает на информационный вход блока 6. По УЛ выполняется-сдвиг содержимого регистра 10 на разряда в сторону старших с записью в младшие , освобождаемые при сдвиге разряды, значении в результате чего в регистре 10 устанавливается двоичный код 100. К моменту времени tj из ячейки с двоичным адресом.00 девятой страницы блока Ц выполняется считывание значений р -Vj(xVx) . В момент tj вырабатывается У ,. формируется очередное равномерно распределеннов случайное число 5 . По У выполняется сравнение числа с значениями F )|() , в результате чего формируется двоичный код младших разрядов случайного числа. По У выполняется сдвиг содержимого регистра 10, в результате чего р нем устанавливается двоичный код очоЧл аЧ де qo qij. ч собственно сформированное случайное число, а сигнал с 0-го выхода регистра 10 является признаком окончания формирования случайного числа. Срабатывает элемент 11 задержки, с выхода которого задержанный сигнал через элемент ИЛИ 12 устанавливает в регистре начальный двоичный код 10100. Далее цикл работы устройства повторяется. Пусть в регистре 9 установлен номер распределения , в регистре 10 - начальный двоичный код 10100. Из восьмой ячейки блока памяти 8 считывается адрес страницы 2 и признак , по которому запрещается считывание информации из блока k, выход блока 5 памяти подключается коммутатором 3 к входу схемы 2 сравнения, устанавливается быстрый цикл блока 7 управления. Из ячейки с двоичным адресом 0100 второй страницы блока 5 считываются значения FQ.() . По У , формируется равномерно распределенное число , по yiji выполняется сравнение изначение Рд(х VO)} и т.д. аналогично предыдушэму за исключением того, что считывание значений Pg(xVx) выполняется из 11 блока 5 и цикл работы блока 7 упра ления быстрый. Рассмотрим работу устройства ,при моделировании однородных марковских процессов с 2 16 состояниями, при этом загрузка запоминающих устройст St 4 и 8 выполнена согласно табл. 1 2и 3 соответственно. На вход 13 установки режима блок 6 поступает единичный сигнал, определяющий режим моделирования случай ного марковского процесса. Пусть в регистре 9 установлено начальное состояние процесса 7По списку, поступающему на вход 14 запуска блока 6, а регистре 10 уста навливается начальный двоичный код , 10100. Из седьмой ячейки блока 8 считывается адрес страницы 1 и признак , по которому запрещается чтение информации из запоминающего устройства Ц, выход блока 5 памяти подключается коммутатором 3к информационному входу схемы 2 сравнения, устанавливается быстрый цикл блока 7 управления. Из ячейки с двоичным адресом 0100 блока 5 счи тываются значения {р7()| . Далее аналогично предыдущему вырабатываются сигналы У-i, XQ и У , в результате 2 циклов работы устрой ства в регистре 10 формируется двоЫный код ,qз..Koд Oq q qijiq является очередным -состоянием марковского процесса. Сигнал с нулевог выхода регистра 10 поступает на С-вход регистра 9i и так как на V-входе регистра О присутствует раз решающий сигнал, то код (1Чз переписывается в регистр § Далее срабатывает элемент 11 задержки, си нал с выхода которого через элемент ИЛИ 12 устанавливает в регистре 10 начальный код 10100. Пусть сформированный код гв|(«5. Из пятой ячейки запоминающего устройства 8 считывается адрес стра ницы k и признак , по которому разрешается считывание информации из блока k памяти, выход блока Ц по ключается коммутатором 3 к выходу блока i сравнения, устанавливается медленный режим работы блока 7. Далее аналогично предыдущему формируется следующее состояние марковского процесса при условии, что считывание значений р5() выпол8няется из четверти страницы устройства 4 при медленном цикле работы блока 7 Сформированное состояние процесса переписывается в регистр 9 устанавливается начальный код 10100 в регистре 10 и т.д. Если первый блок памяти является каналом многоканальной памяти ЭВМ, то работа устройства в целом не отличается от рассмотренной, за исключением того, что в ячейки блока 8 памяти, содержащие значение признака , загружаются адреса областей оперативной памяти 3BMj в которых записаны значения {рц(), При считывании содержимого ячейки блока 8 признак поступает на вход запроса канала оперативной памяти, в результате чего канал выделяется для работы с устройством. Из ячейки с адресами, определяемыми кодами на адресных входах канала, считываются значения ). Как только признак , канал оператопкип ияияп nnonaтивной памяти освобождается. Перед началом моделирования выполняется загрузка блока 8 в соответствии с размещением значений ) )} в оперативной памяти ЭВМ. Ограничений на 0а сположение значений {FK(X,)5 в оперативной памяти ЭВМ не накладывается, что позволяет для управления устройством использовать программы с нефиксированным расположением в оперативной памяти ЭВМ. Таким образом, предлагаемое устройство оёладает рядом технических преимуществ перед известными, так как сочетает высокое быстродействие с эффективным использованием памяти, что достигается за счет применения быстродействующего блока 5 памяти для хранения значений {Р,((х ) вероятность обращения к которым в процессе моделирования наиболее высока, и сравнительно медленного блока k памяти для хранения значений {r(xJ/Х ) для остальных 1. Устройство целесообразно использовать совместно с ЭВМ, при этом управление им осуществляется программно, а программы управления могут загружаться в любую область оперативной памяти ЭВМ.

3922738Щ

Адрес страницы п i - 7

блока 5...

Номер k3 7 8 12

Адрес страницы блока It 0123 56789 10 12

Номер к.О12 5б910111311 15

-----. - - . -

Адрес ячейки блока 80123 56789101112131 15

..п....«..«...... .

Содержимое Номер страячейки бло- ницы (р-ды О 1 2 О 3 5 1 2 6 7 8 3 9 10 11

ка 8 :)

l lill IIIIIIIIIIIII

Номер такта j 1 2 .2 22

Значение к ООЦ8 12

Адрес ячейки в

странице 0100000000010010ООП

Содержимое F,(xVO)} () () Р ) Рк(12)

ячейки Формула изобретения 1. Генератор случайных чисел, содержащий датчик равномерно распределенных случайных чисел, вход которого соединен с первым выходом блока управления; а выход датчика равномерно распределенных случайных чисел соединен с первым входом блока сравнения, второй вход которого подключен к второму выходу блока управления, а выход блока сравнения подключен к информационному входу блока задания адреса , управляющий вход которого соеди нен с третьим выходом блока управления, а первый выход блока задания адреса соединен с первым адресным входом первого блока памяти,- отличающийся тем, что, с целью повышения быстродействия устройства, он содержит коммутатор, второй и третий блоки памяти, первый адресный вход второго блока памяти соединен с

Таблица}

Т а б л и ц а 2

IТ а б Л и Ц а 3

Таблица первым выходом блока задания адреса, второй выход которого соединен с входом третьего блока памяти, первый выход которого соединен с вторыми адресными входами первого и второго блоков памяти, а втброй выход третьего блока памяти подключен к входу блока управления и управляющим входам первого блока памяти и коммутатора, первый информационный вход которого соединен с выходом первого блока памяти, второй информационный вход коммутатора соединен с выходом второго блока памяти, а выход коммутатора соединен с вторымвходом блока сравнения, вход установки режима и вход запуска блока задания адреса являются соответственно первым и вторым входами устройства. 2. Генератор по п. 1, отличающийся тем, что блок задания адреса содержит первый регистр сдвига, элемент задержки, элемент ИЛИ, второй регистр сдвига входы установки в единицу нулевого, т-го, 2т-го ... (п-т)-го разрядов и установки в нуль остальных разрядов которого соединены и подключены к выхо ду элемента ИЛИ, вход сдвига второго регистра сдвига подключен к управляющему входу блока задания адреса, информационные входы младших m разрядов являются информационным входом блока задания адреса, выход нулевого разряда второго регистра сдвига подключен к управляющему входу первого регистра сдвига и к входу элемента задержки, выходы первого, второго... (n-l)-го разрядов второго регистра сдвига являются первым выходом блока задания адреса и подключены к информационным входам соответственно первого, второго... (n-l)-ro разря9816 дов первого регистра сдвига, выходы которого являются вторым выходом блока задания адреса, управляющий вход второго регистра сдвига соединен с входом установки режима блока задания адреса, вход запуска блока задания адреса соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом элемента задержки. Источники информации, принятые во внимание при эксЬертизе 1.Авторское свидетельство СССР Vf 378826, кл. G 06 F 1/02, 1971. 2.Авторское свидетельство СССР № i 30368, кл. G Об F 1/02, 1972. 3.Авторское свидетельство СССР № 488212, кл. G Об F 15/20, 1973 (прототип).

t