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

,Ф СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЕСНРЕСПУБЛИК 8253 А 1 9) Я 5 С 06 Р 15/ ЕТЕНИЯ ТЕЛЬСТ ДвторСиоМ и инс ьков, С.С. тут те орл ов и о СССР1986.СССР1988,ьств5/1тво5/2 ИИ ПОД тех ния, блок 3 аналии второй блоки 4блок 6 памяти подпросмотра, блок 8 ервыи а переходов, п5 подстановки,тановки, блок 7памяти слов, блок ть испол нформационныхных текстово правления Блоквый и ответств горитмом,увеличение 00 пе ыи и вт ый и вт ер тродеистви гер 16 три эле схема устроистлока анализавариант реалидстацовки; на ации блока проеден хема г.3окареал иг. 1 привфиг,2 - сов; на фиервого б. Нана ИЛИ к 4 подста гистры 19,Первым бло сдвигающие ре 20, регистр 2 гер 23, с пер элементов И 2 е ации фи 1, коммута вой по дев 4-1 - 24-9 ариан фигариант реализацидока просмотраеализации второг смотра ементоИЛИ 26 и вторую грппь 25-2, элемент Блок 7 про ционцые узлысмотра сод 28, регист пы элемент ализации подст блок 1 обнаруж 2 памяти вхожд торую груп ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯПРИ ГКНТ СССР ОПИСАНИЕ ИЗО(21) 4673821/24-24(56) Лвторское свидете9 1455345, кл, С 06 РЛвторское свидетельМ 0 1596345, кл, С 06 Р 54) УСТРОЙСТВО ЛЯ РЕЛЛИЗТАНОВОК СЛОВ57) Изобретение относится Изобретение относится к техническим средствам информатики и вычислительной техники и мож зовано для обработкипотоков и массивов даи числового типов в сзаданным нормальным алЦель изобретения операционного узла бца фиг,6 - вариант рблока подстанОнки.Устройство цля ре новок слов;.ь . жит ния вхо:юп.я, блок ческим средствам информатики и вычислительной техники и может быть использовано для обработки информационных потоков и массивов данных текстового и числового типов в соответствиис заданным нормальным алгоритмом,Цель изобретения - повышение быстродействия. Поставленная цель достигается тем, что устройство содержитблок 1 обнаружения вхождения, блок 2памяти вхождения, блок 3 анализа переходов, первый и второй блоки подстановки 4 и 5, блок 6 памяти подстановки, блок 7 просмотра, блок 8 памяти слов, блок 9 управления, 1 з.п.ф-лы, 6 ил,анализа переходов содержиторой регистры 10 и .11,орой коммутаторы 12 и 3орой счетчики 14 и 15,элемент сравнения 17 и овки содержи дешифратор ор 22, тригтую группыпервую и ИЛИ 25-1 и лемент И 27. ржит опера 29, первую в И 30 и 31.1 ЕК 853 Составитель В.Смирновловская Техред И,Дидык . Корректор Л.Пилипенко Редакто аказ 3710 ПНИИПИ Государственно изобретениям ри ГКНТ СССР11303 Раушская на одписное и открытиям и б., д. 4/5 Производственно в издательск комбинат "Патент", г. Ужгоро Гагарина, 1011 О вида 20 об- ОбРрвоО 30 1(Рт 1 рть 3" 11 м)н ы И 1 И 12-.15,:)3 еме)(т И 16, псре 3331 ц вт)р)й элРл 3(тз 11. 3 и "18, церн 331 и нто Г)Й .)лемецты зддержкц э 3 и 40.Каждый Опера 0(он н,ц узел 28 б Ока 7 просм)трд содержит первый и второй регистры 41 и 42, э,ементы .раэцее(ця 43, элемент И 44, группу элементов И 45, перео( и второй элемецты И 1 И 46 и 47,Второй блок 5 подстдцовки содержит сдеэегающе регигтрь 48, с первог) по Зете(прть 3 три геры 49-52, первый и второй элементы И 53 - 54, перв(й и второй элементы ИЛИ 55 и 56, группу эл.ментов ИЛИ 57, ссетчик 58 и )лемент 59 задержки.110 д подстановкой понимагт 5 Гге(0 ГДЕ э - СЛОВО-ХО)КДРНИЕ,.1 - слов 1-подстановка,ро - прилили формулы, оо Р 3 3, 1работы формулы попстдцовки цддрябдтыцделсл словом здключается в цдружеции в цем гловд-вхождения и зд 11)луц, кторые эя(РЕГ)лГ) НГ. г 1);)бдт 3- ндют ( 3(хох;(:ц ця и Р Г)бнд 1 Рэ ужцв;цптс Я)СЛоги 1 гк 31 г(р(эяки Обходя хопос, ССтых формул (ипц )црРЛРлРцие ф)рмул, п)тонцед)сь(Г) срдбдтьвдющих) ГпрРДРля - ютгя, исходя из состава ц структуры фЭРЛУЕ ПОДСТлиОВКИ, ВХОДЯЩИХ В аЛГО Рифм, Б НОРмлрнол длгоРифме могУт триутствовдть пары формул двух видов. К первому виду относятся те пары формул, которые при срабатывании одной из цих це активируют (не индуцируют) срябатьвацие другой формулы, Б этом случае подстановка одной формулы не имеет общего собственного начала и собственного конца вхождения другой формулы (цли собственного конца подстановки одной формулы и начала вхождения другой фо 1)лусы) .Ко второму виду относятся пары формул, которые активизируют срабатывание друг друга или одной из них,Далее будем счцтать, что всякий раэ, когда выполняется одно из следующих условии, формулы являются активиэирующимися, при условии, что в формулах левые и правые части непус мене позиции сповд-вхождеция сповомподстяцовкой.301 с(ц п,)цзндк д)орлть 3 - 1, то формула называется заключительной. )цд рдботдет Одцц рдз, и но 1 эмальнье( длгорифм, предстд цпяющий собой конечный список формул подсчэцое(3(и, прекращает свою работу, Егпц же ОВ = О, то форму- З 5 пд простая и используется в работе столько рдэ, сколько раз обнаруживается вхождение при ее вкцюченци в работу.0 дцдко в работе нормального д.;го-. 40 риЬлд, когда число )Орлул в нем больше, чем одцд, устанавливается реглд - мент работы каждой формулы подстдн Свки. Если формула в :пске цездкеппц - тельная, то прц обндружении первой пОзиции вхождРЕ(ия 0 "сществл 5 Ртся п(п- стдновкд, а переход выполняетгя ца первую Формулу. 1:.3 е,уе)щя формула подстдновки нормаленого длгорцфмя вклн)чается в раб)ту тогда, кое.д 50 пРсДьДУ 445 А)Рмс)д 3111 с 3 е 3(ОЕ)к) не О)- царужцндет цц ОдцэйОб.твен(ой ПО:(цции вхождения прц пец)л Прослотр всего обрдбдтын;цмо( О говд,5511 орядок работы ц)рмдльцого рго-: рцфмд мэжцо ц.эмеццгь, с хрдцяя эквивалент)(О П 1)РОбр(.31)нд 3(ИЯ Об)ряба 3 ь - ЦяСГ С 1 Э(Э;3 33 у"ЕМ )10 НЕЕ.3 1)Ц 53 ТХ(и =, К )К(К. = Н,)Ч(Вх СП )КЧ (11 3 ,Вх )(2)В 11где Н начало вхо ения (по ГО) ЧТО ОДНО СЛОВО ВХОдит в другое слово.К правому типу активизации формул относятся такие формулы, которые при 11 ССпросмотре обрабатываемого слова слева направо порождают вхождения в П 1)авол крыле обрабдтываелого слова (3 о ходу "еросмотра") . Ес:Еи же в ре - з.ьтдте срабатывания какой-нибупь ф)рмупы порождается вхождение в лееэ)м крыле хождения обрабатываемогэ сповд (пр)тцв хода просмотра), то такой тцц активизации бурем надснять левым. Крьцьями вхождения цазывдютгя ЖД дстановки);+1 СчЧ ПзРг ПАФ 551 ТгК реходав; СбрТг К 16 т части (левая и правая) обраба 1 ываемого слона, которые графически не ранцы фрагменту слова, совпавшему с некоторым вхождением формулы подстановки.В данном устройстве переходы с одной формулы на другую осуществляются в соответствии с графом, задающим на множестве формул отношение активизации.Введение активизации в нормальные алгорифмы требует введения не менее двух вспомогательныхметок и собственного номера формулы, а также признаков формул и признаков предыстории работы алгорифма, что позволяет практически исключить холостые шаги работы алгорифма и устройства.1.аждой формуле алгорифма поставим в соответствие две метки переходов и собственный номер формулы, являющийся ее адресом в памяти устройства. Свободные формулы имеют пустые записи в своих метках (пустые метки); у формул, которые только активизируются, имеются две равные метки; у формул, которые активизируют другие, имеются две разные метки, а переход для них осуществляется по первой метке, когда формула срабатывает, а по второй - когда формула не срабатывает, Метки включаются в работу только тогда, когда срабатывает активизирующая формула, а на первом прохождении алгорифма введем следующее правило включения формул в работу.При первом прохождении работы алгорифма каждая формула выполняет все свои подстановки на место обнаруженных вхождений, как только вхождение не обнаруживается - в работу включается следующая формула в списке алгорифма, При этом переходы на предыдущие формулы списка не выполняются, когда мы имеем свободные формулы или активизирующиеся формулы. Как только выполнит все свои подстановки первая в списке формула, которая активизирует другие формулы, находящиеся в списке выше, чем активизирующая формула, переход выполняется с нее по первой метке на первую активизированную формулу в списке алгорифма. Если первая встретившаяся в списке активизирующая формула не срабатывает, то на первом прохождении включается в работу следующая в списке формула, имеющая адрес, на единицу больший, чем активизирующая формула. 88253 6Для описания работы устройства используются следующие обозначения: Пуск - команда запуска устройства; ЧТС - команда чтения обрабатываемого слова из блока 8 памяти слова 1 ЧТЧ - чтение вхождения из блока 2 памяти вхождения; 10 СбрСчЧ - сброс счетчика длин вхожде ний в блок обнаружения вхождения;- признак приема слова в регистре блока 4 подстановки,сброс счетчика в блоке 5 подстановкисброс триггера 15 признак отсутствия вхождения;тактовые сигналы (сдвига); признак конца обрабатываемого словаф признак обнаружения вхождениякоманда чтения подстановки; признак осуществления подстановки признак одной (первой) подстановки,признак активизирующей формулы в нормальном алгорифме, признак того, что можно ставить все подстановки в обрабатываемом слове; признак правоактивизирующеи формулыпризнак последний формулыпризнак заключительной формулы,признак безусловного перехода по адресу;признак конца обрабатываемого слова," команда записи результирующего слова в блок 8 памяти слова;команда увеличения на единицу счетчика длины вхождения в блоке обнаружениявхождения,признак приема адресов перехода в регистры 10 и 11 блока анализа переходов признак наличия информации в счетчике 15 блока анализапереходов; команда записи единицы втриггер 1 б блока анализа пекоманда сброса триггера 16;,ТгТИ вхождений считывается слово-вхождение и связанные с ним признаки в блок 7 просмотра. Проверяется цризцак без О условного переходя по адресу. По сигналу Ч 5; = 1 в счетчик 14 адреса записывается адрес формулы. В случае сли П 1 Ая =- О, то по команде 73: = 1 обрабатываемое слово и значение его д 5 длины из регистров 48 и счетчика 58 перезанисывается в регистры 19 и 21. В следующем такте работы по команде СбрСчб: = 1 происходит сброс счетчика 58. Лале проверяется признак наличия или отсутствия символов в слове-вхождении, Если такие символы есть и ПРЧ = 1, то цд регистры 48, 19, 4 1 и 42 начинают поступать тактовые сигналы ТИ: = 1, Обрабатываемое55 слово цачицает поступдть посцмвольцо из блока 4 в блок 7 нрогмотрд. Одновременно слово-яхожп; ци ндчицдт перездписываться цз пцой части регист+1 Счй - комдцдд увеличения адреса нсчетчике 14 ,ту 5 команда прцмд ицформации всчетчик 14, 5+1 РгСг 2 - команда увеличения адреса всчетчике 157 И команда приема информации всчетчик 15,СбрРгСч 2 - сброс счетчика 15; ОПК ) - результат сравцеция адресаактивизирующей формулы с адрсом перехода,запись единицы в триггер 51дп формул с признаком ВСЕ; 5ТгТИ 1 - запись единицы в триггер 52дпя формул с". признаками,кроме ВСЕ и ПЛ;ППГР - признак перполнения разрядной сетки, ОТПЕЕ - команда здписи диницы втриггер 49;СбрТг 1 ЕР - команда сброс, триггера 49;. СбрСчб - сброс счетчика 58,СТОП - комдцда остановки устройства;СБРОС - комднда установки устройства в исходное состояние,По команде 11 уск: - 1 устройствоачиндет работать. По команде ЧТС: = 1 30осуществляется запись обрабатываемогослова по всей длине из блока 8 памяти слова одновременно в регистры 48,так что каждьй вертикальный срезвсех регистров 48 соответствует символу. В следующем такте работы по команд ТЧ: = 1 иэ бчока 2 памяти ров в правую, горичм тактовые сигналы в эти регистры будут поступать до тех пор, пока цс вхождение це перездпишется в правую часть, а тактовые сигналы, поступающие в регистры 48 до этого времени, блокируются, Слово продолжит перезаписываться в блок 5 до тех пор, пока не выполцится ПКГ 2 - 1. Затем проверится признак переполнения разрядной сетки этого блока и в случае переполнения ППЕР = 1 выдается команда Авар,ост.: = 1 и устройство прекратит свою работу. Если в блоке 1 обнаружения вхождения будет обнаружено вхождение ПВХ = 1, то по команде ЧТП: = 1 слово-подстановка будет считано в регистр 29, анулируя тем самым часть слона, совпадающую со словом-вхождением.Если ПА = 1, то подстановка такой формулы должна поступать иэ левойчасти в правую часть регистров в блоке 7 просмотра, сравниваясь со словомвхохсдением (новое вхождение может появиться только по ходу просмотра снова), в дальнейшем к ней должна присоединиться часть обрабатываемого слова, находящаяся в блоке 4, Если ПА = О, то проверяется признак ВГЕ,Если ВСГ = 1, то будут отыскиваться все вхохсдения данной формулы в слове, а на их место будут вставляться слова-подстановки (при этом слово не должно возвращаться). Для этого по команде ТгПЕР: = 1 в триггер 49 записывается единица и одновременно единица записывается в триггер 51, что позволяет принять подстановку в блок 5 и только после этого оставшейся части обрабатываемого слова разренить поступать в блок 7. Если ВСЕ = О, то сюда относятся формулы левоактивизирующиеся, лево-правоактивизирующиеся и формулы с подстановкой по первому вхождению в обрабатываемом слове, Для этих формул необходимо записать единицу в триггер 23, в триггер 52 также записывается единица, после чего проверяется признак ПРС. Если ПРС = 1, то подстановка из левой части регистров слова в блоке 7 переписдлась в правую часть этого блока или в блок 5, при этом в блок 5 подстдцовка записывается тогда, когдаО.1 ри ВЗА = 1 выполняемая формула цормдльцого алгорцфма является форму - пой дктинизирукщей другую.Для случая, когда можно выполнить все подстановки (ВСЕ = 1), по команде ЧТЧ: = 1 считывается слово-вхождение, в противном случае (ВСЕ = 0) будет анализироваться признак перехода. Если подстановки необходимо выполнять по всей длине слова, то происходит сброс триггера 49 (продолжится поиск вхождения). При данной ситуации подаются тактовые сигналы ТИ: = 1, продолжающиеся до тех пор, пока конец обрабатаваемого слова не появится в блоке 5 (признак ПКС 2 = 1).После загрузки обрабатываемого слова в блоке 5 проверится признак переполнения разрядной сетки устройства. Если ППЕР = 1, то формируется команда аварийной остановки устройства (Авар.ост,; = 1) и устройство пре кращает работу.В случае ППЕР = 0 проверяется признак заключительной формулы (ПЗФ =1) и по команде ЗПС: = 1 обрабатываемое слово записывается в память, 25 и устройство прекращает работу (СТОП: = 1). В том случае когда формула незаключительная, проверяется признак (ОДНА = 1) выполнения подстановки по первому вхождению. 30Если ПАФ = 1, т,е, в счетчике 15 отсутствует информация, то проверяется признак последней формулы в списке формул нормального алгорифма, Если35 ППФ = О, то в счетчик. 14 блока 3 анализа вхождения прибавляется единица ,по команде +1 СЧА: = 1, Если ПАФ = О,1то все переходы будут осуществляться по адресам, записанным в регистрах 10 и 11 блока 3 анализа переходов, ,причем, если подстановка была обнаружена в слове, то адрес будет взят из регистра 10, в противном случае - из регистра 11. По команде Ч 5: = 1 будет записан в счетчик 14 и сравнен с 45 адресом хранящийся в счетчике 15 адрес первой активизирующей формулы.В том случае когда ПК = 1, по команде +1 РгСч 2; = 1 состояние счетчика 15 увеличивается на единицу, одно временно в триггер 16 записывается единица ТгК: = 1, а в следующем такте работы по команде У 5; = 1 эта информация перезаписывается в счетчик 14,Блок 1 обнаружения вхождения служит для обработки сигналов, поступающих .с компараторов, осуществляющих сравнение на равенство символов вхож-, дения (левая часть формулыподстановки) и фрагмента обрабатываемого слова. В случае обнаружения совпадениявхождения и части обрабатываемогослова блок обнаружения вхождения выдает сигнал совпадения в блок управления. Кроме того, блок обнаружениявхождения с помощью счетчика и дешифратора задает условие обмена информацией между блоком 7 просмотра и блоками 4 и 5 подстановки,Счетчик 14, являющийся адреснымрегистром для блока 2 памяти вхождений и блока 6 памяти подстановок,хранит адрес текущей (выполняемой)формулы.Счетчик 15 хранит адрес активизирующей формулы, с которой произошелвозврат на предшествующие в схемеформулы нормального алгорифма с целью проверки появления вхождений, которые могли появиться в результатеактивизации в обрабатываемом слове.Блок 3 анализа переходов работаетследующим образом.При считывании очередной формулыпо команде ЧТЧ: = 1 из блока 2 памяти вхождений в регистры 10 и 11 блокапоступают две метки (адреса) перехода. В регистр 10 поступает метка, ккоторой необходимо перейти, если слово-вхождение будет обнаружено, в регистр 11 метка поступает, тогда, когдавхождение не будет обнаружено, Этидва адреса (метки перехода) могутбыть одинаковыми, разными и нулевыми.В счетчике 14 находится адрес выполняемой в данный момент формулы. Всчетчике 15 будет храниться адрес активизирующей формулы или счетчик 15 .будет находиться в нулевом состоянии.В зависимости от того, в каком изэтих двух состояний находится счетчик 15, на вход блока 9 управлениябудет поступать значение признакаПАФ (ПАФ = 1 - пуст, ПАФ = 0 - информация есть). В зависимости от характера выполняемой формулы после завершения работы с нею необходимо сделать возврат на предшествующие формулы нормального алгорифма или перейтик следующей формуле; если эта формулаактивизирующая, то необходимо в счетчик 15 поместить (запомнить) ее ад-рес, переписав из счетчика 14, при-чем, если при таком возврате (переходе) встретятся формулы, которые самиявляются активизирующими, то их адреса в счетчик 15 записываться не будут(ЦАф = О). Работа с: Формулами будет идти но меткам переход.Если ПЛФ =- 1 и Формула непоследняя (ППф = О), то по команде +1 СчЛ: = 1 5 адрес, хранящийся в счетчике 14 блока 3 анализа переход, будет увеличен на единицу, Есгти ПАф = О, то необходимо по команде Ч 5: -. 1 переписать адрес перехода к следующей формуле из 10 регистра 10 или 11, причем ца управляющем входе коммутатора 13 будет нуспевой.потенциал. Если быпа обнаружена хотя бы одна подстановка в обрабаты ваемом слове, то ца управляющем входе 15 коммутатора 12 будет единица, а к его информационному входу будет подключен выход регистра 10, в противном случае - выход регистра 11. После подачи команды Ч 5: .= 1 ц счетчик 14 бу дет переписан новый адрес, Если на вьгходе компаратора элемента сравнения 17 появится сигнал ПК ) := 0 (это означает, что адрес в счетчике 14 меньше, чем адрес в счетчике 15), то мож но продолжать работу с новой формулой нормального алгорифма. Если сигнал 11 К ) = 1 (это означает, что адрес в счетчике 14 больше, чем адрес в счетчике 15), то необходимо с помощью ко мянды +1 РгСч 2 =. 1 увеличить адрес в счетчике 15 на единицу и одновременно записать в триггер 16 единицу, тем самым подключить информационный выход с.четчика 15 ко входу счетчика 14 и командой Ч 5: = 1 переписать информацию в него. После этого необходимо. с.бросить счетчик 15 (команда СбрРгСч 2: = 1), триггер 16 (СбрТгК: =1) и продолжить работу согласно схеме алгорифма с новой Формулой.Обрабатываемое слово поступает на восемь сдвигающих регистров 19 блока 14, 11 о команде ЧЗ: = 1 слово из блока 5 перезаписывается в сдвигяющие регистры 19 блока 4, одновременно (по тсгму же сигналу) длина обрябать- ваемого слова, выряженная в двоичном коде, перезаписываетс.я из счетчика 58блока 5 в регистр 21 блока 4, Регистр 5021, информационный выход которогосоедгсцец с. дешифратором, может содержать также длину, равную нулю, так кяк при первом считывании слова из блока 8 памяти слов такая длина не подсчитывается счетчиком 58 блока 5. Регистр 2 1 чере дешцфрятс 1 р 20 управляет элементами И 24, находящимися няресистров что позвопяе 1 крятить время выхода оГрабатывяемого слова из регистров, когда длина слона существенно меньше длины регистра. В том случае когда слово только что за - писацо в сдвигающие регистры 19 блока 4 из блока 5, а в блок 5 - из блока 8 памяти слона, при этом начало слона расположено в старших разрядах регистров 19, а длина слова не под - считана, подача обрабатываемого слова из сдвигающих регистров 19 по сигналам ТИ: = 1 организуется с помощью элементов ИЛИ 24, 25, 26Сигналы сдвига (ТИ: = 1) начинают поступать на входы синхронизации регистров 19 только в то время, когда ИВТг 1 = 1,В том случае когда ца управляющем рходе коммутатора 22 - единица (для всех формул, кроме Формул с признаками ПА = 1, ВСЕ = 1) информация после подстановки с первого информационного выхода коммутатора 22 подается на соответствующий вход блока 5, в противном случае информация подается на соответствующий вход блока 7,Через информационные входы второй группы блока 7 посимвольно поступает обрабатываемое слово из блока 4, Каждьд бит байта поступает на соответствующий вход операционного узла 28, первый бит - на первую, второй - на вторую, , восьмой на восьмую, Рассмотрим один из восьми операционных узлов 28. Через элемент ИЛИ 46 информация поступает на вход сдвигающего регистра 42 (регистр слова), Из блока 2 памяти вхождений слово-вхождение поступает на 0-входы регистра 41 и по команде Чт 7: = 1 может быть принята в этот регистр, причем код первого символа слова-вхождения располагается в восьми старших разрядах регистра 41 (вертикальный срез по одноименным разрядам всех восьми регистров 41 представляет код символа), Сигнал ТИ поступает на входы синхронизации всех регистров 42 операционных узлов 28, Этот же сигнал будет поступать и на регистры 41 (вхождения), так как единица приходит с выхода элемента ИЛИ 46, На входы элемента ИЛИ 46 поступает информация со старших разрядов регистров 41, в которых записан символ слова-вхождения. По сигналам 1 И: = 1 слово будет посимвольно поступать на ретистры 42, а спово-подстановка будет цереэаписываться из "старших" разрядов регистров 41 узлов28 в "младшие". Сигналы сдвига цаэтих регистрах прекратятся, как только подстановка перепишется, Одновременно все восемь элементов И 44 включецы и символы, прошедшие зону сравнения (длика равна длине вхождения)через элементы И 45 и ИЛИ 47 (входсоответствующего элемента И 45 управляется дешифратором длины вхождения 1 Облока 1 обнаружения вхождения), атакже элементы И 44 начнут поступатьна соответствующий выход данного блока. Информация с элементов 43 сравнения поступает в блок 1 обнаружения 15вхождения. Необходимо отметить, чтопо команде ЧТЧ: = 1 в регистр блока 7из блока памяти вхождения считываютсяпризнаки выполняемой формулы. В случае обнаружения вхождения ПВХ = 1.По этому сигналу в регистры 42 узлов28 в следующем такте считывается подстановка, "затирая" часть слова, которая совпадает с вхождением. Словоподстановка поступает из блока 6 памяти подстановок в регистры 41. Первый символ слова-подстановки будет встарших разрядах этих регистров, Длявсех формул нормального алгорифма, укоторых признак ПА = О, информация с 30выходов элементов И 31 будет поступать в блок 5 до тех пор, пока словоподстановка не будет переписано вэтот блок (ПРС = 1),Если подстановка правоактивизирующейся формулы, то при подаче сигналовсдвига (ТИ: =.1) подстановка побитнов каждом узле 28 начнет переписываться из старших разрядов в младшие1 11 11 11Одновременно в регистрах 4 1 вхождение 40также начнет переписываться из старших разрядов в младшие , При полнойперезаписи сигнал ПРС будет равенединице , Элемент ИЛИ-НЕ 3 4 выдает вблок 9 управления единицу , к ак только 45в первых разрядах регистров 4 2 появятся все нули (ко нец обр абатываемого слова , ПКС 1 = 1 ) .В исходном состоянии блока 5 счетчик 58 и триггеры 4 9- 5 2 устанавлив аются в нулевое состояние , Обр абатываемое слово или слово-подстановкаможет поступать в блок через информационные входы на соответствующие входы восьми элементов ИЛИ 5 7 , Через 5 5первую группу информационных входов .из блока 4 поступает та часть о бр аб атываемого слова, в которой пр екра, щен поиск вхождения . Через третью группу информационных входов гос ту пав ют те символы обрабатываемого слова, которые прошли сравкецие в блоке 7 (ца предмет обнаружения вхождения) и совпадение це произошло, Через четвертую группу информационных входов поступает подстановка иэ блока 7, Счетчик 58 подсчитывает число поступающих в регистры блока 5 символов. После поступления в данкый блок всего слова в счетчике 58 будет подсчитана длина этого слова. С выходов сдвигающих регистров 48 слово может быть записано в блок 8 памяти слова и пере- записано в блок 4. По команде ЧТС:1 слово из блока 8 памяти слов записывается во все восемь сдвигающих регистров 48, причем в лервый сдвигающий регистр 48 - все первые биты слова, соответственно в восьмой сдвигающий регистр - восьмые, Вертикальный срезпо одноименным разрядам сдвигающих регистров-байт кодирует один символ слова, Триггеры 52, 51, элементы ИЛИ 55 и И 53 составляютсистему элементов, позволяющую пропускать сигналы сдвига на сдвигающие регистры 48 или сигнал РТИ: = 1, поступающий из блока 7. Триггер 49 используется для задания состояния блока 9 управления, определенного по результатам анализа признаков формулы, С выхода элемента ИЛИ 56 снимается зн;,ение признака (ПКС 2 = 1) того, что в сдвигающих регистрах 48 появился конец обрабатываемого слова (восемь нулей - вертикальный "срез" по первым разрядам регистров 48), С триггера 50 поступает значение признака переполнения (ППЕР), если длина слова превысила длину регистров,Формула изобретения1. Устройство для ре цизации подстановок слов, содержащее блок просмотра, блок памяти слов, блок управления, первый и второй блоки подстановки, причем вход запуска и вход начальной установки устройства подключены соответственно к первому и второму входам режима блока управления, первый выход которого подключен к выходу признака аварийного останова устройства, информационные выходы первой группы первого блока подстановки подключены соответственно к ин формационным входам первой группывторого блока подстановки, информационные входы второй группы которогоподключены соответственно к выходамблока памяти слов, выход признакаконца обрабатываемого слова блокапросмотра подключен к третьему входурЕжима блока управления, второй выходкоторого подключен ко входу чтенияблока памяти слов и к первому управляющему входу второго блока подстанОвки, с третьего по десятый выходыблока управления подключены соответствЕнно ко входу записи блока памятислов, ко входу режима первого блокаподстановки, ко входу признака приема.слова первого блока подстановки, кпервому входу режима, ко второму входу режима, ко входу признака перехода, к первому входу разрешения работы и ко второму входу разрешения работы второго блока подстановки, о тл и ч а ю щ е е с я тем, что, с целью увеличения быстродействия, оносодержит блок обнаружения вхождения,блок памяти вхождений, блок памятиподстановок и блок анализа переходов,причем первая, вторая и третья группыинформационных выходов второго блокаподстановки подключены соответственнок информационным входам первой и второй групп первого блока подстановкии к адресным входам блока памяти слов,вьход признака конца. слова второгоблока подстановки подключен к четвертому входу режима блока управления ико входу признака конца слова первогоблока подстановки, информационные выходы второй группы которого подключены соответственно к информационнымвходам первой группы блока. просмотра,информационные выходы первой, второйи третьей групп которого подключенысоответственно к информационным входам первой группы блока обнаружениявкождения, к информационным входамтретьей и четвертой групп второгоблока подстановки, выход признака перехода и выход признака переполнениякоторого подключены соответственно кпятому и шестому входам режима блокауправления, одиннадцатый, двенадцатыйи тринадцатый выходы которого подключены соответственно к первому, второму и третьему управляющем входам блока обнаружения вхождения, выход признака вхождения, выход управления первым блоком подстановки, выход управления блоком просмотра и выход управ 40 50 55 шестнадцатому входу режима блока управления, четырнадцатый выход которого подключен к тактовым входам первого и второго блоков подстановки, блока обнаружения вхождения и блока просмотра, пятнадцатый выход блока управления подключен ко второму управляющему входу блока просмотра и ко входу записи/чтения блока памяти вхождения, выходы первой и второйгрупп которого подключены соответственно к информационным входам третьей группы блока просмотра и к инФормационным входам блока анализа переходов, информационные выходы которого подключены к адресным входам блока памяти вхождения и блока памяти подстановок, выходы которого подключены соответственно к информационным входам четвертой группы блока ления блоком анализа переходов и инФормационные выходы группы которогоподключены соответственно к седьмомувходу режима блока управления, к управляющему входу первого блоха подстановки, к первому управляющему входу блока просмотра, к первому управляющему входу блока анализа переходови к информационным входам второйгруппы блока просмотра, выход призна -ка разрешения синхронизации, выходпризнака одной подстановки, выходпризнака активизирующей Формулы, вы ход признака цравоактивиэирующейсяформулы, выход признака всех подстановок в обрабатываемом слове, выходпризнака последней формулы, выходпризнака заключительной формулы, вы ход признака безусловного перехода,выход признака приема адресов, первыйи второй выходы управления блоком обнаружения вхождения блока просмотраподключены соответственно ко второму 25 управляющему входу второго блока подстановки, ко входам режима, с восьмого по четырнадцатый, блока управления, ко второму управляющему входублока анализа переходов, к четверто му и пятому управляющим входам блокаобнаружения вхождения, выход признакаосвобождения поля подстановки блокапросмотра подключен к третьему управляющему входу второго блока подстановки и к пятнадцатому входу режимаблока управления, выход признака отсутствия вхождения блока просмотраподключен к шестому управляющему входу блока обнаружения вхождения и к168 просмотра, шестнадцатый выход блока управления подключен ко входу записи/чтения блока памяти подстановок и к третьему управляющему входу блока просмотра, выходы, с семнадцатогопо двадцать третий, блока управления подключены соответственно к управляющим входам, с третьего по девятый, блока анализа переходов, выход признака наличия информации и выход признака результата сравнения адреса активизирующей формулы с адресом перехода которого подключены соответственно к семнадцатому и восемнадцатому входам режима блока управления.2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок анализа переходов содержит первый и второй регистры, первый и второй счетчики, первый и второй коммутаторы, триггер, элемент ИЛИ и элемент сравнения, причем первый управляющий вход блока анализа переходов подключен к управляющему входу первого коммутатора, выходы которого подключены соответственно к информационным входампервой группы второго коммутатора, выходы которого подключены соответственно к информационным входам первогосчетчика, информационные выходы которого подключены к информационным входам первой группы элемента сравнения,к информационным выходам блока анализа переходов и к информационным вхо 8253 18дам гторого счетчика, информанионньнвыходы которого подключены ко входамэлемента ИЛИ, к информационным входамвторой группы элемента сравнения и кинформационным входам второй группывторого коммутатора, управляющий входкоторого подключен к выходу триггера,второй управляющий вход блока анализа 10переходов подключен ко входам записи/считывания первого и второго регистров, выходь которых подключены соответственно к информационным входампервой и второй групп первого коммутатора первый и второй информационные входы группы блока анализа переходов подключены соответственно к информационным входам первого и второгорегистров, управляющие входы, с тре- О тьего по девятый, блока анализа переходов подключены соответственно кинформационному входу триггера, ксчетному входу второго счетчика, ксчетному входу первого счетчика, ковходу записи. второго счетчика, ковходу записи первого счетчика, ковходу установки в "ноль триггера, ковходу установки в ноль второгосчетчика, инверсный выход элемента 30ИЛИ и выход элемента сравнения подключены соответственно к выходу признака наличия информации и к выходупризнака результата сравнения адресаактивизируемой формулы с адресом перехода блока анализа переходов.