Устройство для реализации подстановок Советский патент 1992 года по МПК G06F15/20 

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

Цель изобретения - сокращение аппаратурных затрат и повышение быстродействия при обработке символьной информации.

На фиг. 1 изображена структурная схема устройства; на фиг. 2 - граф-схема алгоритма функционирования блока

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

Устройство для реализации подстановок (фиг. 1) содержит компаратор 1, первый запоминающий блок 2, первый регистр- счетчик 3, третий регистр 4, второй регистр- счетчик 5, второй запоминающий блок 6, элемент ИЛИ-НЕ 7, второй элемент И 8, первый элемент И 9, третий запоминающий блок 10, первый регистр 11, первый коммутатор 12, четвертый запоминающий блок 13,

Јь vj

третий регистр-счетчик 14, блок 15 микропрограммного управления, первый элемент ИЛИ 16, второй элемент ИЛИ 17, второй регистр 18, второй коммутатор 19, третий элемент И 20, счетчик 21, четвертый регистр-счетчик 22, выход 23 (с разрядами с 1-го по 28-й) поля местного управления блока 15, вход 24 (с разрядами с 1-го по 9-й) логических условий блока 15.

Устройство работает следующим образом.

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

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

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

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

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

В блок-схеме алгоритма работы устрой0 ства для реализации подстановок, приведенной на фиг. 2, позиции 23-61 являются шагами работы алгоритма Для описания алгоритма используются следующие идентификаторы: СБРОС - успновка исходных

5 состояний устройства; НУСК - команда запуска устройства; ПКП - признак конца правой части подстановки; ПКВ - признак конца образца; ПКС - признак конца обрабатываемого слова; а - признак специаль0 ного символа в обрабатываемом слове; ПЕР

-признак переполнения запоминающего блока 10; ЗКЛ - признак заключительной подстановки; ППФ - признак последней в списке подстановки; - результат компа5 рации символов; Пр 1 - команда приема информации на регистре 4; - 1РС1 - команда вычитания единицы из содержимого регистра-счетчика 3; + 1РС1 - команда прибавления единицы к содержимому реги0 стра-счетчика 3; ЧТ1 - команда чтения из запоминающего блока 2; У1 - команда управления коммутатором 12; У2 - команда управления коммутатором 19; ЧТЗ - команда чтения из запоминающего блока 10; ЗПЗ

5 - команда записи в запоминающий блок 10; ЧТ2 - команда чтения из запоминающего блока 6; ЗП4 - команда записи в запоминающий блок 13; ЧТ4 - команда чтения из запоминающего блока 13; Пр 4 - команда

0 приема информации в регистр-счетчик 14; Пр 5 - команда приема информации в регистр 11; Пр 7 - команда приема информации в регистр 18; Пр 8 - команда приема информации в регистр-счетчик 22; У 1 5 команда установки в нуль регистра -команда установки в нуль счетчика 21 .у/ З

-команда установки в нуль регистра-счетчика 14; y#f -команда установки в нуль регистра 18; + 1РС4 - команда прибавления

0 единицы к содержимому регистра-счетчика 22; Пр 3 - команда приема информации в регистр-счетчик 5; + 1СЧ1 - команда прибавления единицы к содержимому счетчика 21; -1СЧ1 - команда вычитания единицы из

5 содержимого счетчика 21; $f СЧ - признак состояния счетчика 21; СТОП - команда внешней индикации конца работы устройства над заданным словом; Аварийный останов - команда внешней индикации

аварийной остановки работы устройства; Т1

- вспомогательный признак типа подстановки; Т2 - вспомогательный признак позиции последней в списке подстановки; РС1 - обозначение регистра-счетчика 3; Р1 -обозначение регистра 4; РС4 - обозначение ре- гистра-счетчика 22.

К моменту начала работы устройства над заданным словом все его запоминающие блоки 2,6,10 и 13 загружены информацией.

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

По первому адресу поля образца запоминающего блока 2 хранится второй адрес (2п бит) того поля, на который необходимо передать управление в случае несрабатывания данной подстановки, а также признак ППФ, указывающий своим единичным зна- чением на то, что подстановка является последней в списке. Начиная с второго адреса поля образца хранятся его символы (п бит) и ихмаски(п бит). Все признаки: ЗКЛ, ПКВ и ППФ хранятся в 2 п +1-м разряде запоминающего блока 2; длина кода адресов . Маски символов используются для блокировки несовпадения битов кодов символов, сравниваемых на компараторе 1, который работает в соответствии с булевым выражением: (Xi &Xi vXi & Xi vm )Ј...Ј (Хп & Xn V XnS & Xn v mn), где XL Х2..., Хп - биты кода символа образца, Xi, X2 ..., Xn - биты кода символа обрабатываемого слова, mi, ma,..., nrin - биты маски символа образца, п - длина двоичного кода символа.

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

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

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

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

По сигналу СБРОС: 1 (фиг. 1 и 2) регистры-счетчики 5, 14 и 22, счетчик 21 и регистры 11 и 18 обнуляются, а регистр-счетчик 3 и регистр 4 принимают значение двоичной натуральной единицы ( Р1 1; СБРОС: 1; блок 25 алгоритма). По условию ПУСК 1 регистру-счетчику 22 присваивается значение, равное увеличенной на единицу длине исходного обрабатываемого слова с учетом служебных символов, обозначающих начало и конец данного слова, следова- тельно, на регистре-счетчике 22 будет записан адрес начала свободной части запоминающего блока 10 ( Пр блок 27). Блоки 28-44 и 48 алгоритма (фиг. 2) реализуют операцию распознавания вхождения образца в обрабатываемое слово.

Проверяется выход схемы И 8 (фиг. 1), единица на котором обозначает конец обрабатываемого слова и соответствует (блок 28 алгоритма (фиг. 2)). Условие означает, что вхождение образца в обрабатываемое слово не обнаружено, поэтому из регистра 4 переписывается адрес символов образца данной подстановки в регистр- учетчик 3 с помощью команды Пр (блок

29). Содержимое регистра-счетчика 3 уменьшается на единицу (блок 30) командой - 1РС1: 1, в результате по командам Пр 1 и ЧТ:-1 (блок 31) из запоминающего блока 2 на регистр 4 будет записан адрес очередного образца, к которому определен переход при несрабатывании подстановки в заданном алгорифме обработки слов, а также запоминается значение признака ППФ (, блок 31), который хранится в 2л+1-м разряде вместе с адресом очередного образца.

На следующем такте работы устройства адрес очередного образца переписывается в регистр-счетчик 3 из регистра 4 по команде Пр (блок 32); обнуляется: регистр- счетчик 14, регистр 11 и счетчик 21 сигналами 1, и соответственно (блок 32). Если в результате проверки признака Т2 он будет равен единице, что соответствует случаю, когда не сработала последняя подстановка алгорифма, то устройство останавливает свою работу (блок 61) и готово к выдаче на внешние устройства результата по каналу РЕЗ (фиг. 1). В том случае, когда , осуществляется обработка слова с помощью очередной подстановки, адрес первого символа образца которой содержится на регистре-счетчике 3, а адрес начала обрабатываемого слова соответствует нулевому состоянию регистра- счетчика 14.

По условию и по командам и (блоки 28 и 35) с запоминающих блоков 2 и 10 считываются первый символ с маской образца и символ обрабатываемого слова соответственно и осуществляется их сравнение на компараторе 1.

Когда на выходе компаратора 1 формируется сигнал (0), что указывает на несовпадение сравниваемых символов (блок 35), тогда выполняется проверка выхода ИЛИ-НЕ 7, единица на котором указывает на существование в обрабатываемом слове а (блок 36). Если в обрабатываемом слове обнаружен служебный символ а , то выполняется переход к следующему символу обрабатываемого слова, что достигается приемом на регистр-счетчик 14 адреса следующего за а символа в запоминающем блоке 10, для чего коммутатор 12 соединяет выход запоминающего блока 13 с входом регистра-счетчика 14 по команде У1 (блок 40), а по командам и Пр (блок 40) информация считывается из запоминающего блока 13 и записывается в регистр-счетчик 14. При этом в запоминающем блоке 2 не изменяется адрес того символа образца,

который сравнивался на предыдущем такте работы устройства.

Если на выходе компаратора 1 получен сигнал (0), а символ обрабатываемого

слова не является служебным символом а , что соответствует сигналу ( а 0) на выходе схемы ИЛИ-НЕ 7, то тогда проверяется выход схемы ИЛИ 16 (блок 37), нуль на котором () указывает на то, что счетчик

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

Когда на выходе схемы ИЛИ 16 признак

( блок 37), что свидетельстует о том, что определено насовпадение первого символа образца с текущим символом обрабатываемого слова, тогда из запоминающего блока 13 на регистр-счетчик 14 записывается адрес очередного символа обрабатываемого слова с помощью команд У1:1, и (блок 39), а также командой (блок 39) обнуляется регистр 11, на котором хранится адрес в запоминающем блоке 10

начала того фрагмента обрабатываемого слова, который совпадает с образцом. Информация в регистр 11 записывается из регистра-счетчика 14 всякий раз, когда текущий символ обрабатываемого слова не

является служебным символом а и совпадает с текущим символом образца.

Если признак СЧ 1 (блок 37), что означает несовпадение очередного символа обрабатываемого слова с символом образца,

но все предыдущие символы которого совпали с предыдущими символами обрабатываемого слова, то с помощью команд У0 , Пр 2:1 (блок 38) осуществляется обнуление счетчика 21 через схему ИЛИ 17, а

также прием на регистр-счетчик 3 адреса начала образца в запоминающем блоке 2 из регистра 4, на котором предварительно запоминается данный адрес всякий раз, когда в работу включается очередная подстановка. После выполнения действий в соответствии с блоками 38, 39 и 40 переход осуществляется на блок 28 алгоритма (фиг. 2).

Работа устройства в том случае, когда

символы образца и обрабатываемого слова совпадают (сигнал 1, блок 35), заключается в следующем. Проверяется выход схемы ИЛИ 16. (блок 41), то это .означает, что в обрабатываемом слове обнаружено совпадение с первым символом образца, поэтому адрес запоминающего блока 10 потенциально возможного начала вхождения образца в обрабатываемое слово запоминается на регистре 11 с помощью команды ПР (блок 42). По условию (блок 41), а также после выполнения блока 42 содержимое счетчика 21 с помощью команды +1СЧ1 (блок 43) увеличивается на единицу.

Если на выходе запоминающего блока 2 обнаруживается признак (блок 44), означающий, что текущий символ образца не является его последним символом, то подготавливаются для считывания очередные символы из запоминающих блоков 2 и 10, для чего на регистры-счетчики 3 и 14 записываются следующие адреса: состояние регистра-счетчика 3 увеличивается на единицу командой +1РС1: 1 (блок 48), а через коммутатор 12 по команде (блок 48) из запоминающего блока 13 адрес очередного символа обрабатываемого слова запишется на регистр-счетчик 14 с помощью команд и Пр (блок 48). После чего работа устройства по обнаружению вхождения образца в обрабатываемое слово продолжается начиная с блока 28 алгоритма (фиг. 2).

Если на выходе запоминающего блока 2 в его 2п+1-м информационном разряде появляется признак (блок 44), то это однозначно определяет положительный результат вхождения образца в обрабатываемое слово.

Блоки алгоритма 45, 46, 47 и 49-61 (фиг. 2) позволяют реализовать изменение обрабатываемого слова в соответствии с заданной подстановкой и выполнить подготовку устройства к очередному действию по схеме заданного размеченного алгорифма Маркова.

В соответствии с командами блока 45: +1РС1: 1; увеличивается на единицу состояние регистра-счетчика 3, что позволяет подготовить к считыванию из запоминающего блока 2 адрес начала правой части подстановки в запоминающем блоке 6 и значения признака заключительной подстановки ЗКЛ, а на регистр 18 - адрес следующего символа, расположенного непосредственно за последним символом обнаруженного в обрабатываемом слове вхождения образца.

Команды: ЧТ1: 1; Пр 3: 1, У1 ПР 4: 1 - позволяют считать из запоминающего блока 2 адрес начала правой части подстановки и записать его в регистр- счетчик 5, а также присвоить вспомогательному признаку Т1 значение признака

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

На следующем такте работы устройства

содержимое регистра-счетчика 3 увеличивается на единицу и по этому адресу читается адрес первого символа образца очередной подстановки. Данный адрес запоминается

0 на регистре 4 с помощью команд 1РС1: 1,ЧТ1: 1 и Пр (блок 47) соответственно, кроме того, на этом же такте работы устройства выполняется перезапись первого символа правой части подстановки из

5 запоминающего блока 6 в запоминающий блок 10 в соответствии с адресами, хранящимися на регистрах-счетчиках 5 и 14, с помощью команд ЧТ2: 1, ЗПЗ: 1 (блок 47), а также уменьшается на единицу состояние

0 счетчика 21 (-1СЧ1: 1, блок 47), поскольку в результате записи символа израсходован один адрес свободного для записи ресурса запоминающего блока 10.

В соответствии с условиями и команда5 ми блоков 50-52 и 53, 55-60 алгоритма работы устройства осуществляется перезапись правой части подстановки из запоминающего блока 6 в запоминающий блок 10. При этом используется свободный

0 ресурс запоминающего блока 10, состоящий из адресов, которые заняты символами позиции вхождения образца в обрабатываемом слове при условии (блок 50), и адресов, начинающихся со значения адреса

5 свободного ресурса, хранимого в регистре- счетчике 22 при условии (блок 50).

Если на выходе схемы ИЛИ 16 - единица (6 , блок 50), то на регистре-счетчике 5 выставляется адрес очередного символа

0 из запоминающего блока 6 командой 1РС2: 1 (блок 49), из запоминающего блока 13 считывается очередной адрес его свободного ресурса в регистр-счетчик 14, для чего выполняется команда ЧТ4: 1 (блок 49) сое5 диняет выход запоминающего блока 13 с входом регистра-счетчика 14, в которой записывается адрес для приема очередного символа в запоминающий блок 10 командой ПР 4: 1 (блок 49), а также вычитается еди0 ница из счетчика 21 командой -1СЧ1: 1 (блок 49). Следующий шаг работы устройства служит для перезаписи символа по командам ЧТ2: 1 и ЗПЗ: 1 (блок 51) из запоминающего блока 6 в запоминающий

5 блок 10. Данный цикл работы устройства продолжается до тех пор, пока на выходе схемы И 9 не будет обнаружена единица (, блок 52), что означает конец правой части подстановки, или до тех пор, пока не будет обнаружен нуль на выходе схемы ИЛИ

16 (. , блок 50), что означает использование всего ресурса запоминающего блока 10, образованного позицией вхождения образца.

По условию (блок 50) и по условию (блок 53) выполняется запись в запоминающий блок 14 через коммутатор 19 (ЗП4: 1, У2: 1, блок 55) содержимого регистра-счетчика 22, в котором хранится адрес начала исходного свободного ресурса запоминающего блока 10, по которому запишется очередной символ из запоминающего блока 6.

В соответствии с блоком 57 алгоритма работы устройства осуществляется изменение значений адресов на регистрах-счетчиках 5 и 22 с помощью команд +1РС2; 1 и +1РС4: 1 соответственно, а также изменяется значение адреса в регистре-счетчике 14 через коммутатор 12 из запоминающего блока 13 командами ЧТ4: 1, и . По выставленным адресам на регистре- счетчике 5 и на регистре-счетчике 14 командами и (блок 59) очередной символ перезаписывается из запоминающего блока 6 в запоминающий блок 10. Цикл работы устройства по условию (блок 50) и (блок 53) выполняется до тех пор, пока не будет обнаружено переполнение запоминающего блока 10 (единичное состояние регистра-счетчика 22), о чем сигнализирует единица на выходе схемы И 20 (, блок 60), или до тех пор, пока не будет обнаружена единица на выходе схемы И 9, сигнализирующая о конце правой части подстановки, а следовательно, конце записи в запоминающий блок 10.

После перезаписи правой части подстановки ее последний символ, записанный в запоминающий блок 10, разрывает обрабатываемое слово, поэтому необходимо оп- ределить адрес следующего за ним символа. Данный адрес хранится на регистре 18 и переписывается в запоминающий блок 13 из регистра 18 с помощью команд У2: 0,ЗП4: 1 (блок 54) через коммутатор 19. Кроме того, на этом шаге выполняется обнуление счетчика 21 командой (блок 54) и осуществляется подготовка работы устройства в соответствии с очередной подстановкой, для чего адрес начала ее образца переписывается из регистра 4 на регистр- счетчик 3 с помощью команды (блок 54).

Если обнаружится признак , что соответствует значению (блок 56) и указывает тип заключительной подстановки, то работа устройства останавливается, и оно готово для выдачи результата на внешние устройства по каналу РЕЗ (фи. 1). В противном случае (Т ) устройство подготавливается к обработке слова с помощью очередной подстановки, для чего обнуляются регистр 11, регистр-счетчик 14 и регистр 18

командами , и соответственно (блок 58). После этого вновь выполняется переход на блок 28 алгоритма (фиг. 2).

В случае переполнения запоминающего

0 блока 10 осуществляется аварийная остановка работы устройства (блок 62).

После остановки работы устройства (блок 61)алгоритма (фиг. 2) в запоминающем блоке 10 содержится результат, который по

5 внешнему информационному выходу РЕЗ (фиг. 1) выдается в соответствии с алгоритмом (фиг. За), для чего регистр-счетчик 14 сбрасывается в нуль командой У и командой У (блок 63), коммутатор 12 со0 единяет информационный выход запоминающего блока 13 с информационным входом регистра-счетчика 14. После этого выполняется цикл (блоки 65, 66), состоящий из чтения адреса следующего символа в

5 запоминающем блоке 13 командой , прием адреса в регистр-счетчик 14 командой и чтение по этому адресу символа результата из запоминающего блока командой . Цикл передачи символов

0 результата продолжается до тех пор, пока не будет обнаружен признак конца слова (блок 64).

Запись информации в запоминающий блок 2 выполняется по алгоритму (фиг. 36).

5 Вначале выполняется команда СБРОС: 1, что приводит к установке регистра-счетчика 3 в нулевое состояние (блок 68). Затем выполняется цикл записи информации с внеш- него входа устройства ВВ1 (фиг.1)

0 командами записи и изменение адреса +1РС1: 1 (блоки 69, 70) до тех пор, пока на внешнем входе ВВ1 не появится признак последней подстановки (блок 70). Информация, соответствующая последней

5 подстановке, записывается в цикле в запоминающий блок 2 (блоки 74, 72) до тех пор, пока не будет обнаружено отсутствие признака конца образца (блок 73), поскольку последней записывается

0 специальная подстановка, имеющая пустой образец с признаком и .

Запись информации в запоминающие блоки 10 и 13 выполняется синхронно по алгоритму (фиг. Зв) после загрузки запоми5 нающего блока 2. Регистр-счетчик 5 находится в нулевом состоянии, и по этому адресу в запоминающий блок 6 записывается с внешнего входа устройства ВВ2 (фиг. 1) символ, состоящий из всех единиц, командой (блок 76). Выполнить это необходимо для того, чтобы внешний вход устройства ВВЗ мог быть подключен по схеме с открытым коллектором по принципу МОНТАЖНОЕ ИЛИ. Регистр-счетчик 14 устанавливается в нулевое состояние командой Ус- (блок 77), коммутатор 19 командой У2:-1 (блок 77) соединит выход регистра- счетчика 22 с входом запоминающего блока 13. Регистр-счетчик 22 устанавливается в состояние, равное двоичной натуральной единице, командой . Затем выполняется цикл записи символов обработанного слова один за другим по адресам линейного упорядочения в запоминающем блоке 10с помощью команд +1РСЗ: 1 и +1РС4: 1 и команд записи и (блоки 80 и 79), что позволит разместить в запоминающем блоке 10 символы слова так, чтобы следующий символ в слове имел следующий адрес в запоминающем блоке 10. Цикл повторяется до тех пор, пока на внешнем канале ВВЗ (фиг. 1) не будет обнаружен признак конца слова , признак записывается (блок 82) в запоминающий блок 10 по адресу, записанному в регистр-счетчик 14 командой +1РСЗ: 1 (блок 81), а регистр- счетчик 22 принимает нулевое состояние командой из обнуленного регистра блока 15 микропрограммного управления.

Запись информации в запоминающий блок 6 осуществляется символ за символом в цикле (фиг. Зг) до тех пор, пока не будет обнаружен пустой символ на внешнем входе ВВ2 (фиг, 1), для чего выполняются команды записи (блок 84) и изменение адреса запоминающего блока 6 в регистре- счетчике 5 командой 1РС2: 1 (блок 85). Выход из цикла организован по условию ВВ2 .

После записи информации в запоминающие блоки 2, 10, 13 и 6 в регистр блока 15 микропрограммного управления по внешнему входу ВВ4 (фиг. 1) записывается двоичное число, определяющее длину обрабатываемого слова с учетом двух служебных символов, обозначающих начало и конец записи в запоминающем блоке 10.

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

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

чтения и записи первого запоминающего блока, первый, второй и третий информационные выходы которого соединены с вторым, третьим и четвертым разрядами входа логических условий блока микропрограмм0 ного управления, выходы с третьего по пятый разрядов поля местного управления которого соединены соответственно с входом записи, вычитающим и суммирующим ЁХОДЗМИ первого регистра-счетчика, инфор5 мационный выход которого соединен с первым информационным входом первого запоминающего блока, второй информационный вход которого соединен с первым информационным входом устройства, вто0 рой информационный вход устройства соединен с первым информационным входом второго запоминающего блока, выход которого соединен с входами первого элемента И, выход которого соединен с пятым разря5 дом входа логических условий блока микропрограммного управления, выход шестого разряда поля местного управления которого соединен с входом записи третьего регистра, второй информационный вход второго

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

5 управления блока микропрограммного управления, девятый и десятый разряды поля местного управления которого соединены с входами чтения и записи второго запоминающего блока, выходы одиннадцатого и две0 надцатого разрядов поля местного управления блока микропрограммного управления соединены с входами записи и установки в О первого регистра, информационный выход третьего запоминающего

5 блока соединен с вторым информационным входом компаратора, с информационным выходом устройства, с входами второго элемента И, выход которого соединен с шестым рязрядом входа логических условий блока

0 микропрограммного управления, выход тринадцатого разряда поля местного управления которого соединен с управляющим входом первого коммутатора, выходы четырнадцатого и пятнадцатого разрядов по5 ля местного управления блока микропрограммного управления соединены соответственно с входами чтения и записи третьего запоминающего блока, информационный выход третьего регистра-счетчика соединен с вторым информационным БХОдом третьего запоминающего блока, с третьим информационным входом устройства, четвертый информационный вход устройства соединен с входом кода операции блока микропрограммного управления, вы- ходы с шестнадцатого по восемнадцатый разрядов поля местного управления которого соединены соответственно с входами установки в О, записи и суммирующим входом третьего регистра-счетчика, первый и второй входы пуска и вход сброса устройства соединены соответственно с первым и вторым входами пуска и входом сброса блока микропрограммного управления, первый и второй выходы поля внешнего управления которого соединены с выходами Стоп, и Аварийный останов устройства, отличающееся тем, что, с целью сокращения аппаратурных затрат и повышения быстродействия при обработке символьной инфор- мации, в него дополнительно введены второй коммутатор, счетчик, четвертый регистр-счетчик, четвертый запоминающий блок, причем выходы девятнадцатого и двадцатого разрядов поля местного управ- ления блока микропрограммного управления соединены с входами чтения и записи четвертого запоминающего блока, информационный выход третьего запоминающего блока соединен с входами элемента ИЛИ- НЕ, выход которого соединен с седьмым разрядом входа логических условий блока микропрограммного управления, выходы двадцать первого и двадцать второго разрядов поля местного управления которого со- единены соответственно с суммирующим и вычитающими входами счетчика, информационный выход которого соединен с входом первого регистра и с первым информационным входом четвертого запоминающего блока, информационный выход которого соединен с первым информационным входом первого коммутатора, выход которого соединен с информационным входом третьего регистра-счетчика, информационный выход которого соединен с вторым информационным входом первого коммутатора, выход двадцать третьего разряда поля местного управления блока микропрограммного управления соединен с первым входом второ-

го элемента ИЛИ, информационный выход четвертого запоминающего блока соединен с информационным входом второго регистра, информационный выход которого соединен с первым информационным входом второго коммутатора, информационный выход которого соединен с вторым информа- ционнымвходомчетвертого

запоминающего блока, второй информационный вход коммутатора соединен с инфор- мационным выходом четвертого регистра-счетчика, выходы двадцать четвертого и двадцать пятого разрядов поля местного управления блока микропрограммного управления соединены соответственно с входами установки в О и с входом записи второго регистра, управляющий вход второго компаратора соединен с двадцать шестым входом разряда поля местного управления блока микропрограммного управления, информационный выход четвертого регистра-счетчика соединен с входами третьего элемента И, выход которого соединен с восьмым рязрядом входа логических условий блока микропрограммного управления, выход поля констант которого соединен с информационным входом четвертого регистра-счетчика, суммирующий вход и вход записи которого соединены соответственно с выходами двадцать седьмого и двадцать восьмого разрядов поля местного управления блока микропрограммного управления, информационный выход счетчика соединен с входами первого элемента ИЛИ, выход которого соединен с девятым разрядом входа логических условий блока микропрограммного управления, выход второго элемента ИЛИ соединен с входом установки в О счетчика, второй вход второго элемента ИЛИ соединен с выходом первого элемента И, четвертый информационный выход первого запоминающего блока соединен с информационным входом второго регистра- счетчика и с информационным входом третьего регистра, информационный выход которого соединен с информационным входом первого регистра-счетчика, информационный выход второго запоминающего блока соединен с вторым информационным входом третьего запоминающего блока.

I

tNi

Изобретение относится к техническим средствам информатики и вычислительной техники и предназначено для решения задач обработки символьной информации в соответствии с заданной системой формул подстановок. Цель изобретения - сокращение аппаратурных затрат и повышение быстродействия при обработке символьной информации - достигается тем, что в устройство, содержащее с первого по третий запоминающие блоки, с первого по третий регистры, с первого по третий регистры-счетчики, с первого по третий элементы И, первый и второй элементы ИЛИ, элемент ИЛИ-НЕ, первый коммутатор, компаратор, дополнительно введены второй коммутатор, счетчик, четвертый регистр-счетчик, четвертый запоминающий блок. Устройство позволяет обрабатывать системы формул с оптимальной последовательностью включений их в работу с одновременной возможностью обрабатывать как алфавитные переменные, так и битовые ансамбли, а также иметь техническую сложность (число компараторов, разрядность регистров и счетчиков), не зависящую от длины правых и левых частей формул алгорифма в широком диапазоне изменения этих длин. Устройство работает с алфавитными переменными, дополнительными метками формул и ансамблями битов, что в совокупности приводит к сокращению затрат времени и длин обрабатывающих нормальных алгоритмов. 3 ил. со с VJ -N