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

 

(! 1 661 94 1"О --

Союз Советских

Социалистииеских

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 05.04.77 (21) 2472668/18-24 с присоединением заявки №вЂ” (23) Приоритет—

Опубликовано 25.06.79. Бюллетень № 23

Дата опубликования описания 03.07.79 (51) M. Кл.

G 11 С 15/00

Государстве«иый «ем«тет

СССР по делам «запретен«й и открытий (53) УДК 681.327. (088.8) (72) Авторы изобретения

А. Ю. Гурьев и Л. М. Метрик (7l) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

Изобретение относится к запоминающим устройствам.

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

Недостатком этого устройства являются большие аппаратурные затраты.

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

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

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

Это достигается тем, что устройство содержит четвертые индикаторы, блоки установки и сброса индикаторов и дополнительные элементы ИЛИ, выходы KQTopblx по. 1,ключены к одним из входов блока управления, а входы — соответственно к выходам первых и четвертых индикаторов и первым входам блоков сброса индикаторов, вторые и третьи входы которых соединены с одними из выходов блока управления, другие выходы блока управления подключены к управляющим входам блоков установки инди1 каторов, информационные входы которых соединены соответственно с выходами первых и вторых индикаторов, входы четвертых индикаторов соединены со вторыми входами матрицы элементов памяти, выходы блоков сброса и установки индикаторов под2ц ключены к входам третьих индикаторов.

На чертеже дана структурная схема предлагаемого устройства.

Устройство содержит матрицу 1 элементов памяти, первые индикаторы 2, являюгцие6694!О

25 зо

3%

4О

50

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

И 15, элементы НЕ 16, элементы И 17, элементы ИЛИ 18, элементы И 19, элементы HE 20. Устройство также содержит четвертые индикаторы 21, являющиеся индикаторами меток расширенного алфавита, регистр опроса 22 и регистр маски 23.

Первые входы матрицы 1 через регистр

23 соединены с регистром 22, а выходы подключены к входам индикаторов 2 и 3. Выходы элементов ИЛИ 6 и 9 подключены к одним из входов блока управления 8, а входы — соответственно к выходам индикаторов 2 и 21 и первым входам блоков II, вторые и третьи входы которых соединены с одними из выходов блока управления 8, другие выходы блока 8 подключены к управляющим входам блоков 12. Информационные входы блоков 12 соединены соответственно с выходами индикаторов 2 и 3. Входы индикаторов 21 соединены со вторыми входами матрицы 1, выходы блоков 11 и 12 подключены к входам индикаторов !О.

Устройство работает следующим образом.

Примем, что массив информации записывается в матрице без пропуска строк; кодовую комбинацию в одной строке матрицы

1 обозначим оуквой. Тогда множество букв, соответствующих всем различным кодовым комбинациям, записанным в строках матрицы 1, будем называть основным алфавитом F.Е.с;ли в соответствии со структурой конкретного массива информации, записанного в матрице, некоторые строки в матрице выделить метками конца слова, то все ко оные последовательности, начинающиеся с первой строки матрицы или со строк, непосредственно следующих за строками, выделенными метками I oHIIà слов, и до ближайших (по возрастанию номеров) строк, выделенных метками конца слов, можно рассматривать как множество допустимых слов в алфавите F. Введем понятия дополнительного алфавита D, расширенного алфавита

R, которые определяются соотношением

FnD u R = FnD, и понятие метки расширенного алфавита. Тогда слова из множества допустимых слов, содержащие букву, выделенную меткой расширенного алфавита, образуют множество слов, допустимых в алфавите R. Под допустимым словом в алфавите R здесь понимается слово, которое получается посредством включения последовательности произвольной длины из букв алфавита D перед буквой, выделенной меткой расширенного алфавита в любом слове и множества допустимых слов в алфавите F.

В этом случае АЗУ должно осуществлять ассоциативный поиск для поисковых образов запросов, соответствующих допустимым словам как в алфавите F, так и в алфавите R. Для слов в алфавите R должен выдаваться признак и определяться длина включенной последовательности букв из алфавита D в соответствующее слово из множества слов, допустимых в алфавите F.

Отметим, что при описании работы устройства принято, что выход индикаторов 3

i-ой строки матрицы 1 соединяется с входом блока 12, соответствующего i + 1-ой строке матрицы 1, а выход индикаторов 2 j-ой строки матрицы 1, выделенной меткой конца слова, соединяется с входом блока 12 j — 1-ой строки матрицы 1.

Ассоциативное запоминающее устройство может работать в нескольких режимах.

Режим l. В этом режиме предполагается, что в индикаторы 21 не занесено ни одной метки расширенного алфавита, т. е. реализуется ассоциативный поиск только в массиве допустимых слов в алфавите F.

Устройство работает следующим образом.

Г1о сигналу из блока управления 8 на первые входы элемента И 19, входящего в блоки 12, в том случае, если вторые входы элементов И 19 соединены с выходами индикаторов 2, в которых зафиксированы метки конца слов, с выхода элементов ИЛИ 18 выдается сигнал установки соответствующих индикаторов 10 и индикатора 10 первой строки матрицы 1. Затем через регистр маски 23 из регистра опроса 22 на первые входы матрицы 1 подается код очередной буквы слова, соответствук>щего поисковому образу запроcà, для которого производится ассоциативный поиск. После выполнения цикла обращения к матрице 1 блок управления 8 выдает сигнал сброса на первые входы элементов

И 13 и !5, входящих в блоки I I. При этом сигнал опроса с ьыходов элемента И 15 через элемент ИЛИ 14 выдается на входы индикаторов !О, поскольку метки расширенного алфавита отсутствуют и на второй вход элемента И 15 через элемент НЕ 16 выдается сигнал, определяющий срабатывание этого элемента И. Затем если при выполнении цикла ассоциативного поиска для кода очередной буквы, подаваемого на вход регистра опроса 22, выполнялось хотя бы одно совпадение, что определяется сигналом с выхода элемента ИЛИ 5, то в случае, когда совпадение зафиксировано в строках матрицы 1, которые не выделены метками конца слов, что определяется отсутствием сигнала на выходе элемента ИЛИ 6, блок управления 8 выдает на первый вход:-»е!.ентов И 17 сигнал переписи в индикаторы 10 значений индикаторов 3, поступающих на вторые входы элементов И 17. После этого цикл ассоциа669410

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

5S тивного поиска повторяется для кода очередной буквы на входе регистра опроса 22.

Если элемент ИЛИ 6 выдает признак совпадения в строке матрицы 1, выделенной меткой конца слов, по сигналу из блока управления 8 блок 4 формирует ответ. Затем АЗУ устанавливается в начальное состояние. Если элемент ИЛИ 5 не зафиксирует ни одного совпадения для очередной буквы на входе, устройство также устанавливается в начальное состояние.

Режим 2. При работе в этом режиме предполагается, что в индикаторы 21 занесена хотя бы одна метка расширенного алфавита, т. е. может возникнуть необходимость в выполнении ассоциативного поиска слов в расширенном алфавите R. Устройство работает во втором режиме аналогично первому режиму до тех пор, пока ни на один из индикаторов 10, соответствующих строкам, выделенным метками расширенного алфавита, не поступит сигнал установки. Если такие сигналы поступили, с выхода элемента ИЛИ 9 выдается сигнал в блок управления 8, и устройство готово к работе во втором режиме, т, е. к ассоциативному поиску слов в множестве допустимыx слов в алфавите R. Если для первой же (по времени) буквы, поступающей в регистр опроса 22, после перехода устройства во второй режим выдается сигнал совпадения, производится сброс индикаторов 10 и устройство находится в первом режиме до тех пор, пока элемент ИЛИ 9 не выдаст очередной сигнал, определяющий наличие разрешения выбора хотя бы одной строки, выделенной меткой расширенного алфавита в матрице 1.

В том случае, если при переходе устройства во второй режим при поступлении очередных кодов в регистр опроса 22 сигнал совпадения не выдается, то, следовательно, на вход устройства поступает последовательность букв из алфавита D, длина которой фиксируется счетчиком 7. При переходе устройства во второй режим сигналом, поступающим со второго выхода блока управления 8, счетчик 7 сбрасывается, а затем по мере поступления последовательности букв из алфавита Д с выхода блока управления 8 выдается последовательность импульсов, число которых соответствует числу букв в этой последовательности. При этом предполагается, что предельная допустимая длина последовательности букв в алфавите

D определяется блоком управления 8, и в том случае, когда она больше допустимого значения, слово, поступающее на вход регистра опроса 22, классифицируется как недопустимое слово в алфавите R, ассоциативный поиск прекращается, и устройство устанавливается в начальное состояние.

До тех пор, пока длина последовательности букв в алфавите D не превышает заданного предела, индикаторы 10, установленные в положение разрешения, в тех стро4О

1S го

3О

3$

6 ках, которые выделены меткой расширенного алфавита, не сбрасываются, поскольку сигнал сброса индикаторов 21 не выбрасывается блоками 11, соответствующими этим строкам, до тех пор пока на второй вход элементов И 13 не поступит сигнал из блока управления 8, формируемый при поступлении с выхода элемента ИЛИ 5 сигнала в блок управления 8. Таким образом, во втором режиме выполняется ассоциативный поиск допустимых слов в.алфавите R.

Режим 3. Необходимость в этом режиме возникает в том случае, если множество допуcTHMbIx слов в алфавите F расширяется следующим образом. Допустимыми словами считаются также слова, полученные из допустимых слов посредством приписывания справа букв из алфавита F. Тогда в третьем режиме ассоциативный поиск может быть продолжен после получения признака метки конца слова на выходе элемента ИЛИ

6, если длина слова не превышает заданного предела, без установки устройства в начальное состояние. При этом при переписи содержимого индикатора 3 в индикаторы 10, с помощью элемента НЕ 20 блокируется установка индикатора 10, соответствующего строке матрицы 1, непосредственно следующей за строкой, выполненной меткой конца слова, которая выдала сигнал совпадения на предыдущем цикле опроса.

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

Наибольший эффект от применения предлагаемого устройства может быть получен в системах ввода — вывода информации в ЭВМ, в мультиплексных каналах и в специальных процессорах управления каналами связи.

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

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

Редактор Т. Фадеева Техред О. Луговая Корректор Г. Назарова

Заказ 3668 43 Тираж 680 Подписное

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

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

Филиал ППП «Патент», r, Ужгород, ул. Проектная, 4

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

Источники информации, принятые во внимание при экспертизе

1. Computer Desigh, 1971, том. 10 и 1, с. 103 — 110.

2. Авторское свидетельство СССР № 484562, кл. Сз 11 С 15/ОО, 1973.