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

(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО ся индикаторами меток конца слов, вторые индикаторы 3, являющиеся индикаторами совнадения, блок 4 определения многозначного ответа, элемент ИЛИ 5, донолнительный элемент ИЛИ 6, счетчик 7, блок управления 8, дополнительный элемент ИЛИ 9, третьи индикаторы К), являющиеся индикаторами разрешения опроса, блоки 11 сброса индикаторов и блоки 12 установки индикаторов. В состав блоков 11 и 12 входят элементы И 13, элементы ИЛИ 14, элементы И 15, элементы НЕ 16, элементы И 17, элементы ИЛИ 18, элементы И 19, элементы НЕ 20. Устройство также содержит четвертые индикаторы 21, являющиеся индикаторами меток расщиренного алфавита, регистр опроса 22 и регистр маски 23. Первые входы матрицы 1 через регистр 23 соединены с регистром 22, а выходы подключены к входам индикаторов 2 и 3. Выходы элементов ИЛИ 6 и 9 подключены к одним из входов блока управления 8, а входы - соответственно к выходам индикаторов 2 и 21 и первым входам блоков 11, вторые и третьи входы которых соединены с одними из выходов блока управления 8, другие выходы блока 8 подключены к управляющим входам блоков 12. Информационные входы блоков 12 соединены соответственно с выходами индикаторов 2 и 3. Входы индикаторов 21 соединены со вторыми входами матрицы I, выходы блоков 11 и 12 подключены к входам индикаторов 10. Устройство работает следующим образом. Примем, что массив информации записывается в матрице 1 без пропуска строк; кодовую комбинацию в одной строке матрицы 1 обозначим буквой. Тогда множество букв, соответствующих всем различным кодовым комбинациям, записанным в строках матрицы 1, будем называть основным алфавитом F. Если в соответствии со структурой конкретного массива информации, записанного в матрице, некоторые строки в матрице выделить метками конца слова, то все кодовые последовательности, начинающиеся с первой строки матрицы или со строк, непосредственно следующих за строками, выделенными метками конца слов, и до ближайщих (по возрастанию номеров) строк, выделенных метками конца слов, можно рассматривать как множество допустимых слов в алфавите Е. Введем понятия дополнительного алфавита D, расщиренного алфавита R, которые определяются соотнощением EnD и R ЕлО, и понятие метки расширенного алфавита. Тогда слова из множества допустимых слов, содержащие букву, выделенную .меткой расщиренного алфавита, образуют множество слов, допустимых в алфавите R. Под допустимым словом в алфавите R здесь понимается слово, которое получается посредством включения последовательности произвольной длины из букв алфавита D перед буквой, выделенной меткой расщиренного алфавита в любом слове и множества допустимых слов в алфавите E В этом случае АЗУ должно осуществлять ассоциативный поиск для поисковых образов запросов, соответствующих допустимым словам как в алфавите Е, так и в алфавите R. Для слов в алфавите R должен выдаваться признак и определяться длина включенной последовательности букв из алфавита D в соответствующее слово из множества слов, допустимых в алфавите E Отметим, что при описании работы устройства принято, что выход индикаторов 3 i-ой строки матрицы 1 соединяется с входом блока 12, соответствующего i + 1-ой строке матриць 1, а выход индикаторов 2 j-ой строки матрицы 1, выделенной меткой конца слова, соеди)1яется с входом блока 2 j - 1-ой строки матрицы 1. Ассоциативное запоминающее устройство может работать в нескольких режимах. Режим 1. В этом режиме предполагается, что в индикаторы 21 не занесено ни одной метки расщиренного алфавита, т. е. реализуется ассоциативный поиск только в массиве допустимых слов в алфавите Е. Устройство работает следующим образом. По сигналу из блока управления 8 на первые входы элемента И 19, входящего в блоки 12, в том случае, если вторые входы элементов И 19 соединены с выходами индикаторов 2, в которых зафиксированы метки конца слов, с выхода элементов ИЛИ 18 выдается сигнал установки соответствующих индикаторов 10 и индикатора 10 первой строки матрицы 1. Затем через регистр маски 23 из регистра опроса 22 на первые входы матрицы 1 подается код очередной буквы слова, соответствующего поисковому образу запроса, для которого производится ассоциативный поиск. После выполнения цикла обращения к матрице 1 блок управления- 8 выдает сигнал сброса на первые входы элементов И 13 и 15, входящих в блоки И. При этом сигнал опроса с выходов элемента И 15 через элемент ИЛИ 14 выдается на входы индикаторов 10, поскольку метки расширенного алфавита отсутствуют и на второй вход элемента И 15 через элемент НЕ 16 выдается сигнал, определяющий срабатывание этого элемента И. Затем если при выполнении цикла ассоциативного поиска для кода очередной буквы, подаваемого на вход регистра опроса 22, выполнялось хотя бы одно совпадение, что определ55ется сигналом с выхода элемента ИЛИ 5, то в случае, когда совпадение зафиксировано в строках матрицы 1, которые не выделены метками конца слов, что определяется отсутствием сигнала на выходе элемента ИЛИ 6, блок управления 8 выдает на первый вход элементов И 17 сигнал переписи в индикаторы 10 значений индикаторов 3, поступающих на вторые входы элементов И 17. После этого цикл ассоциативного поиска повторяется для кода очередной буквы на входе регистра опроса 22. Если элемент ИЛИ 6 выдает признак совпадения в строке матрицы 1, выделенной меткой конца слов, по сигналу из блока управления 8 блок 4 формирует ответ. Затем АЗУ устанавливается в начальное состояние. Если элемент ИЛИ 5 не зафиксирует ни одного совпадения для дчередной буквы на входе, устройство также устанавливается в начальное состояние. Режим 2. При работе в этом режиме предполагается, что в индикаторы 21 занесена хотя бы одна .метка расширенного алфавита, т. е. может возникнуть необходимость в выполнении ассоциативного поиска слов в расширенном алфавите R. Устройство работает во втором режиме аналогично первому режиму до тех пор, пока ни на один из индикаторов 10, соответствующих строкам, выделенным метками расширенного алфавита, не поступит сигнал установки. Если такие сигналы поступили, с выхода элемента ИЛИ 9 выдается сигнал в блок управления 8, и устройство готово к работе во втором режиме, т. е. к ассоциативному поиску слов в множестве допустимых слов в алфавите К.Если для первой же (по времени) буквы, поступающей в регистр опроса 22, после перехода устройства во второй режим выдается сигнал совпадения, производится сброс индикаторов Ш и устройство находится в первом режи.ме до тех пор, пока элемент ИЛИ 9 не выдаст очередной сигнал,, определяющий наличие разрешения выбора хотя бы одной строки, выделенной меткой расширенного алфавита в матрице 1. В том случае, если при переходе устройства во второй режим при поступлении очередных кодов в регистр опроса 22 сигнал совпадения не выдается, то, следовательно, на вход устройства поступает последовательность букв из алфавита D, длина которой фиксируется счетчиком 7. При переходе устройства во второй режим сигналом, поступающим со второго выхода блока управления 8, счетчик 7 сбрасывается, а затем по мере поступления последовательности букв из алфавита Д с выхода блока управления 8 выдается последовательность импульсов, число которых соответствует числу букв в этой последовательности. При этом предполагается, что предельная допустимая длина последовательности букв в алфавите D определяется блоком управления 8, и в том случае, когда она больше допустимого значения, слово, поступающее на вход регистра опроса 22, классифицируется как недопустимое слово в алфавите R, ассоциативный поиск прекращается, и устройство устанавливается в начальное состояние. До тех пор, пока длина последовательности букв в алфавите D не превышает заданного предела, индикаторы 10, установленные в положение разрешения, в тех строках, которые выделены меткой расщиренного алфавита, не сбрасываются, поскольку сигнал сброса индикаторов 21 не выбрасывается блоками 11, соответствующими этим строкам, до тех пор пока на второй вход элементов И 13 не поступит сигнал из блока управления 8, формируемый прн поступлении с выхода элемента ИЛИ 5 сигнала в блок управления 8. Таким образом, во втором режиме выполняется ассоциативный поиск допустимых слов в .алфавите R. Режим 3. Необходимость в этом режиме возникает в том случае, если множество допустимых слов в алфавите Е расширяется следующим образом. Допустимыми словами считаются также слова, полученные из допустимых слов посредством приписывания справа букв из алфавита Р. Тогда в третьем режиме ассоциативный поиск может быть продолжен после получения признака метки конца слова на выходе элемента ИЛИ 6, если длина слова не превыщает заданного предела, без установки устройства в начальное состояние. При этом при переписи содержимого индикатора 3 в индикаторы 10, с помощью элемента НЕ 20 блокируется установка индикатора 10, соответствующего строке матрицы 1, непосредственно следующей за строкой, выполненной меткой конца слова, которая выдала сигнал совпадения на предыдущем цикле опроса. Ассоциативный поиск слов в расширенном алфавите позволяет увеличить быстродействие и функциональные возможности систем обработки дискретной информации в тех случаях, когда необход имо классифицировать слова в некоторое, алфавите, которые могут изменяться при включении в них в фиксированных местах произвольной последовательности букв другого алфавита, непересекающегося с основным. Наибольший эффект от применения предлагаемого устройства может быть получен в системах ввода - вывода информации в ЭВМ, в мультиплексных каналах и в специальных процессорах управления каналами связи. Формула изобретения Ассоциативное запоминающее устройство содержащее матрицу элементов памяти, первые входы которой через регистр маски соединены с выходами регистра опроса, а выходы подключены к входам первых и вторых индикаторов, элемент ИЛИ, входы которого соединены с выходами вторых индикаторов и входами блока определения многозначного ответа, а выход - с блоком управления, соединенным со счетчиком, третьи индикаторы, выходы которых подключены ко вторым входам матрицы элементов памяти, отличающееся тем, что, с целью расширения области применения устройства. оно содержит четвертые индикаторы, блоки установки и сброса индикаторов и дополнительные элементы ИЛИ, выходы которых подключены к одним из входов блока управления, а выходы - соответственно к выходам первых и четвертых индикаторов и первым входам блоков сброса индикаторов, вторые и третьи входы которых -соединены с одними из входов блока управления, другие выходы блока управления подключены к управляющим входам блоков установки индикаторов, информационные входы которых соединены соответственно с выходами первых и вторых индикаторов, входы четвертых индикаторов соединены со вторыми входами матрицы э лементов памяти, выходы блоков сброса и установки индикаторов подключены к входам третьих индикаторов. Источники информации, принятые во внимание при экспертизе 1.Сотрц1ег Desigh, 1971, том. 10 и 11, с. 103-110. 2.Авторское свидетельство СССР № 484562, кл. G 11 С 15/00, ,19/3.