Универсальный ассоциативный модуль

 

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

СОЮЗ СОВЕТСНИХ

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

PECllYEiËÈH 511 4 С 06 F 15/40

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

4 ссоц, прирюк

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯ14

ПРИ ГННТ СССР (21) 4254583/24-24 (22) 02 ° 06. 87 (46) 15. 01.89. Бюл. й- 2 (72) Г.И. Васильев, А.В. Лярский и В.В.Храмов (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1015390, кл. G 06 F 15/00, 1983.

Кохонен Т. Ассоциативные запоминающие устройства. N. Мир, 1982, с. 168, рис. 3-9. (54) УНИВЕРСАЛЬНЫЙ АССОЦИАТИВНЫЙ

МОДУЛЬ (57) Изобретение относится к вычислительной технике и может быть использовано в вычислительных машинах и системах, системах распознавания образов и т.п. Целью изобретения

„„SU„„1451726 A 1 является расширение функциональных возможностей за счет введения режимов "Поиск наибольшего-наименьшего", "Поиск ближайшего большего-меньшегс", "Поиск ближайшего большего-меньшего по интервалу и сокращение аппаратных затрат. Указанная цель достигается тем, что в универсальный ассоциативный модуль, содержащий первый блок 9 ассоциативной памяти, первый регистр 8 отклика, регистр 2 признака, введены второй блок 10 ассоциативной памяти, два счетчика-вычитателя 5,15, два элемента И-НЕ 3,6, второй регистр 11 отклика, два элемента KIH-HE 7,12, элемент ИЛИ 14, блок 13 управления и счетчик 4.

1 з.п. ф-лы, 2 ил.

1451726

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

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

На фиг. 1 представлена структурная схемЫ универсального ассоциатив-. ного модуля; на фиг. 2 — структурная 20 схема блока управления операциями.

Универсальный ассоциативный модуль содержит вход 1 для записи ассоциативного признака в регистр 2 (фиг.1), элемент И-НЕ 3, счетчик 4, счетчик- 25 вычитатель 5, элемент И-НЕ 6, элемент.

ИЛИ-НЕ 7, регистр 8 отклика, блоки 9 и 10 ассоциативной памяти ЗУ, регистр 11 отклика, элемент ИЛИ-НЕ 12, блок 13 управления, элемент ИЛИ 14, 30 счетчик-вычитатель 15, второй информационный вход 16 для записи числами, первый вход 17 для операции "Поиск ближайшего большего", второй вход 18 для операции "Поиск наименьшего", "Поиск ближайшего большего" и "Поиск ближайшего (большего) по интервалу", третий вход 19 подачи кода операции, первый выход 20 сигнала операции

"Поиск наименьшего" для установки 40 счетчика 4 в "О", второй выход 21 для подачи импульсов счета на счетчик, третий выход 22 для подачи сигнала Занесение в счетчики", четвертый выход 23 для подачи импульсов 45 счета на счетчик-вычитатель 5, пятый выход 24 сигнала операции "Поиск наибольшего", четвертый вход 25 для управления операциями "Поиск наибольшего", "Поиск ближайшего меньшего", "Поиск ближайшего (меньшего) по интервалу, пятый вход 26 для управления операцией "Поиск ближайшего меньшего", шестой выход 27 для подачи импульсов счета на третий счетчик, шестой вход 28 для управления операциями поиска по интервалу (" Поиск ближайшего на интервале С", "Поиск

11 ближайше ro большего на интерв але E

"Поиск ближайшего меньшего на интервале E ") .

Блок 13 управления (фиг.2) содержит элементы ИЛИ 29-31, элементы И

32-39, генератор 40 тактовых импульсов, элемент И 41, элементы ИЛИ 4243, дешифратор 44 кода операции и выходы 45-51 дешифратора 44.

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

Исходное состояние блоков устройства при выполнении всех операций: в оба блока 9 и 10 ассоциативной памяти записаны одинаковые массивы информации; регистр 2, счетчик 4, счетчикивычислители 5 и 15 сброшены в "0"; регистры 8 и 11 отклика сброшены в «0»

Значение кода операции (КОП), ассоциативного признака (AII=X) и значение интервала поиска для операпий

"Поиск ближайшего большего (меньшего), ближайшего по интервалу E" подаются одновременно в дешифратор 44, регистр 2 и счетчик-вычислитель 15 соответственно. Дальнейшая работа устройства происходит в зависимости от кода операции.

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

При этой операции (KOII=O АП=О, E =0) возбуждается выход 45 дешифратора 44. Сигнал с этого выхода подается на вход элемента ИЛИ 42, на сброс счетчика 4 в "О" и на вход элемента И 32. Единичный сигнал со схемы ИЛИ 42 разрешает подачу тактовых импульсов с генератора 40 через схему И 41 на второй вход схемы И 32, а также производит копирование в счетчик 4 и счетчик-вычитатель 5 информации из регистра 2. Поскольку при выполнении данной операции ре" гистр 2 обнулен, то счетчик 4 также будет в состоянии "О". Следовательно, с выходов схемы дешифратора 44 и элемента ИЛИ-НЕ 7 будут сниматься единичные значения сигналов. С выхода элемента И 32 через элемент ИЛИ 29 начнут проходить тактовые импульсы на счетный вход счетчика 4. Содержимое этого счетчика начнет изменяться от нулевого значения в сторону возрастания. При первом совпадении содержимого счетчика 4 с содержимым с хотя бы одной ячейки ассоциативного запоминающего устройства 9 в регистр

8 отклика заносится единица и на вы3

14517 ходе эпемента ИЛИ-НЕ 7 устанавлива11 11 ется О, что приводит к прекращеню работы счетчика 4, так как элемент И

32 закроется. Б результате в счетчи5 ке 4 будет зафиксировано наименьшее значение числа из того массива чисел, которые хранятся в ассоциативной памяти 9.

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

Для этом операции (КОП=001, АП=Х, 8=0) возбуждается выход 46 дешифратора 44. Сигнал с этого выхода поступает на вход элемента ИЛИ 42 и на 15 вход элемента И 33. Единичный сигнал с выхода элемента ИЛИ 42 разрешает подачу импульсов с генератора 40 тактовых импульсов на второй вход элемента И 32 и на копирование содержи- 20 мого регистра 2 в счетчик 4 и счетчик-вычислитель 5. Импульсы счета с выхода элемента ИЛИ 29, сформированные по сигналам "1" на входе 18 и на выходе 46 дешифратора 44, посту- 25 пают на счетный вход счетчика 4 до тех пор, пока очередное значение счетчика 4 не совпадет хотя бы с одним из значений содержимого ассоциативной памяти 9 или счетчик не будет 30 полностью заполнен. В первом случае произойдет установка в "Он выхода элемента ИЛИ-НЕ 7 и прекращение работы счетчика 4. Во втором случае произойдет установка в "0" элемента И-НЕ

3 с последующим прекращением работы счетчика.

В результате в ассоциативной памяти 9 и счетчике 4 будет зафиксировано ближайшее большее к заданному 40 числу Х. В дальнейшем оно может быть обработано известным порядком.

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

Эта операция выполняется аналогич- 45 но операции "Поиск наименьшего". При подаче КОИ=010 на вход дешифратора возбуждается его выход 47, по единичному сигналу с которого разрешается подача тактовых импульсов с генератора 40 за счет "1" с элемента ИЛИ

42, а также занесение в счетчик 4 и счетчик-вычитатель 5 содержимого регистра 2. Но поскольку для данной операции AII=O, то по этому импульсу в счетчики также заносятся нули, однако по единичному сигналу с выхода

24 счетчик 5 уставнавливается в единичное состояние (т.е. все его раз26

4 ряды устанавливаются в "1") . Импуль— сы с генератора 40 через элемент If

41 поступают на элемент И 35, на всех входах которого установлены разрешающие единичные сигналы с выходов дешифратора 44 и элемента ИЛИНЕ 12. С выхода элемента И 35 через элемент ИЛИ 30 импульсы поступают на вычитающий вход счетчика-вычитателя 5, состояние которого с каждым импульсом уменьшается на единицу.

Так происходит до тех пор, пока в ассоциативной памяти 10 не произойдет совпадение содержимого счетчика-вычитателя 5, являющегося признаком ассоциативного поиска, хотя бы с одной ячейкой ассоциативной памяти 10. Как только это случится, с регистра 11 поступит хотя бы одна единица в элемент ИЛИ-НЕ 12, что приведет к запрету прохождения импульсов через элемент И 35. Это означает, что найдено наибольшее из чисел, хранящихся в АЗУ.

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

Эта операция выполняется аналогично операции "Поиск ближайшего больше-. го". При этом возбуждается выход 48 дешифратора 44, что разрешает за счет " 1" с выхода элемента ИЛИ 42 прохождение импульсов с генератора 40 через элемент И 41, а также копирование содержимого регистра 2 в счетчик

4 и счетчик-.вычитатель 5. Импульсы счета с выхода элемента ИЛИ 30 поступают на вычитающий вход счетчикавычитателя 5. Это происходит до тех пор, пока очередное значение счетчика-вычитателя 5 не совпадет с одним из значений из ассоциативной памяти 10 или счетчик не достигнет нулевого значения. B первом случае произой".,ет установка в "0" выхода элемента ИЛИ-НЕ 12 v. прекращение работы счетчика-вычитателя S. Bo втором случае произойдет установка в "О" элемента И-НЕ 6 с последующим прекращением работы счетчика-вычитателя 5.

Б результате в ассоциативной памяти 10 и в счетчике-вычитателе 5 будет зафиксировано ближайшее меньшее к заданному числу Х. Б дальнейшем оно может быть обработано известным порядком.

5 14517

Операция "Поиск ближайшего большего по интервалу" (КОП 101, АП=Х, E-=Y) .

При выполнении этой операции воз5 буждается выход 49 дешифратора 44.

При этом единичный сигнал с- выхода дешифратора через элементы ИЛИ 42 и 43 разрешает выдачу импульсов с генератора 40 через элемента И 41, а 1р также обеспечивает подачу "1" на вход элемента И 38 соответственно.

Импульсы с выхода элемента И 41 подаются на входы элемента И 34 и элемента И 32, Поскольку для данной опе- 1r„ рации значение f =Y, т.е. в счетчикевычитателе 15 хранится значение, не равное нулю, то с выхода элемента

ИЛИ 14 будет сниматься единичный сигнал до тех пор, пока счетчик-вычита- 20 тель 15 не обнулится и на всех его прямых выходах не появятся нули.

В этом случае прекратится прохождение импульсов через элементы 38 и 31 и счетчик 15 прекратит работу. Элемент 25

И 34 пропускает импульсы через элемент ИЛИ 29 на счетный вход счетчика

4 до тех пор, пока не будет найдено ближайшее большее к заданному числу Х в пределах диапазона f=Y или не бу- gp дет достигнута граница этого диапазона. В первом случае по наличию "1" хотя бы в одном разряде регистра 8 появится "0" на выходе элемента ИЛИНЕ 7, запрещающий прохождение импульсов через элемент И 34 ° Это означает, что ближайшее большее в заданном интервале найдено. Во втором случае по достижении границы диапазона E=Y счетчик-вычитатель 15 обнулится и ну- 40 левой сигнал с выхода элемента ИЛИ

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

БО

Сигнал с выхода 22 обеспечивает копирование исходных значений в счетчике 4 и счетчиках-вычитателях 5 и 15.

Операция "Поиск ближайшего меньше- го по интервалу" (КОП=110, АП=Х, Я=у) .

Эта операция выполняется аналогично предыдущей. При подаче кода опера26 6 ции на вход дешифратора 44 возбуждается его выход 50, Точно так же единичное значение сигнала с его выхода разрешает прохождение импульсов через элемент И 37, элемент И 41 и элемент И 38 и происходит копирование значений Х, Y в счетчик 5 и счетчики-вычитатели 5 и 15. Аналогично так же осуществляется цикл обработки .значения Y в счетчике-вычитателе 15, т.е. импульсы на него подаются с выхода элемента ИЛИ 31 до тех пор, пока он не обнулится и нулевые сигналы с его прямых выходов не закроют элементы 37 и 38.

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

10 уменьшающихся с каждым импульсом счета значений Х. Это происходит до наступления одного из двух событий: либо будет найдено искомое значение, либо будет достигнута граница интервала поиска. В первом случае произойдут установка в "0" выхода элемента ИЛИ-НЕ 12 и прекращение прохождения импульсов через элемент И 37 с остановкой счетчика-вычитателя 5. Во втором случае произойдут установка в "0" выхода 28 элемента ИЛИ 14 и прекращение прохождения импульсов через элемент И 37 с остановкой счетчика. факт отсутствия в заданном интервале ближайшего меньшеro определяется по единичному значению сигнала на выходе элемента ИЛИ-НЕ 12.

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

При выполнении этой операции должно быть найдено число, ближайшего к заданному числу X в пределах диапазона Х+Е, При подаче кода операции на вход дешифратора 44 возбуждается его выход 51. При этом аналогично как в предыдущем случае происходит формирование серии импульсов на выходе элемента И 41, которые подаются на вход элемента И 39, На остальные четыре входа элемента H 39 подаются единичные сигналы с выходов элементов ИЛИНЕ 7 и 12, с выхода 51 дешифратора и с выхода элемента ИЛИ 14 единица на выходе элемента ИЛИ 14 устанавливается с занесением в счетчик-вычитатель 15 значения, отличного от ну1451726 ля). Таким образом, импульсы с выхода элемента И 39 поступают одновременно на счетный вход счетчика 4 и вычитающий вход счетчиков-вычитате5 лей 5 и 15, В счетчике 4 и счетчике-вычитателе 5 начинается выработка значений, соответственно возрастающих и уменьшающихся относительно начального значения Х. В счетчике-вычитателе 15 происходит выработка уменьшающегося до нуля значения, отсчитывающего интервал поиска с =Y. При достижении счетчиком-вычитателем 15 значения, равного нулю, происходит 1б завершение операции путем обнуления входа элемента И 39, связанного с выходом элемента ИЛИ 14. Если к этому моменту не произошло ни одного совпадения ассоциативной памяти 9 2ц и 10 с содержимым счетчика 4 и счетчика-вычитателя 5, то этом состояние будет зафиксировано единичными значениями выходов элементов ИЛИ-НЕ 7 и 12. В противном случае элемент И 25

39 закроется нулевым сигналом по входу 18 и/или 25, что означает обнаружение ближайшего к заданному числу Х на интервале <. Копирование Х в счетчик 4 и счетчик-вычитатель 5 как и ранее производится сигналом с выхода 22 блока 13.

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

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

Поиск наибольшего-наименьшего

Поиск ближайшего большего-меньшего

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

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

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

l0 динен с вторым входом первого элемента И, первым входом первого элемента ИЛИ и первым выходом блока, второй выход дешифратора соединен с вто5 рым входом первого элемента ИЛИ и третьим входом первого элемента И, выход которого соединен с первым вхо. дом второго элемента"ИЛИ, выход которого соединен с вторым выходом 1р блока, третий выход дешифратора соединен с первым входом четвертого элемента И, пятым управляющим выходом блока и третьим входом первого элемента ИЛИ, выход которого соеди- 15 нен с третьим выходом блока и первым входом девятого элемента И, выход которого соединен с первым входом пятого, шестого и седьмого элементов И, вторыми входами третьего, четверто- 2р го и восьмого элементов И, третьим входом второго элемента И и четвертым входом первого элемента И, четвертый выход дешифратора соединен с четвертым входом первого элемента ИЛИ 25 и вторым входом пятого элемента И, выход которого соединен с первым входом третьего элемента ИЛИ, выход которого соединен с четвертым выходом устройства, пятый выход дешифратора соединен с пятым входом первого элемента ИЛИ, третьим входо третьего элемента И и первым входом четвертого элемента ИЛИ, выход которого сое-. динен с вторым входом седьмого элемента И, выход которого соединен с первым входом пятого элемента ИЛИ, выход которого соединен с шестым выходом блока, шестой выход дешифратора соединен с шестым входом первого элемента ИЛИ, вторым входом шестого элемента И и вторым входом четвертого элемента ИЛИ, седьмой выход дешифратора соединен с седьмым входом первого элемента ИЛИ и третьим входом восьмого элемента И, выход генератора импульсов соединен с вторым входом девятого элемента И, четвертый вход блока соединен с третьим входом четвертого, пятого и шестого элементов И и четвертым входом восьмого элемента И, выход которого соединен с вторыми входами второго, третьего и пятого элементов ИЛИ, пятый вход блока соединен с четвертым входом пятого элемента И, шестой вход блока соединен с третьим входом седьмого элемента И, четвертым входом третьего и шестого элементов И и пятым входом восьмого элемента И, выходы второго и третьего элементов

И соединены с третьим и четвертым входами второго элемента ИЛИ соответственно, выходы четвертого и шестого элементов И соединены с третьим и четвертым входами третьего элемента ИЛИ соответственно.

1451726

17

18

Zb

2б

Составитель А. Богословских

Редактор A.Ëåæíèíà Техред A. Кравчук Корректор В. Бутяга

Заказ 7083/49 Тираж бб7 Подписное

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

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

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