Устройство для сравнения двух п-разрядных чисел Советский патент 1981 года по МПК G06F7/04 

(54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ ДВУХ 1-РАЗРЯДНЫХ ЧИСЕЛ

Изобретение относится к автоматике и вычислительной технике и может быть использовано в качестве устройства сравнения чисел для выявления больше го, равного или меньшего нисла. Известно устройство для сравнения чисел, которое состоит из однотипных модулей сравнения двух разрядов, причем выход модуля сравнения 1-х разрядов чисел является входом модуля срав нения (1-1) разрядов. При вьгавленш неравенства старших разрядов результат неравенства транслируется на выход устройства сравнения 1. Однако это устройство обладает низ ким быстродействием вследствие того, что при сравнении п-разрядных чисел А и В устройства сравнения содержит п последовательно соединенных модулей сравнения одноразрядных чисел а и Ц от 1 п до I 1. Наиболее близким к тфедпагаемому является устройство для сравнения дву п-разрядных чисел, содержащее mS-разрддных сумматоров, где m Е (VtIS), Е I ближайшее большее целое число,элемент .,причем входная шина прямого значе:ния каждого 1-го разряда первого числа, где « Г, 2,...п соединена с i-ым для i $ S, (f-р5)-ым для i S входом р-го сумматора, где р « Е (ife), вход ная шина инверсного значения каждого i-ro Разряда второго числа подключена к (} + 5)-ому для S, П - (Р+ l)Sому для I 7 S входу Р-го сумматора, выходы суммы первого сумматора соединены со входами элемента И-НЕ 2. Недостатком этого устройства является Низкое быстродействие. Цель изобретения - повышение быстродействия. Поставленная цель достигается тем, что в устройство для сравнения двух п-разрядных чисел, содержащее mS-разрядньк сумматоров, где m Е (hfe) , Е - ближайшее большее целое число, элемент -HEj причем входная шина прямого знаения каждого t-ro разряда первого чис3864280

ла устройства, где i 1,2,. ,.п, соединена с 1-ым дпя I & S, (-р5)-ым для У S входом р-го сумматора, где р Е (/5) t входная шина инверсного значения каждого 1-го разряда второго чис-д ла устройства подключена к ( + 5)-ому для I 5, i - (Р+ 1)5 -ому для i S входу р-го сумматора, выходы разрядов суммы первого сумматора соединены со входами элемента и тем, что введе-ю ны К узлов анализа, где К - Е (vjfZS- 1,5) + 1, причем выходы разрядов суммы каждого J-ro сумматора, где j « 2,4... (m-1), соединены со входами равенства первой группы j/2-го узла анализа, вы- ,§ ход переноса каждого j-ro сумматора-. подключен к первому информационному входу j/2-го узла анализа, выходы разрядов суммы каждого Сто сумматора, где , 1, 3,..,,т, соединены со входамз равенства второй группы t + 1/2го узла анализа, выход переноса каждого сумматора подключен ко второму информационному входу + 1/2-го узла анализа, первый и второй выходы каждого i-ro узла анализа соединены с первым и вторым входами переносов соответственно (i + I) узла анализа, выход элемента И-НЕ подключен к первому входу переносов первого узла анализа, выход переноса первого сумматора соединен со вторым входом переносов первого узла анализа, и тем, что в нем каждьй узел анализа сод ржит элементы И-НЕ, И, НЕ, 11ПИ, причем первый и второй информационные входы узла соединены с первыми входами первого и второго элементов И соответст венно, выходы которых под1шючены к первому и второму входам соответствен но первого элемента ИЛИ, первая и вто рая группы входов равенства узла соединены со входами первого и второго элементов И-НЕ соответственно, выходы которых подключены к первому и втором входам соответственно второго элемента ИЛИ, выход которого соединен с пе вым выходом узла анализа, первый вход переносов узла подключен к третьему входу второго элемента ИЛИ и через пе вый злемент НЕ - ко вторым входам пер вого и второго элементов И, второй вход переносов узла соединен с третьим входом первого элемента ИЛИ, выход которого подключен ко второму выходу узла, выход первого элемента И-Н через второй злемент НЕ соединен с третьим входом второго элемента И.

На фиг. I изображена блок-схема предложенного устройства; на фиг. 2 функциональная схема узла анализа для случая использования 4-х разрядных сумматоров, Устройство содержит т S-разрядных сумматоров L , « hi m « Е (и|5), п - число разрядов в сравниваемых числах, Е - ближайшее большее цеЭлемент И-НЕ 2, К узлов лое число - , 3,...3, где К Е (I25анализа 3 1 5) ь 1. Каждый узел анализа 3 содержит элемент И-НЕ 4, 5, злемент И 6, 7, элемент ИЛИ 8, 9, элемент НЕ JO 11 Устройство работает следующим обазом. п-разрядов сравниваемых чисел разивают на группы по S разрядов. В проессе сравнения двух чисел происходит уммирование в группах S разрядов одого числа и соответствующих инверсньк разрядов другого числа на S-разрядом сумматоре. Для всех возможных сотношений разрядов сравниваемых чисел группе значения шин суммы и переноса -разрядного сумматора следующие jS ). S %2 2 - 1 } Пример. 1. А 8, В 7 Суммируем А + В J. 1000 1000 1 -0000 Р - .(S- 0). 2. А « 8, В - 8 Суммируем А + В О, 2« 15 3. А 7, В « 8 Суммируем А В Р о,(- J4;. Соотношение А В однозначно определяется единичным потенциалом на выходной шине переноса сумматора. Соотношение А В к А В расшифровываются анализом значений выходов суммы. Дпя этого шины суммы подключаются к входам схем И-НЕ 1 и И-НЕ 2, И-НЕ 3, входящих в состав модуля перехода (МП) (фиг. 2). Наличие логического нуля на шинах суммы сумматора СS 2 - ) при отсут ствии переноса однозначно определяет соотношение чисел А В. Таким образо появление логической единицы на выхо схемы И-НЕ, подключенной к шинам сум мы при отсутствии переноса определя ет Соотношение . Наличие единицы на все Ящиках суммы сумматора (S 2 -i j о нозначно определяет соотношение чисел А В, при этом на выхоДе элемента И-НЕ, подключенного к шинам суммы, логический нуль. Соотношение шины переноса сумма- тора и выходной шины элемента И-НЕ при различных соотношениях сравниваемых чисел в группе следуюацие (см. . таблицу). Состояние шин переноса сумматоров и выходов соответствующих схем И-ЙЕ анализируются МП, причем, если сумматором старшей группы разрядов cpaaHHaaehflbix чисел определяется неравенство, то результат сравнения транслируется на выход устройства сравнения. Модуль перехода (фиг. 2) содержит управляющие входы t и две группы информационных входов К К)« Kg л 9 и управлякщие выходы {Ц и сjj . На управляющие входы 6 к t МП 7, 10 поступает информация о результате сравнения разрядов чисел в предыдущих старших группах. При этом, если в пре дыдущих группах определено неравенств разрядов, то информация о неравенстве транслируется на управляющие выходы JL и el, МП.Если на управляющие входы поступает информация о равенстве разрядов в предыдущих старших группах, то МП анализирует информацию о результате сравнения других разрядов чисел, определяемых сумматорами, выходы которых подключены к группам информационных входов. Управляющий вход | МП 4 через элемент И-НЕ 2 подключен к выходным шИнам сумь&1, а управляюосий вход ft - к шине переноса сумматора 1 старшей группы разрядов срвпниваемых числа. К управляющим входам и 6 йодключены сумматор старшей группы разрядов сравниваемых чисел Зд-а. « Ьл . К сумматору младшей группы подключены а 4 о-Ь4разрядыПри определении неравенства в старшей группе разрядов на выходе элемента И-НЕ 1 появляется единица. Логический нуль на выходе инвертора НЕ } эакрьюает схемы И I и И 2, к которым подключены выходные шины переноса сумматоров остальных групп разрядов. На управляющие выходы МП через элементы ШШ I и ИЛИ 2 транслируется признак неравенства, определенный сумматором старшей группы разрядов сравниваемых чисел При равенстве разрядов в старшей группе на выходе элемента И-НЕ логический нуль. Логическая единица на выходе инвертора НЕ I открывает элементы И I и И 2. При этом в случае неравенства в средней группе разрядов на выходе .хемы И-НЕ 2 - логическая единица. Логический нуль на выходе схемы НЕ 2 закрывает схему 1i 2. На управляязщие выходы МП через элементы ШШ I и ШШ 2 транслируется признак неравенства, определяющий сумматоры средней группы сравниваемых чисел. При равенстве разрядов в средней группе на выходе элемеита И-НЕ 2 логический нуль. При равенстве разрядов старшей и средней групп логические единицы на выходах инверторов НЕ I и НЕ 2 открывают элемент И 2. На управлякяцие выходы МП транслируется результат сравнения, определяемый сумматором младшей группы разрядов сравниваемых чисел. Шийы К и Bjj дают следующую информацию о соотношениях сравниваемых чисел ei 1. Две шины могут нести информацию о етырех состояниях, в нашем случае с омощью двух шин выдается информащ1Я трех состояниях. В материалах заяви схема позиционного разделения реультатов сравнения не показана: ритязания заявителя на нее не расространяются, и к существу предложеия она отношения не имеет, так как ыдача информации по Двум шинам являтся с точки зрения обработки резульатов сравнения.

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

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

переноса каждого Р-го сумматора подкл19чен ко .второму информационному входу Р + 1/2-го узла анализа, первый и второй выходыкаждого 1-го узла анализа соединены с первым и вторым входами переносов соответственно (i + 1) узла анализа, выход эл мент а И-НЕ подключен к первому входу переносов первого узла анализа, выход переноса первого

сумматора соединен со вторым входом переносов первого узла анализа.

И-НЕ, И, НЕ, ИЖ, причем первый и второй информационные входы узла соединены с первыми входами первого и второго элементов И соответствеино, выходы которых подключены к первому

и второму входам соответственно первого элемента ИЛИ, первая и вторая группы входов равенства узла соединены со входами первого и второго элементов И-НЕ соответственно, выхоДы которых подключены к первому и второму входам соответственно второго элемента ИЖ, выход которого соединен с первым выходом узла анализа, первый вход переносов узла подключен

к третьему входу второго элемента ИЛИ и через первый элемент НЕ - ко вторым входам первого и второго элементов И, второй вход переносов узла соединен с третьим входом первого элемента ИЛИ, выход которого подключен ко второму выходу узла, выхоД) первого элемента И-НЕ через вtopoй элемент НЕ соединен с третьим входом второго элемента И.

Источники информации, принятые во внимание при экспертизе

Of7.iS-1.

Фиг.1

li

&