Стохастический генератор

Дата опубликования описания 08.05.8 72) Авторы изобретения. А. Баканович, С. Ф. Костюк, М. А. Орпо и А. Г. Якубенко Минский радиотехнический институт 7) Заявите ЧЕСКИЙ ГЕНЕРАТОР впяются, такать тми запя 1 е дназМаркодат чидевойУ, вы и сумИзобретение относится к области вычислительной техники, предназначено дп модепирования потоков случайных чисел с требуемыми законами распределения, Марковских процессов и может быть испопьзовано при построении вероятностных вычислительных машин, а также в. качестве специализированного стохастического блока, подключаемого к вычислительным машинам общего назначения.Известны устройства дпя формирования потоков случайных чисел с требуемыми вероятностными характеристиками.Одно из известных устройств позволяет формировать потоки случайных чисел с требуемыми законами распределения по методу обратных функций. Устройство содержит генератор равномерно распредепенных чисел, схему сравнения, блок памяти, генератор тактов, специализированный дешифратор, регистр формирования спучайноо числа, входные и выходные вентипи 1Известно устройство 2 , позвопяющее формировать спучайные числа с требуемыми законами распределения по ме тоду условных вероятностей. Устройство содержит многоканальный генератор спучайных импульсных токов, схемы И, схему ИЛИ, вероятностный вентиль, регистр формирования случайного числа, схемы И регистра, устройство формирования адрес памяти и генератор-распределитель тактовых импульсов,Недостатками этих устройств я их сложность и узкая специапизаци как устройство позволяет формиров только. случайные числа с требуем конами распределения, но не позво формировать бопее сложные случай процессы, например М арковские.Известно также устройство, пре наченное дпя формирования цепей ва и содержащее бпок управпения, случайных чисел, элементы И, копь счетчик, апементы ИЛИ, регистр, ходной регистр, выходные вентипи матор 31, Это устройство спожнсвязностью цепей Маркова и числом ихсостояний.В то время, как для различных задачтребуется моделировать разное количествозаконов распределений с разной разрядностью формируемых случайных чисел, цепи Маркова различной связности с различным числом состояний.Кроме того, техническая реализацияустройства сложна, так как требуется блокОуправления, вырабатывающий последовательность сигналов, обеспечивающих функционирование устройства.Белью изобретения является повышение:точности воспроизведения законов распределения; расширение функциональных воэможностей (обеспечение возможности программного управлений, варьирования припостоянном объеме памяти числом моделируемых законов и разрядностью генериру- оемых случайных чисел, связностью марковской пепи и числом ее состояний) иупрощение технической реализации.Для достижения поставленной целипредложенный генератор содержит генератор тактовых импульсов, регистр сдвига,три элемента И, два блока элементов НЕблок элементов И, коммутатор и элементНЕ. Выход генератора тактовых импульсовсоединен с первыми входами регистрасдвига, первого и второго элементов И.Второй вход регистра сдвига соединен совторым входом регистра адреса и с выходом третьего элемента И, первым входомрегистра адреса и с выходом третьегоэлемента И, первый вход которого является входом "Пуск" генератора, а второйвход соединен со входом элемента НЕ ивторым выходом регистра адреса. Выходэлемента НЕ соединен со вторым входом40второго элемента И, выход которого соединен с третьим входом регистра адреса. Выход регистра сдвига соединен совторым входом первого элемента И, выход которого соединен со входом генера 45тора равномерно распределенных случайных чисел. Вход первого блока элементовНЕ соединен со вторым выходом генератора равномерно распределенных случай 50,ных чисел, а выход - со входом блокаэлементов И, выход которого соединен совходом шифратора. Выход последнего соединен с первым входом второго блокаэлементов НЕ, второй вход которого сое 55динен с третьим выходом генератора равномерно распределенных случайных чисел,Выход второго блока элементов НЕ соединен с первым входом коммутатора, вто. рой вход которого соединен с четвертымвыходом генератора ревномерно распрьделенных случайных чисел, а выход ком.мутатора - с третьим входом блока сравнения.Это позволяет повысить точность воспроизведения законов за счет преобразования исходных разномерно распределенных чисел. Преобразованное число состоит из двух частей, первая (старшая)часть содержит Р разрядов, вторая (младшая) - тразрядов, Первый разряд старшей части равен первому разряду исходного числа, остальные разряды старшейчасти указывают; сколько подряд разрядов исходного числа, начиная со второго,приняло значение, равное первому, Причем,если первый разряд равен единице, эточислоберется в прямом коде, в противном случае - в инверсном. Если в исходном числе количество старшпх разрядов,принявших подряд равное значение, больше либо равно 2 Р (включая старшийразряд), в старшую часть необразованного числа подаются в зависимости от значения первого разряда все единицы либонули, а в младшую часть - гн разрядовисходного числа, расположенных послеР 2 старших разрядов. Если количествостарших разрядов, принявших подряд равное значение меньше 2 Р , в младшуючасть преобразованного числа подаютсяИ разрядов исходного числа, расположен,ные после первого разряда, принявшегонеравное значение. Первый принявший не-.равное значение разряд в младшую частьпреобразованного числа не включается,поскольку в данном случае его значениевсегда противоположно значению первогоразряда и, следовательно, его введение недает дополнительной информации,В такой же форме представлены и коды вероятностей, хранимые в памяти устройства, Сравнение случайных чисел и кодов вероятностей, представленных в описанной форме, производится с помощьюизвестных схем сравнения двоичных чисел. При этом увеличение разрядностисравниваемых кодов на рпозволяетуменьшить максимальную погрешность задания вероятностей, в кодах которых приих двоичном представлении К старшихразрядов подряд, начиная со второго, при"няло значение, равное первому, в 2 КК+4раз при К 2 и в 2 Рраз,прикЪ2 Р " (к=0,1,2 т , где й 1 исходнаяразрядность сравниваемых кодов), В про-тотипе указанное повышение точности пот77329ребоиапо бь 1 введения дополнительно 2разрядо и.Преобразование исходных равномернораспредепенньх чисел осушествпяетсяпервым блоком эпементов НЕ, бпоком эпе ментов И, шифратором, вторым блокомэлементов НЕ и коммутатором. Разрядность генератора равномерно вспредепенных спучайных чисел равна 2 + гпТак как преобразуются случайные равномерно распределенные числа, каждый изразрядов которых явпяется независимым,мпадшая часть преобразованного числаявпяется случайным равномерно распредепенным числом, не зависящим от зна 15чения старшей части. Поэтому дпя формирования этой части числа можно взять(как это депается в устройстве) тт разрядов исходного случайного числа, а формирование старшей Части производить по 20ростальным 2 разрядам. Дпя попучения максимальной точности воспроизведения при постоянной разрядности кодоввероятностей спедует выбирать дпя каждого закона минимально необходимоезначение Р, Коммутатор обеспечиваетвозможность варьирования разрядностьюпервой и второй части преобразованногочисла,Повышение точности воспроизведениязаконов осуществляется методологи чески.При методе обратных функций дпяформирования одного выходного случайного числа требуется одно исходное случайное число, Это и опредепяет его достоин-З 5ство, так как получение высокостабипьных некореппированных случайных чиселс помощью генераторов случайных чисел,использующих в качестве исходного неко 40торый случайный физический процесс, работающих на достаточно высоких частотах,требует больших затрат оборудования.Известен метод условных вероятностейобпадаюший по сравнению с методом об 45ратных функций, при равной разрядностиисходных случайных чисел, более высокойточностью воспроизведения определенноюкласса законов, этот метод требует большего расхода исходных спучайных чисел(одно исходное случайное число на форми 50рование одного разряда выходного числа), Это приводит либо к уменьшениебыстродействия, по сравнению с первымметодом, пибо к допопнитепьным затратам55оборудования.Известен метод, являющийся комбинашией двух выше указанных. Сущность егосостоит. в следующем: генерируется первое исходное число, по которому определяется, в какую половину, пибо четверть,либо восьмую часть и т,д. области существования моделируемого закона попадает .значение формируемого случайногочиспа, т,е, формируется один либо два,либо три и т,д. разряда номера интервапа квантования (выходного числа), генерируется второе исходное случайное чиспо и уже по условному закону распредепения на найденном интервале формируется спедуюшая группа разрядов номераинтервапа квантования (выходного числа)и т,д. Копичество разрядов, формируемыхпо одному исходному спучайному числу,может быть любым. Методы обратныхфункций и ус повных вероятностей являются частными случаями этого метода, когда по одному исходному спучайному числуформируются все разряды выходного чиспа, и когда один разряд формируется поодному числу,Данное устройство позволяет реапиэовать три этих метода, Они отличаютсяодин от другого методикой расчета кодов,хранимых в памяти, и программой опросагенератора исходных случайных чисел,Требуемая программа опроса генератораравномерно распредепенных случайных чисеп формируется с помощью регистрасдвига и первой схемы И. Возможностьреализации этих трех методов позволяетвыбирать метод, обеспечивающий наибопьшую точность, и выбирать между точностью воспроизведения и быстродействием,Расширение функциональных возможностей и упрощение устройства достигается тем, что дпя управления функционированием устройства используется выход старшего разряда регистра адреса, который представляет собой единый, не разделенный (как в прототипе) на две части регистр сдвига. Перед началом цикпа формирования случайного числа в регистр адреса заносится единица, положение которой относительно старшего разряда опредепяет разрядность формируемого числа, и код номера требуемого закона. На каждом такте работы устройства содержимое регистра сдвигается, а в младшие разряды заносится двоичный код, поступающий из блока сравнения. Это обеспечивает формирование адреса выбора следующих кодов из блока памяти. Количество разрядов, на которое сдвигается содержимое регистра адреса, и разрядность поступающего из блока сравнения73294 кода равны.О, где а- основание логарифма перебора, Сдвиг единицы в старший разряд регистра адреса означает окончание цикла генерации. При атом останавливается процесс формирования случайного 5 числа,и разрешаегся повторное занесение кодов исходного состояния в регистр адреса и в сдвиговый регистр формирования программы, опроса генератора равномерно распределенных случайных чисел.Структурная схема устройства приведена на чертеже.Устройство содержит генератор 1 тактовых импульсов, регистр 2 сдвига, первый алемент 3 И, генератор 4 равномерно распределенных случайных чисел, первый блок 5 алементов НЕ, блок 6 алев ментов И, шифратор 7, второй блок 8 элементов НЕ, коммутатор 9, элемент НЕ 10, второй 11 и третий 12 элементы И, 20 регистр 13 адреса, блок 14 памяти и блок 15 сравнения,Выход генератора 1 соединен с первым входом регистра 2, вторым входом эле 25 мента 3 и первым входом элемента 11. Второй вход регистра 2 соединен с выходом элемента 12, а выход - с первым входом элемента Э, выход которого соединен со входом генератора 4. ПервыйЗО выход генератора 4 соединен с первым входом блока 8 элементов НЕ, второй вы ход - со входом блока 5 элементов НЕ, третий выход - со вторым входом коммутатора, а четвертый выход - со вто- з 5 рым входом блока 15 сравнения, Выход блока 5 элементов НЕ соединен со входом блока 6 элементов И, выход которого соединен со входом шифратора 7, Выход шифратора 7 соединен со вторым вх40 дом блока 8 элементов НЕ, выход которого соединен с первым входом коммутатора 9. Выход коммутатора 9 соединен с первым входом блока 15 сравнения, Вход алемента НЕ 10 соединен со вто 45 рым выходом регистра 13 адреса, а выход - со вчорым входом элемента 11 И, выход которого соединен со вторым входом регистра 13 ад 50реса, Первый вход элемента 12 И соединен со вторым выходом регистра 13 адреса, а выход - со вторым входом регистра 2 сдвига и третьим входом регистрра 13 адреса. Первый вход регистра 1355 адреса соединен с выходом блока 15сравнения, а выход - со входом блока14 памяти, выход которого соединен с .ч;ретьим входом блока 15 сравнения. 7 1 ОюРассмотрим работу устройства при реализации логарифмического перебора по основанию 2. В атом случае блок сравнения содержит одну схему сравнения, регистр 13 обеспечивает сдвиг на один разряд, Количество разрядов регистра 13 равно й . Количество ячеек блока памяти равно 2 . Рассмотрим случай моЯделирования одного дискретного распределения с максимальным для обьема памяти 2 - значением и =2, т,е. случай генерирования Е разрядных случайных двоичных чисел.Устройство работает следующим образом.В исходном состоянии в ст,щшем разряде регистра 13 - единица, На первый вход элемента 12 поступает разрешающий потенциал, на второй вход элемента 11 с выхода алемента НЕ 1 О - запрещающий потенциал.Цикл генерации начинается при поступлении на второи вход элемента 12 импульса запроса. По входам параллельной записи в регистр 2 заносится код, задающий требуемую программу опроса генератора 4 в младший разряд регистра 13 заносится единице, во все остальные разряды- нули (т.е. начальный адрес). По атому адресу из блока 14 памяти считывается код Р, определяющий вероятность попадания формируемой случайной величины в первую либо вторую половину области ее существования. В блоке сравнения считан ный код вероятности сравнивается со слу чайным числом. Если случайное число мень ше кода вероятности, на выходе блока сравнения - нулевой потенциал, Это означает, что первый разряд формируемого случайного числа принял значение, равное нулю, В противном случае на выходе блока сравнения - единичный потенциал первый разряд формируемого случайного числа принял значение, равное единице).При поступлении на командный вход сдвига регистра 13 импульса генератора 1 единица из младшего разряда регистра сдвигается в следующий разряд, а в младший разряд по входу последовательной записи заносится результа операции сравнения.По сформированному в регистре 13 новому адресу из блока памяти считывао ется следующий код вероятности Ропределяющий вероятность попадания формируемой случайной величины в первую либо вторую четверть области существования, если сформированный первый разряд приТадлица 11 7329 нял значение, равное нулю, либо код ве роятности Р, определяющий вероятность попадания в третью либо четвертую чет. верть области существования, если сформированный первый разряд принял значение равное единице. Производится сравнение считанного кода и случайного числа, содержимое регистра 13 сдвигаетсяи в младший разряд записывается результат операции сравнения, 10Цикл сравнений длится 6 тактов. После 6 -1-го сдвига единица из младшего разряда регистра 13 сдвигается в старший, В остальных разрядах регистра находится Е - 1 разрядов сформированного 15 случайного числа, младщий разряд находится на выходе схемы сравнения. Сдвиг единицы в старший разряд регистра 13 говорит об окончании цикла генерации. Поступление импульсов генератора 1 че рез элемент 11 на командный вход сдви,га регистра 13 запрещается низким потенциалом с выхода элемента НЕ 10. Разрешается поступление через элемент 12 импульса запроса на командные входы 25 параллельной записи регистров 2 и 13 (разрешается повторный цикл генерации),Одновременно со сдвигом на каждом такте содержимого регистра 13 сдвигается содержимое регистра 2. На элементе 30 3 производится стробирование импульсами сдвига состояния старшего разряда регистра 2. Это обеспсчивает получение требуемой программы опроса генератора 4.Преобразование равномерно распреде ленных случайных чисел осуществляется следующим образом. 2 Р " -разрядов 47 12генератора 4 подсоединены ко входам блока 5 элементов НЕ, Старп 1 ий разряд генератора 4 управляет блоками 5 и 7 элементов НЕ При равенстве значения старшего разряда единице через блок 5 передается прямой код, в противном случае - инверсный. В блоке 6 элементов И производится анализ числа разрядов, принявших значение, равное единице следовательно принявших значение, равное старшему, и формируется унитарный код этого числа, Шифратор 7 преобразует унитарный код в двоичный. При равенстве единицы старшего разряда генератора 4 этот код передается через блок 7 в прямом коде, в противном случае - в инверсном коде.С помощью коммутатора 9 путем перекоммутации разрядов с выхода блока 8 и генератора 4 задается количество разрядов Р старшей части преобразованного числа. Выходы коммутатора соединены со старшими входами схемы сравнения. Младшие разряды схемы сравнения соединены с остальными выходами генератора 4,Размещение кодов вероагностей в ячей-. ках блока памяти для описанного случая при 6 =5 показано в таблице 1. Слева в каждой клетке таблицы указывается обозначение кода вероятности, справа - адрес ячейки, Нумерация адресов памяти начинается с нуля, Нижний индекс в обозна- чении кода вероятности указывает номер такта, на котором считывается код, верхние индексы - результат, полученный на предыдуших тактах.случайных ествл цикла реса масДля покаслу чайных пения в репри гейки,ого ерации случа од тройки. Ф х чиселмиров ани аконахразРазмещение кодов вероятности при мо 50 делировании двух законов распределений четырехразрядных случайных чисел для8=5 показано в таблице 2. Второй нижний индекс в обозначении кодов вероятности указывает на номер закона к коУ 55 торому принадлежит данный код. Информация о первом законе расположена в ячейках 2,4,5, 8-9, 16-23, информация о втором законе - в ячейках 3,6,7,12-15,24-31. Запрос на генерациючисел требуемого закона осущзанесением в начале каждогорации в регистр 13 первого асива информации этого законазанного примера при генерацичисел первого закона распредегистр 13 заносится код дво732947 Тай ТайиаЮ 7 аЮлаиас занной цепи Мар следующим обгенерации цепи регистра 13 (четзаносится н пепи, в третий 1 й и второй екается код ь перехода в, и происходит числом. По имроиз водитсятра 13 с эвпизультата сравизвлекается код рядных случайных чисел происходит эачетыре такта. По окончании цикла генерации в старшем разряде регистра 13находится единица, в следующем разряде - нуль либо единица, указывающие В таблице 3 показано размещение ко 15 дов вероятности при моделировании трех законов распределения; одного закона распределения четырехразрядных случайных чисел и двух законов распределенияго траразрядных случайных чисел 8=5. Массив информации о первом законе расположен в ячейках 2,4,5,8-11,16-23, информация о втором законе - в ячейках 6-12, 13, 24-29, информация о третьем законе-, в ячейках 7,14,15,28-31. Запрос на генерацию случайных чисел требуемого закона осуществляется занесением в начале каждого цикла генерации начального адреса соответствующего массива, МладшийЗО В таблице 4 показано размещение кодов вероятностей переходов при моделировании односвязной цепи Маркова, описываемой матрицей вероятносгей переходов типа Р (1, =0,1,2,3), 6=5. Верхний4 индекс в обозначении кодов вероятностей указывает номер состояния, из которого переходит цель. Нижние индексы указывают, в какое состояние с данной вероятностью должна перейти цепь. Так, на 5 пример, РО 1 -вероятность того, что цепь перейдет в состояние с номером О либо 1, если она находиласЬ в состоянии 1,1Р - вероятность того, что цепь перейОдет в состояние О, если она находилась в состоянии 1 и при розыгрыше вероятно 5 стей на предыдущем такте определилось, что цепь должна перейти в состояние с номером О либо 1. номер моделируемого распределения, втрех остальных разрядах - три старшихразряда сформированного случайного числа, младший разряд случайного числа находится на выходе схемы сравнения. разряд сформированного случайного числа находится всегда на выходе схемы срав нения, старшие разряды - в младших разрядах регистра 13, Формирование трех- разрядных случайных чисел, происходит за три такта,В общем случае количество тактов формирования случайного числа равно его разрядности. Максимальная разрядность формируемых случайных чисел и количество моделируемых законов распределений случайных чисел требуемой разрядности определяются значением Е, т.е. разрядностью регистра 13 и объемом памяти уст- ройства При моделировании уквкова устройство работаетразом. В начале периодав младшие два раэрялавертый и пят й пр Е=5)мер начального состоянияразряд - единица, в первли. На первом такте извлопределяющий вероятнотмладшие состояния - Росравнение со случайнымпульсу с генератора 1 исдвиг содержимого региссью в младший разряд репения. Нв втором тактеРвввРагвРГРРРгв - 26:О ф-л Рй 2 У Рг - 25Щ в2-65У Рзв 60 Ргг 61 Ргг 52 Ргг 5 Р,"-54 фРю - 56 3-5 У Ргв 46 Ргв 40 Ро 50 Ри 5 15вероятности Рлибо Р, производится сравнение со случайным числом, содержимое регистра 13 сдвигается, а в его младший разряд заносится результат второго сравнения. За два такта единица из третьего, разряда регистра 13 сдвигается в первый разряд. Это говорит об окончании цикла формирования перехода, Сформированный код номера состояние пропроцесса находится в четвертом и пятом разрядах регистра 13, При запуске устройства на следующий цикл формирования перехода необходимо значение четвертого и пятого разрядов регистра 13 оставить без изменения, в третий разряд за писать единицу, а в первый и второй разряды - нули. При достаточно бопьцом значении возможно последовательное моделированиенескольких Марковский процессов и закснов распределений. При этом необходимо30обеспечить хранение необходимых текущихпредыдущих состояний Марковского процесса.Запросы на генерацию случайных чиселтребуемого распределения осуществляются З 5занесением перед цикпом генерации начапьного адреса соответствующего массива информации, При запросе на формированииперехода Марковского процесса задаетсяначапьный адрес требуемого массива в40соответствии с предыдущими состояниямиэтого процесса.Максимапьное число состояний Марковского процесса, максимальная связность процесса с необходимым чиспом состояний, количество поспедоватепьно моделируемых процессов и законов распределений с требуемыми параметрами, т.е. возможности устройства определяются значением - разрядностью регистра 13 и объемом памяти устройства.Технико-экономическая эффективность изобретения опредепяется повышением точности моделирования распределений случайных чисел Марковских процессов, рас.Гширением функционапьных возможностей; обеспечением возможности программного управления, варьирования при постоянном 16В таблице 5 показано размещение кодов вероятностей при генерировании двух связного Марковского процесса, описываемого матрицей вероятностей переходов Р 8=7. Первый верхний индекс в обозначении кодов вероятностей - 1 , второйфункционирует устройство аналогично вышеописанному случаю . Формируемые коды состояния процесса по окончанию каждого цикла формирования перехода находятся в шестом и седьмом разрядах регистра 13, При запуске на каждый новый цикл необходимо значение четвертого - седьмого. разрядов регистра 13 оставпять без изменения, в третий разряд заносить единицу, а в первый и второй.Уразряды - нули. объеме памяти числом моделируемых законов и разрядностью формируемых спуаайных чисел, связностью цепей Маркова и числом их состояний и упрощением и удешевлением устройства. формула изобретения Стохастический генератор, содержащий регистр адреса, блок памяти, вход которого.соединен с первым выходом регистра адреса, блок сравнения, первый вход которого соединен с выходом блока памяти, а выход - с первым входом регистра адреса, гененатор равномерно распределенных случайных чисел, первый выход которого соединен со вторым входом блока сравнения, о т и и ч а ю щ и й с я тем, что, с цепью повышения точности работы генератора, он содержит генератор тактовых импульсов, регистр сдвига, три эпемента И, два блока элементов НЕ, блок элементов И, коммутатор, элемент НЕ, причем выход генератора тактовых импульсов соединен с первым входом ретистра сдвига, первым входом первого эпемента И и первым входом второго эпемента И, второй вход регистра сдвига соединен со вторым входом регистра адреса и с выходом третьего элемента И, первый вход которого является входом718авномерно распределенных случайных чиел, а выход второго блока элементов НЕоединен с первым входом коммутатора,торой вход которого соединен с четверым выходом генератора равномерно расределенных случайных чисел, а выходоммутатора соединен с третьим входомпока сравнения.Исгочннки инФормации,принятые во внимание при экспертизе1. Авторское свидетельство СССРМ 378826, кл. б 06 Г 1/02, 1973.2. Авторское свидетельство СССРЬ 430368, кл. 6 06 Г 1/02, 1974.3, Авторское свидетельство СССРМо 485439, кл, 6 06 Г 1/02. 1975.4, Авторское свидетельство СССРМ": 488212, кл, 0 06 Г 15/20, 1975(прототип) . 17 73294 Пуск" генератора, а второй вход соединен р со входом элемента НЕ и вторым выходом с регистра адреса, выход элемента НЕ сое- с динен со вторым входом второго элемен- в та И, выход которого соединен с третьим 5 т входом регистра адреса, выход регистра п сдвига соединен со вторым входом перво- к го элемента И, выход которого соединен б со входом генератора равномерно распреде. ленных случайных чисед вход первого бпоО ка элементов НЕ соединен со вторым выходом генератора равномерно распределенных случайных чисел а выход первогоблока элементов НЕ соединен со входом блока элементов И, выход которого сое динен со входом шифратора, выход которого соединен с первым входом второго блока элемента НЕ, второй вход которого соединен с третьим выходом генератора 1/41 Тираж 641 Подпи БНИИПИ Государственного комитета ССС по делам изобретений и открытий 113035, Москва, Ж; Раушская наб., д;ктная, 4 г, Ужгород, у пиал ППП фП Составитель А. Карасовактор Л, Утехина ТехредЖ. Кастелевич Корректор Ю, Макаренк аз 174 сное