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

)е свидет06 Р 7/4 ьство ССС 1968.тво СССР, 1969 (пр видетель 6 Р 15/32 входом элемента ИЛИ ервыми адресамяти 1 -й строходами-й третьей группы, фратора соедиви входами ячематрицы, с лементов И четжи входами ячеек ии матрицы и первымиодгруппы элементов-и выход второго де нен с вторыми адресн ек памяти 1 -го столб первьии входами 1 -х ертои и пятои г -й по г ппы ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) (57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯВЕРОЯТНОСТНОГО СОСТОЯНИЯ ДИСКРЕТНОЙСИСТЕМБ 1, содержащее матрицу из п пячеек памяти, каждая из которых содержит регистр памяти и группу элементов И, выходы регистра памяти соединены соответственно с первыми входами элементов И группы, вторые входыкоторых объединены и являются первымадресным входом ячейки памяти, вторым адресным входом которой являютсятретьи объединенные входы элементов И группы, выходы которых являютсягруппой выходов ячейки памяти, генератор тактовых импульсов, управляющийвход которого является входом запускаустройства, группу триггеров, о т л ич а ю щ е е с я тем, что, с цельюрасширения функциональных возможностей за счет определения вероятностиперехода дискретной системы в любоесостояние за заданное число тактови .нахождения ее наиболее вероятногосостояния, оно дополнительно содержит с первой по десятую группы элементов И, элемент ИЛИ, четыре группыэлементов ИЛИ, три элемента задержки, блок умножения, сумматор, схемусравнения, регистр максимальногочисла, блок индикации, две группы регистров, два счетчика импульсов помодулю 11, вычитающий счетчик им.пульсов, три дешифратора, причемвторая, третья, шестая и девятая группы элементов И имеют по И подгруппэлементов И каждая, выход генератора тактовых импульсов соединен сосчетным входом первого счетчика импульсов по модулю И, разрядные выходы которого подключены соответственно к входам первогодешифратора,нулевой выход которого подключен кпервым входам элементов И первой ивторой группы, а через первый элемент задержки - к установочному входу сумматора и счетному входу второго счетчика по модулю 1, разрядныевыходы которого подключены соответственно к входам второго дешифратора,-й выход первого дешифратора=1, И ), соединен с соответствующим в рупп и вторыми входа ;ми 1 д ру элементов И второй группы, нулевой выход второго дешиф. ратора соединен с первыми входами: элементов И шестой группы и вычитающим входом вычитающего счетчика, разрядные выходы которого подключены соответственно к входам третьего де шифратора, первый выход которого соединен с вторыми входами элементов И четвертой и пятой групп и пер 11 выми входами элементов И седьмой группы, второй выход третьего дешифратора соединен с входом остановагенератора тактовых импульсов и первымн входами элементов И восьмой и девятой групп, выходы которых подклю. чены к соответствующим входам блока индикации, .1 -й выход ячейки памяти каждого столбца матрицы соединен с соответствующим входом 1-го элемента ИЛИ первой группы, выходы которых подключены соответственно к первой группе входов блока умножения, вторая группа входов которого соединена соответственно с выходами второй группы элементов ИЛИ, а выходы блока умножения соединены соответственно с первьии входами элементов И десятой группы, вторые входы которых объединены и через второй элемент задержки подключены к выходу. элемента ИЛИ, выходы элементов И десятой группы соединены соответственно с информационными входами сумматора,-й выход которого подключен к вторым входам -х элементов И первой и седьмой групп и третьим входам 1 -й подгруппы элементов И второй группы, выходы элементов И к -й подгруппы второй группы соединены соответственно с разрядными входами -го регист- ра первой группы, разрядные выходы 1 -го регистра первой группы соедйнены соответственно с вторыми входами-х подгрупп элементов И девятой и шестой групп, выходы элементов И 1 -й подгруппы шестой группы подключены соответственно к разрядным входам к -го регистра второй 64729группы, разрядные выходы которого соединены соответственно с вторыми входами 1 -й подгруппы элементов И третьей группы, выходы ( -х элементов И всех подгрупп третьей группы подключены соответственно к входам 1-го элемента ИЛИ второй группы, выходы элементов И первой группы и разрядные выходы регистра максимального числа подключены состветственно к входам первой и вторсй групп схемы сравнения, первый выход которой соединен с третьими входами элементов И пятой группы и через третий элемент задержки - с третьими входами элементов И седьмой группы, выходы которых .соединены соответственно с разрядными входами регистра максимального числа, второй выход схемы сравнения подключен к третьим вхоцам элементов И четвертой группы, выходы 1 -х элементов И четвертой и пятой групп соединены соответственно с входами 1-го элемента ИЛИ третьей группы, выход 1 -го элемента ИЛИ третьей группы соединен с первым входом 1 -го триггера группы, второй вход М-го триггера группы ъ=1, 0 -1) подключен к выходу Ф -го элемента ИЛИ четвертой группы, выходы триггеров группы соединены соответственно с вторыми входами элементов И восьмой группы, первый вход п-го элемента ИЛИ четвертой группы соединен с выходом 1+1)-го элемента И пятой группы, а второй вход-го элемента ИЛИ четвертой группы (=1, О -2) подключен к выходу (+1)-го элемента ИЛИ четвертой группы.1Изобретение относится к вычислительной технике и может быть использовано при использовании сложных распределенных дискретных систем.Известно устройство для поиска путей направленного графа, содержащее генератор, элементы И, управляющий и программирующие переключатели, столбец буферных регистров, столбец и строку сдвоенных выходных ключей 111 . 2Недостатком такого устройства является невозможность исследования вероятностных графов.Наиболее близким к изобретению является устройство для поиска путей направленного графа, содержащее матрицу функциональных ячеек из й строк (И. - наибольший возможный порядок графа), генератор единичных импульсов, триггеры, переключатели задания3 11647 начальной и конечной вершин, первый выход каждой функциональной ячейки, находящейся в 1-м столбце матрицы,соединен через программирующий переключатель задания конечной вершины 1-го столбца с сигнальным входом управляемого переключателя ячейки 1-й строки, второй выход каждой функциональной ячейки, находящейся в 1-й строке, соединен с блокирующими вхо дами всех ячеек 1-го столбца. 2 .Недостатком этого устройства является, отсутствие возможности определять вероятность перехода графа в любое состояние эа заданное шагов и на ходить наиболее вероятное состояние графа.Цель изобретения - расширение функциональных возможностей за счет определения вероятности перехода дис кретной системы в любое состояние за заданное число тактов и нахождения ее наиболее вероятного состояния.Состояние системы отображается в виде вершин графа, дугами которого 25 являются вероятности перехода системы из одного состояния .в другое.Цель достигается тем, что в устройство, содержащее матрицу из и п ячеек памяти, каждая из которых со- З 0 держит регистр памяти и группу элементов И, выходы регистра памяти соединены соответственно с первыми входами элементов И группы, вторые входы Которых объединены и являются З 5 первым адресным входом ячейки памяти, вторым адресным входом которой являются третьи объединенные входы элементов И группы, выходы которых являются группой выходов ячейки памяти, 40 генератор тактовых импульсов, управляющий вход которого является входом запуска устройства, группу триггеров, введена с первой по десятую группы элементов И, элемент ИЛИ четыре 45 группы элементов ИЛИ, три элемента задержки, блок умножения, .сумматор, схема сравнения, регистр максимального числа, блок индикации, две группы регистров, два счетчика импульсов 50 по модулю Ивычитающий счетчик импульсов, три дешифратора, причем вторая, третья, шестая и девятая группы элементов И имеют по О подгрупп элементов И каждая, выход ге нератора тактовых импульсов соединен, со счетным входом первого счетчика импульсов по модулю и, разрядные 29выходы которого подключены соответственно к входам первого дешифратора, нулевой выход которого подключен к первым входам элементов И первой и второй группы, а через первый эле- . мент задержки - к установочному входу сумматора и счетному входу второго счетчика импульсов по модулю 6, разрядные выходы которого подключены соответственно к входам второго дешифратора, 1 -й вьюод первого дешифратора ( =1, и ) соединен с соответствующим входом элемента ИЛИ, первыми адресными входами ячеек памяти 1-й строки матрицы и первыми входами 1 -й подгруппы элементов И третьей группы,-й выход второго дешифратора соединен с вторыми адресными входами ячеек памяти-го столбца матрицы, с первыми входами 1 -х элементов И четвертой и пятой групп и вторыми входами 1 -й подгруппы элементов И второй группы, нулевой выход второго дешифратора соединен с первыми входами элементов И шестой группы и вычитающим входой вычитающего счетчика, разрядные выходы которого подключены соответственно к входам третьего дешифратора, первый выход которого соединен с вторыми входами элементов И четвертой и пятой групп и первыми входами элементов И седьмой группы, второй выход третьего дешифратора соединен с входом останова генератора тактовых импульсов и первыми входами элементов И восьмой и девятой групп, выходы которьрс подключены к соответствующим входам блока индикации, .-й выход ячейки памяти каждого столбца матрицы соединен с соответствукщими входами-го элемента ИЛИ первой группы, выходы которых подключены соответственно к первой группе входов блока умножения, вторая .группа входов которого соединена соответственно с выходами второй группы элементов ИЛИ, а выходы блока умножения соединены соответственно с первыми входами элементов И десятой группы, вторые входы которых объединены и через второй элемент задержки подключены к выходу элемента ИЛИ, выходы элементов И десятой группы соединены соответственно с информационными входами сумматора, 1 -й выход которого подключен к вторым входам 1 -х элементов И первой и седьмой групп и третьим входам 1 -й подгруппы злемен 164729й51015 30 тов И второй группы, выходы элементов И . -й подгруппы второй группысоединены соответственно с разряднымивходами 1 -го регистра первой группыразрядные выходы к -го регистра первой группы соединены соответственнос вторыми входами 1 -х подгрупп элементов И девятойи шестой групп,выходы элементов И .к - й подгруппышестой группы подключены соответственно к разрядным входам-го регистра второй группы, разрядные выхо.. ды которого соединены соответСтвеннос вторыми входами 1 в ,й подгруппы элементов И третьей группы, выходы-хэлементов И всех подгрупп .третьейгруппы подключены соответственно квходам-го элемента ИЛИ второйгруппы, выходы элементов И первойгруппы и разрядные выходы регистрамаксимального числа подключены соответственно к входам первой и второй. групп схемы сравнения, первый выходкоторой соединен с третьим входамиэлементов И пятой группы и через третий элемент задержки - с третьимивходами элементов И седьмой группы,выходы которых соединены соответственно с разрядными входами регистрамаксимального числа, второй выходсхемы сравнения подключен к третьимвходам элементов И четвертой группы,выходы к -х элементов И четвертой ипятой групп соединены соответственнос входами-го элемента ИЛИ. третьейгруппы, выход к -го элемента ИЛИтретьей группы соединен с первымвходом к -го триггера группы, второйвход м -го триггера группы (Ь) =1,п)подключен к выходу м -го элемента ИЛИ четвертой группы, выходы триггеров группы соединены соответственно с вторыми входами элементов Ивосьмой группы, первый. вход Ф -гоэлемента ИЛИ четвертой группы соединен с выходом (в+1)-го элемента Ипятой группы, а второй вход р -гоэлемента ИЛИ четвертой группы (=1,Ь) подключен. к выходу (+1)-гоэлемента ИЛИ четвертой группы.1На фиг. 1 изображена схема предла-гаемого устройства; на фиг,2 - схемаячейки памяти,Устройство содержит матрицу 1 раз.мером Ь 11, состоящую их ячеек 2памяти, генератора 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 представляют собой узел для определения максимального значения вероятностей перехода 1 -х вершин.Блок умножения 14 предназначендля перемножения верояностей перехода 1 -х вершин на исходное вероятное состояние системы, храня.ееся в регистрах 17. Сумматор 15 предназначен для формирования значения вероятности перехода-й вершины.Регистры 18 предназначены для формирования и хранения вероятностей перехода дискретной системы на Н-м шаге.Триггеры 19 предназначены для фиксации номеров 1 -х вершин, имеющих наиболее вероятные состояния за Я шагов.Группы элементов И 21-24 имеют по 11 подгрупп.Элементы устройства соединены между собой следующим образом.Выход генератора 3 тактовых импуль.сов соединен со счетным входом первого счетчика 7 импульсов по модулю11, разрядные выходы которого подключены соответственно к входам первого дешифратора 4, нулевой выход которогоподключен к первым входам элементов И первой 25 и второй 22 группы,а через первый элемент 10 задержки -к установочному входу сумматора 15 исчетному входу второго счетчика 8 импульсов по модулю 11, разрядные выходы которого подключены соответствен164но к входам второго дешифратора 5, 1 -й выход первого дешифратора 4 ( 1 =1, и ) соединен с соответствующим входом элемента ИЛИ 35, первыми адресными входами ячеек 2 памяти 1 -й строки матрицы 1 ячеек памяти и пер 1выми входами ц -й подгруппы элементов И 21 третьей группы,-й выход второго дешифратора 5 соединен с вторыми адресными входами ячеек 2 памя О ти-го столбца матрицы ячеек памяти, с первыми входами 1 -х элементов И четвертой 28 и пятой 29 групп и вторыми входами-й подгруппы элементов И 22 второй группы, нулевой 15 выход второго дешифратора 5 соединен с первыми входами. элементов И 23 шестой группы и вычитающим входом вычитающего счетчика 9, разрядные выходы которого подключены соответственно 20 к входам третьего дешифратора 6, первый выход которого соединен с вторыми входами элементов И четвертой 28 и пятой 29 групп и первыми входами элементов И 26 седьмой группы, второй 25 выход третьего дешифратора 6 соеди-. нен с входом.останова генератора 3 тактовых импульсов и первыми входами элементов И восьмой 30 и девятой 24 . групп, выходы которых подключены к ЗО соответствующим входам блока 20 инди. кации, 1 -й выход ячейки 2 памяти каждого столбца матрицы 1 ячеек памяти соединен с соответствующим входом-го элемента ИЛИ 31 первой35 группы, выходы которых подключены соответственно к первой группе входовблока 14 умножения, вторая группавходов которого соединена соответственно с выходами второй группы эле О ментов ИЛИ 32, а выходы блока 14умножения соединены соответственно спервыми входами элементов И 27 деся"той группы, вторые входы которыхобъединены и через второй элемент 11 45задержки подключены к выходу элемента ИЛИ 35, выходы элементов И 27десятой группы соединены соответственно с информационными входами сум.матора 15,-й выход которого подключен к вторым входам 1 -х элемен тов И первой 25 и седьмой 26 групп и третьим входом к -й подгруппы элементов И 22 второй группы, выходыэлементов И 22 к -й подгруппы второй 55группы соединены соответственно с разрядными входами к -го регистра 18 первой группы, разрядные выходы к -го 729 8регистра 18 первои группы соединенысоответственно с вторыми входами1 -х подгрупп элементов И девятой24 и шестой 23 групп, выходы элементов И 23 к-й подгруппы шестой группы подключены соответственно к разрядным входам 1 -го регистра 17 второй группы, разрядные выходы которого соединены соответственно свторыми входами к -й подгруппы элементов И 2 1 третьей группы, выходы1 -х элементов И 21 всех подгрупптретьей группы подключены соответственно к входам 1 -го элемента ИЛИ 32второй группы, выходы элементов И 25первой группы и разрядные выходы регистра 16 максимального числа подключены соответственно к входам первой и второй группы схемы 13 сравнения, первый выход которой соединен с третьими входами элементов И 29пятой групны и через третий элемент12 задержки - с третьими входами элементов И 26 седьмой группы, выходы которых соединены соответственно с разрядными входами регистра 16 макси. мального числа, второй выход схемы сравнения подключен к третьим вхоцам . элементов И 28 четвертой группы, вы-ходы 1 -х элементов И -четвертой 28 и пятой 29 групп соединены соответственно с входами-го элемента ИЛИ 33 третьей группы, выход-го элемента ИЛИ 33 третьей группы соединенс первым входом-го триггера 19группы, второй вход В -го триггера19 группы (в = 1, Ь - 1) подключен к выходу М-го элемента ИЛИ 34 четвертой группы, выходы триггеров 19 группы соединены соответственно с вторыми входами элементов И 30 восьмойгруппы первый вход ГИ -го элемента ИЛИ 34.четвертой группы соединен с выходом 0 ч+1)-го элемента И 29 пятой группы, а второй вход-го элемента ИЛИ 34 четвертойгруппы (=1, И) подключен к выходу (р+1)-го эле. мента ИЛИ 34 четвертой группы. Устройство работает следующим образом.Исходное состояние: регистры 38 ячеек 2 матрицы 1 хранят вероятности перехода к -х верщин системы. в различные состояния, регистры 17 со- держат исходное вероятное состояние системы, счетчик 17 и сумматор 15 - в нулевомсостоянии, счетчик 8 - в единичном состоянии, вычитающий счет2910 дешифратора 5, При этом регистры 18 содержат значение вероятного состояния системы после первого шага.Сигнал с нулевой шины дешифратора 5 поступает на вход вычитающего счетчика 9, уменьшив его состояние на единицу. Вычитающий счетчик 9 предназначен для контроля количества шагов,Информация с регистров 18 переписывается соответственно в регистры 17 по сигналу с выходной нулевой шины дешифратора 5 и аналогично определяется вероятное состояние системы за второй и т.д. шаг. На последнемшаге (вычитающий счетчик 9 в единичном состоянии, сигнал на первой выходной. шине дешифратора 6) производится анализ значений вероятных состояний к -х вершин и выбираются максимальные значения, которые фиксируются триггерами 19. Эга достигается следующим образом. На схему сравнения 13 поступают значения вероятностей Р с сумматора 15 и с регистра 16, хра- нящего максимальное значение вероятности Р . Сигнал на первом выходе схемы 13 сравненияпоявляется при Р;)Р , на втором выходе - при Р; ==Р . Сигнал с первого выхода схемыйа к13 устанавливает 1 -й риггер группы 19 в единичное состояние через элемент И 29, элемент ИЛИ 33, при этомвсе предыдущие триггеры группы 19через элементы ИЛИ 34 устанавливаются в нулевое состояние. Сигнал с вто.рого выхода схемы 13 устанавливает1-й триггер группы 19 в единичноесостояние без изменения состоянияпредыдущих триггеров, При появлениисигнала на выходной нулевой шине дешифратора процесс формирования вероятного состояния дискретной системыза требуемое число шагов заканчивается и блокируется работа генератора3, и через группы элементов И 24 наблок 20 выдается содержимое регистров 18, а именно значения вероятногосостояния дискретной системы, а через элементы И 30 выдается состояние триггеров 19, единичное состояние 1-х триггеров регистрирует наиболее вероятное состояние-х вершин.Предлагаемое устройство позволяет оперативно определять вероятность .перехода дискретной си:темы в любое состояние за Б шагов и находить ее наиболее вероятное состояние. 9 11647 чик 9 - в состоянии, И+1 (Б - количество шагов), триггеры 19 и регистры 18 и 16 - в нулевом состоянии.Работа устройства начинается при поступлении сигнала на вход 36. Генератор тактовых импульсов 3, счетчик 7 и дешифратор 4 вырабатывают последовательность сигналов на выходных 1 -х шинах дешифратора 4 (1.=1,2О, О), которые возбуждают на считывание 1 О информации с регистров 38 1 -х строк матрицы 1 и-х регистров 17. Дешифратор 5 имеет сигнал на первой выходной шине (так как счетчик 8 в единичном состоянии). В таком состоя нии происходит считывание информации последовательно с регистров 38 первого столбца матрицы 1 и через группуэлементов ИЛИ 31 и выдача ее на первый вход блока умножения 14, на вто рой вход которого подается информация последовательно с регистров 17 через группу элементов ИЛИ 32. В результате последовательного умножения вероятностей перехода элементов пер вого столбца и вероятностей исходного состояния и последующего суммирования через группу элементов И 27 полученных произведений в сумматоре 15 сформировано значение вероятного состояния первой вершины. Это значение записывается в регистр 18 1 через группу элементов И 221 по разрешающим сигналам с первой выходной шины де шифратора 5 и с первой выходной шины З дешифратора 4. Сигнал с нулевой выходной шины дешифратора 4, пройдя через элемент задержки 10, устанавливает сумматор 15 в нулевое состояние, а в счетчике 8 увеличивает его содержимое на единицу, таким образом на считывание подключается второй столбец ячеек памяти матрицы. Считывание второго столбца регистров 38 и регистров 17 осуществляется аналогично последовательно при поступлении сигналов на выходные к -шины дешифратора 4, Информация с регистров поступает на блок умножения 14 и в результате последовательного суммирования в.сумматоре 15 получается значение вероятного состояния второй вершины, которое записывается в регистр 18Аналогично формируются значения вероятных состояний остальных вершин на первом шаге и заканчивается этот процесс при появлении сигнала .на выходной нулевой шине1164729 189/47ВН Зак Тираж 7 ИИПИ Государс по делам изоб 13035, Москва, ЖПодписнота СССР венного коми етений и отк 35, Раушская тии д.4/5 на Патент", г.Ужгород, ул.Проектная, 4 Составитель В.ФукаловРедактор А.Гулько Техред М.Пароцай . . Корректор Е.Сирохман