Ассоциативное запоминающее устройство Советский патент 1989 года по МПК G11C15/00 

(Л

ел

О

СО

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

(puc-.i

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

. о . , а.р/ ИЛИ В,- - (Ь ,

/2 « L.O) В соответствии с режи 2 be

ар)

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

Цель изобретения - расширение области применения устройства за счет обеспечения.ПОИСКА по любому слову из двух хранящихся в устройстве массивов.

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

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

В блок 1 памяти записывается признаковая последовательность А,

(а, , а- Ь.

мом работы устройства, где р и q переменные величины, птзичем элементы ппследовательности записьшаются блок 1 в обратном порядке, т.е. с последнего элемента ар или Ъо до первого а, или Ъ (см.фиг. 2а, б), причем i .1,М, где Н - целое,

В блоке 2 хранится два массива последовательностей А и В в,, .,., Вц|, причем каждому элементу А; массива А соответствует определенная последовательность BI; массива В и наоборот, каждому элеме ту Bi. массива В соответствует эле

из блока 3 в соответствии с режимом работы устройства. Устройство также содержит счетчик 3, элемент И 6,

элемент ИЛИ 11, группу элементов И 14. Изобретение обеспечивает сравнение признаковой последовательности, поступившей на вход устройства, с последовательностями как из первого,

так и из второго массивов, хранящихся в блоке 2 памяти, и соответственно поиск искомой последовательности как во втором, так и в первом массивах. 3 ил.

мент массива А. Таким образом, структура данных в блоке 2 имеет вид АВ ,, , причем каждый элемент А, и Б; этой структуры заканчивается кодом конца последовательности.

Элементы последовательностей Aj, и В в блоке 2 размещаются следующим образом: в последовательностях В с возрастанием адреса ячеек памяти увеличивается и порядковый номер элементов последовательности, содержащихся в этик ячейках, в последовательностях Aj, наоборот - с возрастанием адреса уменьшается порядковый номер элементов последовательности (см. фиг. 2в).

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

° а

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

подключен к одному из входов элемента ИЛИ 11.

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

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

Устройство работает в двух режимах, которые задаются подачей соответствующего потенциального сигнала Режим на вход устройства: режим 1 - поиск по признаку А; режим 2 - поиск по признаку В.

При включении устройства в работу счетчик 3 сбрасьшается.

На первом этапе проводится запись признаковой последовательности в блок 1. На устройство подается сигнал Запись, который устанавливает блок 1 в режим записи, сбрасывает счетчик 4, устанавливает триггер 7 в единичное состояние 1, а триггер 8 через элемент ИЛИ 11 - в О. Запись элементов признаковой последовательности осуществляется в порядке поступления импульсов Счет. Цикл записи заканчивается записью в блок 1

30

кода конца последовательности (фиг.3а).5 с выхода элемента И 10, которые поНа втором этапе проводится сравнение признаковой последовательности, записанной в блоке 1, с последовательностями, содержащимися в блоке 2.

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

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

счетные входы счетчиков 3 и 4, I

Исходное состояние устройства на

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

ступают в соответствии с импульсами Счет при условии, что триггеры 7 и 8 находятся в О и 1 состояниях соответственно. Компаратор 5 срабатывает по несовпадению, что вызьшает установку триггера 8 через элемент ИЛИ 11 в состояние О, что в свою очередь ведет к прекращению подачи импульсов сравнения на ком5 паратор 5.

Таким образом, если в ходе сравнения последовательностей А и А произошло несовпадение, дальнейшее сравнение C4nTb BaeNfbK слов прекра40 щается. При считыва1:ин кода конца последовательности А с блока 2 ерабатызает элемент И Ь, что вызывает сброс счетчика 3 и переключение триггера 7 в состояние 1 (фиг.Зв).

45 Считываемая с блока 2 информационная последовательность Б в данном случае на выход устройства не поступает, так как нет разрешающего сигна ла на входах элементов И 14. Считы50 ваемый код конца последовательности вызьшает срабатьюание элемента И 6, что приводит к сбросу счетчика 3 и переключению триггера 7 в состояние О, что в свою очередь приводит к

55 переключению триггера 8 в состояние 1 (фиг. Зг). Таким образом, счетчик 3 указывает на нулевую ячейку блока 1, содержащую последний элемент ар признаковой последователь-

1 в состояние О, что в свою очеред переключает триггер 8 ё состояние 1 (фиг. 36).

В результате имеем следующее состояние устройства: счетчик 3 установлен на нулевую ячейку блока 1, где записан последний элемент ар признаковой последовательности А .

10 (фиг.2а), счетчик 4 указывает на

ячейку блока 2, где хранится последний элемент последовательности К (см. фиг. 2в), триггеры 7 и 8 нахо- дятсд в О и 1 состояниях соответ15 ственно, что обеспечивает вьфаботку импульсов сравнения элементом И 10 дпя компаратора 5 и запрещение выработки разрешающего сигнала элементом И 9 на вьгоод информации из уст20 ройства. Следовательно, сначала сравниваются последовательности At с блока 1 и AL. с блока 2.

С-равнение последовательностей проводится по поступлению импульсов

ступают в соответствии с импульсами Счет при условии, что триггеры 7 и 8 находятся в О и 1 состояниях соответственно. Компаратор 5 срабатывает по несовпадению, что вызьшает установку триггера 8 через элемент ИЛИ 11 в состояние О, что в свою очередь ведет к прекращению подачи импульсов сравнения на компаратор 5.

Таким образом, если в ходе сравнения последовательностей А и А произошло несовпадение, дальнейшее сравнение C4nTb BaeNfbK слов прекращается. При считыва1:ин кода конца последовательности А с блока 2 ера. батызает элемент И Ь, что вызывает сброс счетчика 3 и переключение триггера 7 в состояние 1 (фиг.Зв).

Считываемая с блока 2 информационная последовательность Б в данном случае на выход устройства не поступает, так как нет разрешающего сигнала на входах элементов И 14. Считываемый код конца последовательности вызьшает срабатьюание элемента И 6, что приводит к сбросу счетчика 3 и переключению триггера 7 в состояние О, что в свою очередь приводит к

переключению триггера 8 в состояние 1 (фиг. Зг). Таким образом, счетчик 3 указывает на нулевую ячейку блока 1, содержащую последний элемент ар признаковой последователь- i

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

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

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

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

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

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

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

0

5

0

5

0

5

0

5

0

5

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

а

ар

О Р-1

Ж

5

.5а

Ж

S

Код fioHLiG. после- додательности.

- .2

пппгттп

.nn

f Ци зтха ripujHCMSou taueSoSa- телыюагшА

nrnnmn imr

innnn тпг

(У;

сра не«да-лРоЛмiSHue

S)

.

о

dip

бЦ

v

.Ч

1ГТГТГ ИГТППГТГ

ТППП

:псдг

пп

XDO

Ц

и «V/W . е). BtiSoi инфор- ченш шпа-начионня} т- itHue слеЗодатгм - ности S