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

(19 4 С 11 С 15/00 ВИДЕТЕЛЬСТВ СНОМ АЮЩЕЕ УСТ ОЦИАТИВНОЕ ЗАЛОМИ(54) АС РОЙСТВО (57) Из тельной зовано носит я к выисли-, ыть испольенных на ретен ехник и може истемах, пос СЬ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(56) Авторское свидетельство СССРУ 1056269, кл. С 11 С 15/00, 1980.Авторское свидетельство СССРш 1127008, кл. С 11 С 15/00, 1983, ",Мфгпринципах искусственного интеллекта,а также в экспертных системах, Цельизобретения - расширение функциональных возможностей устройства эасчет обеспечения запоминания и динамической перестройки ассоциативныхсвязей по совокупности свойств объектов. Устройство содержит блок 1 счетчиков, первый 2, второй 13 и третий16 блоки элементов И, первый 3 и второй 11 блоки регистров, первый и второй 8 блоки памяти, первый 5 и второй 14 блоки сравнения, счетчик 6,сумматор 7, регистр 9 сдвига, дешифратор 10, блок 12 триггеров, элемент5 И-ИЛИ 15, блок 17 управления и пороговый элемент 18. 15 ил,3906371390637а Э Составитель В.РудаковГратилло Техред А.Кравчук Корректор Л Пилипен Редак дписн д, 4/ полиграфическое предприятие, г, Ужгород, ул, Проектная,Производ Ф, Ф Заказ 1771/48 Тираж 59 0 ВНИИПИ Государстве по делам изобрет 13035, Москва, Ж, ного комитета .ний и открыти Раушская наб.Изобретение относится к вычислительной технике и может бьггь использовано в системах, построенных напринципах искусственного интеллекта,а также в экспертных системах,Цель изобретения - расширениефункциональных возможностей устройства за счет обеспечения запоминанияи динамической перестройки ассоциативных связей по совокупности свойствобъектов.На фиг, 1 изображена структурнаясхема ассоциативного запоминающегоустройства; на фиг, 2 - таблица значений признаков объектов, на фиг, 3алгоритм формирования Ы - растущейпирамидальной сети; на Фиг. 4 - матрица элементов сети и связи междуними; на фиг. 5 - структурная схемаблока управления, на Фиг, 6 - микропрограмма работы устройства; на Фиг.7 - структурная схема блока счетчиков; на фиг. 8 - структурная схемапервого блока сравнения; на Фиг. 9 - 25структурная схема первого блока элементов И; на фиг. 10 - структурнаясхема первого блока регистров нафиг. 11 - структурная схема второгоблока сравнения; на Фиг. 12 - структурная схема второго блока регистров;на фиг, 13 - структурная схема блока триггеров; на Фиг, 14 и 15 - структурные схемы второго и третьегоблоков элементов И соответственно. Ассоциативное запоминающее устройство содержит (Фиг, 1) блок 1 счетчиков, первый блок 2 элементов И,первый блок 3 регистров, первый блок 404 памяти, первый блок 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 адреса микрокоманд и блок39 перепрограммируемой памяти, Блок17 имеет входы 40-47. На фиг. 1 обозначены информационные входы 48 и 49устройства, Блок 17 имеет также входы50-66, Устройство (Фиг. 1) имеет вход67 и выходы 68 и 69,Блок 1 (фиг, 7) содержит счетчики1, и 1 адресов. Блок 5 (Фиг8) содержит блоки 5, и 5 сравнения. Блок2 (Фиг. 9) содержит элементы И 2-2.Блок 3 (Фиг, 10) содержит регистры3,-3, Блок 14 (фиг, 11) содержит блоки 141 и 14 сравнения и элемент НЕ14 , Блок 11 (фиг. 12) содержит регистры 11, и 11 элемент ИЛИ 11 ирегистр 11 . Блок 12 (Фиг. 13) содержит триггеры 12, -12, Блок 13 (фиг.14) содержит элементы И 13,-13 иэлемент НЕ 13,д, Блок 16 (фиг. 15)содержит элементы И 16,-16,На фиг, 1-15 даны следующие обозначения: Я - информационный выход;Р - информационный вход; А - адресный вход; Й - вход разрешения, +1суммирующий вход; ЗП - вход разрешения записи; ЧТ - вход разрешения чтения; 1 У - нулевой вход; 1 - единичный вход; - 1 - вычитающий вход.Работа устройства поясняется алгоритмом (фиг. 3) Формирования ы -растущей пирамидальной сети (РПС),обеспечивающей запоминание и динамическую перестройку ассоциативныхсвязей между элементами сети по совокупности свойств объектов, предс"тавленных набором значений признаков(фиг, 2). Связи между элементамиРПС представлены в блоке памяти матрицей элементов сети и связей междуними (фиг. 4), где И разрядов представляют набор значений признаковэлементов, а остальные ш разрядовуказывают. на наличие или отсутствиесвязи между элементами сети, представленными в строках матрицы. Еслиразряд установлен, тс это указываетна наличие признака в объекте (Фиг.2 и 4) или наличие связи между элементами (фиг, 4),Обозначения используемые на фиг. 3, следующие: В - набор объектов (=1,2,3п); А;, А - набор элементов сети (1 1,2,31 с);- результат конъюнкции элементов матрицы; К, К - регистры 11, и 11 второго блока 11 регистров; РКРК - признаки, устанавливаемые в блоке 12 триггеров,Устройство работает следующим образом,1390637 При включении устройства на входы54,56,58,60,62,64 и 66 блока 17 управления последовательно подают сигналы, разрешающие запись адресов микрокоманд циклов, а на входы 53, 55,57, 59, 61, 63, 65 блока 17 в тойже последовательности подают адреса(уменьшенные на единицу) микрокомандциклов В, Е, 1, 2, С, 3 и 4. 10В блок 4 памяти по входу 48 последовательно производится запись объектов В , при этом подаются сигналына вход +1 первого счетчика 1 адреса(Фиг, 7), разрешающий сигнал на входэлемента И 2 (Лиг. 9) и сигнал записи (ЗП) на вход блока 8 памяти, Посигналу на входе 67 на входе блока 3(фиг, 10) запоминается адрес последнего объекта В (3=и). На вход 49 20устройства подается значение М.На вход 40 блока 17 подается сигнал, резрешающий запись начальногоадреса микропрограммы минус (уменьшенного на единицу) по входу 52. Затем на вход 51 блока 17 подается сигнал,разрешающий прохождение тактовыхсигналов по входу 50 на вход +1 счетчика 38 адреса микрокоманд и черезсчетчик 36 на вход чтения (ЧТ) блока39 перепрограммируемой памяти микрокоманд, с выхода счетчика 38 на входадреса (А) блока 39 подается адресмикрокоманды, которая считывается навход блока 39 при наличии сигнала навходе ЧТ. Микрокоманда имеет вертикальное кодирование микроопераций,число которых равно 41. Циклы в микропрограмме организованы изменениемадреса микрокоманды В счетчике 38Значение адресов микрокоманд, соответствующих началу соответствующегоцикла, хранятся в регистрах 28-34блока 17 управления,По первой микрокоманде (Аиг. 6) 45осуществляется сброс счетчиков в блоке 1 счетчиков адреса, триггеров12-12блока 12, счетчика 6..Вторая микрокоманда выполняет перезапись объекта В где 1 = 1 (дляпервого шага), из блока 8 памяти вблок 4 памяти А,: =В3 А 1.: = В В цикле 1 по микрокоманде и+2 осуществляется запись в элемент А;значения 1 с л А,и запоминание адреса А элемента в55регистре 3блока 3 регистров.Третьей микрокомандой начинаетсяцикл Е, осуществляется перезапись объекта В , где З = 2 (для первогошага), из блока 8 памяти в блок 4памяти запоминается адрес элемента А в регистре З блока 3 и анализ концатаблицы объектов.По четвертой микрокоманде элементАпереписывается в регистр 11 блока 11 регистров (Лиг, 12).По пятой микрокоманде адрес элемента А 1,+ записывается в регистр3 блока 3 регистров.По шестой микрокоманде (цикл С)осуществляется промежуточный сбросустройства, установка указателя выборки элементов в начало матрицы изапись А 1, в регистр 11 блока 11регистров.Седьмой микрокомандой начинаетсявыполнение цикла В. Микрокоманда выполняет запись элемента А; в регистр11 анализ конца матрицы элементов,конъюнкцию 1 с = К 23 Л К 24, инверсию.1 с, 1 с лА;: и 1 с лАПо восьмой микрокоманде осуществляется сдвиг содержимого регистра9 сдвига. Эта микрокоманда повторяется и раз по числу разрядов в 1 с.В счетчике 6 (Аиг. 1) осуществляется подсчет количества установленных разрядов. С выхода счетчика 6результат поступает на вход порогового элемента 18, Если число установленных разрядов 1 с ъ 2, то на выходе порогового элемента 18 вырабатывается сигнал и поступает на входтриггера 12 блока 12,По и + 1 микрокоманде осуществляется анализ: число установленныхразрядов 1 с2; если нет, то РК 2=0и выход на цикл В; если 1 с2, тоанализ 1 с = К 11,(1 с = А;); если нет,то РК= 1, если 1 с = К 11., то анализ 1 с = К 112(К = А Д; если 1 с = К 11,то айализ РК 1 = 0; если РК 1 Ф О, товыход на цикл 1; если РК 1 = О, товыход на цикл 2; если 1 с = Р 11 то.анализ РК 1 = 0; если РК 1 Ф О, то выход на цикл 3, если РК 1 = О, то выходна цикл 4, 1390637По микрокоманде и + 3 осуществляется запись н элемент А 1, значения1 с и А,По микрокоманде и + 4 осуществляется запись К в строку К + 1.5По микрокомандам и+5, и+6, и+7осуществляются запись единицы в строке элемента А; в столбец И + адресэлемента А 1 установка РК 2 = 1,сброс РК 1 и выход на цикл В.В цикле 2 по микрокомандам и+8,и+9,п+10, и+11, и+12 осуществляютсяА ; = Гс Л А запись единицы в стро-.ке элемента А, в столбец М + адресэлемента А: РК 2 = 1, РК 1 = 0 и переход на цикл В.В цикле 3 по микрокомандам и+13.и+14, и+15 осуществляется выполнениетретьего цикла; А 1 = 9, указательпросмотра матрицы элементов уменьшитьна единицу 1 = -1 и сбросить РК 1,В цикле 4 по микрокомандам п+16,и+17, и+18, и+19 и и+20 выполняютА .; = 1 л А 1 установку разряда И + 251адрес А, сброс РК 1, установку РК 2и выход на цикл В,.Яалее происходит выполнение описанного цикла В. Если РК 2 установлен,осуществляются переход на цикл С -установка указателя просмотра матрицы в нуль= О, и новый просмотрматрицы с целью выявления элементов,совпадающих по установленным признакам,ЪЕсли РК 2 не установлен, то переходна цикл Е, н котором из второго блока4 памяти выбирается следующий объектВ (1 = 2 выполняется второй шаг) ит.д, до исчерпания всех объектов новтором блоке 4 памяти.Таким образом осуществляется запись объектов в первый блок памяти сформированием и динамической перестройкой (в процессе записи) ассоциативных связей по совокупности свойствзаписываемых объектов,Считывание информации из ассоциативного запоминающего устройства осуществляется по сигналу разрешения чтения на входе первого блока 8 памяти,50При этом осуществляется предварительный анализ сочетаний признаков поискового объекта и разрядов связей между элементами матрицы (тем самым определяются адреса элементов матрицы,удовлетворяющих некоторому критерию,учитывающему принадлежность сочетания признаков нескольким объектам). Формула из обретения Ассоциативное запоминающее устройство, сопержащее первый блок памяти, первый блок регистров, пороговый элемент, блок счетчиков, блоки сравнения и блок управления, причем первый выход блока управления соединен с первым суммирующим входом блока счетчиков, второй выход блока управления соединен с первым установочным входом блока счетчиков, третий выход блока управления соединен с вычитающим входом блока счетчиков, четвертый выход блока управления соединен с вторым суммирующим входом блока счетчиков, пятый выход блока управления соединен с вторым установочным входом блока счетчиков, шестой и седьмой выходы блока управления соединены соответственно с входами разрешения записи и чтения первого блока памяти, восьмой, девятый, десятый и одиннадцатый выходы блока управления соединены соответственно с первым, вторым, третьим и четвертым входами разрешения записи первого блока регистров, о т л и ч а ю щ е ес я тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения запоминания и динамической перестройки ассоциативных связей по совокупности свойств объектов, в него введены первый, второй и третий блоки элементов И, второй блок регистров, сумматор, второи блок памяти, регистр сдвига, счетчик, дешифратор, блок триггеров и элемент 5 И-ИЛИ, информационньгй выход которого соединен синформационным входом первого блока памяти, вы- ход которого соединен с первым информационным входом второго блока регистров, первый и второй выходы которого соединены с первым и вторым информационными входами второго блока элементов И, третий выход второго блока регистров соединен с первым информационным входом элемента 5 И-ИЛИ, второй информационный вход которого соединен с первымвыходом второго блока элементов И, второй выход которого соединен с третьим информационным входом элемента 5 И-ИЛИ, третий выход второго блока элементов И соединен с первым входом второго блока сравнения, первый выход которого соединен с первым установочным вхо 1390637дом блока триггеров, первый, второй гистров соединены соответственно с и третии прямые выходы которого сое- четвертым и пятым информационными динены соответственно с первым, входамп первого блока элементов И, вторым и третьим разрешающими входа- второй выход которого соединен с адми второго блока элементов И, чет- ресным входом первого блока памяти и вертыи выход которого соединен с первым входом сумматора, выход кото- вторым входом второго блока сравнения, Рого соединен с входом дешифратора, второй выход которого соединен с выход которого соединен с вторым инпервым входом третьего блока элемен О формационным входом второго блока рер тов И, третий выход второго блока, гистров, пятый выход первого блока сравнения соединен с вторым входом регистров соединен с вторым входом третьего блока элементов И, пятый вы- сумматора, восьмой, девятый и десяход второго блока элементов И сое- тый выходы второго блока элементов динен с четвертым информационным вхоИ 1 первый, втоРой, третий и четвердом элемента 5 И-ИЛИ и информационным тый выходы третьего блока элементов входом регистра сдвига, выход кото- И соединены соответственно с входа- рого соединен со счетным входом ми первой группы разрешения записи счетчика, выход которого соединен с блока управления, двенадцатый, тривходом порогового элемента, выход 2 О надцатый, четырнадцатый, пятнадцатый которого соединен с вторым установоч- н шестнадцатый выходы блока управным входом блока триггеров, второй и ления соединены соответственно счтретин инверсные выходы которого сое- первым, вторым, третьим, четвертым динены соответственно с четвертым и пятым разрешающими входвходами первого и пятым разрешающими входами второго 25 блока элементов И, семнадцатый и воблока элементов И, шестой и седьмой семнадцатый выходы блока выправления выходы которого соединены соответст- соединены соответственно с входами венно с третьим и четвертым входами записи и чтения второго блока памявторого блока сравнения четвертый1ти девятнадцатый двадцатыи и двадпрямой выход блока триггеров соединен ЗО цать первый выходы блока управления с шестым разрешающим входом второго соединены с первым, вторым и третьим блока элементов И и третьим входом входами записи второго блока реги- третьего блока элементов И, четвертый стров, пятый информационный вход элевход третьего блока элементов И сое- мента 5 И-ИЛИ и пятыйпятый вход третьего динен с пятым инверсным выходом бло- блока элементов И подключены соответка триггеров, первый выход блока счет- ственно к шине нулевого потенциала и чиков соединен с первыми информацион- к двадцать первому выходу блока управ- ными входами первого блока элементов ления двадцать второй, двадцать тре- И и первого блока регистров, второй тий, двадцать четвертый, двадцать выход блока счетчиков соединен с вто- пятый двадцать шестой и двадцат40ц ть рыми информационными входами первого седьмой выходы блока управления соеблока элементов И и первого блока динены соответственно с первым, вторегистров и первым информационным вхо- Рым, третьим, четвертым, пятым ну дом первого блока сравнений, первЬ 1 й левыми и шестым информационным входа- выход которого соепинен с третьим45ми блока триггеров а двадцать седьУ установочным входом блока триггеров, мой выход блока управления соединен, первый выход первого блока регистров с единичным входом блока триггеров, соединен с вторым входом первого бло- двадцать восьмой, двадцать девятый ка сравнения, второй выход первого и тридцатый выходы блока управления блока регистров соединен с третьим соединены соответственно с первым, входом первого блока сравнения и тре- вторым и третьим разрешающими входами тьим информационным входом первого второго блока элементов И, тридцать блока элементов И, первый выход ко- первый, тридцать второй, тридцать торого соединен с четвертым входом третий, тридцать четвертый и тридпервого блока сравнения и адресным цать пятый выходы блока управления входом второго блока памяти, выход 55 соединены соответственно с первым, которого соединен с информационным вторым, третьим, четвертым и пятым входом первого блока памяти, третий Разрешающими входами элемента 5 И-ИЛИ, и четвертый выходы первого блока ре- информационный вход второго блока па 3906мяти и третий информационный вход первого блока регистров являются информационными входами устройства, выход первого блока памяти являетсяи5 информационным выходом устроиства, входы разрешения зепи и первого блока регистров являются входами первой группы признака записи устройства, входы второй группы разрешения запиСи блока управления являются входа 37 1 Оми второй группы признака записи устройства, входы адресов микрокоманд,блока управления являются адреснымивходами устройства, второй выходпервого блока сравнения является выходом останова устройства, вход тактовых импульсов блока управления ивход строба блока управления являются входами синхронизации уст -ройства.1390637 14 июе Йаюф фааФ 4 вам Фс4 г4 вч ф 4 С ф в 44 Фф Я У л, , ь4 4 4 ю 45 4 ки 4 ю