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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИЛЕТЕЛЪСТВУ Союз Советскик Социалистических Республик(51) М. Кл. Ы 11 С 15100 Росуларственный комитет сссР ио делам изобретений и открытий(53) УЛК Ь 31. 327088.8) Опубликовано 250279 Бюллетень7 Лата опубликования описания 250279Изобретение относится к запоминающим устройствам и может быть использовано в информационно-поисковых системах.Известно устройство, содержащее ма- о трицу запоминающих ячеек и детекторы, осуществляющие формирование сигналов на адресных шинах модулей памяти 1), Этому устройству свойственно невысокое быстродействиеОНаиболее близким техническим решением к изобретению является ассоциативное запоминающее устройство,содержащее входной регистр, одни выходы которого подключены к входам первого накопителя, подключенного к первому регистру адреса и блоку управления, второй регистр адреса, соединенный через элементы И с вторым накопителем 2, 20В этом устройстве преобразование признака в адрес памяти с произвольным доступом осуществляется путем выполнения некоторой последовательности преобразований над значениями разрядов входного регистра, соответствующих признаку для поиска информации и выборки из накопителея адресов для записи в память с произвольным доступом. Вид и последовательность преобразований определяет используемые наборы логических блоков и топологию связей между ними.Однако любые изменения в классификации связаны с внесением изменений в устройство. Это исключает возможность оперативной перестройки устройства, приводит к необходимости разработки специального устройства для каждого конкретного применения, что существенно снижает область применения устройства.Целью изобретения является расширение области применения устройства,Достигается это тем, что устройство содержит сумматор, преобразователь кода, блок контроля и третий накопитель, входы которого подключены к другим выходам входного регистра, а выходы - к входам второго регистра адреса, один из выходов второго накопителя соединен с входом преобразователя кода, выход которого подключен к входу второго накопителя и входу блока контроля, выход которого соединен с входом блока управления, входы сумматора подключены соответственно к другому выходу второго накопителя и выходу преобразовазеля кода, а выходы сумматора соеди649038 5 10 Устройство (см.фиг.1) содержит входной (и+1+1) в . разрядный регистр 1, предназначенный для приема входного кода по входу 2. Выход 3 регистра 1 соединен с выходом устройства 4 и с входом 5 первого накопителя б (разряды регистра 1 - с первого по и-ный). Выход 7 регистра 1 объединяет разряды регистра с и+1) по и+Е) -ый Выход 8 накопителя служит для передачи информации из накопителя б на вход 9 регистра 1. Устройство содержит также первый регистр адреса 10, выход 11 которого соединен с входом накопителя б. Регистр 10 имеет входы 12. Выход 13 (и + К + 1) -го старшего разряда регистра 1 соединен с входом блока управления 14, имеющего выходы 15"20.Устройство содержит также третий накопитель 21, входы которого подключены к выходам 7 регистра 1, а ныходы 22 - к входам второго регистра адреса 23. Информационные входы 24 элементов И 25 соединены с выходами регистра 23, а выходы 26 элементов И 25 подключены к входам второго накопителя 27, выходы 28 которого соединены с одним иэ входов сумматора 29. Один из выходов накопителя 27 соединен с входом 30 преобразователя кода 31, другие входы 32 сумматора 29, входы 33 накопителя 27 и входы 34 блока контроля 35 подключены к выходам преобразователя кода 31. Выходы сумматора 29 соединены с входами 12 регистра 1. Накопитель27 является (Ь + щ) -разцядным, причем в сумматор 29 поступает базоная часть кода (разряды с 1-го по Ь-ый), а н преобразователь кода 31 индексная часть кода (остальные разряды). В блоке 35 осуществляется сравнениекода с нулевым кодом.Накопитель 21 (см.фиг,2.) содержитг линеек по 1 ячеек памяти 36 и каждой линейке, г ячеек ныцачи результата 37 по одной в каждой линейкеканал передачи 38 н прямом коде и канал передачи 39 н инверсном кодесостояния (и+1) - (п+К) -го разрядоврегистра 1, каналы ввода.40 и 41константы 0 и 1 в ячейкипамяти 36, имеющие номер 1 в каждойлинейке, и н ячейку 37 выдачи результата с номером 1, каналы передачи42,43 и 44 информации на входы ячеекпамяти 36 с номером 1 между яче ,ками памяти 36 и от ячеек памяти 36 с в прямом (В; и инверсном Д;) коде,и)5 по каналу передачи 51 - состояниетриггера 46 в иннерсном ) коде,каналы передачи 52 и ЬЗ выходных сигналов элементов И 47 и 48 на элементыИЛИ 54 и 55 и элементы НЕ 56 и 57,каналы пеРедачи 58,59 выходных сигналон элементов НЕ 56, 57 на элементИ 60,Каждая ячейка выдачи результата37 (см.фиг.4) содержит триггер 61,состояние которого задает вид сраннения кода с эталоном, каналы йере-. в прямом (Х) и инверсном (И) коде,элементы И 64 и 65, элемент ИЛИ 66сигналов, поступающих по каналам42 и 43 с выхода И-ой ячейки памяти36 Э-ой линейки накопителя 21, каналпередачи 67 выходного сигнала элемента ИЛИ 66 на вход вентиля 65, каналыпередачи 68 и 69 выходных сигналовэлементов И 64 и 65 на вход элементаобъединения 70.предложенное устройство работаетв режимах приема и поиска информации.Режим приема информации. В этомрежиме необходимо по признаку, сопровождающему поступающую на входустройства информацию, определитьместо н накопителе б, куда необходимо записать эту информацию с тем,чтобы она была доступна в дальнейшем для ассоциативного поиска, т.е.могла быть выбрана в случае, когдапризнак запроса полностью или в заданной части совпадает с признаком,который сопровождал информациюпри записи,Настройка устройства перед началом работы заключается в следующем.В триггеры 45 ячеек памяти 36накопителя 21 записываются значенияэталонов для классификации входныхпризнаков. При этом триггеры 45одной линейки рассматриваются какразряды одного )-разрядного эталона.В триггеры 46 ячеек памяти 36накопителя 21 записываются признакивключения ячеек памяти 36 в процесссравнения признака с эталоном. Приэтом триггеры 46 одной линейкирассматриваются как разряды одного иены с входами первого регистра адреса.На Фиг.1 дана блок-схема устройства; на фиг.2 - блок-схема третьего накопителя; на фиг.З - Функциональная схема ячейки памяти этого накопителя; на фиг.4 - функциональная схема ячейки выдачи результата третьего накопителя. 30 35 40 45 50 55 60 65 номерами К к ячейкам выдачи результата 37.Каждая ячейка памяти 36 (см.фиг.3) содержит триггер 45, состояние которого задает значение 1 -го разряда 3-го эталона, триггер 46, являющийся 1-ым разрядом 3-го регистра маски, элементы И 47 и 48, на которые по каналам передачи 38 и 39 поступает значение 1-го разряда с регистра 1 в прямом (Х) и инверсном (Х ) коде, по каналу передачи 43 поступает сигнал сравнения кодов в (1 - 1)-ой ячейке 3-ой линейки, по каналам передачи 49,50 - состояние триггера 45 дачи 62 и 63 состояния триггера 61Таблица 1 Шина Х; езультат х;лг х 2О ХЛГ; Х г с 1 с; к-разрядного регистра маски. Введение регистров маски раздельно по всемэталонам позволяет анализироватьпризнак запроса как по всем разрядампризнака, так и по заданной совокупности разрядов, назначаемой независимо для каждого эталона.В триггеры 61 ячеек выдачи результата 37 накопителя 21 записываютсяпризнаки, определяющие вид сравнения с эталоном раздельно по каждойлинейке. При этом триггеры 61 рассматрпваются как разряды одногог-разрядного регистра вида поиска.Установка триггера 61 ячейки выдачирезультата 37 в 3-ой линейке в состояние 1 соответствует логическомупоиску по 3-му эталону в состояниеО - параметрическому поиску по3-му эталону. В последнем случае вкачестве эталонов задаются граничные значения интервалов на шкалезначений рассматриваемого физическиого параметраКроме перечисленного, при настройке устройства производится, записьв накопитель 27 текущего состоянияраспределения ячеек накопителя 6.Накопитель 27 содержит г числовыхячеек - по одной на эталон. Разрядность каждой линейки равна (Ь + щ) .В разряды с 1 по Ь-ый для,3-ой личейки записывается число, на единицу ЗОменьшее адреса первой ячейки областипамяти накопителя 6, выделенной дляинформации, соответствующей 3-муэталону; в разрядах с (Ь + 1) по (Ь + в)-ый - число занятых ячеек вэтой области.В режиме приема информации код поступает на входной регистр 1.Содержательная часть входной информации поступает в накопитель 6Стар ший разряд регистра 1 устанавливает в блоке управления 14 режим прием.Код признака с регистра 1 поступает на вход накопителя 21, в котором одновременно во всех линейках производится сравнение принятого кода призна 45 ка с эталонами - содержимым регистров, образованных триггерами 45 ячеек памяти 36.Сравнение кодов признака и эталонов происходит следующим образом. 5 ОПроизводится последовательное поразрядное сравнение этих кодов, Начиная со старшего (1-го, равного 1). Если значения кодов в рассматриваемом разряде совпадают, то начинается сравнение в следующем разряде;если значения не совпали, то процесс сравнения заканчивается, и код, значение которого в данном разряде большее, считывается большим.В двоичном коде значение каждого разряда может быть равно или О, или 1.Логика сравнения иллюстрируется в табл. 1. О Х; л г не определен 1 Х; Л 1; не определен В соответствии с табл.1 для выявления соотношения между Х и 2 необходимо реализовать соотношенияо,=хлг;(11Ь =Х л 1. (г 1С =Х Лг ЛХ Л. (Э)Одновременно истинным может быть одно и только одно из соотношений (1) - (3) .Сигналы, поступающие по шинам й, и Ь от (1 - 1) -ой ячейки, должны ретранслироваться через 1-ую ячейку независимо от соотношения между Х и 2 Сигналы О;, Ь , с; в 1-с)й ячейке должны вырабатываться только при наличии сигнала С= 1 и состоянии триггера 46 в состояние О, т,е. при У = О,Для удовлетворения этим условиям необходимо:формировать сигналы на выходах 42 43 и 44 1 -ой ячейки памяти 36Ув соответствии с табл.2;на входы 42 и 44 первых ячеек в каждой линейке подать сигнал, эквивалентный О 1.649038 Т а б л и ц а 2 42 43 4 43 44 49 50 38 0 1 П имечаниельтат. значение не влияет дк 23 в сос до едставлен тношвния,мяти 36,дно- зультанала 44; к н ь"50 45 в на реэуКомбинационная схема, прная на фиг.3, реализует соосоответствующие табл.2.Сигналы с выхоДов ячеек паимеющих 1 - М, поступают иа оименные входы ячеек выдачи ретов 37 со сдвигом на 1 для касигнал 3-ой линейки поступает навход 3 + 1 ячейки 37, вход 1-ой ячки 37 закоммутирован на константу1 ф, а выход г-ой линейки не исп зуется.Элемент ИЛИ 70 формирует сигнал, соответствующий выполнению условия Х2(по разрядам, для которых У ) Элемент И 65 выдает сигнал только в том случае, когда одновременно Х 6 2 и Х2т,е, значение Х лежит в полуоткрытом интервале 2 - 2Ф а триггер 61 находится в состоянии 1, т.е. задан ;параметрический поиск. Элем. нт И 64 выдает сигнал в случае, когда Х = 2 (по разрядам, для которых Х;0), а триггер 61 находится в состоянии О, т.е. задан логический поиск.Элемент ИЛИ 70 передает сигналы, поступающие с элементов И 64 и 65на выход 22.Результат сравнения через ячейкиыдачи результата 37 передается в регистр 23. В регистре 23 устанавливаются в 1 разряды, соответствующие номерам линеек в накопителе 21 с положительным результатом сравнения. В общем случае схема клиссификации мажет быть построена такимобразом, что признак входной информации соответствует одновременно нескольким эталонам, в результате возможна установка одновремс нно нескольких разря в ре трае тояние 1.Блок управления 14 поочередно через элементы И 25 подключает по одному разряды регистра 23 к выходам 26 накопителя 27. Если значение подлючаемого разряда регистра 23 раво 0, то считывание иэ накопителя 27 не происходит,и блок управления 14 переходит к следующему разрядку рег стра 23, если значение равно 1, то считывается содержимое из ячейки с номером, равным номеру подключенного разряда регистра 23. Содержимое с первого по Ю -ый разряд считатанного кода (база) передается в сумматор 29, содержимое с (Ь+1) по (Ъ+щ)-ый разряд (индекс) - в преобразователь 31, где к значению индекса прибавляется 1, модифицированное значение индекса передается в сумматор 29, где суммируется с кодом базы, образуя код адреса для накопителя 6. Одновременно модифицированное значение индекса записывается в накопитель 27 на место считанного значения индекса для фиксации корректировки.По сигналу блока управления 14 пб выданному коду адреса производится запись в накопитель 6 информации, имеющей место на входе 5.После завершения цикла записи в накопитель 6 блок управления 14 выбирает следующий разряд регистра 23 и повторяется описанный процесс, По окончании цикла подключения г-го разряда регистра 23 выдается сигнал завершения режима приема информации.Режим поиска информации.В этом режиме необходимо выжать из накопителя 6 содержимое всех ячеек, 649038 10признаковые коды которых в разрядах, не закрытых маской, соответствуют запросу на поиск.В режиме поиска информации на входной регистр 1 по входу 2 подается (К+1) -разрядный код на разряды с (и+1) по (и+)с+1)-ый. бСтарший разряда регистра 1 устанавливает в блоке управления 14 режим тоиск с ныдачей соответствующей последовательности управляющих сигналов на блоки устройства. 30Код признака с регистра 1 поступает с выхода 7 для формирования адреса считывания из накопителя 6.Работа устройства в части формирования кода на регистре 23, соответст вующего принятому на регистр 1 коду признака, и считывания содержимого числовыхлинеек иэ накопителя 23 на сумматор 29 и преобразователь 31 происходит точно так же,как в режиме приема информации.После передачи кода базы в сумматор 29 и кода индекса в преобразователь 31 работа устройстна происходит следующим образом.Содержимое преобразователя 31 перв 2) дается в сумматор 29 , где суммируется с кодом базы. Результатом суммирования является код адреса, который передается в регистр адреса 10. По сигналу блока управления 14 осущест вляется считывание иэ накопителя 6 по адресу, установленному на регистре 10, Считанная информация записывается в разряды с 1 по и -ый входного регистра 1, откуда с ныхода 3 передается на выход 4 устройства,После завершения цикла считывания из накопителя 6 содержимое преобразователя 31 уменьшается на единицу, результат сравнивается в блоке контроля 35 с нулем. Если новое значение индекса больше нуля, то модифицированное значение индекса передается в сумматор 29 и повторяется цикл считывания. Таким .образом, на выход 4 передается инфор мация из всех ячеек зоны накопителя 6, которая соответствует признаку запроса. Как только преобразователь 31 устанавливается в О, блок контроля 35 выдает сигнал н блок 50 управления 14 для перехода к следующему разряду регистра 23. При поиске информации никаких корректировок содержимого накопи селя 27 и никаких записей в накопитель Ь не производится. По окончании цикла подключения г-го разряда регистра 23 выдается сигнал завершения режима поиска информации.Для стирания информации н какой- либо зоне достаточно обнулить значение индекса в соответствующей числовой линейке накопителя 27.Предлагаемое устройство, не уступая известным устройствам. (1 и (2) по быстродействию, обладает универсальностью в широком смысле. Оно доступно для оперативной смены информации, так как классификационные эталоны заносятся в накопители програмным путеми позволяет выполнять поиск как логического вида - по наличию определенной совокупности признаков, так и параметрического вида - по численному значению выделенных параметров.Формула изобретенияАссоциативное запоминающее устройство, содержащее нходной регистр,одни выходы которого подключены квходам первого накопителя, подключенного к первому регистру адреса иблоку управления, второй регистрадреса, соединенный через элементыИ с вторым накопителем, о т л и ч а ющ е е с я тем, что, с целью расширения области применения устройства, оно содержит сумматор, преобразователь кода, блок контроля и третий накопитель, входы которого подключены к другим выходам входногорегистра, а выходы - к входам второго регистра адреса, один из выходоввторого накопителя соединен с входом преобразователя кода, выход которого подключен к входу второго накопителя и входу блока контроля,выход которого соединен с входомблока управления, входы сумматораподключены соответственно к другомувыходу второго накопителя и выходупреобразователя кода, а выходы сумматора соединены с входами первогорегистра адреса.Источники информации, принятыено внимание при экспертизе1. Патент СИ У 3297995,кл. 340 в 1,5, 19 Ь 7,2. Авторское свидетельство СССР9 4545 Ь 1, И.кл. С ОЬ Г 15/40, 19/2.649038Составитель В.Рудаков Редактор Й.Гончар Техреду. Петко ., КорректорЛ.Веселовская Закаэ 566/49 Тираж 660 Подписное ЦНИИПИ Государственного комитета СССРпо делам иэобретений и открытий113035, Москва, Ж, Раушская наб., д.4/5Филиал ППП Патент, г.ужгород, ул. Проектная, 4