Устройство для вероятностного моделирования

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬС?ВУ

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

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

Республик ()922707

Я, / г (61) Дополнительное к авт. свид-ву Р 488212 (22) Заявлено 100980 (21) 2980775/18-24

Р М g> з с присоединением заявки ¹

G F 1/02

G Об F 7/58

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

СССР по дел ам изобретений н открытий (23) Приоритет (33) УДК б 81 325 (088. 8) Опубликовано 23.0482 Бюллетень ¹15

Дата опубликования описания 230482 в и " Р " -1 °, ",«ь удойно-.,Краси or o (72) Авторы изобретения

Г.Г.Баранов, P.Ã.Âàãàïoâ, В.М.Захар и Ю.С.Комаров (71) Заявитель

Казанский ордена Ленина и ордена

Яр

С! (54) УСТРОЧСТВО ДЛЯ ВЕРОЯТНОСТНОГО

МОДЕЛИРОВАНИЯ

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

По основному авт ° св. 9 488212 известно устройство, содержащее генератор случайных чисел, блок сравнения, регистр маски, регистр числа, блок . памяти, регистр адреса и блок управления, причем вход генератора случайных чисел. соединен с первым выходом. блока управления, первый вход блока сравнения соединен с выходом генератора случайных чисел, второй вход— с вторым вйходом блока управления, а первый выход — с первым входом регистра адреса, второй вход которого соединен с третьим выходом блока управления, а выход — c входом блока памяти, выход которого подключен к первому входу регистра числа, второй вход которого подключен к четверто= му выходу блока управления, пятый выход которого соединен с первыМ входом регистра маски, второй вход которого соединен с вторым выходом блока сравнения, а третий вход — с выходом регистра числа, первый выходс третьим входом блока сравнения, а второй выход .- с третьим входом ре,гистра адреса, предназначенное для З0 формирования дискретных случайных величин и простых цепей Маркова.

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

Цель изобретения — раэширение функциональных возможностей за счет формирования многосвязных цепей

Маркова.

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

922707

Генератор 1 случайных чисел предназначен для генерации. исходных, равномерно распределенных случайных двоичных чисел. Вход генератора 1 слут- чайных чисел соединен с первым выходом блока 7 управления. Блок 2 сраво нения служит для параллельного сравнения группы граничных значений инмму- тервалов разбиения области определения формируемой случайной функции с

10 исходным случайным числом. Первый вход блока 2 сравнения сбединен с выходом генератора 1 случайных чисел, второй вход - с вторым выходом блока

7 управления, а первый выход — с первым входом регистра б адреса. Регистр б адреса служит для управления блоком 5 памяти и разделен на две части — младшую и старшую. Младшая часть указывает место расположения отдельных ячеек блока памяти. Старшая часть регистра указывает место расположения массива ячеек. Первый вход регистра б адреса,. соединенный с первым выходом блока 2 сравнения, является входом младшей части. Второй вход регистра б адреса соединен с третьим выходом блока 7 управления и вторым входом блока 8. Этот вход является входом синхронизации. Третий вход регистра б адреса соединен с выходом блока 8 изменения глубины связи состояний цепи и является информационным входом старшей части регистра б. Блок 5 памяти служит для хранения кода функции распределения

35 и ее аргументов. Вход блока 5 памяти соединен с выходом регистра б адреса. Регистр 4 числа служит для приема содержимого блока 5 памяти и его хранения на время операции сравнения.

4Р Первый вход регистра 4 числа соединен с выходом блока 5 памяти, а второй вход — с четвертым выходом блока 7 управления. Регистр 3 маски служит для маскирования разрядов регистр45 ра 4 числа. Цель маскирования - в заданный такт работы устройства снимать информацию только с определенной части разрядов ячейки блока 5 памяти. Первый вход регистра 3 маски соединен с пятым выходом блока 7 управления, второй вход с вторым выходом блока 2 сравнения, а третий вход — с выходом регистра 4 числа.

Первый выход регистра 3 маски соединен с третьим входом блока 2 сравнения, а второй выход — с первым входом блока 8 изменения глубины связи состояний цепи. Блок содержит коммутатор 9, группу 10 элементов, сумматор ll.по модулю два, элемент ИЛИНЕ 12, счетчик 13 и элемент И 14, причем первый вход коммутатора 9 и первый вход элементов 10 соединены между собой и образуют первый вход блока 8. Второй вход элементов 10, 65 выходу блока. управления, пятый выход которого соединен с первым входом регистра маски, второй вход которого соединен с вторым выходом блока срав нения, третий вход — с выходом регис ра числа, а первый выход — с третьим входом блока сравнения, дополнительн введены счетчик, элемент ИЛИ-НЕ, эле мент И, сумматор по модулю два, ко татор и группа элементов И, первые входы которых объединены с первым входом коммутатора и подключены к второму выходу регистра маски, вторые входы элементов И группы объединены с первым входом элемента И, со счетным входом счетчика и с вторым входом регистра адреса, третий вход которого соединен с выходом коммутатора, второй вход которого объединен со вторым входом элемента И и подключен к выходу элемента ИЛИ-НЕ, входы которого соединены с разрядными выходами счетчика, третий вход коммутатора подключен к выходу сумматора по модулю два, первый и второй входы которого соединены соответственно с выходами элементов И группы и элемента И.

На фиг.l приведена блок-схема устройства; на фиг.2 — схема блока управления; на фиг.3 — диаграммы работы блока управления.

Устройство содержит генератор 1 случайных чисел, блок 2 сравнения, регистр 3 маски, регистр 4 числа, блок 5 памяти, регистр 6 адреса, блок 7 управления, блок 8 изменения глубины связи состояний цепи, коммутатор 9, группу 10 элементов И, сумматор 11 по модулю два, элемент ИЛИНЕ 12, счетчик 13, элемент И 14.

Блоки 1-7 относятся к основному устройству, узлы 9-14, содержащиеся в блоке 8, являются дополнительными.

Блок 7 управления содержит генератор 15 тактовой частоты, элементы ИЛИ-НЕ 16 и 17, сдвигающий регист

18, элементы ИЛИ 19 и 21, элемент И

20, сдвигающий регистр 22, элементы

И 23-25, сдвигающий регистр 26, элемент И 27, элемент HE 28, элементы И

29 и 30, шину 31 связи с генератором

1 случайных чисел, шину 32 связи с регистром 4 числа, шину 33 связи с регистром 3 маски, шину 34 связи с блоком 2 сравнения, шину 35 связи с регистром б адреса, часть 36 шины 35, используемую для синхронизации блока 8.

При этом R - -вход установки нуля;

С - синхровход;. D — информационный вход; "1" — уровень логической единицы.

Цепи питания и начальной установки исходного состояния не показаны.

На фиг.3 приведены временные диаграммы работы блока управления на выходах определенных узлов схемы. первый вход элемента И 14 и вход

922707 счетчика 13 также соединены между собой и образуют второй вход блока 8.

Выходом блока 8 служит выход коммутатора 9. Второй вход коммутатора 9 соединен с вторым входом элемента

И 14 и выходом элемента ИЛИ-HE 12, вход которого соединен с выходом счетчика 13. Выход элемента И 14 соединен с первым входом, сумматора 11 по модулю два, второй вход которого соединен с выходом элементов 10, а выход — с третьим входом коммутатора 9.

1О

Принцип работы устройства состоит в следующем. 15

Получение случайных чисел х (з.-1,2,....,n) с заданным законом распределения F(x; ) основано на сравнении равномерно распределенных чисел со значениями F(x<), отыскании интер-к< вала, где выполняется условие

F(х;)< <Г(х;, ) (1) и выдачи соответствующего данному интервалу значения х<.

Для реализации соотношения (1) нсе значения F(x<) разбиты на группы.

Группы выбираются из блока памяти логарифмическим перебором и каждая группа сравнивается с числом параллельно. Логарифмический перебор осуществляется упорядоченным расположением значений F(x ) и х< по группам.

При формировании простых и многосвязных цепей Маркова алгоритмы получения х; служат для реализации одной строки стохастической матрицы. Выбор 35 следующей строки определяется полученными значениями х;.

Функционирование устройства рассмотрим на следующем примере. Пусть

n=64(1=1,64) и основание логарифма 40 равно 4.,Кроме того, для определенности предположим, что генератор 1 случайных чисел является псевдослучайным. Соответствующая этому примеру схема блока 7. управления приведе- 45 на на фиг.2.

Устройство работает следующим об-. разом.

По внешнему сигналу "Пуск", который поступает в блок 7 управления по шине "Пуск" (см.фиг.2), триггер, образованный элементами ИЛИ-НЕ 16 и 17, устанавливается в единичное состояние. При этом на информационный.. вход сдвигающего регистра 18 поступает уровень логической единицы. Передним фронтом очередного импульса тактовой частоты, которые пбступают на синхровход регистра 18 с выхода генератора 15 тактовой частоты, в первый раэряц регистра 18 (верхний по схеме) записынается "1". Эта "1" устанавлинает в исходное нулевое состояние триггер, образованный элементами ИЛИ-НЕ 16 и 17, и через элемент

ИЛИ 19 открывает элемент И 20 для 65 прохождения импульсон генератора 15 тактовой частоты. При поступлении следующего импульса тактовой частоты "1" иэ первого разряда регистра

18 переписывается но нторой, а в первый гьэряд записывается "0". Ыестой импульс тактовой частоты вызывает появление "1" на выходе шестого, последнего разряда регистра 18, который через элемент ИЛИ 21 соединен с Dвходом сдвигающего регистра 22. При, поступлении седьмого импульса такто<вой частоты регистр 18 оказывается в нулевом состоянии, элемент И 20 запи-. рается, а н первый разряд регистра 22 (верхний по схеме, образует шину 32) записывается "1" ° В результате на шине 31> связывающей блок управления с генератором 1 случайных чисел, формируются шесть импульсов, кото,рые необходимы для генерации исход ного случайного 6-разрядного двоич ного числа. Полученное случайное число поступает с выхода генератора 1 на первый вход блока 2 сравнения. Импульс на шине 32, которая образована выходом перного разряда регистра

22 и связывает блок управления с регистром 4-числа, осуществляет запись в регистр 4 числа содержимого ячейки блока 5 памяти, адрес которой определяется регистром 6 адреса. При этом старшая часть. регистра 6 определяет адрес массива ячеек, а млад-. шая часть — адрес ячейки в массиве..

Записанное в регистр 4 числа содержимое ячейки блока 5 памяти через ре. гистр 3 маски поступает на другой вход блока 2 сравнения. В рассматриваемом примере для реализации соотношения (1) необходимо три такта. В первый такт проверяются условия

F (х< )Е 3

Г (хя) < F

F (х<

Пусть попало в интервал (F (х< ), F (х а ) ), тогда но второй такт проверяются условия

Г(х,)<1Г(х <), F (хи)<В,F(xe),,F (x8)

PF (х< ), F(х«)5, тогда н третий такт проверяются условия

F (х < ) < < F (х < 3 ). р

F (х<, )<и,< F (X <4 ), F(х<„)<Е,

Р(х<э )<Е, F (х

В эти три такта иэ блока 5 памяти выбираются три ячейки, в которых содержатся следующие группы значений

F(х<б) ° F(х 32) F(х<<8) i =

F(x q ), F(xg ), F(x )

F(x

922707

Эти группы сравниваются в блоке 2 сравнения со случайным числом Е,. Принадлежность числа $ одному из четырех интервалов указывается в виде логической единицы на одном из четырех выходов, образующих выходную шину бло- ка 2. Результат сравнения поступает в младшую часть регистра 6 адреса, которая представляет собой сдвигающий регистр, и служит для Формирования адреса, по которому из блока 5 !О памяти выбирается новая группа,значений F(x ), Первая группа F(х;), которая сравнивается в первом такте сравнения, не зависит от Е„ поэтому (адрес ячейки, в которой хранится пер-15 вая группа F(õ ), является постоянным. Это достигается путем установки младшей части регистра 6 адреса в (нулевое состояние перед каждым циклом сравнения. 20

Процесс сравнения обеспечивается

22 выполняет Функцию распределителя импульсов, а регистр 26 в сочетании с элементом И 27 — функцию счетчика тактов сравнения. При этом первый импульс, поступающий на шину 32, служит для записи в регистр 4 числа очередной группы F(x;). Второй импульс, который с второго выхода ре" гистра 22 через открытый элемент И

29 поступает на шину 34, служит для записи в регистр,.содержащийся в блоке 2 сравнения, результата сравнения. Запоминание результата сравнения необходимо для правильной ра- З5 боты регистра 3 маски, так как в противном случае при маскировании разрядов регистра 4 числа изменяется результат предыдущего сравнения, который управляет регистром 3 маски, 40 что приводит к изменению результата маскирования. Третий импульс, который с третьего выхода регистра 22 .через открытый элемент И 30 поступает на шину 35, служит для записи ре- 45 зультата сравнения в младшую часть регистра 6 адреса..

После окончания цикла сравнения из блока 5 памяти в регистр 4 числа считывается группа значений х, одно из которых является текущим состоянием цепи. Выбор х; обеспечивается регистром 3 маски. Те части регистра маски, в которые по выходам из блока

2 сравнения поступили логические нули, закрываются. Открытой остается только одна часть, на вход которой поступила "1". Число х; снимается с . тех разрядов регистра 4 числа, которые соответствуют этой открытой части. Считывание х(и переход к следу.ющей строке стохастической матрицы обеспечиваются изменением режима работы блока управления. Если первая, вторая и третья серии импульсов, сформированных реги тром 22, обеспе- 65

0- ние, что вызывает появление "1" на следующим образом. Сдвигающий регистр чивают реализацию цикла сравнения, то последняя четвертая серия импульсов обеспечивает формирование текущего значения цепи и подготовку к новому циклу работы устройства. Элемент И 27 при этом открывается, так как после каждой серии импульсов в регистр 26 записывается "1", и после третьей серии на всех входах элемента И 27 присутствует "1". Это приводит к запиранию элементов И 29 и 30 и отпиранию элементов И 23 и 25. В результате, второй импульс с регистра 22 поступает не в блок 2 сравнения, а через элемент И 23 на шину 33, связывающую блок управления с регистром 3 маски. Одновременно этот им- . пульс поступает на шины 36 и 35. По шине 35 этот импульс поступает в младшую часть регистра 6 адреса и устанавливает ее в исходное нулевое состояние, осуществляя тем самым подготовку к новому циклу работы, а по шине 36 он поступает на вход счетчйка 13 и второй вход элементов 10.

Третий импульс с регистра 22 через элемент И 25 поступает на шины 36 и

35, причем по шине 36 он поступает на первый вход элемента И 14, а по шине 35 - на старшую часть регистра б адреса и служит для записи информации в старшую часть регистра 6.

Полученное значение х;, представляющее собой текущее состояние цепи, с выхода регистра 4 через регистр 3 маски поступает на первые входы коммутатора 9 и элементов И 10. Импульс блока 7 управления, поступающий с выхода элемента И 23 и устанавливающий в исходное состояние младшую часть регистра 6 адреса, одновременно поступает на второй. вход элементов И 10, открывает их, и на вход сумматора li по модулю два поступает число х;. Сумматор 11 представляет собой набор Т-триггеров, входы которых соединены с соответствующими выходами элементов И 10, и служит для поразрядного суммирования по модулю два чисел х . Исходным состоянием сумматора 11 является нулевое.

Импульсы, поступающие на второй вход группы 10 элементов, одновременно поступают на вход счетчика 13, который подсчитывает количество суммированных чисел х(.

После сложения m чисел (число ш определяет заданную глубину связности цепи и представляет собой число возможных состояний счетчика 13, включая нулевое) счетчик 13 переполняется и переходит в нулевое состоявыходе элемента ИЛИ-НЕ 12, входы которого соединены с выходами триггеров счетчика 13. При этом результат суммирования чисел х„ с выхода сумматора 11 через коммутатор 9 поступа922707

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

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

ИЛИ-НЕ, элемент И, сумматор по модулю два, коммутатор и группу элементов И, первые входы которых объединены с первым входом коммутатора и подключены к второму выходу регистра маски, вторые входы элементов И группы объединены с первым входом элемента И, со счетным входом счетчика и с вторым входом регистра адреса, третий вход которого соединен с выходом элемента И и подключен к выходу элемента ИЛИ-НЕ, входы которого соединены с разрядными выходами счетчика, третий вход коммутатора подключен к выходу сумматора по модулю два, первый и второй входы которого соединены соответственно с выходами элементов И группы и элемента И. ет на вход старшей части регистра б адреса. Запись этой информации в регистр 6 осуществляется импульсом блока 7 управления, поступающим с . выхода элемента И 25. Записанный в регистр б адреса результат суммирования служит адресом массива ячеек в блоке 5 памяти, по которому записана очередная строка стохастической матрицы цепи. После каждого такого цикла формирования m-связного значе- 10 ния цепи сумматор 11 по модулю два устанавливается в нулевое состояние импульсом записи информации в старшую часть регистра 6. Этот импульс поступает на первый вход элемента И 15 .l4 на второй вход которого с выхода элемента ИЛИ-НЕ 12 поступает "l".

Возникающий на выходе элемента И 14 импульс поступает на вход установки нуля сумматора ll по модулю два.

Цикл работы блока 7 управления завершается после окончания импуль- . са записи информации в старшую часть регистра б. При этом очередной тактовый импульс генератора 15 тактовой частоты вызывает появление нl" на последнем выходе регистра 22, что приводит к появлению > 1 " на цоследнем выходе регистра 26. В результате на выходе элемента И 24 появляется " 1 ", которая устанавливает в нулевое состояние регистры 18, 22 и 26 и одновременно устанавливает в единичное состояние триггер, образованный элементами ИЛИ-HE 16 и 17, осуществляя тем самым новый пуск блока. 7 управ- З5 ления. На этом цикл работы устройства завершается.

В предлагаемом устройстве наряду с формированием простых цепей Маркова, что достигается путем установки 40 счетчика 13 в нулевое состояние, можно получить более сложные цепи, „в которых вероятность появления текущего состояния цепи зависит от заданной комбинации предыдущих состояний или от заданного числа состояний. По своим функциональным возможностям предлагаемое устройство может при небольших аппаратурных затратах по сравнению с известным устройством заменить одновременно два устройства, одно из которых предназначено для генерации простых цепей Маркова, а второе - для генерации многосвязных цепей Маркова.

922707 йуя

Фала

Жона

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

Редактор В.Данко Техред А.Ач

Корректор М.Пожо

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

Заказ 2580/62 Тираж 732 Подписное

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

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