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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 80150 51 4 С 11 С 15/О ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ ВТОРС ВИДЕТЕЛЬСТпоис- нящихР 143 (54) УСТРО (57)тельн к в к вычисли йти примее относи и может ьно СФ 4247987/2 25,05.87 15.08.89. Г.П. Токм Ивыдков и 681.327(0 Авторское 3036, кл, торское с 2608, кл. АССОЦИАТ ЙСТВО Изобретен ой техник нение при распознавании ч син сигналов, в частности речевых томатизированных словарях для да с одного языка на другой и но, в справочных системах для ка инФормации и т.п. Цель изо ния - расширение области прим устройства за счет обеспечения ка по любому слову из двух хр ся в устройстве массивов. Пос ющая на вход устройства призн последовательность записывает блок 1 памяти. В компараторе водится сравнение последовател3 15011634тей, считываемых с блоков 1 и 2 па- из блока 3 в соответствии с режимом мяти, по поступлению импульсов срав- работы устройства. Устройство также нения. Выработку импульсов сравне- содержит счетчик 3, элемент И 6, ния элементом И 10 и разрешающего 5 элемент ИЛИ 11, группу элементов И сигнала элементом И 9 обеспечивают 14Изобретение обеспечивает сравнетриггеры 7 и 8. Триггер 7 идентифи- ние признаковой последовательности, цирует последовательности, считыва- поступившей на вход устройства, с емые с блока 2, т,еразграничивает последовательностями как из первого, признаковую и информационную последо так и из второго массивов, хранящихвательности, а триггер 8 фиксирует ся в блоке 2 памяти, и соответственрезультат сравнения. Реверсивный .но поиск искомой последовательности счетчик 4 и элементы И 12, 13 управ- как во втором, так и в первом массиляют порядком считывания информации вах, 3 ил.35 Изобретение относится к вычислительной технике, а именно к ассоциативным запоминающим устройствам (АЗУ), и может быть использовано для распознаваний и синтеза сигналов.25Цель изобретения - расширение области применения устройства за счет обеспечения. поиска по любому слову из двух хранящихся в устройстве массивов.30На фиг. 1 изображена структурная схема ассоциативного запоминающего устройства; на фиг,. 2 - размещение информации з первом и втором блоках памяти; на фиг. 3 - временные диаграммы работы устройства.Устройство (смйфиг. 1) содержит первый 1 и второй 2 блоки памяти, к адресным входам которых подключены счетчик 3 и реверсивный счетчик 4 соответственно.В блок 1 памяти записывается признаковая последовательность А,(а а , , а ) или В; = (Ь, Ь , в Ь 5) В СООтВЕтСтВИИ С рЕжк 45 мом работы устройства, где р и о переменные величины, поичем элементы последовательности записываются в блок 1 в обратном порядке, т,е. с последнего элемента а или Ь до первого а, или Ъ (см.фиг. 2 а, б),50 причем= .1,М, где М - целое.1В блоке 2 хранится два массива последовательностей А =А , Ам 1 ф 55 элементу А массива А соответствует определенная последовательность В массива В и наоборот, каждому элемеи ту В, массива В соответствует элемент А; массива А. Таким образом,структура данных в блоке 2 имеетвип АВ =1 А,В Аан причем нандийэлемент А; и В; этои структуры заканчивается кодом конца последовательности,Элементы последовательностей Аи В в блоке 2 размещаются следуЪющим образом: в последовательностяхВ с возрастанием адреса ячеек памяти увеличивается и порядковый номерэлементов последовательности, содержащихся в этих ячейках, в последовательностях А 1 наоборот - с возрастанием адреса уменьшается порядковыйномер элементов последовательности(см фиг 2 в)Сравнение признаковой последовательности А или В записанной в бло ке 1, с последовательностями массива А или В , хранящимися в блоке 2, происходит в компараторе 5.оДля .определения результатов сравнения последовательностей служит первый элемент И 6, выходом подключенный к тактовому входу первого триггера 7, который прямым выходом подключен к тактовому входу второго триггера 8 и к входу второго элемента И 9, а инверсным выходом - к входу третьего элемента И 10, выход которой подключен к управляющему входу компаратора 5, выход которого подключен к одному из входов элемен"та ИЛИ 11.Для организации работы счетчика 4в двух режимах служат четвертый 12и пятый 13 элементы И.15011 45 Искомая информация считываетсячерез группу элементов И 14, подключенных к выходам блока 2.Устройство работает в двух режи 5мах, которые задаются подачей соответствующего потенциального сигнала"Режим" на вход устройства: релком 1 поиск по признаку А; режим 2 - поискпо признаку В. 10При включении устройства в рабо 1 тусчетчик 3 сбрасывается.На первом этапе проводится записьпризнаковой последовательности вблок 1. На устройство подается сигнал "Запись", которыи устанавливаетблок 1 в режим записи, сбрасываетсчетчик 4, устанавливает триггер 7в "единичное" состояние "1", а триггер 8 через элемент ИЛИ 11 - в "0", 20Запись элементов признаковой последовательности осуществляется в порядкепоступления импульсов Счет". Циклзаписи заканчивается записью в блоккода конца последовательности (фиг,За).5На втором этапе проводится сравнение признаковой последовательности,записанной в блоке 1, с последовательностями, содержащимися в блоке 2,Допустим, что в результате проведения цикла записи в блок 1 записанапризнаковая последовательность А.На этапе сравнения на устройствоподается сигнал иЧтение", которыйустанавливает блоки 1 и 2 в режимсчитывания информации и разрешает прохождение импульсов "Счет" на счетный вход "+1" счетчика 4. Считывание элементов последовательностей с блоков 1 и 2 производится синхронно по поступлению импульсов "Счет" на счетные входы счетчиков 3 и 4.Исходное состояние устройства на этапе сравнения следующее: счетчик 4 сброшен и с блока 2 считывается содержимое "нулевой" ячейки, которая не используется под хранение элементов последовательностей (фиг, 2 в), триггеры 7 и 8 находятся в "1" и "0" состояниях соответственно, что запрещает выработку импульсов сравнения элементом И 10 и подачу их на компаратор 5, Такое состояние устройства сохраняется до тех пор, пока с блока 2 не считывается код конца последовательности, в результате чего срабаты,вает элемент И 6, что вызывает сброс , счетчика 3 и переключение триггера 63.67 в состояние "О", что в свою очередь переключает триггер 8 в состояние " 1" (фиг . Зб) .В результате имеем следующее состояние устройства: счетчик 3 установлен на "нулевую" ячейку блока 1, где записан последний элемент аР признаковой последовательности А(фиг,2 а), счетчик 4 указывает на ячейку блока 2, где хранится последний элемент последовательности А (см. фиг. 2 в), триггеры 7 и 8 находятся в "0" и "1" состояниях соответственно, что обеспечивает выработку импульсов сравнения элементом И 10 для компаратора 5 и запрещение выработки разрешающего сигнала элементом И 9 на вывод информации из устройства. Следовательно, сначала сравниваются последовательности А, с блока 1 и Аь с блока 2.Сравнение последовательностей проводится по поступлению импульсов с выхода элемента И 10, которые поступают в соответствии с импульсами Счет нри условии, что триггеры 7 и 8 находятся в "0" и "1" состояниях соответственно. Компаратор 5 срабатывает по несовпадению, что вызывает установку триггера 8 через элемент ИЛИ 11 в состояние "0, что в свою очередь ведет к прекращению подачи импульсов сравнения на компаратор 5.Таким образом, если в ходе сравнения последовательностей А и Апроизошло несовпадение, дальнейшее сравнение считываемых слов прекращается. При считывании кода конца последовательности А с блока 2 сра-. батывает элемент И 6, что вызывает сброс счетчика 3 и переключение триггера 7 в состояние "1" (фиг.Зв). Считываемая с блока 2 информационная последовательность В в дачном случае на выход устройства не поступает, так как нет разрешающего сигнала на входах элементов И 14. Считываемый код конца последовательности вызывает срабатывание элемента И 6, что приводит к сбросу счетчика 3 и переключению триггера 7 в состояние 0, что в свою очередь приводит к переключению триггера 8 в состояние "1" (фиг, Зг). Таким образом, счетчик 3 указывает на "нулевую ячейку блока 1, содержащую последний элемент а признаковой последователь 1501163вой последовательности А , записанной в блоке 1, с последовательностями массива А, хранимого в блоке 2,и вывод искомой последовательностиВь заканчивается. 30 Предлагаемое устройство обеспечивает сравнение признаковых последовательностей произвольной длины с последовательностями из первого или второго массивов, хранящихся в устройстве, и в случае совпадения, вывод соответствующей последовательности из второго или первого массивов соответственно. 35 40 Формула изобретения Ассоциативное запоминающее устройство, содержащее первый блок памяти, компаратор, второй блок памяти, группу элементов И, счетчик, первый и второй триггеры, с первого по третий элементы И, элемент ИЛИ, причем50 информационные входы первого блока памяти являются признаковыми входами устройства, вход признака записи первого блока памяти является входом записи устройства, входы признака чтения первого и второго блоков па 55 мяти объединены и являются входом / чтения устройства, адресные входы первого блока памяти подключены к ности А;, счетчик 4 - на ячейку блока 2, содержащую последний элемент последовательности А , а элемент И 10 находится в состоянии, пропускающем импульсы сравнения на компаратор 6, и описанный процесс повторяется.После некоторого количества повторений таких процедур сравнения 10 счетчик 4 указывает на ячейку блока 2, содержащую последний элемент последовательности А;.В этом случае производится сравнение.одинаковых последовательностей и компаратор 5 не вырабатывает сигнала несовпаденийследовательно, триггер 8 остается в состоянии "1", а триггер 7 по коду конца последовательности А переключается в состо яние "1" (фиг. Зд), что вызывает выдачу разрешающего сигнала на элементы И 14 и искомая информационная последовательность В; поступает на выходы устройства (фиг,Зе). 25На этом этапе сравнения признаковыходам разрядов счетчика, счетныйвход которого является тактовым входом устройства, выходы первого блока памяти соединены с входами первой группы компаратора, выходы второго блока памяти, первые входы элементов И группы и входы первого элемента И соединены с входами второйгруппы компаратора, с входами второйгруппы компаратора, выходы элементовИ группы являются информационными выходами устройства, управляющий входкомпаратора соединен с выходом третьего элемента И, первый и второй входыкоторого соединены соответственнос тактовым входом устройства и инверсным выходом первого триггера,прямой выход которого подключен квходу синхронизации второго триггера и первому входу второго элемента.И выход которого соединен с вторымивходами элементов И группы, выходвторого триггера соединен с вторымвходом второго элемента И и входомтретьего элемента И, выход первогоэлемента И соединен с входом синхронизации первого триггера, о т л ич а ю щ е е с ятем, что, с цельюрасширения области применения устройства за счет обеспечения поискапо любому слову из двух хранящихсяв устройстве массиве, в него введены реверсивный счетчик и четвертыйи пятый элементы И, причем выходыразрядов реверсивного счетчика подключены к адресным входам второгоблока памяти, входы сложения и вычитания реверсивного счетчика подключены соответственно к выходам четвертого и пятого элементов И, пер- .вые входы которых соединены с входомчтения устройства, вторые входы четвертого и пятого элементов И соединены с тактовым входом устройства,третьим входы четвертого и пятогоэлементов И объединены и являютсявходом задания режима устройства,выход первого элемента И подключенк установочному входу счетчика, первый и второй входы элемента ИЛИ подключены соответственно к выходу компаратора и входу записи устройства,выход элемента ИЛИ соединен с входомустановки в "0",второго триггера,установочный вход реверсивного счетчика и вход установки в "1" первоготриггера подключены к входу записиустройства,1501163 Коо конца пои Оооатольиостц МОИ ььет ЗеаКь Ы ение х.ьг хьЗ Ьх.1 Выл.2 Вых.7 Вых,7 Выл Ю Вых.Б Выл.Ю Выл.Е Выл,З Вых.19