Блок поиска информации для ассоциативного запоминающего устройства Советский патент 1987 года по МПК G11C15/00 

13

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

Цель изобретения - расширение об- ласти приме нения блока за счет выполнения граничного поиска среди чисел, представленных в кодах Фибоначчи.

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

Блок поиска информации (фиг. 1) содержит триггеры 1-4 с первого по четвертьй, элементы И 5-15 с первого по одиннадцатый, элементы ИЛИ 16-21 с первого по шестой, первый 22 и второй 23 элементы НЕ, входы 24-29 блока поиска информации с первого по шестой и выходы 30-34 блока с первого по пятый.

В ассоциативном запоминающем устройстве (фиг. 2) на указанных блоках 35 поиска информации входы 24 и 26 блоков подключены к выходам соот- ветствующих регистров 36 хранимых признаков, входы 27 и 25 блоков 35 подключены к выходам регистра 37 признака опроса, входы 28 и 29 блоков 35 подключены соответственно к входу 38 синхронизации и установочному входу 39, а выходы 30-34 блоков 35 являются выходами 40-44 ассоциативного запоминающего устройства.

Граф (фиг. 3) отражает состояние 45-51 с первого по седьмое и возмож- ,ные переходы в блоке 35 поиска информации. В вершинах графа в виде дроби приведены значения функции w . w. (числитель дроби), определяющих со- стояние блока 35 и двоичные коды, соответствующие состояниям триггеров I- 4 (знаменатель, слева направо) при данных состояниях блока 35 поиска ин- формации.

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

В исходном состоянии сигналом начальной установки по входу 39 триггеры 1-4 устанавливаются в состояни;я, соответствующие вершине 45 графа.

5

1

5

0

5

0 5

152

Весь поиск занимает m .тактов (где m - разрядность признаков), в каждом из которых с регистров 36 и 37. считываются очередные разряды (начиная со старших), анализируются с учетом предьщущих состояний в блоках 35 и по синхросигналу с входа. 38 в блоках 35 фиксируются новые состояния.

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

СП ff Г)-П Cj-27 ,

Ы; f(Wj , W . , Х.-,у. ),

где с. ГгП П-2 уГ}-2Т.

xj. - Г. х,у F(j-J );

У li y,-.F(J-J );

J rl J

/ Г;-21(x i , - определяется аналогично );

Xij, yj , x,.j.|, y., e fO,;

f 0 при л 0-; F(j) Л 1 при j 0;

lF(l)+F(j-2) при 5 У 0.

J 1,m;

i 1,n (n - число хранимых признаков) .

Величины X ( и представляют собой запись J-1 старших разрядов кодов Фибоначчи признаков х,- и у

X,- 11 x-,j F(m-j);

У Т. y.F(m-j),

т.е. двоичных кодов с разрядными весами 1 , 1 ,2,3,5,8, 13,21 ,34,55. .. . Тогда

и..соГ/- .„СИи,..

Все возможные переходь в блоке 35 поиска информации в зависимости от значений ш, и ш ;) (с учетом исходного состояния U) 004 0), значений х.. , у. и g (сигнала начальной установки) дает следующая таблица переходов.

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

Первая вершина графа 45 соответствует w -. О, верши313

на 46 соответствует ы . -, О

третья вершина 47 соответствует

г ,)

1,- LJj 0; четвертая вершина 48 соответствует 0) . - О, w пятая вершина 49 соответствует w . О, iov . 1; шестая вершина 50 соответствует ( U) ; + U) i -2)V V(2w. + u) у -3) и седьмая вершина 51 соответствует (ш . + w ; 72)У

У( 3).

Если на входы 24 и 27 блоков подаются прямые значения разрядов кодов признаков, а на входы 25 и 26 - инверсные значения , сигналами единицы на выходах 40-44 отмечаются, соответ- ственно, хранимые признаки, которые, меньше, больше или равны, больше, меньше или равны, равны по отношению

к признаку опроса,

Формула изобретен И.Я

Блок поиска информации для ассоциативного запоминающего устройства, содержащий триггеры с первого по третий, элементы И с первого по четвертый и первый элемент ИЛИ, причем выход первого элемента И подключен к первому входу второго элемента И, второй вход которого соеди- нен с прямым выходом второго триггера, выход третьего элемента И подключен к первому входу четвертого элемента И, выход первого элемента ИЛИ подключен к входу асинхронной установ ки в 1 второго триггера, первый и второй входы первого элемента И являются соответственно первыми информационным и признаковым входами блока, первый и второй входы третьего эле- мента,И являются соответственно .вторыми информационным и признаковым входами блока, прямые и инверсные выходы первого и третьего триггеров являются соответственно выходами Меньше, Больше или равно, Меньше или равно , Равно блокад отличающийся тем, что, с целью расширения области применения блока за счет вьшолнения граничного поиска чисел, представленных в кйдах Фибоначчи, в него введены четвертый триггер, с пятого по одиннадцатый элементы И, с второго по шестой эле15

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

tt6

its

ff9

Изобретение относится к вычислительной технике и позволяет осуществлять граничный ассоциативный поиск в массивах данных. Цель изобретения - расширение области применения блока поиска информации для ассоциативного запоминающего устройства за счет выполнения граничного поиска среди чисел, представленных в кодах Фибоначчи. Блок представляет собой конечный автомат, имеющий семь внутренних состояний, содержит четыре триггера 1-4, одиннадцать элементов И 5-15 шесть элементов ИЛИ 16-21 и два элемента НЕ 22 и 23. Входы 24 и 26 блока подключаются к выходам соответствующего регистра хранимого признака ассоциативного запоминающего устройства (АЗУ) Входы 27 и 25 блока подключаются к выходам регистра признака опроса АЗУ. Коды признаков поступают в блок побит- но, начиная со старших разрядов. По входам 28 и 29 подаются сигналы синхронизации и начальной установки. Уровнями логической единицы на ,рдах 30- 34 Отмечаются хранимые признаки, которые меньше, больше или равны, больше, меньше или равны, равны по отношению к признаку опроса. 3 ил., 1 табл. i с со О) СП Фиг.1 гв

Составитель В. Рудаков Редактор А. Козориз Техред И.Попович Корректор А. Обручар

Заказ 4051/50 Тираж 589Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4