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

, 14 Р 15/4 ц 4 С 06 ОБРЕТЕНИЕЛЬСТВУ ОПИСА ВТОР СНОМ(56) Авторское свидетельство СССР У 1015390, кл. С 06 Р 15/00, 1983,Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 1982, с. 168, рис, 3-9.(54) УНИВЕРСАЛЬНЫЙ АССОЦИАТИВНЫЙ МОДУЛЬ(57) Изобретение относится к вычислительной технике и может быть использовано в вычислительных маш и системах, системах распознавания образов и т.п. Целью изобретения инах.и. ф-лы, 2 ил. 4 ссоц, прирю ГОСУДАРСТВЕННЫЙ НОМИТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТПРИ ГННТ СССР является расширение функциональныхвозможностей за счет введения режимов "Поиск наибольшего-наименьшего","Поиск ближайшего большего-меньшегопо интервалу и сокращение аппаратных затрат. Указанная цель достигается тем, что в универсальный ассоциативный модуль, содержащий первыйблок 9 ассоциативной памяти, первыйрегистр 8 отклика, регистр 2 признака, введены второй блок 10 ассоциативной памяти, два счетчика-вычитателя 5,15, два элемента И-НЕ 3,6,второй регистр 11 отклика, два элемента ИЛИ-НЕ 7,12, элемент ИЛИ 14,блок 13 управления и счетчик 4,Изобретение относится к вычислительной технике и может быть использовано в вычислительных машинах и системах, системах распознавания образов, а также других устройствах обработки цифровой информации.Целью изобретения является расширение Функциональных возможностей за счет введения режимов "Поиск наибольшего-наименьшего","Поиск ближайшего большего-меньшего" и "Поиск большего-меньшего по интервалу" и сокращение аппаратных затрат путем реализации указанных операций в едином аппаратном модуле,10 На фиг. 1 представлена структурная схемЫ универсального ассоциатив-, ного модуля; на фиг. 2 - структурная 20 схема блока управления операциями.Универсальный ассоциативный модуль содержит вход 1 для записи ассоциативного признака в регистр 2 (фиг.1), элемент И-НЕ 3, счетчик 4, счетчик вычитатель 5, элемент И-НЕ 6, элемент. ИЛИ-НЕ 7, регистр 8 отклика, блоки 9 и 10 ассоциативной памяти ЗУ, регистр 11 отклика, элемент ИЛИ-НЕ 12, блок 13 управления, элемент ИЛИ 14, 30 счетчик-вычитатель 15, второй информационный вход 16 для записи числами, первый вход 17 для операции "Поиск ближайшего большего", второй вход 18 для операции Поиск наименьшего , 35 "Поиск ближайшего большего" и "Поиск ближайшего (большего) по интервалу", третий вход 19 подачи кода операции, первый выход 20 сигнала операции "Поиск наименьшего" для установки 40 счетчика 4 в "0", второй выход 21 для подачи импульсов счета на счетчик, третий выход 22 для подачи сигнала Занесение в счетчики", четвертый выход 23 для подачи импульсов 45 счета на счетчик-вычитатель 5, пятый выход 24 сигнала операции "Поиск наибольшего", четвертый вход 25 для управления операциями "Поиск наибольшего", "Поиск ближайшего меньшего", "Поиск ближайшего (меньшего) по интервалу, пятый вход 26 для управления операцией "Поиск ближайшего меньшего", шестой выход 27 для подачи импульсов счета на третий счетчик, 55 шестой вход 28 для управления операциями поиска по интервалу (" Поиск ближайшего на интервале Е", "Поискфт ближайшего большего на интервале Е"Поиск ближайшего меньшего на интервале Е ").Блок 13 управления (фиг.2) содержит элементы ИЛИ 29-31, элементы И 32-39, генератор 40 тактовых импульсов, элемент И 41, элементы ИЛИ 42- 43, дешифратор 44 кода операции и выходы 45-51 дешифратора 44.Устройство работает следующим образом.Исходное состояние блоков устройства при выполнении всех операций;в оба блока 9 и 10 ассоциативной памяти записаны одинаковые массивы инФормации;регистр 2, счетчик 4, счетчики- вычислители 5 и 15 сброшены в "0";регистры 8 и 11 отклика сброшены в "0"Значение кода операции (КОП), ассоциативного признака (А 11=Х) и значение интервала поиска для операпий "Поиск ближайшего большего (меньшего), ближайшего по интервалу Г подаются одновременно в дешифратор 44, регистр 2 и счетчик-вычислитель 15 соответственно. Дальнейшая работа устройства происходит в зависимости от кода операции.Операция "Поиск наименьшего".При этой операции (КОИ=О, АП=О, Е=О) возбуждается выход 45 дешифратора 44. Сигнал с этого выхода подается на вход элемента ИЛИ 42, на сброс счетчика 4 в "0" и на вход элемента И 32. Единичный сигнал со схемы ИЛИ 42 разрешает подачу тактовых импульсов с генератора 40 через схему И 41 на второй вход схемы И 32, а также производит копирование в счетчик 4 и счетчик-вычитатель 5 информации из регистра 2, Поскольку при выполнении данной операции ре" гистр 2 обнулен, то счетчик 4 также будет в состоянии "0". Следовательно, с выходов схемы дешифратора 44 и элемента ИЛИ-НЕ 7 будут сниматься единичные значения сигналов. С выхода элемента И 32 через элемент ИЛИ 29 начнут проходить тактовые импульсы на счетный вход счетчика 4. Содержимое этого счетчика начнет изменяться от нулевого значения в сторонувозрастания. При первом совпадениисодержимого счетчика 4 с содержимым%хотя бы одной ячейки ассоциативногозапоминающего устройства 9 в регистр8 отклика заносится единица и на выз14517 ходе эпемента ИЛИ-НЕ 7 устанавлива 11 11ется 0 , чт о приводит к пре к раще ню работы счетчика 4 , т ак к а к элемент И 3 2 закроется . Б результате в сч етчи 5 ке 4 будет зафиксировано наименьшее значение числа из того массива чисел, которые хранятся в ассоциативной памяти 9.Операция 1 Поиск ближайшего боль щего" к заданному числу.Для этом операции (КОП=001, АП=Х, Г=О) возбуждается выход 46 дешифратора 44, Сигнал с этого выхода поступает на вход элемента ИЛИ 42 и на 15 вход элемента И 33, Единичный сигнал с выхода элемента ИЛИ 42 разрешает подачу импульсов с генератора 40 тактовых импульсов на второй вход элемента И 32 и на копирование содержи мого регистра 2 в счетчик 4 и счетчик-вычислитель 5. Импульсы счета с выхода элемента ИЛИ 29, сформированные по сигналам "1" на входе 18 и на выходе 46 дешифратора 44, посту пают на счетный вход счетчика 4 до тех пор, пока очередное значение счетчика 4 не совпадет хотя бы с одним из значений содержимого ассоциативной памяти 9 или счетчик не будет 30 полностью заполнен. В первом случае произойдет установка в "01 выхода элемента ИЛИ-НЕ 7 и прекращение работы счетчика 4. Во втором случае произойдет установка в "0" элемента И-НЕ 3 с последующим прекращением работы счетчика.В результате в ассоциативной памяти 9 и счетчике 4 будет зафиксировано ближайшее большее к заданному 40 числу Х. В дальнейшем оно может быть обработано известным порядком.Операция "Поиск наибольшего" в массиве чисел (КОП=010; АП=О; С=О),Эта операция выполняется аналогич но операции "Поиск наименьшего 1. При подаче КОН=010 на вход дешифратора возбуждается его выход 47, по единичному сигналу с которого разрешается подача тактовых импульсов с генератора 40 за счет "1" с элемента ИЛИ 42, а также занесение в счетчик 4 и счетчик-вычитатель 5 содержимого регистра 2. Но поскольку для данной операции А 11=0, то по этому импульсу в счетчики также заносятся нули, однако по единичному сигналу с выхода 24 счетчик 5 уставнавливается в единичное состояние (т.е. все его раз 26ряды устанавливаются в "1") . Импульсы с генератора 40 через элемент И41 поступают на элемент И 35, навсех входах которого установленыразрешающие единичные сигналы с выходов дешифратора 44 и элемента ИЛИНЕ 12. С выхода элемента И 35 черезэлемент ИЛИ 30 импульсы поступаютна вычитающий вход счетчика-вычитателя 5, состояние которого с каждымимпульсом уменьшается на единицу.Так происходит до тех пор, пока в ассоциативной памяти 10 не произойдетсовпадение содержимого счетчика-вычитателя 5, являющегося признакомассоциативного поиска, хотя бы содной ячейкой ассоциативной памяти 10. Как только это случится, срегистра 11 поступит хотя бы однаединица в элемент ИЛИ-НЕ 12, чтоприведет к запрету прохождения импульсов через элемент И 35. Это означает, что найдено наибольшее из чисел, хранящихся в АЗУ.Операция "Поиск ближайшего меньшего" к заданному числу (КОН=100, А 11=Х,Й=О),Эта операция выполняется аналогичнс операции "Поиск ближайшего больше-.го". При этом возбуждается выход 48дешифратора 44, что разрешает засчет " 1" с выхода элемента ИЛИ 42прохождение импульсов с генератора 40через элемент И 41, а также копирование содержимого регистра 2 в счетчик4 и счетчик-.вычитатель 5, Импульсысчета с выхода элемента ИЛИ 30 поступают на вычитающий вход счетчикавычитателя 5. Это происходит дотех пор, пока очередное значениесчетчика-вычитателя 5 не совпадетс одним из значений из ассоциативнойпамяти 10 или счетчик не достигнетнулевого значения. В первом случаепроизой.".,ет установка в "0" выходаэлемента ИЗИ-НЕ 12 и прекращениеработы счетчика-вычитателя 5. Бовтором случае произойдет установкав "0" элемента И-НЕ 6 с последующимпрекращением работы счетчика-вычитателя 5,Б результате в ассоциативной памяти 10 и в счетчике-вычитателе 5 будет зафиксировано ближайшее меньшее к заданному числу Х. В дальнейшем оно может быть обработано известным порядком.5 14517Операция "Поиск ближайшего большего по интервалу" (КОП 101, АП=Х,Е=У).При выполнении этой операции воз 5буждается выход 49 дешифратора 44.При этом единичный сигнал с выходадешифратора через элементы ИЛИ 42и 43 разрешает выдачу импульсов сгенератора 40 через элемента И 41, атакже обеспечивает подачу "1" навход элемента И 38 соответственно.Импульсы с выхода элемента И 41 подаются на входы элемента И 34 и элемента И 32, Поскольку для данной опе Врации значение Е =У, т.е. в счетчикевычитателе 15 хранится значение, неравное нулю, то с выхода элементаИЛИ 14 будет сниматься единичный сигнал до тех пор, пока счетчик-вычита"тель 15 не обнулится и на всех егопрямых выходах не появятся нули.В этом случае прекратится прохождениеимпульсов через элементы 38 и 31 исчетчик 15 прекратит работу. Элемент 25И 34 пропускает импульсы через элемент ИЛИ 29 на счетный вход счетчика4 до тех пор, пока не будет найденоближайшее большее к заданному числу Хв пределах диапазона Е=У или не бу- ЗОдет достигнута граница этого диапазона. В первом случае по наличию "1"хотя бы в одном разряде регистра 8появится "0" на выходе элемента ИЛИНЕ 7, запрещающий прохождение импульсов через элемент И 34Это означает,что ближайшее большее в заданном интервале найдено. Во втором случаепо достижении границы диапазона Е=Усчетчик-вычитатель 15 обнулится и нулевой сигнал с выхода элемента ИЛИ14 запретит прохождение импульсов че-.рез элемент И 34Это означает, чтодостигнута граница диапазона поискаи операция завершена. Если при этом 4 Вв заданном интервале не оказалосьни одного числа, ближайшего большегок заданному числу Х, то на этот фактуказывает единичное значение сигналана выходе элемента ИЛИ-НЕ 7.БОСигнал с выхода 22 обеспечиваеткопирование исходных значений в счетчике 4 и счетчиках-вычитателях 5и 15,Операция "Поиск ближайшего меньше- ВВго по интервалу" (КОП=110, АП=Х,Я=у) .Эта операция выполняется аналогично предыдущей, При подаче кода опера 26 6ции на вход дешифратора 44 возбуждается его выход 50, Точно так же единичное значение сигнала с его выходаразрешает прохождение импульсов через элемент И 37, элемент И 41 и элемент И 38 и происходит копированиезначений Х, У в счетчик 5 и счетчики-вычитатели 5 и 15. Аналогично также осуществляется цикл обработкизначения У в счетчике-вычитателе 15,т.е. импульсы на него подаются свыхода элемента ИЛИ 31 до тех пор,пока он не обнулится и нулевые сигналы с его прямых выходов не закроютэлементы 37 и 38.Разница состоит в том, что импульсы счета с выхода 23 элемента ИЛИ 30поступают на счетчик-вычитатель,вследствие чего производится поискпо совпадению в ассоциативной памяти10 уменьшающихся с каждым импульсомсчета значений Х. Это происходит донаступления одного из двух событий:либо будет найдено искомое значение,либо будет достигнута граница интервала поиска, В первом случае произойдут установка в "0" выхода элемента ИЛИ-НЕ 12 и прекращение прохождения импульсов через элемент И 37 состановкой счетчика-вычитателя 5. Вовтором случае произойдут установкав "0" выхода 28 элемента ИЛИ 14 ипрекращение прохождения импульсов через элемент И 37 с остановкой счетчика. факт отсутствия в заданноминтервале ближайшего меньшего определяется по единичному значению сигнала на выходе элемента ИЛИ-НЕ 12.Операция "Поиск ближайшего по интервалу" (КОП 111, АП=Х, С=У).При выполнении этой операции должно быть найдено число, ближайшего кзаданному числу Х в пределах диапазона Х+с,При подаче кода операции на входдешифратора 44 возбуждается его выход 51, При этом аналогично как впредыдущем случае происходит формирование серии импульсов на выходе элемента И 41, которые подаются на входэлемента И 39, На остальные четыревхода элемента И 39 подаются единичные сигналы с выходов элементов ИЛИНЕ 7 и 12, с выхода 51 дешифратораи с выхода элемента ИЛИ 14 единицана выходе элемента ИЛИ 14 устанавливается с занесением в счетчик-вычитатель 15 значения, отличного от ну 1451726ля). Таким образом, импульсы с выхода элемента И 39 поступают одновременно на счетный вход счетчика 4 и вычитающий вход счетчиков-вычитате 5 лей 5 и 15, В счетчике 4 и счетчике-вычитателе 5 начинается выработка значений, соответственно возрастающих и уменьшающихся относительно начального значения Х. В счетчике-вычита О теле 15 происходит выработка уменьшающегося до нуля значения, отсчитывающего интервал поиска Е =У. При достижении счетчиком-вычитателем 15 значения, равного нулю, происходит 1 Б завершение операции путем обнуления входа элемента И 39, связанного с выходом элемента ИЛИ 14. Если к этому моменту не произошло ни одного совпадения ассоциативной памяти 9 2 О и 10 с содержимым счетчика 4 и счетчика-вычитателя 5, то этом состояние будет зафиксировано единичными значениями выходов элементов ИЛИ-НЕ 7 и 12. В противном случае элемент И 25 39 закроется нулевым сигналом по входу 18 и/или 25, что означает обнаружение ближайшего к заданному числу Х на интервале Е. Копирование Х всчетчик 4 и счетчик-вычитатель 5 как и ранее производится сигналом с выхода 22 блока 13,Формула изобретения351. Универсальный ассоциативный модуль, содержащий первый блок ассоциативной памяти, первый регистр отклика, регистр признака, информационный вход которого является первым информационным входом устройства, выход совпадения первого блока ассоциативной памяти соединен с информационным входом первого регистра отклика, о тл и ч а ю щ и й с я тем, что, с целью расширения функциональных возможностей за счет введения режимовПоиск наибольшего-наименьшегоПоиск ближайшего большего-меньшего "Поиск ближайшего большего-меньшего по интервалу" и сокращения аппаратных затрат, в него введены второй блок ассоциативной памяти, два счетчика-вычитателя, два элемента И-НЕ, второй регистр отклика, два элемента ИЛИ-НЕ, элемент ИЛИ, блок управ 55 ления и счетчик, разряды выхода которого соединены с разрядами входа поиска по совпадению первого блока ассоциативной памяти и с входами первого элемента И-НЕ, выход которого соединен с первым входом блока управления, первый выход которого со. единен с входом сброса счетчика, выход регистра признака соединен с информационным входом счетчика и первого счетчика-вычитателя, прямой выход которого соединен с входом поиска по совпадению второго блока ассоциативной памяти, выход совпадения которого соединен с информационным входом второго регистра отклика, разряды выхода которого соединены с входами второго элемента ИЛИ-НЕ, разряды выхода первого регистра отклика соединены с входами первого элемента ИЛИ-НЕ соответственно, выход которого соединен с вторым входом блока управления, третий вход которого соединен с входом задания режима устройства, второй информационный вход которого соединен с информационным входом второго счетчика-вычитателя выход второго элемента ИЛИ-НЕ соединен с четвертым входом блока управления, второй выход которого соединен со счетным входом счетчика, вход которого соединен с входом записи второго счетчика-вычитателя, третьим выходою блока управления, входом записи первого счетчика-вычислителя, разряды инверсного выхода которого соединены с входами второго элемента И-НЕ, выход которого соединен с пятым входом блока управления, четвертый выход которого соединен с вычитающим входом первого счетчика-вычитателя, вход установки в "1" которого соединен с пятым выходом блока управления, шестой выход которого соединен с вычитающим входом второго счетчика-вычитателя, разряды информационного выхода которого соединены с входами элемента ИЛИ, выход которого соединен с шестым входом блока управления.2. Модуль по п. 1, о т л и ч а ющ и й с я тем, что блок управления содержит дешифратор, девять элементов И, пять элементов ИЛИ и генератор импульсов, первый вход блока соединен с первым входом первого элемента И, второй вход блока соединен первыми входами второго, третьего и восьмого элементов И и вторым входом первого элемента И, третий вход блока соединен с адресным входом Лешифратора, первый выход которого сое 1451726динен с вторым входом первого элемента И, первым входом первого элемента ИЛИ и первым выходом блока, вто" рой выход дешифратора соединен с вто 5 рым входом первого элемента ИЛИ и третьим входом первого элемента И, выход которого соединен с первым вхо дом второго элемента"ИЛИ, выход которого соединен с вторым выходом 1 О блока, третий выход дешифратора соединен с первым входом четвертого элемента И, пятым управляющим выходом блока и третьим входом первого элемента ИЛИ, выход которого соеди нен с третьим выходом блока и первым входом девятого элемента И, выход которого соединен с первым входом пятого, шестого и седьмого элементов И, вторыми входами третьего, четверто О го и восьмого элементов И, третьим входом второго элемента И и четвертым входом первого элемента И, четвертый выход дешифратора соединен с четвертым входом первого элемента ИЛИ 25 и вторым входом пятого элемента И, выход которого соединен с первым входом третьего элемента ИЛИ, выход которого соединен с четвертым выходом устройства, пятый выход дешифратора ЗО соединен с пятым входом первого элемента ИЛИ, третьим входо третьего элемента И и первым входом четвертого элемента ИЛИ, выход которого соединен с вторым входом седьмого элемента И, выход которого соединен спервым входом пятого элемента ИЛИ,выход которого соединен с шестымвыходом блока, шестой выход дешифратора соединен с шестым входом первого элемента ИЛИ, вторым входом шестого элемента И и вторым входом четвертого элемента ИЛИ, седьмой выходдешифратора соединен с седьмым входом первого элемента ИЛИ и третьимвходом восьмого элемента И, выходгенератора импульсов соединен с вторым входом девятого элемента И, четвертый вход блока соединен с третьимвходом четвертого, пятого и шестогоэлементов И и четвертым входом восьмого элемента И, выход которого соединен с вторыми входами второго, третьего и пятого элементов ИЛИ, пятыйвход блока соединен с четвертым входом пятого элемента И, шестой входблока соединен с третьим входомседьмого элемента И, четвертым входом третьего и шестого элементов Ии пятым входом восьмого элемента И,выходы второго и третьего элементовИ соединены с третьим и четвертым входами второго элемента ИЛИ соответственно, выходы четвертого и шестогоэлементов И соединены с третьим ичетвертым входами третьего элемента ИЛИ соответственно.77 76 25 Заказ 7083/49 Тираж 6 ВНИИПИ Государственного комит 113035, Москвпо изобретениям иЖ, Раушская наб оеткрытиям при ГКНТ СССР4/5