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

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

Реферат

 

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

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

Известен генератор последовательностей случайных чисел (см. а.с. СССР 447706, кл. G 06 F 1/02, 1974), содержащий датчик равномерно распределенных чисел, коммутатор, первый и второй генераторы тактовых импульсов, счетчик, регистры, клапаны, элемент задержки, преобразователь, формирователь импульса сброса и ключ.

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

Известен генератор случайных чисел (см. а.с. СССР 771654, кл. G 06 F 1/02, 1978), содержащий источник равномерно распределенных случайных сигналов, два блока памяти, сумматор, переключатель и умножитель.

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

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

Наиболее близким техническим решением к заявляемому изобретению является генератор случайной последовательности заданных значений набора данных (см. патент РФ 2138074, кл. G 06 F 7/58, 1998), содержащий источник случайных чисел с заданным законом распределения, выход которого подключен ко второму адресному входу мультиплексора, а его первый адресный вход является адресным входом генератора случайной последовательности заданных значений набора данных, вход разрешения мультиплексора является входом разрешения генератора. Выход мультиплексора подключен к адресным входам первого и второго блоков памяти, информационный вход второго блока памяти соединен с информационным входом первого блока памяти и является информационным входом генератора, выход первого подключен ко входу блока сравнения, а выход второго ко входу блока элементов "И". Второй управляющий вход блока элементов "И" соединен с входом выбора мультиплексора, а третий вход блока элементов "И" соединен с выходом блока сравнения. Выход блока элементов "И" является выходом устройства.

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

Недостатком генератора-прототипа является относительно низкая точность моделирования (под точностью моделирования (несмещением) понимается условие, когда математическое ожидание оценки случайной величины при любом возможном будет равно (см., например, книгу: Б. А. Севастьянов - Курс теории вероятности и математической статистики-М.: Наука, 1982, с.213-232)) случайных величин.

Целью изобретения является разработка генератора случайных чисел, обеспечивающего более высокую точность моделирования случайных величин, оценок моментов моделируемых случайных величин, описывающих поведение сложных систем, за счет формирования случайных чисел в заданном диапазоне изменения вероятностной меры (см., например, книгу: Надежность и эффективность (справочник) /Под ред. Б.В. Гнеденко, т.2, с.20) их представления путем управления длиной случайной последовательности генерируемых чисел.

Поставленная цель достигается тем, что в известный генератор случайных чисел, содержащий датчик случайных чисел (ДСЧ) и блок управления, дополнительно введены N, где 2, блоков ключей, N блоков формирования порогов и N-входовый элемент ИЛИ. Датчик случайных чисел имеет k-разрядный выход, где k2, который соединен с k-разрядным информационным входом каждого блока ключей.

Управляющий вход i-го блока ключей, где i=1, 2,... N соединен с i-м выходом блока управления, а его k-разрядный выход соединен с k-разрядным входом i-го блока формирования порогов.

Управляющий выход блока формирования порогов соединен с i-м входом N-входового элемента ИЛИ. Информационный k-разрядный выход N-го блока формирования порогов является выходом генератора случайных чисел.

Блок управления состоит из входного элемента, синхронизирующего элемента, блока запуска, блока отключения разрядов, блока начальной установки и N-разрядного регистра сдвига, включающего N ячеек. Продвигающий выход j-й ячейки, где j=1, 2,..., N-1 N-разрядного регистра подключен к информационному входу (j+1)-й ячейки, а продвигающий выход N-й ячейки подключен к первому входу входного элемента. Второй вход входного элемента подключен к первому входу синхронизирующего элемента и выходу блока начальной установки. Выход входного элемента подключен к информационному входу первой ячейки N-разрядного регистра. Синхронизирующие входы ячеек регистра с номерами от второго до N-го объединены и подключены ко второму входу синхронизирующего элемента, являющемуся входом блока управления. Синхронизирующий вход первой ячейки подключен к выходу синхронизирующего элемента. Разрешающий вход i-й ячейки N-разрядного регистра подключен к i-му выходу блока отключения разрядов. Установочные входы всех N ячеек N-разрядного регистра объединены и подключены к выходу блока запуска. Информационные выходы всех N ячеек N-разрядного регистра являются соответствующими N выходами блока управления.

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

Заявленное устройство поясняется чертежами: фиг.1 - функциональная схема устройства; фиг.2 - схема блока управления; фиг.3 - схема ячейки блока управления; фиг.4 - схема элемента запуска; фиг.5 - схема элемента начальной установки.

фиг.6 - схема блока ключей; фиг.7 - схема блока формирования порогов; фиг.8 - схема N-входового элемента "ИЛИ".

Генератор случайных чисел, показанный на фиг. 1, состоит из датчика случайных чисел 1, блока управления 5, N, где N2, блоков ключей 2, N блоков формирования порогов 3 и N-входового элемента ИЛИ 4.

Датчик случайных чисел 1 предназначен для получения последовательности чисел, подчиненных заданному закону распределения. Известный датчик описан в книге: М.П. Бобнев "Генерирование случайных сигналов", М.: Энергия, 1971, с. 170, рис. 6-13. Датчик имеет k-разрядный выход, где k2, который соединен с информационным входом соответствующего элемента "И" 2.1_l,..., 2.1_k каждого блока ключей 2.

Блок ключей 2 предназначен для проключения случайного числа с выхода ДСЧ на вход соответствующего блока формирования порогов. Управляющие входы i-го блока ключей, где i=1, 2,... N, соединены с i-м выходом блока управления. Выходы элементов "И" 2.1_l,... 2.1_k одновременно соединены с первой группой входов первого 3.3 и второго 3.4 блоков сравнения и вторыми входами трехвходовых элементов 3.7_l... 3.7_k "И" i-го блока формирования порогов 3.

Блок формирования порогов 3 предназначен для селективной выборки случайных чисел, сформированных ДСЧ. Вторая группа входов первого 3.3 и второго 3.4 блоков сравнения соединены с выходами первой 3.1 и второй 3.2 резистивных матриц. Первый и второй выходы первого 3.3 и второй и третий выходы второго 3.4 блоков сравнения соединены соответственно с первым 3.5 и вторым 3.6 двухвходовыми элементами "ИЛИ". Выход первого 3.5 элемента "ИЛИ" соединен с первыми входами трехвходовых элементов 3.7_l,..., 3.7_k "И", а выход второго 3.6 элемента "ИЛИ" соединен с третьими входами трехвходовых элементов 3.7_l,. . . , 3.7_k "И", выходы которых соединены с соответствующими входами k-входового 3.8 элемента "ИЛИ". Кроме того, выход элементов 3.7_l,..., 3.7_k N-гo блока формирования порогов одновременно является информационным выходом блока формирования порогов и выходом генератора случайных чисел.

Резистивные матрицы 3.1, 3.2 и 5.3 идентичны и могут быть реализованы, как описано в книге: Б.В. Тарабрин, Л.Ф. Лунин, Ю.Н. Смирнов и др.; Интегральные микросхемы; Справочник. - Издание второе, исправленное -М: Энергоатомиздат, 1985г. , стр.190. Узлы сравнения 3.3 и 3.4 идентичны и могут быть реализованы путем применения известных схем узлов сравнения, описанных в книге: В.В. Гусев, О.Н. Лебедев, А.М. Сидоров. Основы импульсной и цифровой техники.- СПВВИУС, 1995г., стр.149-152.

Выход k-входового 3.8 элемента "ИЛИ" является управляющим выходом блока формирования порогов, который соединен с i-м входом N-входового элемента ИЛИ 4. Кроме того, выходы элементов 3.7_l,.... 3.7_k N-гo блока формирования порогов являются выходом генератора случайных чисел. Выход N-входового элемента ИЛИ 4 одновременно соединен со вторым входом синхронизирующего элемента 5.2, являющимся входом блока управления, и синхронизирующими входами ячеек регистра сдвига 5.1₂... 5.1_N блока управления 5.

Блок управления 5 предназначен для формирования сигналов управления блоками ключей и может быть реализован, как показано на фиг.2. Блок управления 5 состоит из N-разрядного регистра сдвига 5.1, включающего N-ячeек (фиг. 3), синхронизирующего элемента 5.2, элемента отключения разрядов 5.3, элемента запуска 5.4 (фиг.4), элемента начальной установки 5.5 (фиг.4) и входного элемента 5.6. Первый вход синхронизирующего элемента 5.2 одновременно соединен с выходом элемента начальной установки 5.5 и вторым входом входного элемента 5.6, а выход с синхронизирующим входом первой ячейки 5.1₁ регистра сдвига 5.1. Продвигающий выход j-й ячейки, где j=1, 2,... N-1, N-разрядного регистра подключен к информационному входу (j+1)-й ячейки, а продвигающий выход N-й ячейки подключен к первому входу входного элемента, выход которого подключен к информационному входу первой ячейки N-разрядного регистра. Разрешающий вход i-й ячейки N-разрядного регистра подключен к i-му выходу элемента отключения разрядов, а установочные входы всех N ячеек N-разрядного регистра объединены и подключены к выходу элемента запуска 5.4. Информационные выходы всех N ячеек N-разрядного регистра являются соответствующими N выходами блока управления.

Ячейки регистра сдвига 5.1_l... 5.1_N могут быть реализованы, как показано на фиг.3, и включают DV-триггер 5.1.3, первый 5.1.1 и второй 5.1.5 инверторы, двухвходовый элемент "И" 5.1.2 и двухвходовый элемент "ИЛИ" 5.1.4. Установочный S вход одновременно соединен с выходом элемента отключения разрядов 5.3, разрешающим входом V и входом первого инвертора 5.1.1, выход которого соединен со вторым входом двухвходового элемента "И" 5.1.2. Установочный вход R через второй инвертор 5.1.5 соединен с выходом элемента запуска 5.4. Синхронизирующий вход С 1-й ячейки соединен с синхронизирующего элемента 5.2, синхронизирующие входы С ячеек 5.1₂... 5.1_N одновременно соединены со вторым входом синхронизирующего элемента 5.2 и входом блока управления (фиг. 2). Информационный вход D первой ячейки одновременно подключен к выходу входного элемента 5.6 и первому входу двухвходового элемента "И" 5.1.2. Информационные входы ячеек 5.1₂... 5.1_N одновременно соединены с первым входом двухвходового элемента "И" 5.1.2 ячеек 5.1₂... 5.1_N и выходом двухвходового элемента "ИЛИ" 5.1.4 ячеек 5.1_l... 5.1_N-1, первый вход которого соединен с выходом двухвходового элемента "И" 5.1.2, а второй с прямым выходом DV-триггера, являющимся выходом блока управления. Выход двухвходового элемента "ИЛИ" 5.1.4 ячейки 5.1_N соединен с первым входом входного элемента 5.6 (фиг. 2).

Элемент запуска 5.4 может быть реализован, как показано на фиг.4, и включает источник питания Е, RC-цепочка и переключатель, выход элемента запуска одновременно соединен с установочными входами i-х ячеек регистра сдвига.

Элемент начальной установки 5.5 может быть реализован, как показано на фиг. 5, и включает в себя источник питания Е, гасящий резистор и кнопку. Выход элемента одновременно подключен к первому входу синхронизирующего элемента 5.2 и ко второму входу входного элемента 5.6, представляющего собой двухвходовый элемент "ИЛИ". Синхронизирующий элемент 5.2 представляет собой двухвходовый элемент "ИЛИ", второй вход которого одновременно соединен со входом блока управления и с синхронизирующими входами 5.1₂... 5.1_N ячеек регистра сдвига. Элемент отключения разрядов 5.3 реализован на базе резистивной матрицы, идентичной первой 3.1 и второй 3.2 резистивной матрице блока формирования порогов, i-й выход которой соединен с разрешающим выходом i-й ячейки регистра сдвига.

DV-триггеры могут быть реализованы на интегральных микросхемах, описанных в книге: В. А. Батушев, В.Н. Вениаминов, В.Г. Ковалева и др.; Микросхемы и их применение - М.: Энергия, 1978г., стр.164-168.

Элементы "И", "ИЛИ", инверторы могут быть реализованы на интегральных микросхемах, описанных в книге: Б.В. Тарабрин, Л.Ф. Лунин, Ю.Н. Смирнов и др. ; Интегральные микросхемы; Справочник. - Издание второе, исправленное - М: Энергоатомиздат, 1985г.

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

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

Точность формирования моделируемых функций распределения во многом определяется возможностью генераторов случайных чисел (ГСЧ) формировать последовательность чисел, значения которых в каждом такте его работы являются случайной величиной, определенной в интервале от 0 до М^N-1, где N - число разрядов датчика случайных чисел ГСЧ, М - основание используемой системы счисления (М.П. Бобнев "Генерирование случайных сигналов. Изд. 2-е перераб. и доп. - М., "Энергия", 1971, с. 132). При этом N-разрядный генератор позволяет получить n= M^N (1) различных чисел. В этом случае вероятность появления каждого из n чисел определяется числом разрядов ДСЧ, которое в общем случае является конечным. Данное обстоятельство обуславливает определенные трудности получения случайных величин с малой вероятностью. Область генерирования случайных величин с малой вероятностью можно расширить, применив последовательное формирование числа с использованием метода селективных выборок (Л.1, с.136).

Смысл данного метода заключается в отсеивании совокупности чисел, не удовлетворяющих требуемому правилу. В этом случае формируется область чисел, которые являются "истинными", и участвуют в формировании случайных чисел на следующем шаге преобразования. В этом случае вероятность появления требуемого случайного числа на каждом шаге преобразования подчиняется гипергеометрическому распределению (В.С. Королюк, Н.И. Портенко, А.В. Скороход, А.Ф. Турбин. Справочник по теории вероятности и математической статистике. Издание второе, перераб. и дополненное. М.; "Наука", 1985, с.112).

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

Сигнал в виде двоичного k-разрядного числа с выхода датчика случайных чисел (ДСЧ) (фиг. 1) поступает на информационные входы элементов "И" всех блоков ключей (фиг.6). Управляющий i-й вход блоков ключей соединен с соответствующим i-м выходом блока управления и при наличии на нем сигнала логической "1" происходит запись числа в i-й блок формирования порогов.

В каждый момент времени (такт) сигнал логической "1" имеется только на одном из выходов блока управления. Это обусловлено тем, что основу блока управления (фиг. 2) составляет кольцевой регистр сдвига, работающий следующим образом. При включении питания (фиг.3), когда замыкаются контакты переключателя элемента запуска 5.4 ячейки регистра сдвига, выполненные на базе DV-триггера, устанавливаются в "0" состояние. Это происходит благодаря кратковременной подаче сигнала логического "0" на вход . Подача сигнала логической "1" на установочные входы S ячеек, участвующих в формировании выходного сигнала, осуществляется замыканием контактов соответствующих переключателей элемента отключения разрядов 5.3. Таким образом, ячейки разрядов регистра подготавливаются к работе по информационному входу D. Путем кратковременного замыкания кнопки элемента начальной установки 5.5 (фиг.5) сигнал логической "1" через входной элемент 5.6 и синхронизирующий элемент 5.2, поступая на информационный вход D и синхронизирующий вход С DV-триггера первой ячейки, обеспечивает запись в нее "1". При этом на выходе первого триггера будет "1", на выходе остальных "0". В случае, когда i-й триггер не используется в формировании выходного сигнала, на разрешающий вход ячейки регистра сдвига от элемента 5.3 подается логический "0", в этом случае сигнал логической "1" через элемент 5.1.2 и 5.1.4, минуя триггер ячейки сдвига, подается на информационный вход следующего триггера. При этом сигналом логического "0" на выходе триггера обеспечивается запрет записи числа с выхода ГСЧ через соответствующий блок ключей на блок формирования порогов.

Последовательное перемещение по разрядам регистра сдвига осуществляется подачей на синхронизирующие входы С триггеров сигнала логической "1", который формируется в N-входовом элементе "ИЛИ" (фиг.8) при наличии "1" на выходе любого i-го блока формирования порогов. В этом случае на информационных выходах 1, 2,..., i блока управления попеременно формируются комбинации 100. .. 00, 010... 00, 000... 01, которые, поступая на управляющие входы элементов "И" блоков ключей (фиг.6), разрешают запись числа с выхода ДСЧ на вход соответствующего блока формирования порогов.

В блоке формирования порогов с помощью узлов сравнения 3.3 и 3.4 (фиг.7) производится сравнения N-разрядного числа, поступающего с выхода блока ключей с верхним и нижним порогами, которые определяются требуемой вероятностью появления числа. Пороги устанавливаются с помощью резистивных матриц 3.1 и 3.2. В случае удовлетворения условий, задаваемых резистивными матрицами, сигнал "1" через блок 3.8 подается на вход N-входового элемента "ИЛИ" 4.

В результате последовательной селективной выборки чисел при появлении результирующего сигнала на выходе элементов 3._l,..., 3.7_k N-го блока формирования порогов будет сформировано случайное число, удовлетворяющее требованиям.

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

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

2. Генератор по п. 1, отличающийся тем, что блок управления состоит из входного элемента, представляющего собой двухвходовой элемент ИЛИ, синхронизирующего элемента, блока запуска, блока отключения разрядов, блока начальной установки и N-разрядного регистра сдвига, включающего N ячеек, продвигающий выход j-й ячейки, где j= 1, 2, . . . , N-1, N-разрядного регистра подключен к информационному входу (j+1)-й ячейки, а продвигающий выход N-й ячейки подключен к первому входу входного элемента, второй вход которого подключен к первому входу синхронизирующего элемента и выходу блока начальной установки, выход входного элемента подключен к информационному входу первой ячейки N-разрядного регистра, синхронизирующие входы ячеек N-разрядного регистра с номерами от второго до N-го объединены, подключены ко второму входу синхронизирующего элемента, являющемуся входом блока управления, а синхронизирующий вход первой ячейки подключен к выходу синхронизирующего элемента, разрешающий вход i-й ячейки N-разрядного регистра подключен к i-му выходу блока отключения разрядов, а установочные входы всех N ячеек N-разрядного регистра объединены и подключены к выходу блока запуска, информационные выходы всех N ячеек N-разрядного регистра являются соответствующими N выходами блока управления.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8