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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик(22) Заявлено 100980 (21) 2980775/18-24 р 1 М К 1 з с присоединением заявки МВ 6 Об Р 1/02 С Об Р 7/58 Государственный комитет СССР по делам изобретений н открытийОпубликовано 23.0482 Бюллетень М 915 Дата опубликования описания 230482 в);,1 вудой 4 йо-.,Красного(71) Заявитель Казанский ордена Ленина и ордена3 ю а54) УСТРОЧСТВО ДЛЯ ВЕРОЯТНОСТНОГО МОДЕЛИРОВАНИЯИзобретение относится к вычисли тельной технике и предназначено для моделирования случайных процессов.По основному авт.св. Р 488212 известно устройство, содержащее генератор случайных чисел, блок сравнения, регистр маски, регистр числа, блок . памяти, регистр адреса и блок управления, причем вход генератора случайных чисел. соединен с первым выходом. блока управления, первый вход блока сравнения соединен с выходом генера" тора случайных чисел, второй вход - с вторым вйходом блока управления, а первый выход - с первым входом регистра адреса, второй вход которого соединен с третьим выходом блока управления, а выход - с входом блока памяти, выход которого подключен к первому входу регистра числа, второй вход которого подключен к четверто-. му выходу блока управления, пятый выход которого соединен с первыМ входом регистра маски, второй вход которого соединен с вторым выходом бло ка сравнения, а третий вход - с выходом регистра числа, первый выходс третьим входом блока сравнения, а второй выход ." с третьим входом ре,гистра адреса, предназначенное для З 0 формирования дискретных случайных величин и простых цепей Маркова.Однако с помощью этого устройства нельзя формировать более сложные цепи - многосвязные цепи, в которых вероятность появления последующего состояния .зависит от более чем одного предыдущих. состояний.Цель изобретения - раэширение функциональных возможностей за счет формирования многосвязных цепей Маркова.Поставленная цель. достигается тем, что в устройство, содержащее генератор случайных чисел, блок сравнения, регистр маски, регистр числа, блок памяти, регистр адреса и блок управления, причем вход генератора случайных чисел соединен с первым выходом блока управления, первый вход. блока сравнения соединен с выходом генератора случайных чисел, второй вход - с вторым выходом блока управления, а первый выход - с первым входом регистра адреса, второй. вход которого соединен с третьим выходом блока управления, а выход - с входом блока памяти, выход которого подключен к первому входу регистра числа, второй вход которого подключен к четвертомуГенератор 1 случайных чисел предназначен для генерации. исходных, равномерно распределенных случайных двоичных чисел. Вход генератора 1 слут- чайных чисел соединен с первым выхо 5 дом блока 7 управления. Блок 2 сраво нения служит для параллельного сравнения группы граничных значений инмму- тервалов разбиения области определения формируемой случайной функции с10 исходным случайным числом. Первыйвход блока 2 сравнения сбединен свыходом генератора 1 случайных чисел,второй вход - с вторым выходом блока7 управления, а первый выход - с первым входом регистра б адреса. Регистрб адреса служит для управления блоком 5 памяти и разделен на две части - младшую и старшую. Младшая частьуказывает место расположения отдельных ячеек блока памяти. Старшаячасть регистра указывает место расположения массива ячеек. Первый входрегистра б адреса, соединенный спервым выходом блока 2 сравнения,является входом младшей части. Второй вход регистра б адреса соединенс третьим выходом блока 7 управленияи вторым входом блока 8. Этот входявляется входом синхронизации. Третий вход регистра б адреса соединенс выходом блока 8 изменения глубинысвязи состояний цепи и является информационным входом старшей части регистра б. Блок 5 памяти служит дляхранения кода функции распределения35 и ее аргументов. Вход блока 5 памятисоединен с выходом регистра б адреса. Регистр 4 числа служит для приема содержимого блока 5 памяти и егохранения на время операции сравнения,40 Первый вход регистра 4 числа соединен с выходом блока 5 памяти, а второй вход - с четвертым выходом блока 7 управления. Регистр 3 маски служит для маскирования разрядов регистр 45 ра 4 числа. Цель маскирования - взаданный такт работы устройства снимать информацию только с определенной части разрядов ячейки блока 5памяти. Первый вход регистра 3 маски соединен с пятым выходом блока 7управления, второй вход с вторым выходом блока 2 сравнения, а третийвход - с выходом регистра 4 числа.Первый выход регистра 3 маски соединен с третьим входом блока 2 сравнения, а второй выход - с первым входом блока 8 изменения глубины связи состояний цепи. Блок содержит коммутатор 9, группу 10 элементов, сумматор 11.по модулю два, элемент ИЛИбо НЕ 12, счетчик 13 и элемент И 14,причем первый вход коммутатора 9 ипервый вход элементов 10 соединенымежду собой и образуют первый входблока 8. Второй вход элементов 10,б 5 выходу блока управления, пятый выход которого соединен с первым входом регистра маски, второй вход которого соединен с вторым выходом блока срав нения, третий вход - с выходом регис ра числа, а первый выход - с третьим входом блока сравнения, дополнительн введены счетчик, элемент ИЛИ-НЕ, эле мент И, сумматор по модулю два, ко татор и группа элементов И, первые входы которых объединены с первым входом коммутатора и подключены к второму выходу регистра маски, вторые входы элементов И группы объеди. нены с первым входом элемента И, со счетным входом счетчика и с вторым входом регистра адреса, третий вход которого соединен с выходом коммутатора, второй вход которого объединен со вторым входом элемента И и подключен к выходу элемента ИЛИ-НЕ, входы которого соединены с разрядными выходами счетчика, третий вход коммутатора подключен к выходу сумматора по модулю два, первый и второй входы которого соединены соответственно с выходами элементов И группы и элемента И.На фиг.1 приведена блок-схема устройства; на фиг.2 - схема блока управления; на фиг.З - диаграммы работы блока управления.Устройство содержит генератор 1 случайных чисел, блок 2 сравнения, регистр 3 маски, регистр 4 числа, блок 5 памяти, регистр 6 адреса, блок 7 управления, блок 8 изменения глубины связи состояний цепи, коммутатор 9, группу 10 элементов И, сумматор 11 по модулю два, элемент ИЛИНЕ 12, счетчик 13, элемент И 14.Блоки 1-7 относятся к основному устройству, узлы 9-14, содержащиеся в блоке 8, являются дополнительными.Блок 7 управления содержит генератор 15 тактовой частоты, элементы ИЛИ-НЕ 16 и 17, сдвигающий регист 18, элементы ИЛИ 19 и 21, элемент И 20, сдвигающий регистр 22, элементы И 23-25, сдвигающий регистр 26, элемент И 27, элемент НЕ 28, элементы И29 и 30, шину 31 связи с генератором1 случайных чисел, шину 32 связи с регистром 4 числа, шину 33 связи с регистром 3 маски, шину 34 связи с блоком 2 сравнения, шину 35 связи с регистром б адреса, часть Зб шины 35, используемую для синхронизации блока 8.При этом й - вход установки нуля; С - синхровход;, 0 - информационныйвход; "1" - уровень логической единицы.Цепи питания и начальной установкиисходного состояния не показаны.На Фиг,З приведены временные диаграммы работы блока управления на выходах определенных узлов схемы. первый вход элемента И 14 и входсчетчика 13 также соединены междусобой и образуют второй вход блока 8.Выходом блока 8 служит выход коммутатора 9. Второй вход коммутатора 9соединен с вторым входом элементаИ 14 и выходом элемента ИЛИ-НЕ 12,вход которого соединен с выходомсчетчика 13. Выход элемента И 14 соединен с первым входом. сумматора 11по модулю два, второй вход которогосоединен с выходом элементов 10, авыход - с третьим входом коммутатора 9. 1 О Принцип работы устройства состоит в следующем. 15Получение случайных чисел х 3.-1,2,п) с заданным законом распределения Р(х; ) основано на сравнении равномерно распределенных чисел со значениями Р(Х 1), отыскании интер-,0 вала, где выполняется условиеР(х; )АР(х; ) (1) и выдачи соответствующего данному интервалу значения х;.Для реализации соотношения (1) нсе значения Р(х) разбиты на группы. Группы выбираются из блока памяти логарифмическим перебором и каждая группа сравнивается с числомпараллельно. Логарифмический перебор осуществляется упорядоченным расположением значений Р(х и х по группам.При формировании простых и многосвязных цепей Маркова алгоритмы получения х; служат для реализации одной строки стохастической матрицы. Выбор 35 следующей строки определяется полученными значениями х;.функционирование устройства рассмотрим на следующем примере. Пусть п=64(1=1,64) и основание логарифма 40 равно 4.,Кроме того, для определенности предположим, что генератор 1 случайных чисел является псевдослучайным. Соответствующая этому примеру схема блока 7. управления приведе на на фиг.2.Устройство работает следующим образом.По внешнему сигналу "Пуск", который поступает в блок 7 управления по шине "Пускф (см.фиг.2), триггер, образованный элементами ИЛИ-НЕ 16 и 17, устанавливается в единичное состояние. При этом на информационный. вход сдвигающего регистра 18 поступает уровень логической единицы. Передним фронтом очередного импульса тактовой частоты, которые пбступают на синхровход регистра 18 с выхода генератора 15 тактовой частоты, в первый разряд регистра 18 (верхний по схеме) записынается "1". Эта "1" устанавлинает в исходное нулевое состояние триггер, образованный элементами ИЛИ-НЕ 16 и 17, и через элемент ИЛИ 19 открывает элемент И 20 для 65 прохождения импульсон генератора 15тактовой частоты. При поступленииследующего импульса тактовой частоты "1" иэ первого разряда регистра18 переписывается но нторой, а в первый разряд записывается "0". Ыестойимпульс тактовой частоты вызывает появление "1" на выходе шестого, последнего разряда регистра 18, которыйчерез элемент ИЛИ 21 соединен с О"входом сдвигающего регистра 22. При,поступлении седьмого импульса такто 1 вой частоты регистр 18 оказывается внулевом состоянии, элемент И 20 запи-,рается, а н первый разряд регистра 22(верхний по схеме, образует шину 32)записывается "1"В результате нашине 31, связывающей блок управления с генератором 1 случайных чисел,формируются шесть импульсов, кото,рые необходимы для генерации исходного случайного 6-разрядного двоичного числа. Полученное случайное число поступает с выхода генератора 1 напервый вход блока 2 сравнения. Импульс на шине 32, которая образована выходом перного разряда регистра22 и связывает блок управления срегистром 4 числа, осуществляет запись в регистр 4 числа содержимогоячейки блока 5 памяти, адрес которойопределяется регистром 6 адреса. Приэтом старшая часть. регистра 6 определяет адрес массива ячеек, а младшая часть - адрес ячейки в массиве.Записанное в регистр 4 числа содержимое ячейки блока 5 памяти через регистр 3 маски поступает на другойвход блока 2 сравнения. В рассматрива.емом примере для реализации соотношения (1) необходимо три такта. Впервый такт проверяются условия Р (х )Е сР (х; ) юР (хф)4 (Р (х) ГР(х 2) Е,Р(х щ),Р ( х 1 д)Яс Р ( х4 )Пустьпопало в интервал1 Р(х 1), Р(ха )1, тогда но второйтакт проверяются условияР (х, )1 Р (х ),Р(),.Ь Р( ),,Р (х 8) Р (ха)Р (Х)( ( Р (Х 16),Пустьпопало н интервалР(ха ), Р(х )3, тогда н третийтакт проверяются условияР(х 2 )А Р (хз ).,Р(х)6,Р(Х,4 ),Р (х,)с Е, Р (х л ),Р (Х 1 э )8, Р (Х 16 )В эти три такта иэ блока 5 памяти выбираются три ячейки, в которыхсодержатся следующие группы значенийР (х б )Р (х з 2)Р (хмв)Р(х ), Р(х, ), Р(х );Р(Х), Р(Хц ), Р(Х,5 ).Эти группы сравниваются в блоке 2 сравнения со случайным числом Е Принадлежность числаодному из четырех интервалов указывается в виде логической единицы на одном из четырех выходов, образующих выходную шину блока 2, Результат сравнения поступает в младшую часть регистра 6 адреса, которая представляет собой сдвигающий регистр, и служит для Формирования адреса, по которому из блока 5 10 памяти выбирается новая группа,значений Р(х;), Первая группа Р(х;), которая сравнивается в первом такте сравнения, не зависит от Е поэтому (адрес ячейки, в которой хранится пер-(5 вая группа Р(х;), является постоянным. Это достигается путем установки младшей части регистра 6 адреса в нулевое состояние перед каждым циклом сравнения. 20Процесс сравнения обеспечивается 22 выполняет Функцию распределителя импульсов, а регистр 26 в сочетании с элементом И 27 - функцию счетчика тактов сравнения. При этом первый импульс, поступающий на шину 32, служитдля записи в регистр 4 числа очередной группы Р(х;). Второй импульс, который с второго выхода ре" гистра 22 через открытый элемент И 29 поступает на шину 34, служит для записи в регистр,.содержащийся в блоке 2 сравнения, результата сравнения, Запоминание результата сравнения необходимо для правильной ра боты регистра 3 маски, так как в противном случае при маскировании разрядов регистра 4 числа изменяется результат предыдущего сравнения, который управляет регистром 3 маски, 40 что приводит к изменению результата маскирования. Третий импульс, который с третьего выхода регистра 22 .через открытый элемент И 30 поступает на шину 35, служит для записи ре зультата сравнения в младшую часть регистра б адреса.После окончания цикла сравнения из блока 5 памяти в регистр 4 числа считывается группа значений х, одно из которых является текущим состоянием цепи. Выбор х; обеспечивается регистром 3 маски. Те части регистра маски, в которые по выходам из блока 2 сравнения поступили логические нули, закрываются. Открытой остается только одна часть, на вход которой поступила "1". Число х; снимается с . тех разрядов регистра 4 числа, которые соответствуют этой открытой части, Считывание х; и переход к следу.ющей строке стохастической матрицы обеспечиваются изменением режима работы блока управления. Роли первая, вторая и третья серии импульсов, сформированных регитром 22, обеспе 0 ние, что вызывает появление ф 1" на следующим образом. Сдвигающий регистр чивают реализацию цикла сравнения, то последняя четвертая серия импульсов обеспечивает формирование текущего значения цепи и подготовку к новому циклу работы устройства. Эле" мент И 27 при этом открывается, так как после каждой серии импульсов в регистр 26 записывается ф 1 ф, и после третьей серии на всех входах элемента И 27 присутствует ф 1". Это приводит к запиранию элементов И 29 и 30 и отпиранию элементов И 23 и 25. В результате, второй импульс с регистра 22 поступает не в блок 2 сравнения, а через элемент И 23 на шину 33, связывающую блок управления с регистром 3 маски. Одновременно этот им- . пульс поступает на шины 36 и 35. По шине 35 этот импульс поступает в младшую часть регистра 6 адреса и устанавливает ее в исходное нулевое состояние, осуществляя тем самым подготовку к новому циклу работы, а по шине Зб он поступает на вход счетчйка 13 и второй вход элементов 10. Третий импульс с регистра 22 через элемент И 25 поступает на шины 36 и 35, причем по шине 36 он поступает на первый вход элемента И 14, а по шине 35 - на старшую часть регистра б адреса и служит для записи информации в старшую часть регистра б.Полученное значение х;, представляющее собой текущее состояние цепи, с выхода регистра 4 через регистр 3 маски поступает на первые входы коммутатора 9 и элементов И 10. Импульс блока 7 управления, поступающий с выхода элемента И 23 и устанавливающий в исходное состояние младшую часть регистра 6 адреса, одновременно поступает на второй. вход элементов И 10, открывает их, и на вход сумматора 11 по модулю два поступает число х;. Сумматор 11 представляет собой набор Т-триггеров, входы которых соединены с соответствующими выходами элементов И 10, и служит для поразрядного суммирования по модулю два чисел х. Исходным состоянием сумматора 11 является нулевое. Импульсы, поступающие на второй вход группы 10 элементов, одновременно поступают на вход счетчика 13, который подсчитывает количество суммированных чисел х(.После сложения щ чисел (число ш определяет заданную глубину связности цепи и представляет собой число возможных состояний счетчика 13, включая нулевое) счетчик 13 перепол" няется и переходит в нулевое состоявыходе элемента ИЛИ-НЕ 12, входы которого соединены с выходами триггеров счетчика 13. При этом результат суммирования чисел х с выхода сумматора 11 через коммутатор 9 поступаможно получить более сложные цепи,в которых вероятность появления текущего состояния цепи зависит от за-.данной комбинации предыдущих состояний или от заданного числа состояний. По своим Функциональным возможностям предлагаемое устройство можетпри небольших аппаратурных затратахпо сравнению с известным устройствомзаменить одновременно два устройства,одно из которых предназначено длягенерации простых цепей Маркова, авторое - для генерации многосвязныхцепей Маркова. Формула изобретения Устройство для вероятностного моделирования по авт.св. В 488212, о т л и ч а ю щ е е с я тем,.что, с целью расширения функциональных возможностей устройства за счет формирования многосвязных цепей Маркова, оно содержит счетчик, элемент ИЛИ-НЕ, элемент И, сумматор по модулю два, коммутатор и группу элементов И, первые входы которых объединены с первым входом коммутатора и подключены к второму выходу регистра маски, вторые входы элементов И группы объединены с первым входом элемента И, со счетным входом счетчика и с вторым входом регистра адреса, третий вход которого соединен с выходом элемента И и подключен к выходу элемента ИЛИ-НЕ, входы которого соединены с разрядными выходами счет" чика, третий вход коммутатора подключен к выходу сумматора по модулю два, первый и второй входы которого соединены соответственно с выходами элементов И группы и элемента И. ет на вход старшей части регистра б адреса. Запись этой информации в регистр 6 осуществляется импульсом блока 7 управления, поступающим с выхода элемента И 25. Записанный в регистр б адреса результат суммирования служит адресом массива ячеек в блоке 5 памяти, по которому записана очередная строка стохастической матрицы цепи. После каждого такого цикла формирования ш-связного значе ния цепи сумматор 11 по модулю два устанавливается в нулевое состояние импульсом записи информации в старшую часть регистра 6. Этот импульс поступает на первый вход элемента И 15 .14, на второй вход которого с выхода элемента ИЛИ-НЕ 12 поступает ф 1". Возникающий на выходе элемента И 14 импульс поступает на вход установки 1 нуля сумматора 11 по модулю два.Цикл работы блока 7 управления завершается после окончания импуль-, са записи информации в старшую часть регистра б. При этом очередной тактовый импульс генератора 15 тактовой частоты вызывает появление н 1" на последнем выходе регистра 22, что приводит к появлению 1" на цоследнем выходе регистра 26. В результате на выходе элемента И 24 появляется " 1 ", которая устанавливает в нулевое состояние регистры 18, 22 и 26 и одновременно устанавливает в единичное состояние триггер, образованный элементами ИЛИ-НЕ 16 и 17, осуществляя тем самым новый пуск блока. 7 управления, На этом цикл работы устройства завершается.В предлагаемом устройстве наряду с формированием простых цепей Маркова, что достигается путем установки 40 счетчика 13 в нулевое состояние,922707 йуя Вава Жфн Составитель А,Карасов Редактор В.Данко Техред А.Ач Корректор М.ПожоТираж 732 государственделам изобрет Иосква, Жго кийРауш Подпитета СССРткрытийкая наб д