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

2.Устройство no п. 1, отличающееся тем, что накопитель с одномерной выборкой содержит блок памяти, первый и второй селекторы, первь й и второй элементы ИЛИ, причем адресные входы юрвой и второй групп блока памяти подключены к входам первого и второго селекторов соответственно и являются входами накопителя, выходы селекторов соединены с входами первого элемента ИЛИ, первый вход второго элемента ИЛИ подключен к выходу блока памяти, второй вход соединен с выходом первого элемента ИЛИ, а выход является выходом накопителя.

3.Устройство по п. 1, отличающееся тем, что накопитель с многомерной выборкой содержит блок памяти, первый и второй : ;.::, : -::;Ч;рь:, перзык и HTOpoi; селекторы,

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

1, АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО, содержащее блок управления и накопители, отличающееся тем, что, с целью повышения быстродействия и надежности, в него введены блоки управления поиском и блоки обработки данных, причем входы накопителей подключены к выходам соответствующих блоков управления поиском, выходы накопителей соединены с входами соответствующих блоков обработки данных, выходы которых подключены к входам соответствующих блоков управления поиском, управляющие входы и выходы блока управления соединены с соответствующими входами и выходами блоков управления поиском, а входы/выходы сопряжения блока управления и блоков управления поиском являются входами / выходами устройства. (Л о ;о о to со ui.

1

И:«)бретен1 е относится к вычислительiioii технике и может быть испо.1ьзовано при ио(.Г|)сеиии систем хранения м поиска информации и банков данных с ассопиативн.ым поиском.

Целью изобретения является повыи ение быст.)оде;1ствня и надежности устройства.

H.i фиг. 1 нредстаЕ лена структурная схема ;1ссо1-иативного запоминающего устройства д,:1я слов, состоящих из четырех

букв; на флг. 2 схема накопителя с одноп)оме 1чо11 выборкой; на фиг. 3 - схема ..оп 11ч:-,я с .Ч1 01омерной выборкой; на фи.г. 4 пример кодирования отношения в накопителе; на фиг. 5 - пример кодирования слов.

Устройство (фиг. 4) содержит наконите-лк 1, блоки 2 у(равления поиском; блоки 3 обработки дагигоьч, блок 4 управления, входы/выходы 5 и 6 сопряжещш соответCTBeiHo блоков 3 обработки данных и блока 4 управления, управляющие входы и выходы 7.

Накопитель с одновременной выборкой (фиг. 2) содержит первую группу адресных входов 8, блок 9 памяти, первый селектор 10, Г1ерв1 |й эле.мепт ИЛИ 11, вторую группу адресных входов 12, второй селектор 13, второй элемент ИЛИ 14 и выход 15.

Иакопител) с многомерной выборкой (фин . 3) содержит первую группу адресных входов 16, мультиплексор 17, первый се.:ект(:р 18, триггер 19, блок 20 памяти, вторую группу адресных входов 21, второй се..leKTOp 22, мультиплексор 23, выходы 24 и элемент И 25.

Блоки 2 управления поиском, блоки 3 обработки данных и блок 4 управления представляет собой управляющие автоматы, например, на основе микро-ЭВМ.

Массив запоминающих ячеек накопителя (фиг. 4) представляет собой прямоуголь 1ую .матрицу, строки и столбцы которой соответствуют символам алфавитов i и i букв соответственно. Ненулевому значению запоминаемого отнощения соответствует

0 единица, записанная на пересечении соответствующих строки и столбца. Например, если в запоминае.мом слове i и j буквы являются А и В соответственно, то единица записывается на пересечении строки, соответствующей букве А, и столбца, соответствующего букве В.

На фиг. 5 показан пример кодирования слов в ассоциативном запоминающем устройстве, где Rijj - множество 1, j отношений, хранящихся в поле памяти 1, j нако0 иителя. Горизонтальные и вертикальные линии отражают информационные связи между отношениями, в ассоциативном заноминающем устройстве им соответствуют горизонтальные и вертикальные входы. Матрицы отношений расположены так, что для каждой буквы слова существует одна информационная связь по всем отнощениям, включающим эту букву. Шкалы «I буква, 11 буква и так далее отражают соотнощения соответствующих горизонтальных и вертикальных входов и соответствуют состояниям выходных сигналов процессоров второго вида. При записи слова в намять соответственно значениям всех его букв возбуждают все горизонтальные и вертикальные линии. При этом в каждом из накопителей одна ячейка памяти. Импульсом записи, подаваемы.м одновременно во все накопители, осуществляется запись единиц в выбранные ячейки памяти. Этим единицам соответствуют ненулевые отношения в записываемом слове. Если в словах имеются одинаковые отношения, то эти отношения кодируются одинаково и хранятся в одних и тех же ячейках намяти, т. е. без избыточности. Например, в словах «Сеть, и «Суть отношения RI.3, R1.4 и R3.4 одинаковы, и они хранятся в одни.х и тех же ячейках памяти для обоих слов. Ассоциативная выборка информации осуществляется следующим образом. Предположим, требуется выбрать из памяти слово, первая и вторая буквы которого с и у соответственно (фиг. 6). Сначала проводят горизонтальную линию на уровне буквы-6 от и1калы, соответствующей первой букве, а также горизонтальную и вертикальную линии на уровне буквы у от шкалы, соответст1 Ю цей второй букве. Если на нересечении этих Л1Н11Й записана единица, т.е. отношение , значит в ассоциативном запоминающем устройстве присутствуют слова с заданным поисковым признако.м. Далее просматривают пары отношений RI.3--R2.3 и RL4 - R2.4 пересекая их вертикальными линиями.. При этом запо.минают все такие сочетания отнон1ений когда оба отношения в па)е одновременно равняются единице. После этого, исходя из полученных наборов, проводят вертикальные линии, соответствующие третьей и четвертой буквам, и горизонтальную линию, соответствуюцд.ую третьей букве. При это.м, если R3., поиск прекраихают и считывают искомые буквы. В противном случае устанавливают ;ipyroe сочетание претьей и четвертой букв и вновь проверяют отношение R3.4. Накопитель с одномерной выборкой работает следующим образом. При подаче на входы 8 и 12 кодов букв в блоке 9 намяти выбирается соответствующая ячейка памяти, содержимое которой появляется на выходе блока 9. На выходах селекторов 10 и 13 появляется сигнал логической «1 в случае, если на соответствующем входе 12 или 8 появляется код, означающий, что поиск по данной букве не производится. Сигнал с выхода блока 9 памяти ноявляется на выходе 15 лишь в случае, если на горизонтальный 12 и вертикальный 8 входы поданы коды букв из соответствующих алфавитов. В цротивном случае на выходе 15 накопителя постоянно присутствует сигнал логической «1. Накопитель с многомерной выборкой работает следующим образом. Блок 20 па.мяти с многомерной выборкой представляет собой квадратный массив запоминающих ячеек и имеет столько информационных выходов и входов, сколько запоминающих ячеек содержится в ее строке либо столбце. В зависимости от управляющего сигнала на выходах блока 20 появляется содержимое всей строки либо столбца массива запо.минающих ячеек, адрес которых установлен на его адресных входах Триггер 9 управляется сигналами от горизонтального 21 и вертикального 16 входов и служит для подключения к адресным входам блока 20 намяти посредством мультиплексора 17 сигналов из горизонтального 21 либо вертикального 16 входов, а также для управления направ.ie;ii:eM выборки в запоминающем устройстве 20. Селекторы 18 и 22 предназначены .пя обнаружения кода запрета выборки на ropii30HTa, 21 и вертикальном 16 входах соответственно и совместно с элементод П 25 и мультиплексором 23 осуществляют подключение к выходам 24 выходов блока 20 памяти ,тнбо сигналов логической «1. При этом выходы блока 20 намяти подключены к выходам накопителя лицJЬ в том случае, если или по горизонтальному входу 2, или по вертикальному входу 16 не npiiiiie.-i код запрета выборки. Асс.ч)ц; атнвное запоминающее устройст30 работает следующим образом. Перед началом работы на входах 5 блоков 3 устанавливают коды букв, составляющих по.чсковый к,тюч, при этом каждому блоку 3 соответствует буква в определенной позиции слова. Если ноисковый образ не содержит буквы в данной позиции слова, то на входе 5 соответствующего данной и()31щии слова блока 3 устанавливают код запрета. После установления на входах 5 всех блоков 3 нужных кодов подают унравля.ющий сигнал по входу 6 блока 4 управления, который, в свою очередь, по входам 7 осуществляет загрузку блоков 3 установленными на их входах 5 кодами. При этом блоки 3 возбуждают вертикальные и горизонтальные входы, соединенные с их первым li и вторы.ми выходами соответственно, кодами, соответствующих букв. В результате этого на выходах накопителей на основе запоминающего устройства с одновременной выборкой (фиг. 2), расположенных на пересечениях входов, возбужденных кодами букв, появляется содержимое выбранных ячеек памяти, отражающее наличие или отсутствие в ассоциативном запоминающем устройстве отношений, определенных ключом. На выходах накопителей,. на одну или на обе группы адресных входов которых поступил код запрета, устанавливаются сигналы логической «1. Таким образом, если выходы всех накопите,лей

находятся в состоянии логической «1, значит слово или слова с заданным поисковым признаком присутствуют в ассоциативном запоминающем устройстве. Проверка этой ситуации осуществляется с помощью блоков 2, которые в простейщем случае представляет собой схемы И.

Дальнейший поиск может производиться двумя путями. Если элементы ключа расположены преимущественно в начале слова, блок 4 управления посредством входа 7 выдан в блоки 3 управляющий сигнал, по которому последние начинают просмотр столбцов. При этом каждый блок 3 возбуждает вертикальный вход, соединенный с его первым выходом, кодами различных букв, всякий раз опращивая при slXJM выход блока 2, входы которого соединены с выходами накопителей расположенных в данном столбце. Поскольку часть горизонтальных входов уже возбуждена колами 6vKB поискового ключа, часть накопителей, расположенных на пересечении этих ropiKiOhrra.ibHbix входов с вертикальными, выдает в блоки 2 информацию о хранилпмх в них отношениях для соответствую1ЦИХ сочесаний букв. Выходы остальных накопителей находятся в состоянии логической «1. На вход блока 3 с выхода блока 2 ностунает си1нал логической «1 в том ;HIUII с.1учае. если все выбранные для установленного кода буквы отношения в столбце .чевые. Последовательно возбуждая вертикал1)иый вход кодами различных букв, блок 3 запоминает те коды букв, в ответ па которые из блока 2 поступили сигнал. логической «1, и по окончании просмотра всех букв устанавливают на вертикальном входе .код первый из них. При этом он выдает на вход 7 сигнал об окон чанни просмотра.

После .получения от всех блоков 3 сигналов об окончании просмотра блок 4 упраь.;е11ик посредством выхода 7 вьщает блокз : 3 управляющий сигнал, по которому 1ос.1едние начинают просмотр строк. Просмотр строк осуществляется так же, как н просмотр столбцов. Если его результатом является такая комбинация букв слова, для каждой из которых блок 2 соответствующей строки выдал сигнал логической «1, бло-; 4 выдает сигнал, извещающий, что первое слово с заданным поисковым ключом найдено и его буквы могут быть считаны с входов 5 блоков 3. После этого, а также в случае, если первый просмотр горизонтальных njHH не дает искомого результата, блок 4 управления посредством входа 7 выдает в блоки 3 управляющий сигнал, по которому последние устанавливают на своих вертикальных шинах другую комбинан.ию кодов букв из числа найденных прп первом просмотре столбцов. После

этого осуществляется второй просмотр горизонтальных шин и т.д.

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

Q Если элементы ключа расположены преимущественно в конце слова, поиск производят описанным способом, но начинают с просмотра строк.

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

0 блока 4 управления, который посредством выхода 7 выдает управляющие сигналы в блоки 3. При этом, если элементы ключа расположены преимущественно в начале слова, блоки 3, на входы 5 которых поданы

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

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

находятся в состоянии логической «1. Далее блоки 3 опрашивают выходы блоков 2 о столбцах. Блоки 2, в этом случае, выполняют логические операции «И над одноименными выходами всех накопителей столбца либо строки. Выход определенного разряда блока 2 находится в состоянии логической «1 лишь в том случае, если эти же разряды на выходах всех накопителей 1 столбца либо строки одновременно равны единице. В результате опроса выходов блоков 2 блок 3 запоминает коды букв, соответствующих единичным разрядам на выходах первых. При этом блоки 3, обрабатывающие элементы ключа, сравнивают эти коды с кодами букв ключа. Если коды

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

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

по сигналу из блока 4 управления .блоки 3 вновь опрашивают выходы строчных блоков 2 и т. д.

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

Таким образом, использование в ассоциативном запоминающем устройстве накопителя с многомерной выборкой существенFio снижает время поиска.

16

;

77

21

23

2

ЬГ

.З

L ая букба

Ю Я

5 В Г

ФигЛ

.2

3 Ю я 5ук8а

Ri.4