Устройство анализа и замены числовых полей

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУ БЛИН (19) (И) (50 4 G 06 F 7/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К A8TOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3941101/24-24 (22) 29.07.85 (46) 23.05.87. Бюл. Ф 19 (7 1) Белорусский государственный университет им. В.И.Ленина (72) А.В.Соболев, Г.Н.Черников и В.А.Чудовский (53) 681.3 (088.8) (56) Авторское свидетельство СССР

И 1132284, кл. С 06 F 7/00,,1983.

Авторское свидетельство СССР

У 1280606, кл. G 06 F 7/00,25.07.85 ° (54) УСТРОЙСТВО АНАЛИЗА И ЗАМЕНЫ ЧИСЛОВЫХ ПОЛЕЙ (57) Изобретение относится к цифровой вычислительной технике и может использоваться при обработке структурносложной информации (графов, таблиц), анализе структур алгоритмов и программ, оптимизации разветвляющихся участков граф-схем алгоритмов. Оно позволяет выполнять часто встречаемую операцию анализа и замены числовых полей, которыми кодируется списковое представление графов. Цель изобретения — расширение функциональных возможностей за счет одновременной обработки четырех элементов данных. Устройство содержит четыре входных регистра, формирователь масок, два. регистра маски, две ,группы элементов И, корректор, группу элементов ИЛИ, два выхода. Формирователь масок содержит пять элемен, тов И, элемент НЕ, два анализатора, два идентификатора, элемент ИЛИ. Корректор содержит группу элементов НЕ.

Анализатор содержит четыре схемы" сравнения, два элемента И, элемент

ИЛИ. Идентификатор содержит две схемы сравнения, элемент И; Четыре элемента данных, которые необходимо проверить, поступают на входные регистры и с них — на входы формирователя масок, а первый и четвертый элементы данных, кроме того, поступают на входы первой и второй групп элементов И.

С помощью формирователя масок проверяется возможность замены числовых полей в соответствии с правилом обобщения разветвляющихся участков графсхем и результат проверки представляется на его втором выходе, являющемся вторым выходом устройства, а также формируются маски на первом и третьем выходах. С этих выходов маски поступают на регистры масок и с выходов последних — на входы первой и второй групп элементов И. С выхода второй группы элементов И вьщеленное их четвертого элемента данных поле подается на вход корректора, где оно сдвигает- ся на размер одного поля влево, а освободившееся место заполняется признаком пустого поля. С выходов первой группы элементов И и корректора вьщеленные поля подаются на входы группы элементов ИЛИ., где объединяются и поступают на первый выход устройства. 7 ил. :В»

1 1312562 2

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

<элемент данных> . = <поле 3> <поля связи> (поле 3> 0<число>

<поля связи> . = <поле 2><поле 1>(поле О>

<поле О> =.с1 числсъ 1111...11, <поле 1> = 0<число> 1<число>

<поле 2> : =- 0<число>

<число> : - 000...00,0000...01 ОООО...10 ...

1 1 -1

1111...10.

1 .и

Поле элемента данных представляет разрядов — ЧП -, . Условием возможности собой целое число со знаком. Обозна- замены числовых полей в устройстве чиы j-e поле i элемента данных для анализа и замены числовых

П,. значение знакового разряда это- полей является истинность вы1j У го поля — ЗП <,, значение числовых . 25 ражения

Х = (ЗП11=1) л(ЧП10Ф 11...11)A(3II10=1)n (ЗП21=1) л

Л(П201 111... 11) < (3II31=1) (1130=111... 11) л (ЗП41=0) Л

Л(ЗП40=1) А(ЧП40 11... 11) Л((ЧП11=ЧП23) Л(ЧП10=ЧПЗЗ) (ЧП11=ЧПЗЗ) Л(ЧП10=ЧП23) ) Л((ЧП42=ЧП23)Л(ЧП41=ЧПЗЗ)Ч (ЧП42=ЧПЗЗ) (ЧП41=ЧП23) ) Л((ЧП22=ЧП13)Л(ЧП21=ЧП43) )

Л((ЧП32=ЧП13) Л(ЧП31=.ЧП43) ) .

Операция замены для элементов дан ных П13 П12 П11 П10, П23 П22 П21

111...11, ПЗЗ П32 П31 111...11, П43

1 П42 П41 П40 дает результат: П13 П12

П40 111...11.

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

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

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

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

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

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

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

Идентификатор включает первую и 0 вторую схемы 31 и 32 сравнения, элемент И 33.

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

В первый 1, второй 2, третий 3 и четвертый 4 входные регистры (фиг. 1) заносятся первый, четвертый, второй и третий элементы данных. Соответствующие разряды входных регистрой постуI

3 1312 пают на соответствующие входы формирователя 5 масок, с первого и третьего выходов которого сформированные маски поступают соответственно на входы первого 6 и второго 7 регист5 ров маски, с выходов которых маски поступают на входы элементов И первой

8 и второй 9 групп, на другие входы которых поступают элементы данных с выходов соответственно первого 1 и второго 4 10 входных регистров. Выделенные поля элементов данных снимаются с выходов элементов И первой группы 8 и подаются на входы элементов ИЛИ группы 11 и с выходов элементов И второй груп.пы 9 и подаются на вход корректора, с выхода которого откорректированное поле, выделенное в четвертом элементе данных, подается на вход элементов

ИЛИ группы 11, выходы которых в ветствующий момент времени представляют результат замены числовых полей.

Второй выход формирователя является вторым выходом устройства и представляет результат проверки, 25

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

40 (2n-1) -м разрядом второго входа, значения (П20 =,111...11, представрь ляемого выходом элемента И 13 значения (ЗП31 = 1), представляемого (2n-1)-м разрядом третьего входа, 45 значения (ПЗО = 111...11), представП ляемого выходом элемента И 14, значения (ЗП41 = О), представляемого выходом элемента НЕ 15, значения (ЗП40вя

=1), представляемого (и-1)-м разрядом четвертого входа, значения (ЧП40 Ф

11...11), представпяемпгр инверсиям т1- 1 выходом элемента И 16, значения

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

562 4

= ЧПЗЗ)) ч((ЧП42 = ЧПЗЗ)л(ЧП4 1=ЧП23)), представляемого выходом анализатора

18, значения ((ЧП22 = ЧП13)л(ЧП21

ЧП43)), представляемого выходом идентификатора 19, значения ((ЧП32

= ЧП13)А(ЧП31 = ЧП43)), представляемого выходом идентификатора 20.

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

П20 поступает на входы элемента И 13 с разрядов, начиная с О-го по (n-1)-й второго входа, значение ЧП21 поступает на третий вход идентификатора 19 с разрядов, начиная с и-го по (2n-2)второго входа, значение ЧП22 поступает на первый вход идентификатора

19 с разрядов, начиная с 2n-ro no (Зп-2)-й включительно второго входа, значение ЧП23 поступает на третий вход анализатора 17 и на четвертый вход анализатора 18 с разрядов, начиная с (Çn-1)-го по (4n-3)-й второго входа, значение ПЗО поступает на входы элемента И 14 с разрядов, начиная с нулевого по (n-1)-й третьего входа, значение ЧП31 поступает на третий вход идентификатора 20 с разрядов, начиная с и-го по (2n-2)-й третьего входа, значение ЧП32 поступает на первый вход идентификатора 20 с разрядов, начиная с 2n-ro по (Çn-2)-й третьего входа, значение ЧПЗЗ поступает на четвертый вход анализатора

17 и на третий вход анализатора 18 с разрядов, начиная с (Çn-!)-го по (4n-3)-й третьего входа, значения

ЧП40 поступает на входы элемента И 16 с разрядов, начиная с О-го по (п-2)-й четвертого входа, значение ЧП41 поступает на второй вход анализатора 18 с разрядов, начиная с и-го по (2n-2)-й чствертого входа, значение ЧП42 пос тупает на первый вход анализатора 18 с разрядов, начиная с 2n-ro по (Çn-2)-й четвертого входа, значение

ЧП43 поступает на четвертые входы идентификаторов 19 и 20 с разрядов, начиная с (Зп-1)-го йо (4п-3)-й четвертого входа. пают соответственно на первый и третий выходы формирователя масок, на второй выход которого подается значение с прямого выхода элемента И 21, сигнализирующее об успешности операции анализа на возможность замены числовых полей.

Анализатор (фиг,6) предназначен

10 для анализа значений на его четырех (n-1)-разрядных входах в соответствии с правилом

) (ВХ1=,ВХ4)n,(ВХ2 ВХЗ)). с и-го по (2n-1) -й выхода корректора.

Нулевое значение разрядов, начиная с п-го по (2n-.1 )-й,входа корректора превращается в единичное с помощью группы элементов НЕ 23, и полученное на их выходах значение 111...11 по—

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

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

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

И, элемента ИЛИ, двух идентификаторов, каждый из которых состоит из двух схем сравнения и элемента И, и

5 1312562 6

Из-за соединения прямого и инверсного выходов элемента И 21 с входами элемента ИЛИ 22 Hà его прямом и инверсном выходах генерируются постоянные значения, соответствующие "1" и "0" соответственно, причем прямой выход устанавливает разряды, начиная с 2п-го по (4n-1)-й первой маски, и разряды, начиная с 0-го по (п-1)-й второй маски, остальные разряды масок устанавливаются в "0" инверсным выходом. Первая и вторая маски посту((ВХ1-BX3) n(BX2-ВХ4

Значение с первого входа ВХ1постуЪ пает на первые входы схем 24 и 26 15 сравнения, на вторые входы которых поступают соответственно значения

ВХ3 и ВХ4 с третьего и четвертого входов. Значение с второго входа ВХ2 поступает на первые входы схем 25 и 20

27 сравнения, на вторые входы которых поступают соответственно значения

ВХ4 и ВХЗ с четвертого и, третьего входов, Элемент И 28, объединяя на входах выходы "Равно" схем 24 и 25 сравнения представляет на своем выходе значение ((ВХ1=ВХЗ) n(BX2=BX4) ), элемент И 29, объединяя на входах выходы "Равно" схем 26 и 27 сравнения, представляет на своем выходе значения 30 (ВХ1=ВХ4)h(BX2-ВХЗ), причем значения с выходов элементов И 28, 29, поступая на входы элемента ИЛИ 30, обеспечивает на его выходе требуемый результат . 35

Идентификатор (фиг. 7) предназначен для анализа значений на его четырех (n-1)-разрядных входах и идентификации ситуации (ВХ1=ВХ2) л(ВХЗ=ВХ4) .

Значения на первом и втором входах 40

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

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

f0

35

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

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

n-ro по (2n-2) -й, выхода третьего входного регистра соединены с первыми входами второй схемы сравнения первого индентификатора формирователя масок, разряды, начиная с 2n-ro по (Зп-2)-й, выхода третьего входного регистра соединены с вторыми входами первой схемы сравнения первого идентификатора формирователя масок, разряды, начиная с Зп-го по (4n-2)-й, выхода третьего входного регистра соединены с вторыми входами второй и третьей схем сравнения первого анализатора формирователя масок и вторыми входами первой и четвертой схем сравнения второго анализатора формирователя масок, причем разряды, начиная с нулевого по (n-1)-й, выхода четвертого входного регистра соединены с входами третьего элемента И формирователя масок, разряды, начиная с n-ro по (2n-2)-й, выходы четвертого входного регистра соединены с первыми входами второй схемы сравнения второго идентификатора формирователя масок, разряды, -начиная с 2п-ro по (Зп-2)-й, выхода четвертого входного регистра соединены с вторыми входами первой схемы сравнения второго идентификатора формирователя масок, разряды, начиная с Зп-ro по (4п-2)-й, выхода четвертого входного .регистра соединены с вторыми входами первой и четвертой схем сравнения первого анализатора формирователя масок и с вторыми вхо12562 8 дами третьей и второй схем сравнения второго анализатора формирователя масок, причем разряды, начиная с нулевого по (п-2)-й, выхода второго входного регистра соединены с входами четвертого элемента И формирователя масок, разряды, начиная с и-го по (2n-2)-й, выхода второго входного регистра соединены с первыми входами первой и второй схем сравнения второго анализатора формирователя масок, разряд (2n-1)-й выхода второго входного регистра соединен с входом элемента НЕ формирователя масок, разряды, начиная с 2n-ro по (3n-2)-й, выхода второго входного регистра сое. динены с первыми входами третьей и четвертой схем сравнения второго анализатора формирователя масок, разряды, начиная с 3п-го по (4п-2)-й, выхода второго входного регистра соединены с вторыми входами вторых схем сравнения первого и второго идентификатора формирователя масок,. причем выходы "Равно" первой и третьей схем сравнения первого и второго анализаторов формирователя масок соединены с первым и вторым входами первого элемента И первого и второго анализаторов формирователя масок соответственно, а выходы "Равно" второй и четвертой схем сравнения первого и второго анализаторов формирователя масок соединены с первым и вторым входами второго элемента И первого и второго анализаторов формирователя масок соответственно, выходы первого и второго элементов И анализаторов формирователя масок соединены соответственно с первым и вторым входами элемента ИЛИ анализаторов формирователя масок, причем в каждом идентификаторе формирователя масок выходы

"Равно" первой и второй схем сравнения идентификатора формирователя ма131 рого входного регистра, инверсный вьгсод четвертого элемента И формирователя масок, выходы элементов ИЛИ первого и второго анализаторов формирователя масок, выходы элементов И первого и второго идентификаторов формирователя масок соединены соответственно с входами пятого элемента

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

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

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

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

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

13)2562

Рие,2

13125á2!

3!2562

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

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

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

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий!!3035, Москва, Ж-35, Раушская наб., д. 4/5

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