Генератор однородного марковского процесса

О П И С А Н И Е4854 з 9ИЗОБРЕТЕН ИЯ Союз СоветскихСоциалистическихРеспублик АВТОРСКОМУ СВИДЕТИЛЬСТ 61) Дополнительное к авт. свид-ву 2.02.74 (21) 1 995772/18-2 2) Заявле(43) Опубликовано 25,09.75 БюллетеньГасударственный комитет Совета Министров СССР по делам изооретений и открытий(71) Заявител 4) ГЕНЕРА 1 ОР ОДНОРОДНОГО МАР 1 ОВСКОГОПРОЦЕССА Изобретентехнике и можгенерирования относится к вычиспитеп т быть использовано дпя однородного марковского роцесса. Известны уса ойства, генерируюшкие процессы и содатчик спучайных е однородные марк е ж шие унравпяемый вентипи, устройс также счетчик и ва управлениярегистры. амяти,Однако в таких устройствах выработкааждого нового состояния марковской цепи происходит пишь в резупьтате последовательных "черновых" розьп рышей (перебора)и и с обязатепьным периодом в 2 -1 розы грьша, не зависящим от действительного кошчества розыгрышей в каждом отдепьном случае. 11 ри таком принципе работы марковско оенератора несмотря не его высокое качество невозможно попу чить максимальное быстродействие при выработке очередного состояния маркове.кой цепи.Цепь изоб 1 етения - созеание ларковско оенератора обшдающего помимо качественности высоким бы:тродейгтвием,Это достигается тем, что генераторсодержит кольцевой счетчик, сдвигающийвход которого подключен ко второму выхо -ду бпока управления, регистр, сбросовыйвход которого подключен к выходу кольцевого счетчика и ко вторым входам вентипей, эпементы И,1 И выходы последнихнодкнючены ко второлу входу опока мяти, а входы - к разрядыл выходил р"гистра, кольцевого счетчика и ко вторымвходам элементов И соответственно,11 а чертеже изображена бок-анхелпредпагаемого генератора.На схеме: 1 - блок управпения; 2датчик случайных чисел; 3 - эпементы4 - копьцевой счетчик; 5 - элеленты101 И; 6 - регистр; 7 - бнок намяги; 8выходной регистр; 9 - вентили; 10 - сум матор,Генератор содержит блок 1 унршен,один из выходов кторого соедин.н е 1 зунравпяелый датчик 2 спучаиных севходами эпементов И 3, а дру ой в хивсо сдвиовыми входы кОпево .ка 4. Выходи кои цаво о счетчика 1 чдинены с первыми входами элементовЬИ 5, вторые входы которых подсоединены к выходам регистра 6, а выходыэлементов ИЛИ 5 соединены со вторым входом блока 7 памяти, Выход блока 7 памяти 5соединен с управляющим входом датчика 2случайных чисел, а первый вход блока 7памяти соединен с выходами регистра 8,которые являются выходами всего генератора, Входы регистра 8 соединены через Овентили 9 переписи с выходами сумматора10, а входы сумматора 10 - с выходамиэлементов И 3 и со входами регистра 6,Входы установки в "0" регистра 6 соединены как со входом кольцевого счетчика4, так и со вторыми входами вентилей 9переписи.В начале работы генератора в первомразряде кольцевого счетчика 4 записана"1 , а в остальных разрядах всюду "О",В это же время на регистре 6 также всюду установлены нули. Таким образом, коды записанные на счетчике 4 и регистре6, поразрядно складываясь, образуют младшие разряды адреса, старшие разряды когорого содержатся в выходном регистре 8,о упомянутому двоичному адресу в блоке7 памяти записана вероятность перескока, Ь - 1сразу на 2 ссстояний. Это означает,что на управляющий вход датчика 2 случйных чисел подана соответствующая вероятность. По мере того, как блок 1 управлеши подает свой первый импульс на входдатчика 2, на выходе последнего появляется импульс с заданной вероятностью..:ели дтчнк 2 дает разрешение па перескок (единица на выходе), то к первомуразряду сумматора 10 добавляется "1"и одновременно с этим записывается 1"в первый разряд регистра 6. Следующийвслед з первым импульс блока 1 управления, появляющийся на втором выходе,сдвигет в кольцевом счетчике 4 единицуна один разряд вправо, Соответственноменяется информация на выходах эле 45м оптовИИ 5, что определяет новый адресблок 7 памяти, и на управляющий входд шк 2 случайных чисел поступаетновая вероятность.аким образом, очередной импульс,следующий теперь опять с первого выходаблока 1 управления, может пройти на выход датчика 2 с новой вероятностью, ипроцедура будет повторяться до тех пор, 55 пока единица в кольцевом счетчике 4 не сдвинется в конец и не перепишется впервый разряд. Такая перепись сбрасываетв ноль регистр 6 и одновременно переписывает содержимое сумматора 10 в выходйой регистр 8, определяя тем самым очередное состояние цепи Маркова,Следовательно, работа блока 1 управления сводится к выдаче пар импульсовна каждый розыгрыш, причем эти импульсыразнесены как по выходам, так и по времени.Предположим, что П =5, то предлагаемый генератор на первом же тактесвоей работы будет с помощью датчика 2решать вопрос: продолжать ли розыгрыш впервой половине или перескочить сразу нашестнадцать состояний и разыгрывать вторую половину. Если предположить, что былосуществлен перескок на шестнадцать состояний, то генератор опять будет решать задачу продолжения розыгрыша в третьейчетверти или перескока в четвертую и т. д,Следовательно, вместо возможных 2 =32,розыгрышей, предлагаемый генератор будетсовершать не более пяти, что позволяетзначительно ускорить общую работу,Предмет изобретенияГенератор однородного марковского процесса, содержащий блок управления, первыйвыход которого подключен к первому входудатчика случайных чисел, второй вход которого соединен с выходом блока памяти,а выход - с первыми входами элементовИ, выходы которых подключены к разряднымвходам сумматора соответственно, выходной регистр, разрядные выходы которогосоединены с первым входом блока памятии с выходом устройства, а разрядные входы - с выходами вентилей соответственно,первые входы которых соединены с разрядными выходами сумматора, о т л и ч а юш и й с я тем, что, с целью повышениябыстродействия генератора, он содержиткольцевой счетчик, сдвигающий вход которого подключен ко второму выходу блокауправления, рс гистр, сбросовый вход которого подключен к выходу кольцевого счетчика и ко вторым входам вентилей, элементы ИЛИ, выходы которых подключены ко второму входу блока памяти, а входы - к разрядным выходам ре истра, кольцевогосчетчика и ко вторым входам элеметов Исоответственно,465439 выход Изд, М ОЯ Заказ ,) 3 3 Тираж 673 Подписное 11 НИИПИ Государственного комитета Сонета Министров СССР ио делам изобретений н открытий Москва, 13035, Раушская наб., 4 Предприятие Патент, Москва, Г.59, Бережковская наб., 24 Составитель А.Карасев Редактор ТЗагребельнаЮекред Т.Курилко Корректор А.Дзесова