Устройство поиска информации

(51)5 С Об Р 15/40, 6 11 С 15/00 ГОСУДАРСТВЕННЫПО ИЗОБРЕТЕНИЯМПРИ ГКНТ СССР ОМИТЕТОТКРЫТИЯМ Е ИЗОБРЕСВИДЕТЕЛЬСТВ(56) Авторское свидеВ 883972, кл. С 11 САвторское свндетеУ 1057989, кл. С 11 У 2етик В.И. Глузнан раса счеттов, чении тельство СССР 15/00, 1980. льство СССР С 15/00, 1982 е ы с 4 ь ОПИСАНИ АВТОРСКОМУРОЙ СТВО ПОИСКА ИНФОРМАЦИИ бретение относится к вычис" й технике, в частности к ас- . ным запоминаинцим устройстжет быть использовано в ЭВМ околения для создания беэ Целью изобретения является ие области применения эа.еления ассоциативных элементветствующих сочетаниям энаиэнаков некоторого объекта,(54) УСТ (57) Изо лительно социатив вам, и мо пя того и.Ф Фз Фф ВЮ Ф ъфф й,файв Ъвв ЪФФ Ъ Ф Ь;:С) Ъ;Ф а оъ1536400 и определения иерархии сочетаний значений признаков по длине, что позволяет просматривать сочетания, принадлежащие одному объекту, в порядкеизменения их длин. Поставленная цельдостигается тем, что устройство содержит блок 1 определения конца элементов матрицы, блок 2 ввода инфорИзобретение относится к вычислительной технике, в частности к ассоциативным запоминающим устройствам, и может быть использовано в ЭВМ пятого поколения для создания баз знаний.Цель изобретения - расширение20 области применения путем выделения ассоциативных элементов, соответствующих сочетаниям значений признаков некоторого объекта, и определения .иерархии сочетаний значений признаков по длине, что позволяет просматривать сочетания, принадлежащие одному объекту, в порядке изменения их длин.На фиг.1 представлена структурная30 схема устройства поиска информации; на фиг,2 - .структурная схема блока определения конца элементов матрицы и блока ввода. информации; на фиг.З то же, блока определения адресов эле ментов матрицы; на фиг.4 - то же, блока анализа элементов матрицы 1 на фиг.5 - то же блока анализа связей элементов матрицы; на фиг.Ь - то же, блока установки и анализа признаков; на фиг.7 - то же, блока накапливающего ИЛИ; на фиг.8 - то же, блока управления; на фиг.9 - пример растущей пирамидальной сети (РПС); на фиг.10 - набор объектов; на фиг.11 матрица РПС, Формируемая ассоциативным запоминающим устройством; на Фиг.12 - алгоритм поиска объекта в матрице РПС; на Фиг,13 - микропрограмма работы устройства.Устройство поиска информации (Фиг.1) содержит блок 1 определения конца элементов матрицы, бпок 2 ввода информации, блок 3 определения ад" ресов элементов матрицы, блок 4 ана- . 5 лиза элементов матрицы, блок 5 анали" за связей элементов матрицы, блок б установки и анализа признаков, блок мации, блок 3 определения адресов элементов матрицы, блок 4 анализа элементов матрицы, блок 5 анализа связейэлементов матрицы, блок 6 установки и анализа признаков, блок 7 накапливающего ИЛИ и блок 8 управления.8 з.п. Ф-лы, 13 ил. 7 накапливающего ИЛИ и блок 8 управления,Блок 1 (фиг.2). содержит счетчик 9и элемент 10 сравнения.Блок 2 (фиг.2) содержит регистры11 - 14 и коммутатор 15.Блок 3 (фиг.З) содержит счетчик16, блок 17 памяти, сумматор 18, регистр 19 и элемент 2 И-ИЛИ 20.Блок 4 (фиг.4) содержит элементыИ 21 - 27, элементы 28 - 31 сравнения, элемент ИЛИ 32.Блок 5 (фиг.5) содержит сдвигающий регистр 33, счетчик 34, элементы 35, 36 сравнения, элементы И 37,38.Блок 6 (Фиг.6) содержит счетчик39, элемент И 40 и элемент 41 сравнения.Блок 7 (Фиг.7) содержит элементыИ 42, 43, элемент ИЛИ 44 и регистр 45.Блок 8 (фиг.8) содержит элементыИ 46 - 53, элементы 54, 55 задержки,элемент НЕ 56, регистры 57 - 62,счетчик 63 и блок 64 перепрограммируемой памяти.Используемые в описании и на фигурах идентификаторы расшифровываютсяследующим образом: Ц - информационный выход, 0 - информационный входА - адресный вход, 4 - вход разрешения, +1 - суммирующий вход, -1 - вычитающий вход, ЗП - вход разрешениязаписи, ЧТ - вход разрешения чтения,нулевой вход, В скобках указаны входы и выходы блоков.Устройство работает следующиМ образом.При включении устройства на входы(54, 56, 58 60, 62 и 64) блока 8управления последовательно подаютсясигналы, разрешающие запись адресовмикрокоманд циклов, а на входы (53,55, 57, 59, 61 и 63) блока 8 в тойжепоследовательности - адреса (умень00 6По первой микрокоманде (фиг.13)осуществляется сброс счетчиков 16,34 и 39,Вторая и третья микрокоманды осуществляют чтение элемента матрицы изрегистра 12 через коммутатор 15 в ре"гистры 13 и 14, разделяя при этомэлемент матрицы на составляющие ш;,и.п . Составляющая ш. записывается1 1в регистр 13, а и, - в регистр 14,при этом значение счетчика 9 уменьшается (по сигналу на входе -1 этогосчетчика) и анализируется: Элементы матрицы исчерпались 3 Если исчерпались, то останов, если нет - переход на четвертую микрокоманду.По четвертой микрокоманде осущест"вляется анализ: Хчп. и и,=0; еслиХ = ш,. и п; =О, то переход на циклА; если Хш или Х =ш,но и; О,то переход на следующую микрокоманду.По пятой микрокоманде осуществляется анализ; Х 8 ш.=О и п,=9; если1Хйш;=9 и п,10, то выход на цикл В;если ХЬшО, то переход на следующуюмикрокоманду.По шестой микрокоманде осуществляется запись ш . в регистр 45 блока7 накапливающего ИЛИ и анализ п,=9если п;= 9, то выход на цикл В, еслинет, то переход на следующую микрокоманду.Седьмой микрокомандой начинаетсяцикл С, осуществляется сдвиг и , запись единицы в счетчик 34 и анализ:выдвинутый разряд равен единице; если разряд равен единице, то переходна цикл Р, если нет, то переходнавосьмую микрокоманду; кроме того,анализируется конец сдвигов: если число с выхода счетчика 34, поступающее на вход элемента 36 сравнения,равно числу разрядов в п, плюс один,то вырабатываются сигналы 44, 47 иосуществляется переход на цикл О.Восьмой микрокомандой осуществляется возврат на цикл С.Девятой микрокомандой начинаетсяцикл П, осуществляется анализ; приз-,нак 1 = 9, если 1 Ф О, то переход нацикл Е, если Нет, то выполняется де-.сятая микрокоманда.По десятой микрокоманде осуществляется декремент счетчиков 16 и 39,чтение адреса ш. элемента матрицы изблока 1 памяти, который подается вассоциативное запоминающее устройство. 5 15364шенные на единицу) микрокоманд цикловА, В, С, Э, Е, Р,В блок 1 определения конца элементов матрицы по входу (48) производит-.5.ся запись К+1, при этом подается сигнал на вход ЗП счетчика 9, разрешающий запись числа К+1.В блок 2 ввода информации по входу (49) производится запись объектапоиска Х, при этом подается сигнална вход ЗП регистра 11.На вход (47 ) блока 8 подается сигнал, разрешающий запись начальногоадреса микропрограммы (уменьшенногона единицу) по входу (65). Затем навход (66) блока 8 подается сигнал,разрешающий прохождение тактовых сиг"налов по входу (67) на вход +1 счетчика 63 адреса микрокоманд и через 20элемент 55 задержки на вход чтения(ЧТ) блока 64 перепрограммируемой па"мяти микрокоманд, с выхода счетчика63 на вход адреса (А) блока 64 подается адрес микрокоманды, которая 25считывается на вход блока 64 при наличии сигнала на входе ЧТ. Микрокоманда имеет вертикальное кодированиемикроопераций, число которых равно42. Циклы в микропрограмме организованы .изменением адреса микрокоманды в счетчике 63, Значения адресовмикрокоманд, соответствующих началусоответствующего цикла, хранятся врегистрах 57-62 блока управления.Вход .(51) блока 3 запоминания ад-ресов элементов матрицы заэемлен ислужит для обнуления блока 17 памяти при поступлении сигналов: 15 наразрешающий вход элемента 2 И ИЛИ 20; 4018 на вход ЗП блока 17 памяти и 12на вход -1 счетчика 16,По входу (52) в блоке 3 запоминания адресов элементов матрицы адресэлемента матрицы заносится в регистр19 по сигналу с входа (17), разрешающему запись. По входу (50) элемент матрицы считывается из ассоциативного устройства в регистр 11 блока 2 ввода информации и запоминается в нем при поступлении сигнала на вход ЗП этого регистра,По выходу (46) из блока 3 модифицированный адрес элемента матрицы ц 1поступает в ассоциативное запоминающее устройство.По одиннадцатой микрокоманде осуществляется. возврат на цикл С.Двенадцатой микрокомандой осуществляется чтение Х из регистра 11 и чте 5ние М (значение, накопленное в регистре 45) по разрешающему сигналус входа (20) на входы элемента 29сравнения; если Х=М, то переход нацикл А, если ХМ, то выполняетсятринадцатая микрокоманда,По тринадцатой микрокоманде осуществляется возврат на цикл В,По четырнадцатой микрокоманде(цикл Р) осуществляется запись моди 15фицированного адреса (адреса элемен та матрицы, указанного установленнымразрядом связи) в блок 17 памяти.Пятнадцатая микрокоманда выдаетадрес считывания в ассоциативное эапоминающее устройство и осуществляетзапись нового ассоциативного элемента матрицы в регистре 12.Шестнадцатая и семнадцатая микрокоманды осуществляют разделение элемента матрицы на составляющие ш; и и,и запись ш в регистр 13 и и, в регистр 14,По восемнадцатой микрокоманде осуществляется анализ: Х Фш; Ф О; если 30Хбш; = 9,то переход на цикл В," еслиХбш, Ф 3, то выполняется девятнадцатая микрокоманда.По девятнадцатой микрокоманде осуществляется запись в блоке 7 накапливающего ИЛИ,Двадцатой микрокомандой осуществляется анализ: и= 9; если и;-" 9,то переход на цикл С; если нет, топереход к следующей микрокоманде. 40Двадцать первая микрокоманда увеличивает содержимое счетчика 39 установки признака 1 Ц +1) и осуществляет переход на цикл С.Таким образом, осуществляются поиск объекта Х в ассоциативном запоминающем устройстве и выделение элементов, соответствующих сочетаниямзначений признаков объекта Х по ихдлине. 50Формула изобретения1, Устройство поиска информации, содержащее блок управления, блоканализа элементов матрицы и блок накапливающего ИЛИ, о т л и ч а ю щ ее с я тем, что, с целью расширения области применения за счет выделения ассоциативных элементов, соответствующих сочетаниям значений признаковнекоторого объекта, и определенияиерархии сочетаний значений признаков по длине, в него введены блокввода информации, блок определенияконца элементов матрицы, блок определения адресов элементов матрицы,блок анализа связей элементов матрицы и блок установки и анализа признаков, причем первый и второй управляющие входы блока. определенияконца элементов матрицы соединены ссоответствующими разрядами выхода бло.ка управления, управляющие входы спервого по десятый блока ввода информации соединены с соответствующимиразрядами выхода блока управления,управляющие входы с первого по девятый блока определения адресов элементов матрицы соединены с соответствующими разрядами выхода блока управления, управляющие входы с первогопо шестой блока анализа элементовматрицы соединены с соответствующимиразрядами выхода блока управления, управляющие входы с первого по пятыйблока анализа связей элементов матрицы соединены с соответствующимиразрядами выхода блока управления,управляющие входы с первого по четвертый блока установки и анализапризнаков соединены с соответствующими разрядами выхода блока управления, первый, второй и третий управляющие входы блока накапливающегоИЛИ соединены с соответствующими разрядами выхода блока управления, первый, второй и третий управляющие вы ходы блока анализа элементов матрицы соединены с соответствующимиразрядами управляющего входа блокауправления, первый и второй управляющие выходы блока анализа связейэлементов матрицы соединены с соответствующими разрядами управляющеговхода блока управления, управляющийвыход блока установки и анализа признаков соединен с соответствующимиразрядами управляющего входа блокауправления, первый информационныйвыход блока ввода информации соединен с первым информационным входомблока анализа элементов матрицы, второй информационный выход блока ввода информации - с вторым информационным входом блока анализа элементовматрицы и с информационным входомблока накапливающего ИЛИ, третий информационный выход блока ввода информации - с третьим информационным входом блока анализа элементов матри-,5 цы и с информационным входом блока анализа связей элементов матрицы, выход блока накапливающего ИЛИ соединен с четвертым информационным входом блока анализа элементов матрицы, первый информационный выход блока анализа связей элементов матрицы - с пятым. информационным входом блока анализа элементов матрицы, второй информационный выход блока анализа 15 связей элементов матрицы - с первым информационным входом блока определения адресов элементов матрицы, информационный выход которого является адресным выходом устройства, инфор мационный вход блока определения конца элементов матрицы является первым информационным входом устройства, первый и второй информационные входы блока ввода информации являют ся соответственно вторым и третьим информационными входами устройства, второй и третий информационные входы блока определения адресов элементов матрицы - четвертым и пятым информационными входами устройства, информационные входы с первого по седьмой блока управления являются соответственно информационными входами с шес" того по двенадцатый устройства, входы записи с первого по шестой блока управления - входами записи с первого по шестой устройства, вход разрешения блока управления является входом разрешения устройства, вход син хронизации блока управления - входом синхронизации устройства, выход сигнала остановки блока определения конца элементов матрицы - выходом сигнала остановки устройства, 452. Устройство по п.1, о т л и - чающееся тем, чтоблокопределения конца элементов матрицы содержит счетчик и элемент сравнения, причем информационный вход счетчи- щ ка является информационным входом блока, вход записи счетчика - первым управляющим входом блока, вычитающий вход счетчика - вторым управляющим входом блока, информационный 5 а выход счетчика соединен с входом эле" мента сравнения, выход которого является выходом сигнала остановки блока. 3. Устройство по п,1, о т л и - ч а ю щ е е с я тем, что блок ввода информации содержит четыре регистра и коммутатор, причем информационный вход первого регистра является первым информационным входом блока, входы записи и чтения первого регистра являются соответственно первым и вторым управляющими входами блока, информационный выхоц первого регистра: является первым информационным выходом блока, информационный вход второго регистра - вторым информационным.,входом блока, информационный выход второго регистра соединен с информационным входом коммутатора,первый и второй управляющие входы которого являются соответственно третьим и четвертым управляющими входами блока, входы записи и чтения второго регистра являются соответственно пятым и шестым управляющими входами блока, первый и второй информационные выходы коммутатора соединены с информационными входами соответственно третьего и четвертого регистров, информационные выходы которых являются соответственно вторым и третьим, информационными выходами блока, вхо-ды записи и чтения третьего регистра являются соответственно седьмым и восьмым управляющими входами блока, входы записи и чтения четвертого регистра - девятым и десятым управляющими входами. блока.4. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок определения адресов элементов матрицы содержит счетчик, сумматор, блок па мяти, регистр и элемент 2 И-ИЛИ,причем вычитающий вход, суммирующий вход и вход установки в "О" счетчика являются соответственно первым, вторым и третьим управляющими входами блока, информационный вход счетчика соединен с адресным входом блока памяти, информационный выход которого является информационным выходом блока, информационный вход блока па- . мяти соединен с выходом элемента 2 ИИЛИ, первый. информационный вход которого соединен с информационным выходом сумматора, первый информационный вход которого является первым информационным входом блока, второй информационный вход сумматора соеди". нен с информационными выходом регистра, второй информационный вход эле11 1 мента 2 И-ИЛИ является вторым информационным входом блока, информационный вход регистра является третьим информационным входом блока, первый . и второй входы разрешения элемента 2 И-ИЛИ являются соответственно четвертым и пятым управляющими входами блока, входы записи и чтения блока памяти являются соответственно шестым и седьмым управляющими входами блока, входы записи и чтения регистра являются соответственно восьмым и девятым управляющими входами блока,5, Устройство по п.1, о т л и - ча ю щ е е с я тем, что блок накапливающего ИЛИ содержит регистр, элемент ИЛИ и два элемента И, причем первые входы элементов И соединены с информационным входом блока, вторые входы первого и второго элементов И являются соответственно первым и вторым управляющими входами блока, выход первого элемента И соединен с первым входом элемента ИЛИ, выход ,которого соединен с выходом второго элемента И и с информационным входом регистра, информационный выход которого соединен с вторым входом элемента ИЛИ и с информационным выходом блока, вход записи регистра является третьим управляющим входом блока,6, Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок анализа элементов, матрицы содержит семь элементов И, четыре элемента сравнения и элемент ИЛИ, причем первые входы первого и второго элементов сравнения соединены с первым входом первого элемента И и с первым информационным входом блока вторые входы первого элемента сравнения и первого элемента И соединены с вторым информационным входом блока, первый вход элемента ИЛИ является третьим информационным входом блока, первый вход второго элемента И - четвертым информационным входом блока, второй вход элемента ИЛИ - пятым информационным входом блока, второй вход второго элемента И - первым управляющим входом блока, выход второго элемента И соединен с вторым входом второго элемента сравнения, выход первого элемента И соединен с входом третьего э,лемента сравнения, выход элемента ИЛИ соединен с входом четвертого элемента сравнения, выход которого соединен с первыми входами третьего, 536400 12 10 15 20 25 ЗО 35 40 45 50 55 четвертого, пятого,и шестого элемен-тов И, выход третьего элемента сравнения соединен с первым входом седьмого элемента И и с вторым входомчетвертого элемента И, второй входседьмого элемента И является вторым управляющим входом блока, третийвход четвертого элемента И - третьим управляющим входом блока, второйвход пятого элемента И. - четвертымуправляющим входом блока, второйвход третьего элемента И являетсяпятым управляющим входом блока, второй вход шестого элемента И - шестым управляющим входом блока, выходпервого элемента сравнения соединенс третьим входом шестого элемента И,выход второго элемента сравнения соединен с выходом шестого элемента Ии с первым управляющим выходом блока,выходы четвертого, пятого и седьмогоэлементов И соединены с вторым управляющим выходом блока, выход третьего элемента И является третьим управляющим выходом блока. 7. Устройство по п.1, о т л и -ч а ю щ е е с я тем, что блок анализа связей элементов матрицы содержит сдвигающий регистр, счетчик, дваэлемента сравнения и два элемента И,причем информационный вход сдвигающего регистра является информационным входом блокаинформационныйвыход сдвигающего регистра соединенс входом первого элемента сравненияи первым входом первого элемента И,овыход первого элемента сравнения является первым управляющим выходом блока, выход первого элемента И является первым информационным выходом блока, входы записи и чтения сдвигающего регистра являются соответственнопервым и вторым управляющими входамиблока, второй вход первого элементаИ, вход сброса счетчика и первыйвход второго элемента И являются соответственно третьим, четвертым ипятым управляющими входами блока,счетный вход счетчика соединен с вторым управляющим входом блока, информационный выход счетчика соединен свторым входом второго элемента И и свходом второго элемента сравнения,выход которого является вторым управляющим выходом блока, а выход второго элемента И - вторым информационным выходом блока,13 158. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок установки и анализа признаков содержит счетчик, элемент И и элемент сравне-. ния, причем входы прямого счета, обратного счета и сброса счетчика являются соответственно первым, вторым и третьим управляющими входами блока, информационный выход счетчика соединен с первым входом элемента И, второй вход которого является четвертью управляющим входом блока, выход элемента И соединен с входом элемента сравнения, выход которого являет,ся управляющим выходом блока. 9. Устройство по п.1, о т л й ч а ю щ е е с я тем, что блок управления содержит шесть регистров, восемь элементов И, счетчик, два элемента задержки и блок перепрограммируемой памяти, причем информационные входы регистров с первого по шестой являются информационными входами соответственно с первого по шестой блока, информационные входы регистров с первого по шестой соединены с первыми входами элементов И соответственно с первого по шестой, входы записи регистров с первого по шестой являются входами записи соответственно с пер 36400 4вого по шестой блока, вторые входыэлементов И с первого по шестой соединены с соответствующими разрядами 5управляющего входа блока, выходы элементов И с первого по шестой соединены с информационным входом счетчикаи седьмым информационным входом блока, вход записи счетчика соединен спервым входом седьмого элемента И,с выходом элемента НЕ и соответству-:ющим разрядом управляющего входа блока, информационный выход счетчика сое"динен с адресным входом блока пере программируемой памяти, информационный выход которого является управляющим выходом блока, первый вход восьмого и второй вход седьмого элементов И соединены с входом синхрониза О ции блока, второй вход восьмого элемента И является входом разрешенияблока, третий вход восьмого элемента И соединен с выходом элемента НЕ,выход седьмого элемента И соединен 25 с входом первого элемента задержки,выход которого соединен с выходомвосьмого элемента И, с входом второго элемента задержки и со счетнымвходом счетчика, выход второго эле- ЗО мента задержки соединен с входомчтения блока перепрограммируемой памяти.