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

(54) геНЕРАТОР СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

ЧИСЕЛ

Изобретение относится к вьпшслительной технике и препназначено для генерашга потока равномерно-распределительных чисел в заданном циапазоне . Устройство целесообразно применять при решении задач методом имитационного моделирования, исследования и оптимизации структурно сложных систем, в качестве датчика случайных, чисел при решении задач методами статистических испытаний. В частноепи имитационные модели сложных систем предполагают наличие аппаратуры, отвечающей различным, в том числе противоречивым требованиям. Это большое число каналов имитации, высокая интенсивность потоков выходных случайных величин, отсутствие корреляционных зависимостей между каналами и в потоках каждого канала, возможность программного управления, а при имитации быстро меняющейся обстановки - простота алгоритмов расчета настроечных параметров. Ядром лю бого имитатора случайных npcaieccoB являются генераторы случайных величин, чи|сел, последовательностей. Их характеристики в конечноьм счете и определяют возможность iitvJhratopa, следовательно и модели, а далее и эффективность решения .задачи. Например, наличие корреляционных связей в потоке случайных чисел требует значительного увеличения обьема выборки для достижения одинаковой достоверности результатов по сравнению с использованием некоррелированного потока при решении задач методами Мрнте-Карло. Наличие корреляционных связей делает подчас невозможным получение достоверного результата в решении задач исследования сложных систем методами имитационного моделирования. Интенсивностью Генераторов случайных величин определяется пригодность модели для решения задач в реальном масштабе времени. Известно устройство для генерирования случайных чисел, содержащее генератор равномерно-распределенных случайных чисел, блок сравнения, ретстр маски, регистр числа, блогс памяти, регистр . блей управления. Устройство позволяет фор мировать последовательности спучайнъ., чисел с пршзвольным (заданным) законом распределения и реализует метод условных вер 5 остей ij. Недостатком известного уб ройсгва является то, что изменение диапазона генерируемых чисел без изменения при этом закона распределения тре бует изменения настроечных параметров, расчет которых достаточно трудоемок; кро ме того, формирование одного случайного тасла требует VI вычислительных операций, где h- разрядность числа, т.е. с ростом разря,дносги формируемых чисел увеличиваются временные затраты на генерируемое число; недостатком является также относительно сложная аппаратура реализация, так как для получения высокого быстродействия, сравнимого ,с граничной рабочей частотой элементов, требуется бьютродействующая память. Известно устройство для генерирования случайных чисел, содержащее датчик случайных чисел, блок схем Запрет, дешифратор, набор схем И, ИЛИ, НЕ, счетчик с пересчетом А, блок логических схем. Принцип работы-устройства основан на сравнении некоторого случайного числа R. с границей диапазша А (диапазон (0;А). Если R: А, то блок схем Запрет закрыт, на выход устройства проходит состояние счетчика, далее к содержимому счетчика прибавляется единица. Если число А, то на выход устройства проходит R- , т.е. интенсивность появления чисел на выходе постоянна . Чем меньше А, тем большей длины последовательности состояний счетчика проходят на выход устройства, тем больше значения автокорреляционной функции выходного потока при малых аргументах . Недостатком этого устройства является коррелированность выходной последовательности, причем значение актокорреляциданой функции увеличивается прямо пропорционально уменьшению диапазона генерации. Достижение постоянной интенсивности выходного потока случайных чисел получено за счет ухудшения их качества. Наиболее близким по технической сущносги к предлагаемому является устройство для статистического моделирования, с держащее датчик случайных чисел, генератор тактовых импульсов, первый блок коньюнкторов (вентилей), первый вход которого соединен с выходом датчика случайных чнсел,,второй - с выходом генератора тактовых импульсов, регистр второй блок коньюнкторов (вентилей), первый вход которого соединен с выходом генератора тактовых импульсов, второй вход - с выходом регистра, схему сравнения, вход которой соединен с выходом первого блока коньюнкторов, второй - с выходом второго блока коньюнкторов, блок выходных вентилей, первый вход которого подключен к вьЕсопу первого блока коньюнкторов, второй вход - к выходу схемы сравнения, выход заведен на выход устройства. Устройство работает по принципу отбора случайных чисел. В регистре хранится число, определяющее верхнюю границу диапазона генерирования. Числа, большие этой границы, отбрасываются, меньшие проходят на выход устройства. Таким образом, в случае равномерного закона распределения интенсивность появления выходных чисел обратно пропорциональна величине диапазона этих чисел. Недостатком устройства является то, что снижение интенсивности выходных случайных чисел пропорционально уменьшению диапазона их генерирования, что, во-первых, затрудняет управление параметрии формируемых случайных величин при использовании устройства в имитационной аппаратуре, т.е. изменение диапазона существования формируемой случайной величины связано с изменением интенсивности ее появления, во-вторых, ухудшает эксплуатационные качества устройства при использовании его в качестве датчика случайных чисел для ЭВМ ввиду увеличения времени на решение задачи методами статистических испытаний в сдучае потребности в числах меньших, п«з сравнению с максимальным, диапазонов;кроме того, асинхронная работа системы генератор-потребитель вец-эт к неизбежным повторным считываниям одного и того же числа, вероятность которых возрастает с уменьшением диапазона, что ухудшает корреляционные характеристики последовательности чисел, П1:книмаемой потребителем. Выше было указано на nt следствия ухудшения корреляционных характеристик потока случайных чисел, используеммл для решения тех или иных задач. Вследствие этого можно угверж- дать, что и-звесгное устройство обладает в целом невысоким быстродействием, так как уменьшая диапазон генерируемых случайных чисел от максимального до требуемого значения, во столько же раз уменьшают бьгстродействие устройства, а так же то, что корреляционные свойства потока чисел, принимаемого потребителем, недостаточно высокие и ухудшаются с уменьшением диапазона генерируемых чисел.

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

Для достижения поставленной цели в известный генератор случайной поспедовательности чисел, содержащий первичный датчик случайных чисел, регистр кода, блок элементов И, первый вход которого соединен с выходом первичного датчика случай- ных чисел, блсж сравнения, первый вход которого соединен с выходом блока элементов И, введены блок управления, регистр памяти и шифратор, вход которого объединен со вторым входом блока срав- 20 нения и подключен к выходу регистра кода, а выход шифратора соединен со вторым входом блока элементов И, выход которого соединен с первым входом ретастра памяти и со вторым входом блока сравнения, выход 25 которого соединен со вторым входом регистра памяти, выход которого является выходом генератора, при атом блок упра влшия содержит генератор тактовых импульсов, триггер, элементИ-НЕ и элемент И, зо первый вход которого соединен с выходом генератора тактовых импульсов, а выход элемента И соединен со входом первичного датчика случайных чисел и с третьим входом регистра памяти, вьлход элемента 35 И-НЕ соединен со вторым входом элемента И, тактовый вход триггера соединен с выходом элемента И, единичный вход триг гера соединен с первым входом элемента И-НЕ, с Выходом блока сравнения, нуле- 40 вой вход триггера является входом генератора, а выход триггера соединен со вторым входом элемента И-НЕ и является вторым выходом генератора. ,

Кроме того, шифратор содержит группу 45 элементов ИЛИ, выходы которых являются выходами шифратора, первые входы каждого элемента ИЛИ соединены с выходами предысстцнх старших разрядов шифратора соответственно, а вторые входы элемен- 50 тов ИЛИ являются входом шифратора.

Введение новых блоков и связей обуславливает появление следующего положительного аффекта: увеличение быстродействия вследствие повьииения верО5ЯРНости 55 отбора случайных чисел, попадакядих в грашшы диапазона генериртжания за счет В1ведения шифратора, вход которого соединен

с выходом регистра кода диапазона, а выход соединен с первым входом блока коньюнкторов; вероятность отбора в предлагаемом устройстве не менее 0,5, в известном вероятность отбора при небольши значениях границы диапазона значительно меньше 0,5 (фиг. 4) и равна А/Ауу,ду, где А-граница диапазсиа, максимально возможное значение границы диапазона; синхронный режим работы с потребителем случайных чисел за счет введения блока управления, первый вход ксн« торого соединен с выходом схемы сравнения, первый выход соединен с выходом датчика с учайных чисел и вторым выходом регистра выхода, второй вход блока управления является выходом запуска генератора случайных последовательностей, а второй выход является указателем готовности устройства.

На фиг. I представлена структурная схема генератора случайных последовате льностей;на фиг. 2 - схема шифратора; на фйГ. 3 - график зависимости РОТБ (А)

I для воськтеразрядного генератора (1- для предлагаемого генератора 2 для

прототипа).

Устройство содержит датчик случайных чисел I, регистр кода 2, шифратор 3, блок элементов И 4, блок сравнения 5, регистр памяти 6, блок управления 7. ход датчика случайных чисел I соединен с первым входом блока элементов И 4, выход регистра Кода 2 соединен со входом шифратора 3 и вторым входом блока сравнения 5, выход блока элементов 4 соединен с псовым входом регистра памяти и с первым входом блока сравнения 5, выход шифратора 3 соединен со ВТ орым входом блока элементов И 4, выход блока сравнения 5 соединен с вторым входом регистра памяти бис первым входом блока управления 7, первый выход блока управления 7 соединен со входом датчика случайных чисел 1 и третьим входом penicrpa памяти 6, второй вход блока управления 7 является входом запуска генератора случайных последовательностей, а второй выход является указателем готовности устройства, выход выходного ре- гастра 6 является выходом устройства.

В предлагаемом устройстве реазизуется принцип отбора случайных чисел с автоматическим уменьшением разрядности датчика случайных чисел при уменьшении диапазона генерируемых чисел. Устройство работает в двоичной систему счисления, разрядность блоков (1-6) оаинакова и равна йБлок управления соцержит генератор токговых импульсов 8, элемент И9, эле мент И-НЕ 10, триггер 11 . Выхоц генератора 8 соединен с первым входом эле мента И9, выход котфого соединен с

первым входом триггера 10 и является первым выходом блока управления, а второй вход соединен с выходом элемента И-НЕ 10, соединенные межс собой первый и второй входы элемента И-НЕ 10 и триггера 11 соответственно, являются j первым входом блока управления, вторым входом блока управления является третий рход триггера 11, выход которого соединен со вторым входом элемента И-НЕ 1О и является выходом 2 (готовность) блока управления.

Функциональная схема одной из воз можньк реализаций шифратора, 3 иредставлена на фиг, 3. Шифратор содержит H-f двухходовьх элементов ИЛИ, выходы которых являются разрядными выходами шифоагора, первые входы которь1Х (элементов ИЛИ) соединены с выходами предыдущих разрядов шифратора, а вторые входы являются разрядными входами шифратора. Вход первого разряда шифратора соединен непосредственно с вьссодом. Если в старших разрядах поступающего на вход числа нули, на выходе шифратора в этих разрядах тоже нули, на всех остальных младших выходах шифратора,, начиная с разряда, на который поступает первая единица входного кода, находятся единицы.

Устройство функционирует следующим обризом.

Латчик сдучайных чисел 1 ффмирует случайные числа с равномерным распределенв:ем в диапазоне О - 2 , С выхода I блока управления 7 на вход датчика случайных чисел 1 поступают тактовые импульсы, по каждому из которых датчик случайных чисел формирует одно новое случайное число, которое через блок элементов И 4, в котором производится его предварительное преобразование в соответствии с Кодом выхода шифратора 3, по ступает на втфой вход схемы сравнения, на первый вход которой поступает из регистра 2 код границы диапазона А, Если очередное поступающее на вход схемы сравнения 5 случайное число меньше либо равно коду границы диапазона, с выхода схемы сравнения на входы регистра б и блока управления 7 поступает сигнал логической единицы, разрешатацей запись по следующему импульсу с первого выхода блока управления 7 случайного числа в регистр 6. Одновременно на втором выходе блока управления устанавливается сигнал готовности, указывающий об окончании фомирования нового случайного числа. Если очередное случайное число больше код границы диапазона, то сигналом логического нуля с выхода схемы сравнения 5 запись в регистр 6 и установка сигнала готовности запрещаются, устройство переходит к анализу следующего случайного числа. В соответствии с кодом границы диапазона шифратора 3 формирует так называемый код маски, представляющий собой последовательность нулей в старших разрядах до первого значения числа разряда в коде диапазона (до первого разряда равного единице) и единиц в остальных младших разрядах. Разрядные выходы шифратора соединены с первыми входами элементов И блока 4, ко вторым входам которых подсоединены разрядные выходьг датчика случайных чисел, гри этом происходит поразрядное логическое умножение кода маски и случайных чисел, в результате чего на выходе блока коньюнкторов автоматически получаются разрядные числа, количество значащих разрядов которых равно количеству значащих цифр в коде диапазона.

Во избежание повторных считываний одного и того же числа считывание устройством-потребителем случайных чисел осуществляется только при наличии сигнала готовности на втором выходе блока управления 7. При этом на второй вход блока управления от устройства-потребителя должен поступить сигнал запроса, который говорит о том, что с;1учайное число считано и можно формировать новое, сигнал Готовности отбрасывается блоком управления.

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

Блок управления функционирует следуюш нм образом.

При поступлении на вход триггера 11 сигнала запроса- триггер 11 устанавливается в нулевое состояние, при атом на выходе элемента И-НЕ Ю сигнал логи- ческой еииттцы, разрешакядий прохождение импульсов генератора 8 через элемент 9 93 И 9 на выход блока управления. При поступлении сигнала лопической единицы с выхода схемы сравнения 5 триггер 11 устанавливается следующим тактовым импульсом в единичное состоявде - на выхо це блока управления присутствует сигнал пэтовности. ЕСЛИ следующий сипнал логической единицы с выхода схемы сравнения 5, котфый говорит, что на выходе блока элементов И 4 находится новое число меньшее либо равное границе диапазона, поступает в блок управления раньше, чем поступает повторный сигнал запроса, на выходе элемента И-НЕ 10 вырабатывается уровень логической единицы, запретающий прохождение тактовых импульсов че- ,

рез элемент И9 на выход блока управления, а следовательно, и синхронизацию датчика случайных чисел 1 и регистра 6. При этом и в регистре 6 и на выходе бло-20 ка 4 находотся случайные числа, попадающие в диапазон О-А. При поступлении сигнала запроса триггер 11 устанавливается в нулевое состояние, при этом по следующему тактовому импульсу число с Выхода блока 4 записывается в регистр выхода 5 и вырабатывается сигнал готовшэсти, устройство начинает поиск следующего числа, попа-дающего в диапазон фор мирования. у.. Так как в использовании данного блока управления устройство после записи в выходной регистр нового случайного числа не останавливается до момента поступления сигнала запроса, а сраЪу начинает поиск следующего, суммарное время остановок сокращается, интенсивность формирования выходных чисел повышается. Если -1, где 1 - 0,,...,И-, все полученные на выходе блока коньюнкторсй случайные числа меньше либо равны А, , , вероятность отбора равна едшшце, скорость работы устройства максимальна и равна скорости работы датчика случайных чисел I. Наименьшее быстродействие устройства получаем при . При этом коли чество чисел на выходе блока коньюнкгоров, меньших, либо равных А, равно , больших - 2 -I, вероятность отбора при равномерном распределении ()/2 О,5+2 - Таким образом, вероятность отбора случайных чисел в предлагаемом устройстве во всем диапазона изменения А не Меньше 0,5, устройство дает выипрыш в быстродействии по сравнению с известным при А А ууц,,/2, тем более значительный, чем меньше А. Вероятность отболее высоким быстродействием, обусловленным более высокой вероятностью отбора случайных чисел, а, также сокраще3бора меньше зависит в предлагаемом устройстве от А, чем в известном. Время формирования одного выходного числа включает случайное количество тактов отбора. Математическое ожидание времени формирования вьгражается через вероятность отбора () соотношением .I.-p. Где ДТ ген - период следования импульсов сшхрсяизации датчика случайных чисел М (Ьфор/ - минимально и равно ДТген при при уменьшении PQJ-B - увеличивается. Таким образом, предлагаемое устройство обладает по сравнению с известным нием времени остановок устройства между моментами времени окончания формирования чисел и их потребления; меньшей зависимостью скорости формирования чисел от значения границы циапазша; возможностью синхронного с формированием случайных чисел их потребления, что исклк чает повтфные считывания одних и тех же чисел, и следовательно, корреляцию выходного потока. Формула изобретения I. Генератф случайных последовательностей чисел, содержащий первичный дат.чик случайных чисел, регистр кода, блок элементов И, первый вход которого соешгаен с выходом первичного датчика случайных чисел, блок сравнения, первый вход которого соединен с выходом блока элементов И, отличающийся тем, что, с целью повышения быстродействия генератора, он содержит блок управления, регистр памяти и шифратор, вход которого объединен со вторым входом блока сравнения и подключен к выходу регистра кода, а вьосод шифратора соединен со вторым входом блока элементов И, выход которого соединен с первым входом регистра памяти и с вторым входом блока сравнения, вькод которого соединен с вторым входом регистра памяти, вькод кото рого является первым выходом генератора, при атом блок управления содержит генератор тактовых импyльcoвj триггер, элеменг И-НЕ .элемент И, первый вход кото;рого соепинен с выходом генератора тактовьсс импульсов, а выход элемента И соединен со вхояом первичного датчика слу 11.93 чайнья чисел и с третьим входом регист ра пвмятИ| выхоа элемента И-НБ сеепинен со вторым входом элемента И, тактовый вхоа триггера соедагаен с выходом элемента Hi единичный вход триггера соединен с первым входом элемента И-НБ и с выходом блока сравнения, нулевой вход триггера является входом генератора, а JeuxoQ триггера соединен с вторым входом алек49нта И-НБ и является вторым выходом генератора. 2.Генератор по п. I, о т л и ч а ю Ш к и с я тем, что шифратор содержит элементов ИЛИ, выходы которых являются выходом шифратора, первые ды Каждого элемента ИЛИ соединены с выходами предыдущих старших разрядов шифратора соответственно, а вторые входы элементов ИЛИ являются входом шифратора. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР 488212, кл. 6 06 F 15/20, 1973. 2.Авторское свидетельство СССР 398940, кл. О Об F 1/02, 1972. 3,. Авторское свидетельство СССР 387353, кл. 6 Об F 1/О2, 1971 (прототип).

Фи1.2