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

 

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

COI03 СОВЕТСКИХ

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

РЕСПУБЛИК (я)5 G 06 F 7/58

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

ПО ИЗОБРЕТЕПИЯМ И ОТКРЫТИЛМ

ПРИ ГК! I1 СССР

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

К ABTOPCKOMY СВИДЕТЕЛЬСТВУ

I ! ! е °

I+

iUl 00

IQ

;фа Ql

М (61) 1585794 (21) 4887104/24 (22) 10.10.90 (46) 30,08.92. Бюл. № 32 (72) С.В.Соколов и Б.А,Погорелов (56) Авторское свидетельство СССР

¹ 1585794, кл. 6 06 Г 7/58, 1987. (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение относится к специализированной вычислительной технике и может быть использовано при моделировании дискретных случайных процессов в системах управлс ия и связи, Цель изобретения— расширение функциональных возможноИзобретение относится к специализированной вычислительной технике и может быть использовано при моделировании дискретных случайных процессов в системах управления и связи.

Известны генераторы случайных чисел, обеспечивающие формирование заданного закона распределения на основе использования порядковых статистик. Недостатком данных устройств является отсутствие возможности формирования плотности распределения, представление которой в виде степенного ряда имеет отрицательные коэффициенты, Наиболее близким по техническому исполнению к предложенному устройству является генератор случайных чисел, формирующий последовательности с / -раcпpеделeниeлi (которое представляет собой, по существу, частный случай описания плотности распределения степенным рядом). Недостатком данного устройства является отсутствие возможности формиро. Ж 1758645 А2 стей устройства за счет формирования плотности распределения, описываемой степенным рядом с произвольными коэффициентами. Генератор случайных чисел содержит датчик равномерно распределенных случайных чисел, два мультиплексора, регистры, блоки выделения наибольшего числа, регистр сдвига, элементы И, элемент ИЛИ. блок синхронизации, два счетчика, две группы элементов

И, два регистра памяти, два элемента задержки; RS-триггер, группу элементов

ИЛИ, две группы из L параллельных регистров памяти, два мультиплексора "L х 1".

1 ил. вания случайной последовательности с плотностью распределения, описываемой степенным рядом с произвольными коэффициентами (в т.ч. отрицательными).

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

Поставленная цель достигается тем, что в генератор случайных чисел, содержащий датчик равномерно распределенных случайных чисел, демультиплексор, регистры, блоки выделения наибольшего числа, регистр сдвига, элемент И, демультиплексор, элемент ИЛИ, блок синхронизации, счетчик, элемент И, группу элементов И, регистр памяти, регистр, группу элементов И, счетчик, элемент задержки RS-триггер, введены два мультиплексора, дополнительный элемент задержки и две группы регистров памяти. причем выход датчика равномерно распре1758645 устройства закон распределения р; выбран равномерным (что позволяет избежать дополнительного введения генераторов случайных чисел с каким-либо другим распределением р;).

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

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

191...„19н элементов ИЛИ, — и вновь введенный контур f (на чертеже показан пунк15 тиром), содержащий элемент задержки 20

20 первую группу из1 параллельных регистров памяти 211, ..., 21i, первый мультиплексор

"L х 1" 22, вторую группу из L параллельных регистров памяти 23, ..., 23 и второй мультиплексор "Lx 1" 24. Разрядность регистров

211 совпадает с разрядностью регистра 14, f(x) > 04х (0,1).

25 регистров 23i — с разрядностью регистра 13: число регистров L равно: L = 2 "-1, где m— разрядность числа на выходе датчика слу30 чайных чисел 1. Выходы регистров первой и ць„

f(x)= Xbi х" " (1-х) (=1

bi>0;1 ki пь

T.ê, плотность распределения k-й порядковой статистики из выборок случайных величин, равномерно распределенных на

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

Ц (), С к-1. к-1 . (1 )и-к

ki-1 „< В исходный момент времени в счетчике — 10 записан код дополнения, соответствуюприходим к возможности моделиРованиЯ щий коду одного из чисел 1ц (определяющих искомого распреде ения у™ Суперпози- номер статистики, выбираемой в данном ции РаспРеделений Различных поРЯдковых 55 цикле pa6oT ) o per cTpe 13

-нулевой код, в статистик из выборок рав"î åð"î рас"ðå- регистре 14 — один из кодов чисел п (о„ðåделенных величин переменного объема (т.е. деляющих объем выборки в данном цикле поРЯдковаЯ статистика с номеРом 11 из вы- работы) кото ы 1 злее КБ ра оты, который далее по сигналу с КБбоРКИ Объема nl МОДелиРУетсЯ с веРОЯтно- тр гера18 пас.упает как колдополнения в стью р;). Для рассматриваемой ниже схемы ч чи

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

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

Любая плотность распределения реального случайного процесс существует на заведомо конечном интервале и мо>кет быть легко приведена к существованию на интервале

0.1 с помощью операций масштабирования и сдвига. В связи с этим рассматриваем далее моделирование плотности

Функция f(x) на данном интервале с произвольной требуемой точностью может быть представлена в виде степенного ряда, коэффициенты которого в общем случае могут быть отрицательными (что приводит к невозможности использования методов моделирования, примененных в аналогах и прототипе).

С другой стороны, такой степенной ряд может быть преобразован в т.н. ряд Берийтейна, коэффициенты которого положительно определены:

50 группы 211, ..., 21i подключены к информационным входам 22i мультиплексора 22, выходы регистров второй группы 23i, ..., 23 — к информационным входам 24> мультиплексора 24. Управляющие входы мультиплексоров 22 и 242 обьединены и соединены с выходом датчика случайных чисел 1.

Выход мультиплексора 22 подключен ко входу записи 14 регистра 14, выход мультиплексора 24 — ко входу записи 13i регистра 13.

Входы управления записью обоих регистров 132, 142 обьединены и через элемент задержки 20 соединены с первым выходом второго счетчика 16 генератора случайных чисел.

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

1758645

Числа ni и Ь соответствуют при этом одному из членов ряда Бернш гейна и выбираются произвольно. Генератор работает следующим образом.

На выходе датчика 1 равномерного распределения (выбрано равномерное на интервале (0,1) в параллельном коде формируется случайное число, поступающее на демультиплексор "Ix"2, За один цикл работы генератора в конце которого формируется число с P -распределением, с выхода датчика 1 снимается выборка из N> < N равномерно распределенных случайных величин.

На первом этапе происходит запись выборки заданного obber. Ni, поступающий параллельным кодом, в N< параллельно-последовательных регистров З ...., Зм через демультиплексор 1гй" 2 в соответствии с тактовыми импульсами, поступающими из блока 9 синхронизации. Варьирование обьема N1 анализируемой (исходной) выборки, записываемой в регистры Зь осуществляется путем записи соответствующего кода дополнения (N-Ni) в регистр 14 памяти. В исходном положении

RS-триггер 18 находится в единичном состоянии, что обеспечивает запись кода дополнения, определяющего обьем выборки, через элементы И 15ъ ..., 15д группы в счетчик 16. Г1ервый синхроимпульс с выхода

9> блока 9 синхронизации переводит RSтриггер 18 в нулевое состояние, запрещая перезапись из регистра 14, формирует счетный импульс на входе 16< счетчика 16, проходящий через элемент 17 задержки, а также синхронизирует формирование случайного кода в датчике 1. По переполнении счетчика 16 (набора статистического ряда требуемого объел а) на выходе переполнения счетчика 16 формируется импульс, поступающий на вход 9> блока 9, который запрещает поступление тактовых импульсов на счетчик 16 и разрешает их поступление на тактовые входы регистров 3, ..., Зц ".

В блоке 4 происходит выделение наибольшего из i случайных равномерно распределенных чисел. С выхода 4м-i снимается наибольшее (из выборки в регистрах 31, .„Зы), число, поступающее последовательным кодом на информационный вход 5 регистра 5 и элемент И 6. Если на выходе переполнения счетчика 10 "0", то на выход устройства число не проходит. Б последовательно-параллельный регистр " (Kразрядный) записывается лишь код К младших разрядов числа, т.е. код номера регистра 3, с этим числол . Этот код поступает на входы управления коммутацией

7>...Д 7к демультиплексора "1xN" 7, обеспечивая прохождение сигнала сброса с выхода

91 блок 9 синхронизации на вход обнуления регистра Зь в котором записано наибольшее на данный момент число.

Данный регистр 3i обнуляется. Сигнал сброса приводит в исходное блоки 4 >...Д 4tv-> выделения наибольшего числа, увеличивает на "1" код на выходе счетчика 10, приводит в исходное блок 9 синхронизации, обеспечивая новый цикл выбора наибольшего числа и обнуление регистра 31 с ним, Так повторяется (N,г) раэ. Так как в исходном состоянии в счетчике 10 записан дополнительный код числа (r+1), то в (N-r)-м цикле с его выхода переполнения снимается единичный сигнал и наибольшее число (r— статистика) считывается на выход устройства через элемент И 6 — по окончании данного цикла работы на выходе генератора формируется r = ki-я статистика из выборки объема ni = N1.

Далее и роисходит следующее.

Коды равномерно распределенных случайных чисел с выхода датчика 1 поступают на управляющие входы мультиплексоров 22 и 24. Принцип суперпозиции предполагает формирование той ki-й статистики из выборки объема и;, для которой текущее значение равномерно распределенного числа совпало со значением. Таким образом, поступление кодов различных чисел с выхода датчика

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

222 и 242, на выход мультиплексоров проходят соответствующие им (т.е. р;) коды чисел и; (записанных в регистрах 21;) и ki (записанных в регистрах 23 ).

T.ê. с выхода датчика 1 в цикле работы устройства снимается ряд случайных чисел (число которых определено величиной кода пь записанного в предыдущем цикле в регистр 14), а в регистры 13, 14 запись в каждом цикле должна осуществляться однажды, то для этого входы управления записью 13, 142 регистров 13, 14 соединены через элемент задержки 20 с первым выходом счетчика 16.

Это приводит к тому, что после считывания кода из регистра 14 и начала очередного цикла работы устройства (выбора ki-й статистики из выборки обьема и;), в момент прохождения первого случайного числа с выхода датчика 1 через демультиплексор 2, с I-ro выхода счетчика 16 снимается сигнал, разрешающий запись кодов ni и ki, соответствующих этому числу, в регистры 14, 13.

Время задержки в элементе 20 выбрано равным времени срабатывания мультиплексоров 22, 24. T.î. уже в начале цикла выбора k -й статистики из выборки обьема t758645

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

Генератор случайных чисел io авт, св.

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

Редактор И.Загорбинина Техред M.Ìîðãåíòàë Корректор Н, Соколов

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

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101 пь в регистры 13, 14 записываются коды следующих чисел k . nj. Код из регистра 13 переписывается в счетчик 10 в конце данного цикла, из регистра 14 в счетчик 1б — в начале следующего (1). Работа генератора повторяется аналогично вышеизложенному — на выходе генератора формируется последовательность случайных чисел с заданным распределением 1(х). вольными коэффициентами, в него введены два мультиплексора, дополнительный элемент задержки и две группы регистров памяти, причем выход датчика равномерно

5 распределенных случайных чисел соединен с управляющими входами первого и второго мультиплексоров, информационные входы которых подключены к выходам регистров памяти cooTBGTGTBpHHo первой и второй

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