Ассоциативное запоминающее устройство Советский патент 1982 года по МПК G11C15/00 

(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

1

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в ассоциативное запоминающее устройство. содержащее регистры признаков, элементы НЕРАВНОЗНАЧНОСТЬ , триггеры, элементы ИЛИ НЕ, элементы И-НЕ и элемент И,причем выходы регистров признаков подключены соответственно к первым входам элементов НЕРАВНОЗНАЧНОСТЬ, выходы которых соединены с первыми входами соответствующих элементов ИЛИ-НЕ и элементов И-НЕ, вторые входы элементов ИЛИ-НЕ подключены к выходу элемента И, входы которого соединены соответственно с выходами элементов И-НЕ, вторые входы которых подключены соответственно к выходам триггеров, первые входы которых соединены с выходами соотйетствующих элементов ИЛИ-НЕ, вторые входы элементов НЕРАВНОЗНАЧНОСТЬ и триггеров являются установочными входами, а третьи входы триггеров - входами синхронизации устройства, введены коммутаторы, блоки логического анализа, группу элементов И, элемент ИЛИ и регистр сдвига, причем -выходы элементов И группы подключены соответственно ко входам элемента ИЛИ, выход которого соединён -с первыми входами коммутаторов, вторые входы которых подключены к выходам соответствующих регистров признаков и первым входам элементов И группы соответственно, вторые входы которых соединены с выходами соответствующих триггеров, первые и вторые информационные входы блоков логического анализа подключены к выходам соответствующих коммутаторов, а третьи информационные входы соединены с выходом регистра сдвига, третьи входы коммутаторов и выходы блоков логического анализа являются соответственно управляющими входами и выходами устройства. При этом блок логического анализа содержит триггеры, элементы И, НЕ и ИЛИ, причем выходы первого и второго элементов И подключены соответственно к первым входам первого триггера и первого элемента ИЛИ, выход которого соединен со вторым входом первого триггера, выходы элементов И с третьего по восьмой подключены соответственно ко входам второго элемента ИЛИ, выход которого соединен с первым входом второго триггера, второй вход которого подключен ко второму входу первого элемента ИЛИ, инверсный выход второго триггера соединен с первыми входами первого и второго элементов И, прямой выход первого триггера подключен к первым входам третьего, четвертого и пятого элементов И, а инверсный выход - к первым входам щестого, седьмого и восьмого элементов И, выход первого элемента НЕ соединен со вторыми входами первого, третьего и пятого элементов И, а вход - со вторыми входами второго, щестого и седьмого элементов И, второй вход четвертого и третьи входы первого и пятого элементов И подключены ко входу второго элемента НЕ, выход которого соединён с третьими входами второго и щестого элементов И и вторым входом восьмого элемента И, четвертый вход первого элемента И и третьи входы третьего и четвертого элементов И подключены к выходу третьего элемента НЕ, вход которого соединен с четвертым входом второго элемента И и третьими входами седьмого и восьмого элементов И, входы первого, второго и третьего элементов НЕ являются соответствующими информационными входами, второй вход второго триггера - установочным входом, третьи входы триггеров - входом синхронизации, а инверсный выход первого триггера является выходом блока логического анализа. На фиг. 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) отражает состояние j блока 11 и сигналы Ci-С 6 перехода из одного состояния в другое. Устройство работает следующим образом. Каждый блок 11 формирует значение логического условия вхождения признака в заданную окрестность экстремального признакаL, - LZ + К 0 , гдеЬ х-, - В случае поиска признаков, входящих в окрестность мак2, х,симального признака; Lj LZ X ; для поиска признаков, входящих в окрестность минимального признака; х-| -значение i-ro признака; значение максимального (минимального) признака; К - заданная длина окрестности экстремального признака. Пусть L), Ly, К - т-разрядные двоичные числа: L, Inl.zli il|ii2il3...ig...iim| L2 lzil22lzJ---l2j...l2m,

К KiKz-.-Kj-.-Km. где 1 у , 1 fj, Kj - двоичные разряды

j - номер разряда.

Обозначим через число, получающееся из А путем отбрасывания всех младших разрядов, начиная с (j + 1)-го разряда. Тог да, если

L, - u -f К А:

1 ij - 1JJ + К) Hj, то

L,j - U, + или в итерационной форме

,+ aj; j 1,2,3,...,m; A, at Анализ условия выполняется в виде определенного числа итераций. На каждом J-OM шаге определяется коррекцией , в зависимости от значения aj, при этом (ajS О, ± 1, ±2). При этом определяется лишь семь возможных значений А: О, ±1, ±2, ±3.

Если (-2, -3, то делается окончательный вывод о невыполнении условия А 0 и анализ последующих разрядов чисел х,,Хтахили И К блокируется; если Ajj {1,2, то устанавливается, что А 0; при е о, 11 анализ последующих разрядов продолжается. Так как А А, то при А О, ±1, ±2, +3 выполняется m итераций, т. е. ,аиализу подвергаются все разряды чисел, содержащихся в регистрах 1 (фиг. 1).

Рассмотрим работу устройства на примере поиска множества признаков, входящих в окрестность максимального признака,

Перед началом работы все триггеры 4 (фиг. 1) устанавливают в единичное состояние по входам 14, на вход 13 подаются нулевые сигналы, что соответствует установке всех разрядов сравниваемого признака в единичное состояние. Сравнение разрядов признаков, хранящихся в регистрах 1, ведут последовательно, начиная со старших, с помощью элементов НЕРАВНОЗНАЧНОСТЬ 2 Первое встретившееся неравенство фиксируется нулевым сигналом на выходе соответствующего элемента НЕРАВНОЗНАЧНОСТЬ 2, который через элемент ИЛИ-НЕ 3 устанавливает триггер 4 в нулевое состояние, причем анализ последующих разрядов соответствующего признака блокируется. Когда некоторый разряд всех признаков содержит нуль, то все триггеры 4 находятся в нулевом состоянии и поиск единицы в признаках пропускается, так как в этом случае на выходе элемента И 6 устанавливается единичный сигнал, поступающий на входы всех элементов ИЛИ-НЕ 3.

Наличие единичного сигнала на выходе i-ro триггера 4 после анализа j-ro разряда указывает на то, что i-ый признак соответствует максимальному с точностью до j-ro разряда, а после анализа всех разрядов - на максимальный признак.

Последовательно определяемые разряды максимального признака х поступают

через элементы И 7 и элемент ИЛИ 8 на первые входы коммутаторов 9, на вторые входы которых подаются значения разрядов соответствующих признаков с выходов регистров 1. В случае определения признаков, входящих в окрестность максимального признака, сигнал на управляющих входах 16 равен единице и коммутаторы 9 обеспечивают выдачу на входах 19 блоков 11 значений разрядов X;; ,-а на входах 20 - значений x uxjНа входы 21 блоков 11 подаются последовательно с выхода регистра 10 сдвига значения разрядов Kj длины окрестности максимального признака.

. В каждом блоке 11 для каждого j -го разряда определяется число , фиксируемое в виде определенного состояния ai - а4 (фиг. 3). Значение 0 фиксируется в виде начального состояния ai, -IB виде состояния аз. При ,2 блок 11 (фиг. 2) переходит в конечное состояние аг (фиг. 3), при ,-3 - в конечное состояние а (фиг. 3).

Каждое состояние блока 11 кодируется определенным набором состояний триггеров 22 и 23 (фиг. 2); состояние а (фиг. 3) кодируется набором (О, 0), а2 - набором (О, 1 aj - набором (1,0) и а4 - набором (1, 1).

Если блок 11 (фиг. 2) находится в состоянии ai (фиг. 3), то при поступлении на входы 19, 20 и 21 (фиг. 2) любого набора сигналов из множества Ci |(0, О, 0); (О, 1, ,1); (1, 1,0) (фиг. 3) состояние at не меняется, при поступлении сигналов С+ (О, 1, ,0)} переходит в промежуточное состояние аз, которое сохраняется при поступлении любого набора сигналов из множества Сд (0,0, 1); (1,0,0); (1, 1, 1)} . Из состояния аз блок 11 (фиг. 2) переходит в начальное состояние ai (фиг. 3) под действием сигиалов Cj (1,0, 1). Любой набор сигналов из множества Се Ci и С+ переводит блок 11 (фиг. 2) из состояния аз (фиг. 3) в конечное состояние а .„ в котором он не реагирует на сигналы на входах 19, 20 и 21 (фиг. 2) Под действием любого набора сигналов из множества Cs CjLCj (фиг. 3) блок И (фиг. 2) переходит в конечное состояние а (фиг. 3).

Таким образом, после анализа всех разрядов признаков триггеры 22 и 23 (фиг. 2) находятся соответственно в нулевом и единичном состояних, если единичном и нулевом состояниях, если А -1, в нулевых состояниях, если А О и единичных, если А -1. Отсюда следует, что нулевое состояние триггера 22 является признаком выполнения условия . Это свидетельствует о том, что соответствующий признак х; входит в окрестность максимального признака х„, заданную длиной К. Выявление всех признаков, входящих в заданную окрестность, осуществляется параллельно за один цикл поиска, состоящий из последователь7

ного анализа всех разрядов чисел, хранящихся в регистрах 1.

При поиске признаков, входящих в окрестность минимального признака, устройство работает аналогично, но при этом на вход 13 (фиг. 1) подаются единичные сигналы, что соответствует установке всех разрядов сравниваемого признака в нулевое состояние. На входы 16 при этом подаются нулевые сигналы и коммутаторы 9 обеспечивают выдачу на входах 19 блоков 11 значений разрядов , а на входах 20 - значеНИИ Xjj . После анализа всех разрядов признаков нулевые сигналы на выходах 12 (фиг. 1 и 2) указывают на то, что соответствующие признаки входят в окрестность минимальното признака.

Технико-экономические преимущества предлагаемого устройства заключаются в реализации выполняемого за один цикл поиска множества признаков, входящих в фиксированную по длине окрестность экстремального признака, и в повыщении быстродейстВИЯ по сравнению с известным устройством.

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

. Ассоциативное запоминающее устройство, содержащее регистры признаков, элементы НЕРАВНОЗНАЧНОСТЬ, триггеры, элементы ИЛИ-НЕ, элементы И-НЕ и элемент И, причем выходы регистров признаков подключены соответственно к первым входам элементов НЕРАВНОЗНАЧНОСТЬ, выходы которых соединены с первыми входами соответствующих элементов ИЛИ-НЕ и элементов И-НЕ, вторые входы элементов ИЛИ-НЕ подключены к выходу элемента И, входы которого соединены соответственно с выходами элементов И-НЕ, вторые входы которых подключены соответственно к выходам триггеров, первые входы которых соединены с выходами соответствующих элементов ИЛИ-НЕ, вторые входы элементов НЕРАВНОЗНАЧНОСТЬ и триггеров являются установочными входами, а третьи входы триггеров - входами синхронизации устройства, отличающееся тем, что, с целью повыщения быстродействия устройства, оно содержит коммутаторы, блоки логического анализа, группу элементов И, элемент ИЛИ и регистр сдвига, причем выходы элементов И группы подключены соответственно ко входам элемента ИЛИ, выход которого соединен с первыми входами коммутаторов, вторые входы которых подключены к выходам соответствующих регистров признаков и первым входам элементов И группы соответственно, вторые входы которых соединены с

8

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

Источники информации, принятые во внимание при экспертизе

13

(риг.1