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

1169023 2. Устройство по и. 1, отличающееся тем, что накопитель с одномерной выборкой содержит блок памяти, первый и второй селекторы, первый и второй элементы ИЛИ, причем адресные Входы первой и нторой групп блока памяти подключены к входам первого и второго селекторов соответственно и являются входами накопителя, выходы селекторов соединены с входами первого элемента ИЛИ, первый вход второго элемента ИЛИ подключен к выходу блока памят 1, второй вход соединен с выходом первого элемента ИЛИ, а выход является выхс)дом на кон ителя.3. Устройство по и. 1, отличающееся тем, что накопитель с многомерной выборкой содержит блок памяти, первый и второйр.,к .рзьЙ и Вт;)р)Й сслскторы 54 Обртсн)сс Отпостс 5 к В 1 чис,1 ительцой тхпике и может быть исн)ьзонс)о 1 ри иск": ро)гии сисгс м храпения и поиска ицфс)1)мз)и и банков данных с ассоцизтпн. цьи ПОиском.1 сегь) Изобрсгсния является повниение ОЬ 1 СТРС)ДССТВИЯ И 1 ЗДЕКНОСТИ УСТРОЙСТВ.Н П 1 г.и редставлецз структурная СХЕМ, СОНИ)ТИ В 1)ГО ЗЗПОМИНЗ 1 ОЦЕГО ройств дли слов, Остояших из четырех букв; цз фиг. 2 схмз накопителя с ОдНОВ)смсОй Вы Ооркой; на фи. 3 - схем пшко 1 п ,:,.:; с и 1 о Ом ерной выборкой; на фиг. ч пр 1 мер кочи 1)ОВзни 51 Отношсния В 11 ко 1 це)1; и фиг. 5 - - пример кодирОВапия с п,)вУсгройство (фиг. 4) содержит накопит- ,иОлс)ки 2 упранлени 5 поиском: блоки 3 Обрбитки дзппых. блок 4 управления, Входь:,11 хо. 5 и 6 сопряжения соотвстств 1:нс) блоков 3 обработки данных и блока 4 у равлсция, управляюшие входы и выходы 7.НаксяНтель с Одновременной выборкой (фиг. 2) содержит первую группу адресных Входов 8, блок 9 памяти, первый селектор 10, первый элсмепт ИЛИ1, вторус) группу адрссц)х Входон 12, второй селектор 13, второй элемент ИЛИ 14 и выход 5. 111 коптеь с многомсрнОЙ Выооркой (с)и 3) содержит первую группу адресных чходон 16, мультиплексор 17, первый се. ект,) 18, трипер 19, блок 20 памяти, втогую группу здресных входов 21, второй се.ектор 22, мультиплексор 23, выходы 24 и элемецт 1; 25. 5 О 15 20 25 30 триггер, элемент И, причем адресные входы блока памяти подключены к выходам первого мультиплексора, входы первой группы которого соединены с входами первого селекторз, входы второй группы подключены к входам второго селектора, а вход управления соединен с выходом триггера и входом управления блока памяти, выходы которого подключены к входам первой группы второго мультиплексора, выходы которого являются выходами накопителя, входы второй группы соединены с шиной логической единицы, а вход управления подключен к выходу элемента И, входы которого соединены с выходами первого и второго селекторов, первый и второй входы триггера и входы селекторов являются соответственно входами накопителя. Блоки 2 управления поиском, блоки 3 обработки данных и блок 4 управления представляет собой управляюсцие автоматы, например, на основе микро-ЭВМ.Массив запоминающих ячеек накопителя (фиг. 4) представляет собой прямоугольную матрицу, строки и столбцы которой соответствуют символам алфавитов 1 ибукв соответственно. Ненулевому значению запоминаемого отношения соответствует единица, записанная на пересечении соответстнуюших строки и столбца. Например, если В запоминаемом слове 1 и ) буквы являк)тся А и В соответственно, то единица записьВается на пересечении строки, соотнетстнуюшей букве Л, и столбца, соответствующего букве О.На фиг. 5 показан пример кодирования слов н ассоц,иативном запоминающем устройстве, где К), - множество 1, ) отношений, храцяшихся н поле памяти 1, 1 накопителя. Горизонтальные и верти кальные линии отражают информационные связи между отношениями, в ассоциативном запоминаюшем устройстве им соответствуют горизонтальные и вертикальные входы. Матрицы отношений расположены так, что для каждой букны слова сушествует одна информационная связь по всем отношениям, Включаюцим эту букву, Шкалы 1 буква, 11 буква и так далее отражают соотношения соответствуюших горизонтальных и вертикальных входов и соответствуют состояниям выходных сигналов процессоров второго вида. При записи слова в намять соответственно значениям всех его букв возбуждают все горизонтальные и вертикальные линии. При этом в каждом из накопителей одна ячейка памяти. Импульсом записи, подаваемым одцовремецно во все накопители, осуществляется запись единиц в выбранные ячейки памяти. Этим единицам соответствуют ненулевые отношения в запись 1 ваемом слове. Если в словах имеются одинаковые отношения, то эти Отц 0151 еци 5 коли ру 1 отся Одинаково и хра. нятся в одних и тех же ячейках памяти, т. е. без избыточности.Например, в слова Сеть, и Суть отношения К 1.3, К 1.4 и К 3.4 одинаковы, и они хранятся в одних и тех же ячейках памяти для обоих слов. Ассоциативная выборка информации осуществляется следующим образом.11 редцоложим, тоеб 1 хется выбратг из памяти слово, первая и вторая буквы которого с и у соответственно фиг. 6). Сначала проводят горизонтальную .1 ицию на уровне буквь 1 с ог п 1 калы, соответствующей первой букве, а также горизоц гальну 1 о и вертикальную линии ца уровце оуквы у от шкалы, соответствуюпей второй букве. Если ца пересечении этих линий заг 1 исаца единица, т. с. Отноц 1 ение К 1,2 = 1, значит в ассоциативном запомицакяцсм устройстве присутствуот слова с заданным поисковым признаком. Далее просматривают пары отношений К 1.3 - - К 2.3 и К 1.4 К 2.4 пересекая их вертикальными линиями. При этом запоминают все такие сочетания Отношений когда оба отношения в царе одцовременцо равняются ели ни це. После этого, 11 схоля из получеццых цаооров. проводят вертикальные линии, соответствующие третьей и четвертой буквам, и горизоцтальцую линию, соответству юшую третьей букве. П ри этом, если К 3.4=-1, поиск прекращают и считывают искомые буквы. В противном случае устанавливают другое сочетание третьей и четвертой Оукв и вновь проверяют отношение К 3.4.Накопитель с одномерной выборкой работает следующим образом.При подаче на входы 8 и 12 кодов букв в блоке 9 памяти выбирается соответствую 1 цая ячейка памяти, содержимое которой появляется на выходе блока 9. На выходах селекторов 10 и 13 появляется сигнал логической 1 в случае, если на соответствующем входе 2 или 8 появляется код, означающий, что поиск по данной букве не производится. Сигнал с выхода блока 9 памяти появляется на выходе 15 лишь в случае, если на горизонтальный 12 и вертикальный 8 входы поданы коды букв из соответствующих алфавитов. В противном случае на выходе 15 накопителя постоянно присутствует сигнал логической 1.Накопитель с многомерной выборкой работает следующим образом. 5 1 О 15 20 25 30 35 40 45 50 55 Ь,И 1 к 20 памяти с многомерной выборкой представляет собой квадратный массив запомицаюц 1 их ячеек и имеет столько инфор;1 ационных выходов и входов, сколько з 1 помццак)ших ячеек содержится в ее строке либо столбце. В зависимости от управляю 1 пего сигнала 11 а выходах блока 20 появляется содержимое всей строки либо столбца м ас си па запоминающих ячеек, адрес которых установлен на его адресных входах Триггер 19 управляется сигналами от горизонтального 21 и вертикального 16 входов и служит лля подключения к адресным входам блока 20 памяти посредством мультиплексора 17 сигналов из горизонтального 21 либо вертикального 16 вх 11 дов, а также лля управления направ с.: :,1 борки в зацомицаю 1 цем устройст. ве 20. Селекторы 18 и 22 предназначены для обнаружения кода запрета выборки на гдр 11 зоцт 11 льцом 21 и вертикальном 16 входах соответственно и совместно с элеменго. 1 25 и мультиплексором 23 осушествллкгг цодклк 1 чецие к выходам 24 вьходов блока 20 памяти либо сигналов логической . При этом выходы блока 20 памяти подключены к выходам накопителя лишь в том случае, если или по горизонтальному входу 2, Или по вертикальному входу 16 ш нр,шел код запрета выборки.Л с 11 ц 11 ативное запоминающее устройство работает следую 1 цим образом.Перед началом работы на вхолах 5 блоков 3 усганавливают колы букв, составляюццх 111 исковь 1 Й ключ, при этом каждому блоку 3 соответствует буква в опрелелен. цой 1;сзинин слова. Если поисковый образ це содержит буквы в данной позиции слова, то ца входе 5 соответствующего данной И 1 зпции слова блока 3 устанавливают код запрета. После установления на входах 5 всех Олоков 3 нужных кодов подают управл 1 юший сигнал по входу 6 блока 4 управления, который, в свою очередь, по входам 7 осуцгетвляет загрузку блоков 3 установлецць 1 ми на их входах 5 колами. При этом блоки 3 возбуждают вертикальные и горизонтальные входы, соединенные с их первьмп и вторыми выходами соответственно, кодами, соответствующих букв. В результате этого на выходах накопителей на ос 11 ове запоминающего устройства с одновременной выборкой (фиг. 2), расположенных на пересечениях входов, возбужденных колами букв, появляется содержимое выбранных ячеек памяти, отражающее налицие или отсутствие в ассоциативном запоминающем устройстве отношений, определенных ключом. На выходах накопителей на одну или на обе группы адресных входов которых поступил код запрета, устанавливаются сигналы логической 1. Таким образом. если выходы всех накопителей5 10 находятся в состоянии логической 1, значит слово или слова с заданным поисковым признаком присутствуют в ассоциативном запоминающем устройстве. Проверка этой ситуации осуществляется с помощью бло. ков 2, которые в простейшем случае пред. ставляет собой схемы И. Дальнейший поиск может производиться двумя путями, Если элементы ключа расположены преимущественно в начале слова, блок 4 управления посредством входа 7 выдан в блоки 3 управляющий сигнал, по которому последние начинают просмогр столбцов. При этом каждый блок 3 возбуждает вертикальный вход, соединеннь(й с его первым выходом, кодами различных букв. всякий раз опрашивая при э Г(м вьхо блока 2, входы которого соедине 1;ы с выходами накопителей расположенных в данном столбце. Поскольку часть горизоГгяльных входов уже возбуждена колями сака поискового ключа, часть нако(итслсй. расположенных на пересечении эгх Горизонтальных входов с вертикальным, выдает в блоки 2 информацию о хранимых в 1(их оти 1(ениях для соответствующих со сяний букв. Выходы остальных на к О 11 теле Й на ход 51 тся В сОстОянии лОГической . На вход блока 3 с выхода блока 2 Госгупяст сигнал логической 1 в том липь случае, если все выбранные для установленного кода буквы отношения в столбце не(улсвые. Последовательно возбуждая верти к(1,ь 1 ь 1 и вход кодами различных букв, блок 3 запоминает те коды букв, в Отвс( ня которые из блока 2 поступили сигналы логицеской 1, и по окончании просм(ГГр всех букв устанавливают на вергикя,ьном входе код первый из них. При этом он выдает на вход 7 сигнал об окон 1(н(1 просмотра.11 осле получения от всех блоков 3 сиги,ов Об окончании просмотра блок 4 у(ря ь.".е ия посредством выхода 7 выдает блок,": управляющий сигнал, по которому посдние начиняют просмотр строк. Прос(Отр строк осуществляется так же, как и (рос.огр столбцов. Если его результатом является такая комбинация букв слова, для каждой из которых блок 2 соответствующей строки выдал сигнал логической 1, бло:,; 4 выдает сигнал, извещающий, что первое слово с заданным поисковым ключом найдено и его буквы могут быть считаны с входов 5 блоков 3. После этого, а такжс в слуцяе, сли первый просмотр горизонтяльных шин не дает искомого результата, блок 4 управления посредством входа 7 выдает в блоки 3 управляющий сигнал, по которому последние устанавливают ня своих вертикальных шинах другую комбиняцио кодов букв из числа найденных при первсм просмотре столбцов. После 15 20 25 30 35 40 45 50 55 этого осуществляется второй просмотр горизонтальных шин и т. д.Таким образом, в результате последовательных итераций находятся все слова с заданным поисковым признаком, Сигналом окончания поиска является исчерпание всех комбинаций кодов букв на вертикальных шинах. найденных при первом просмотре.Если элементы ключа расположены преимущественно в конце слова, поиск производят описанным способом, но начинают с просмотра строк. Если в ассоциативном запоминающем устройстве используют накопители с многомерной выборкой, поиск информации производится следующим образом. На входах 5 соответствующих блоков 3 устанавливают либо коды букв ключа, либо коды запрета. Сигнал Пуск подают по входу 6 блока 4 управления, который посредством выходавыдает управляющие сигналы в блоки 3, При этом, если элементы ключа расположены преимущественно в начале слова, блоки 3, на входы 5 которых поданы коды букв, составляющих ключ, возбуждают этими кодами свои горизонтальные входы, вертикальные входы эти же блоки 3 возбуждают кодами запрета. Блоки 3, на входах 5 которых установлены коды запрета, возбуждают этими кодами и горизонтальные и вертикальны входы, соединенные с их первыми и вторыми выходами соответственно. В результате этого на выходах накопителей, содержащих, входящие в поисковый ключ, появляется содержимое выбранных в них строк. Все выходы остальных накопителей находятся в состоянии логической 1. Далее блоки 3 опрашивают выходы блоков 2 о столбцах. Блоки 2, в этом случае, выполняют логические операции И над одноименными выходами всех накопителей столб. ца либо строки, Выход определенного разряда блока 2 находится в состоянии логическойлишь в том случае, если эти же разряды на выходах всех накопителей 1 столбца либо строки одновременно равны единице. В результате опроса выходов блоков 2 блок 3 запоминает коды букв, соответствующих единичным разрядам на выходах первых. При этом блоки 3, обрабатывающие элементы ключа, сравнивают эти коды с кодами букв ключа. Если коды равны для всех позиций букв в ключе, значит слова с данным поисковым признаком имеются в ассоциативном запоминающем устройстве. В этом случае блок 4 управления выдает в блоки 3 управляющий сигнал, по которому последние устанавливают на своих горизонтальных входах коды запрета, на вертикальных входах блоки 3, обрабатывающие элементы ключа, устанавливают коды соответствующихбукв, составляющих ключ, остальные блоки 3 устанавливают на своих вертикальных входах коды букв, найденных при первом просмотре. Далее блоки 3 оп рапп и ва ют выходы блоков 2, расположенных в строках матрицы накопителей. Все возможные комбинации букв, соответс гвующих единичным разрядам на выходах строчных блоков 2, являются словами, выбранными из ассоциативного запоминающего устройст ва для данного ключа, После этого, а также в случае, когда во всех разрядах хотя бы одного строчного блока 2 окажутся записанными нули, блок 4 управления выдает в блоки 3 управляющий сигнал, по которому последние возбуждают свои вертикальные входы другой комбинацией букв, найденных при первом просмотре. Далее по сигналу из блока 4 управления блоки 3 вновь опрапивают выходы строчных блоков 2 и т.д.Таким образом, в результате последовательных операций из ассоциативного запоминающего устройства исключаются все слова с заданным поисковым признаком.Процесс поиска прекращается по исчерпании всех комбинаций букв на вертикальных входах, полученных при первом просмотре, Если элементы ключа расположены преимущественно в конце слова, поиск проводят описанным способом, начиная с просмотра строк.Таким образом, использование в ассо циативном запоминающем устройстве накопителя с многомерной выборкой существенно снижает время поиска.- ая Оукба я букда дунаи 1 У адкаа итель О. ИсаевИ. Верес584 венного комит ретений и от 35, Раушская г. Ужгород, у го ва Редактор И. НиколайчукЗа каз 4620/46 ВНИИПИ по д 113035, Мо лиал ПППСостав Техред Тираж Государс лам изоб ква, Ж - Патент,Корректор ОПодписноета СССРрытийнаб., д. 4/5Проектная,