Устройство для поиска информации Советский патент 1988 года по МПК G06F17/30 

/

и

Изобретение относится к автоматике и-вычислительной технике и может быть использовано в системах обработки информации. Цель изобретения - повышение быстродействия устройства при поиске в нез порядоченном массиве и расширение функциональных возможностей за счет обновления информации в обрабатываемых MacciiBax в зависимости от результата поиска. С этой целью в устройство, содержащее блок 6 управления, блок 2 памяти и схему 8 сравнения, введены блоки 3-4 памяти, блок 1 обработки рубежа и коммутатор 9с соответствующими-связями. 4 з.п. ф-лы, 4 ил. г

31.

/ Г

ffl

Ю О

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

Цель изобретения - повышение быстродействия устройства при поиске в неупорядоченном массиве и расширение функциональных возможностей за счет обновления 1Нформации в обрабатывае- мых массивах в зависимости от результата поиска

На фиг, 1 изображена схема устрой

ства; на фиг„ 2 схема блока обработЕсли в течение тактов (N + 1) - 2N ср авнения содержимого регистра 7 с со держимым первого регистра блока 2 памяти не происходит, то содержимое 15 блока 2 памяти переносится в блок 3 памяти. При этом на схеме 17 сравнения в течение тактов (N + 1) - 2N производится поиск первого нулевого (не.значащего) элемента массива;, поски рубежа| на фиг, 3 - схема блока управления; на фиг 4 - схема блока коммутаторов.

Устройство содержит блок 1 обработки рубежа, блоки 2-5 памяти, блок 6 управления, регистр 7, схему 8 срав-20 ту-пающего из блока 2 памяти, пз тем

сравнения каждого вновь поступающего злемента с кодом нуля. При сравнении очередного элемента с кодом нуля схема Г/ сравнения выдает на выходе сигнения и коммутатор 9, содержшций элемент 10 задержки, элемент И 11 группы 12 и 13, элементов. И. Блок 1 обработки рубежа содержит элемент 14 задер кки5 триггер 15, формирователь 16 25 нал, временно (на один такт) блоки-.

рующий тактовый вход распределителя импульсов и разреп а ощий прием кода из регистра 7 в последний регистр блока 3 памяти, и по прошествии указак- 30 ного времени, устанавливает триггер 15 в единицу, запрещая работу блока 1 обработки рубежа в течение всех оставшихся тактов работы устройства

штульса, схему 17 сравнения, группу 18 элементов И, Блок б управления содержит элемент ШШ 19j, эле ге нт И 20;, 21,. формирователь 22 импульсар регистр 23J триггер 24 и распределитель импульсов „ содержащий элементы И 25 - 28;, элементы 1-1ЛИ 29 31s. элемент 32

задер аси, счетчики 33 и 34,, дешифратор 35 и генератор 36 ъз-гаульсов

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

В исходном состоянии триггеры 15 и 24 сброшены, блок 3 памяти содержит первьш обрабатываег.ый массив данных, блок 4 памяти содержит второй обраба- Q тываемый массив данных. Блоки 2 5 памяти имеют стековую структуру. Перед запуском генератора 36 i-мпуль- сов в регистр 7 записьгаается данное.

На тактах C2N + 1) - 3N сигнал с второго выхода деш1гфратора 35 запре- ш;ает прием з блок 2 информации из блока 3 памяти и разре:яает прием Е блок 2 памяти информации из блока 4 памяти. Аналогично на тактах (3N -ь 1)- - 4N информация из блока 2 памяти сдвигается в третий блок памяти, сравниваясь в схеме 8 с содержимьц.; регистра 7„ Переключение коммутатора

Счетчики 33, 34 и регистр 23 сброшены,;. 9 .во время тактов (3N + 1) - 4М про

С подачей разрешающего сигнала, разблокргрующего генератор 36 импульсов, происходит запуск устройства. По импульсам с выходов элементов 27, 31 происходит сдвиг информации из блока 3 в блок 2 памяти э в результа те чего на первом выходе дешифратора 35 появляется уровень 1, сохраняющийся в течении (N + 1) - 2N тактов, который подается на схему 8 сравнения разрешая ее работу, и на первый управ лякщий вход коммутатора 9, который при отсутствии блокировки на втором управляющем входе подключает выход

50

5

исходит по сигналу с трет.ьего выхода дешифратора 33, Если в течение тактов (3N. + 1) - 4N в схеме 8 сравнения совпадает содержимое регистра 7 и регистра блока 2 памяти то сигнал с выхода триггера 24 разрешает прием в регистр 23 номера текущего тактй. (О - N), во время которого произошло сравнение информации После этого информация заносится в блок 4 памяти из блока 2 памяти .и на такте C4N + 1) сигнапом с четвертого выхода дешифратора 35 блокируется работа генератора 36 импульсов. Этим

JQ 14202

блока 2 памяти к входу блока 3 памяти, Б каждом такте схема 8 сравнивает код содержимого первого регистра блока 2 памяти с содерлсимым регистра 7. При сравнении этих кодов триггер 24 устаI л 11

I f

навливается в состояние

блокируя

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

Если в течение тактов (N + 1) - 2N ср авнения содержимого регистра 7 с содержимым первого регистра блока 2 памяти не происходит, то содержимое блока 2 памяти переносится в блок 3 памяти. При этом на схеме 17 сравнения в течение тактов (N + 1) - 2N производится поиск первого нулевого (не.значащего) элемента массива;, посту-пающего из блока 2 памяти, пз тем

На тактах C2N + 1) - 3N сигнал с второго выхода деш1гфратора 35 запре- ш;ает прием з блок 2 информации из блока 3 памяти и разре:яает прием Е блок 2 памяти информации из блока 4 памяти. Аналогично на тактах (3N -ь 1)- - 4N информация из блока 2 памяти сдвигается в третий блок памяти, сравниваясь в схеме 8 с содержимьц.; регистра 7„ Переключение коммутатора

исходит по сигналу с трет.ьего выхода дешифратора 33, Если в течение тактов (3N. + 1) - 4N в схеме 8 сравнения совпадает содержимое регистра 7 и регистра блока 2 памяти то сигнал с выхода триггера 24 разрешает прием в регистр 23 номера текущего тактй. (О - N), во время которого произошло сравнение информации После этого информация заносится в блок 4 памяти из блока 2 памяти .и на такте C4N + 1) сигнапом с четвертого выхода дешифратора 35 блокируется работа генератора 36 импульсов. Этим

314

же сигналом разрешается прием кода в блок 5 памяти.

Таким образом, в результате работы устройства производится проверка массива данных, содержащегося в блоке 3 памяти, на наличие элемента, идентичного вновь вводимому данному из регистра 7, дописывание этого данного на первое свободное место в этот массив, затем поиск идентичного элемента во втором массиве данных, содержащемся в блоке 4 памяти, определение номера (адреса) этого элемента и добавление этого номера (адреса в массив адресных констант, хранящийся в блоке 5 памяти. Среди данных и адресов не должно содержаться нулевых элементов.

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

04

ход которого соединен с первым информационным входом блока обработки рубежа, второй информационный вход которого соединен с информационным

входом устройства, четвертый выход блока управления соединен с синхро- входом схемы сравнения и первым управляющим входом коммутатора, второй

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

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

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

седьмой выход которого соединен с первым входом элемента ИЛИ, выход которо- го соединен с входом останова генера- тора импульсов5выход которого соеди- нен с тактовым входом распределителя импульсов, восьмой выход которого соединен с первым входом первого элемента И, выход которого соединен с входом разрешения записи регистраj выход триггера соединен с вторым и первым входами первого и второго элементов И соответственно, девятый выход рас- . пределителя импульсов соединен с вторым входом второго элемента И, выход которого соединен с вторым входом

элемента ИШ1,

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

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

4, Устройство по п. 1, отличающееся тем, что коммутатор состоит из двух групп элементов И, элемента И и элемента задершси, выход которого является выходом признака переключения коммутатора, первый управляющий вход которого соединен с прямым входом элемента И, выход кото- рого соединен с входом элемента задержки и первым входом первой группы элементов И, выход которой является первым информационным выходом KOr-s-iy- татора,второй информационныйвьгход которого соединен с выходом второй группы элементов И, первый вход которой является вторым управляющим входом коммутатора и соединен с инверсным входом элемента И, информационный вход коммутатора соединен с вторыми входами первой и второй групп элементов И.

Фиг.г

1

...