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

 

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

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

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

РЕСПУБЛИК 51) 6 06 F 15/40

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

Н ABTOPCHOMY СВИДЕТЕПЬСТБУ

СР

;СР

Ю

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3380805/18-24 (22) 26.11.81 (46) 30.03.83. Бюл. Г 12 (72) В.М. Капустян, 6.А. Махотенко, Ю.Л. Ордин и В.Ю. Пинаев (53) 681.325.22(088.8) (56) 1. 4ернрй А.И. Введение в теорию информационного поиска, М., "Наука", 1975

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

Н 454561, кл. 6 06 F 15/40, 1972 (прототип). (54)(57) 1. УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ, содержащее регистр ввода, блок памяти, информационные вход и выход которого соединены соответственно с первыми информационными выходом и входом регистра числа, блок памяти документальной информации, адресный вход которого соединен с выходом регистра адреса, блок анализа условий перехода, первый вход которого соединен с выходом признака регистра числа, регистр вывода, управляющий вход которого и управляющие входы-регистра ввода, блока памяти, регистра адреса, регистра числа, блока памяти документальной информации, регистра вывода и блока анализа условий перехода соединены с соответствующими выходами блока микропрограммного уп. равления, выход регистра вывода является информационным выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и экономии объема памяти для хранения поисковых признаков, в него введены блок памяти последовательного доступа, блок формирования адреса, блок сложения-умножения, „„SU„„1008752 A блок памяти магазинного типа, блок буферной памяти, счетчик, управляющие входы которых соединены с соот" ветствующими выходами блока микропрограммного управления, и дешифра" тор, выход которого подключен к входу выбора регистра ввода,. выходы которого соединены соответственно с адресными входами блока памяти, информационные входы регистра ввода соединены с выходом блока буферной памяти, информационный вход которого является информационным входом устройства, выход счетчика соединен с входом дешифратора и с вторым входом блока анализа условий перехода, выход которого подключен к первому входу блока микропрограммного управления, второй вход которого соединен с управляющим выходом блока формирования адреса, информационный вход которого соединен с первым информационным выходом блока сложения-умножения, первый информационный вход и второй информационный выход которого соединены соответствен но с вторыми информационными выходом и входом регистра числа, второй информационный вход и третий информационный выход блока сложения-умножения соединены соответственно с информационным выходом и входом блока памяти магазинного типа, второй информационный выход блока формиро- . вания адреса подключен к информационному входу регистра адреса, вход единичного признака блока формирования адреса соединен с выходом блока памяти последовательного доступв, выход блока памяти документальной ин1008752

10 формации соединен с информационным входом регистра вывода.

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

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

Изобретение относится к вычислительной технике.

Известны системы для поиска информации, построенные на основе применения электронных вычислительных машин.

В этих системах поисковое предписание представляет собой, как правило, неупорядоченный набор признаков. Поиск по заданным признакам осуществляют путем многократного последовательного просмотра массива записи, либо путем многократного просмотра цепей ссылок P1).

Недостатком устройства является требование большого количества машинного времени при решении задач, связанных с многоступенчатым поиском информации в больших массивах данных, большой объем памяти внешних устройств, большая сложность и высокая стоимость всей системы, сложность процедур обновления информации и особенно удаление исключаемых записей, когда они связаны с другими записями системой сложных i.ñûëîê; труляющим входом блока, второй управляющий вход которого подключен к второму входу второго элемента И и к второму входу вычитающего счетчика, информационные входы которого соединены с информационным входом блока, выход второго элемента И подключен к второму входу суммирующего счетчика.

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

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

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

Недостатком этого устройства является невысокое быстродействие при

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

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

:ввода,.выходы которого соединены соответственно с адресными входами блока памяти, информационные входы регистра ввода соединены с выходом

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

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

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

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

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

19 нулевого состояния, регистр 20, элементы И 21, 22, элементы ИЛИ 23, дешифратор 24, группа элементов И 25, элемент ИЛИ 26, узел 27 памяти, регистр 28, дешифратор 29 номера поля микроопераций, генератор 30 тактовых импульсов, элементы И 31, 32, группы элементов И 33-35, элементы И 36, 37, элементы ИЛИ 38, 39, выходы 40 управляющих сигналов, шаги 4 1-69 алгоритма работы устройства.

На фиг. 5 обозначены: поисковые предписания — ПП для информации, хранящейся в ячейке блока 3 памяти; значение - дк служебного элемента

"Конец серии", которое равно единице, если рассматриваемый символ по45 следний в серии, в противном случае равно нулю; значение - дкп служебного элемента "Конец признака", равное . единице, если рассматриваемый символ определяет висячую вершину, в против50 ном. случае равно нулю; значениеd служебного элемента, хранящегося в ячейке корневой вершины и равное единице, если символы серии нижележащего уровня, выходящей из данной вершины, находятся в;конъюнктивных отношениях, в противном случае равное нулю; значение - d< служебного элемента, хранящегося в ячейке корне.

52 4 вой вершины, связанной с серией символов (вершин) нижележащего уровня, находящихся в конъюнктйвных отношениях друг .с другом и равное единице, если было обращение к этой серии при расчете добавки 1 для данной корневой вершины: в противном случае равное нулю; числовое значение - d MH хранящееся в информационной части ячейки и используемое для расчета э на чений доба вки 0 .

Для составных частей устройства приняты обозначения: регистр 2ВхРг; счетчик 11 - СчУр; блок 1

БфПр; запоминание служебной информации в блоке 3 - ЗУС; регистр 4

РгЧ: блок 5 — ЬСУ; блок 6 — ЗУМ; блок 7 - ЗУПД; блок 8 - ЗУДИ; блок 9 — СхфА; вычитающий счетчик блока 9 - СхФА1; суммирующий счетчик блока 9 — СхфА2; регистр 14ВыхРг.

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

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

В целом механизм памяти состоит в следующем.

Все признаки и градации признаков, которые могут встретиться хотя бы у двух объектов запоминаемой совокупности, объединены в структуре комбинаторного дерева, где призна l008752 8 ки и их альтернативные градации про- . ПОД задается сово нумерованы, йоэтому набор признаков ных признаков, наход объекта, который надо запоминать, тивных отношениях др обозначится как дерево номеров. Ино- дый признак, состоит жеству объектов соответствует мас- s имеет иерархическую сив таких деревьев. Каждое дерево дый символ определяе номеров рассматривают как фигуру хических уровней дан некоторого числа в обобщенно-полиа- ПОД графически можно дической системе счисления и пере- виде древовидной стр водят это число в десятичную (двой- 1в любой иэ составных и ную и т.n.) систему. Получают деся- ных ПОД с верхнего у тичный номер Ф вЂ” естественный номер либо из нижележащих данного объекта. Иножеству объек- общие символы с друг тов, таким образом, соответствует Совокупность ПОД хра массив естественных ноьяров этих >> бинаторного дерева, объектов. Но массив номеров не соз- чески предствляет со дают. Вместо него берут запоминающую структуру, полученну строку битов, первоначально сплошь друг на друга древов заполненную нулями. В эту строку в ПОД. Таким образом, соответствии с десятичным номером в 20 дерево представляет

4-й по счету бит от начала строки лективный портрет со засылают битовую единицу,чем-и завер- на котором различные шается запоминание признаков данно- идентичным частям и го объекта. В конечном итоге в за- от друга оригинальны поминающей строке можно будет обна- 23 щими) признаками или ружить столько битов единиц, сколь В этом случае каждый ко объектов было предъявлено для за- вого признака будет поминания. Каждый объект запоминает- которую вершину комб ся как своеобразная битовая точка, рева. находящаяся в строке на вполне опре- щ Такой способ хран деленном расстоянии от ее начала. ти ПОДов позволяет и

Это расстояние всегда равно номеру признаков получать и объекта. Каждый номер и массив номе- соответствующие новы ров можно восстановить, измерив рас- но возможным, но ран стояние всех битовых единиц от нача- ным ПОДам. Различные ла строки. Те признаки, которые свой- и того-же уровня, пр ственны только данному объекту, не признакам, которые включают в комбинаторное дерево, а символы на всех выше хранят отдельно в виде фактографи- образуют серию симво ческого паспорта объекта, Паспортов этой серии находятся столько, сколько запомнено объектов ных (альтернативных) и, следовательно, сколько единиц с другом, если они и хранится в запоминающей строке битов. накам, которые не мо

Количество битовых единиц, от нача- нены в один ПОД, в и ла запоминающей строки битов опреде- символы серии находя ляет номер паспорта в упорядочненном ных отношениях. спике паспортов. Паспорт извлекают Любая вершина, вх по этому номеру (адресу) методом пря- наторное дерево приз мого доступа. некоторое комбинатор

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

Перед описанием работы предлаемого устройства рассмотрим особенности задания и хранения поисковых предписаний и поисковых образов документов (ПОД) . купностью составящихся в.конъюкуг с другом. Кажиз символов и структуру. Кажт один иэ иерарного признака. представить в уктуры, т.е. ризнаков заданровня до какогоуровней иметь ими признаками. нится в виде комкоторое графибой древовидную ю от наложения идных структур ко финаторное собой как бы кол" вокупности ПОДов, ПОД совпали по отличаются друг ми (не совпадаюих частями. символ поискоопределять неинаторного деения совокупносри выделении х комбинации, м принципиальее не записансимволы одного инадлежащие имеют общие лежащих уровнях, лов. Символы в дизъюнктивотношениях друг ринадлежат призгут быть объедиротивном случае тся в конъюнктиводящая в комбинаков, выделяет ное поддерево. быть охарактеричисловой характерной мощностью. р ощ ть - это макси" мально возможное количество древовидных структур, если признаки (символы), определяющие эти структуры, могут быть объединены в одном ПОД.

Такая характеристика правомерна и для комбинаторных поддеревьев, что

Для любых двух смежных уровней между значениями величины, так называемой добавки 0< 1 для корневой верЧ шины вышележащего g-го уровня и связанными с ней вершинами нижележащего (1+1)-.rо уровня существуют соотношения (Е) (+1) « 4

9-0 если символы B серии нижележащего уровня находятся в дизъюнктивных отношениях друг с другом, I где а - корневая вершина если символы серии нижележащего уровt а — 1-я вершина нижележащей се- нЯ находитсЯ в конъюнктивных отнории; шениях;

n - число вершин (символов) в 30 где - номер уровня; серии.

1 ®- номер символа (вершины) в сеI

Эти соотношения положены в осно- рии символов; ву расчета значений комбинаторной номер последнего символа в

Ь®( мо ности ля всех ве шин е ева и и серии.

9 1008 позволяет приписывать значение ком, бинаторной мощности не дереву или поддереву в целом, а только его корневой вершине. Таким образом, всем вершинам в комбинаторном дереве бу" дет формально приписано значение комбинато ной мощности. Висячим вершинам нижнего уровня может быть приписано значение мощности, равное единице.

Для любых двух смежных уровней между значениями комбинаторной мощности m(a) для корневой вершины вышележащего уровня и связанными с ней вершинами нижележащего уровня 1% существуют соотношения и

m(a) =,X m(a ), 1 если символы серии нижележащего уровня находятся в диз";юнктивных (альтер. 20 нативных) отношениях друг с другом и

m(a) =,Г1 m(a. ), 1 1 если символы серии нижележащего уров. ня находятся в конъюнктивных отноше- 25 ниях щ A р A р р переходе от нижележащего уровня к

3$ вышележащему. Расчет начинается с ви. сячих вершин нижнего уровня, где

m(a) = 1. В результате получают исходные дачные для аналогичного расчета в ближайшем вышележащем уровне, и так вплоть до расчета в единственной корневой вершине нулевого уровня.

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

50 документов, а его структура - структурой этого комбинаторного дерева.

Таким образом, поисковый признак определяет путь последовательно проходящей от корневой вершины нулевого уровня до какой-либо из вершин нижнеro уровня. Позиция с.lмвола в признаке определяет номер уровня омбинаторного дерева, на котором

752 10 расположена серия символов, находящихсА в диэъюнктйвных или конъюнктив=. ных отношениях, а числовое значение символа - его порядковый номер в этой серии.

Эти соотношения положены в основу расчета значений добавки для всех вершин дерева при переходе от нижележащего уровня к вышележащему. Расчет начинается от висячих вершин нижнего уровня, где 1) » =О. В результате получаются исходные данные для расчета в ближайшем вышележащем уровне, и так вплоть до расчета 1)(0) в единственной корневой вершине нулевого уровня. Вычисленное значение

q(o) используется для считывания

4< 1-го по счету бита в запоминающей строке битов, нулевое значение которого свидетельствует об отсутствии документа, соответствующего заданному поисковому предписанию, а единственное значение — о наличии документа. Количество битовых еди- ниц от начала запоминающей строки битов будет определять номер фактографического паспорта в упорядоченном списке паспортов. Каждой вершине поставлен в соответствие адрес ячей11. 1008 ки блока 3, в которых храняться вы- численные заранее значения,(е)

m (01), "" 1-О.ели для вершины вышележащего уровня

dT=0 о

1(а„ 1,н= 11 я(0,„), ()=1 1

1S если для вершины вышележащего уровHR dOy = 1.

Работу устройства можно описать следующими шагами. а) Прием признаков поискового предписания в блок 1 (БфПр). б) Начальная. установка. Обнуление 20

ВхРг, СчУр, регистров БСУ.

e) Прием очередного признака поискового предписания во ВхРг и определение числа уровней рассматриваемого

1 признака путем подсчета в нем количества символов в СчУр. г) Обращение к ячейке ЗУС, соответствующей корневой вершине вышележащего уровня, для определения принадлежности данного символа (верши- 30 ны) к конъюнктивной или дизъюнктивной серии„ если символ принадлежит к конъюнктивной серии, то переход к шагу 7 (содержимое СчУр-1, .считывание содержимого ячейки ЗУС. в PгЧ З$ по адресу заданному во ВхРг, если

d,.„=1, то перейти к шагу 4ж). д) Обращение к ячейке ЗУС, соответствующей рассматриваемым символам, сложение d H с содержимым БСУ. 40 (Содержимое СчУр+1, считывание ячейки ЗУС в 11гЧ по адресу заданному во

ВхРг, 01111+содержимое БСУ). е) Если рассматирваемый символ (вершина) принадлежит первому уров- IS ню, то перейти к шагу 5 с, в противном случае перейти к шагу 4г). (Содержимое .СчГр-1, проверка блоком анализа содержимого СчУр- на равенство нулю. Если содержимое СчУр=О, то So перейти к шагу -c, в противном случае к шагу 4г). ж) Если обращения к рассматривае- .

:мой серии не было, то перейти к шагу

5м. (если d < = О, то переход к шагу $$ оь

5м) °

1 и) Содержимое ЗУМ сложить с содер жимым БСУ.

752

12 к) Если рассматриваемый конъюнктивный символ последний в серии, то перейти к шагу О. (Содержимое СчГу+1, считывание ячейки ЗУС в РгЧ по адресу, заданному во ВхРг. Если д„ = 1, то переход к шагу О). л ) Содержимое БСУ записать в ЗУИ, перейти к шагу 6). м) Зафиксировать обращение к данной конъюнктивной серии, перейти к шагу К. (В элемент РгЧ для хранения d0< записать единицу, -.одержимое РгЧ переписать в ячейку ЗУС по адресу, заданному во ВхРг, перейти к шагу к); о) Если рассматриваемый символ (вершина) принадлежит первому уровню, то перейти к шагу с. (Содержимое СчУрl, проверка блоком анализа содержимое СчУр на равенство нулю. Если содержимое СчУр=0, то перейти к шагу с). и) Обращение к ячейке ЗУС соответствующей корневой вершине вышележащего уровня, перемножение dl с содержимым в БСУ. (Считывание содержимого ячейки ЗУС в РгЧ по адресу, заданному во BxPr, .11,н умножить на содержимое .БСУ). р) Зафиксировать конец обращения к данной конъюнктивной серии, перейти к шагу г. (В элемент РгЧ для хранения 4 оБ за" писать содержимое РгЧ переписать в . ячейку ЗУС по адресу, заданному во

ВхРг.. Перейти к шагу г). с ) Считывание из запоминающей строки битов, записанной в ЗУПД, бита информации, местоположение которого определяется результатом вычислений, хранящимся в БСУ. Одновременное определение количества би-— товых единиц от начала запоминающей строки до данного бита. Если значение считанного бита равно единице, то перейти к шагу т, в противном случае - к шагу у. (Содержимое БСУ переписывается в

СхФА, производится последовательное считывание информации нз ЗУПД Если значение последнего считанного бита равно единице, то адрес сформированный СхФА выдается в РгА и переход к шагу т. Если значение считанного бита равно нулю, то переход к шагу у). т ) Считывание из памяти ЗУДИ фактографического паспорта по адресу определенному в шаге C и соответ08752 14

ФО

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

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

28 устанавливается в нулевое состояние при начальной установке, наращивается на единицу в случае естественного перехода, принудительно устанавливается. в соответствии с адресом перехода хранящимся в узле 27 памяти в случае наличия управляющих сигналов: безусловного перехода УС (Sll), условного перехода по результатам анализа сигналов из блока 9 формирования адреса УС условного перехода по результатам анализа сигналов из блока 13 анализа условий перехода.

Работа блока 15 осуществляется по тактовым импульсам, формируемым схемой генератора тактовых импульсов.

При поступлении на вход счетчика

17 управляющего сигнала с блока I5

30

13 10 ствующему количеству битовых единиц в строке битов. Выдать информацию о найденном документе и перейти к шагу а. (Считывание информации из ЗУДИ по ад ресу, хранящемуся в PrA, выдача ее в ВыхРг, переход к шагу а). у) Выдача информации об отсутствии документа. .(Считывание информации из ЗУДИ по ну. левому адресу, заданному в PrA).

Основные управляющие сигналы вырабатываются в блоке 15 за счет последовательного считывания и расшифровки информационных слов (микрокоманд), располагающихся в ячейках отдельного постоянного (полупостоянного) узла 27 памяти (фиг. 4). информация с выхода блока 5 записывается в счетчик 17 одновременно обнуляется счетчик 18 ° Затем по управляющим сигналам с блока 15 производится последовательное уменьшение на единицу содержимого счетчика 17 и одновременное считывание информации из ячеек блока 7 памяти последовательного доступа, начиная с нулевой. При появлении на выходе блока

7 единицы, содержимое счетчика 18 увеличивается на единицу. Сигнал об обнулении содержимого счетчика 17 вырабатывается дешифратором и выдается в блок 15. По этому сигналу из блока 15 выдается управляющий сигнал для переписи информации со счетчика 18 в регистр 10 адреса. Однако, если при.этом на выходе блока 7 присутствует нуль (отсутствие документа в блоке 8), то регистр 10 адреса обнулится, а записи информации со счетчика 18 не произойдет.

По следующему управляющему сигналу с блока 7 производится считывание из блока 8 информации по адресу, содержащемуся в регистре 10 адреса и выдача ее в регистр 14. Таким образом, в зависимости от содержимого регистра 10 адреса в регистр 14 поступит информация о найденном в блоке 8 документе, либо (РгА=О) об отсутствии документа.

Блок 13 служит для выработки условий перехода при работе устройства по алгоритму. На выходах элементов И 25 появляется сигнал о состоянии разрядов регистра 4 числа адекебных эл

ding, 4кс, при наличии соответствующих управляющих сигналов из бло.ка 15, причем в любой микрокоманде может присутствовать лишь один из этих управляющих сигналов. На выходе элемента ИЛИ 26 появляется сигнал при выполнении любого из условий, проверяемых блоком 13.

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

1008752

1008752

Ф 3 Я

1008752

10087 2

ВНИИПИ Заказ 2340/60 Тираж 704 Подписное филиал ППП "Патент", г. Ужгород, ул. Проектная,.4