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

 

Изобретение относится к вычислительной технике и может быть использовано в качестве задающего блока в имитаторах случайных процессов, а также в качестве специализированного вероятностного процессора. Цель изобретения - повышение быстродействия. Генератор содержит первый блок памяти, датчик равномерно распределенных случайных чисел, первый сумматор,четыре регистра, четыре элемента ИЛИ, первый элемент задержки, мультиплексор, схему сравнения, узел синхронизации. Дополнительно введены два регистра, блок мультиплексоров, счетчик, второй и третий блоки памяти, элемент И, второй сумматор, второй элемент задержки. Узел синхронизации содержит четыре элемента задержки, Р-триггер, элемент, генератор тактовых импульсов, мультиплексор, блок памяти, регистр блок элементов И. 1 з.п. ф-лы, 2 ил.

СОЮЗ СОВЕТСНИХ

СОЦИА ЛИСТ И1ЕСНИХ

РЕСПУБЛИН (51)5 G 06 F 7 58

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОЧНРЫТИЯМ

ПРИ ГКНТ СССР

Н АВТОРСКОМ У СВИДЕТЕЛЬСТВУ

1 (21) 4487596/24-24 (22) 29.09.88 (46) 15.10.90. Бюл. У 38 (71) Казанский государственный университет им. В.И.Ульянова (Ленина) (72) В.М.Захаров, С.Е.Кузнецов, H.È.Èàêàð0â, В.И.Пермитин и Ф.И.Салимов (53) 681.3(088.8) (56) Авторское свидетельство СССР

И 1008738, кл. С 06 F 7/58, 1983.

Авторское свидетельство СССР

У 1524048, кл. G 06 F 7/58, 1988 °

2 (54) ГЕНЕРАТОР СЛУЧАИНЬП(ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в качестве задающего блока в имитаторах случайных процессов, а также в качестве специализированного вероятностного процессора.

Цель изобретения — повынение быстродействия ° Генератор содержит блок памяти, элемент ИЛИ 2, мультиплексор 3, регистр 4, элемент ИЛИ 5, элемент 6 задержки, элемент ИЛИ 7, регистры 8-10, блок 1 1 памяти,,узел изацин, cy MBTopbr 13 14 схему 15 сравнения, элемент И 16, блок 17 мультиплексоров, регистр

18, датчик 19 равномерно распреде; ленных случайных чисел, элемент ИЛИ

1599856

20, счетчик 2 1, регистр 22, блок 23 памяти, элемент 24 задержки. Поставленная цель достигается за счет вве дения новых связей и блоков. 1 з.п. ф-лы, б ил., 5 табл.

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

Цель изобретения — повышение быстродействия.

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

I фиг.4 показано содержимое ячеек, хранящих команды; на фиг.5 изображены временные диаграммы реализации команд; на фиг.б дана иллюстрация заполнения блока памяти выходными значениями.

Генератор (фиг.i) содержит блок

1 памяти, элемент ИЛИ 2, мультиплексор 3, регистр 4, элемент ИЛИ 5,эле-, мент 6 задержки, элемент ИЛИ 7, регистры 8-10, блок 11 памяти, узел 12 синхронизации, сумматоры 13, 14, схему 15 сравнения, элемент И 16, блок

17 мультиплексоров, регистр 18, дат-. чик 19 равномерно распределенных случайных чисел, элемент ИЛИ 20, счетчик 21, регистр 22, блок 23 памяти, 45 элемент 24 задержки.

Узел 12 синхронизации (фиг.2) содержит элемент ИЛИ 25, элемент 26 задержки, RS-триггер 27, элемент И 28, генерато 29 тактовых импульсов, эле50 менты 30, 31 задержки, мультиплексор 32, блок 33 памяти, регистр 34, блок 35 элементов И, элемент 36 задержки.

В основе работы генератора лежат следующие теоретические положения.

В генераторе получение текущего случайного числа х; для заданного распределения

Рт ° ° х, ° ° °, х „, где P — вероятность появления чис1

Yl ла х ° и,> P," = 1, производится с

13 помощью вспомогательного (имплицирующего) распределения (вектора) I I

Р, Р,. ° .,Р

1 у у, е е у (2) c Яэ (< 2 )э ° ° ю 2, э

2 -1

2" 21

f где P. — вероятность появления числа

J ю и у и,7 Р,. = 1, 2 v>m»n;

1=1

n — число двоичных разрядов для кодирования равномерно распределенных случайных чисел.

На первом шаге формируется значение у> а на втором производится функциональное преобразование значения у; в значение х, . Выполнение шага 1 для формирования последующего числа совмещено со временем выполнения шага 2, относящегося к процессу формирования теущего числа х.

Имплицирующее распределение (2), соответствующее заданному распределению (1), предварительно вычисляется по известному алгоритму.

Формирование значений у, в генераторе производится по следующему алгоритму, являющемуся модификацией алгоритма Уэлкера. Сначала вычисляются данные, которые заносятся в блок 1 памяти по следующему правилу.

Пусть К = 1о8 ю,(а1 — целое, не меньшее а). Разбиваем интервал (0,1) на 2 равных интервалов

0 в соответствие число у, а P за1

1 меняем на число Р, — (— g) (это со2 ответствует тому, что в блок 1 памяти в ячейку с адресом 0 записывается число у ). Теперь остается 2 — 1

k интервал и t. отличных от нуля чисел в последовательности Р,...,Р,„(t =

= m или t m 1). Если t - 2 — 1, 1 то вновь выбирается P. + — y, а

3 2 у) I,1 сопоставляется интервалу 1, из

1 вычитается — — (т.е. в блоке 1 памя2» ти устройства число у записывается в ячейку с адресом 1), и так продолжается до тех пор, пока число t не-. нулевых чисел в последовательности

Р,,...,Р не станет больше (ровно на единицу) числа интервалов, которым не сопоставлены числа. Без потери общности считаем., что числа

I I

Р,,...,Р ненулевые. Интервалы, которым не сопоставлены числа у, ос» к тались с номерами 2 — t + 1,...,2

1. Далее применяется рекурсивная процедура M(t).

Описание процедуры N(t) .

I I

Вход: числа P Ð, интервалы с номерами 2 — t + 1, ° .., 2 . — 1.

1. Если среди Р, 1...1Р есть Р 6 =

» то (2 — t + 1)-му интервалу

2»1 . сопоставляется число у (т. е. в блок

1 памяти в ячейку с номером 2 — t +

1 записывается у )1 число Р заменяется на 0 и применяется процедура

N(t-1) .

2. Если среди чисел P,...,Р

1 ° ° ° 1 ф

1 нет равных †- то выбираются такие

2к1

1 1

6и РЕ1 что Pb+ РŠ— -„, а Рбс 2» (легко увидеть, что такие два числа к

I всегда найдутся) . (2 — t + 1)-му интервалу сопоставляются два числа

Z 2 — t + 1/2 + Р» и А (содерк к

5 159 пронумеруем их числами 0,1,...,2»-1.

» соответственно. Поскольку ш « 2, то среди чисел P,,...,P найдется Р

Ставим интервалу с номером

2»

9856 6 жательно в блоке 1 памяти в ячейку с адресом 2 — t + 1 помещаются чис к ла Z и А, а в ячейках с адресами.

А и А + 1 — числа у и у соответb Ф . ственно). Р> заменяется на О, à P<1 ! на P + P — --y. Если P x 0 то ос5 е 2 е

10 талось t-1 число и t-2 интервала. Далее применяется процедура N(t-1) .

Если P О, то имеется t — 2 ненулевых числа и столько же интервалов.

В этом случае делается шаг, описанный ранее.

Далее выполняются процедуры формирования значений у .

Шаг 1. По первым S разрядам случайного числа 1 получаемого от датчика 19, считывается из блока 1 памя-, ти слово с адресом (), где () и двоичный код первых М разрядов 1

R — - двоичный код начальной базы адреса. Если это у, то процесс закончен за одно обращение к памяти.

Щаг.2. Если это слово состоит из чисел Z и А, то производится сравнение: если Z, то считывается число у из ячейки с адресом (А+1), в

ЗО противном случае считывается у иэ ячейки с адресом А, т.е. процесс saканчивается. за два обращения к памяти.

Наг 3. Если же слово с адресом () состоит из базы адреса А, то

\ и считывается из ячейки с адресом А +

+ у (где у — смещение) двоичный код следующих разрядов числа и повторяется шаг 1. Алгоритм работает, по4О ка не считывается слово у .

При работе устройства йроисходит циклическое считывание из блока памяти команд (К 1 К 1 К 1 К ) с после. дующей реализацией этих команд. Ал45 горитм работы изображен на фиг.3.

Формат выполняемых команд показан на фиг.4. Поле 1 содержит код операции, поле 2 команды К вЂ” число

5 ; 2,0 Р(у ), поле 3 — тип операнда: ! ес в командах К,1 К,К вЂ” это база относительного адреса (А), в команде

Kb — это код у; (значение имплицирующего вектора).

По команде К, определяется отрезок интервала, в который попало число 1 и формируется адрес команды . К или команды К>, или команды К+.

1599856

Узел 12 синхронизации начинает работать по сигналу "Пуск", посту вЂ, пающему через элемент ИЛИ 25, или по сигналу С;. По этому сигналу триг.

rep 27 открывает элемент И 28 через время, определяемое элементом 26 задержки, необходимое для считывания команд в регистры 8-10. Через элемент И 28 с генератора 29 тактовых 4ц импульсов поступает серия импульсов, число импульсов в которой зависит от команды К; (i = 1,4). Под действием каждого импульса этой серии происходит считывание из блока 33 памяти в регистр 34 одной микрокоманды. Адрес очередной микрокоманды поступает из регистра 34 через мультиплексор 32 в блок 33 памяти под действием управгяющего сигнала С 1, . Частота импульсов считывания, поступающих от генератора тактовых импульсов,определяется быстродействием блока 33 памяти.

Выходные значения считываются из блока 11 памяти. Иллюстрацию заполнения блока 11 значениями х показаны на фиг.6.

По команде К уточняется дальней- . шее положение числа Р на интервале . и формируется адрес команды К или команды К, или команды К4.

По команде К число х считывает5

Ъ

t ся на выход устройства.

По команде К уточняется интервал и формируется адрес команды К или

К4 1О

Все команды (K, — К4) реализуются с помощью микрокоманд, которые вырабатываются в узле 12. Последова» тельность выполнения команды К1 показана в табл.1; команды К вЂ” в табл.2;команды Кz — в табл,3; команды К 4 — в табл,4. !

Генератор работает следующим образом.

По сигналу "Пуск" по адресу, определяемому регистром 4, происходит считывание из блока 1 памяти команды

К, и запуск датчика 19. Дальнейший алгоритм работы устройства изображен на фиг.3 . Управление функциони- 25 рованием генератора осуществляется узлом 12 синхронизации. Работу узла

12 поясняет табл.5. Временные диаграммы управляющиХ сигналов на выходе узла 12 показаны на фиг.5 ° 30

Формула изобретения

1. Генератор случайных чисел, содержащий первый блок памяти, датчик равномерно распределенных случайных чисел, первый сумматор, четыре регистра, четыре элемента ИЛИ, первый элемент задержки, мультиплексор, схему сравнения, узел синхронизации, первый выход узла синхронизации соединен с первыми входами первого и второго элементов HJIH, второй выход узла синхронизации соединен с первым входом третьего элемента ИЛИ, причем второй вход первого элемента

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

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

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

io

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

20 разрядные выходы соединены с вторым управляющим входом мультиплексора, выход элемента ИЛИ через второй элемент задержки соединен с S-входом

RS-триггера, Р-вход которого соединен

25 с выходом элемента ИЛИ, выход триггера соединен с первым входом элемента И, второй вход которого соединен с выходом генератора тактовых импульсов, выход элемента И соединен у» с входом чтения блока памяти и через третий элемент задержки — с тактовым входом регистра, выход третьего элемента задержки через четвертый элемент задержки соединен с вторым входом блока элементов И, информационный вход мультиплексора является входом задания режима узла, первый вход элемента ИЛИ является входом запуска узла, второй вход элемента ИЛИ соединен с первым входом блока элементов И.

1599856

Та блица 1

Описание микроопераций

Управляющие сигналы

фф

С79 9С11

С, Си

С„С, Таблица 2

Описание микроопераций Управляющие сигналы

С, С„

С„С „

С, СМ

c„c«

1.

2.

3.

1.

2.

3.

Считывание случайного числа из датчика 19 в регистр 18

Считывание из блока

23 памяти по адресу, образованному счетчиком 21 (младшие разряды адреса) и регистром 22 (старшие разряды адреса) сигналов, управляющих работой блока мультиплексоров 17 (первый номер разбиения отрезка 0,1), и подключение к сумматору 13 адреса первого разбиения

Иодификация адреса в сумматоре 13

Считывание иэ блока

1 памяти очередной команды по сформированному адресу

Перевод счетчика

21 в значение, соответствующее следующему уровню распределения

Считывание из блока

23 памяти по адресу, образованному счетчиком 21 (младшие разряды адреса) и регистром 22 (старшие разряды адреса) сигналов, управляющих работой блока 17 (второй номер разбиения отрезка О, 1), и подключение к сумматору 13 адреса второго разбиения

Модификация адреса в сумматоре 13

Считывание из блока

1 памяти очередной команды по сформированному адресу

1599856

Таблица 3

Описание микроапераций Управляющие сигналы .

С, С<, С4» СИ

С,С,С „

С, С, I

Та блица 4, Описание микроопераций Управляющие сигналы

7у С»

С5, Сн,С,о

С, С, 1.

2 °

3.

1.

По адресу, находящемуся в регистре

10 (значение имплицирующего вектора

"у"), считывание на выход генератора из блока 11 памяти значения х.„

1"

Запуск датчика 19

Считывание из блока

1 памяти команды по адресу, определяемому регистром 4,.

Сброс счетчика 21 в значение, соответствующее первому, уровню распределения

Считывание из блока

23 памяти по адресу, образованному счетчиком 21 (младшие разряды адреса) и регистром 22 (старшие разряды адреса) сигналов, управляющих работой блока

17 {текущий уровень распределения)

Сравнение в схеме 15 содержимого регистров 9 и 18, выдача результата сравнения (О или 1) в младшие разряды сумматора 14 и модификация адреса в сумматоре 13

Считывание из блока

1 памяти следующей команды по сформированному адресу

1599856

Команда

Адрес микрокоманды

Адрес следующей микрокоманды..

16

Та блица 5

Управляющие сигналы

К, 0100, 0011

0001

0101:

0001

1001

К 0111

0001

0011

0001

0001

1001

0001

0000 с6» сц с„с„с,, С19 СИ с,, с„с,, с„ с, с,н с, с«,с

С ° C C„c„

С, Сн, С о, С с,, C«-Щ/2. 4

Ку 7

Су

Су

Су

Ср

С

Су

/ T юп

1599856

0" О

0- ° ° 0

0 ° ° -0

С 8 7

/Т

1599856

Регистр адреса

ЕРОВ ламяаи

44

z Щ) =л(б)=л

ja)

Е P(3j) Р(М )-Ц

j=t

Составитель И.Столяров.

Редактор А.Маковская Техред М.pидшк Корректор М. Максимишинец

Заказ 3144 Тираж 566 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, N-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101