Устройство анализа и замены числовых полей Советский патент 1987 года по МПК G06F7/00 

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

В вычислительной технике часто встречаемой является операция анализа возможности замены числовых поОлемент данных поле 3 поля связи поле О

поле 1 поле 2 число

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

поле 3 «споля связи

()число

поле 0

1 число .П 11.

h 0 ЧИСЛО 1 ЧИСЛО

0 число

.000.. .00. 0000... 01. .0000. .10. . ..

и-1

h- 1 и- 1 . 1111...10.

Поле элемента данных представляет собой целое число со знаком. Обозна- ЧИЦ1 j-e поле i элемента данных П .., значение знакового разряда этого ПОЛЯ

ЗП

ij

значение числовых

L (ЗП11 1)л(ЧП10 11...11)Л()л(ЗП21 1)л

(mo 11... 11 )л( )(... 11 )л()л

() (ЧП405 11. . . 11) Л( () ()v /()Л())Л(()Л()У ()()) л( ()л()) Л(()Л()).

Операция замены для элемент.ов дан ных П13 П12 П11 П10, П23 П22 П21 111...11, ПЗЗ П32 П31 111...11, П43 П42 П41 П40 дает результат: П13 П12 П40 111.. . 11.

Целью изобретения является расширение функциональных возможностей за счет одновременной обработки четырех элементов данных.

На фиг.1 изображена функциональная схема устройства анализа и замены числовых полей; на фиг.2 - функциональная схема формирователя масок; на фиг.З - функциональная схема корректора; на фиг.4 -- функциональная схема группы элементов ИЛИ; на фиг.З - функциональная схема группы элементов И; на фиг.6 - функциональная схема анализатора; на фиг.7 - функциональная схема идентификатора.

Предлагаемое устройство содержит первый 1, третий 2, четвертый 3 и второй 4 входные регистры, формирователь 5 масок, первый 6 и второй 7 регистры маски, первую 8 и вторую 9

h- 1 и- 1 . 1111...10.

и I

разрядов - ЧП -..

Условием возможности замены числовых полей в устройстве для анализа и замены числовых полей является истинность вы- 25 ражения

группы элементов И, корректор 10,

.j группу 11 элементов ИЛИ.

Формирователь масок содержит первый, второй и третий элементы И 12- 14, элемент НЕ 15, четвертый элемент И 16, первый и второй анализаторы

40 17 и 18, первый и второй идентифика- торы 19 и 20, пятый элемент И 21, элемент 1ШИ 22.

Корректор содержит, группу элементов НЕ 23.

45 Анализатор включает третью,первую, четвертую и вторую схемы 24-27 сравнения, первый и второй элементы И 28, 29, элемент ИЛИ 30„

Идентификатор включает первую и

JIQ вторую схемы 31 и 32 сравнения, элемент И 33.

Устройство анализа и замены числовых полей функционирует следующим образом.

55 В первый 1, второй 2, третий 3 и четвертый 4 входные регистры (фиг. 1) заносятся первый, четвертый, второй и третий элементы данных. Соответствующие разряды входных регистров поступают на соответствующие входы формирователя 5 масок, с первого и третьего выходов которого сформированные маски поступают соответственно на входы первого 6 и второго 7 регистров маски, с выходов которых маски поступают на входы элементов И первой 8 и второй 9 групп, на другие входы которых поступают элементы данных с выходов соответственно первого 1 и второго 4 входных регистров. Выделенные поля элементов данных снимаются с выходов элементов И первой группы 8 и подаются на входы элементов ИЛИ группы 11 и с выходов элементов И второй груп- .пы 9 и подаются на вход корректора, с выхода которого откорректированное поле, выделенное в четвертом элементе данных, подается на вход элементов

4n33))v((4n42 ЧПЗЗ)л()), представляемого выходом анализатора 18, значения ((ЧП22 ЧП13)Х(ЧП21 ЧП43)), представляемого выходом идентификатора 19, значения ((ЧП32 ЧП13)л(ЧП31 ЧП43)), представляемого выходом идентификатора 20.

10

f5

Значение ЧП10 поступает на входы элемента И 12 и на второй вход анализатора 17 с разрядов, начиная с 0-го по (п-2)-й первого входа, значение ЧП11 поступает на первый вход анализатора 17 с разрядов, начиная с п-го по (2п-2)-й первого входа, значение ЧП13 поступает на вторые входы идентификаторов 19 и 20 с разрядов, начиная с 2п-го по (Зп-2)-й включительно первого входа, значение

ИЛИ группы 11, выходы которых в соот-20 ° поступает на входы элемента И 13 ветствующий момент времени представ- разрядов, начиная с 0-го по (п-1)-й ляют результат замены числовых полей. второго входа, значение ЧП21 поступа- Второй выход формирователя является т на третий вход идентификатора 19 вторым выходом устройства и представ- разрядов, начиная с п-го по (2п-2)22 второго входа, значение ЧП22 поступает на первый вход идентификатора 19 с разрядов, начиная с 2п-го по (Зп-2)-й включительно второго входа, значение ЧП23 поступает на третий вход анализатора 17 и на четвертый вход анализатора 18 с разрядов, начиная с (Зп-1)-го по (4п-3)-й второго входа, значение ПЗО поступает на вхо(2п-1)-м разрядом первого входа, зна- элемента И 14 с разрядов, начиная чения (ЗП10 1), представляемого ,. нулевого по (п-1)-й третьего входа, (п-1)-м разрядом первого входа, эна- значение ЧП31 поступает на третий чения ((ЧШС) 11... 11),, представляе- ход идентификатора 20 с разрядов,

начиная с п-го по (2п-2)-й третьего мого инверсным выходом элемента И 12, входа, значение ЧП32 поступает на

ляет результат проверки.

Формирователь масок (фиг.2) предназначен для анализа возможности замены числовых полей и формирования масок для осуществления замены. Элемент И 21 осуществляет формирование результата проверки числовых полей элементов данных как конъюнкции значения (ЗП11 1), представляемого

30

значения (ЗП21 1), представляемого (2п-1)-м разрядом второго входа, значения (П20 JJM-vJJj представляемого выходом элемента И 13, значения (ЗП31 1), представляемого (2п-1)-м разрядом третьего входа, значения ,(ПЗО 111... 11), представ- -уf

ляемого выходом элемента И 14, значения (ЗП41 0), представляемого вы40

первый вход идентификатора 20 с разрядов, начиная с 2п-го по (Зп-2)-й третьего входа, значение ЧПЗЗ поступает на четвертый вход анализатора 17 и на третий вход анализатора 18 с ., разрядов, начиная с (Зп-1)-го по (4п-3)-й третьего входа, значения ЧП40 поступает на входы элемента И 16 с разрядов, начиная с 0-го по (п-2)-й четвертого входа, значение ЧП41 походом элемента НЕ 15, значения (ЗП40 ступает на второй вход анализатора 18 1), представляемого {п-1)-м разрядом с разрядов, начиная с п-го по (2п-2)й четвертого входа, значения (ЧП40 J 1 ., .11), представляемого инверсньм

четвертого входа, значение ЧП42 поступает на первый вход анализатора 18 с разрядов, начиная с 2п-го по (Зп- сг -2)-й четвертого входа, значение ЧП43 поступает на четвертые входы идентификаторов 19 и 20 с разрядов, начиная с (Зп-1)-го по (4п-3)-й четвертого входа.

выходом элемента И 16, значения ((ЧП11 ЧП23) л(ЧП10 4n33))V

((ЧП11 ЧПЗЗ)(ЧП10 ЧП23)), ставляемого выходом анализатора значения ((ЧП42 ЧП23)л(ЧП41

4n33))v((4n42 ЧПЗЗ)л()), представляемого выходом анализатора 18, значения ((ЧП22 ЧП13)Х(ЧП21 ЧП43)), представляемого выходом идентификатора 19, значения ((ЧП32 ЧП13)л(ЧП31 ЧП43)), представляемого выходом идентификатора 20.

10

f5

первый вход идентификатора 20 с разрядов, начиная с 2п-го по (Зп-2)-й третьего входа, значение ЧПЗЗ поступает на четвертый вход анализатора 17 и на третий вход анализатора 18 с разрядов, начиная с (Зп-1)-го по (4п-3)-й третьего входа, значения ЧП40 поступает на входы элемента И 16 с разрядов, начиная с 0-го по (п-2)-й четвертого входа, значение ЧП41 поступает на второй вход анализатора 18 с разрядов, начиная с п-го по (2п-2)й

ступает на второй вход анализатора 18 с разрядов, начиная с п-го по (2п-2)четвертого входа, значение ЧП42 поступает на первый вход анализатора 18 с разрядов, начиная с 2п-го по (Зп- г -2)-й четвертого входа, значение ЧП43 поступает на четвертые входы идентификаторов 19 и 20 с разрядов, начиная с (Зп-1)-го по (4п-3)-й четвертого входа.

Из-за соединения прямого и инверсного выходов элемента И 21 с входами элемента ИЛИ 22 на его прямом и инверсном выходах генерируются постоянные значения, соответствующие 1 и О соответственно, причем прямой выход устанавливает разряды, начиная с 2п-го по (4п-1)-й первой маски, и разряды, начиная с 0-го по (п-1)-й второй маски, остальные разряды масок устанавливаются в О инверсным выходом. Первая и вторая маски поступают соответственно на первый и третий выходы формирователя масок, на второй выход которого подается значение с прямого выхода элемента И 21, сигнализирунвдее об успешности операции анализа на возможность замены числовых полей.

Анализатор (фиг.6) предназначен fO для анализа значений на его четырех (п-1)-разрядных входах в соответствии с правилом ((BX1-BXЗ)л(BX2-BX4)V(BX1fBX4)л()).

с п-го по (2п-1)-й, выхода корректора. 5 Нулевое значение разрядов, начиная с п-го по (2п-.1 )-й, входа корректора превращается в единичное с помощью группы элементов НЕ 23, и полученное на их выходах значение 111. .. 11 по-Значение с первого входа ВХ1 поступает на первые входы схем 24 и 26 сравнения, на вторые входы которых поступают соответственно значения ВХЗ и ВХ4 с третьего и четвертого входов. Значение с второго входа ВХ2 поступает на первые входы схем 25 и 20 27 сравнения, на вторые входы которых поступают соответственно значения ВХ4 и ВХЗ с четвертого и, третьего входов. Элемент И 28, объединяя на входах выходы Равно схем 24 и 25 25 сравнения представляет на своем выходе значение (()л()), элемент И 29, объединяя на входах выходы Равно схем 26 и 27 сравнения,

дается поразрядно на разряды, начиная с 0-го по (п-1)-й, выхода корректора.. .Разряды, начиная с 2п-го по (4п-1)-й, выхода корректора повторяют соответствующие входные разряды.

Формула изобретения Устройство анализа и замены чис35

40

представляет на своем выходе значения 30 ловых полей, включающее первый и вто- ()лСВХ2-ВХЗ), причем значения с выходов элементов И 28, 29, поступая на входы элемента ИЛИ 30, обеспечивает на его вцходе требуемый результат.

Идентификатор (фиг.7) предназначен для анализа значений на его четырех (ri-1)-разрядных входах и идентификации ситуации ()л(). Значения на первом и втором входах идентификатора сравниваются с помощью схемы 31 сравнения, значения на третьем и четвертом входах идентификатора - с помощью схемы 32 сравнения. Выходы Равно поступают на входы элемента И 33, единичное значение с выхода которого идентифицирует анализируемую ситуацию. Корректор (фиг.З) предназначен для сдвига на одно поле влево выделенного с помощью маскирования на второй группе элементов И 9 (фиг.1) поля четвертого элемента данных и заполнения освободившегося поля признаком 111.. ,

(сдвиг выделенного поля осуществл1 ет-1 ;ся поразрядной связью разрядов, начи- ная с нулевого по (п-1)-и, входа корректора (фиг.З) с разрядами, начиная

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

50

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

дается поразрядно на разряды, начиная с 0-го по (п-1)-й, выхода корректора.. .Разряды, начиная с 2п-го по (4п-1)-й, выхода корректора повторяют соответствующие входные разряды.

Формула изобретения Устройство анализа и замены чис

ловых полей, включающее первый и вто-

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

7.

корректор, состоящий из группы элементов НЕ, причем с нулевого по (п-2)-й разряды выхода первого входного регистра соединены с входами первого элемента И формирователя масок и с первыми входами первой и втрой схем сравнения первого анализатора формирователя масок (п-разряд- ность числа), разряды, начиная с п-го по (2п-2)-й выхода первого вхоного регистра, соединены с первыми входами третьей и четвертой схем сравнения первого анализатора формирователя масок, разряды, начиная с Зп-го по (4п-2)-й, выхода первого входного регистра соединены с первыми входами первых схем сравнения певого и второго идентификаторов формирователя масок, причем разряды, начиная с нулевого по (п-1)-й, выхо третьего входного регистра соединен с входами второго элемента И формирователя масок, разряды, начиная с п-го по (2п-2)-й, выхода третьего входного регистра соединены с первыми входами второй схемы сравнения первого индентификатора формирователя масок, разряды, начиная с 2п-г по (Зп-2)-й, выхода третьего входного регистра соединены с вторыми входами первой схемы сравнения первого идентификатора формирователя масок, разряды, начиная с Зп-го по (4п-2)-й, выхода третьего входного регистра соединены с вторыми входами второй и третьей схем сравнения первого анализатора формирователя масок и вторыми входами первой и четвертой схем сравнения второго анализатора формирователя масок, причем разряды, начиная с нулевого по (п- -1)-й, выхода четвертого входного регистра соединены с входами третьего элемента И формирователя масок, разряды, начиная с п-го по (2п-2)-й выходы четвертого входного регистра соединены с первыми входами второй схемы сравнения второго идентификатора формирователя масок, разряды, начиная с 2п-го по (Зп-2)-й, выхода четвертого входного регистра соединены с вторыми входами первой схемы сравнения второго идентификатора формирователя масок, разряды, начиная с Зп-го по (4п-2)-й, выхода четвертого входного регистра соединены с вторыми входами первой и четвертой схем сравнения первого анализатора формирователя масок и с вторыми вхо25628

дами третьей и второй схем сравнения второго анализатора формирователя масок, причем разряды, начиная с нулевого по (п-2)-й, выхода второго 5 входного регистра соединены с входами четвертого элемента И формирова- теля масок, разряды, начиная с п-го по (2п-2)-й, выхода второго входного регистра соединены с первыми входами O первой и второй схем сравнения второго анализатора формирователя масок, разряд (2п-1)-и выхода второго входного регистра соединен с входом элемента НЕ формирователя масок, раз- 5 ряды, начиная с 2п-го по (Зп-2)-й, выхода второго входного регистра соединены с первыми входами третьей и четвертой схем сравнения второго анализатора формирователя масок, раз- 0 ряды, начиная с Зп-го по (4п-2)-й, выхода второго входного регистра соединены с вторыми входами вторых схем сравнения первого и второго идентификатора формирователя масок,, причем 5 выходы Равно первой и третьей схем сравнения первого и второго анализаторов формирователя масок соединены с первым и вторым входами первого элемента И первого и второго анали- 0 заторов формирователя масок соответственно, а выходы Равно второй и . четвертой схем сравнения первого и второго анализаторов формирователя масок соединены с первым и вторым 5 входами второго элемента И первого и второго анализаторов формирователя масок соответственно, выходы первого и второго элементов И анализаторов формирователя масок соединены 0 соответственно с первым и вторым входами элемента ИЛИ анализаторов формирователя масок, причем в каждом идентификаторе формирователя масок ВЕЯХОДЫ Равно первой и второй схем сравне- 5 ния идентификатора формирователя масок соединены соответственно с первым и вторым входами элемента И идентификатора формирователя масок, кроме того, разряды (2п-1)-й и (п-1)-й вы- 0 хода первого входного регистра, ин- верс11ый выход первого элемента И формирователя масок, разряд (2п-1)-й выхода третьего входного регистра, выход второго элемента И формирова- 5 теля масок, разряд (2п-1)-й выхода четвертого входного регистра, выход третьего элемента И формирователя масок, выход элемента НЕ формирователя масок, разряд (п-1)-й выхода вто913

рого входного регистра, инверсный выход четвертого элемента И формирователя масок, выходы элементов ИЛИ первого и второго анализаторов формирователя масок, выходы элементов И первого и второго идентификаторов формирователя масок соединены соот- ветстве но с входами пятого элемента И формирователя масок, прямой и инверсный выходы пятого элемента И формирователя масок соединены с первым и вторым входами элемента ИЛИ формирователя масок, прямой выход элемента ИЛИ формирователя масок соединен с 2п-го по (4п-1)-й разрядами входа .первого регистра маски и с нулевого по (п-1)-й разрядами входа второго регистра маски, инверсный выход элемента ИЛИ формирователя масок соединен с нулевого по (2п-1)-й

210

разрядами входа первого регистра маски и с п-го по ()-й разрядами входа второго регистра маски, причем прямой выход пятого элемента И форИрователя масок является вторым выодом устройства анализа и замены числовых полей, причем с нулевого по (п-1)-й выходы элементов И второй группы соединены с вторыми входами

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

с вторыми входами элементов ИЛИ группы, начиная с нулевого по (п-1)-й,. с 2п-го по (4п-1)-й выходы элементов И второй группы соединены с вторыми входами элементов ИЛИ группы, начиная с 2п-го по (4п-1)-й.

(pus.2.

- //7

Фиг.д

/7 I Vn

Чп

4n-i ул-г 1/

- I

n-1 I

(Pu.i

Лп I /7

Й Л-/Л п-2

А п-г sL J

ф4 /7

Г Д-/C rt-2

Фие.5

Чп

11

Редактор В.Данко

Составитель О.Березикова

Техред Л,Олийнык . Корректор С.Черни

Заказ 1972/47 Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Фиг, 6

п- i.n-i

и

т

ФигЛ

Изобретение относится к цифровой вычислительной технике и может использоваться при обработке структурно- сложной информации (графов, таблиц), анализе структур алгоритмов и программ, оптимизации разветвлякяцихся участков граф-схем алгоритмов. Оно позволяет выполнять часто встречаемую операцию анализа и замены числовых полей, которыми кодируется списковое представление графов. Цель изобретения - расширение функциональных возможностей за счет одновременной обработки четырех элементов данных. Устройство содержит четыре входных регистра, формирователь масок, два. регистра маски, две ,группы элементов И, корректор, группу элементов ИЛИ, два выхода. Формирователь масок содержит пять элеменITOB И, элемент НЕ, два анализатора. два идентификатора, элемент ИЛИ. Корректор содержит группу элементов НЕ. Анализатор содержит четыре схемы, сравнения, два элемента И, элемент ИЛИ. Идентификатор содержит две схемы сравнения, элемент И.- Четыре элемента данных, которые необходимо проверить, поступают на входные регистры и с них - на входы формирователя масок, а первый и четвертый элементы данных, кроме того, поступают на входы первой и второй групп элементов И. С помощью формирователя масок проверяется возможность замены числовых полей в соответствии с правилом обобщения разветвляющихся участков граф- схем и результат проверки представляется на его втором выходе, являющемся вторым выходом устройства, а также формируются маски на первом и третьем выходах. С этих выходов маски поступают на регистры масок и с выходов последних - на входы первой и второй групп элементов И. С выхода второй группы элементов И вьщеленное их четвертого элемента данных поле подается на вход корректора, где оно сдвигается на размер одного поля влево, а освободившееся место заполняется признаком пустого поля. С выходов первой группы элементов И и корректора вьщеленные поля подаются на входы группы элементов ИЛИ., где объединяются и поступают на первый выход устройства. 7 ил. а S (Л