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

(19) (1 02 51)4 С 0 ОПИСАНИЕ ИЗОБРЕТЕНН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ НОМИТЕПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИПРИ ГКНТ СССР(71) Таганрогский радиотехнический институт им. В,Д;Калмыкова (72) В,Н,Решетняк, В,П,Карелин и А,Н,Мелихов(56) Авторское свидетельство СССР 9 1376079, кл, С 06 Р 7/02, 1986,Авторское свидетельство СССР У 497583, кл, С 06 Р 7/02 1974, (54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ МНОЖЕСТВ(57) Изобретение относится к техни ческой кибернетике и может быть ис пользовано для построения техничес ких средств классификации, распьзнавания образов, поиска информации 2 автоматизации принятия решений в не-четких условиях, Целью изобретения является расширение функциональных возможностей, Устройство содержит блок вычитания 3, сумматор 4, регист " ры 5, 20, 21, схемы сравнения 6, 15, счетчик 11, элемент И 10, элементы ИЛИ 13, 18, элементы задержки 16, 17, Блок вычитания содержит преобразователи прямого кода в дополнительный и сумматор, Блок формирования результата содержит элементы И, делитель, шинные формирователи, Устройство позволяет определять степень сходства нечетких множеств и отыскивать адрес нечеткого множества из не-которой совокупности хранящихся в ОЗУ, которое имеет максимальное сход,ство с заданным множеством, 2 з,п,ф-лы, 3 ил,Изобретение относится к техничес-кой кибернетике и может быть использовано для построения технических, -средств классификации, распознаванияобразов, поиска информации и автоматизации принятия решений в нечеткихусловиях,Устройство предназначено для опре; деления степени С сходства (нечеткого равенства) двух нечетких мно ижеств А и В и отыскания из совокупности нечетких множеств тако го множества В, которое имеетмаксимальную степень С сходства с заданным нечетким множеством, А, т,е, минимально отличается от А,Здесь степень С сходства нечеткого, равенства двух нечеткик множествА= а а а а,и ) и В = Ь Ь 1, Ьа ЬДопределяется по формуле С(А,В)11 а, -Ь;ш=1-К(А,В), где К(А,В)1=1степень различия между множествамиА и В, =1,ш,Числа а;, Ь;, 1=1,ш, С(А,В),К(А,В) в устройстве находятся винтервале 0, 1 и представленыи-разрядными двоичными кодами,30Степень сходства (нечеткогоравенства) нечетных множеств А и Вопределяется следующим образом: С(А,В)=, с,/т=, (1-аЬ;)/тп= 35)=- 1-К/ш,40 где К= , г, Среди совокупности нечетких множеств В , где 1=1,К, наиболее близким к мйожеству А будет такое мно жество, для которого степень сходствах па хва С(А,В)=1 С(А,В 1)=-3 1 л т ош тЛи аАс .1 (,С а -Ъ)) 50 где К(А,В) - степень различия множеств А и ВаЦель изобретения - расширение функциональных возможностей, путем определения степени сходства (нечеткого равенства) нечетких множестви в отыскивании адреса того нечеткого множества из заданной совокупности хранящихся в ОЗУ, которое имеет максимальное сходство (минимальное отличке) с заданным.На фиг, показана Функциональная схема устройства; на фиг,2 в .функ-.циональная схема блока вычитания;на фиг,З - функциональная схема блока формирования результата,Устройство содержит. входы компонентов первого 1 и второго 2 множеств,. блок 3 вычитания, сумматор 4,регистр 5, схему 6 сравнения, коммутатор 7, вход 8 запуска, вход 9 синхронизации, элемент И 10, счетчик 11,вход 12 начальной установки, элементИЛИ 13, вход 14 размерности множествсхему 15 сравнения, элементы 16 и 17задержки, элемент ИЛИ 18, вход )9 адреса множеств, регистры 20 и 21, входы 22 и 23 соответственно получениярезультата и управления выдачей результата, блок 24 Формирования результата, выходы 25 и 26 соответственно степени сходства множеств и адреса множества,Блок вычитания содержит преобразователь прямого кода 27 в дополнительный, сумматор 28, преобразователь29 прямого кода в дополнительный,выход 30.Блок формирования результата со-стоит из входов 31 и 32, элементов И33 и 34, делителя 35, шинного форми,рователя Зб с инверсией, входа 37 ишинного Формирователя 38,Преобразователи 27 и 29 могут бытьреализованы по схеме двустороннегопреобразователя прямого кода в допол"нительный и наоборот,Матричный делитель 35 может бытьреализован по схеме матричного делителя, на входы которого подаются 2 иразрядов делимого и и разрядов делителя, а на выходе которого Формируются и разрядов частного,Блок 3 служит для получения модуля разности г; =1 а;-Ь;1 элементов Аи В, где а, Е А, Ь; Е В, 1=1,ш, шразмерность (число компонентов),Назначение блока 24 устройства состоит в определении степени сходства С(А,В) найденного множества В с анализируемым множеством А и вйделе 5 15256нии на выходах устройства С(А,В ) иА 3 В 1 - адреса множества ВАлгоритм работы устройства следующий,5Имеется исходная совокупность эталонных нечетких множеств В , где31=1,К; К - число множеств, Средиэтой совокупности необходимо отыскать такое множество В , которое 10имеет минимальную степень различияс анализируемым нечетким множествомА, запомнить адрес этого множества иопределить его степень сходстваС(А,В)В устройстве выполняется поэлементное сравнение множества А =аа а, с каждым множествомЬ 1,Ь ). При этом коме)20поненты а Ь;, д=1,ш,анализируемыхмножеств находятся в интервале 0,1и представлены и-разрядными двоичными кодами, Блок вычитания 3 Формируетмодуль разности г; =)а;-Ь 1 соответ 25ствующих компонентов двух сравниваемых нечетких множеств А и В, гдеа; Е А, Ь; Е В, Сумматор 4 и регистр15, образующие накапливающий сумматорпозволяют определить степень различия К(А,В ) анализируемых множествпо Формуле К(А,В)=г; =а -Ь,э 1а фСхема 6 сравнения, коммутатор 7, регистры 21 и 20 позволяют отыскатьпутем последовательного сравнения 35.адрес такого множества В, котороеимеет минимальную степень различияс множеством А, т.е. К(А, В).основе которых блок 24 формйрования результата находит оценку степени сходства С(А,В )=1-К(А,В)/ши передает на выход устройства А В "адрес найденного множества и стейеньего сходства С(А,В) с анализируемыммножеством А,Устройство работает следующим образом,Перед началом работы устройстводолжно быть приведено в исходное состояние, для чего на вход 12 подается единичный импульс "Уст,", который проходит через элементы ИЛИ 13"и 18 и поступает на К-входы регистра 99 о5 и счетчика 11, сбрасывая их в ну левое состояние, а также - на 8-вход регистра 21, устанавливая усе его разряды в единичное состояние, На вход 9 необходимо подать непрерывную последовательность тактовых импульсов ТИ, на вход 14 - и-разрядный двоичный код ш размерности множеств, на входы 1 и 2 - соответстжнно и-разрядные коды а, и Ь а на вход 19 - и-разрядный код, А В Последовательности кодов а , Ь должны подаваться навходы 1, 2 в каждом такте, опережая на время Г/3 приход очередного тактового импульса, где- период следования ТИ, При этом в каждом такте (фиг,2) в блоке 3 вычитания компоненту а; присваивается знак "+", так как вход 8 сумматора 28 соединен с вхо-. дом "0", а компоненту Ъ - знак "-", так как входы Яа, Я сумматора 28 и преобразователя 27 соединены,с входом "1", Это приводит к тому, что на выходе преобразователя 27 формируется дополнительный код числа (-Ъ), значащие разряды которого подаются на вход В сумматора 28 со знаком "-", При этом на выходах сумматора 28 формируется дополнительный код разности (а;-Ь.), который преобразователем 29 подвергается. обратному преобразованию в прямой код, значащие разряды которого определяют модуль разности г;1 а -Ь.) и поступают на выход. 30 блока вычитания, Полученный модуль разности г, поступает на вход Во сумматора 4, Так как получаемое в каждом такте г; необходимо накапливать для дальнейшей офработки то накапливающий сумматор, Собранный на сумматоре 4 и регистре 5, расчитан на 2 п разрядов, В связи с тем, что блок вычитания,3 Формирует только и-разрядный код.г;, и-разрядный вход В, сумматора 4 соединен с входом "0"обнуляя тем самым старшие и разрядов кода гУстройство начинает функционирование при подаче уровня "1" на вход 8При этом каждый ТИ проходит через элементы И 10, поступая на С-вход регистра 5 и на счетный вход счетчика 11В регистре 5 фиксируется результат суммирования текущего г с,полу 1ченными на предыдущих тактах г., а содержимое счетчика 11 увеличивается на единицу., Процесс, накопления г,9, 152569Если принять а=1, К1, то устройство работает в режиме определения экстремального числа из заданного множества чисел В=ЬЬЬ,Ь, .ф 5,При этом для определения минимального числа необходимо положить А=1 а,Д= =00,О, а для определения максимального числа необходимо положить 10 А=1 а, =111, Сигнал "Пуск" на входе 8 в этом случае следует сбрасывать после обработки компонентов аи Ь В качестве АРВ необходимо подавать либо адрес очередного Ъ в ОЗУ, либо 151его порядковый номер в множестве,Формула изобретения 1, Устройство для сравнения множеств, 20 содержащее схему сравнения, коммута" тор, элемент И, два элемента ИЛИ, при чем первый и второй входы схемы срав.нения объединены соответственно с первым и вторым входами коммутатора, 25 выход "Больше или равно" схемы сравнения подключен к управляющему входу коммутатора, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей эа счет определения степени сходства нечетных мно-, жеств и адреса нечетного множества; имеющего максимальное сходство с заданным, в него введены блок вычитанияю сумматор три регистрау счетчик вторая схема сравнения, два элемента задержки и блок формирования результата, причем входы компонентов первого и второго множеств соединены соответственно с первым и вторым входами 4 Облока вычитания, выход которого.соединен с первым входом сумматора, второй вход которого соединен с.входом логического нуля. устройства а третий - с выходом первого регистра и первыми входами первой схемы сравнения и коммутатора, выход сумматора соединен с информационным входом первого регистра, синхровход которого соединен с выходом элемента И и счет ным входом счетчика, а вход установки в нулевое состояние - с выходом первого элемента ИЛИ, первый вход которого соединен с,выходом первого элемента задержки, а второй вход - с входом установки в единичное состояние второго регистра, входом начальной установки устройства и пЕрвым входом второго элемента ИЛИ, второй 9вход которого соединен с выходом"Равно",второй схемы сравнения, аего выход - с входом установки в ну-.Флевое состояние счетчика, выход разрядов которого соединен с первымвходом второй схемы сравнения, второй вход которой соедичен с входомразмерности множеств и первым входом блока формирования результата,второй вход которого соединен с выходом второго регистра и вторымивходами первой схемы сравнения икоммутатора, выход которого соединен с информационным входом второгорегистра, синхровход которого соединен с выходом второго элемента задержки, входом первого элемента задержки.и синхровходом третьего регистра, вход разрешения записи ко -торого соединен с выходом "Больше,или равно" первой схемы сравнения,а информационный вход - с.входом адреса множества устройства, а выходтретьего регистра - с третьим входом блока формирования результата,первый и второй управляющие входыкоторого соединены с входами соответственно получения результата и управления выдачей результата устройства,а первый и второй выходы являютсявыходами соответственно степени сходства множеств и адреса множества устройства, входы запуска и синхронизации устройства соединены с входами элемента И,2, Устройство по п, 1, о т л ич а ю щ е е с я тем, что. блок вычитания содержит сумматор и два преобразователя прямого кода в дополнительный, причем первый информационный вход сумматора соединен; с первым входом блока вычитания, информационный вход первого преобразователя соединен с вторым входом блокавычитания, первый знаковый вход сумматора соединен с входом логического нуля устройства, а его второйзнаковый вход соединен с логическойединицей устройства и знаковым входомпервого преобразователя, выход которого соединен с вторым информационным входом сумматора, знаковый выход которого соединен со знаковымвходом второго преобразователя, аего информационный выход - с информационным входом второго преобразователя, выход которого является выхоцом блока вычитания,11 525699 123 устройство по п, 1, о т л и - ход которого соединен с информач а ю щ е е с я тем, что блок форми- ционным входом шинного формирователя рования результата содержит группу с инверсией, выход которого соединен из 2 п элементов И, группу из и эле- . 5 с первым выходом блока, третий вход ментов И, где и. - разрядность компо-. блока соединен с информационным вхонентов множеств, матричный делитель, дом шинного формирователя, выход кошинный формирователь с инверсией торого соединен. с вторым выходом блои шинный формирователь, причем пер- ка, первый управляющий вход блока совый вход блока соединен с первыми 10 единен с вторыми входами всех элеменвходами первой группы элементов И, тов И первой и второй групп, второй ,второй вхоц блока соединен с первыми управляющий вход блока соединен с входами второй группы элементов И, входами упраления выдачей информации выходы первой и второй групп элемен- обоих шинныхформирователей,входывытов И соединены соответственно с втоборки кристалла которых соединеныс рым и первым входами делителя, вы- входом логического нуля устройстваРегСоставитель К,ИваноТехред А,Кравчук Редактор Л,Пчолинская Корректо ирняк,Заказ 722845 Тираж бб 8НИИПИ Государственного комитета па113035, Москва, НПодписноеретениям и открытиям при ГКНТ Сушская наб., д, 4/5 Производственно-издательский комбинат "Патент", г. Ужгород Гага