Генератор случайных последовательностей чисел

 

С. Ф. Костюк, А. И. Кузьмич, Н. И. Мельник и A. Г. Якубенко (72) Авторы изобретения.(7!) Заявитель

Минский радиотехнический институт (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

ЧИСЕЛ

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

5 задач методом имитационного моделирования, исследования и оптимизации структурночгложных систем, в качестве датчика случайных чисел при решении задач методами статистических испытаний. B частнсс-

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

15 потоков выходных случайных величин, отсутствие корреляционных зависимостей между каналами и в потоках каждого канала, возможность программного управления, а при имитации быстро меняюшейго ся обстановки — простота алгоритмов расчета настроечных параметров. Ядром moбого имитатора случайных процессов являются генераторы случайных величин, чиiced, последовательностей. Их характерис тики в конечноьм счете и определяют возможность имитатора, следовательно и модели, а далее и эффективность решения задачи. Например, наличие корреляционных связей в потоке случайных чисел требует значительного увеличения обьема выборки для достижения одинаковой достоверности результатов по сравнению с использованием некоррелированного потока при решении задач методами Мрите- 1<арло. Наличие корреляционных связей делает подчас невозможным получение достоверного результата в решении задач исследования сложных систем методами нмпта» ционного мооелирования. Интенсивностью генераторов случаййых величин определ ется пригодность модели для решения задач в реальном масштабе времени.

Известно устройство для генерирования случайных чисел, содержашее генератор равномерно-распределенных случайных чисел, блок сравнения, регистр маски, регистр числа, блок памяти, регистр ад » са, 038983 блок управления. Устройство позволяет формировать последовательности случайных чисел с произвольным (заданным) законом распределения и реализует метод условных вероятйлстей (1J. Недостатком известного устройства является то, что изменение пиапазона генерируемых чисел без изменения при этом закона распределения требует изменения настроечных параметров, расчет которых достаточно трудоемок; кро- " ме того, формирование опного случайного числа требует И вычислительных операций, гпе р- рвзряпность числа, т.е. с ростом рвзряпности формируемых чисел увеличиваются временные затраты нв генерируемое число; недостаткам является также относительно сложная аппаратура реализация, так как пля получения высокого быстродействия, сравнимого,с граничной рабочей частотой элементов, требуется быстродействующая память.

Известно устройство пля генерирования случайных чисел, содержащее датчик случайных чисел, блок схем Запрет, пешифратор, набор схем И, NEIN, НЕ, счетчик с пересчетом А, блок логических схем.

Принцип работьг устройства основан на сравнении некоторого случайного числа R. с границей диапазона А (пиапвзон (О;А).

Если R< > А, то блок схем "Запрет за- 3о крыт, на выхоп устройства прохопит состояние счетчика, палее к сопержимому счетчика прибавляется епиница. Если число Р; А, то нв выход устройства прохопит R-, т.е. интенсивность появления

1 чисел на выходе постоянна . Чем меньше

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

Недостатком этого устройства является коррелированность выхопной послеповательности, причем значение актокорреляционной функции увеличивается прямо про- <> порционально уменьшению диапазона генерации. Достижение постоянной интенсивно» сти выходного потока случайных чисел получено за счет ухудшения их качества.

Наиболее близким по технической сущ- -"" ности к предлагаемому является устройство для статистического мопелироввция, содержащее датчик случайных чисел, генератор тактовых импульсов, первый блок коньюнкторов (вентилей), первый вход кото- ." рого соепинен с выходом патчика случайных чисел„второй — с выхопом генератора тактовых импульсов, регистр второй блок коньюнкторов {вентилей), первый ехоп которого соепинен с выходом генератора тактовых импульсов, второй вхоп — с выхопом регистра, схему сравнения, вхоп которой соепинен с выходом первого блока коньюнкторов, второй — с выхопом второго блока конь|онкторов, блок выходных вентилей, первый вход которого подключен к выходу первого блока коньюнкторов, второй вхоп - к выходу схемы сравнения, выхоп заведен на выход устройства. Устройство работает по принципу отбора случайных чисел. В регистре хранится число, опрепеляющее верхнюю границу диапазона генерирования. Числа, большие этой границы, отбрасываются, меньшие проходят на выход устройства. Таким образом, в случае равномерного закона распрепеления интенсивность появления выходных чисел обратно пропорциональна величине пиапазона этих чисел.

Недостатком устройства является то, что снижение интенсивности выходных случайных чисел пропорционально уменьшению диапазона их генерирования, что, во-первых, затрудняет управление параметрии формируемых случайных величин при использовании устройства в имитационной аппаратуре, т.е. изменение пивпазона существования формируемой случайной величины связано с изменением интенсивности ее появления, во-вторых, ухупшает эксплуатационные качества устройства при использовании его в качестве датчика случайных чисел пля ЭВМ ввипу увеличения времени на решение задачи мет одами статистических испытаний в случае потребности в числах меньших, по сравне нию с максимальным, диапазонов кроме тога, асинхронная работа системы генератор-потребитель вепет к неиз бежным повторным считываниям одного и того же числа, вероятность которых возрастает с уменьшением диапазона, что ухудшает корреляционные характеристики последовательности чисел, прк имвемой потребителем. Выше было указано на послепствия ухупшения корреляционных характеристик потока случайных чисел, используем..о; пля решения тех или иных задач. Вследствие этого можно утверждать, что известное устройство обладает в целом невысоким быстродействием, так как уменьшая пиапазон генерируемых случайных чисел от максимального по требуемого значения, во столько же рвз уменьшают быстродействие устройства, а твк же то, что корреляционные свойст5 9359 ва потока чисел, принимаемого потребитежм, недостаточно высокие и ухудшаются с уменьшением диапазона генерируемых чисел.

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

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

И-НЕ соединен со вторым входом элемента И, тактовый вход триггера соединен с выходом элемента И, единичный вход три гера соединен с первым входом элемента

И-НЕ, с выходом блока сравнения, нуле- 46 вой вход триггера является вхоцом генератора, а выход триггера соединен со вто рым входом элемента И-ИЕ и является вторым выходом генератора.

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

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

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

Устройство содержит датчик случайных чисел 1, регистр копа 2, шифратор 3, блок элементов И 4, блок сравнения 5, регистр памяти 6, блок управления 7.Bb ход датчика случайных чисел 1. соединен с первым входом блока элементов И:4, выход регистра кода 2 соединен со входом шифратора 3 и вторым входом блока сравнения 5, выход блока элементов

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

В предлагаемом устройстве реазизуется принцип отбора случайных чисел с автоматическим уменьшением разрядности датчика с,пучайных чисел при уменьшении щгапазона генерируемых чисел. Устройство работает в двоичной системе счисления, разряцность блоков (1-6) оаинакова и равна и.

935953

Блок управления содержит генератор тактовых импульсов 8, элемент И9, элемент И-НЕ 10, триггер 11 . Выход генератора 8 соединен с первым входом эле« мента И9, выход которого соединен с первым входом триггера 10 и является первым выходом блока управления, а второй вход соединен с выходом элемента

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

10 и является выходом 2 (готовность) блока управления.

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

Вход первого разряда шифратора соединен непосредственно с выходом. Если в старших разрядах поступающего на вход числа нули, на выходе шифратора в этих раз-ЗО рядах тоже нули, на всех остальных младших выходах шифратора„начиная с разряда, на который поступает первая единица входного кода, находятся единицы.

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

Датчик случайных чисел 1 формирует случайные числа с равномерным распредеИ

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

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

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

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

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

При поступлении на вход триггера 11 сигнала запроса- триггер 11 устанавливается в нулевое состояние, при этом на выходе элемента И-НЕ 10 сигнал логической единицы, разрешающий прохождение импульсов генератора 8 через элемент

935953 10 н

И 9 на выход блока управления. При по- бора меньше зависит в предлагаемом устступлении сигнала логической единицы с ройстве от А, чем в известном. выхода схемы сравнения 5 триггер 11 ус- Время формирования одного выходного танавливается сжцующим тактовым им- числа включает случайное количество так пульсом в единичное состояние — на выхо > тов отбора. Математическое ожидание де блока управления присутствует сигнал времени формирования выражается через готовности. Если сждующий сигнал логи- вероятнгсть отбора (Р ) соотношением ческой единицы с выхода схемы сравнения

5, который говорит, что на выходе блока ФОР> Г8Н,, От5 отв элементов И 4 находится новое число ме»- 0 гце AT ген - период следования импульньшее либо равное границе диапазона, по- сов синхронизации датчика случайных ступает в блок управления раньше, чем чисел; М (%gape минимально и равно поступает повторный сигал запроса, íà ЬТг н при Р<гг =1, при уменьшении выходе элемента И-НЕ 10 вырабатываех Ротб — увеличивается. ся уровень логической единицы, запреща- > Таким образом, предлагаемое устройюший прохождение тактовых импульсов че- ство обладает по сравнению с известным рез элемент И9 на выход блока управле- более высоким быстродействием, обусловния, а следовательно, и синхронизацию ленным более высокой вероятностью отдатчика случайных чисел 1 и регистра 6. бора случайных чисел, а, также сокраше-

При этом и в регистре 6 и на выхоце бло-20 нием времени остановок устройства между ка 4 находятся случайные числа, попаца- моментами времени окончания формироваюшие в диапазон 0-А. При поступлении ния чисел и их потребления; меньшей засигнала запроса триггер 11 устанавлива- висимостью скорости формирования чисел ется в нулевое состояние, при этом по от значения границы диапазонар возможслецующему тактовому импульсу число с 2> постыл синхронного с формированием слувыхода блока 4 записывается в регистр чайных чисел их. потребления, что исклювыхода 5 и вырабатывается сигнал готор чает повторные считывания одних и тех насти, устройство начинает поиск csregy- же чисел, и следовательно, корреляцию юшего числа, попадающего в диапазон фор- выходного патока. ми роваии я. 30

Р

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

Если А=2" -1, где 1=0,4,...,И-4, все полученные на выходе блока коньюнкторов случайные числа меньше либо равны А,, вероятность отбора равна единице, ско»-. рость работы устройства максимальна и

15 равна скорости работы датчика случайных чисел 1. Наименьшее быстродействие уст ройства получаем при А=2. При этом количество чисел на выходе блока коньюнкторов, меньших либо равных А, равно 2 +1, больших — 2" -l, вероятность отб ра при

Ж реннамернам реанрененении раин=(2 о1)/2 =

=0,5+2<" "У. Таким образом, вероятность отбора случайных чисел в предлагаемом устройстве во всем диапазона изменения н.

А не меньше 0,5, устройства дает выигрыш в быстродействии по сравнению с известным при А< А /2, тем более значительный, чем меньше A. Вероятность ow

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

1. Генератор случайных последовательностей чисел, содержшций первичный датчик случайных чисел, регистр кода, блок эжментов И, первый Bxog, которого соединен с выходом первичного цатчика слу.чайных чисел, блок сравнения, первый вход которого соединен с выходом блока эжментов И, о т л и ч а ю ш и и с я тем, что, с целью повышения быстродействия генератора, он содержит блок управления, реестр памяти и шифратор, вход которого обьедннен со вторым входом блока сравнения и подключен к выходу регистра кода, а выход шифратора соединен со вторым входом блока элементов И, выход которого соединен с первым входом регистра памяти и с вторым вхоцом блока сравнения, выход которого соединен с вторым входом регистра памяти, выход кото- рого является первым выходом генератора, при этом блок управления содержит гена ратор тактовых импульсов, триггер, элемент И-НЕ:,элемент И, первый вход которого соедийен с выходом генератора тактовых импульсов, а выход элемента И со единен со входом первичного датчика слу

11 935953 12 чайных чисел и с третьим входом речист=- ды каждого элемента ИЛИ соединены с ра памяти, выход элемента И-HE соединен выходами предыдуших старших разрядов со вторым входом элемента И, тактовый шифратора соответственно, а вторые вховход триггера соединен с выходом эле- цы элементов ИЛИ являются входом шифмента И, еа ничный вход триггера соеди- S ратора. нен с первым входом элемента И-HE и. с выходом блока сравнения, нулевой вход Источники информации, триггера является входом генератора, а принятые во внимание при экспертизе выход триггера соединен с вторым входом 1. Авторское свидетельство СССР элемента И-НЕ и является вторым выхс- о М 4882 12, кл. 6 06 F 15/20, 1973. дом генератора. 2. Авторское свидетельство СССР

2Генератор по н, 1, о т л и ч а ю - ¹ 398940, кл. 0 06 F 1/02, 1972. шийся тем, что шифратор содержит 3,. Авторское свидетельство СССР группу элементов ИЛИ, выходы которых № 387353, кл. G 06 Р 1 02, 1971 являются выходом шифратора, первые вхо- (прототип).

Фи2.f

935953

2" 2

Pui. Я

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

Редактор П. Повхан Техред К.Мыцьо Корректор И. Муска

Заказ 4213/52 Тираж 731 Подписи ое

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП Патент, r. Ужгород, ул. Проектная, 4