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

(22) Заявлен 1.7821)2566755/18 м заявки М -присоединен23) Приоритет Опублико Дата опубл дарственный комитетСССРделам изобретенийи открытий по ано 25.05.80. Бюллетень М 19икования описания 2805.80(72) Авторы изобретени В.М.Трусфу Б. Матвеев 71) Заявитель й ордена Трудового Красного Знамени виационный институт им. А.Н. Туполев аз анс УСТРО СТ 54) АССОПИАТИВНОЕ ЗАПОМИ зи,одни входы каждого из которых ключены к одноименным первым раз ным шинам, а выходЫ - к предыдущ вторым разрядным шинам и к дру входам предыдущих блоков обрат связи,При этом, целесообразно блоки ратной связи выполнить в виде э тов И, входы и выходы которых п чены к соответствующим входам и ходам блоков обратной связи,Пусть в некотором запоминающе устройстве содержится и тп разря слов, в которых записаны ассоциа ные признаки гим ной щенаю облемен одклю вых ив-. Х -Х,ХХ мД а такж щ-разр 20 а яв- поние пос- азрядПри первые в поряПри ассоци выявля т,е, о тивных роса,ем, что старшие разрядЫ -и номера разрядов. возрастаютке убывания их веса,экстремальном поиске характертивных связей между признакамится в процессе самого поиска,требует сравнения ассоциапризнаков как с признаком опак и между собой. Изобретение относится к запоминающим устройствам.Известно ассоциативное запоминаюе устройство, содержащее запомищие регистры, регистр опроса,детекторы и компаратооы 11.Недостаток этого устоойства - отсутствие воэможности поиска по экстремальным условиям без применения алгоритмов, требующих многократногообращения к устройству.Наиболее близким техническим решением к данному изобретению являетсяассоциативное запоминающее устройство,содержащее элементы памяти, выходыкоторых подключены к одним из входовсоответствующих блоков сравнения,выходы и другие входы которых соединены с соответствующими разряднымишинами 23,Недостатком этого устройствляется повышенная сложность ижение быстродействия вследствиледовательной организации межрной обратной связи,Пель изобретения - упрощение устройство и повышение его быстродействия,Эта цель достигройство содержит б ается тем, что устлоки обратной свя имеется регистр, содержащиный признак опроса:(4) Появление то соотнетст признак равен11си гн ал 7;,ближайшим бол Оначение сигнала Е") определянт,г(ва процесса: образование едини 1 ногосигнала и его распространение, 5 ОЕдиница на втором логическом выходе К-того блока сравнения (КП 1,в ) -того слова образуется в томслч ае, если1) Е,. 1):1, т.е, во всех предыдуших разрядах з афи ксировано совпадение12) в данном разряде имеет место по -лсянительное несовпадение;3) среди остальных (п - 1) слов неттаких, в которых укаэанные в пп, 1 и 6 О2 ограничения (оба) выполнялись бын последуюших (младих) (гп-к) оаз -рядах,Таким образом, единица на второмлогическом выходе соответствую(их Ф 5 равным,Б данном устройстве, в отличие от известного, реализован сквозной перенос си гн ала1 (9 Полностью параллельная реазацияэкстремального поиска требует наличия распределительной логики (пхпблоков сравнения, связанных с соотнетствующими признаками разрядами),и, наряду с разрядыми и межраэрядными обратными св яз ями, нали чи япряы 1 х межразрядных связей междулогическими выходами предыдуих илогическими входали последуюших вслонах блоков сравнения,Осозначим Е - сигнал на первом3логическом выходе-того /на первомлогическом входе ) +1-ого) блока оран11нения 1-того слова; Е; - сигнална втором логическом выходе 3 -того(на втором логическом входе ) +1-ого)блока сравнения .-того слова, и будемназывать сонпадением выполнение внеКо 1 оро:1 блоке славно(ия логическойфунк(и) (1)При поиске по условиямбликайшее большееинаименьшеебудем азвать положительным несовпадением в,цопее в некотором блоке сравнения функции а приоритетои - 4 ункцииПри поиске по условиямближайшее менывееинаибольшеесоответствующиее фу н кци игалран"о 1 ах, где вор(дах зафиксировано сов падентак как задача состоит н распнии исходного сигнала1для любого 3.):1;. 11 1 блоков сравнения образуется в техсловах, где первое (старшее) в дан -ном слове положительно несонпаде -ние, при условии совпадения во всехпредыду(1(их разрядах, наступило неранее,. чем н любом другом слове:- 11 к1 . 1 1(1)1-.1 3.11Единица Е =1 не образуется ни в одном слове, если все слова либо равны признаку опроса, либо меные (при поиске ближайшего большего) или боль - ше признака опроса (при поиске бли - жайшего меньшего),Единица может образоваться в одно -именных К-тых разрядах несколькихслов (это означает, что старшие Кразрядов хранимых ассоциативныхпризнаков равны), Однако последуюниеразряды признаков могут быть раэ -личными,нОигнал Е (0 К) ранен1в10тех словах, где.( (1.,2) в ланном разряде имеет. местоприоритет,Если пп, 1 и 2 (оба) не выполня - ются ни в одном слове, то Е, =1 во всех слонах, где выполняется условие и. 1; Объединяя процессы образованияи распространения единицы 7,;( =1получим: 11 1)-1 1 (,1 (-) 1 Р 1 Рф 1 си гн ала Е;, =1 означает,вуюий ассоциативныйпризнаку опроса, а=1, что он являетсяьшим (меньшим), но не Для аппаратной реализ ации з кстремального поиска необходимо построить комбинационную логическую сеть,. реализуюую для каждого разряда функции (4) и (7),На фиг, 1 изображена структурнаясхема ассоциативного з аполя наюше го(9) иН -Ч 7; Усяр иста (без целей записи, считывания), на Ьиг,2 - функциональнаясхема блоков сравнения.Устройство (фиг.1) содержит и х щэлементов 1 памяти, выходы 2 которыхприсоединены к приэчаконым входамсоответствующих блоков 3 сравнения,межразрядные шины 4, соединяющиелогические выходы и входы предыдущих и, соответственно, последующихблоков сравнсния (я)-1) первых 5,щ вторых 6, щ третих 7, и) четнертых8 разрядных шин и (и - 1) блоковобратной связи, например, элементов И 9, одни нходы которых подключены к одноименным первым разряднымшинам 5, а выходы присоединены к предыдущим вторым разрядным шинам 6 и кдругим входам предыдущих блоков 9обратной связи.Межразрядные 4 и четвертые разрядные шины 8-двухфазные. Каждый блок 3сравнения (фиг,2) представляет собойкомбинационную логическую схему,содержащую элементы И 10-14,элементы ИЛИ 15и 16 и элементы НЕ 17 и 18 и имеетпервый 19 и второй 20 входы опроса,первый 21 и второй 22 логическиевходы, первый 23 и второй 24 логические выходы, выходы разрядной 25 имежразрядной 26 обратной связи,входы разрядной 27 и межразрядной 28обратной связи и первый 29 и второй30 входы опроса,Устройство работает следующимобразом.Запись и считывание в устройствемогут быть организованы любым изизвестных способов.При поиске ближайшего большего(наименьшего) в исходном состояниина первый 19 и второй 20 признаконые входы 1 -того блока 3 сраннения 1-того слова поданы прямое иинверсное значения Х; и Х соответствуюего ассоциативного приз -нака, а на первый 29 и второй 30входы опроса поданы прямое и инверсное значения 1 и Э 1-того разряда признака опроса, Предположим,что на первый 21 и второй 22 логические входы поданы сигналы 2 (, и2;(1 1),ОПРЕДЕЛЕННЫЕ СОГЛаСНо фОрМуЛам(4) и (6),на вход разрядной обратнойсвязи 27 подан сигнал а на вход межразрядной обратной связи - си гн ал Я,Ропределенный согласно (8),Тогда на первом 23 и втором 24логических выходах реализуются функции, соответственно:а - 213-1)(х 1) (1 ч х 1) 1,1) 1) ) )+11(; 1)(хЧН Учитывая (1) - (4), (7) - (9) получим1Ф,а =2 , и а =2 . На выходе разряднойобратной связи 25 реализована функ 1 иЯ третья разрядная шина 7 выполняетфункцию монтажного И, поэтомусигнал на ней И у)ц - ( 7. 1ч 2-.Я т.е.предположение о сигнале на входе разрядной обратной связи 27 справедливо. На выходе межразрядной обратнойсвязи 26 реализована функций первая разрядная шина 5 выполняетфункцию монтажного И, поэтому сигнал на ней25н 13 = 5 1 Ч 2;()Х"ЧМожно показать, что сигнал на выходе соответствующего блока обратной связи 9 ьС= ч (ч . 1(р) р,=8 1 Л Р)1и является сигналом на входах межразрядной обратной связи 28 (-1)-ыхблоков Б равнения, что также подтверждает сделанное выше предположение. Для полного соответствия математической модели (4) и (7) и аппаратной реализации экстремального поиска необходимо определить начальные условия, Так как признаки имеют в известных разрядов, следует считать, что незаданные разряды, старшие первого и младшие щ-того, равны у всех признаков, откуда следует, что8 виЕ" = Е" =0 для любого1 О От.е. при поиске на второй вход последнего блока 9 обратной связи (на последнюю третью разрядную шину 7) и на первые логические входы 21 первых блоков 3 сравнения должны быть поданы логические1,а на вторые логические нходы 22 первых блоков 3 сравнения - логические040 Описанное устройство, кроме общего с известным устройством оборудования, содержит (и)-1) элементов И, которые в аппаратном отношении заменяют и (щ) элементов ИЛИ и и (в) элементов НЕ, т.е.оно проще изнест 736171ного, Чакже оно является и более быстродействующим.Формула изобретения1, Ассоциативное запоминающее устройство, содержащее элементы памяти, выходы которых подлчны к одн иэ входов соответствующих блоков сравнения, выходы и другие входы которых соединены с соответствующими разрядными шинами, о т л и ч а ющ е е с я тем, что, с целью повыщения быстродействия и упрощения устройства, оно содержит блоки обратной свяэир одни входы каждого иэ ко " торых подключены к одноименным первым раэоядным шинам, а выходы - к предыдущим вторым разрядным щинам и кдругим входам предыдущих блоковобратной связи,2, Устройство по п,1, о т л ич а ю щ е е с я тем, что блокиобратной связи, выполнены в видеэлементов И, входы и выходы которыхподключены к соответствующим входами выходам блоков обратной связи,1 ОИсточники инФормации,принятые во внимание при экспертизе1, Авторское свидетельство СССРУ 277857, кл,С 11 С 15/00, 1970,2. Авторское свидетельство ГССРР 564656, кл,Г 11 С 15/00, 1975 (про 15 тотип),/36171 Составитель В.Рудаковаактор В,Зарванская ТехредМ,Кузьма Коррект азарова Зака филиал ППП фПатентф, г.ужгород, ул,Проектная,4 22 78/8 Тир ЦНИИПИ Государственн по делам изобретени 3035, Москва, Ж, аж 662 Подписного комитета СССРи открытийаушская наб.,д,4/5