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

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИД1:ТИЛЬСТВУ (11) 485439

Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено12.02.74 (21) 1 995772/18-24 (51) М. Кл. с присоединением заявки № —.

Q 06 7 1/02

Гасударственный комитет

Совета Министров СССР по делам изооретений и открытий (23) Приоритет (43) Опубликовано 25.09.75 Бюллетень № 35 (45) Дата опубликования описания 19.О2.76 (53) 5#681.3(088.8) (72) Авторы изобретения

А. М. Морозов и Д. М. Судаков (71) Заявитель (54) ГЕНЕРА 1 ОР ОДНОРОДНОГО МАР1 0ВСКОГО

ПРОЦЕССА

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

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

1О

Однако в таких устройствах выработка каждого нового состояния марковской цепи

«po»exon» r »ишь в резупьтате последовательных "черновых" розьн рышей (перебора) п и с обязатепьным периодом в 2 -1 розы

15 грыз(а, не зависящим от действительного ко!шчества розыгрышей в каждом отдепьном случае. Нри таком принц»пе работы марковско! î енератора несмотря не его высокое качество невозможно но»учить

20 максимальное быстродействие при выработке очередного состояния марков(.кой цепи.

Цепь »зоб1<етения — создание марковско-! о енератора, об<(адающего помимо качестве»ности высоким бы(тродей(твием, Это достигается тем, что генератор содержит кольцевой счетчик, сдвигающий вход которого подключен ко второму выхо— ду бпока унравпен»я, регистр, сбросовьш вход которого подключен к выходу кольцевого счетчика и ко вторым входам вент»пей, эпементы IIJIII, выходы последних нодкнючены ко второл(у входу опока памяти, а входы — к разрядныл! выходал! р(-гистра, копьцевого счетчика и ко вторым входам элементов И соответственно.

I I a чертеже изображена блок-с-.хем» предпагаемого генератора.

На схеме: 1 — блок управпения; 2 да! чик случайных чисел; 3 — эпементы

4 — копьцевой счетчик; 5 — элементы

IIlllI; 6 — регистр; 7 — бнок !!г<л<я н; выходной регистр; 9 — вентили; 1 0 — су<.<-матор.

Генератор содержит блок 1 унр(<ш!«»» <, один из выходов к<>торого соед»н(н»:I>t :! управ!(яел<ый датчик 2 сну чайных !»се!! « входами эпементов II 1, а дру! ой в! <х< и— со (- дви < овым и входа ми КО!<<ц< в<

485439 нены с первыми входами элементов

ИЛИ 5, вторые входы которых подсоединены к выходам регистра 6, а выходы элементов ИЛИ 5соединены со вторым входом блока 7 памяти. Выход блока 7 памяти соединен с управляющим входом датчика 2 случайных чисел, а первый вход блока 7 памяти соединен с выходами регистра 8, которые являются выходами всего генератора. Входы регистра 8 соединены через )() вентили 9 переписи с выходами сумматора

10, а входы сумматора 10 — с выходами элементов И 3 и со входами регистра 6.

Входы установки в "0" регистра 6 соединены как со входом кольцевого счетчика 4, так и со вторыми входами вентилей 9 переписи.

В начале работы генератора в первом разряде кольцевого счетчика 4 записана

"1, а в остальных разрядах всюду "0".

В это же время на регистре 6 также всюду установлены нули. Таким образом, коды записанные на счетчике 4 и регистре

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

llo упомянутому двоичному адресу в блоке

7 памяти записана вероятность перескока, Ь вЂ” 1 .разу на 2 ссстояний. Это означает, что на управляющий вход датчика 2 случайных чисел подана соответствующая вероятность. По мере того, как блок 1 управления подает свой первый импульс на вход датчика 2, на выходе последнего появляется импульс с заданной вероятностью. !.:ели датчик 2 дает разрешение ца перескок (единица на выходе), то к первому разряду сумматора 10 добавляется "1" и одновременно с этим записывается 1" в первый разряд регистра 6. Следующий вслед за первым импульс блока 1 управления, появляющийся на втором выходе, сдвигает в когп,цевом счетчике 4 единицу на один разряд вправо. Соответственно меняется информация на выходах эле45 м оптов f ИИ 5, что определяет новый адрес блока 7 памяти, и на управляющий вход дат шка 2 случайных чисел поступает новая вероятность.

Таким образом, очередной импульс, следующий теперь опять с первого выхода блока 1 управления, может пройти на выход датчика 2 с новой вероятностью, и процедура будет повторяться до тех пор, 55 пока единица в кольцевом счетчике 4 не сдвинется в конец и не перепишется в первый разряд. Такая перепись сбрасывает в ноль регистр 6 и одновременно переписывает содержимое сумматора 10 в выходйой регистр 8, определяя тем самым очередное состояние цепи Маркова.

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

Предположим, что П =5, то предлагаемый генератор на первом же такте своей работы будет с помощью датчика 2 решать вопрос: продолжать ли розыгрыш в первой половине или перескочить сразу на шестнадцать состояний и разыгрывать вторую половину. Если предположить, что был осуществлен перескок на шестнадцать состояний, то генератор опять будет решать задачу продолжения розыгрыша в третьей четверти или перескока в четвертую и т. д.

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

Предмет изобретения

Генератор однородного марковского процесса, содержащий блок управления, первый выход которого подключен к первому входу датчика случайных чисел, второй вход которого соединен с выходом. блока памяти, а выход — с первыми входами элементов

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

485439 дыхоУ

Изд. М)ОЯ

Заказ . ) .3.3

Тираж 673

Подписное

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

Москва, 113035, Раушская наб., 4

Предприятие «Патент», Москва, Г-59, Бережковская наб., 24

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

Редактор Т.ЗагребельнаЮекред Т.Курилко Корректор А.Дзесова