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

(51)5 6 06 1 15 ИСАНИЕ ИЗОБРЕТЕ структурная схеграф-схема алгования блока ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Курский политехнический институт (72) В.М. Довгаль, О,Ф, Корольков, Ф.А, Старков, Е.И. Леонов, Д.Н. Тютюнов и С,С, Шевелев(56) Авторское свидетельство СССР М 1187173, кл. 6 06 Е 15/04, 1985.Авторское свидетельство СССР М 1455345, кл, 6 06 Р 15/20, 1987.(54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ ПОДСТАНОВОК(57) Изобретение относится к техническим средствам информатики и вычислительной техники и предназначено для решения задач обработки символьной информации в соответствии с заданной системой формул подстановок. Цель изобретения - сокращение аппаратурных затрат и повышение быстродействия при обработке символьной информации - достигается тем, что в устройство, содержащее с первого по третий запоИзобретение относится к техническим средствам информатики и вычислительной техники и предназначено для решения задач обработки символьной информации в соответствии с заданной системой формул подстановок.Цель изобретения - сокращение аппаратурных затрат и повышение быстродействия при обработке символьной информации.На фиг. 1 изображенама устройства; на фиг. 2 -ритма функциониро минающие блоки, с первого по третий регистры, с первого по третий регистры-счетчики, с первого по третий элементы И; первый и второй элементы ИЛИ, элемент ИЛИ-НЕ, первый коммутатор, компаратор, дополнительно введены второй коммутатор, счетчик, четвертый регистр-счетчик, четвертый запоминающий блок, Устройство позволяет обрабатывать системы формул с оптимальной последовательностью включений их в работу с одновременной возможностью обрабатывать как алфавитные переменные, так и битовые ансамбли, а также иметь техническую сложность (число компараторов, разрядность регистров и счетчиков), не зависящую от длины правых и левых частей формул алгорифма в широком диапазоне изменения этих длин, Устройство работает с алфавитными переменными, дополнительными метками формул и ансамблями битов, что в совокупности приводит к сокращению затрат времени и длин обрабатывающих нормальных алгоритмов, 3 ил. мультипрограммного управления; на фиг, 3 - граф-схемы алгоритмов загрузки запоминающих блоков устройства и граф-схема алгоритма выдачи результата,Устройство для реализации подстановок (фиг. 1) содержит компаратор 1, первый запоминающий блок 2, первый регистр- счетчик 3, третий регистр 4, второй регистр- счетчик 5, второй запоминающий блок 6, элемент ИЛИ-НЕ 7, второй элемент И 8, первый элемент И 9, третий запоминающий блок 10, первый регистр 11, первый коммутатор 12, четвертый запоминающий блок 13, 17411471741147 Соста вител ь А. Со ш ки Тех е М,Мо гентал р А.Маковская Р д Р Корректор В,Гирн Ре Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 1 аказ 2086 Тираж ВНИИПИ Государственного коми 113035, МоскеПодписноеа по изобретениям и открытиям при ГКНТ ССЖ, Раушская наб 4/5третий регистр-счетчик 14, блок 15 микропрограммного управления, первый элемент ИЛИ 16, второй элемент ИЛИ 17, второй регистр 18, второй коммутатор 19, третий элемент И 20, счетчик 21, четвертый регистр-счетчик 22, выход 23 (с разрядами с 1-го по 28-й) поля местного управления блока 15, вход 24 (с разрядами с 1-го по 9-й) логических условий блока 15.Устройство работает следующим образом.Теория алгорифмов Маркова является аппаратом математики, ориентированным на способы преобразования слов с помощью формул подстановок. Обрабатываемые слова и формулы подстановок (подстановки) задаются в некотором фиксированном алфавите, исключение составляет служебный символ, используемый для разделения левой(образца) и правой части подстановки. Подстановки имеют два типа: заключительные и текущие, кроме того, необходим признак, указывающий последнюю подстановку в алгорифме Маркова.Работа всякой подстановки заключается в выполнении двух основных операций: распознавание вхождения образца в обрабатываемое слово; замена обнаруженного вхождения образца на правую часть подстановки. Текущая подстановка выполняет свою работу столько раз, сколько раз обнаруживается вхождение ее образца в обрабатываемое- слово, а заключительная подстановка срабатывает один раз.Конечный список подстановок называется алгорифмом Маркова тогда, когда определен следующий порядок их включения в работу: всякий раз, когда срабатывает текущая подстановка, переход осуществляется на первую в списке подстановку; всякий раз, когда срабатывает заключительная подстановка, алгорифм останавливает свою работу и выдает результат; всякий раз, когда любая подстановка не срабатывает, переход осуществляется на следующую в списке подстановку, а когда не срабатывает последняя в списке подстановка, тогда алгорифм заканчивает свою работу и выдает результат,При решении задач обработки символьной информации очень часть используются различные алгорифмы Маркова, в которых порядок включения подстановок определяется двумя метками переходов для передачи управления на уровне подстановки как в том случае, когда данная подстановка срабатывает, так и в противном случае.Изменение порядка включения в работу подстановок во многих практически важных задачах обработки символьной информа 5 10 15 20 25 30 35 40 45 50 55 ции существенно сокращает затраты времени, Минимизация времени работы алгорифма Маркова также достигается за счет введения в подстановки образцов, содержащих алфавитные переменные, с помощью которых можно эффективно обрабатывать цепочки символов и нуль-единичные конфигурации,В блок-схеме алгоритма работы устройства для реализации подстановок, приведенной на фиг, 2, позиции 23 - 61 являются шагами работы алгоритма Для описания алгоритма используются следующие идентификаторы: СБРОС - усгэновка исходных состояний устройства;1 УСК - команда запуска устройства; ПКП - признак конца правой части подстановки; ПКВ - признак конца образца; ПКС - признак конца обрабатываемого слова; а - признак специального символа в обрабатываемом слове; ПЕР - признак переполнения запоминающего блока 10; ЗКЛ - признак заключительной подстановки; ППФ - признак последней в списке подстановки; "=" - результат компарации символов; Пр 1 - команда приема информации на регистре 4; - 1 РС 1 - команда вычитания единицы из содержимого регистра-счетчика 3; + 1 РС 1 - команда прибавления единицы к содержимому регистра-счетчика 3; ЧТ 1 - команда чтения из запоминающего блока 2; У 1 - команда управления коммутатором 12; У 2 - команда управления коммутатором 19; ЧТЗ - команда чтения из запоминающего блока 10, ЗПЗ - команда записи в запоминающий блок 10; ЧТ 2 - команда чтенияиз запоминающего блока 6; ЗП 4 - команда записи в запоминающий блок 13; ЧТ 4 - команда чтения из запоминающего блока 13; Пр 4 - команда приема информации в регистр-счетчик 14; Пр 5 - команда приема информации в регистр 11; Пр 7 - команда приема информации в регистр 18; Пр 8 - команда приема информации в регистр-счетчик 22; УФ 1 - команда установки в нуль регистра 11 Ф 2 - команда установки в нуль счетчика 21 ф 3 - команда установки в нуль регистра-счетчика 14; УФ-команда установки в нуль регистра 18; + 1 РС 4 - команда прибавления единицы к содержимому регистра-счетчика 22; Пр 3 - команда приема информации в регистр-счетчик 5; + 1 СЧ 1 - команда прибавления единицы к содержимому счетчика 21; - 1 СЧ 1. - команда вычитания единицы из содержимого счетчика 21; ф СЧ - признак состояния счетчика 21; СТОП - команда внешней индикации конца работы устройства над заданным словом; Аварийный останов - команда внешней индикации аварийной остановки работы устройства; Т 1- вспомогательный признак типа подстановки; Т 2 - вспомогательный признак позиции последней в списке подстановки; РС 1 - обозначение регистра-счетчика 3; Р 1 - обозначение регистра 4; РС 4 - обозначение ре гистра-счетчика 22.К моменту начала работы устройства над заданным словом все его запоминающиеблоки 2,6,10 и 13 загружены информацией.Каждой подстановке соответствуют два 10 адресных поля для хранения образца и правой ее части в запоминающих блоках 2 и 6 соответственно.По первому адресу поля образца запоминающего блока 2 хранится второй адрес 15 (2 п бит) того поля, на который необходимо передать управление в случае несрабатывания данной подстановки, а также признак ППФ, указывающий своим единичным зна чением на то, что подстановка является последней в списке. Начиная с второго адреса поля образца хранятся его символы (и бит) и их маски(п бит), Все признаки; 3 КЛ, ПКВ и ППФ хранятся в 2 и+1-м разряде запоминающего 25 блока 2; длина кода адресов гп=2 п. Маски символов используются для блокировки несовпадения битов кодов символов, сравниваемых на компараторе 1, который работает в соответствии с булевым выражением: 30 "="=(Х 1 Х 11/Х 1 8 Х 1 ЧВ 1)Д Я(Хп 8 в ХпХпфХ ч пь), где Х, Хг, "., Х - биты кода символа образца, Х 1, Хг Х - биты кода символа обрабатываемого слова, т 1, в 2, .,гп - биты маски символа образца, и - длина двоичного кода символа.Все следующие по порядку адреса запоминающего блока 2 используются для хранения символов и их масок с пустым 2 п+1-мразрядом, кроме адреса последнего символа, где наряду с символом и его маской хранится признак ПКВ=1 в 2 п+1-м разряде. Следующий по порядку адрес поля образца используется для хранения адреса началаполя правой части данной подстановки в запоминающем блоке 6, в 2 п+1-м разряде запоминающего блока 2 по этому же адресу записывается значение признака типа подстановки ЗКЛ, В следующем по порядку и по последнему адресу поля образца записывается второй адрес того поля образца, которому нужно передать управление в случае срабатывания подстановки.По каждому адресу поля, отведенного для хранения правой части подстановки в запоминающем блоке 6, записаны ее символы по порядку (и бит каждый). По последнему адресу поля запоминающего блока 6 записывается служебный символ, код которого(п бит) содержит все единицы и исполь 354045 50 55 зуется в качестве признака конца правой части подстановки (П КП).В запоминающем блоке 10 хранится исходное обрабатываемое слово, По первому адресу содержится служебный "пустой" символ (и бит), по всем остальным адресам строго по порядку размещаются символы слова (каждый и бит). Последним символом является служебный код (и бит), состоящий из всех единиц и используемый в качестве признака конца слова (ПКС). В составе обрабатываемого слова может встретиться специальный символ(а ), который используется для косвенной адресации на следующий символ в слове,Запоминающий блок 13 используется для хранения адресов, следующих по порядку в структуре слова, а не по порядку адресов символов в запоминающем блоке 10. Запоминающие блоки 10 и 13 имеют общую для них адресацию с помощью регистра-счетчика 14, что позволяет поставить в соответствие каждому символу из запоминающего блока 10 адрес следующего за ним символа в структуре обрабатываемого слова. Однако исходное обрабатываемое слово записывается так, чтобы все его символы имели адреса своих последователей на единицу больше, чем их собственные адреса в линейной структуре адресов запоминающего блока 10 в его исходном состоянии, совпадающем с линейной структурой исходного слова,По сигналу СБРОС; =1 (фиг, 1 и 2) регистры-счетчики 5, 14 и 22, счетчик 21 и регистры 11 и 18 обнуляются, а регистр-счетчик 3 и регистр 4 принимают значение двоичной натуральной единицы (РС 1:=1; Р 1=1; СБРОС:=1; блок 25 алгоритма). По условию ПУСК = 1 регистру-счетчику 22 присваивается значение, равное увеличенной на единицу длине исходного обрабатываемого слова с учетом служебных символов, обозначающих начало и конец данного слова, следовательнона регистре-счетчике 22 будет записан адрес начала свободной части запоминающего блока 10 (РС 4:=А; Пр 8;=1; блок 27). Блоки 28 - 44 и 48 алгоритма (фиг, 2) реализуют операцию распознавания вхождения образца в обрабатываемое слово.Проверяется выход схемы И 8 (фиг. 1), единица на котором обозначает конец обрабатываемого слова и соответствует ПКС=1 (блок 28 алгоритма (фиг. 2. Условие ПКС=1 означает, что вхождение образца в обрабатываемое слово не обнаружено, поэтому из регистра 4 переписывается адрес символов образца данной подстановки в регистр- счетчик 3 с помощью команды Пр 2:=1 (блок10 15 20 25 30 35 40 45 50 55 29), Содержимое регистра-счетчика 3 умен ьшается на единицу (блок 30) командой - 1 РС 1:=1, в результате по командам Т 2;=ППФ Пр 1;=1 и ЧТ:=1 (блок 31) из запоминающего блока 2 на регистр 4 будет записан адрес очередного образца, к которому определен переход при несрабатывании подстановки в заданном алгорифме обработки слов, а также запоминается значение признака ППФ (Т 2;=ППФ, блок 31), который хранится в 2 п+1-м разряде вместе с адресом очередного образца. На следующем такте работы устройства адрес очередного образца переписывается в регистр-счетчик 3 из регистра 4 по команде Пр 2:=1 (блок 32); обнуляется; регистр- счетчик 14, регистр 11 и счетчик 21 сигналами У 3: =1,У)Ф 1;=1 и У 62=1 соответственно(блок 32), Если в результате проверки признака Т 2 он будет равен единице, что соответствует случаю, когда не сработала последняя подстановка алгорифма, то устройство останавливает свою работу (блок 61) и готово к выдаче на внешние устройства результата по каналу РЕЗ (фиг. 1), В том случае, когда Т 2=0, осуществляется обработка слова с помощью очередной подстановки, адрес первого символа образца которой содержитсяна регистре-счетчике 3, а адрес начала обрабатываемого слова соответствует нулевому состоянию регистра- счетчика 14. По условию ПКС=О и по командам ЧТ 1:=1 и ЧТ 2=1 (блоки 28 и 35) с запоминающих блоков 2 и 10 считываются первый символ с маской образца и символ обрабатываемого слова соответственно и осуществляется их сравнение на компараторе 1.Когда на выходе компаратора 1 формируется сигнал ("="=О), что указывает на несовпадение сравниваемых символов (блок 35), тогда выполняется проверка выхода ИЛИ-НЕ 7, единица на котором указывает на существование в обрабатываемом слове " а "(блок 36). Если в обрабатываемом слове обнаружен служебный символ "а ", то выполняется переход к следующему символу обрабатываемого слова, что достигается приемом на регистр-счетчик 14 адреса следующего за" а " символа в запоминающем блоке 10, для чего коммутатор 12 соединяет выход запоминающего блока 13 с входом регистра-счетчика 14 по команде У 1:=1(блок 40), а по командам ЧТ 4:=1 и Пр 4:=1(блок 40) информация считывается из запоминающего блока 13 и записывается в регистр-счетчик 14, При этом в запоминающем блоке 2 не изменяется адрес того символа образца,который сравнивался на предыдущем тактеработы устройства.Если на выходе компаратора 1 полученсигнал ("="=0), а символ обрабатываемогослова не является служебным символом "а ", что соответствует сигналу ( а =0) навыходе схемы ИЛИ-НЕ 7, то тогда проверяется выход схемы ИЛИ 16 (блок 37), нуль накотором фСЧ=О) указывает на то, что счетчик21 находится в нулевом состоянии. Счетчик21 фиксирует количество совпавших символов образца с символами обрабатываемогослова, что позволяет определить тот фрагмент обрабатываемого слова и, соответственно, запоминающего блока 10, которыйможно использовать в качестве ресурса длязаписи правой части подстановки из запоминающего блока 6,Когда на выходе схемы ИЛИ 16 признакСЧ=О ( блок 37), что свидетельстует о том,что определено насовпадение первого символа образца с текущим символом обрабатываемого слова, тогда из запоминающегоблока 13 на регистр-счетчик 14 записывается адрес очередного символа обрабатываемого слова с помощью команд У 1;1, ЧТ 4:=1и Пр 4;=1 (блок 39), а также командой УФ 1;=1(блок 39) обнуляется регистр 11, на которомхранится адрес в запоминающем блоке 10начала того фрагмента обрабатываемогослова, который совпадает с образцом, Информация в регистр 11 записывается из регистра-счетчика 14 всякий раз, когдатекущий символ обрабатываемого слова неявляется служебным символом а и совпадает с текущим символом образца.Если признакСЧ=1 (блок 37), что означает несовпадение очередного символа обрабатываемого слова с символом образца,но все предыдущие символы которого совпали с предыдущими символами обрабатываемого слова, то с помощью команд У2:=1, Пр 2:1 (блок 38) осуществляется обнуление счетчика 21 через схему ИЛИ 17, атакже прием на регистр-счетчик 3 адресаначала образца в запоминающем блоке 2 изрегистра 4, на котором предварительно запоминается данный адрес всякий раз, когдав работу включается очередная подстановка, После выполнения действий в соответствии с блоками 38, 39 и 40 переходосуществляется на блок 28 алгоритма (фиг.2),Работа устройства в том случае, когдасимволы образца и обрабатываемого словасовпадают (сигнал "=1, блок 35), заключается в следующем. Проверяется выход схемы ИЛИ 16. ЕслиСЧ=О (блок 41), то это5 10 ружено совпадение с первым символом образца, поэтому адрес запоминающего блока 10 потенциально возможного начала вхождения образца в обрабатываемое слово запоминается на регистре 11 с помощью команды ПР 5:=1 (блок 42). По условию фСЧ=1 (блок 41), а также после выполнения блока 42 содержимое счетчика 21 с помощью команды+1 СЧ 1:=1 (блок 43) увеличивается на единицу.Если на выходе запоминающего блока 2 обнаруживается признак ПКВ=О (блок 44), означающий, что текущий символ образца не является его последним символом, то подготавливаются для считывания очередные символы из запоминающих блоков 2 и 10, для чего на регистры-счетчики 3 и 14 записываются следующие адреса: состояние регистра-счетчика 3 увеличивается на единицу командой +1 РС 1:=1 (блок 48), а через коммутатор 12 по команде У 1;=1 (блок 48) из запоминающего блока 13 адрес очередного символа обрабатываемого слова запишется на регистр-счетчик 14 с помощью команд ЧТ 4:=1 и Пр 4:=1 (блок 48). После чего работа устройства по обнаружению вхождения образца в обрабатываемое слово продолжается начиная с блока 28 алгоритма (фиг. 2).Если на выходе запоминающего блока 2 в его 2 п+1-м информационном разряде появляется признак ПКВ=1 (блок 44), то это однозначно определяет положительный результат вхождения образца в обрабатываемое слово.Блоки алгоритма 45, 46, 47 и 49 - 61 (фиг.2) позволяют реализовать изменение обрабатываемого слова в соответствии с заданной подстановкой и выполнить подготовку устройства к очередному действию по схеме заданного размеченного алгорифма Маркова,В соответствии с командами блока 45; +1 РС 1: = 1; ЧТ 4=1; Пр 7=1 увеличивается на единицу состояние регистра-счетчика 3, что позволяет подготовить к считыванию из запоминающего блока 2 адрес начала правой части подстановки в запоминающем блоке 6 и значения признака заключительной подстановки ЗКЛ, а на регистр 18 - адрес следующего символа, расположенного непосредственно за последним символом обнаруженного в обрабатываемом слове вхождения образца.Команды; ЧТ 1: =1; Пр 3: =1, Т 1:=ЗКЛ; У 1:=0; ПР 4: =1 - позволяют считать из запоминающего блока 2 адрес начала правой части подстановки и записать его в регистр- счетчик 5, а также присвоить вспомогательному признаку Т 1 значение признака 15 20 25 30 35 40 45 50 55 заключительной подстановки ЗКЛ и, кроме того, через коммутатор 12 на регистр - вхождения образца в обрабатываемом слове запоминающего блока 10,.На следующем такте работы устройства содержимое регистра-счетчика 3 увеличивается на единицу и по этому адресу читается адрес первого символа образца очередной подстановки, Данный адрес запоминается на регистре 4 с помощью команд 1 РС 1:=1,ЧТ 1: =1 и Пр 1:=1 (блок 47) соответственно, кроме того, на этом же такте работы устройства выполняется перезапись первого символа правой части подстановки из запоминающего блока 6 в запоминающий блок 10 в соответствии с адресами, хранящимися на регистрах-счетчиках 5 и 14, с помощью команд ЧТ 2: =1, ЗПЗ: =1 (блок 47), а также уменьшается на единицу состояние счетчика 21 ( - 1 СЧ 1: =1, блок 47), поскольку в результате записи символа израсходован один адрес свободного для записи ресурса запоминающего блока 10.В соответствии с условиями и командами блоков 50 - 52 и 53, 55 - 60 алгоритма работы устройства осуществляется перезапись правой части подстановки из запоминающего блока 6 в запоминающий блок 10. При этом используется свободный ресурс запоминающего блока 10, состоящий из адресов, которые заняты символами позиции вхождения образца в обрабатываемом слове при условии СЧ=1 (блок 50), и адресов, начинающихся со значения адреса свободного ресурса, хранимого в регистре- счетчике 22 при условии фСЧ=О (блок 50),Если на выходе схемы ИЛИ 16 - единица ф СЧ=1, блок 50), то на регистре-счетчике 5 выставляется адрес очередного символа из запоминающего блока 6 командой 1 РС 2: =1 (блок 49), из запоминающего блока 13 считывается очередной адрес его свободного ресурса в регистр-счетчик 14, для чего выполняется команда ЧТ 4: =1 (блок 49) соединяет выход запоминающего блока 13 с входом регистра-счетчика 14, в которой записывается адрес для приема очередного символа в запоминающий блок 10 командой ПР 4: =1 (блок 49), а также вычитается единица из счетчика 21 командой -1 СЧ 1: =1 (блок 49). Следующий шаг работы устройства служит для перезаписи символа по командам ЧТ 2; =1 и ЗПЗ: =1 (блок 51) из запоминающего блока 6 в запоминающий блок 10. Данный цикл работы устройства продолжается до тех пор, пока на выходе схемы И 9 не будет обнаружена единица (ПКП=1, блок 52), что означает конец правой части подстановки, или до тех пор, пока не будет обнаружен нуль на выходе схемы ИЛИ16 (, СЧ=О, блок 50), что означает использование всего ресурса запоминающего блока10, образованного позицией вхождения образца.По условию СЧ=О (блок 50) и по условию ПКП=О (блок 53) выполняется запись взапоминающий блок 14 через коммутатор19 (ЗП 4:= 1, У 2: =1, блок 55) содержимогорегистра-счетчика 22, в котором хранитсяадрес начала исходного свободного ресурса 10запоминающего блока 10, по которому запишется очередной символ из запоминающего блока 6,В соответствии с блоком 57 алгоритмаработы устройства осуществляется изменение значений адресов на регистрах-счетчиках 5 и 22 с помощью команд +1 РС 2; =1 и+1 РС 4: =1 соответственно, а также изменяется значение адреса в регистре-счетчике14 через коммутатор 12 из запоминающего 20блока 13 командами ЧТ 4; =1, У 1=1 и Пр 4;=1,По выставленным адресам на регистресчетчике 5 и на регистре-счетчике 14 командами ЧТ 2;=1 и ЗПЗ;=1 (блок 59) очереднойсимвол перезаписывается из запоминающего блока 6 в запоминающий блок 10. Циклработы устройства по условию СЧ=О (блок50) и ПКП=О (блок 53) выполняется до техпор, пока не будет обнаружено переполнение запоминающего блока 10 (единичное 30состояние регистра-счетчика 22), о чем сигнализирует единица на выходе схемы И 20(ПЕР=1, блок 60), или до тех пор, пока небудетобнаружена единица на выходесхемыИ 9, сигнализирующая о конце правой части 35подстановки, а следовательно, конце записи в запоминающий блок 10.После перезаписи правой части подстановки ее последний символ, записанный взапоминающий блок 10, "разрывает" абрабатываемое слово, поэтому необходимо определить адрес следующего за нимсимвола. Данный адрес хранится на регистре 18 и переписывается в запоминающийблок 13 из регистра 18 с помощью команд 45У 2: =0,3 П 4: =1 (блок 54) через коммутатор 19.Кроме того, на этом шаге выполняется обнуление счетчика 21 командой ПКП:=1 (блок54) и осуществляется подготовка работы устройства в соответствии с очередной подстановкой, для чего адрес начала ее образцапереписывается из регистра 4 на регистрсчетчик 3 с помощью команды Пр 2:=1 (блок54).Если обнаружится признак ЗКЛ=1, что 55соответствует значению Т 1=1 (блок 56) и указывает тип заключительной подстановки, торабота устройства останавливается, и оноготово для выдачи результата на внешние устройства по каналу РЕЗ (фи. 1), В противном случае (Т 1=0) устройство подготавливается к обработке слова с помощью очередной подстановки, для чего обнуляются регистр 11, регистр-счетчик 14 и регистр 18 командами У 01:=1, УЛ:=1 и У 4:=1 соответственно (блок 58). После этого вновь выполняется переход на блок 28 алгоритма (фиг.2),В случае переполнения запоминающего блока 10 осуществляется аварийная остановка работы устройства (блок 62),После остановки работы устройства (блок 61) алгоритма (фиг,2) в запоминающем блоке 10 содержится результат, который по внешнему информационному выходу РЕЗ (фиг. 1) выдается в соответствии с алгоритмом (фиг. За), для чего регистр-счетчик 14 сбрасывается в нуль командой У"3:=1 и командой У 1=1 (блок 63), коммутатор 12 соединяет информационный выход запоминающего блока 13 с информационным входом регистра-счетчика 14. После этого выполняется цикл (блоки 65, 66), состоящий из чтения адреса следующего символа в запоминающем блоке 13 командой ЧТ 4;=1, прием адреса в регистр-счетчик 14 командой Пр 4 т 1 и чтение по этому адресу символа результата из запоминающего блока командой ЧТЗ;=1. Цикл передачи символов результата продолжается до тех пор, пока не будет обнаружен признак конца слова ПКС=1 (блок 64),Запись информации в запоминающий блок 2 выполняется по алгоритму (фиг. Зб), Вначале выполняется команда СБРОС:=1, что приводит к установке регистра-счетчика 3 в нулевое состояние (блок 68). Затем выполняется цикл записи информации с внешнего входа устройства ВВ 1 ( фиг.1) командами записи ЗП 1;=1 и изменение адреса+1 РС 1:=1 (блоки 69, 70) до тех пор, пока на внешнем входе ВВ 1 не появится признак последней подстановки ППФ=1 (блок 70), Информация, соответствующая последней .подстановке, записывается в цикле в запоминающий блок 2 (блоки 74, 72) до тех пор, пока не будет обнаружено отсутствие признака конца образца ППВ=О (блок 73), поскольку последней записывается специальная подстановка, имеющая пустой образец с признаком ПКВ=1 и ЗКЛ=1.Запись информации в запоминающие блоки 10 и 13 выполняется синхронно по алгоритму (фиг, Зв) после загрузки запоминающего блока 2. Регистр-счетчик 5 находится в нулевом состоянии, и по этому адресу в запоминающий блок 6 записывается с внешнего входа устройства ВВ 2 (фиг. 1) символ, состоящий из всех единиц, командой ЗП 2:=1 (блок 76), Выполнить это необхо5 10 15 20 25 30 40 50 55 димо для того, чтобы внешний вход устройства ВВЗ мог быть подключен по схеме с открытым коллектором по принципу МОНТАЖНОЕ ИЛИ. Регистр-счетчик 14 устанавливается в нулевое состояние командой Уб 3;=1 (блок 77), коммутатор 19 командой У 2:=1 (блок 77) соединит выход регистра- счетчика 22 с входом запоминающего блока 13. Регистр-счетчик 22 устанавливается в состояние, равное двоичной натуральной единице, командой РС 4;=1. Затем выполняется цикл записи символов обработанного слова один за другим по адресам линейного упорядочения в запоминающем блоке 10 с помощью команд +1 РСЗ:=1 и +1 РС 4 т 1 и команд записи ЗПЗ:=1 и ЗП 4:=1 (блоки 80 и 79), что позволит разместить в запоминающем блоке 10 символы слова так, чтобы следующий символ в слове имел следующий адрес в запоминающем блоке 10. Цикл повторяется до тех пор, пока на внешнем канале ВВЗ (фиг. 1) не будет обнаружен признак конца слова ПКС=1, признак записывается (блок 82) в запоминающий блок 10 по адресу, записанному в регистр-счетчик 14 командой +1 РСЗ:=1 (блок 81), а регистр- счетчик 22 принимает нулевое состояние командой Пр 8 т 1 из обнуленного регистра блока 15 микропрограммного управления.Запись информации в запоминающий блок 6 осуществляется символ за символом в цикле (фиг. Зг) до тех пор, пока не будет обнаружен пустой символ на внешнем входе ВВ 2 (фиг, 1), для чего выполняются команды записи ЗП 2:=1 (блок 84) и изменение адреса запоминающего блока б в регистре- счетчике 5 командой 1 РС 2:=1 (блок 85), Выход из цикла организован по условию ВВ 2= а ф После записи информации в запоминающие блоки 2, 10, 13 и б в регистр блока 15 микропрограммного управления по внешнему входу ВВ 4 (фиг, 1) записывается двоичное число, определяющее длину обрабатываемого слова с учетом двух служебных символов, обозначающих начало и конец записи в запоминающем блоке 10.Формула изобретенияУстройство для реализации подстановок, содержащее блок микропрограммного управления, с первого по третий запоминающие блоки, с первого по третий регистры, с первого по третий регистры-счетчики, с первого по третий элементы И, первый.и второй элементы ИЛИ, элемент ИЛИ-НЕ, первый коммутатор, компаратор, причем информационный выход первого запоминающего блока соединен с первым информационным входом компаратора, выход равенства которого соединен с первым разрядом входа логических условий блока микропрограммного управления, выходы первого и второго разрядов поля местного управления которого соединены с входами чтения и записи первого запоминающего блока, первый, второй и третий информационные выходы которого соединены с вторым, третьим и четвертым разрядами входа логических условий блока микропрограммного управления, выходы с третьего по пятый разрядов поля местного управления которого соединены соответственно с входом записи, вычитающим и суммирующим входами первого регистра-счетчика, информационный выход которого соединен с первым информационным входом первого запоминающего блока, второй информационный вход которого соединен с первым информационным входом устройства, второй информационный вход устройства соединен с первым информационным входом второго запоминающего блока, выход которого соединен с входами первого элемента И, выход которого соединен с пятым разрядом входа логических условий блока микропрограммного управления, выход шестого разряда поля местного управления которого соединен с входом записи третьего регистра, второй информационный вход второго запоминающего блока соединен с информационным выходом второго регистра-счетчика, вход записи и суммирующий вход которого соединен соответственно с седьмым и восьмым разрядами поля местного управления блока микропрограммного управления, девятый и десятый разряды поля местного управления которого соединены с входами чтения и записи второго запоминающего блока, выходы одиннадцатого и двенадцатого разрядов поля местного управления блока микропрограммного управления соединены с входами записи и установки в "0" первого регистра, информационный выход третьего запоминающего блока соединен с вторым информационным входом компаратора, с информационным выходом устройства, с входами второго элемента И, выход которого соединен с шестым рязрядом входа логических условий блока микропрограммного управления, выход тринадцатого разряда поля местного управления которого соединен с управляющим входом первого коммутатора, выходы четырнадцатого и пятнадцатого разрядов поля местного управления блока микропрограммного управления соединены соответственно с входами чтения и записи третьего запоминающего блока, информационный выход третьего регистра-счетчика соединен с вторым информационным вхо15 1741147 55 дом третьего запоминающего блока, с третьим информационным входом устройства, четвертый информационный вход устройства соединен с входом кода операции блока микропрограммного управления, выходы с шестнадцатого по восемнадцатый разрядов поля местного управления которого соединены соответственно с входами установки в "0", записи и суммирующим входом третьего регистра-счетчика, первый и второй входы пуска и вход сброса устройства соединены соответственно с первым и вторым входами пуска и входом сброса блока микропрограммного управления, первый и второй выходы поля внешнего управления которого соединены с выходами "Стоп", и "Аварийный останов" устройства, о т л и ч аю щ е е с я тем, что, с целью сокращения аппаратурных затрат и повышения быстродействия при обработке символьной информации, в него дополнительно введены второй коммутатор, счетчик, четвертый регистр-счетчик, четвертый запоминающий блок, причем выходы девятнадцатого и двадцатого разрядов поля местного управления блока микропрограммного управления соединены с входами чтения и записи четвертого запоминающего блока, информационный выходтретьего запоминающего блока соединен с входами элемента ИЛИНЕ, выход которого соединен с седьмым разрядом входа логических условий блока микропрограммного управления, выходы двадцать первого и двадцать второго разрядов поля местного управления которого соединены соответственно с суммирующим и вычитающими входами счетчика, информационный выход которого соединен с входом первого регистра и с первым информационным входом четвертого запоминающего блока, информационный выход которого соединен с первым информационным входом первого коммутатора, выход которого соединен с информационным входом третьего регистра-счетчика, информационный выход которого соединен с вторым информационным входом первого коммутатора, выход двадцать третьего разряда поля местного управления блока микропрограммного управления соединен с первым входом второ 5 10 15 20 25 ЗО 35 40 45 50 го элемента ИЛИ, информационный выход четвертого запоминающего блока соединен с информационным входом второго регистра, информационный выход которого соединен с первым информационным входом второго коммутатора, информационный выход которого соединен с вторым информационным входом четвертого запоминающего блока, второй информационный вход коммутатора соединен с информационным выходом четвертого регистра-счетчика, выходы двадцать четвертого и двадцать пятого разрядов поля местного управления блока микропрограммного управления соединены соответственно с. входами установки в "0" и с входом записи второго регистра, управляющий вход второго компаратора соединен с двадцать шестым входом разряда поля местного управления блока микропрограммного управления, информационный выход четвертого регистра-счетчика соединен с входами третьего элемента И, выход которого соединен с восьмым рязрядом входа логических условий блока микропрограммного управления, выход поля констант которого соединен с информационным входом четвертого регистра-счетчика, суммирующий вход и вход записи которого соединены соответственно с выходами двадцать седьмого и двадцать восьмого разрядов поля местного управления блока микропрограммного управления, информационный выход счетчика соединен с входами первого элемента ИЛИ, выход которого соединен с девятым разрядом входа логических условий блока микропрограммного управления, выход второго элемента ИЛИ соединен с входом установки в "0" счетчика, второй вход второго элемента ИЛИ соединен с выходом первого элемента И, четвертый информационный выход первого запоминающего блока соединен с информационным входом второго регистра- счетчика и с информационным входом третьего регистра, информационный выход которого соединен с информационным входом первого регистра-счетчика, информационный выход второго запоминающего блока соединен с вторым информационным входом третьего запоминающего блока.