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

СОЮЗ СОВЕТСНИХСОЦИА ЛИСТ ИЧЕСНИХРЕСПУБЛИН(51)5 С 06 Р 7 58 ОПИСАНИЕ ИЗОБРЕТЕНИЯ сФ ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОЧНРЫТИЯМПРИ ГКНТ СССР Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Казанский государственный университет им. В.И,Ульянова (Ленина) (72) В.М.Захаров, С.Е.Кузнецов, И,И.Макаров, В.И.Пермитин и Ф.И.Салимов(56) Авторское свидетельство СССР В 1008738, кл. С 06 Р 7158, 1983,Авторское свидетельство СССР У 1524048, кл. С 06 Р 7/58, 19882(54) ГЕНЕРАТОР СЛУЧАИНЫК ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в качестве задающего блока в имитаторах случайных процессов, а также в качестве специализированного вероятностного процессора. Цель изобретения - повьюнение быстродействияГенератор содержит блокпамяти, элемент ИЛИ 2, мультиплексор 3, регистр 4, элемент ИЛИ 5, элемент 6 задержки, элемент ИЛИ 7, регистры 8-10, блок 1 1 памятиузел1599856 Регат адреса Рог. Составитель И.Столяроведактор А.Маковская Техред М,Дндык Коррект аксимишинец рствен 113ивизводственно-издательский комбинат "Патент", г. Ужгор Гагарина, 10 Заказ 3144 ВНИИПИ Гос Тираж 5 го комит 5, Москв Ях%1 Фг) фиг=1 Е РЯ=РЯ3р 1 Подписное изобретениям и открытиям при Раушская наб., д. 4/5 е1599856 20, счетчик 21, регистр 22, блок 23 памяти, элемент 24 задержки. Поставленная цель достигается за счет введения новых связей и блоков. 1 з,п.ф-лы, 6 ил., 5 табл. Изобретение относится к вычислительной технике, предназначено для генерации последовательностей случайных чисел с заданным законом распределения и может быть использовано в качестве задающего блока в имитаторах случайных процессов, а также в качестве специализированного вероятностного процессора, подключенного к универсальной вычислительной технике.Пель изобретения - повышение быстродействия.На Фиг. 1 изображена структурная схема генератора; на Фиг.2 . - Функцио нальная схема узла синхронизации; на фиг.З - граф, поясняющий циклическую последовательность выбора команд; на Фиг.4 показано содержимое ячеек, хранящих команды; на фиг.5 изображены временные диаграммы реализации команд; на Фиг.6 дана иллюстрация заполнения блока памяти выходными Р 1 ф РффРю ххуьхд,Р , Р ,Р,У У,фу У(2) значениями,Генератор (Фиг.1) содержит блок1 памяти, элемент ИЛИ 2, мультиплексор 3, регистр 4, элемент ИЛИ 5,эле-,мент 6 задержки, элемент ИЛИ 7, реги"стры 8-10, блок 11 памяти, узел 12синхронизации, сумматоры 13, 14, схему 15 сравнения, элемент И 16, блок4017 мультиплексоров, регистр 18, дат-.чик 19 равномерно распределенных случайных чисел, элемент ИЛИ 20, счетчик 21, регистр 22, блок 23 памяти,45элемент 24 задержки.Узел 12 синхронизации (фиг.2) содержит элемент ИЛИ 25, элемент 26 задержки, В 5-триггер 27, элемент И 28,генерато29 тактовых импульсов, эле 50менты 30, 31 задержки, мультиплексор 32, блок ЗЗ памяти, регистр 34,блок 35 элементов И, элемент 36 задержки.В основе работы генератора лежатследующие теоретические положения.55В генераторе получение текущегослучайного числа х; для заданногораспределения 12 синхронизации, сумматоры 13, 14,схему 15 сравнения, элемент И 16,блок 17 мультиплексоров, регистр18, датчик 19 равномерно распреде;ленных случайных чисел, элемент ИЛИ где Р , - вероятность появления чисМла х и , Р, = 1, производится с помощью вспомогательного (имплицирующего) распределения (вектора) где Р - вероятность появления числа3юиу и Р; =1, 2 шп;1=1и - число двоичных разрядов для кодирования равномерно распределенных случайных чисел.На первом шаге формируется значение у, а на втором производится Функциональное преобразование значения у; в значение х ф. Выполнение шага 1 для формирования последующего числа совмещено со временем выполнения шага 2, относящегося к процессу формирования теущего числа х.Имплицирующее распределение (2), соответствующее заданному распределению (1), предварительно вычисляется по известному алгоритму.Формирование значений у, в генераторе производится по следующему алгоритму, являющемуся модификацией алгоритма Уэлкера. Сначала вычисляются данные, которые заносятся в блок 1 памяти по следующему правилу.Пусть К = 1 о 8 ю ,(а 1 - целое, не меньшее а), Разбиваем интервал (0,1) на 2равных интервалов с ф 2 ф2 к 2 В)ьф 2 Г ъ2 -12" 1215 159пронумеруем их числами 0,12-1.Ксоответственно. Поскольку ш ( 2 , тосреди чисел Р,. ,Р найдется Р1Ставим интервалу с номером2О в соответствие число у , а Р заФ1меняем на число Р, - ( - ) (это со 2ответствует тому, что в блок 1 памяти в ячейку с адресом О записывается число у ), Теперь остается 2 - 1 интервал и с отличных от нуля чисел в последовательности Р Р,(й = = ш или й ш), Если й . 2 - 1,1то вновь выбирается Р. В - , а3 2сопоставляется интервалу 1, из1вычитается -- (т.е. в блоке 1 памя 2ти устройства число узаписывается в ячейку с адресом 1), и так продолжается до тех пор, пока число С ненулевых чисел в последовательности РР, не станет больше (ровно на единицу) числа интервалов, которым не сопоставлены числа. Без потери общности считаем., что числаР,Р ненулевые. Интервалы, которым не сопоставлены числа у , оск тались с номерами 2 - й + 121. Далее применяется рекурсивная процедура М(С).Описание процедуры М(с) .1 (Вход: числа Р,Р , интервалы с номерами 2 - й + 1 2, - 1.1. Если среди Р,Р есть Р1 3то (2 - С + 1)-му интервалу2 "ф .сопоставляется число у (т.е. в блок 1 памяти в ячейку с номером 2 - С + 1 записывается у,), число Р заменяется на О и применяется процедура М( 1)2. Если среди чисел Р Рф ф1нет равных в " то выбираются такие2 к 111 6 и Ре что Рь Ре -2 к, а Р 2 к (легко увидеть, что такие два числак( всегда найдутся) . (2 - е + 1)-му интервалу сопоставляются два числа 2 2 - е + 1/2 + Р и А (содерк к 9856 6жательно в блоке 1 памяти в ячейкус адресом 2 - й + 1 помещаются чискла 2 и А, а в ячейках с адресами.5А и А + 1 - числа у и у соответ. ственно). Рз заменяется на О, а Р 1на Р + Р - . Если РО то ос 5 е 2 е ф10талось йчисло и Тинтервала. Далее применяется процедура И(й) .Если РО, то имеется й - 2 ненулевых числа и столько же интервалов.В этом случае делается шаг, описан 15 ный Ранее.Далее выполняются процедуры формирования значений у,Шаг 1. По первьвю Я разрядам случайного числа , получаемого от дат 20 чика 19, считывается из блока 1 памя-,ти слово с адресом Ф), гдез -йдвоичный код первых В разрядов ,К - двоичный код начальной базы адреса, Если это у , то процесс закончен за одно обращение к памяти.Щаг,2. Если это слово состоит изчисел 2 и А, то производится сравнение: если 2, то считывается число у из ячейки с адресом (А+1), в30 противном случае считывается уиэячейки с адресом А, т.е. процесс заканчивается. за два обращения к памяти.Наг 3. Если же слово с адресомсостоит из базы адреса А, тоь йсчитывается из ячейки с адресом А ++ у (где у - смещение) двоичный кодследующих разрядов числаи повторяется шаг 1. Алгоритм работает, по 40 ка не считывается слово у .При работе устройства йроисходитциклическое считывание из блока памяти команд (К, К, К, К) с после. дующей реализацией этих команд, Ал 5 горитм работы изображен на фиг.3.Формат выполняемых команд показан на фиг.4. Поле 1 содержит кодоперации, поле 2 команды К - число.5 2Р(у), поле 3 - тип операнда;в командах 1, К,К - это база относительного адреса (А), в командеК- это код у; (значение имплицирующего вектора).По команде К, определяется отрезок интервала, в который попало число , и формируется адрес команды15 Узел 12 синхронизации начинает работать по сигналу "Пуск", посту в , пающему через элемент ИЛИ 25, или по сигналу С;. По этому сигналу триг гер 27 открывает элемент И 28 через время, определяемое элементом 26 задержки, необходимое для считывания команд в регистры 8-10. Через элемент И 28 с генератора 29 тактовых 4 О импульсов поступает серия импульсов, число импульсов в которой зависит от команды К; (1 = 1,4). Под действием каждого импульса этой серии происходит считывание из блока 33 памяти в регистр 34 одной микрокоманды. Адрес очередной микрокоманды поступает из регистра 34 через мультиплексор 32 в блок 33 памяти под действием управгяющего сигнала С Частота импульсов считывания, поступающих от генератора тактовых импульсов,определяется быстродействием блока 33 памяти. Выходные значения считываются из блока 11 памяти. Иллюстрацию заполнения блока 11 значениями х показаны на фиг,6. По команде К уточняется дальнейшее положение числана интервале ,и формируется адрес команды К или команды К, или команды К 4.По команде К число хсчитывает 5 ся на выход устройства.По команде К уточняется интервали формируется адрес команды К или команды К 4 ОВсе команды (К, - К) реализуются с помощью микрокоманд, которые вырабатываются в узле 12, Последовательность выполнения команды К показана в табл.1; команды К - в табл,2;.команды Кз - в табл,З; команды К- в табл,4.Генератор работает следующим об" разом.По сигналу "Пуск" по адресу, определяемому регистром 4, происходит считывание из блока 1 памяти команды К, и запуск датчика 19. Дальнейший алгоритм работы устройства изображен на фиг.З . Управление функциони рованием генератора осуществляется узлом 12 синхронизации. Работу узла12 поясняет табл.5, Временные диаграммы управляющиХ сигналов на выходе узла 12 показаны на фиг.5. 30 Формула изобретения 1, Генератор случайных чисел,содержащий первый блок памяти, датчик равномерно распределенных случайных чисел, первый сумматор, четыре регистра, четыре элемента ИЛИ, первый эле" мент задержки, мультиплексор, схему сравнения, узел синхронизации, первый выход узла синхронизации соединен с первыми входами первого и второго элементов ИЛИ, второй выход узла синхронизации соединен с первым входом третьего элемента ИЛИ, причем второй вход первого элемента ИЛИ соединен с вторыми входами второго и третьего и с первым входом четвертого элементов ИЛИ, входом запуска узла синхронизации и является входом "Пуск" генератора, выход первого элемента ИЛИ соединен с входом разрешения считывания первого блока памяти, первый, второй и третий информационные выходы которого соединены соответственно с информационными входами первого, второго и третьего регистров, тактовые входы которых соединены с выходом первого элемента задержки, вход которого соединен с выходом второго элемента ИЛИ, адресный вход первого блока памяти соединен с выходом мультиплексора, первый информационный вход которого соединен с выходом четвертого регистра, выход третьего элемента ИЛИ соединен с управляющим входом мультиплексора, второй информационный вход которого соединен с выходом первого сумматора, выход четвертого элемента ИЛИ соединен с тактовым входом датчика равномерно распределенных случайных чисел, выход первого регистра соединен с входом задания режима узла синхронизации, о т л и - ч а ю щ и й с я тем, что, с целью повышения быстродействия, в него введены два. регистра, блок мультиплексоров, счетчик, второй и третий блоки памяти, элемент И, второй сумматор, второй элемент задержхи, причем выход второго регистра соединен с первым входом схемы сравнения, второй вход которой соединен с информацион" ным входом блока мультиплексоров и с выходом пятого регистра,информационный вход которого соединен с выходом датчика равномерно распределенных случайных чисел, тактовый вход пято9856 9 159 го регистра соединен с третьим выходом узла синхронизации, управляющий вход блока мультиплексоров соединен с выходом второго блока памяти, вход разрешения считывания которого соединен с выходом второго элемента задержки, вход которого соединен с четвертым выходом узла синхронизации, старшие разрядные адресные входы второго блока памяти соединены с соответствующими разрядными выходами . шестого регистра, младшие разрядные адресные входы второго блока памяти соединены с разрядным выходом счетчика, тактовый вход и вход сброса которого соединены соответственно с пятым и шестым выходами узла синхронизации, выход блока мультиплексоров соединен с первым входом второго сумматора, второй вход которого соединен с выходом элемента И, первый вход которого соединен с выходом "Равно" схемы сравнения, второй вход элемента И соединен с седьмым выходом узла синхронизации, выход второго сумматора соединен с первым информационным входом первого сумматора, второй информационный вход которого соединен с выходом третЬего регистра и с адресным входом третьего блока памяти, выход которого является выхо" дом генератора, тактовый вход первого сумматора соединен с восьмым выходом узла синхронизации, вход разрешения считывания третьего блока памяти соединен с девятым выходом узла синхронизации, десятый выход узла синхронизации соединен с вторым входом четвертого элемента ИЛИ.)о2Генератор по п. 1, о т л и ч аю щ и й с я тем, что узел синхронизации содержит четыре элемента задержки, ЕЯ-триггер, элемент И, генератор тактовых импульсов, мультиплексор, блок памяти, регистр, блок элементов И, причем первые десять выходов блока элементов И являются выходами узла, одиннадцатый выход блока элементов И через первый элемент .задержки соединен с первым управляющим входом мультиплексора, выход которого соединен с адресным входомблока памяти, выход которого соединенс информационным входом регистра,старшие разрядные информационные выходы соединены с первым входом блокаэлементов И, младшие информационные 20 разрядные выходы соединены с вторымуправляющим входом мультиплексора,выход элемента ИЛИ через второй элемент задержки соединен с Б-входомКВ-триггера, Р-вход которого соединен 25 с выходом элемента ИЛИ, выход триггера соединен с первым входом элемента И, второй вход которого соединен с выходом генератора тактовыхимпульсов, выход элемента И соединен у с входом чтения блока памяти и черезтретий элемент задержки - с тактовымвходом регистра, выход третьего элемента задержки через четвертый элемент задержки соединен с вторым входом блока элементов И, информационный вход мультиплексора является входом задания режима узла, первый входэлемента ИЛИ является входом запускаузла, второй вход элемента ИЛИ соединен с первым входом блока элементов И.15998 5 б 12 Та блица 1 Описание микроопераций Управляющиесигналы С 11 С, СиТаблица 2 Описание микроопераций Управляющиесигналы С, С СС,С, СМ 1.2.3.4. 1. 2. 3. 4. Считывание случайногочисла из датчика 19в регистр 18Считывание из блока23 памяти по адресу,образованному счетчиком 21 (младшие разряды адреса) и регистром 22 (старшие разряды адреса) сигналов,управляющих работой блока мультиплексоров 17(первый номер разбиения отрезка 0,1),и подключение к сумматору 13 адресапервого разбиенияМодификация адресав сумматоре 13Считывание иэ блока1 памяти очереднойкоманды по сформированному адресу Перевод счетчика 21 в значение, соответствующее следующему уровню распределенияСчитывание из блока23 памяти по адресу, образованному счетчиком 21 (младшие разрядн адреса) и регистром 22 (старшие разряды адреса) сигналов, управляющих работой блока 17 (второй номер разбиения отрезка О, 1),и подключение к сумматору 13 адреса второго разбиенияМодификация адреса в сумматоре 13Считывание из блока 1 памяти очередной команды по сформированному адресу13 1599856 Таблица 3 Описание микроапераций Управляющиесигналы . С, Си С, С С С Та блица 4, Описание микроопераций Управляющиесигналы С, С 1 С,о 3. С С 1.23.4. 1.2,По адресу, находящемуся в регистре 10 (значение имплицирующего вектора "у"), считывание на выход генератора из блока 11 памяти значения х.1" Запуск датчика 19 Считывание из блока 1 памяти команды по адресу, определяемому регистром 4 Сброс счетчика 21 в значение, соответствующее первому, уровню распреде- ления Считывание из блока 23 памяти по адресу, образованному счетчиком 21 (младшие разряды адреса) и регистром 22 (старшие разряды адреса) сигналов, управляющих работой блока 17 (текущий уровень распределения)Сравнение в схеме 15 содержимого регистров 9 и 18, выдача результата сравнения (О или 1) в младшие разряды сумматора 14 фи модификация адреса в сумматоре 13 Считывание из блока1 памяти следующейкоманды по сформированному адресу1599856 Команда Адресмикрокоманды Адресследующей микрокоманды 16Таблица 5управляющиесигналы