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

 

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ МАРКОВСКИХ ПОТОКОВ СИГНАЛОВ, содержащее генератор случайного кода, генератор тактовых импульсов, блок элементов ИЛИ, блок элементов И, блок памяти и блок задания закона распределения , состоящий из п идентичных узлов; каждый из которых содержит группу регистров, группу сумматоров, первую и вторую группы элементов И, группу схем сравнения, разрядные входы регистров всех узлов блока, задагния закона распределения являются соответствующими установочными входами устройства, а в каждом узле выходы первого -регистра группы соедо1иены с первыми входами соответствующих элементов И первой группы, выходы k-ro регистра группы (, п) сое динены соответственно с входами первой группы (It-l)-ro сумматора группы, вторая группа входов первого сумматора группы соединена соответствен о с выходами первого регистра группы, вторая группа входов М-го сумматора группы (, п-1) Соединена соответifrMbrf .-. ла д ствеино с выходайи (M-l)-ro сумматора группы, выходы всех сумматоров группы подключены к первым входам соответствующих элементов И первой группы, выходы которых соединены с входами первой группы соответствующих схем сравнения группы, выход k-ft схемы сравнения группы соединен с прямым входом (k-l)-ro элемента И второй группы, выход р-й сравнения группы (, п-1) подключен к р-м инверсным входам элементов И второй группы с номером, большим р, выход первой схемы сравнения группы и выходы элементов И второй группы являются соот .ветствующими выходами узла блока (Л задания закона распргеделения, одноименные выхода узлов блока задания закона расйределения подключены к соответствующим входам одноименного ; элемента ИЛИ блока элементов ИЛИ-, tвыходы которых подключены соответственно к первым входам элементови блока элементов И, вторые входы кото00 00 рых объединены и подключены к выходу генератора тактовых импульсов и входу запуска генератора случайного кода, выходы элем1ентов И блока элементов И 4 соединены с соответствукяцими входами блока памяти, выходы которого подклю-. чены к вторым объединенным входам элементов И первой группы сортветствующего узла блока задания закона распределения, входы второй группы схем сравнения которого подключены соответственно к выходам генератора случайного кода, отличающее с я тем, что, с целью расширения функциональных возможностей путем мо

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСтИЧЕСНИХ

РЕСПУБЛИК

y g G 06 F l5/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3551274/18-24 (22) 09.02.83 (46) 23.04.84, Вюл..й 1 5 (72) В. И,. Финаев (71) Таганрогский радиотехнический институт им. В. Д. Калмыкова (53) 681.333(088.8) (56) 1, Авторское свидетельство СССР

NI 450178, кл. G 06 F 15/20, 1973 °

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

Ф 807309, кл. G 06 F !5/20, 1979, 3. Авторское cïèäåòåëüñòâî СССР

1! 645162, кл. С 06 F 15/20, 1977. (прототип). (54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ МАРКОВСКИХ ПОТОКОВ СИГНАПОВ, содержащее генератор случайного кода, генератор тактовых импульсов, блок элементов ИЛИ, блок элементов И, блок .памяти и блок задания закона распределения, соСтоящий из п идентичных узлов; каждый из которых содержит группу регистров, группу сумматоров, первую и вторую группы элементов И„ группу схем сравнения, разрядные входы регистров всех узлов блока зада.ния закона распределения являются соответствующими установочными входами устройства, а в каждом узле выходы первого регистра группы соеди. иены с первыми входами соответствующих элементов И первой группы, выходы k-го регистра группы (k=2, n) соединены соответственно с входами первой группы (k-1)-ro сумматора группы, вторая группа входов первого сумма" тора группы соединена соответствен но с выходами первого регистра группы, вторая группа входов М-го cjMMaTOps группы (M=2, и-1) соединена соответ",Л0„„1 88004 A ственно с выходайи (М-1)-го сумматора группы, выходы всех сумматоров группы подключены к первым входам соответствующих элементов И первой группы, выходы которых соединены с входами первой группы соответствующих схем сравнения группы, выход k-й схемы сравнения группы соединен с прямым входом (k-!)-ro элемента И второй группы, выход р-й схемы сравнения группы (р=l, n-l) подключен к р-м инверсным входам элементов И второй группы с номером, большим р, выход первой схемы сравнения группы и выходы элементов И второй группы являются соответствующими выходами узла блока задания закона распределения, одноименные выходы узлов блока задания закона распределения подключены к соответствующим входам одноименного, элемента ИЛИ блока элементов ИЛИ;

1выходы которых подключены соответ1 ственно к первым входам элементов И блока элементов И, вторые входы которых объединены и подключены к выходу © генератора тактовых импульсов и входу. 00 запуска генератора случайного кода, C? выходы элементов И блока элементов И Ю соединены с соответствующими входами 4аЬ блока памяти, выходы которого подклю-. чены к вторым обьединенным входам элементов И первой группы соответствующего узла блока задания закона,фЬ распределения, входы второй группы схем сравнения которого подключены соответственно к выходам генератора случайного кода, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей путем мо1088004

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

«зищаееерегистра, с входами первой груюиы первого и второго блоков срав1

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

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

ЗАПРЕТ, реверсивный счетчик, многока- 1О иаиъиый блок случайных временных задержек, первый и второй элементы ИЛИ, баек сравнения, элемент И,первый, второй и третий счетчики, блок элементов И,ге— иератор импульсов, причем выход перво-15 го генератора случайного потока импульсов соединен с первым счетчиком .и через элемент ЗАПРЕТ с многоканальиын блоком случайных временных задержек и суммирующим входом ревер- 20

c3t3N0Fo счетчика, выход которого соедиыещ через блок сравнения с первым входом первого элемента ИЛИ, выход которого соединен с управляющими входами элемента И и элемента ЗАПРЕТ, сигиапыаий вход элемента И соединен с входом первого счетчика, а выход элемента И соединен с входом второго счетчика, выход второго генератора случайного потока импулъсов соединен 30 с вторым входом первого элемента ИЛИ и aepsw входом генератора .импульсов, выход которого соединен с входом третьего счетчика и через второй эле мент ИЛИ с вычнтающим входом ревер- .35 сивного счетчика, разрядные выходы которого соединены через блок элементов И с вторым входом генератора импулъсов, а выход многоканального блока случайных задержек соединен с 4О нения, вторые группы входов которых подключены соответственно к разрядным выходам регистра, выходы первой и вто" рой схем сравнения являются соответственно первым и вторым выходами устройст. ва,выходы первого и второго элементов задержки подключены соответственно к входу разрещения записи и входу сброса регистра,а выход третьего элемента задержки соединен с входами разрешения сравнения первой н второй схем сравнения. другим входом

ИЛИ Г 1.

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

Известно устройство для моделирования систем массового обслуживания, содержащее первый и второй генераторы случайных потоков импульсов, генератор импульсов, первый и второй счет» чики, первый и второй реверсивные счетчики, элемент ЗАПРЕТ, элемент задержки, многоканальный блок случайных временных задержек, первый, второй, третий, четвертый и пятый элементы

ИЛИ, первый, второй и третий элементы И, блок элементов И, блок синхронизации, сумматор, пороговый эле" мент, формирователь и переключатель, причем выход первого генератора случайного потока импульсов соединен с входом первого счетчика и с первым входом первого элемента ИЛИ, выход которого соединен с первым входом элемента ЗАПРЕТ, выход которого соединен с суммирукицим входом первого реверсивного счетчика и с входом многоканального блока случайных временных задержек, выход которого соединен с первым входом второго элемента ИЛИ, выход которого соединен с вычитающим входом первого реверсивного счетчика, выход которого через пороговый элемент соединен с первым входом.третъе%

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

ЗАПРЕТ и с первым входом второго элемента И, второй вход которого объединен с входом первого счетчика, первый 10 и второй выходы блока синхронизации соединены соответственно с управляющими входами блока элементов И и сум" матора, входы которого соединены с выходами блока элементов И соответственно, входы которого подсоединены .к разрядным выходам второго реверсив. ного счетчика и через четвертый элемент ИЛИ соединены. с первым входом третьего элемента И, второй вход которого подключен к первому выходу переключателя, второй выход которого соединен с входом второго реверсивногс счетчика, выход третьего эгемента И через элемент задержки соединен с вто- 25 рым входом первого элемента И и непосредственно с вычитающим входом второго реверсивного счетчика, суммирующий вход которого соединен с- выходом пятого элемента ИЛИ, входы кото- з, рого соединены с выходом второго элемента И и с третьим выходом,переключателя соответственно, входы которого соединены, соответственно с выходом генератора импульсов и с выходом

35 шестого элсмента ИЛИ, входы которого соединены соответственно с первым вхоДом второго элемента ИЛИ и через формирователь серии импульсов — с входом генератора импульсов P2).

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

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

И, вторые входы которого соединены с выходами блока элементов ИЛИ, входы

I которого соединены с выходами блока. задания законов распределений, третьи входы которого соединены с выходами устройства и выходами блока памяти, входы которого соединены с выходами блока элементов И ГЗ).

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

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

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

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

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

g-го регистра группы (=2,n) соединены соответственно с входами первой

10880

S группы (1(-1)-го сумматора группы, вторая групйа входов первого сумматора группы соединена соответственно с выходами первого регистра группы, ° вторая группа входов М-го сумматора

5 группы 912, 6 -1) соединена соответственно с выходами Olh-1)-го сумматора группы, выходы всех сумматоров руппы подключены к первым входам соответствующих элементов И первой rp группы, выходы которых соединены с входами первой группы соответствующих схем сравнения группы,выход Р-й схемы сравнения группы соединен с прямым входом (k-1)-го элемента И второй груп" 5 пы, выход .Р-й схемы сравнения группы (P l, h-1) подключен к P-м инверсным входам элементов И второй группы с номером, болыаим Р, выход первой схемы сравнения группы и выходы элементов И второй группы являются соответствующими выходами узла блока задания закона распределения, одноименные выходы узлов блока задания закона распределения подключены к соответствующим входам одноименного элемента ИЛИ блока элементов ИЛИ, выходы которых подключе. ны соответственно к первым входам элементов И блока элементов И, вторые входы которых объединены и подключены к выходу генератора тактовых импульсов и входу запуска генератора случайного кода, выходы элементов И блока элементов И соединены с соответствующими входами блока памяти, выходы которого подключены к вторым объединенным входам элементов И первой группы соответствующего узла блока задания закона распределения, входы вто" рой группы схем сравнения которого подключены соответственно к выходам

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

04 Ь и входу сброса регистра, а выход третьего элемента задержки соединен с входами разрешения сравнения первой и второй схем сравнения.

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

Устройство для моделирования систем массового обслуживания (фнг. 1) содержит .группу установочных входов 1, блок 2 задания закона распределейия, генератор 3 случайного кода, генератор 4 тактовых импульсов, первый 5, второй 6 и третий 7 элементы задержки, блок 8 элементов И, блок 9 элеменI %/ тов ИЛИ, регистр 10, первый 1! и второй 12 блоки сравнения, причем второй блок 12 сравнения реализован аналогично первому блоку 11 сравнения, группу выходов 13, блок 14 памяти, первый и второй выходы 15 и 16.

Блок 2 задания закона распределения содержит и однотипных узлов, каждый иэ узлов блока 2 включает группу регистров .17, вторую группу входов 18, соединенную с соответствующими выходами генератора 3, группу схем 19. сравнения, первую группу элементов

И 2, выход 13; для каждого узла, сое диненный с соответствующим i-м выходом 13 устройства, вторую группу элементов И 21, группу сумматоров 22, группу выходов 23.

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

По установочным входам 1 в регистры 17 блока 2 задания закона распределения заносятся. коды матрицы вероятностей перехода системы массового обслуживания. При этом в регистр 17 заносится вероятность P- -перехода

1J системы в р. -е состояние, при условии, что она в предыдущий момент вре" мени находилась в 1-м состоянии.

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

1088004

0 0

0.. О ht 14 4 t О 0 0

11/44

1-р.4

ItN44

О 0

1+сСИ аМ

1+Ы,М

1- 41

1+о 4 и дФ

1+e444

0 0

1-,Ы Ь

1+дСМ

1+о дФ

30

Рассмотрим формирование матрицы йереходных вероятностей для и канальной системы. ВсеЪ каналов абсолютно идентичны, освободившийся канал занимает первое в очереди требование. 5

ВЕроятности >ac=1-С М, PO1=OL4t а вероятности Рой ° РоЭ» P равны

on нулю как величины высшего порядка малости по сравнению с Р и Р 1 где с интенсивность входящего пуассоновско= го потока требований на обслуживание.

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

Предположим, что моделируется система с 1.приборами и максимально возможным числом требований в системе, равным 11, Тогда наличие сигнала на первом выходе 13> говорит о том, что в системе нет требований и все приборы свободны, наличие сигнала на выходе. 13 в системе одно требование и занят один канал, а наличие сигнала на выходе

13 — заняты два прибора.. Если сигнал на выходе 131,Ä1 то заняты обслуживанием .все Ж приборов. Если сигнал на выходе

132, то В приборов заняты и в очереди Ю-,(1+4) требований. 55

Интервалы времени д1 выбираются значительно меньше по величине, чем

;евши /А,. Причем чем меньшеД, тем больше

Вероятность P1g=pht Р, 1 p <, a вероятность Р1® распределяется из усло.вия поступления в систему очередного требования, т.е. P УФ,, где

„ц. — интенсивность потока .обслуживания. Вероятности Р g О. (i = 3, П). Вероятности Р,16

P q2. нормируются.

В целом матрица переходных вероятностей имеет вид точность моделирования, однако в этом случае увеличивается время моделирования, Генератор 4 тактовой частоты задаеч интервалы времениЮ1, равные периоду следования его импульсов.

Устройство работает следующим образом.

Начальное состояние устройства для моделирования предусматривает наличие сигнала на выходе 13, т.е. в системе

1 массового обслуживанйя нет требований.

По установочным входам 1 в регистры 17 олока 2 задания закона распределений внесены коды Р; матрицы P. С приходом

Ч импульса генератора 4, который подается на входы первого. 5, второго 6 и третьего 7 элементов задержки времени. на первый вход блока элементов И 8 и вход генератора 3 случайного кода, в нем вырабатывается код числа, равномерно распределенного в интервале от нуля до единицы, Так как на выходе 13 имеется потея. циал, то по входу 131 блока 2 подается потенциал, элементы И 20 первого узла

4 10 .чае срабатывают схемы 19 -1Я равнеjz 1Р ния. Сигнал с выхода схемы 191 сравнения закрывает элементы И 21 -21 „ „ и на выходе 132 блока 2 появляется потенциал, который проходит через блок 9 элементов ИЛИ, блок 8 элементов И на второй вход блока 14 памяти и на выходе 13 устройства появляется потенциал. Это моделирует случай прихо да в систему требрвания за интервал 4Й и принятия его на обслуживание. В системе занят один канал обслуживанием, Наличие сигнала на выходе 132 свидетельствует о занятости обслуживанием в системе одним каналом одного требования и отсутствие очереди в системе.

4 появлением импульса на выходе третьего элемента 7 задержки на входы блоков 11 и !2 сравнения подается потенциал. Так- как на выходах регистра

l0 снимается код 1000..., подаваемый на одни входы блока .11, а на другие его входы подается код 01000..., ко" торый меньше кода 10000..., то на выходе блока ll сравнения появляется . потенциал, который подается на выход 15. Появление потенциала на выходе

15 свидетельствует о приходе в систему требования в отсчет времени, задаваемый генератором 4, и о занятии обслуживанием одного канала, На фиг. 3 показано, что и за шестой интервал ДМ в систему поступает еще одно требование и занят обслуживанием второй канал, так как сигнал появляется на выходе-13> устройства и на выходе 15.

Если же за какой-либо интервал,ДФ будет закончено обслуживание требования, то в этом случае сигнал появляется на выходе 13 по порядковому номеру индекса, меньшему на единицу, чем 13 ° + В этом случае срабатывает

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

Таким образом, в процессе моделирования системы массового обслуживания возможно получить модель входного потока сообщений по анализу потока импуль-. сов на выходе 15, модель выходного потока сообщений — по анализу потока импульса на выходе 16, модель занятости системы обслуживания (период занятости) требований — по анализу потенциалов иа выходах 13, 45

9 108800 блока 2 открыты.и коды регистра 17д, а также сумматоров 2211«221 . подаются. на вторые входы схем 19j<-19„сравнения.

Если в регистрах 17! -1 „хранятся коды Рбб, Ро, Р02, Цц, п, то на выходах регистра 17„ и сумматоров

22 "22; сформировываются коды, 1 и-q ю

Р, Р +Р „, Р Р, +Рб,...,Р

+ О1 -- ОаПричем сумма последнего элемейта строки равна единице.

Предположим, что генератор 3 сгенерировал случайный код А,.численная величина которого меньше величины 15 кода Р . Данный код подается на входы схем 1911-191„, Так как код А меньше по величине кодов, подаваемых на другую группу входов схем 19 сравнения, то на их выходах появляются по- 20 тенциалы, причем потенциал с выхода, схемы 19 сравнения закроет все элементы И 21 и сигнал появится только на выходе 23, блока 2, l1

Данный сигнал поступает через блок 25

9 элементов HJIH. Тогда с выхода 131 вновь снимается. потенциал (фиг, 3), т.е. эа время Дф в систему массового обслуживания заявок не поступает, По заднему фронту сигнала генератора 4 З0 через первый элемент 5 задержки в регистр 10 происходит запись нового состояния выходов 13. Причем перед этим по переднему фронту импульса генератора 4 с незначительной задержкой, формируемой третьим элементом 7 задержки, в блоках 11 и 12 сравнения происходит сравнение чисел регистра

10 и нового состояния выходов 13 в позиционном коде. Так как изменений не40 происходит, то на выходах первого 11 и второго 12 блоков сравнения сигналов нет. После сравнения второй элемент 6 задержки сбрасывает регистр 10 в нулевое состояние, т.е. процесс сравнения с предыдущим кодом выходов 13 происходит перед записью нового состояния выходов 3 в регистр 10, Предположим, (фиг. 3), что лишь за четвертый интервал ДФ в систему массо50 ваго обслуживания поступило сообщение.

Рассмотрим, как это моделируется в системе.

С приходом четвертого импульса от генератора 4 тактовых импульсов re55 нератор 3 случайного кода генерирует код, величина которого меньше числа

1 <+Р1.1, но больше числа Р В этом слу3088004

)088004 4 2 АЗ

1088004

Составитель В. Фукалов

Редактор И. Шулла Техред В.Далекорей

Корректор Ю.Макаренко

«Ь

Заказ 2674/46 Тираж 699

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

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

Подписное

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