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

,(7 ) Заявитель Минский радиотехнический инстит 4) ГЕНЕ РАТОР СЛУЧАЙНЫ ЧИСЕЛсел, последовательностей. Их характерис- тики в конечноьм счете и определяют возможность имитатора, следовательно и модели, а далее и эффективность решения .задачи. Например, наличие корреляционных связей в потоке случайных чисел требует значительного увеличения обьема выборки для достижения одинаковой достоверности результатов по сравнению с использованием некоррелированного потока при решении задач методами Мрите-Карло. Наличие корреляционных связей делает подчас невозможным получение достоверного результата в решении задач исследования сложных систем методами имитационного морелирования, Интенсивностью генераторов случаййых величин определяетсяя пригодность модели для решения зад ч в реальном масштабе времени.Известно устройство для генерирования случайных чисел, содержащее генератор равномерно-распределенных случайных чисел, блок сравнения, регистр маски, регистр числа, блок памяти, регистр адг.са,а Изобретение относится к вычислительной технике и предназначено для генерации потока равномерно-распределительных чисел в заданном диапазоне . Устройство целесообразно применять при решении5 задач методом имитационного моделирования, исследования и оптимизации структурночгложных систем, в качестве датчика случайных чисел при решении задач методами статистических испытаний, В частнсс-1 О ти имитационные модели сложных систем предполагают наличие аппаратуры, отвечающей различным, в том числе противоречивым требованиям. Это большое число каналов имитации, высокая интенсивность15 потоков выходных случайных величин, отсутствие корреляционных зависимостей между каналами и в потоках каждого канала, возможность программного управления, а при имитации быстро меняющейго ся обстановки - простота алгоритмов расчета настроечных параметров. Ядром любого имитатора случайных процессов являются генераторы случайных величин, чиССЛЕЦОВАТЕЛЬНОСТЕИблок управления. Устройство позволяет формировать последовательности случайныхчисел с произвольным (заданным) законамраспределения и реализует метод условныхверщФцлстей 11, Недостатком известного устройства является то, что изменениедиапазона генерируемых чисел без изменения при этом закона распределения требует изменения настроечных параметров,расчет которых достаточно трудоемок; кро-"ме того, формирование одного случайногочисла требует И вычислительных операций,где Ь- разрядность числа, т.е. с ростомразрядности формируемых чисел увеличиваются временные затраты на генерируемое число; недостатком является такжеотносительно сложная аппаратура реализация, так как цля получения высокогобыстродействия, сравнимого,с граничнойрабочей частотой элементов, требуетсябыстродействующая память,Известно устройство для генерированияслучайных чисел, содержащее датчик случайных чисел, блок схем "Запрет", дешифратор, набор схем И, ИЛИ, НЕ, счетчикс пересчетом А, блок логических схем.Принцип работьг устройства основан насравнении некоторого случайного числа Р,с границей диапазона А (пиапазон (О;А).Если йА то блок схем "Запрет" за- здкрыт, на выход устройства прохопит состояние счетчика, палее к содержимомусчетчика прибавляется единица. Если число Р; А, то на выход устройства проходит В, т,е, интенсивность появлениячисел на выходе псстоянна . Чем меньшеА, тем большей длины последовательностисостояний счетчика прохопят на выходустройства, тем больше значения автокорреляционной функции выходного потока прималых аргументах 2.Недостатком этого устройства является коррелированность выходной последовательности, причем значение актокорреляционной функции увеличивается прямо про-порционально уменьшению диапазона генерации, Достижение постоянной интенсивности выходного потока случайных чисел получено за счет ухудшения их качества.Наиболее близким по технической сущ-ности к предлагаемому является устройство для статистического моделирования, содержащее датчик случайных чисел, генератор тактовых импульсов, первый блок коньюнкторов (вентилей), первый вход кото-." рого соединен с выходом датчика случайных чиселвторой - с выхопом генератора тактовых импульсов, регистр второй блок коньюнкторов (вентилей), первый вход которого соединен с выходом генератора тактовых импульсов, второй вход - с выходом регистра, схему сравнения, вход которой соединен с выходом первого блока коньюнкторов, второй - с выхопом второго блока коньонкторов, блок выходных вентилей, первый вход которого подключен к выходу первого блока коньюнкторов, второй вход - к выходу схемы сравнения, выход заведен на выход устройства. Устройство работает по принципу отбора случайных чисел. В регистре хранится число, опрепеляющее вепкнюю границу диапазона генерирования. Числа, большие этой границы, отбрасываются, меньшие проходят на выход устройства. Таким образом, в случае равномерного закона распрецеления интенсивность появления выходных чисел обратно пропорциональна величине пиапазона этих чисел.Недостатком устройства является то, что снижение интенсивности выходных случайных чисел пропорционально уменьшению диапазона их генерирования, что, во-первых, затрудняет управление параметрии формируемых случайных величин при использовании устройства в имитационной аппаратуре, т.е. изменение диапазона существования формируемой случайной величины связано с изменением интенсивности ее появления, во-вторых, ухудшает эксплуатационные качества устройства при использовании его в качестве датчика случайных чисел для ЭВМ ввиду увеличения времени на решение задачи мет одами статистических испытаний в случае потребности в числах меньших, по сравнению с максимальным, диапазонов кроме тога, асинхронная работа системы генератор-потребитель ведет к неиз бежным повторным считываниям одного и того же числа, вероятность которых возрастает с уменьшением диапазона, что ухудшает корреляционные характеристики последовательности чисел, пркимаемой потребителем, Выше было указано на последствия ухудшения корреляционных характеристик потока случайных чисел, используемо; пля решения тех или иных задач. Вследствие этого можно утверждать, что известное устройство обладает в целом невысоким быстродействием, так как уменьшая диапазон генерируемых случайных чисел от максимального по требуемого значения, во столько же раз уменьшают быстродействие устройства, а так же то, что корреляционные свойст5 9359 ва потока чисел, принимаемого потребителем, недостаточно высокие и ухудшаются с уменьшением диапазона генерируемых чисел.елью изобретения является повышение быстродействия генератора, введение режима синхронной работы генератора с потребителем чисел случайной последовательностиДля достижения поставленной цели в 19 известный генератор случайной последовательности чисел, содержаший первичный датчик случайных чисел, регистр кода, блок элементов И, первый вход которого соединен с выхоцом первичного патчнка случай- ных чисел, блок сравнения, первый вход которого соединен с выходом блока элементов И, введены блок управления, регистр памяти и шифратор, вход которого обьепинен со вторым входом блока срав пения и подключен к выходу ре.гистра кода, а выход шифратора соединен со вторымвходом блока элементов И, выход которого соединен с первым входом регистра памяти и со вторым входом блока сравнения, выход 25 которого соединен со вторым входом регистра памяти, выхоп которого является выхоцом генератора, прн этом блок управления содержит генератор тактовых импу. льсов, триггер,элементИ-НЕ и элемент И, з 9 первый вход которого соединен с выходом генератора тактовых импульсов, а выход элемента И соединен со входом первичного датчика случайных чисел и с третьим вхоцом регистра памяти, выход элемента И-НЕ соединен со вторым входом элемента И, тактовый вход триггера соединен с выходом элемента И, единичный вход триР- гера соединен с первым входом элемента И-НЕ, с выходом блока сравнения, нуле вой вход триггера является вхоцом генератора, а выход триггера соепинен со вто рым входом элемента И-ИЕ и является вторым выхопом генератора.Кроме того, шифратор содержит группу 4 элементов ИЛИ, выходы которых являются выходами шифратора, первые вхоцы каждого элемента ИЛИ соединены с выходами предыдуших старших разрядов шифратора соответственно, а вторые входы элемен тов ИЛИ являются входом шифратора. 53 Введение новых блоков и связей обус лавливает появление слепукяцего положительного эффекта: увеличение быстродействия вследствие повышения вероятности И отбора случайных чисел, попадающих в границы диапазона генерирования за счет введения шифратора, вход которого соединен с выходом регистра кода диапазгка, а выход соепинен с первым входом блока коньюнкторов;:вероятность отбора в предлагаемом устройстве не менее 0,5, в известном вероятность отбора при небольшихзначениях границы диапазона значительноменьше 0,5 (фиг, 4) и равна АГА пс,где А-граница диапазона, А сг- максимально возможное значение границы диапазона; синхронный режим работы с потребителем случайных чисел за счет введения блока управления, первый вход которого соединен с выходом схемы сравнения, первый выход соединен с выходомдатчика случайных чисел и вторым выходом регистра выхода, второй вход блокауправления является выходом запуска ге-нератора случайных посждовательностей,а второй выход является указателем готовности устройства.На фиг. 1 представлена структурнаясхема генератора случайных псследовательностей; на фиг, 2 - схема шифратора;на фиг. 3 - график зависимости Рот (А), пля восьмиразрядного генератора (1 фпля предлагаемого генератора ф 2 ф цляпрототипа),Устройство содержит датчик случайных чисел 1, регистр кода 2, шифратор 3, блок элементов И 4, блок сравнения 5, регистр памяти 6, блок управления 7,Вьюход датчика случайных чисел 1. соединен с первым входом блока элементов И:4, выход регистра кода 2 соединен со входом шифратора 3 и вторым входом блока сравнения 5, выход блока элементов 4 соединен с первым входом регистра памяти и с первым входом блока сравнения 5, выход шифратора 3 соединен со вторым входом блока элементов И 4, вы- ход блока сравнения 5 соединен с вторым входом регистра памяти 6 и с первым входом блока управления 7, первый выход блока управления 7 соединен со входом датчика случайных чисел 1 и третьим входом регистра памяти 6, второй вход блока управления 7 является входом запуска генератора случайных последовательностей, а второй выход является указателем готовности устройства, выход вьжорного регистра 6 является выходом устройства.В предлагаемом устройстве реазизуется принцип отбора случайных чисел с автоматическим уменьшением разрядности датчика случайных чисел при уменьшении шгапазона генерируемых чисел. Устройство работает в двоичной системе счисления, разря цность блоков ( 1-6) оаинакова и равна д.Блок управления содержит генератор тактовых импульсов 8, элемент И 9, элемент И-НЕ 10, триггер 11. Выход генератора 8 соединен с первым входом эле мента И 9, выход которого соединен с первым входом триггера 10 и является первым выходом блока управления, а второй вход соединен с выхопом элемента И-НЕ 10, соединенные между собой первый и второй входы элемента И-НЕ 10 и 1 О триггера 11 соответственно, являются первым входом блока управления, вторым входом блока управления является третий рход триггера 11, выход которого соединен со вторым входом элемента И-НЕ 10 и является выхопом 2 (готовность) блока управления.Функциональная схема одной из возможных реализаций шифратора, 3 иредставлена на фиг, 3, Шифратор сопержит И20 пвуххоповьх элементов ИЛИ, выходы которых являются разрядными выходами шифратора, первые входы которых (элементов ИЛИ) соединены с выходами предыдущих разрядов шифратора, а вторые входы являются разрядными входами шифратора, Вход первого разряда шифратора соединен непосредственно с выходом. Если в старших разрядах поступающего на вход числа нули, на выходе шифратора в этих раз Зо рядах тоже нули, на всех остальных младших выходах шифратораначиная с разряда, на который поступает первая единица входного кода, находятся единицы.35Устройство функционирует следующим образом.Датчик случайных чисел 1 формирует случайные числа с равномерным распреде.Илением в диапазоне 0 - 2, С выхода 1 4 О блока управления 7 на вход датчика случайных чисел 1 поступают тактовые импульсы, по каждому из которых датчик случайных чисел формирует одно новое случайное число, которое через блок эле ментов И 4 в котором производится его предварительное преобразование в соответствии с кодом выхода шифратора 3, поступает на второй вход схемы сравнения, на первый вход которой поступает из ре 50 гистра 2 код границы диапазона А, Если очередное поступающее на вхоп схемы сравнения 5 случайное число меньше либо равно коду границы диапазона, с выхода схемы сравнения на входы регистра 6 и35 блока управления 7 поступает сигнал логической единицы, разрешающей запись по следующему импульсу с первого выхода блока управления 7 случайного числа в регистр 6. Одновременно на втором выхопеблока управления устанавливается сигналготоиосттг, указывающий об окончании формирования нового случайного числа. Если очередное случайное число больше кодаграницы диапазона, то сигналом логического нуля с выхопа схемы сражения 5запись в регистр 6 и установка сигналаготовности запрещаются, устройство перехопит к анализу следующего случайногочисла. В соответствии с кодом границыдиапазона шифратора 3 формирует так называемый код маски, представляющий собой последовательность нулей в старшихразрядах до первого значения числа разряда в коде диапазона (до первого разряда равного единице) и единиц в остальных младших разрядах. Разрядные выходышифратора соединены с первыми входамиэлементов И блока 4, ковторым входамкоторых подсоединены разрядные выходыдатчика случайных чисел, при этом происходит поразрядное логическое умножениекода маски и случайных чисел, в результате чего на выходе блока коньюнкторовавтоматически получаются разряпные чиола, количество значащих разрядов которыхравно количеству значащих цифр в кодедиапазона,Во избежание повторных считыванийодного и тога же числа считывание устройством-потребителем случайных чиселосуществляется только при наличии сигнала готовности на втором выходе блокауправления 7. При этом на второй входблока управления от устройства-потребителя должен поступить сигнал запроса, который говорит о том, что случайное число считано и можно формировать новое,сигнал готовности отбрасывается блокомуправления. Простейший вариант блока управлениясодер жит генератор тактовых импульсов,выход которого является выходом 1 блока управления, и триггер., выход которогоявляется выходом готовности. При поступлении сигнала запроса триггер устанавливается в нулевое состояние, при поступлении сигнала с выхода схемы сравненияв единичное.Блок управления функционирует следующим образом,При поступлении на вход триггера 11сигнала запроса триггер 11 устанавливается в нулевое ссстояние, при этом навыходе элемента И-НЕ 10 сигнал логической единицы, разрешающий прохождениеимпульсов генератора 8 через элемент11 935953 12 чайных чисел и с третьим входом речист= ды каждого элемента ИЛИ соединены с ра памяти, выход элемента И-НЕ соединен выходами предыдуших старших разрядов со вторым входом элемента И, тактовый шифратора соответственно, а вторые вховхоц триггера соединен с выходом эле- ды элементов ИЛИ являются входом щифмента И, еаюничный вход триггера соеди ратора.нен с первым входом элемента И-НЕ и. свыходом блока сравнения, нулевой вход Источники информации, триггера является входом генератора, а принятые во внимание при экспертизе выход триггера соединен с вторым входом 1. Авторское свидетельство СССР элемента И-НЕ и является вторым выхо- О488212, кл. 6 06 Г 15/20, 1973. дом генератора. 2. Авторское свидетельство СССР2.Генератор по и, 1, о т л и ч а ю -398940, кл, 0 06 Р 1/02, 1972. щ и й с я тем, что шифратор содержит 3 Авторское свидетельство СССР группу элементов ИЛИ, выходы которых387353, кл. 6 06 Р 1/02, 1971 являются выходом шифратора, первые вхо- (прототип).935953 р 1,остави тельТехред К,М Кара актор Корректор ОВ 7 2 ТиражГосударственн елам изобретени Москва, Ж 35 филиал ППП Патент, г, Ужгород, ул. Проектная,Заказ 4213/5 31 Подписи ВНИИ ПИ го комитета СССР по д й и открытий 113035, , Раушская набд. 4/5