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

 

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

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

Респубпик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИ ИТИЛЬСТВУ (61) Дополнительное к авт. санд-ву (22) Заявлено 171279 (21) 2851833/18-24 (53) М. КЛ. с присоединением заявки ¹ (23) Приоритет

G 06 F 7/58

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

СССР но деаам изобретений и открытий

Опубликовано 23.0881. бюллетень Н9 31

Дата опубликования описания 230881 (53) УДК 681. 325 (088.8) I

Э.А.Баканович, В.И.Новиков, В.К.Мел ников и М.А.Орлов г. !

Минский радиотехнический институт -.- / (72) Авторы изобретения (7! ) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯ

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

Известен генератор случайных импульсов, в котором преобразуются случайные импульсные потоки с известными вероятностными характеристиками в случайные импульсные последовательности с требуемыми распределениями параметров импульсного потока. Этот генератор содержит датчики пуансоновских случайных ймпульсных потоков, блоки проведения случайных испытаний, блоки анапиза результата случайных испытаний, блоки преобразования случайных величин в случайные числа или в случайные значения параметров импульсных потоков Г11 .

Недостатки этого генератора состоят в том, что он не позволяет формировать марковские процессы с конечным множеством состояний и исследовать связность вероятностных

i рафов.

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

Недостатком данного устройства является то, что оно может быть использовано только для исследования связности вероятностного графа. Моделирование последовательностей случайных чисел с заданными вероятностными характеристиками н марковс° ких случайных процессов на нем невозможно. Кроме того, применение

ЭЦВМ для формирования случайных

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

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

30 счетчик.

857985

Устройство формирует случайные события н результате случайных испытаний, заключающихся в одновременном оптирании по общему входу блока схем совпадения и установки в регистре кода, соотнетстнующегo номеру схемы совпадения, через которую прошел первый с момента начала испытаЯ ния импульс датчиков блока ввода.

Генератор импульсов и счетчик преобразуют полученное случайное число в случайный временной интервал (3 .

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

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

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

Зо с входами. элементов ИЛИ и с входами перного регистра сдвига, выход которого является выходом устройства и соединен с входом блока ввода, введены блок управления, элемент И, 35 группа элементов ИЛИ, второй регистр сдвига, входы которого подключены к первой группе ныходон блока ввода соответственно, вторая группа выходов которого соединена с первыми входа- 4Q ми группы элементов ИЛИ, вторые входы которых объединены с второй группой входов блока элементов И и подключены к выходам второго регистра сдвига, вход "Сброс" которого объединен со входом "Сброс" первого регистра сдвига и подключен к первому выходу блока управления, второй и третий выходы которого подключены к входам "Сдвиг" второго и первого регистров сдвига соответственно, четвертый выход блока управления соединен с третьей группой входов блока элементов И, выходы группы элементов

ИЛИ соединены с входами элемента И, выход которого соединен с первым 5S входом блока управления, второй вход которого подключен к выходу элемента ИЛИ, третий и четвертый входы блока управления являются соответст венно первым и вторым входами уст- @ ройстна.

Кроме того, блок упранления содержит триггер, четыре элемента И, четыре элемента ИЛИ, три элемента задержки и дна формирователя импуль ф5 сов, первый вход блока управления подключен к первому S-входу тригге ра, второй S-вход которого через первый элемент задержки подключен к выходу первого элемента ИЛИ, первый вход которого объединен с к-входом триггера и является вторым входом блока управления, третий вход которого подключен к первому нходу первого элемента И и к первому входу второго элемента ИЛИ, выход которого соединен с третьим S-входом триггера и через первый формирователь импульсов соединен с первым входом блока управления и с входом второго элемента задержки, выход которого соединен с вторым входоь первого элемента И, выход которого соединен с первым входом третьего элемента

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

ИЛИ и с вторым входом первого элемента ИЛИ, четвертый выход блока управления соединен с выходом триггера и с первым входом третьего элемента

И, выход которого соединен с вторым входом четвертого элемента ИЛИ, четвертый вход блока управления соединен с вторыми входами второго элемента ИЛИ, третьего элемента И и с первым входом четвертого элемента И, второй вход которого подключен к выходу первого формирователя импульсов, выход четвертого элемента

И через второй формирователь импульсов Соединен с входом третьего элемента задержки.

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

Устройство содержит блок элементов И 1, шифратор 2, первый регистр

3 сдвига, элемент ИЛИ 4, второй регистр 5 сдвига, группу элементов

ИЛИ.б, элемент И 7, блок 8 управления, блок 9 ввода. Блок 1 содержит трехнходовые элементы И 10, блок 6 двухвходовые элементы ИЛИ 11, блок

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

Блок 8 управления выполнен на триггере 16 с тремя объединенными входной логикой И входами S и входом R, элементах И 17, 18, 19 и 20, элементах ИЛИ 21, 22, 23 и 24, элементах 25, 26 и 27 задержки, формирователях 28 и 29 импульсов.

857985

Блок 8 управления имеет также клеммы управления 30 и 31.

Рассмотрим функциональное назначение структурных компонентов устройства. Регистр 3 сдвига служит для хранения н процессе моделирования номера 1 последней пройденной к данному моменту вершины графа, причем 1 1,n. Для установки номера начальной вершины графа или начального состояния марковского процесса служат клеммы 15, соединенные с управляемыми входами начальной установки регистра 3 сдвига, запись номера вершины с которых происходит по сигналу УЗ блока 8, поступающему на второй управляющий вход регистра

3 сдвига. Для изменения состояния регистра 3 сдвига в процессе моделирования служат входы записи, подсоединенные к соответствующим выходам шифратора 2. Кроме того, регистр 20 имеет первый вход установки в нулевое состояние.

Регистр 5 сдвига имеет первый вход установки н нулевое состояние, управляемые входы установки н единичное состояние для каждого разряда регистра, запись информации с которых разрешена при наличии сигнала

У2 блока упранления 8 на втором управляющем входе регистра сдвига 5 и 30 производится по задним фронтам сигналов с выходом блока 9 ввода.

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

Таким образом, каждому состоянию

k регистра 3 сдвига соответствуют определенные интенсивности Л ге5 нераторов блока 9 ввода. Если для некоторого при заданном k интенсивность Хg =О, то на )-ом дополнительном выходе блока 9 ввода вырабатывается сигнал, поступающий на вход 45 соответствующей схемы ИЛИ 11 блока 6, Структура случайного испытания в предлагаемом устройстве не отлича.ется от структуры испытания в известном устройстве и заключается в одновременном отпирании элементов И 10 блока 1 с последующей фиксацией н регистре 3 сдвига номера, соответствующего номеру элемента И 10, блока 1, через который с момента начала испытаний прошел первый случайный импульс с выходов блока 9 ввода.

Зависимость распределения вероятностей состояния регистра 3 сдвига после случайного испытания от значений интенсивностей потоков на ны- 4О ходах блока 9 может быть различной.

В частности, если блок 9 вырабатывает пуассоновские потоки с интенсинностямиЛ,, .вЂ,„, где и — число по 1 токов, То вероятность того, что в. результате испытания в регистре 3 будет установлен номер m, определяется как п кт= Кщ/Е Лк1

1 1

Структура блока 9 ввода может быть различной. В качестве примера выбран вариант, приведенный на фиг.1, Номер из регистра 3 поступает на объединенные адресные входы модулей

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

ИЛИ-НЕ 14, выход которого является одним из дополнитель iHx выходов блока 9 ннода, причем выходы генератора

13 являются выходами блока 9.

Перед началом работы в модули 12 памяти записываются значения А к для управления интенсивностями Л генераторов 13, причем j соответствует номеру модуля 12 памяти, а адресу ячейки н модуле, где j=l,n, k 0,n. При k=0 моделируются запрещенные (ненадежные) вершины, при k=1,п моделируются дуги графа или состояния марковского процесса. Так как

). — — О соответствует A 0, при считы,вании нулевого кода из модуля 12 срабатывает соответствующий элемент

ИЛИ-НЕ 14. При подаче на клемму 10 разрешающего сигнала И, соответствующего случаю моделирования марковского случайного процесса, вырабатывается последовательность сигналов (фиг.3). Срабатывает элемент ИЛИ 22 (с„), формирователь 28 вырабатывает одйночный импульс У1, цлительностью

t 8 . tIo истечении времени задержки сигнала Т Ь элементом 26 срабатывают элемент И 19 и ИЛИ 24, вырабатывается сигнал УЗ (t1). Срабатывает элемент ИЛИ 21 и йосле времени задержки i>< элементом 25 устанавливается триггер 16 {t3). По импульсу

СИ (с ) триггер 16 сбрасывается, срабатывает элемент HJtH 21, элемент 25, триггер 16 снова через время с устанавливается и цикл повторяется. Работа устройства прсщолжается либо цо сброса сигнала p, либо до появления сигнала на первом входе блока

8 управления, запрещающего установку триггера 16.

При подаче на клемму 31 разрешающего сигнала Г, соответствующего случаю моделирования вероятностного графа, блок 8 вырабатынает последовательность сигналов (фиг.4). Срабатывают элементы ИЛИ 22, формирователь 28,вырабатывается сигнал у1 (tg), B момент времени t сигнал у1 оканчивается, срабатынает элемент

И 18, запускается формирователь 29, вырабатывающий сигнал с определеннод

857985 заданной длительностью Т 9 . Срабаты- вает элемент ИЛИ 23, вырабатывается

У2, В момент t> окончания У2 срабатывают элементы И 20 - ИЛИ 24, вырабатывается в течение интервала, задаваемого схемой 27 задержки, сигнал УЗ. Срабатывают элементы ИЛИ 21, задержки 25, устанавливается триггер

16, вырабатывается У4 (t4). Срабатывают элементы И 17, ИЛИ 23, вырабатывается У2. Пр СИ (t ) триггер 16, а вместе с тем и сигналы У4 и У2, сбрасываются, аналогично предыдущему через !gg вновь устанавливаются и т.д. Останов устройства происходит либо по сбросу сигнала Г, либо по сигналу, поступающему на первый вход блока 8 управления.

Рассмотрим работу устройства при формировании однородных цепей Маркова с конечным множеством состояний, На клемму 30 блока 8 управления поступает сигнал,ц., по которому блок

8 формирует последовательность сигналов, приведенную на фиг. 3.!

15

По сигналу У1 регистры 3 и 5 устанавливаются в нулевое состояние. Так как У2 в этом режиме не вырабатывается, то регистр 5 постоянно установлен в нуль и на его выходах присутствуют низкие уровни, которые поступают на инверсные вторые входы элементов И 10 блока 1.

По сигналу УЗ в регистр 3 заноситния сигнал У4, в результате чего элементы И 10 закрываются и оканчивается случайное испытание. В течение интервала ь из ячеек с адресом модулей 12 памяти считываются коды

А „, =устанавливаются интенсивности

1„, после чего блок 8 снова вырабаf тывает сигнал У4, начинается следующее случайное испытание и т.д.

Формирование марковского процесса останавливается при достижении заданного состояния процесса по сбросу сигнала М, либо если очередное состояние k будет иметь нулевые вероят. ности перехода Р, а следовательно, 65 ся начальное состояние ko марковского процесса с клемм 15. Из ячеек с адресом ko модулей 12 памяти блока 9 считываются коды А р„,настраивающие генераторы 13 на интенсивности

Х, соответствующие вероятностям перехода процесса P

ИЛИ 4. Выходной сигнал СИ элемента 50

ИЛИ 4 сбрасывает в блоке 8 управлеи нулевые Ак, . !Ipv, этом срабатывают элементы ИЛИ-ПЕ 14, ИЛИ 11, И 7, вы. ходной сигнал которых останавливает работы блока 8 управления.

Рассмотрим функционирование ус=.— ройства при исследовании связности вероятностных графов. Временная диаграмма сигналов, вырабатываемых блоком 8 в этом режиме при поступлении сигнала Г на клемму 31 блока, приведена на фиг. 4.

По сигналу У1 регистры 3 и 5 устанавливаются в нулевое состояние.

Из нулевых ячеек модулей 12 памяти блока 9 считываются коды Ар . Блок 8 вырабатывает сигнал У2 длительностью в течение которого случайные импульсы с выходов генераторов 13 могут устанавливать триггеры регистра

5 в единичное состояние. Путем изменения параметров Ао и ь з длительности сигнала У2 можно в широких пределах регулировать вероятности установки триггеров регистра 5, а следовательно, вероятности существования (надежности) вершин графа.

Пусть в регистре 5 поСле окончания У2 установлены в единицу 1, 3 и

12-й разряды, что соответствует несуществующим 1-, 3- и 12-й вершинам графа. Тогда в блоке 1 всегда будут закрыты элементы И 10 с номерами

1, 3 и 12. Следовательно, в регистре

3 никогда не будут установлены номера 1, 3 и 12, чем исключаются пути через эти вершины.

По сигналу УЗ в регистр 3 с шин

15 записывается номер k начальной вершиной графа. Из модулей 12 считываются коды А„р., устанавливаются интенсивности 1 р . Вырабатываются сигналы У2 и У4. Начинается случайное испытание, однако прохождение импульсов с выходов генераторов 13 разрешается только через те схемы

И 10, на инверсных вторых входах которых присутствует низкий потенциал.

Первый прошедший через блок 1 импульс блока 9 ввцда проходит через шифратор 2, устанавливает в регистре 3 номер М„ следующей вершиной графа, в регистре 5 устанавливает в единицу k -ый разряд, поступает на вход элемента ИЛИ 4, выходной сигнал

СИ которого сбрасывает в блоке 8 сигналы У4, У2, тем самым прекращая испытание. После интервала „ng, необходимого на перенастройку генераторов 13, снова вырабатываются У2 и У4, повторяется случайное испытание.

Однако теперь к ранее закрытым элементам И 10 добавилась схема с номером М, благодаря чему запрещается повторная установка в регистре 3 номера k„, что исключает прохождение пути на графе через одну и ту же вершину дважды.

Процесс моделирования пути оканчивается или по сбросу сигнала Г

857985

10 при достижении заданной вершины гра. фа, или при прохождении всех существующих вершин графа. При этом в регистре 5 установлены в единицу все разряды, срабатывают все элементы ИЛИ 11 блока 6, элемент И 7, по сигналу которого блок 8 останавливает устройство. В третьем случае процесс моделирования занершается при достижении вершины графа, вероятность выхода из которой в любую существующую, но еще не пройденную, вершину графа равна нулю. В этом случае также срабатывают нсе элементы ИЛИ 11, так как часть из них срабатывает от установленных в единицу разрядов несуществующих и вы- 15 полненных вершин, а остальные - от сигналов с выходов элемента ИЛИ-НЕ 14, соответствующих вершинам графа, вероятности перехода в которые равны нулю. 26

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

Кроме того, применение н блоке ввода генераторов потоков случайных Зо импульсов с автоматически регулируемой интенсивностью потока позноляет автоматизировать процесс управления устройством.

Однотипность применяемых блоков (генераторы потоков случайных импульсов, блоки памяти) позволяет создать основные узлы устройства в виде интегральных модулей, что упрощает конструирование.

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

1 ° Устройство для вероятностного моделирования, содержащее блок ввода, 4I$ первая группа выходов которого соединена с первой группой входов блока элементов И соответственно, вы-ходы которого через шифратор соединены с входами элемента ИЛИ и c gg входами первого регистра сдвига, выход которого является выходом устройства и соединен с вхбдом блока ввода, о т л и ч а ю щ е е с я тем, что с целью расширения функциональ- 55 ных возможностей устройства за счет исследования связности вероятностных графов, оно содержит блок управления, элемент И, группу элементов

ИЛИ, второй регистр сдвига, входы которого подключены к первой группе 46 выходов блока ввода соответственно, вторая группа выходов которого соединена с первыми входами группы элементов ИЛИ, вторые входы которых объединены с второй группой входов $5 блока элементов И и подключены к выходам второго регистра сдвига, вход "Сброс" которого объединен со входом "Сброс" первого регистра сдвига и подключен к первому выходу блока управления, второй и третий выходы которого подключены к входам

"Сдвиг" второго и первого регистров сдвига соответственно, четвертый выход блока управления соединен с третьей группой входов блока элементов И, выходы группы элементов ИЛИ соединены с входами элемента И, выход которого соединен с первым входом блока управления, второй вход которого подключен к выходу элемента

ИЛИ, третий и четвертый входы блока управления являются соответственно первым и вторым входами устройства.

Z. Устройство по п.1, о т "л и ч а ю щ е е с я тем, что блок управления сэдержит триггер, четыре элемента И, четыре элемента ИЛИ, три элемента задержки и два формирователя импульсов, первый вход блока управления подключен к первому Sвходу триггера, второй S-вход которого через первый элемент задержки подключен к выходу первого элемента

ИЛИ, первый вход которого объединен с Я-входом триггера и является вторым входом блока управления, третий вход которого подключен к первому входу первого элемента И и к перному входу второго элемента ИЛИ, выход которого соединен с третьим S -входом триггера и через первый формирователь импульсов соединен с первым входом блока управления и с входом второго элемента задержки, выход которого соединен с вторым входом первого элемента И, выход которого соединен с первым входом третьего элемента

ИЛИ, второй вход которого подключен к выходу второго элемента И, первый вход которого через третий элемент задержки объединен с его вторым входом и соединен с первым входом четвертого элемента ИЛИ, выход которого является вторым выходом блока управления, третий выход которого соединен с выходОм третьего элемента ИЛИ и с вторым входом первого элемента ИЛИ, четвертый выход блока управления соединен с выходом триггера и с первым входом третьего элемента И, выход которого соединен с вторым входом четнертого элемента ИЛИ, четвертый вход блока управления соединен с вторыми входами второго элемента ИЛИ, третьего элемента И и с первым входом четвертого элемента

И, второй вход которого подключен к выходу первого формирователя импульсов, выход четвертого элемента

И через второй формирователь импульсов соединен с входом третьего элемента задержки, 12

11

857985

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

9504196, кл, G 06 F 1/02, 1974, 2. Авторское свидетельство СССР

9433504, кл. 6 06 G 7/4В, 1972.

3. Авторское свидетельство СССР

9344431, кл. G 06 G 1/02, 1970 (прототип).

857985

Редактор П.Ортутай

Заказ 7245/79 Тираж 745 Подписное

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

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

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

Л (r>

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

Текред%. Кастелевич Корректор Г.Реыетник