Устройство для реализации операций ассоциативного поиска

 

Изобретение позволяет при сохранении функциональных возможностей устройства значительно снизить аппаратные затраты на его реализацию за счет сокращения блока ассоциативного запоминающего устройства емкостью m и разрядностью п. Для этого в устройство введены генератор тактовых импульсов 3, элемент И на три входа 5, делитель частоты 6 на два, элемент НЕ 7, элемент задержки 8, первая группа элементов И 13, вторая группа элементов И 16, два элемента И 9. 10. Это устройство также позволяет реализовать любую из таких операций ассоциативного поиска по совпадению, поиск ближайшего большего, поиск ближайшего меньшего, поиск наименьшего, поиск наибольшего, поиск ближайшего большего (меньшего) на интервале и поиск ближайшего на интервале путем преобразования аргумента ассоциативного поиска увеличением или уменьшением этого аргумента либо до максимального (минимального ), либо до заданного предела значения в зависим ости от кода операции. 3 ил. ел С

СОЮЗ. СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)з G 06 F 15/40

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4829851/24 (22) 29,05.90 (46) 15.02.93. Бюл. N. 6 (72) Г.И.Васильев и В.Б.Молчанов (56) Кохонен Т. Ассоциативные запоминающие устройства. M.: Мир,,1982, с. 168.

Авторское свидетельство СССР

М 1451726, кл. 6 06 F 15/40, 1984. (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ

ОПЕРАЦИЙ АССОЦИАТИВНОГО ПОИСКА (57) Изобретение позволяет при сохранении функциональных воэможностей устройства значительно снизить аппаратные затраты на его реализацию за счет сокращения блока ассоциативного запоминающего устройства емкостью m и разрядностью и. Для этого в устройство введены генератор так„„5Q„„ 1795485 А1 товых импульсов 3, элемент И на три входа

5, делитель частоты 6 на два, элемент НЕ 7, элемент задержки 8, первая группа элементов И 13, вторая группа элементов И 16, два элемента И 9, 10. Это устройство также позволяет реализовать любую из таких операций ассоциативного поиска по совпадению, поиск ближайшего большего, поиск ближайшего меньшего, поиск наименьшего, поиск наибольшего, поиск ближайшего большего (меньшего) на интервале и поиск ближайшего на интервале путем преобразования аргумента ассоциативного поиска увеличением или уменьшением этого аргумента либо до максимального (минимального), либо до заданного предела значения в зависимости от кода операции. 3 ил, 1795485

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

Ассоциативное ЗУ и содержащее модуль АЗУ, регистр аргумента поиска, регистр маски, память фиксации реакций„ анализатор многократного совпадения, вспомогательные цепи управления и передачи данных, не имеет возможности выполнять операции типа поиск ближайшего

20 большего, ближайшего меньшего, наименьшего, наибольшего, ближайшего большего на интервале, ближайшего меньшего на интервале, ближайшего на интервале среди массива чисел, хранящихся в АЗУ. 25

Наиболее близким к предлагаемому яв. ляется универсальный ассоциативный модуль, содержащий регистр признака, счетчик-сумматор, двэ счетчика-вычитателя, . два блока ассоциативной памяти, два регистра отклика, два элемента ИЛИ-НЕ, блок управления операциями, элемент ИЛИ. Хотя у данного устройства функциональные возможности.и расширены по сравнению с предыдущими устройствами, но недостат- Ç5 ком являются большие аппаратные затраты., Целью изобретения является сокращение аппаратных затрат.

Поставленная цель достигается тем, что в указанное устройство для реализации one- 40 раций ассоциативного поиска, содержащее с первого по третий счетчики, блок ассоциативной памяти, блок управления операциями, первый и второй элементы И-ХЕ, элемент ИЛИ, первый элемент И и элемент "5

ИЛИ-НЕ, причем вход ассоциативного признака устройства подключен к информационным входам первого и второго счетчиков, информационные выходы первого счетчика подключены ко входам первого элемента 50

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

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

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

7795485

55 первым входам элементов И с третьего по шестой, входы режима группы блока управления операциями подключены соответственно к информационным входам дешифратора, первый выход которого подключен к первым входам седьмого элемента

И, первого элемента ИЛИ и к первому выходу блока управления операциями, второй выход дешифратора подключен ко вторым входам первого элемента И и первого элемента ИЛИ, выход которого подключен к пятому выходу блока управления операция-ми и к первому входу второго элемента

ИЛИ, выход которого подключен ко второму выходу блока управления операциями, ко вторым входам второго, третьего, четвертого, пятого и седьмого элементов И, к первому входу восьмого элемента И и к третьему входу первого элемента И, третий выход дешифратора подключен к третьему выходу блока управления операциями, ко второму входу восьмого элемента И, ко второму входу второго элемента ИЛИ и к первому входу третьего элемента ИЛИ, выход которого подключен к шестому выходу блока управления операциями, четвертый выход дешифратора подключен ко второму входу третьего элемента ИЛИ, к третьему входу второго элемента ИЛИ и к третьему входу второго элемента И, пятый выход дешифратора подключен к третьему входу первого . элемента ИЛИ, к третьему входу третьего элемента И и к первому входу четвертого элемента ИЛИ, выход которого подключен ко второму входу шестого элемента И, выход которого подключен к четвертому выходу блока управления операциями, шестой выход дешифратора подключен к третьему входу третьего элемента ИЛИ, ко второму входу четвертого элемента ИЛИ, к четвертому входу второго элемента ИЛИ и к третьему входу четвертого элемента И, седьмой выход дешифратора подключен к четвертому входу первого элемента ИЛИ, к четвертому входу третьего элемента ИЛИ, к третьему входу четвертого элемента ИЛИ и к третьему входу пятого элемента И, выходы первого, второго, третьего, четвертого, пятого, седьмого и восьмого элементов И подключены соответственно ко входам пято о элемента ИЛИ, выход которого подключен к седьмому выходу блока управления операциями, На фиг, 1 представлена структурная схема устройства для реализации операций ассоциативного поиска; на фиг, 2 — структурная схема блока управления операциями; на фиг, 3 — функциональная схема делителя частоты на два.

Устройство для реализации операций ассоциативного поиска содержит вход 1, для подачи ассоциативного признака, общую информационную шину 2 для передачи признака на входы двух первых счетчиков, генератор тактовых импульсов 3, вход 4 подачи тактовых импульсов на схему И 5, делитель частоты 6 на два, элемент НЕ 7, первый элемент задержки 8, элементы И 9 и И 10, счетчик 11, первый счетчик-вычитатель 12, первую группу 13 схем

И, элементы И-НЕ 14, 15, вторую группу элементов 16 схем И, блок 17 управления операциями, второй элемент ИЛИ 18, элемент И 19, второй счетчик-вычитатель 20, второй информационный вход 21 для записи числа е, первый вход 22 подачи кода операции, второй вход 23 для операции "поиск ближайшего большего", первый выход 24 сигнала операции "поиск наименьшего" для установки счетчика 11 в "0", второй выход 25 блока управления операциями, разрешающий подачу импульсов счета на счетчик 11, третий выход 26 для подачи сигнала "занесение в счетчики", четвертый выход 27 разрешающий подачу импульсов счета на первый счетчиквычитатель 12, пятый выход 28 сигнала операции "поиск наибольшего" для установки первого счетчика-вычитателя 12 в "1", третий вход 29 для управления операцией "поиск ближайшего меньшего", шестой выход 30 разрешающий подачу импульсов счета на второй счетчик-вычитатель 20, четвертый вход 31 для управления операциями поиска по интервалу("поиск ближайшего на интервале c", "поиск ближайшего меньшего на интервале я", "поиск ближайшего большего на интервале я"), шестой выход 32 разрешающий подачу тактовых импульсов с ГТИЗ, блок 33 ассоциативной памяти ЗУ, второй элемент

ИЛИ-НЕ 34, выход 35 запрещающий выдачу тактовых импульсов с ГТИЗ при сравнении содержимого счетчиков 11 или 12 с содержимым одной из ячеек ассоциативной памяти

33, Блок управления операциями 17 содержит элементы ИЛИ 36, 45-48, элементы И 37-44, дешифратор 49 кода операции и выход дешифратора 50 для кода операции (КОП) "поиск наименьшего", выход 51 дешифратора для КОП "поиск ближайшего большего" к заданному числу, выход 52 дешифратора для

КОП "поиск наибольшего" в массиве чисел, выход 53 дешифратора для КОП "поиск ближайшего меньшего" к заданному числу, выход 54 дешифратора для КОП "поиск ближайшего большего по интервалу" выход

55 дешифратора для КОП "поиск ближайшего меньшего по интервалу" выход 56 дешифратора для КОП "поиск ближайшего по интервалу".

1795485

35

45 Bce блоки и узлы устройства известны и описаны в научно-технической литературе.

Например, блоки 11, 12, 20 используются те же, что и в(1),,блок ассоциативного ЗУ может быть реализован аналогично блоку ассоциативного параллельного микропроцессора, описанного в (5). В качестве делителя частоты на два можно использовать О-триггер, описанный в (6), соединив инверсный выход со входом D (ôèã, 3).

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

Исходное состояние блоков устройства при выполнении всех операций: .— в блок 34 ассоциативной памяти записан определенный массив информации; — счетчики 11, 12 и 20, триггер 6 сброшены в "0".

Значение кода операции (КОП), ассоциативного признака (АПХ) и значение интервала поиска для операций "поиск ближайшего большего (меньшего), ближайшего по интервалу 6 подаются одновременно в дешифратор 49, на информационную шину 2 и счетчик-вычитатель 20 соответственно.

Дальнейшая работа устройства происходит в зависимости от кода операции.

Операция "Поиск наименьшего"

При этой операции (КОП = О, АП = О, О) возбуждается выход 50 дешифратора 49, Сигнал с этого выхода подается на вход элемента ИЛИ 46, на сброс счетчика 11 в "0" и на вход элемента И 38. Единичный сигнал со схемы ИЛИ 46 подается на вход элемента

И 9 и проходя через элемент ИЛИ 45 подается на вход элемента И 38 и производит кодирование информации из информационной шины 2 в счетчики 11 и 12 (счетчик 12 в дальнейшей работе не участвует). Сигнал с выхода элемента И 38 проходя через weмент ИЛИ 36 поступает на вход элемента И

5 вместе с сигналом 35, который также равен "1", поскольку с выхода ячеек блока ассоциативной памяти поступает нулевой сигнал. Сигналы 32 и 35 разрешают прохождение импульсов счета с генератора тактовых импульсов 3 на вход делителя частоты 6 на два и на входы элементов XE 7 и задержки 8, с выхода элемента задержки 8 единичный сигнал открывает первую группу элементов И,13. Импульсы счета через элемент И 9 начнут поступать на счетный вход счетчика 11, поскольку при выполнении заданной операции вход 1 обнулен (АП = О), то счетчик 11 также будет в состоянии "0". При поступлении импульсов содержимое этого счетчика начнет изменяться от нулевого .значения в сторону возрастания и сравниваться через открытую первую группу элементов И 14 с содержимым хотя бы одной ячейки ассоциативного запоминающего устройства 33, При первом же совпадении на одном из выходов ячеек. блока ассоциативного запоминающего устройства появится единичный сигнал, поступающий на вход элемента ИЛИ-НЕ 34, следовательно нулевой сигнал 35 закроет схему И 5, что приведет к прекращению работы счетчика 11, В результате в счетчике 11 будет зафиксировано наименьшее значение числа из того массива чисел, которые хранятся в ассоциативной памяти 34.

Операция "Поиск ближайшего большего" к заданному числу.

При этой операции (КОП = 001, АП = Х, я= О) возбуждается выход 51 дешифратора

49. Сигнал с этого выхода поступает на вход элемента ИЛИ 46 и.на вход элемента И 39.

Единичный сигнал с выхода элемента ИЛИ

46 поступает на элемент И 9, разрешается прохождение импульсов счета на счетчик

11, и на вход схемы ИЛИ 45, Выходной единичный сигнал 26 с выхода элемента ИЛИ

45 производит копирование информации из информационной шины 2 в счетчики 11 и 12 (счетчик 12 в дальнейшей работе не участвует) и подается на вход элемента И 39, с выхода которого единичный сигнал подается на вход элемента ИЛИ 36. Единичный сигнал 32 вместе с сигналом 35, который также равен "1", т,к. с выхода ячеек блока ассоциативного запоминающего устройства снимается "0", поДаются на вход элемента И 5, разрешая прохождение тактовых импульсов с ГТИ 3 на вход делителя частоты

6 на два и на входы элементов HE 7 и задержки 8, единичный сигнал с выхода схемы задержки 8, поступая на входы первой группы элементов И 13, разрешит сравнивать содержимое счетчика 11 с содержимым блока АЗУ 33. Так как при выполнении данной операции АП = Х, то в счетчики 11 и 12 при копировании будет записано также значение Х, При поступлении импульсов счета на счетчик 11 содержимое его начнет изменяться от X в сторону возрастания до тех пор, пока очередное значение счетчика 11 не совпадет хотя бы с одним из значений содержимого ассоциативной памяти 33 или счетчик не будет полностью заполнен. В первом случае произойдет установка в "0" выхода схемы ИЛИ-НЕ 34 и прекращение работы счетчика 11, Во втором случае произойдет установка в "0" выхода элемента

И-НЕ 14, что приведет к закрытию элемента

И 39 с последующим прекращением работы счетчика 11. В результате в ассоциативной памяти 33 и счетчике 11 будет зафиксирова1795485

5

25

50 но ближайшее большее к заданному числу

Х.

Операция "Поиск наибольшего" в массиве чисел (КОП = 010, АП = О, e= О}.

Эта операция выполняется аналогично операции "Поиск наименьшего". В этом случае возбуждается выход 52 дешифратора

49, единичный сигнал с которого через схему ИЛИ 48, поступая на вход элемента И 10 разрешает поступление тактовых импульсов на счетчик-вычитатель 12, через схему

ИЛИ 45 выходным сигналом 26 производит копирование информации на информационной шине 2 в счетчик 11 и 12 (счетчик 11 в дальнейшей работе не участвует), а также

„этот сигнал поступает на элемент И 40. Поскольку для этой операции АП = О, то в счетчики 11 и 12 также заносятся нули, однако по единичному сигналу с выхода 28 счетчиквычитатель 12 устанавливается в единичное состояние, Единичный выходной сигнал 32, сформированный по сигналам 52 и 26, поступая одновременно с единичным сигналом 35 на элемент И 5, разрешает поступление тактовых импульсов с ГТИ 3 на вход делителя частоты 6 на два и на входы элементов НЕ 7 и задержки 8. Тактовые импульсы поступают через элемент И 10 на вычитающий вход счетчика-вычитателя 12.

Единичный выходной сигнал с выхода элемента НЕ 7 открывает вторую группу 17 элементов И и производит сравнение содержимого счетчика-вычитателя 21 с содержимым блока ассоциативной памяти 33.

При поступлении импульсов счета состояние счетчика-вычитателя 12 уменьшается на единицу до тех пор, пока в ассоциативной памяти 33 не произойдет совпадение содержимого счетчика-вычитателя 12 с содержимым хотя бы одной ячейки ассоциативной памяти. Как только это случится, с выходов ячеек ассоциативной памяти поступит хотя бы одна единица на один из входов схемы

ИЛИ-НЕ 34, что приведет к запрету прохождения импульсов через элемент И 5. Это означает, что найдено наибольшее из чисел, хранящихся в ассоциативной памяти ЗУ.

Операция "Поиск ближайшего меньшего" к заданному числу(КОП = 100. АП =X, e=

=О), Эта операция выполняется аналогично операции "Поиск ближайшего большего".

При этом возбуждается выход 53 дешифратора 49, единичный сигнал с которого через элемент ИЛИ 48 поступая на схему И 10„ разрешает прохождение импульсов счета на вычитающий вход счетчика 12, через элемент ИЛИ 45 производит копирование информации из информационной шины 2 в счетчики 11 и 12 (счетчик 11 в дальнейшей работе не участвует) и поступает на элемент

И 41, на всех входах которого установлены разрешающие единичные сигналы, с выхода элемента И-Н Е 15 и с выхода элемента ИЛИ

45. Выходной единичный сигнал с элемента

И 41, проходя через элемент ИЛИ 36, посту- . пая одновременно с единичным сигналом

35 на схему И 5 разрешает прохождение тактовых импульсов ГТИ 3 на входы делителя частоты 6 на два и элементы HE 7 и задержки 8. Значение счетчика-вычитателя

12 начнет изменяться до тех пор, пока очередное значение его не совпадет с одним из значений из ассоциативной памяти 33 или счетчик-вычитатель не достигнет нулевого значения. В первом случае произойдетустановка в "0" выхода схемы ИЛИ-НЕ 34, что приведет к прекращению работы счетчикавычитателя 12. Во втором случае произойдет установка в "0" выхода элемента И-НЕ

15, что снимает разрешающий единичный сигнал 32 с элемента И 5 и, следовательно приведет к прекращению работы счетчикавычитателя 12, В результате в ассоциативной памяти

33 и в счетчике-вычитателе 12 будет зафиксировано ближайшее меньшее к заданному числу Х, В дальнейшем оно может быть обработано известным порядком.

Операция "Поиск ближайшего большего по интервалу" (КОП = 101, АП = Х, е= Y}, При выполнении этой операции возбуждается выход 54 дешифратора 49, Единичный сигнал с этого выхода через элемент

ИЛИ 46 разрешает подачу импульсов на счетчик 11, через элементы И 42, ИЛИ 36 формирует единичный сигнал 32, который поступая вместе с единичным сигналом 35 на элемент И 5, разрешает прохождение тактовых импульсов с ГТИ 3 на вхоДы делителя частоты 6 на два, элементов НЕ 7 и задержки 8, Кроме этого сигнал с выхода 54 дешифратора 49 через элемент ИЛИ 47 поступает на вход элемента И 37 вместе с сигналом 31, который также равен "1", т.к, поскольку для данной операции значение е= У, т.e . в счетчике-вычитателе 20 хранится значение не равное нулю, следовательно, с выхода элемента ИЛИ 18 будет сниматься единичный сигнал до тех пор, пока счетчиквычитатель 20 не обнулится и на всех его прямых выходах не появятся нули. Единичный сигнал 30 с выхода элемента И 37, поступая на вход элемента И 19 разрешает подачу импульсов счета на вычитающий вход счетчика-вычитателя 20, Элемент И 9 пропускает импульсы на счетный вход счетчика 11 до тех пор, пока не будет найдено

1795485

5

30

50 ближайшее большее к заданному числу Х в пределах диапазона = или не будет достигнута граница этого диапазона. В первом случае по наличию "1" хотя бы на одном из выходов ячеек блока 33 ассоциативной памяти на выходе элемента ИЛИ-НЕ 34 появится "0". запрещающий прохождение импульсов через элемент И 5. Это означает, что ближайшее большее в заданном интерsane найдено, Во втором случае по достижении границы диапазона = счетчиквычитатель 20 обнулится и нулевой сигнал с выхода элемента ИЛИ 18 закроет элементы

И 42 и И 37, что приведет к останову счетчиков 11 и 20. Это означает, что достигнута граница диапазона поиска и операция завершена. Если при этом в заданном интервале не оказалось ни одного числа, ближайшего большего к заданному числу Х, то на этот факт указывает единичное значение сигнала с выхода элемента ИЛИ-НЕ 34.

Сигнал с выхода 26 обеспечивает копирование исходных значений в счетчик 11 и счетчики-вычитатели 12 и 20, Операция "Поиск ближайшего меньшего по интервалу" (КОП = 110, АП = X, e= Y).

Эта операция выполняется аналогично предыдущей. Возбуждается выход 55 дешифратора 49. Единичный сигнал с него разрешает прохождение импульсов на счетчик-вычитатель 1?, через элемент ИЛИ 45 копирует значение Х в счетчики 11 и 12 (счетчик 11 в дальнейшей работе не участвует), а значение Y в счетчик-вычитатель 20 и поступает на вход элемента И 43, Аналогично, как и в предыдущем случае формируются единичные сигналы 30, 31, 32, 35, также осуществляется цикл обработки значения Y e счетчике-вычитателе 20, т.е. импульсы на него подаются с выхода элемента И 19 до тех пор, пока он не обнулится и нулевые сигналы с его прямых выходов не закроют элементы И 43 и И 37.

Разница состоит в том, что импульсы счета с выхода элемента И 10 поступают на счетчик-вычитатель 12, вследствие чего производится поиск по совпадению в ассоциативной памяти 33 уменьшающихся с каждым импульсом счета значений X. Это происходит до поступления одного из двух событий: либо будет найдено искомое значение, либо будет достигнута граница интервала поиска, В первом случае произойдет установка в "0" выхода элемента ИЛИ-НЕ 34 и прекращение прохождения импульсов через элемент И 5 с остановкой счетчиков-вычитателей 12 и 20. Во втором случае произойдет установка в "0" выхода элемента 18, что приведет к снятию разрешающего единичного сигнала со входов элементов И 43 и И 37, а это в свою очередь остановит счетчики-вычитатели 12, 20. Факт отсутствия в заданном интервале ближайшего меньшего определяется по единичному сигналу на выходе элемента ИЛИ-НЕ 34.

Операция "Поиск ближайшего по интервалу" (КОП = 111, АП = X, w Y).

При подаче кода операции КОП = 111 на вход дешифратора 49 возбуждается его выход 56. Единичный сигнал с этого выхода чеоез элемент ИЛИ 48 оазоешает прохож-, дение импульсов на счетчик-вычитатель 12, через элемент ИЛИ 46 — на счетчик 11, через элемент ИЛИ 45 копирует значение Х в счетчики 11, 12 и значение Y в счетчик-вычитатель 20, поступает на вход элемента И 44 и через элемент ИЛИ 47 на вход элемента И

37. Аналогично, как и в двух предыдущих случаях формируются единичные сигналы

30, 31, 32, 35. В счетчике 11 и счетчике-вычитателе 12 начинается выработка значений, соответственно возрастающих и уменьшающихся относительно начального значения X. Изменяющиеся значения содержимого счетчиков 11 и 12, за счет пери одически поя вля ющихся единичных сигналов с выходов элементов НЕ 7 и задержки 8 и открывающие вследствие этого попеременно первую и вторую группы схем И

13.и И 16 соответственно, сравниваются с содержимым хотя бы одной ячейки ассоциативной памяти 33. В счетчике-вычитателе

20 происходит выработка уменьшающегося до нуля значения, отсчитывающего интервал поиска Y. При достижении счетчикомвычитателем 21 значения, равного нулю, происходит завершение операции путем обнуления входов элементов И 44, И 37, связанного с выходом элемента ИЛИ 18. Если к этому моменту не произошло ни одного совпадения ассоциативной памяти 33 с содержимым счетчика 11 и счетчика-вычитателя 12, то это значение будет зафиксировано единичным значением выхода 35с элемента

ИЛИ-НЕ 34. В противном случае элемент И

5 закроется нулевым сигналом по входу 35, что означает обнаружение ближайшего большего или меньшего к заданному числу

X на интервале

14

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

Устройство для реализации операций ассоциативного поиска. содержащее с первого по третий счетчики, блок ассоциатив1 ной памяти, блок управления операциями, первый и второй элементы И-НЕ, элемент

ИЛИ, первый элемент И и элемент ИЛИ-НЕ, причем вход ассоциативного признака устройства подключен к информационным входам первого и второго счетчиков, информационные выходы первого счетчика подключены к входам первого элемента ИНЕ, выход которого подключен к первому входу режима блока управления операциями, первый выход которого подключен к входу установки в "0" счетчика, второй выход блока управления операциями подключен к входам записи первого, второго и третьего счетчика, информационные инверсные выходы второго счетчика подключены к входам второго элемента И-НЕ, выход которого подключен к второму входу режима блока управления операциями, третий и четвертый выходы которого подключены соот" ветственно к входу установки в "1" второго счетчика и к первому входу первого элемента И, выход которого подключен к входу декремента третьего счетчика, информационные выходы которого подключены к входам элемента ИЛИ,. выход которого подключен к третьему входу. режима блока управления операциями, входы группы режима которого подключены соответственно к входам кода операции устройства, выходы блока ассоциативной памяти подключены к входам элемента ИЛИ-НЕ, о т л и ч а ю щ ее с я тем, что, с целью сокращения аппаратурных затрат, устройство содержит с второго по четвертый элементы И, первую и вторую группы элементов И, элемент задержки, элемент НЕ, генератор тактовых импульсов и делитель частоты, причем выход генератора тактовых импульсов подключен к первому входу второго элемента И, выход которого подключен к входам делителя частоты, элемента НЕ и элемента задержки, выход делителя частоты подключен к riepвым входам третьего элемента И, четвертого элемента И и к второму входу первого элемента И, пятый и шестой выходы блока управления операциями подключены соответственно к вторым входам третьего и четвертого элементов И, выходы которых подключены соответственно, к входу инкре. мента первого счетчика и к входу декремента второго счетчика, информационные выходы первого счетчика и прямые информационные выходы второго счетчика подключены соответственно к первым входам элементов И первой и второй групп, выходы

И; входы интервала поиска устройства подключены соответственно к информационным входам третьего счетчика, при этом блок управления операциями содержит с

15 первого по восьмой элементы И, с первого

25 операциями подключены соответственно к

35

50

5

10 которых подключены соответственно к информационным входам блока ассоциативной памяти, выход элемента задержки подключен к вторым входам элементов И первой группы, выход элемента НЕ подключен к вторым входам элементов И второй группы, седьмой выход блока управления операциями и выход элемента

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

ИЛИ, выход которого подключен к пятому выходу блока управления операциями и к первому входу второго элемента ИЛИ, выход которого подключен к второму выходу блока управления операциями, к вторым входам второго, третьего, четвертого, пятого и седьмого элементов И, к первому входу восьмого элемента И и к третьему входу первого элемента И, третий выход дешифратора подключен к третьему выходу блока управления операциями, к второму входу восьмого элемента И, к второму входу второго элемента ИЛИ и к первому входутретьего элемента ИЛИ, выход которого подключен к шестому выходу блока управления операциями, четвертый выход дешифратора подключен к второму входу третьего элемента ИЛИ, к третьему входу второго элемента ИЛИ и к третьему входу второго элемента И, пятый выход дешифратора подключен к третьему входу первого элемента ИЛИ, к третьему входу третьего элемента И и к первому входу четвертого элемента ИЛИ, выход которого подключен к второму входу шестого элемента И, выход которого подключен к четвертому выходу блока управления операциями, шестой выход дешифратора подключен к третьему о

1795485

16 входу третьего элемента ИЛИ, к второму входу четвертого элемента ИЛИ, к четвертому входу второго элемента ИЛИ и к третьему входу четвертого элемента И, седьмой выход дешифратора подключен к четвертому входу первого элемента ИЛИ, к четвертому входу третьего элемента ИЛИ, к третьему входучетвертого элемента ИЛИ и к третьему входу пятого элемента И, выходы nepeoro, второго, третьего, четвертого, пятого, седьмого и восьмого элементов И подключены саатвет5 ственно к входам пятого элемента ИЛИ, выход которого подключен к седьмому выходу блока управления операциями.

1795485

Составитель Г.Васильев

Техред М.Моргентал Корректор А.Козориз

Редактор Т.Иванова

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 432 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5