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

о 30.0 ковани убли делам изебрет и еткрмтий. Матв об етен занский ордена Трудового Красного Знаме им. А. Н. Туполев1) Заявител УСТРОЙСТВО 4) АССОЦИАТИВНОЕ ЗАПОМИНАЮ Изобретение относится к запоминающим устройствам и может быть использовано при решении задач, связанных с определением окрестностей экстремальных точек, например, при цифровой обработке радиолокационной информации,Известное ассоциативное запоминающее устройство с параллельной обработкой разрядов содержит матрицу запоминающих ячеек, каждая из которых состоит из триггера и логических схем 1.Недостатки данного устройства - отсутствие возможности ограничения окрестности экстремальных признаков и большие аппаратурные затраты.Наиболее близким к предлагаемому является ассоциативное запоминающее устройство с последовательной обработкой разрядов, содержащее регистры признаков, детекторный регистр, регистр маски, схемы ИСКЛЮЧАЮЩЕЕ ИЛИ, ИЛИ-НЕ, И-НЕ по числу регистров признаков и схему И, причем выходы регистров признаков подключены к первым входам соответствующих схем ИСКЛЮЧАЮЩЕЕ ИЛИ и первым входам триггеров регистра маски, вторые входы схем ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с инверсным входом разрядов опрашиваемого признака, а выходы подключены к первым входам схем ИЛИ-НЕ и первым входам схем И-НЕ, вторые входы схем ИЛИ-НЕ соединены со входом разрядов маски, а выходы подключены к первым входам триггеров детекторного регистра, вторые входы которых являются входами синхронизации, а третьи - входами начальной установки; выходы триггеров детекторного регистра подключены ко вторым входам схем И-НЕ и вторым входам триггеров регистра маски, выходы схем И-НЕ подключены ко входам схемы И 12.Недостатки известного устройства - отсутствие возможности ограничения окрестности экстремального признака и низкое быстродействие вследствие того, что определение каждого признака выполняется за два цикла поиска.Цель изобретения - повышение быстрощ действия устройства, а также реализацияпоиска множества признаков, входящих в фиксированную окрестность экстремального признака, заданную ее длиной.Поставленная цель достигается тем, чтов ассоциативное запоминающее устройство, 902073НЕРАВНОЗНАЧНОСТЬ, выходы которых соединены с первыми входами соответствующих элементов ИЛИ-НЕ и элементов И-НЕ,вторые входы элементов ИЛИ-НЕ подключены к выходу элемента И, входы которого соединены соответственно с выходами элементов И-НЕ, вторые входы которых подключены соответственно к выходам триггеров, первые входы которых соединены с выходами соответствующих элементов ИЛИ-НЕ, вторые входы элементов НЕРАВНОЗНАЧНОСТЬ и триггеров являются установочными входами, а третьи входы триггеров - вхо э дами синхронизации устройства, введены коммутаторы, блоки логического анализа,группу элементов И, элемент ИЛИ и регистр сдвига, причем. выходы элементов И группы подключены соответственно ко входам элемента ИЛИ, выход которого соединен.с пер 20 выми входами коммутаторов, вторые входы которых подключены к выходам соответствующих регистров признаков и первым входам элементов И группы соответственно, вторые входы которых соединены с выхода ми соответствующих триггеров, первые и вторые информационные входы блоков логического анализа подключены к выходам соответствующих коммутаторов, а третьи информационные входы соединены с выходом регистра сдвига, третьи входы коммутаторов и выходы блоков логического анализа являются соответственно управляющими входами и выходами устройства. 30 При этом блок логического анализа содержит триггеры, элементы И, НЕ и ИЛИ; причем выходы первого и второго элементов И подключены соответственно к первым входам первого триггера и первого элемента ИЛИ, выход которого соединен со вторым входом первого триггера, выходы элементов И с третьего по восьмой подключены соот 35 40 ветственно ко входам второго элемента ИЛИ,выход которого соединен с первым входом второго триггера, второй вход которого подключен ко второму входу первого элемента ИЛИ, инверсный выход второго триггера соединен с первыми входами первого и второго элементов И, прямой выход первого триггера подключен к первым входам третьего, четвертого и пятого элементов И, а инверсный выход - к первым входам шестого, седьмого и восьмого элементов И, выход первого элемента НЕ соединен со вторыми входами первого, третьего и пятого элементов И, а вход - со вторыми входами второго, шестого и седьмого элементов И, второй вход четвертого и третьи входы первого и пятого элементов И подключены ко входу второго элемента НЕ, выход которого соесодержащее регистры признаков, элементы НЕРАВНОЗНАЧНОСТЬ, триггеры, элементы ИЛИ НЕ, элементы И-НЕ и элемент И,причем выходы регистров признаков подключены соответственно к первым входам элементов 45 50 И динен с третьими входами второго и шестого элементов И и вторым входом восьмого элемента И, четвертый вход первого элемента И и третьи входы третьего и четвертого элементов И подключены к выходу третьего элемента НЕ, вход которого соединен с четвертым входом второго элемента И и третьими входами седьмого и восьмого элементов И, входы первого, второго и третьего элементов НЕ являются соответствующими информационными входами, второй вход второго триггера - установочным входом, третьи входы триггеров - входом синхронизации, а инверсный выход первого триггера является выходом блока логического гнализа,На фиг. 1 изображена функциональная схема предлагаемого устройства; на фиг. 2 - блок логического анализа; на фиг. 3 - граф состояний блока логического анализа.Устройство содержит (фиг. 1) регистры 1 признаков, выполненные в виде регистров сдвига, элементы НЕРАВНОЗНАЧНОСТЬ 2, элементы ИЛИ-НЕ 3, триггеры 4, элементы И-НЕ 5, элемент И 6, группу элементов И 7, элемент ИЛИ 8, коммутаторы 9, регистр 10 сдвига, предназначенный для задания длины окрестности экстремального признака, блоки 11 логического анализа, а также выходы 12, установочные входы 13 и 14, входы 15 синхронизации и управляющие входы 16 устройства информационные 17 и управляющие 18 входы регистров 1, первый 19, второй 20 и третий 21 информационные входы блока логического анализа. При этом блок 11 логического анализа содержит (фиг. 2) первый 22 и второй 23 триггеры, первый 24, второй 25 и третий 26 элементы НЕ, первый - восьмой элементы И 27 - 34 и первый 35 и второй 36 элементы ИЛИ. Граф (фиг. 3) отражает состояние а, - а блока 11 и сигналы С 1 - Са перехода из одного состоя. ния в другое.Устройство работает следующим образом,Каждый блок 11 формирует значение логического условия вхождения признака в заданную окрестность экстремального признака1., - 1.,+ К 0,где 1.1 = х - в случае поиска признаков,входящих в окрестность мак 2 вахсимального признака; 1., == хп 1; 1. = х; для поискапризнаков, входящих в окрестность минимального признака;х; - значение 1-го признака;х хх,;- значение максимального (минимального) признака;К - заданная длина окрестностиэкстремального признака.Пусть 11, 1.ъ, К - гп-разрядные двоичныечисла:1-1 = 1 1 1 1 1 21з 1 1 1 ,1-г = 1 1 1 г 21 з з 1 211 тК = К 1 КгК) К где 1, г, К) - двоичные разряды,- номер разряда.Обозначим через А; число, получающееся из А путем отбрасывания всех младших разрядов, начиная с (1 + 1)-го разряда. Тог да, если1.1 - 1.г+ К =А; 11 - 1 г) + К) = а),тоА) -- Ь) - 1.г + Кили в итерационной формеА) -- 2 А) + а), 1 = 1,2,3гп;А 1 = а 1Анализ условия А0 выполняется в виде определенного числа итераций. На каждом -ом шаге определяется А 1 коррекцией А, в зависимости от значения а;, при этом (а; а О, + 1, + 2) . При этом определяется лишь семь возможных значений А: О, -1, -2, +3.Если А 1 е - 2, - 3), то делается окончательный вывод о невыполнении условия А20 30 и анализ последующих разрядов чисел ххтзхили хи К блокируется; если А, 1,2, то устанавливается, что А )О; йри А.е 0,1 анализ последующих разрядов продолжается, Так как А= А, то при А О, -1, +2, +3 выполняется т итераций, т. еанализу подвергаются все разряды чисел, содержащихся в регистрах 1 (фиг. 1).Рассмотрим работу устройства на примере поиска множества признаков, входящих в окрестность максимального признака. 30Перед началом работы все триггеры 4 (фиг. 1) устанавливают в единичное состояние по входам 14, на вход 13 подаются нулевые сигналы, что соответствует установке всех разрядов сравниваемого признака в единичное состояние. Сравнение разрядов признаков, хранящихся в регистрах 1, ведут последовательно, начиная со старших, с помощью элементов НЕРАВНОЗНАЧНОСТЬ 2, Первое встретившееся неравенство фиксируется нулевым сигналом на выходе соответ ствующего элемента НЕРАВНОЗНАЧНОСТЬ 2, который через элемент ИЛИ-НЕ 3 устанавливает триггер 4 в нулевое состояние, причем анализ последующих разрядов соответствующего признака блокируется. Когда некоторый разряд всех признаков 45 содержит нуль, то все триггеры 4 находятся в нулевом состоянии и поиск единицы в признаках пропускается, так как в этом случае на выходе элемента И б устанавливается единичный сигнал, поступающий на входы всех элементов ИЛИ-НЕ 3. 50Наличие единичного сигнала на выходе 1-го триггера 4 после анализа 1-го разряда указывает на то, что 1-ый признак соответствует максимальному с точностью до -го разряда, а после анализа всех разрядов - на максимальный признак.Последовательно определяемые разряды максимального признака хпоступают через элементы И 7 и элемент ИЛИ 8 на первые входы коммутаторов 9, на вторые входы которых подаются значения разрядов соответствующих признаков с выходов регистров 1. В случае определения признаков, входящих в окрестность максимальногс признака, сигнал на управляющих входах 16 равен единице и коммутаторы 9 обеспечивают выдачу на входах 19 блоков 11 значений разрядов х;, а на входах 20 - значений х На входы 21 блоков 11 подаются последовательно с выхода регистра 10 сдвига значения разрядов К длины окрестности максимального признака.. В каждом блоке 11 для каждого )-го разряда определяется число А, фиксируемое в виде определенного состояния а 1 - а (фиг. 3). Значение А -- 0 фиксируется в виде начального состояния а 1, А = - 1 в виде состояния аь. При А е 1, 2 блок 11 (фиг. 2) переходит в конечйое состояние аг (фиг. 3), при А) 2, - 31 - в конечное состояние а 4. (фиг. 3)Каждое состояние блока 11 кодируется определенным набором состояний триггеров 22 и 23 (фиг. 2); состояние а (фиг. 3) кодируется набором (О, 0), аг - набором (О, 1 аз - набором (1, 0) и а 4 - набором (1, 1).Если блок 11 (фиг. 2) находится в состоянии а (фиг. 3), то при поступлении на входы 19, 20 и 21 (фиг, 2) любого набора сигналов из множества С 1 = (О, О, 0); (О, 1, ,1); (1, 1, 0) (фиг. 3) состояние а не меняется, при поступлении сигналов С = 1(0, 1, ,0 переходит в промежуточное состояние аз, которое сохраняется при поступлении любого набора сигналов из множества С 4 = = (0,0, 1); (1, О, 0); (1, 1, 1)1 . Из состояния аз блок 11 (фиг. 2) переходит в начальное состояние а (фиг. 3) под действием сигналов С = 1(1, О, 1) . Любой набор сигналов из множества Сб = С 1 и С 4 переводит блок 11 (фиг. 2) из состояния аз (фиг. 3) в конечное состояние ав котором он не реагирует на сигналы на входах 19, 20 и 21 (фиг, 2)Под действием любого набора сигналов из множества С 5 = Сг 1.Сз (фиг, 3) блок 11 (фиг. 2) переходит в конечное состояние аг (фиг. 3). Таким образом, после анализа всех разрядов признаков триггеры 22 и 23 (фиг. 2) находятся соответственно в нулевом и единичном состояних, если А0; единичном и нулевом состояниях, если А = - 1, в нулевых состояниях, если А = 0 и единичных, если А ( - 1, Отсюда следует, что нулевое состояние триггера 22 является признаком выполнения условия А ЗО. Это свидетельствует о том, что соответствующий признак х; входит в окрестность максимального признака х , заданную длиной К. Выявление всех признаков, входящих в заданную окрестность, осуществляется параллельно за один цикл поиска, состоящий из последователь 902073ного анализа всех разрядов чисел, хранящихся в регистрах 1.При поиске признаков, входящих в окрестность минимального признака, устройство работает аналогично, но при этом на вход 13 (фиг. 1) подаются единичные сигналы, что соответствует установке всех раз-рядов сравниваемого признака в нулевое состояние. На входы 16 при этом подаютя нулевые сигналы и коммутаторы 9 обеспечивают выдачу на входах 19 блоков 11 значений разрядов х ;, а на входах 20 - значе-, ний х; . После анализа всех разрядов признаков нулевые сигналы на выходах 12 (фиг. 1 признаки входят в окрестность минимально.го признака.Технико-экономические преимущества 1 формула изобретения ИЛИ-НЕ, вторые входы элементов НЕРАВНОЗНАЧНОСТЬ и триггеров являются ус- ффтановочными входами, а третьи входы триг 45 и 2) указывают на то, что соответствующие предлагаемого устройства заключаются в реализации выполняемого за один цикл поиска множества признаков, входящих в фиксированную по длине окрестность экстремального признака, и в повышении быстродействия по сравнению с известным устройством. 1. Ассоциативное запоминающее устройство, содержащее регистры признаков, элементы НЕРАВНОЗНАЧНОСТЬ, триггеры, элементы ИЛИ-НЕ, элементы И-НЕ и элемент И, причем выходы регистров признаков подключены соответственно к первым входам элементов НЕРАВНОЗНАЧНОСТЬ, выходы которых соединены с первыми входами соответствующих элементов ИЛИ-НЕ и элементов И-НЕ, вторые входы элементов ИЛИ-НЕ подключены к выходу элемента И, входы которого соединены соответственно с выходами элементов И-НЕ, вторые входы которых подключены соответственно к выходам триггеров, первые входы которых соединены с выходами соответствующих элементов геров - входами синхронизации устройства, отличающееся тем, что, с целью повышения быстродействия устройства, оно содержит коммутаторы, блоки логического анализа, группу элементов И, элемент ИЛИ и регистр сдвига, причем выходы элементов И группы подключены соответственно ко входам элемента ИЛИ, выход которого соединен с первыми входами коммутаторов, вторые входы которых подключены к выходам соответствующих регистров признаков и первым входам элементов И группы соответственно, вторые входы которых соединены с 2 ЗО 33 выходами соответствующих триггеров, первые и вторые информационные входы блоков логического анализа подключены к выходам соответствующих коммутаторов, а третьи информационные входы соединены с выходом регистра сдвига, третьи входы коммутаторов и выходы блоков логического анализа являются соответственно управляющими входами и выходами устройства.2. Устройство по п. 1, отличающееся тем, что блок логического анализа содержит триггеры, элементы И, НЕ и ИЛИ, причем выходы первого и второго элементов И подключены соответственно к первым входам первого триггера и первого элемента ИЛИ, выход которого соединен со вторым входом первого триггера, выходы элементов И с третьего по восьмой подключены соответственно ко входам второго элемента ИЛИ, выход которого соединен с первым входом второго триггера, второй вход которого подключен ко второму входу первого элемента ИЛИ, инверсный выход второго триггера соединен с первыми входами первого и второго элементов И, прямой выход первого триггера подключен к первым входам третьего, четвертого и пятого элементов И, а инверсный выход - к первым входам шестого, седьмого и восьмого элементов И, выход первого элемента НЕ соединен со вторыми входами первого, третьего и пятого элементов И, а вход - со вторыми входами второго, шестого и седьмого элементов И, второй вход четвертого и третьи входы первого и пятого элементов И подключены ко входу второго элемента НЕ, выход которого соединен с третьими входами второго и шестого элементов И и вторым входом восьмого элемента И, четвертый вход первого элемента И и третьи входы третьего и четвертого элементов И подключены к выходу третьего элемента НЕ, вход которого соединен с четвертым входом второго элемента И и третьими входами седьмого и восьмого элементов И, входы первого, второго и третьего элементов НЕ являются соответствующими информационными входами, второй вход второго триггера - установочным входом, третьи входы триггеров - входом синхронизации, а инверсный выход первого триггера является выходом блока логического анализа. Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР 424141, кл. б 11 С 15/00, 1974.2. Р. Р. Адгаюа 1 Явц 11 еп 1 оцз Соврех 5 еагф 1 п Аззос 1 а 1 ке Мешог 1 ез - ,Соп 1 егепсе оп Согпрц 1 ег Ьуз 1 егпз апд Тесйпо 1 оду, Ыпдоп, 1974 (прототип).902073 9 Уиг доно венного ком ретений и 35, Раушска г. Ужгород,4/5ная, 4 едакторЛ. Пчелинскааказ 12391/61ВНИИП 113035, Моилиал ППП Составитель В.Техред А. БойкаТираж 623 Государс лам Изоб ква, Ж - Патент,П итета С ткрытий я наб., ул. Про рректор А, Дзятк дписноеССР