Устройство для поиска информации по совпадению

 

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

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

Известно устройство для поиска информации используемое в системах управления базами данных для автономного поиска информации в полном фрагменте данных, организованных в виде бинарного дерева [1] .

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

Наиболее близким к изобретению является устройство для поиска информации в памяти предназначенное для поиска информации в любых структурах данных [2] .

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

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

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

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

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

Устройство содержит блок 1 памяти, блок 2 сравнения, регистр 3 признака, регистр 4 маски, счетчик 5 адреса, блок 6 управления, информационные входы 7 и выходы 8, адресные входы 9, входы 10 и 11 записи и считывания соответственно, выход 12 признака переполнения, выход 13 признака пустого накопителя, выход 14 признака сравнения.

Регистр 3 признака имеет выход 15 признака поиска, регистр 4 маски имеет выход 16 маски, счетчик 5 адреса имеет выход 17 адреса.

Блок 6 управления имеет выход 18 разрешения записи и выход 19 синхронизации регистра 3 признака, выход 20 разрешения записи и выход 21 синхронизации регистра маски, выход 22 синхронизации блока 2 сравнения, выход 23 вычитания счетчика 5 адресов, выход 24 разрешения и выход 25 управления записью/считыванием блока 1 памяти.

Устройство для поиска информации в памяти содержит блок 1 памяти, регистр 3 признака, регистр 4 маски, счетчик 5 адреса, блок 6 управления, причем информационные входы 7 устройства являются информационными входами регистра 3 признака, вход разрешения записи которого соединен с первым выходом 18 блока 6 управления, второй выход 23 которого соединен с вычитающим входом счетчика 5 адреса, регистр 4 маски, информационные входы которого соединены с информационными входами блока 1 памяти, с информационными входами первой группы блока 2 сравнения и с информационными входами регистра 3 признака, выходы которого соединены с информационными входами 15 второй группы блока 2 сравнения, вход синхронизации регистра признака соединен с третьим выходом 19 блока 6 управления, четвертый 20 и пятый 21 выходы которого соединены соответственно с входами разрешения записи и синхронизации регистра 4 маски, выходы которого соединены с информационными входами 16 третьей группы блока 2 сравнения, вход синхронизации которого соединен с шестым выходом 22 блока управления, а выход является выходом признака сравнения устройства и соединен с входом суммирования счетчика 5 адреса, информационные выходы 17 которого соединены с адресными входами блока памяти, выход переноса и выход заема счетчика 5 адреса являются соответственно выходами 12 и 13 признака переполнения и признака пустого накопителя устройства соответственно, вход разрешения и вход записи/считывания блока 1 памяти соединены соответственно с седьмым 24 и восьмым 25 выходами блока 6 управления, информационные входы которого являются адресными входами 9 устройства, входы записи и считывания блока 6 управления являются соответственно входами 10 и 11 управления записью и управления считыванием устройства соответственно, выходы блока 1 памяти являются информационными выходами 8 устройства.

На фиг. 2 показан один из вариантов реализации блока 6 управления, содержащий дешифратор 26, первый 27, второй 28 и третий 29 элементы ИЛИ, элемент И-ИЛИ-НЕ 30, элемент задержки 31, первый 32 и второй 33 одновибраторы.

На фиг. 3 показан вариант блока 2 сравнения для 8-разрядной информационной шины, содержащий первый 34-1 и т. д. , восьмой 34-8 элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, первый 35-1 и т. д. , восьмой 35-8 элемент И-НЕ, элемент И-НЕ 36 и элемент ИЛИ-НЕ 37.

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

Работа устройства может осуществляться в трех режимах: записи признака поиска и маски, поиска-записи информации, считывания информации.

В режиме записи признака поиска адрес регистра 3 поступает на входы 9 блока 6 управления, который формирует на выходе 18 сигнал разрешения записи. С выхода 18 управляющий сигнал поступает на вход разрешения записи регистра 3 признака. С поступлением сигнала управления записью на вход 10 блока 6 управления на его входе 19 формируется сигнал синхронизации, по которому признак поиска запишется в регистр 3 признака.

В режиме записи маски аналогично записи признака поиска адрес регистра 4 поступает на выходы 9 блока 6 управления, который формирует на выходе 20 сигнал разрешения записи. С выхода 20 управляющий сигнал поступает на вход разрешения записи регистра 4 маски. С поступлением сигнала управления записью на вход 10 блока 6 управления на его выходе 21 формируется сигнал синхронизации, по которому маска запишется в регистр 4 маски.

В режиме поиска-записи информации при обращении к устройству адрес устройства подается на входы 9 и на дешифратор 16 в блоке 6 управления. При дешифрировании адреса обращения на выходе 24 блока 6 управления формируется сигнал выборки, который поступает на вход разрешения записи блока 1 памяти. Блок 6 управления формирует сигнал начальной установки на входе сброса счетчика 5 адреса (цепь начальной установки счетчика 5 адреса условно не показана). При этом счетчик 5 адреса устанавливается в нулевое состояние. Адрес ячейки блока 1 памяти с информационных выходов счетчика 5 адреса поступает на адресные входы блока 1 памяти. С поступлением сигнала управления записью на вход 10 блока 6 управления на его выходе 25 формируется сигнал записи, который поступает на вход записи/считывания блока 1 памяти, при этом слово данных с информационной шины запишется в ячейку блока 1 памяти. По спаду сигнала записи на выходе 22 блока 6 управления формируется сигнал "строб сравнения", который поступает на вход синхронизации блока 2 сравнения.

В зависимости от результата сравнения возможны два варианта дальнейшей работы устройства.

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

Если результат сравнения отрицательный, т. е. не все разряды признака поиска совпали с разрядами текущего слова на информационных 7 входах устройства, то импульс сравнения на выходе блока 2 сравнения формироваться не будет, счетчик 5 адреса не изменит своего содержимого и в следующем такте поиска-записи слово данных запишется в блок 1 памяти по этому же адресу. При заполнении блока 1 памяти на выходе 12 устройства формируется сигнал признака переполнения.

В режиме считывания информации по сигналу управления считыванием на входе 10 устройства на выходе 23 блока 6 управления формируется управляющий импульс, который поступает на вычитающий вход счетчика 5 адреса и уменьшает содержимое счетчика на 1. С информационных выходов 17 счетчика 5 адрес ячейки поступает на адресные входы блока 1 памяти. По сигналу считывания, который поступает с выхода 25 блока 6 управления на вход записи/считывания блока 1 памяти, слово данных через время считывания из блока 1 памяти поступает на информационные выходы устройства.

При считывании последнего слова данных из блока 1 памяти на выходе 13 устройства формируется сигнал признака пустого накопителя. (56) Авторское свидетельство СССР N 1464173, кл. G 06 F 15/40, 1989.

Авторское свидетельство СССР N 1520547, кл. G 06 F 15/40, 1990.

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

УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ ПО СОВПАДЕНИЮ, содержащее блок памяти, регистр признака, блок сравнения, счетчик, блок управления, причем информационные входы устройства являются информационными входами регистра признака, вход разрешения записи которого соединен с первым выходом блока управления, второй выход которого соединен с вычитающим входом счетчика адреса, отличающееся тем, что, с целью расширения области применения за счет выборочного маскирования отдельных разрядов признака и сокращения аппаратных затрат, оно содержит регистр маски, информационные входы которого соединены с информационными входами блока памяти, с информационными входами первой группы блока сравнения и с информационными входами регистра признака, выходы которого соединен с информационными входами второй группы блока сравнения, вход синхронизации регистра признака соединен с третьим выходом блока управления, четвертый и пятый выходы которого соединены соответственно с входами разрешения записи и синхронизации регистра маски, выходы которого соединены с информационными входами третьей группы блока сравнения, вход синхронизации которого соединен с шестым выходом блока управления, а выход является выходом признака сравнения устройства и соединен с суммирующим входом счетчика адреса, выходы разрядов которого соединены с адресными входами блока памяти, выход переноса и выход заема счетчика адреса являются соответственно выходами признака переполнения и признака пустого накопителя устройства, вход разрешения и вход записи-считывания блока памяти соединены соответственно с седьмым и восьмым выходами блока управления, информационные входы которого является адресными входами устройства, входы записи и считывания блока управления являются соответственно входами управления записью и управления считыванием устройства, выходы блока памяти являются информационными выходами устройства.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3