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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК ГОСУДАРСТВЕННЫЙПО ИЗОБРЕТЕНИЯМПРИ ГКНТ СССР МИТЕТТКРЫТИЯМ СА ИЗОБРЕТЕН О(72) В.М,Довгаль, О нов, Ф.А.Старков и (53) 681.325 (088,8) (56) Авторское свид М 1455345, кл. 6 0 1985,Авторское свид М 1596345, кл. 6 0 тельство ССС Г 15/04, 6 0 9 4 тельство СССРР 15/04, 1988. 54) УСТРОЙ ОДСТАНОВО РЕАЛИЗАЦИИ рвыи и втои эле, с К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Курский политехнический ин Изобретение относится к техническим. средствам информатики и вычислительной техники и может быть использовано для обработки информационных потоков и массивов данных текстового и числового типов в соответствии с заданным нормальным алгорифмом.Цель изобретения - увеличение быстродействия.На фиг. 1 представлена схема устройства; на фиг.2- схема арифметического блока; на фиг. 3 - схема первого операционного узла арифметического блока; на фиг. 4 - схема второго операционного узла арифметического блока; на фиг, 5 - схема третьего операционного узла арифметического блока; на фиг, 6 - схема четвертого операционного узла арифметического блока; на фиг, 7 - схема блока анализа вхождения; на фиг. 8 - схема узла анализа блока анализа вхожде.,Ж 1683025 А 1(57) Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано для обработки информационных потоков и массивов данных текстового и числового типов в соответствии с заданными нормальными алгорифмами. Цель изобретения - повышение быстродействия устройства, Поставленная цель достигается тем, что устройство для реализации подстановок содержит арифметический блок, блок анализа вхождения, блок формирования слов вхождения и подстановки, блок просмотра, блок памяти формул, блок подставки, блок буферной памяти, блок памяти слов и блок микропрограммного управления. 2 з.п. ф-лы, 1 табл. 13 ил,ния; на фиг. 9 - схема блока формирования. слова вхождения и подстановки; на фиг, 10 - схема блока просмотра; на фиг. 11 - схема узла обнаружения блока просмотра; на фиг. 0 з 12 - схема блока подстановки; на фиг, 13 - (А схема блока буферной памяти, СРУстройство для реализации подстано- ,) вок содержит апиЬметический блок 1, блок Ц 1 2 анализа вхождения, блок 3 формирования слов вхождения и подстановки, блок 4 просмотра, блок 5 памяти формул, блок 6 подстановки, блок 7 буферной памяти, блок 8еаеВпамяти слова, блок 9 микропрограммного управления,Арифметический блок содержит пе элемент И 10, элемент НЕ 11, первый рой триггеры 12 и 13, второй и трети мент И 14 и 15, первый коммутатор первого по четвертый операционные20 25 ЗО 35 мые выходы которых подключены соответственно к первому входу первого элемента И и входу элемента НЕ, выход которого подключен к второму входу первого элемента И, выход которого подключен к выходу блока, инверсные выходы первого и второго триггеров подключены соответственно к первым входам второго и третьего элементов И, выходы которых подключены соответственно к информационным входам второго и первого триггеров, третий управляющий вход блока подключен к упоавляющему входу второго коммутатора, выходы с первого по четвертый которого подключены соответственно к информационным входам с первого по четвертый первого операционного узла, выходы с первого пс чствертый которого подключены к первому информационному входу третьего операционного узла, к первому информационному входу второго операционного узлавторому информационному входу второго операционного узла и второму информационному входу третьего операционного узла, первый и второй выходы второго операционного узла подключены соответственно к третьему и к четвертому информационному входам третьего операционного узла, вь,ходы с первого пс шестой которого подключены соответственно к первому и второму информационным входам узла задержки, к первому и второму информационным входам четвертого операционного узла, к третьему и четвертому информационным входам узла задержки, первый выход четвертого опера,ционного узла подключен к второму входу третьего элемента И и первому информационному входу первой группы первого коммутатора, второй выход четвертого операционного узла подключен к второму входу второго элемента И и второму информационному входу первой руппы первого коммутатора, выхсды с первого по четвер. тый узла задержки подключены соответственно к информационным входам с пятога по восьмой третьего операционного узла, четвертый управляющий вход блока подключен к третьему входу первого элемента И, пятый управляющий вход блока подключен к второму управляющему входу первого коммутатора и управляющему входу третьего коммутатора, выходы первой и второй групп которого подключены соответственно к информационным входам второй группы первого коммутатора и информационным входам второго коммутатора, с первого по четвеотый информационные входы группы блока подключены соответственно к информационным входам с первого па четвертый третьего коммутатора, информационные входы с пятого по восьмой группы блока подключены соответственно к информационным входам с первого по четвертый третьей группы первого коммутатора, при этом первый операционный узел содержит первый и второй элементы И-НЕ, элемент ИЛИ - НЕ и элемент ИЛИ, причем первый информационный вход первого операционного узла подключен к первым входам первого элемента И - НЕ и элемента ИЛИ, выходы которых подключены соответственна к первому и второму выходам первого операционного узла, второй информационный вход которога подключен к вторым входам.первого элемента И-НЕ и элемента ИЛИ, третий информационный вход первога операционного узла подключен к первым входам второго элемента И - НЕ и элемента ИЛИ-НЕ, четвертый информационный вход первого операционного узла подключен к вторым входам второго элемента И - НЕ и элемента ИЛИ - НЕ, выходы которых падклсчены соответственно к третьему и четвертому выходам первого операционного узла, при этом второй операционный узел содержит элемент И и элемент ИЛИ - НЕ, причем первый информационный вход второго операционного узла подключен к первым входам элемента И и элемента ИЛИ - НЕ, выходы которых подключены соответственно к первому и второму выходам второго операционного узла, второй информационный вход котарсга подключен к вторым входам элемента И и элемента ИЛИ - НЕ, при этом третий операционный узел содержит с первого пс четвертый элементы И, с первого патретий элементы ИЛИ и с первого пс треий элементы ИЛИ - НЕ, причем первый информационный вход третьего операционного узла подключен к первому входу первого элемента И, выход которого подключен к первому выходу третьеГо операционного узла, второй информационный вход третьего операционного узла подключен к первому входу второго элемента И, третий и: Формационный вход третьего операционного узла подключен к первому входу третьего элемента И, к первому входу первого элемента ИЛИ и второму входу первого элемента И, четвертый информационный вход третьего операционного узла подключен к первому входу четвертога элемента И, к первому входу второго элемента ИЛИ и второму входу второго элемента И, пятый информационный вход третьего операционного узла подключен к первому входу перьага элемента ИЛИ - НЕ, к второму входу первого элемента ИЛИ и второму входу третьего элемента И, выход которого подключен к первому входуоперации число третьего элемента ИЛИ и второму входу второго элемента ИЛИ, шестой информационный вход третьего операционного узла подключен к второму входу первого элемента ИЛИ - НЕ, выход которого подключен к второму входу третьего элемента ИЛИ, седьмой информационный вход третьего операционного узла подключен к первому входу второго элемента ИЛИ - НЕ, выход которого подключен к первому входу третьего элемента ИЛИ - НЕ, восьмой информационный вход третьего операционного узла подключен к третьему входу второго элемента ИЛИ, к второму входу второго элемента ИЛИ-НЕ и второму входу четвертого элемента И, выход которого подключен к второму входу третьего элемента ИЛИ - НЕ и к третьему входу первого элемента ИЛИ, вы ход которого подключен к второму выходутретьего операционного узла, выходы с третьего по шестой которого подключены соответственно к выходам третьего элемента ИЛИ, третьего элемента ИЛИ - НЕ, второго элемента ИЛИ и второго элемента И, при этом четвертый операционный узел содер. жит элемент И и элемент ИЛИ - НЕ, причемпервый информационный вход четвертого операционного узла подключен к первым входам элементов И и ИЛИ - НЕ, выходы которых подключены соответственно к первому и второму выходам четвертого операционного узла, второй информационный вход которого подключен к вторым входам элементов И и ИЛИ - НЕ,. 3. Устройство по и, 1, о т л и ч а ю щ е ес я тем, что блок буферной памяти содержит с первого по восьмой сдвигающие регистры, с первого по восьмой элементы ИЛИ первой группы, с первого по восьмой элементы ИЛИ второй группы, регистр, дешифратор,элемент ИЛИ, элемент ИЛИ - НЕ, триггер подстановки, с первой по восьмую группы из гп элементов И каждая. где в - разрядность обрабатываемого слова, и девятую Бит А В + Ч И группу из восьми элементов И, причем вход синхронизации блока подключен к гходам синхронизации всех сдвигающих регистров, первый управляющий вход блока подключен к первому (инверсному) входу элемента ИЛИ, второй управляющий вход блока подключен к входам записи (считывания) всех сдвигающих регистров и регистра, информационные входы первой группы блока подключены соответственно к информационным входам регистра, выходы которого подключены к входам элемента ИЛИ - НЕ и входам дешифратора с первого по в-й, выходы а-й группы которого (где а = 1 8) подключены соответственно к первым входам элементов И с первого по (т - 1)-й а-й группы и к первому входу а-го элемента ИЛИ первой группы, выход которого подключен к первому входу а-го элемента И а-й группы, выход элемента ИЛИ - НЕ подключен к вторым входам всех элементов ИЛИ первой группы, выходы элементов И а-й группы подключены соответственно к входам а-го элемента ИЛИ второй группы, выход которого подключен к первому входу а-го элемента И девятой группы, выходы элементов И девятой группы подключены соответственно к выходам группы блока, третий и четвертый управляющие входы которого подключены соответственно к информационному входу и входу установки в"0" триггера подстановки, инверсный выход которого подключен к второму (прямому) входу элемента ИЛИ, выход которого подключен к вторым входам всех элементов И девятой группы, прямой выход триггера подстановки подключен к выходу блока, информационные входы с первого по восьмой второй группы которого подключены соответственно к информационным входам сдвигающих регистров с первого по восьмой, информационные выходы с первого пс п 1-й а-га сдвигающего регистра подключены соответственно к вторым входам элементов И с первого по щ-й а-й группы, 16830251 б 83025 Фф Я. Составитель В.СмирновТехред М.Моргентал Корректор Редактор Л.Гратилл ня ат "Патент", г. Ужгород, ул,Гагарина, 1 Прои енно-издательский ко каз 3414 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-ЗБ, Раушская наб., 4/517-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 первой группы, элементы И 49 второй группы, элементы ИЛИ 50 группы и элемент ИЛИ 51,Блок 3 формирования слов вхождения и подстановки содержит регистр 52, сдвигающие регистры 53 первой группы, сдвигающие регистры 54 второй группы, элемен 55 задержки, первый элемент И 56, первый элемент ИЛИ - НЕ 57, второй и третий элементы И 58 и 59, второй элемент ИЛИ - НЕ 60, с четвертого по шестой элементы И 61- 63, группу элементов И 64, элемент ИЛИ 65, третий элемент ИЛИ - НЕ 66, элемент НЕ 67, седьмой элемент И 68.Блок 4 просмотра содержит узлы 69 обнаружения, первый элемент И 70, элементы ИЛИ 71 и второй элемент И 72.Каждый узел 69 обнаружения содержит первый сдвигающий регистр 73, компараторы 74, второй сдвигающий регистр 75, элементы И 76 группы, И 77 и ИЛИ 78.Блок б подстановки содержит первь 1 й элемент И 79 сдвигающие регистоы 80, счетчик 81, второй элемент И 82, триггер 83 и элемент 84 задержки.Блок 7 буферной памяти содержит регистр 85, элемент ИЛИ - НЕ 86, дешифратор 87, сдвигающие регистры 88, элементы И 89 с первой по восьмую группы, элементы ИЛИ 90 первой группы, элементы ИЛИ 91 второй группц, элементы И 92 девятой группы, триггер 93 подстановки и элемент ИЛИ 94.В основу нормальных алгорифмбв положено понятие формулы подстановки, под которой понимается слово вида угде ч - слово-вхождение:р - слово-подстановка;д - признак формулы, дб(О, 1,10 20 25 30 3540 45 50 55 Работа формулц подстановки над обрабатцваемым словом заключается в обнаружении в нем слова-вхождения и замены позиции слова-вхождения словом-подстановкой. Важным моментом, проясняющим работу формулы подстановки, является последовательность позиции слова-вхождения в обрабатываемом слове,Позиция вхождения является первой, если при просмотре обрабатываемого слова вхождение обнаружено первь 1 й раз. Если признак формулы д = 1, то формула называется заключительной, Она работает один раз, и нормальный алгорифм,представляющий собой конечный список формул подстановки, прекращает свою работу, Если признак формулы д=- О, то формула называется незакл 1 очительнс 1 й.и используется в работе столько оаз, сколько раз обнаруживается вхождение.В работе нормального алгорифма, когда число формул в нем больше, чем одна, устанавливается регламент работы каждой формулы подстановки, Если формула в списке незначительная, то при обнаружении первой позиции вхождения осуществляется подстановка, а переход выполняется на пеовую формулу. Следующая формула подстановки нормального алгорифма вкл 1 очается в работу тогда, кода предыдущая формула подстановки не обнаруживает ни одной собственной позиции вхождения при полном просмотре всео обрабатываемого слова, Далее рассматривается такая разновидность нормальных алгорифмов, для графической записи которой используются сокращенные формулы. Сокращенные формулы графической записи осугцествляются с использованием алфавитных переменных, принимающих значение любой буквы того алфавита, которому принадлежат буквы обрабатываемого слова, слова-вхождения и слова-подстановки,Арифметический блок служит для обработки арифметической информации, где обоаботка чисел, заданных в знакора рядной системе, выдается старшими разрядами впередкроме того, он может осуществить операци,о сравнения на больше или меньше и равно.Блок анализа вхождения служит для обработки результатов сравнения на равенство символов вхождения (левой части формулы подстановки) и фрагмента обрабатываемого слова, Анализируя результат компарации, блок анализа вхождения выдает сигнал о налички вхождении в обрабатцваемом слове в тех случаях, когда имеются на обработке формулы, которые содержаталфавитные переменные и которые их не содержат. Кроме того, блок анализа вхождения задает условия обмена информацией между блоком просмотра и блоком подстановки,Блок формирования слов вхождения и подстановки но команде блока микропрограммного управления принимает параллельно формулы подстановки, формат, который содержит слово-вхождение, слово- подстановку, признаки о наличии в формуле алфавитной переменной, признак о заключительности формулы (формула используется только один раз, если имеется вхождение), признак о том, что данная формула является последней в списке формул данного нормального алгорифма, и признак арифметики. Каждая формула подстановки является элементом нормального алгорифма. Блок формирования слов вхождения и подстановки по команде сдвига из блока микропрограммного управления выдает последовательно по символам слово-вхождение и слово-подстановку в блок просмотра, а также в блок буферной памяти. Кроме того, этот блок выдает значения приведенных признаков формулы подстановки в блок управления, а также признаки конца слова- вхождения и слова-подстановки, а в блок анализа вхождения выдает значения признаков о конце слова-вхождения и о наличии в слове-вхождении алфавитной переменной, закодированной специальным. символом " ", и управляет арифметическим блоком,Блок просмотра служит для организации просмотра обрабатываемого слова последовательно по фраг ментам, равным по длине слову вхождения, при этом осуществляется компарация на равенство выделенного фрагмента обрабатываемого слова и слава-вхождения. В том случае, когда слово- вхождение имеет в своем составе специальный символ "м", кодирующий алфавитную переменную, компаратор на равенство выдает сигнал "Не равно", но этот сигнал интерпретируется как символьное совпадениев блоке анализа вхождения. Всякий не совпадающий символ, эа исключением указанного случая, передается в блок подстановки и синхронно, в соответствии с длиной слова-вхождения, очередной символ обрабатываемого слова подается в выставленное поле компарации. В случае обнаружения вхождения вместо символов обрабатываемого слова в блок подстановки подается слово-подстановка или те символы обрабатываемого слова, которые соответствуют алфавитным переменным в той последовательности, которая определяется специально организованной формой слова-подстановки, если е ней содержатся алфае.1 тныепеременные.Блок подстановки служит для хранения 5 промежуточных фрагментов обрабатываемого слова или результирующего обрабатываемого слова с тем, чтобы процесспросмотра обрабатываемого слова с цельюобнаружения вхождения и процесс подста новки в соответствии с заданной формулойподстановки осуществлялись непрерывно.Блок буферной памяти предназначендля хранения и выдачи обрабатываемогослова при его обработке по очередной фор муле, а также для задержки слова до тех пор,пока идет подстановка.Для описания алгоритма работы блокауправления используются следующие обозначения;20 УОО - установка исходного состояния;"Пуск" - команда запуска устройства;ЧТС - команда чтения обрабатываемогослова из блока памяти слов;ЧТФ - команда чтения формулы из бло ка памяти формул;ЧЗ - команда, разрешающая записьслова иэ блока подстановки в блок буферной памяти;ТИЗ - команда сдвига для сдвигающих ЗС регистров блока вхождения и слов в блокеанализа вхождения;ТИ 5 - команда сдвига в блоке подстановки;ТИЧ - команда сдвига содержимого 35 сдвигающих регистров вхождения блокапросмотра, блока анализа вхождения, блокаформирования слов вхождения и подстановки;ТИ 6 - команда сдвига в регистрах блока 40 буферной памяти;+1 СчВ - команда увеличения на единицу счетчика блока анализа вхождения;СбрСчВ - команда сброса счетчика блока анализа вхождения;45 ТИ Р - команда сдвига для сдвигающихрегистров слова"подстановки в блокахвхождения и подстановки формированияслов;ПУф- признак конца слова-вхождения;50 ПРф- признак конца слова-подстановки фПВХ - признак наличия вхождения;ПКС 1 - признак конца обрабатываемого слова в блоке просмотра;55 ПКС 2 - признак конца обрабатываемого слова в блоке подстановки;ППЕР - признак переполнения разрядной сетки в блоке подстановки;ППФ - признак последней формулы внормальном алгорифме;10 ды; ПЗФ - признак заключительной формуАвар.ост, - команда аварийной остановки устройства;СбрСчА - команда сброса в нуль счетчика адреса блока памяти формул;+1 СчА - команда увеличения на единицу счетчика адреса блока памяти формул;ПР - признак наличия символа "Х 2" в слове-подстановке;ПР - признак символа разделителя в слове-подстановке;ПСчВ - признак ненулевого состояния счетчика в блоке анализа вхождения;ТгР - команда записи единицы в триггер подстановки,ОбТгР - команда установки в нуль триггера подстановки;Пу - признак наличия скобки в обрабатываемом слове;ПАР - признак арифметической команСБрСчб - команда установки в нуль счетчика блока подстановки;ЗСП - команда записи обрабатываемого слова в блок памяти слова;"Стоп" - команда остановки устройства, "Сброс" - команда установки исходных состояний;П- признак того, что при сравнении первое число больше второго;СбрТгА - команда обнуления арифметического блока;1 УК - команда управления коммутатором в арифметическом блоке;ТИА - тактовые сигналы для арифметического блока.По сигналу "Сброс": = 1 все элементы устройства с памятью устанавливаются в исходное состояние, По сигналу "Пуск"; = 1 устройство начинает работать, По сигналу ЧТС: = 1 осуществляется запись обрабатываемого слова по всей длине из блока памяти слова 8 в блок 6 подстановки. В следующем такте работы по команде ЧТф = 1 параллельно считывается формула по всей длине в блок 3 формирования слов-вхождения и подстановки, и одновременно по команде ЧЗ: = 1 обрабатываемое слово из блока 6 подстановки параллельно переписывается в регистры блока 7 буферной памяти.В следующихтактах подаются команды сдвига на блок 4 просмотра и блок 2 анализа вхождения ТИЗ: = 1, на блок 7 - ТИ 6; = 1, блок 2 анализа вхождения и блок 4 просмотра - ТИЧ; = 1, одновременно подсчитывается количество символов слова-вхождения по команде +1 Сч 8: = 1 в блоке 2 анализа вхождения до тех пор, пока не обнаружится 15 20 25 30 35 40 45 50 признак конца слов-вхождений (ПФ= 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), в этом случае формируется команда аварийной остановки устройства (Авар.ост,;= 1) и устройство прекращает работу,В следующем такте обнуляется счетчик блока 6 подстановки (команда СбрСчб:=1), Далее проверяется признак конца слова- вхождения очередной формулы нормального алгорифма. Если ПУ= 1 (формула имеет пустое слово-вхождение, а такая формула не может встретиться в начале нормального алгорифма), то в начало обрабатываемого слова на место первого пустого символа ставится слово-подстановка и считывается первая формула нормального алгорифма. По команде 1 ТгР:=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, осуществляется проверка наличия символов м, кодирующих в слове подстановки алфавитные переменные, Если эти символы присутствуют (в начале слова-подстановки), то осуществляется их подсчет с помощью счетчика блока 2 анализа вхождения и одновременно происходит сдвиг слова-подстановки в блоке 3 формирования слова вхождения и подстановки (+ 1 СчВ;= 1, ТИР:= 1). Цикл выполняется до тех пор, пока не закончится последовательность символов 4.После завершения цикла проверяется наличие в слове-подстановке символа-разделителя "/" или конкретного символа. В том случае, когда символ-разделитель обнаруживается ПР/=1, то выполняются команды ТИ 5;=1, ТИР:= 1, с помощью которых конкретное значение алфавитной переменной переписывается из регистров слова блока 4 просмотра (к конкретному значению доступ получен с помощью счетчика и дешифратора блока 2 анализа вхождения) в блок 6 подстановки и выполняется сдвиг на одну позицию в регистрах подстановки блока 3 формирования слова-вхождения и подстановки. Если в слове-подстановке 10 15 20 25 30 35 40 45 50 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 подстановки. Если признак Правен единице (а это может произойти, если выполнялась операция сразнения и первое число больше второго), то осуществляется переход по адресу, который хранится во втором и третьих разрядах регистров подстановки в блоке 3 формирования слов вхождения и подстановки,Запись в блок 5 памяти формул осуществляется командой ЧИ;=1. В случае, еслиП= О, проверяется признак ПЗФ = 1 (формула заключительная). Если ПЗФ " О, топроисходят сброс счетчика адреса(СбрСчА:=1) и обнуление триггера подстановки, следующей будет выполняться первая формула нормального алгорифма.Работа арифметического блока 1 в двоичной энакоразрядной системе счисления,который представляет собой результатаппаратной поддержки нормального алгорифма сложения, заключается в преобразовании чисел с помощью операционныхузлов.17 - 20 и узла 21 задержки,На вход узла 17 числа подаются в зависимости от типа операции (" Сложение" или"Вычитание" ) в естественном или перевернутом виде. Арифметический блок 1 включается в работу по условию срабатыванияформулы подстановки. Обрабатываемое 20слово может состоять из символьной информации, каждый символ кодируется восемьюбитами знака операции (+, - , ) - кодировката же, что и у арифметической информации,записанной (двачисла) в четырех верхних 25битах, затем идет закрывающая скобка, иснова может идти символьная информация,Рассмотрим пример - кодировка условная(таблица),Код символов выбран так, что ни у одного символа не может быть четырех нулей внижних четырех битах. Если на пятый уп равляющий вход блока 1 приходится то коммутаторы 16 и 23 арифметического блока 1пропускают информацию без изменения в 35е блок 6 подстановки (арифметический блок 1отключен), в противном случае - "1", четыреверхних бита (разряды двух чисел) поступают на коммутатор 22, вторая и третья строкаменяются местами, т,е, подаются в виде Х, 40У, Х, У; В таком случае, если на управляющем входе коммутатора 22 присутствуете,то информация в таком же виде поступаетна вход узла 17 (операция сложения), в противном случае (- "1") коммутатор 22 меняет 45местами положительную и отрицательнуюсоставляющие второго числа Х, У, Х, У(операция вычитания или сравнения по разности). Коммутатор 16 работает следующимобразом, пока на первом или втором управляющем входе присутствует "1", в два верхних разряда (первая и вторая строка)поступает результат операции соответственно 2, 2, все остальные разряды нулевые, затем эта информация поступает в блок 556 подстановки,Операционные узлы 17 - 20 арифметического блока 1 строятся непосредственно наоснове формул подстановок соответствующих алгорифмов, Хо УУо= Хо фУо = Хо ъ Уо А о, Хо - значения входов узл где Хс, Уо, У17,Узел 18: В Уг =У+/ У У 1, Х 1 -значен, Уг, Хг, Т 1, Т 4, Т 2, ТЗ - значенияла 19; , ТЗ и Т 4 - соответствующие зна одов узла 21,Уг, Уг, Хг - значения выходов де Хг, Уг входов узТ 1, Т 2 чения выхХг, узла 18.Узел 0: 24 =Я ЫЯ 24 =ЯЯ Я,ЯМз,Уз де Уз, Мз,ов узла 20;24, 24мы ачения вхоеэультирующий разряд сукУ 4, У 4, М 4, М 4 - счетные входы узла задержки,После прохождения исходных операндов через операционные узлы 17 - 20 формируется результат в виде по ледовательности пар 2 и 2, а первый значащий разряд результата выдается через один или два такта от момента поступления первых разрядов операнда. Появление значащего разряда результата на втором такте работы означает возникновение переполнения, однако возникающее переполнение не может исказить результат.Рассмотрим конкретную обработку на примере сложения. В результате вхождения блока 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 анализа и5 10 15 20 25 30 35 40 45 50 55 поступит сигнал "Конец вхождения", (ПЧф= =1), Сигнал ПВХ выдается с выхода элемента И 47, на входы которого поступает информация с выходов узлов 46 и ПЧ= 1.Блок 3 формирования слов вхождения и подстановки работает следующим образом. Из блока 5 памяти формул через информационные входы блока 3 формирования слов вхождения и подстановки по сигналу ЧТФ на восемь сдвигающих регистров 53 поступает слово-вхождение, так что первые биты каждого байта, кодирующего символ этого слова, подаются на первый сдвигающий регистр 53, а, соответственно, восьмые биты каждого байта - на восьмой сдвигающий регистр 53, Таким образом, вертикальный срез сдвигающих регистров 53 дает один байт, соответствующий одному символу, Аналогично информация подается на восемь сдвигающих регистров 53, куда записывается слово-подстановка,Служебный байт с признаками формулы; формула с алфавитными переменными (ПАП = 1), формула заключительная (ПЗО = =1), последняя формула нормального алгорифма (ППФ = 1)Я (ПАР = 1), - арифметика записывается в регистр 52.Информация с регистров вхождения и подстановки поступает последовательно, а с регистра 52 - параллельно. Для первых восьми сдвигающих регистров, хранящих вхождение, используется команда сдвига ТИЧ, для следующих восьми регистров, хранящих подстановку, - команда сдвига ТИР.Элеменг И 56 распознает символ "%" в слове-вхождении и выдает этот сигнал ПЧМ на первый выход блока. Элемент ИЛИ - НЕ 57 распознает пустой Оайт в конце слова-вхождения и выдает сигнал ПФ Элемент И 58 распознает символ "м" в слове-подстановке и выдает сигнал Прх. Элемент И 59 распознает символ-разделитель "(" в слове-подстановке и выдает сигнал ПР/. Элемент ИЛИ - НЕ 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 подключены к выходам счетчика, фиксирующего 5 10 15 20 25 ф 0 35 40 45 50 51 длину обрабатываемого слова, Информация с выходов регистров 80 поступает в блок 8 памяти слова и в блок 7 буферной памяти,Блок 7 буферной памяти работает следующим образом.В исходном состоянии триггер 93 подстановки находится в нулевом состоянии, Регистр 85 используется для управления дешифратором 87, с помощью которого обеспечивается поступление обрабатываемого слова (когда его длина меньше длины регистров, в которых оно находится) по сигналам сдвига (ТИ 6: = 1) в блок 4 просмотра, Обрабатываемое слово хранится в регистрах 88. По сигналу Ч 3=1 обрабатываемое слово из блока 6 подстановки параллельно записывается в регистры 88, а код длины обрабатываемого слова по тому же сигналу записывается в регистр 85(горизонтальный срез по всем восьми одноименным разрядам представляет код символа). В том случае, когда слово из блока 8 памяти слова первый раз загружается в регистры 88, в регистре 85 будут нули (длина слова не хранится в блоке 8 памяти слова) и чтобы организовать посимвольный выход его в блок 4 просмотра, используется элемент ИЛИ-НЕ 86, выход которого подключен к входам элементов ИЛИ 90, Единицы с выходов этих элементов подаются на входы соответствующих элементов И 89, что позволяет открыть выходы регистров 88. Элементы И 92 работают в качестве ключей, разрешая или запрещая подачу символов на обработку,Формула изобретения 1, устройство для реализации подстановок, содержащее блок анализа вхождения, блок формирования слов вхождения и подстановки, блок просмотра, блок памяти формул, блок подстановки и блок микропрограммного управления, о т л и ч а ю щ е ; с я тем, что, с цель,о увеличения быстродействия, оно содержит арифметический блок и блок буферной памяти, причем вход начальной установки устройства и вход запуска устройства подключены соотвегственно к входу начальной установки и входу запуска блока микропрограммного управления, первый выход которого подключен к выходу г.ризнака аварийной остановки устройства, выходы первой группы блока подстановки подключены соответственно к информационным входам блока памяти слова, выходы которого подключены соответственно к инфоомационным входам первой группы блока подстановки, выходы первой и второй групп блока формирования слов вхождения и подстановки подключены соответственно к информационным входам первой и второй групп блока просмотра, выходы первойгруппы которого подключены соответственно к информационным входам блока анализа вхождения, вцходц группы которого подключены соответственно к информационным входам третьей группы блока просмотра, первый и второй выходы которого подключены. соответственно к первому и второму входам режима блока микропрограммного управления, второй выход которого подключен к первому входу синхронизации блока просмотра и первому входу синхронизации блока анализа вхождений, первый и второй выходы которого подключены соответственно к третьему и четвертому входам режима блока микропрограммного управления, третий и четвертый выходы которого подключены соответственно к входу увеличения числа вхождений и входу обнуления числа вхожде, ний блока анализа вхождений, выходы третьей группы блока формирования слов вхождения и подстановки подключены соответственнок адресным входам блока памяти формул, выходы которого подключены соответственно к информационным входам блока формирования слов вхождения и подстановки, выходы с первого по восьмой которого подключены соответственно к первому управляющему входу блока анализа вхождений и входам режима с пятого по одиннадцатый блока микропрограммного управления, девятый выход блока фаамиравания слов вхождения и подстановки подключен к второму управляющему входу блока анализа вхождений и двенадцатому входу режима блока микропрограммного управления пятый и шестой выходы каторога подключены соответственно к первому входу синхронизации блока формирования слов вхождения и подстановки и входу записи блока памяти слова, седьмой выход блока микропрограммного управления подключен к первому управляющему входу блока формирования слов вхождения и подстановки и входу чтения блока памяти формул, восьмой, девятый и десятый выходы блока микропрограммного управления подключены соответственно к входу инкремента адреса, входу обнуления адреса и входу синхронизации блока памяти формул, одиннадцатый и двенадцатый выходы блока микропрограммного управления подключены соответственнс к первому и второму управляющим входам арифметического блока, выход которого подключен к таинадцатому входу режима блока микропрограммного управления, тринадцатый выход которого подключен к входу синхронизации арифметического блока, выходы группы которого подключены соответственна к информаци 5 10 15 20 25 30 35 40 45 50 55 онным входам второй группы блала подстановки, первый и второй выходы которого подключены соответственно к четырнадцатому и пятнадцатому входам режима блока микропрограммного управления, четырнадцатый и пятнадцатый выходы которого подключены соответственно к первому управляющему входу и входу синхронизации блока подстановки, выходы второй группы которого подключены соответственно к информационным входам первой группы блока буферной памяти, выходы группы которого подключены соответственно к информационным входам четвертой группы блока просмотра, выходы второй группы которого подключены соответственно к информационным входам группы арифметического блока; шестнадцатый выход блока микропрограммного управления подключен к второму управляющему входу блока подстановки и входу чтения блока памяти слова, выходы третьей группы которого подключены соответственно к информационным входам второй группы блока буферной памяти, выход которого подключен к второму управляющему входу блока формирования слов вхождения и подстановки, десятый, одиннадцатый, двенадцатый и тринадцатый выходы которого падклачены соответственно к первому управляющему входу блока буферной памя 1 и, третьему, четвертому и пятому упрзвляющм входам арифметического блока, с семнадцатога па двадцатый выходы блока ми.:рапраграммного управления подключены соответственна к второму управляющему входу, входу синхронизации, третьему управля ющему входу и четвертому управляюгцему входу блока буферной памяти, двадцать первый выход блока микропрограммного управления подключен к второму входу синхронизации блока формирования слав вхождения и подстановки, второму входу синхронизации блока прасматаа и второму входу синхронизациии блока анализа вхождения,2,Устройства па п.1, атл и ча ю щеес я тем, что арифметический блок содержит с первого па четвертый операционные узлы, зел задержки, с первого па третий коммутаторы, первый и второй тригеры, с первого па третий элементы И и зле;.",ент НЕ, пои зтам ехад синхронизации и геалый управляющий вход блока падклаченн соответственна к входу синхронизации узла задержки и первому уп ра ел я гащему входу первого коммутатора, вь:хад."ка-араго подключены соответственно .", в 1 ха,.",ам группы блока, второй управляющ 1-: вход которого подключен к входам установки в "0" узла задержки, первого и второго тр;1-герав, пря