Устройство для реализации подстановок
Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано для обработки информационных потоков и массивов данных текстового и числового типов в соответствии с заданными нормальными алгорифмами . Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что устройство для реализации подстановок содержит арифметический блок, блок анализа вхождения, блок формирования слов вхождения и подстановки , блок просмотра, блок памяти формул , блок подставки, блок буферной памяти, блок памяти слов и блок микропрограммного управления. 2 з.п. ф-лы, 1 табл. 13 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (я)5 G 06 F 15/04, 9/44
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4735882/24 (22) 11.09,89 (46) 07.10.91. Бюл. (Ф 37 (71) Курский политехнический институт (72) В.M.Äîâãàëü, О.Ф.Корольков, Е.И.Леонов, Ф.А.Старков и С.С.Шевелев (53) 681.325 (088,8) (56) Авторское свидетельство СССР
М 1455345, кл. G 06 F 15/04, G 06 F 9/44, 1985, Авторское свидетельство СССР
N -1596345, кл. G 06 F 15/04, 1988. (54) УСТРОЙСТВО ДЛЯ PЕАЛИЗАЦИИ
ПОДСТАНОВОК
Изобретение относится к техническимсредствам информатики и вычислительной техники и может быть использовано для обработки информационных потоков и массивов данных текстового и числового типов в соответствии с заданным нормальным алгорифмом.
Цель изобретения — увеличение быстродействия.
На фиг. 1 представлена схема устройства; на фиг. 2- схема арифметического блока; на фиг. 3 — схема первого операционного узла арифметического блока; на фиг. 4— схема второго операционного узла арифметического блока; на фиг. 5 — схема третьего операционного узла арифметического блока; на фиг, 6 — схема четвертого операционного узла арифметического блока; на фиг, 7 — схема блока анализа вхождения; на фиг. 8 — схема узла анализа блока анализа вхожде. Ж 1683025 А1 (57) Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано для обработки информационных потоков и массивов данных текстового и числового типов в соответствии с заданными нормальными алгорифмами. Цель изобретения — повышение быстродействия устройства, Поставленная цель достигается тем, что устройство для реализации подстановок содержит арифметический блок, блок анализа вхождения, блок формирования слов вхождения и подстановки, блок просмотра, блок памяти формул, блок подставки, блок буферной памяти, блок памяти слов и блок микропрограммного управления. 2 з.п. ф-лы, 1 табл. 13 ил, ния; на фиг. 9 — схема блока формирования. слова вхождения и подстановки; на фиг, 10— схема блока просмотра; на фиг. 11 — схема узла обнаружения блока просмотра; на фиг.
12 — схема блока подстановки; на фиг, 13— схема блока буферной памяти.
Устройство для реализации подстановок содержит апи Ьметический блок 1, блок
2 анализа вхождения, блок 3 формирования слов вхождения и подстановки, блок 4 просмотра, блок 5 памяти формул, блок 6 подстановки, блок 7 буферной памяти, блок 8 памяти слова, блок 9 микропрограммного управления, Арифметический блок содержит первый элемент И 10, элемент НЕ 11., первый и второй триггеры 12 и 13, второй и третий элемент И 14 и 15, первый коммутатор 16, с первого по четвертый операционные узлы
1683025
17-20, узел 21 задержки, второй и тре ий коммутаторы 22 и 23.
Первый операционный узел 17 содержит первый элемент И вЂ” НЕ 24, элемент ИЛИ
25, элемент ИЛИ вЂ” НЕ 26 и второй элемент
И вЂ” НЕ 27. Второй операционный узел 18 содержит элемент И 28 и элемент ИЛИ вЂ” Н Е 29, Третий операционный узел 19 содержит первые элементы И 30, ИЛИ 31 и ИЛИ вЂ” HF
32, вторые элементы ИЛИ 33, И 34 и ИЛИН Е 35, третьи элементы И 36, ИЛИ 37, ИЛ Ив
HE 38 и четвертый элемент И 39, Четвертый операционный узел 20 содержит элементь. . И 40 и ИЛИ вЂ” НЕ 41.
Блок 2 анализа вхождения содержит сдвигающий регистр 42, дешифратор 43, элемент ИЛИ вЂ” НЕ 44, счетчик 45, узлы 46 анализа и элемент И 47, Каждый узел 46 анализа содержит элементы И 48 первой группы, элементы И 49 второй группы, элементы ИЛИ 50 группы и элемент ИЛИ 51, Блок 3 формирования слов вхождения и подстановки содержит регистр 52, сдвигающие регистры 53 первой группы, сдвигающие регистры 54 второй группы, элемен 55 задержки, первый элемент И 56, первый элемент ИЛИ вЂ” HE 57, второй и третий элементы И 58 и 59, второй элемент ИЛИ вЂ” НЕ
60, с четвертого по шестой элементы И 6163, группу элементов И 64, элемент ИЛИ 65, третий элемент ИЛИ вЂ” НЕ 66, элемент НЕ 67, седьмой элемент И 68.
Блок 4 просмотра содержит узлы 69 обнаружения, первый элемент И 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ц
Работа формулы подстановки над обрабатываемым словом заключается в обнаружении в нем слова-вхождения и замены позиции слова-вхождения словом-подстановкой. Важным моментом, проясняющим работу формулы подстановки, является последовательность позиции слова-вхождения в обрабатываемом слове.
Позиция вхождения является первой, если при просмотре обрабатываемого слова вхождение обнаружено первый раз. Если признак формулы д = 1, то формула называется заключительной. Она работает один раз, и нормальный алгорифм,представляющий собой конечный список формул подстановки, прекращает свою работу. Если признак формулы д=- 0, то формула называется неэакл1очительной.и используется в работе столько оаз, сколько раз обнаруживается вхождение.
В работе нормального алгорифма, когда число формул в нем больше, чем од !a, устанавливается регламент работы каждой формулы подстановки. Если формула в списке незначительная, то при обнаружении первой позиции вхождения осуществляется подстановка, а переход выполняется на первую формулу. Следующая формула подстановки нормального алгорифма вкл1очается в работу тогда, когда предыдущая формула подстановки не обнаруживает ни одной собственной позиции вхождения при полном просмотре всего обрабатываемого слова, Далее рассматривается такая разновидность нормальных алгорифмов, для графической записи которой используются сокращенные формулы. Сокращенные формулы графической записи осугцествляются с использованием алфавитных переменных, принимающих значение любой буквы того алфавита, которому принадлежат буквы обрабатываемого слова, слова-вхождения v слова-подстановки.
Арифмети .еский блок служит для обработки арифметической информации, где обработка чисел, заданных в знакора р;дной системе, выдается cTBpLLINMM разря Г,ами вперед, кроме того, он может осуществить операци.о сравнения на больше или меньше и равно.
Блок анализа вхождения служит для обработки результатов сравнения на равенство символов вхождения (левой части формулы подстановки1 и фрагмента обрабатываемого слова, Анализируя результат компарации, блок анализа вхождения выдает сигнал о наличии вхождении в обрабаты"-аемом слове в тех случаях, когда имеются на обработке формулы, которые содержат
1683025 алфавитные переменные и которые их не содержат. Кроме того, блок анализа вхождения задает условия обмена информацией между блоком просмотра и блоком подстановки.
Блок формирования слов вхождения и подстановки по команде блока микропрограммного управления принимает параллельно формулы подстановки, формат, который содержит слово-вхождение, словоподстановку, признаки о наличии в формуле алфавитной переменной, признак о заключительности формулы (формула используется только один раз, если имеется вхождение), признак о том, что данная формула является последней в списке формул данного нормального алгорифма, и признак арифметики. Каждая формула подстановки является элементом нормального алгорифма. Блок формирования слов вхождения и подстановки по команде сдвига из блока микропрограммного управления выдает последовательно по символам слово-вхождение и слово-подстановку в блок просмотра, а также в блок буферной памяти. Кроме того, этот блок выдает значения приведенных признаков формулы подстановки в блок управления, а также признаки конца словавхождения и слова-подстановки, а в блок анализа вхождения выдает значения признаков о конце слова-вхождения и о наличии в слове-вхождении алфавитной переменной, закодированной специальным. символом " ", и управляет арифметическим блоком, Блок просмотра служит для организации просмотра обрабатываемого слова последовательно по фрагментам, равным по длине слову вхождения, при этом осуществляется компарация на равенство выделенного фрагмента обрабатываемого слова и слова-вхождения. В том случае, когда слововхождение имеет в своем составе специальный символ "м", кодирующий алфавитную переменную, компаратор на равенство выдает сигнал "Не равно", но этот сигнал интерпретируется как символьное совпадение в блоке анализа вхождения. Всякий не совпадающий символ, эа исключением указанного случая, передается в блок подстановки и синхронно, в соответствии с длиной слова-вхождения, очередной символ обрабатываемого слова подается в выставленное поле компарации. В случае обнаружения вхождения вместо символов обрабатываемого слова в блок подстановки подается слово-подстановка или те символы обрабатываемого слова, которые соответствуют алфавитным переменным в той последовательности, которая определяется специально организованной формой слова-подстановки, если в ней содержатся алфаг тные переменные.
Блок подстановки служит для хранения
5 промежуточных фрагментов обрабатываемого слова или результирующего обрабатываемого слова с тем, чтобы процесс просмотра обрабатываемого слова с целью обнаружения вхождения и процесс подста10 новки в соответствии с заданной формулой подстановки осуществлялись непрерывно.
Блок буферной памяти предназначен для хранения и выдачи обрабатываемого слова при его обработке по очередной фор15 муле, а также для задержки слова до тех пор, пока идет подстановка.
Для описания алгоритма работы блока управления используются следующие обозначения:
20 УОΠ— установка исходного состояния;
"Пуск" — команда запуска устройства;
ЧТС вЂ” команда чтения обрабатываемого слова из блока памяти слов;
ЧТФ вЂ” команда чтения формулы из бло25 ка памяти формул;
ЧЗ вЂ” команда, разрешающая запись слова иэ блока подстановки в блок буферной памяти;
ТИЗ вЂ” команда сдвиа для сдвигающих
30 регистров блока вхождения и слов в блоке анализа вхождения;
ТИ5 — команда сдвига в блоке подстановки;
ТИЧ вЂ” команда сдвига содержимого
35 сдвигающих регистров вхождения блока просмотра, блока анализа вхождения, блока формирования слов вхождения и подстановки;
ТИ6 — команда сдвига в регистрах блока
40 буферной памяти;
+1Сч — команда увеличения на единицу счетчика блока анализа вхождения;
СбрСч — команда сброса счетчика блока анали-а вхождения;
45 ТИ Р вЂ” команда сдвига для сдвигающих регистров слова-подстановки в блоках вхождения и под.-.,тановки формирования слов;
ПЧф- признак конца слова-вхождения;
50 ПРф- признак конца слова-подстановки
ПВХ вЂ” признак наличия вхождения;
ПКС1 — признак конца обрабатываемого слова в блоке просмотра;
55 ПКС2 — признак конца обрабатываемого слова в блоке подстановки;
ППЕР— признак переполнения разрядной сетки в блоке подстановки;
ППФ вЂ” признак последней формулы в нормальном алгорифме;
1683025
ПЗФ вЂ” признак заключительной формуАвар.ост, — команда аварийной остановки устройства;
СбрСчА — команда сброса в нуль счетчи- 5 ка адреса блока памяти формул;
+1СчА — команда увеличения на единицу счетчика адреса блока памяти формул;
ПР* — признак наличия символа "Х2" в слове-подстановке; 10
ПР— признак символа разделителя в слове-подстановке;
ПСч — признак ненулевого состояния счетчика в блоке анализа вхождения;
ITrP — команда записи единицы в триг- 15 гер подстановки, ОбТгР— команда установки в нуль триггера подстановки;
П/ — признак наличия скобки в обрабатываемом слове; 20
ПАР— признак арифметической команды;
СБрСчб — команда установки в нуль счетчика блока подстановки;
ЗСП вЂ” команда записи обрабатываемо- 25
ro слова в блок памяти слова;
"Стоп" — кома нда остановки устройства, "Сброс" — команда установки исходных состояний;
П > — признак того, что при сравнении 30 первое число больше второго;
СбрТгА — команда обнуления арифметического блока;
1УК вЂ” команда управления коммутатором в арифметическом блоке; 35
ТИА — тактовые сигналы для арифметического блока.
По сигналу "Сброс": = 1 все элементы устройства с памятью устанавливаются в исходное состояние, По сигналу "Пуск"; = 1 40 устройство начинает работать. По сигналу
ЧТС: = 1 осуществляется запись обрабатываемого слова по всей длине из блока памяти слова 8 в блок 6 подстановки. 8 следующем такте работы по команде ЧТф = 45
1 параллельно считывается формула по всей длине в блок 3 формирования слов-вхождения и подстановки, и одновременно по команде V3: = 1 обрабатываемое слово из блока 6 подстановки параллельно перепи- 50 сывается в регистры блока 7 буферной памяти.
В следующих тактах подаются команды сдвига на блок 4 просмотра и блок 2 анализа вхождения ТИЗ: = 1, на блок 7 — ТИ6: = 1, 55 блок 2 анализа вхождения и блок 4 просмотра — ТИЧ: = 1, одновременно подсчитывается количество символов слова-вхождения по команде +1СчВ: = 1 в блоке 2 анализа вхождения до тех пор, пока не обнаружится признак конца слов-вхождений (ПФ= 1), что позволяет загрузить блок 4 просмотра,словом-вхождением и равным ему по длине фрагментом обрабатываемого слова, Если ПВХ = 0 (вхождения нет), то в блоке
20 формируются команды сдвига и обрабатываемое слово продолжает поступать из блока 7 через блок 4 просмотра в блок 6 подстановки, при этом в блоке 6 подстановки ведется подсчет подступающих символов обрабатываемого слова. Символы обрабатываемого слова поступают в блок 6 подстановки в обход тех разрядов регистров блока
4 просмотра, которые не входят в зону компарации, определяемую длиной вхождения.
Команды сдвига формируются до тех пор, пока не будет обнаружено вхождение (ПВХ = 1) или не будет обнаружен в зоне компарации блока 4 просмотра конец обрабатываемого слова (ПКС1 = 1), Если вхо>кдение не обнаружено по всей длине обрабатываемого слова, то далее проверяется, не является ли формула последней в нормальном алгорифме (ППФ = 1, блок 22), Обрабатываемое слово продолжает загружаться в блок 6 подстановки до тех пор, пока в нем не будет обнаружен признак конца обрабатываемого слова ПКС2=1. В этом случае обрабатываемое слово параллельно заносится в блок 8 памяти слова, В том случае, когда формула не является последней в нормальном алгорифме(ППФ =
О), то в счетчик адреса блока 5 памяти формул прибавляется единица (+1СчА: = 1), После этого считывается очередная формула, а обрабатываемое слово продолжает загружаться в блок 6 подстановки до тех пор, пока в нем не будет обнаружен конец слова (П КС2=1).
После загрузки обрабатываемого слова в блок 6 подстановки проверяется признак переполнения (ППЕР=1), в этом случае формируется команда аварийной остановки устройства (ABBp.Îñò,;= 1) и устройство прекращает работу, В следующем такте обнуляется с етчик блока 6 подстановки (команда СбрСчб:=1), Далее проверяется признак конца словавхождения очередной формулы нормального алгорифма. Если П ф= 1 (формула имеет пустое слово-вхождение, а такая формула не может встретиться в начале нормального алгорифма), то в начало обрабатываемого слова на место первого пустого символа ставится слово-подстановка и считывается первая формула нормального алгорифма. По команде 1TrP:=1 в триггер подстановки записывается единица и одновременно происходит сброс счетчика адреса формулы
СбрСчА;=1, что позволяет записать подста1683025
10 новку иэ блока 3 формирования слов вхождения и подстановки в блок 6 подстановки.
В следующем такте командами сдвига
ТИР:=1 и ТИ5.=1 слово-подстановка загружается в блок 6 подстановки до тех пор, пока не будет обнаружен конец слова-подстановки (ПРф= 1). После этого считывается первая формула нормального алгорифма
ЧТ. =1, а также сбрасывается в нуль триггер подстановки ОбТрГ:=1.
Рассмотрим работу алгоритма блока 9 микропрограммного управления при переходе по условию ПВХ = 1 (вхождение обнаружено). В этом случае устанавливается в единицу триггер подстановки, чтобы блокировать поступление последующей части слова иэ буфера 7, и сбрасывается счетчик блока 2 анализа вхождения (Т1гР,:=1, СбрСчВ:=1). После этого определяется тип подстановки для классической схемы или для схемы нормального алгорифма, содержащего в текущей формуле алфавитные переменные, или признак арифметической обработки.
Рассмотрим случай, когда ПАП=)Ф и
ПАР=О, алфавитные переменные отсутствуют и операция не арифметическая. В этом случае слово-подстановка будет посимвольно записываться напрямую через блок 4 просмотра и арифметический блок 1 в блок
6 подстановки с помощью команд ТИР;=1, ТИ Р:=1 до тех пор, пока не будет обнаружен конец слова-подстановки (ПР =1)., В том случае, когда ПАП=1, осуществляется проверка наличия символов Ц, кодирующих в слове подстановки алфавитные переменные, Если эти символы присутствуют (s начале слова-подстановки), то осуществляется их подсчет с помощью счетчика блока 2 анализа вхождения и одновременно происходит сдвиг слова-подстановки в блоке 3 формирования слова вхождения и подстановки (+ 1Сч8;= 1, ТИР:= 1). Цикл выполняется до тех пор, пока не закончится последовател ьность символов .
После завершения цикла проверяется наличие в слове-подстановке символа-разделителя "/" или конкретного символа. В том случае, когда символ-разделитель обнаруживается ПР/=1, то выполняются команды ТИ5;=1, ТИР:= 1, с помощью которых конкретное значение алфавитной переменной переписывается из регистров слова блока 4 просмотра (к конкретному значению доступ получен с помощью счетчика и дешифратора блока 2 анализа вхождения) в блок 6 подстановки и выполняется сдвиг на одну позицию в регистрах подстановки блока 3 формирования слова-вхождения и подстановки. Если в слове-подстановке
55 конкретный символ первый, то осуществляется запись этого символа из регистров подстановки в блок 6 подстановки, Конкретное значение алфавитной переменной записывается в блок 6 подстановки из обрабатываемого слова (ТИ5:=1), а затем — конкретный символ из блока-подстановки. Сначала сбрасывается счетчик блока 2 анализа вхождения (СбрСчВ5=1), что позволяет осуществить доступ к конкретному символу слова-подстановки и записать его в блок 6 подстановки.
Рассмотрим работу устройства, если
ПАР =1, т.е. сработала арифметическая формула нормального алгорифма. С помощью команд ТИР:=1 и ТИ5:=1 в блок 6 подстановки из регистров подстановки блока 3 формирования слов вхождения и подставки для любой арифметической формулы записывается символ "С", после чего на выходе регистров подстановки блока 3 устанавливается конкретный символ арифметической операции (+ соответствует, — соответствует ?;
>соответствует,), которые выставят единицу на выходе одного из элементов И 61 — 63 блока 3 формирования слов вхождения и подстановки, что позволит обрабатываемому слову (разряды обрабатываемых чисел) из блока 7 через блок 4 просмотра поступать в арифметический блок 1 на обработку, а уже с этого блока в виде результата поступать в блок 6 подстановки, причем в первом такте поступит нулевой результат, Если произойдет переполнение разрядной сетки, то во втором такте будут значащие цифры. Без переполнения, начиная с третьего такта, будут поступать значащие разряды результата, Если следующий символ в обрабатываемом слове является заключительной скобкой (признак П/ = 1), то в следующем такте происходит обнуление триггера подстановки и на коммутатор 16 арифметического блока 1 подается единица (команда
1УК; = 1), что позволяет отсоединить вход арифметического блока 1 от обрабатываемого слова, но оставить выход его соединенным с блоком 6 подстановки и в следующих двух тактах выпустить еще два разряда результата. После этого заключительная скобка из обрабатываемого слова поступит в блок 6 подстановки. Если признак П > равен единице (а это может произойти, если выполнялась операция сразнения и первое число больше второго}, то осуществляется переход по адресу, который хранится во втором и третьих разрядах регистров подстановки в блоке 3 формирования слов вхождения и подстановки, Запись в блок 5 памяти формул осуществляется командой ЧИ;=1. В случае, если
1683025
П > = О, проверяется признак ПЗФ = 1 (формула заключительная). Если ПЗФ - О, то происходят сброс счетчика адреса (СбрСчА:=1) и обнуление триггера подстановки, следующей будет выполняться пер- 5 вая формула нормального алгорифма.
Работа арифметического блока 1 в двоичной энакоразрядной системе счисления, который представляет собой результат аппаратной поддержки нормального ал- 10 горифма сложения, заключается в преобразовании чисел с помощью операционных узлов. 17 — 20 и узла 21 задержки.
На вход узла 17 числа подаются в зави- 15 симости от типа операции (" Сложение" или
"Вычитание" ) в естественном или перевернутом виде. Арифметический блок 1 включается в работу по условию срабатывания формулы подстановки. Обрабатываемое 20 слово может состоять из символьной информации, каждый символ кодируется восемью битами знака операции (+, —, >) — кодировка та же, что и.у арифметической информации, записанной (два числа) в четырех верхних 25 . битах, затем идет закрывающая скобка, и снова может идти символьная информация.
Рассмотрим пример — кодировка условная (таблица).
Код символов выбран так, что ни у одно- 30 го символа не может быть четырех нулей в нижних четырех битах. Если на пятый уп равляющий вход блока 1 приходится то коммутаторы l6 и 23 арифметического блока 1 пропускают информацию без изменения в 35 блок 6 подстановки (арифметический блок 1 отключен), в противном случае — "1", четыре верхних бита (разряды двух чисел) поступают на коммутатор 22, вторая и третья строка меняются местами, т,е. подаются в виде Х, 40
У, Х, У; В таком случае, если на управляющем входе коммутатора 22 присутствует@ то информация в таком же виде поступает на вход узла 17 (операция сложения), в противном случае (- "1") коммутатор 22 меняет 45 местами положительную и отрицательную составляющие второго числа Х, Y Х, Y (операция вычитания или сравнения по разности). Коммутатор 16 работает следующим образом, пока на первом или втором управ- 50 ляющем входе присутствует "1", в два верхних разряда (первая и вторая строка) поступает результат операции соответственно 2, Z, все остальные разряды нулевые, затем зта информация поступает в блок 55
6 подстановки.
Операционные узлы 17 — 20 арифметического блока 1 строятся непосредственно на основе формул подстановок соответствующих алгорифмов, Узел 17: X> = Хо Уо А, У1 = Хо Уо
X»
17, Узел 18: У2 = Y< К У1
В
Уг =Y> v Yl где Х1, У1, У1, Х1 — значения входов узла
18.
Узел 19;
УЗ = У23 Х2
УЗ = Y2 g Х2
М = Т1 Уг (Y2 Я Т4)
= ТЗ гУг v(Y2+QТ1)
Хз = (Т1 vТ2)v/(Y2 Я=Т1)
Хз =(ТЗ VТ4) ъ (Y2 gТ4) где Х2, У2, У2, Хг, Т1, Т4, Т2, ТЗ вЂ” значения входов узла 19;
Т1, Т2, Т3 и Т4 — соответствующие значения выходов узла 21, Х2, У2, У2, X2 — àíàчения выходов узла 18.
Узел20: Z4 =S RS
24 =ЯvЯ где Уз+, Мз+, S, S Мз, Уз — значения входов узла 20;
Z4+, Z4 — результирующий разряд суммы;
У4, У4, М4, М4 — счетные входы узла задержки.
После прохождения исходных операндов через операционные узлы 17 — 20 формируется результат в виде по ледовательности пар Z и Г, а первый значащий разряд результата выдается через один или два такта от момента поступления первых разрядов операнда. Появление значащего разряда результата на втором такте работы означает возникновение переполнения, однако возникающее переполнение не может исказить результат.
Рассмотрим конкретную обработку на примере сложения. В результате вхождения блока 4 просмотра находится символ "+", как только встретится в слове символ "+", блок 2 анализа вхождения выдаст сигнал
ПВХ = 1 и в триггер подстановки блока 7 буферной памяти будет записана "1", затем в блок 6 подстановки из регистров подста13
1683025 новки блока 3 формирования слов вхождения и подстановки поступит символ С, а на выходе этих регистров выставится символ конкретной операции, что позволит включить коммутаторы арифметического блока 1 на принятие разрядов чисел, после появления в информации символа ")". Далее в течение двух тактов из арифметического блока 1 будут поступать два разряда числа, после чего в блок 6 подстановки будет записан символ ")" и остаток слова начнет поступать в блок 6 подстановки, Если первое число больше второго, то в результате операции сравнения на выходе блока 1 установится логическая единица (признак П > = 1).
Блок 2 анализа вхождения работает следующим образом.
В исходном состоянии (команда
"Сброс": = 1) регистр 42 и счетчик 45 установлены в нулевое состояние. При поступ пении в устройство очередной формулы подстановки нормального алгорифма на вход обнуления числа вхождений блока 2 анализа вхождения подается команда
СбрСчВ; = 1, устанавливающая счетчик 52 в нулевое состояние. Счетчик 45 считает число символов слова-вхождения, поступивших в блок 4 просмотра с тем, чтобы с помощью дешифратора 43 задать длину слова-вхождения для узлов 46 анализа, а также дпя блока 4 просмотра, Информация со счетчика 45 подается на входы элемента
ИЛИ вЂ” НЕ 44, при ненулевом состоянии счетчика 45 выдается сигнал ПСОВ; = О. Этот сигнал выдается на первый выход 1 данного блока..С выхода счетчика 45 информация поступает на дешифратор 43, с выходов которого информация выдается на группу выходов блока 2.
Сдвигающий регистр 42 служит дпя приема последовательности символов словавхождения в соответствии с сигналом сдвига. При этом, если в слове-вхождении находится обычный текущий символ, то в регистр 42 записывается нуль, если — текущий символ " ", кодирующий алфавитную переменную, то записывается единица, С выходов регистра 42 информация параллельно подается на каждый из восьми узлов
46 анализа. На первый узел 46 подаются результаты компарации первых битов каждых байтов слова-вхождения и обрабатываемого слова, а на восьмой узел 46 — восьмые биты. Кроме того, на входы всех узлов 46 поступает сигнал ПВХ как в случае, когда в работе простая формула нормального апгорифма, так и в случае формулы, содержащей алфавитные переменные, Сигнал ПВХ=1 формируется по сигналу ТИЗ тогда, когда сработают все элементы узлов 46 анализа и
55 поступит сигнал "Конец вхождения", (OVP=
=1), Сигнал ПВХ выдается с выхода элемента И 47, на входы которого поступает информация с выходов узлов 46 и BVP= 1.
Блок 3 формирования слов вхождения и подстановки работает следующим образом.
Из блока 5 памяти формул через информационные входы блока 3 формирования слов вхождения и подстановки по сигналу ЧТФ на восемь сдвигающих регистров 53 поступает слово-вхождение, так что первые биты каждого байта, кодирующего символ этого слова, подаются на первый сдвигающий регистр 53, а, соответственно, восьмые биты каждого байта — на восьмой сдвигающий регистр 53, Таким образом, вертикальный срез сдвигающих регистров 53 дает один байт, соответствующий одному символу, Аналогично информация подгетсл на восемь сдвигающих регистров 53, куда записывается слово-подстановка, Служебный байт с признаками формулы; формула с алфавитными переменными (ПАП = 1), формула заключительная (ПЗО =
=1), последняя формула нормального апгорифма (ППФ = 1)Я (ПАР = 1), — арифметика записывается в регистр 52.
Информация с регистров вхождения и подстановки поступает последовательно, а с регистра 52 — параллельно. Для первых восьми сдвигающих регистров, хранящих вхождение, используется команда сдвига
ТИЧ, длл следующих восьми регистров, хранящих подстановку, — команда сдвига ТИР.
Элеменг И 56 распознает символ "%" в слове-вхождении и выдает этот сигнал ПЧМ на первый выход блока. Элемент ИЛИ вЂ” НЕ 57 распознает пустой Оайт в конце слова-вхождения и выдает сигнал flVP . Элемент И 58 распознает символ " " в слове-подстановке и выдает сигнал Прх. Элемент И 59 распознает символ-разделитель "i" в слове-подстановке и выдает сигнал ПР/. Элемент
ИЛИ вЂ” HE 60 распознает пустой байт (00000000) конца слова-подстановки и выдает сигнал ПРф.
Элемент И 61 управляет операцией спо" женил (симвоп вс вхождении Ф), элемент И
62 управляет операцией вычитания (симвоп
-?), элемент И 63 управляет операцией сравнения (симвоп — !), сравнение осуществляетсл операцией вычитания. Информация с выходов всех элементов И 61 — 63 поступает на входы элемента ИЛИ 66, а также на входы элементов И 64, разрешая или запрещая выдачу подстановки на информационные выходы второй группы. Информация с выходов эпе..ентов И 62 и 63 поступает на входы элек.в та ИЛИ 72, который управляет коммута-с ром 22 арифметического блока. С по1683025 мощью элемента И 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, ко да подаются сигналы сдвига ТИ5. Таким образом, счетчик подсчитывает длину обрабатываемого слова, прошедшего обработку по одной формуле нормального алгарифма, Сигнал о том, что слава полностью поступило в блок 6 подстановки (ПКС2=1), поступает с выхода элемента И 76, Если признак переполнения (П ПЕР), снимаемый с выхода триггера 83, равен нулю, т.е. в триггере 83 не поступила логическая единица с элемента И
82, то работа продолжается, иначе блок 9 микропрограммного управления выдает сигнал Авар,ост,; = 1 и устройство прекращает работу. Входы элемента И 82 подключены к выходам счетчика, фиксирующего
w0
51 длину обрабатываемого слова. Информация с выходов регистров 80 поступает в блок 8 памяти слова и в блок 7 буферной памяти.
Блок 7 буферной памяти работает следующим образом.
В исходном состоянии триггер 93 подстановки находится в нулевом состоянии, Регистр 85 используется для управления дешифратором 87, с помощью которого обеспечивается поступление обрабатываемого слова (когда его длина меньше длины регистров, в которых оно находится) по сигналам сдвига (ТИ6: = 1) в блок 4 просмотра, Обрабатываемое слово хранится в регистрах 88.
По сигналу V3=1 обрабатываемое слово из блока 6 подстановки параллельно записывается в регистры 88, а код длины обрабатываемого слова по тому же сигналу записывается в регистр 85 (горизонтальный срез по всем восьми одноименным разрядам представляет код символа). В том случае, когда слово иэ блока 8 памяти слова первый раз загружается в регистры 88, в регистре 85 будут нули (длина слова не хранится в блоке 8 памяти слова) и чтобы организавать посимвольный выход его в блок 4 просмотра, используется элемент ИЛИ-НЕ
86, выход которого подключен к входам элементов ИЛИ 90, Единицы с выходо: этих элементов подаются на входы соответствующих элементов И 89, что позволяет GT крыть выходы регистров 88. Элементы И 92 работают в качестве ключей, разрешая или запрещая подачу символов на обработку, Формула изобретения
1. Устройство для реализации падстановак, содержащее блок анализа вхождения, блок формирования слов вхождения и подстановки, блок просмотра, блок памяти формул, блок подстановки и блок микропрограммного управления, а т л и ч а ю щ е ; с я тем, что, с цель,а увеличения быстродействия, оно содержит арифметический блок и блок буферной памяти, причем вход начальной установки устройства и вход запуска устройства подключены соотвегственно к входу начальной установки и входу запуска блока микропрограммного управления, первый выход каторога подключен к выходу призна.<а аварийной остановки устройства, выходы первой группы блока подстановки подключены соответственно к информационным входам блока памяти слова, выходы которого подключены соответственно к информационным входам первой группы блока подстановки, выходы первой и второй групп блока формирования слов вхождения и подстановки подключены соответственно к информационным входам первой и второй групп блока просмотра, выходы первой
1683025
18 группы которого подключены соответственна к информационным входам блока анализа вхождения, выходы группы которого подключены соответственно к информационным входам третьей группы блока просмотра, первый и второй выходы которого подключены соответственно к первому и второму входам режима блока микропрограммного управления, второй выход которого подключен к первому входу синхронизации блока просмотра и первому входу синхронизации блока анализа вхождений, первый и второй выходы которого подключены соответственно к третьему и четвертому входам режима блока микропрограммного управления, третий и четвертый выходы которого подключены соответственно к входу увеличения числа вхождений и входу обнуления числа вхожде, ний блока анализа вхождений, выходы третьей группы блока формирования слов вхождения и подстановки подключены соответственно к адресным входам блока памяти формул, выходы которого подключены соответственно к информационным входам блока формирования слов вхождения и подстановки, выходы с первого по восьмой которого подключены соответственно к первому управляющему входу блока анализа вхождений и входам режима ". пятого па одиннадцатый блока микропрограммного управления, девятый выход блока формирования слов вхождения и подстановки подключен к второму управляющему входу блока анализа вхождений v, двенадцатому входу режима блока микропрограммного управления., пятый и шестой выходы катарога подключены соответственно к первому входу синхронизации блока формирования слов вхождения и подстановки и входу записи блока памяти слова, седьмой выход блока микропрограммного управления подключен к первому управляющему входу блока формирования слов вхождения и подстановки и входу чтения блока памяти формул, восьмой, девятый и десятый выходы блока микропрограммного управления подключены соответственна к входу инкремента адреса, входу обнуления адреса и входу синхронизации блока памяти формул, одиннадцатый и двенадцатый выходы блока микропрограммного управления подключены соответственнс к первому и второму управляющим входам арифметического блока, выход которого подключен к тринадцатому входу режима блока микропрограммного управления, тринадцатый выход которого подключен к входу синхронизации арифметического блока, выходы группы которого подключены соответственна к информаци5
55 онным входам ВТороА группы блока подстановки, первый и второй выходы которого подключены соответственно к четырнадца тому и пятнадцатому входам режима блока микропрограммного управления, четырнадцатый и пятнадцатый выходы которого подключены соответственно к первому управляющему входу и входу синхронизации блока подстановки, выходы второй группы которого подключены соответственно к информационным входам первой группы блока буферной памяти, выходы группы которого подключены соответственно к информационным входам четвертой группы блока просмотра, выходы второй группы которого подключены соответственно к информационным входам группы арифметического блока; шестнадцатый выход блока микропрограммного управления подключен к второму управляющему входу блока подстановки и входу чтения блока памяти слава, выходы третьей группы которого подключены соответственно к информационным входам второй группы блока буферной памяти, выход котарага подключен к второму управляющему входу блока формирования слов вхождения и подстановки, десятый, одиннадцатый, двенадцатый и тринадцатый выходы которога падкл ачены соответственно к первому уп рОавляющему входу блока буферной памя-и, третьему, четвертому и пятому управляющ :м входам арифметического блока, с сел надцатога па двадцатый выходы блока ми.:,. О и рог раммного управления подключены соответственна к второму управляющему входу, входу синхронизации, третьему управля ющему входу и четвертому управляюгцему входу блока буферной памяти, двадцать первый выход блока микропраграммнага управления подключен к второму входу синхронизации блока формирования слав вхождения и подстановки, второму входу синхронизации блока просмотра и второму входу синхронизациии блока анализа вхождения, 2, ) страйства па и. 1, а т л и ч а ю щ е ес я тем, чта арифметический блок содержит с первого по четвертый операционные узлы, " en ".адержки, "п,е.рвого па третий коммутаторы, первый и второй три гери, с первого
ПО трЕтий ЭЛЕМЕНТЫ И И ЭЛЕл".Ент НЕ, ПрИ этом вход синхронизации и геааый управляющий вход блока падкл аченн соответственна к входу синхронизации узла задержки и первому уп ра ел я гащему входу первого коммутатора, выход..! ка-араго подключены соответственно . . в:.-,1ха,:;ам группы блока, второй управляющ",: в>:Од которого подключен к входам уста-:анки в "0" узла задержки, первого и второго три Герав, пря1683025
ЗО
35 мые выходы которых подключены соответственно к первому входу первого элемента
И и входу элемента НЕ, выход которого подключен к второму входу первого элемента И, выход которого подключен к выходу блока, инверсные выходы первого и второго триггеров подключены соответственно к первым входам второго и третьего элементов И, выходы которых подключены соответственно к информационным входам второго и первого триггеров, третий управляющий вход блока подключен к упоавляющему входу второго коммутатора, выходы с первого по четвертый которого подключены соответственно к информационным входам с первого по четвертый первого операционного узла, выходы с первого по четвертый которого подключены к первому информационному входу третьего операционного узла, к первому информационному входу второго операционного узла, второму информационному входу второго операционного узла и второму информационному входу третьего операционного узла, первый и второй выходы второго операционного узла подключены соответственно к третьему и к четвертому информационному входам третьего операционного узла, выходы с первого по шестой которого подключены соответственно к первому и второму информационным входам узла задержки, к первому и второму информационным входам четвертого операционного узла, к третьему и четвертому информационным входам узла задержки, первый выход четвертого операционного узла подключен к второму входу третьего элемента И и первому информационному входу первой группы первого коммутатора, второй выход четвертого операционного узла подключен к второму входу второго элемента И и второму информационному входу первой группы первого коммутатора, выхсды с первого по четвертый узла задержки подключены cooTBBTGTвенно к информационным входам с пятого по восьмой третьего операционного узла, четвертый управляющий вход блока подключен к третьему входу первого элемента
И, пятый. управляющий вход блока подключен к второму управляющему входу первого коммутатора и управляющему входу третьего коммутатора, выходы первой и второй групп которого подключены соответственно к информационным входам второй группы первого коммутатора и информационным входам второго коммутатора, с первого по четвеотый информационные входы группы блока подключены соответственно к информационным входам с первого по че1вертый третьего коммутатора, информационные входы с пятого по восьмой группы блока подключены соответственно к информационным входам с первого по четвертый третьей группы первого коммутатора, при этом первый операционный узел содержит первый и второй элементы И-НЕ, элемент
ИЛИ вЂ” НЕ и элемент ИЛИ, причем первый информационный вход первого операционного узла подключен к первым входам первого элемента И вЂ” НЕ и элемента ИЛИ, выходы которых подключены соответственно к первому и второму выходам первого операционного узла, второй информационный вход которого подключен к вторым входам.первого элемента И-НЕ и элемента
ИЛИ, третий информационный вход первога операционного узла подключен к первым входам второго элемента И вЂ” НЕ и элемента
ИЛИ-НЕ, четвертый информационный вход первого операционного узла подключен к вторым входам второго элемента И вЂ” НЕ и элемента ИЛИ вЂ” НЕ, выходы которых подключены соответственно к третьему и четвертому выходам первого операционного узла, при этом второй операционный узел содержит элемент И и элемент ИЛИ вЂ” НЕ, причем первый информационный вход второго операционного узла подключен к первым входам элемента И и элемента
ИЛИ вЂ” НЕ, выходы которых подключены соответственно к первому и второму выходам второ о операционного узла, второй информационный вход которого подключен к ВТо рым входам элемента И и элемента
ИЛИ вЂ” НЕ, при этом третий операционный узел содержит с первогс по четвертый элементы И, с первого потретий элементы ИЛИ и с первого по третий элементы ИЛИ вЂ” НЕ, причем первый информационный вход третьего операционного узла подключен к первому входу первого элемента И, выход которого подключен к первому выходу третьего операционного узла, второй информационный вход третьего опарацион:oго узла подключен к первому входу второго элемента И, третий информационный вход третьего операционного узла подключен к первому входу третьего элемента И, к первому входу первого элемента ИЛИ и второму входу первого элемента И, четвертый информационный вход третьего операционного узла подключен к первому входу четвертого элемента И, к первому входу второго элемента ИЛИ и второму входу второго элемента И, пятый информационный вход третье-о операционного узла подключен к первому входу перього элемента
ИЛИ вЂ” НЕ, к второму входу первого элемента
ИЛИ и второму входу третьего элемента И, выход которого подключен к первому входу
1683025
20
30
ЛА;, /
К E
° о
О 1 О
О С 1;"+
1 O yо с о с
1 1
1 1
О О 1 О
О О 1 О О о
О 1 О о о о о о о о о о
О 1 О О о о о о о о о о о о о о о опереции число третьего элемента ИЛИ и второму входу второго элемента ИЛИ, шестой информационный вход третьего операционного узла подключен к второму входу первого элемента ИЛИ вЂ” НЕ, выход которого подключен к второму входу третьего элемента ИЛИ, седьмой информационный вход третьего операционного узла подключен к первому входу второго элемента ИЛИ вЂ” НЕ, выход которого подключен к первому входу третьего элемента ИЛИ вЂ” НЕ, восьмой информационный вход третьего операционного узла подключен к третьему входу второго элемента
ИЛИ, к второму входу второго элемента
ИЛИ-НЕ и второму входу четвертого элемента И, выход которого подключен к второму входу третьего элемента ИЛИ вЂ” НЕ и к третьему входу первого элемента ИЛИ, вы> ход которого подключен к второму выходу третьего операционного узла, выходы с третьего по шестой которого подключены соответственно к выходам третьего элемента ИЛИ, третьего элемента ИЛИ вЂ” НЕ, второго элемента ИЛИ и второго элемента И, при этом четвертый операционный узел содер. жит элемент И и элемент ИЛИ вЂ” НЕ, причем первый информационный вход четвертого операционного узла подключен к первым входам элементов И и ИЛИ вЂ” НЕ, выходы которых подключены соответственно к первому и второму выходам четвертого операционного узла, второй информационный вход которого подключен K вторым входам элементов И и ИЛ И вЂ” Н Е,.
3. Устройство по и. 1, о т л и ч а ю щ е ес я тем, что блок буферной памяти содержит с первого по восьмой сдвигающие регистры, с первого по восьмой элементы ИЛИ первой группы, с первого по восьмой элементы
ИЛИ второй группы, регистр, дешифратор, элемент ИЛИ, элемент ИЛИ вЂ” НЕ, триггер подстановки, с первой по восьмую группы из m элементов И каждая. где m — разрядность обрабатываемого слова, и девятую
Бит А В + Ч И группу из восьми элементов И, причем вход синхронизации блока подключен к гходам синхронизации всех сдвигающих регистров, первый управляющий вход блока подключен к первому (инверсному) входу элемента ИЛИ, второй управляющий вход блока подключен к входам записи (считывания) всех сдвигающих регистров и регистра, информационные входы первой группы блока подключены соответственно к информационным входам регистра, выходы которого подключены к входам элемента ИЛИ вЂ” НЕ и входам дешифратора с первого по m-й, выходы а-й группы которого (где а = 1,..., 8) подключены соответственно к первым еходам элементов И с первого по (m — 1)-й а-й группы и к первому входу а-го элемента
ИЛИ первой группы, выход которого подключен к первому входу m-го элемента И а-й группы, выход элемента ИЛИ вЂ” НЕ подключен к вторым входам всех элементов ИЛИ первой группы, выходы элементов И а-й группы подключены соответственно к входам а-го элемента ИЛИ второй группы, выход которого подключен к первому входу а-ro элемента И девятой группы, выходы элементов И девятой группы подключены соответственно к выходам группы блока. третий и четвертый управляющие входы которого подключены соответственно к информационному входу и входу установки в
"0" триггера подстановки, инверсный выход которого подключен к второму (прямому) входу элемента ИЛИ, выход которого подключен к вторым входам всех элементов И девятой группы, прямой выход триггера подстановки подключен к выходу блока, информационные входы с первого по восьмой второй группы которого подключены соответственно к информационным входам сдвигающих регистров с первого по восьмой, информационные выходы с первого пс
m-й а-га сдвигающего регистра подключены соответственно к вторым входам элементов
И с первого по m-й а-й группы, 1683025
1683025
1683025
1683025
ЧТ Р ти
11 )y;1t),")г !
l
l
4 Рог. //
1683025
1б83025
I
l
1
Составитель B.ÑMèðíoB
Редактор Л.Гратилло Техред М.Моргентал Корректор В.Гирняк
Заказ 3414 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., 4/5
Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101
