Блок поиска информации для ассоциативного запоминающего устройства

 

БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА , содержащий два триггера, восемь элементов И, два элемента ИЛИ и три элемента НЕ, причем первые входы первого, второго и третьего .элементов И объединены и являются первым входом блока, первые входы четвертого, пятого и шестого элементов И, первый вход седьмого и вторые входы четвертого и пятого элементов И, первый вход восьмого и вторьте входы первого и третьего элементов И объединены соответст&енно и являются входами блока с второго по четвертый, второй вход восьмого и третий вход третьего элементов И подключены к выходу первого триггера, третий вход первого элемента И подключай к выходу второго триггера, выходы пятого и шестого элементов И подключены соответственно к первом и второму входам первого элемента ИЛИ, выходы .первых элементов И и ИЛИ подключены соответственно к первым входс1М первого и второго триггеров, выход чет вертого элемента И подключен к первому входу второго элемента ИЛИ, второй вход которого является пятым входом блока, а выход подключен к второму входу первого триггера, третий вход первого и второй вход второго триггеров объединены и являются шестым входом блока, отличающ и и с я тем, что, с целью расширения области применения блока за счет увеличения числа критериев поиска , в него введены элемента , элементы И с девятого по шестнадцатый , элементы ИЛИ, элементы НЕ с четвертого по шестой и третий триггер, при;чем первые входы первого и второго элементов И-НЕ и девятого элемента И подключены к первому входу блока, первые входы десятого, одиннадцатого и двенадцатого и второй вход седьмого элементов И подклю-, i чены к второму входу блока, первые входы тринадцатого и четырнадцатого (Л элементов И соединены с третьим входом блока, первые входы третьего и четвертого элементов ИЛИ подключены к пятому входу блока, вторые входы подключены соответственно к выходам 2 двенадцатого и седьмого элементов И, а выходы - к первому.входу третьего и третьему входу второго триггеров , второй вход третьего триггесд ра подключен к шестому входу блока, ч1 третий вход - к выходу одиннадцатого элемента И, а выход - к второму :о входу второго элемента И-НЕ, первые СХ) входы пятого элемента ИЛИ и третьего элемента И-НБ объединены и являются ;о седьмым входом блока, вторые входы подключены к выходу девятого элемента И, . а выходы являются первым и вторым выходами блока, второй вход одиннадцатого и четвертый вход первого элементов И и вход первого элемента НЕ объединены и являются вторым выходом блока, выход первого элемента НЕ подключён к второму входу тринадцатого элемента И, первого элемента И-НЕ соединен с входом второго элемента НЕ и является третьим выходом блока, выход

COOS СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

09) (И) 3(Я) 6 11 С 15 00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ:

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Ф С

Эа

° а

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3497777/18-24 (22) 29 ° 09.82 (46) 30.11.83. Бюл. )) 44 (72) В.Б. Матвеев (7l) Казанский ордена Трудового

Красного Знамени и ордена Дружбы народов авиационный институт им. А.Н. Туполева (53) 681 . 327 .6 (088. 8) (56) 1. Фостер К. Ассоциативные параллельные процессоры. М., Энергоиздат, 1981, с ° 84. рис. 5.15.

2. Авторское свидетельство СССР

9 883972, кл. G 11 С 15/00, 1980 (прототип) . (54)(57) БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ

АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА, содержащий два триггера, восемь элементов И, два элемента ИЛИ и три элемента НЕ, причем первые входы первого, второго и третьего .элементов И объединены и являются первым входом блока, первые входы четвертого, пятого и шестого элементов И, первый вход седьмого и вторые входы четвертого и пятого элементов

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

И-НЕ, элементы И с девятого по шестнадцатый, элементь1 ИЛИ, элементы НЕ с четвертого по шестой и третий триггер, причем первые входы первого и второго элементов И-HE и девятого элемента И подключены к первому входу блока, первые входы десятого, одиннадцатого и двенадцатого и второй вход седьмого элементов И подклюд чены к второму входу блока, первые )й входы тринадцатого и четырнадцатого элементов И соединены с третьим входом блока, первые входы третьего и четвертого элементов ИЛИ подключены к пятому входу блока, вторые входЫ подключены соответственно к выходам двенадцатого и седьмого элементов

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

1057989 второго элемента НЕ подключен к второму входу шестого и третьему входу одиннадцатого элементов И, выход второго элемента И-НЕ объединен с вторым входом второго, третьим входом восьмого и пятым .входом первого элементов И и входом третьего элемента НЕ и является четвертым выходом блока, вьжод третьего элемента НЕ подключен к вторым входам десятого, двенадцатого и четырнадцатого и третьим входам четвертого и седьмого элементов И, выход первого триггера подключен к третьему входу второго и четвертою входу седьмого элементов И, axi ду четвертого эпемента НЕ, выход которого под- ключен к пятому входу блока и первому входу пятнадцатого элемента И, выход которого подключен к первому входу шестого элемента ИЛИ, выход второго триггера подключен к входу пятого элемента НЕ, выход которого является пятым выходом блока, первому

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

Известен ассоциативный блок для 5 осуществления последовательного по разрядам ассоциативного поиска содержащее триггеры, элементы И и элемент НЕ, причем первый вывод блока подключен к первому входу первого элемента И и входу элемента НЕ, вы-, ход которого подключен к первому входу второго элемента И, второй вывод блока подйяючен к вторым входам первого и второго элементов И, а 15 третий вывод блока подключен к пер» вому входу. третьего элемента И, вто- 1 рой вход которого подключен к выходу первого триггера, а выход подключен к входу второго триггера, выход которого подключен к третьим входам первого и втораго элементов И, выходы которых подключены соответственно к первому и второму входам первого триггера fl) .

Однако область применения этого блока ограничена задачами, в которых требуется поиск максимального (минимального) слова.

Наиболее близким техническим решением к предлагаемому является блок 30 содержащий два триггера, восемь элементов.И, два элемента ЙЛИ и три элемента НЕ, в котором первый вывод блока подключен к первым входам первого, второго и третьего элементов И 35 входу шестнадцатого элемЕнта И, вы= ход которого подключен к второму входу шестого элемента ИЛИ, вторым входам девятого элемента И и первого элемента И-НЕ и третьим входам пятого, десятого и четырнадцатого и четвертому входу одиннадцатого элементов И, выходы десятого, тринадцатого и четырнадцатого элементов

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

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

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

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

1подключен к первому входу восьмого и

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

ИЛИ, выходы первых элементов И .и ИЛИ подключены к первым входам nepaoro и второго соответственно триггеров, выход четвертого элемента И нодключен к первому входу второго элемента ИЛИ, у которого второй вход подключен к пятому выводу блока, а выход подключен к второму входу первого триггера, а третий вход первого и второй вход второго триггеров под- . ключены к шестому выводу блока (2) .

Недостатком блока является огра" ниченность области его применения.

Цель изобретения - расширение области применения блока за счет увеличения числа критериев поиска, в частности за счет выполнения поиска в массиве хранимых признаков хД, i l,n, таких признаков х„Е1х3 i o

1057989

25 С=Ге х„-хц - С

/ или ФР=,я xq- <к"- Г, где (- признак опроса.

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

ИЛИ и .три элемента НЕ, причем первы входы первого, второго и третьего to элементов И объединены и являются первым входом блока, первые входы четвертого, пятого и шестого элементов И, первый вход седьмого и вторые входы четвертого и пятого элементов $5

И, первый вход восьмого и вторые

: входы первого и третьего элементов

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

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

ИЛИ подключены соотнетстненно к первым входам первого и второго триггеров, выход четвертого элемента И подключен к первому входу второго элемента ИЛИ, второй вход которого является пятым входом блока; а выход подключен к второму входу перво го триггера, третий нход первого и 35 второй вход второго триггеров объединены и являются шестым входом блока, введены три элемента И-НЕ, элементы И с девятого по шестнадцатый, элементы ИЛИ, элементы НЕ с четвер- 4Q того по шестой и третий триггер, причем первые входы первого и второго элементов И-НЕ и девятого элемента И подключены к первому входу блока, первые входы десятого, один- 45 надцатого и двенадцатого и второй вход седьмого элементов И подключены к второму входу блока, первые входы тринадцатого и четырнадцатого элементов И соединены с третьим входом блока/. первые входы третьего и четвертого элементов ИЛИ подключены к пятому входу блока, вторые входы подключены соответственно к выходам двенадцатого и седьмого элементов И, а выходы - к первому входу третьего и третьему входу второго триггеров, второй вход третьего триггера подключен к шестому входу блока, третий вход - к выходу одиннадцатого элемента И, а выход - к второму входу N второго элемента И-HE первые входы пятого. элемента ИЛИ и третьего элемента И-НЕ объединены и являются седьмыми нходом блока, вторые входы подключены к выходу девятого элемен- 65 та И, а выходы являются первым и вторым выходами блока, второй вход одиннадцатого и четвертый. вход пер-. вого элементов И и вход первого зле мента НЕ объединены и являются вторым выходом блока„ выход первого элемента НЕ подключен к второму входу тринадцатого элемента И, выход первого элемента И-НЕ соединен с входом второго элемента НЕ и является третьим выходом блока, выход второго элемента НЕ подключен к второму входу шестого и третьему входу одиннадцатого элементов И, выход второго элемента И-НЕ объединен с вторым входом второго, третьим входом восьмого и пятым входом первого элементов И и входом третьего элемента НЕ и янляется четвертым выходом блока, выход третьего элемента

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

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

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

На фиг.1 показана структурная схема блока поиска информации для ассоциативного запоминающего устройства; на фиг.2 — структурная схема ассоциативного запоминающего устройства, в состав которого входят предлагаемые блоки поиска информации; на фиг.3 — граф переходов блока поиска информации.

1057989

Блок поиска информации содержит (фиг.1) элементы И 1-16 с nepaoro no шестнадцатый, элементы ИЛИ 17-23 с

1первого по седьмой, элементы НЕ 24-29 с первого по шестой, первый 30, вто-,5 рой,31 и третий 32 элементы И-НЕ и первый 33, второй 34 и третий 35 триггеры. Блок имеет входы 36-42 с первого по седьмоЯ, выходы 43-49 е первого по седьмой.

Ассоциативное .запоминающее устройство (фиг.2) может содержать )) блоков 50 »50л поиска информации, П регистров 51-51 1 хранимых призна-, ков с первыми 52 и вторыми 53 выходами и регистр 54 признака опроса с 15 первым 55 и вторым 56 выходами. Выходы 44-47, 49 блоков 50 -50я объединены соответственно и через резисторы 57 подключены к шине 58 опорного напряжения. Кроме того, вы.- Я ходы 49, 47 и 48 блока являются соответственно выходами 59, 60 и 61 —

61П устройства, входами которого являются входы 62-64.

Граф переходов блока поиска ин- 25 формации (фиг.3) имеет четыре вершины 65-68. Рядом с вершинами графа приведены коды состояний блока, в которых двоичные цифры соответствуют (слева направо) состояниям вто- ЗО рого 34,, первого 33 и третьего 35 триггеров. И вЂ” безразличное состояние второго 34 триггера.

Блок работает следующим образом.

В исходном состоянии сигналом по входу 63 все блоки устанавливаются в состояние 65.

Ассоциативный поиск производится не более чем за пч тактов поразрядного сравнения (т - число разрядов признаков). В каждом j -ом такте 40 (j 1,2,...„j

Признаки в регйстрах располагаются таким образом, что веса их разрядов убывают с ростом ) 50

В каждом j -ом такте на установочных входах триггеров вйрабатываются сигналы: 5 и Й11 - на входах второго 34, 11," ий, - на

axopax nepsoro 33 a H (55 на входах третьего 35 триггеров, которые определяются следующим обраaoMi 5,„ -TvQ< у„(.

1 б "=ц Е" ° в

2ч «, .» - j (j j-i j e

5 =0 Т.л. а,, Ч si,1-а -(1 Aj-< -1-

R "Q ( (i,«-Ф 1 1 V 2„j С;,ЧУ, б;.,. Ч чт,;8; <»q

R 2jij "2<)YACC) 1 3( гдето,,,,01,,< q иЦ1,, (— текущие состояния второго 34, первого

33 и треТьего 35 триггеров, Т вЂ” сигнал начальной установки, A q-q Вj f и Сj g - текущие состояния на объединенных .выходах 44, 45 и 46 блока:

A =Ч а" go

3-1 „о —,„«Д- 1Ю, )- "О f3

B =V О., р., С = и °, ч,. — "1, -1 Ц t ) < . — 1,1-3""s1 (1,р"

При поступлении. сигнала на вход

64 в триггерах фиксируются новые -ые состояния блока и начинается

) +1-ый такт поиска..

Результат поиска определяется сигналами на выходах 59 - 61 устройства. Появление единичного значения

Функции Щ . ц„„=м; чio чЯ, где э=,М е,; и

М,п о ц= )g< 4(;S+< 3 21, м р " чМ на выходе 61„ означает, что признак х удовлетворяет условию поиска.

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

59 устройства или логической. единицы на выходе 60 устройства. В первом случае независимо ат значений оставшихся, младших разрядов признаков, условию поиска удовлетворяет. тот хранимый признак х„, у которого на соответствующем выходе 61; в данный момент зафиксирована логическая единица (Я; = 1),. Во втором случае появление едйничного значения функции

E =.V (,"0р;, (=(р означает, что независимо от оставшихся разрядов условию поиска не удовлетворяет ни один хранимый признак.

Если хранимые признаки записаны

s прямом коде, т.е.Е;- = х;, где х -.значение ) -го разряда признака х; то в результате поиска выбираются такие признаки х, что

МО = и: х„-х4 (.

Если хранимые признаки записаны в инверсном коде, т.е.2;1 х, то в результате поиска выберутся такие признаки х;, что

VE = ð. хе- x 1057989

ФО ф3И

Фмв. Ф

Поиск максимума и минимума является частным случаем реализуемого с помощью данных блоков ассоциативного поиска для Y" О.

Аппаратурная реализация описанных .видов ассоциативного поиска позволяет расширить область применения предлагаемого блока на такие задачи, как, например, обнаружение выбро-. сов . в статическом материале, АСУ технологическим процессом и т.д, Рассмотренные виды поиска могут быть выполнены программным путем со значительно меньшим (ориентировочно иа два-три пбрядка, в зависимости от размеров массива признаков) быстродействием по сравнению с предлагаемым решением.

ВНИИПИ Заназ 9586/53

Тираж 594 Подписное

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