Устройство для реализации подстановок
Изобретение относится к техническим средствам информации и вычислительной технике и может быть использовано для обработки массивов данных текстового и числового типа. Цель изобретения - повышение быстродействия устройства. Устройство содержит блок 1 анализа вхождений, блок 2 формирования слов вхождения и подстановки, блок 3 просмотра, блок 4 памяти формул, блоки 5, 6 подстановки, блок 7 памяти слова, блок 8 микропрограммного управления с соответствующими связями. 5 з.п. ф-лы, 10 ил.
союз советсних
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИН (19) (И1
5 А1 щ) 5 С 06 F 15/20
1"
,,,. Ц;.ьа ,;;уо. ERA
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
H A ВТОРСНОМЪ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТНРЬГИЯМ
ПРИ ГКНТ СССР
1 (21) 4483370/24-24 (22) 27.09.88 (46) 30.09.90. Вюл. Ф 36 (7 1) Курский политехнический институт (72) В.M.Äoâãàëü, О.Ф.Корольков, Ф.А.Старков и С.С.Шевелев (53) 681.325(088.8) (56) Авторское свидетельство СССР
9 1187173, кл. G 06 F 15/04, 1984.
Авторское свидетельство СССР
1455345, кл. Г 06 F 15/20, 1987.
2 (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ ПОДСТАНОВОК (57) Изобретение относится к техническим средствам информации и вычислительной техники и может быть использовано для обработки массивов данных текстового и числового типов. Цель изобретения — повьппение бы стродействия устройства.. Устройство содержит блок 1 анализа вхождений, блок 2 формирования слов вхождения
4 и подстановки, блок 3 просмотра, блок 4 памяти Формул, блоки 5, 6 подстановки, блок 7 памяти слова, блок
Изобретение относится к техническим средствам информатики и вычисли- 10 тельной техники и может быть использовано для обработки массивов данных текстового и числового типов.
Цель изобретения — повышение быстродействия устройства. 15
На фиг. 1 приведена схема устройства; на фиг.2 — схема блока анализа вхождения: на фиг.3 — схема узла анализа; на фиг.4 — схема блока формирования слов вхождения и подстановки; на фиг.5 — схема блока просмотра; на фиг.б — схема узла обнаружения; на фиг.7 — схема первого блока подстановки; на фиг.8 - схема второго блока подстановки; на фиг.9 — блоксхема алгоритма работы устройства; на фиг.10 — состояние блоков устройства в рассматриваемом примере функционирования устройства.
Устройство содержит блок 1 анализа вхождения, блок 2 формирования слов вхождения и подстановки, блок 3 просмотра, блок 4 памяти формул, первый 5 и второй 6 блоки подстановки, блок 7 памяти слова, блок 8 микропрограммного управления.
Блок 1 анализа вхождения содержит сдвигающий регчстр 9, дешифратор 10, элемент ИЛИ 11, счетчик 12, восемь. узлов анализа 13, элемент И 14. 40
Узел 13 анализа содержит первую группу элементов И 15, вторую группу элементов И 16, группу элементов
ИЛИ 17. и элемент ИЛИ 18.
Блок 2 формирования слов вхожде 45 ния и подстановки содержит с первого по восьмой сдвигающие регистры
-19, с девятого по шестнадцатый сдвигающие регистры 20, элемент 2 1 задержки, с первого по третий элементы
И 22-24, первый 25 и второи 26 эле
50 менты ИЛИ, группу элементов И 27, коммутатор 28 и регистр 29.
Блок 3 просмотра содержит восемь
55 элементов ИЛИ 30, элемент ИЛИ-НЕ 31 и восемь узлов 32 обнаружения, каждый из которых содержит первый 33 и второй Зч сдвигающие регистры, группу
8 микропрограммного управления с соответствующими связями. 5 з.п. ф-лы, 10 ил. элементов И 35, элемент ИЛИ 36, элемент И 37 и элементы 38 сравнения.
Первый блок 6 подстановки содержит счетчик 39, дешифратор 40, триггер 41, коммутатор 42, группу элементов
ИЛИ 43, первый 44 и второй 45 элементы ИЛИ, первый, второй и третий элементы И 46-48, восемь узлов 49 сдвига и элемент 50 задержки.
Второй блок 5 подстановки содержит регистр 51, триггер 52, элемент И 53, счетчик 54, элемент ИЛИ 55, восемь узлов 56 сдвига и дешифратор 57.
Блок 1 анализа вхождения служит для обработки результатов сравнения на. равечство символов вхождения (левой части формулы подстановки) и фрагмента обрабатываемого слова. Анализируя результат сравнения, блок анализа вхождения выдает сигнал о наличии вхождения в обрабатываемом слове в тех случаях, когда имеются на обра— ботке как те формулы, которые содержат алфавитные переменные, так и те, которые их не содержа т. Кроме того, блок анализа вхождения с помощью счетчика и дешифратора задает условия обмена инФормацией между блоками просмотра, первым и вторым блоками подстановки.
Блок 2 формирования слов вхождения и п дстановки принимает параллельно формулы подстановки, формат, который содержит слово-вхождение, слово-подстановку, признаки о наличии в формуле алФавитной переменной, признак о заключительности формулы (формула используется только один раз, если имеется вхождение) и признак о том, что данная формула является: последней в списке формул данного нормального алгорифма.Каждая формула подстановки является элементом нормального алгорифма. Блок формирования слов вхождения и подстановки по команде сдвига из блока микропрограммного управления выдает последовательно по символам слово-вхождение и слово-подстановку в блок просмотра, а также .в первый блок подстановки.
Кроме того, этот блок выдает значе5 15963 ния вышеприведенных признаков формулы подстановки в блок микропрограммного управления, а также признаки конца слова-вхождения и словаподстановки, а в блок анализа вхож- дения выдает значения признаков о конце слова-вхождения и о наличии в слове-вхождении алфавитной переменной, закодированной символом .у ., !
О
Блок просмотра служит для организации просмотра обрабатываемого слова последовательно по фрагментам,равным по длине слову-вхождению, при этом осуществляется .сравнение на ра1 венство выделенного фрагмента обрабатываемого слова и слова-вхождения.
В том случае, когда слово-вхождение имеет в своем составе символ м-, кодирующий алфавитную переменную, в блоке анализа вхождения интерпретируется символьное совпадение. Всякий не совпадающий символ, за исключением указанного выше случая, передается во второй блок подстановки, и синхронно в соответствии с длиной словавхождения очередной символ обрабатываемого слова подается в выставленное поле сравнения. В случае обнаружения вхождения вместо символов обра3 батываемого слова во второй блок подстановки подается слово-подстановка или те символы обрабатываемого слова, которые соответствуют алфавитным переменным в той последовательности, которая определяется специально организованной формой слова-подстановки, если в ней содержатся алфавитные переменные.
Второй блок подстановки служит для
4 хранения промежуточных фрагментов обрабатываемого слова или результирующего обрабатываемого слова с тем, чтобы процесс просмотра обрабатываемого слова с целью обнаружения вхождения и процесс подстановки в соот45 ветствии с заданной формулой подстановки осуществлялись непрерывно.Выходы второго блока подстановки соединены с входами первого блока .подстановки в случае промежуточного ре50 зультата и входами блока памяти слов в случае конечного результата обработки. ф
V P где 7 — слово-вхождение;
P — слово-подстановка;
«Р — признак формулы Ре(0,1).
Работа формулы подстановки над обрабатываемым словом заключается в об2О наружении в нем слова-вхождения и замене позиции слова-вхождения словомподстановкой.
Позиция вхождения является первой, если при просмотре обрабатыва5 емого слова вхождение обнаружено первый раз. Если признак формулы cP= 1,. то формула называется заключительной.
Она работает один раз, а нормальный алгоритм, представляющий собой конечный список формул подстановки,прекращает свою работу. Если признак, формулы d =- О, то формула называется незаключительной и используется в работе столько раэ, сколько раз об5 наруживается вхождение, причем при обнаружении первой позиции вхождения осуществляется подстановка, а переход выполняется на первую формулу. Следующая формула подстановки нормального алгорифма включается в работу тогда, когда предыдущая формула подстановки не обнаруживает ни одной собственной позиции вхождения при полном просмотре всего обрабатываемого слова. Для описания работы устройс гва используются следующие идентификаторы:
УОΠ— установка исходных состояний .блоков устройства;
ПУСК вЂ” команда запуска устройства;
ЧТС вЂ” команда чтения обрабатываемого слова из блока памяти слов,"
ЧТФ вЂ” команда чтения формулы иэ блока памяти формул;
ЗСчР2 — команда записи всех единиц в первый блок подстановки;
ТИЗ вЂ” команда сдвига для блока пропросмотра и блока анализа вхождения;
ТИ5 — команда сдвига второго блока подстановки;
Первый блок подстановки предназначен для хранения и выдачи обрабатываемого слова при его первичной загрузке иэ блока памяти слов, а также
45 6 для организации непрерывности вышеназванных процессов.
Подстановка в обрабатываемое слово на место слова"вхождения формируется как из символов самого обрабатываемого слова вместо алфавитных переменных,так и иэ конкретных символов подстановки самой формулы.
Под Формулой подстановки понимается слово вида
1596345 ства;
СБРОС вЂ” команда установки исходных состояний; t0
ЗВСчРг — команда перезаписи со держания счетчика в регистр в первом блоке подстановки, По сигналу СБРОС:=1 все элементы устройства с памятью устанавливаются в.исходное состояние ° По сигналу
ПУСК:=1 устройство начинает работать.
По сигналу ЧТС:=1 осуществляется запись обрабатываемого слова по всей
ТИ6 — команда сдвига первого блока подстановки; (1
THV — команда сдвига содержимого регистров блока просмотра, блока анализа вхождения и блока формирования слов вхождения и подстановки;
+ 1Сч — команда увеличения на единицу счетчика блока анализа вхождения;
СбрСч — команда сброса счетчика блока анализа вхождения;
ТИР— команда сдвига регистров ,блока формирования слов вхождения и подстановки;
IIV P — признак конца слова-вхождения;
ПР— признак конца слова-подстановки;
ПВХ вЂ” признак наличия вхождения;
ПКС1 — признак конца обрабатываемого слова в блоке просмотра;
ПКС2 — признак конца обрабатываемого слова во втором блоке подстановки
ППЕР— признак переполнения разрядной сетки во втором блоке подстановки;
ППФ вЂ” признак последней формулы в нормальном алгорифме;
ПЗФ вЂ” признак заключительной формулы;
Авар.ост — команда аварийной остановки устройства;
СбрСчА — команда сброса в нуль счетчика адреса блока памяти формул;
УКМ вЂ” значение управляющего входа коммутатора в блоке формирования слов вхождения и подстановки;
11СчА — команда увеличения на единицу счетчика адреса блока памяти формул;
IIP + — признак наличия символа в слове-подстановке;
ПР/ — признак символа разделения в слове-подстановке;
ПСч — признак ненулевого состояния счетчика в блоке анализа вхождения;
1ТгР— команда установки признака подстановки первого блока подста% новки
ОбТгР— команда сброса признака подстановки первого блока подстановки;
+1Сбч2 — команда увеличения на единицу состояния счетчика второго блока подстановки;
СбрСчб2 — команда установки в нуль счетчика второго блока подстановки;
ЗСП вЂ” команда записи обрабатыва-! емого слова в блок памяти слова;
СТОП вЂ” команда остановки .устройдлине из блока 7 памяти слова одно— временно в восемь регистров блока 6 так, что каждый вертикальный срез всех восьми регистров соответствует символу. По сигналу ЗВСчРГ:=2 -1 в счетчик блока 6 записываются все единицы, что позволяет с помощью дешифратора открывать выходы блока 6 для сдвига информации посимвольно в блок
3. В этом же такте по команде ЧТФ:=1 параллельно считывается формула по всей длине в блок 2.
В следующих тактах подаются команды сдвига на блок 3 и блок 1 анализа вхождения — ТИЗ:=1, на блок 6
ТИ6:=1, на блок 5 — ТИ5:=1, на блок
2, блок 1 анализа вхождения и блок
3 — THV:=1, одновременно подсчитывается количество символов слова-вхождения по команде +1СчВ:=1 счетчиком в блоке 1 анализа вхождения до тех пор, пока не обнаружится признак конца слова-вхождения, что позволяет загрузить блок 3 словом-вхождением и. равным ему по длине фрагментом обрабатываемого слова.
Если ПВХ=О (вхождения нет), то обрабатываемое слово продолжает поступать из блока 6 через блок 3 в блок
5, при этом производится счет символов обрабатываемого слова, загружаемого в блок 5. Символы обрабатываемого слова поступают в блок 5 в обход тех разрядов регистров блока 3, которые не входят в зону срав- нения, определяемую длиной вхождения. Команды сдвига формируются до тех пор, пока не будет обнаружено вхождение или не будет обнаружен конец обрабатываемого слова. Если вхождение не обнереиено по всей длине
1596345
10 обрабатываемого слова, то проверяется, не является ли формула последней.
Обрабатываемое слово продолжает загружаться в блок 5 до тех пор, пока в нем не будет обнаружен признак конца обрабатываемого слова.
В этом случае по команде ЗСП:=1 обрабатываемое .слово параллельно заносится в блок 7 памяти слова.
В случае, когда формула не явля.ется последней, в счетчик адреса блока 4 памяти формул прибавляется единица. После этого считывается оче- 15 редная формула, а обрабатываемое слово г родолжает загружаться в блок 5 до тех пор, пока в нем не будет обнаружен конец слова, и продолжается счет количества символов, поступивших 20 в блок 5. После загрузки обрабатываемого слова в блоке 5 проверяется признак переполнения, при ППЕР=1 формируется команда аварийной остановки устройства и устройство прекращает 25 работу. В случае отсутствия переполнения (ППЕР=О) осуществляется перезапись содержимого счетчика блока 5 в его регистр, связанный с дешифратором, а затем обнуляются счетчики бло- 30 ка 6 и блока 5 с помощью команд .ЗСчР2:=1 и СбрСчб1:=1, СбрСчб2:=1.
После этого проверяется признак конца слова-вхождения очередной формулы нормального алгорифма", Если формула
35 имеет пустое слово-вхожцение, то в начало обрабатываемого слова на место первого пустого символа ставится слово-подстановка и считывается первая фоРмула ноРмального алгорифма. Это 40
I достигается тем, что обарабатываемое слово сохраняется в блоке 5, а словоподстановка записывается посимвольно в блок 6. Для этого устанавливается в единицу триггер блока 6, сбрасыва-, ется в ноль счетчик адреса блока 4 памяти формул, на управляющем входе коммутатора блока 2 выставляется потенциал в соответствии с командой
УКИ:=1 что позволяет организовать
У
50 поступление подстановки в блок 6 из блока 2, Командами сдвига ТИР:=1 и
ТИ6:=1 слово-подстановка загружается в блок 6 до тех пор, пока не будет обнаружен конец слова-подстановки.
После этого считывается первая форму- .
55 ла нормального алгорифма и УКМ:=О,а также сбрасывается в нуль триггер . блока 6.
При ПВХ1 (вхождение обнаружено) необходимо осуществить включение слова-подстановки в обрабатываемое слово на место обнаруженного вхождения, для чего устанавливается в единицу триггер блока 6 (чтобы блокировать поступление последующей части слова через блок 5 в блок 3) и сбрасывается счетчик блока 1 анализа вхождения.
После этого определяется тип подстановки для классической схемы или для схемы нормального алгорифма, содержащего в текущей формуле алфавитные переменные.
Когда ПАП= Ф вЂ” (алфавитные переменные отсутствуют), слово-подстановка посимвольно записывается в блок 5 через блок 3 и производится счет принятых символов слова-подстановки из блока 2 с помощью команд ТИР:=1, ТИ5:=1, +1Счб2:=1, ТИ6:=1 до тех пор, пока не будет обнаружен конец словаподстановки. В процессе записи слова-подстановки в блок 5 из него в это же время может поступать конец обрабатываемого слова в блок 6 (кроме случая, когда первая формула нормального алгорифма используется первый раз).
Когда ПАП=1, осуществляется проверка наличия символбв, кодирующих в слове-подстановке алфавитные переменные. Если эти символы присутствуют (в начале слова-подстановки), то осуществляется их подсчет с помощью счетчика блока 1 анализа вхождения и одновременно происходит сдвиг сло". ва-подстановки в блоке 2. Цикл выполняется до тех пор, пока не закончится последовательность символов +.
После завершения цикла проверяется наличие в слове-подстановке символаразделителя "/" или конкретного символа. В том случае, когда символ-разделитель обнаруживается (ПР/=.1), выполняются команды ТИ6:=1, ТИ5:=1, ТИР: 1, с помощью которых конкретное значение алфавитной переменной переписывается из регистров блока 3 в блок 5 и выполняется сдвиг на одну позицию в регистрах блока 2, Пусть исходное обрабатываемое слово состоит из пяти символов (Ка(АВД), а фрагмент нормального апгорифма содержит две формулы подстановки вида:
1596345
1. АВ СДЕ;
2. (— — — — — gg(p
На устройство нормальный алгорифм в блок 4 памяти формулы подается в следующем виде: 10
К1АВ Л СДЕЛ, К2Ы +. Л ««а» lЛ, где Ki и К2 — признаки К1 = ПАП, ППФ, ПЗФ = 000 К2--1003
Л вЂ” пустой байт (00000000).
К1 А В Л С Д Е Л 20
0 О
О О
О О
1 О 25
1 О
1 О
О О
О
О
О
О
К О
О;
О О 1
О 1 О
О 1 О
О О 1 О 1 1
О 1. 1
О О 1
О
О
О
О
О
О
1
В таблице для символов приведена условная кодировка. Состояния блоков 3, 6 и 5 по этапам работы при словах-вхождениях приведены на фиг. 10.
В исходном состоянии (СБРОС:=1) регистр 9 и счетчик 12 установлены в нулевое состояние. При поступлении
35 в устройство очередной формулы подстановки нормального алгорифма пода-. ется команда СбрСчВ:=1, устанавливающая счетчик 12 в нулевое состоя ние. Счетчик 12 считает число символов слова-вхождения, поступивших в блок 3, с тем, чтобы с помощью дешифратора 10 задать длину слова-вхождения на узлах анализа 13, а также задать эту же длину на блок 3. При ненулевом состоянии счетчика 12 вьдается сигнал ПСЧВ=О.
Сдвигающий регистр 9 служит для приема последовательности символов
5О слова-вхождения в соответствии с сигналом сдвига. При этом, если в словевхождении: находится обычный текущий символ, то в регистр 9 записывается нуль, если текуший символ +, кодирующий алфавитную переменную, то эа55 писывается единица.
Узлы 13 анализа вьдают сигнал
ПВХ как в том случае, когда в работе простая формула нормального алгориф- . ма, так и в случае формулы, содержащей алфавитные переменные. Сигнал
ПВХ=1 формируется по опрашивающему сигналу ТИЗ, причем тогда, когда срабатывают все узлы 13 и поступает сигнал конца вхождения (ПЧф = 1) .Сигнал ПВХ выдается с выхода элемента
И 14, на входы которого поступают значения с выходов узлов 13 и ПЧ =1.
Пусть слово-вхождение имеет вид:
V =+аь.
Тогда в регистре 9 код слова-вхождения будет 101, на счетчике 12 код 011, соответственно, будет возбужден четвертый выход дешифратора
10. На входы элементов ИЛИ 17 поступит, соответственно, код с выходов регистра 9 и элементов сравнения 38.
Блок 2 работает следующим образом.
Из блока 4 памяти формул по сигналу ЧТФ слово-вхождение подается на сдвигащие регистры 20 таким образом, что вертикальный срез сдвигающих регистров 20 дает один байт, соответствующий одному символу.
Аналогично информация подается на сдвигающие регистры 19, куда записывается слово-подстановка.
Служебный байт с признаками формулы: формула с алфавитными переменными (ПАП = 1), формула заключительная (ПЗФ = 1), последняя формула нормального алгорифма (ППФ = 1) — записывается в регистр 29.
Информация с регистров 19 и 20 поступает последовательно, а с регистра 29 по первым трем выходам — параллельно. Для сдвигающих регистров
20 используется команда сдвига THV для сдвигающих регистров 19 — команда сдвига ТИР.
Элемент И 24 распознает символ в слове-вхождении и выдает этот сигнал IIV на выход блока. Схема ИЛИ 26 распознает пустой байт в конце слова-вхождения и выдает сигнал IIVP.Элемент И 22 распознает символ в сло ве-подстановке и вьдает сигнал ПР+.
Элемент И 23 распознает символ-разделитель /в слове-подстановке и вьдает сигнал ПР/.Схема ИЛИ 25 распознает пустой байт (00000000) конца слова-подстановки и вьдает сигнал IIP P, 13
Блок 3 работает следующим образом.
На выходы элементов ИЛИ 30 поступа- ( ет информация побайтно из блока 6 или из блока 2. Обрабатываемое слово с выходов элементов ИЛИ 30 и слововхождение из блока 3 поступают на входы узлов 32 обнаружения, на входы которых также поступает информация о длине слова-вхождения из блока 1 анализа вхождений.
В сдвигающий регистр 34 постугают первые биты каждого байта словавхождения, а в регистр 33 — первые биты каждого байта обрабатываемого слова. Элементы 38 осуществляют побитное сравнение содержимого регистров 33 и 34.
Последовательная выдача информа- 20 ции регистра 33 задается с той позиции, которая задается длиной словавхождения и определяется возбужденным выходом дешифратора 10 блока 1 анализа вхождения. Если возбужден выход 25 дешифратора, который соответствует нуль-состоянию счетчика 12 блока 1 анализа вхождения, то обрабатываемое слово не загружается в .сдвигающий регистр 33. Во всех остальных слу- 30 чаях сдвиг информации по сигналам
THV и ТИЗ осуществляется в названной выше позиции.
Сигналы выходов элементов 38 сравнения подаются на блок 1 анализа
35 вхождения для дальнейшей обработки.
Сигнал выхода элемента ИЛИ 31, распознающий пустой байт, индицирует конец обрабатываемого слова (ПКС1) в сдвигающих регистрах 33 всех восьми 40 узлов 32. Выходная информация с блока
3 подается последовательно на блок 5 в том случае, когда вхождение не обнаружено. В.том случае, когда вхождение обнаружено, через узлы 32 пе- 45 редается слово-подстановка, а затем
"хвост" обрабатываемого слова из блока 6 °
Блок 5 работает следующим образом.
В исходном состоянии счетчик и триггер устанавливается в нулевое состояние. Поступление обрабатываемого слова или подстановки происходит через внешний информационный вход по восьмиразрядной шине последовательно
55 на вторые входы восьми схем сдвигающих регистров (срез по вертикали— один байт представляет код одного символа).
Подсчет символов начинает вестись. (команда +1СчВ:=1) счетчиком, как только слово-вхождение будет полностью находиться в зоне сравнения (П7ф 1) и первый же символ несравнившегося фрагмента обрабатываемого слова начнет поступать в блок 5 таким образом, счетчик подсчитывает длину обрабатываемого слова, прошедшего обработку по одной формуле нормального алгорифма.
Сигналом того, что слово полностью поступило в блок 5, является ПКС2
1-; что фиксируется элементом ИЛИ 55.
Чтобы устройство могло продолжить работу, необходимо проверить признак переполнения (ППЕР = 0Y1). Если он равен ф, то работа продолжается, ина-. че блок 8 выдает сигнал Авар.ост.:-=1, и устройство прекращает работу.
Блок 6 работает следующим образом.
В исходном состоянии счетчик 39 и триггер 41 устанавливаются в нулевое состояние. По сигналу ЧТС на выходах блока 7 памяти слова выставляется обрабатываемое слово. В счетчик 39 по команде ЗСчР2:=1 записывается двоичный код, открывая возможность подачи обрабатываемого слова по сигналам сдвига ТИ6:=.1 на блок 3.
После поступления обрабатываемого слова в блок 5 происходит обнуление счетчика 39 по сигналу СбрСчб1:=1.
К этому моменту триггер 41 всегда находится в нулевом состоянии. Если теперь слово из блока 5 начнет поступать на входы элементов ИЛИ 43, а затем на коммутатор 42, на управляющем входе которого будет логический ноль, коммутатор начнет пропускать обрабатываемое слово на вход блока 3. При обнаружении слова-вхождения триггер
41 переводится в единичное состояние (команда iTrP:=1}, а на управляющем входе коммутатора появляется ло-гическая единица. По окончании подстановки произойдет сброс триггера
41. Теперь, если в блоке 5 содержится "хвост" обрабатываемого слова, оно будет поступать в блок 3 через части регистра узлов 49, занятых символами обрабатываемого слова, успевшими поступить за время подстановки.
Формула из о бр ет ения
1. Устройство для реализапии,подстановок, содержащее блок памяти формул, блок памяти слова и блок микро1596345 !
16 программного управления, причем первый — пятый выходы блока микропрограммного управления подключены соответственно к входам записи блока
5 памяти слова, чтения блока памяти слова, чтения блока памяти формул, к первому и второму адресным входам блока памяти формул, о т л и ч а ю щ е е с я тем, что, с целью увели- 10 чения быстродействия, оно содержит блок анализа вхождения, блок формирования слов вхождения и подстановки, блок просмотра, первый и второй блоки подстановки, причем второй и третий выходы блока микропрограммного управления подключены соответственно к первым управляющим входам первого блока йодстановки и блока формирования слов вхождения и подстанов-Zp ки, с шестого по четырнадцатый выходы блока микропрограммного управления подключены соответственно к управляющим входам с первого по четвертый второго блока подстановки и 25 к управляющим входам с второго по шестой первого блока подстановки, выходы первой и второй групп которого подключены соответственно к информационным входам первой и второй З0 групп блока просмотра, выходы первой группы которого подключены соответственно к информационным входам второго бпока подстановки, выходы первой и второй групп которого подключены соответственно к информационным входам первой группы первого блока подстановки и к информационным входам блока памяти слова, выходы которого подключены к информационным входам 40 второй группы первого блока подстановки, выход которого подключен к второму управляющему входу блока формирования слов вхождения и подстановки, выходы первой, второй H ape- 45 тьей групп которого подключены соответственно к информационным входам третьей группы первого блока подстановки, к информационным входам третьей и четвертой групп блока про50 смотра, выходы второй группы которого подключены соответственно к ин"
» формационным входам блока анализа вхождения, выходы группы которого подключены соответственно к информа55 ционным входам пятой группы блока просмотра, выход которого подключен к первому входу режима блока микропрограммного управления, пятнадцатый выход которого подключен к первым управляющим входам блока просмотра и блока анализа вхождения, шестнадцатый выход блока микропрограммного управления подключен к третьему управляющему.входу блока формирования слов вхождения и подстановки,инфор— мационные входы которого подключены соответственно к выходам блока памяти формул, семнадцатый выход блока микропрограммного управления подключен к вторым управляющим входам блока просмотра, блока анализа вхождения и к четвертому управляющему входу блока формирования слов вхождения.и подстановки, восемнадцатый выход блока микропрограммного управления подключен к пятым управляющим входам блока формирования слов вхождения и подстановкч и второго блока подстановки, первый и второй выходы которого подключены соответственно к второму и третьему входам режима блока микропрограммного управления, девятнадцатый и двадцатый выходы которого подключены соответственно к третьему .и к четвертому управляющим входам блока анализа вхождения,первый и второй выходы которого подключены соответственно к четвертому и пятому входам режима блока микропрограммного управления, с первого по седьмой выходы блока формирования слов вхождения и подстановки подключены соответственно к пятому управляющему входу блока анализа вхождения и входам режима с шестого по одиннадцатый блока микропрограммного управления, восьмой выход блока микропрограммного управления подключен к шестому управляющему входу блока анализа вхождения и к двенадцатому входу режима блока микропрограммного управления, входы признака останава, признака запуска и начальной установки которого подключены соответственно к входам признака аварийного останова, запуска и начальной установки устройства.
2. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что блок анализа вхождения содержит сдвигающий ре- гистр, дешифратор, счетчик, элемент
ИЛИ, элемент И, с первого по восьмой узлы анализа, причем информациойные входы блока подключены соответственно к.информационным входам первых групп узлов анализа с первого по вось»
159бЗ45
18 мой, первый управляющий вход бЛока подключен к управляющим входам узлов анализа с первого по восьмой, управляющие входы блока с второго по шестой подключены соответственно к
5 входу синхронизации сдвигающего регистра, к счетному входу счетчика, входу установки в "0" счетчика, к информационному входу сдвигающего реги- 1О стра и к первому входу элемента И, входы с второго по девятый которого подхлю зны соответственно к выходам узлов анализа с первого по восьмой, выходы счетчика подключены к входам дешифратора и входам элемента ИЛИ, инверсный выход которого подключен к первому выходу блока, выходы сдвигающего регистра подключены к информационным входам вторых групп узлов 2О анализа с первого по восьмой, выход элемента И подключен к второму выходу блока, выходы дешифратора подключены соответственно к информационным входам третьей группы узлов 25 анализа с первого по восьмой соответственно и к выходам группы блока, при этом каждый узел анализа содержит первую группу из и элементов И (где
n — число позиций в слове вхождения), ЗО вторую группу из и элементов И, группу из и элементов ИЛИ и элемент ИЛИ, причем в, каждом узле анализа информационные входы первой группы узла подключены соответственно к первым входам элементов ИЛИ с первого по и-й группы, информационные входы второй группы узла подключены соответственно к вторым входам элементов
ИЛИ с первого по и-й группы, выходы 40 которых подключены соответственно к первым входам элементов И с первого по и-й первой группы, информационные входы третьей группы узла подключены соответственно к первым вхо-. дам элементов И с первого по п-.é второй группы, выходы которых нодключены к входам элементов ИЛИ, выход которого подключен к выходу узла, управляющий вход которого подключен к второму входу первого элемента И первой группы, выход х-го элемента И (где i = 1,. ° .,и-1) первой группы подключен к вторым входам (i+1)-ro элемента И первой группы и i-ro эле55 мента И второй группы, выход и-го элемента И.первой группы подключен к второму входу n-ro элемента И второй группы.
3. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что блок формирования слов вхождения и подстановки содержит шестнадцать сдвигающих регистров регистр, элемент задержки, три элемента И, два элемента ИЛИ, группу элементов И и коммутатор,причем с первого по семнадцатый информационные входы блока подключены соответственно к информационным входам сдвигающих регистров с первого по шестнадцатый и регистра, первый управляющий вход блока подключен к вх<щу элемента задержки, выход которого подключен к управляющим входам сдвигающих регистров с первого по шестнадцатый и регистра, второй управляющий вход блока подключен к пер-. вым входам элементов И группы, выходы которых подключены к информационным входам коммутатора, выходы первой и второй групп котсрого подключены соответственно к выходам первой и второй групп блока, третий управляющий вход которого подключен к входам синхронизации сдвигающих регистров с первого по восьмой, выходы которых подключены к входам первого элемента
И, второго элемента И, первого элемента ИЛИ и соответственно к вторым входам элементов И группы, четвертый управляющий вход блока подключен к входам синхронизации сдвигающих регистров с девятого по шестнадцатый, выходы которого подключены к входам третьего элемента И, к входам второго элемента ИЛИ и соответственно к выходам третьей группы блока, пятый управляющий вход которого подключен к управляющему входу коммутатора, выходы с первого по восьмой, блока подключены соответственно к выходу третьего элемента.И, к первому,второму и третьему выходам регистра, к выходам первого элемента И, второго элемента И, к инверсному выходу первого элемента ИЛИ и к инверсному выходу второго элемента ИЛИ.
4 ° Устройство по п.1, о т л и— ч а ю щ е е с я тем, что блок просмотра содержит восемь узлов обнаружения вхождения, восемь элементов
ИЛИ и элемент ИЛИ-НЕ, причем информационные входы групп с первой по четвертую блока подключены соответ- ственно к входам с первого по тре тий элементов ИЛИ и к информационным входам узлов обнаружения, первые вы19
1596345 входу узла °
5. Устройство по п.1, о т л и ч а ю щ е е с я тем, что первый блок подстановки содержит восемь узлов
I ходы которых подключены к выходам первой группы блока, первый и второй управляющие входы которого подключены соответственно к первым и вторым уп5 равляющим входам узлов обнаружения, вторые выходы которых подключены к входам элемента ИЛИ-НЕ, выход которого подключен к выходу блока, информационные входы пятой группы которого 10 подключены к информационным входам групп узлов обнаружения, выходы групп которых подключены соответственно к выходам второй группы блока, выходы элементов ИЛИ с первого по восьмой подключены соответственно к третьим управляющим входам узлов обнаружения с первого по восьмой, причем каждый узел обнаружения содержит два сдвигающих регистра, группу из и элементов И,элемент И, элемент ИЛИ и п элементов сравнения, при этом в каждом узле обнаружения информационные входы группы узла подключены соответственно к первым входам элементов И 25 группы и элемента И, выходы элементов
И группы и элемента И подключены к входам элемента ИЛИ, выход которого подключен к первому выходу узла,первый управляющий, второй управляющий g0 и информационный входы которого подключены соответственно к входу синхронизации первого сдвигающего.регистра, к входу синхронизации второго сдвигающего регистра и к информационному входу второго сдвигающего регистра, выходы с первого по и-й которого .подключены соответственно к первым входам элементов сравнения с первого по п-й, выходы которых под- 40 ключены соответственно к выходам группы .узла, третий управляющий вход которого подключен к второму входу элемента И и к информационному входу .первого сдвигающего регистра, выходы 45 с первого по (n-1)-й подключены соот- . ветственно к вторым входам элементов сравнения с первого по (и-1)-й и соответственно к вторым входам элементов И c rrepaoro по (n-1)-Й группы, и-й выход первого сдвигающего регистра подключен к второму входу n-ro элемента сравнения, к второму входу и-го элемента И группы и второму сдвига, счетчик, дешифратор, триггер, 1 коммутатор, элемент задержки, группу элементов ЙЛИ, два элемента ЙЛИ и три элемента И, причем первый управляющий вход блока подключен к входу элемента задержки, выход которого подключен к первым управляющим входам узлов сдвига, второй управляющий вход блока подключен к первому входу первого элемента И, выход которого подключен к первому входу второго элемента
И и входам синхронизации узлов сдвига с первого по восьмой, третий и четвертый управляющие входы блока подключены соответственно к входам установки в "0" и в "1" триггера, прямой выход которого подключен к выходу блока и первому входу первого элемента ИЛИ, к первому входу третьего элемента И и второму входу второго элемента И, выход которого подключен к счетному входу счетчика, выходы которого подключены к входу второго элемента ИЛИ и входам дешифратора, выходы которого подключены соответственно к управляющим входам групп узлов сдвига, выход первого элемента
ИЛИ подключен к управляющему входу коммутатора и вторым управляющим входам узлов сдвига с первого по восьмой, выход второго элемента ИЛИ подключен к второму входу первого элемента ИЛИ и второму входу третьего элемента И, инверсный выход которого подключен к второму входу первого элемента И, инверсный выход триггера подключен к третьим управляющим входам узлов сдвига с первого по восьмой информационные входы первой группы блока подключены соответственно к червым входам элементов ИЛИ группы, выходы которых подключены к информационным входам коммутатора, выходы первой rpynnbt которого подключены соответственно к выходам первой группы блока, выходы второй группы коммутатора подключены соответственно к информационным входам узлов сдвига с первого по восьмой, выходы которых подключены соответственно к выходам второй группы блока, пятый и шестой управляющие входы которого подключены соответственно к информационному входу и входу установки в "Оп счетчика, информационные входы второй группы блока подключены к информационным входам групп узлов сдвига с первого по восьмой.
22
1596345
HV
У»
Счв
lTVP
Фиг. Я
Фиг.5
6. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что второй блок подстановки содержит восемь узлов сдвига, дешифратор, регистр, триг. гер, счетчик, элемент ИЛИ и элемент
И, причем первый управляющий вход, блока подключен к входам установки в "0" триггера и счетчика, выходы которого подключены к входам элемента
И и к информационным входам регистра, выходы которого подключены к входам дешифратора, выходы которого подключены соответственно к управляющим входам групп узлов сдвига с первого по восьмой, первые выходы которых подключены соответственно к выходам первои группы блока, второй управляющий вход которого подключен к входам синхронизации узлов сдвига с первого по 2р восьмой, третий управляющий вход блока подключен к счетному входу счет- чика, выход элемента И подключен к входу установки в "1" триггера, выход которого подключен к первому выходу блока, четвертый и пятый управляющие входы которого подключены соответственно к управляющим входам регистра и первого узла сдвига, вторые выходы узлов сдвига с первого по восьмой подключены к входам элемента ИЛИ, инверсный выход которого подключен к второму выходу блока, информационные входы которого подключены соответственно к информационным входам узлов сдвига с первого по восьмой, третьи выходы которых подключены соответственно к вьжодам второй группы блока.
ППР
П
P
1596345
1596345
1596345 РУе 10
Составитель В.Смирнов
Редактор Л.Веселовская Техред Л.Олийи к Корректор. Н Ревская
Заказ 2911 Тираж 569 Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ C(CP
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 1О!
