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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и предназначено для формирования случайного процесса с β-распределением. Цель изобретения - расширение функциональных возможностей за счет формирования случайных чисел, имеющих β-распределение. Генератор содержит датчик 1 равномерно распределенных случайных чисел, демультиплексор 2, регистры 3 1...3 N, блоки 4 1...4 N выделения наибольшего числа, регистр 5 сдвига, элемент И 6, демультиплексор 7, элемент ИЛИ 8, блок 9 синхронизации, счетчик 10, элемент И 11, группу 12 элементов И, регистр 13 памяти, регистр 14 памяти, группу 15 элементов И, счетчик 16, элемент 17 задержки, RS-триггер 18. Поставленная цель достигается за счет введения новых связей и блоков. 2 ил.

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

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

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

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

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

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

ПО ИЗОБРЕТЕНИЯМ И OTHPblTHRM

ПРИ ГКНТ СССР

1 (21) 4345369/24-24 (22) 20.11.87 (46) 15.08.90. Бюл, И - 30 (72) С.В. Соколов (53) 681. 3 (088. 8) (56) Авторское свидетельство СССР

В 256375, кл. С 06 F 15/36, 1968.

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

Р 1196897, кл. G 06 F 15/36, 1985. (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и предназначено для формирования случайного процесса с -распределением. Цель изобретения— расширение функциональных возможнос„„SU„, 15 5 4 А1

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

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

Поставленная цель достигается за Счет введения новых связей и блоков. 2 ил.

1585794

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

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

Генератор содержит датчик 1 равномерно распределенных случайных чисел, демультиплексор 2, регистры 3,...,3, блоки 4,...,4 выделения наибольыего

Э Ф К числа, регистр 5 сдвига, элемент И 6, демультиплексор. 7, элемент ИЛИ 8, блок 9 синхронизации, счетчик 10, элемент И 11, группу 12 элементов И, регистр 13 памяти, регистр 14 памяти, группу 15 элементов И, счетчик 16, элемент 17 задержки, RS-триггер 18, группу 19,...,19, элементов ИЛИ.

Блок синхронизации содержит RSтриггер 20, элемент И 21, генератор

22 тактовых импульсов, элемент И 23, группу 24 элементов задержки, счетчик

25, элемент 26 задержки.

Генератор работает следующим образом, На выходе датчика I равномерного распределения (выбрано равномерное на интервале Г0,11) в параллельном коде

35 формируется случайное число, посту11 It пающее на демультиплексор 1 х N 2.

За один цикл работы устройства, в конце которого формируется число с р-распределением, с выхода датчика 1 снимается выборка из N < < N равномер. но распределенных случайных величин.

На первом этапе происходит запись выборки заданного объема N поступающей параллельным кодом, в N „ параллельно-последовательных регистров

3,,...,3, через демультиплексор

"1 x N" 2 в соответствии с тактовыми импульсами, поступающими из блока 9 синхронизации.. Варьирование объема

N, анализируемой (исходной) выборки, 1 записываемой в регистры 3 ., осуществ1 ляется путем записи соответствующего кода дополнения (N -И,) в регистр 14 памяти. В исходном положении RS-триггер 18 находится в единичном состоя55 нии, что обеспечивает запись кода дополнения, определяющего объем выборки, через элементы И 15,,...,15 „ груп-. пы в счетчик 16. Первый синхроимпульс с выхода 9 блока 9 синхронизации переводит РЛ-триггер 18 в нулевое состояние, запрещая перезапись иэ регистра 14, формирует счетный импульс на входе 16, счетчика 16, проходящий через элемент 17 задержки, а также синхронизирует формирование случайного кода в датчике 1. Время задержки в, элементе 17 выбирается из раси

2 lö + t,15t g1ò+ с -, ° По перел полнений счетчика 16 (набора статистического ряда требуемого объема)на выходе переполнения счетчика 16 формируется импульс, поступающий на вход

9 блока 9, который запрещает поступление тактовых импульсов на счетчик

16 и разрешает их поступление на тактовые входы регистров 3„,...,3,, 5.

Поступление тактовых импульсов организовано с учетом времен задержки в регистрах 3 и блоках 4 и синхрон1 J ности поступления информации с выходов регистра 3 и блока 4;, на вход

1 блока 4;.. В блоке 4; происходит выделение наибольшего из i случайных равномерно распределенных чисел. С выхода блока 4 снимается наибольй шее (из выборки, записанной в регистрах З,,...,Зд) число, поступающее последовательным кодом на информационный вход 5, регистра 5 и элемент

И 6. Если на выходе переполнения счетчика 10 "0", то на выход устройства число не проходит. В последовательно"параллельный регистр 5 (К-разрядный) записывается лишь код К младших разрядов числа, т.е. код номера регистра 3; с этим числом. Этот код поступает на входы управления коммутацией 71, ° .,7 „ демультиплексора "1х N" 7, обеспечивая прохождение сигнала сброса с выхода 9 блока

9 синхронизации на вход обнуления регистра 3;., в котором записано наибольшее на данный момент число. Данный регистр 31 обнуляется. Сигнал сброса приводит в исходное блоки 4 „,...,4 и выделения наибольшего числа, увеличивает на "1" код на выходе счетчика

10, приводит в исходное блок 9 син,хронизации, обеспечивая новый цикл выбора наибольшего числа и обнуление регистра З с ним. Так повторяется (N-r) раз. Так как в исходном состоянии в счетчике 10,записан дополнительный код числа (r+1 ), т о в (N- r ) -м цикле с его выхода переполнения сни85794 6

9 вь1ходы блока 9 синхронизации и через соответствующие элементы 241, ...,24 и-1задержки на 5-й,..., (N+3)-й выходы 9,...,9,g блока 9 синхрониза5 ции. С 3,..., И+2-га выходов 9 y... °, 9„1+ блока 9 синхронизации тактовые импульсы поступают йа входы управления сдвигом соответствующих регистров

3,...,3„., с выхода 9 „+g — на вход 5g ф ° ° » ф ф управпения сдвигом регистра 5. С регистров 3,...,Зд информация в после1 довательном (M+K) -разрядном коде (в

К младших разрядах каждого i-ro регистра 3, постоянно записан код его порядкового номера) посТупает на входы блоков 4„,...,4 „ „ выделения наибольшего числа (с первого регистра 3 1 — на первый вход первого блока 4 выделе1

5 15 мается единичный сигнал и наибольшее число (r-я статистика) считывается на выход устройства через элемент И 6 на выходе устройства сформировано чис ло с р -распределением. Все регистры

3,,...,3, 5, счетчики 10 и 16 сигналом с выхода элемента И 11 приводятся в исходное. Одновременно RS †òðèãгер 18 переводится в единичное состояние, обеспечивая запись кода дополнения иэ регистра 14 в счетчик 16, а также открываются элементы И 12„, 12 и обеспечивается запись дополник тельного кода r+1 из регистра 13 в счетчик 10. Работа устройства повторяется.

С выхода датчика 1 равномерно распределенных на интервале 0,1) случайных величин последовательность случайных величин, представленных в параллельном M-разрядном коде, поступает на информационный М-разрядный вход демультиплексора "1 х N" 2 и в соответствии с информацией, пастугающей с .двоичного счетчика 16 на входы управления коммутацией 2 „,...,2 „ демультиплексора "1х N" 2, записывается в соответствующие параллельно-последовательные циклические сдвигавые (1+К)-разрядные регистры 3,...,3,„, 19»» э Я»

Импульсы счета поступают на информационный вход 16 двоичного счетчика

16 с выхода тактового генератора 22 через элемент И 23, на второй (инверсный) вход которого поступает сигнал с выхода переполнения этого двоичного К-разряднага (К = (log

При поступлении (N+i)-ro счетного импульса с первого выхода 9, блока 9 синхронизации (выхада элемента H 23) на выходе переполнения счетчика 16 формируется сигнал, поступающий на второй вход 9 .блока 9 синхронизации, т.е. на инверсный вход элемента 23 и на третий вход элемента И 21. Тем самым запрещается дальнейшее прохождение счетных импульсов на информационный вход 161 счетчика 16 и разрешается прохождение тактовых импульсов с выхода тактового генератора 22 через элемент И 21 (RS-триггер 20 блока

9 синхронизации находится в единичном состоянии). Тактовые импульсы с выхода элемента И 21 поступают на информационный вход Т-ичнага счетчика

25 с фазоимпульсным представлением информации, HG третий 9 g и четвертьпй ния наибольшего числа, с 1.-ro регистра 3; — на второй вход (i-1)-го блока 4;, выделения наибольшего числа). Время задержки в элементе 23; задержки выбрано равным (i 7, ), где

25 — время задержки сигнала в блоке выделения наибольшего числа, i = 1,2,.

° ° » у»» 1

В группе блоков 4,,...,4 1 1выделения наибольшего числа происходит по30 следавательный выбор наибольшего числа H=. выборки Н равномерна распределенных случайных величин, записанных в группе регистров 3,...,3 <.

С выхода (N-1)-го блока 4 „ выделения наибольшего числа (И+К)-разрядный последовательный кад, образо- . ванный М-разрядным кодом наибольшего числа из выборки N случайных величин и К разрядным кодом порядкового номера соответствующего ему регистра

@ 3 поступает на инфармационньп вход

9 последовательно-параллельного К-разряднога регистра 5 и на первый вход элемента И 6. На вход управления сдвигам регистра 5 пастугают тактовые

45 импульсы с (N+a,--o выхода 9 > блока

1 »

9 синхронизации (через (N-i)-й элемент 24 задержки и элемент И 21 с

N-1 выхода тактового генератора 22).

Па поступлении (Т=М+К)-го такта50 вага импульса на информационный вход

Т-ичнага счетчика 25 на его выходе формируется единичный импульс, поступающий на R-вход RS-триггера 20 и запрещающий тем самьпя дальнейшее про55 .хождение тактавь:::: импульсов с выхода тактового генератора 22 через элемент

И 21 на выходы блока 9 синхронизации, а также паступаюпГ1й через N-й элемент

1585794

26 задержки (время задержки которого равно времени задержки в (N-1)-м элементе 24 <, задержки) на второй выход

9 блока 9 синхронизации и с него на вход разрешения коммутации и информа5 ционный вход демультиплексора "1 x N"

7, разрешая. тем самым прохождение на один иэ выходов демультиплексора

"1х N" 7 единичного импульса. На вхо"

10 ды управления коммутацией демультиплексора "1 х М" 7 поступает информация с К выходов регистра 5 (в параллельном коде поступает код номера

i-го регистра 3, в котором записано наибольшее число из выборки N случайных величин), определяющая прохожде-. ние единичного сигнала с второго выхода 9 блока 9 синхронизации на соответствующий -й выход демультиплексора 1 х N 7. С i†- го выхода демультин t1 г.

20 плексора "1 х N" 7 сигнал через элемент

И 3 поступает на вход обнуления i-ro

1 регистра 3;, обнуляя его, и через элемент ИЛИ 8 на первый вход 9, бло- 25 ка синхронизации, íà -.àêòîâûå входы блоков 4; выделения наибольшего числа (обнуляя их), на информационный вход счетчика 10 и на второй вход элемента

И 11. Сигнал, поступающий. на первый вход 9, блока 9 синхронизации, поступает на Б-вход RS-триггера 20, переводя его в единичное состояние (подготавливая дальнейшее прохождение тактовых импульсов через элемент И

21), и на вход обнуления счетчика 25, приводя его в исходное состояние.

Сигнал с выхода переполнения счетчика 10 поступает на второй вход элемента И 6 и первый вход элемента И 11.

Так как в конце каждого цикла работы устройства (j-й цикл определяется выбором очередного наибольшего числа из выборки (N-3) случайных величин) выбирается и исключается иэ дальнейшего рассмотрения обнулением соответствующего регистра 3 . наибольшее число, то формирование порядковых статистик организуется, начиная с их большего номера, в (N-i) ì цикле на первый. вход элемента И б посту- 50 пает i-я порядковая статистика в последовательном коде.

Таким образом„ по окончании выделения наибольшего числа в (N-r-1)-м цикле работы на выходе переполнения счетчика 1б сформирована "1",обеспечивающая в следующем цикле работы ((N-r)-м) прохождение r-й порядковой

О х <О х > 11

Г(+ ) y.<,1» ) P-1

I <) Г /Ь) М

Для имеем

Из теории порядковых с тати с тик известно, что при построении вариационного ряда x{ > 4х <,1<... х <„ 1из выстатистики через элемент И 6 на выход устройства.

Кроме того, "1" с выхода переполнения счетчика 10, поступая на первый вход элемента И 11 при появлении сигнала с выхода элемента ИЛИ 8 обеспечивает формирование на выходе элемента

И. 11 сигнала сброса, поступающего на входы обнуления регистров 3,...,3, входы обнуления 5, 16, 10 регистра 5 и счетчиков 10 и 16. Счетчик 16 обнуляется, сигнал с выхода переполнения исчезает, тем самым разрешается вновь формирование счетных импульсов с первого выхода 9 блока 9 синхрони1 зации на информационный вход 16 счет1 чика 16 и запрещается прохождение тактовых импульсов через элемент И 23, Начинается выбор г-й статистики.иэ новой. выборки N равномерно распреде1 ленных случайных величин и работа устройства повторяется.

В результате анализа выборки N, случайных равномерно распределенных чисел подобным образом и: формирования

r-й порядковой статистики с выхода устройства снимается последовательность случайных чисел, представленных двоичным последовательным кодом и имеющих р -распределение.; Требуемое изменение параметров распределения легко достигается соответствующей вариа" цией значений N „ и r, т.е. кодов дополнения,записываемых в регистры 13 и

14. Подобная реализация P"распределе- ния, обеспечивающая варьирование параметров закона распределения, упрощает существующие способы статистических исследований.

Теоретические положения, положенные в основу построения устройства, следующие °

Закон -распределения может быть записан в виде

1585794

10 борки объема N случайных величин с

1 распределением, равномерным на интернале (0,1), плотность распределения

r-й, статистики х (1этого ряда может быть представлена формулой (х)

Ns . (r-1)!(N,-r)!

IV,-r л(1 — х) r-q Х х

Из сравнения (1) и (2) видно, что

f„(x) представляет собой плотность -распределения с параметрами о(= r — N — r " 1 и той же областью

1 существования аргумента.

Таким образом, объем выборки N

1 случайных независимых равномерно распределенных на интервале (О, 1 ) величин и номер статистики х „ вариационного ряда этой выборки йолностью задают требуемое (З-распределение.

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

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

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

50 предварительной установки второго счетчика, выход переполнения которого соединен с входом задания режима блока синхронизации, выход второго демультиплексора — с входами элемента ИЛИ, выход которого соединен с так. товым входом блока синхронизации, информационный выход второго счетчика соединен с управляющим входом первого демультиплексора, выход второго элемента И является выходом генера- . тора, отличающийся т м, что, с целью расширения функциональных возможностей за счет формирования случайных чисел, имеющих р распределение, в него введены группа блоков выделения наибольшего числа, группа элементов ИЛИ, два регистра памяти, RS-триггер, причем выход первого регистра памяти соединен с . информационным входом второго счетчика, счетный вход которого соединен с выходом элемента задержки, вход которого соединен с R-входом RS-триг" гера, входом опроса датчика равномерно распределенных случайных чисел и вторым выходом блока синхронизации, входы обнуления регистров сдвига группы соединены с выходами элементов ИЛИ группы, первые входы элементов ИЛИ группы соединены с выходом первого элемента И, вторые входы элементов ИЛИ группы соединены с соответствующими выходами второго демультиплексора, тактовые входы блоков выделения наибольшего числа соединены с первым входом первого элемента И, со счетным входом первого счетчика и подключены к выходу элемента ИЛИ, выход переполнения первого счетчика соединен с вторым входом первого элемента И, выход которого соединен с входом предварительной установки первого счетчика, входом разрешения считывания второго регистра памяти и S-входом RS-триггера, выход второго регистра памяти подключен к информационному входу первого счетчика, выходы первого и второго регистров сдвига группы соединены соответственно с первым и вторым информационными входами первого блока выделения наибольшего числа группы, выход i-ro блока выделения наибольшего числа, кроме последнего, соединен с первым информационным входом (i+i)-ro блока выделения наибольшего числа группы (где i = 1,2,...,N, N — объем выборки), выход (i+3)-го регистра сдвига группы подключен к второму информационному входу (i+2)-ro блока выделения наибольшего числа группы, выход последнего блока выделения наибольшего числа группы соединен с информационным входом регистра сдвига, с первым входом второго элемента И, второй вход которого соединен с выхо1585794

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

Техред Л. Сердюкова Корректор В. Гирняк

Редактор Е. Копча

Тираж 562

Заказ 2327

Подписное

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

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

Производственно-издательский комбинат "Патент™, r.ужгород, ул. Гагарина, 101 дом переполнения первого счетчика, прямой выход RS-триггера соединен с входом разрешения считывания nepaoroi регистра памяти.