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

(21)4031755/24-24

(22)03.03.86

(46) 23.04.88, Бкш. № 15

(71)Институт кибернетики им. В.М.Глушкова

(72)В.А.Ященко

(53)681.327(088.8)

(56)Авторское свидетельство СССР

№ 1056269, кл. G 11 С 15/00, 1980. .

Авторское свидетельство СССР № 1127008, кл. G 11 С 15/00, 1983.

(54)АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

(57)Изобретение относится к вычислительной технике и может быть использовано в системах, построенных на

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

связей по совокупности свойств объектов. Устройство содержит блок 1 счетчиков, первый 2, второй 13 и третий 16 блоки элементов И, первый 3 и второй 11 блоки регистров, первый и второй 8 блоки памяти, первый 5 и второй 14 блоки сравнения, счетчик 6, сумматор 7, регистр 9 сдвига, дешифратор 10, блок 12 триггеров, элемент

,5И-ИЛИ 15, блок 17 управления и пороговый элемент 18. 15 ил.

i

W С

со со о

О5 СО

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

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

На фиг. 1 изображена структурная схема ассоциативного запоминающего устройства} на фиг. 2 - таблица зна- 15 содержит элементы И 16,-16. чений признаков объектов; на фиг. 3 - На фиг. 1-15 даны следующие обозначения: Q - информационный выход-, D - информационный вход; А - адресный вход-, f - вход разрешения J +1 на фиг. 5 - структурная схема 20 суммирующий вход ЗП - вход разрешения записи; ЧТ - вход разрешения чтения; 0 - нулевой вход-, 1 - единичБлок 1 (фиг. 7) содержит счетчики 1, и 1j адресов. Блок 5 (фиг. 8) содержит блоки 5, и 5 сравнения. Блок 2 (фиг. 9) содержит элементы И .g, Блок 3 (фиг. 10) содержит регистры 3i-3j. Блок 14 (фиг. 11) содержит блоки I4i и 14 сравнения и элемент НЕ 14J. Блок 11 (фиг. 12) содержит регистры 11, и 11,, элемент ИЛИ 11j и регистр 1 Ц. Блок 12 (фиг. 13) содержит триггеры 12,-12j. Блок 13 (фиг, 14) содержит элементы И , и элемент НЕ 13,, . Блок 16 (фиг. 15)

алгоритм формирования of - растущей .пирамидальной сети; на фиг.4 - матрица элементов сети и связи между

ними:

блока управления; на фиг. 6 - микропрограмма работы устройства; на фиг, 7 - структурная схема блока счетчиков; на фиг. 8 - структурная схема

ный вход; -1 - вычитающий вход.

Работа устройства поясняется ал- 25 горитмом (фиг. 3) формирования растущей пирамидальной сети (РПС), - обеспечивающей запоминание и динамическую перестройку ассоциативных связей между элементами сети по соРабота устройства поясняется ал- 25 горитмом (фиг. 3) формирования растущей пирамидальной сети (РПС), - обеспечивающей запоминание и динамическую перестройку ассоциативных связей между элементами сети по сопервого блока сравнения; на. фиг. 9 - структурная схема первого блока элементов И; на фиг. 10 - структурная схема первого блока регистров; на фиг.11- структурная схема второго блока сравнения; на фиг. 12 - струк-30 вокупности свойств объектов, предс- турная схема второго блока регистров; тавленных набором значений признаков на фиг. 13 - структурная схема блока триггеров; на фиг,, 14 и 15 - структурные схемы второго и третьего блоков элементов И соответственно.

(фиг. 2). Связи между элементами (/- РПС представлены в блоке памяти матрицей элементов сети и связей между

25 ними (фиг. 4), где N разрядов представляют набор значений признаков (Элементов, а остальные га разрядов указывают, на наличие или отсутствие связи между элементами сети, предАссоциативное,запоминающее устрой- :ство содержит (фиг. 1) блок 1 счетчиков, первый блок 2 элементов И, первый блок 3 регистров, первый блок 4 памяти, первый блок 5 сравнения.

счетчик 6, сумматор 7, второй блок 8 памяти, регистр 9 сдвига, дешифратор 10, второй блок 11 регистров, блок 12 триггеров, второй блок 13 элемен- тов И, второй блок 14 сравнения, элемент 5И-ИЛИ 15, третий блок 16 элементов И, блок 17 управления и пороговый элемент 18. Блок 17 управления содержит (фиг. 5) блоки 19-27 элементов И, регистры 28-34, счетчики 35 и 36 импульсов, элемент НЕ 37, счетчик 38 адреса 1чикрокоманд и блок 39 перепрограммируемой памяти. Блок 17 имеет входы 40-47. На фиг. 1 обозначены информационные входы 48 и 49 устройства. Блок 17 имеет также входы 50-66. Устройство (фиг. 1) имеет вход 67 и выходы 68 и 69,

содержит элементы И 16,-16. На фиг. 1-15 даны следующие обозначения: Q - информационный выход-, D - информационный вход; А - адресный вход-, f - вход разрешения J +1 Блок 1 (фиг. 7) содержит счетчики 1, и 1j адресов. Блок 5 (фиг. 8) содержит блоки 5, и 5 сравнения. Блок 2 (фиг. 9) содержит элементы И .g Блок 3 (фиг. 10) содержит регистры 3i-3j. Блок 14 (фиг. 11) содержит блоки I4i и 14 сравнения и элемент НЕ 14J. Блок 11 (фиг. 12) содержит регистры 11, и 11,, элемент ИЛИ 11j и регистр 1 Ц. Блок 12 (фиг. 13) содержит триггеры 12,-12j. Блок 13 (фиг, 14) содержит элементы И , и элемент НЕ 13,, . Блок 16 (фиг. 15)

ный вход; -1 - вычитающий вход.

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

вокупности свойств объектов, предс- тавленных набором значений признаков

(фиг. 2). Связи между элементами (/- РПС представлены в блоке памяти матрицей элементов сети и связей между

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

д г

0

А;,

J

А.

Обозначения, используемые на фиг 3, следующие:

В; - набор объектов (j 1,2,3,.. .,

п); - набор элементов сети (i

1,2,3,.,.,k);

k - результат конъюнкции элементов матрицы-, регистры 11, и 11 второго блока 11 регистров; признаки, устанавливаемые в блоке 12 триггеров. Устройство работает следующим образом.

R

(.

R, PR,,PR,При включении устройства на входы 54,56,58,60,62,64 и 66 блока 17 управления последовательно подают сигналы, разрешающие запись адресов микрокоманд циклов, а на входы 53, 55, 57, 59, 61, 63, 65 блока 17 в той же последовательности подают адреса (уменьшенные на единицу) микрокоманд циклов В, Е, 1, 2, С, Зи4.

В блок 4 памяти по входу 48 последовательно производится запись объектов В;, при этом подаются сигналы на вход +1 первого счетчика 1, адреса

объекта В

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

памяти

10

Bj

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

По четвертой микрокоманде элем А . переписывается в регистр llj бл ка 11 регистров (фиг. 12).

По пятой микрокоманде адрес эле

(фиг. 7), разрешаюпщй сигнал на вход }5 мента А.,., записывается в регистр элемента И 2 (фиг. 9) и сигнал записи (ЗП) на вход блока 8 памяти. По сигналу на входе 67 на входе блока 3 (фиг. 10) запоминается адрес послед3 блока 3 регистров.

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

него объекта В; (). На вход 49 устройства подается значение N.

На вход 40 блока 17 подается сигнал, резрешающий запись начального адреса микропрограммы минус (умень30

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

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

.Вторая микрокоманда выполняет перезапись объекта Ву5/где j 1 (для первого шага), из блока 8 памяти в блок 4 памяти

35

40

45

50

11,, анализ конца матрицы элементов, конъюнкцию k R23 Л R24, инверсию, k, k . л и k л А..

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

В счетчике 6 (фиг. 1) осуществляется подсчет количества установленных разрядов. С выхода счетчика 6 результат поступает на вход порогового элемента 18. Если число установленных разрядов k 7, 2, то на выходе порогового элемента 18 вьфаба- тывается сигнал и поступает на вход триггера 12з блока 12.

По п « 1 микрокоманде осуществляется анализ: число установленных разрядов k 2,- если нет, то и выход на В; если k 7/ 2, то анализ k R11 , (k А ) j если нет, то PR 1 1, если k R11., , то анализ k R11i(R AV)-, если k R1U, ;то анализ PR1 0; если PR1 0, то выход на цикл 1j если PR1 О, то выход на цикл 2; если k Р11,,-то анализ PR1 0; если PR1 О, то выход на цикл 3, если PR1 0, то выход на цикл 4.

Ai

В

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

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

1390637

объекта В

у, где шага), из блока

памяти

Bj

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

По четвертой микрокоманде элемент А . переписывается в регистр llj блока 11 регистров (фиг. 12).

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

3 блока 3 регистров.

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

Седьмой микрокомандой начинается выполнение цикла В. Микрокоманда вы

попняет запись элемента А; в регистр

11,, анализ конца матрицы элементов, конъюнкцию k R23 Л R24, инверсию, k, k . л и k л А..

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

В счетчике 6 (фиг. 1) осуществляется подсчет количества установленных разрядов. С выхода счетчика 6 результат поступает на вход порогового элемента 18. Если число установленных разрядов k 7, 2, то на выходе порогового элемента 18 вьфаба- тывается сигнал и поступает на вход триггера 12з блока 12.

По п « 1 микрокоманде осуществляется анализ: число установленных разрядов k 2,- если нет, то и выход на В; если k 7/ 2, то анализ k R11 , (k А ) j если нет, то PR 1 1, если k R11., , то анализ k R11i(R AV)-, если k R1U, то анализ PR1 0; если PR1 0, то выход на цикл 1j если PR1 О, то выход на цикл 2; если k Р11,,-то анализ PR1 0; если PR1 О, то выход на цикл 3, если PR1 0, то выход на цикл 4.

В цикле 1 по микрокомагоде п+2 осуществляется запись в элемент А; значения k л А .

1390637

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

осуществля- + 1.

По микрокоманде п + 4 ется запись k в строку k

По микрокомандам п+5 п+6, п+7 осуществляются запись единицы в строке элемента AJ в столбец N + адрес элемента А , , установка PR2 1, сброс PR1 и выход на цикл В,

В цикле 2 по микрокомандам п+8, n+9,n+jO, п+11, п+12 осуществляются k Л А|, запись единицы в стро-.

10

элемента А, в столбец N + адрес

Ч ке

элемента А: PR2 1, PR1 О и переход на цикл В.

В цикле 3 по микрокомандам п+13, п+14, п+15 осуществляется выполнение третьего цикла А : 0, указатель просмотра матрицы элементов уменьшить на единицу i i-1 и сбросить PR1,

В цикле 4 по микрокомандам п+16, п+17, п+18, п+19 и п+20 выполняют Ар k л А, установку разряда N + адрес A)j, сброс PR1, установку PR2 и выход на цикл В.

Далее происходит вьшолнение описанного цикла В. сш:( PR2 установлен, осуществляются переход на цикл С - установка указателя просмотра матрицы в нуль i О, и новый просмотр матрицы с целью вьшвления элементов, совпадающих по установленным признакам.

15

20

25

30

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

Если PR2 не установлен, то переход второй и третий блоки элементов И,

на цикл Е, в котором из второго блока 4 памяти выбирается следующий объект В; (J 2, выполняется второй шаг) и т.д. до исчерпания всех объектов во втором блоке 4 памяти.

Таким образом осуществляется запись объектов в первый блок памяти с формированием и дина1 1ической перестройкой (в процессе записи) ассоциативных связей по совокупности свойств записываемых объектов.

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

рмула

6

3

обретения

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

второй и третий блоки элементов И,

0

5

0

5

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

прямой выход блока триггеров соединенJQ цать первый выходы блока управления

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

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

55

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

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

10

Значения приъна«о6 обьентов щ fpu,z.2

т, (

k. к Л/(«

к

. -/ сГ;)Ок X L За. Help. АК idaaS. W2-rf;

иен

зап.1бАкЬн -А1

ррг: -1,

1 3f/5 S 7 eff 10 ff 12131(115 fб n 181920 21 гг2 2 У526212829Х-ЦЗгУЛ11-55-36773839 i/0 /

liZi

(Рйг.9

61

ГА

VLLZ. 10

9ut.12

Ж

9uz.11

(Pue.fJ

Составитель В.Рудаков Редактор Л.Гратилло Техред А.Кравчук Корректор Л.Пилипенко

Заказ 1771/48

Тираж 590

ВНИИГ1И Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

9иг.1

Подписное