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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИРЕСПУБЛИК 800 Р 15 20 НОМИТЕТ СССР ТЕНИЙ И ОТКРЫТИЙГОСУДАРСТВЕННЫ ПО ДЕЛАМ ИЗОБР БРЕТЕНИЯЬСТВУ(71) Таганрогский радиотехнический институт им. В, Д, Калмыкова (53) 681.333(088.8)(56) 1, Авторское свидетельство СССР У 450178, кл. С 06 Р 15/20, 19732. Авторс" е свидетельство СССР Ф 807309, кл. С 06 Р 5/20, 979,3. Авторское свидетельство СССР Иф 645162, кл. С 06 Р 15/20, 1977. (прототип).(54)(57) УСТРОЙСТВО ДПЯ МОДЕЛИРОВАНИЯ МАРКОВСКИХ ПОТОКОВ СИГНАПОВ, со- . держащее генератор случайного кода, генератор тактовых импульсов, блок элементов ИЛИ, блок элементов И, блок .памяти и блок задания закона распределения, соСтоящий из п идентичных узлов; каждый из которых содержит группу регистров, группу сумматоров, первую и вторую группы элементов И группу схем сравнения, разрядные входы регистров всех узлов блока зада.- ния закона распределения являются соответствующими установочными вхо" дами устройства, а в каждом узле выходы первого регистра группы соеди иены с первыми входами соответствующих элементов И первой группы, выходы К-го регистра группы (1=2, п) соединены соответственно с входами первой группы (К)-го сумматора группы, вторая группа входов первого сумма" тора группы соединена соответствен,(но с выходами первого регистра группы, вторая группа входов М-го сумматора группы (М=2, и) соединена соответ")-го сумматосумматоров выходами (М выходы все ключены к п ующих элем пы, выходыс входами ственно с ра группы группы по соответст вой груп соединены В 15 рвым входамнтов И пе которых рвой гру ОПИСАНИЕ ИЗ АВТОРСКОМУ СВИДЕпы соответствующих схем сравнения группы, выход К-й схем сравнения группы соединен с прямым входом (К-)-го элемента И второй группы, выход р-й схемы сравнения группы (р=1, и) подключен к р-м инверсным входам элементов И второй группы с номером, большим р, выход перво схемы сравнения группы и выходы элементов И второй группы являются соответствующими выходами узла блока задания закона распределения, одноименные выходы узлов блока задания закона распределения подключены к соответствующим входам одноименного , элемента ИЛИ блока элементов ИЛИ;1 выходы которых подключены соответ 1 ственно к первым входам элементов И блока элементов И, вторые входы кото рых объединены и подключены к выходу генератора тактовых импульсов и входу запуска генератора случайного кода, выходы элементов И блока элементов И соединены с соответствующими входами блока памяти, выходы которого подключены к вторым обьединенным входам элементов И первой группы соответству ющего узла блока задания закона распределения, входы второй группы схем сравнения которого подключены соответственно к выходам генератора случайного кода, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей путем мо1088004 2второго элемента делирования входных и выходных потоковв системахмассового обслуживания,.оно дополнительно содержит регистр,первый и второй блоки сравнения итри элемента задержки, входы которыхподключены к выходу генератора тактоавюс импульсов, выходы блока памяти,являющиеся группой выходов устройствасоедкаеиы соответственно с разряднымидищаев.регистра, с входами первойгруаюы первого и второго блоков срав 1Изобретение относится к вычислительной технике и может быть использовано дня моделирования систем, описываемых аппаратом теории массового обслуживания. 5Известно устройство для моделирования систем массового обслуживания,содержащее первый и второй генераторысяучайиого потока импульсов, элементЗАПРЕТ, реверсивнцй счетчик, многокаиаиьиый блок случайных временных задержек, первый и второй элементы ИЛИ,баек сравнения, элемент И,первый, второйи третий счетчики, блок элементов И,ге -иератор импульсов, причем выход перво го генератора случайного потокаимпульсов соединен с первым счетчиком.и через элемент ЗАПРЕТ с многоканальиын блоком случайных временных задержек и суммирующим входом реверсавиого счетчика, выход которого соедиыев через блок сравнения с первымвходон первого элемента ИЛИ, выходкоторого соединен с управляющими вхо.дами элемента И и элемента ЗАПРЕТ,сигиапыщй вход элемента И соединенс входом первого счетчика, а выходэлемента И соединен с входом второгосчетчика, выход второго генератораслучайного потока импульсов соединен ЗОс вторым входом первого элемента ИЛИй первым входом генератора .импульсов, выход которого соединен с входомтретьего счетчика и через второй элемент ИЛИ с вычитающим входом ревер- .З 5сивного счетчика, разрядные выходыкоторого соединены через блок элементов И с вторым входом генератора . импульсов, а выход многоканального блока случайных задержек соединен с нения, вторые группы входов которыхподключены соответственно к разряднымвыходам регистра, выходы первой и вто"рой схем сравнения являются соответственно первым и вторым выходами устройся.ва,выходы первого и второго элементовзадержки подключены соответственно квходу разрещения записи и входу сбросарегистра,а выход третьего элемента задержки соединен с входами разрешениясравнения первой и второй схем сравнения. другим входомИЛИ Г 13.Недостаток устройства состоит в ограниченных функциональных воэможностях, так как устройство моделирует функционирование только систем с пот- рямиеИзвестно устройство для моделирования систем массового обслуживания, содержащее первый и второй генераторы случайных потоков импульсов, генератор импульсов, первый и второй счетчики, первый и второй реверсивнце счетчики, элемент ЗАПРЕТ, элемент задержки, многоканальный блок случайных временных задержек, первый, второй, третий, четвертый и пятый элементы ИЛИ, первый, второй и третий элементы И, блок элементов И, блок синхронизации, сумматор, пороговый эле" мент, формирователь и переключатель, причем выход первого генератора случайного потока импульсов соединен с входом первого счетчика и с первым входом первого элемента ИЛИ, выход которого соединен с первым входом элемента ЗАПРЕТ, выход которого соединен с суммирующим входом первого реверсивного счетчика и с входом многоканального блока случайных временных задержек, выход которого соединен с первым входом второго элемента ИЛИ, выход которого соединен с вцчитающим входом первого реверсивного счетчика, выход которого через пороговый элемент соединен с первым входом. третье%го элемента ИЛИ, второй вход которого подключен к.выходу генератора случай- ного потока импульсов и объединен с первым входом генератора импульсов,второй вход которого через первый элемент И соединен с разрядными выходами первого реверсивного счетчи-, ка, а выход генератора импульсов соединен с вторым входом второго элемента ИЛИ, выход третьего элемента ИЛИ соединен с вторым входом элемента ЗАПРЕТ и с первым входом второго элемента И, второй вход которого объединен с входом первого счетчика, первый 10 и второй выходы блока синхронизации соединены соответственно с управляющими входами блока элементов И и сум" матора, входы которого соединены с выходами блока элементов И соответ ственно, входы которого подсоединены .к разрядным выходам второго реверсив ного счетчика и через четвертый элемент ИЛИ соединены. с первым входом третьего элемента И, второй вход которого подключен к первому выходу переключателя, второй выход которого соединен с входом второго реверсивногс счетчика, выход третьего элемента И через элемент задержки соединен с вто- д 5 рым входом первого элемента И и непосредственно с вычитающим входом второго реверсивного счетчика, суммирующий вход которого соединен с- выходом пятого элемента ИЛИ, входы кото- з, рого соединены с выходом второго элемента И и с третьим выходом,переключателя соответственно, входы которого соединены, соответственно с выходом генератора импульсов и с выходом35 шестого элсмента ИЛИ, входы которого соединены соответственно с первым вхоДом второго элемента ИЛИ и через формирователь серии импульсов - с входом генератора импульсов 1.21. При моделировании систем для каждого закона распределения входящего потока сообщений необходим собственный генератор случайного потока. В устройстве не фиксируется, временное45 распределение выходного потока требований, что сообенно важно для моделирования, например, многофазиых систем (в технике систем связи), а также занятость приборов обслуживания (период занятости), Все это огра .ничивает функциональные возможности устройства, котороетакже отличается сложностью реализации.Наиболее близким к изобретению по 55 совокупности конструктивных и функци.ональных признаков является устройство, содержащее генератор тактовых импульсов, блок генерации случайногокода, блок задания закона распределе"ний, блок элементов И, блок элементов.ИЛИ, блок памяти, причем первые установочные входы соединены с первыми входами блока задания законов распределений, вторые входы которых соединены с выходами блока генерации случайного кода, вход которого соединен с выходом генератора тактовых импуль-.сов и с первым входом блока элемента И, вторые входы которого соединены с выходами блока элементов ИЛИ, входы которого соединены с выходами блока.задания законов распределений, третьи входы которого соединены с выходами устройства и выходами блока памяти, входы которого соединены с выходами блока элементов И ГЗ 3.Известное устройство моделирует марковский процесс, который описывае 1 и системы массового обслуживания,- Если задавать достаточно малые интер.валы времени, за которые исследовать (моделировать) изменение состояний системы массового обслуживания, толегко представить вероятностный автомат как модель системы массового обслуживания, Однако устройство не позволяет регистрировать моменты входа и выхода требований из системы, а также занятость системы обслуживанием, что ограничивает функциональные возможности известного устройства. Цель изобретения в , расширение функциональных возможностей путем моделирования входных и выходных потоков в системах массового обслуживания.Указанная цель достигается тем, что устройство для моделирования марковских потоков снгналов, содержащее генератор случайного кода, генератор тактовых импульсов, блок элементов ИЛИ, блок элементов И, блок памяти и блок задания закона распределения, состоящий иэ и идентичных узлов, каждый из которых содержит группу регистров, группу сумматоров, первую и вто" рую группы И, группу схем сравнения, разрядные входы регистров всех узлов блока задания закона распределения являются соответствующими установочными входами устройства, а в каждом узле выходы первого регистра группы соединены с первыми входами соответствующих . элементов И первой группы, выходы г-го регистра группы (К=2,п) соединены соответственно с входами первой10880 3груп (М)-го сумматора группы, вторая групйа входов первого суммато" ра группы соединена соответственно с выходами первого регистра группы,вторая группа входов М-го сумматора5 группы фщ 2, 6 -1) соединена соответ" ственно с выходами 0 М)-го сумматора группы, выходы всех сумматоров руппы подключены к первым входам соответствующих элементов И первой 10 группы, выходы которых соединены с входами первой группы соответствующих схем сравнения группы,выход-й схемы сравнения группы соединен с прямым входом (Е)-го элемента И второй груп" 5 пы, выход Р-й схемы сравнения группы (Р 1, Ь) подключен к Р"м инверсным входам элементов И второй группы с номером, болыаим Р, выход первой схемы сравнения группы и выходы элементов И второй группы являются соответствующими выходами узла блока задания закона распределения, одноименные выходы узлов блока задания закона распределения подключены к соответствующим входам одноименного элемента ИЛИ блока элементов ИЛИ, выходы которых подключе ны соответственно к первым входам элементов И блока элементов И, вторые входы которых объединены и подключены к выходу генератора тактовых импульсов и входу запуска генератора случайного кода, выходы элементов И блока элементов И соединены с соответствующими входами блока памяти, выходы которого подключены к вторым объединенным входам элементов И первой груп" пы соответствующего узла блока зада" ния закона распределения, входы вто" рой группы схем сравнения которого подключены соответственно к выходам40 генератора случайного кода, дополни тельно содержит регистр, первый и . второй блоки сравнения и три элемента задержки, входы которых подключены к выходу генератора тактовых импульсов, выходы блока памяти, являющиеся , группой выходов устройства, соединены соответственно с разрядными входами регистра, с входами первой группы первого и второго блоков сравнения, 50 вторые группы входов которых подключены соответственно к разрядным выходам регистра, выходы первой и в второй схем сравнения являются соответственно первым и вторым выходами 55 устройства, выходы первого и второго элементон задержки подключены соответственно к входу разрешения записи 04 Ьи входу сброса регистра, а выходтретьего элемента задержки соединенс входами разрешения сравнения первой и второй схем сравнения.На фиг. 1 приведена блок-схемаустройства; на фиг. 2 - функциональнаясхема узла блока задания закона распределения; на фиг. 3 - временныедиаграммы работы устройства.Устройство для моделирования системмассового обслуживания (фнг. 1) содержит .группу установочных входов 1,блок 2 задания закона распределейия,генератор 3 случайного кода, генератор 4 тактовых импульсов, первый 5,второй 6 и третий 7 элементы задержки,блок 8 элементов И, блок 9 элемен"/тов ИЛИ, регистр 1 О, первый 11 ивторой 12 блоки сравнения, причемвторой блок 12 сравнения реализовананалогично первому блоку 11 сравнения, группу выходов 13, блок 14 памяти, первый и второй выходы 15 и 16,Блок 2 задания закона распределениясодержит и однотипных узлов, каждыйиэ узлов блока 2 включает группу регистров 17, вторую группу входов 18,соединенную с соответствующими выходами генератора 3, группу схем 19,сравнения, первую группу элементовИ 2, выход 13; для каждого узла, соединенный с соответствующим 1-м выходом 13 устройства, вторую группу элементов И 21, группу сумматоров 22,группу выходов 23.Одноименные вь 1 ходы всех узлов.подключены к входам одного и того же элемента ИЛИ блока элементов ИЛИ,Устройство работает следующимобразом.По установочным входам 1 в регистры 1 блока 2 задания закона распределения заносятся. коды матрицы вероятностей перехода системы массового обслуживания. При этом в регистр 17 1заносится вероятность Р"-перехода1системы в р -е состояние, при условии, что она в предыдущий момент вре"мени находилась в 1-м состоянии.Устройство может моделироватьпроцесс функционирования систем массового обслуживани как одноканальных,так и многоканальных с отказами и беэпотерь, Причем для систем беэ потерьвводится ограничение на макимальнодопустимую длину очереди. При этомв каждом случае матрица переходныхвероятностей формируется индивидуально,1088004 Рассмотрим формирование матрицы йереходных вероятностей для и канальной системы. Все о каналов абсолютно идентичны, освободившийся канал занимает первое в очереди требование. 5 Вероятности Р 01-СМ , РО=ОЬСа вероятности РРп Р равныопнулю как величины высшего порядка малости по сравнению с Р ,и Рогде с-интенсивность входящего пуассоновско= 10 гопотока требований на обслуживание. О О ОО Эьф О О О О1 фой 1 1-р.М 1+фИ 1 О О 1+сСд 1 а ьФ 1+Ы,М1-1 1+оСЬ и дФ1+оИО О 1-,ы М 1+сСИ 1+оьФ ОО О 30 Начальное состояние устройства длямоделирования предусматривает наличиесигнала на выходе 13 т.е. в системе1массового обслуживанйя нет требований.По установочным входам 1 в регистры 17олока 2 задания закона распределенийвнесены коды Р; матрицы Р. С приходомЧимпульса генератора 4, который подается на входы первого. 5 второго 6 итретьего 7 элементов задержки времени, на первый вход блока элементов И 8и вход генератора 3 случайного кода,в нем вырабатывается код числа, равномерно распределенного в интервале отнуля до единицы,Так как на выходе 13 имеется потеяциал то по входу 131 блока 2 подаетсяпотенциал, элементы И 20 первого узла Для систем массовсго обслуживаниябеэ потерь с -каналами матрица пере"ходных вероятностей имеет такой жевид,как и для системы с п приборамиобслуживания, но в этом случае и - максимально допустимое число заявок вочереди (выбирается из условия максимального отклонения от математическогоожидания).Предположим, что моделируется сиСтема с 1.приборами и максимально возможным числом требований в системе,равным 1,Тогда наличие сигнала на первомвыходе 13 говорит о том, что в систе.ме нет требований и все приборы свободны, наличие сигнала на выходе. 13 в системе одно требование и занят одинканал, а наличие сигнала на выходе13 - заняты два прибора. Если сигнална выходе 13 то заняты обслуживанием,все приборов. Если сигнал на выходе132 топриборов заняты и в очереди Ю-,(1+4) требований. 55Интервалы времени Д 1 выбираютсязначительно меньше по величине, чем;еби А,. Причем чем меньшеДт,тем больше Вероятность Ррс 4 Ф Р, = 1-кЬа вероятность Р распределяется из усло.вия поступления в систему очередного требования, т.е, Р сМФ где ц, - интенсивность потока .обслуживания. Вероятности РО.(д = 3, П). Вероятности Р, , Р иР 2 нормируются В целом матрица переходных вероятностей имеет вод точность моделирования, однако в этом случае увеличивается время моделирования,Генератор 4 тактовой частоты задаеч интервалы времениМ равные периоду следования его импульсов.Устройство работает следующим образом.45 9 108800блока 2 открыты.и коды регистра 17 д,а также сумматоров 2241"221. подаются.на вторые входы схем 191-19 сравнения.Если в регистрах 17 -1 хранятсякоды Рбо, Ро, Р 02, 11, П., то навыходах регистра 17 и сумматоров2211-22 сформировываются коды1 и-э, Р +Р , Р Р, + Р Р+ р 1,- +рпгоПричем сумма последнего элемейтастроки равна единице.Предположим, что генератор 3 сгенерировал случайный код А,.численнаявеличина которого меньше величины 15кода Р . Данный код подается на входы схем 1911-191, Так как код А меньшепо величине кодов, подаваемых надругую группу входов схем 19 сравнения, то на их выходах появляются потенциалы, причем потенциал с выхода, схемы 19 сравнения закроет все элементы И 21 и сигнал появится толькона выходе 23, блока 2,Данный сигнал поступает через блок 259 элементов ИЕИ. Тогда с выхода 131вновь снимается потенциал (фиг, 3),т.е. эа время Д 1 в систему массовогообслуживания заявок не поступает, Позаднему фронту сигнала генератора 4 30через первый элемент 5 задержки врегистр 10 происходит запись новогосостояния выходов 13, Причем передэтим по переднему фронту импульса генератора 4 с незначительной задержкой, формируемой третьим элементом 7задержки, в блоках 1 и 12 сравненияпроисходит сравнение чисел регистра10 и нового состояния выходов 13 впозиционном коде. Так как изменений не 40происходит, то на выходах первого 11 ивторого 12 блоков сравнения сигналовнет. После сравнения второй элемент 6задержки сбрасывает регистр 10 в нулевое состояние, т,е. процесс сравнения с предыдущим кодом выходов 13происходит перед записью нового состояния выходов3 в регистр 10,Предположим, (фиг. 3), что лишь зачетвертый интервал ДФ в систему массо 50ваго обслуживания поступило сообщение,Рассмотрим, как это моделируется всистеме,С приходом четвертого импульса отгенератора 4 тактовых импульсов ге 55нератор 3 случайного кода генерируеткод, величина которого меньше числа.б+Р 1.1, но больше числа Р 0 В этом слу 4 1 Очае срабатывают схемы 19 -1 Я гравие"а 1ния. Сигнал с выхода схемы 191 сравнения закрывает элементы И 21 -21и на выходе 132 блока 2 появляетсяпотенциал, который проходит черезблок 9 элементов ИЛИ, блок 8 элементов И на второй вход блока 14 памятии на выходе 132 устройства появляетсяпотенциал. Это моделирует случай прихода в систему требрвания за интервал 4 Йи принятия его на обслуживание. Всистеме занят один канал обслуживанием,Наличие сигнала на выходе 32 свидетельствует о занятости обслуживаниемв системе одним каналом одного требования и отсутствие очереди в системе.С появлением импульса на выходетретьего элемента 7 задержки на входыблоков 11 и 2 сравнения подаетсяпотенциал, Так как на выходах регистраО снимается код 1000, подаваемыйна одни входы блока .11, а на другиеего входы подается код 01000, ко"торый меньше кода 10000, то навыходе блока 11 сравнения появляетсяпотенциал, который подается на выход 15. Появление потенциала на выходе15 свидетельствует о приходе в систему требования в отсчет времени, задаваемый генератором 4, и о занятииобслуживанием одного канала,На фиг, 3 показано, что и за шестой интервал М в систему поступаетеще одно требование и занят обслуживанием второй канал, так как сигналпоявляется на выходе 13 устройстваи на выходе 15.Если же за какой-либо интервал АФбудет закончено, обслуживание требования, то в этом случае сигнал появляется на выходе 13 по порядковому номеру индекса, меньшему на единицу,чем 13 + В этом случае срабатывает1+1второй блок сравнения. На третьемвыходе 16 устройства появляется потенциал, что позволяет зафиксировать времявыхода требования из системы массовогообслуживания.Таким образом, в процессе моделирования системы массового обслуживаниявозможно получить модель входного потока сообщений по анализу потока импуль-,сов на выходе 15, модель выходногопотока сообщений - по анализу потокаимпульса на выходе 16, модель занятости системы обслуживания (период занятости) требований - по анализу потенциалов иа выходах 13,1088004 г,Составитель В. Фукалова Техред В,Далекорей Редактор И,ректор Ю.Макарен 2674/46 Тираж 699ВНИИПИ Государственного комитета ССпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д сное За 5 лиал ППП "Патент", г. Ужгород, ул. Проектная, 4