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

 

Изобретение относится к вычислительной технике и может найти применение при распознавании и синтезе сигналов , в частности, речевых, в автоматизированных словарях для перевода с одного языка на другой и обратно, в справочных системах для поиска информации и т.п. Цель изобретения - расширение области применения устройства за счет обеспечения поиска по любому слову из двух хранящихся в устройстве массивов. Поступающая на вход устройства признаковая последовательность записывается в блок 1 памяти. В компараторе 5 проводится сравнение последовательностей, считываемых с блоков 1 и 2 памяти, по поступлении импульсов сравнения. Выработку импульсов сравнения элементом И 10 и разрешающего сигнала элементом 9 Обеспечивают триггеры 7 и 8. Триггер 7 идентифицирует последовательности, считываемые с блока 2, т.е. разграничивает признаковую и информационную последовательности, а триггер 8 фиксирует результат сравнения. Реверсивный счетчик 4 и элементы И 12, 13 управляют порядком считывания информации из блока 3 в соответствии с режимом работы устройства. Устройство также содержит счетчки 3, элемент И 6, элемент ИЛИ 11, группу элементов И 14. Изобретение обеспечивает сравнение признаковой последовательности, поступившей на вход устройства, с последовательностями как из первого, так и из второго массивов, хранящихся в блоке 2 памяти, и соответственно поиск искомой последовательности как во втором, так и в первом массивах. 3 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (ду 4 G 11 С 15/00

И1Е...

Г. ; Б, Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ

2 нение при распознавании ч синтезе сигналов, в частности речевых, в авЪ томатизированных словарях для перевода с одного языка на другой и обратно, в справочных системах для поиска информации и т.п. Цель изобретения — расширение области применения устройства за счет обеспечения поиска по любому слову из двух хранящихся в устройстве массивов. Поступающая на вход устройства признаковая последовательность записывается в .блок 1 памяти. В компараторе 5 проводится сравнение последовательнос ф |

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4247987/24-24 (22) 25.05.87 (46) 15.08.89. Бюл. 9 30 (72) Г.П. Токмаков, В.H. Кильдюшев, А.Н. Ивыдков и В.Т. Болгов (53) 681.327(088.8) (56) Авторское свидетел ст о СССР

9 1243036, кл. G 11 С 29/00, 1984.

Авторское свипетельство СССР

Р 1432508, кл. G 11 С 15/00, 1987. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО (57) Изобретение относится к вычисли тельной технике и может найти приме„„SU,» 1501163 А 1

3 1501163

4 тей, считываемых с блоков 1 и 2 па- из блока 3 в соответствии с режимом мяти, по поступлению импульсов срав- работы устройства. Устройство также нения. Выработку импульсов сравне- содержит счетчик 3, элемент И 6, ния элементом И 10 и разрешающего 5 элемент ИЛИ 11, группу элементов И сигнала элементом И 9 обеспечивают 14 ° Изобретение обеспечивает сравнетриггеры 7 и 8. Триггер 7 идентифи- ние признаковой последовательности, цирует последовательности, считыва- поступившей на вход устройства, с емые с блока 2, т,е ° разграничивает последовательностями как из первого, признаковую и информационную последо- 10 так и из второго массивов, хранящихвательности, а триггер 8 фиксирует ся в блоке 2 памяти, и соответственрезультат сравнения. Реверсивный .но поиск искомой последовательности счетчик 4 и элементы И 12, 13 управ- как во втором, так и в первом массиляют порядком считывания информации вах. 3 ил.

Изобретение относится к вычисли тельной технике, а именно к ассоциативным запоминающим устройствам (АЗУ), и может быть использовано для распознаваний и синтеза сигналов.

Цель изобретения — расширение области применения устройства за счет обеспечения. поиска по любому слову из двух хранящихся в устройстве массивов.

На фиг. 1 изображена структурная схема ассоциативного запоминающего устройства; на фиг.. 2 — размещение информации з первом и втором блоках памяти; на фиг. 3 — временные диаграммы работы устройства.

Устройство (смйфиг. 1) содержит первый 1 и второй 2 блоки памяти, к адресным входам которых подключены счетчик 3 и реверсивный счетчик 4 соответственно.

В блок 1 памяти записывается признаковая последовательность А, (а В а В °, ° В Rp) MIH В» = (b„ В

b„ ..., Ъ,) в соответствии с режи45 мом работы устройства, где р и о переменные величины, поичем элементы последовательности записываются в блок 1 в обратном порядке, т.е. с последнего элемента а или b> до первого а, или ЪВ (см.фиг. 2а, б), 50 причем i =.1,М, где М вЂ” целое.

В блоке 2 хранится два массива последоветелвиостей А =(А,, ..., Ам и В - 1 В,, ..., Вм}, причем кекдомт элементу А„массива А соответствует определенная последовательность В „ массива В и наоборот, каждому элемеи» ту В, массива В соответствует элемент А; массива А. Таким образом, структура данных в блоке 2 имеет вид АВ =(A,В,, А„В j, причем кеидмй элемент А; и В; этои структуры заканчивается кодом конца последовательности.

Элементы последовательностей А и В в блоке 2 размещаются следуЪ ющим образом: в последовательностях

В„ с возрастанием адреса ячеек памяти увеличивается и порядковый номер элементов последовательности, содержащихся в этих ячейках, в последовательностях А наоборот — с возрастанием адреса уменьшается порядковый номер элементов последовательности (см. фиг. 2в) °

Сравнение признаковой последовательности А или В записанной в бло ке 1, с последовательностями массива А или В, хранящимися в блоке 2, происходит в компараторе 5. о

Для .определения результатов сравнения последовательностей служит первый элемент И 6, выходом подключенный к тактовому входу первого триггера 7, который прямым выходом подключен к тактовому входу второго триггера 8 и к входу второго элемента И 9, а инверсным выходом — к входу третьего элемента И 10, выход которой подключен к управляющему входу компаратора 5, выход которого подключен к одному из входов элемента ИЛИ 11.

Для организации работы счетчика 4 в двух режимах служат четвертый 12 и пятый 13 элементы И.

15011

Искомая информация считывается через группу элементов И 14. подключенных к выходам блока 2.

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

"Режим" на вход устройства: релком 1— поиск по признаку А; режим 2 — поиск пс признаку В. 10

При включении устройства в рабо гу счетчик 3 сбрасывается °

На первом этапе проводится запись признаковой последовательности в блок 1. На устройство подается сигнал "Запись", которыи устанавливает блок 1 в режим записи, сбрасывает счетчик 4, устанавливает триггер 7 в "единичное" состояние "1", а триггер 8через элемент ИЛИ 11 — в "0". 20

Запись элементов признаковой последовательности осуществляется в порядке поступления импульсов Счет". Цикл записи заканчивается записью в блок кода конца последовательности (фиг.За).!5

На втором этапе проводится сравнение признаковой последовательности, записанной в блоке 1, с последовательностями, содержащимися в блоке 2.

Допустим, что в результате прове- 30 дения цикла записи в блок 1 записана признаковая последовательность А .

На этапе сравнения на устройство подается сигнал иЧтение", который устанавливает блоки 1 и 2 в режим считывания информации и разрешает прохождение импульсов "Счет" на счетный вход "+1" счетчика 4. Считывание элементов последовательностей с блоков 1 и 2 производится синхронно по поступлению импульсов "Счет" на счетные входы счетчиков 3 и 4. !

Исходное состояние устройства на этапе сравнения следующее: счетчик

4 сброшен и с блока 2 считывается содержимое "нулевой" ячейки, которая не используется под хранение элементов последовательностей (фиг. 2в), триггеры 7 и 8 находятся в "1" и "0" состояниях соответственно, что запрещает выработку импульсов сравнения элементом И 10 и подачу их на компаратор 5. Такое состояние устройства сохраняется до тех пор, пока с блока 2 не считывается код конца последовательности, в результате чего срабаты,вает элемент И 6, что вызывает сброс, сче а 3 и переключение триггера

63.

? в состояние 0, что в свою очередь переключает триггер 8 в состояние и н (фиг ° Зб) .

В результате имеем следующее состояние устройства: счетчик 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" (фиг. 3r). Таким образом, счетчик 3 указывает на "нулевую ячейку блока 1, содержащую последний элемент ад признаковой последовательI

1501163 вой последовательности А, записанной в блоке 1, с последовательностями массива А, хранимого в блоке 2, и вывод искомой последовательности

Bj. заканчивается.

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

40

Формула изобретения

Ассоциативное запоминающее устройство, содержащее первый блок памяти, компаратор, второй блок памяти, группу элементов И, счетчик, первый и второй триггеры, с первого по третий элементы И, элемент ИЛИ, причем

50 информационные входы первого блока памяти являются признаковыми входами устройства, вход признака записи первого блока памяти является входом записи устройства, входы признака чтения первого и второго блоков па55 мяти объединены и являются входом / чтения устройства, адресные входы первого блока памяти подключены к ности А;, счетчик 4 — на ячейку блока 2, содержащую последний элемент последовательности А, а элемент

И 10 находится в состоянии, пропускающем импульсы сравнения на компаратор 6, и описанный процесс повторяется.

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

В этом случае производится сравнение.одинаковых последовательностей и компаратор 5 не вырабатывает сигнала несовпадений,,следовательно, триггер 8 остается в состоянии "1",* а триггер 7 по коду конца последовательности А| переключается в состо- 20 яние "1" (фиг. Зд), что вызывает выдачу разрешающего сигнала на элементы И 14 и искомая информационная последовательность В; поступает на выходы устройства (фиг.Зе). 25

На этом этапе сравнения признаковыходам разрядов счетчика, счетный вход которого является тактовым входом устройства, выходы первого блока памяти соединены с входами первой группы компаратора, выходы второго блока памяти, первые входы элементов И группы и входы первого элемента И соединены с входами второй группы компаратора, с входами второй группы компаратора, выходы элементов

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

И„ выход которого соединен с вторыми входами элементов И группы, выход второго триггера соединен с вторым входом второго элемента И и входом третьего элемента И, выход первого элемента И соединен с входом синхронизации первого триггера, о т л ич а ю щ е е с я тем, что, с целью расширения области применения устройства за счет обеспечения поиска по любому слову из двух хранящихся в устройстве массиве, в него введены реверсивный счетчик и четвертый и пятый элементы И, причем выходы разрядов реверсивного счетчика подключены к адресным входам второго блока памяти, входы сложения и вычитания реверсивного счетчика подключены соответственно к выходам четвертого и пятого элементов И, первые входы которых соединены с входом чтения устройства, вторые входы четвертого и пятого элементов И соединены с тактовым входом устройства, третьим входы четвертого и пятого элементов И объединены и являются входом задания режима устройства, выход первого элемента И подключен к установочному входу счетчика, первый и.второй входы элемента ИЛИ подключены соответственно к выходу компаратора и входу записи устройства, выход элемента ИЛИ соединен с входом установки в "0",второго триггера, установочный вход реверсивного счетчика и вход установки в "1" первого триггера подключены к входу записи уствойств а.

1501163

Ка0 конца после О5аiПЕЛЬИОСП7и

Фиг,2 чьи

Ceram

Лйлись бх.!

ЧтЫиЕ

Йи. 12

Вых t3

Ь!х.1

EVb.2

Вих.7

Вих.7

Выл S

Вил.6

Вил.10

Вил.6 . Выл9

Вил. Н