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

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

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

На фиг. 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, элементов ШШ. jS

Блок синхронизации содерлшт RS- триггер 20, элемент И 21, генератор 22 тактовых импульсов, элемент И 23, группу 24 элементов задержки, счетчик 25, элемент 26 задержки.

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

На выходе датчика 1 равномерного распределения (выбрано равномерное на интервале tO,1J) в параллельном коде формируется случайное число, посту- пающее на демультиплексор IxN 2. За один цикл работы устройства, в конце которого формируется число с Ь-распределением, с выхода датчика 1 снимается выборка из N. N равномерно распределенных случайных величин.

На первом этапе происходит запись выборки заданного объема Ы,, поступающей параллельным кодом, в М параллельно-последовательных регистров 3 ,,... ,3 через демультиплексор 1 XN 2 в соответствии с тактовыми импульсами, поступаюищми из блока 9 синхронизации.о Варьирование объема N , анализируемой (исходной) выборки, 50 записываемой в регистры 3-, осуществляется путем записи соответствующего кода дополнения (N -N) в регистр 14 памяти. В исходном положении КЗ-триггер 18 находится в единичном состоя- 55 НИИ, что обеспечивает запись кода дополнения, определяющего объем выбор- ки, через элементы И 15 ,... , 15 . грул30

S

0

0

пы в счетчик 16, Первый синхроимпульс с выхода 9у блока 9 синхронизации переводит RS-триггер 18 в нулевое состояние, запрещая перезапись из регистра 14, формирует, счетный импульс на входе 16 счетчика 16, проходящий через элемент 17 задержки, а также синхронизирует формирование случайного кода в датчике 1. Время задержки . элементе 17 выбирается из расчета: f,,i:,+,5, Г,,+ ,, .f. По пере- полнении счетчика 16 (набора статистического ряда требуемого объема)на выходе переполнения счетчика 16 формируется импульс, поступающий на вход 9 бпока 9, который запрещает поступление тактовых импульсов на счетчик 16 и разрешает их поступление на тактовые входы регистров 3,...,3 , 5. Поступление тактовых импульсов организовано с учетом времен задержки в регистрах 3; и блоках 4- и синхронности поступления информации с выходов регистра 3 . и блока 4 ,-., на вход блока 4 -.. В блоке 4 j происходит выделение наибольшего из i случайных равномерно распределенных чисел. С выход а блока 4 снимается наибольшее (из выборки , записанной в регистрах 3,,...,3f() число, постуцающее последовательньм кодом на информационный вход 5, регистра 5 и элемент И 6. Если на выходе переполнения счетчика 10 О, то на выход устройства число не проходит. В последовательно-параллельный регистр 5 (К-раз- оядный) записывается лишь код К младших разояпов числа, т.е. коп но- мер.а регистра 3; с этим числом. Этот код поступает на входы управления коммутацией 7 ,...,7 демультиплек- сора IxN 7, обеспечивая прохождение сигнала сброса с выхода 9 , блока 9 синхронизации на вход обнуления регистра 3,-, в котором записано наибольшее на данньЕЙ момент число. Данньй регистр 3| обнуляется. Сигнал сброса приводит в исходное блоки 4 ,,.,,4 выделения наибольшего числа, увеличивает на 1 код на выходе счетчика 10, приводит в исходное блок 9 син- .хронизации, обеспечивая новый цикл выбора наибольшего числа и обнуление регистра 3j с ним. Так повторяется (N-r) раз. Так как в исходном состоя- ,нии в счетчике 10.записан дополнительный код числа (г+1),тов (К-г)-м цикле с его выхода переполнения сни5158

мается единичный сигнал и наибольшее число (г-я статистика) считывается на выход устройства через элемент И 6 - на выходе устройства сформировано число с л -распределением. Все регистры 3 ,...,3, 5, счетчики 10 и 16 сигналом с выхода элемента И 11 приводятся в исходное. Одновременно RS-триг- гер-18 переводится е единичное состояние, Обеспечивая запись кода дополнения из регистра 14 в счетчик 16, а также открываются элементы И 12,...,

12 и обеспечивается запись дополнительного кода г+1 из регистра 13 в счетчик 10. Работа устройства повторяется.

С выхода датчика 1 равномерно распределенных на интервале случай

9 выходы блока 9 синхронизации и через соответствующие элементы 24i,,.. ...,24N-1 задержки на 5-й,..., (Н+3)-й выходы 95-,..., 9 N+3 блока 9 синхронизации. С 3,..., N+2-го выходов 9j,, .., 9рщ блока 9 синхронизации тактовые импульсы поступают rta входы управления сдвигом соответствующих регистров 3,,...,3., с выхода 9 3 °Л 2 управпения сдвигом регистра 5. С регистров 3 ,...,3|у, информация в последовательном (М+К)-разрядном коде (в К младших разрядах каждого i-ro регистра 3 ; постоянно записан код его порядкового номера) поступает на входы блоков 4 ,..,,4 , выделения наибольшего числа (с первого регистра 3 - на первый вход первого блока 4 вьщеле

Изобретение относится к вычислительной технике и предназначено для формирования случайного процесса с β-распределением. Цель изобретения - расширение функциональных возможностей за счет формирования случайных чисел, имеющих β-распределение. Генератор содержит датчик 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 ил.

ных величин последовательность случай- 20 ия наибольшего числа, с 1-го регист- на второй вход (i-l)-ro

25

30

ных величин, представленных в параллельном М-разрядном коде, поступает , на информационный М-разрядный вход демультиплексора 1 х N 2 и в соответствии с информацией, поступающей с -двоичного счетчика 16 на входы управления коммутацией 2 ,... ,2 | демультиплексора IxN 2, записывается в соответствующие параллельно-последовательные циклические сдвиговые (f-1+К)-разрядные регистры 3j,...,3. Импульсы счета поступают на информационный вход 16 двоичного счетчика 16 с выхода тактового генератора 22 через элемент И 23, на второй (инверс- ньм) вход которого поступает сигнал с выхода переполнения этого двоичного К-разрядного (К )+ 1) счетчика 16.

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

ра 3;

блока 4 , -, выделения наибольшего числа). Время задержки в элементе 23; задержки выбрано равным (i- C ), где - время задержки сигнала в блоке выделения наибольшего числа, i 1,2,, .. .,N-1 .

В группе блоков 4 ,,. , . ,4 |, вьщеле- ния наибольшего числа происходит последовательный выбор наибольшего числа из выборки N равномерно распределенных случайных величин, записанных в группе регистров 3,...,3р.

С выхода (N-l)-ro блока 4

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

40

45

50

3, поступает на информащ онньй вход последовательно-параллельного К-разрядного регистра 5 и на первый вход элемента И 6 На вход управления сдвигом регистра 5 поступают тактовые импульсы с (N+3)-ro выхода 9 f 42:блока 9 синхронизации (через (Н-1)-й элемент 24 задержки и элемент И 21с

™TON

выхода тактового генератора //j.

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

- на второй вход (i-l)-ro

5

0

5

ра 3;

блока 4 , -, выделения наибольшего числа). Время задержки в элементе 23; задержки выбрано равным (i- C ), где - время задержки сигнала в блоке выделения наибольшего числа, i 1,2,, .. .,N-1 .

В группе блоков 4 ,,. , . ,4 |, вьщеле- ния наибольшего числа происходит последовательный выбор наибольшего числа из выборки N равномерно распределенных случайных величин, записанных в группе регистров 3,...,3р.

С выхода (N-l)-ro блока 4

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

0

5

0

3, поступает на информащ онньй вход последовательно-параллельного К-разрядного регистра 5 и на первый вход элемента И 6 На вход управления сдвигом регистра 5 поступают тактовые импульсы с (N+3)-ro выхода 9 f 42:блока 9 синхронизации (через (Н-1)-й элемент 24 задержки и элемент И 21с

™TON

выхода тактового генератора //j.

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

10

1585794

26 задержки (время задержки которого равно времени задержки в (N-1)-M элементе 24,., задержки) на второй выход 9j блока 9 синхронизации и с него на вход разрешения коммутации и информационный вход демультиплексора 1 хN 7, разрешая тем самым прохождение на один из выходов демультиплексора 1 X N 7 единичного ш.шульса. На входы управления коммутацией демультиплексора IxN 7 поступает информация с К выходов регистра 5 (в параллельном коде поступает код номера i-ro регистра 3 , в котором зап1|сано наибольшее число из выборки N случайных величин), определяющая прохождение единичного сигнала с второго выхода 9 2 блока 9 синхрониза1щи на соот ветствующий i-й выход демультиплексора IxN 7. С i-ro выхода демультиплексора 1 X N 7 сигнал через элемент И 3j поступает на вход обнуления i-ro регистра 3-, обнуляя его, и через

8

статистики через элемент И 6 на выход устройства.

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

10 регист

f5

20

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

Начинается выбор г-й статистики, и новой.выборки N равномерно распред ленных случайных величин и работа у ройства повторяется.

В результате анализа выборки N,

элемент ИЛИ 8 на первый вход 9 бло- 25 случайных равномерно распределенных

ка синхронизации, на тактовые входы блоков 4 выделения наибольшего числа (обнуляя их), на информационный вход счетчика 10 и на второй вход элемента И 11. Сигнал, поступаюшзнй. на первьй вход 9,, блока 9 синхронизации, поступает на S-вход RS-триггера 20, переводя его в единичное состояние (подготавливая дальнейшее прохо5кдение такто.вых импульсов через элемент И 21), и на вход обнуления счетчика 25, приводя его в исходное состояние.

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

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

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

0

5794

8

статистики через элемент И 6 на выход устройства.

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

10 регист5

0

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

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

В результате анализа выборки N,

5 случайных равномерно распределенных

чисел подобным образом и-, формирования г-й порядковой статистики с вьгхода устройства снимается последовательность случайных чисел, представленных двоичным последовательным кодом и имеющих Р) -распределение.; Требуемое изменение параметров распределения легко достигается соответствующей вариацией значений N и г, т.е. кодов дополнения, записьшаемьтх в регистры 13 и 14. Подобная реализация /J-распределе- ния, обеспечивающая варьирование параметров закона распределения, упрощает существующие способы статистических исследований.

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

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

О, X 0, X 1; (°(Л) ..(,.)-

rU) -г()

х 1, of70, Х1.

целочисленных значений VH А

р(х)

О, X О, X ( + /5 -1)

1;

,« - (1../-К1

(о/-1)(А-1)

Из теории порядковых статистик известно, что при построении париацион- ного ряда 4х (. .. X ( выборки объема N случайных величин с распределением, равномерным на интервале 0,1, плотность распределения г-й. статистики х, этого ряда может быть представлена формулой.

f „л NiJ

(r-lTKN.л(1 -х)1-:

Из сравнения (1) и (2) видно, что fР(х) представляет собой плотность «.-распределения с параметрами о( г.

/Ь N. 1 и той же областью

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

Таким образом, объем выборки N случайных независимых равномерно распределенных на инте11вале 0,1 величин и номер статисти ки х , . вариационного ряда этой выборки полностью задают требуемое Л-распределение.

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

J5

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

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

20

30

25

5

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

0

5

0

01

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

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

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

Заказ 2327

Тираж 562

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

фиг. 2

Подписное