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

Изобретение относится к цифровой

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

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

«С Элемент данных : «Споле 3

поля связи ; «i Поле 3 : 0 число ; Поле связи :. поле 2 . : поле 1 поле 0 :

г:Поле 0 : 1 число 1 HI...II; г Поле 1 : О число

I 1 число ; - Поле 2 : 0 « число ; -i Число : .000.. .00,i| ООП. ..01, I ,000.. .10,1.../

-( П-1

III...10. 25

40

п-(,30

ТАКИМ образом, поле элемента данных представляет собой целое число со знаком. Обозначим j-e поле i-ro элемента данных Пи значение знакового разряда этого поля - ЗП ,; , значение числовых разрядов этого поля - Mnifj,. Условием возможности замены числовых полей устройства анализа и замены числовых полей является истинность вьфажения

L () Л «() А (П10 111....111) V (()Л (П10 111(.v ...111))) А () Л (...1.1)л

Л (() V ())Л . ().

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

Цель изобретений - повьшение родействия устройства.

На фиг. 1 изображена функциональ- Ная схема устройства анализа и заме- « ны числовых полей; на фиг. 2 - функциональная схема блока формирования масок; на фиг. 3 - функциональная схема блока коррекции; на фиг. 4 45

50

5

0 15

0

5

0

0

«

5

0

функциональная схема группы элементов ИЛИ; на фиг. 5 - функциональная схема группы элементов И.

Устройство содержит первый 1 и второй 2 входные регистры, блок 3 формирования масок, первый 4 и второй 5 регистры маски, первую 6 и вторую 7 группы элементов И, блок 8 коррекции, группу 9 элементов ИЛИ второй элемент НЕ 10, вторую группу 11 элементов И, первый и четвертый элементы И 12 и 13, первую группу 14 элементов И, второй и третий элементы И 15 и 16, первый элемент НЕ 17, первый элемент ИЛИ 18, группу 19 элементов ИЖ, вторую и первую схемы 20 и 21 сравнения, пятый элемент И 22, второй элемент ИЛИ 23, группу 24 элементов ИЛИ, первую 25 и вторую 26 группы элементов И,элемент НЕ 27.

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

В первый входной регистр 1 заносится первый элемент данных, во второй входной регистр 2 - второй элемент данных. С выходов первого 1 и второго 2 входных регистров первый и второй элементы данных поступает на первую 6 и вторую 7 группы элементов И. На входы первого 4 и второго 5 регистров масок маски поступают соответственно с первого и третьего выходов блока 3 формирования масок. На первый и второй входы блока 3 формирования масок поступают соответствующие разряды (фиг. 1) полей соответствующих элементов данных. Элемент И 22 блока формирования масок (фиг. 2) осуществляет формирование признака возможности замены числовых полей, включающего значение элемента НЕ 10, представляющего собой ЗП12, значение выхода элемента ИЛИ 18, представляющего собой значение (ЗП11 Л (...11)) V (ЗП11Д А (П10 111... 11)), образуемого с помощью значений выходов элементов И 15, 12 и 16, значение выхода совпадения второй схемы 20 сравнения,представляющего собой значение (ЧП11 ЧП23) V (), образуемого с помощью значений выходов первой 14 и второй 11 групп элементов И и руппы 19 элементов ИЛИ, осуществляющих выбор поля с и содержаще- то нули в ЧП, значение выхода совпадения первой схемы 21 сравнения,представляющего собой значение (ЧП22 ЧП13), значение разряда п 2-го входа блока, представляющего собой ЗП21, значение выхода элемента И 13, представляющего собой значение (П20 111... 11). Прямой и инверсньй выходы элемента ИЛИ 23 имеют постоянные значения, эквивалентные соответственно нулю и единице, которые устанавливают соответственные разряды масок (фиг. 2). Выход элемента НЕ 17, имеющий значение ЗП11, и прямой выход элемента И 12, имеющий значение (П10 111... 11), устанавливают соответст- вующие разряды (фиг. 2) первой маски причем последний является четвертым выходом блока 3 формирования масок и управляет группами элементов И (фиг. 3) блока 8 коррекции, осущест- вляющего сдвиг пропущенного поля второго элемента данных в зависимости от значения (...11) на одно поле вправо. С помощью группы 9 элементов ИЛИ, производится логичес- кое сложение кодов с выходов элементов И первой группы 6 и выхода блока 8 коррекции. Результат поступает на первый выход устройства, второй выход которого представляет собой прямой выход элемента И 22 (фиг. 2)J

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

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

5 О 5 0 0

5

0 5 п г

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

.

5

с 2п-го по (4п-1)-й разрядами входа первого регистра маски и с п-го по (2п-1)-й разрядами входа второго регистра маски, инверсный выход второго элемента ИЛИ блока формирования масок соединен с нулевого по (п-1)-й разрядами и с 2п-го по (4п-1)-й разрядами входа второго регистра маски, причем прямой выход пятого элемента И блока формирования масок является вторым выходом устройства, с нулевого по (п-1)-й разряды выходов элементов И второй группы соединены поразрядно с первыми входами элементов ИЛИ группы блока коррекции, с п-го по(2п-1)-й разряды выходов элементов И второй группы соединены поразрядно с вторыми входами элементов ИЛИ группы блока коррекции, с 2п-го по (4п-1)-й разряды выходов элементов И второй группы соединены с вторыми входами соответствующих элементов ИЛИ группы, выход элемента НЕ блока коррекции соединен с первыми входами элементов И второй группы блока коррекции, выходы элементов ШШ группы блока коррекции со дине- ны с вторыми входами элементов И первой и второй групп блока коррекции, разряды с нулевого по (п-1)-й выходов элементов И второй группы блока коррекции соединены с вторыми входами элементов ИЛИ группы, р азря- . ды с 0-го по (п-1)-й выходов элёмен- 5 тов И первой группы блока коррекции поразрядно соединены с вторыми входами с п-го по (2п-1)-й элементов ИЛИ группы.

0

5

0

1Нл

«М.2

7066/53

Тираж 671Подписное

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

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

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

ФксЗ

Изобретение относится к области цифровой вычислительной техники и может быть использовано при обработке структурно-сложной информации (графов, таблиц), анализе структур алгоритмов и программ, оптимизации линейных участков граф-схем алгоритмов. Оно позволяет выполнить часто встречаемую операцию анализа и замены числовых полей, которыми кодируется смысловое представление графов. Цель изобретения - повышение быстродействия устройства. Устройство содержит два входных регистра, блок формирования масок, два регистра масок, две группы элементов И, блок коррекции, .группу элементов ИЛИ, два входа, два выхода. БЛОК формирования масок.содержит два элемента НЕ, две группы элементов. И, -пять элементов И, группу элементов ИЛИ, две схемы сравнения. элемент ИЛИ. Блок коррекции содержит группу элементов ИЛИ, две группы элементов И, элемент НЕ. Два элемента данных, которые необходимо проанализировать и заменить числовые ПОЛЯ, поступают на входные регистры и с выхода последних - на входы двух групп элементов И и на входы блока формирования масок. С помощью последнего анализируется возможность замены числовых полей в соответствии с правилом обобщения линейных участков грзф-схем и результат анализа представляется на втором выходе блока, являющемся вторым выходом устройства, а также проводится формирование масок на первом и третьем выходах блока. Маски с этих выходов поступают на регистры масок и с выходов последних - на соответствующие группы элементов И. С выхода второй группы элементов И выделенное поле подается на первый вход блока коррекции, на второй вход которого Пос- тупает сигнал с четвертого выхода блока о том, что первьш элемент данных имеет 1 или 2 входа в граф- схеме и выделенное поле из втсГрого элемента соответственно не должно ИЛИ ДОЛЖНО быть сдвинуто на размер одного ПОЛЯ вправо. С выходов первой группы элементов И и блока коррекции вьщеленные поля подаются на входы группы элементов ИЛИ, где объединяются и поступают на первый вы- ход устройства. 5 ил. I О)