Устройство для исследования нечетких графов Советский патент 1987 года по МПК G06F15/173 

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

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

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

Устройство содержит генератор 1 тактовых импульсов, дешифратор 2, два элемента 3 и 4 задержки, шесть элементов И 5-10, блок 11 элементов И, два элемента ИЛИ 12 и 13, блок 14 элементов ИЛИ, матрицу 15 узлов принад- лежности, матрицу 16 регистров разбиений, два элемента НЕ 17 и 18, два распределителя 19 и 20 импульсов, выполненные в виде кольцевых регистров сдвига, три регистра 21-23, группу регистров 24 сдвига, два счетчика 25 и 26, группу счетчиков 27, два реверсивных счетчика 28 и29, схему 30 сравнения и два триггера 31 и 32.

Каждый узел матрицы 15 принадлел :- ности содержит регистр 33 и схему 34 сравнения.

Матрица 16 регистров разбиений выполнена на регистрах 35, вход 36 является входом пуска устройства, входы 37 и 38 ЯВЛЯЮТСЯ входами начальной установки устройства.

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

Устройство работает следующим образом.

Под нечетким графом G понимается граф

G IW, .(W)- ,

где W - множество пар вершин графа; л) - множество связывающих их, дуг с заданньгми функциями принадлежности и,. (W) ;

,1.

I

Множество W и функции |ix. ,(W), соответствующие его элементам, задаются матрицей I5 узлов принадлежности, т.е матрицей смежности некратного графа, в узлах которой заданы функции принадлежности ,и (W) .

В исходном состоянии в регистре 22 хранится число -И, где М - максимальная размерность матрицы 15, а в регистре 23 - число М+1. Каждый регистр 24 соответствует одной строке матрицы смежности, а К-й разряд всех регистров 24 соответствует К-му столбцу матрицы 15.

По сигналу, поступающему на вход 37, число М с регистра 22 переписывается в счетчик 28, а число М+1 с регистра 23 - в счетчик 29, низкий потенциал с выхода признака переполнения которого, пройдя через элемент НЕ 18 и элемент ИЛИ 13, открывает элемент И 7.

На вход элемента 3 задержки по входу 38 подается импульс сброса, который сбрасывает регистры 24 сдвига, регистры 14 и счетчики 25-27 и устанавливает в ноль триггеры 32 и 31. Этим же сигналом заносится единица в мла;ц11ий разряд регистров 19 и 20.

Задержанный элементом 3 задержки импульс сброса поступает на входы опроса схем 34 сравнения, при этом сравниваются элементы матрицы 15, хранящиеся в соответствующих регистрах 33 (значения функций принадлежности) с некоторым пороговым значением, хранящимся в регистре 21. Если значение содержимого регистра 33 больше или равно пороговому значению, в соответствующий разряд регистра 24 записывается единица, если меньше, записывается ноль. Устройство готово к работе.

При подаче высокого потенциала на вход 36 устройства на вьтходе элемента И 5 появляются тактовые импульсы, так как он открыт высоким потенциалом с выхода элемента НЕ 17, который снимается лищь при переходе реверсивного счетчика 28 через ноль, т.е. после М-го тактового импульса.

Тактовые импульсы проходят через элемент И 10, который открыт высоким потенциалом с инверсного выхода триггера 31, и поступают на входы сдвига регистров 24. Информация с в.ыхода каждого регистра 24 подается на счетный вход соответствующего счетчика 27

После прихода М-го тактового импульса на вычитающий вход счетчика 28 он переходит в нулевое состояние,так как в исходном состоянии в него записано число М, соответствующее мак-, симальной размерности матрицы 15. На выходе переполнения реверсивного счетчика 28 появляется уровень логи ческой единицы, который устанавливает триггер 31 в единичное состояние и через элемент НЕ 17 запрещает дальнейшее прохождение тактовых импульсов через элемент И 2. За М тактов информация в регистрах 24 переписьгеа- ется полностью и соответствует исходной матрице смежности. При этом в соответствующих счетчиках 2 записано число единиц, содержащееся в соответ- ствзтощей Строке матрицы смежности.

(М+1)-й импульс с генератора 1 тактовых импульсов проходит через элемент И 8, который откроет его высоким потенциалом с выхода признака переполнения реверсивного счетчика 28 и, проходя через элемент ИЛИ 12, переписывает с регистра 22 на реверсивный счетчик 28 число М, соответствующее размеру исходной матрицы смежности. На выходе признака переполнения реверсивного счетчика 28 появля- ется низкий потенциал, который закрывает элемент И 8 и, проходя через эле-25 счетчика 25 и счетчика 26 при усло

мент НЕ 7, разрешает прохождение тактовых импульсов через элемент И 5.

Кроме того, (М+1)-й импульс устанавливает эталонное значение, соответствующее первому уровню верпшн (т.е. все единицы в строке), на счетчике 29, поступая на его вычитающий вход, а так как в нем хранится число (М+1), то после этой операции оно становится равным М. Это эталонное значение сравнивается поочередно с числами, находящимися в счетчиках 2. Информация со всех счетчиков 2 через блок 14 элементов ИЛИ подается на схему 30 сравнения.

Запись информации в матрицу 16 происходит следующим образом.

За такт (М+1)-го импульса проходит сравнение с эталоном числа, находящегося в первом счетчике 27. Если сравнение произошло, схема 30 сравнения вырабатьшает сигнал, который устанавливает триггер 32 в единичное состояние, записывает в первый ре- гистр 38 строки, отведенной под наивысший класс, содержимое счетчика 25, которое соответствует номеру первого счетчика 27. Этот же импульс увеличивает содержимое счетчика 26 позиций на единицу в случае, если при дальнейшей проверке найдены еще строки, входящие в данный уровень. Если же сравнения не произошло, все схемы остаются в первоначальном состоянии.

Следующий тактовый импульс через элемент И 5 поступает на вычитающий вход счетчика 28, проходит через элемент И 6, открытьй высоким потенциалом с выхода триггера 31, и поступает на регистр 19 и счетчик 25 номера строк матрицы смежности . Под действием тактового импульса единица в регистре 19 сдвига ется на один разряд, разрешая прохождение через блок 11 элементов И на схему 30 сравнения информации с второго счетчика 27, и увеличивает содержимое счетчика 25 5 на единицу, что соответствует второй строке.

Таким образом, по приходу тактовых импульсов содержимое всех счетчиков 27 поочередно подается на схему 30 сравнения и при совпадении с эталонным значением в соответствующий регистр 14 записывается номер строки матрицы смежности. При этом изменяется состояние регистра 9,

0

5

о

5

0

5

ВИИ, что сравнение является неоднократным.

После того как проверено содержимое всех счетчиков 27 цо данному уровню, содержимое счетчика 28 становится равным нулю, на его выходе признака переполнения появляется высокий потенциал, который, проходя через элемент НЕ 17, запрещает прохождение тактовых импульсов с выхода генератора 1 через элемент И 5. В исходном состоянии на регистре 20 единица находится в младшем разряде, (М+1)-и импульс, пройдя через элемент 8 И, установит в счетчик 28 чис- число М, поступит на вычитающий вход счетчика 29 и установит число минус один. Если в предыдущем шаге были сравнения, триггер 20 находится в единичном состоянии и разрешает прохождение (М+1)-го импульса через элемент И 9 на вход сдвига кольцевого сдвигового регистра 20 и на вход установки в ноль счетчика 26.

Под действием этого импульса единица в регистре 20 перемещается на один разряд, и на следующем этапе работы информация записывается в следующую строку матрицы 16, что соответствует новому уровню. Тот же (М+1)-и импульс, задержанный во вре- |мени элементом 33 задержки на время, необходимое для перемещения единицы в регистре 20 и установки в ноль

счетчика 26, установит в ноль триг- гер 32, и процесс работь) устройства повторяется.

После того как (М+)-й импульс генератора 1 тактовых импульсов на очередном шаге работы устройства установит на реверсивном счетчике 29 значение ноль, т.е. значение функции принадлежности низшего уровня вершин, на его выходе признака переполнения появляется высокий потенциал, который, пройдя через элемент НЕ 18, постзшает на элемент ИЛИ 13, на выходе которого появляется высокий потенциал, так как он открыт высоким потенциалом с выхода элемента НЕ 17. После того как содержимое счетчика 28 достигнет ноля, на его выходе признака переполнения появляется высокий потенциал, который, проходя че рез элемент НЕ 7 и элемент ИЛИ 13, закрывает элемент И прещает прохождение

7 и тем самым затактовых импульсов с генератора ва завершена.

1. Работа устройстФормула изо. бретения

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

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

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

255036

выход третьего элемента И подключен к первым входам четвертого и пятого элементов И и вычитающему входу первого реверсивного счетчика, выход признака переполнения которого подключен к информационному входу первого триггера, входу первого элемента НЕ и второму входу второго элемента И, выход которого подключен к выfO читаюш,ему входу второго реверсивного счетчика, первому входу шестого элемента И, входу элемента задержки и первому входу первого элемента ИПИ, выход которого подключен к входу писи первого реверсивного счетчика и входу чтения первого регистра, выход которого подключен к информационному входу первого реверсивного счетчика, прямой выход первого триггера

20 подключен к второму входу четвертого элемента И, выход которого подключен к тактовому входу первого распределителя импульсов и счетному входу первого счетчика, информационньй выход

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

зо первому входу К-го блока элементов И

0

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

5

0

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

255038

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

fO

Изобретение относится к вычислительной технике, может быть использовано для исследования нечетких не- кратных графов и позволяет разбить множество вершин нечеткого графа на уровни по количеству смежных ребер, функция принадлежности которых не меньше заданного значения. С этой целью в матрице смежности графа заданы значения функций принадлежности всех ребер графа. В момент подачи сигнала начальной установки устройства, значения функций принадлежности сравниваются с заданным значением, в результате чего формируется новая матрица смежности, в которую входят только те ребра, функция принадлежности которых не меньше заданной. После пуска устройства подсчитьшается количество смежньк ребер дпя каждой вершины графа и во все вершины последовательно сравниваются по количеству смежных ребер с эталонами уровней: от высшего - все единицы в столбце матрицы смежности, до низшего - все ноли в столбце матрицы смежности. Белу- а чае совпадения количества смежных ребер с эталоном номера соответствую- mjrx вершин записьшаются в регистры тех строю матрицы разбиений, которые соответствуют уровню, заданному эталоном... 1 ил. S (Л со ю ел СП

/5

Редактор Н.Рогулич

Составитель А.Мишин

Техред И.Попович Корректор Л.Пилипенко

Заказ 3112/46 Тиразк 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Рашуская наб., д.4/5

Производственно-полиграфическое предприятие,г.Ужгород,ул.Проектная,4