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

 

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

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

Известен датчик случайных чисел [1] заданных произвольным законом распределения, содержащий генератор тактовых импульсов, блок управления, два ключа, запоминающее устройство, датчик случайных чисел (равномерно распределенных в интервале (0,1), вычитающее устройство возведения в квадрат, множительный блок, блок возведения в куб, сумматор, фиксирующее устройство.

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

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

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

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

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

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

Генератор содержит блок 1 управления, RS-триггер 2, элементы запрета 3-8, элементы ИЛИ 9-13, датчик 14 случайных чисел, блок 15 вычитания из единицы, блок 16 деления, блок 17 логарифмирования, элемент ИЛИ 18, блоки 19, 20 элементов И, блок 21 элементов ИЛИ, регистр 22, элемент ИЛИ 23, регистр 24, элементы задержки 25, 26, блок 27 элементов И, сумматор 28, счетчик 29, блок 30 деления, элемент ИЛИ 31, блок логарифмирования 32, блок 33 деления, блоки 34, 35 сравнения, блок 36 деления, элемент И 37, блок 38 памяти, блоки 39, 40 элементов И, блок 41 сравнения и блок 42 элементов И.

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

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

Теорема. Пусть X_i, i= выборка независимых случайных величин, для которой выполняется неравенство ≅ ≅ . (1) Тогда с доверительной вероятностью Р_д/P_д 1 β) (где β уровень значимости) можно утверждать, что данная выборка случайных величин обладает свойством экспоненциальности.

Доказательство. Предположим, что исходная выборка случайных величин обладает свойством экспоненциальности. Введем в рассмотрение статистику Δh h(n + 1) h/n), (2) где h(j)=1+ln выборочная энтропии экспоненциального закона распределения, а выборочное среднее.

Тогда (2) имеет вид Δh=ln-ln=ln+ln1 + . Затем, обозначая g . отметим, что сумма независимых случайных экспоненциальных величин x_i имеет распределение Эрланга n-го порядка f(z) e^-λ^z.

Следовательно, плотность распределения случайной величины после несложных преобразований запишется следующим образом: f(g)=Z e^-λ^zλe^-λ^zgdz= n e^-λ^z(1+g)dz . (3) Введем в рассмотрение случайную величину T=1 + 1+g. (4)
После чего, подставив (4) в выражение (3) и проинтегрировав его, нетрудно получить функцию распределения случайной величины в следующем виде
F(T)=nT^-n-1dT= -T^-n+1.

В дальнейшем, выделив двустороннюю критическую область, соответствующую заданному уровню значимости β (или доверительной вероятности Р_д 1 β), придем к требуемому неравенству
≅ -T^-n+1 ≅ 1 ; или окончательно
≅ ≅ .

Теорема доказана.

Прологарифмировав неравенство (1) и поделив все его части на n, получим соотношение
≅ ln ≅ . (5)
Отметим, что необходимым условием функционирования теста (5) является наличие двух и более случайных чисел.

Работоспособность предложенной операции проверялась с помощью вычислительного эксперимента на ЭВМ ЕС-1045 методом Монте-Карло. При этом последовательность случайных чисел формировалась посредством стандартной процедуры RANDU (датчика случайных чисел), распределенных равномерно в интервале (0,1). Затем, используя обратное преобразование Смирнова, осуществляли переход к случайным величинам с экспоненциальным законом распределения
x_i=ln i=, где α_i равномерно распределенная величина в интервале (0,1).

При этом вводились нелинейные возмущения с целью ухудшения свойств исходной последовательности случайных чисел, после чего производилось тестирование с помощью соотношения (5). Если неравенство (5) выполняется, то исходная последовательность обладает свойством экспоненциальности. В противном случае отбрасывается последнее случайное число и происходит формирование новой подпоследовательности, начиная с n 1. В дальнейшем отселектированная выборка (α_i, ), так же, как и исходная, проверялись на равномерность с использованием критерия Колмогорова.

Повышение достоверности результата эксперимента обеспечивалось многократностью их проведения при фиксированных значениях М и β. В качестве показателя результативности теста в этой ситуации представляется целесообразным принять величину Ку (назовем его коэффициентом улучшения свойств последовательности случайных чисел) как отношение количества принятых гипотез о равномерности Nноск для откорректированной с помощью теста последовательности объема М к количеству принятых гипотез о равномерности Nнобк исходной последовательности того же объема при постоянном числе экспериментов, т.е.

K_у .

Генератор работает следующим образом. Перед началом работы в блок 38 памяти вводятся заранее рассчитанные значения доверительных границ ln ln для теста проверки принадлежности случайной величины экспоненциальному закону распределения, а RS-триггер 2 устанавливается в нулевое состояние. С началом работы генератора тактовых импульсов блока 1 управления первый тактовый импульс генератора переводит сдвиговый регистр блока 1 в состояние, при котором на его первом выходе появится уровень логической единицы, и этот сигнал подается в устройство для управления первым тактом вычислений. Второй тактовый импульс генератора переводит сдвиговый регистр в состояние, при котором на его первом выходе появится уровень логического нуля, а на втором выходе уровень логической единицы. Этот сигнал управляет вторым тактом вычислений. Блок управления работает аналогичным образом по восемнадцатый тактовый импульс с генератора. Девятнадцатый тактовый импульс переводит регистр в состояние, при котором на его первом выходе появится уровень логической единицы (начинается следующий цикл вычислений). Это происходит потому, что выход регистра соединен с его же входом (т.е. реализован циклический счетчик).

Первый тактовый импульс с 1-го выхода блока 1 управления обнуляет блок 15 вычитания, блоки 16, 30, 33, 36 деления, блок 17 логарифмирования, сумматор и счетчик, регистры 22, 24, блоки 34, 35, 41 сравнения.

Второй тактовый импульс с 2-го выхода блока 1 управления подается через элемент запрета 4 на вход датчика 14 случайных чисел. С выхода датчика 14 случайных чисел случайное число α₁ поступает на вход блока 15 вычитания.

Третий тактовый импульс с 3-го выхода блока 1 управления подается через элемент 5 запрета на вход блока 15 вычитания и инициирует его работу. Результат 1- α₁ подается на вход блока 16 деления.

Четвертый тактовый импульс с 4-го выхода блока 1 управления через элемент 6 запрета подается на вход блока 16 деления и инициирует его работу. Результат подается на вход блока 17 логарифмирования.

Пятый тактовый импульс с 5-го выхода блока 1 управления через элемент запрета 7 подается на вход блока 17 логарифмирования и инициирует его работу. Результат ln подается на входы блоков 19, 20 элементов И.

Шестой тактовый импульс с 6-го выхода блока 1 управления через элемента запрета 8 подается на вход блока 19 элементов И. С выхода блока 19 элементов И результат ln через блок 21 элементов ИЛИ подается на вход регистра 22.

Седьмой тактовый импульс с 7-го выхода блока 1 управления через элемент ИЛИ 23 подается на вход записи регистра 22 и инициирует его работу. Результат ln записывается в регистр 22. Одновременно через элемента ИЛИ 9 этот же импульс обнуляет блок 15 вычитания, блок 16 деления, блок 17 логарифмирования.

Восьмой тактовый импульс с 8-го выхода блока 1 управления подается на вход считывания регистра 22 и инициирует его работу. Результат ln подается на входы: 1 блока 39 элемента И, блока 30 деления, сумматора 28.

Девятый тактовый импульс с 9-го выхода блока 1 управления подается на вход датчика 14 случайных чисел. С выхода датчика 14 случайных чисел случайное число α₂ поступает на вход блока 15 вычитания.

Девятый тактовый импульс с 10-го выхода блока 1 управления подается на вход блока 15 вычитания и инициирует его работу. Результат 1 α₂подается на вход блока 16 деления.

Одиннадцатый тактовый импульс с 11-го выхода блока 1 управления подается на вход блока 16 деления и инициирует его работу. Результат подается на вход блока 17 логарифмирования.

Двенадцатый тактовый импульс с 12-го выхода блока управления подается на вход блока 17 логарифмирования и инициирует его работу. Результат ln подается на входы блоков 19, 20 элементов И.

Тринадцатый тактовый импульс с 13-го выхода блока 1 управления подается на входы блока 20 элемента И и счетчика. С входа блока 20 элемента И результат ln подается на вход регистра 24.

Четырнадцатый тактовый импульс с 14-го выхода блока 1 управления подается на вход записи регистра 24 и инициирует его работу. Результат ln записывается в регистр 24.

Пятнадцатый тактовый импульс с 15-го выхода блока 1 управления подается на вход считывания регистра 24 и инициирует его работу. Результат ln подается на входы сумматора 28 и блока 40 элементов И.

Шестнадцатый тактовый импульс с 16-го выхода блока 1 управления подается на входы сумматора и счетчика, блока 38 памяти и инициирует их работу. Результат ln + ln с выхода сумматора подается на блок 30 деления и вход блока 27 элементов И. Результат "1 с выхода счетчика 29 подается на входы блоков 33, 36 деления и вход блока 41 сравнения. С 4-го выхода блока 38 памяти значение ln подается на вход блока 33 деления, значение ln подается на вход блока 36 деления.

Семнадцатый тактовый импульс с 17-го выхода блока 1 управления подается на входы блоков 30, 36, 33 деления и блока 32 логарифмирования, инициирует работу блоков 30, 33, 36 и обнуляет блок 32 логарифмирования. Результат с выхода блока 30 деления поступает на вход блока 32 логарифмирования, инициирует работу блоков 30, 33. Результат деления с выхода блока 36 деления поступает на вход блока сравнения 35. Результат деления с выхода блока деления 33 поступает на вход блока 34 сравнения.

Восемнадцатый тактовый импульс с 18-го блока 1 управления подается на вход блока 32 логарифмирования и инициирует работу этого блока. Результат lnln + ln /ln с выхода блока 32 логарифмирования поступает на входы блоков 34, 35 сравнения.

Девятнадцатый тактовый импульс с 19-го выхода блока 1 управления подается на вход блоков 34, 35 сравнения и инициирует их работу.

Если при сравнении результатов в блоках 34, 35 не выполняется хотя бы одно условие теста, то на выходе элемента И 37 импульс не формируется и случайное число устройством не выдается. После этого устройство при подаче первого тактового импульса с выхода блока 1 управления работает аналогично.

Если при сравнении результатов в блоках 34, 35 условия теста выполняются, то на их выходах формируются импульсы и подаются на входы элемента И 37. Импульс с выхода элемента И 37 подается на входы блоков 39, 40 элементов И, через элемент ИЛИ 18 на вход блока 41 сравнения, на элементы 25, 26 задержки и на установочный вход "1" RS-триггера 2. С выхода регистра 24 через блок 40 элементов И результат ln подается на выход устройства. С выхода регистра 22 через блоки 39, 42 элементов И, результат ln подается на выход устройства. С выхода элемента ИЛИ 18 импульс подается на входы блоков 34, 35 сравнения и обнуляет их, блоков 30, 33, 36 деления, установочные входы регистров 22, 24 и обнуляет их.

С выхода элемента 25 задержки импульс подается на входы элемента 26 задержки, блока 27 элемента И, вход записи регистра 22. С выхода сумматора 28 результат ln + ln через блок 27 элементов И подается на вход блока 21 элементов ИЛИ. С выхода блока 21 элементов ИЛИ результат подается на регистр 22 и записывается в нем. С выхода элемента 26 задержки через элемент ИЛИ 31 импульс подается на вход сумматора 28 и обнуляет его. С выхода триггера единичный импульс подается соответственно на входы элементов запрета. С выходов 1-6 блока 1 управления тактовые импульсы поочередно подаются соответственно на входы элементов запрета. В результате на входе элементов запрета импульсы не формируются. При подаче тактового импульса с 7-го выхода блока 1 управления устройство начинает функционировать согласно ранее описанному порядку.

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

ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ, содержащий датчик случайных чисел, блок памяти и вычитатель из единицы, отличающийся тем, что, с целью расширения функциональных возможностей за счет формирования случайных чисел, распределенных по экспоненциальному закону, в него введены блоки деления, блоки логарифмирования, элементы запрета, блоки элементов И, блок элементов ИЛИ, элементы ИЛИ, сумматор, счетчик, блоки сравнения, элементы задержки, элемент И, регистры, RS-триггер и блок управления, с первого по шестой выходы которого соединены с первыми входами с первого по шестой элементов запрета, вторые входы которых подключены к прямому выходу RS-триггера, выход первого элемента запрета соединен с первыми выходами первого и второго элементов ИЛИ и обнуляющим входом счетчика, выход переполнения которого соединен с входами делителя первого и второго блоков деления и первым входом первого блока сравнения, выход "Равно" которого подключен к управляющему входу первого блока элементов И, информационный вход которого соединен с выходом второго блока элементов И, информационный вход которого подключен к выходу первого регистра, соединенному с первым входом сумматора и входом делителя третьего блока деления, выход которого подключен к информационному входу первого блока логарифмирования, выход которого соединен с первыми входами второго и третьего блоков сравнения, вторые входы которых соединены с выходами соответственно второго и первого блоков деления, выходы "Больше" второго и "Меньше" третьего блоков сравнения подключены к входам элемента И, выход которого непосредственно соединен с вторым входом элемента ИЛИ, управляющими входами второго и третьего блоков элементов И, входом установки в нулевое состояние RS-триггера и через первый элемент задержки подключен к управляющему входу четвертого блока элементов И, первому входу третьего элемента ИЛИ и входу второго элемента задержки, выход которого соединен с вторым входом второго элемента ИЛИ, выход которого подключен к обнуляющему входу сумматора, выход которого соединен с входом делимого третьего блока деления и информационным входом четвертого блока элементов И, выход которого подключен к первому входу первого блока элемента ИЛИ, выход которого соединен с младшими разрядами информационного входа первого регистра, выход второго элемента запрета подключен к входу запуска датчика случайных чисел, выход которого подключен к входу вычитателя из единицы, выход которого соединен с входом делителя третьего блока деления, выход которого подключен к информационному входу второго блока логарифмирования, выход которого соединен с информационными входами пятого и шестого блоков элементов И, выходы которых подключены соответственно к второму входу блока элементов ИЛИ и информационному входу второго регистра, выход которого соединен с вторым входом сумматора и информационным входом третьего блока элементов И, выход которого и выход первого блока элементов И через схему монтажного ИЛИ соединены с выходом генератора, седьмой выход блока управления подключен к второму входу третьего элемента ИЛИ, входу установки в единичное состояние RS-триггера и первому входу пятого элемента ИЛИ, второй вход которого соединен с первым выходом блока управления, а выход подключен к входам установки второго блока логарифмирования, третьего блока деления и блока вычитания из единицы, синхровход которого соединен с выходом шестого элемента ИЛИ, первый и второй входы которого подключены к выходу третьего элемента запрета и восьмому выходу блока управления, девятый и десятый выходы которого соединены соответственно с вторым входом четвертого элемента ИЛИ и первым входом седьмого элемента ИЛИ, второй вход которого подключен к выходу четвертого элемента запрета, а выход соединен с синхровходом третьего блока деления, первый и второй входы восьмого элемента ИЛИ подключены к выходу пятого элемента запрета и одиннадцатому выходу блока управления, а выход соединен с синхровходом второго блока логарифмирования, двенадцатый выход блока управления подключен к входу управления считыванием первого регистра, вход управления записью которого соединен с выходом третьего элемента ИЛИ, тринадцатый выход блока управления подключен к управляющему входу шестого блока элементов И и тактовому входу счетчика, вход разрешения выдачи результата которого соединен с входом управления считыванием блока памяти, синхровходом сумматора и четырнадцатым выходом блока управления, пятнадцатый и шестнадцатый выходы блока управления подключены к входам управления записью и считыванием второго регистра, вход установки которого соединен с входами установки первого регистра, первого, второго и третьего блоков деления, первого, второго и третьего блоков сравнения и выходом первого элемента ИЛИ, семнадцатый выход блока управления подключен к синхровходам первого, второго и третьего блоков деления и входу установки первого блока логарифмирования, синхровход которого соединен с восемнадцатым выходом блока управления, девятнадцатый выход которого подключен к синхровходам второго и третьего блоков сравнения, выходы блока памяти соединены с входами делимого первого и второго блоков деления.

РИСУНКИ

Рисунок 1, Рисунок 2