Устройство для моделирования марковских процессов Советский патент 1976 года по МПК G06F7/58 G06F15/173 G06F17/00 G06F7/70 

1

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

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

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

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

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

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

Такое устройство не позволяет моделировать процессы с независимыми приращениями.

Цель изобретения - расширение класса решаемых задач.

Это достигается тем, что предлагаемое устройство дополнительно содержит делитель частоты, вход которого соединен с третьим выходом блока управления, счетчик импульсов, вход которого соединен с вы.ходом делителя частоты, преобразователь кодов; первая группа входов которого соединена с выходами счетчика импульсов, вторая группа входов - с разрядными выходами регистра, третья группа входом - с разрядными выходами сумматора, а выходы - с разрядными входами датчика случайных чисел, и аналоговый аппроксиматор, вход которого подключен к четвертому выходу блока управления, первая группа входов - к разрядным выходам сумматора, вторая группа входов - к разрядным выходам регистра, а выход - к выходу устройства. На фиг. 1 показана блок-схема устройства на фиг. 2 приведены временные диаграммы ра боты устройства (а, б, в, г - сигналы на выходах блока управления, д - содержимое регистра, е - содержимое сумматора, ж - сигнал на выходе датчика случайных чисел, з - сигнал на выходе аналогового аппроксиматора переходные процессы показаны условно как линейные); на фиг. 3 - сформированпая устройством реализация моделируемого процесса в ином, чем на фиг. 2 масштабе времени. Устройство содержит датчик 1 случайных чисел, преобразователь 2 кодов, сумматор 3, блок 4 элементов «И, регистр 5, аналоговый аппроксиматор 6, счетчик 7 импульсов, делитель 8 частоты, элемент «ИЛИ 9, блок 10 управления. Входы датчика 1 случайных чисел соединены с выходами преобразователя 2, а выходы - с входами сумматора 3, выходы которого подключены к входам анпроксиматора 6, к входам преобразователя 2 и через блок элементов «И 4 - к входам регистра 5, выходы которого подключены к входам апнроксиматора 6 и к входам преобразователя 2. Выходы блока управления 10 соединены с входами аппроксиматора 6, регистра 5, блока элементов «И 4 и сумматора 3, выход которого соединен с входом блока управления 10. Вход устройства подключен к первому входу элемента «ИЛИ 9 и к входу блока управления 10, один из выходов которого соединен с вторым входом элемента «ИЛИ, выход которого подключен к входу датчика 1 случайных чисел. Вход делителя соединен с выходом блока управления 10, а выход - с входом счетчика 7, выходы которого соединены с входами преобразователя 2. Датчик случайных чисел выполнен управляемым- распределение вероятностей генерируемых им чисел определяется согласно задаваемому ранее закону кодовой комбинацией, присутствующей на его управляющих входах (т. е. кодовой комбинацией с выхода преобразователя кодов 2). Датчик формирует на выходах случайное число в параллельной двоичной потенциальной форме после каждого импульса, поступающего на его запускающий вход. Преобразователь 2 формирует на выходах кодовые комбинации по заранее задаваемому закону из совокупности кодовых комбинаций, присутствующих на его трех группах входов - от счетчика импульсов 7, от сумматора 3 и от регистра 5. Сумматор 3 при поступлении импульса на его управляющий вход прибавляет число, присутствующее на входах, к своему содержимому. Если при этом происходит переполнение сумматора, на его выходе а появляется импульс. Регистр 5 служит регистром памяти. Многоразрядный логический элемент «И в момент поступления сигнала на его импульсный вход передает содержимое сумматора 3 в регистр 5. Аналоговый аппроксиматор имеет две группы входов, соединенных соответственно с выходами регистра 5 и сумматора 3, а также запускающий (синхронизируюи1,нй) вход. Иосле каждого запускающего импульса апироксиматор в течение заранее фиксированного времени линейно изменяет напряжение U на выходе от значения, кодируемого содержимым регистра 5, до значения, кодируемого содержимым сумматора 3 (фиг. 2 и 3). Делитель частоты выполнен управляемым- требуемый коэффициент деления устанавливается перед началом работы и может изменяться во время моделирования реализации процесса (например, по заданной программе). Блок управления, спустя некоторое время после поступления импульса на его запускающий вход, генерирует на выходах а-г сдвинутые во времени короткие имнульсы с периодом Г (фиг. 2). Генерирование прекращается после поступления импульса на вход останова (с выхода А сумматора 3). Схема работает следующим образом. Рассмотрим сначала режим моделирования однородного процесса с независимыми приращен и я м и. В исходном состоянии в сумматоре 3 и регистре 5 находится число ло, кодирующее требуемое начальное значение U моделируемого случайного процесса {i}, блок управления остановлен (т. е. импульсы на его выходах не генерируются), делитель частоты 8, счетчик 7 и преобразователь 2 кодов в этом режиме в работе схемы не участвуют (могут быть отключены). Датчик случайных чисел настраивается на генерирование нормально распределенных чисел с требуюн1ими параметрами. Иуск схемы осуществляется подачей импульса на запускающий вход блока управления. Этот же импульс через элемент «ИЛИ поступает на запускаюп ий вход датчика случайных чисел. Спустя время та импульс с выхода а блока управления сбрасывает в нуль регистр 5, спустя необходимое для этого время TG появляется импульс на выходе б блока управлеиия 10, передающий в регистр 5 содержимое сумматора 3 (в первом такте он, следовательно, возвращает регистр в исходное состояние), спустя необходимое для этого время Тв импульс с выхода е блока управления 10 побуждает сумматор 3 прибавить случайное число Дь сформированное к этому времени датчиком I, и содержимому сумматора, т. е. теперь в сумматоре находится число Xi ;iCo-f АЬ Через время Тг, необходимое для окончания процесса уммирования, появляется имнульс на выходе г блока управления 10, запускающий аппрокиматор 6 и датчик случайных чисел 1. Существенно, что 7 тб-|-Тв+гг т (величиа т ограничена снизу временем переходных роцессов в регистре и сумматоре и имеет поядок микросекунд или их долей, величина Т граничена снизу быстродействием датчика лучайных чисел, поэтому Т превосходит велиину т на несколько порядков. Вследствие этого переходными процессами в аппроксиматоре в течение времени т при смене содержимого регистра и сумматора можно пренебречь, от них легко избавиться, например, при помощи простого фильтра. Величина тп выбирается такой, чтобы за время датчик случайных чисел закончил формирование первого числа AI. С момента запуска аипроксиматора напряжение на его выходе начинает линейно изменяться от значения f/o До значения t/i, соответствуюн1,его числу Xi в сумматоре 3. причем это изменение заканчивается за время Т-т (можно считать, что практически изменение напряжения на выходе аппроксиматооа 6 от Ui до /,-+ осуществляется за время Г между импульсамп на его запускающем входе). Далее работа схемы протекает аналогично описанному: очередной импульс управлепия, появляющийся на выходе а блока управлепия, сбрасывает регистр в нуль, импульс с выхода б передает в регистр содержимое сумматора Xi, импульс с выхода в формирует в сумматоре число X2 Xi+A2, импульс с выхода г вновь запускает датчик случайных чисел, формирующий теперь приращение Дз. и аналоговый аппроксиматор, линейно изменяющий за воемя Т очередного такта выходное напряжение от уровня f/1 до уровня Uz, соответствующего числу Xz в сумматоре. Формируемая таким образом реализация U(t) (фиг. 3). Если в результате суммирования получается число, превосходящее емкость сумматора, па его выходе А появляется импульс переполнения, прекрай1.ающий работу блока управления, снабженного соответствующей индикацией. Формируемый процесс является детерминированным в пролежутках между тактовыми имплльсами. однако имеет иезависммые прираптения на пптервалах времени, равных или больших Т. Величина Т при использовании современных быстродействующих датчиков случайных чисел может быть сделана на столько малой, чтобы выходной сигнал устройства с достаточной для аналогового моделирования точностью мог быть использован как непрерывный процесс с независимыми приращениями. При моделировании неоднородного процесса с независимыми приращениями (т. е. с параметрами распределения приращений, зависяпщмп от времени) в работе схемы участвуют также счетчик импульсов 7, де.чптель частоты 8 и преобразователь кодов 2, остальные элементы схемы работают аналогично описанному. Счетчик 7, суммируя импульсы, поступающие через делитель 8 с выхода в блока управления 10, ведет, по сути, отсчет времени. Преобразователь кодов настраивается на воспроизведение требующейся зависимости параметров распределения чисел Д,- от времени (т. е. от величины i, фиксируемой счетчиком 7), остальные входы преобразователя 2 ппи этом формировании выходных кодовых комбинации не участвуют, т. е. могут быть отключены от выходов регистра 5 и сумматора 3 соответственно. Наличие делителя частоты 8 обеспечивает возможность изменения масштаба времени указанной зависимости. При моделировании однородного непрерывного марковского процесса счетчик 7 и делитель 8 отключены, в работе участвует преобразователь кодов, причем используются лишь его входы, соединенные с выходами сумматора. Преобразователь 2 настраивается на воспроизведение требуюшейся зависимости параметров распределения величины приращения процесса Д от величины х (содержимого сумматора, т. е. текуш,его значения проиесса). Если аналогично описанному выше подключить счетчик 7. делитель частоты 8 и соответственно настроить преобразователь 2 (с использованием входов, соединенных со счетчиком 7), получают неоднородный марковский процесс, распределение величины x,-+i зависит как от величины х, так и от величины i (т. е. от времени). Используя также входы преобразователя 2, соединенные с выходами регистра 5, получают требуемую зависимость распределения величины М одновременно от величины Xi, X,. Устройство также можно использовать для моделирования менее часто встречающихся в практике процессов с независимыми значениями. С этой целью достаточно отключить входы преобразователя 2. соединенные с выходами регистра 5, а также входы, соединенные с выходами сумматора 3 (т. е. ликвидировать зависимость распределепия величины Д, от величины Х; и x,), а сумматор 2 перед каждым суммированием устанавливать в нуль, т. е. использовать его в роли регистра. При этом в регистре 5 и сумматоре Формируются числа Д, и Д,-+1 соответственно, являющиеся независимыми. аппрокспматор 6 строит пх линейную огибающую аналогично описанному выще. Устройство может также моделировать многосвязные марковские процессы, у которых распределение величины зависит от нескольких предыдущих значений: x;-i, х,, ..., х,--,,. Для этого следует лишь использовать п регистров. включенных аналогично регистру 5, так что в каждом такте содержимое -го регистра передается в (-f 1)-й. На выходах сумматора 3 в описанных выще режимах моделируются случайные последовательности соответствующих типов, которые могут быть непосредственно нспользованы при моделировании стохастических объектов. Подключая к выходу сумматора обычный цифроаналоговый преобразователь, можно получить процесс соответствующего вида с конечным множеством значений и непрерывным временем. Ф о р т у л а изобретения Устройство для моделирования марковских процессов, содержащее блок управления, первый вход которого подключен к входу устройства, регистр, вход которого подключен к первому выходу блока управления, блок элементов «И, вход которого подключен к второму выходу блока управления, а разрядные выходы- к разрядным входам регистра, сумматор, вход которого подключен к третьему выходу блока управления, разрядные выходы - к разрядным входам блока элементов «И, а выход- к второму входу блока управления, элемент «ИЛИ, первый вход которого подключен к входу устройства, а второй вход-к четвертому выходу блока управления, датчик случайных чисел, вход которого подключен к выходу элемента «ИЛИ, а разрядные выходы- к разрядным входам сумматора, отличающееся тем, что, с целью расширения класса решаемых задач, устройство дополнительно содержит делитель частоты, вход которого соединен с третьим выходом блока управления.

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

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

1.Авт. св. № 292281, G 06F 15/36, 1969.

2.Авт. св. № 333667, G 06G 7/52, 1970.

3.Авт. св. № 437061, G 06F 1/02, 1973.

Bbiwd

Ж

Фиг.З

Фиг 2.