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

,ЯО 1234 А УБЛИН С 15 0 ГО ОПИСАНИЕ ИЗОБРЕТЕН СВИ ЛЬСТВ АВТОРСКО М 1043750, кл. б 11 С 15/(57) Изобретение относитсяной технике, в частностихранения информации, и можзовано в системах храненияформации, выполненных на у А О лительйствам спольтки инк вычис к уст ро т быть и обрабо лах с б лысой УДАРСТВЕННЫЙ НОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Киевский ордена Ленина политехничский институт им. 50-летия Великой Октябрской социалистической революции(72) Гойял Раджив Кумар (1 М), ГавФадль Хасан (УР), В. И. Корнейчуки А. П. Марковский(56) Авторское свидетельство СССР73729, кл. б 1 С 15/00, 1979,Авторское свидетельство СССРо 00, 1983. степенью интеграции. Цель изобретения - расширение области применения устройства за счет обеспечения поиска слов переменной длины по совокупности признаков и повышение эффективной емкости устройства. Устройство содержит накопитель 1, состояший из ассоциативных ячеек памяти, ре. гистры 2 - 4, 12, 13, 15 и 16, шифратор 7, счетчики 8 и 14, дешифратор 10. При поиске информации в регистр 12 заносятся коды ключей поиска, в регистр 13 записывается маска ключей поиска, в регистр 15 - информация, предназначенная для записи (если производится операция записи по ключу), в регистр 16 - маска информации. В устройстве производится поиск слов по произвольному количеству произвольно расположенных ключей, чтение или запись произвольной области найденного слова, причем начало слова может располагаться в произвольном порядке, так что накопитель 1 заполняется информацией полностью. 2 ил.1234880 На фиг. 1 представлена структурнаясхема ассоциативного запоминающего устройства; на фиг. 2 - структурная схемаблока управления.Устройство содержит (фиг. 1) накопитель 1, выполненный из ассоциативныхячеек памяти, регистр 2 опроса, регистр 3маски, регистр 4 слова, элементы И 5 ь 5(гп - число ассоциативных ячеек памятинакопителя 1), регистр 6 адреса, шифратор 207, первый счетчик 8, блок 9 сравнения,дешифратор 10, элемент ИЛИ 11, первый12 и второй 13 регистры числа, второй счетчик 14, третий 15 и четвертый 16 регистрычисла, блок 17 управления, имеющий входы18 - 20, выходы 21 - 32, входы 33 - 35, выходы 36 - 38,Блок 17 управления (фиг. 2) содержит логические элементы 39 - 69, в том числеэлементы 39, 41, 43, 48, 52, 57, 60, 61 задержки,элементы ИЛИ 40, 42, 47, 53, 56, 62, 65, 66,ОБЪЕКТ - КПИАДРЕСКИЕВЧИСЛОСТУДЕНТОВ 1200 ОБЪЕКТ - КПИ ЧИ СЛОСТУДЕНТОВ 111111111100000000111111111111110000 1257 00000000000000000000000000000000111пает на управляющий вход накопителя 1, происходит ассоциативный опрос накопителя 1, на управляющих выходах которого формируктся сигналы единичного уровня, 4 соответствующие совпадению незамаскированных разрядов ячейки с незамаскированными разрядами регистра 2. В случае, если хотя бы на одном из выходов будет сформирован сигнал единичного уровня, что соот.ветствует наличию в накопителе 1 хотя бы одного слова, начало которого совпадает с началом поля ключей искомого слова, то на выходе элемента ИЛИ 11 будет сформирован сигнал единичного уровня, которым откроется элемент И 46 и сигнал через открытый элемент И 51 поступит на выход 26 блока 17. По этому сигналу в регистре 6 записью единицы в соответствующих разрядах зафиксируются ячейки, содержимое которых Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано в системах хранения и обработки информации, выполненных на узлах с большой степенью интеграции.Цель изобретения - расширение области применения устройства за счет обеспечения поиска слов переменной длины по совокупности признаков и повышение эффективной емкости устройства. необходимо число 1200 заменить на 1257, то На входы 19 и 20 блока 17 подаются единичные сигналы соответственно в случае записи информации по ключу или считывания информации по ключу.По сигналу начала работы, подаваемому на вход 18 блока 17, счетчик 8 устанавливается в нуль, а все разряды регистра 6 - в единицу, триггер 70 и счетчик 71 устанавливаются в нуль. Далее сигнал через элемент 39 задержки и элемент ИЛИ 40, 60 и выход 27 блока 17 управления поступает на управляющие входы регистров 2, 3, 12, 13 и вход счетчика 14; часть разрядов регистра 12 к символов поступает на регистр 2 (к - число групп разрядов, содержащихся в ячейке накопителя 1) и к разрядов с второго регистра 13 - на регистр 3.Сигнал через элемент 41 задержки, элемент ИЛИ 42 и выход 22 блока 17 постуэлементы И 44- - 46, 49 - 51, 54, 55, 58, 59, 63, 64, элементы НЕ 67 - 69.Устройство также содержит триггер 70, счетчик 71 сдвигов и элемент ИЛИ 72. Все блоки предлагаемого устройства могут быть выполнены в виде интегральных микросхем (одной или нескольких) с большой степенью интеграции или на серийно выпускаемых микросхемах малой и средней степени интеграции.Устройство работает следующим образом.В исходном состоянии в ячейках памяти накопителя 1 записаны информационные слова произвольной длины и соответствующие им коды. Структура записи информации в накопителе 1 следующая: код символов информационного слова записывается в ячейку с любого ее разряда; если слово не помещается в одной ячейке, то его продолжение располагается в следующей ячейке; если недостаточно двух ячеек, используется три, четыре и больше ячеек.При поиске информации на регистры 12, 13, 15, 16 записывается следующая информация: на регистр 12 заносятся коды ключей поиска (в общем случае их может быть неосколько); на регистр 13 - маска ключей поиска; на регистр 15 - информация, предназначенная для записи (если производится операция записи информации в накопитель 1 по ключу); на регистр 16 - маска информации. Например, если в информационном слове: в регистры 12, 13, 15 и 16 соответственнозаносятся коды:совпадает с полем ключей, если такая ячейка одна, то через шифратор 7 номер ее записывается на счетчик 8 (если более чем одна, то записи не происходит). Сигналом с выхода элемента 52 задержки триггер 70 устанавливается в единичное состояние, а сам сигнал через элементы ИЛИ 53, И 55, ИЛИ 40, ИЛИ 66, выход 27 блока 17 поступает на регистры 2, 3, 12, 13, вызывая сдвиг их содержимого на к разрядов, при этом на регистре 2 оказываются следующие к разрядов ключа, а на регистре 3 - следующие к разрядов маски ключа. Сигналом, задержанным элементом 41 задержки, снимаемым с выхода элемента ИЛИ 42 через выход 22 блока 1, накопитель 1 опрашивается на наличие ячейки, содержимое которой в незамаскированных разрядах совпадает с содержимым части ключевой информации, находящейся в регистре 2: в случае совпадения с соответствующих управляющих выходов накопителя 1 снимаются сигналы единичного уровня, а на выходах элементов И 5 единичные сигналы формируются лишь в том случае, если найденная ячейка следует за ячейкой, отмеченной в предыдущем цикле поиска, т. е. если находится слово в накопителе 1, первая и вторая часть ключевого поля которого совпадает с заданным ключом. Если такие слова есть и на выходе хотя бы одного из элементов И 5 формируется сигнал единичного уровня, то вновь снимается сигнал с выхода элемента ИЛИ 11 и устройство работает аналогично, сравнивая третью, четвертую и так далее части ключевого поля. Конец поисковой процедуры определится, когда будет проанализировано все поле ключей и счетчик 14, содержимое которого увеличивается на к всякий раз при сдвиге информации на к разрядов в регистрах 2, 3, 12, 13, выдаст сигнал переполнения, который, пройдя через вход 35 блока 17, откроет элемент И 54 и закроет элемент И 5, прекратив тем самым опрос накопителя 1.Если на одном из циклов поиска на выходах элементов И 5 не бедут сформировано ни одного сигнала, то нулевым сигналом с выхода элемента ИЛИ 11 закроется элемент И 46. Если триггер 70 при этом находился в нулевом состоянии (соответствует первому циклу работы устройства), то сигнал через открытый элемент И 44 поступает на счетный вход счетчика 71, на вход установки в единицу регистра 6 и на вход управления вправо на один разряд содержимого регистров 2, 3, 12, 13, 15, 16. Этим же сигналом, прошедшим через элемент ИЛИ 42, выдается сигнал опроса на ячейки накопителя 1, при этом единичные сигналы будут сформированы на тех управляющих выходах, в соответствующих ячейках кооторых записана информация, совпадающая незамаскированными разрядами с (к - 1) -ми разрядами ключевого поля, сдвинутыми на раз 5 10 15 20 25 30 35 40 45 50 55 ряд вправо (соответствует тому случаю, если искомое слово записано, начиная с второго разряда). Если такое слово (или слова) будет найдено, то с выхода элемента ИЛИ 11 формируется сигнал единичного уровня и устройство функционирует по описанному способу. Если в момент выдачи нулевого сигнала с выхода элемента ИЛИ 11 триггер 70 находился в единичном положении (соответствует работе устройства на втором и дальнейших циклах), то открывается элемент И 45, на выходе которого формируется сигнал единичного уровня, который, пройдя через элемент ИЛИ 47, поступает далее на управляющие входы регистров 2, 3, 12, 14, вызывая сдвиг вправо на к разрядов. Эта операция повторяется до тех пор, пока блок 9 не выдаст сигнал равенства (соответствует возврату информации в регистрах 2, 12, 3, 13 в исходное состояние перед установкой триггера 70 в единицу).По сигналу равенства, подаваемому на вход 33 блока 17, открывается элемент И 49, триггер 70 устанавливается в нуль и начинается повторное выполнение первого цикла, при этом ключ в регистре 2 оказывается сдвинутым на разряд вправо. Если счетчик 71 при этом выдаст сигнал переполнения по выходу 30, это означает, что искомой информации нет в накопителе 1. В противном случае, будет выдан сигнал с выхода элемента И 54 (в этот момент будет найдено искомое слово, причем адрес его начала хранится на счетчике 8, а информация в регистрах 15 и 16 сдвинута влево на то же число разрядов, что и начало найденного слова относительно начала ячейки). По сигналу с выхода элемента И 54 происходит перепись информации из регистра 15 на регистр 12 и из регистра 1 6 на регистр 13,этим же сигналом через элемент И 56 производится считывание ячейки накопителя 1, в которой хранится начало найденного слова, на регистр слова 4. В режиме чтения (соответствует единичному .сигналу на входе 19 блока 17) открытым оказывается элемент И 58, сигналом с выхода которого информация из регистра 4 переписывается на регистр 2, причем переписываются только разряды, отмеченные единицами в регистре 3, затем сигналом с выхода элемента И 64 содержимое счетчика 8 увеличивается на к разрядов. Операция повторяется до тех пор, пока счетчик 14 не выдаст сигнал переполнения, которым откроется элемент И 63, сигнал с выхода которого является сигналом конца операции. При записи информации (соответствует единичному сигналу на входе 20 блока 1) единичным сигналом с выхода элемента И 59 информация из регистра признака 2 переписывается на регистр 4, причем аереписываются только разряды, отмеченные единицами в регистре 3. Затем сигналом, задержанным элементом1234880 Формула изобретения Рис, у 61 задержки, содержимое регистра 4 записывается в накопитель 1, В остальном устройство при записи работает так, как и в режиме чтения.После окончания работы устройства в режиме чтения на регистре 12 зафиксирован код считанной информации. Ассоциативное запоминающее устройство, содержащее накопитель, регистр слова, регистр маски, регистр адреса, элементы И, шифратор, регистр опроса, регистры числа, с первого по третий, и блок управления, причем управляющие выходы накопителя подключены к первым входам элементов И, выходы которых соединены с входами регистра адреса, выходы которого подключены к вторым входам элементов И, информационный выход регистра опроса и выход регист ра маски подключены к одним из управляющих входов накопителя, информационные вход и выход которого соединены соответственно с информационным выходом и входом регистра слова, один из выходов переполнения первого регистра числа соединен25 с одним из выходов заполнения регистра опроса, другие управляющие входы накопителя, одни из управляющих входов регистра адреса, регистра опроса, регистра слова и первого и второго регистров числа и управляющие входы регистра маски и третьего регистра числа подключены к соотвстствуюгцим выходам блока управления, отличаюиееся тем, что, с целью расширения области применения устройства за счет обеспечения поиска слов переменной длины по совокупности признаков и повышения эффективной емкости устройства, в него введены дешифратор, первый и второй счетчики, блок сравнения, четвертый регистр числа и элемент ИЛИ, входы которого подключены к выходам элементов И, выходы регистра адреса соединены с входами шифратора, выход которого подключен к первому входу блока сравнения и одному из входов первого счетчика, выход которого соединен с вторым входом блока сравнения и входом дешифратора, выходы которого соединены с адресными входами накопителя, другие выходы переполнения первого регистра числа соединены с другими входами заполнения регистра опроса, выходы переполнения и заполнения регистра маски соединены с соответствующими входами заполнения и переполнения второго регистра числа, выход регис-тра маски подключен к входам управления разрядной записью регистра опроса и регистра слова, которые поразрядно соединены между собой, информационные выходы третьего и четвертого регистров числа подключены соответственно к информационным входам первого и второго регистров числа, другие входы первого счетчика, дру. гие управляющие входы регистра адреса, регистра опроса, регистра слова и первого и второго регистров числа, управляющий вход четвертого регистра числа и входы второго счетчика подключены к соответствующим выходам блока управления, одни из входов которого соединены с выходами блока сравнения, элемента ИЛИ и второго счетчика, а другие входы являются управляющими входами устройства.удак Кор рек Подпи ССРорЕ.Рое тета С крытий И Госуда делам и Москва, Ж П Патент 4/ б Пр ктн Составитель В.Техред И. ВересТираж 543рственного комиобретений и от- 35, Раушская