Устройство для вероятностного моделирования Советский патент 1982 года по МПК G06F7/58 

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

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

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

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

Цель изобретения - разширение

10 Функциональных возможностей за счет формирования многосвязных цепей Маркова.

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

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

30 вход которого подключен к четвертому выходу блок управления, пятый выход которого соединен с первым входом регистра маски, второй вход которого соединен с Бторым выходом блока срав нения, третий вход - с выходом реги ра числа, а первый выход - с третьим Ьходом блока сравнения, дополнитель введены счетчик, элемент ИЛИ-НЕ, эле мент И, сумматор по модулю два, комм татор и группа элементов И, первые входы которых объединены с первым входом коммутатора и подключены к второму выходу регистра маски, вторые входы элементов И группы объеди нены с первым«входом элемента И, со счетным входом счетчика и с вторым входом регистра адреса, третий вход которого соединен с выходом коммутй тора, второй вход которого объединен со вторым входом элемента И и подключен к выходу элемента ИЛИ-НЕ, входы которого соединены с разрядны ми выходами счетчика, третий вход коммутатора подклю-чен к выходу сумматора по модулю два, первый и второй входы которого соединены соответственно с выходами элементов И группы и элемента И. На фиг.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 связи с регистром б адреса, часть 36 шины 35, используемую для синхронизации блока В. При этом R - вход установки нуля С - синхровход;. D -.информационный вход; 1 - уровень логической единицы. Цепи питания и начальноя установки исходного состояния не показаны. На фиг.З приведены временные диаграммы работы блока управления на выходах определен((нх узлов схемы. Генератор 1 случайных чисел пред назначен для генерации-исходных, равномерно распределенных случайных двоичных чисел. Вход генератора 1 случайных чисел соединен с первым выходом блока 7 управления. Блок 2 сравнения служит для параллельного сравнения группы граничных значений интервалов разбиения области Ъпоеделения формируемой случайной функции с исходным случайным числом. Первый вход блока 2 сравнения соединен с выходом генератора 1 случайных чисел, второй вход - с вторым вьЕходом блока 7 управления, а первый выход - с первым входом регистра 6 адреса. Регистр 6 адреса служит для управления блоком 5 памяти и разделен на две части - младшую и старшую. Младшая часть указывает место расположения отдельных ячеек блока памяти. Старшая часть регистра указывает место расположения массива ячеек. Первый вход регистра 6 адреса, соединенный с первым выходом блока 2 сравнения, является входом младшей части. Второй вход регистра 6 адреса соединен с третьим выходом блока 7 управления и вторым входом блока 8. Этот вход является входом синхронизации. Третий вход регистра 6 адреса соединен с выходом блока 8 изменения глубины связи состояний цепи и является информационным входом старшей части регистра 6. Блок 5 памяти служит для хранения кода функции распределения и ее аргументов. Вход блока 5 пгиияти соединен с выходом регистра 6 адреса. Регистр 4 числа служит для приема содержимого блока 5 Пс1мяти и его хранения на время операции сравнения. Первый вход регистра 4 числа соединен с выходом блока 5 памяти, а второй вход - с четвертым выходом блока 7 управления. Регистр 3 маски служит для маскирования разрядов регистра 4 числа. Цель маскирования - в заданный такт работы устройства снимать информацию только с определенной части разрядов ячейки блока 5 памяти. Первый вход регистра 3 маски соединен с пятым выходом блока 7 управления, второй вход с вторым выходом блока 2 сравнения, а третий вход - с выходом регистра 4 числа. Первый выхрд регистра.3 маски соединен с третьим входом блока 2 сравнения, а второй выход - с первым входом блока 8 изменения глубины связи состояний цепи. Блок содержит коммутатор 9, группу 10 элементов, сумматор 11- по модулю два, элемент ИЛИНЕ 12, счетчик 13 и элемент И 14, причем первый вход коммутатора 9 и первый вход элементов 10 соединены между собой и образуют первый вход блока 8. Второй вход элементов 10, первый вход элемента И 14 и вход счетчика 13 также соединены между собой и образуют второй вход блока 8 Выходом блока 8 служит выход комг татора 9-. Второй вход коммутатора 9 соединен с вторым входом элемента И 1.4 и выходом элемента -ИЛИ-НЕ 12, вход которого соединен с выходом счетчика 13. Выход элемента И 14 соединен с первым Ёходом.сумматора 11 по модулю два, второй вход которого соединен с выходом элементов 10, а выход - с третьим входом коммутатора 9. Принцип работы устройства состоит в следующем. Получение случайных чисел XJ (1-1,2,. . ..,п) с заданным законом распределения F(xj ) основано на срав нении равномерно распределенных чисе со значениями Р(х|), отыскании интер вала, где выполняется условие F(xi)(x;, )(1) и выдачи соответствующего данному ин тервалу значения х. . Для реализации соотношения (1) . все значения Г(х|) разбиты на группы Группы выбираются из блока памяти ло гарифмическим перебором и каждая, гру па сравнивается с числом ё, параллель но. Логарифмический перебор осуществляется упорядоченным расположением значений F(xj) и xj по группам. При формировании простых и многосвязных цепей Маркова алгоритмы полу чения Х| служат для реализации одной строки стохастической матрицы. Выбор следующей строки определяется полученными значениями Х|. Функционирование устройства рассмотрим на следующем примере. Пусть (,б4) и основание логарифма равно 4. .Кроме того, для определенности предположим, что генератор 1 случайных чисел является псевдослучайным. Соответствующая этому примеру схема блока 7 управления приведена на фиг.2. Устройство работает следующим образом. По внешнему сигналу Пуск, который поступает в блок 7 управления по шине Пуск (см.фиг.2), триггер, обр зованный элементами ИЛИ-НЕ 16 и 17, устанавливается в единичное состояние. При этом на информационный, вхо сдвигающего регистра 18 поступает уровень логической . Передним фронтом очередного импульса тактовой частоты, которые поступают на синхровход регистра 18 с выхода генератора 15 тактовой частоты, в первый разряд регистра 18 (верхний по схеме) записывается 1. Эта 1 устанавливает в исходное нулевое состо яние триггер, образованный элементами ИЛИ-НЕ 16 и 17, и через элемент ИЛИ 19 открывает элемент И 20 для прохождения импульсов генератора 15 тактовой частоты. При поступлении следующего импульса тактовой частоты 1 из первого разряда регистра 18 переписывается во второй, а в первый разряд записывается О. Шестой импульс тактовой частоты вызывает появление 1 на выходе шестого, последнего разряда регистра 18, который через элемент ИЛИ 21 соединен с Dвходом сдвигающего регистра 22. При |поступлении седьмого импульса такто;вой частоты регистр 18 оказывается в нулевом состоянии, элемент И 20 запи-. рается, а в первый разряд регистра 22 (верхний по схеме, образует шину 32) записывается 1. В результате на шине.31, связывающей блок -управления с генератором 1 случайных чисел, формируются шесть импульсов, кото.рые необходимы для генерации исходJHoro случайного 6-разрядного двоичного числа. Полученное случайное чиело поступает с выхода генератора 1 на первый вход блока 2 сравнения. Импульс на шине 32, которая образована выходом первого разряда регистра 22 и связывает блок управления с регистром 4 -числа, осугчествляет запись в регистр 4 числа содержимого ячейки блока 5 памяти, адрес которой определяется регистром 6 адреса. При этом старшая часть.регистра б определяет адрес массива ячеек, а младшая часть - адрес ячейки в массиве. Записанное в регистр 4 числа содержимое ячейки блока 5 памяти через регистр 3 маски поступает на другой вход блока 2 сравнения. В рассматриваемом примере для реализации соотношения (1) необходимо три такта. В первый такт проверяются условия F (х, )« S,F (х JJ ) , F(x,6)4.F(Xii) , F (xjjk ,F (х це) F (Хц«) 5.F (х бм) . Пусть S попало в интервал F(XI), F()l, тогда во второй такт проверяются условия F(x, )(xц), F(K4)(x8) , ,F(x«)5,F(xa), F(Xiz)(xis) , Пусть J попало в интервал FCxtt ) , F(x.,6 ) , тогда в третий такт проверяются условия F( ),F(xii ) , F(x., )«5.F(x ) , F(x,ц )6.F (хч5) , F(xis )6,F(x,6 ) . В эти три такта из блока 5 памяти выбираются три ячейки, в которых содержатся следующие группы значенийFfx,6) , F(x ъг) , F(xue) ; F(x 1, ) , F(x s ). f F(x ii) ; F(Xi , F(x,u ), ) . Эти группы сравниваются в блоке 2 сравнения со случайным числом ,. При надлежность числа одному из четырех интервалов указывается в виде ло гической единицы на одном иэ четырех выходов, образующих выходную шину бл ка 2, Результат сравнения поступает в младшую часть регистра б адреса, которая представляет собой сдвигающий регистр, и служит для формирования адреса, по которому из блока 5 памяти выбирается новая группа,значений F(xj), Первая группа F(xi), которая сравнивается в первом такте сравнения, не зависит от с,, пбэтому {адрес ячейки, в которой хранится пер вая группа F(xj), является постоянным. Это достигается путем установ1КИ младааей части регистра б адреса в нулевое состояние перед каждым циклом сравнения. Процесс сравнения обеспечивается следующим образом. Сдвигающий регист 22 выполняет функцию распределителя импульсов, а регистр 26 в сочетаний с элементом -И 27 - функцию счетчика тактов сравнения. При этом первый импульс, поступающий на шину 32, служит для записи в регистр 4 числа очередной группы F(x;). Второй имдульс, который с второго выхода регистра 22 через открытый элемент И 29 поступает на шину 34, служит для записи в регистр, содержащийся в блоке 2 сравнения, результата сравнения. Запоминание результата сравнения необходимо для правильной работы регистра 3 маски, так как в про тивном случае при маскировании разрядов регистра 4 числа изменяется результат предыдущего сравнения, которьай управляет регистром 3 маски, что приводит к изменению результата маскирования. Третий импульс, который с третьего выхода регистра 22 через открытый элемент И 30 поступает на шину 35, служит для записи результата сравнения в младшую часть регистра б адреса.После окончания цикла сравнения из блока 5 памяти в регистр 4 числа считывается группа значений к/, одно из которых является текущим состоянием цепи. Выбор Xj обеспечивается регистром 3 маски. Те части регистра маски, в которые по выходам из блока 2 сравнения поступили логические нули, закрываются. Открытой остается только одна часть, на вход которой поступила 1. Число xj снимается с тех разрядов регистра 4 числа, которые -соответствуют этой открытой части. Считьшание xf и переход к следующей строке стохастической матрицы обеспечиваются изменением режима работы блока управления. Если первая, вторая и третья серии импульсов, сформированных реги ;тром 22, обеспечйвают реализацию цикла сравнения, то последняя четвертая- серия импульсов обеспечивает формирование текущего значения цепи и подготовку к новому циклу работы устройства. Элемент И 27 при этом открывается, так как после каждой серии импульсов в регистр 26 записывается 1, и после третьей серии на всех входах элемента И 27 присутствует 1. Это приводит к запиранию элементов И 29 и 30 и отпиранию элементов И 23 и 25. В результате, второй импульс с регистра 22 поступает не в блок 2 сравнения, а через элемент И 23 на шину 33, связывающую блок управления с регистром 3 маски. Одновременно этот им- . рульс поступает на шины 36 и 35. По шине 35 этот импульс поступает в младшую часть регистра б адреса и устанавливает ее в исходное нулевое состояние, осуществляя тем самым подготовку к новому циклу работы, а по шине 36 он поступает на вход счетчика 13 и второй вход элементов 10. Третий импульс с регистра 22 через элемент И 25 поступает на шины 36 и 35, причем по шине 36 он поступает на первый вход элемента И 14, а по шине 35 - на старшую часть регистра 6 адреса и служит для записи информации в старшую часть регистра 6. Полученное значение х,, представляющее собой текущее состояние цепи, с выхода регистра 4 через регистр 3 маски поступает на первые входы коммутатора 9 и элементов И 10. Импульс блока 7 управления, поступающий с выхода элемента И 23 и устанавливающий в исходное состояние младшую часть регистра б адреса, одновременно поступает на второй, вход элементов И 10, открывает их, и на вход сумматора 11 по модулю два поступает число xj . Сумматор 11 представляет собой набор Т-триггеров, входы которых соединены с соответствующими выходами элементов И 10, и служит для поразрядного суммирования по модулю два Чисел xj. Исходным состоянием сумматора 11 является нулевое. Импульсы, поступ,ающие на второй вход группы 10 элементов, одновременно поступшот на вход счетчика 13, который подсчитывает количество суммированных чисел xi . После сложения га чисел (число m определяет згшанную глубину связности цепи и представляет собой число возможных состояний счетчика 13, включая нулевое) счетчик 13 переполняется и переходит в нулевое состояние, что вызывает появление 1 на выходе элемента ИЛИ-НЕ 12, входы которого соединены с выходг1ми триггеров счетчика 13. При этом результат суммкровання чисел х, с выхода сумматора 11 через коммутатор 9 поступает на вход старшей части регистра б iадреса. Запись этой информации в регистр б осуществляется импульсом блока 7 управления, поступающим с выхода элемента И 25. Записанный в регистр б адреса результат суммирования служит адресом массива ячеек в блоке 5 памяти, по которому записана очередная строка стохастической матрицы цепи.После каждого такого цикла формирования го-связного значения цепи сумматор 11 по модулю два устанавливается в нулевое состояние импульсом записи информации в старшую часть регистра 6. Этот импульс на первый вход элемента И 14, на в.торой вход которого с выхода элемента ИЛИ-НЕ 12 поступает 1. Возникающий на выходе элемента И 14 импульс поступает на вход установки нуля сумматора-11 по модулю два.

Цикл работы блока 7 управления завершается после окончания импульса записи информации в старшую часть регистра 6. При этом очередной тактовый импульс генератора 15 тактовой частоты вызывает появление Ч на последнем выходе регистра 22, что прводит к появлении) 1 на последнем выходе регистра 26. В результате на выходе элемента И 24 появляется 1, которая устанавливает в нулевое соетояние регистры 18, 22 и 26 и одновременно устанавливает в единичное состояние триггер, образованный элементами ИЛИ-НЕ 16 и 17, осуществляя тем сгилам новый пуск блока 7 управления. На этом цикл работы устройства завершается.

В предлагаемом устройстве наряду с формированием простых цепей Маркова, что достигается путем установки счетчика 13 в нулевое состояние.

можно получить более сложные цепи, i.B которых вероятность появления текущего состояния цепи зависит от заданной комбинации предыдущих состояний или от заданного числа состояний. По своим функциональным возможностям предлагаемое устройство может при небольших аппаратурных затратах по сравнению с известным устройством заменить одновременно два устройства одно из которых предназначено для генерации простых цепей Маркова, а второе - для генерации многосвязных цепей Маркова. .

Формула изобретения

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