Устройство поиска информации Советский патент 1990 года по МПК G06F17/30 G11C15/00 

Сп

со

О 4ь

и определения иерархии сочетаний значений признаков по длине, что позволяет просматривать сочетания, принадлежащие одному объекту, в порядке изменения их длин. Поставленная цель достигается тем, что устройство содержит блок 1 определения конца элементов матрицы, блок 2 ввода информации, блок 3 определения адресок элементов матрицы, блок 4 анализа элементов матрицы, блок 5 анализа связей элементов матрицы, блок 6 установки и анализа признаков, блок 7 накапливающего ИЛИ и блок 8 управления. 8 з.п. ф-лы, 13 ил.

Изобретение относится к вычислительной технике, в частности к ассоциативным запоминающим устройствам, и может быть использовано в ЭВМ пятого поколения для создания баз знаний. Целью изобретения является расширение области применения за счет выделения ассоциативных элементов, соответствующих сочетаниям значений признаков некоторого объекта, и определения иерархии сочетаний значений признаков по длине, что позволяет просматривать сочетания, принадлежащие одному объекту, в порядке изменения их длин. Поставленная цель достигается тем, что устройство содержит блок 1 определения конца элементов матрицы, блок 2 ввода информации, блок 3 определения адресов элементов матрицы, блок 4 анализа элементов матрицы, блок 5 анализа связей элементов матрицы, блок 6 установки и анализа признаков, блок 7 накапливающего ИЛИ и блок 8 управления. 8 з.п. ф-лы, 12 ил.

Изобретение относится к вычислительной технике, в частности к ассо- ,циативным запоминающим устройствам,, и может быть использовано в ЭВМ пятого поколения для создания баз знаний.

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

На фиг.1 представлена структурная схема устройства поиска информации; на фиг.2 - структурная схема блока определения конца элементов матрицы и блока ввода информации; на фиг.З - то же, блока определения адресов элементов матрицы; на фиг.4 - то же, блока анализа элементов матрицы; на фиг.З - то же блока анализа связей элементов матрицы; на фиго6 - то же, блока установки и анализа признаков; на фиг.7 - то же, блока накапливающего ИЛИ; на фиг.8 - то же, блока управления; на фиг.9 - пример растущей пирамидальной сети (РПС); на фиг.10 - набор объектов; на фиг.11 - матрица РПС, формируемая ассоциативным запоминающим устройством; на фиг.12 - алгоритм поиска объекта в матрице РПС; на фиг„13 - микропрограмма работы устройства.

Устройство поиска информации (фиг.1) содержит блок 1 определения конца элементов матрицы, блок 2 ввода информации, блок 3 определения адресов элементов матрицы, блок 4 анаш лиза элементов матрицы, блок 5 анализа связей элементов матрицы, блок 6 установки и анализа признаков, блок

0

5

0

5

0

5

0

5

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 (фиг.З) содержит сдвигающий регистр 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 перепрограммируемой памяти.

Используемые в описании и на-фигу pax идентификаторы расшифровываются следующим образом: Q - информационный выход, D - информационный вход А - адресный вход, & - вход разрешения, +1 - суммирующий вход, -1 - вычитающий вход, ЗП - вход разрешения записи, ЧТ - вход разрешения чтения, 0 - нулевой вход. В скобках указаны входы и выходы блоков„

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

При включении устройства на входы (54, 56, 58, 60, С2 и 64) блока 8 управления последовательно подаются сигналы, разрешающие запись адресов микрокоманд циклов, а на входы (53, 55, 57, 59, 61 и 63) блока 8 в той же последовательности - адреса (умень

шенные на единицу) микрокоманд цикло А, В, С, D, Е, F.

В блок 1 определения конца элементов матрицы по входу (48) производит .ся запись К+1, при этом подается сигнал на вход ЗП счетчика 9, разрешающий запись числа К+1.

В блок 2 ввода информации по входу (49) производится запись объекта поиска X, при этом подается сигнал на вход ЗП регистра 1 1.

На вход (47 блока 8 подается сигнал, разрешающий запись начального адреса микропрограммы (уменьшенного на единицу)-по входу (65)„ Затем на вход (66) блока 8 подается сигнал, разрешающий прохождение тактовых сигналов по входу (67) на вход +1 счетчика 63 адреса микрокоманд и через элемент 55 задержки на вход чтения (ЧТ) блока 64 перепрограммируемой памяти микрокоманд, с выхода счетчика 63 на вход адреса (А) блока 64 подается адрес микрокоманды, которая считывается на вход блока 64 при наличии сигнала на входе ЧТ. Микрокоманда имеет вертикальное кодирование микроопераций, число которых равно 42. Циклы в микропрограмме органи- зованы изменением адреса микрокоманды в счетчике 63. Значения адресов микрокоманд, соответствующих началу соответствующего цикла, хранятся в регистрах 57-62 блока управления. Вход (51) блока 3 запоминания адресов элементов матрицы заземлен и служит для обнуления блока 17 памяти при поступлении сигналов: 15 на разрешающий вход элемента 2И ИЛИ 20;

18на вход ЗП блока 17 памяти и 12 на вход -1 счетчика 16.

По входу (52) в блоке 3 запоминания адресов элементов матрицы адрес элемента матрицы заносится в регистр

19по сигналу с входа (17), разрешающему запись.

По выходу (46) из блока 3 модифицированный адрес элемента матрицы поступает в ассоциативное запоминающее устройство.

По входу (50) элемент матрицы считывается из ассоциативного устройст- ва в регистр 11 блока 2 ввода информации и запоминается в нем при поступлении сигнала на вход ЗП этого регистра.

По первой микрокоманде (фиг.13) осуществляется сброс счетчиков 16, 34 и 39.

Вторая и третья микрокоманды осуществляют чтение элемента матрицы .из регистра 12 через коммутатор 15 в регистры 13 и 14, разделяя при этом элемент матрицы на составляющие т и п-. Составляющая т( записывается в регистр 13, а п ; - в регистр 14, при этом значение счетчика 9 уменьшается (по сигналу на входе -1 этого счетчика) и анализируется: Элементы матрицы исчерпались Если исчерпались, то останов, если нет - переход на четвертую микрокоманду.

По четвертой -микрокоманде осуществляется анализ: . и п«-0; если X т. и n j 0, то переход на цикл А; если X тj или X т(,но п- О, то переход на следующую микрокоманду

По пят-ой микрокоманде осуществляется анализ: X & и п.0; если X I m , и п. 0, то выход на цикл В; если X 4 , то переход на следующую мик ро ко ма нду„

По шестой микрокоманде осуществляется запись m. в регистр 45 блока 7 накапливающего ИЛИ и анализ п.0; если П; 0, то выход на цикл В, если нет, то переход на следующую микрокоманду.

Седьмой микрокомандой начинается цикл С, осуществляется сдвиг п-, запись единицы в счетчик 34 и анализ: выдвинутый разряд равен единице; если разряд равен единице, то переход на цикл F, если нет, то переход на восьмую микрокоманду; кроме того, анализируется конец сдвигов: если чило с выхода счетчика 34, поступающее на вход элемента 36 сравнения, равно числу разрядов в п. плюс один, то вырабатываются сигналы 44, 47 и осуществляется переход на цикл D.

Восьмой микрокомандой осуществляется возврат на цикл С.

Девятой микрокомандой начинается цикл D, осуществляется анализ: признак j 0, если j Ј 0, то переход на цикл Е, если нет, то выполняется десятая микрокоманда.

По десятой микрокоманде осуществляется декремент счетчиков 16 и 39, чтение адреса ri. элемента матрицы из блока 17 памяти, который подается в- ассоциативное запоминающее устройство.

По одиннадцатой микрокоманде осуществляется возврат на цикл С.

Двенадцатой микрокомандой осуществляется чтение X из регистра 11 и чте-, ние М (значение, накопленное в регистре 45) по разрешающему сигналу с входа (20) на входы элемента 29 сравнения; если , то переход на цикл А, если X М, то выполняется JQ тринадцатая микрокоманда.

По тринадцатой микрокоманде осуществляется возврат на цикл В.

По четырнадцатой микрокоманде (цикл F) осуществляется запись моди-- 15 фицированного адреса (адреса элемен- та матрицы, указанного установлешгам разрядом связи) в блок 17 памяти.

Пятнадцатая микрокоманда выдает адрес считывания в ассоциативное за- 20 поминающее устройство и осуществляет запись нового ассоциативного элемента матрицы в регистре 12.

Шестнадцатая и семнадцатая микрокоманды осуществляют разделение эле- мента матрицы на составляющие m ; и п, и запись га в регистр 13 и п. в регистр 14.

По восемнадцатой микрокоманде осуществляется анализ: X&rij 0; если 30 Х&т,- 0,то переход на цикл В; если Х&т , 0, то выполняется девятнадцатая микрокоманда.

По девятнадцатой микрокоманде осуществляется запись в блоке 7 накап- ливающего ИЛИ.

Двадцатой микрокомандой осуществляется анализ: п- 0; если п;- 0, то переход на цикл С; если нет, то переход к следующей микрокоманде. до

Двадцать первая микрокоманда увеличивает содержимое счетчика 39 установки признака j (j H) и осуществляет переход на цикл Со

Таким образом, осуществляются по- 45 иск объекта X в ассоциативном запоминающем устройстве и выделение элементов, соответствующих сочетаниям значений признаков объекта X по их длине о- 50

Формула изобретения

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

9

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

3640010

и коммутатор, причем информационный вход первого регистра является первым информационным входом блока, входы записи и чтения первого регистра являются соответственно первым и вто10 рым управляющими входами блока, информационный выход первого регистра является первым информационным выходом блока, информационный вход второго регистра - вторым информацион15 нытвходом блока, информационный выход второго регистра соединен с информационным входом коммутатора,первый и второй управляющие входы которого являются соответственно треть20 им и четвертым управляющими входами блока, входы записи и чтения второго регистра являются соответственно пятым и шестым управляющими входами блока, первый и второй информацион25 ные выходы коммутатора соединены с информационными входами соответственно третьего и четвертого регистров, информационные выходы которых являются соответственно вторым и третьим,

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

40 содержит счетчик, сумматор, блок па- мяти, регистр и элемент 2И-ИЛИ,причем вычитающий вход, суммирующий вход и вход установки в О счетчика являются соответственно первым,

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

5р блока, информационный вход блока па- „ мяти соединен с выходом элемента 2И- ИЛИ, первый.информационный вход которого соединен с информационным выходом сумматора, первый информацион5« ный вход которого является первым информационным входом блока, второй информационный вход сумматора соедит нен с информационными выходом регистра, второй информационный вход эле1

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

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

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

с.

четвертого, пятого .и шестого элементов И, выход третьего элемента сравнения соединен с первым входом седь- г мого элемента И и с вторым входом четвертого элемента И, второй вход седьмого элемента И является вторым управляющим входом блока, третий вход четвертого элемента И - треть10 им управляющим входом блока, второй вход пятого элемента И - четвертым управляющим входом блока, второй вход третьего элемента И является пятым управляющим входом блока, вто15 рой вход шестого элемента И - шестым управляющим входом блока, выход первого элемента сравнения соединен с третьим входом шестого элемента И, выход второго элемента сравнения сое2о динен с выходом шестого элемента И и с первым управляющим выходом блока, выходы четвертого, пятого и седьмого элементов И соединены с вторым управляющим выходом блока, выход третье25 го элемента И является третьим уп

равляющим выходом блока

выход сдвигающего регистра соединен с входом первого элемента сравнения и первым входом первого элемента И, выход первого элемента сравнения является первым управляющим выходом бло

5

0

5

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

13

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

вого по шестой блока, вторые вх

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

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

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

2о Дни блока, второй вход восьмого мента И является входом разрешен блока, третий вход восьмого элем та И соединен с выходом элемента выход седьмого элемента И соедин

25 с входом первого элемента задерж выход которого соединен с выходо восьмого элемента И, с входом вт го элемента задержки и со счетны входом счетчика, выход второго эл

с первого по шестой, входы записи ре-30 мента задержки соединен с входом

гистров с первого по шестой являются входами записи соответственно с перчтения блока перепрограммируемой мяти.

3640014

вого по шестой блока, вторые входы

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

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

25 с входом первого элемента задержки, выход которого соединен с выходом восьмого элемента И, с входом второго элемента задержки и со счетным входом счетчика, выход второго эле30 мента задержки соединен с входом

мента задержки соединен с входом

чтения блока перепрограммируемой памяти.

Фи8.3

ffl Hi

if

Фиг. 6

Фие.7

(1lU4S6199№H1ltt1437$8MM4t)

/nAA жАЛААжЛжЛ. А А

ft)

в

т

/s

/7

Фиг. 11

{Вход)

JET

Bbod объектах, Вбод-K+J число -ж- ментоо 3 матрице

Чтение I элемента матрицы mi+ffi ,(к+1Н

Объект не найден

| Выделить mi л из (mi +щ}

Записать mi 6 накапливающее

Tib mi И$

Сдвигать п;, убелицибая счетчик ад. со язей

Запись 8 ВП Ад. mi эл. с.

Фие.12

Выход

AL

1

Объект найден

ь mi

Tib mi И$

Р-/, чтение из 6/7

ycm.npj J+1

О О 0-& 0 0 0-0 06 0 Of 0J Q 0 0 0 0000 Q Q 00 00 t 0 Q 0$ 0 00 fj &Ж t$&l QJO-J-Ж oj& о ®ФоМ о о

,- . T L n Лл . A.rfbЛЬ Btt« k 4kЛЬ. Ш Ль ЯКь . MiЛ .&.ш. Ьл .Л. л. . 4ВЬ-А 1 . .М Ъ лк ЛЬ. Г Ь. м. К. - . . .ъ.Jb

о о а о о / о о о о о о а о а & о о о о о о о о о о о оа р о о &oj o ti:ojfo То Го о о о о о /о fa a &1& о(Го оЪо: olo -- о о в IQ1 о огсГо. о о То о оо Ж еГо &OQ:&Q во

ООО О О OO/&J 00.0 О О О О О Q вёГоЪ / & О О (ЪQ Q Q Q Q I О I QO О О G QQ О 6 О 00 О Q О ОО О Q Q Q О О Q О О О D О / О Q Q О О О О

00 О О ОО О О О О О ОО О О О О О ОО # О Q ОО О О О О О Q О: О О Q GO 6 О О О I

% оо сГо о о о о о о о о о о о о о а о о 0 о о о оо оо о о о о о I о о о о о о о о о о о о о о о о i во О о с оо ао о о о о oro o OQ&Q о в о о о о о оо о ооо о о о Ъ, о о о, о о QQ о Q о о о о оо о о i

to

(I

12

о а о I о о о о о о о о о о о о Q о / а о о, во QQQ о,о м- а о о а о о о о о

73 ® ®Ж®: ® ° ° ° ®ООО8&&Уо&0 оЖ &U:a(fj О

чч

15

16 /

18

19 20

It

Я 0.-U & °. О ° О. Q ° а G.. /О О I О О Q Q О OS Q Q О О I GOO О Q Q & Ги Q

oaqoWloogq Q

ojorq o no&itf&jdOQQa oifo о о о о о с р о Ъ оойооооОо о Р1 оГо о ТЮ, / о О о о о.о Q о о оо о о о :&JGG Q о .i aaoQ & op о о &о. J ° о Ojfo й. о о оо о & о о а &ла а о о о о-Жй.о (, о во ,р о оао&оЪ о oj o о ffloo &0 оо о&о&впУйо о&о о о оГоГ( о о о-о оо б& tJ6 Q odrjoo 6uQ .o ffQ ojcfc o G y ;u:gr r gottfr :gt y:g- о о &(ой о &оа&Я &о о i о:8 о f

фие. 15