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

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

Иллюстрации

Показать все

Реферат

 

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 13.06.80 (21) 2940829/18-24 с присоединением заявки ¹вЂ” (23) Приоритет— (51) М. Кл.

G 11 С 15/00

Гееударствеииый кемитет (53) УДК 681.327 (088.8) СССР

Опубликовано 30.01.82. Бюллетень № 4

Дата опубликования описания 05.02.82

M делам изобретений и еткрмтий

У < Е (:„-.

В. М. Трусфус, P. P. Бикмухаметов, В. Б. Матв (72) Авторы изобретения (71) Заявитель Казанский ордена Трудового Красного Знамени им. А. Н. Туполева (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

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

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

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

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

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

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

Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, 902073 ми входами, а третьи входы триггеров — вхо- 2э дами синхронизации устройства, введены коммутаторы, блоки логического анализа, 20 которых подключены к выходам соответствующих регистров признаков и первым входам элементов И группы соответственно, вторые входы которых соединены с выхода- гь ми соответствующих триггеров, первые и вторые информационные входы блоков логичесЗо

3$

40 содержащее регистры признаков, элементы

НЕРАВНОЗНАЧНОСТЬ, триггеры, элементы

ИЛИ НЕ, элементы И-НЕ и элемент И,причем выходы регистров признаков подключены соответственно к первым входам элементов

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

При этом блок логического анализа содержит триггеры, элементы И, НЕ и ИЛИ; причем выходы первого и второго элементов

И подключены соответственно к первым входам первого триггера и первого элемента

ИЛИ, выход которого соединен со вторым входом первого триггера, выходы элементов

И с третьего по восьмой подключены соответственно ко входам второго элемента ИЛИ, выход которого соединен с первым входом второго триггера, второй вход которого подключен ко в орому входу первого элемента

ИЛИ, инверсный выход второго триггера соединен с первыми входами первого и второго элементов И, прямой выход первого триггера подключен к первым входам третьего, четвертого и пятого элементов И, а инверсный выход — к первым входам шестого, седьмого и восьмого элементов И, выход первого элемента НЕ соединен со вторыми входами первого, третьего и пятого элементов И, а вход — со вторыми входами второго, шестого и седьмого элементов И, второй вход четвертого и третьи входы первого и пятого элементов И подключены ко входу второго элемента НЕ, выход которого сое45

$0

И динен с третьими входами второго и шестого элементов И и вторым входом восьмого элемента И, четвертый вход первого элемента И и третьи входы третьего и четвертого элементов И подключены к выходу третьего элемента НЕ, вход которого соединен с четвертым входом второго элемента И и третьими входами седьмого и восьмого элементов И, входы первого, второго и третьего элементов НЕ являются соответствующими информационными входами, второй вход второго триггера — установочным входом, третьи входы триггеров — входом синхронизации, а инверсный выход первого триггера является выходом блока логического гнализа, На фиг. 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) отражает состояние а2 — а блока 11 и сигналы С вЂ” С перехода из одного состояния в другое.

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

Каждый блок 11 формирует значение логического условия вхождения признака в заданную окрестность экстремального признака

Li — Lz + K +0 ( где 1.< = х;; — в случае поиска признаков, входящих в окрестность макгпах симального признака; 1. =

= xm, L1 = х; для поиска признаков, входящих в окрестность минимального признака; х; — значение i-го признака;

x „xx значение максимального (минимального) признака;

К вЂ” заданная длина окрестности экстремального признака.

Пусть Ь, Lz, К вЂ” m-разрядные двоичные числа:

L = 1»1i 2lts".1>j ...1, L1 = 12i122123. ° -12j ° "12m, 902073

К = KiK2-..K)...K, где 1 1,! г, К) — двоичные разряды, j — номер разряда.

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

1-1 — Lz+ К =А;

11 1г) + К) = а) то (А)) — — (1«)) — (1-z) j + (K)j или в итерационной форме (А) = 2(А)) + а), j = 1,2,3,...,m; (А) = а1

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

Если (А)1е, { — 2, — 3}, то делается окончательный вывод о невыполнении условия А >

>О и анализ последующих разрядов чисел х,,х, или х„, и К блокируется; если (А).

«1,2), то устанавливается, что А >О; йри (А). е 10,11 анализ последующих разрядов продолжается. Так как (А) = А, то при

А О, «-1, «-2, +3 выполняется m итераций, т. е.,анализу подвергаются все разряды чисел, содержащихся в регистрах 1 (фиг. 1).

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

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

Первое встретившееся неравенство фиксируется нулевым сигналом на выходе соответ- 4 ствующего элемента НЕРАВНОЗНАЧНОСТЬ 2, который через элемент ИЛИ-НЕ

3 устанавливает триггер 4 в нулевое состояние, причем анализ последующих разрядов соответствующего признака блокируется. Когда некоторый разряд всех признаков 45 содержит нуль, то все триггеры 4 находятся в нулевом состоянии и поиск единицы в признаках пропускается, так как в этом случае на выходе элемента И б устанавливается единичный сигнал, поступающий на входы всех элементов ИЛИ-НЕ 3. 50

Наличие единичного сигнала на выходе

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

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

На входы 21 блоков 11 подаются последовательно с выхода регистра 10 сдвига значения разрядов К„ длины окрестности максимального признака. . В каждом блоке 11 для каждого j-ro разряда определяется число (A)>, фиксируемое в виде определенного состояния а1— а4 (фиг. 3). Значение (A)> — — О фиксируется в виде начального состояния а1, (A)j

= — 1 в виде состояния аз. При (А). 1,2j блок 11 (фиг. 2) переходит в конечйое состояние а (фиг. 3), при (A)j 2, — 3) — в конечное состояние а+ (фиг. 3).

Каждое состояние блока 11 кодируется определенным набором состояний триггеров

22 и 23 (фиг. 2); состояние а (фиг. 3) кодируется набором (О, О), az — набором (О, 1 аз — набором (1, О) и а+ — набором (1, 1).

Если блок 11 (фиг. 2) находится в состоянии а (фиг. 3), то при поступлении на входы 19, 20 и 21 (фиг, 2) любого набора сигналов из множества С1 = ((О, О, О); (О, 1,,1); (1, 1, 0) (фиг. 3) состояние а не меняется, при поступлении сигналов С4. = 1(0, 1,,О)} переходит в промежуточное состояние аз, которое сохраняется при поступлении любого набора сигналов из множества C4 =

=1(0,0,1); (1, 0,0); (1, 1,1)j . Из состояния аз блок 11 (фиг. 2) переходит в начальное состояние а (фиг. 3) под действием сигналов С = {(1, О, 1)) . Любой набор сигналов из множества Сб = С и С переводит блок

11 (фиг. 2) из состояния аз (фиг. 3) в конечное состояние а „в котором он не реагирует на сигналы на входах 19, 20 и 21 (фиг. 2)

Под действием любого набора сигналов из множества С5 = CzLCs (фиг. 3) блок 11 (фиг. 2) переходит в конечное состояние а> (фиг. 3).

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

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

33

3О

43

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

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

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

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

ИЛИ-НЕ подключены к выходу элемента И, входы которого соединены соответственно с выходами элементов И-НЕ, вторые входы которых подключены соответственно к выходам триггеров, первые входы которых соединены с выходами соответствующих элементов

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

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

И, прямой выход первого триггера подключен к первым входам третьего, четвертого и пятого элементов И, а инверсный выход— к первым входам шестого, седьмого и восьмого элементов И, выход первого элемента

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

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

1. Авторское свидетельство СССР №424141, кл. G 11 С 15/00, 1974.

2. D. P. Agrawal Simultenious Complex

Search in Associative Memories —,Conference

on Computer Systems and Technology. Ьзпdon, 1974 (прототип).

902073

Составитель В. Гордонова

РедакторЛ. Пчелинская Техред А. Бойкас Корректор А. Дзятко

Заказ 12391/61 Тираж 623 Подписное

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

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

Филиал ППП «Патент>, г. Ужгород, ул. Проектная, 4