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

112

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

Цель изобретения - расширение об- лйсти применения генератора путем получения гипергеометрического распределения.

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

Генератор случайных двоичных чисел содержит генератор 1 импульсов, первый 2 и второй 3 злементы задержки, элемент 4 ЗАПРЕТ, элемент И 5, дели- тель 6 частоты, первый 7, второй 8 и третий 9 регистры памяти, первый 10 и второй 11 вычитающие счетчики, мирующий счетчик 12 и блок 13 формирования случайного двоичного прот цесса.

Блок 13 формирования случайного двоичного процесса содержит генератор 14 случайного потока импульсов, элемент 15 ЗАПРЕТ, вероятностный двухполюсник 16, преобразователи 17 и 18 код-интенсивность случайного потока импульсов, триггер 19;

Каждый преобразователь 17 и 18 со- держит элемент 20 задержки, счетчик 21, стробированный дешифратор 22, группу 23 элементов И и элемент ИЛИ 24.

Сущность изобретения основана на моделировании случайных испытаний, заключающихся в извлечении (без возврата) шаров из урны, содержащей К и N-K шаров белого и черного цвета соответственно, и подсчете числа шаров белого цвета в серии из п испытаний (извлечений). В результате этого у предлагаемого объекта появляется новое свойство дискретной вероятност- ной системы с тремя степенями свободы: п, R и N-R. Отметим, что известный генератор имеет один регулируемый параметр п. Благодаря этому .свойству область применения (функциональные возможности) генератора случайных чисел расширяется за счет получения гипергеометрического распределения.

0

0

5

0

35

40

45 50

182

Генератор случайных двоичных чисел работает следующим образом.

Предварительно в первый 7 и второй

8регистры памяти заносят числа К и N-K, определяющие численность белых

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

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

Каждый импульс с выхода делителя 6 записывает содержимое первого 7 и второго 8 регистров памяти в первый to и второй 11 вычитающие счетчики соответственно, а содержимое суммирующего счетчика 12 - в третий регистр

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

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

Рассмотрим работу блока 13 более подробно. ,;

Импульсы генератора 14 случайного потока импульсов через постоянно открытый в отсутствие входных импульсов элемент 15 ЗАПРЕТ поступает на вход равновероятностного двухполюсника 16. Равновероятностный двухполюсник 16 разделяет входной поток на два независимых друг от друга потока с равной интенсивностью. Первый поток импульсов с помощью первого преобразователя 17 код-интенсивность, управляемого двоичным кодом, преобразуется в случайный поток импульсов .Aj. Аналогично второй поток с помощью второго преобразователя 18 код-интенсивность преобразуется в поток ц.

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

Таким образом, параметр случайного двоичного процесса на выходе блока 13

31

является функцией текущих состояний первого 10 и второго 11 вычитающргх счетчиков.

Двоичный процесс присутствует на управляющих входах элемента 4 ЗАПРЕТ и элемента И 5, на информационные входы которых поступают тактовые импульсы генератора 1. При выполнении условия F с помощью элемента И 5 и элемента А ЗАПРЕТ реализуются независимые случайные извлечения отдельных шаров из моделируемой урны.

Каждый импульс генератора 1 с вероятностью (0) --- по является

на выходе элемента 4 ЗАПРЕТ. Это событие эквивалентно выбору из урны шара черного цвета-, поэтому содержимое второго вычитающего счетчика 11 всякий раз уменьшается на единицу. При этом изменение управляющего кода У приводит к изменению параметра Р(0) случайного двоичйого процесса на выходе блока 13.

гг

С вероятностью Р(1) - импульсы

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

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

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

С целью повьш1ения надежности рабо.ты генератора случайных чисел блок 13 формирования случайного двоичного процесса бланкируется путем отключения равновероятностного двухполюсника 16 от генератора 14 случайного потока импульсов. Второй элемент 3 задержки предназначен для разделения моментов проведения последнегр из серии п извлечения шара и установки начальных

184

состояний соответствующих элементов в новом рабочем цикле генератора.

При больших, значениях N для гипергеометрического распределения справедливы следующие приближения: биномиальное, если ,1 пуассоновское,

если 0,1 и- 0,1,- нормальное,

n-K-(N - R)(N-n)- если D 9, где D N(

дисперсия гипергеометрического распределения.

5

0

0 5

0 5

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

1. Генератор случайных двоичных чисел, содержащий генератор импульсов, делитель частоты, выход которого соединен с входом первого элемента задержки, выход которого соединен с входом Сброс суммирующего счетчика, элемент И, элемент ЗАПРЕТ, второй элемент задержки, отличаю-, щ и и с я тем, что, с целью расширения области применения генератора путем получения гипергеометрического распределения, он содержит два вычитающих счетчика, блок формирования случайного двоичного процесса, три регистра памяти, выход генератора импульсов соединен с первым входом элемента И, прямым входом элемента ЗАПРЕТ, входом ЗАПРЕТ блока формирования случайного двоичного процесса и входом второго элемента задержки, выход которого соединен с входом делителя частоты, выход которого соединен с входами Запись первого и второго вычитающих счетчиков и первого регистра памяти, информационный вход которого подключен к информационному выходу суммирующего счетчика, а выход первого регистра памяти является выходом генератора, выходы второго и третьего регистров памяти соединены с информационными входами соответственно первого и второго вычитающих счетчиков, информационные выходы которых соединены соответственно с первым и вторым входами задания интенсивности блока формирования случайного двоичного процесса, выход которого соединен с вторым входом элемента И и инверсным входом элемента ЗАПРЕТ, выход которого соединен со счетным входом первого вычитающего счетчика.

5128

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

2. Генератор поп.1,отлича- ю щ и и с я тем, что блок формирования случайного двоичного процесса содержит генератор случайного потока импульсов, элемент ЗАПРЕТ, равновероятностный двухполюсник, два преобра- зователя код-интенсивность случайного потока импульсов, триггер, прямой выход которого является выходом блока, входом ЗАПРЕТ которого является инверсный вход элемента ЗАПРЕТ,, прямой вход которого подключен к выходу генератора случайного потока импульсов, а выход элемента ЗАПРЕТ соединен с входом равновероятностного двухполюсФаг. /

18 6

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

-f3

Редактор О.Бугир

Составитель А.Карасов

Техред Л.Сердюкова Корректор Л.Пилипенко

Заказ, 1267/ 7Тираж 670 Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, Д

Фиг. 3

Генератор случайных двоичных чисел относится к вычислительной технике и может быть использован при построении датчиков случайных чисел с гипергерметрическим распределением. Цель изобретения - расширение области применения генератора путем получения гипергеометрического распределения. Генератор.случайных чисел содержит генератор импульсов, делитель часто-, ты, выход переноса которого через первый элемент задержки соединен с входом Сброс суммирзпощего счетчика, элемент И, элемент ЗАПРЕТ и второй элемент задержки. Новым является введение первого и второго вычитакщих счетчиков, блока формирования случайного двоичного процесса, первого, второго и третьего регистров памяти. При этом выход генератора импульсов соединен с первым входом элемента И, прямым входом элемента ЗАПРЕТ, входом бланкирования блока формирования случайного двоичного процесса и входом второго элемента задержки. Выход последнего соединен с входом делителя частоты, выход переноса которого объединен с входами Запись вычитающих счетчиков и третьего регистра памяти, информационный вход которого подключен к выходу суммирующего счетчика, : а выход является выходом генератора. Выходы первого и второго регистров памяти соединены с входами соответствующих вычитающих счетчиков, разрядные выходы которых соединены соответственно с первым и вчорым управляющим входами блока формирования случайного двоичного процесса. Выход этого блока соединен с вторым входом элемента И и инверсным входом элемента ЗАПРЕТ, выходы которых соединены соответственно с объединенными между собой счетными входами второго вычитающего и суммирующего счетчиков и счетным входом первого вычитающего счетчика. Кроме того, блок формирования случайного двоичного процесса содержит последовательно соединенные , генератор случайного потока импульсов, элемент ЗАПРЕТ, инверсный вход которого является входом бланкирования блока, и равновероятностный двухполюсник, выходы которого соединены с входами первого и второго преобразователей, код-интенсивность. Выходы преобразователей соединены с S и R- входами Триггера, прямой выход кото рого является выходом блока. 3 ил. § (Л