Устройство для вероятностного моделирования Советский патент 1981 года по МПК G06F7/58 

1

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

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

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

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

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

10 случайных чисел с вешанными вероятностными характеристиками и марковских случайных процессов на нем невозможно. Кроме того, применение ЭЦВМ для формирования случайных

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

20

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

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

30 счетчик.

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

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

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

Для достижения поставленной цели в устройство для вероятностного моделирования, содержащее блок ввода, первая группа выходов которого соединена с первой Группой входов блока элементов И соответственно, выходы которого через шифратор соединены с входами., элементов ИЛИ и с входами первого регистра сдвига, выход которого является выходом устройства и соединен с входом блока ввода, введены блок управления, элемент И, группа элементов ИЛИ, второй регистр сдвига, входы которого подключены к первой группе выходов блока ввода соответственно, вторая группа выходо кс горого соединена с первыми входами группы элементов ИЛИ, вторые входы которых объединены с второй группой входов блока элементов И и подключены к выходам второго регистра сдвига, вход Сброс которого объединен со входом Сброс первого регистра сдвига и подключен к первсму выходу блока управления, второй и третий выходы которого подключены к входам Сдвиг второго и первого регистров сдвига соответственно, четвертый выход блока управления соединен с третьей группой входов блока элементов И, выходы группы элементов ИЛИ соединены с входами элемента И, ВЫХ04 которого соединен с первым входом блока управления, второй вход которого подключен к выходу элемента ИЛИ, третий и четвертый входы блока управления являются соответственно первым и вторым входами устройства.

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

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

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

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

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

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

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

Устройство содержит блок элементов И 1, шифратор 2, первый регистр 3 сдвига, элемент ИЛИ 4, второй регистр 5 сдвига, группу элементов ИЛИ б, элемент И 7, блок 8 управления, блок 9 ввода. Блок 1 содержит трехвходовые элементы И 10, блок 6 двухвходовые элементы ИЛИ 11, блок

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

Блок 8 управления выполнен на триггере 16 с тремя объединенными входной логикой И входами S и входом R, элементах И 17, 18, 19 и 20, элементах ИЛИ 21, 22, 23 и 24, элементах 25, 26 и 27 задержки, формирователях 28 и 29 импульсов. Блок 8 управления имеет также клеммы управления 30 и 31. Рассмотрим функциональное назначение структурных компонентов устройства. Регистр 3 сдвига служит для хранения в процессе моделирования номера i последней пройденной к данно лу моменту вершины графа, причем , п. Для установки номера начальной вершины графа или начального состояния марковского процесса служат клеммы 15, соединенные с управляемыми входами начальной уста новки регистра 3 сдвига, запись номера вершины с которых происходит по сигналу УЗ блока 8, поступающему на второй управляющий вход регистра 3 сдвига. Для изменения состояния регистра 3 сдвига в процессе модели рования служат входы записи, подсоединенные к соответствующим выходам шифратора 2. Кроме того, регистр имеет первый вход установки в нулев состояние. Регистр 5 сдвига имеет первый вход установки в нулевое Состояние, управляемые входы установки в единичное состояние для каждого разряда регистра, запись информации с ко торых разрешена при наличии сигнала У2 блока управления 8 на втором упра ляющем входе регистра сдвига 5 и производится по задним фронтам сигналов с выходом блока 9 ввода. Блок 9 ввода вырабатывает п пото ков случайных импульсов с интенсивностями j , где j - номер потока, k - номер текущей вершины или состоя ния марковского процесса, поступающи на вход блока 9. Таким образом, каждому состоянию k регистра 3 сдвига соответствуют определенные интенсивности ге нераторов блока 9 ввода. Если для некоторого j при заданном К интенсив ность Я 0, то на J-OM дополнитель ном выходе блока 9 ввода вырабатывается сигнал, поступающий на вход соответствующей схемы ИЛИ 11 блока Структура случайного испытания в предлагаемом устройстве не отлича.ется от структуры испытания в извест ном устройстве и заключается в одно временном отпирании элементов И 10 блока 1 с последующей фиксацией в регистре 3 сдвига номера, соответст вующего номеру элемента И 10, блока 1, через который с момента начала испытаний прошел первый случайный импульс с выходов блока 9 ввода. Зависимость распределения вероят ностей состояния регистра 3 сдвига после случайного испытания от значений интенсивностей потоков на выходах блока 9 может быть различной. Б частности, если блок 9 вырабатыва ет пуассоновские потоки с интенсивнocтямиЯцj,, число потоков, то вероятность того, что в. результате испытания в регистре 3 будет установлен номер т, определяется как /ёЛг Р Х Km Структура блока 9 ввода может быть различной. Б качестве примера выбран вариант, приведенный на фиг.1, Номер из регистра 3 поступает на объединенные адресные входы модулей 12памяти, выход каждого из которых соединен с входом управления интенсивностью соответствующего генератора 13 случайных импульсных потоков и входом соответствующего элемента ИЛИ-НЕ 14, выход которого является одним из дополнительных выходов блока 9 ввода, причем выходы генератора 13являются выходаи 1и блока 9. Перед началом работы в модули 12 памяти записываются значения АKJ для управления интенсивностями Л KJ генераторов 13, причем j соответствует номеру модуля 12 памяти, а k адресу ячейки в модуле, где ,n; ,n. При моделируются запрещенные (ненадежные) вершины, при ,n моделируются дуги графа или состояния марковского процесса. Так как 0 соответствует , при считы.вании нулевого кода из модуля 12 срабатывает соответствующий элемент ИЛИ-НЕ 14. При подаче на клемму 10 разрешающего сигнала М, соответствующего случаю моделирования марковского случайного процесса, вырабатывается последовательность сигналов (фиг.З). Срабатывает элемент ИЛИ 22 (t), формирователь 28 вырабатывает одиночный импульс У1, длительностью tjg . По истечении времени задержки сигнала С элементом 26 срабатывают элемент И 19 и ИЛИ 24, вырабатывается сигнал УЗ (tQ) . Срабатывает элемент ИЛИ 21 и после времени задержки TIJJ элементом 25 устанавливается триггер 16 (tj). По импульсу СИ (tj.) триггер 16 сбрасывается, срабатывает элемент ИЛИ 21, элемент 25, триггер 16 снова через время t,. устанавливается и цикл повторяется. Работа устройства прсщолжается либо до сброса сигнала JJ- , либо до появления сигнала на первом входе блока 8 управления, запрещающего установку триггера 16. При подаче на клемму 31 разрешающего сигнала Г , соответствующего случгио моделирования вероятностного графа, блок 8 вырабатывает последовательность сигналов (фиг.4). Срабатывают элементы ИЛИ 22, формирова тель 28,вырабатывается сигнал У1 (t), В момент времени tg сигнал У1 оканчивается, срабатывает элемент И 18, запускается формирователь 29, вырабатывающий сигнал с определенной

заданной длительностью Срабатывает элемент ИЛИ 23, вырабатывается У2. В момент ti, окончания У2 срабатывают элементы И 2О ;-ИЛИ 24, вырабатывается в течение интервала ,, задаваемого схемой 27 задержки, сигнал УЗ. Срабатывают элементы ИЛИ 21, Зсщержки 25, устанавливается триггер 16, вырабатывается У4 (t4.).. Срабатывают элементы И 17, ИЛИ 23, вырабатывается У2. По СИ tg- триггер 16, а вместе с тем и сигналы У4 и У2, сбрасываются, аналогично предьщущему через вновь устанавливаются и т.д. Останов устройства происходит либо по сбросу сигнала Г, либо по сигналу, поступающему на первый вход блока 8 управления.

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

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

По сигналу УЗ в регистр 3 заносится начальное состояние ko марковског о процесса с клемм 15. Из ячеек с адресом kQ модулей 12 памяти блока 9 считываются коды ,настраивающие генераторы 13 на интенсивности ((oj соответствующие вероятностям перехода процесса из состояния kp в состояние j.

о По сигналу У4 разрешается прохождение импульсов с выходом генераторов 13 через блок 1 элементов И 10, и тем самым начинается случайное испытание. Первый прошедший через блок 1 импульс блока 9 ввода проходит через шифратор 2, устанавливает в регистре 3 номер k следующего состояния марковского процесса и одновременно поступает на элемент ИЛИ 4. Выходной сигнал СИ элемента ИЛИ 4 сбрасывает в блоке 8 управления сигнал У4, в результате чего элементы И 10 закрываются и оканчивается случайное испытание. В течение интервала fjj из ячеек с адресом k модудей 12 памяти считываются коды AIC.J, Останавливаются И1 тенсивности , после чего блок 8 снова вырабатывает сигнал У4, начинается следующее случайное испытание и т.д.

Формирование марковского процесса останавливается при достижении заданного состояния процесса по сбросу сигнала ГА , либо если очередное состояние k будет иметь нулевые вероятности перехода P.j , а следовательно.

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

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

По сигналу У1 регистры 3 и 5 устанавливаются в нулевое состояние. Из нулевых ячеек модулей 12 памяти блока 9 считываются коды Ад., . Блок 8 вырабатывает сигнал У2 длительностью Tag / в течение которого случайные импульсы с выходов генераторов 13 могут устанавливать триггеры регистра 5 в единичное состояние. Путем изменения параметров А(JJ иСгэ длительности сигнала У2 можно в широких пределах регулировать вероятности установки триггеров регистра 5, а следовательно, вероятности существования (надежности) вершин графа.

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

По сигналу УЗ в регистр 3 с шин 15 записывается номер k начальной вершиной графа. Из модулей 12 считываются коды A)t,j-, устанавливаются интенсивностиXkoj Вырабатываются сигналы У2 и У4. Начинается случайное испытание, однако прохождение импульсов с выходов генераторов 13 разрешается только через те схемы и 10, на инверсных вторых входах которых присутствует низкий потенциал.

Первый прошедший через блок 1 импульс блока 9 ввдда проходит через шифратор 2, устанавливает в регистре 3 номер k следующей вершиной графа, в регистре 5 устанавливает в единицу разряд, поступает на вход элемента ИЛИ 4, выходной сигнал СИ которого сбрасывает в блоке 8 сигналы У4, У2, тем самым прекращая испытание. После интервала Jnj , необходимого на перенастройку генераторов 13, снова вырабатываются У2 и У4, повторяется случайное испытани Однако теперь к {занее закрытым элементам И 10 добавилась схема с номером k , благодаря чему запрещается повторная установка в регистре 3 номера k, что исключает прохождение пути на графе через одну и ту же вершину дважды.

Процесс моделирования пути оканчивается или по сбросу сигнала Г при достижении заданной вершины гра фа, или при прохождении всех существующих вершин графа. При этом в регистре 5 установлены в единицу все разряды, срабатывают все элемен ты ИЛИ 11 блока 6, элемент И 7, по сигналу которого блок 8 останавливает устройство. В третьем случае процесс моделирования завершается при достижении вершины графа, вероя ность выхода из которой в любую существующую, но еще не пройденную вершину графа равна нулю. В этом случае также срабатывают все элемен ты ИЛИ 11, так как часть из них срабатывает от установленных в единицу разрядов несуществую1йих и выполненных вершин, а остальные - от сигналов с выходов элемента ИЛИ-НБ соответствующих вершинам графа, вероятности перехода в которые равны нулю. Таким образом, предлагаемое изоб ретение обеспечивает возможности формирования марковских случайных процессов с конечным множеством сос тояний, исследование связности вероятностных графов с заданными вероятностями существо1вания вершин и дуг. Кроме того, применение в блоке ввода генераторов потоков случайных импульсов с автоматически регулируе мой интенсивностью потока позволяет автоматизировать процесс управления устройством. Однотипность применяемых блоков (генераторы потоков случайных импульсов, блоки памяти) позволяет создать основные узлы устройства в виде интегральных модулей, что упро щает конструирование. Формула изобретения 1. Устройство для вероятностного моделирования, содержащее блок ввод первая группа выходов которого соединена с первой группой входов бло ка элементов И соответственно, вы-ходы которого через шифратор соединены с входс1ми элемента ИЛИ и с входами первого регистра сдвига, вы ход которого является выходом устро ства и соединен с вхбдом блока ввода, отличающееся тем, ;что, с целью расширения функциональ |ных возможностей устройства за счет исследования связности вероятностных графов, оно содержит блок управ ления, элемент И, группу элементов ИЛИ, второй регистр сдвига, входы Которого подключены к первой группе выходов блока ввода соответственно, вторая группа выходов которого соед нена с первыми входами группы элементов ИЛИ, вторые входы которых объединены с второй группой входов блока элементов И и подключены к выходам второго регистра сдвига, вход Сброс которого объединен со входом Сброс первого регистра сдвига и подключен к первому выходу блока управления, второй и третий выходы которого подключены к входам Сдвиг второго и первого регистров сдвига соответственно, четвертый выход блока управления соединен с третьей группой входов блока элементов И, выходы группы элементов ИЛИ соединены с входами элемента И, выход которого соединен с первым входом блока управления,-второй вход которого подключен к выходу элемента ИЛИ, третий и четвертый входы блока управления являются соответственно первым и вторым входами устройства. 2. Устройство по П.1, о т л и чающееся тем, что блок управления содержит триггер, четыре элемента И, четыре элемента ИЛИ, три элемента задержки и два формирователя импульсов, первый вход блока управления подключен к первому Sвходу триггера, второй S-вход которого через первый элемент задержки подключен к выходу первого элемента ,ИЛИ, первый вход которого объединен с R-входом триггера и является вторым входом блока управления, третий вход которого подключен к первому входу первого элемента Инк первому входу второго элемента ИЛИ, выход которого соединен с третьим S-входом триггера и через первый формирователь импульсов соединен с первым входом блока управления и с входом второго элемента задержки, выход которого соединен с вторым входом первого элемента И, выход которого соединен с первым входом третьего элемента ИЛИ, второй вход которого подключен к выходу второго элемента И, первый вход которого через третий элемент задержки объединен с его вторым входом и соединен с первым входом четвертого элемента ИЛИ, выход которого является вторым выходом блока управления, третий выход которого соединен с выходом третьего элемента ИЛИ и с вторым входом первого элемента ИЛИ, четвертый выход блока управления соединен с выходом триггера и с первым входсм третьего элемента И, выход которого соединен с вторым вхбдом четвертого элемента ИЛИ, четвертый вход блока управления соединен с вторыми входа1ми второго элемента ИЛИ, третьего элемента И и с первым входом четвертого элемента И, второй вход которого подключен к выходу первого формирователя импульсов, выход четвертого элемента И через второй формирователь импульсов соединен с входом третьего элемента задержки.

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

/

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

2.Авторское свидетельстве СССР №433504, кл. е 06 G 7/48, 1972.

3.Авторское свидетельство СССР №344431, кл. G 06 G 1/02, 1970 (прототип) .

Фиг. 2