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

(57) Изобретлительной те астност нике и институт запокин ающим я яв троиствам, Целью изо тся повыпее быстро дейте тва, Устый блок- числов матриц устроис текторн иство с ство СССР 00, 1968, во СССР 00, 1978,матриц строк и и ) заломи сло столб и юпих злемеап ригВе гевФ е ф феГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ ИСАНИЕ ИЗОБРЕТЕН1316048 блоки 3 -Зп сравнения, регистрпризнаков опроса, блоки 5 -5 адержки, сумматоры 7, -7 с инфо рмдионными входами 13-13 и выходами 12 -12и блок 8 поиска максимума совпадений,который содержит матрицу ячеек ассоциативной памяти. Каждая ячйка ассоциативной памяти содержит два элемента НЕ, элемент ИЛИ-Ш; и четыре элемента И, В запоминающих элеис.нтах 2находятся ассоциатиггныс григгаки,которые сравниваются в б оках 3-Зсг 1 ризнаками опроса, со;с ржаг.имися врегистре 4, При их совпадении на выходе блока 3 появляется сигчсал "1",который обе спечиватрокск;гениссигнала "1" с входа блока 5 задержки данной строки на егс вггход и навход следующего в стобцс б лока 5задержкиВо всех сумматорах 7 -7одного столбца подсчитьпаетс суммапо модулю 2 (где е - чело информа -Изобретение относитс к вычислительной технике, в частности к запоминающим устройствам.Целью изобретения является повышение быстродействия устройства,На фиг.1 представлена функциональная схема предложенного устройства; на фиг, 2 - 5 - функциональные схемы соответственно блока поиска максимума совпадений, ячейки ассоциативной памяти, блока задержки и сумматора.Устройство содержит (фиг.1) детекторный блок 1, матрицу ш х п, где ш - число строк и и - число столбцов матрицы запоминающих элементов 2, блоки 3, -3 сравнения, регистр 4 признаков опроса, блоки 5, -5 задержки с первыми входами 6, сумматоры 7 -7 и блок 8 поиска максимума совпадений.На фиг.1 обозначены вторые входы 9,-9, выходы 10,-10, третьи входы 11-11 блоков 5-5 задержки, выходы 12,-121 г и входы 13 -13 сумматоров 7-7 , четвертые входы 14 блоков 5-5задержки.Блок 8 поиска максимума совпадений содержит (фиг,2) матрицу ячеек 15 ассоциативной памяти с первыми ционных входов каждого сумматора 7)единичных сигналов несовпадения.Сигналы "1, поступающие с выходовблока 5 п и сумматора 7 п какого-либостолбца на входы блока 8, разрешаютработу ячеек ассоциативной памятив соответствующем столбце, Сигнал"0" на выходе блока 5 п какого-либостолбца исключает из поиска соответствующий столбец ячеек в блоке 8,Так как с выходов каждого сумматора7 п поступает в блок 8 остаток от де.ления К/2 в инверсном виде (где Кчисло несовпадающих разрядов признаков опроса и ассоциативных признаков), то в блоке 8 осуществляетсяпоиск минимального остатка от деления, Устройство обеспечивает поискближайшего по образу слова зе меньшее, чем К число тактов, за счетчего повышается его быстродействие,2 з.п.ф-лы, 5 ил., 1 табл. выходами 16, управляющими входами7 и вторыми выходами 18, Каждаяячейка 15 ассоциативной памяти содержит (фиг,3) первый элемент НЕ 19,первый 20 и второй 21 элементы И,элемент ИЛИ-НЕ 22, третий 23 и четвертый 24 элементы И второй элементНЕ 25, На фиг,2 и 3 обозначены разрядные шины 26 блока 8 поиска макси 10 мума совпадений, Каждый блок 5 задержки фиг.4 может содержать, например, двухступенчатый синхронныйР-триггер 27, элемент 28 ИЛИ и элементы И 29 и 30, Каждый сумматор 7содержит (фиг,5) элементл 31, -31равнозначности (где 11 о ш/2) иэлементы ИЛИ 32 -32 , Запоминающиееэлементы 2 могут быть выполнены иэсинхронных одноступенчатых В-тригге 20 ров,Устройство работает следующим образом.В исходном состоянии в регистре254 (фиг.1) находится приэнак опроса,в вертикальных линейках их синхронных одноступенчатых 0-триггеров 2находятся ассоциативные признаки,триггеры 27 находятся в улевом стабильном состоянии. На вход 6 эле 30группы количество нулей, поступающихс входов 6 блоков 3, равно 2 (вкрайней верхней группе - 4 21).Единица, поступившая по входу 9, распространяется внутри группы по элементам И 29 блоков 5,-5 до границы. 55 3 360 мента ИЛИ 28 (Фиг.4) и сумматора 7и входы 13 действует уровень логи 1 11ч е ско г о 0 , если с о с то яние соот в е те тв ующих запоминающего эл еме н т а 2 и разряда регистра 4 и е с о вп адают , 5 или - " 1 " , е сли совп ад дют . На входы 9 всех блоков 5 и входы3, сумматоров 7 подается константа " 1 " . Е сли с выхода какого -либо блока 3 по выходу 6 поступает сигнал " 1 " ( ра з -0 р яды совпадают) , т о этот си г н ал и роходит через элемент ИЛИ 2 8 на вход элемента И 2 9 и разрешает и похожд ение сигнала с входа 9 н а выхо д 1 О блока 5 . Этот же сигнал ( "" ) и о ст упает на вход элемента ИЛИ 3 2, со о т. в е т с тв ующег о сумматора 7 ( фи и . 5 ) , пройдя через него поступает н д входы элементов равнозначности 3 1 и элементов ИЛИ 3 2 2 и та к дал е е , т . е , 20 если на вход 6 элементов р а в но э начности 3 1, -3р поступает си гн дл "" , в этом случае на вых оды 1 2 сумма тора 7 проходит информация с е го в х одов 1 3, - 1 3Если по вхо ду 6 поступает сигнал 11011 (разряды не совпада ют), то в сумматоре 7 происходит прибавление единицы к коду, представленному в инверсном виде, посту- лающему по входам 13 -13 с выдачей1 Ррезультата (в инверсном виде) на выходы 12-12В столбцах иэ сумматоров 7, -7 происходит подсчет по ме 1 дулю . сигналов несовпадения, поступающих с 35соответствующих блоков 3, Если код, поступающий по входам 13 в сумматор 7, не равен "0" (имеется хотя бы одна единица), то на выходе последнего элемента ИЛИ 32 этого сумматора 40 7 появляется "1", которая, пройдя через вход 11 на элемент ИЛИ 28 блока 5, поступает на вход элемента И 29 (Фиг.4) и соответственно на выход 1 О этого блока 5 проходит сиг нал с входа 9. Столбец иэ сумматора7 -7 делится на группы, внутри группы значение выходов 11 (элементов ИЛИ 32) равно "1", а на границах групп равно "0", так как код на вхо дах 13, сумматора 7 равен "0" и по входу 6 проходит "0". Внутри 48Первый сигнал, пост уц 11 вг;ип нд вес элементы И 30 блоков 5, -5 , установит в триггерь. 27 блоков 5 первой группы, включая и грдничный блок 5, тем самым разрешает прохождение единицы с вхолд 9 блока 5 нд выход 10 этого же блока 5 в следующую группу. 1 усть, например, имеется два столбца с наименьшим количеством групп (например, 8=3), Если 1 = 3, К - количество несовпавших разрядов (К=25, К =26), то после трех тактов сигнал единицы появится на выходах 1 О крайних верхних блоков 5 этих столбцов, С 1 дыходов 2,сумматоров 7 этих столбцов в блок118 поступят соответственно коды чисел К - 2 Б и К., - 2 8 (т,е. единицы и двойки) в инверсном виде,Гдиницы, поступающие с выходов 1 О блоков 5 этих столбцов, поступают нд входы 7 блока 8, разрешдя его рабо - ту в соответствующих столбцахЕсли на вход 17 ячейки 15 (фиг.2) поступает сигнал 11011, то через элемент НЕ 19 он отпирает элемент И 21 и на выход 16 с шины нулевого потенциала поступает "0", тем самым соответствующий столбец в блоке 8 исключается иэ поиска и на выходе 6 крайней верхней ячейки 15 блока 8 появится сигнал "0". Если на вход 17 поступает "1", то она через элемент НГ 19 запирает элемент И 21. Единичный сигнал с одного из входов 12 отпирает элемент И 23, через который единица входа 17 поступает на выход 16. Если оказалось, что в строке ячеек 15 блока 8 на входы 2,-12 всех ячеек, у которых на входе 17 действует сигнал 1", поданы сигналы "0", то сигнал "1" с входов 17 проходит через элемент И 24 на выход 16, Элементы И 24 этой строки ячеек 15 открываются единицей на шине 26, так как сигнал 110, поступающий с информационных входов 21-21 через элемент НЕ 25 и элемент ИЛИ-ЙЕ 22, запирает элемент И 20, а элементы И 20 тех ячеек 15, у которых сигнал "0" подан на вход 17, так же заперты, Таким образом, если на совокупность входов 17 крайней нижней строки ячеек 15 блока 8 подать "1", то на выходе 16 крайней верхней ячейки 15 блока 8 появится сигнал "1", если в соответствующем 1.толбце на входы 12,-12 ячеек 15 издано макси1316048 г16 32 64 Номер 2,8 3,34,7 6,06,9 9,925 8,9 14,6 2,2 3,2 19,0 мальное число. Так как с сумматоров 7 по входам 12 -12 поступает остаток от деления К/2 в инверсном виде, то осуществляется поиск минимального остатка от деления. Коэффициент увеличения быстродействия зависит от ш,К,1, и н таблице дано значение его величины в зависимости от ш и 1, при этом величина К бешрется равной ,значение 1 целе 2сообразно выбирать1 о 8 К, Как видгно из таблицы, предложенное устройство позволяет ускорить процесс поиска ближайшего ло образцу" слова,Формула изобретения 1. Ассоциативное запоминающее уст 35 ройстно, сочержащее регистр признаков опроса, блоки сравнения, детекторный блок, блоки задержки и матрицу запоминающих элементов, причем выход каждого запоминающего элемента строки матрицы подключен к первому нходу соответствующего блока сравнения, второй вход которого соединен с соответствующим выходом регистра признаков опроса, инверсный выход каждого бло ка сравнения подключен к первому входу блока задержки, второй вход которого соединен с выходом предыдущего блока задержки данного столбца матрицы, о т л и ч а ю ш е е с я тем, что, с целью повышения быстродействия устройства, в него введены блок поиска максимума совладений и сумматоры, причем один из входов каждого сумматора подключен к инверсному выходу соответствующего блока сравнения, а выход переноса - к третьему входу соответствующего блока задержки, вторые входы первых блоков задержки и другие входы лервьгх сумматоров каждого столбца матрицы подключены к шине единичного потенциала, выходы каждого сумматора соединены с другими входами последующего сумматора данного столбца матрицы, выходы последнего сумматора каждого столбца матрицы соединены с группой информационных нходов блока поиска максимума совпадений, управляющие входы и выходы которого подключены соответственно к выходам последних блоков задержки каждого столбца матрицы и к входам детекторного блока, четвертые входы блоков задержки объединены и являются входом синхронизации устройства.2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок поиска максимума совпадений содержит матрицу ячеек ассоциативной памяти,причем первый выход каждой ячейки ассоциативной памяти соединен с пернымвходом последующей н столбце ячейкиассоциативной памяти, первые входыпервых и первые выходы последних встолбцах ячеек ассоциативной памяти являются соответственно управляющими входами и выходами блока, информационными входами которого являютсявторые входы ячеек ассоциативной памяти, вторые выходы ячеек ассоциативной памяти строки объединены,3. Устройство по пп. 1 и 2, о т л и ч а ю щ е е с я тем, что каждая ячейка ассоциативной памяти содержит элементы НЕ, элемент ИЛИ-НЕ и элементы И, причем первый вход перного элемента И соединен с выходомэлемента ИЛИ-НЕ, первый вход которого подключен к выходу первого элемента НЕ и к первому входу второго элемента И, вторые входы первого и второго элементов И соединены с шиной нулевого потенциала, второй вход элемента ИЛИ-НЕ подключен к выходу второго элемента НЕ, вход первого элемента НЕ и первые входы третьего ичетвертого элементов И объединены иявляются первым входом ячейки, второй вход третьего элемента И и входвторого элемента НЕ объединены и являются вторым входом ячейки, второйвход четвертого элемента И подключенк выходу первого элемента И, выходыэлементов И с второго по четвертыйобъединены и являются первым выходомячейки, вторым выходом которой является выход первого элемента И.1316048 оставитель Т, Зайцеваехред Л. Олийнык орректор Г.Решетник Редактор Г,Гербер Тираж 589 ВНИИПИ Государственного комитета по делам изобретений и откры 113035, Москва, Ж, Раушская н