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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 191 1)5 С 06 Р 15/20 ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЬГИЯПРИ ГННТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИ ЕЛЬСТВУ СКИЙ ИНСрольков,в ство СССР(56) Авторское свидетел9 1187173, кл. С 06 Р 1Авторское свидетельсР 1455345, кл. С 06 Р 1 54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ П СТАНОВОК(57) Изобретение относится к техническим средствам информации и вычислительной техники и может быть использовано для обработки массивовданных текстового и числового типов. Цель изобретения - повьппение бстродействия устройства Устройствосодержит блок 1 анализа вхождений,блок 2 формирования слов вхожденияходы которых подключены к выходам первой группы блока, первый и второй управляющие входы которого подключены соответственно к первым и вторым уп 5 равляющим входам узлов обнаружения, вторые выходы которых подключены к входам элемента ИЛИ-НЕ, выход которого подключен к выходу блока, информационные входы пятой группы которого 1 О подключены к информационным входам групп узлов обнаружения, выходы групп которых подключены соответственно к выходам второй группы блока, выходы элементов ИЛИ с первого по восьмой подключены соответственно к третьим управляющим входам узлов обнаружения с первого по восьмой, причем каждый узел обнаружения содержит два сдвигающих регистра, группу из и элементов И,элемент И, элемент ИЛИ и и элементов сравнения, при этом в каждом узле обнаружения информационные входы группы узла подключены соответственно к первым входам элементов И 25 группы и элемента И, выходы элементов И группы и элемента И подключены к входам элемента ИЛИ, выход которого подключен к первому выходу узла,первый управляющий, второй управляющий ЗО и информационный входы которого подключены соответственно к входу синхронизации первого сдвигающего.регистра, к входу синхронизации второго сдвигающего регистра и к информационному входу второго сдвигающего регистра, выходы с первого по и-й которого подключены соответственно к первым входам элементов сравнения с первого по и-й, выходы которых под О ключены соответственно к выходам группы .узла, третий управляющий вход которого подключен к второму входу элемента И и к информационному входу ,первого сдвигающего регистра, выходы 45 с первого по (и)-й подключены соот- . ветственно к вторым входам элементов сравнения с первого по (и)-й и соответственно к вторым входам элементов И с первого по (и)-й группы, и-й выход первого сдвигающего регистра подключен к второму входу и-го элемента сравнения, к второму входу и-го элемента И группы и второмувходу узла555. Устройство по п.1, о т л ич а ю щ е е с я тем, что первый блокподстановки содержит восемь узлов сдвига, счетчик, дешифратор, триггер,1коммутатор, элемент задержки, группуэлементов ЙЛИ, два элемента ЙЛИ и триэлемента И, причем первый управляющий вход блока подключен к входу элемента задержки, выход которого подключен к первым управляющим входамузлов сдвига, второй управляющий входблока подключен к первому входу первого элемента И, выход которого подключен к первому входу второго элементаИ и входам синхронизации узлов сдвига с первого по восьмой, третий и четвертый управляющие входы блока подключены соответственно к входам установки в "О" и в "1" триггера, прямойвыход которого подключен к выходублока и первому входу первого элемента ИЛИ, к первому входу третьегоэлемента И и второму входу второго. элемента И, выход которого подключенк счетному входу счетчика, выходы которого подключены к входу второгоэлемента ИЛИ и входам дешифратора,выходы которого подключены соответственно к управляющим входам группузлов сдвига, выход первого элементаИЛИ подключен к управляющему входукоммутатора и вторым управляющим входам узлов сдвига с первого по восьмой, выход второго элемента ИЛИ подключен к второму входу первого элемента ИЛИ и второму входу третьегоэлемента И, инверсный выход которого подключен к второму входу первого элемента И, инверсный выход триггера подключен к третьим управляющимвходам узлов сдвига с первого по восьмой информационные входы первойгруппы блока подключены соответственно к червым входам элементов ИЛИгруппы, выходы которых подключенык информационным входам коммутатора,выходы первой группь 1 которого подключены соответственно к выходам первойгруппы блока, выходы второй группыкоммутатора подключены соответственно к информационным входам узловсдвига с первого по восьмой, выходыкоторых подключены соответственнок выходам второй группы блока, пятыйи шестой управляющие входы которого подключены соответственно к инФормационному входу и входу установки в "Оп счетчика, информационныевходы второй группы блока подключенык инфОрмационным входам групп узловсдвига с первого по восьмой,21 22 1596345 ИУ Уч Сдр Сч +сче 6. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что второй блок подстановки содержитвосемь узлов сдвига, дешифратор, регистр, триггер, счетчик, элемент ИЛИ и элемент И, причем первый управляющий вход , блока подключен к входам установки в "О" триггера и счетчика, выходы которого подключены к входам элемента И и к информационным входам регистра, выходы которого подключены к входам дешифратора, выходы которого подключены соответственно к управляющим входам групп узлов сдвига с первого по 15 восьмой, первые выходы которых подключены соответственно к выходам первой группы блока, второй управляющий вход которого подключен к входам синхронизации узлов сдвига с первого по 2 О восьмой, третий управляющий вход блока подключен к счетному входу счет-чика, выход элемента И подключен квходу установки в "1" триггера, выходкоторого подключен к первому выходублока, четвертый и пятый управляющиевходы которого подключены соответственно к управляющим входам регистраи первого узла сдвига, вторые выходыузлов сдвига с первого по восьмойподключены к входам элемента ИЛИ, инверсный выход которого подключен квторому выходу блока, информационныевхолы которого подключены соответственно к информационным входам узловсдвига с первого по восьмой, третьивыходы которых подключены соответственно к вьжодам второй группыблока.1596345 оставитель В.Смиехред Л,Олийнык в Корректор, Н.Ревская е ор селовская Тираж 569 ого гкнт сЧс Производственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина,Заказ 2911ВНИИПИ Государств1 тетава,изо брет5, Раушс Подписное иям и открытиям и я наб., д. 4/515963454 и подстановки, блок 3 просмотра,блок 4 памяти Формул, блоки 5, 6 подстановки, блок 7 памяти слова, блок Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано для обработки массивов данных текстового и числового типов.Цель изобретения - повышение быстродействия устройства. 15На Фиг.1 приведена схема устройства; на Фиг.2 - схема блока анализавхождения: на Фиг.З - схема узла анализа; на Фиг.4 - схема блока формирования слов вхождения и подстановки;на Фиг.5 - схема блока просмотра; нафиг.б - схема узла обнаружения; нафиг.7 - схема первого блока подстановки; на фиг.8 - схема второгоблока подстановки; на фиг.9 - блоксхема алгоритма работы устройства;на фиг.10 - состояние блоков устройства в рассматриваемом примере Функционирования устройства,Устройство содержит блок 1 анализа вхождения, блок 2 формированияслов вхождения и подстановки, блок 3просмотра, блок 4 памяти формул, первый 5 и второй 6 блоки подстановки,блок 7 памяти слова, блок 8 микропрограммного управления.35Блок 1 анализа вхождения содержитсдвигающий регчстр 9, дешифратор 10,элемент ИЛИ 11, счетчик 12, восемь.узлов анализа 13, элемент И 14,40Узел 13 анализа содержит первуюгруппу элементов И 15, вторую группу элементов И 16, группу элементовИЛИ 17.и элемент ИЛИ 18,Блок 2 Формирования слов вхожде 45ния и подстановки содержит с первого по восьмой сдвигающие регистры.19, с девятого по шестнадцатый сдвигающие регистры 20, элемент 2 1 задержки, с первого по третий элементыИ 22-24, первый 25 и второи 26 зле50менты ИЛИ, группу элементов И 27,коммутатор 28 и регистр 29. Блок 3 просмотра содержит восемь55 элементов ИЛИ 30, элемент ИЛИ-НЕ 31 и восемь узлов 32 обнаружения, каждый из которых содержит первый 33 и второй Зч сдвигающие регистры, группу 8 микропрограммного управления с соответствующими связями. 5 з.п. Ф-лы,10 ил. элементов И 35, элемент ИЛИ 36, элемент И 37 и элементы 38 сравнения.Первый блок 6 подстановки содержитсчетчик 39, дешифратор 40, триггер 41,коммутатор 42, группу элементовИЛИ 43, первый 44 и второй 45 элементы ИЛИ, первый, второй и третий элементы И 46-48, восемь узлов 49 сдвигаи элемент 50 задержки.Второй блок 5 подстановки содержитрегистр 51, триггер 52, элемент И 53,счетчик 54, элемент ИЛИ 55, восемьузлов 56 сдвига и дешифратор 57.Блок 1 анализа вхождения служитдля обработки результатов сравненияна. равечство символов вхождения (левой части формулы подстановки) и фрагмента обрабатываемого слова. Анализируя результат сравнения, блок анализа вхождения выдает сигнал о наличии вхождения в обрабатываемом словев тех случаях, когда имеются на обра -ботке как те Формулы, которые содержат алфавитные переменные, так и те,которые их не содержа т. Кроме того,блок анализа вхождения с помощьюсчетчика и дешифратора задает условияобмена инФормацией между блоками просмотра, первым и вторым блоками подстановки.Блок 2 Формирования слов вхожденияи п дстановки принимает параллельно формулы подстановки, формат, которыйсодержит слово-вхождение, слово-подстановку, признаки о наличии в Формуле алФавитной переменной, признак озаключительности формулы (формула используется только один раз, еслиимеется вхождение) и признак о том, что данная формула является последней в списке формул данного нормального алгорифма,Каждая формула подстановки является элементом нормального алгорифма. Блок формирования слов вхождения и подстановки по команде сдвига из блока микропрограммного управления выдает последовательно по символам слово-вхождение и слово-подстановку в блок просмотра, а также в первый блок подстановки. Кроме того, этот блок выдает значе5 15963ния вышеприведенных признаков формулы подстановки в блок микропрограммного управления, а также признаки конца слова-вхождения и словаподстановки, а в блок анализа вхож-дения вьдает значения признаков о конце слова-вхождения и о наличии в слове-вхождении алфавитной переменной,закодированной символом у.,ОБлок просмотра служит для организации просмотра обрабатываемого слова последовательно по фрагментам,равным по длине слову-вхождению, приэтом осуществляется сравнение на ра 1венство вьделенного фрагмента обрабатываемого слова и слова-вхождения.В том случае, когда слово-вхождениеимеет в своем составе символ м., кодирующий алфавитную переменную, в блоке анализа вхождения интерпретируется символьное совпадение. Всякийне совпадающий символ, за исключениемуказанного выше случая, передаетсяво второй блок подстановки, и синхронно в соответствии с длиной словавхождения очередной символ обрабатываемого слова подается в выставленное поле сравнения. В случае обнаружения вхождения вместо символов обра 3батываемого слова во второй блок подстановки подается слово-подстановкаили те символы обрабатываемого слова, которые соответствуют алфавитнымпеременным в той последовательности,которая определяется специально организованной формой слова-подстановки, если в ней содержатся алфавитныепеременные.Второй блок подстановки служит для4хранения промежуточных фрагментовобрабатываемого слова или результирующего обрабатываемого слова с тем,чтобы процесс просмотра обрабатываемого слова с целью обнаружения вхождения и процесс подстановки в соот 45ветствии с заданной формулой подстановки осуществлялись непрерывно.Вы"ходы второго блока подстановки соединены с входами первого блока .подстановки в случае промежуточного ре 50зультата и входами блока памяти словв случае конечного результата обработки. ф Ч - Ргде Ч - слово-вхождение;Р - слово-подстановка;Р - признак формулы Ре 0,1 .Работа формулы подстановки над обрабатываемым словом заключается в об О наружении в нем слова-вхождения и замене позиции слова-вхождения словомподстановкой.Позиция вхождения является первой, если при просмотре обрабатыва емого слова вхождение обнаружено первый раз. Если признак формулы 4= 1то формула называется заключительной.Она работает один раз, а нормальныйалгоритм, представляющий собой конечный список формул подстановки,прекращает свою работу. Если признак,формулы д= О, то формула называется незаключительной и используетсяв работе столько раэ, сколько раз обнаруживается вхождение, причем приобнаружении первой позиции вхожденияосуществляется подстановка, а переходвыполняется на первую формулу. Следующая формула подстановки нормальногоалгорифма включается в работу тогда,когда предьдущая формула подстановкине обнаруживает ни одной собственнойпозиции вхождения при полном просмотре всего обрабатываемого слова.Для описания работы устройсгва используются следующие идентификаторы:УОО - установка исходных состоянийблоков устройства;ПУСК - команда запуска устройства;ЧТС - команда чтения обрабатываемого слова из блока памяти слов,"ЧТФ - команда чтения формулы иэблока памяти формул;ЗСчР 2 - команда записи всех единиц в первый блок подстановки;ТИЗ - команда сдвига для блока пропросмотра и блока анализа вхождения;ТИ 5 - команда сдвига второго блока подстановки; Первый блок подстановки предназначен для хранения и выдачи обрабатываемого слова при его первичной за- грузке иэ блока памяти слов, а также 45 6для организации непрерывности вьппеназванных процессов.Подстановка в обрабатываемое слово на место слова"вхождения формируется как из символов самого обрабатываемого слова вместо алфавитных переменных,так и иэ конкретных символов подстановки самой Формулы.Под Формулой подстановки понимается слово видаства;СБРОС - команда установки исходных состояний;1 ОЗВСчРг - команда перезаписи содержания счетчика в регистр в первомблоке подстановки,По сигналу СБРОС:=1 все элементыустройства с памятью устанавливаютсяв,исходное состояниеПо сигналуПУСК:=1 устройство начинает работать.По сигналу ЧТС:=1 осуществляется запись обрабатываемого слова по всей ТИ 6 - команда сдвига первого блока подстановки;1 ТИЧ - команда сдвига содержимого регистров блока просмотра, блока анализа вхождения и блока формирования слов вхождения и подстановки;+ 1 СчВ - команда увеличения на единицу счетчика блока анализа вхождения;СбрСчВ - команда сброса счетчика блока анализа вхождения;ТИР - команда сдвига регистров ,блока формирования слов вхождения и подстановки;П 7- признак конца слова-вхождения;ПР - признак конца слова-подстановки;ПВХ - признак наличия вхождения;ПКС 1 - признак конца обрабатываемого слова в блоке просмотра;ПКС 2 - признак конца обрабатываемого слова во втором блоке подстановкиППЕР - признак переполнения разрядной сетки во втором блоке подстановки;ППФ - признак последней формулы в нормальном алгорифме;ПЗФ - признак заключительной формулы;Авар.ост - команда аварийной остановки устройства;СбрСчА - команда сброса в нуль счетчика адреса блока памяти формул;УКМ - значение управляющего входа коммутатора в блоке формирования слов вхождения и подстановки;11 СчА - команда увеличения на единицу счетчика адреса блока памяти формул;ПР дй - признак наличия символа в слове-подстановке;ПР/ - признак символа разделения в слове-подстановке;ПСчВ - признак ненулевого состояния счетчика в блоке анализа вхождения;1 ТгР - команда установки признака подстановки первого блока подстав новки;ОбТгР - команда сброса признака подстановки первого блока подстановки;+1 Сбч 2 - команда увеличения на единицу состояния счетчика второго блока подстановки; 20 25 30 35 40 45 50 55 СбрСчб 2 - команда установки в нуль счетчика второго блока подстановки;ЗСП - команда записи обрабатываемого слова в блок памяти слова;СТОП - команда остановки .устройдлине из блока 7 памяти слова одновременно в восемь регистров блока 6 так, что каждый вертикальный срез всех восьми регистров соответствует символу. По сигналу ЗВСчРГ;=2 ев счетчик блока 6 записываются все единицы, что позволяет с помощью дешифратора открывать выходы блока 6 для сдвига информации посимвольно в блок 3. В этом же такте по команде ЧТФ:=1 параллельно считывается формула по всей длине в блок 2,В следующих тактах подаются команды сдвига на блок 3 и блок 1 анализа вхождения - ТИЗ:=1, на блок 6 ТИ 6:=1, на блок 5 - ТИ 5:=1, на блок 2, блок 1 анализа вхождения и блок 3 - ТИЧ:=1, одновременно подсчитывается количество символов слова-вхождения по команде +1 СчВ:=1 счетчиком в блоке 1 анализа вхождения до тех пор, пока не обнаружится признак конца слова-вхождения, что позволяет загрузить блок 3 словом-вхождением и. равным ему по длине фрагментом обрабатываемого слова.Если ПВХ=О (вхождения нет), то обрабатываемое слово продолжает поступать из блока 6 через блок 3 в блок 5, при этом производится счет символов обрабатываемого слова, загружаемого в блок 5, Символы обрабатываемого слова поступают в блок 5 в обход тех разрядов регистров блока 3, которые не входят в зону срав- нения, определяемую длиной вхождения. Команды сдвига формируются до тех пор, пока не будет обнаружено вхождение или не будет обнаружен конец обрабатываемого слова. Если вхождение не обнеруяено по всей длинеобрабатываемого слова, то проверяется, не является ли формула последней,Обрабатываемое слово продолжает загружаться в блок 5 до тех пор, покав нем не будет обнаружен признакконца обрабатываемого слова,В этом случае по команде ЗСП:=1обрабатываемое .слово параллельно заносится в блок 7 памяти слова. 1 О В случае, когда формула не явля.ется последней, в счетчик адреса блока 4 памяти формул прибавляется единица. После этого считывается оче редная Формула, а обрабатываемое слово продолжает загружаться в блок 5 до тех пор, пока в нем не будет обнаружен конец слова, и продолжается счет количества символов, поступивших 20 в блок 5. После загрузки обрабатываемого слова в блоке 5 проверяется признак переполнения, при ППЕР=1 формируется команда аварийной остановки устройства и устройство прекращает 25 работу, В случае отсутствия переполнения (ППЕР=О) осуществляется перезапись содержимого счетчика блока 5 в его регистр, связанный с дешифратором, а затем обнуляются счетчики бло ка 6 и блока 5 с помощью команд ЗСчР 2:=1 и СбрСчб 1:=1, СбрСчб 2:=1. После этого проверяется признак конца слова-вхождения очередной формулы нормального алгорифма", Если формула35 имеет пустое слово-вхожцение, то в начало обрабатываемого слова на место первого пустого символа ставится слово-подстановка и считывается первая формула нормального алгорифма. Это достигается тем, что обарабатываемое слово сохраняется в блоке 5, а слово- подстановка записывается посимвольно в блок 6. Для этого устанавливается в единицу триггер блока 6, сбрасыва-, ется в ноль счетчик адреса блока 4 памяти формул, на управляющем входе коммутатора блока 2 выставляется потенциал в соответствии с командой УКИ:=1 что позволяет организоватьу50 поступление подстановки в блок 6 из блока 2, Командами сдвига ТИР:=1 и ТИ 6:=1 слово-подстановка загружается в блок 6 до тех пор, пока не будет обнаружен конец слова-подстановки. После этого считывается первая форму- .55 ла нормального алгорифма и УКМ:=О,а также сбрасывается в нуль триггер . блока 6. При ПВХ=1 (вхождение обнаружено)необходимо осуществить включение слова-подстановки в обрабатываемое слово на место обнаруженного вхождения,для чего устанавливается в единицутриггер блока 6 (чтобы блокироватьпоступление последующей части словачерез блок 5 в блок 3) и сбрасывается счетчик блока 1 анализа вхождения.После этого определяется тип подстановки для классической схемы или длясхемы нормального алгорифма, содержащего в текущей формуле алфавитныепеременные,Когда ПАП= Ф - (алфавитные переменные отсутствуют), слово-подстановка посимвольно записывается в блок 5через блок 3 и производится счет принятых символов слова-подстановки изблока 2 с помощью команд ТИР:=1,ТИ 5;=1, +1 Счб 2:=1, ТИ 6:=1 до тех пор,пока не будет обнаружен конец словаподстановки. В процессе записи слова-подстановки в блок 5 из него вэто же время может поступать конецобрабатываемого слова в блок 6 (кроме случая, когда первая формула нормального алгорифма используется первый раз).Когда ПАП=1, осуществляется проверка наличия символов , кодирующихв слове-подстановке алфавитные переменные. Если эти символы присутствуют (в начале слова-подстановки), тоосуществляется их подсчет с помощьюсчетчика блока 1 анализа вхожденияи одновременно происходит сдвиг сло".ва-подстановки в блоке 2. Цикл выполняется до тех пор, пока не закончится последовательность символов +,После завершения цикла проверяетсяналичие в слове-подстановке символаразделителя "/" или конкретного символа. В том случае, когда символ-разделитель обнаруживается (ПР/=.1), выполняются команды ТИ 6:=1, ТИ 5:=1,ТИР: 1, с помощью которых конкретноезначение алфавитной переменной переписывается из регистров блока 3 вблок 5 и выполняется сдвиг на однупозицию в регистрах блока 2,Пусть исходное обрабатываемое слово состоит из пяти символов (КаАВД), а фрагмент нормального апгорифма содержит две формулы подстановки вида:1596345 К 1 АВ Л СДЕЛ,К 2 ЫЛ а lЛ,О 0 0 0 0 0 1 0 25 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 0 К О0: 0 1 0 0 1 1 1 1 0 1 0 0 1 1 1, АВ СДЕ;2с ----- о На устройство нормальный алгорифмв блок 4 памяти формулы подается вследующем виде:1 О где К 1 и К 2 - признаки К 1 = ПАП,ППФ, ПЗФ = 000, К 2=100; Л - пустой байт (00000000).К 1 А В Л С Д Е Л 20 В таблице для символов приведена условная кодировка. Состояния блоков 3, б и 5 по этапам работы при словах-вхождениях приведены на фиг. 10.В исходном состоянии (СБРОС:=1) регистр 9 и счетчик 12 установлены в нулевое состояние. При поступлении35 в устройство очередной формулы подстановки нормального алгорифма подается команда СбрСчВ:=1, устанавливающая счетчик 12 в нулевое состоя- ние. Счетчик 12 считает число символов слова-вхождения, поступивших в блок 3, с тем, чтобы с помощью дешифратора 10 задать длину слова-вхождения на узлах анализа 13, а также задать эту же длину на блок 3. При ненулевом состоянии счетчика 12 вьдается сигнал ПСЧВ=О.Сдвигающий регистр 9 служит для приема последовательности символов5 О слова-вхождения в соответствии с сигналом сдвига, При этом, если в слове- вхождении находится обычный текущий символ, то в регистр 9 записывается нуль, если текуший символ ю, коди" рующий алфавитную переменную, то эа 55 писывается единица,Узлы 13 анализа вьдают сигнал ПВХ как в том случае, когда в работе простая формула нормального алгориф-ма, так и в случае формулы, содержащей алфавитные переменные. Сигнал ПВХ=1 формируется по опрашивающему сигналу ТИЗ, причем тогда, когда срабатывают все узлы 13 и поступает сигнал конца вхождения (ПЧФ = 1) .Сигнал ПВХ выдается с выхода элемента И 14, на входы которого поступают значения с выходов узлов 13 и ПЧ 1.Пусть слово-вхождение имеет вид: Тогда в регистре 9 код слова-вхождения будет 101, на счетчике 12 код 011, соответственно, будет возбужден четвертый выход дешифратора 10. На входы элементов ИЛИ 17 поступит, соответственно, код с выходов регистра 9 и элементов сравнения 38.Блок 2 работает следующим образом.Из блока 4 памяти формул по сигналу ЧТФ слово-вхождение подается на сдвигащие регистры 20 таким образом, что вертикальный срез сдвигающих регистров 20 дает один байт, соответствующий одному символу.Аналогично информация подается на сдвигающие регистры 19, куда записывается слово-подстановка.Служебный байт с признаками формулы: формула с алфавитными переменными (ПАП = 1), формула заключительная (ПЗФ = 1), последняя формула нормального алгорифма (ППФ = 1) - записывается в регистр 29.Информация с регистров 19 и 20 поступает последовательно, а с регистра 29 по первым трем выходам - параллельно. Для сдвигающих регистров 20 используется команда сдвига ТИЧ, для сдвигающих регистров 19 - команда сдвига ТИР. Элемент И 24 распознает символ в слове-вхождении и выдает этот сигнал ПЧ на выход блока. Схема ИЛИ 26 распознает пустой байт в конце слова-вхождения и выдает сигнал ПЧФ.Элемент И 22 распознает символ + в слове-подстановке и вьдает сигнал ПР+, Элемент И 23 распознает символ-разделитель /в слове-подстановке и вьдает сигнал ПР/.Схема ИЛИ 25 распознает пустой байт (00000000) конца слова-подстановки и вьдает сигнал ПР Ф, 13159634514Блок 3 работает следующим образом.На выходы элементов ИЛИ 30 поступает информация побайтно из блока 6 илииз блока 2, Обрабатываемое слово свыходов элементов ИЛИ 30 и слововхождение из блока 3 поступают навходы узлов 32 обнаружения, на входыкоторых также поступает информация одлине слова-вхождения из блока 1 анализа вхождений.В сдвигающий регистр 34 постугают первые биты каждого байта словавхождения, а в регистр 33 - первыебиты каждого байта обрабатываемогослова. Элементы 38 осуществляют побитное сравнение содержимого регистров 33 и 34.Последовательная выдача информации регистра 33 задается с той позиции, которая задается длиной словавхождения и определяется возбужденнымвыходом дешифратора 10 блока 1 анализа вхождения. Если возбужден выход 25дешифратора, который соответствуетнуль-состоянию счетчика 12 блока 1анализа вхождения, то обрабатываемоеслово не загружается в .сдвигающийрегистр 33. Во всех остальных случаях сдвиг инФормации по сигналамТИ 7 и ТИЗ осуществляется в названнойвыше позиции.Сигналы выходов элементов 38 сравнения подаются на блок 1 анализа35вхождения для дальнейшей обработки.Сигнал выхода элемента ИЛИ 31, распознающий пустой байт, индицирует конец обрабатываемого слова (ПКС 1) всдвигающих регистрах 33 всех восьми 40узлов 32. Выходная информация с блока3 подается последовательно на блок 5в том случае, когда вхождение не обнаружено. В.том случае, когда вхождение обнаружено, через узлы 32 передается слово-подстановка, а затем"хвост" обрабатываемого слова из блока 6Блок 5 работает следующим образом,В исходном состоянии счетчикитриггер устанавливается в нулевое состояние. Поступление обрабатываемогослова или подстановки происходит через внешний информационный вход повосьмиразрядной шине последовательно55на вторые входы восьми схем сдвигающих регистров (срез по вертикали -один байт представляет код одногосимвола),Подсчет символов начинает вестись. (команда +1 СчВ:=1) счетчиком, как только слово-вхождение будет полностью находиться в зоне сравнения (П 7 ф1) и первый же символ несравнившегося Фрагмента обрабатываемого слова начнет поступать в блок 5 таким образом, счетчик подсчитывает длину обрабатываемого слова, прошедшего обработку по одной формуле нормального алгорифма.Сигналом того, что слово полностью поступило в блок 5, является ПКС 21", что фиксируется элементом ИЛИ 55. Чтобы устройство могло продолжить работу, необходимо проверить признак переполнения (ППЕР = ОЧ 1). Если он равен Ф, то работа продолжается, иначе блок 8 выдает сигнал Авар.ост.:=1, и устройство прекращает работу,Блок 6 работает следующим образом.В исходном состоянии счетчик 39 и триггер 41 устанавливаются в нулевое состояние, По сигналу ЧТС на выходах блока 7 памяти слова выставляется обрабатываемое слово. В счетчик 39 по команде ЗСчР 2:=1 записывается двоичный код, открывая возможность подачи обрабатываемого слова по сигналам сдвига ТИ 6:=.1 на блок 3. После поступления обрабатываемого слова в блок 5 происходит обнуление счетчика 39 по сигналу СбрСчб 1:=1. К этому моменту триггер 41 всегда находится в нулевом состоянии. Если теперь слово из блока 5 начнет поступать на входы элементов ИЛИ 43, а затем на коммутатор 42, на управляющем входе которого будет логический ноль, коммутатор начнет пропускать обрабатываемое слово на вход блока 3. При обнаружении слова-вхождения триггер 41 переводится в единичное состояние (команда 1 ТгР:=1), а на управляющем входе коммутатора появляется логическая единица. По окончании подстановки произойдет сброс триггера 41. Теперь, если в блоке 5 содержится "хвост" обрабатываемого слова, оно будет поступать в блок 3 через части регистра узлов 49, занятых символами обрабатываемого слова, успевшими поступить за время подстановки.формула изобретения 1. Устройство для реализапии,подстановок, содержащее блок памяти формул, блок памяти слова и блок микро 15963 ч 5516программного управления, причем первый - пятый выходы блока микропрограммного управления подключены соответственно к входам записи блока5памяти слова, чтения блока памятислова, чтения блока памяти Формул, кпервому и второму адреснымвходамблока памяти формул, о т л и ч аю щ е е с я тем, что, с целью увеличения быстродействия, оно содержитблок анализа вхождения, блок формирования слов вхождения и подстановки,блок просмотра, первый и второй блоки подстановки, причем второй и третий выходы блока микропрограммногоуправления подключены соответственно к первым управляющим входам первого блока йодстановки и блока формирования слов вхождения и подстанов ки, с шестого по четырнадцатый выходы блока микропрограммного управления подключены соответственно куправляющим входам с первого по четвертый второго блока подстановки и 25к управляющим входам с второго пошестой первого блока подстановки,выходы первой и второй групп которого подключены соответственно к инФормационным входам первой и второй З 0групп блока просмотра, выходы первой группы которого подключены соответственно к информационным входам второго бпока подстановки, выходы первой и второй групп которого подключены соответственно к информационнымвходам первой группы первого блокаподстановки и к информационным входамблока памяти слова, выходы которогоподключены к информационным входам 40второй группы первого блока подстановки, выход которого подключен к второму управляющему входу блока Формирования слов вхождения и подстановки, выходы пеРвой, втоРой и тре тьей групп которого подключены соответственно к информационным входам третьей группы первого блока подстановки, к информационным входам третьей и четвертой групп блока про 50 смотра, выходы второй группы которого подключены соответственно к ин" формационным входам блока анализа вхождения, выходы группы которого подключены соответственно к информа 55 ционным входам пятой группы блока просмотра, выход которого подключен к первому входу режима блока микропрограммного управления, пятнадцатый выход которого подключен к первымуправляющим входам блока просмотраи блока анализа вхождения, шестнадцатый выход блока микропрограммного управления подключен к третьему управляющему.входу блока Формирования слов вхождения и подстановки,информационные входы которого подключены соответственно к выходам блока памяти формул, семнадцатый выход блока микропрограммного управления подключен к вторым управляющим входам блока просмотра, блока анализа вхождения и к четвертому управляющему входу блока формирования слов вхождения.и подстановки, восемнадцатый выход блока микропрограммного управления подключен к пятым управляющим входам блока формирования слов вхождения и подстановкч и второго блокаподстановки, первый и второй выходыкоторого подключены соответственнок второму и третьему входам режимаблока микропрограммного управления,девятнадцатый и двадцатый выходы которого подключены соответственно к третьему .и к четвертому управляющим входам блока анализа вхождения,первый и второй выходы которого подключены соответственно к четвертому и пятому входам режима блока микропрограммного управления, с первого по седьмой выходы блока Формирования слов вхождения и подстановки подключены соответственно к пятому управляющему входу блока анализа вхождения и входам режима с шестого по одиннадцатый блока микропрограммного управления, восьмой выход блока микропрограммного управления подключен к шестому управляющему входу блока анализа вхождения и к двенадцатому входу режима блока микропрограммного управления, входы признака останова, признака запуска и начальнойустановки которого подключены соответственно к входам признака аварийного останова, запуска и начальнойустановки устройства, 2. Устройство по п.1, о т л и -ч а ю щ е е с я тем, что блок анализа вхождения содержит сдвигающий ре-гистр, дешифратор, счетчик, элементИЛИ, элемент И, с первого по восьмой узлы анализа, причем информациойные входы блока подключены соответственно к информационным входам первыхгрупп узлов анализа с первого по вось.мой, первый управляющий вход бЛока подключен к управляющим входам узлов анализа с первого по восьмой, управляющие входы блока с второго по шестой подключены соответственно к5 входу синхронизации сдвигающего регистра, к счетному входу счетчика, входу установки в 0" счетчика, к информационному входу сдвигающего реги О стра и к первому входу элемента И, входы с второго по девятый которого подхлю ны соответственно к выходам узлов анализа с первого по восьмой, выходы счетчика подключены к входам дешифратора и входам элемента ИЛИ, инверсный выход которого подключен к первому выходу блока, выходы сдвигающего регистра подключены к информационным входам вторых групп узлов анализа с первого по восьмой, выход элемента И подключен к второму выходу блока, выходы дешифратора подключены соответственно к информационным входам третьей группы узлов 25 анализа с первого по восьмой соответственно и к выходам группы блока, при этом каждый узел анализа содержит первую группу из и элементов И (где и - число позиций в слове вхождения), ЗО вторую группу из и элементов И, группу из и элементов ИЛИ и элемент ИЛИ, причем в, каждом узле анализа информационные входы первой группы узла подключены соответственно к первым входам элементов ИЛИ с первого по и-й группы, информационные входы второй группы узла подключены соответственно к вторым входам элементов ИЛИ с первого по и-й группы, выходы 40 которых подключены соответственно к первым входам элементов И с первого по и-й первой группы, информационные входы третьей группы узла подключены соответственно к первым вхо-. дам элементов И с первого по и-.й второй группы, выходы которых нодключены к входам элементов ИЛИ, выход которого подключен к выходу узла, управляющий вход которого подключен к второму входу первого элемента И первой группы, выход х-го элемента И (где= 1,..,и) первой группы подключен к вторым входам (д+1)-го элемента И первой группы и д-го эле 55 мента И второй группы, выход и-го элемента И,первой группы подключен к второму входу и-го элемента И второй группы. 3. Устройство по п,1, о т л и ч а-. ю щ е е с я тем, что блок формирования слов вхождения и подстановки содержит шестнадцать сдвигающих регистров регистр, элемент задержки, три элемента И, два элемента ИЛИ, группу элементов И и коммутатор,причем с первого по семнадцатый информационные входы блока подключены соответственно к информационным входам сдвигающих регистров с первого по шестнадцатый и регистра, первый управляющий вход блока подключен к вхщу элемента задержки, выход которого подключен к управляющим входам сдвигающих регистров с первого по шестнадцатый и регистра, второй управляющий вход блока подключен к первым входам элементов И группы, выходы которых подключены к информационным входам коммутатора, выходы первой и второй групп котсрого подключены соответственно к выходам первой и второй групп блока, третий управляющий вход которого подключен к входам синхронизации сдвигающих регистров с первого по восьмой, выходы которых подключены к входам первого элемента И, второго элемента И, первого элемента ИЛИ и соответственно к вторымвходам элементов И группы, четвертый управляющий вход блока подключен к входам синхронизации сдвигающих регистров с девятого по шестнадцатый, выходы которого подключены к входам третьего элемента И, к входам второго элемента ИЛИ и соответственно к выходам третьей группы блока, пятый управляющий вход которого подключен к управляющему входу коммутатора, выходы с первого по восьмой, блока подключены соответственно к выходу третьего элемента.И, к первому,второму и третьему выходам регистра, к выходам первого элемента И, второго элемента И, к инверсному выходу первого элемента ИЛИ и к инверсному выходу второго элемента ИЛИ.4Устройство по п,1, о т л и - ч а ю щ е е с я тем, что блок просмотра содержит восемь узлов обнаружения вхождения, восемь элементов ИЛИ и элемент ИЛИ-НЕ, причем инфор" мационные входы групп с первой по четвертую блока подключены соответ- ственно к входам с первого по тре тий элементов ИЛИ и к информационным входам узлов обнаружения, первые вы