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

 

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

СОЮЗ СОВЕТСНИХ.

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

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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К A BT0PCHOMY СВИДЕТЕЛЬСТВУ

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

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

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

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

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

9 1432608, кл. С ii С 15/00, 1987. (54) АССОЦИАТИВНОЕ ЗАПОИИНАЮЩЕЕ

УСТРОЙСТВО (57) Изобретение относится к вычислительной технике и может быть использовано в ассоциативных процессорах, устройствах распознавания — синтеза сигналов. Цель изобретения — повышение быстродействия устройства. Устройство содержит блоки 1 и 2 памяти, служащие соответственно для хранения ключевой и искомых последовательностей, компаратор 3, счетчики 4 и 5, регистры 6 и 7, блок управления 8.

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

3 150116

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

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

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

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

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

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

В процессе записи в блок 1 заносится ключевая последовательность в порядке поступления элементов, считывание этой последовательности 30 в режиме сравнения производится в обратном порядке» т.е. по принципу

"последний пришел — первым ушел" (фиг. 2).

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

А 1 = а » а » ° ° ° а1 »

»» — 1» 2» ° ° » q = Ча1» а в инверсном Режиме — ключевая по- . 40 следовательность вида

В . = (b;Ä b,, ..., Ь; «1;

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

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

В; (Ь4» Ь; еаеу ЬФ» . 5О

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

А ., а в ячейке следующей за послед1 +Ф» ним элементом b;) последовательнос4 4 ти В;, записан элемент й; являющийся адресом перехода к аналогичной ячейке для последовательности В

1- »

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

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

Адресное пространство блока 2 между элементами d „ и с не используется и может содержать произвольную информацию (х).

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

»

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

Элементы ключевой последовательности поступают на информационные входы устройства в соответствии с тактовыми импульсами СИ", поступающими на вход Х1 блока 8. Тактовые импульсы синхронизируют работу устРойства и состоят из двух полутактов: первый имеет уровень "1", второй "О".

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

"0" в блок 1. В последующих тактах блок 8 вырабатывает по первому полутакту импульс на выходе УЗ, по которому содержимое счетчика 4 увеличивается на единицу, а по второму— импульс на выходе У1, по которому следующий элемент ключевой последовательности записывается в следующую ячейку блока 1.

5

15011

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

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

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

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

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

A = (а, а;, ..., a; 1. (, 1Ч,1 20

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

У18.

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

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

С), являющийся адресом перехода на 45 следующую последовательность. Во втором полутакте этот адрес записывается в регистр 7, для этого с выхода У10 блока 8 на вход регистра 7 подается импульс. 50

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

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

64 6 с выхода У10 олока S поступает импульс, вызывая адресацию очередной ячейки блока 2, с которой считывается q-ый элемент а последователь< . ности А ° С блока 1 перед началом сравнения также считывается q-ый элемент а „. ключевой последовательности А. Во втором полутакте этого такта на вход компаратора 3 с выхода У9 блока 8 подается импульс сравнения и элемент ключевой последовательности и элемент с признаком А последовательности блока 2 сравниваются в компараторе 3. В случае совпадения сравниваемьк элементов с выхода компаратора 3 поступает уровень

"О"

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

"0"

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

"короче" последовательности блока 2; на выходе блока 2 появился признак

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

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

2 считывается признак В, то мы имеем

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

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

1 с последней последовательностью А из блока 2 возникает одна из трех ситуаций несовпадения. После обработки этой ситуации с выхода У17 блока

8 на выходе устройства появляется сигнал "ПрЕ" о том, что в процессе просмотра всего массива информации, записанной в блоке 2 искомая последовательность не обнаружена.

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

= Ь, Ь, ..., Ь 2 1

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

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

&Ок 1 ственно с вторым и третьим установочными входами блока управления, шестнадцатьй, семнадцатый и восемнадцатый выходы блока управления являются соответственно выходами "Начало вы= вода данных 1, Завершение вывода данных и "Результат поиска отрицательный устройства.

1501164

ФигЗ

Составитель Б. Рудаков

Техред Л.Олийнык Корректор Н. Король

Редактор M. Недолуженко

Заказ 4878/50 ° Тираж 558 Подписное

ИНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, R-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101