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

(54) А УСТРОЙ (57) И литель рсйств назнач вычисл ОМИНАЮЩЕ СОЦИАТИВНОЕТВОобретение оой технике,м храненияно для электельных сис тносится к вычисв частности к устинформации, и предтронных цифровыхтем. Цель иэобреГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР. ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В.И,Корнейчук, А.П.Марковский и Ю.В.Яблуновский(56) Авторское свидетельство СССР У 978196, кл, С 11 С 15/00, 1980.Авторское свидетельство СССР332502, кл. С 11 С 15/00, 1970,ЯО, 143 щр тения - расширение области применения устройства за счет введения дополнительных критериев поиска в метрике Хэмминга. Ассоциативное запоминающее устройство содержит блок 1 памяти размерностью пш (где и - количество разрядов признака опроса, а а - количество признаков информации), и - разрядный регистр 2 опроса, выполненный в виде регистра сдвига, блок 3 управления, группу элементов ИЛИ, 4, группу счетчиков 5, первый элемент ИЛИ 6, буФерный регистр 7, выполненный на Э-триггерах, регистр 8 результата поиска, выполненный на Т-триггерах, генератор 9 тактовых импульсов, щ2 элемент 1 О задержки, счетчик 11, первый 12, второй 13 и третий 14 элементы И, первый 15, второй 16 и тре- еф тий 17 элементы И-НЕ, второй элемент ИЛИ 18, коммутатор 19, 2 ил.1437920 Устройство работает следующим образом.Перед началом работы устройства счетчики 5, 11 и регистры 7, 8 обнулены. В блоке 1 хранятся признаки информации, а в регистре 2 - признаки опроса. При этом на выходах блока 3 управления поддерживаются следующие сигналы; Р .выхода 20 21 22 23 24 Сигнал 0 О 0 135 При поступлении на вход 32 блока 3 управляющего импульса в регистр 36 адреса микрокоманд по входу 33 запишется код команды "Подготовка к по 11иску . В результате блоком 3 управ ления на выходах 20-22 выдаются единичные сигналы, обеспечивающиесчитывание из блока 1 старшего или младшего разряда всех признаков информации с синхронной выборкой чз 45 регистра 2 опроса соответствующего разряда признака опроса. Ксли из регистра 2 считан единичный. сигнал, то сигналы на выходах коммутатора 19 аналогичны сигналам, считанным с пря-"50 мых выходов блока 1 (единицами на выходах коммутатора 19 отмечаются совпавшие разряды соответствующих признаков информации и признака опроса), иначе считываются сигналы с инертных выходов блока 1. Далее единичные сигналы, проходя через элементы ИЛИ 4, записываются в соответствующие счетчики 5. 25 26 27 28 29 30 1 О 0 0 0 0 Изобретение относится к вычислительной технике, в частности к устройствам хранения, информации, и предназначено для электронных цифровых вычислительных систем.Цель изобретения - расширение области применения устройства эа счет введения дополнительных крчтериев поиска в метрике Хзмыинга, 1 ОНа фиг, 1 изображена Функциональная схема предложенного ассоциативного устройства; на Фиг. 2 - функциональная схема блока управления,Ассоциативное запоминающее устройство содержит (Фиг. 1) блок 1 памяти размерностью и ш (где и - количество разрядов признака информации, а ш - количество признаков инФормации), и-разрядный регистр 2 20 опроса, выполненный в вице регистра сдвига, блок 3 управления, группу элементов ИЛИ 4, группу счетчиков 5, первый элемент ИЛИ 6, буферный регистр 7, выполненный на В-триггерах, регистр8 результата поиска, выполненный на Т-триггерах, генератор 9 тактовых импульсов, элемент 10 задержки, счетчик 11, первый 12, ьторой 13 и третий 14 элементы И, первый 15, второй ЗО 16 и третий 17 элементы И-НК, второй элемент ИЛИ 18 и коммутатор 19. Блок 3 управления имеет выходы 20-30 и входы 31-33. Устройство имеет вход 34.Блок 3 управления содержит (фиг,2) коммутатор 35, регистр 36 адреса микрокоманды, дешифратор 37, генератор 38 тактовых импульсов, микропрограммную матрицу 39, регистр 40 микро- команд. Запоминающие ячейки блока 1 памяти могут иметь различную конструкцию (сдвиговые регистрь дорожки вращающихся магнитных дисков и т,п,). Однако они должны обеспечивать последовательное, поразрядное обращение, а именно: при поступлении очередного управляющего импульса на управляющий вход блока 1 с выхода каждой запоминающей ячейки считывается очередной разряд содержимого данной ячейки. После окончания серии иэ и аналогичных микрокоманд в счетчиках 5 хранятся суммы количества совпадений разрядов всех признаков информации и признака опроса, а на выходе 22 блока 3 устанавливается нулевой сигналблокировки коммутатора 19 (на его выходах формируется нулевой код), который поддерживается до окончания любого вида поиска. При этом на вход 32 блока 3 поступает управляющий импульс, разрешающий запись в регистр 36 кода заданного нида поиска (адрес первой мнкрокоманды поиска),Рассмотрим теперь поиск по различным критериям1, Поиск ближайшего по Хэммингу.В первой микрокоманде поиска на выходах 26 и 27 блока 3 Формируются единичные сигналы. Если среди признаков информации нет признака, равного признаку опроса, то единичным сигналом с выхода первого элемента И 12. После переполнения счетчика 11 работа всех счетчиков прекращается (это обеспечивается подачей на вход первого элемента И 12 нулевого сигнала), а в регистре 8 единицами фиксируется результат поиска.Данный вид поиска является базовым для всех последующих видов поиска. 55 з14379запускаются на счет счетчики 5 и счетчик 11, иначе данный признак отмечается единицей в регистре 8 результата. При переполнении какого-либо изсчетчиков 5 единичный сигнал с выхода первого элемента ИЛИ 6 устанавливает на выходах третьего элементаИ-НЕ 16 и первого элемента И 12 сигнал нулевого уровня, т.е, останавливает все счетчики, Кроме того, этотже сигнал, инвертируясь первым элементом И-НЕ 15, на втором входе этого элемента поддерживает единичныйсигнал, т,е. сигнал переполнения 15счетчика 11 нулевого уровня, но счетчик 11 не переполнен, разрешает запись в регистры 7, 8 кода, поступающего с выходов переполнения счетчиков 5. Таким образом, в регистре 8единицей отмечается признак, ближайший по Хэммингу к признаку опроса,а в счетчике 11 фиксируется его расстояние Хэмминга к признаку опроса.2. Поиск всех больших границы Хэмминга,В первой микрокоманде поиска навыходе ЗО блока 3 формируется сигналразрешения записи в счетчик, кудапо входам 34 поступает значение К(граничное расстояние Хэмминга). Вследующей микрокоманде на выходах 28и 26 блока 3 установится единичныйсигнал, а на выходе 27 - сигнал нулевого уровня, т.е, блокируется за 35пись в регистр 36, запускаются всесчетчики на счет. При переполнениикакого-либо из счетчиков 5 единичныйсигнал с соответствующего выхода переполнения записывается в регистр 7 40(в нем хранится только последний единичный сигнал переполнения), послечего он перезаписывается в регистр 8,причем те триггеры, на информационныевходы которых поступает единичный 45сигнал, меняют свое состояние напротивоположное, при поступлениинулевого сигнала их состояние неизменяется,50 203. Поиск всех меньших границы Хэмминга.После выполнения базового поиска в очередной микрокоманде на выходе 23 блока 3 управления формируется сигнал установки в единицу всех разрядов регистра 7, а на выходе 24 - сигнал разрешения записи в регистр 8. Таким образом, содержимое регистра 8 проинвертируется, т.е. единицами в нем отмечаются все признаки, меньшие границы Хэмминга.4. Поиск ближайшего большего границы Хэмминга.После выполнения базового поиска в очередной микрокоманде на выходе 25 блока 3 управления формируется сигнал обнуления регистра 8, а на выходе 24 - сигнал разрешения записи в регистр 8. Таким образом, в нем фиксируется результат данного вида поиска.5. Поиск равного границе Хэмминга.После выполнения базового поиска на выходе 25 блока 3 формируется сигнал разрешения обнуления регистра 8, а на выходе 29 - сигнал разрешения счета счетчика 11. Таким образом, на выходе переполнения счетчика 11 устанавливается единичный сигнал и про" исходит запись в регистры 7, 8 результата поиска (если существует признак информации, расстояние Хэмминга которого равно границе Хэмминга).6Поиск ближайшего меньшего границы Хэмминга.После выполнения базового поиска на выходе 29 блока 3 формируется единичный сигнал разрешения счета счетчиком 11 (его обнуление). На выходах 26 и 27 блока 3 устанавливается соответственно сигнал единичного и нулевого уровней (при этом запускаются на счет все счетчики), а на выходе 25 - сигнал обнуления регистра 8. Затем на выходах 26 и 27 блока 3 устанавливается единичный сигнал, т.е. разрешается остановка всех счетчиков при появлении первого сигнала переполнения счетчиков 5. После появления этого сигнала в регистре 8 зафиксируется результат поиска, а в счетчике 11 - его расстояние Хэмминга по отношению к границе Б.,7. Поиск в интервале границ Хэмминга.При осуществлении данного вида поиска базовый поиск выполняется два5 14раза: в первом случае на счетчик 11записывается К а после окончанияпервого базового поиска сигналом свыхода 25 блока 3 осуществляется обнуление регистра 8. В счетчик 11.записывается Я - К,) и происходитвторой базовый поискпосле чего навыходе 29 блока 3 формируется единичный сигнал, т,е. счетчик 11 устанавливается н исходное состояние, а нрегистре 8 фиксируется результат поиска.8. Поиск нне интервала границ Хэмминга.После выполнения предыдущего нидапоиска осуществляются операции, аналогичные поиску всех меньших границХэмминга, т.е, проинвертируется содержимое регистра 8,В рассмотренных случаях все разряды признака опроса имели равные веса,однако для многих практических применений необходимо проведение описанных видов поиска для признака опроса,разряды которого имеют различные весовые коэффициенты, Тогда размерностьсчетчиков 5 и 11 увеличивается. Работа устройства в данном режиме начинается подачей запускающего импульса на вход 32 блока 3, при этом в регистр 36 по входам ЗЗ запишется код команды "Подготонка к поиску",В первой микрокоманде этой команды сигналом с выхода 30 блока 3 разрешается запись веса разряда в счетчик 1 1, а также формируется единичный сигнал на выходе 28 этого блока, т,е. запрещается запись в регистр 36. Помимо этого единичными сигналами с выходов 20-22 блока 3 разрешается выборка старшего или младшего разряда из регистра 2 и блока 1 и разблокируется коммутатор 19. Сигналом с выхода 29 блока 3 запускается на счет счетчик 11 и хранящийся в нем код перезаписынается в счетчики 5, на входы которых поступает единичный сигнал. После переполнения счетчика 11 блокируется коммутатор 19 и разрешается запись в регистр 36. После окончания и аналогичных тактов работы устройства выполняется один из описанных видов поиска.Если веса разрядов признака опрооса равны степени двойки (2 , 2 2 ), а в регистре 2 записан единичный код, то после выполнения описан Ассоциативное запоминающее устройство, содержащее блок памяти,. регистр опроса, информационные входы которого являются признаковыми входами устройства, группу элементов ИЛИ, первый элемент ИЛИ, буферный регистр, блок упранления и группу счетчиков, выходы переполнения которых подключены к информационным входам буферного регистра и к входам первого элемента ИЛИ, причем входы счетчиков группы подключены к ныходам элементов ИЛИ группы, вход "Запуск" и вход "Тип поиска" блока управления являются соответственно входом обращения и входом задания типа поиска устройства, о тл и ч а ю щ е е с я тем, что, с целью расширения области применения устройства за счет введения дополнительных критериев поиска н метрике Хэмминга, в него введены коммутатор, генератор тактовых импульсов, счетчик, второй элемент ИЛИ, первый, второй и третий элементы И, элемент задержки, первый, второй и третий элементы И-НЕ и регистр результата поис ка, информационные входы которого соединены с выходами буферного регистра, вход синхронизации регистра результата поиска соединен с выходом элемента задержки, вход которого соединен с выходом третьего элемента И, первый вход которого подключен к входу синхронизации буферного регистра и к выходу первого элемента И-НЕ, первый вход которого соединен с ныходом первого элемента ИЛИ и с первым входом второго элемента И-НЕ, выход которого соединен с первым входом первого элемента И, второй вход которого подключен к выходу генератора тактовых импульсов и к первому входу второго элемента И, выход которого соединен с входом раэреше 20 25 30 35 40 45 50 55 37920 6ной команды 1 Подготовка. к поиску" данное устройство может выполнять следующие виды поиска; поиск максимального числа; поиск всех больших заданного числа; поиск ближайшего большего к заданному числу; поиск всех меньших заданного числа; поиск ближайшего меньшего заданного числа; простой ассоциативный поиск; поиск чисел, входящих в заданный интервал; поиск чисел, не нходящих н заданный интервал.Формула и э о б р е т е н и яодпис Тираж 59сударственного км изобретений ива, Ж, Раушск митета СССРткрытийя наб., д. 4/5 город, ул, Проектная, 4 иятие Производст о-полиграфическ 11437 ния блокировки коммутатора, информационные входы первой и второй групп которого подключены к прямым и инверсным выходам блока памяти, управляющий вход коммутатора соединен с выходом регистра опроса, выходы коммутатора подключены к первым входам элементов ИЛИ группы, вторые входы которых подключены к выходу первого эле.10 мента И и к первому входу второго элемента ИЛИ, выход которого соединен с входом разрешения счета счетчика, выход переполнения которого соединен с третьим входом первого и вторым 1 с входом второго элементов И, с вторым входом первого элемента И-КЕ и с первым входом третьего элемента И-НЕ,11 выход которого подключен к входу Пе 920 8реход к следующей микрокоманде" блока управления, выходы которого с первого по одиннадцатый соответственно соединены с управляющим входом регистра опроса, с управляющим входом блока памяти, с третьим входом второго элемента И, с входом установки в "1" буферного. регистра, с вторым входом третьего элемента И, с входом установки в "0" регистра результата поиска, с четвертым входом первого элемента И, с вторым входом второго элемента И-НЕ, с вторым входом третьего элемента И-НЕ, с вторым входом второго элемента ИЛИ и счетным входом счетчика, входы разрядов которого являются входами установки границы Хэмминга.