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

(Л

ОТ

О) 4

Изобретение относится к вычислительной технике и может быть использовано в ассоциативных процессорах, устройствах распознавания - синтеза сигналов.

Цель изобретения - повьшение бысродействия устройства.

На фиг. 1-изображена структурная схема ассоциативного запоминающего устройства (АЗУ); на фиг. 2 - размещение информации в первом и втором блоках памяти; на фиг. 3 - гшгоритм работы устройства.

Устройство содержит (см.фиг.1) первый 1 и второй 2 блоки памяти, .компаратор 3, первый 4 и второй 5 счетчики, первый 6 и второй 7 регисры и блок 8 управления, вьтолненный например, в виде программируемой логической матрицы.

На фиг. 1 приняты также следу- кщие обозначения: Х1 - Х10 - входы блока 8, Y1-Y18 - выходы блока 8.

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

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

,

ти В- , записан элемент d,- , являющийся адресом перехода к аналогичной ячейке для последовательности В1-1

Кроме того, по нулевому адресу блока 2 записан элемент d, являющийся адресом перехода к элементу d,

ми

по10

15

следовательности В, а по максимальному адресу блока 2 записан элемент с, содержимое которого произвольно

В признаковой части блока 2 эле- м енты последовательностей А 41 - 1 ..., N) снабжены при.чнаком А, элементы последовательностей B-(i 1, ..., NJ - признаком В, элементы (i 1, ..о, N) - признаком С, элементы d-(i 1, ..., N) - признаком D.

Адресное пространство блока 2 между элементами d

и-1

и с не использует20 ся и может содержать произвольную информацию (х).

Устройство работает в двух режимах: прямом (поиск по признаку А-) и обратном (поиск по признаку .

25 На первом этапе производится запись ключевой последовательности в блок 1. Процесс записи в обоих режимах абсолютно одинаков и проводится по единому алгоритму (фиг. За.

30 Элементы ключевой последовательности поступают на информационные входы устройства в соответствии с тактовыми импульсами СИ, поступающими на вход XI блока 8, Тактовые

Изобретение относится к вычислительной технике и может быть использовано в ассоциативных процессорах, устройствах распознавания - синтеза сигналов. Целью изобретения является - повышение быстродействия устройства. Устройство содержит блоки 1 и 2 памяти, служащие соответственно для хранения ключевой и искомых последовательностей, компаратор 3, счетчики 4 и 5, регистры 6 и 7, блок управления 8. В устройстве реализован алгоритм, который позволяет при первом же несравнении элементов последовательностей переходить к следующему циклу поиска. 3 ил.

В прямом режиме в блок 1 записьша- импульсы синхронизируют работу устется ключевая последовательность вироиства и состоят из двух полутактов первый имеет уровень 1, второй

АГ

а.

Я

Ч VaR,

а в инверсном режиме - ключевследовательность вида В {Ь,,, Ь., ..., Ъ,.; .2, ...54 Vaн(

В блоке 2 записаны последоности

А;

I

А,-

i Т, 2,

которых еле,

ь

ч й ipj

1, 2, ..., N р Va;R.

я. I

i(V ) .., N; q VaR,

за каждой из которых следует довательность

Причем в ячейке, находящейся перед первым элементом а последовательности

А,.,

записан элемент с

1Ч

являющийся адресом перехода к аналогичной ячейке для последовательности А., а в ячейке следующей за последним элементом Ь, р последовательнос0

5

0

5

роиства и состоят из двух полутактов: первый имеет уровень 1, второй .

Процесс записи инициируется подачей сигнала Запись (1 уровень) на вход Х2 блока 8. В первом такте по первому полутакту блок 8 вырабатывается на своем выходе У6 импульс, который сбрасьшает счетчики 4 и 5 в состояние О, а по второму полутакту - на выходе У1 блок 8 вырабатывает импульс, по которому имеющаяся на входах устройства информация (первый элемент ключевой последовательности) записывается по адресу О в блок 1. В последующих тактах блок 8 вырабатьтает по первому полутакту импульс на выходе УЗ, по которому содержимое счетчика 4 увеличивается на единицу, а по второму - , импульс на выходе У1, по которому следующий элемент ключевой последовательности записывается в следующую ячейку блока 1.

°1

Таким образом, производится запис элементов ключевой последовательности в блок 1, который завершается записью последнего элемента и снятием сигнала Запись (О уровень) с входа Х2 блока 8,

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

Процесс сравнения инициируется подачей сигнала Сравнение (1 уровень) на вход ХЗ блока 8.

Рассмотрим в качестве-примера процесс сравнения в прямом режиме (фиг. Зб).

В блоке 1 в процессе записи запиг сана ключевая последовательность

Af а. , а,, ..., а.|.

Исходное значение счетчика 4 равно q-1 (устанавливается в процессе записи), а счетчика 5-0 (устанавливается в начале процесса записи, путем сброса). Сигнал Сравнение пе- реводит блоки 1 и 2 в режим чтения путем выработки блоком 8 соответствующих потенциалов на выходах У2 и У18.

Перед тем, как начать сравнение элементов последовательностей, производится предварительная устан овка.

В первом полутакте подаются импульсы с вькодом У7 и У12 блока 8 соответственно на вход регистра 6 и выход счетчика 5, в результате чего в регистре 6 запоминается адрес элемента а ключевой последовательности А, который используется перед началом каждого очередного цикла сравнения для восстановления исходного значения счетчика 4, а счетчик 5 указывает на первую ячейку блока 2, в которой находится элемент С (признак С), являЕощийся адресом перехода на следукяцую последовательность. Во втором полутакте этот адрес записывается в регистр 7, для этого с выхода У10 блока 8 на вход регистра 7 подается импульс,.

Сравнение элементов ключевой последовательности с элементами последовательностей блока 2 происходит следуюпщм образом.

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

о

5

0

5

о

0 5

5

646

с выхода У10 Ьлока В поступает импульс, вызьшая адресацию очередной ячейки блока 2, с которой считывается q-ый элемент а последовательности А(. С блока перед началом сравнения также считьшается q-ьш элемент ключевой последовательности А. Во втором полутакте этого такта на вход компаратора 3 с выхода У9 блока 8 подается импульс сравнения и элемент ключевой последовательности и элемент с признаком А посл едовательности блока 2 сравниваются в компараторе 3. В случае совпадения сравниваемых элементов с выхода компаратора 3 поступает уровень О.

При сравнении последующих элементов в первом полутакте очередного такта с выходов У10 и УЗ блока 8 соответственно на суммирукщий вход счетчика 5 и вычитающий вход счетчи-г- ка 4 построгают импульсы счета. С блоков 1 и 2 при этом сг1итываются очередные элементы сравниваемых последовательностей. Во втором полутакте на вход компаратора 3 с выхода У7. блока 8 поступает импульс сравнения и с его выхода в случае совпадения элементов поступает сигнал уровня О.

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

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

тот случай, когда произошло совпадение ключевой последовательности с одной из последовательностей, записанных в блоке 2, При этом сигнал во втором полутакте вырабатьшается сигнал Вьгоод с выхода У15 блока 8, свидетельствующий о наличии на информационных выходах устройства элемента искомой последовательности, в данном случае первого элемента последовательности Б. Производится считывание искомой последовательности В, и продолжается до тех пор, пока после очередного пересчета счетчи ка 5 с блока 2 на входы Х9 и Х10 блока 8 подступит признак В. По этому признаку во втором полутакте с выхода У16 на выход устройства поступит сигнал ПрЕ, сигнализирующий о завершении процесса сравнения и вывода искомой последовательности.

Возможна также ситуация, когда ни одна из последовательностей, записанных в блоке 2 не совпадает с ключе- вой последовательностью, записанной в блоке 1. В этом случае при сравнении ключевой последовательности А с Последней последовательностью А из блока 2 возникает одна из трех ситуаций несовпадения. После обработки этой ситуации с выхода У17 блока 8 на выходе устройства появляется сигнал ПрЕ о том, что в процессе просмотра всего массива информации, записанной в блоке 2 искомая последовательность не обнаружена.

Процесс сравнения в инверсном режиме аналогичен процессу сравнения в прямом (фиг. За, в). При этом в блок 1 в результате записи вводится ключевая последовательность В.

Гъ. , ъ. , I ч 1

N,i

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

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

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

B/IOKl

13 ett€nai

3

-

н&я наст ф признаковая facmo

соответственно выходами Начало выг

tt

Завершение вьтода

вода данных ,

- и Результат поиска отрица- устройства.

данных тельный