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

Союз Советских Социалистицеских РеспубликОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(23) Приоритет -ооударствеииый комитет СССР по делам изооретений и открытий(72) Авторы изобретени Гурьев 71) Заявит Е УСТРОИСТВ(54) АССОЦИАТИВНОЕ ЗАПОМИН номи наюши запоминающее щее матрицу асэлементов, реогозначного отИзобретение относится устройствам.Известно ассоциативное устройство (АЗУ), содержа социативных запоминающи гистры и блок извлечения м вета 11. Недостатком этого устроиства являются большие аппаратурные затраты.Наиболее близким к изобретению является ассоциативное запоминающее устройство, содержащее матрицу элементов памяти, первые входы которой через регистр маски соединены с выходами регистра опроса, а выходы подключены к входам первых и вторых индикаторов, элемент ИЛИ, входы которого соединены с входами вторых индикаторов и входами блока определения многозначного ответа, а выход - с блоком управления, соединенным со счетчиком, третьи индикаторы, выходы которых подключены ко вторым входам матрицы элементов памяти 12.Такое устройство реализует ассоциативный поиск слов произвольной длины только в основном алфавите, что сужает область его применения. Целью изобретения является расширение области применения устройства за счет обеспечения возможности поиска слов в расширенном алфавите.Это достигается тем, что устройство содержит четвертые индикаторы, блоки установки и сброса индикаторов и дополнительные элементы ИЛИ, выходы которых подключены к одним из входов блока управления, а входы - соответственно к выходам первых и четвертых индикаторов и первым входам блоков сброса индикаторов, вторые и третьи входы которых соединены с одними из выходов блока управления, другие выходы блока управления подключены к уп равляюшим входам блоков установки индикаторов, информационные входы которых соединены соответственно с выходами первых и вторых индикаторов, входы четвертых индикаторов соединены со вторыми входами матрицы элементов памяти, выходы блоков сброса и установки индикаторов подключены к входам третьих индикаторов.На чертеже дана структурная схема предлагаемого устройства.Устройство содержит матрицу 1 элементов памяти, первые индикаторы 2, являюцие20 25 зо 3 4 О 4 50 зся индикаторами меток конца слов, вторые индикаторы 3, являющиеся индикаторами совпадения, блок 4 определения многозначного ответа, элемент ИЛИ 5, дополнительный элемент ИЛИ 6, счетчик 7, блок управления 8, дополнительный элемент ИЛИ 9, третьи индикаторы 10, являющиеся индикаторами разрешения опроса, блоки 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 соединены со вторыми входами матрицы 1, выходы блоков 11 и 12 подключены к вхолам индикаторов 1 О.Устройство работает следующим образом.Примем, что массив информации записывается в матрице 1 без пропуска строк; кодовую комбинацию в одной строке матрицы 1 обозначим оуквой. Тогда множество букв, соответствующих всем различным кодовым комбинациям, записанным в строках матри. цы 1, будем называть основным алфавитом Е Если в соответствии со структурой конкретного массива информации, записанного в матрице, некоторые строки в матрице выделить метками конца слова, то все кооные последовательности, начинающиеся с первой строки матрицы или со строк, непосредственно следующих за строками, выделенными метками конца слов, и до ближайшихпо возрастанию номеров) строк,выделенных метками конца слов, можно рассматривать как множество допустимых слов в алфавите Е Введем понятия дополнительного алфавита Р, расширенного алфавита К, которые определяются соотношением ЕоР и К = ЕпР, и понятие метки расширенного алфавита. Тогда слова из множества допустимых слов, содержащие букву, выделенную меткой расширенного алфавита, образуют множество слов, допустимых в алфаВите К. Под допустимым словом в алфавите К здесь понимается слово, которое получается посредством включения последовательности произвольной длины из букв алфавита Р перед буквой, выделенной меткой расширенного алфавита в любом слове и множества допустимых слов в алфавите ЕВ этом случае АЗУ должно осуществлять ассоциативный поиск для поисковых образов запросов, соответствующих допустимым словам как в алфавите Р, так и в алфавите К, Для слов в алфавите К должен выдаваться признак и определяться длина включенной последовательности букв из алфавита Р в соответствующее слово из множества слов, допустимых в алфавите ЕОтметим, что при описании работы устройства принято, что выход индикаторов 3 1-ой строки матрицы 1 соединяется с входом блока 12, соответствующего+ 1-ой строке матрицы 1, а выход индикаторов 21-ой строки матрицы 1, выделенной меткой конца слова, соединяется с входом блока 12 ) - 1-ой строки матрицы 1.Ассоциативное запоминающее устройство может работать в нескольких режимах,Режим 1. В этом режиме предполагается, что в индикаторы 21 не занесено ни одной метки расширенного алфавита, т. е. реализуется ассоциативный поиск только в массиве допустимых слов в алфавите ЕУстройство работает следующим образом. Г 1 о сигналу из блока управления 8 на первые входы элемента И 19, входящего в блоки 12, в том случае, если вторые входы элементов И 19 соединены с выходами индикаторов 2, в которых зафиксированы метки конца слов, с выхода элементов ИЛИ 18 выдается сигнал установки соответствующих индикаторов 10 и индикатора 10 первой строки матрицы 1. Затем через регистр маски 23 из регистра опроса 22 на первые входы матрицы 1 подается код очередной буквы слова, соответствук)щего поисковому образу запроса, лля которого производится ассоциативный поиск. После выполнения цикла обращения к матрице 1 блок управления 8 выдает сигнал сброса на первые входы элементов И 13 и 15, входящих в блоки 11. При этомсигнал опроса с ьыходов элемента И 15 через элемент ИЛИ 14 выдается на входы индикаторов 10, поскольку метки расширенного алфавита отсутствуют и на второй вход элемента И 15 через элемент НЕ 16 выдается сигнал, определяющий срабатывание этого элемента И. Затем если при выполнении цикла ассоциативного поиска для кола очередной буквы, подаваемого на вход регистра опроса 22, выполнялось хотя бы одно совпадение, что определяется сигналом с выхода элемента ИЛИ 5, то в случае, когда совпадение зафиксировано в строках матрицы 1, которые не выделены метками конца слов, что определяется отсутствием сигнала на выходе элемента ИЛИ 6, блок управления 8 выдает на первый вход элементов И 17 сигнал переписи в индикаторыО значений индикаторов 3, поступающих на вторые входы элементов И 17. После этого цикл ассоциаФорму.га изобретения тивного поиска повторяется для кода очередной буквы на входе регистра опроса 22. Если элемент ИЛИ 6 выдает признак совпадения в строке матрицы 1, выделенной меткой конца слов, по сигналу из блока управления 8 блок 4 формирует ответ. Затем АЗУ устанавливается в начальное состояние. Если элемент ИЛИ 5 не зафиксирует ни одного совпадения для очередной буквы на входе, устройство также устанавливается в начальное состояние.Режим 2. При работе в этом режиме предполагается, что в индикаторы 21 занесена хотя бы одна метка расширенного алфавита, т. е. может возникнуть необходимость в выполнении ассоциативного поиска слов в расширенном алфавите К. Устройство работает во втором режиме аналогично первому режиму до тех пор, пока ни на один из индикаторов 10, соответствующих строкам, выделенным метками расширенного алфавита, не поступит сигнал установки. Если такие сигналы поступили, с выхода элемента ИЛИ 9 выдается сигнал в блок управления 8, и устройство готово к работе во втором режиме, т, е. к ассоциативному поиску слов в множестве допустимых слов в алфавите й, Если для первой же (по времени) буквы, поступающей в регистр опроса 22, после перехода устройства во второй режим выдается сигнал совпадения, производится сброс индикаторов 10 и устройство находится в первом режиме до тех пор, пока элемент ИЛИ 9 не выдаст очередной сигнал, определяющий наличие разрешения выбора хотя бы одной строки, выделенной меткой расширенного алфавита в матрице 1.В том случае, если при переходе устройства во второй режим при поступлении очередных кодов в регистр опроса 22 сигнал совпадения не выдается, то, следовательно, на вход устройства поступает последовательность букв из алфавита Р, длина которой фиксируется счетчиком 7. При переходе устройства во второй режим сигналом, поступающим со второго выхода блока управления 8, счетчик 7 сбрасывается, а затем по мере поступления последовательности букв из алфавита Д с выхода блока управления 8 выдается последовательность импульсов, число которых соответствует числу букв в этой последовательности. При этом предполагается, что предельная допустимая длина последовательности букв в алфавите Р определяется блоком управления 8, и в том случае, когда она больше допустимого значения, слово, поступающее на вход регистра опроса 22, классифицируется как недопустимое слово в алфавите К, ассоциативный поиск прекращается, и устройство устанавливается в начальное состояние,До тех пор, пока длина последовательности букв в алфавите Р не превышает заданного предела, индикаторы 1 О, установленные в положение разрешения, в тех стро 1 о 15 зо 25 зо З 5 40 45 6ках, которые выделены четкой расширенного алфавита, не сбрасываются, поскольку сигнал сброса индикаторов 21 не выбрасывается блоками 11, соответствующими этим строкам, до тех пор пока на второй вход элементов И 13 не поступит сигнал из блока управления 8, формируемый при поступлении с выхода элемента ИЛИ 5 сигнала в блок управления 8. Таким образом, во втором режиме выполняется ассоциативный поиск допустимых слов в алфавите К.Режим 3. Необходимость в этом режиме возникает в том случае, если множество допустимых слов в алфавите Г расширяется следующим образом. Допустимыми словами считаются также слова, полученные из допустимых слов посредством приписывания справа букв из алфавита Е Тогда в третьем режиме ассоциативный поиск может быть продолжен после получения признака метки конца слова на выходе элемента ИЛИ 6, если длина слова не превышает заданного предела, без установки устройства в начальное состояние. При этом при переписи содержимого индикатора 3 в индикаторы 1 О, с помощью элемента НЕ 20 блокируется установка индикатора 10, соответствующего строке матрицы 1, непосредственно следующей за строкой, выполненной меткой конца слова, которая выдала сигнал совпадения на предыдущем цикле опроса. Ассоциативный поиск слов в расширенном алфавите позволяет увеличить быстродействие и функциональные возможности систем обработки дискретной информации в тех случаях, когда необходимо классифицировать слова в некотором алфавите, которые могут изменяться при включении в них в фиксированных местах произвольной последовательности букв другого алфавита, непересекающегося с основным.Наибольший эффект от применения предлагаемого устройства может быть получен в системах ввода - вывода информации в ЭВМ, в мультиплексных каналах и в специальных процессорах управления каналами связи. Ассоциативное запоминающее устройство содержащее матрицу элементов памяти, первые входы которой через регистр маски соединены с выходами регистра опроса, а выходы подключены к входам первых и вторых индикаторов, элемент ИЛИ, входы которого соединены с выходами вторых индикаторов и входами блока определения многозначного ответа, а выход - с блоком управления, соединенным со счетчиком, третьи индикаторы, выходы которых подключены ко вторым входам матрицы элементов памяти, отличающееся тем, что, с целью расширения области применения устройства,669410 Составитель В.ехред О. Луговираж 680 Рудаковая Корректор Г.Подписноеитета СССРткрытийя иаб д 4/5ул. Проектная, 4 Редактор Т. фадееваЗаказ 3668/43НИИ заро Ц ПИ Госудапо делам и 3035, Москва, Ж ал ППП Патеит рствекиого ком обретений и - 35, Раушска в, г, Ужгород,фи 7оно содержит четвертые индикаторы, блоки установки и сброса индикаторов и дополнительные элементы ИЛИ, выходы которых подключены к одним из входов блока управления, а выходы - соответственно к выходам первых и четвертых индикаторов и первым входам блоков сброса индикаторов, вторые и третьи входы которых соединены с одними из входов блока управления, другие выходы блока управления подключены к управляющим входам блоков установки индикаторов, информационные входы которых 10 соединены соответственно с выходами первых и вторых индикаторов, входы четвертых индикаторов соединены со вторыми входами матрицы элементов памяти, выходы блоков сброса и установки индикаторов подключены к входам третьих индикаторов.Источники информации, принятые во внимание при экспертизе1, Согпрцтег Ре 51 дК 191, том. 1 О и 1, с. 103 - 110.2. Авторское свидетельство СССР484562, кл. б 11 С 15/ОО, 1973.