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

(Л

С

Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано для обработки информационных потоков и массивов данных текстового и числового типов в соответствии с заданными нормальными алгорифмами. Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что устройство для реализации подстановок содержит арифметический блок, блок анализа вхождения, блок формирования слов вхождения и подстановки, блок просмотра, блок памяти формул, блок подставки, блок буферной памяти, блок памяти слов и блок микропрограммного управления. 2 з.п. ф-лы, 1 табл. 13 ил.

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

Цель изобретения - увеличение быстродействия.

На фиг. 1 представлена схема устройства; на фиг. 2 - схема арифметического блока; на фиг. 3 - схема первого операционного узла арифметического блока; на фиг. 4 - схема второго операционного узла арифметического блока; на фиг. 5 - схема третьего операционного узла арифметического блока; на фиг, 6 - схема четвертого операционного узла арифметического блока; на фиг, 7

-схема блока анализа вхождения; на фиг. 8

-схема узла анализа блока анализа вхождений; на фиг. 9 - схема блока формирования слова вхождения и подстановки; на фиг. 10 - схема блока просмотра; на фиг. 11 - схема узла обнаружения блока просмотра; на фиг, 12 - схема блока подстановки; на фиг. 13 - схема блока буферной памяти.

Устройство для реализации подстановок содержит аои Ьметический блок 1, блок 2 анализа вхождения, блок 3 формирования слов вхождения и подстановки, блок 4 просмотра, блок 5 памяти формул, блок 6 подстановки, блок 7 буферной памяти, блок 8 памяти слова, блок 9 микропрограммного управления.

Арифметический блок содержит первый элемент И 10, элемент НЕ 11, первый и второй триггеры 12 и 13, второй и третий элемент И 14 и 15, первый коммутатор 16, с первого по четвертый операционные узлы

О 00 Сл О

ю

(Я

17-20, узел 21 задержки, второй и третий коммутаторы 22 и 23.

Первый операционный узел 17 содержит первый элемент И-НЕ 24, элемент ИЛИ 25, элемент ИЛ И-НЕ 26 и второй элемент И-НЕ 27. Второй операционный узел 18 содержит элемент И 28 и элемент ИЛ И-Н Е 29, Третий операционный узел 19 содержит первые элементы И 30, ИЛИ 31 и ИЛИ-НЕ 32, вторые элементы ИЛИ 33, И 34 и ИЛИ- НЕ 35, третьи элементы И 36, ИЛИ 37, ИЛИ- НЕ 38 и четвертый элемент И 39, Четвертый операционный узел 20 содержит элементы .И 40 и ИЛ И-НЕ 41.

Блок 2 анализа вхождения содержит сдвигающий регистр 42, дешифратор 43, элемент ИЛИ-НЕ 44, счетчик 45, узлы 46 анализа и элемент И 47,

Каждый узел 46 анализа содержит элементы И 48 первой группы, элементы И -19 второй группы, элементы ИЛИ 50 группы и элемент ИЛИ 51.

Блок 3 формирования слов вхождения и подстановки содержит регистр 52, сдвигающие регистры 53 первой группы, сдвигающие регистры 54 второй группы, элемент 55 задержки, первый элемент И 56, первый элемент ИЛИ-НЕ 57, второй и третий элементы И 58 и 59, второй элемент ИЛИ-НЕ 60, с четвертого по шестой элементы И 61 - 63, группу элементов И 64, элемент ИЛИ 65, третий элемент ИЛИ-НЕ 66, элемент НЕ 67, седьмой элемент И 68.

Блок 4 просмотра содержит узлы 59 обнаружения, первый элемент И 70, элементы ИЛИ 71 и второй элемент И 72.

Каждый узел 69 обнаружения содержит первый сдвигающий регистр 73, компараторы 74, второй сдвигающий регистр 75, злэ- менты И 76 группы, И 77 и ИЛИ 78. Блок 6 подстановки содержит первый

элемент И 79, сдвигающие регистры 80, счетчик 81, второй элемент И 82, триггер 83 и элемент 84 задержки.

Блок 7 буферной памяти содержит регистр 85, злем ент ИЛИ-НЕ 86, дешифратор 87, сдвигающие регистры 88, элементы И 89 с первой по восьмую группы/элементы ИЛИ 90 первой группы, элементы ИЛИ 91 второй группы, элементы И 92 девятой группы, триггер 93 подстановки и элемент ИЛИ 94.

В основу нормальных алгорифмбв положено понятие формулы подстановки, под которой понимается слово вида

а

.О)

где v - слово-вхождение: р - слово-подстановка; б-признак формулы, б€{0, 1},

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

Позиция вхождения является первой,

если при просмотре обрабатываемого слова вхождение обнаружено первый раз. Если признак формулы д 1, то формула называется заключительной. Она работает один раз, и нормальный алгорифм,представляющий собой конечный список формул подстановки, прекращает СБОЮ работу. Если признак формулы (, то формула нззы- гается пеззключительной и используется в работе столько раз, сколько раз обнаруживается вхождение.

8 работе нормального алгорифма, когда число формул в нем больше, чем одна, устанавливается регламент работы каждой формулы подстановки. Если формула в списке

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

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

Арифметический блок служит для обре

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

и равно.

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

алфавитные переменные и которые их не содержат. Кроме того, блок анализа вхождения задает условия обмена информацией между блоком просмотра и блоком подстановки.

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

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

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

Блок буферной памяти предназначен для хранения и выдачи обрабатываемого слова при его обработке по очередной формуле, а также для задержки слова до тех пор, пока идет подстановка.

Для описания алгоритма работы блока управления используются следующие обозначения:

УОО - установка исходного состояния;

Пуск - команда запуска устройства;

ЧТС - команда чтения обрабатываемого слова из блока памяти слов;

ЧТФ - команда чтения формулы из блока памяти формул;

V3 - команда, разрешающая запись слова из блока подстановки в блок буферной памяти;

ТИЗ - команда сдвита для сдвигающих регистров блока вхождения и слов в блоке анализа вхождения;

ТИ5 - команда сдвига в блоке подстановки;

THV - команда сдвига содержимого сдвигающих регистров вхождения блока просмотра, блока анализа вхождения, блока формирования слов вхождения и подстановки;

ТИ6 - команда сдвига в регистрах блока буферной памяти;

-НСчВ - команда увеличения на единицу счетчика блока анализа вхождения;

СбрСчВ - команда сброса счетчика блока анализа вхождения;

Т ИР - команда сдвига для сдвигающих регистров слова-подстановки в блоках вхождения и подстановки формирования слов;

nv0- признак конца слова-вхождения;

признак конца слова-подстановки;

ПВХ - признак наличия вхождения;

ГПчС1 - признак конца обрабатываемого слова в блоке просмотра;

ПКС2 - признак конца обрабатываемого слова в блоке подстановки;

ППЕР - признак переполнения разрядной сетки в блоке подстановки:

ППФ - признак последней формулы в нормальном алгорифме;

ПЗФ признак заключительной формулы;

Авар.ост, - команда аварийной остановки устройства;

СбрСчА - команда сброса в нуль счетчика адреса блока памяти формул;

+1СчА - команда увеличения на единицу счетчика адреса блока памяти формул;

ПР - признак наличия символа Х2 в слове-подстановке;

ПР - признак символа разделителя в слове-подстановке;

ПСчВ - признак ненулевого состояния счетчика в блоке анализа вхождения;

|ТгР - команда записи единицы в триггер подстановки;

ОбТгР - команда установки в нуль триггера подстановки;

П/ - признак наличия скобки в обрабатываемом слове;

ПАР - признак арифметической команды;

СБрСчб - команда установки в нуль счетчика блока подстановки;

ЗСП - команда записи обрабатываемого слова в блок памяти слова;

Стоп - команда остановки устройства;

Сброс - команда установки исходных состояний;

П - признак того, что при сравнении первое число больше второго;

СбрТгА- команда обнуления арифметического блока;

1УК - команда управления коммутатором в арифметическом блоке;

ТИА - тактовые сигналы для арифметического блока.

По сигналу Сброс : 1 все элементы устройства с памятью устанавливаются в исходное состояние. По сигналу 1 устройство начинает работать. По сигналу ЧТС : 1 осуществляется запись обрабатываемого слова по всей длине из блока памяти слова 8 в блок 6 подстановки. 8 следующем такте работы по команде 4Jjj: 1 параллельно считывается формула по всей длине в блок 3 формирования слов-вхожде- ния и подстановки, и одновременно по команде V3: 1 обрабатываемое слово из блока 6 лодстановки параллельно переписывается в регистры блока 7 буферной памяти.

В следующих тактах подаются команды сдвига на блок 4 просмотра и блок 2 анализа вхождения ТИЗ: 1, на блок 7 - ТИ6: 1, блок 2 анализа вхождения и блок 4 просмотра -ТИУ: 1, одновременно подсчитывается количество символов слова-вхождения по команде +1СчВ: 1 в блоке 2 анализа вхождения до тех пор, пока не обнаружится

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

Если ПВХ 0 (вхождения нет), то в блоке

20 формируются команды сдвига и обрабатываемое слово продолжает поступать из блока 7 через блок 4 просмотра в блок 6 подстановки, при этом в блоке 6 подстанов0 ки ведется подсчет подступающих символов обрабатываемого слова. Символы обрабатываемого слова поступают в блок 6 подстановки в обход тех разрядов регистров блока 4 просмотра, которые не входят в зону ком5 парации, определяемую длиной вхождения.

Команды сдвига формируются до тех

пор, пока не будет обнаружено вхождение

(ПВХ 1) или не будет обнаружен в зоне

компарации блока 4 просмотра конец обра0 батываемого слова (ПКС1 1). Если вхождение не обнаружено по всей длине обрабатываемого слова, то далее проверяется, не является ли формула последней в нормальном алгорифме (ППФ 1, блок 22),

5 Обрабатываемое слово продолжает загружаться в блок 6 подстановки до тех пор, пока в нем не будет обнаружен признак конца обрабатываемого слова . В этом случае обрабатываемое слово парал0 лельно заносится в блок 8 памяти слова.

В том случае, когда формула не является последней в нормальном алгорифме (ППФ 0), то в счетчик адреса блока 5 памяти формул прибавляется единица (+1СчА: 1), По5 еле этого считывается очередная формула, а обрабатываемое слово продолжает загружаться в блок 6 подстановки до тех пор, пока в нем не будет обнаружен конец слова ().

0 После загрузки обрабатываемого слова в блок 6 подстановки проверяется признак переполнения (), в этом случае формируется команда аварийной остановки устройства (Авар.ост.: 1) и устройство

5 прекращает работу.

В следующем такте обнуляется сметчик блока 6 подстановки {команда СбрСчб: 1), Далее проверяется признак конца слова- вхождения очередной формулы нормально0 го алгорифма. Если ПУ 1 (формула имеет пустое слово-вхождение, а такая формула не может встретиться в начале нормального алгорифма), то в начало обрабатываемого слова на место первого пустого символа ста5 вится слово-подстановка и считывается первая формула нормального алгорифма. По команде 1ТгР: 1 в триггер подстановки записывается единица и одновременно происходит сброс счетчика адреса формулы СбрСчА: 1, что позволяет записать подстановку из блока 3 формирования слов вхождения и подстановки в блок б подстановки. В следующем такте командами сдвига и слово-подстановка загружается в блок 6 подстановки до тех пор, пока не будет обнаружен конец слова-подстановки (ПР 1). После этого считывается первая формула нормального алгорифма ЧТ., а также сбрасывается в нуль триггер подстановки ОбТрГ: 1.

Рассмотрим работу алгоритма блока 9 микропрограммного управления при переходе по условию ПВХ 1 (вхождение обнаружено). В этом случае устанавливается в единицу триггер подстановки, чтобы блокировать поступление последующей части слова из буфера 7, и сбрасывается счетчик блока 2 анализа вхождения (Т1гР: 1, СбрСчВ: 1). После этого определяется тип подстановки для классической схемы или для схемы нормального алгорифма, содержащего в текущей формуле алфавитные переменные, или признак арифметической обработки.

Рассмотрим случай, когда ПАП и , алфавитные переменные отсутствуют и операция не арифметическая. В этом случае слово-подстановка будет посимвольно записываться напрямую через блок 4 просмотра и арифметический блок 1 в блок 6 подстановки с помощью команд , до тех пор, пока не будет обнаружен конец слова-подстановки ().

В том случае, когда ПАП.1, осуществляется проверка наличия символов , кодирующих в слове подстановки алфавитные переменные, Если эти символы присутствуют (в начале слова-подстановки), то осуществляется их подсчет с помощью счетчика блока 2 анализа вхождения и одновременно происходит сдвиг слова-подстановки в блоке 3 формирования слова вхождения и подстановки (+ 1СчВ: 1, ТИР: 1). Цикл выполняется до тех пор, пока не закончится последовательность символов у.

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

конкретный символ первый, то осуществляется запись этого символа из регистров подстановки в блок 6 подстановки. Конкретное значение алфавитной переменной записывается в блок 6 подстановки из обрабатываемого слова (), а затем - конкретный символ из блока-подстановки. Сначала сбрасывается счетчик блока 2 анализа вхождения (СбрСчВ5 1), что позволяет осущест0 вить доступ к конкретному символу слова-подстановки и записать его в блок 6 подстановки.

Рассмотрим работу устройства, если ПАР 1, т.е. сработала арифметическая фор5 мула нормального алгорифма. С помощью команд иТИ5: 1 в блок 6 подстановки из регистров подстановки блока 3 формирования слов вхождения и подставки дтп любой арифметической формулы записыва0 ется символ С, после чего на выходе реги- строе подстановки блока 3 устанавливается конкретный символ арифметической операции (+ соответствует ; - соответствует ; Соответствует), которые выставят единицу

5 на выходе одного из элементов И 61 - 63 блока 3 формирования слов вхождения и подстановки, что позволит обрабатываемому слову (разряды обрабатываемых чисел) из блока 7 через блок 4 просмотра поступать

0 в арифметический блок 1 на обработку, а уже с этого блока в виде результата поступать в блок 6 подстановки, причем в первом такте поступит нулевой результат. Если произойдет переполнение разрядной сетки, то

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

0 скобкой (признак П/ 1), то в следующем такте происходит обнуление триггера подстановки и на коммутатор 16 арифметического блока 1 подается единица (команда 1УК: 1), что позволяет отсоединить вход

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

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

Запись в блок 5 памяти формул осуществляется командой . В случае, если

П 0, проверяется признак ПЗФ 1 (форула заключительная). Если ПЗФ 0, то происходят сброс счетчика адреса СбрСчА: 1) и обнуление триггера подстановки, следующей будет выполняться первая формула нормального алгорифма.

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

На вход узла 17 числа подаются в зависимости от типа операции (Сложение или Вычитание) в естественном или перевернутом виде. Арифметический блок 1 включается в работу по условию срабатывания формулы подстановки. Обрабатываемое слово может состоять из символьной информации, каждый символ кодируется восемью битами знака операции (+, -, )- кодировка та же, что и у арифметической информации, записанной (два числа) в четырех верхних битах, затем идет закрывающая скобка, и снова может идти символьная информация. Рассмотрим пример - кодировка условная (таблица).

Код символов выбран так, что ни у одного символа не может быть четырех нулей в нижних четырех битах. Если на пятый управляющий вход блока 1 приходит, то коммутаторы 16 и 23 арифметического блока 1 пропускают информацию без изменения в блок 6 подстановки (арифметический блок 1 отключен), в противном случае - 1, четыре верхних бита (разряды двух чисел) поступают на коммутатор 22, вторая и третья строка меняются местами, т.е. подаются в виде Х+, Y4, Х, В таком случае, если на управляющем входе коммутатора 22 присутствует, то информация в таком же виде поступает на вход узла 17 (операция сложения), в противном случае (- 1) коммутатор 22 меняет местами положительную и отрицательную составляющие второго числа л , Y , X, Y+ (операция вычитания или сравнения по разности). Коммутатор 16 работает следующим образом, пока на первом или втором управляющем входе присутствует 1, в два верхних разряда (первая и вторая строка) поступает результат операции соответственно Z+, Z, все остальные разряды нулевые, затем эта информация поступает в блок 6 подстановки.

Операционные узлы 17-20 арифметического блока 1 строятся непосредственно на основе формул подстановок соответствующих алгорифмов.

0

Узел 17:

Х1+ YI

,+ XO+ЈYO+ + XoV YD j

f)

ХГ- I Yf Xo

где Xo , Yo , Yo, Xo - значения входов узла 17,

Узел 18: Y2+ Yf

Y2 - Yi V Yf

В

где Xi+, Yi+, YI , Xi - значения входов узла 18. Узел 19:

Y3+ Y2+Ј X2+

Y3 X2

+ T1vY2+ v ()

NT

M T3VY2 V(Y2+ST1) X3+ (T1 vf2)V() X3 (f3VT4)V()

гдеX2+, Y2+, Y2 X2,T1,T4,T2,ТЗ-значения входов узла 19;

T1, Т2, ТЗ и Т4 - соответствующие значения выходов узла (

Х2 , Y2 , Y2 , X2 - значения выходов узла 18.

Узел 20: Zi+ S+& S

Z S v S

D

где Ys+, Мз+, S+, S Мз , Ys - значения входов узла 20;

Z4+, Z/f - результирующий разряд суммы;

Y4+, Y4, MA+, M/f - счетные входы узла задержки.

После прохождения исходных операндов через операционные узлы 17-20 формируется результат в виде пооледовательности пар Z4 и Z, а первый значащий разряд результата выдается через один или два такта от момента поступления первых разрядов операнда. Появление значащего разряда результата на втором такте работы

означает возникновение переполнения, однако возникающее переполнение не может исказить результат.

Рассмотрим конкретную обработку на примере сложения. В результате вхождения

блока 4 просмотра находится символ +, как только встретится в слове символ +, блок 2 анализа вхождения выдаст сигнал ПВХ 1 и в триггер подстановки блока 7 буферной памяти будет записана 1, затем в блок б подстановки из регистров подстановки блока 3 формирования слов вхождения и подстановки поступит символ С, а на выходе этих регистров выставится символ конкретной операции, что позволит вклюить коммутаторы арифметического блока 1 на принятие разрядов чисел, после появления в информации символа ). Далее в течение двух тактов из арифметического блока 1 будут поступать два разряда числа, после чего в блок 6 подстановки будет записан символ ) и остаток слова начнет посту пать в блок б подстановки, Если первое число больше второго, то в результате операции сравнения на выходе блока 1 установится логическая единица (признак П 1).

Блок 2 анализа вхождения работает следующим образом.

В исходном состоянии (команда Сброс : 1) регистр 42 и счетчик 45 установлены в нулевое состояние. При поступ- лении в устройство очередной формулы подстановки нормального алгорифма на вход обнуления числа вхождений блока 2 анализа вхождения подается команда СбрСчВ: 1, устанавливающая счетчик 52 в нулевое состояние. Счетчик 45 считает число символов слова-вхождения, поступивших в блок 4 просмотра с тем, чтобы с помощью дешифратора 43 задать длину слова-вхождения для узлов 46 анализа, а также для блока 4 просмотра, Информация со счетчика 45 подается на входы элемента ИЛИ-НЕ 44, при ненулевом состоянии счетчика 45 выдается сигнал ПСЧВ: 0. Этот сигнал выдается на первый выход 1 данного блока. .С выхода счетчика 45 информация поступает на дешифратор 43, с выходов которого информация выдается на группу выходов блока 2.

Сдвигающий регистр 42 служит для приема последовательности символов слова- вхождения в соответствии с сигналом сдвига. При этом, если в слове-вхождении находится обычный текущий символ, то в регистр 42 записывается нуль, если - текущий символ V, кодирующий алфавитную переменную, то записывается единица. С выходов регистра 42 информация параллельно подается на каждый из восьми узлов 46 анализа. На первый узел 46 подаются результаты компарации первых битов каждых байтов слова-вхождения и обрабатываемого слова, а на восьмой узел 46 - восьмые биты. Кроме того, на входы всех узлов 46 поступает сигнал ПВХ как в случае, когда в работе простая формула нормального алгорифма, так и в случае формулы, содержащей алфавитные переменные, Сигнал формируется по сигналу ТИЗ тогда, когда сработают все элементы узлов 46 анализа и

поступит сигнал Конец вхождения, (HV0- 1). Сигнал ПВХ выдается с выхода элемента И 47, на входы которого поступает информация с выходов узлов 46 и П 1.

Блок 3 формирования слов вхождения и

подстановки работает следующим образом. Из блока 5 памяти формул через информационные входы блока 3 формирования слов вхождения и подстановки по сигналу ЧТФ

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

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

Служебный байт с признаками формулы: формула с алфавитными переменными (ПАП 1), формула заключительная (ПЗФ

5 1), последняя формула нормального алгорифма (ППФ 1). (ПАР 1), - арифметика записывается в регистр 52.

Информация с регистров вхождения и подстановки поступает последовательно, а

0 с регистра 52 - параллельно. Для первых восьми сдвигающих регистров, хранящих вхождение, используется команда сдвига , для следующих восьми регистров, хранящих подстановку, - команда сдвига ТИР.

5Элемент И 56 распознает символ в

слове-вхождении и выдает этот сигнал HVj на первый выход блока. Элемент ИЛИ-НЕ 57 распознает пустой Ьайт в конце слова-вхождения и выдает сигнал . Элемент И 58

0 распознает символ V в слове-подстановке и выдает сигнал Пр#. Элемен И 59 распознает символ-разделитель / в слове-подстановке и выдает сигнал ПР/. Элемент ИЛИ-НЕ 60 распознает пустой байт

5 (00000000) конца слова-подстановки и выдает сигнал ПР0,

Элемент И. 61 управляет операцией сло1- жения (символ во вхождении #), элемент И ti2 управляет операцией вычитания (символ

0 -), элемент И 63 управляет операцией сравнения (символ -), сравнение осуществляется операцией вычитания. Информация с выходов всех элементов И 61-63 поступает на входы элемента ИЛИ 66, а также на входы

5 элементов И 64, разрешая или запрещая выдачу подстановки на информационные выхоли второй группы. Информация с выходов элементов И 62 и 63 поступает на входы элемента ИЛИ 72, который управляет коммутатором 22 арифметического блока. С поощью элемента И 63 арифметический блок 1 информируется о том, что производится равнение чисел.

Блок 4 просмотра работает следующим бразом. На элементы ИЛИ 71 поступает нформация побайтно из блока 7 буферной амяти или из блока 3 формирования слов хождения и подстановки. Обрабатываемое лово с выходов элементов ИЛИ 71 и слово- хождение из блока 3 формирования слов вхождения и подстановки поступают на сответствующие входы узлов 69 обнаружения, на входы которой также поступает информация о длине-слова-вхождения мз блока 2 анализа вхождений. В сдвигающий регистр 73 поступают первые биты каждого байта слова-вхождения, а в регистр 75 - первые биты каждого байта обрабатываемого слова. Компараторы 74 осуществляют побитное сравнение содержимого этих регистров.

Последовательная выдача информации с регистра 75 происходит с той позиции, которая задается длиной слова-вхождения и определяется возбужденным выходом дешифратора 43 блока 2 анализа вхождения. Если возбужден выход дешифратора,который соответствует нулевому состоянию счетчика 75 блока 2 анализа вхождения, то обрабатываемое слово (его первый бит каждого байта для рассматриваемого варианта узла 69 обнаружения) не загружается в сдвигающий регистр 75, а через элементы И 77 и ИЛИ 78 идет в обход регистра, Блок 6 подстановки работает следующим образом.

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

Подсчет символов, поступающих в регистры блока, ведется счетчиком 81, когда подаются сигналы сдвига ТЕ/15. Таким образом, счетчик подсчитывает длину обрабатываемого слова, прошедшего обработку по одной формуле нормального алгорифма, Сигнал о том, что слово полностью поступило в блок 6 подстановки (), поступает с выхода элемента И 76. Если признак переполнения (ППЕР), снимаемый с выхода триггера 83, равен нулю, т.е. в триггере 83 не поступила логическая единица с элемента И 82, то работа продолжается, иначе блок 9 микропрограммного управления выдает сигнал Авар.ост.; 1 и устройство прекращает работу. Входы элемента И 82 подключены к выходам счетчика, фиксирующего

длину обрабатываемого слова. Информация с выходов регистров 80 поступает в блок 8 памяти слова и в блок 7 буферной памяти. Блок 7 буферной памяти работает следующим образом.

В исходном состоянии триггер 93 подстановки находится в нулевом состоянии, Регистр 85 используется для управления дешифратором 87, с помощью которого обес0 печивается поступление обрабатываемого слова (когда его длина меньше длины регистров, в которых оно находится) по сигналам сдвига (ТИ6: 1) в блок 4 просмотра. Обрабатываемое слово хранится в регистрах 88.

5 По сигналу обрабатываемое слово из блока 6 подстановки параллельно записывается в регистры 88, а код длины обрабатываемого слова по тому же сигналу записывается в регистр 85 (горизонтальный

0 срез по всем восьми одноименным разрядам представляет код символа). В том случае, когда слово из блока 8 памяти слова первый раз загружается в регистры 88, в регистре 85 будут нули (длина слова не хра5 нится в блоке 8 памяти слова) и чтобы организовать посимвольный выход его в блок 4 просмотра, используется элемент ИЛИ-НЕ 86, выход которого подключен к входам элементов ИЛИ 90. Единицы с выходов этих

0 элементов подаются на входы соответствующих элементов И 89, что позволяет открыть выходы регистров 88. Элементы И 92 работают в качестве ключей, разрешая или запрещая подачу символов на обработку.

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

1, Устройство для реализации подстановок, содержащее блок анализа вхождения, блок формирования слов вхождения и подстановки, блок просмотра, блок памяти

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

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

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

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

0 первого операционного узла подключен к вторым входам второго элемента И-НЕ и элемента ИЛИ-НЕ, выходы которых подключены соответственно к третьему и четвертому выходам первого операционного

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

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

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

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

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

L

операции число

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

подключены соответственно к первым входам элементов И с первого по (т-1)-й а-й группы и к первому входу а-го элемента ИЛИ первой группы, выход которого подключен к первому входу m-ro элемента И а-й

группы, выход элемента ИЛИ-НЕ подключен к вторым входам всех элементов ИЛИ первой группы, выходы элементов И а-й группы подключены соответственно к входам а-ro элемента ИЛИ второй группы, выход которого подключен к первому входу а-го элемента И девятой группы, выходы элементов И девятой группы подключены соответственно к выходам группы блока, третий и четвертый управляющие входы которого подключены соответственно к информационному входу и входу установки в О триггера подстановки, инверсный выход которого подключен к второму (прямому) входу элемента ИЛИ, выход которого подключей к вторым входам всех элементов И девятой группы, прямой выход триггера подстановки подключен к выходу блока, информационные входы с первого по восьмой второй группы которого подключены соответственно к информационным входам сдвигающих регистров с первого по восьмой, информационные аыходы с первого по m-й а-го сдвигающего регистра подключены соответственно к вторым входам элементов

И с первого по m-й а-й группы.

Фиг,

CDCi

Will

CKOM

4TP THV

t

п

L-TLJ 1

bjiso

4S

t

ш

С r

I