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

113361

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

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

На фиг. 1 изоб15ажена функциональная схема блока поиска информации для ассоциативного запоминающего устройства; на фиг. 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.

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

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

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

162

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

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

5Г-(-Г. Г.,.-.; :.. -к. -ч ..

где

U),.J

.f)-i „ 18

j-13

JM

. i .

Т x,., F(J-J )

(X V.

f j-z

x

Cj-Jl

определяются аналогично); x.,e fO,

0при j / 0,

л

1при.j О,

.F(j-l)+F(j-2) при j 7 0,

J 1, in;

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

Величина x -J - представляет собой запись j-1 старщих разрядов кода Фибоначчи признака х.

х Г X.. F(m-j)..

Тогда

;..Г« -Г-,-,,.

Все возможные переходы в блоке поиска информации в зависимости от значений и ( учетом ис Гi-l1 Г i- 7t

ходного состояния WVf i 0), значений х,;- , х j. ,

X

i

m а XX

М

1, п, k i;

ю

.

U)

k (( е о

и значения g (сигнала начальной тановки) дает таблица переходов.

.о

о

-1

(-)

о , о

(-)

-1 о

(-)

ч о

(-) (-) (-)

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

Первая вершина графа 24 соответствует LJ вторая вершина 25 соответствует wye 1 i О, третья вершина 26 О, ;j -1, а четвертая вершина 27 соответствует

(,,)V(2u,.r + -.u, 4-3).

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

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

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

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

о

-1

. о

(-)

о о (-)

-1 о

(-3

о о о о

о о о о

25

30

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

35 подключены к признаковому входу бло- . ка, выход первого элемента И подключен к инверсному входу- шестого элемента И.и первому входу второго элемента РШИ, второй вход которого сое40 динен с выходом пятого элемента И, выход второго элемента ИЛИ подключен к входу асинхронной установки в О первого триггера, выход второго элемента И соединен с вторым входом чет45 вертого и инверсным входом пятого элементов И, прямой выход первого триггера подключен.к прямому входу шестого элемента И, выход которого ,соединен с первым входом третьего

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

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

гг г/

Фиъ.г

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

Фиг 5

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

4051/50

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

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

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