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

(19) 111) А 1 С 150 5) ИСАНИЕ ИЗОБРОРСКОМУ СВИДЕТЕЛЬСТ ах ез ьд)о ти хране ь тельство 15/00,льство С 15/00,АПОИИНАЮЩЕносу ычисл сится к ет быть спо ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОЩРЫТИЯМПРИ ГННТ СССР(57) Изобретение отнтельной технике и мож СССР1984.СР1987.Е зовано в ассоциативныхустройствах распознавансигналов. Цель изобретение быстродействия устрройство содержит блокислужащие соответственно роцессо я- син ния - по йства. и 2 памния ключевои и искомых последова костей, компаратор 3, счетчики 4 регистры 6 и , блок управления В устройстве реализован алгоритм который позволяет при первом же сравнении элементов последователь тей переходить к следукицему цикл поиска. 3 ил.4 4ти В;, записан элемент й; являющийся адресом перехода к аналогичной ячейке для последовательности В1-1Кроме. того, по нулевому адресу блока 2 записан элемент й, являющийся адресом перехода к элементу Йпоследовательности В, а по максимальному адресу блока 2 записан элемент с, содержимое которого произвольно.В признаковой части блока 2 элементы последовательностей А ( - "1,Я) снабжены признаком А, элементы последовательностей В;(1 = 1,М) - признаком В, элементы с ( = 1, , И) - признаком С, эле 1менты й( = 1, , И) - признаком 0.Адресное пространство блока 2 между элементами Йи с не используется и может содержать произвольную информацию (х).Устройство работает в двух режимах: прямом (поиск по признаку А;) и обратном (поиск по признаку В).На первом этапе производится запись ключевой последовательности в блок 1. Процесс записи в обоих режимах абсолютно одинаков и проводится по единому алгоритму (фиг. За),Элементы ключевой последовательности поступают на информационные входы устройства в соответствии с тактовыми импульсами СИ", поступающими на вход Х 1 блока 8, Тактовые импульсы синхронизируют работу устройства и состоят из двух полутактов: первый имеет уровень "1", второй "0". ь %А 1 = ау а э э а 1 у1, 2, ; с 1 щЧа 1,а в инверсном Режиме - ключевая по- . 40 следовательность видаВ,:Ь,Ь, , Ь,1;В блоке 2 записаны последовательности45 за каждой из которых следует последовательностьВ; Ь, Ь;, , Ь; р 50 3 15011 бИзобретение относится к вычислительной технике и может быть исполь" зовано в ассоциативных процессорах, устройствах распознавания - синтеза сигналов.Цель изобретения - повышение быстродействия устройства.На фиг. 1.изображена структурная схема ассоциативного запоминающего устройства (АЗУ); на Фиг. 2 - разме" щение информации в первом и втором блоках памяти; на фиг. 3 - алгоритм работы устройства.Устройство содержит (см.фиг.1) первый 1 и второй 2 блоки памяти, ,компаратор 3, первый 4 и второй 5 счетчики, первый 6 и второй 7 регистры и блок 8 управления, выполненный, например, в виде программируемой 20 логической матрицы.На фиг, 1 приняты также следующие обозначения: Х 1 - Х 10 - входы блока 8, 71-718 - выходы блока 8.Принцип работы устройства заклю чается в следующем.В процессе записи в блок 1 заносится ключевая последовательность в порядке поступления элементов, считывание этой последовательности ЗО в режиме сравнения производится в обратном порядке, т.е. по принципу "последний пришел - первым ушел" (фиг. 2).В прямом режиме в блок 1 записывается ключевая последовательность виПричем в ячейке, находящейся перед первым элементом а последовательности А;, записан элемент с;, являющийся адресом перехода к аналогичной ячейке для последовательности А . , а в ячейке следующей за послед+ 1ним элементомЬ;, последовательносПроцесс записи инициируется подачей сигнала "Запись" (" 1" уровень) на вход Х 2 блока 8, В первом такте по первому полутакту блок 8 вырабатывается на своем выходе Уб импульс, который сбрасывает счетчики 4 и 5 в состояние "0", а по второму полу- такту - на выходе У 1 блок 8 вырабатывает импульс, по которому имеющаяся на входах устройства информация (первый элемент ключевой последовательности) записывается по адресу "О" в блок 1. В последующих тактах блок 8 вырабатывает по первому полу- такту импульс на выходе УЗ, по которому содержимое счетчика 4 увеличивается на единицу, а по второму - импульс на выходе У 1, по которому следующий элемент ключевой последовательности записывается в следующую ячейку блока 1.30 515011Таким образом, производится записьэлементов ключевой последовательности в блок 1, который завершается записью последнего элемента и снятиемсигнала "Запись" (0" уровень) с входа Х 2 блока 8,На втором этапе проводится сравнение ключевой последовательности,записанной в блок 1, с последовательностями, находящимися в блоке 2.Процесс сравнения инициируетсяподачей сигнала "Сравнение" ("1" уровень)на вход ХЗ блока 8.Рассмотрим в качестве примера 15процесс сравнения в прямом режиме(фиг. Зб) .В блоке 1 в процессе записи запи-.сана ключевая последовательностьА = а , а; , , а,20Исходйое значение счетчика 4 равно о(устанавливается в процессезаписи), а счетчика 5 - 0 (устанавливается в начале процесса записи, путем сброса). Сигнал "Сравнение" переводит блоки 1 и 2 в режим чтенияпутем выработки блоком 8 соответствующих потенциалов на выходах У 2 иУ 18.Перед тем, как начать сравнениеэлементов последовательностей, производится предварительная установка,В первом полутакте подаются импульсы с выходом У 7 и У 12 блока 8соответственно на вход регистра 6и выхоц счетчика 5, в результатечего в регистре 6 запоминается адрес,элемента а; ключевой последователь 1 с,ности А, который используется передначалом каждого очередного цикла 40сравнения для восстановления исходного значения счетчика 4, а счетчик 5 указывает на первую ячейку блока 2, в которой находится элемент С (признакС), являющийся адресом перехода на 45следующую последовательность. Вовтором полутакте этот адрес записывается в регистр 7, для этого с выхода У 10 блока 8 на вход регистра 7подается импульс. 50Сравнение элементов ключевой последовательности с элементами последовательностей блока 2 происходитследующим образом.При сравнении первых элементов по Вследовательностей, начинающемся вследующем такте после считывания признака С с блока 2, в 1-ом полутактеочередного такта на вход счетчика 5 64 бс выхода У 10 олока 8 поступает импульс, вызывая адресацию очередной ячейки блока 2, с которой считывается ц-ый элемент а последовательности А. С блока Ч перед началом сравнения также считывается о-ый элемент а ключевой последовательности А. Во втором полутакте этого такта на вход компаратора 3 с выхода У 9 блока 8 подается импульс сравнения и элемент ключевой последовательности и элемент с признаком А последовательности блока 2 сравниваются в компараторе 3. В случае совпадения сравниваемьк элементов с выхода компаратора 3 поступает уровень "О"При сравнении последующих элементов в первом полутакте очередного такта с выходов У 10 и УЗ блока 8 соответственно на суммирующий вход счетчика 5 и вычитающий вход счетчи-. ка 4 поступают импульсы счета. С блоков 1 и 2 при этом считываются очередные элементы сравниваемых последовательностей, Во втором полутакте на вход компаратора 3 с выхода У 7 блока 8 поступает импульс сравнения и с его выхода в случае совпадения элементов поступает сигнал уровня "0"Процесс сравнения последовательностей завершается при сравнении очередных элементов последовательностей, когда произошло несовпадение элементов последовательностей, при этом на выходе обратного переноса счетчика 4 появился сигнал при отсутствии признака В на выходе блока 2; эта ситуация соответствует случаю, когда при совпадении всех элементов сравниваемых последовательностей ключевая последовательность "короче" последовательности блока 2; на выходе блока 2 появился признак В при отсутствии сигнала на выходе обратного переноса счетчика 4; эта ситуация соответствует случаю, когда при совпадении всех элементов сравниваемых последовательностей, последовательность блока 2 "короче" ключевой.Если в некотором цикле сравнения совпали все элементы сравниваемых последовательностей и в следующем такте появился сигнал с выхода обратного переноса счетчика 4, а с блока 2 считывается признак В, то мы имеемтот случай, когда произошло совпадение ключевой последовательности содной из последовательностей, записанных в блоке 2, При этом сигналво втором полутакте вырабатываетсясигнал "Вывод" с выхода У 15 блока 8,свидетельствующий о наличии на информационных выходах устройства элемента искомой последовательности, вданном случае первого элемента Ь по 1следовательности В , Производитсясчитывание искомой последовательности В, и продолжается до тех пор, пока после очередного пересчета счетчика 5 с блока 2 на входы Х 9 и Х 10блока 8 подступит признак В, По этому признаку во втором полутакте с выхода У 1 б на выход устройства поступит сигнал "ПрЕ", сигнализирующий о 20завершении процесса сравнения и вывода искомой последовательности.Возможна также ситуация, когда ниодна из последовательностей, записанных в блоке 2 не совпадает с ключевой последовательностью, записаннойв блоке 1, В этом случае при сравнеМнии ключевой последовательности Ас последней последовательностью Аиз блока 2 возникает одна из трех З 0ситуаций несовпадения. После обработки этой ситуации с выхода У 17 блока8 на выходе устройства появляетсясигнал "ПрЕ" о том, что в процессепросмотра всего массива информации,записанной в блоке 2 искомая последовательность не обнаружена,Процесс сравнения в инверсномрежкке аналогичен процессу сравнения в прямом (фиг. За, в). При этомв блок 1 в результате записи вводится ключевая последовательность В,ФЬ Ь еЬ1Формула изобретения Ассоциативное запоминающее устройство, содержащее первый и второй блоки памяти, компаратор, первый и второй, счетчики и блок управления, причем адресные входы первого и второго блоков памяти подключены соответственно к информационным выходам первого и второго счетчиков, информационные входы первого блока памяти являются входами признака поиска устройства, информационные выходы первого блока памяти и информационные выходы первой группы второго блока памяти соединены соответственно с информационными входами первойи второй групп компаратора, синхронизирующий вход, входы разрешениязаписи и сравнения и вход заданиярежима посика блока управления являются одноименными входами устройства, вход результата сравнения блока управления подключен к выходукомпаратора, первый и второй выходыблока управления подключены соответственно к входам записи и чтения первого блока памяти, третий, четвертыйи пятый выходы блока управления соединены соответственно с суммирующтм,вычитающим входами и входом разрешения приема первого счетчика, шестойвыход блока управления подключенк входам сброса первого и второгосчетчиков, седьмой выход блока управления соединен с управляющим входомкомпаратора, восьмой, девятый и десятый выходы блока управления подключены соответственно к суммирующему,вычитающему входам и входу разрешения приема второго счетчика, одиннадцатый выход блока управления подключен к входу чтения второго блока памяти, информационные выходы первойгруппы второго блока памяти являютсяинформационными выходами устройства,отличающее ся тем,что,с целью повышения быстродействия устройства, оно содержит первый и второй регистры, выходы которых подключены соответственно к информационным входам первого и второго счетчиков, информационные входы первогорегистра соединены с информационными выходами первого счетчика, выходобратного переноса которого подкгво-чен к первому установочному входублока управления, входы разрешениязаписи и чтения первого регистра подключены соответственно к двенадцатому и тринадцатому выходам блока управления, информационные входы второго регистра соединены с информационными выходами первой группы второгоблока памяти, информационные выходывторой группы которого подключенык признаковым входам блока управления, входы разрешения записи и чтения второго регистра соединены соответственно с четырнадцатым и пятнадцатым выходами блока управления, выходы прямого и обратного переносавторого счетчика соединены соответственно с вторым и третьим установочными входами блока управления, шестнадцатью, семнадцатый и восемнадцатый выходы блока управления являются соответственно выходами "Начало вы=вода данных 1, "Завершение выводаданных и "Результат поиска отрицательный" устройства,1501164 ставитель Б. Рудакахред Л.Олийнык ктор Н. Коро рМ.Н Ре нко Производственно-издательский комбинат "Патент", г. Ужгород Гагарина, 101 аказ 4878/50 Тираж 558 ПодписноеНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб., д. 4/5