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

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

Изобретение относится к запоминающим устройствам и может быть использо вано в информационно-поисковых системах. Известно устройство,содержащее матрицу запоминающих ячеек и детекторы осуществляющие формирование сигналов на адресных шинах модулей памяти 11 Этому устройству свойственно невысокое быстродействие. Наиболее близким техническим решением к изобретению является ассоциативное запоминающее устройство,содер жащее входной регистр,одни выходы ко торого подключены к входам первого накопителя, подключенного к первому регистру адреса и блоку управления, второй регистр адреса, соединенный через элементы И с вторым накопителем 2 . В этом устройстве преобразование признака в адрес памяти с произвольным доступом осуществляется путем выполнения некоторой последовательности преобразований над значениями разрядов входного регистра, соответствующих признаку для поиска информации и выборки из накопителей адресов для записи в память с произвольным доступом. Вид и последовательность преобразований определяет используемые наборы логических блоков и топологию связей между ними. Однако любые изменения в классификации связаны с внесением изменений в устройство. Это исключает возможность оперативной перестройки устройства, приводит к необходимости разработки специального устройства для каждого конкретного применения, что существенно снижает область применения устройства. Целью изобретения является расширение области применения устройства. Достигается это тем, что устройство содержит сумматор, преобразователь кода, блок контроля и третий накопитель, входы которого подключены к другим выходам входного регистра, а выходы - к входам второго регистра адреса, один из выходов второго накопителя соединен с входом преобразователя кода, выход которого подключен к входу второго накопителя и входу блока контроля, выход которого соединен с входом блока управления, входы сумматора подключены соответственно к другому выходу второго накопителя и выходу преобразова1еля кода, а выходы сумматора соедийены с входами первого регистра адре са. На фиг.1 дана блок-схема устройства; на фиг.2 - блок-схема третьего накопителя; на фиг.З - функциональная схема ячейки памяти этого накопителя; на фиг.4 - функциональная схема ячейки выдачи результата третьего накопителя. Устройство (см.фиг.1) содержит входной (n+k+l) -. разрядный регистр 1, предназначенный для приема входного кода по входу 2. Выход 3 регист ра 1 соединен с выходом устройства 4 и с входом 5 первого накопителя 6 (разряды регистра 1 - с первого по п-ный). Выход 7 регистра 1 объединяе разряды регистра с (п+1) по (n+k)-ы Выход 8 накопителя служит для передачи информации из накопителя 6 на вход 9 регистра 1. Устройство содержит также первый регистр гщреса 10, выход 11 которого соединен с входом накопителя б. Регистр 10 имеет входы 12. Выход 13 (п + k + 1)-го старшего разряда регистра 1 соединен с входом блока управления 14, имеющего выходы 15-20. Устройство содержит также третий накопитель 21, входы которого подключены к выходам 7 регистра 1, а вы ходы 22 - к входам второго регистра алреса 23. Информационные входы 24 элементов И 25 соединены с выходами регистра 23, а выходы 26 элементов И 25 подключены к входам второго накопителя 27, выходы 28 которого соединены с одним из входов суммато ра 29. Один из выходов накопителя il соединен с входом 30 преобразова теля кода Л. Другие входы 32 сумма тора 29, входы 33 накопителя 27 и входы 34 блока контроля 35 подключены к выходам преобразователя кода 31. Выходы сумматора 29 соединены с входами 12 регистра 1. Накопитель 27 является {Ь т)-разрядным, причем в сумматор 29 поступает базовая часть кода (разряды с 1-го по Ь-ый) а в преобразователь кода 31 индексная часть кода (остальные разряды). В блоке 35 осуществляется сравнение кода с нулевым кодом. Накопитель 21 (см.фиг. 2-) содержи г линеек по k ячеек памяти 36 в каж дой линейке, г ячеек выцачи результата 37 по одной в каждой линейке kaнaл передачи 38 в прямом коде и к нал передачи 39 в инверсном коде состояния (п+1) - (n+k)-i-o разрядов регистра 1, каналы ввода.40 и 41 константы в ячейки памяти 36, имеющие номер 1 в каждой линейке, и в ячейку 37 выдачи резул тата с номером 1, каналы передачи 42,43 и 44 информации на входы ячее памяти 36 с номером 1 между ячежами памяти 36 и от ячеек памяти 36 с номерами k к ячейкам выдачи результата 37. Каждая ячейка памяти 36 (см.фиг.З) содержит триггер 45, состояние которого задает значение i -го разряда J-го эталона, триггер 46, являющийся i-ым разрядом j-го регистра маски, элементы И 47 и 48, на которые по каналам передачи 38 и 39 поступает значение i-го разряда с регистра 1 в прямом (Х) и инверсном (Х4} коде, по каналу передачи 43 поступает сигнал сравнения кодов в (i - 1)-ой ячейке j-ой линейки, по каналам передачи 49,50 - состояние триггера 45 в прямом (2U) и инверсном (;) коде по каналу передачи 51 - состояние триггера 46 в инверсном (Y;p коде, каналы передачи 52 и bJ выходных сигналов элементов И 47 и 48 на элементы ИЛИ 54 и 55 и элементы НЕ 56 и 57, каналы передачи 58,59 выходных сигналов элементов НЕ 56, 57 на элемент И 60. Каждая ячейка выдачи результата 37 (см.фиг.4) содержит триггер 61, состояние которого задает вид сравнения кода с эталоном, каналы neper дачи 62 и 63 состояния триггера 61 в прямом (Wj) и инверсном (Wj) коде, элементы И 64 и 65, элемент ИЛИ 66 сигналов, поступающих по каналам 42 и 43 с выхода k-ой ячейки памяти 36 j-ой линейки накопителя 21, канал передачи 67 выходного сигнала элемента ИЛИ 66 на вход вентиля 65, каналы передачи 68 и 69 выходных сигналов элементов И 64 и 65 на вход элемента объединения 70. Предложенное устройство работает в режимах приема и поиска информации. Режим приема информации. В этом режиме необходимо по признаку, сопровождающему поступающую на вход устройства информацию, определить место в накопителе 6, куда необходимо записать эту информацию с тем, чтобы она была доступна в дальнейшем для ассоциативного поиска, т.е. могла быть выбрана в случае, когда признак запроса полностью или в заданной части совпадает с признаком, который сопровождал информацию при записи. Настройка устройства перед началом работы заключается в следующем. В триггеры 45 ячеек памяти 36 накопителя 21 записываются значения эталонов для классификации входных признаков. При этом триггеры 45 одной линейки рассматриваются как разряды одного k-разрядного эталона. В триггеры 46 ячеек памяти 36 накопителя 21 записываются признаки включения ячеек памяти 36 в процесс сравнения признака с эталоном. При этом триггеры 46 одной линейки рассматриваются как разряды одного k-разрядного регистра маски. Введение регистров маски раздельно по все эталонам позволяет анализировать признак запроса как по всем разрядам признака, так и по заданной совокупности разрядов, назначаемой независимо для каждого эталона. В триггеры 61 ячеек выдачи резуль тата 37 накопителя 21 записываются признаки, определяющие вид сравнения с эталоном раздельно по каждой линейке. При этом триггеры 61 рассматриваются как разряды одного г-разрядного регистра вида поиска. Установка триггера 61 ячейки выдачи результата 37 в j-ой линейке в состо ние 1 соответствует логическому поиску по j-му эталону в состояние О - параметрическому поиску по J-му эталону. В последнем случае в качестве эталонов задаются граничные значения интервалов на шкале значений рассматриваемого физичесkoro параметра. Кроме перечисленного, при настрой ке устройства производится запись в накопитель 27 текущего состояния распределения ячеек накопителя 6. Накопитель 27 содержит г числовых ячеек - по одной на эталон. Разрядность каждой линейки равна (Ь + тп) . В разряды с 1 по Ь-ый для , j-ой линейки записывается число, на единицу меньшее адреса первой ячейки области амяти накопителя 6, выделенной для информации, соответствующей j-му эталону; в разрядах с (Ь + 1) по (Ь + т)-ый - число занятых ячеек в этой области. В режиме приема информации код поступает на входной регистр 1. Содержательная часть входной инфо мации поступает в накопитель 6. Стар ший разряд регистра 1 устанавливает в блоке управления 14 режим прием Код признака с регистра J. поступа на вход накопителя 21, в котором одн временно во всех линейках производится сравнение принятого кода приэ ка с эталонами - содержюлым регистро образованных триггерами 45 ячеек пам ти 36. Сравнение кодов признака и этало происходит следующим образом. Производится последовательное по разрядное сравнение этих кодов, Нач ная со старшего (i-ro, равного Ч Если значения кодов в рассматриваемом разряде совпадают, то начинается сравнение в следующем разряде; если значения не совпали, то процесс сравнения заканчивается, и код, значение которого в данном разряде большее, считывается большим. В двоичном коде значение каждого разряда может быть равно или О, или 1. Логика сравнения иллюстрируется в табл. 1. Т а б л и ц. а В соответствии с табл.1 для выявления соотношения между X и Zj необходимо реализовать соотношения O.-X.AZ,,,- (П Ьи-х- л1,д t2) с х. лг..|.лх.л2. () Одновременно истинным может быть одно и только одно из соотношений (1) - (3) . Сигналы, поступающие по шинам О, и Ь от (1 - 1)-ой ячейки, должны ретранслироваться через i-ую ячейку незав исимо от соотношения между Х и Сигналы а , , с в i-ой ячейке должны вырабатываться только при наличии сигнала C, 1 и состоянии триггера 46 в состояние О, т.е. при Yj -0. для удовлетворения этим условиям необходимо: формировать сигналы на выходах 42, 43 и 44 i -ой ячейки памяти 36 в соответствии с табл.2; на входы 42 и 44 первых ячеек в каждой линейке подать сигнал, эквивалентный О .

49

ы

к

О 1 1

1 1 1 1 о

О

Приме тание на результат. Комбинационная схема, представлен ная на фиг.З, реализует соотношения соответствующие табл.2. Сигналы с выходов ячеек памяти 36 имеюи1их i - k, поступают на одноименные входы ячеек выдачи результатов 37 со сдвигом на 1 для канала 44 сигнал J-ой линейки поступает на вход j + 1 ячейки 37, вход 1-ой ячей ки 37 закоммутирован на константу , а выход г-ой линейки не испол зуется. Элемент ИЛИ 70 формирует сигнал соответствующий выполнению условия X г Z (по разрядам, для которых ) Элемент И 65 выдает сигнал только в том случае, когда одновременно X Z: и X Z т.е. значение X лежит в полуоткрытом интервале Zj , а триггер 61 находится в состоянии , т.е. задан параметрический поиск. Элем.,нт И 64 выдает сигнал в случае, когда X Zj (по разрядам, для которых Y,-j -- 0) , а триггер 61 находится в состоянии О т.е. задан логический поиск. Элемент ИЛИ 70 передает сигналы, поступающие с элементов И 64 и 65 на выход 22. Результат сравнения через ячейки выдачи результата 37 передается в регистр 23. В регистре 23 устанавливаются в разряды, соответст вующие номерам линеек в накопителе 21 с положительным результатом срав нения. В общем случае схема клиссификации может быть построена таким образом, что признак входной информации соответствует одновремен но нескольким эталонам, в результат возможна установка одновременно неТаблица 2 к - значение не влияет скольких разрядов регистра 23 Е состояние . Блок управления 14 поочередно через элементы И 25 подключает по одному разряды регистра 23 к выходам 26накопителя 27. Если значение подключаемого разряда регистра 23 равно О, то считывание из накопителя 27 не происходит,и блок управления 14 переходит к следующему разряду регчстра 23, если значение равно , то считывается содержимое из ячейки с номером, равным номеру подключенного разряда регистра 23. Содержимое с первого по b-ый разряд считатанного кода (база) передается в сумматор 29, содержимое с (Ь+1) по (Ь+т)-ый разряд (индекс) - в преобразователь 31, где к значению индекса прибавляется 1, модифицированное значение индекса передается в сумматор 29, где суммируется с кодом базы, образуя код адреса для накопителя 6, Одновременно модифицированное значение индекса записывается в накопитель 27на место считанного значения индекса для фиксации корректировки. По сигналу блока управления 14 по выданному коду адреса производится запись в накопитель 6 информации, имеющей место на входе 5. После завершения цикла записи в накопитель 6 блок управления 14 выбирает следующий разряд регистра 23 и повторяется описанный процесс. По окончании цикла подключении г-го разряда регистра 23 вьщается сигнал завершения режима приема информации. Режим поиска информации. В этом режиме необходимо выжать из накопителя 6 содержимое всех ячеек. q6 признаковые коды которых в разрядах не закрытых маской, соответствуют з просу на поиск. В режиме поиска информации на вх ной регистр 1 по входу 2 подается (k+1)-разрядный код на разряды с (п+1) по (п+К-И)-ый. Старший разряда регистра 1 устан ливает в блоке управления 14 режим поиск с выдачей соответствующей последовательности управляющих сигна пов на блоки устройства. Кол признака с регистра 1 поступает с выхода 7 для формирования адр са считывания из накопителя 6. Работа устройства в части формиро вания кода на регистре 23, соответс вующего принятому на регистр 1 коду признака, и считывания содержимого числовых линеек из накопителя 23 на сумматор 29 и преобразователь 31 про ходит точно так же,как в режиме при ма информации. После передачи кода базы в сумматор 29 и кода индекса в преобразователь 31 работа устройства происходит следующим образом. Содержимое преобразователя 31 пер дается в сумматор 29 ,ч где суммируется с кодом базы. Результатом суммиро вания является код адреса, который передается в регистр адреса 10. По сигналу блока управления 14 осуществляется считывание из накопителя б по адресу, установленному на регистре 10. Считанная информация записывается в разряды с 1 по п-ый входного регистра 1, откуда с выхода 3 передается на выход 4 устройства. После завершения цикла считьгеания из накопителя б содержимое преобразователя 31 уменьшается на едини цу, результат сравнивается в блоке контроля 35 с нулем. Если новое значение индекса больше нуля, то модифицированное значение индекса передается в сумматор 29 и повторяется цикл считывания. Таким -образом, на выход 4 передается инфор мация из всех ячеек зоны накопителя 6, которая соответствует признаку запроса. Как только преобразователь 31 устанавливается в О, блок контроля ЗЬ выдает сигнал в блок управления 14 для перехода к следующему разряду регистра 23. При поиске информации никаких кор ректировок содержимого накопителя 27 и никаких записей в накопитель 6 не производится. По окончании цикла подключения г-го разряда регистра 23 выдается сигнал завершения режима поиска информации. Для стирания информации в какойлибо зоне достаточно обнулить значение индекса в соответствующей числовой линейке накопителя 27. Предлагаемое устройство, не уступая известным устройствам, llj и 12J по быстродействию, обладает универсальностью в широком смысле. Оно доступно для оперативной смены информации, так как классификационные эталоны з аносятся в накопители програмнымТ1утем и позволяет выполнять поиск как логического вида - по наличию определенной совокупности признаков, так и параметрического вида - по численному значению вьщеленных параметров . Формула изобретения Ассоциативное запоминающее устройство, содержащее входной регистр, одни выходы которого подключены к входам первого накопителя, подключенного к первому регистру адреса и блоку управления, вторюй регистр адреса, соединенный через элементы И с вторым накопителем, отличающееся тем, что, с целью расширения области применения устройства, оно содержит сумматор, преобразователь кода, блок контроля и третий накопитель, входы которого подключены к другим выходам входного регистра, а выходы - к входам второго регистра адреса,один из выходов второго накопителя соединен с входом преобразователя кода, выход которого подключен к входу второго накопителя и входу блока контроля, выход которого соединен с входом блока управления, входы сумматора подключены соответственно к другому выходу второго накопителя и выходу преобразователя кода, а выходы сумматора соединены с входами первого регистра адреса. Источники информации, принятые во внимание при экспертизе 1.Патент США № 32У799Ь, кл, 340-172,Ь, 1967. 2.Авторское свидетельство СССР № 4Ь45Ы, М.кл G 06 F lb/4U, 1У72.

фиг.1