Ассоциативное запоминающее устройство

Ассоциативное запоминающее устройство

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК

<я)ю G 11 С 15/00

ГОСУДАРСТВЕ 1.НЫИ КОМИТЕТ

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

ПРИ ГКНТ СССР

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

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

1 (61) 1390637 (21) 4368599/24-24 (22) 30,11,87 (46) 15,06.90. Бюл. № 22 (71) Институт кибернетики им. В.M. Глушкова (72) В.А. Ященко (53) 681,327(088,8) (56) Авторское свидетельство № 1390637, кл. G 11 С 15/00, 1986. (54) АССОЦИАТИВНОЕ ЗАПОМИНАК)ЩЕЕ

УСТРОЙСТВО

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

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

На фиг. 1 изображена структурная схема ассоциативного запоминающего устройства; на фиг. 2 — таблица значений признаков объектов; на фиг, 3 — алгоритм формирования а-растущей пирамидальной сети; на фиг. 4 — матрица элементов и связи между ними; на фиг. 5 — структурная схема блока управления.

Ассоциативное запоминающее устройство содержит (фиг. 1) блок 1 счетчиков, первый блок 2 элементов И, первый блок 3 регистров, первый блок 4 памяти, первый блок 5 сравнения, первый счетчик 6, сумматор 7, второй блок 8 памяти, регистр 9 сдвига, дешифратор 10, второй блок 11 регистров, блок 12 триггеров, второй блок

„„Я „„1571676 А2 (57) Изобретение относится К вычислительной технике, может быть использовано в системах, построенных на принципах искусственного интеллекта, а также в экспертных системах и является усовершенствованием устройства по авт. св. № 1390637. Цель изобретения — расширение области применения за счет обеспечения хранения описаний объектов, принадлежащих к различным

rnaccaM. Устройство дополнительно содержит блок памяти, счетчйк и элемент И. 5 ил, 13 элементов И, второй блок 14 сравнения, элемент 5 И-ИЛИ 15, третий блок 16 элементов И, блок 17 управления, пороговый элемент 18, третий блок 19 памяти, второй счетчик 20 и элемент И 21. Блок 17 управления содержит (фиг. 5) блоки 22-27 элементов

И, регистры 28 — 34, счетчики 35 и 36, элемент

НЕ 37, счетчик 38 адреса микрокоманд и блок 39 перепрограммируемой памяти, Блок 17 имеет входы 40 — 47. Устройство имеет информационные входы 48 и 49. Блок

17 имеет также входы 50-66. Устройство (фиг. 1) имеет вход 67, выходы 68 и 69, вход

70 "Признак поиска", выход 71 "Число возбужденных элементов сети", Используемые идентификаторы расшифровываются следующим образом: Q— инфоомационный выход, D — информационный вход, А — адресный вход, 8 — вход разрешения, +1 — суммирующий вход, ЗП вЂ” вход разрешения записи, ЧТ вЂ” вход разрешения чтения, 8 — нулевой вход, 1 — единичный вход, -1 — вычитающий вход;

Работа устройства поясняется алгоритмом (фиг. 3) формирования а-растущей пирамидальной сети (РСП), обеспечивающей

1571676 апоминание и динамическую перестройку ссоциативных связей между .элементами ети по совокупности свойств обьектов, редставленных набором значений признаков, и подсчет числа возбуждений элемен1 ов сети (фиг. 2). Связи между элементами

С-PflC представлены в блоке памяти матрицей элементов и связей между ними (фиг. 4), где N разрядов представляют набор эначеий признаков элементов, а остальные m азрядов указывают на наличие.или отсуттвие связи между элементами сети, предтавленными в строках матрицы. Если азряд установлен, то это указывает на наличие признака в объекте или наличие связи

Между элементами.

На фиг. 3 использованы следующие обозначения;  — набор объектов (j-=1,2,3,...,п); Аь Аiс — набор элементов сети (t

1,2,3...„k); k — результат конъюнкции эле ментов матрицы; Вв, Вт — регистры второго блока 11; PR 1, PR 2, PR 3- при знаки, устанавливаемые в блоке 12 тригге, ров.

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

При включении устройства на входы 54, 56, 58, 60, 62, 64 и 66 блока 17 управления последовательно подают сигналы, разрешаю .цие запись адресов микрокоманд циклов, а на выходы 53, 55, 57, 59, 61, 63 и 65 блока

17 в той же последовательности подают ад реса (уменьшенные на единицу) микроко. манд циклов В, Е, 1, 2, С, 3 и 4.

В блок 4 памяти по входу 48 последова тельно производится запись объектов В . По . сигналу на входе 67 на входе блока 3 запо-! минается адрес последнего объекта В (j = п).

На вход 40 блока 17 подается сигнал, разрешающий запись начального адреса микропрограммы (уменьшенного на единицу) по входу 52. Затем на вход 51 блока 17 подается сигнал, разрешающий прохождение тактовых сигналов по входу 50 на вход

+1 счетчика 38 адреса микрокоманд и через счетчик 36 на вход чтения ЧТ блока 39 перепрограммируемой памяти микрокоманд. С выхода счетчика 38 на вход адреса А блока

39 подается адрес микрокоманды, которая считывается на вход блока 39 при наличии сигнала на входе ЧТ. Микрокоманда имеет вертикальное кодирование микроопераций, число которых равно 41. Цйклы в микропрограмме организованы изменением адреса микрокоманды в счетчике 38. Значения адресов микрокоманд, соответствующих началу соответствующего цикла, хранятся в регистрах 28-34 блока 17 управления.

По первой микрокоманде осу ществляется сброс счетчиков в блоке 1 счетчиков адреса, триггеров блока 12, счетчика 6, Вторая микрокоманда выполняет пере5 запись объекта Bj, где j - 1 (для первого шага), из блока 8 памяти в блок 4 памяти;

Ai: -,В и запоминание адреса А элемента в третьем регистре блока 3 регистров.

10 Третьей микрокомандой начинается цикл Е, осуществляется перезапись объекта

Bj, где j = 2 (для первого шага), из блока 8 памяти в блок 4 памяти:

А .В1, .

15 запоминается адрес элемента А во втором регистре блока 3 и анализ конца таблицы объектов.

По четвертой микрокоманде элемент А переписывается во второй регистр блока

20 11 регистров, По пятой микрокоманде адрес элемента

А +1 записывается в четвертый регистр блока 3 регистров.

По шестой микрокоманде (цикл С) осу25 ществляется промежуточный сброс устройства, установка указателя выборки элементов в начало матрицы и запись А во второй регистр блока 11 регистров.

Седьмой микрокомандой начинается

30 выполнение цикла В. Микрокоманда выполняет запись элемента А в первый регистр, анализ конца матрицы элементов; конъюнкцию К = R 23И R 24, инверсию К k А и А, 35 По восьмой микрокоманде осуществляется сдвиг содержимого регистра 9 сдвига.

Зта микрокоманда повторяется п раз по числу разрядов в К.

В счетчике 6 осуществляется подсчет

40 количества установленных разрядов. С выхода счетчика 6 результат поступает на вход порогового элемента 18. Если число установленных разрядов К 2, то. на выходе порогового элемента 18 вырабатывается

45 сигнал и поступает на вход блока 12.

По {и+1)-й микрокоманде осуществляется анализ: числа установленных разрядов К 2; если нет, то PR 2 = О и выход на цикл В; если К = 2, то анализ К = R 111

50 (К = А ); если нет, то PR 1 = 1; если К =

R 11, то анализ К = R 11г (R = А ); если К =

811,то анализ PR1= 8; если PR1 9, то выход на цикл 1; если PR 1 = О, то выход на цикл 2; если K = = R 111, то анализ PR =

55 g; если PR 1 = 8, то выход на цикл 3; если PR

1 =9, то выход на цикл 4.

Ц 1.

По (1+2)-й микрокоманде осуществляется запись в элемент А значения kAA .

1571676

По микрокоманде n+3 осуществляется запись в элемент А значения к Л А .

По микрокоманде и+4 осуществляется запись К в строку К+1.

По микрокоманде n+5, и+6, п+7 осуще- 5 ствляется запись единицы в строке элемента А в столбец N + адрес элемента А +1, установку PR2 =1, сброс PR 1.

По микрокоманде n+8 осуществляется чтение информации из третьего блока 19 10 памяти по адресу А и запись в счетчик 20, По микрокоманде и+9 информация в счетчике 20 увеличивается на единицу. По микрокоманде n+10 осуществляется чтение информации из счетчика 20 в третий блок 19 15 памяти.

По микрокоманде и+11 осуществляется сброс счетчика 20.

Таким образом в третьем блоке 19 памя- 20 ти элементу матрицы А ставится в соответствие число возбуждений этого элемента.

По микрокомандам n+12, и+13, и+14, и+15 осуществляется чтение информации по адресу А> из третьего блока 19 памяти и 25 запись в счетчик 20, увеличение информации на единицу, запись ее в третий блок 19 памяти и сброс счетчика 20.

Па микрокомандам и+16, и+17, n+18, 6+19 осуществляется чтение по адресу А +, 30 из третьего блока 19 памяти и запись в счетчик 20, увеличение информации на единицу, запись ее в третий блок 19 памяти и сброс счетчика 20, переход на цикл В, Цикл 2. 35

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

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

По микрокамандам n+20, n+21, n+22, и+23, n+24 осуществляется: А : = k 4 А, запись единицы в строке элемента А в столбец M + адрес элемента А: PR 2 = 1, 40

PR1=8.

По микракомандам и+25, n+26, n+27, и+28 осуществляется чтение информации по адресу А из третьего блока 19 и запись в счетчик 20, увеличение информации на 45 единицу, запись ее в третий блок 19 памяти, сброс счетчика 20, переход на цикл В.

Цикл 3.

Микрокоманды и+29, и+30, и+31 осуще- 50 ствляют выполнение третьего цикла

А : = 8, указатель просмотра матрицы weментов уменьшить на единицу и сбросить

PR 1.

По микрокамандам n+32, и+33, и+34, 55

n+35 осуществляется чтение информации по адресу Ai из третьего блока 19 и запись в счетчике 20, увеличение информации на единицу, запись ее в третий блок 19 памяти, сброс счетчика 20 и выход на цикл В, Цикл 4.

Микрокоманды n+36, и+37, n+38, и+39 и и+40 выполняют Ai: = k Л Аь установку разряда N+ адрес Ак, сброс PR 1, установку PR2.

По микрокомандам n+ 41, n+42, и+43, n+ 44 осуществляется чтение информации по адресу А из третьего блока 19 и запись в счетчик 20, увеличение. информации на единицу, запись ее в третий блок l9 памяти, сброс счетчика 20 и выход на цикл В.

Далее происходит выполнение цикла В, описанного выше. Если PR 2 установлен, осуществляется переход на цикл С вЂ” установка указателя просмотра матрицы в нуль

l = 8 и новый просмотр матрицы с целью выявления элементов, совпадающих по установленным признакам.

Если PR 2 не установлен, то переход на цикл Е, в катарам из блока памяти 4 выбирается следующий абьект В .и так далее до исчерпания всех объектов в блоке 4 памяти, Таким образом осуществляется запись объектов в первый блок памяти с формированием и динамической перестройкой {в процессе записи) ассоциативных связей по совокупности свойств записываемых объектов, запоминание в блоке 19 памяти числа возбуждений каждого элемента матрицы.

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

3571676

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

5 установочному и суммирующему входам и входам разрешения записи и считывания второго счетчика.!

1571676

1571676

1 2 3 4 8 6 7 8 У Ю11 12 13 1Ф

Ж

Л

61

62 (И

Я

Составитель В.Рудаков

Редактор M,Öèòêèíà Техред М,Моргентал Корректор И,Муска

Заказ 1517 Тираж 485 Подписное

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

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

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