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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)з G 06 F 15/20

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (ф

В

> (21) 4799324/24 (22) 05.03.90 (46) 15.06.92. Бюл. N 22 (71) Курский политехнический институт (72) B.M. Довгаль, О,Ф. Корольков, Ф.А.

Старков, Е.И. Леонов, Д.Н. Тютюнов и С,С, Шевелев (53) 681.3(088.8) (56) Авторское свидетельство СССР

N 1187173, кл. G 06 F 15/04, 1985.

Авторское свидетельство СССР

¹ 1455345, кл. G 06 F 15/20, 1987. (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ

ПОДСТАНОВОК (57) Изобретение относится к техническим средствам информатики и вычислительной техники и предназначено для решения задач обработки символьной информации в соответствии с заданной системой формул подстановок. Цель изобретения — сокращение аппаратурных затрат и повышение быстродействия при обработке символьной информации — достигается тем, что в устройство, содержащее с первого по третий запоИзобретение относится к техническим средствам информатики и вычислительной техники и предназначено для решения задач обработки символьной информации в соответствии с заданной системой формул подстановок.

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

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

„„ 0 „„1 741 147 А1 минающие блоки, с первого по третий регистры, с первого по третий регистры-счетчики, с первого по третий элементы И; первый и второй элементы ИЛИ, элемент ИЛИ-НЕ, первый коммутатор, компаратор, дополнительно введены второй коммутатор, счетчик, четвертый регистр-счетчик, четвертый запоминающий блок, Устройство позволяет обрабатывать системы формул с оптимальной последовательностью включений их в работу с одновременной возможностью обрабатывать как алфавитные переменные, так и битовые ансамбли, а также иметь техническую сложность (число компараторов, разрядность регистров и счетчиков), не зависящую от длины правых и левых частей формул алгорифма в широком диапазоне изменения этих длин. Устройство работает с алфавитными переменными, дополнительными метками формул и ансамблями битов, что в совокупности приводит к сокращению затрат времени и длин обрабатывающих нормальных алгоритмов. 3 ил. мультипрограммного управления; на фиг. 3 — граф-схемы алгоритмов загрузки запоминающих блоков устройства и граф-схема алгоритма выдачи результата.

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

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

1-го по 28-й) поля местного управления блока 15, вход 24 (с разрядами с 1-ro по 9-й) логических условий блока 15.

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

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

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

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

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

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

55 ции существенно сокращает затраты времени, Минимизация времени работы алгорифма Маркова также достигается за счет введения в подстановки образцов, содержащих алфавитные переменные, с помощью которых можно эффективно обрабатывать цепочки символов и нуль-единичные конфигурации, В блок-схеме алгоритма работы устройства для реализации подстановок, приведенной на фиг. 2, позиции 23 — 61 являются шагами работы алгоритма Для описания алгоритма используются следующие идентификаторы: СБРОС вЂ” усгэновка исходных состояний устройства; HYCK — команда запуска устройства; ПКП вЂ” признак конца правой части подстановки; ПК — признак конца образца; ПКС вЂ” признак конца обрабатываемого слова; a — признак специального символа в обрабатываемом слове; ПЕР— признак переполнения запоминающего блока 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

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

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

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

ППФ, указывающий своим единичным зна- 20 чением на то, что подстановка является последней в списке. Начиная с второго адреса поля образца хранятся его символы (n бит) и их маски(п бит). Все признаки; 3 КЛ, ПКВ и ППФ хранятся в 2 n+1-м разряде запоминающего 25 блока 2; длина кода адресов m=2n. Маски символов используются для блокировки несовпадения битов кодов символов, сравниваемых на компараторе 1, который работает в соответствии с булевым выражением: 30

"="=(Х1 8 Х11/Х1 8 X< vm <)g...Я(Хд 8i Xri g X4

ЬХпдmn) где Х, X2, ..., Xn — биты кода символа образца, Х, Хг,..., Х вЂ” биты кода символа обрабатываемого слова, m<, mz, .„, m — биты маски символа образца, n — длина двоичного кода символа.

Все следующие по порядку адреса запоминающего блока 2 используются для хранения символов и их масок с пустым 2п+1-м разрядом, кроме адреса последнего символа, где наряду с символом и его маской хранится признак ПКВ=1 в 2n+1-м разряде.

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

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

55 зуется в качестве признака конца правой части подстановки (ПКП).

В запоминающем блоке 10 хранится исходное обрабатываемое слово. По первому адресу содержится служебный "пустой" символ (n бит), по всем остальным адресам строго по порядку размещаются символы слова (каждый и бит). Последним символом является служебный код (n бит), состоящий из всех единиц и используемый в качестве признака конца слова (ПКС). В составе обрабатываемого слова может встретиться специальный символ (a ), который используется для косвенной адресации на следующий символ в слове, Запоминающий блок 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 (блок

1741147

15

30

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 и У 2=1 соответственно (блок 32). Если в результате проверки признака Т2 он будет равен единице, что соответствует случаю, когда не сработала последняя подстановка алгорифма, то устройство останавливает свою работу (блок

61) и готово к выдаче на внешние устройства результата по каналу РЕ3 (фиг. 1), В том случае, когда Т2=0, осуществляется обработка слова с помощью очередной подстановки, адрес первого. символа образца которой содержится на регистре-счетчике 3, а адрес начала обрабатываемого слова соответствует нулевому состоянию регистрасчетчика 14.

По условию ПКС=О и по командам

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

Когда на выходе компаратора 1 формируется сигнал ("="=0), что указывает на несовпадение сравниваемых символов (блок

35), тогда выполняется проверка выхода

ИЛИ-НЕ 7, единица на котором указывает на существование в обрабатываемом слове

" а "(блок 36). Если в обрабатываемом слове обнаружен служебный символ "a ", то выполняется переход к следующему символу обрабатываемого слова, что достигается приемом на регистр-счетчик 14 адреса следующего за" а " символа в запоминающем блоке 10, для чего коммутатор 12 соединяет выход запоминающего блока 13 с входом регистра-счетчика 14 по команде У1:=1 (блок

40), а по командам ЧТ4:=1 и Пр 4:=1(блок 40) информация считывается из запоминающего блока 13 и записывается в регистр-счетчик 14. При этом в запоминающем блоке 2 не изменяется адрес того символа образца, который сравнивался на предыдущем такте работы устройства.

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

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), то это ,означает, что в обрабатываемом слове обна1741147

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:=О; ПР 4: =1 — позволяют считать из запоминающего блока 2 адрес начала правой части подстановки и записать его в регистрсчетчик 5, а также присвоить вспомогательному признаку Т1 значение признака

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), что означает конец правой части подстановки, или до тех пор, пока не будет обнаружен нуль на выходе схемы ИЛИ

1741147

12 блок 13 из регистра 18 с помощью команд 45

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, У1=1 и Пр4;=1, По выставленным адресам на регистресчетчике 5 и на регистре-счетчике 14 командами ЧТ2;=1 и ЗПЗ;=1 (блок 59) очередной символ перезаписывается из запоминающего блока 6 в запоминающий блок 10. Цикл работы устройства по условию СЧ=О (блок

50) и ПКП=О (блок 53) выполняется до тех пор, пока не будет обнаружено переполнение запоминающего блока 10 (единичное состояние регистра-счетчика 22), о чем сигнализирует единица на выходе схемы И 20 (ПЕР=1, блок 60), или до тех пор, пока не будетобнаружена единица на выходесхемы

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

После перезаписи правой части подстановки ее последний символ, записанный в запоминающий блок 10, "разрывает" обрабатываемое слово, поэтому необходимо определить адрес следующего за ним символа. Данный адрес хранится на регистре 18 и переписывается в запоминающий

У2: =0,3П4: =1 (блок 54) через коммутатор 19.

Кроме того, на этом шаге выполняется обнуление счетчика 21 командой ПКП:=1 (блок

54) и осуществляется подготовка работы устройства в соответствии с очередной подстановкой, для чего адрес начала ее образца переписывается из регистра 4 на регистрсчетчик 3 с помощью команды Пр2:=1 (блок

54).

Если обнаружится признак ЗКЛ=1, что соответствует значению Т1=1 (блок 56) и указывает тип заключительной подстановки, то работа устройства останавливается, и оно готово для выдачи результата на внешние устройства по каналу РЕЗ (фи. 1). В против5

40 ном случае (Т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), Выполнить это необхо13

1741147

5

25

40

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 принимает нулевое состояние командой Rp8;=1 из обнуленного регистра блока 15 микропрограммного управления.

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

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

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

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

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

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

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

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

1741147

1741147

Я Я

ПРГ:=1 -1РС1:=1

ПРИ=1; УР2: -"1

Л g 77 р РС /

Л „Р я

uf:=1; Пр/:=1 /7 // =1 УР/: =f

У/" =1 ip//: = f

У7Ъ =1

4 2 . 7p5:1

46

ЧТ1:= f ПР.7: = f

У1:=ф n//:=1

-1Ю1:=1

c 45

+fPCc:=1У/: = 1 О1:=f ЛР7:=1

-1C4 f:= f

51

//Т2:=1ЗПЗ:= f п п

52

ПКП

Я

ПРЯ:=/ ПКП: =1

jg: = Ф,УЛФ: = I

ХХ

УГ:=1.7ЛФ =1

mO/7 сброс гх сйос:= f

Г1:=1 Р1--1

Пут

Ã7

Луа :=1

Кю:=а п г:=1 пл Г

Л

УП7:=1УT1 = 1

РСУ

43 1С/1: =1

Ф5

+1РС1:=1

//Т//: =1 ПР7: =1

Л

7pf. =f

//Tf : = 1

ТЕ: =ЛПФ

УФ:=1УФГ =1 0

npZ:=Ыат:=1 ХУ

Я Г7. g г

3 1

Ф7 1РП:=1 УУГ=1

1Ж1:=1//Tr: = 1

Л .У:= 1ЛР1: =1.57

+1РСг:=1 .f//:// =r У1. =1

КТ4: =10р//:=1

1741147

Соста вител ь А. Со ш ки н

Редактор А.Маковская Техред М,Моргентал Корректор В. Гирняк

Заказ 2086 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", r Ужгород, ул,Гагарина, 101