Устройство для моделирования марковских процессов

Устройство для моделирования марковских процессов

Иллюстрации

Показать все

Реферат

 

(;, ; )!

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ (») 526909

Сова Советских

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 06.03.75 (21) 2111698/24 с присоединением заявки ¹ (51) М Кч г G 06F 15 36

Совета Министров СССР по делам изобретений н открытий (53) УДК 681.3(088.8) Опубликовано 30.08.76. Бюллетень № 32

Дата опубликования описания 10.12.7б (72) Автор изобретения

В. А. Добрыдень

Харьковский институт радиоэлектроники (71) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ МАРКОВСКИХ

ПРОЦЕССОВ

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

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

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

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

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

Это устройство имеет ограниченные функциональные возможности, что не позволяет моделировать непрерывные случайные процессы (2).

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

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

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

Это достигается тем, что предлагаемое уст15 ройство дополнительно содержит делитель частоты, вход которого соединен с третьим выходом блока управления, счетчик импульсов, вход которого соединен с выходом делителя частоты, преобразователь кодов; первая груп20 па входов которого соединена с выходами счетчика импульсов, вторая группа входов — с разрядными выходами регистра, третья группа входом — с разрядными выходами сумматора, а выходы — с разрядными входами датчика

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

30 выход — к выходу устройства, 526909

На фиг. 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, а также запускающий (синхропнзирующнй) вход. После каждого запускающего импульса аппроксиматор в течение заранее фиксированного времени линейно изменяет напряжение U на выходе от значения, кодируемого содержимым регистра 5, до значения, кодируемого содержи111 мым сумматора 3 (фиг. 2 и 3).

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

Блок управления, спустя некоторое время после поступления импульса на его запускающий вход, генерирует на выходах а — г сдвинутыс во времени короткие импульсы с перио20 дом Т (фиг. 2). Генерирование прекращается после поступления импульса на вход останова (с выхода А сумматора 3) .

Схема работает следующим образом. Рассмотрим сначала режим моделирования одно25 родного процесса с независимыми приращениями.

В исходном состоянии в сумматоре 3 и регистре 5 находится число х„кодирующее требуемое начальное значение U, моделируемого зп случайного процесса U(i), блок управления остановлен (т. е. импульсы на его выходах не генерируются), делитель частоты 8, счетчик 7 и прсобразователь 2 кодов в этом режиме в работе схемы не участвуют (могут быть откЗб лючсны). Датчик случайных чисел настраивается на генерирование нормально распределенных чисел с требующими параметрами.

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

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

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

Ль сформированное к этому времени датчиком

1, и содержимому сумматора, т. е. теперь в сумматоре находится число х,=х,+Ли Через время т„необходимое для окончания процесса суммирования, появляется импульс на выходе г блока управления 10, запускающий аппроксиматор 6 и датчик случайных чисел 1.

Существенно, что Т))т;,+т,.+г,=т (величина т ограничена снизу временем переходных процессов в регистре и сумматоре и имеет порядок микросекунд или их долей, величина Т ограничена снизу быстродействием датчика случайных чисел, поэтому Т превосходит вели65 чину т на несколько порядков. Вследствие это526909

55 нем.

ro переходными процессами в аппроксиматоре в течение времени т при смене содержимого регистра и сумматора можно пренебречь, от них легко избавиться, например, при помощи простого фильтра. Величина т,, выбирается такой, чтобы за время т,,+т датчик случайных чисел закончил формирование первого числа Л1.

С момента запуска аппроксиматора напрлжение на его выходе начинает линейно изменяться от значения U, до значения UI, соответствующего числу х в сумматоре 3. причем это изменение заканчивается за время Т вЂ” т (можно считать, что практически изменение напряжения на выходе аппроксиматопа 6 от

U; до U;+ осуществляется за воемя Т между импульсами на его запускающем входе).

Далее работа схемы протекает аналогично описанному: очередной импульс управления, появляющийся на выходе а блока управления, сбрасывает оегистр в нуль, импульс с выхода б передает в регистр содержимое сумматора х1, импульс с выхода в формирует в сумматоре число х =х,+Л, импульс с выхода г вновь запускает датчик случайных чисел, формирующий теперь приращение Л. и аналоговый аппроксиматор, линейно изменяющий за впемл

T очередного такта выходное напряжение от уровня Ul до уровня U2, соответствующего числу х в сумматоре. Формируемая таким образом реализация (,11 1) (фиг. 3). Если в результате суммирования получаетсл число, превосходящее емкость сумматора, на его выходе А появляется импульс переполнения, прекращающий работу блока управления, снабженного соответствующей индикацией.

Формируемь1й процесс является детермпниpoRaIII!Ilail в промежутках времени между тактовыми импульсами, однако и.,1еет независимые прирашснил па интервалах времени, равных илп больших Т.

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

При моделировании неоднородного процесса с независимыми приращениями (т. е. с параметрами распределения приращений, зависягцимп от «рсменп) в работе схемы участву1ОТ Также C IeT IIIK II IIII . II COII 7, де I IITE. II. часTOты 8 и преобразователь кодов 2, остальные элементы схемы работают аналогично описанному. Счетчик 7, суммируя импульсы, поступающие через делитель 8 с выхода в блока управления 10, ведет, по сути, отсчет времени.

Преобразователь кодов настраивается на воспроизведение требующейся зависимости параметров распределения чисел Л; от времени (т. е. от величины 1, фиксируемой счетчиком

7), остальные входы преобразователя 2 ппи этом формировании выходных кодовых комбинаций не участвуют, т. е. могут быть отключе10

Зо

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

При моделировании однородного непрерывного марковского процесса счетчик 7 и делитель 8 отключены, в работе участвует преобразователь кодов, причем используются лишь его входы, соединенные с выходами сумматора. Преобразователь 2 настраивается на воспроизведение требующейся зависимости параметров распределения величины приращения процесса Л от величины х (содержимого сумматора, т. е. текущего значения процесса). Если аналогично описанному выше подключить счетчик 7. делитель частоты 8 и соответственно настроить преобразователь 2 (с использованием входов, соединенных со счетчиком 7), получают неоднородный марковский процесс, распределение величины х„ь1 зависит как от величины х; так и от величины 1 (т. е. от времени) .

Используя также входы преобразователя 2, соединенные с выходами регистра 5, получают требуемую зависимость распределения величины Л1 одновременно от величины х;, х; 1.

Устройство также можно использовать для моделирования менее часто встречающихся в практике процессов с независимыми значениями. С этой целью достаточно отключить входы преобразователя 2. соединенные с выходами регистра 5, а также входы, соединенные с выходами сумматора 3 (т. е. ликвидировать зависимость распределения величины Л; от величины х; и х; I), а сумматор 2 перед каждым суммированием устанавливать в нуль, т. е. использовать его в роли регистра. При этом в регистре 5 и сумматоре Формируются числа Л; и Л;+1 соответственно. являющиеся независимыми, аппрокспматор 6 строит пх линейную огибающую аналогично описанному выше.

Устройство может также моделировать многосвязные марковские процессы, у которых распределение величины зависит от нескольких предыдущих значений: х; х; ., х;-„. Для этого следует лишь использовать и регистров, включенных аналогично регистру 5, так что в каждом такте солержимое fz-ro регистра передается в (Й+ 1)-й.

На выходах сумматора 3 в описанных выше режимах моделируются случайные последователш1остп соответствующих типов, которые Могут быть непосредственно использованы при моделировании стохастическпх объектов. Подкл1очал к выходу сумматора обычный цифроаналогoBbIII преобразователь. можно получить процесс соответствующего вида с конечным множеством значений и непрерывным времеФормул а изобретения

Устройство для моделирования марковских процессов, содержащее блок управления, пергый вход которого подключен к входу устрой526909 ства, регистр, Вход которого подключен к первому выходу блока управления, блок элементов «И», вход которого подключен к второму выходу блока управления, а разрядные выходы — к разрядным входам регистра, сумматор, вход которого подключен к третьему выходу блока управления, разрядные выходы — к разрядным входам блока элементов «И», а выход — к второму входу блока управления, элемент «ИЛИ», первый вход которого подключен к входу устройства, а второй вход — к четвертому выходу блока управления, датчик случайных чисел, вход которого подключен к выходу элемента «ИЛИ», а разрядные выходы— к разрядным входам сумматора, отличающ е е с я тем, что, с целью расширения класса решаемых задач, устройство дополнительно содержит делитель частоты, вход которого соединен с третьим выходом блока управления, 5

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

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

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

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

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

526909

/7уг г

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

Техред 3. Тараненко Корректор Л. Денискина

Редактор Т. Рыбалова

Типография, пр. Сапунова, 2

Заказ 2314/7 Изд. № 1650 Тира>к 864 Подписное

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

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