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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЪСТВУ

Союз Советскик

Социалистических

Республик ((ц 649038

1 ° ( (61) Дополнительное к авт. свнд-ву (22) Заявлено 301276(21)2437704/18-24 с присоединением заявки №вЂ” (23) Приоритет— (51) М. Кл.

С; 11 C 1SyOO

I осударственный комитет сссР но делам изобретений и открытий (53) УДК 631. 327 (088. 8) Опубликовано 250279- Бюллетень № 7

Дата опубликования описания 250279 (72) Авторы изобретения

Y.Â.Ãóøèíà и Т.С.Засыпкина (71) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО

Изобретение относится к запоминающим устройствам и может быть использовано в информационно-поисковых системах.

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

Этому устройству свойственно невысокое быстродействие. l0

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

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

Однако любые изменения в классификации связаны с внесением изменений в устройство. Это исключает возможность оперативной перестройки устройства, приводит к необходимости разработки специального устройства для каждого конкретного применения, что существенно снижает область применения устройства.

Целью изобретения является расширение области применения устройства.

Достигается это тем, что устройство содержит сумматор, преобразователь кода, блок контроля и третий накопитель, входы которого подключены к другим выходам входного регистра, а выходы — к входам второго регистра адреса, один из выходов второго накопителя соединен с входом преобразователя кода, выход которого подключен к входу второго накопителя и входу блока контроля, выход которого соединен с входом блока управления, входы сумматора подклю ены соответственно к другому выходу второго накопителя и выходу преобразовазеля кода, а выходы сумматора соеди649038

10 иены с входами первого регистра адре( са.

На фиг.l дана блок-схема устройства; на фиг.2 — блок-схема третьего накопителя; на фиг.3 — функциональная схема ячейки памяти этого накопителя; на фиг.4 — функциональная схема ячейки выдачи результата третьего накопителя.

Устройство (см. фиг. 1) содержит входной (n+k+1) —. разрядный регистр

1, предназначенный для приема входного кода по входу 2. Выход 3 регистра 1 соединен с выходом устройства 4 и с входом 5 первого накопителя 6 (разряды регистра l — с первого по и-ный). Выход 7 регистра 1 объединяет разряды регистра с (n+1) по (n+k)-ый

Выход 8 накопителя служит для передачи информации из накопителя 6 на вход 9 регистра 1. Устройство содержит также первый регистр адреса 10, выход ll которого соединен с входом накопителя 6. Регистр 10 имеет входы 12. Выход 13 (n + k + 1) -ro старшего разряда регистра 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 является (b + m)-разцядным, причем в сумматор 29 поступает базоная часть кода (разряды с 1-ro no b-ый), а н преобразователь кода 31 индексная часть кода (остальные разряды).

В блоке 35 осуществляется сравнение кода с нулевым кодом.

Накопитель 21 (см.фиг.2-) содержит

r линеек по k ячеек памяти 36 и каждой линейке, r ячее к ныцачи результата 37 по одной н каждой линейке канал передачи 38 н прямом коде и канал передачи 39 н инверсном коде состояния (п+1) — (n+k) -ro разрядов регистра 1, каналы ввода.40 и 41 константы 0 и 1 в ячейки памяти 36, имеющие номер 1 н каждой линейке, и н ячейку 37 выдачи результата с номером 1, каналы передачи

42,43 и 44 информации на входы ячеек памяти 36 с номером 1 между яче .ками памяти 36 и от ячеек памяти 36 с

65 номерами k к ячейкам выдачи результата 37.

Каждая ячейка памяти 36 (см.фиг.3) содержит триггер 45, состояние которого задает значение i -го разряда

j-ro эталона, триггер 46, являющийся

1-ым разрядом j-го регистра маски, элементы И 47 и 48, на которые по каналам передачи 38 и 39 поступает значение i-го разряда с регистра 1 в прямом (Х ) и инверсном (Х ) коде, по каналу передачи 43 поступает сигнал сравнения кодов в (i — 1)-ой ячейке 3-ой линейки, по каналам передачи 49,50 — состояние триггера 45 в прямом (tt;)) и инверсном (%;() коде,и по каналу передачи 51 — состояние триггера 46 в инверсном ((()) коде, каналы передачи 52 и ЬЗ выходных сигналов элементов И 47 и 48 на элементы

ИЛИ 54 и 55 и элементы НЕ 56 и 57, каналы передачи 58,59 выходных сигналон элементов HE 56, 57 на элемент

И 60.

Каждая ячейка выдачи результата

37 (см.фиг.4) содержит триггер 61, состояние которого задает вид сраннения кода с эталоном, каналы йере-. дачи 62 и 63 состояния триггера 61 в прямом (W>) и инверсном (W)) коде, элементы И 64 и 65, элемент ИЛИ 66 сигналов, поступающих по каналам

42 и 43 с выхода k-ой ячейки памяти

36 3-ой линейки накопителя 21, канал передачи 67 выходного сигнала элемента HJIH 66 на вход вентиля 65, каналы передачи 68 и 69 выходных сигналов элементов И 64 и 65 на вход элемента объединения 70. предложенное устройство работает в режимах приема и поиска информации.

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

Настройка устройства перед началом работы заключается в следующем.

В триггеры 45 ячеек памяти 36 накопителя 21 записываются значения эталонов для классификации входных признаков. При этом триггеры 45 одной линейки рассматриваются как разряды одного k-разрядного эталона.

B триггеры 46 ячеек памяти 36 накопителя 21 записываются признаки включения ячеек памяти 36 в процесс сравнения признака с эталоном. При этом триггеры 46 одной линейки рассматриваются как разряды одного

649038

Таблиц,а1

Шина Х езультат

b; с; к-разрядного регистра маски. Введение регистров маски раздельно по всем эталонам позволяет анализировать признак запроса как по всем разрядам признака, так и по заданной совокупности разрядов, назначаемой независимо для каждого эталона. 3

В триггеры 61 ячеек выдачи результата 37 накопителя 21 записываются признаки, определяющие вид сравнения с эталоном раздельно по каждой линейке. При этом триггеры 61 рас- 30 сматрпваются как разряды одного

r-разрядного регистра вида поиска.

Установка триггера 61 ячейки выдачи результата 37 в 3-ой линейке в состояние 1 соответствует логическому поиску по j-му эталону в состояние Π— параметрическому поиску по

j-му эталону. В последнем случае в качестве эталонов задаются граничные значения интервалов на шкале @ значений рассматриваемого физического параметра.

Кроме перечисленного, при настройке устройства производится; запись в накопитель 27 текущего состояния распределения ячеек накопителя 6.

Накопитель 27 содержит r числовых ячеек — по одной на эталон. Разрядность каждой линейки равна (b + m) .

В разряды с 1 по Ь-ый для,j-ой личейки записывается число, на единицу 30 меньшее адреса первой ячейки области памяти накопителя 6, выделенной для информации, соответствующей j ìó эталону; в разрядах с (b + 1) по (b + m) ûé — число занятых ячеек в этой области.

В режиме приема информации код поступает на входной регистр 1.

Содержательная часть входной информации поступает в накопитель 6. Стар- 40 ший разряд регистра 1 устанавливает в блоке управления 14 режим прием .

Код признака с регистра 1 поступает на вход накопителя 21, в котором одновременно во всех линейках производится сравнение принятого кода призна45 ка с эталонами — содержимым регистров, образованных триггерами 45 ячеек памяти 36.

Сравнение кодов признака и эталонов происходит следующим образом. 50

Производится последовательное поразрядное сравнение этих кодов, Начиная со старшего (i †„ равного 1 ).

Если значения кодов в рассматриваемом разряде совпадают, то начинает- 55 ся сравнение в следующем разряде; если значения не совпали, то процесс сравнения заканчивается, и код, значение которого в данном разряде большее, считывается большим.

В-двоичном коде значение каждого разряда может быть равно или О, или 1.

Логика сравнения иллюстрируется в табл. 1.

О Х; л 2 не определен т) 1 Х; Л 1; не определен

В соответствии с табл.1 для выявления соотношения между Х и Z необФ ходимо реализовать соотношения а,=к„л z; (11

Ь =х- Л1- (2)

1 1 1) с. = х. n z .лх. л2, (э)

1 1 1) 1 1j

Одновременно истинным может быть одно и только одно из соотношений (1) — (3) .

Сигналы, поступающие по шинам й. и b от (i — 1) -ой ячейки, должны ретранслироваться через i-ую ячейку независимо от соотношения между Х и

Сигналы а;, b„., с; в i oA ячейке должны вырабатываться только при наличии сигнала С„„ = 1 и состоянии триггера 46 в состояние О, т.е. при Y = О.

Для удовлетворения этим условиям необходимо: формировать сигналы на выходах

42 43 и 44 i -ой ячейки памяти 36

I в соответствии с табл.2; на входы 42 и 44 первых ячеек в каждой линейке подать сигнал, эквивалентный О .

649038

Т а б л и ц а 2

51 49 50 38 39 42 43 44 42 43 44

0 1 0 О

Ф м «

1 О 1 О

0 1 О О

О 1 О

О 1 1

О 1 1 О . О 1 О

О 1 О

1 1 О О 1

1 О % О

П р и м е ч а н и е. Знак + — значение не влияет на результат.

Комбинационная схема, представленная на фиг.3, реализует соотношения, соответствующие табл.2.

Сигналы с выходов ячеек памяти 36, имеющих 1 — k поступают иа одноименные входы ячеек выдачи результатов 37 со сдвигом на 1 для канала 44; сигнал j — ой линейки поступает на вход j + 1 ячейки 37, вход 1-ой ячейки 37 закоммутирован на константу 1, а выход r-ой линейки не исполь зуется.

Элемент ИЛИ 70 формирует сигнал, соответствующий выполнению условия

Х - 2 (по разрядам, для которых Y„. 0) .

Элемент И 65 выдает сигнал только в том случае, когда одновременно X K Z и Х ) 2,, т.е. значение Х лежит в полуоткрытом интервале Z — 2

У а триггер 61 находится в состоянии 1, т. е. задан; араме грический поиск. Элем. нт И 64 выдает сигнал в случае, когда Х = 2 (по разрядам, для которых Х;. О), а триггер 61 находится в состоянии 0, т.е. задан логический поиск.

Элемент ИЛИ 70 передает сигналы, поступающие с элементов И 64 и 65 на выход 22.

Результат сравнения через ячейки выдачи результата 37 передается в регистр 23. В регистре 23 устанавливаются в 1 разряды, соответствующие номерам линеек в накопителе

21 с положительным результатом сравнения. В общем случае схема клиссификации мажет быть построена таким образом, что признак входной информации соответствует одновременно нескольким эталонам, в результате возможна установка одновремс нно нескольких разрядов регистра 23 в состояние 1 .

Блок управления 14 поочередно через элементы И 25 подключает по одному разряды регистра 23 к выходам

26 накопителя 27. Если значение подключаемого разряда регистра 23 равно 0, то считывание иэ накопителя 27 не происходит,и блок управления 14 переходит к следующему разряд у

per «стра 23, если значение равно 1, то считывается содержимое из ячейки с номером, равным номеру подключенного разряда регистра 23. Содер40 жимое с первого по ()-ый разряд считатанного кода (база) передается в сумматор 29, содержимое с (Ь+1) по (b+m)-ый разряд (индекс) — в преобразователь 31, где к значению индекса прибавляется 1, модифицированное значение индекса передается в сумматор

29, где суммируется с кодом базы, образуя код адреса для накопителя 6.

Одновременно модифицированное значе9) ние индекса записывается в накопитель

27 на место считанного значения индекса для фиксации корректировки.

По сигналу блока управления 14 пб выданному коду адреса производится запись в накопитель 6 информации, имеющей место на входе 5.

После завершения цикла записи в накопитель 6 блок управления 14 выбирает следующий разряд регистра

23 и повторяется описанный процесс.

60 По окончании цикла подключения r-го разряда регистра 23 выдается сигнал завершения режима приема информации.

Режим поиска информации.

В этом режиме необходимо выжать

65 из накопителя 6 содержимое всех ячеек, 649038

10 признаковые коды которых в разрядах, не закрытых маской, соответствуют запросу на поиск.

В режиме поиска информации на входной регистр 1 по входу 2 подается (k+1) -разрядный код на разряды с (n+1) по (n+k+1)-ый. 5

Старший разряда регистра 1 устанавливает в блоке управления 14 режим поиск с ныдачей соответствующей последовательности управляющих сигналов на блоки устройства. 10

Код признака с регистра 1 поступает с выхода 7 для формирования адреса считывания из накопителя 6.

Работа устройства в части формирования кода на регистре 23, соответст- 1 вующего принятому на регистр 1 коду признака, и считывания содержимого числовых линеек иэ накопителя 23 на сумматор 29 и преобразователь 31 происходит точно так же,как в режиме приема информации.

После передачи кода базы в сумматор 29 и кода индекса в преобразователь 31 работа устройстна происходит следующим образом.

Содержимое преобразователя 31 пере.й дается в сумматор 29 „, где суммируется с кодом базы. Результатом суммирования является код адреса, который передается в регистр адреса 10. По сигналу блока управления 14 осущест- 30 вляется считывание иэ накопителя б по адресу, установленному на регистре 10. Считанная информация записывается в разряды с 1 по и -ый входного регистра 1, откуда с ныхода 3 передается на выход 4 устройства.

После завершения цикла считывания из накопителя 6 содержимое преобразователя 31 уменьшается на единицу, результат сравнивается в блоке контроля 35 с нулем. Если новое значение индекса больше нуля, то модифицированное значение индекса передается в сумматор 29 и повторяется цикл считывания. Таким .образом, на выход 4 передается инфор- 45 мация из всех ячеек зоны накопителя 6, которая соответствует признаку запроса. Как только преобразователь

31 устанавливается в 0, блок контроля 35 выдает сигнал н блок 50 управления 14 для перехода к следующему разряду регистра 23.

При поиске информации никаких корректировок содержимого накопителя 27 и никаких записей в накопитель Ь не производится. По окончании цикла подключения r-го разряда регистра 23 выдается сигнал завершения режима поиска информации.

Для стирания информации н какойлибо зоне достаточно обнулить значение индекса в соответствующей числовой линейке накопителя 27.

Предлагаемое устройство, не уступая известным устройствам. (1) и (2) по быстродействию, обладает универсальностью в широком смысле. Оно доступно для оперативной смены информации, так как классификационные эталоны заносятся в накопители програмным путем 1и позводяет выполнять поиск как логического вида — по наличию определенной совокупности признаков, так и параметрического вида — по численному значению выделенных параметров. формула изобретения

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

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

Источники информации, принятые но внимание при экспертизе

1. Патент СИА У 3297995, кл. 340 †1,5, 1967.

2. Авторское свидетельство СССР

М 454561, И.кл. G 06 F 15/4U, 19/2.

649038 ив. 5

Аи.4

Составитель В.Рудаков

Редактор Й.Гончар Техред М. Петко . Корректор Л.Веселовская

Закаэ 566/49 Тираж 660 Подписное

ЦНИИПИ Государственного комитета СССР по делам иэобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Филиал ППП Патент, г.ужгород, ул. Проектная, 4