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

 

Изобретение относится к технической кибернетике и может быть использовано для построения технических средств классификации, распознавания образов, поиска информации и автоматизации принятия решений в нечетких условиях. Целью изобретения является расширение функциональных возможностей. Устройство содержит блок вычитания 3, сумматор 4, регистры 5, 20, 21, схемы сравнения 6, 15, счетчик 11, элемент И 10, элементы ИЛИ 13, 18, элементы задержки 16, 17. Блок вычитания содержит преобразователи прямого кода в дополнительный и сумматор. Блок формирования результата содержит элементы И, делитель, шинные формирователи. Устройство позволяет определять степень сходства нечетких множеств и отыскивать адрес нечеткого множества из некоторой совокупности хранящихся в ОЗУ, которое имеет максимальное сходство с заданным множеством. 3 з.п. ф-лы, 3 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (19) (И) (50 4 С 06 F 7 02

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

cg,Ù

АфРу

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4447600/24-24 (22) 24,06,88 (46) 30.11,89, Бюл, Р 44 (71) Таганрогский радиотехнический институт им. В,Д;Калмыкова (72) В.Н,Решетняк, В,П,Карелин и А,Н,Мелихов (53) 681,325.5(088,8). (56) Авторское свидетельство СССР

9 1376079, кл, G 06 F 7/02, 1986.

Авторское свидетельство СССР

Ф 497583, кл, G 06 F 7/02- 1974, (54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ МНОЖЕСТВ (57) Изобретение относится к технической кибернетике и может быть использовано для построения технических средств классификации, распьз, навания образов, поиска информации и

2 автоматизации принятия решений в не- четких условиях, Целью изобретения является расширение функциональных возможностей, Устройство содержит блок вычитания 3, сумматор 4, регист ры 5, 20, 21, схемы сравнения 6, 15, счетчик 11, элемент И 10, элементы ИЛИ 13, 18, элементы задержки

16, 17, Блок вычитания содержит преобразователи прямого кода в дополнительный и сумматор. Блок формирования результата содержит элементы И, делитель, шинные формирователи, Устройство позволяет определять степень сходства нечетких множеств и отыскивать адрес нечеткого множества из не- g которой совокупности хранящихся в

ОЗУ, которое имеет максимальное сход,:ство с заданным множеством, 2 з,п, ф лы 3 ил

l525699

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

Устройство предназначено для опре, деления степени С сходства (нечет кого равенства) двух нечетких мнол жеств А и В и отыскания из совокупности нечетких множеств тако го множества В, которое имеет!

IìàKñèìàëüHóþ степень С сходст- )5 . :. ва с заданным нечетким множеством !, А, т.е, минимально отличается от А, Здесь степень С сходства нечеткого, равенства двух нечеткик множеств А={в„а В 9а В =(Ь,,Ь ь ЬД О определяется по формуле С(А,B)l

la, -Ь; ) m= I -R(A, В), где R(A, В)

1=1 степень различия между множествами

Аи В, i=1 m

Числа а;, Ь;, 1.=1,m, С(А,В), . R(A,В) в устройстве находятся в интервале 0, 1) и представлены п-разрядными двоичными кодами, 30

Степень сходства (нечеткого равенства) нечетных множеств А и В определяется следующим образом:

С(А,B)= с, /m= 7 (1-)а;"Ь;()/m=!

=1 — (l-r, )/m=1 r; /m =

1 1=1 — 1-R/m, 40 где R= 0 r °, Среди совокупности нечетких множеств В, где j=l,К, наиболее близким к мйожеству А будет такое мно- 45 жество, для которого степень сходств!с(Х ma x ва С (А, B) =j С (А, В1) =-j tl

/ тп <

m m

rnè и с j (, la, -ъ: I)

50 где R(A,B) — степень различия множеств А и В, Цель изобретения — расширение функциональных возможностей, путем определения степени сходства (нечеткого равенства) нечетких множеств и в отыскивании адреса того нечет кого множества из заданной совокупности хранящихся в 03У, которое имеет максимальное сходство (минимальное отличке) с заданным.

На фиг,1 показана функциональ ная схема устройства; на фиг,2 †.функ-. циональная схема блока вычитания; на фиг,3 — функциональная схема блока формирования результата, Устройство содержит. входы компонентов первого 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, шинного форми,рователя 36 с инверсией, входа 37 и шинного формирователя 38, Преобразователи 27 и 29 могут быть реализованы по схеме двустороннего преобразователя прямого кода в дополнительный и наоборот, Матричный делитель 35 может быть реализован по схеме матричного делителя, на входы которого подаются 2п разрядов делимого и и разрядов делителя, а на выходе которого формируются и разрядов частного, Блок 3 служит для получения модуля разности r; =1а;-Ь;1 элементов А и В, где а, Е А, Ь; Е B, i=1,m, mразмерность (число компонентов), Назначение блока 24 устройства состоит в определении степени сходства

С(А,В ) найденного множества В с с анализируемым множеством А и вйделе5 15256 нии на выходах устройства С(А,В ) и

А3 В1 — адреса множества В

Алгоритм работы устройства следующий, 5

Имеется исходная совокупность эталонных нечетких множеств В . где

j=l К; К вЂ” число множеств, Среди этой совокупности необходимо отыскать такое множество В, которое 10 имеет минимальную степень различия с анализируемым нечетким множеством

А, запомнить адрес этого множества и определить его степень сходства

С(А,В) ° В устройстве выполняется по- 15 элементное сравнение множества А = а,,а ...,,а„, с каждым множеством

В = 1Ъ,Ь ...,Ь ). При этом ком)

20 поненты а,, b i=l,m àíàëèçèðóåìûõ множеств находятся в интервале (О,I) и представлены и-разрядными двоичными кодами, Блок вычитания 3 формирует модуль разности r; = а;-Ь!1 соответ25 ствующих компонентов двух сравниваемых нечетких множеств А и В, где а;Е А, Ь; 6 В, Сумматор 4 и регистр

J )

5, образующие накапливающий су.матор позволяют определить степень различия К(А,В ) анализируемых множеств по формуле R(A,В ° ) = Qr> = 1а1-Ь; j, 3 = 1., l,;û i °

Схема 6 сравнения, коммутатор 7, регистры 21 и 20 позволяют отыскать путем последовательного сравнения 35 .адрес такого множества В, которое имеет минимальную степень различия с множеством А, т.е„ К(А, В, )

\т rl Mlt1 tn

- "j R(AЗ )= j (, 1а;-Ь )), где

J =1 j--l,К, При этом в регистре 20 saпоминается адрес В, а в регистре

21 — степень различия R(A,В ),на .основе которых блок 24 формйрова- 45 ния результата находит оценку степени сходства С(А,В )=I-R(A,В )/m и передает на выход устройства А В адрес найденного множества и стейень его сходства С(А,В ) с анализируемым множеством А, Устройство работает следующим образом, Перед началом работы устройство должно быть приведено в исходное состояние, для чего на вход 12 подается единичный импульс "Уст,", который проходит через элементы ИЛИ 13 и 18 и поступает на R-входы регистра

99 6

5 и счетчика ll сбрасывая их в ну-! левое состояние, а также — на S-вход регистра 21, устанавливая все его разряды в единичное состояние, На вход 9 необходимо подать непрерывную последовательность тактовых импульсов

ТИ, на вход 14 — n-разрядный двоичный код ш размерности множеств, на входы

1 и 2 — соответстжнно и-разрядж1е коды а, и b, а на вход 19 — n-раз( рядный код, А В,, Последовательности кодов а, Ь должны подаваться на

i входы 1, 2 в каждом такте, опережая на время Г/3 приход очередного тактового импульса, где — период следования ТИ. При этом в каждом такте (фиг,2) в блоке 3 вычитания компоненту а, присваивается знак "+", так как вход S> сумматора 28 соединен с вхо-. дом "0", а компоненту Ь вЂ” знак "-", так как входы S» S>, сумматора 28 и преобразователя 27 соединены,с входом "1", Это приводит к тому, что на выходе преобразователя 27 формируется дополнительный код числа (-Ъ ), значащие разряды которого подаются на вход В сумматора 28 со знаком "-", При этом на выходах сумматора 28 формируется дополнительный код разности (а;-Ь .), который преобразователем 29 подвергается. обратному преобразованию в прямой код, значащие разряды которого определяют модуль разности г;)а -Ь .1 и поступают на выход 30 блока вычитания, Полученный модуль разности r, поступает на вход Во сумматора 4, Так как получаемое в каждом такте г; необходимо накапливать для дальнейшей обработки то накапливающий сумматор Собранный на сумматоре

4 и регистре 5, расчитан íà 2п разрядов, В связи с тем, что блок вычитания,3 формирует только и-разрядный код.r;, и-разрядный вход В сумматора 4 соединен с входом "0" ° обнуляя тем самым старшие и разрядов кода r;, Устройство начинает функциониро"вание при подаче уровня "1" на вход

8 ° При этом каждый ТИ проходит через элементы И 10, поступая на С-вход регистра 5 и на счетный вход счетчика

11 ° В регистре 5 фиксируется результат суммирования текущего r с,полу1 ченными на предыдущих тактах r a

1 содержимое счетчика ll увеличивается на единицу.. Процесс, накопления r;

9, 152569 Если принять m=1, К > 1, то устройство работает в режиме определения экстремального числа из заданного множества чисел В= Ь1,Ь,,b,,...,b, .. 5.

При этом для определения минимального числа необходимо положить А=(а,jj=

=00,,0, а для определения максимального числа необходимо положить 10

А=(а,) =11...1, Сигнал "Пуск" на входе 8 в этом случае следует сбрасывать после обработки компонентов а1 и b

В .качестве АрВ необходимо подавать либо адрес очередного Ъ в ОЗУ, либо 15

1 его порядковый номер в множестве, Формула изобретения

1, Устройство для сравнения множеств, 20 содержащее схему сравнения, коммутатор, элемент И, два элемента ИЛИ, при. чем первый и второй входы схемы срав.нения объединены соответственно с первым и вторым входами коммутатора, 25 выход "Больше или равно" схемы сравнения подключен к управляющему входу коммутатора, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей эа счет определе-3Q ния степени сходства нечетных мно-, жеств и адреса нечетного множества; имеющего максимальное сходство с заданным, в него введены блок вычитания сумматор три регистра счет 1ик 35 вторая схема сравнения, два элемента задержки и блок формирования результата, причем входы компонентов .первого и второго множеств соединены соответственно с первым и вторым входами 4О блока вычитания, выход которого. соединен с первым входом сумматора, второй вход которого соединен с.входом логического нуля. устройства, а третий — с выходом первого регистра и первыми входами первой схемы сравнения и коммутатора, выход сумматора соединен с информационным входом первого регистра, синхровход которого соединен с выходом элемента И и счет- 5р ным входом счетчика, а вход установки в нулевое состояние — с выходом первого элемента ИЛИ, первый вход которого соединен с,выходом первого .элемента задержки, а второй вход - с входом установки в единичное состояние второго регистра, входом начальной установки устройства и первым входом второго элемента ИЛИ, второй

9 вход которого соединен с выходом

"Равно",второй схемы сравнения, а

его выход — с входом установки в ну-.

l левое состояние счетчика, выход разрядов которого соединен с первым входом второй схемы сравнения, второй вход которой соедичен с входом размерности множеств и первым входом блока формирования результата, второй вход которого соединен с выходом второго регистра и вторыми входами первой схемы сравнения и коммутатора, выход которого соединен с информационным входом второго регистра, синхровход которого соединен с выходом второго элемента задержки, входом первого элемента задержки.и синхровходом третьего регистра, вход разрешения записи ко— торого соединен с выходом "Больше, или равно" первой схемы сравнения, а информационный вход — с.входом адреса множества устройства, а выход третьего регистра — с третьим входом блока формирования результата . первый и второй управляющие входы которого соединены с входами соответственно получения результата и управления выдачей результата устройства, а первый и второй выходы являются выходами соответственно степени сходства множеств и адреса множества устройства, входы запуска и синхронизации устройства соединены с входами элемента И, 2, Устройство по п, 1, о т л и ч а ю щ е.- е с я тем, что. блок вычитания содержит сумматор и два преобразователя прямого кода в дополнительный, причем первый информационный вход сумматора соединен; с первым входом блока вычитания, информационный вход первого преобразователя соединен с вторым входом блока вычитания, первый знаковый вход сумматора соединен с входом логического нуля устройства, а его второй знаковый вход соединен с логической единицей устройства и знаковым входом первого преобразователя, выход которого соединен с вторым информационным входом сумматора, знаковый выход которого соединен со знаковым входом второго преобразователя, а его информационный выход — с информационным входом второго преобразователя, выход которого является выхо„цом блока вычитания, l1 525699 12

3, устройство по п, 1, о т л и — ход которого соединен с информач а ю щ е е с я тем, что блок форми- ционным нходом шинного формирователя рования результата содержит группу с инверсией, выход которого соединен из 2и элементов И, группу из и эле- . 5 с первым выходом блока, третий вход ментов И, где и.— разрядность компо-. блока соединен с информационным вхонентон множеств, матричный делитель, дом шинного формирователя, ныход кошинный формирователь с инверсией торого соединен с вторым выходом блои шинный формирователь, причем пер- ка, первый управляющий вход блока совый вход блока соединен с первыми 10 единен с нторыми входами всех элеменвходами первой группы элементов И, тов И первой и второй групп, второй ,второй нхоц блока соединен с первыми управляющий вход блока соединен с входами второй группы элементов И, входами упраления выдачей информации выходы первой и второй групп see> H обоих шинных формирователей,входынытов И соединены соответственно с вто- 15 борки кристалла которых соединены с

1 . :рым и первым входами делителя, ны- входом логического нуля устройства °

Ю

)а -d)

Л р

Составитель К,Иванова

Редактор Л,Пчолинская Техред A.Êpàâ÷óê Корр ек тор В-. Гирняк -, Заказ 7228/45 Тираж 668 Подписное

ВНИИПИ Государственного комитета па изобретениям и открытиям при ГКНТ СССР

113035, Москва, Н-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r Ужгород, ул. Гагарина, 101