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

ОП ИОАНИЗОБРЕТЕН К АВТОРСКОМУ СВИДВТВЛЬ Союз СоветскихСоциалистическихРеспублик И Е ИЯ 11651416 ВУ(61) Дополнительное к авт (22) Заявлено 01.09.76(21 ву) М. Кл. О 11 С 15/О 97807/18-2 присоединением заявкиооударотвеиный номнте СССР оо делам изобретений и открытий(71) Заявитель НАЮЩЕЕ УСТРОИ Из известных устройств наиболее близким по технической сущности к изобретению является ассоциативное запоминающее устройство, содержащее первый регистр, основные и дополнительные элементы памяти, выходы которых подключены ко входам соответствующих индикаторов совпадения с признаками опроса, выходы которых подключены ко входам элементов ИЛИ первой и второй групп, при этом выходы элементов ИЛИ первой группы подключены к одним входам элементов И первой группы, другие входы которых через элементы НЕ первой группы соединены с выходами элементов ИЛИ второй группы, первые входы элементов И второй группы подключены к выходам основных элементов памяти, а выходы - ко входам элементов ИЛИ третьей группы, выходы которых подключены соответственно ко входам второго регистра 2.Недостатком этого устройства является то, что в нем признаковая информация заранее жестко записывается в памяти (перед извлечением ее из памяти), затем постоянно в ней хранится и не меняется в ходе работы устройства, какие бы изменения в наборах Недо то, что о чающих ет досто вием чег самоорга шению к признако статком этого уст но при маскирова признаков (событи ейного выбора ин о является отсутс низации при запи ранее записанным вой информации. роиствании взаим й) не обе формации твие возм си новых в память является оисклюспечива- , следстож ности по отно- наборов(54) АССОЦИАТИВНОЕ ЗА Изобретение относится к автоматике, Известны ассоциативные запоминающие устройства, в которых хранятся слова, любая часть которых выступает в качестве ассоциативного признака, а другая часть -- в качестве основной информации, а также регистра опроса, регистр маски, выходной регистр и индикаторы по одному на каждую ячейку . Так как в этом устройстве разряды признаков перемежаются разрядами основной информации, при опросе регистр маски маскирует разряды основной инфор= мации, чем обеспечивается сравнение разрядов признаков опроса только с ассоциатив ными признаками слов. Г 1 ри этом по замаскированным разрядам признаков опроса сигнал несовпадения не вырабатывается,а Енту . ".3 ь 4 гф 1 с , 1 р16 6514 3признаковой информации на выходе регист,.ра признаков опроса не происходили, что существенно сужает область применения устройства.: Целью изобретения является расширениеобласти применения устройства. Поставленная цель достигается тем, чтоустройство содержит блок памяти, третий и четвертый регистры, последовательно соединенные первый и второй элементы задержкии соответственно третий и четвертый элементы задержки, блоки местного управления1коммутаторы, третие, четвертые и пятые группы элементов И, элементы ИЛИ и НЕ, приэтом входы первого, второго, третьих и четвертых блоков местного управления соединены с выходами основных элементов памяти, выходы третьих и четвертых блоков местного управления соединены соответствен.но со входами четвертого и третьего регистров, выходы блока памяти соединены с первыми информационными входами первого и второго коммутатора, выходы третьего регистра соединены со вторыми информационными входами первого и второго коммутатора, а выходы четвертого регистра подключены к третьим информационным входам второго коммутатора и к информационным входам третьего коммутатора, выход первого блока местного управления соединен с одним входом первого элемента ИЛИ, другой вход которого через первый элемент НЕ соединен с выходом второго элемента ИЛИ, входы которого соединены с выходами элементов И первой группы, выход первого блока местного управления подключен ко входу первого элемента задержки и к одному входу третьего элемента ИЛИ, другой вход которого 35 подключен к выходу второго блока местного управления и ко входу третьего элемента задержки, а выход через второй элемент НЕ - к одним входам элементов И третьей группы, . другие входы которых подключены к выходам соответствующих элементов И первой4 О группы, а выходы - ко вторым входам элементов И второй группы, выходы первого и третьего элементов задержки соединены соответственно с первым и вторым управляющими входами первого коммутатора, а так же со входами четвертого элемента ИЛИ, выходы второго и четвертого элементов задержки и четвертого элемента ИЛИ соединены соответственно с первым, вторым и третьим управляющими входами второго коммутатора, управляющий вход третьего коммутатора соединен через пятый элемент ИЛИ с выходами второго и четвертого элементов задержки, выход второго элемента задержки соединен со входами блока памяти, выходы первого коммутатора соедине- ы ны с одним из входов элементов И четвертых групп, другие входы которых соединены с выходами соответствующих четвертых коммутаторов, а выходы соединены поразрядно с соответствующими основными элементами. памяти, выходы второго коммутатора соедииены с первыми входами элементов И пятых групп, со вторыми входами которых через элементы НЕ вторых групп соединены основные элементы памяти, а с третьими входами- соответствующие выходы четвертых коммутаторов, выходы элементов И пятых групп подключены ко входам соответствующих дополнительных элементов памяти, первые информационные входы четвертых коммутаторов соединены с выходами первого регистра, а вторые информационные входы подключены к выходам основных элементов памяти соответствующего разряда, первые управляющие входы четвертых коммутаторов через третий элемент НЕ соединены с выходом пятого элемента ИЛИ, а вторые управляющие входы - с соответствующими выходами третьего коммутатора, входы блоков местного управления соединены с выходами четвертых коммутаторов. На чертеже изображена структурная схема предложенного устройства.Устройство содержит основные элементы 1 памяти, ячейки 2 памяти для хранения первых ассоциативных признаков, дополни. тельные элементы 3 памяти, ячейки 4 памяти, индикаторы 5, элементы ИЛИ 6 первой группы, элементы ИЛИ 7 второй группы, элементы И 8 первой группы, элементы НЕ 9 первой группы, элементы И 10 второй группы, элементы ИЛИ 11 третьей группы, первьй регистр 12, второй регистр 13, блок 14 памяти, служащий для хранения начального адреса свободной зоны памяти, третий регистр 15, четвертый регистр 16, первый блок 17 местного управления, второй блок 18 местного управления, третьи блоки 19 местного управления, четвертые блоки 20 местного управления, первый элемент 21 задержки, второй элемент 22 задержки, третий элемент 23 задержки, четвертый элемент 24 задержки, первый коммутатор 25, второй коммутатор 26, третий коммутатор 27, четвертые коммутаторы 28, элементы И 29 третьей группы, элементы И 30 четвертых групп, элементы И 31 пятых групп, элементы НЕ 32 вторых групп, первый элемент ИЛИ 33, первый элемент НЕ 34, второй элемент И,ЛИ 35, третий элемент ИЛИ 36, второй элемент НЕ 37, четвертый элемент ИЛИ 38, пятый элемент ИЛИ 39 и третийэлемент НЕ 40. Одни входы индикаторов 5 соединены с выходами соответствующих основных и дополнительных элементов памяти, а другие входы - с выходами четвертых коммутаторов 28, подключенных по первым информационным входам к выходам соответствующих разрядов первого регистра 12, хранящего признаки опроса,651416 45 Входы блоков 17 - 20 соединены с выходами основных элементов памяти 1. и четвертых коммутаторов 28. Элемент ИЛИ 33 по выходу соединен со входом первого элемента задержки 21 и со входом элемента ИЛИ 36, а по входу - с выходом блока 17 и через элемент НЕ 34 с выходом элемента ИЛИ 35, входы которого подключены к выходам элементов И 8.Выход блока 18 соединен со входом третьего элемента 23 задержки и со вхо О дом элемента ИЛИ 36, подключенного по выходу через элемент НЕ 37 к одним входам элементов И 29, другие входы которых соединены с выходами элементов И 8, а выходы - с одними входами соответствующих элементов И 10, другие входы которых соединены с выходами соответствующих основных элементов памяти 1, а выходы поразрядно через элементы ИЛИ 11 - со входами второго регистра 13. Выходы блоков 19 и 20 соединены соответственно со входами регистра 16 и 15.Выходы блока 14 и регистр 15 соединены соответственно с первыми и вторыми информационными входами коммутаторов 25 и 26, а выходы регистра 16 - с третьимыиыформационными входами коммутатора 26 и с информационными входами коммутатора 27.Элемент 21 задержки соединен по выходу с первым управляющим входом коммутатора 25, со входом элемента 22 задержки и со входом элеменат ИЛИ 38, другой вход которого подключен к выходу элемента задержки 23 и ко входу элемента задержки 24, а выход - к третьему управляющему входу коммутатора 26, первый и второй управляющие входы которого подключены соответственно к выходам элементов задержки 22 и 24 и ко входам элемента ИЛИ 39, выход которого соединен З 5 с управляющим входом коммутатора 27 и через элемент НЕ 40 с первыми управляющими входами коммутаторов 28, вторые информационные входы которых соединены с выкодами элементов 1 памяти соответствующих раз О рядов. Выходы коммутаторов 25-27 соединены соответственно со входами элементов И 30, И 31 и со вторыми управляющими входами коммутаторов 28, подключенных по выходу к другим входам элементов И 30 и 31. ;Чри этом элементы И 30 по выходу подключены ко входам элементов 1, а элементы И 3 в ко входам элементов 3, причем третьи входы элементов И 31 соединены через элементы НЕ 32 с выходами элементов памяти 1.50Перед началом работы устройства во всех ячейках 2 и во всех ячейках 4 хранятся нулевые значения ассоциативных признаков. При формировании сигнала опроса и при наборе признаков на выходе регистра 12, 55 в котором, например, единицы находятся на выходе 1-го, 2-го, 3-го и 6-го разрядов регистра, т. е. набор признаков соответству 6ет коду 000000100111, ассоциативные признаки опроса через открытые по первым управляющим вхОдам вентили (на чертеже не показаны) четвертых коммутаторов 28 (сигнал на выходеэлемента НЕ 40- е) поступают на индикаторы 5, а также на входы блоков 17-20 и на первые входы элементов И 30 и И 31 четвертых и пятых групп.На выходе блока 4 памяти после приведения устройства в исходное состояние сформирован адрес первой ячейки, При этом ни один из индикаторов 5 не срабатывает, так как ни в одном из элементов 1 и 3 нет значения с, совпадающего с поступающим с регистра 12 с соответствующего разряда значением в: Поэтому ни один из элементов ИЛИ 6 первой группы не формирует значение 1, вследствие чего ни один из элементов И 8 первой группы также не формирует значение х, а на выходе элемента ИЛИ 35 формируется 0, по которому сигнал с выхода элемента НЕ 34 через элемент ИЛИ 33 поступает на вход элемента 21 задержки, задерживающего данный управляющий сигнал на один такт.. При этом в первом такте обращения ни один из блоков 19 и 20 не срабатывает,так как еще ни одна ячейка не попала в занятую зону, поэтому регистр 16 во все последующие такты обращения остается в нулевом состоянии.Во втором такте сигнал с выхода элемента 21 задержки поступает на первый управляющий вход первого коммутатора 25, через который по сформированному на выходе блока 14 адресу разрешает запись информации через элементы И 30 в основные элементы 1 первой ячейки, в результате чего в эту ячейку записывается код 00000010011. В третьем такте по сигналу с выхода элемента 22 задержки и по нулевым значениям с выходов третьего коммутатора 27 (регистр 16 в нулевом состоянии) запрещается срабатывание коммутаторов 28 соответственно как по первым, так и по вторым управляющим входам, вследствие чего в дополнительные элементы 3 первой ячейки информация не записывается, в то же время в блоке Я по сигналу с элемента 22 задержки формируется следующий по порядку адрес ячейки, т. е. адрес второй ячейки устройства ( блок 14 может представлять собой обычный сдвигающий регистр, в котором в конце каждого цикла обращения к устройству, где выполняется запись информации в новую ячейку, т. е. первую ячейку свободной зоны, производится сдвиг единицы на один разряд с формированием следующего адреса начала свободной зоны),Далее при формировании в следующем цикле обращения к устройству на выходе регистра 12, например, кода 000001001100 срабатывает блок 17, выявляющий в первой ячей7ке относящейся в этот момент уже к занятойзоне, в 1-ом, во 2-ом и 6-ом разрядах единиц, которых нет на выходе регистра 2. Поэтому коду срабатывает также относящийсяк первой ячейки блок 19, который запускаетсоответствующий адресу первой ячейки первый разряд регистра 16.Во втором такте,аналогично записиосновных признаков в первую ячейку, производится запись единиц в элементы 1 второйячейки в З-ий, в 4-ый и в 7-ой разряды, т. е. записьгвается указанный выше код 00000100110, ОВ то же время, по сигналу 1 на третьем управляющем входе второго коммутатора 26,поступающему с выхода элемента ИЛИ 38,и по сигналу 1 на третьем информационном входе первого разряда этого коммутатора, поступившему с выхода первого разряда регистра 16, разрешается запись единич-,ных значений с выхода регистра признаковопроса в дополнительные элементы 3 первойячейки через соответствующую группу элементов И 31 только в те разряды, в которых 20в основном элементе 1 нет поступающей срегистра признаков опроса единицы, т, е. в4-ый и в 7-ой разряды,В третьем таке по сигналуна первом управляющем входе коммутатора 26 ина первом информационном входе 2-го разряда этого коммутатора, а также по сигналузапрета на первых управляющих входах четвертых коммутаторов 28 и сигналам 1 науправляющем входе третьего коммутатора иинформационном входе первого разряда это- ЗОго коммутатора обеспечивается аналогичнозаписи в первую ячейку; запись ассоциативных признаков в дополнительные элементы 3второй ячейки. Только ассоггиативные признаки поступают не с выхода регистра призна- з35ка опроса, а с выхода основных элементов 1первой ячейки. При формировании в следующем циклеобращения на выходе регистра12 кода 00001000101 этот код аналогично предыдущему, запишется в третью ячейку в элементы 1, а одновременно выбираемые в первом такте данного цикла обращения запишутся единицы в элементы 3 восьмого разряда обеих ячеек. При этом в третьем такте в элементы 3 третьей ячейки в З-ий, в 6-ой и в 7-ой разряды запишутся значения 1.Аналогично, в следующем цикле обращения при формировании на выходе регистра 12 кода 110100001010 запишутся основные и до полнительные признаки в четвертую ячейку и новые дополнительные признаки в первую, во вторую и в третью ячейки. Единственнымотличием является то, что из-за-утсгайовленных в предыдуших циклах между первыми тремя ячейками взаимозапретов ни один из элементов И 8 не срабатывает, вследствие чего запуск элемента 21 задержкии последугцая запись будут обеспечиваться-посигна. л у , форм ируе мому н а выходе элементаНЕ 34,В следующем цикле при формированиикода признаков опроса 01000100111 срабатывает блок 18, выявляюгций отсутствие приопросе в первой ячейки в 10-ом и в 11-омразрядах поступающих с регистра признаковопроса единиц при совпадении информациипо остальным разрядам, а также срабатывает относящийся к первой ячейки блок 20, который переводит первый разряд регистра 15в еди ни цу.Далее, аналогично предыдущим циклам,в первую ячейку записываются новые основные признаки в 1 О-ый и в 11-ый разряды, ав четвертую ячейку (из-за совпадения хранящейся в ней в 11-ом разряде единицы восновном элементе памяти с единицей 11-горазряда, поступающей с регистра 12) записываются соответствующие признаки в дополнительные элементы памяти. Единственным отличием является то, что во втором и втретьем тактах обращения к устройству к элементам И 30 и И 31 соответствующих ячеекчерез коммутаторы 25 и 6 подключается неблок 14, а регистр 5.В конце всех циклов обращения к устройству регистры 15 и 16 обнулятся.В режиме считывания информации выбирается всегда только одна ячейка (ячейки,совпадающие по отдельным признакам сосчитываемой, заблокированы по записаннымв дополнительные элементы 3 ячеек признакам), при этом по несрабатыванию блоков 17и 18 и отсутствию сигнала 1 на выходе элемента НЕ 34 производится считывание информации из ячейки через соответствующиеэлементы И 10 и ИЛИ. 11 в выходной регистр13.При этом срабатывают относящиеся кданной ячейке элемейты ИЛИ 6 и И 8 и несрабатывают соответственно элементы ИЛИ7 и НЕ 9, так как ни в одном из элементов 3по опрашиваемым признакам не записаны 1,Например, по кодам признаков опроса000000000111, 000000100000 и 011000000000считывается содержимое первой ячейки, и,следовательно, те хранящиеся в ней признаки, которые отсутствуют в коде признаковопроса. По кодам признаков спроса 110000001010 и 000100000000 считывается, например, четвертая ячейка. Аналогично считываются и другие ячейки. При этом в другом варианте конкретного исполнения в устройстве дополнительно может быть использована обычная адресная система, обеспечивающая запись и считывание из устройства по адресу на входе.Изобретение позволяет для самых различных наборов ассоциативных признаков, формируемых на выходе первого регистра и изменяющихся во времени самым различным об25 щими основными элементами памяти, выходы второго коммутатора соединены с первыми входами элементов И пятых групп со вторыми входами которых через элементы НЕ вторых групп соединены основные элементы 30памяти, а с третьими входами - соответствующие выходы четвертых коммутаторов, выходы элементов И пятых групп подключены ко входам соответствующих дополнительных элементов памяти, первые информационные З 5 входы четвертых коммутаторов соединены с 50 разом, обеспечить самоорганизацию при записи этих признаков как в свободные ячейки, так и в свободные разряды ячеек, за счет выявления отличий между информацией на входе памяти и информацией, ранее записанной в память. формула изобретенияАссоциативное запоминающее устройство,содержагцее первый регистр, основные и дополнительные элементы памяти, выходы которых подключены ко входам соответствующих индикаторов, Выходы которых соединены со входами элементов ИЛИ первой и второй групп, при этом выходы элементов ИЛИ первой группы подключены к одним входам элементов И первой группы, другие входы которых через элементы НЕ первой группы соединены с выходами элементов ИЛИ второй группы, первые входы элементов И второй группы подключены к выходам основных элементов памяти,а выходы - ко входам элементов ИЛИ третьей группы, выходы которых подключены соответственно ко входам второго регистра, отличающееся тем, что, с целью расширения области применения устройства, оно содержит блок памяти, третий и четвертый регистры, последовательно соединенные первый и второй элементы задержки и соответственно третий и четвертый элементы задерж ки, блоки местного управления, коммутаторы, третие, четвертые и пятые группы элементов И, вторые группы элементов НЕ, элементы ИЛИ, и НЕ, при этом входы первого, второго, третьих и четвертых блоков местного управления соединены с выходами основных элементов памяти, выходы третьих и четвертых блоков местного управления подключены соответственно ко входам четвертого и третьего регистра, выходы блоков памяти соединены с первыми информационными входами первого и второго коммутатора, выходы третьего регистра соединены со вторыми информаицонными входами первого и второго коммутатора, а выходы четвертого регистра подключены к третьим информационным входам второго коммутатора и к информационным входам третьего коммутатора, выход первого блока местного управления соединен с одним входом первого элемента ИЛИ, другой вход которого через первый элемент НЕ соединен с выходом второго элемента ИЛИ, входы которого соединены с выходами элементов И первой группы, выход первого блока местного управления подключен 5 10 15 20 ко входу первого эл.мента задержки и к одному из входов третьего элемента ИЛИ, другой вход которого подключен к выходу второго блока местного управления и ко входу третьего элемента задержки, выход через второй элемент НЕ - к одним входам элементов И третьей группы, другие входы которых подключены к выходам соответствующих элементов И первой группы, а выходы - ко вторым входам элементов И второй группы, выходы первого и третьего элементов задержки соединены соответственно с первым и вторым управляющими входами первого коммутатора, а также со входами четвертого элемента ИЛИ, выходы второго и четвертого элемента задержки и четвертого элемента ИЛИ соединены соответственно с первым, вторым и третьим управляющими входами второго комму. татора, управляющий вход третьего коммутатора соединен через пятый элемент ИЛИ г выходами второго и четвертого элементов задержки, выход второго элемента задержки соединен со входом блока памяти, выходы первого коммутатора соединены с одними из входов элементов И четвертых групп, другие входы которых соединены с выходами соответствующих четвертых коммутаторов, а выходы соединены поразрядно с соответствуювыходами первого регистра, а вторые информационные входы подключены к выходам основных элементов памяти соответствующего разряда, первые управляющие входы четвертых коммутаторов через третий элемент НЕ соединены с выходом пятого элемента ИЛИ, а вторые управляюгцие входы - с соответствующими выходами третьего коммутато-,ра.,входы блоков местного управления соединены с выходами четвертых коммутаторов. Источники информации, принятые во внимание при экспертизе1, Крайзмер Л. П, и др. Ассоциативные запоминающие устройства. Л., Энергия, 1967, с. 34-37.2. Заявка2359707/24, кл. б 11 С 5/00,1976, по которой принято решение о выдачеавторского свидетельства,651416Составитель В. РудакТехред О. ЛуговаяТираж 680 овска ЦНИИПИ Государствпо делам изобр113035, Москва, Ж.З илиал ППП Патент,нного комитета ССетений иоткрытийРаушская наб дУжгород, ул. Про 4/5 ктндя