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

 

Изобретение относится к вычислительной технике и позволяет осуществлять быстрый ассоциативный поиск экс -ремапьных величин или сортировку в массивах данных. Цель изобретения - расширение области применения -блока за счет выполнения поиска среди чисел , представленных в кодах Фибоначчи . Блок поиска представляет собой конечный автомат, имеющий четыре внутренних состояния, содержит триггеры 1 и 2, шесть элементов И 3-8 и три элемента ИЛИ 9-11 и имеет входы 12- 15 и выходы 16 и 17. Вход 12 блока подключается к выходу соответствующего регистра признака, с которого код поступает побитно, начиная со старшего разряда. Вход 13 подключается к выходу внешнего элемента ИЛИ,, к входам которого подключаются выходы Л 7 всех блоков поиска информации, используемых в ассоциативном запоминающем устройстве. По входам 14 и 15 подаются сигналы синхронизации и начальной установки. Уровень логической единицы на выходе 16 блока сигнализирует об экстремальности соответствующего признака. 3 ил., 1 табл. (Л со 00 О) О) иг. f

СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИН

IkkI k ..

7 1 (7 .7<7 77 k

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

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

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

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4061251/24-24 (22) 28.04.86 (46) 07.09.87. Бюл. 9 33 (71) Казанский авиационный институт им. А. Н. Туполева (72) В..Б. Матвеев и А. Н. Никонов (53) 681.327(088.8) (56) Авторское свидетельство СССР

11 1049974; — кл. С 11 С 15/00, 1982.

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

Р 1153359, кл. G 11 С 15/00, 1983. (54) БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА (57) Изобретение относится к вычислительной технике и позволяет осуществлять быстрый ассоциативный поиск экстремальных величин или сортировку в массивах данных. Цель изобретения— расширение области применения -блока за счет выполнения поиска среди чи„„Я0„„1336116 А1 дц 4 С ll С 15/00 сел, представленных в кодах Фибоначчи. Блок поиска представляет собой конечный автомат, имеющий четыре внутренних состояния, содержит триггеры

1 и 2, шесть элементов И 3-8 и три элемента ИЛИ 9-11 и имеет входы 1215 и выходы 16 и 17. Вход 12 блока подключается к выходу. соответствующего регистра признака, с которого код поступает побитно, начиная со старшего разряда. Вход 13 подключается к выходу внешнего элемента ИЛИ,. к входам которого подключаются выходы:17 всех блоков поиска информации, используемых в ассоциативном запоминающем устройстве. По входам 14 и 15 подаются сигналы синхронизации и начальной установки, Уровень логической единицы на выходе 16 блока сигнализирует об экстремальности соответствующего признака. 3 ил., 1 табл.

1336116 где (-f) (j-13

МУ1.Е = Х. (j-1)

"e (ã). е . э

f j-2) ";е (j 2)

l-1 ,> х I- 2 (Р 1) .е

У ()-2) х .

) . Р()-j > (1- 2) х 1 определяюте

f j-z)

t ся аналогично); х„:., с О, и

О при j,(0, F()) и

1 при,j =О, Граф (фиг, 3) отражает состояние 40

24-27 с первого по четвертое и возможные переходы в блоке 18 поиска информации. В верхних шинах графа в виде дроби приведены значения функ ций ы () ) и 1 (. 2) (числитель дроби) 45 определяющих состояние блока, и двоичные коды, соответствующие состояниям первого 1 и второго 2 триггеров (знаменатель, слева направо) при дан- . ных состояниях блока поиска информации. где х, =ша хх

Pj

k 1, n, k (2-1) Ке и значения g (сигнала тановки) дает таблица

2C i (j-2)

- О, начальной ус переходов.

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

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

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

Блок поиска информации (фиг. 1) содержит первый 1 и второй 2-триггеры, элементы И 3-8 с первого по шестой и элементы ИЛИ 9-11 с первого по третий, входы 12-15 и выходы 16 и 17, 25

В ассоциативном запоминающем устройстве (фиг. 2) на блоках 18 поиска информации входы 12 блоков подключены к выходам соответствующих регистров

19 признаков, входы 13 подключены к 30 выходу элемента ИЛИ 20, входы 14 и 15 подключены соответственно к входу 21, синхронизации и установочному входу

22; выходы 16 блоков являются выходами 23 ассоциативного запоминающего 35 устройства, а выходы 17 подключены к соответствующим входам элемента

ИЛИ 20.

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

В исходном состоянии сигналом начальной установки по входу 22 триггеры 1 и 2 устанавливаются в состояние, соответствующее вершине 24 графа °

Весь поиск занимает ш тактов (где

m — разрядность признаков), в каждом иэ которых с регистров 19 считываются очередные разряды (начиная со старших), анализируются с учетом предыдущих состояний в блоках 18 и по синхросигналу с входа 21,в блоках 18 фиксируются новые состояния.

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

18, основана на итеративном вычислении функций ш, = f(cu, ы., х, х .) (2) (2- ) (1-2) и и и

F(j-1)+F(j-2) при ) ) О, 1, и;

1 = 1, п.(n — число признаков) .

Величина х(.2 ") . представляет со1 бой запись j-1 старших разрядов кода

Фибоначчи признака х.

1 х. = х.. F(m j).

1=

Тогда

C j3 (2-1) (Гг) м. =м е +м е +х хе;е

I 11

Все возможные переходы в блоке поиска информации в зависимости от значений (Г1) и >(j 23 (с учетом ис1Е ;е ходного состояния 1,1(1 ) = ы (2)

= О), значений х,,, х яj 1 У

1336116

О х1.

1) C) -13 С) 23

1") 1Е " )Е

C j3 ()-13

"в ";е о о

О -1 О О О О (-) О

О О

0 (-) о . о

О О

О

-1 — 1

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

Первая вершина графа 24 соответствует ы(),."3 = и(113 = О, вторая вершина 25 соответствует 1,) .) 3 = -1, ю,. = О, третья вершина 26 ш Д =

= О, со .) = -1, а четвертая вершина

27 соответствует (1 -13 С)-23 С)-13 (ы Д + со; <-2)7(2 ы;р +

„С)-23 с 3)

Ь 16.

Если на входы 12 блоков 18 подаются прямые значения разрядов кодов признаков, сигналами единицы на выходах 23 отмечаются максимальные при-. знаки, а если инверсные значения разрядов — минимальные.

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

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

З5 подключены к признаковому входу блока, выход первого элемента И подключен к инверсному входу-шестого элемента И и первому входу второго элемента ИЛИ, второй вход которого сое40 динен с выходом пятого элемента И,. выход второго элемента ИЛИ подключен к входу асинхронной установки в "0"1 первого триггера, выход второго элемента И соединен с вторым входом чет45 вертого и инверсным входом пятого элементов И, прямой выход первого триггера подключен.к прямому входу шестого элемента И, выход которого, соединен с первым входом третьего !

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

"1" второго триггера, прямой выход которого соединен с.третьим входом третьего элемента И, вход асинхронной

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

1336116

22 21

Фиг.2

2б

Риа Э

Составитель В. Рудаков

Редактор А. Козориз Техред И.Попович Корректор С. Черни

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

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

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

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