Ассоциативное запоминающее устройство Советский патент 1990 года по МПК G11C15/00 

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

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

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

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

13 элементов И, второй блок 14 сравнения, элементб И-ИЛИ 15, третий блок 16элемен- тов И, блок 17 управления, пороговый элемент 18, третий блок 19 памяти, второй счетчик 20 и элемент И 21. Блок 17 управления содержит (фиг. 5) блоки 22-27 элементов И, регистры 28-34, счетчики З5 и 36, элемент НЕ 37, счетчик 38 адреса микрокоманд и блок 39 перепрограммируемой памяти. Блок 17 имеет входы 40-47. Устройство имеет информационные входы 48 и 49. Блок 17 имеет также входы 50-66. Устройство (фиг. 1) имеет вход 67, выходы 68 и 69, вход 70 Признак поиска, выход 71 Число возбужденных элементов сети.

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

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

сл

(

vj

О

запоминание и динамическую перестройку ИССОЦИЭТИБНЫХ связей между элементами сети по совокупности свойств объектов, Представленных набором значений признаков, и подсчет числа возбуждений элементов сети (фиг. 2). Связи между элементами «-РПС представлены в блоке памяти матрицей элементов и связей между ними (фиг. 4), де N разрядов представляют набор значений признаков элементов, а остальные m эазрядов указывают на наличие или отсутствие связи между элементами сети, представленными в строках матрицы. Если зазряд установлен, то это указывает на на- пичие признака в объекте или наличие, связи между элементами.

На фиг. 3 использованы следующие обозначения: В - набор объектов (j -1,2,3,...,n); AI, Ak - набор элементов сети (1 - 1,2,3,...,k); k - результат конъюнкции элементов матрицы; Re, R - регистры второго блока 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. i В блок 4 памяти по входу 48 последовательно производится запись объектов В. По сигналу на входе 67 на входе блока 3 запоминается адрес последнего объекта Bj 0 п).

На вход 40 блока 17 подается сигнал, разрешающий запись начального адреса микропрограммы (уменьшенного на единицу) по входу 52. Затем на вход 51 блока 17 подается сигнал, разрешающий прохождение тактовых сигналов по входу 50 на вход +1 счетчика 38 адреса микрокоманд и через счетчик 36 на вход чтения ЧТ блока 39 перепрограммируемой памяти микрокоманд. С выхода счетчика 38 на вход адреса А блока 39 подается адрес микрокоманды, которая считывается на вход блока 39 при наличии сигнала на входе ЧТ, Микрокоманда имеет вертикальное кодирование микроопераций, число которых равно 41, Циклы в микропрограмме организованы изменением адреса микрокоманды в счетчике 38. Значения адресов микрокоманд, соответствующих началу соответствующего цикла, хранятся в регистрах 28-34 блока 17 управления.

По первой микрокоманде осуществляется сброс счетчиков в блоке 1 счетчиков адреса, триггеров блока 12, счетчика 6.

Вторая микрокоманда выполняет перезапись объекта Bj, где j 1 (для первого

шага), из блока 8 памяти в блок 4 памяти:

AI : - В

и запоминание адреса А элемента в третьем регистре блока 3 регистров. Третьей микрокомандой начинается цикл Е, осуществляется перезапись объекта BJ, где j 2 (для первого шага), из блока 8 памяти в блок 4 памяти:

Ak : Bj.

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

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

По пятой микрокоманде адрес элемента Ak+1 записывается в четвертый регистр блока 3 регистров.

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

Седьмой микрокомандой начинается выполнение цикла В. Микрокоманда выполняет запись элемента AI в первый регистр, анализ конца матрицы элементов, конъюнкцию К R 23/1 R 24, инверсию k, k AI и k Ak.

По восьмой микрокоманде осуществляется сдвиг содержимого регистра 9 сдвига. Эта микрокоманда повторяется п раз по числу разрядов в К.

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

По (п+1)-й микрокоманде осуществляется анализ: число установленных разрядов если нет, то PR и выход на цикл В; если К 2, то анализ К R 11i 0 (K Ai); если нет, то PR 1 1; если К R 111, то анализ К R 112 (R Ak); если К R 112, то анализ PR 1 0 , если PR , то выход на цикл 1; если PR 1 0, то выход на цикл 2; если К R 111, то анализ PR 5 0; если PR 1 0, то выход на цикл 3; если PR 1 0, то выход на цикл 4. Цикл 1.

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

По микрокоманде n+З осуществляется запись в элемент Ak значения 1jл Ak.

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

По микрокоманде n+Б, п+6, п+7 осуществляется запись единицы в строке элемента AI в столбец N + адрес элемента Ak-M. установку PR 2 1, сброс PR 1,

По микрокоманде п+8 осуществляется чтение информации из третьего блока 19 памяти по адресу AJ и запись в счетчик 20. По микрокоманде п+9 информация в счетчике 20 увеличивается на единицу. По микрокоманде п-НО осуществляется чтение информации из счетчика 20 в третий блок 19 памяти.

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

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

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

По микрокомандам п+16, п+17, п+18, rt+19 осуществляется чтение по адресу Ak+i из третьего блока 19 памяти и запись в счетчик 20, увеличение информации на единицу, запись ее в третий блок 19 памяти и сброс счетчика 20, переход на цикл В.

Цикл 2.

V

По микрокомандам п+20, п+2;К п+22, п+23, п+24 осуществляется: Ak: к Л Ak, запись единицы в строке элемента Ak в столбец N + адрес элемента A: PR 2 1, PR 1 0.

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

Цикл 3.

Микрокоманды ni-29, n+30, п+31 осуществляют выполнение третьего цикла Ak: 0, указатель просмотра матрицы элементов уменьшить на единицу и сбросить PR 1.

По микрокомандам п+32, п+33, п+34, п+35 осуществляется чтение информации по адресу AJ из третьего блока 19 и запись в счетчике 20, увеличение информации на единицу, запись ее в третий блок 19 памяти, сброс счетчика 20 и выход на цикл В.

Цикл 4.

Микрокоманды n+36,j}+37, n+38. п+39 и п+40 выполняют AI: к Л AI. установку разряда N + адрес Ak, сброс PR 1, установ- 5 ку PR 2.

По микрокомандам п+41, п+42, п+43, п+ 44 осуществляется чтение информации но адресу AJ из третьего блока 19 и запись в счетчик 20, увеличение, информации на

10 единицу, запись ее в третий блок 19 памяти, сброс счетчика 20 и выход на цикл В.

Далее происходит выполнение цикла В, описанного выше. Если PR 2 установлен, осуществляется переход на цикл С - уста15 новка указателя просмотра матрицы в нуль I Я и нозый просмотр матрицы с целью выявления элементов, совпадающих по установленным признакам.

Если PR 2 не установлен, то переход на

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

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

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

0 учитывающему принадлежность сочетания признаков нескольким обьектам и принадлежность обьекта некоторому понятию).

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

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

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

е

I

3

«3

I1

i

Фиг.2.

UOl69L9$bЈZLQl6dL9§beZI,

Ш

| | | H- y

9191191

TiuiifHVU

N

piuiiTj-ilw i Mr|M fV«« ifinr

t

1 2 3 5 6 7 8 8Ю11 1t13tt3334SS 3537 M40W4

ftttfttttftttt ttt tfttttt

J«6/

62

.5 6V

Фи1$