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

ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(46) 23,11.89. Бюл. Нф 43 (71) Казанский государственный университет им. В,И.Ульянова в Лени (72) Р,Г.Бухараев, Г.Г.Баранов, В.М.Захаров, С.Е.Кузнецов, Ю,С.Комаров, И.И.Макарон и В.И.Пермитин (53) 681.3(088,8)(56) Авторское свидетельство СССР Ь" 378826, кл. С 06 Р 7/58, 1973.Авторское свидетельство СССР 9 1008738, кл. С 06 Р 7/58, 1983. (54) ГЕНЕРАТОР СЛУЧА 1 БЬХ ЧИСЕЛ (57) Изобретение относит,.я к вычислительной технике и может быть испольэоваио в качестве специализированного вероятностного процессора.Цель изобретения - повьппение быстродействия. Генератор содержит блок1 памяти, элемент ИЛИ 2, мультиплексор 3, регистр 4, элемент ИЛИ 5,элемент 6 задержки, элемент ИЛИ 7,регистры 8-10, блок 11 элементов И,узел 12 управления, мультиплексор 13,регистр 14, сумматор 15, схему 16сравнения, регистры 17-18 сдвига,датчик 19 равномерно распределенныхслучайных чисел, элемент ИЛИ 20. Поставленная цель достигается засчет введения новых связей и блоков.7 ил., 5 табл,Изобретение относится к вычислительной технике и может быть использовано н качестве специализированного вероятностного процессора, подключенного к вычислительным универсальным машинам, а также в качествезадающего блока н имитаторах случайных процессов,Цель изобретения - повышение быстродействия.На фиг. 1 изображена функциональная схема устройства; на фиг. 2 -функциональная схема блока управления устройства; на фиг. 3 - циклическая последовательность выбора команд; на фиг. 4 - содержимое ячеек,хранящих команды; на фиг. 5 - временные диаграммы, поясняющие работу ге.нератора; на фиг. 6 - блок-схема сумматора; на фиг. 7 - блок-схема регистра сдвига.Генератор (фиг, 1) содержит блок 1памяти, элемент ИЛИ 2, мультиплексор3, регистр 4, элемент ИЛИ 5, элемент 256 задержки, элемент ИЛИ 7, регистры8-10, блок 11 элементов И, узел 12управления, мультиплексор 13, регистр14, сумматор 15, схему 16 сравнения,регистры 17 и 18 сдвига, датчик 19 30равномерно распределенных случайныхчисел, элемент ИЛИ 20.Узел 12 управления (фиг, 2) содержит элемент ИЛИ 21, расширитель22 импульсон, счетчик 23, элемент24 задержки, триггер 25, генератор26 тактовых импульсов, элементы И 27и 28, делитель 29 частоты, элементы30 и 31 задержки, мультиплексор 32,блок 33 памяти, регистр 34, блок 35 0элементов И, элемент 36 задержки,Сумматор 15 (фиг. 6) содержит комбинационный сумматор 37 и регистр 38.Регистр 17 сдвига содержит старшуючасть - (п-двухразрядный) регистр 39сдвига и младшую часть, - двухразрядный регистр 40 сдвига (и - число разрядов для представления случайногочисла),50Генератор работает следующим образом.В генераторе реализуется метод обратных функций, основанный на сравнении равномерно распределенных случайных чисел со значениями Р(х ) носпро 55 изводимой йункции распределения, отыскании интервала, для котороговыполняется условие Р(х;)(Р(х,),ц ныдаче соотнетстнующего данномуинтервалу значения х . Поиск интер 1вала производится логарифмическимперебором интервалов с основанием алогарифма перебора равным целой степени два, т.е. а 2 , где 1 - любоецелое положительное число, На каждомшаге перебора величина 1 может бытьпрограммно изменена с целью достижения оптимального компромисса междускоростью генерации случайных чисели объемом требуемой памяти. Реализа"ция алгоритма поиска требует проведения подготбвительпьх операций (поподготовке данных и их организациив памяти), которые могут быть программцо стандартизованы,Работа устройства сводится к циклической выборке из блока памяти команд (К,-К ) в соответствии с переходами (фиг. 3), где пунктиром обозначено начало циклов более длинных, но ималовероятных. Код х считывается на1выход устройства после выполнения команды К, или К , или К. Иллюстрацииалгоритма поиска даны н приложении.Содержимое ячеек, соответствующеекомандам, показано ца фиг. 4, где поле 1 содержит четырехразрядный кодоперации, поле 2 - двоичный код величины 1, поле 3 - тип операнда; длякоманд К, К и К - база (Л) относительного адреса, для К - код х;, дляВК - число Е= Р(х).-По команде К, по 1 старшим разрядам числаопределяется тот отрезокиз 2 равновероятных отрезков интервала 0, 2", где и - разрядностьчисел), н который попало числоПо команде К производится дальнейшее уточнение места расположениячислана ицтернале 0, 2 1 по сле 11 гдующим 1 старшим разрядам числа ,где 1 может быть меньше, равно илибольше 1. По команДе Кз производитсясчитывание кода х, из регистра командна выход устройства и пуск датчикаслучайных чиселдля нового цикла.По команде К производится пересылкабазы адреса иэ регистра команд в регистр адреса, По команде Кз реализуется указанное соотношение.Команды выполняются с помощью элементарных операций (микроопераций),1524048которые определяются микрокомандами,поступающими из блока 33 памяти, Микрокоманды задают последовательностьуправляющих сигналов (синхросигна 5лов), которые обеспечивают Выполнениемикроопераций (С,-С, ),Микрооперации, которые выполняютсяпо команде К 4 представлены в табл. 1.Таблица 1 1 ОМикрооперации в команде К, Управляющие сиг- налы 6Продолжение табл,2Считывание из блока памятикоманды К, по адресу, хранимому в регистре 4Таблица 3Микрооперации в команде К 4,Управляющие сиг- налыПересылка содержимого иэрегистра 10 в счетчик 23блока управленияСчитывание случайного числа иэ датчика 19 в регистр 18Сдвиг содержимого 1-старших разрядов регистра 18 вмладшую часть регистра 17 С,О,С,Образование адреса в сумматоре 15 путем суммирования в сумматоре содержимого регистров 10 и 17 С 5 рС 1 аСчитывание из блока памяти очередной команды посформированному в регистре 14 адресу С 8,С5 икрооперации в команде К Управляющие сигналы я содержимое рена выход устройчитывае гист а Запуск датчика 19 случайныхчисел Операция формирования адреса при выполнении команды К, производится по формуле Я=А+ 1 1, где А - база адреса хранимого в регистрах 14 или 1 О, 1 - смещение - двоичньм 1-разрядный код, хранимый в регистре 17,Результат суммирования записывается в регистр 40 сумматора.КомаНда К отличается от К тем, что в ней отсутствует считывание случайного числа из датчика в регистр.ПО команде КЭ К 4 К 5 ВыполнЯютсЯ микрооперации, представленные в табл. 2-4.Таблица 2Пересылка содержимого регистра 1 О в регистр 14 памяти . С, рС 1 дСчитывание из блока памяти команды К С 4,С,Таблица 4 Сравнение в схеме 16 содержимого регистров 10 и 18 и запись результата сравнения в регистр 17, при этом результат сравнения "меньше, равно" - единичный сигнал - поступает в первый разряд регистра 17, а результат больше" - единичный сигнал- поступает во второй разряд регистра 17Модификация адреса путем суммирования сгистров 14 и 1Считывание из одержимого ре 7блока памяти ледующеи команды пмированному адресу орГенератор начинает работать посигналу "Пуск", поступающему на элементы ИЛИ 2, 5, 7 и узел 12. Под действнем этого сигнала производится считывание из блока 1 памяти команды К, и включение датчика 19 случайных чисел. Дальнейшая выборка в соответствии с переходами (фиг.3) производится с помощью узла 12 управления, процесс выборки микрокоманд которого описывается в табл. 5. Временные диаграммы появления управляющих импульсов на выходе блока 35 элементов И при реализации команд Микрооперации в команде К Управля 1ющие сиг1524 048 Продолжение табл.5 КоманАдресмикрокоманны Содержимое ячейки Адрес Управляющиеследую- импульсыщей мнкрокоман 0000 1001 0000 0001 0000 00 О 000 0000 0001 ОО 100 0111 0001 ООО 0010 0001 ССС, С, СС, С, С, С С, С С,Кз Содержимое ячейки Адресмикрокоманды Команды Управляющиеимпульсы Адресследующей микрокоманды 001 0010 0000 0000 0011 0010 0001 С СС, сс ССе 0100 0011 0010 0001 010 К 00110010 К 55 К,-Кпоказаны на фиг5. Узел 12управления начинает работать по сигналу "Пуск", поступающему через элемент ИЛИ 21 или синхроимпульсу С.гПо этому импульсу триггер 25 открывает элемент И 28, (через промежутоквремени, определяемый величиной задержки элемента 24. Эта величинаопределяется временем считывания ко- Оманды К;,,5 в регистрах 8, 9,О памяти).Через открытый элемент И 28 от генератора 26 через делитель 29 поступает серия импульсов. Длина серии 15зависит от команды К;, (фиг, 5), каждый импульс в этой серии считьвает изблока 33 памяти в регистр 34 одну микрокоманду, Адрес очередной микроко. манды поступает из регистра 3 через 20мультиплексор 32 в блок 33 памяти поддействием синхроимпульса С, , Содержимое микрокоманд отражено в табл. 5,Каждому импульсу синхронизации С;,ь=1,12 соответствует кодв 1-ом 25разряде регистра 34. Частота импульсовсчитывания, поступающих из элементаИ 28, определяется быстродействиемблока 33 памяти,Блоки 23, 24, 27 и 28 формируют на выходе элемента И 27 серию(длины 1 тактовых импульсов сдвига,поступающих в регистры сдвига 18 и 17),По синхроимпульсу Сн производится запись в счетчик 23 содержимого регистра 9 (двоичный код величины 1). Посинхроимпульсу С о расширитель 22 формирует импульс длительностью, равнойпериоду считывания микрокоманд из блока памяти 33. Появление импульсов на 40выходе элемента И 27 прекращается вмомент обнуления счетчика 23,Таблица 5 Таким образом, в генераторе ускорение процедуры формирования случайных чисел достигается тем, что архитектура устройства позволяет использовать специальную поисковую процедуру, сочетающую параллельную реализацию логарифмического перебора с группировкой значений вероятностей случайных кодов, позволяющую учитывать структуру генерируемого распределения и соотношение разрядности случайных чисел и точности представления значений вероятностей. Это позволяет минимизировать среднее число обрашений к блоку памяти,Формула изобретения Генератор случайных чисел, содержащий блок памяти, датчик равномерно распределенных случайных чисел, сумматор, первый регистр сдвига, о тл и ч а ю щ и й с я тем, что, с целью повышения быстродействия, он содержит пять регистров, второй регистр сдвига Схему сравнения, два мультиплексора, четыре элемента ИЛИ, элемент задержки, блок элементов И иузел управления, который содержит элемент ИЛИ, два элемента И, расширитель импульсов, счетчик, генератор тактовых импульсов, КЯ-триггер, делитель частоты, четыре элемента задержки, мультиплексор, блок памяти, регистр и блок элементов И, выход элемента ИЛИ узла управления через первый элемент задержки соединен с 8-входом КЯ-триггера, К-вход которого соединен с выходом элемента ИЛИ узла управления, прямой выход КБ-триггера соединен с первым входом перво-го элемента И, выход которого через5 второй элемент задержки соединен с входом синхронизации регистра узла управления, старший разрядный выход которого соединен с первым информационным разрядным входом мультиплексора узла управления, выход которого соединен с адресным входом блока памяти узла управления, выход которого соединен с информационным входом регистра, вход синхронизации 15 блока памяти соединен с выходом первого элемента И, выход расширителя импульсов соединен с первым входом второго элемента И, второй вход которого соединен с выходом генератора 20 тактовых импульсов и подключен к входу делителя частоты, выход которого соединен с вторым входом первого элемента И, выход счетчика соединен с третьим входом второго элемента И, 25 выход которого соединен с счетнымвходом счетчика, выход второго элемента задержки через третий элемент задержки соединен е первым входом блока элементов И узла управленя, второй 30 вход которого соединен с соответствующими младшими разрядными выходами реги.тра узла управления, первый вход первого элемента ИЛИ соединен с первыми входами второго, третьего и 35 четвертого элементов И.П 1, с первым входом элемента ИЛИ узла управления и является входомПуск" генератора, выход первого элемента ИЛИ соединен с входом разрешения чтения блока па мяти, первый, второй и третий информационные выходы которого соединены соо гветственпо с информационными входами первого, второго и третьего регистров, входы синхронизации кото рых соединены с выходом элемента задержки, вход которого соединен с выходом третьего элемента ИЛИ, адресный вход блока памяти соединен с выходом первого мультиплексора, первый50 информационный вход которо о соединен с выходом четвертого регистра, выход второго элемента ИЛИ соединен с управляющим входом первого мультиплекеора, второй информационный вход55 которого соединен с выходом сумматора, первый и второй информационные входы которого соединены соответственно с выходами первого регистра сдвига и второго мультиплексора, первый и второй информационные входыкоторого соединены соответственно свыходами третьего и пятого регистров,выход четвертого элемента ИЛИ соединен с тактовым входом датчика равномерно распределенных случайных чисел,выход которого соединен с информационным входом второго регистра сдвига, старший информационный разрядныйвыход которого соединен с информационным входом первого регистра сдвига,разрядные выходы второго регистрасдвига соединены с первой группой разрядных входов схемы сравнения, выходы "1 феньше", "Равно" и "Больше" которой соединены с первым и вторым младшим информационным разрядным входомпервого регистра сдвига, выход третьего регистра соединен с первым входом блока элементов И, с информационным входом пятого регистра и с второйгруппой разрядных входов схемы сравнения, выход первого регистра соединенс вторым информационным входом мультиплекеора узла управления, первый ивторой выходы блока элементов И узлауправления соединены соответственно свторыми входами первого и третьегоэлементов ИЛИ и вторым входом блокаэлементов И, выход которого является выходом генератора, третий и четвертый выходы блока элементов И узлауправления соединены соответственнос вторым входом второго элемента ИЛИи входом синхронизации пятого регистра, пятый и шестой выходы блока элементов И узла управления соединенысоответственно с входом синхронизации сумматора и входом управлениясдв 1 пом первого регистра сдвига, седьмой и восьмой выходы блока элементовИ узла управления соединены соответственно с управляющим входом мультиплексора и входом управления сдвигомвторого регистра сдвига, девятый выход блока элементов И узла управления соединен с вторым входом четвертого элемента ИЛИ, выход второго элемента И узла управления соединен стактовыми входами первого и второгорегистров сдвига, первый выход блокаэлементов И узла управления соединенс вторым входом элемента ИЛИ узлауправления, десятый выход блока элементов И узла управления соединен свходом расширителя импульсов, одиннадцатый выход блока элементов И узлауправления соединен с входом занесения счетчика, двенадцатый выход блока элементов И узла управления черезчетвертый элемент задержки соединен с управляющим входом мультиплексораузла управления, выход второго регистра соединен с информационным входом счетчика узла управления,1524048 г.7 Составитель И.Столяедактор Л.Зайцева Техред Л, Олийнык рректорТ.Пал роизводственно-издательскнй комбинат "Патент", г, Ужгород, уп, Гагарина, 101 Заказ 7044/50 Тираж.668 ВНИИПИ Государственного комитета по изоб 113035, Москва, Ж, РаПодписноетениям и открытиям при ГКНТ СССРская наб., д. 4/5