Устройство для определения вероятностного состояния дискретной системы Советский патент 1985 года по МПК G06F17/18 

выми входами элементов И седьмой группы, второй выход третьего дешифратора соединен с входом останова генератора тактовых импульсов и пер выми BxojciaMH элементов И восьмой и девятой групп, выходы которых подклю чены к соответствующим входам блока индикации, .1с -и выход ячейки памяти каждого столбца матрицы соединен с соответствующим входом k-ro элемента ИЛИ первой группы, выходы которых подключены соответственно к группе входов блока умножения, вторая группа входов которого соединена соответственно с выходами второй группы- элементов ИЛИ, а выходы блока умножения соединены соответственно с первьми входами элементов И десятой группы, вторые входы которых объединены и через второй элемент задержки подключены к выходу элемента ИЛИ, выходы элементов И десятой группы соединены соответственно с информационными входами сумматора, k и выход которого подключен к вторым входам k-x элементов И первой и седьмой групп и третьим входам К-и подгруппы элементов И второй группы, выходы элементов И k-и подгруппы второй группы соединены соответственно с разрядными входами k-ro регистра первой группы, разрядные выходы k -го регистра первой группы соединены соответственно с вторыми входами k -X подгрупп элементов И девятой и шестой групп, выходы элементов И k-й подгруппы шестой группы подключены соответственно к разрядным входам k-го регистра второй

4729

группы, разрядные выходы которого соединены соответственно с вторыми входами k-й подгруппы элементов И третьей группы, выходы k-х элемен- , тов И всех подгрупп третьей группы подключены соответственно к входам k-ro элемента ИЛИ второй группы, выходы элементов И первой группы и разрядные выходы регистра максимального числа подключены соответственно к входам первой и второй групп схемы сравнения, первьш выход которой соединен с третьими входами элементов И пятой группы и через третий элемент .задержки - с третьими входами элеMe iTOB И седьмой группы, выходы которых -Соединены соответственно с разрядными входами регистра максимального числа, второй выход схемы сравнения подключен к третьим входам элементов И четвертой группы, выкодыk-х элементов И четвертой и пятой групп соединены соответственно с входами k-ro элемента ИЛИ третьей группы, выход k -го элемента ШИ третьей группы соединен с первьвч входом k -го триггера группы, второй вход (и-го триггера группы (, М -1) подключен к выходу (71 -го элемента ИЛИ четвертой группы, выходы триггеров группы соединены соответственно с вторыми - входами элементов И восьмой группы, первьй вход fn-ro элемента ИЛИ четвертой группы соединен с выходом (hi+1)-ro элемента И пятой группы, а второй вход р -го элемента ШШ четвертой группы (,П-2) подключен к выходу (р+1)-го элемента ИЛИ четвертой группы.

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ВЕРОЯТНОСТНОГО СОСТОЯНИЯ ДИСКРЕТНОЙ СИСТЕМЫ, содержащее матрицу из м-п ячеек памяти, каждая из которых содержит регистр памяти и группу элементов И, выходы регистра памяти соединены соответственно с первыми входами элементов И группы, вторые входы которых объединены и являются первым адресным входом ячейки памяти, вторым адресным входом которой являются третьи объединенные входы элементов И группы, выходы которых являются группой выходов ячейки памяти, генератор тактовых импульсов, управляющий вход которого является входом запуска устройства, группу триггеров, о т л ичающееся тем, что, с целью расширения функциональных возможностей за счет определения вероятности перехода дискретной системы в любое состояние за зада.нное число тактов и нахождения ее наиболее вероятного состояния, оно дополнительно содер жит с первой по десятую группы элементов И, элемент ИЛИ, четыре группы элементов ШШ, три элемента задержки, блок умножения, сумматор, cxei сравнения, регистр максимального числа, блок индикации-, две группы регистров, два счетчика импульсов по модулю Я , вычитающий счетчик им.пульсов, три дешифратора, причем вторая, третья, шестая и девятая группы элементов И имеют по h подгрупп элементов И каждая, выход генератора тактовых импульсов соединен со счетным входом первого счетчика импульсов по модулю и , разрядные выходы которого подключены соответственно к входам первого дешифратора, нулевой выход которого подк тючен к первым входам элементов И первой и второй группы, а через первый эле.мент задержки - к установочному входу сумматора и счетному входу второго счетчика по модулю п , разрядные (Л выходы которого подключены соответственно к входам второго дешифратора, К-й выход первого дешифратора t 1,И), соединен с соответствугацим входом элемента ИЛИ, первыми адресными входами ячеек памяти к-и строки матрицы и первыми входами k -и подгруппы элементов И третьей группы, выход второго дешифратора соединен с вторыми адресными входами ячеек памяти k-го столбца матрицы, с первыми входами k-х элементов И четвертой и пятой групп и вторыми входа |ми k-и подгруппы элементов И второй группы, нулевой выход второго дешифратора соединен с первыми входами ; элементов И шестой группы и вычитаюU. щим входом вычитающего счетчика, разрядные выходы которого подключены соответственно к входам третьего де шифратора, первый выход которого соединен с вторыми входами элементов И четвертой и пятой групп и пер

1

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

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

л

Недостатком такого устройства является невозможность исследования вероятностных графов.

Наиболее близким к игюбретению является устройство для поиска путей направленного графа, содержа це1е матрицу функциональных ячее:К из П строк (1 - наибольший возможный порядок графа), генератор единичных импульсов, триггеры, переключатели задания

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

Недостатком этого устройства явля ется .отсутствие возможности определять вероятность перехода графа в любое состояние за заданное шагов и на ходить наиболее вероятное состояние графа.

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

Состояние системы отображается в виде вершин графа, дугами которого являются вероятности перехода г.истемы из одного состояния-в другое.

Цель достигается тем, что в устройство,- содержащее матрицу из п. п ячеек памяти, каждая из которых содержит регистр памяти и группу элементов И, выходы регистра памяти соединены соответственно с первыми входами элементов И группы, вторые входы Которых объединены и являются первым адресным входом ячейки памяти вторым адресным входом которой являются третьи объединенные входы элементов И группы, выходы которых являются группой выходов ячейки памяти, генератор тактовых импульсов, управляющий вход которого является входом запуска устройства, группу триггеров введена с первой по десятую группы элементов И, элемент ИЛИ, четьфе группы элементов ИЛИ, три элемента задержки, блок умножения, .сумматор, схема сравнения, регистр максимального числа, блок индикации, две группы регистров, два счетчика -импульсов по модулю hj вьиитающий счетчик импульсоз, три дешифратора, причем вторая, третья, шестая и девятая группы элементов И имеют по П подгрупп элементов И каждая, выход генератора тактовых импульсов соединен со счетным входом первого счетчика импульсов по модулю п, разрядные

выходы которого подключены соответственно к входам первого дешифратора, нулевой выход которого подключен к первым входам элементов И первой и второй группы, а через первьй элемент задержки - к установочному входу сумматора и счетному входу второго счетчика импульсов по модулю fl , разрядные выходы которого подключены соответственно к входам второго дешифратора, k -и выход первого дешифратора (k 1 Т) ) соединен с соответствующим входом элемента ИЛИ, первыми адресными входами ячеек памяти k-й строки матрицы и первыми входами k-и подгруппы элементов И третьей группы, k -и выход второго дешифратора соединен с вторыми адресными входами ячеек памяти k-го столбца матрицы, с первыми входамиk-X элементов И четвертой и пятой групп и вторыми входами k -и подгруппы элементов И второй группы, нулевой выход второго дешифратора соеди1|ен с первыми входами элементов И шестой группы и вычи- танщим входов вычитающего счетчика, разрядные выходы которого подключены соответственно к входам третьего дешифратора, первьй выход которого соединен с вторыми входами элементов И четвертой и пятой групп и первыми L. входами элементов И седьмой гpyппыj второй выход третьего дешифратора соединен с входом останова генератора тактовых импулъсов и первыми входами элементов И восьмой и девятой групп, выходы которьрс подключены к соответствующим входам блока индикации, k.-й выход ячейки памяти каждого столбца матрицы соединен с соответствуняцими входами k -го элемента ИЛИ первой группы, выходы которых подключены соответственно к перовой группе входов блока умножения, вторая группа входов которого соединена cooTBeTCTBejiHo с выходами второй - группы элементов ШШ, а выходы блока умножения соединены соответственно с первыми входами элементов И десятой группы, вторые входы которых объединены и через вто рой элемент задержки Подключены к выходу элемента ИЛИ, выходы элементов И десятой группы соединены соответственно с информационными входами сумматора, k-и выход которого подключен к вторым входам k -х элементов И первой и седьмой групп и третьим входам k-и подгруппы элементов и второй группы, выходы элементов И k -и подгруппы второй группы соединены соответственно с разрядными входами к -го регистра первой группы, разрядные выходы k го регистра пер- 5 вой группы соединены соответственно ;с вторыми входами k -х подгрупп элементов И девятой.и шестой групп, выходы элементов И ; -и подгруппы шестой группы подключены соответст- венно к разрядным входам k -го регистра второй группы, разрядные выходы которого соединены соответственно с вторыми входами k -и подгруппы элементов И третьей группы, выходы k-х элементов -И всех подгрупп третьей группы подключены соответственно к входам k -го элемента ИЛИ вторс й группы, выходы элементов И первой группы и разрядные выходы регистра 20 максимального числа подключены соответственно к входам первой и второй групп схемы сравнения, первый выход которой соединен с третьим входами элементой И пятой группы и через тре- 25. тий элемент задержки - с третьими входами элементов И седьмой группы, выходы которых соединены соответственно .с разрядными входами регистра

максимального числа, второй выход зо схемы сравнения подключен к третьим входам элементов И четвертой группы, выходы k -X элементов И четвертой и пятой групп соединены соотве ственно с входами k -го элемента ШШ. третьей j. группы, выход k -го элемента ИЛИ третьей группы соединен с первым входом -го триггера труппы, второй вход w -го триггера группы (1т)1,п-1) подключен к выходу m-го элемен- 40 та ИЛИ четвертой группы, выходы триггеров Группы соединены соответственно с вторыми входами элеме.нтов И восьмой группы, первый, вход m -го

элемента ИЛИ четвертой группы соеди- 4S нен с выходом (ir +D-ro элемента И пятой группы, а второй вход р -го элемента ИЛИ четвертой группы (, ) подключен.к выходу (р+1)-го

элемента ИЛИ четвертой группы. . j I

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

Устройство содержит матрицу 1 размером п , состоящую их ячеек 2 55 памяти, генератора 3 тактовых импульсов, первый 4,. второй 5 и третий 6 дешифраторы, первьш 7 и второй 8

счетчики импульсов по модулю п , вычитающий счетчик импульсов 9, первый 10, второй 11, третий 12 элементы задержки, схему 13 сравнения, блок 14 умножения, сумматор 15, регистр 16 максимального числа, вторую 17 и первую 18 группы регистров, группу триггеров 19, блок 20 индикации, третью 21, вторую 22, шестую 23, девятую 24 первую 25, седьмую 26, десятую 27, четвертую 28, пятую 29 и восьмую 30 группы элементов И, первую 31, вторую 32, третью 33 и четвертую 34 группы элементов ИЛИ, элемент ИЛИ 35, управляющий вход 36.

Каждая ячейка памяти содержит группу элементов И 37, регистр памяти 38, первый 39 и второй 40 адресные входы.

Схема сравнения 13, регистр 16, группы элементов И 25 и 26, элемент задержки 12 представляют собой узел для определения максимгального значения вероятностей перехода k-х вершин. .

БЛОК умножения 14 предназначен для перемножения вероя ностей перехода k -X вершин на исходное вероятное состояние системы, хранятееся в ре.гистрах 17.,

Сумматор 15 предназначен для формирования значения вероятности перехода |( -и вершины.

Регистры 18 предназначены для формирования и хранения вероятностей перехода дискретной системы на N-M шаге.

Триггеры 19 предназначены для фиксации номеров k -X вершин, имеющих наиболее вероятные состояния за N шагов.

Группы элементов И 21-24 имеют до ) подгрупп.

Элементы устройства соединены между собой следующим образом.

Выход генератора 3 тактовых импульсов соединен со счетным входом первого счетчика 7 импульсов по модулю П , разрядные выходы которого подключены соответственно к входам первого дешифратора 4, нулевой выход которого подключен к п.ервым входам элементов И первой 25 и второй 22 группы, а через первый элемент 10 задержки к установочному входу сумматора 15 и счетному входу, второго счетчика 8 импульсов по модулю 1 , разрядные выходы которого подключены соответственно к входам второго дешифратора 5, k -и выход первого д ешифратора 4 (V 1, п ) соединен с соответствующим входом элемента ИЛИ 35, первыми адресными входами ячеек 2 памяти k-и строки матрицы 1 ячеек памяти и первыми входами k -и подгруппы элементов И 21 третьей группы, k й выход второго дешифратора 5 соединен с вто рыми адреснь ш ячеек 2 памяти k -го столбца матрицы ячеек памяти, с первыми входами k -х элементов И четвертой 28 и пятой 29 групп вторыми входами подгруппы элементов И 22 второй группы, нулевой выход второго дешифратора 5 соединен с первыми входами.элементов И 23 шес той группы и вьгчитающим входом вычитающего счетчика 9, разрядные выходы которого подключены соответственно к входам третьего дешифратора 6, пер вый выход которого соединен с вторыми входами элементов И четвертой 28 и пятой 29 rpynti и первыми входами элементов И 26 седьмой-группы,второйвыход третьего дешифратора 6 соединен с входом.останова генератора 3 тактовых импульсов и первыми входами элементов И восьмой 30 и девятой 24 групп, выходы которых подключены к соответствующим входам блока 20 инди кации, k -и выход ячейки 2 памяти каждого столбца матрицы 1 ячеек памяти соединен с соответствующим входом k го элемента ИЛИ 31 первой группы,,выходы которых подключены со ответственно к первой группе входов блока 14 умножения, вторая группа входов которого соединена соответст. венно с выходами второй группы элементов ИЛИ 32, а выходы блока 14 умножения соединены соответственно с первыми входами элементов И 27 десятой группы, вторые входы которых объединены и. через второй элемент 1 задержки подключены к выходу элемента ИЛИ 35, выходы элементов И 27 десятой Труппы соединены соответственно с информационными вxoдa и сумматора 15, k -и выход которого под ключей к вторым входам k -х элементов И первой 23. и седьмой 26 групп и третьим входом k-и подгруппы элементов И 22 второй группы, выходы элементов И 22 k-и подгруппы второй группы соединены соответственно с разрядными входами k-го регистра 18 первой группы, разрядные выходы k -г 1 29 8 . регистра 18 первой группы соединены соответственно с вторыми входами k -X подгрупп элементов И девятой 24 и шестой 23 групп, выходы элементов И 23 k-и подгруппы шестой группы подключены соответственно к разрядным входам к -го регистра 17 второй группы, разрядные выходы которого соединены соответственно с вторыми входами k -и подгруппы элементов И 21 третьей группы, выходы k -X элементов И 21 всех подгру пп третьей группы подключены соответственно к входам k-го элемента ИЛИ 32 второй группы, выходы элементов И 25 первой группы и разрядные выходы регистра 16 максимального числа подключены соответственно к входам первой и второй группы схемы 13 сравнения, первый выход которой соединен с третьими входами элементов И 29 пятой группы и через третий элемент 12 задержки - с третьими входами элементов И 26-седьмой группы, выходы которых соединены соответственно с разрядными входами регистра 16 максимального числа, второй выход схемы сравнения подключен к третьим входам элементов И 28 четвертой группы, вы- ходы k -X элементов И -четвертой 28 и пятой 29 групп соединены соответст- венно с входами -k -го элемента ИЛИ 33 третьей группы, выход k го элемента ИЛИ 33 третьей группы соединен с первым входом k -го триггера 19 группы, второй вход П} го триггера 19 группы (m 1, h -1) подключен к выходу Кп-го элемента ИЛИ 34 четвертой группы, выходы триггеров 19 группы соединены соответственно с вторыми входами элементов И 30 восьмой группы первый вход W -го элемента ИЛИ 34.четвертой группы соединен с выходом (|т1+1)-го элемента И 29 группы, а второй вход р -го элемента ИЛИ 34 четвертойгруппы (, Я-2) подключен к выходу (р+1)-го элемента ИЛИ 34 четвертой группы. Устройство работает следующим образом. Исходное состояние: регистры 38 ячеек 2 матрицы 1 хранят вероятности перехода - k -х верщин системы, в различные состояния, регистры 17 содержат исходное вероятное состояние системы, счетчик 17 и сумматор 15 в нулевом состоянии, счетчик 8 - в единичном состоянии, вычитающий счетчик 9 - в состоянии/ N+1 (N - количество шагов), триггеры 19 и регистры 18 и 16 - в нулевом состоянии. Работа устройства начинается при поступлении сигнала Н:а вход 36. Генератор тактовых импульсов 3, счетчи 7 и .дешифратор 4 вырабатывают последовательность сигналов на выходных k-X шинах дешифратора 4 (,2, . . . ,h 0), которые возбуждают на считьшание информации с регистров 38 k-к строк матрицы 1 и k -X регистров 17. Дешифратор 5 имеет сигнал на первой выходной шине (так как счетчик 8 в единичном состоянии). В таком состоя НИИ происходит считьюание информации последовательно с регистров 38 перво го столбца матрицы 1 и через группу элементов ИЛИ 31 и вьщача ее на первьй вход блока умножения 14, на второй вход которого подается информация -последовательно с регистров 17 через группу элементов ИЛИ 32. В результате последовательного умножения вероятностей перехода элементов первого столбца и вероятностей исходног состояния и последующего суммировани через группу элементов И 27 полученных произведений в сумматоре 15 сфор мировано значение вероятного состояния первой вершины.. Это значение записывается в регистр 18 через группу элементов И 22 по разрешающим сигналам с первой выходной шины дешифратора 5 и с первой выходной шины дешифратора 4. Сигнал с нулевой выходной шины дешифратора 4, пройдя через элемент задержки 10, устанавли вает сумматор 15 в нулевое состояние а в счетчике 8 увеличивает его содержимое на единицу, таким образом на считьшание подключается второй столбец ячеек памяти матрицы. Считывание второго столбца регистров 38 и рсгистров 17 осуществляется аналогич но последовательно при поступлении сигналов . на вьгходные k -шины дешифратора 4. Информация с регистров посту пает на блок умножения 14 и в ре- зультате последовательного суммирования в.сумматоре 15 получается значение вероятного состояния второй верщины, которое записьшается в регистр 182 Аналогично формируются значения вероятных Состояний остальных вершин на первом шаге и заканчивается этот процесс при появлении сигнала .на выходной.нулевой- шине 9 дешифратора 5. При этом регистры 18 содержат значение вероятного состояния системы после первого шага.Сиг нал с нулевой шины дешифратора 5 поступает на вход вычитающего счетчика 9, уменьшив его состояние на единицу. Вычитающий счетчик 9 предназначен для контроля количества шагов. Информация с регистров 18 переписывается соответственно в регистры 17 по сигналу с выходной нулевой шины дешифратора 5 и аналогично определяется вероятное состояние системы за второй.и т.д. шаг. На последнем шаге (вычитающий счетчйк 9 в единичном состоянии,сигнал на первой выходной шине дешифратора 6) производится анализ значений вероятных состояний k -X вершин и выбираются максимальные значения, которые фиксируются триггерами 19, Это достигается следующим образом. На схему сравнения 13 поступают значения вероятностей Е с сумматора 15 и с регистра 16, хранящего максимальное значение вероятности . Сигнал на первом выходе схемы 13 сравненияпоявляется при Р,, на втором выходе - при Р ) С1игнал с перв.ого выхода схемы 13 устанавливает k-и триггер группы 19 в единичное состояние через элемент И 29, элемент ИЛИ 33, при этом все предьщущие триггеры группы 19 через элементы Ш1И 34 устанавливаются в нулевое состояние. Сигнал с второго выхода схемы 13 устанавливает 1с-й триггер группы 19 в единичное состояние без изменения состояния предьщущих триггеров. При появлении сигнала на выходной нулевой шине дешифратора процесс форкировачия вероятного состояния дискретной системы за требуемое число шагов заканчивается и блокируется работа генератора 3, и через группы элементов И 24 на блок 20 вьщается содержимое регистров 18, а именно значения вероятного сх) стоя ния дискретной системы, а через элементы И 30 выдается состояние триггеров 19, единичное состояние К-х триггеров регистрирует наиболее вероятное состояние k-х вершин. Предлагаемое устройство позволяет оперативно определять вероятность перехода дискретной системы в любое состояние за N шагов и находить ее наиболее вероятное сос:гояние.