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

блоки сравнения, регистр 4 признаков опроса, блоки иядерж- ки, сумматоры 7,-7 с информационными входами и выходами и блок 8 поиска максимума сонпадений, который содержит матрицу ячеек ассоциативной памяти. Каждая ячейка ассоциативной памяти содержит два элемента НЕ, элемент ИЛИ-НК и чети)р элемента И. В запоминаюгаих -элементах 2 находятся ассоциатинпые признаки,которые сравниваются п Плоках , с йризнаками опроса, со,ч.( р1 мися в регистре 4, При их сопллдении на выходе блока 3 появляется сиг нал 1, который обеспечивает прск .иж.чение сигнала 1 с входа блока 5 задержки данной строки на см о пыход и на вход следующего в столОп.е бпока 5 задержки. Во всех с ммато 1Л : 7,-7 одного столбца подсчи1ьг11ао гся сумма по модулю 2 (где е - чнс:ло информа1

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам.

Целью изобретения является повышение быстродействия устройства.

На фиг.1 представлена функциональная схема предложенного устройства; на фиг. 2 - 5 - функциональные схемы соответственно блока поиска максимума совпадений, ячейки ассоциативной памяти, блока задержки и сумматора.

Устройство содержит (фиг.1) детекторный блок 1, матрицу m X п, где m - число строк и п - число столбцов матрицы запоминающих элементов 2, блоки сравнения, регистр 4 признаков опроса, блоки задержки с первыми входами 6, сумматоры 7 -7j, и блок 8 поиска максимума совпадений.

На фиг.1 обозначены вторые входы ,, выходы , третьи входы блоков задержки, выходы и входы сумматоров , четвертые входы 14 блоков задержки.

Блок 8 поиска максимума совпадений содержит (фиг I 2) матрицу ячеек I5 ассоциативной памяти с первыми

5.-5,

ционных входов каждого сумматора 7) единичньк сигналсп несовпадения. Сигналы 1, поступающие с выходов блока 5п и сумматора 7п какого-либо столбца на входы блока 8, разрешают работу ячеек ассоциативной памяти в соответствующем столбце. Сигнал о на выходе блока 5п какого-либо столбца исключает из поиска соответствующий столбец ячеек в блоке 8. Так как с выходов каждого сумматора 7п поступает в блок 8 остаток от деления К/2 в инверсном виде (где К - число несовпадаюг;юс разрядов признаков опроса и ассоциативных признаков) , то в блоке 8 осуществляется поиск минимального остатка от деления. Устройство обеспечивает поиск ближайшего по образу слова за меньшее, чем К,, число тактов, за счет чего повышается его быстродействие. 2 з.п.ф-лы, 5 ил., 1 табл.

вькодами 16, управляющими входами 17 и вторыми выходами 18. Каждая ячейка 15 ассоциативной памяти содержит (фиг.З) первый элемент НЕ 19, 5 первый 20 и второй 21 элементы И, элемент ИЛИ-НЕ 22, третий 23 и четвертый 24 элементы И, второй элемент НЕ 25. На фиг.2 и 3 обозначены разрядные шины 26 блока 8 поиска максимума совпадений. Каждый блок 5 задержки фиг.4 может содержать, например, двухступенчатый синхронный D-триггер 27, элемент 28 ИЛИ и элементы И 29 и 30. Каждый сумматор 7

5 содержит (фиг. 5) злемент . 31i-31j равнозначности (где 1 log m/2) и элементы ИЛИ ,, Запоминающие элементы 2 могут быть вьшолнены из синхронных одноступенчатых D-тригге0 ров,

Устройство работает следующим образом.

В исходном состоянии в регистре 4 (фиг.1) находится признак опроса, в вертикальных линейках их синхронных одноступенчатых D-триггеров 2 находятся ассоциативные признаки, триггеры 27 находятся в нулевом стабильном состоянии. На вход 6 эле- 0

5

31

мента liJBi 28 (фиг. А) и сумматора 7 и входы 13 действует уровень логического О, если состояние соответствующих запоминающего элемента 2 и разряда регистра 4 не совпадают, или - 1, если совпадают. На входы 9, всех блоков 5 и входы 13, сумматоров 7 подается константа 1.Если с выхода какого-либо блока 3 по выходу 6 поступает сигнал 1 (разряды совпадают), то этот сигнал проходит через элемент НЛИ 28 на вход элемента И 29 и разрешает прохождение сигнала с входа 9 на выход 10 блока 5. Этот же сигнал (1) поступает на вход элемента ИЛИ 32, соответствующего сумматора 7 (фиг.5), пройдя через него поступает на входы элементов равнозначности 31 и элементов ИЛИ 32, и так далее, т.е. если на вход 6 элементов равнозначности ЗЦ-31р поступает сигнал 1, в этом случае на выходы )2 сумматора 7 проходит информация с его нхо- дов 13,-13р, Если по входу 6 поступает сигнал О (разряды не совпадают) , то в сумматоре 7 происходит прибавление единицы к коду, представленному в инверсном виде, поступающему по входам 13,-13р с выдачей результата (в инверсном виде) на выходы ,

В столбцах из сумматоров 7, -7

,, р

происходит подсчет по модулю сигналов несовпадения, поступающих с соответствующих блоков 3. Если код, поступающий по входам 13 в сумматор 7, не равен О (.имеется хотя бы одна единица), то на выходе последнего элемента ИЛИ 32 этого сумматора 7 появляется 1, которая, пройдя через вход 11 на элемент ИЛИ 28 блока 5, nocT TiaeT на вход элемента И 29 (фиг.4) и соответственно на выход 10 этого блока 5 проходит сигнал с входа 9. Столбец из сумматора 7 -7 делится на группы, внутри группы значение выходов 11 (элементов ИПИ 32) равно I, а на границах групп равно О, так как код на входах 13 „ сумматора 7 равен О и по входу 6 проходит О, Внутри группы количество нулей, поступающих с входов 6 блоков 3, равно 2 (в крайней верхней группе ).Еди- ница, поступившая по входу 9, распространяется внутри группы по элементам И 29 блоков 5i-5n до границы

60484

Первый сигнал, ил все элементы И 30 блокои 3, , , установит в 1 триггеры 27 блоков 5 первой группы, включая и гршшчный 5 блок 5, тем самым разрешает прохож- дение едю1ииь с входа 9 блока 5 на Емкод 10 этого же блока 5 в щую группу. Пусть, например, имеется два столбпа с наименьшим количе10 ством групп (например, ). Если , К - количество несовпавших разрядов (, ), то после трех тактов сигнал единицы появится на выходах 10 крайних верхних блоков

5 этих столбцов, С рыходов 12, „ сумматоров 7 этих столбцов в блок 8 поступят соо-тветствен))о коды чи- сел К, - S и К, - 2 S (т.е. единицы и двойки) в инверсном виде.Еди0 , поступающие с выходов 10 блоков 5 этих столбцов, поступают на входы 17 блока 8, разрешая его работу в соответств тощих столбцах.

Если на вход 17 ячейки 15 (фиг.2)

25

поступает сигнал О , то через элемент НЕ 19 он отпирает элемент И 21 и на выход 16 с шины нулевого потенциала поступает О, тем самым соответствующий столбец в блоке 8 исключается из поиска и на выходе 16 крайней верхней ячейки 15 блока 8 появится сигнал О, Если на вход 17 поступает 1, то она через элемент НЕ 1 9 запирает элемент И 21. Единичный сигнал с одного из входов 12 отпирает элемент И 23, через который единица входа 17 поступает на выход 16. Если оказалось, что в строке ячеек 15 блока 8 на входы всех

ячеек, у которых на входе 17 действует сигнал 1, поданы сигналы О, то сигнал 1 с входов 17 проходит через элемент И 24 на выход 16. Элементы И 24 этой строки ячеек

15 открываются единицей на шине 26, так как сигнал О, поступающий с информационных входов 12,-l2j через элемент НЕ 25 и элемент ИЛИ-НЕ 22, запирает элемент И 20, а элементы

И 20 тех ячеек 15, у которых сигнал О подан на вход 17, так же заперты. Таким образом, если на совокупность входов 17 крайней нижней строки ячеек 15 блока 8 подать 1, то

на выходе 16 крайней верхней ячейки 15 блока 8 появится сигнал 1, если в соответствующем г.толбце на входы ( ячеек 15 подано макси513

мальное число. Так как с сумматоров 7 по входам 12 -12 поступает остаток от деления K/Z в инверсном виде, То осуществляется поиск минимального остатка от деления, Коэф- фициент увеличения быстродействия зависит от т,К,1, и в таблице дано значение его величины в зависимости от га и 1, при этом величина К бега

рется равной ---, значение i целесообразно выбирать i log К. Как видно из таблицы, предложенное устройство позволяет ускорить процесс поиска ближайшего по образцу слова.

Формула изобретения

1, Ассоциативное запоминающее устройство, содержащее регистр признаков опроса, блоки сравнения, детекторньп ; блок, блоки задержки и матрицу запо- минающи : элементов, причем выход каждого запоминающего элемента строки матриц) подключен к первому входу со- ответствчтощего блока сравнения, второй вход которого соединен с соответствующим выходом регистра признаков опроса, инверсный выход каждого блока сравнения подключен к первому входу блока задержки, второй вход которого соединен с выходом предыдущего блока задержки данного столбца матрицы, отличающееся тем, что, с целью повьпиения быстродействия устройства, в Него введены блок поиска максимума совпадений и сумматоры, причем один из входов каждого сумматора подключен к инверсному выходу соответствующего блока сравнения, а выход переноса - к третьему входу соответствующего блока задержки, вторые входы первых блоков задержки и

o

5

0

5

0

35

40

45

50

55

другие входы первых сумматоров каждого столбца матрицы подключены к шине единичного потенциала, выходы каждого сумматора соединены с другими входами последующего сумматора данного столбца матрицы, выходы последнего сумматора каждого столбца матрицы соединены с группой информационных входов блока поиска максимума совпадений, управляющие входы и выходы которого подключены соответственно к выходам последних блоков задержки каждого столбца матрицы и к входам детекторного блока, четвертые входы блоков задержки объединены и являются входом синхронизации устройства.

2.Устройство по П.1, о т л и - чающее ся тем, что блок поиска максимума совпадений содержит матрицу ячеек ассоциативной памяти,причем первый выход каждой ячейки ассо циативной памяти соединен с первьгм входом последую1цей в столбце ячейки ассоциативной памяти, первые входы первых и первые выходы последних в столбцах ячеек ассоциативной памяти являются соответственно управляющими входами и выходами блока, информационными входами которого являются вторые входы ячеек ассоциативной памяти, вторые выходы ячеек ассоциативной памяти строки объединены,

3.Устройство по пп, 1 и 2, о т - л и ч а ю щ е е с я тем, что каждая ячейка ассоциативной памяти содержит элементы НЕ, элемент ИЛИ-НЕ

и элементы И, причем первьй вход первого элемента И соединен с выходом элемента ИЛИ-НЕ, первый вход которого подключен к выходу первого элемента НЕ и к первому входу второго элемента И, вторые входы первого и второго элементов И соединены с щиной нулевого потенциала, второй вход элемента ИПИ-НЕ подключен к выходу второго элемента НЕ, вход первого элемента НЕ и первые входы третьего и четвертого элементов И объединены и являются первым входом ячейки, второй вход третьего элемента И и вход второго элемента НЕ объединены и являются вторым входом ячейки, второй вход четвертого элемента И подключен к выходу первого элемента И, выходы элементов И с второго по четвертый объединены и являются первым выходом ячейки, вторым выходом которой является выход первого элемента И,

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам. Целью изобретения является повышение быстродействия устройства. Устройство содержит детекторный блок 1, матрицу m X п (где m - число строк и п - число столбцов матрицы) запоминающ1тх элементов 2, например, В-т 5иггеров, (Л со О5 О 4 00

(Рса.д

П

9

1

Фи.

Редактор Г.Гербер

Составитель Т.Зайцева Техред Л.Оликнык

Заказ 2369/54Тир;аж 589Подписное

ВНИИ1Ш Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная, 4

(Рие5

Корректор Г.Решетник