Устройство поиска вхождения образца

 

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

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

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

В качестве прототипа выбрано "Устройство для реализации подстановок слов" (а. с. 1642880, 1990 г.), которое предназначено для обработки символьной информации в соответствии с заданными нормальными алгоритмами. Выполнение алгоритма заключается в реализации формул-подстановок вида Р-->S. Реализация формулы сводится к поиску образца Р в обрабатываемом слове и замене в случае обнаружения позиции вхождения этого фрагмента на подстановку S.

Поиск позиции вхождения выполняется схемой сравнения по всем буквам образца одновременно, что при кодировании букв в стандарте ASCII (8 бит) и тем более при использовании двухбайтовой кодировки UNICODE (16 бит) приводит к значительной аппаратной сложности блока обнаружения вхождения и к снижению надежности его работы.

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

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

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

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

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

В устройстве поиска вхождения образца реализуется двухступенчатый конвейер. Первая ступень конвейера включает в себя блок 6 преобразования слов и блок 5 обнаружения вхождения образца и предназначена для поиска возможных позиций вхождения образца по минимальному объему данных, следуемых из структурных особенностей обрабатываемых слов, и для помещения адресов позиций вхождений в буфер. Центральное место второй ступени конвейера, представленной блоком 2 результата, занимает схема побуквенного сопоставления образца и слова, начиная с позиций, которые были определены при работе первой ступени конвейера. Блоки 7 и 1 - блоки управления первой и второй ступенью конвейера соответственно. Устройство поиска содержит также блок 4 памяти формул и блок 3 памяти слов. Для независимой работы двух ступеней конвейера блок 3 памяти слов имеет двухканальное ОЗУ. Для согласованного управления функционированием двух ступеней конвейера используется регистр флагов - внутренний регистр состояний 8, входящий в блок 6 преобразования слов.

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

Пусть А_i и А_i+1 подряд следующие буквы произвольного слова, тогда при выполнении отношения код (А_i)≥код(А_i+1) в результирующий вектор записываем 1, в противном случае - 0. Под операцией код(<буква>) подразумевается порядковый номер буквы рабочего алфавита.

Применение вышеописанного правила ко всем по порядку слева направо буквам слова длиной L приводит к получению сжатого представления слова в виде двоичного вектора длиной L-1.

После обработки образца и слова вышеизложенным правилом процедура поиска позиции вхождения сводится к сопоставлению двоичных цепочек W (сжатое представление образца) и V (сжатое представление обрабатываемого слова).

Например, Слово-образец: - cbdd Вектор W: - 101 Обрабатываемое слово: - cbccbabcbccbddbabdaddc Вектор V: - 101110010110111001011 При последовательном сканировании W в V можно сделать четыре предположения о возможной позиции вхождения образца в обрабатываемом слове. Это позиции 1, 8, 11 и 18.

Блок 6 преобразования слов (см. фиг.2) состоит из двух групп элементов, отвечающих за независимое преобразование образца и слова. Группа элементов для преобразования слова включает в себя регистры 12 и 14 хранения соседних букв слова, схему 10 выработки признака заключительного символа слова, схему 13 сравнения регистров 12 и 14 на отношение "Больше Или Равно", суммирующего счетчика 9 для адресации буквы слова в памяти слов 3 и одного элемента "ИЛИ" 11 для коммутации сигналов СЧ1+1 и ТИЗПС. Группа элементов для преобразования образца включает в себя регистры 19 и 21 хранения соседних букв образца, схему 17 выработки признака заключительного символа образца, схему 20 сравнения регистров 19 и 21 на отношение "Больше Или Равно", суммирующего счетчика 16 для адресации буквы образца в памяти формул 4, мультиплексора 15 для переключения адресов обращения к памяти формул 4 двух ступеней конвейера и одного элемента "ИЛИ" 18 для коммутации сигналов СЧ2+1 и ТИЗПО. Кроме того, в блок 6 преобразования слов входит внутренний регистр состояний 8 с одним элементом "ИЛИ" во входной части.

Блок 5 обнаружения позиции вхождения образца (см. фиг.3) состоит из m-разрядных регистров 22 и 26 хранения сжатого представления слова и образца соответственно, (m+1)-разрядного регистра маски 27 для хранения длины образца, m однобитовых компараторов 25 сравнения на "Равно" одноименных разрядов регистров 22 и 26, m двухвходовых элементов "ИЛИ" 24 для учета маски регистра 27 и схемы "И" 23.

Блок 2 результата содержит буферный адресный регистр 32, вычитающий счетчик 30 для адресации буквы образца в памяти формул 4, вычитающий счетчик 33 для адресации буквы слова в памяти слов 3, регистр 34 хранения буквы слова, регистр 36 хранения буквы образца, схему 35 сравнения на "Равно" регистров 34 и 36, схему 37 выработки признака заключительного символа образца, адресный регистр 29 для хранения результата поиска позиции вхождения образца и регистр флагов результата поиска 28.

В регистре результата 28 предусмотрены следующие флаги (см. фиг.5): Р3 - флаг конечного результата. Установлен в "1", когда устройством был получен определенный результат: или вхождение обнаружено, или вхождение не обнаружено. При этом все флаги регистра результата 28 и значение адресного регистра результата 29 являются актуальными и могут быть прочитаны через внешние информационные выходы; ПО - флаг пустого образца. Установлен в "1", когда была обнаружена ситуация вхождения пустого образца;
ПС - флаг пустого слова. Установлен в "1", когда обрабатываемое слово пустое;
ПП - флаг переполнения. Этот флаг всегда установлен в значение 0-го разряда регистра маски 27 и сигнализирует о переполнении разрядности устройства;
КС - флаг конца слова. Этот флаг всегда установлен в значение сигнала ПРКС (признак заключительного символа слова), вырабатываемого схемой 10;
ВО - флаг - вхождение обнаружено. Устанавливается в "1" блоком управления второй ступени конвейера после доказательства того факта, что позиция вхождения образца, предварительно определенная первой ступенью конвейера, верна. При этом адрес позиции вхождения загружен в адресный регистр 29 для хранения результата.

Во внутреннем регистре состояний 8 предусмотрены следующие флаги (см. фиг.6):
С1 - флаг состояния первой ступени конвейера. Флаг установлен в "1", когда первая ступень конвейера завершила свою работу;
НБ - флаг непустого буфера. Установлен в "1", когда буферный адресный регистр 32 не пуст.

При описании алгоритма работы устройства используются следующие обозначения:
"Сброс" - сброс элементов с памятью;
"Пуск" - команда запуска устройства;
ЧБС 1 - команда чтения буквы слова из памяти слов 3 и записи ее в регистр 12 хранения текущей буквы слова;
ЧБО1 - команда чтения буквы образца из памяти формул 4 и записи ее в регистр 19 хранения текущей буквы образца;
AM - команда мультиплексирования адреса для доступа к букве образца от двух ступеней конвейера. При AM=0 учитывается адрес буквы образца для первой ступени конвейера, при AM=1 проходит адрес буквы образца второй ступени конвейера;
ПРКО - признак заключительного символа образца;
ПРКС - признак заключительного символа слова;
УАЗ - команда загрузки адреса в буферный адресный регистр 32;
УНБ - команда установки в "1" или "0" флага НБ;
УПО - команда установки в "1" флага ПО;
УБС2 - команда загрузки значения в регистр 14 хранения предыдущей буквы слова;
УБО2 - команда загрузки значения в регистр 21 хранения предыдущей буквы образца;
СЧ1+1 - команда инкремента счетчика 9 хранения адреса буквы слова;
СЧ2+1 - команда инкремента счетчика 16 хранения адреса буквы образца;
УПС - команда установки в "1" флага ПС;
УС1 - команда установки в "1" флага С1;
СД1 - команда сдвига на один разряд влево значения регистра 22 хранения сжатого представления слова;
СД2 - команда сдвига на один разряд влево значения регистра 26 хранения сжатого представления образца и регистра маски 27;
У1 - команда записи "1" в старший разряд регистра маски 27;
УРС2 - команда записи значения сигнала РС2 в старший разряд регистра 22 хранения сжатого представления слова;
УРС1 - команда записи значения сигнала РС1 в старший разряд регистра 26 хранения сжатого представления образца;
ПП - сигнал переполнения расчетной разрядности устройства;
ПВХ - признак вхождения образца в слово;
НБ - признак непустого буфера;
С1 - признак останова первой ступени конвейера;
УР3 - команда установки в "1" флага РЗ;
УА4 - команда загрузки начального значения счетчика 33 для адресации буквы слова в памяти слов 3 для второй ступени конвейера;
УА2 - команда загрузки начального значения счетчика 30 для адресации буквы образца в памяти формул 4 для второй ступени конвейера;
СЧ1-1 - команда декремента счетчика 30, адресующего буквы образца в обратном порядке;
ЧБО2 - команда чтения буквы образца из памяти формул 4 и записи ее в регистр 36 хранения буквы образца для второй ступени конвейера;
ЧБС2 - команда чтения буквы слова из памяти слов 3 и записи ее в регистр 34 хранения буквы слова для второй ступени конвейера;
ПРНО - признак заключительного символа образца;
СЧ2-1 - команда декремента счетчика 33, адресующего буквы слова в обратном порядке;
УВО - команда установки в "1" флага ВО;
УА5 - команда загрузки значения в адресный регистр результата 29;
ПРС - признак равенства букв слова и образца во второй ступени конвейера;
У02 - команда установки в "0" всех разрядов внутреннего регистра состояний 8;
АБСВН - адрес буквы слова. Внешний информационный вход;
ТИЗС - тактовый импульс счета букв слова при загрузке памяти слов 3;
БС1 - двоичный код буквы слова для первой ступени конвейера;
АБОВН - адрес буквы образца. Внешний информационный вход;
ТИЗО - тактовый импульс счета букв образца при загрузке памяти формул 4;
БО - двоичный код буквы образца;
АБО1 - адрес текущей буквы образца, адресуемой первой ступенью конвейера;
АБО2 - адрес текущей буквы образца, адресуемой второй ступенью конвейера;
АБО - входной адрес для чтения буквы образца из памяти формул 4;
РС1 - результат сравнения соседних букв образца на отношение "Больше Или Равно";
РС2 - результат сравнения соседних букв слова на отношение "Больше Или Равно";
АБС 1 - входной адрес для чтения буквы слова из памяти слов 3 через первый канал;
У01 - команда установки в "0" всех разрядов регистра маски 27;
БС2 - двоичный код буквы слова для второй ступени конвейера;
АБС3 - входной адрес для чтения буквы слова из памяти слов 3 через второй канал;
АПВ - адрес обнаруженной позиции вхождения. Внешний информационный выход;
ВРЗ - данные регистра флагов. Внешний информационный выход;
ЗАГРПС - сигнал запуска процедуры загрузки памяти слов 3;
ЗАГРПО - сигнал запуска процедуры загрузки памяти формул 4;
ЗПС - сигнал записи буквы слова в память слов 3;
ЗПО - сигнал записи буквы образца в память формул 4.

Устройство работает следующим образом. По сигналу "Сброс" устанавливаются в начальное состояние следующие элементы памяти: в блоке 5 обнаружения вхождения регистр 27, в блоке результата регистр 28, в блоке преобразования слов регистр 8. Значения счетчиков 9 и 16 принимаются соответственно за адрес первой буквы слова в памяти слов 3 и адрес первой буквы образца в памяти формул 4.

По сигналу "Пуск" в устройстве активизируется первая ступень конвейера, которая сигналами ЧБС1 и ЧБО1 запрашивает из памяти слов 3 первую букву слова, адресуемую счетчиком 9, а из памяти формул 4 - первую букву образца, адресуемую счетчиком 16 через мультиплексор 15 соответственно. Буквы записываются в регистры 12 и 19 соответственно.

В начальных тактах работы первой ступени конвейера определяются ситуации: вхождение пустого образца в пустое или непустое слово, длина образца L_о меньше длины обрабатываемого слова L_c, длина образца равна длине слова.

В блоке 6 преобразования слов регистр 12 схемой 10 тестируется на признак заключительного символа слова (ПРКС), регистр 19 схемой 17 тестируется на признак заключительного символа образца (ПРКО).

Если ПРКО= 1 (ситуация пустого образца), тогда в буферный регистр 31 по сигналу УАЗ записывается значение счетчика 9, устанавливаются флаги непустого буфера НБ:=1, пустого образца ПO:=1 и пустого слова ПС:=1, если ПРКС=1. Работа первой ступени конвейера завершается установкой флага С1:=1 во внутреннем регистре состояний 8.

Если ПРКС= 1, ПРКО=0 (ситуация L_o>L_c), то устанавливается флаг пустого слова ПС:=1 и работа первой ступени конвейера завершается С1:=1.

Если ни одна из вышеперечисленных ситуаций места не имела, тогда значение регистра 12 по сигналу УБС2 переписывается в регистр 14, значение регистра 19 по сигналу УБО2 переписывается в регистр 21. При помощи счетчиков 9 и 16, на которые подаются сигналы инкремента СЧ1+1 и СЧ2+1, адресуются следующие буквы обрабатываемых слов и их коды записываются в регистры 12 и 19.

В блоке 6 преобразования слов регистр 12 схемой 10 снова тестируется на признак ПРКС, регистр 19 схемой 17 тестируется на признак ПРКО.

Если ПРКС= 1, ПРКО=1 (слово и образец состоят из одинакового количества букв), тогда значение счетчика 9 по команде УАЗ помещается в буферный адресный регистр 32, устанавливается флаг непустого буфера НБ:=1. Работа первой ступени конвейера заканчивается установкой в "1" флага С1 во внутреннем регистре состояний 8.

Если ПРКС=1 и ПРКО=0, то работа первой ступени конвейера завершается только установкой в "1" флага С1.

При возникновении ситуации ПРКС=0 и одновременно ПРКО=0 на управляющие входы регистров 26, 27 подается сигнал СД2, а на управляющий вход регистра 22 подается сигнал СД1. СД1, СД2 - управляющие сигналы сдвига на один разряд влево. В m-е разряды регистров 22, 26 и 27 записываются соответственно результаты сравнения соседних букв РС2, РС1 и "1". Возникновение ситуации переполнения расчетной разрядности устройства (ПП=1) приводит к останову работы первой ступени конвейера (С1:=1). При отсутствии переполнения цикл чтения следующих букв образца и слова повторяется.

Если ПРКС=0 и ПРКО=1 (ситуация отсутствия переполнения и завершения формирования сжатого представления образца), тогда работа первой ступени конвейера переходит в режим поиска позиции вхождения.

Начало работы первой ступени конвейера в режиме поиска позиции вхождения характеризуется тем, что в регистр 26 загружено сжатое представление образца, в регистр 22 загружено сжатое представление начала слова (за счет использования двух схем преобразования слов, работающих параллельно), в регистре 27 сформирована маска, устанавливающая, какие разряды регистров 22 и 26 действительно будут участвовать в формировании признака вхождения ПВХ.

Группой однобитовых компараторов 25-1-25-m, группой двухвходовых элементов "ИЛИ" 24-1-24-m и схемой И 23 на m входов формируется сигнал ПВХ - результат сравнения на отношение "Равно" регистров 22 и 26 с учетом маски регистра 27.

Если вхождение обнаружено (ПВХ=1), то устройством управления первой ступени конвейера тестируется флаг НБ - запрос на запись в буфер до тех пор, пока буфер не перейдет в состояние ПУСТ (НБ=0), тогда значение счетчика 9 (адрес позиции вхождения в слове) управляющим сигналом УАЗ переписывается в буферный адресный регистр 32, устанавливается в "1" флаг НБ непустого буфера.

На управляющий вход регистра 22 подается сигнал СД1 сдвига на один разряд влево и в старший разряд m записывается результат сравнения регистров 12 и 14 РС2, одновременно с этим на счетчик 9 подается импульс СЧ1+1, тем самым адресуя следующую букву обрабатываемого слова.

Анализируется сигнал ПВХ. При обнаружении вхождения (ПВХ=1) первое устройство управления помещает позицию вхождения в буферный адресный регистр 32 (как только НБ станет равным "0") и переходит к чтению следующей буквы обрабатываемого слова.

Сигналом УБС2 буква регистра 12 переписывается в регистр 14, затем по управляющему сигналу ЧБС1 в регистр 12 из памяти слов 3 загружается код следующей буквы. Схемой 10 вырабатывается признак заключительного символа слова (ПРКС). При ПРКС=0 цикл формирования сжатого представления обрабатываемого слова и поиск позиции вхождения повторяются.

Работа первой ступени конвейера заканчивается по достижении заключительного символа слова (ПРКС=1), после чего устанавливается в "1" флаг С1.

Устройство управления второй ступени конвейера находится в режиме опроса флагов С1 и НБ внутреннего регистра состояний 8. Если буферный регистр 32 не пуст (НБ= 1), в вычитающий счетчик 30 по команде УА2 загружается значение счетчика 16, а в вычитающий счетчик 33 по команде УА4 загружается значение буферного регистра 32, сбрасывается флаг НБ.

Тестируется флаг ПО внутреннего регистра состояний, установкой которого управляет первая ступень конвейера. При обнаружении пустого образца (ПО=1) вторая ступень играет роль ретранслятора, переписывая адрес первой буквы обрабатываемого слова из буферного регистра 32 в регистр результата 29.

Если же ПО= 0, тогда на управляющий вход счетчика 30 подается сигнал декремента СЧ1-1, адресуя букву образца в обратном порядке, и одновременно на управляющий вход счетчика 33 подается сигнал декремента СЧ2-1, адресуя букву слова в обратном порядке. По команде ЧБО2 через мультиплексор 15 из памяти формул 4 в регистр 36 читается буква образца, а по команде ЧБС2 из памяти слов 3 в регистр 34 читается буква слова. Схемой 37 вырабатывается признак заключительного символа образца ПРНО. При ПРНО=1 сравнение слов прекращается, в регистр результата 29 по сигналу УА5 переписывается значение счетчика 33, устанавливаются в "1" флаги ВО и РЗ.

Если же ПРНО= 0 и результат сравнения букв образца и слова схемой 35 истинен (ПРС=1), тогда цикл побуквенного сопоставления повторяется.

Если в процессе сопоставления слова и образца возникает ситуация ПРС=0, тогда вторая ступень конвейера переходит в режим опроса флагов НБ и С1 - режим ожидания нового предварительного определения позиции вхождения образца или останова работы первой ступени конвейера.

Останов работы первой ступени конвейера (С1=1) и отсутствие предсказания в буфере (НБ= 0) приводит к останову работы второй ступени конвейера с результатом - вхождение не обнаружено.

По сигналу ЗАГРПС устройство начинает функционировать в режиме загрузки памяти слов 3. По информационному входу АБСВН счетчик 9 управляющим сигналом УА1 устанавливается в 0. Тактовым импульсом ТИЗС адресуется следующая ячейка в памяти слов 3. Пока ТИЗС=1, по информационному входу ИВС сигналом ЗПС в ячейку памяти слов 3, адресуемую счетчиком 9, загружается очередная буква слова.

По сигналу ЗАГРПО устройство начинает функционировать в режиме загрузки памяти формул 4. По информационному входу АБОВН счетчик 16 управляющим сигналом УА2 устанавливается в 0. Тактовым импульсом ТИ-30 адресуется следующая ячейка в памяти формул 4. Пока ТИЗО=1, по информационному входу ИВО сигналом ЗПО в ячейку памяти формул 4, адресуемую счетчиком 16 через мультиплексор 15, загружается очередная буква образца.

Устройства управления (блок 1 управления второй ступенью конвейера и блок 7 управления первой ступенью конвейера) синтезируются по известным правилам на основе блок-схем алгоритмов управления, представленных на фиг.8 и 7 соответственно.

Список используемой литературы
1. А.С. 1642880 СССР, МКИ5 G 06 F 15/16. Устройство для реализации подстановок слов. /Довгаль В.М. и др. 1988.

2. А.С. 1667097 СССР, МКИ5 G 06 F 15/20. Устройство для реализации подстановок с двухкомпонентными вхождениями. /Довгаль В.М. и др. 1987.

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10