SU1758645A2

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

Info

Publication number: SU1758645A2
Application number: SU904887104A
Authority: SU
Inventors: Сергей Викторович Соколов; Вадим Алексеевич Погорелов
Original assignee: Ростовское высшее военное командно-инженерное училище ракетных войск
Priority date: 1990-10-10
Filing date: 1990-10-10
Publication date: 1992-08-30

Abstract

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

Description

ел

с

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

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

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

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

iQs

,4

сл

ifO

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

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

Люба плотность распределени реального случайного процесс существует на заведомо конечном интервале и может быть легко приведена к существованию на интервале 0,1 с помощью операций масштабировани и сдвига. В св зи с этим рассматриваем далее моделирование плотности

f(x),1.

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

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

N

f(x) Z bi x i 1

ki-1

bi 0; 1 ki PH.

Т.к. плотность распределени k-й пор дковой статистики из выборок случайных величин, равномерно распределенных на 0,1, определ етс выражением

fk(x) n -С„-1Ы-хы -(1-x)n-k,

то, полага bi pi го / Сп-1 где 0 pi 1 приходим к возможности моделировани искомого распределени путем суперпозиции распределений различных пор дковых статистик из выборок равномерно распределенных величин переменного объема (т.е. пор дкова статистика с номером ki из выборки объема nl моделируетс с веро тностью PI). Дл рассматриваемой ниже схемы

устройства закон распределени pi выбран равномерным (что позвол ет избежать дополнительного введени генераторов случайных чисел с каким-либо другим

распределением pi).

На чертеже представлена функциональна схема генератора, который содержит генератор случайных чисел, датчик 1 равномерно распределенных случайных чисел,

0 демультиплексор 2, регистры 3iЗм, блоки 4i, ..., 4м выделени наибольшего числа, регистр 5 сдвига, элемент И 6, демультип- лексор 7, элемент ИЛИ 8, блок 9 синхронизации , счетчик 10, элемент И 11, группу 12

5 элементов И, регистр 13 пам ти, регистр 14 пам ти, группу 15 элементов И, счетчик 16, элемент 17 задержки, RS-триггер 18, группу 19i, ..., 19м элементов ИЛИ, - и вновь введенный контур f (на чертеже показан пунк0 тиром), содержащий элемент задержки 20, первую группу из L параллельных регистров

пам ти 211 21ь первый мультиплексор

L х 1 22, вторую группу из L параллельных регистров пам ти 23i, ..., 23t и второй муль5 типлексор Lx 1 24. Разр дность регистров 21i совпадает с разр дностью регистра 14, регистров 23i - с разр дностью регистра 13; число регистров L равно: L 2m-1, где m - разр дность числа на выходе датчика слу0 чайных чисел 1. Выходы регистров первой группы 211, ..., 21 L подключены к информационным входам 22i мультиплексора 22,

выходы регистров второй группы 23i

к информационным входам 24т муль5 типлексора 24. Управл ющие входы мультиплексоров 22а и 242 объединены и соединены с выходом датчика случайных чисел 1.

Выход мультиплексора 22 подключен

0 ко входу записи 14 регистра 14, выход мультиплексора 24 - ко входу записи 13i регистра 13.

Входы управлени записью обоих регистров 132, 142 объединены и через элемент

5 задержки 20 соединены с первым выходом второго счетчика 16 генератора случайных чисел.

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

0

В исходный момент времени в счетчике 10 записан код дополнени , соответствующий коду одного из чисел ki (определ ющих номер статистики, выбираемой в данном

5 цикле работы), в регистре 13-нулевой код, в регистре 14 - один из кодов чисел ni (определ ющих объем выборки в данном цикле работы), который далее по сигналу с RS- триггера 18 поступает как код дополнени в счетчик 16.

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

На выходе датчика 1 равномерного распределени (выбрано равномерное на интервале 0,1 в параллельном коде формируетс случайное число, поступающее па демультиплексор ,

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

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

демультиплексор 2 в соответствии с тактовыми импульсами, поступающими из блока 9 синхронизации. Варьирование объема Ni анализируемой (исходной) выборки , записываемой в регистры 3i, осуществл етс путем записи соответствующего кода дополнени (N-Ni) в регистр 14 пам ти. В исходном положении RS-триггер 18 находитс в единичном состо нии , что обеспечивает запись кода дополнени , определ ющего объем выборки,

через элементы И 15i 15ы группы о

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

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

7i7к демультиплексора IxN 7, обеспечива прохождение сигнала сброса с выхода 9i блок 9 синхронизации на вход обнулени регистра 3i, в котором записано наибольшее на данный момент число.

Данный регистр 3i обнул етс . Сигнал

сброса приводит в исходное блоки 414N-1

выделени наибольшего числа, увеличивает на 1 код на выходе счетчика 10, приводит

0 в исходное блок 9 синхронизации, обеспечива новый цикл выбора наибольшего числа и обнуление регистра 3j с ним.

Так повтор етс (N,r) раз. Так ках в исходном состо нии в счетчике 10 записан

5 дополнительный код числа (г+1), то в (М-г)-м цикле с его выхода переполнени снимаетс единичный сигнал и наибольшее число (г - статистика) считываетс на выход устройства через элемент И 6 - по окончании данно0 го цикла работы на выходе генератора формируетс г kj- статистика из выборки объема DJ NI.

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

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

0 равномерно распределенного числа совпало со значением. Таким образом, поступление кодов различных чисел с выхода датчика 1 на управл ющие входы мультиплексоров 222 и 242, на выход мультиплексоров прохо5 д т соответствующие им (т.е. pi) коды чисел щ (записанных в регистрах 21j) и ki (записанных в регистрах 23i).

Т.к. с выхода датчика 1 в цикле работы устройства снимаетс р д случайных чисел

0 (число которых определено величиной кода ru, записанного в предыдущем цикле в регистр 14), а в регистры 13, 14 запись в каждом цикле должна осуществл тьс однажды, то дл этого входы управлени

5 записью 132, 142 регистров 13, 14 соединены через элемент задержки 20 с первым выходом счетчика 16.

Это приводит к тому, что после считывани кода из регистра 14 и начала очередного

0 цикла работы устройства (выбора ki-й статистики из выборки объема гн), в момент прохождени первого случайного числа с выхода датчика 1 через демультиплексор 2, с 1-го выхода счетчика 16 снимаетс сигнал,

5 разрешающий запись кодов щ и ki, соответствующих этому числу, в регистры 14, 13.

Врем задержки в элементе 20 выбрано равным времени срабатывани мультиплексоров 22, 24. Т.о. уже в начале цикла выбора ki-й статистики из выборки объема

щ, в регистры 13, 14 записываютс коды следующих чисел kj. nj. Код из регистра 13 переписываетс в счетчик 10 в конце данного цикла, из регистра 14 в счетчик 16 - в начале следующего 1. Работа генератора повтор етс аналогично вышеизложенному - на выходе генератора формируетс последовательность случайных чисел с заданным распредепением f(x).

Claims

Формула изобретени Генератор случайных чисел по авт. со. N; 1585794, отличающийс тем, что, с целью расширени функциональных возможностей за счет формировани случайных чисел с плотностью распределени , описываемой степенным р дом с произ

5

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