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

1

(21)4440532/24-24

(22)14.06.88

(46) 07.03.90. Бкш. К 9 (72) В.Н.Горохов

(53)681.325.5(088.8)

(56)Авторское свидетельство СССР fr 947854, кл. G 06 F 7/04, 1980.

Авторское свидетельство СССР № 1193659, кл. G 06 F 7/04, 1984.

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

(57)Изобретение относится к автоматике и вычислительной технике. Цель изобретения - уменьшение аппаратурных затрат и повышение быстродействия. Устройство содержит п/2 ячеек сравнения первого типа и n/2-l ячеек сравнения второго типа,объединенных в узлы сравнения, элемент НЕ

и два элемента ИЛИ-НЕ. Ячейка сравнения первого типа содержит два элемента ИЛИ-НЕ и два элемента И, выходы которых попарно объединены в МОНТАЖНОЕ ИЛИ. Ячейка сравнения второго типа содержит элемент И, элемент НЕ и элемент развязки. Выход элемента И с первым входом объединены в МОНТАЖНОЕ ИЛИ. Выход элемента развязки объединен с четвертым входом в МОНТАЖНОЕ ИЛИ. Ячейки сравнения образуют в узлах сравнения древовидную структуру, сбалансированную по длительности формирования сигналов на своих выходах. Ячейка сравнения первого типа анализирует соотношение двух смежных разрядов сравниваемых чисел. Ячейка сравнения второго типа анализируют результаты, сформированные двумя смежными ячейками сравнения предыдущего каскада. На выходе устройства формируются сигналы А В, и . 1 з.п. ф-лы, 5 ил., 1 табл.

с &

(Л

с

Изобретение относится к области автоматики и вычислительной техники. Цель изобретения - уменьшение аппаратных затрат и повышение быстродействия. Устройство содержит N/2 ячеек сравнения первого типа и N/2 - 1 ячеек сравнения второго типа, объединенных в узлы сравнения, элемент НЕ и два элемента ИЛИ-НЕ. Ячейка сравнения первого типа содержит два элементы ИЛИ-НЕ и два элемента И, выходы которых попарно объединены в "монтажное ИЛИ". Ячейка сравнения второго типа содержит элемент И, элемент НЕ и элемент развязки. Выход элемента И с первым входом объединены в "монтажное ИЛИ". Выход элемента развязки объединен с четвертым входом в "монтажное ИЛИ". Ячейки сравнения образуют в узлах сравнения древовидную структуру, сбалансированную по длительности формирования сигналов на своих выходах. Ячейка сравнения первого типа анализирует соотношение двух смежных разрядов сравниваемых чисел. Ячейка сравнения второго типа анализируют результаты, сформированные двумя смежными ячейками сравнения предыдущего каскада. На выходе устройства формируются сигналы A*98В, А=В и A*98B. 1 з.п. ф-лы, 5 ил., 1 табл.

Изобретение относится к автоматике и вычислительной технике.

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

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

Устройство содержит п/2 ячеек 1 первого типа, (n/2-l) ячеек 2 второго

типа, объединенных в узлы з сравнения р-го порядка, выходные элементы НЕ 4, ИЛИ-НЕ 5 и 6, входы первого 7 и второго 8 чисел, выходы 9-11.

Каждый узел сравнения р-го порядка (4 р п) содержит ячейку 2 сравнения второго типа и узлы ЗРрти сравнения Рс-Гго и порядка соответственно, причем рЈ . Узел З1 сравнения 2-го порядка содержит ячейку 1 сравнения первого типа.

Ячейка 1 сравнения первого типа содержит элементы ИЛИ-НЕ 12 и 13, элементы И 14 и 15, выходы которых попарно объединены соединением МОНVI

Јь

00

J

00 00

ТАЖНОЕ ИЛИ. Ячейка имеет выходы 16 и 17.

Ячейка 2 второго типа содержит элементы И 18, НЕ 19 и элемент 20 развязки, первый 21, второй 22, третий 23 и четвертый 24 входы и первый 25 и второй 26 выходы. Выход элемента И 18 объединен с первым входом ячейки МОНТАЖНОЕ ИЛИ, выход элемента 20 развязки объединен в МОНТАЖНОЕ ИЛИ с четвертым входом ячейки В качестве элемента развязки может быть использован одновходовой элемент И (ИЛИ) или многовходовой элемент И (ИЛИ), на другие входы которого подаются постоянные сигналы логической единицы (нуля).

Устройство работает следующим образом.

На входы 7 и 8 подаются числа А и В соответственно в прямом и инверсном кодах, причем -первый разряд является старшим. Каждая ячейка 1 первого типа анализирует два смежных разряда сравниваемых чисел и формирует результат на своих выходах 16 и 17: результат 00, если в анализируемых этой ячейкой разрядах зафиксировано равенство a.b, ,; результат 01, если ., или если а.Ь, и а Ь1+1; результат 10 или И если , или если а ,Ь . и . + 1

Ячейка 2 сравнения второго типа, входящая в состав узла 3 сравнения р-го порядка объединяет результаты сравнения, выработанные узлами ЗрЈти Зр дсравнения рЈт-го и р порядка с учетом старшинства анализируе - мых этими узлами сравнения разрядов.

Ячейка 2 сравнения второго типа, входящая в узел 3 сравнения п-го порядка, формирует на своих выходах 25 и 26 результаты сравнения чисел А и В: 00, если 01, если , 10 или 11, если A-iB. Эти сигналы преобразуются дешифратором, состоящи из элементов НЕ(4, ИЛИ-НЕ 5 и 6, в сигнал логической единицы на одном из трех выходов 9-11 устройства, если соответственно , , .

Элемент 20 развязки ячейки 2 сравнения предназначен для исключения влияния сигнала, сформированного на втором выходе узла сравнения р -го

М А

порядка и поданного на вход 24 этой ячейки на состояние выхода элементов НЕ 19 и 18. В то же время элемен 20 развязки не препятствует формиро

5

ванию на выходе 26 ячейки сигнала F2b F22+F24, реализуемого соединением ГОНТАКНОЕ ИЛИ,

Если принять, что время срабатывания элементов И, ИЛИ-НЕ, НЕ и элемента развязки tM-tHA,ftME t,p tal а. время задержки при формировании сигйала соединением МОНТАЖНОЕ ИЛИ пренебрежимо мало по сравнению с t3, то на выходах 16 и 17 ячейки 1 сравнения сигналы будут сформированы через t, t1T t3 с момента подачи кодов сравниваемых чисел.

Время формирования сигналов на выходах 25 и 26 ячейки 2 сравнения определяется как

tzi max{t21 ; tns™a ti +t3 t 434s+t3

1;

5

0

5

0

0

5

Поэтому, соединяя ячейки сравнения в определенном порядке, с учетом новой дисциплины соединения узлов сравнения можно добиться, чтобы длительности формирования сигналов на входах ячейки 2 сравнения, входящей в состав узла сравнения q-ro порядка (4 i q in), были сбалансированы.

Рассмотрим пример построения устройства для в соответствии с предлагаемой дисциплиной соединения узлов сравнения.

Узел 28-го порядка состоит из ячейки 2 сравнения второго типа и узлов сравнения q -го и q -го порядка,

П

1 МЛ СТ

где qMA max{G(c ,),G(ca),G (c),..., G (Cj ),...},

где j l,2,...,o причем, так как c.,2, то с- 1 3cJ-2, т.е.

, с,4, ,

с

и т.д., а

5

G(c,)2, G(c2)4, G(c3)lO, G(c4) G(c5)...0.

Следовательно, q ,4,10,0.. . 10, a q -q-qil-ier

Теперь выполняют соединение для узла 18-го порядка (). Этот узел состоит из ячейки 22 сравнения и узлов qcr-ro и порядка, причем (c1),G(c7),G(c3),...3.

Поскольку теперь , то с

toJ

3cj-2.(l- Fk(q)), так как L,8,

R,8; L

т)д

20, , и

2 ix 2

то величина

Г F

k(q) будет равна единице, если , или если 20 q i26, или если 56 q 84 и

т.д.

Так как не принадлежит ни кеодто

1

15

ному из этих интервалов, (18)0, и , т.е. maxfG(2), G(4), G(10), G(28),...

,4,10,. Следовательно, Ч-.-1°. .

1 MA

Для узла сравнения 10-го порядка

со

Т Р„(10)0, поэтому

K:1 k

q maxfc(2), G(4), G(10),...}

4

k-i

to - a qc -6.

Для узла сравнения 8-го порядка

, поэтому F1 (8) 1, и ZFK(8)

Kil

1, поэтому для узла 8-го порядка с,2, , и (2), 6(6), G(l8),...,,6,0,....

Далее получают для узла 6-го порядка , , для узла 4-го порядка q . Узлы сравнения 2-го порядка не разбиваются на другие узлы, а содержат ячейки 1 сравнения первого типа.

Устройство для (фиг. 5) состоит из элементов НЕ 4, ИЛИ-НЕ 5 и 6 и узла 3 сравнения 28-го порядка. Этот узел состоит из ячейки 2, сравнения второго типа и двух узлов 3 и сравнения 18-го и 10-го порядка соответственно. Узел 3м сравнения 18-го порядка состоит из ячейки 2г, узла З10 10-го порядка и узла 3 8-го порядка. Узлы 31° сравнения 10-го порядка

ния и узлы ка соответственно и т.д.

На фиг,5 указано время формирования правильных сигналов (в единицах t) на выходах всех ячеек сравнения с момента поступления кодов сравниваемых чисел на входы 7 и 8 устройства. Правильный результат сравнения будет сформирован на выходах 9-11 устройства через время 6 t9 с момента поступления кодов сравниваемых чисел на входы.

Результаты расчетов сведены в таблицу.

Рассмотрим процесс конструирования устройства с помощью таблицы для . В графе Разрядность находят требуемое . Если строк с нужным п несколько, выбирается та, которая отмечена звездочкой. В графах Стар а содержат ячейку 2(2.) сравнеА (

и узлы 3 и 3 4-го и 6-го поряд548783

10

15

)

р

20

25

30

35

ший узел и Младший узел находят порядок соответственно старшего и младшего узлов , q 10.

Аналогично находят порядок старшего и младшего узлов для (, ) и для q-10 ((, ). Если в графе Порядок узла проставлена буква А или В (например 10 А), то для данного узла сравнения следует выбирать строку с тем же порядком и той же буквой. Эту процедуру следует повторять до тех пор, пока не будут обработаны все узлы сравнения более чем второго порядка. Узлы сравнения второго порядка заменяются на ячейки 1 сравнения первого типа.

Время формирования правильного результата сравнения на выходах 9-11 6 tj. На фиг. 4 изображено устройство для , в котором использована иная дисциплина соединения ячеек сравнения в узлы сравнения. В этом варианте соединения ячеек в узлы (как и в любом другом из 560074 возможных вариантов устройства для , кроме изображенного на фиг. 5).время формирования результата на выходах 9-11 устройства превышает 6 t3.

В таблице приведено время формирования результата для устройства с п 100. Там же для сравнения приведена величина Tf ( +l) - время срабатывания устройств с бинарным соединением поддеревьев, в том числе у известного устройства.

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

I. Устройство для сравнения двух п-разрядных чисел, содержащее п/2 ячеек сравнения первого типа и (п/2- -I) ячеек сравнения второго типа,

объединенных в узел сравнения п-го порядка, первый выход которого является первым выходом устройства, причем узел сравнения р-го порядка, где , р- четное,-содержит узлы

сравнения и порядка и ячейку сравнения второго типа, причем рр первый и второй выходы узла сравнения порядка соединены соответственно с первым и вторым входами ячейки сравнения второго типа р-го узла сравнения, первый и второй выходы которой являются соответственно первым и вторым выходами узла сравнения р-го порядка, первыи и второй выходы узла сравнения

р р -го порядка соединены соответстЛЛл

венно с третьим и четвертым входами

ячейки сравнения второго типа р-го узла сравнения, причем узел сравнения второго порядка содержит ячейку сравнения первого типа, первый и второй выходы которой являются соответственно первым и вторым выходами это- ,0 третьим входом этой ячейки сравнения

15

20

25

го узла сравнения, первый, второй, третий и четвертый входы i-й ячейки сравнения первого типа, где ,2,... п/2, являются соответственно входами прямого значения (21-1)-го разряда первого числа устройства, инверсного значения (2i-l)ro разряда второго числа устройства, прямого значения 21-го разряда первого числа устройства и инверсного значения 21-го разряда второго числа устройства, отличающееся тем, что, с целью уменьшения аппаратурных затрат, в него введены первый и второй выходные элементы ИЛИ-НЕ и выходной элемент НЕ, ячейка первого типа содержит первый и второй элементы И и первый и второй элементы ИЛИ-НЕ, причем первый и второй входы ячейки сравнения первого типа соединены со- 30 ответственно с первым и вторым входами первых элементов ИЛИ-НЕ и И, третий и четвертый входы этой ячейки сравнения первого типа соединены соответственно с первым и вторым входами вторых элементов ИЛИ-НЕ и И, выходы первого и второго элементов ИЛИ-НЕ объединены в МОНТАЖНОЕ ИЛИ и соединены с первым выходом этой ячейки сравнения первого типа, выходы первого и второго элементов И объединены в МОНТАЖНОЕ ИЛИ и соединены с третьим входом второго элемента ИЛИ-НЕ и с вторым выходом этой ячейки сравнения первого типа, ячейка сравнения второ- 45 го типа содержит элемент И, элемент НЕ и элемент развязки, причем первый вход ячейки сравнения второго типа

35

40

второго типа, выход элемента развязки объединен в МОНТАЖНОЕ ИЛИ с четвертым входом этой ячейки сравнения второго типа и соединен с вторым выходом этой ячейки сравнения второго типа, первьй выход узла сравнения n-го порядка соединен с первыми входами первого и второго выходных элементов ИЛИ-НЕ, выходы которых являются соответственно вторым и третьим выходами устройства, второй выход узла сравнения n-го порядка соединен с вторым входом первого выходного элемента ИЛИ-НЕ и через выходной элемент НЕ - с вторым входом выходного элемента ИЛИ-НЕ.

где qM/,(c.,) .GCc.GCcj), ..., G(CJ ),...}, j l,2,...oo ,

гдеС(С1)-{°1 ПРИ м1 10 при

Зс.-2«спри q

Ct Cj« l3c -2-0-I )) при q J

F ( )f 1, если kI 0 в противном случае,

где L -8; Ь -ЗЦ-4; Rt te3Ri.+287838

объединен в МОНТАЖНОЕ ИЛИ с выходом элемента И и соединен с первым выходом этой ячейки сравнения, второй вход этой ячейки сравнения второго типа соединен с входами элемента развязки и элемента НЕ, выход элемента НЕ соединен с первым входом элемента И, второй вход которого соединен с

0 третьим входом этой ячейки сравнения

5

0

5

0 45

35

второго типа, выход элемента развязки объединен в МОНТАЖНОЕ ИЛИ с четвертым входом этой ячейки сравнения второго типа и соединен с вторым выходом этой ячейки сравнения второго типа, первьй выход узла сравнения n-го порядка соединен с первыми входами первого и второго выходных элементов ИЛИ-НЕ, выходы которых являются соответственно вторым и третьим выходами устройства, второй выход узла сравнения n-го порядка соединен с вторым входом первого выходного элемента ИЛИ-НЕ и через выходной элемент НЕ - с вторым входом выходного элемента ИЛИ-НЕ.

где qM/,(c.,) .GCc.GCcj), ..., G(CJ ),...}, j l,2,...oo ,

гдеС(С1)-{°1 ПРИ м1 10 при

Зс.-2«спри

Ct Cj« l3c -2-0-I )) при J

F ( )f 1, если kI 0 в противном случае,

где L -8; Ь -ЗЦ-4; Rt te3Ri.+27, 7

Продолжение таблицы

ьгпф

92

V

а&

Zg На

0 П0 Ztg iZg

0706/0 DetD

fftattg

о«Ъ

91 о St( 9&SA

Ј 2ПО)

tt

- /г

eemsi

«Лчм d&cftrf 4I2MW8 dQ AM«fd& H«r«&r«W$ $#di,tM &ЦъЈ

Составитель А.Александров Редактор А.Козориз Техред А.КравчукКорректор Т.Малец

Заказ 142Тираж 558Подписное

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

Производственно-издательский комбинат Патент, г. Ужгород, ул. Гагарина, 101