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

Союз СоветскихСоциалистическихРеспублик ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИ ИТИЛЬСТВУ(22) Заявле исоединением заявки 06 Г 7/58 осударствеиный комитет СССР ио дедам изобретений и открытий(23) Приорите убликовано 23,0881.бюллетень ЙУта опубликования описания 230881 3) УДК 681.(7 ) Заявитель инский радиотехнический институт 54) УСТРОЙС 10 Изобретение относится к вычислительной технике и может быть использовано при построении моделирующей аппаратуры для исследования структурно сложных систем.Известен генератор случайных импульсов, в котором преобразуются случайные импульсные потоки с известными вероятностными характеристиками в случайные импульсные последовательности с требуемыми распределениями параметров импульсного потока. Этот генератор содержит датчики пуансоновских случайных ймпульсных потоков, блоки проведения случайных испытаний, блоки анадиза результата случайных испытаний, блоки преобразования случайных величин в случайные числа или в случайные значения параметров импульсных потоков Г 11 .Недостатки этого генератора состоят в том, что он не позволяет формировать марковские процессы с конечным множеством состояний и исследовать связность вероятностных 1 рафов.Известно устройство для определения характеристик связности вероятностного графа, соединенное электронной цифровой вычислительной маши РОЯТНОСТНОГО МОДЕЛИРОВАНИ ной и содержащее блок возбуждениявершин, блок возбуждения кодовыхшин, блок анализа и генератор импульсных меток Г 21.Недостатком данного устройстваявляется то, что оно может быть использовано только для исследованиясвязности вероятностного графа. Моделирование последовательностейслучайных чисел с заданными вероятностными характеристиками н марковских случайных процессов на нем невозможно. Кроме того, применениеЭЦВМ для формирования случайныхсостояний вершин и дуг графа и длявывода полученных значений в блокивозбуждения вершин и кодовых шинснижает производительность системыв целом.Наиболее близким техническим решением к предлагаемому изобретениюявляется устройство для вероятностного моделирования, содержащее последовательно соединенные блок ввода,выполненный на датчиках потоков случайных импульсов с регулируемымиинтенсивностями, блок схем И, шифратор, регистр номера схем, совпадения,схему ИЛИ, генератор импульсов исчетчик, 857985Устройство формирует случайныесобытия в результате случайных испытаний, заключающихся в одновременном оптирании по общему входу блокасхем совпадения и установки в регистре кода, соответствующего номерусхемы совпадения, через которую прошел первый с момента начала испыта 3ния импульс датчиков блока ввода,Генератор импульсов и счетчик преобразуют полученное случайное числов случайный временной интервал 33 .Недостаток этого устройства втом, что оно не позволяет формироватьмарковские процессы с конечным множеством состояний и исследовать связность вероятностных графов. 15Цель изобретения - расширениефункциональных возможносте за счетформирования однородных цепей Маркова с конечным множеством состояний,исследования связности вероятност Оных графов, определения всех возможных простых цепей в графе при заданных вероятностях существования дуги вершин,Для достижения поставленной целив устройство для вероятностного моделирования, содержащее блок ввода,первая группа выходов которого соединена с первой группой входов блокаэлементов И соответственно, выходыкоторого через шифратор соединеныЗОс входами. элементов ИЛИ и с входамипервого регистра сдвига, выход которого является выходом устройства исоединен с входом блока ввода, введены блок управления, элемент И, 35группа элементов ИЛИ, второй регистрсдвига, входы которого подключенык первой группе выходов блока вводасоответственно, вторая группа выходовкоторого соединена с первыми входами группы элементов ИЛИ, вторые входы которых объединены с второй группой входов блока элементов И и подключены к выходам второго регистрасдвига, вход "Сброс" которого объединен со входом "Сброс" первого регистра сдвига и подключен к первомувыходу блока управления, второй итретий выходы которого подключены квходам "Сдвиг" второго и первого регистров сдвига соответственно, четвертый выход блока управления соединен с третьей группой входов блокаэлементов И, выходы группы элементовИЛИ соединены с входами элемента И,выход которого соединен с первым 35входом блока управления, второй входкоторого подключен к выходу элемента ИЛИ, третий и четвертый входыблока управления являются соответственно первым и вторым входами устройства.Кроме того, блок управления содержит триггер, четыре элемента И, четыре элемента ИЛИ, три элемента задержки и два формирователя импуль 45 сов, первый вход блока управления подключен к первому 5-входу тригге ра, второй 5-вход которого через первый элемент задержки подключен к выходу первого элемента ИЛИ, первый вход которого объединен с к-входом триггера и является вторым входом блока управления, третий вход которого подключен к первому входу первого элемента И и к первому входу второго элемента ИЛИ, выход которогосоединен с третьим 5-входом триггера и через первый формирователь импульсов соединен с первым входом блока управления и с входом второго элемента задержки, выход которого соединен с вторым входоь первого элемента И, выход которого соединен с первым входом третьего элемента ИЛИ, второй вход которого подключен к выходу второго элемента И, первый вход которого через третий элемент задержки объединен с его вторым входом и соединен с первым входом четвертого элемента ИЛИ, выход которогоявляется вторым выходом блока управления, третий выход которого соединен с выходом третьего элементаИЛИ и с вторым входом первого элемента ИЛИ, четвертый выход блока управления соединен с выходом триггера и с первым входом третьего элемента И, выход которого соединен с вторым входом четвертого элемента ИЛИ, четвертый вход блока управления соединен с вторыми входами второго элемента ИЛИ, третьего элемента И и с первым входом четвертого элемента И, второй вход которого подключен к выходу первого формирователя импульсов, выход четвертого элемента И через второй формирователь импульсов Соединен с входом третьего элемента задержки.На фиг. 1 приведена структурная схема устройства, на фиг. 2 - функ циональная схема блока управления; на фиг, 3 и фиг, 4 - временные диаграммы сигналов на выходах блока управления.Устройство содержит блок элементов И 1, шифратор 2, первый регистр 3 сдвига, элемент ИЛИ 4, второй регистр 5 сдвига, группу элементов ИЛИ б, элемент И 7, блок 8 управления, блок 9 ввода. Блок 1 содержит трехвходовые элементы И 10, блок б двухвходовые элементы ИЛИ 11, блок 9 ввода - модули 12 памяти, генераторы 13 случайных импульсных потоков, элементы ИЛИ-НЕ 14, клеммы 15. Блок 8 управления выполнен на триггере 16 с тремя объединенными входной логикой И входами 5 и входом Н, элементах И 17, 18, 19 и 20, элементах ИЛИ 21, 22, 23 и 24, элементах 25, 2 б и 27 задержки, формирователях 28 и 29 импульсов.заданной длительностью Т 9 . Срабаты- вает элемент ИЛИ 23, вырабатывается У 2, В момент С окончания У 2 срабатывают элементы И 20 ИЛИ 24, вырабатывается в течение интервала 7, задаваемого схемой 27 задержки, сигнал УЗ. Срабатывают элементы ИЛИ 21, задержки 25, устанавливается триггер 16, вырабатывается У 4 (с 4), Срабатывают элементы И 17, ИЛИ 23, вырабатывается У 2. Пр СИ (с) триггер 16, а вместе с тем и сигналы У 4 и У 2, сбрасываются, аналогично предыдущему черезвновь устанавливаются и т.д. Останов устройства происходит либо по сбросу сигнала Г, либо по сигналу, поступающему на первый вход блока 8 управления.Рассмотрим работу устройства при Формировании однородных цепей Маркова с конечным множеством состояний,На клемму 30 блока 8 управления поступает сигнал,ц., по которому блок 8 формирует последовательность сигналов, приведенную на фиг, 3. О 15 20 По сигналу У 1 регистры 3 и 5 устанавливаются в нулевое состояние. Таккак У 2 в этом режиме не вырабатывается, то регистр 5 постоянно установлен в нуль и на его выходах присутствуют низкие уровни, которые поступают на инверсные вторые входыэлементов И 10 блока 1. 25 ЭО По сигналу УЗ в регистр 3 заноситния сигнал У 4, в результате чего элементы И 10 закрываются и оканчивается случайное испытание. В течение интервала т из ячеек с адресом модулей 12 памяти считываются коды А, =устанавливаются интенсивностипосле чего блок 8 снова вырабатывает сигнал У 4, начинается следующее случайное испытание и т.д. 55 Формирование марковского процесса останавливается при достижении заданного состояния процесса по сбросусигнала М, либо если очередное состояние 1 будет иметь нулевые вероятности перехода Р, а следовательно,65 ся начальное состояние 1 о марковского процесса с клемм 15. Из ячеек с адресом К 0 модулей 12 памяти блока 9 считываются коды Ар,настраивающие генераторы 13 на интенсивности Х , соответствующие вероятностям перехода процесса Р 0 из состоянияв состояниер По сигналу У 4 разрешается прохож дение импульсов с выходом генераторов 13 через блок 1 элементов И 10, и тем самым начинается случайное испытание. Первый прошедший через блок 1 импульс блока 9 ввода проходит через шифратор 2, устанавливает в регистре 3 номер К следующего состояния марковского процесса и од.новременно поступает на элементИЛИ 4, Выходной сигнал СИ элемента 5 О ИЛИ 4 сбрасывает в блоке 8 управлеи нулевые Ак,. Прк этом срабатываютэлементы ИЛИ-НЕ 14, ИЛИ 11, И 7, выходной сигнал которых останавливаетработы блока 8 управления,Рассмотрим функционирование уст -ройства при исследовании связностивероятностных графов. Временная диаграмма сигналов, вырабатываемых блоком 8 в этом режиме при поступлениисигнала Г на клемму 31 блока, приведена на фиг. 4.По сигналу У 1 регистры 3 и 5 устанавливаются в нулевое состояние.Из нулевых ячеек модулей 12 памятиблока 9 считываются коды Ар , Блок 8вырабатывает сигнал У 2 длительностьюв течение которого случайныеимпульсы с выходов генераторов 13 могут устанавливать триггеры регистра5 в единичное состояние, Путем изменения параметров А 0 иьз длительности сигнала У 2 можно в широкихпределах регулировать вероятностиустановки триггеров регистра 5, аследовательно, вероятности существования (надежности) вершин графа.Пусть в регистре 5 поСле окончания У 2 установлены в единицу 1, 3 и12-й разряды, что соответствует несуществующим 1-, 3- и 12-й вершинамграфа. Тогда в блоке 1 всегда будутзакрыты элементы И 10 с номерами1, 3 и 12, Следовательно, в регистре3 никогда не будут установлены номера 1, 3 и 12, чем исключаются путичерез эти вершины.По сигналу УЗ в регистр 3 с шин15 записывается номер М начальнойвершиной графа. Из модулей 12 считываются коды Ар, устанавливаютсяинтенсивности Х р, Вырабатываютсясигналы У 2 и У 4. Начинается случайное испытание, однако прохождениеимпульсов с выходов генераторов 13разрешается только через те схемыИ 10, на инверсных вторых входах которых присутствует низкий потенциал,Первый прошедший через блок 1 импульс блока 9 ввцда проходит черезшифратор 2, устанавливает в регистре 3 номер М следующей вершиной граФа, в регистре 5 устанавливает вединицу М -ый разряд, поступает навход элемента ИЛИ 4, выходной сигналСИ которого сбрасывает в блоке 8сигналы У 4, У 2, тем самым прекращаяиспытание. После интервала л, необходимого на перенастройку генераторов 13, снова вырабатываются У 2и У 4, повторяется случайное испытание.Однако теперь к ранее закрытым элементам И 10 добавилась схема с номером М , благодаря чему запрещаетсяповторная установка в регистре 3 номера , что исключает прохождениепути на графе через одну и ту жевершину дважды.Процесс моделирования пути оканчивается или по сбросу сигнала Гпри достижении заданной вершины графа, или при прохождении всех существующих вершин графа. При этом врегистре 5 установлены в единицувсе разряды, срабатывают все элементы ИЛИ 11 блока б, элемент И 7, посигналу которого блок 8 останавливает устройство. В третьем случаепроцесс моделирования занершаетсяпри достижении вершины графа, вероятность выхода из которой в любуюсуществующую, но еще не пройденнуювершину графа равна нулю. В этомслучае также срабатывают нсе элементы ИЛИ 11, так как часть из нихсрабатывает от установленных в единицу разрядов несуществующих и выполненных вершин, а остальные - отсигналов с выходов элемента ИЛИ-НЕ 14,соответствующих вершинам графа,вероятности перехода в которые равны нулю. 26Таким образом, предлагаемое изобретение обеспечивает возможностиформирования марковских случайныхпроцессов с конечным множеством состояний, исследование связности вероятностных графов с заданными вероятностями существования вершини дуг.Кроме того, применение н блокеввода генераторов потоков случайных Зоимпульсов с автоматически регулируемой интенсивностью потока позноляетавтоматизировать процесс управленияустройством.Однотипность применяемых блоков(генераторы потоков случайных импульсов, блоки памяти) позволяетсоздать основные узлы устройства ввиде интегральных модулей, что упрощает конструирование.40Формула изобретения1Устройство для вероятностногомоделирования, содержащее блок ввода, 5первая группа выходов которого соединена с первой группой входов блока элементов И соответственно, выходы которого через шифратор соединены с входами элемента ИЛИ и с увходами первого регистра сдвига, выход которого является выходом устройства и соединен с вхбдом блока ввода, о т л и ч а ю щ е е с я тем,,что, с целью расширения функциональных возможностей устройства за счетисследования связности вероятностных графов, оно содержит блок управления, элемент И, группу элементовИЛИ, второй регистр сдвига, входыкоторого подключены к первой группе 66выходов блока ввода соответственно,вторая группа выходов которого соединена с первыми входами группы элементов ИЛИ, вторые входы которыхобъединены с второй группой входов 65 блока элементов И и подключены квыходам второго регистра сдвига,вход "Сброс" которого объединен совходом "Сброс" первого регистра сдвига и подключен к первому выходу блока управления, второй и третий выходы которого подключены к входам"Сдвиг" второго и первого регистровсдвига соответственно, четвертыйвыход блока управления соединен стретьей группой входов блока элементов И, выходы группы элементов ИЛИсоединены с входами элемента И, выход которого соединен с первым входом блока управления, второй входкоторого подключен к выходу элементаИЛИ, третий и четвертый входы блокауправления являются соответственнопервым и вторым входами устройства. 2. Устройство по п.1, о т "л ич а ю щ е е с я тем, что блок управления сэдержит триггер, четыре элемента И, четыре элемента ИЛИ, триэлемента задержки и два формирователя импульсов, первый вход блокауправления подключен к первому входу триггера, второй 5-вход которого через первый элемент задержкиподключен квыходу первого элементаИЛИ, первый вход которого объединенс й-входом триггера и является вторым входом блока управления, третийвход которого подключен к первомувходу первого элемента И и к перномувходу второго элемента ИЛИ, выходкоторого соединен с третьим-входомтриггера и через первый формировательимпульсов соединен с первым входомблока управления и с входом второгоэлемента задержки, выход которогосоединен с вторым входом первогоэлемента И, выход которого соединенс первым входом третьего элементаИЛИ, второй вход которого подключенк выходу второго элемента И, первыйвход которого через третий элементзадержки объединен с его вторым входом и соединен с первым входом четвертого элемента ИЛИ, выход которогоявляется вторым выходом блока управления, третий выход которого соединенс выходОм третьего элемента ИЛИ и свторым входом первого элемента ИЛИ,четвертый выход блока управлениясоединен с выходом триггера и с первым входом третьего элемента И,выход которого соединен с вторымвходом четнертого элемента ИЛИ, четвертый вход блока управления соединен с вторыми входами второго элемента ИЛИ, третьего элемента И ис первым входом четвертого элементаИ, второй вход которого подключенк выходу первого формирователя импульсов, выход четвертого элементаИ через второй формирователь импульсов соединен с входом третьего элемента задержки, 8579851211Источники информации,принятые во внимание при экспертизе/1. Авторское свидетельство СССР950419 б, кл, 6 Об Г 1/02, 1974,2. Авторское свидетельство СССР 9433504, кл, 6 Об 6 7/48, 1972.3. Авторское свидетельство СССР 9344431, кл. 6 Об 6 1/02, 1970 (прототип).857985Реыетник Редакто т ПодписноеССР аз 72 4/5 филиал ППП "Патент", г, Ужгород, ул. Проектна Л И Составитель А.КарасовТекредй. Кастелевич Корре 9 Тираж 745ИИПИ Государственного комитет по делам изобретений и открытМосква, Ж, Раушская наб.