УСТРОЙСТВО ПОИСКА ВХОЖДЕНИЙ Российский патент 2000 года по МПК G06F17/30 

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

Известно "Устройство для реализации подстановок с двухкомпонентными вхождениями" (а. с. N 1667097, 1991, Бюл. N 28), позволяющее определить вхождения в представленном слове-образце.

Известно также "Устройство для сортировки чисел" (а.с. N 1277091, 1986, Бюл. N 46), позволяющее упорядочить числа в возрастающем и в убывающем порядке.

В качестве прототипа выбран блок поиска вхождений, входящий в состав "Устройства для морфологического анализа слов естественных языков и языков "деловой прозы" (а. с. N 1837327), которое позволяет проводить морфологический анализ слов реальных языков, на основе логических признаков принадлежности к классам словоформ.

Задача заключалась в следующем:
1) уменьшить аппаратные затраты устройства;
2) упростить алгоритм блока управления;
3) повысить надежность работы поискового устройства.

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

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

БПВ - блок служит для хранения вхождений, с которыми необходимо будет провести поисковые операции.

БПС - блок служит для хранения слов, в которых будут определяться вхождения.

КОМ - служит для сравнения символов слово-образца с буквами вхождения.

БА - блок служит для анализа сигнала компаратора по обнаружению вхождений, а также по определению адреса (позиции) вхождений в слове-образце.

БХР - блок служит для хранения в памяти адресов вхождений.

БУ - блок служит для управления устройством.

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

Под алгорифмом Маркова понимается конечная последовательность формул, представляющих собой слова вида:
P ---> G,
где P - образец;
G - подстановка;
P и G - произвольные слова в фиксированном алфавите.

Работа формулы подстановки над словом заключается в обнаружении в нем такого фрагмента, который совпадает с образцом, а также замены позиции обнаруженного фрагмента на слово - подстановку. Следовательно, в том случае, когда, обрабатываемое слово может быть представлено в следующем виде:
F = _W1P_W2
где = - знак графического равенства;
_w1, _w2 - любые слова в фиксированном алфавите, тогда результат работы формулы будет иметь вид:
F = _w1G_w2.

Обнаружение фрагмента, совпадающего с образцом, осуществляется слева - направо по обрабатываемому слову. Всякий раз, когда обнаруживается первое слева вхождение образца, тогда выполняется подстановка и осуществляется переход на ту формулу подстановки, номер которой определяется меткой, принадлежащей сработавшей формуле, что составляет основу функционирования разрабатываемого устройства поиска вхождений. Такие алгорифмы Маркова называются размеченными [1, 2].

При осуществлении поисковых функций в словах, вхождения могут быть представлены пятью различными комбинациями букв в слове-образце (вхождении):
1) нет повтора одинаковых фрагментов слов (итерация) в слове-образце, пример - "абсорпнеи";
2) повтор одинаковых фрагментов слов (итерация) есть в середине слова-образца, пример - "мтрааааавыф", при этом принято обозначение P{S}T;
3) итерация существует в конце слова, пример - "савкуооооо", обозначение P{S};
4) итерация в слове-образце существует в начале слова, примером может служить вхождение "еееимпавк", обозначение {S}P;
5)итерация в слове-образце присутствует и в начале слова и в конце, пример - "ииипрнссссс", обозначение {S}P{V}.

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

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

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

Признак представления вариантов вхождений осуществляет пользователь.

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

На фиг. 2 представлен вариант технической реализации блока памяти вхождений.

На фиг. 3 представлен вариант технической реализации блока памяти слов.

На фиг. 4 показана функциональная схема блока анализа.

На фиг. 5 изображена функциональная схема блока хранения адреса вхождений.

На фиг. 6 - содержательная ГСА работы устройства.

На фиг. 7 - размеченная ГСА работы устройства.

Устройство поиска вхождений (фиг. 1) содержит блок 1 памяти вхождений, компаратор 2, блок 3 памяти слов, блок 4 анализа, блок 5 хранения адреса вхождений, блок 6 управления устройством.

Для описания алгоритма работы блока 6 управления используются следующие идентификаторы.

1. ПРКВ - признак конца вхождения. Это может быть двоичный код, равный 11...1.

2. ПРКС - признак конца слова. Равный 11...1.

3. КР - команда, определяющая конец работы устройства.

4. СУ₁ - сигналы управления сдвигающим регистром блока памяти вхождений (сигналы записи, приема, выдачи данных).

5. СУ₂ - сигналы управления сдвигающим регистром блока памяти слов (сигналы записи, приема, выдачи данных).

СДВ - команда сдвига, поступающая из блока управления на вход сдвигающего регистра вхождения блока памяти вхождений.

7. СДС - команда сдвига, поступающая из блока управления на вход сдвигающего регистра слова блока памяти слов.

8. СУП₁ - команды управления записью, выдачей, хранения блока памяти вхождений.

9. СУП₂ - команды управления записью, выдачей, хранения блока памяти слов.

10. АД₁ - адреса данных выдачи, записи блока памяти вхождения.

11. АД₂ - адреса данных выдачи, записи блока памяти слов.

12. ДН₁ - данные (двоичные коды букв) блока памяти вхождений.

13. ДН₂ - данные (двоичные коды букв) блока памяти слов.

14. ССР - сигнал сравнения, поступающий из компаратора.

15. ПРгВ - команда перезаписи вхождения из памяти вхождений в регистр вхождения.

16. ПОВ - команда признака определения вхождения в слове.

17. СВА - команда выдачи адреса вхождения из блока анализа в блок хранения адреса вхождений.

18. СЗП - команда разрешения записи в триггер Тр выходного сигнала из компаратора и записи сигнала из генератора тактовых импульсов в счетчик адреса.

19. R, S. - команды предварительной установки триггера Тр в начальное состояние.

20. ПРИЕМ - команда разрешения записи адреса вхождения в блок хранения адреса вхождений.

21. ВЫДАЧА - команда разрешения выдачи адреса вхождения из блока адреса вхождений.

22. СБРОС - команда сброса триггеров приема и выдачи адреса блока хранения вхождений.

23. АЗ - адреса записи вхождений в блоке хранения адреса вхождений.

24. АВ - адреса вхождений в блоке хранения адреса вхождений.

25. ДАВ - данные адресов вхождений.

26. АВХ - адрес вхождения.

27. ВДВ - выходные данные вхождения блока памяти вхождений.

28. ВДС - выходные данные слова блока памяти слов.

29. ДС - данные слов.

30. ДВ - данные вхождений.

31. СИМ1 - выходные данные первого символа слова.

32. СИМп - выходные данные последнего символа слова.

33. ВДС1 - двоичный код первой буквы слова.

34. ВДСп - двоичный код последней буквы слова.

35. ВДВ1 - двоичный код первой буквы вхождения.

36. ВДВп - двоичный код последней буквы вхождения.

37. БК1 - выходные данные первого символа вхождения.

38. БКп - выходные данные последнего символа вхождения.

Работа алгоритма управления устройства.

Содержательная ГСА управления приведена на фиг. 6 и отражает работу блока управления (фиг. 1).

По сигналам "УОО" и "ПУСК" (блоки 2,4-граф-схемы алгоритма) (фиг. 1) происходит установка в нуль всех элементов памяти устройства, по команде "СБРОС: = 1" (блок 3).

В блоке 5 алгоритма анализируется условие ПР, при котором в случае, если ПР равно единице, то происходит переход на блок 22, где устройством вырабатывается сигнал Аварийного останова. Если ПР равен нулю, то устройство готово к работе, т. е. поставленная задача по поиску вхождения в слове выполнима. Осуществляется при этом переход на блок 6 алгоритма.

В работе 6 алгоритма происходит запись в регистр слов из памяти слов слово-образца РгС:=ДС, в регистр вхождений записывается из памяти вхождений последовательность букв (вхождение) РгВ:=ДВ. Триггер Тр блока анализа устанавливается в "0". По этим командам происходит предварительная загрузка устройства.

В блоке 7 алгоритма происходит анализ признака конца слова ПРКС (признаком является двоичный код, равный всем единицам 11...1). Если ПРКС=0, то процесс поиска будет продолжен. Если обнаружен признак конца слова ПРКС= 1, то осуществляется переход на блок 20 алгоритма.

В блоке 8 алгоритма происходит анализ правого или левого сдвига в регистрах РгВ и РгС блоков 1 (БПВ) и 3 (БПС) соответственно. Если признак сдвига ПНС равен единице, то осуществляется переход на блок 10 алгоритма, в котором сигналы сдвига СДС и СДВ принимают значение единицы. Сдвиг регистров РгВ и РгС будет осуществляться вправо на один разряд. Поиск будет происходить с конца слова и с последней буквы вхождения. Задача соответствует четвертому варианту представления слова-образца. Если признак сдвига ПНС равен нулю, то осуществляется переход на блок 9 алгоритма, в котором сигналы сдвига СДС и СДВ принимают значение нуля. Сдвиг регистров РгВ и РгС будет осуществляться влево на один разряд. Поиск будет происходить с начала слова и с первой буквы вхождения. Задача соответствует первому-третьему варианту представления слова-образца (фиг. 2 и 3).

В блоке 11 алгоритма происходит анализ сигнала сравнения ССР, поступившего с выхода компаратора (фиг. 4). Если ССР = 1, то произошло совпадение буквы вхождения с буквой слова. В этом случае осуществляется переход на блок 16 алгоритма. Если ССР = 0, то совпадения не произошло и переход выполняется на блок 12 алгоритма.

В блоке 12 алгоритма анализируется содержимое триггера Тр (фиг. 4). Если Тр = 0, то это означает, что совпадения на предыдущем шаге не было, в этом случае на вход регистра поступает прямоугольный импульс СДС: = ГИ и осуществляется сдвиг на 1 разряд содержимого регистра слова (фиг. 3). Если Тр = 1, то осуществляется переход на блок 14 алгоритма.

В блоке 13 алгоритма на вход регистра СДС поступает прямоугольный импульс СДС: = ГИ. Происходит сдвиг на один разряд содержимого регистра слов PгС←_¹_→. Триггер Тр устанавливается в состояние "0" Тр: = 0 (фиг. 3).

В блоке 14 алгоритма происходит анализ признака конца слова ПРКС. Если ПРКС = 0, то происходит перезапись регистра вхождений из памяти вхождений этой же информации.

В блоке 15 алгоритма осуществляется перезапись информации в регистр вхождений РгВ из памяти вхождений при этом на вход регистра вхождения СДВ поступают прямоугольные импульсы СДВ: = ГИ, регистр вхождения РгВ принимает информацию из памяти вхождений считанной по этому же адресу РгВ: = ДВ. Триггер Тр устанавливается в состояние "0" Тр: = 0 (фиг. 2) .

Выходы из блоков 13, 14 (по единичному значению), 15 переходят на блок 7 алгоритма.

В блоке 16 алгоритма сигнал записи СЗП устанавливается в единичное значение СЗП: = 1, триггер Тр записывает единицу Тр: = 1, на входы счетчика Сч поступают сигналы генератора импульсов Сч: = Ги (фиг. 4).

В блоке 17 алгоритма происходит анализ признака конца вхождения ПРКВ (фиг. 2). Если ПРКВ = 1, то в регистре вхождения обнаружен двоичный код 11.. . 1. В этом случае вхождение обнаружено в слове-образце и в блок хранения адреса вхождений записывается адрес вхождения (фиг. 5). Если ПРКВ = 0, то это означает, что процесс сравнения идет по буквенно, но не все буквы вхождения еще просмотрены.

В блоке 18 алгоритма происходит запись адреса в блок хранения адреса вхождений. Сигнал разрешения для записи поступает из блока управления ПРИЕМ: = 1. В блок хранения адреса вхождений поступает на вход данных адрес вхождения БХАВ: = АВХ. Триггер Тр устанавливается в нулевое значение Тр: = 0. Происходит процесс записи адреса в блок хранения адреса вхождений (фиг. 5). По выходу из этого блока происходит переход на блок 7 алгоритма.

В блоке 19 алгоритма на входы регистров РгС и РгВ поступают из блока управления прямоугольные импульсы СДС: = ГИ, СДВ: = ГИ происходит сдвиг регистров слова и вхождения на один разряд PгС←_¹_→, PгB←_¹_→. По выходу из этого блока осуществляется переход на блок 11 алгоритма.

В блоке 20 алгоритма происходит анализ конца работы всего поискового устройства. Конец работы устройства будет в том случае, когда память вхождений окажется "пустой". Если Кр=0, то осуществляется переход на блок 21. Если КР= 1, то устройство поиска заканчивает работу и происходит переход на блок 23 алгоритма - конечный блок алгоритма.

В блоке 21 алгоритма происходит запись очередного слова из памяти слов в регистр слов для дальнейшего поиска вхождений (фиг. 3), РгС: = Дс. Триггер Тр устанавливается в нулевое значение Тр: = 0.

Работа устройства поиска вхождений заключается в следующем.

Внешние управляющие сигналы "Пуск" и "Сброс" поступают в блок 6 управления. Основная идея работы устройства заключается в следующем:
В оперативно-запоминающем устройстве блока БПС записаны слова, в которых необходимо обнаружить вхождения образца. Под вхождением подразумевается символ или цепочка символов, которые нужно найти в словах блока БПС. Вхождения находятся в оперативно-запоминающем устройстве блока БПВ. В блоке сравнения (компараторе) происходит последовательное сравнение каждой буквы вхождения с символами слова. В блоке 4 анализа обрабатывается сигнал сравнения блоков БПС и БПВ. Если вхождение обнаружено в слове то формируется адрес (позиция) этого вхождения в слове. Адрес хранится в блоке 5 хранения адреса. Если сравнение не произошло, то формируются сигналы сдвига в блоке БУ, поступающие на вход блоков БПС и БПВ.

Блок 1 памяти вхождений содержит оперативно-запоминающее устройство (ОЗУ) - память вхождений образца, реверсивный регистр сдвига РгВ (регистр вхождений), в котором будет храниться вхождение, логический элемент И1 для обнаружения признака конца вхождения, логические схемы элементов И2 (Сх И2), выполняющий роль коммутатора, логические схемы элементов ИЛИ (Сх ИЛИ), выполняющий функцию коммутатора. По сигналам управления СУп1 происходит разрешение записи информации, по адресным входам АД1 записываются данные ДН1 в ОЗУ (память вхождений) из блока 6 управления (фиг. 2). С выхода памяти вхождений информация ДВ поступает на вход реверсивного регистра вхождений, по сигналам управления СУ1 из блока 6 управления происходит запись буквы вхождения в регистр вхождений. Сигнал сдвига вхождений СДВ из блока 6 управления поступает на вход реверсивного регистра вхождений (фиг. 2). Выходная информация из реверсивного регистра вхождений БК1 и БК2 поступает на вход элемента И2 (фиг. 2). Если пользователь определил задачу соответствующую первому-третьему варианту представления вхождений, то информация из реверсивного регистра РгВ поступает с выхода БК1. Поиск вхождений осуществляется с первой буквы слова и с первой буквы вхождения. Если задача соответствует четвертому варианту представления вхождений, то выходная информация из реверсивного регистра РгВ поступает с выхода БКп. В этом случае сдвиг регистра осуществляется вправо. Поиск вхождений будет происходить с последней буквы слова и с последней буквы вхождения. Логические схемы элементов И2 и ИЛИ осуществляют коммутацию при различных вариантах представления вхождений. Реверсивный регистр выполняет сдвиг в любом направлении: слева направо или наоборот. Сдвиг вправо выполняется при значении сигнала СДВ = 1, сдвиг влево - при СДВ = 0, т.е. направление сдвига осуществляется одним управляющим сигналом [3] . Логические элементы ИЛИ коммутирует один из двух входов ВДВ1 и ВДВ2 на выходе в виде информационного сигнала ВДВ. Элемент И1 формирует сигнал признака конца вхождений ПРКВ, равный единице (все единицы на входе). В памяти вхождений формируется сигнал КР - конец работы, если ОЗУ будет пусто. Перед началом работы устройства в памяти вхождений записаны все вхождения, в регистре вхождений находится первое вхождение, сигнал признака конца вхождений ПРКВ равен нулю, сигнал сдвига вхождений СДВ равен нулю.

Компаратор 2 представляет собой устройство сравнения на равенство входных величин: выходных данных вхождений ВДВ блока 1 БПВ и выходных данных слов ВДС блока 3 БПС (фиг. 1). Если входные сигналы равны, то на выходе компаратора формируется единичный сигнал ССР. В обратном случае ССР будет равен нулю. Выходной сигнал компаратора поступает на вход блока 6 управления и вход 4 анализа (фиг. 1).

Блок 3 памяти слов содержит оперативно-запоминающее устройство (ОЗУ) - память слов, реверсивный регистр сдвига РгС (регистр слов), в котором будет хранится слово (вхождение), логический элемент И1 предназначен для обнаружения признака конца слова. Логические схемы элементов И2 (Сх И2), выполняющий роль коммутатора, логические схемы элементов ИЛИ (Сх ИЛИ), выполняющий функцию коммутатора. По сигналам управления СУп2 происходит разрешение записи информации, по адресным входам АД2 записываются данные ДН2 в ОЗУ (память слов) из блока 6 управления (фиг. 3). С выхода памяти слов информация ДС поступает на вход реверсивного регистра слов, по сигналам управления СУ2 из блока 6 управления происходит запись слова в реверсивный регистр слов РгС. Сигнал сдвига слов СДС из блока 6 управления поступает на вход реверсивного регистра слов РгС (фиг. 3). Выходная информация из реверсивного регистра слов СИМ1 и СИМп поступает на вход логических схем элементов И2. Выходная информация из элемента И2 поступает на вход логических схем элементов ИЛИ. Логические схемы элементов ИЛИ и И2 осуществляют коммутацию выходной информации из реверсивного регистра РгС на вход компаратора блока 2 (фиг. 1) и на вход логического элемента И1 (фиг. 2). Направление сдвига реверсивного РгС происходит в зависимости от выбора пользователем варианта представления вхождений, влево или вправо. Работа этого блока аналогична работе блока 1 (БПВ). Если вариант представления соответствует первому-третьему пункту формирования вхождений, то сдвиг осуществляется влево при СДС = 0. При четвертом представлении сдвиг реверсивного регистра будет происходить вправо при СДС = 1. Элемент И1 формирует сигнал признака конца слова ПРКС, равный единице (все единицы на входе). Перед началом работы устройства в памяти слов записаны все слова, в регистре слов находится первое слово, сигнал признака конца слова ПРКС равен нулю.

Блок 4 анализа содержит D-триггер с предварительной установкой - RS входы, двухвходовый элемент И, трехвходовый элемент И с двумя инверсными входами, генератор тактовых импульсов ГИ, двухвходовый элемент И, работающий в виде ключа Кл1, двоичный счетчик Сч, электронный ключ Кл2. Блок 4 анализа обрабатывает выходной сигнал ССР с компаратора. Если сигнал ССР равен единице, то это означает, что произошло совпадение двоичного кода символа вхождения с двоичным кодом буквы слова. При этом из блока 6 управления поступает сигнал СЗП, равным единице, ключ Кл1 открыт, тактовые импульсы с выхода генератора импульсов ГИ через Кл1 поступают на вход двоичного счетчика Сч. Триггер D устанавливается в единичное значение Тр: = 1. Если признак конца вхождения ПРКВ равен нулю (вхождение все еще не просмотрено), то формируются блоком 6 управления сигнал сдвига слова СДС и сигнал сдвига вхождения СДВ, равные единице, и происходит сдвиг регистров слова и вхождения на одну позицию влево, тем самым сравниваются очередные буквы слова и вхождения. Если признак конца вхождения ПРКВ равен единице (вхождение уже все просмотрено), то формируется блоком 6 управления сигнал приема ПРИЕМ, равный единице блока 5 хранения адреса вхождений (фиг. 5). Сигнал разрешения выдачи СВА, равный единице, "открывает" электронный ключ Кл2. В блок 5 хранения адреса вхождений записывается адрес вхождения с выхода двоичного счетчика Сч.

В случае не совпадения двоичных кодов символов вхождения и слова сигнал ССР принимает значения нуля. В этом случае возможны два варианта работы устройства:
1) если триггер D был установлен в нуль Тр: = 0, то блок 6 управления формирует сигнал сдвиг слова СДС, равным единице, информация при этом в регистре слова РгС блока 3 памяти слов БПС будет сдвинута на разряд влево (просмотр следующего символа регистра слова). D - триггер будет установлен в нулевое значение Тр: =0. Процесс поиска совпадений вхождения в слове будет продолжен.

2) если триггер D был установлен в единице Тр: = 1 (совпадения уже были), а признака конца слова еще нет ПРКС: = 0, то происходит перезапись этого же вхождения из памяти вхождений в регистр вхождений блока 1 памяти вхождений БПВ (фиг. 2). Содержимое регистров слов блока 3 памяти слов БПС остается неизменным. При этом формируются сигналы: сигнал сдвига вхождений СДВ: = 1, регистр вхождений РгВ принимает выходную информацию из памяти вхождений РгВ: = ДВ, сигнал сдвига слов СДС: = 0, D-триггер принимает значение нуля Тр: = 0.

Признак конца работы устройства КР, равного единице может быть сформирован тогда, когда все вхождения просмотрены, в памяти вхождений нет информации. Если КР равен нулю, то регистр слова РгС блока 3 памяти слов БПС принимает новую информацию (новое слово) из памяти слов (фиг. 3).

Блок 5 хранения адреса вхождений БХАВ содержит регистровую память РП, счетчик записи Сч1, счетчик выдачи Сч2 (фиг. 5). На вход регистровый памяти РП поступают адреса вхождений из блока 4 анализа АВХ и по соответствующим адресам АЗ записываются в память. На счетчики Сч1 и Сч2 из блока 6 управления поступает сигнал сброса. По этому сигналу СБРОС: = 1 счетчики переходят в нулевое значение.

Блок 6 управления синтезируется на основе ГСА алгоритма управления (фиг. 6) известным способом [4]. Размеченная ГСА работы блока 6 управления приведена на фиг. 7, где обозначено:
Источники информации
1. Марков А.А., Нагорный Н.М. Теория алгоритмов. - Москва.: Наука - 318 с. Главная редакция физико-математической литературы. 1984 г.

2. Успенский В.А., Семенов А.Л. Теория алгорифмов: основные открытия и приложения. - Москва.: Наука. Главная редакция физико-математической литературы. 1987 г. - 210 с.

3. Алексенко А.Г., Шагурин И.И. Микросхемотехника: Учеб. пособие для вузов. - 2-е изд., перераб. и доп. - М.: Радио и связь, 1990. - 496 с.: ил.

4. Баранов С. И. Синтез микропрограммных автоматов. - Энергия. Ленинградское отделение. 1974 г. - 184 с.

5. Цифровые и налоговые интегральные микросхемы: Справочник под ред. С. В.Якубовского. - М.: Радио и связь, 1990. - 496 с.: ил.

6. А.С. СССР N 1837327 (прототип).

7. А.С. СССР N 1667097 (аналог).

8. А.С. СССР N 1277091 (аналог).

Изобретение относится к вычислительной технике и может быть использовано при создании баз данных. Техническим результатом является уменьшение аппаратурных затрат и повышение надежности устройства. Устройство поиска вхождений содержит блок памяти вхождений, компаратор, блок памяти слов, блок анализа, блок хранения адреса вхождений, блок управления, оперативно-запоминающие устройства, Д-триггер, электронные ключи, генератор тактовых импульсов, двоичные счетчики, реверсивные регистры, логические элементы И, НЕ-И, ИЛИ. 7 ил.

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