Устройство для сравнения множеств Советский патент 1989 года по МПК G06F7/02 

«|я,ад

aJJASfi

Фиг.{

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

Устройство предназначено для определения степени С сходства (нечеткого равенства) двух нечетких мно- жеств А и 2 и отыскания из совокупности ..нечетких множеств такого множества , В, которое имееТ| максимальную степень С сходства с заданным нечетким множеством Af т,е, минимально отличается от А, Здесь степень С сходства нечеткого равенства двух множеств ,,а,.,,, и В {Ц ,b(....b

определяется по формуле С(А,В)1 IY1

-Zl|a; b;| (A,B), где R(A,B)

степень различия между множествами А и В, ,т,

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

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

C(A,B)-Z-Ci/m 2:(l -|a; b

- 1 1

mnri

y;;(l-r;)/m -21r;/m

l-R/m,

m

где R Zl r - ,

Среди совокупности нечетких жеств В- , где j,K, наиболее ким к множеству А будет, такое жество, для которого степень с, f max wax (- ва C(A,B)j C(A,Bj)j 1 R;(A, - Г-:; -,

„ „itiJl.;

m

ill ,LSiAjI) 1

J Lm

I VVl-I

min T

,1 (2: la;-b

i 1

m

где R(A,B) - степень различия множеств A и В,

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

5

20

35

40

45

25

30

50

55

кого равенства) нечетких множеств и в отыскивании адреса того нечет- кого множества из заданной совокупности хранящихся в ОЗУ, которое имеет максимальное сходство (минимальное отличие) с заданным.

На фиг.1 показана функциональная схема устройства; на фиг.2 -.функ-. циональная схема блока вычитания; на фиг.З - функциональная схема блока формирования результата.

Устройство содержит.входы компонентов первого 1 и второго 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,

Преобразователи 27 и 29 могут быть реализованы по схеме двустороннего преобразователя прямого кода в допол- нительньй и наоборот,

Матричньй делитель 35 может быть реализован по схеме матричного делителя, на входы которого подаются 2п разрядов делимого и п разрядов делителя, а на выходе которого формируются п разрядов частного.

Блок 3 служит для получения модуля разности , 1 элементов А и %, где а; 6 S, Ъ; е В, ,т, m - размерность (число компонентов),

Назначение блока 24 устройства состой в определении степени с содства

C(A,BQ) найденного множества В/, с

т

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

Ад BO - адреса множества ,Ва.

Алгоритм работы устройства следу-

10

5 и счетчика 11, сбрасывая их в нулевое состояние, а также - на S-вход регистра 21, устанавливая gee его ; разряды в единичное состояние. На вход 9 необходимо подать неррерывную последовательность тактовых импульсов ТИ, на вход 14 - п-разрядный двоичный код m размерности множеств, на входы 1 и 2 - соответствеино п-разряднь1е коды а и Ь, , а на вход 19 - п-разПоследовательностикодов а;, h должны подаваться на

рядный код , АарВ

. Ь. входы 1, 2 в каждом такте, опережая

ющий.

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

,K; К - число множеств. Среди

этой совокупности необходимо отыскать такое множество В , которое

имеет минимальную степень различия

с анализируемым нечетким множеством

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

определить его степень сходства

С(А,В), В устройстве выполняете по- 15 на время 7Г/3 приход очередного тактового импульса, где - период следования ТИ, При этом в каждом такте (фиг,2) в блоке 3 вычитания компоненту а; присваивается знак, так как 20 вход S д сумматора 28 соединен с вхог дом О, а компоненту Ъ - знак -, так как входы Sg, Sx сумматора 28 и преобразователя 27 соединены.с входом 1, Это приводит к тому, что на 25 выходе преобразователя 27 формируется дополнительный код числа (-ЬО значащие разряды которого подаются на вход В сумматора 28 со, знаком -, При этом на выходах сумматора 28 фор- 30 мируется дополнительный код разности (а;-Ьр, который преобразователем 29 подвергается, обратному преобразованию в прямой код, значащие разряды которого определяют модуль разности

35 i поступают на выход- 30 блока вычитания, Полученный модул ь разности г; поступает на вход В сумматора 4, Так как получаемое в каждом такте Г; необходимо накапливать для

элементное сравнение множества А |а , ,а,,,,, с каждым множеством

И . с Р этом компоненты а;, Ь; , ,т анализируемых множеств находятся в интервале 0,1J и представлены п-разрядными двоичными кодами. Блок вычитанир 3 формирует модуль разности соответствующих компонентов двух сравниваемых нечетких множеств и В- , где а;е А, Ь| е В , Сумматор 4 и регистр 5, образующие накапливающий су -матор, позволяют определить -степень различия R(A,B:) анализируемых множеств J пп гл . по формуле R(A,B. ) 51 jai-b|j,

f ;«

Схема 6 сравнения, коммутатор 7, регистры 2) и 20 позволяют отыскать путем последовательного сравнения .адрес такого множества Вд которое

имеет минимальную степень различия с множеством А, т.е. R(A, Вп)

Т R(A,B ) Т( ZLta- Ь -1 )| где 40 дальнейшей обработки, то накапливаю- J щий сумматор, добранный на сумматоре

4 и регистре 5, расчитан на 2п разрядов, В связи с тем, что блок вычитания, 3 формирует только п-разрядный 45 код.г;, п-разрядный вход В сумма- тора 4 соединен с входом О, обну- ляя тем самым старшие п разрядов ко- да г;.

,K, При этом в регистреt20 за j ,

поминается адрес В, а в регистре

21 - степень различия R(A,X ), на

.основе которых блок 24 формирования результата находит оценку степени сходства С(А,В„ ) l-R(A,Bn)/m и передает на выход устройства Аа-Вл - адрес найденного множества и степень

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

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

Перед началом работы устройство должно быть приведено в исходное состояние, для чего на вход 12 подается единичный импульс Уст,, который проходит через элементы ИЛИ 13 и 18 и поступает на R-входы регистра

0

5 и счетчика 11, сбрасывая их в нулевое состояние, а также - на S-вход регистра 21, устанавливая gee его ; разряды в единичное состояние. На вход 9 необходимо подать неррерывную последовательность тактовых импульсов ТИ, на вход 14 - п-разрядный двоичный код m размерности множеств, на входы 1 и 2 - соответствеино п-разряднь1е коды а и Ь, , а на вход 19 - п-разПоследовательностикодов а;, h должны подаваться на

рядный код , АарВ

. Ь. входы 1, 2 в каждом такте, опережая

5 на время 7Г/3 приход очередного тактового импульса, где - период следования ТИ, При этом в каждом такте (фиг,2) в блоке 3 вычитания компоненту а; присваивается знак, так как 0 вход S д сумматора 28 соединен с вхог дом О, а компоненту Ъ - знак -, так как входы Sg, Sx сумматора 28 и преобразователя 27 соединены.с входом 1, Это приводит к тому, что на 5 выходе преобразователя 27 формируется дополнительный код числа (-ЬО значащие разряды которого подаются на вход В сумматора 28 со, знаком -, При этом на выходах сумматора 28 фор- 0 мируется дополнительный код разности (а;-Ьр, который преобразователем 29 подвергается, обратному преобразованию в прямой код, значащие разряды которого определяют модуль разности

Устройство начинает функциониро- вание при подаче уровня 1 на вход 8, При этом каждый ТИ проходит через элементы И 10, поступая на С-вход регистра 5 и на счетный вход счетчика П, В регистре 5 фиксируется результат суммирования текущего с .полученными на предьщущих тактах г., а содержимое счетчика 11 увеличивается на единицу,. Процесс,накопления г

продолжается до тех пор, пока содер- :;|кимое счетчика 1 1 не совпадет с {зазмерностью множеств т. При этом а выходе компарато ра 15 формирует- |:я единичный сигнал, который проходит через элемент ИЛИ.13,и, поступая на R-вход счетчика 11, сбрасьшает го в нулевое состояние. Кроме того, |этот сигнал поступает на вход эле- 16 задержки, С задержкой &-/3 он поступает на С-входы регистров |20 и 21, При этом в регистр 21 за- |носится результат сравнения накоп- Ьенной в регистре 5 степени различия R.(A,B ) с промежуточным значением минимальной степени .различия, храня- ейся в регистре 21„ Степень разли- чия R(Sj|B ) поступает «а входы В и |Ь2 компаратора 6 и коммутатора 1, |Промежуточное значение минимальной 1степени различия поступает с выхода регистра 21 на входы А и L1 схемы сравнения 6 и коммутатора 7, Если пр ;этом имеет место ситуация А В, на |выходе схемы 6 сравнения появляется :единичный сигнал, который поступает НА входы СО и V коммутатора 7.и ре- |гистра 20, Это приводит к тому, что IB коммутаторе .7 вход L2 соединяется |С выходом L3 и текущая степень раз- 1ЛИЧИЯ ) поступает на D-вход ре |Гистра 21, а в регистре 20 разреша- ;ется прием информации с D-входа, При поступлении единичного сигнала на С входы в регистр 21 заносится R(A, В: а в регистр 20 - адрес текущего множества. . Если имеет место ситуация , то на выходе схемы сравнения появляется нулевой сигнал, который поступает на входы СО и V схем сравнения и регистра 20, Это приво- дит к тому, что в коммутаторе 7 вход L1 соединяется с выходом L3 и промежуточное значение минимальной степени различия поступает на D-вход регистра 21, а в регистре 20 запрещается прием информации с D-входа, При поступлении единичного сигнала на С-входы в регистр 21 перезаписываетс его содержимое, а содержимое регистра 20 не изменяется,

С задержкой 2 сГ/З еданичный сигнал с выхода схемы 15 сравнения появляется на выходе элемента 17 задержки, и, проходя через элемент ИЛИ 18 на R-вход регистра 5, сбрасывает его в нулевое состояние. Тем самым устройство подготавливается к про

5

0

5

0

5

0

5

50

55

цессу сравнения множеств А и В ,, которьй происходит аналогично описанному,

В целом процесс отыскания множест Vва Вд завершается после сравнения компонентов и Ь Множеств л и В , При этом на в;ход 8 необходимо подать уровень 0 который приведет к появлению нулевого сигнала на выходе элемента И 10, С-входе регистра 5 и на счетном входе счетчика 11, Тем самым состояние устройства фиксируется, т,е, в регистре 20 находится А Б(, а в регистре 21 - R(A,Ba).

Полученные данные подлежат Окончательной обработке в блоке 24 формирования результата fфиг,З), Для этого необходимо на вход 22 подать уровень 1, При этом 2п-разрядный код К(А,Вл) с выхода регистра 21 через группу элементов И 33 поступает на первьй вход матричного делителя 35, а п-разрядйый код m с входной шины 14 через группу элементов И 34 поступает на второй вход матричного делителя 35, По заверше- НИИ переходных процессов в матричном делителе на его выходе ется п-разрядное частное R(A,Bo)/m которое поступает на А-вход формирователя 36,

Для получения на выходах устройства окончательных результатов необходимо на вход 23 подать уровень 1, который, пдступая.на входы ВСЕ формирователей 36 и 38, определяет появление на их выходах информации с А-входов, При этом Aa-B. с выхода регистра 20 проходит через формирователь 38,на выход 26 устройства без изменений, а п-разрядный код R(A,Bo)/m с выхода матричного делителя 35 при прохождении через формирователь 36 инвертируется. Тем самым с достаточной точностью на выходной шине 25 устройства формируется оцен- . ка степени сходства С(Х,В,) I - R(K,J,)/m.

Если принять , то устройство работает в режиме определения степени сходства нечетных множеств А

a,a2,,,,, и .Ъ,... ,Ъ .

При этом на вход 19 в качестве Апр В, можно подавать нулевой код, а сиг- нал . Пуск на входе 8 следует сбрасывать после обработки компонентов и Ь|,

9 . 152569910

Если принять m , , то устрой- вход которого соединен с выходом ство работает в режиме определения Равно чвторой схемы сравнения, а экстремального числа из заданного мно- его выход - с входом установки в ну-г- г-1 г 3 , К1 левое состояние счетчика, выход раз- жества чисел ,,b,,h,b,,.. 5 которого соединен с первым

При этом для определения минималь- входом второй схемы сравнения, вто- ного числа необходимо положить , рой вход которой соединен с входом 00,,«О, а для определения макси- размерности множеств и первым вхо- мального числа необходимо положить ю Д блока формирования результата, , 11.,,i, Сигнал Пуск на вхо- второй вход которого соединен с вы- де 8 в этом случае следует сбрасьшать ходом второго регистра и вторыми после обработки компонентов а и b входами первой схемы сравнения и В качестве АлрВ необходимо подавать коммутатора, выход которого соеди- либо адрес очередного Ь- в ОЗУ, либо 15 нен с информационным входом второго его порядковый номер в множестве, регистра, синхровход которого соединен с выходом второго элемента заФормула изобретения держки, входом первого элемента задержки, и синхровходом третьего ре1, Устройство для сравнения множеств,, 20 гистра, вход разрешения записи ко- содержащее схему сравнения, коммута- торого соединен с выходом Больше, тор, элемент И, два элемента ИЛИ, при- или равно первой схемы сравнения, чем первьй и второй входы схемы срав- а информационный вход - с.входом ад. нения объединены соответственно с . реса множества устройства, а выход первым и вторым входами коммутатора, 25 третьего регистра - с третьим вхо- выход Больше или равно схемы срав- дом блока формирования pesynbTaTaj нения подключен к управляющему входу первый и второй зшравляющие входы коммутатора, отличающееся которого соединены с вxoдa a соответ- тем, что, с целью расширения функцио- ственно получения результату и управ- нальных возможностей за счет определе-30 ления вьщачей результата устройства, ния степени сходства начетных мно-, а первый и второй выходы являются жеств и адреса нечетного множества выходами соответственнр степени сход- имеющего максимальное сходство с за- ства множеств и адреса множества уст- данным, в него введены блок вычита- ройства, входы запуска и синхрони- ния, сумматор, три регистра, счетчик , | нации устройства соединены с входа- вторая-схема сравнения, два элемента Ими элемента И,

задержки и блок формирования резуль- 2, Устройство по п, 1, о т л и - тата, причем йходы компонентов-перво- чаю щ е- е с я тем, что, блок вы- го и второго множеств соединены соот- читания содержит сумматор и два пре- ветственно с первым и вторым входами Q образователя прямого кода в дополни блока вычитания, выход которого.сое- тельньй, причем первый информацион- динен с первым входом сумматора, вто- ный вход сумматора соединен: с пер- рой вход которого соединен с входом вым входом блока вычитания, информа- логического нуля, устройства, а тре- ционньш вход первого преобразовате. тий - с -выходом первого регистра и 45 соединен с вторым входом блока первыми входами первой схемы сравне- вычитания, первый знаковый вход сум- ния и KOMMyTa Topaj выход сумматора матора соединен с входом логичес- соединен с информационным входом пёр- кого нуля устройства, а его второй вого регистра, синхровход которого зна ковый вход соединен с логической соединен с выходом элемента И -и счет- 50 единицей устройства и знаковым входом ным входом счетчика, а вход установ- первого преобразователя, выход коки в нулевое состояние - с выходом торого соединен с вторым информаци- первого элемента ИЛИ, первьй вход ко-. онньпч входом сумматора, знаковый вы- торого соединен с,выходом первого ход которого соединен со знаковым элемента задержки, а второй вход с ее входом второго преобразователя, а входом установки в единичное состой- его информационный выход - с инфор- ние второго регистра, входом началь- мационным входом второго преобразо- ной установки устройства и первым вателя, выход которого является выхо- входом второго элемента ИЛИ, второй дом блока вычитания.

3. Устройство no П, 1, о т л и - чающееся тем, что блок форми- Ъования результата содержит группу из 2п элементов И, группу из n эле- IMBHTOB И, где n - разрядность компо- 1нентов множеств, матричный делитель, шинный формирователь с инверсией ;и шинный формирователь, причем 1 вый вход блока соединен с первыми Iвходами первой группы элементов И, второй вход блока соединен с первыми входами второй группы элементов И, выходы первой и второй групп элемен- iтов И соединены соответственно с вто-

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

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