Устройство для сравнения двух n-разрядных чисел
Изобретение относится к области автоматики и вычислительной техники. Цель изобретения - уменьшение аппаратных затрат и повышение быстродействия. Устройство содержит N/2 ячеек сравнения первого типа и N/2 - 1 ячеек сравнения второго типа, объединенных в узлы сравнения, элемент НЕ и два элемента ИЛИ-НЕ. Ячейка сравнения первого типа содержит два элементы ИЛИ-НЕ и два элемента И, выходы которых попарно объединены в "монтажное ИЛИ". Ячейка сравнения второго типа содержит элемент И, элемент НЕ и элемент развязки. Выход элемента И с первым входом объединены в "монтажное ИЛИ". Выход элемента развязки объединен с четвертым входом в "монтажное ИЛИ". Ячейки сравнения образуют в узлах сравнения древовидную структуру, сбалансированную по длительности формирования сигналов на своих выходах. Ячейка сравнения первого типа анализирует соотношение двух смежных разрядов сравниваемых чисел. Ячейка сравнения второго типа анализируют результаты, сформированные двумя смежными ячейками сравнения предыдущего каскада. На выходе устройства формируются сигналы A*98В, А=В и A*98B. 1 з.п. ф-лы, 5 ил., 1 табл.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
„.SU„„1548783
А1 (51)5 С 06 Р 7 04
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ "", -,:
К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ
1 (21) 4440532/24-24 (22) 14,06.88 (46) 07.03.90. Бюл. 1"- 9 (72) В.Н.Горохов (53) 681.325.5(088.8) (56) Авторское свидетельство СССР
N - 947854, кл. G 06 F 7/04, 1980.
Авторское свидетельство СССР
У 1193659, кл. G 06 F 7/04, 1984. (54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ ДВУХ и-РАЗРЯДНЫХ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения — уменьшение аппаратурных затрат и повышение быстродвйствия. Устройство содержит п/2 ячеек сравнения первого типа и n/2-1 ячео ек сравнения второго типа, объединенных в узлы сравнения, элемент НЕ и два элемента ИЛИ-НЕ. Ячейка сравнения первого типа содержит два элеменИзобретение относится к автоматике и вычислительной технике.
Цель изобретения — уменьшение аппаратурных затрат и повышение быстродействия.
На фиг. 1 представлена схема устройства; на фиг. 2 и 3 — схемы ячеек сравнения первого и второго типов; на фиг. 4 и 5 — схемы 20-разрядного устройства, реализованные в соответствии с бинарным соединением поддеревьев и предлагаемой дисциплиной соединения узлов сравнения °
Устройство содержит n/2 ячеек 1 первого типа, (n/2-1) ячеек 2 второго
2 та ИЛИ-НЕ и два элемента И, выходы которых попарно объединены в МОНТАЖНОЕ ИЛИ. Ячейка сравнения второго типа содержит элемент И, элемент НЕ и элемент развязки. Выход элемента И с первым входом объединены в МОНТАЖНОЕ ИЛИ. Выход элемента развязки объединен с четвертым входом в МОНТАЖНОЕ ИЛИ. Ячейки сравнения образуют в узлах сравнения. древовидную структуру, сбалансированную по длительности формирования сигналов на своих выходах. Ячейка сравнения первого типа анализирует соотношение двух смежных разрядов сравниваемых чисел. Ячейка сравнения второго типа анализируют результаты, сформирован= ные двумя смежными ячейками сравнения предыдущего каскада. На выходе устройства формируются сигналы А> В, А=В и А (В. 1 з.п. ф-лы, 5 ил., 1 табл.
1 типа, объединенных в узлы 3 сравнения р-ro порядка, выходные элементы
НЕ 4, ИЛИ-НЕ 5 и 6, входы первого 7 и второго 8 чисел, выходы 9 — 11.
Каждый узел сравнения р-ro порядка (44 р (n) содержит ячейку 2 сравР кения второго типа и узлы 3P и Зp„„ сравнения р -го и р „-го порядка соответственно, причем р +р =р.
2 ст мл
Узел 3 сравнения 2-го порядка содержит ячейку 1 сравнения первого типа.
Ячейка 1 сравнения первого типа содержит элементы ИЛИ-НЕ 12 и 13, элементы И 14 и 15, выходы которых
;попарно объединены соединением МОН1548783
ТАЖНОБ ИЛИ. Ячейка имеет выходы 16 и 17.
Ячейка 2 второго типа содержит элементы И 18, НЕ 19 и элемент 20 развязки, первый 21, второй 22, третий 23 и четвертый 24 входы и первый 25 и второй 26 выходы. Выход элемента И 18 объединен с первым входом ячейки МОНТАЖНОЕ ИЛИ, выход элемента 20 развязки объединен в МОНТАЖНОЕ ИЛИ с четвертым входом ячейки. !
В качестве элемента развязки может ,быть использован одновходовой элемент И (ИЛИ) или многовходовой элемент И (ИЛИ), на другие входы которого подаются постоянные сигналы логической единицы (нуля).
Устройство работает следующим образом. 20
На входы 7 и 8 подаются числа А и
В соответственно в прямом и инверс ном кодах, причем .первый разряд является старшим. Каждая ячейка 1 первого типа анализирует два смежных 25 разряда сравниваемых чисел и формирует результат на своих выходах 16 и
17: результат 00, если в анализируемых этой ячейкой разрядах зафиксировано равенство а1=Ь ., а;„=" результат 01, если а;)Ь,, или если а,=Ь, и а,,„ Ь1,; результат 10 или 11, если а (Ь., или если а,=-b . .и à Э i 1+1 1б 1 Ячейка 2 сравнения второго типа, входящая в состав узла 3 сравнения 35 р-ro порядка обьединяет результаты сравнения, выработа 1ые узлами 3p,и Зр „сравнения р -ro и p P -ro порядр ка с учетом старшинства анализируе— мых этими узлами сравнения разрядов. 40 Ячейка 2 сравнения второго типа, входящая в узел 3 сравнения n-ro порядка, формирует на своих выходах 25 и 26 результаты сравнения чисел А и В: 00, если А=В; 01„ если А > В, 45 10 или 11, если А В. Эти сигналы преобразуются дешийратором, состоящим из элементов HE 4, ИЛИ-НЕ 5 и 6, в сигнал логической единицы на одном из трех выходов 9-11 устройства ес50 ли соответственно А (В, А ) В, А=В. Элемент 20 развязки ячейки 2 сравнения предназначен для исключения влияния сигнала, сформированного на втором выходе узла сравнения р -ro е МЛ порядка и поданного на вход 24 этой ячейки на состояние выхода элементов НЕ 19 и 18 ° В то же время элемент 20 развязки не препятствует формированию на выходе 26 ячейки сигнала F2 с =Г 2 +Г 4, реализ уемо ro соединением Y0HTARH0E 1!ЛИ. Если принять, что время срабатывания элементов И, ИЛИ-НЕ, НЕ и элемента развязки =1 = =t = а,. вреи Или нЕ Эр Э». мя задержки при формировании сигнала соединением. МОНТАЖНОЕ ИЛИ пренебрежимо мало по сравнению с t, то на выходах 16 и 17 ячейки l сравнения сигналы будут сформированы через t =2t 1В 3 с момента подачи кодов сравниваемых чисел. Время формирования сигналов на выходах 25 и 26 ячейки 2 сравнения определяется как t2z=maxft2„; t22+2t,; t +t Э 23 Э 26 шах 12 2 ЙЭ в 2,1 в Поэтому, соединяя ячейки сравнения в определенном порядке, с учетом новой дисциплины соединения узлов сравнения можно добиться, чтобы длительности формирования сигналов на входах ячейки 2 сравнения, входящей в состав узла сравнения q-го порядка (4 < q п), были сбалансированы. Рассмотрим пример построения устройства для п=28 в соответствии с предлагаемой дисциплиной соединения узлов сравнения ° Узел 28-ro порядка состоит из ячейки 2 сравнения второго типа и узлов 28 28» сравнения q„„-ro u q -ro порядка, 28 где с1„,„=шах G(c,),G(c2),С (с ),..., С (с„),...i, где j=l,2,..., eo причем, так как 28=q=n; с„=2, то с,=Зс -2, т.е, G(c,)=2, G(c2)=4; С(сз)=! О, G(c )= =С(с )=. ° ° =О ° Следовательно, q =max(2,4,10,0..1 28 8 кл =10 à q =ц-q =18. Э мл Теперь выполняют соединение для узла 18-го порядка (q=18). Этот узел состоит из ячейки 22 сравнения и уз18 18 лов q,-ro u q „-го порядка, причем q 8 =шах % G (с, ), G (c ), G (с,, ),... 1. Поскольку теперь quan, то с. =. )б f =Зс -2. (1- X F „(с1)), так как L, 8, 1б с1 R,=8; L 2=20, R =26; =56, К =84 и E% т,д., то величина Г F „(q) будет равk--1 на единице, если q--8, или если 20 q <26, или если 56 4 q (84 и т.д. Так как q=IS не принадлежит ни ному из этих интервалов, то X F (I S) =О, и с„,=3с .-2, т. е. к Ф1 =шах1С (2), С (4), G (10), G(28) 154878 к 5д1а i Inn ) 5 =max (2, 4, 10, 0)=10. Следовательно, Для узла сравнения 10-ro порядка .К F (10) =О, поэтому К=1 10 с1 „=шах 1С(2), С(4), С(10),... = =4 à q =6. У Ст Для узла сравнения 8-го порядка L (q сR,, поэтому F „(8}=l, и Р „(8)= k=» =1, поэтому для узла 8-ro порядка 20 с „=2, с =6, с =18 и q„„=max(G(2), G(6), G(l8),...,} =max(2,6,0,...)=6. Далее получают для узла 6-ro noс рядка q „=3, q =2, для узла 4-го порядка q4 =q =2. Узлы сравнения 2-го 4 ст мл 25 порядка не разбиваются на другие узлы, а содержат ячейки 1 сравнения первого типа. Устройство для n=28 (фиг. 5) состаит иэ элементов НЕ 4, ИЛИ-НЕ 5 и 6 и узла 3 сравнения 28-го порядка. Этот узел состоит из ячейки 2, сравнения второго типа и двух узлов 3 и 3 сравнения 18 ro и 10-го порядка соответственно. Узел 3 сравнения 18-ro порядка состоит из ячейки 2, à узла 3 10-го порядка и узла 3 8-ro порядка. Узлы 3 сравнения 10-го по1о рядка содержат ячейку 2 (2 ) сравнения и узлы 3 и 3 4-ro и 6-го поряд4 Ь ка соответственно и т.д. На фиг .5 указано время формирования правильных сигналов (в единицах и ) на выходах всех ячеек сравнения с момента поступления кодов сравниваемых чисел на входы 7 и 8 устройства. Правильный результат сравнения будет сформирован на выходах 9-. 11 устройства через время 6 t с момента поступления кодов сравниваемых чисел на входы. Результаты расчетов сведены в таблицу. Рассмотрим процесс конструирования устройства с помощью таблицы для n=28. В графе "Разрядность" находят 55 требуемое n=28. Если строк с нужным п несколько, выбирается та, которая отмечена звездочкой. В графах "Старший узел" и "Младший узел" находят порядок соответственно старшего и младшего узлов q 18, q 10, 2f 2В Аналогично находят порядок старшего и младшего узлов для q=18 (q ст =8э q„,„=10) и для q=10 (q, =61 q qo =4) . Если в графе "Порядок узла" мл проставлена буква А или В (например 10 А), то для данного узла сравнения следует выбирать строку с тем же порядком и той же буквой, Эту процедуру следует повторять до тех пор, пока не будут обработаны все узлы сравнения более чем второго порядка. Узлы сравнения второго порядка заменяются на ячейки 1 сравнения первого типа. Время формирования правильного результата сравнения на выходах 9-11 6 t,. .Ha фиг. 4 изображено устройство для n=28, в котором использована иная дисциплина соединения ячеек сравнения в узлы сравнения. В этом варианте соединения ячеек в узлы (как и в любом другом иэ 560074 возможных вариантов устройства для n=28, кроме изображенного на фиг. 5).время формирования результата на выходах 9-11 устройства превышает 6 В таблице приведено время формирования результата для устройства с и 100. Там же для сравнения приведена величина Т„=(/log (а +1) — время срабатывания устройств с бинарным соединением поддеревьев, в том числе у известного устройства. Формула изобретения 1. Устройство для сравнения двух и-разрядных чисел, содержащее и/2 ячеек сравнения. первого типа и (и/2-1) ячеек сравнения второго типа, объединенных в узел сравнения n-ro порядка, первый выход которого является первым выходом устройства, причем узел сравнения р-го порядка, где 4 < р (п, р — четное, содержит узлы сравнения р -го и р „-го порядка и р ячейку сравнения второго типа, причем р +р =р, первый и второй выхост мл ды узла сравнения р -го порядка соединены соответственно с первым и вторым входами ячейки сравнения второго типа р-го узла сравнения, первый и второй выходы которой являются соответственно первым и вторым выходами узла сравнения р-го порядка, перI 548783 вый и второй выходы узла сравнения р „-ro порядка соединены соответстP венно с третьим и четвертым входами ячейки сравнения второго типа р-ro узла сравнения, причем узел сравне5 ния второго порядка содержит ячейку сравнения первого типа, первый и второй выходы которой являются соответственно первым и вторым выходами это- 1О . го узла сравнения, первый, второй, . третий и четвертый входы i-й ячейки сравнения первого типа, где i=1,2, п/2, являются соответственно входами прямого значения (21-1)-ro разряда 15 первого числа устройства, инверсного значения (2i- I )-ro разряда второ го числа устройства, прямого значения 21-го разряда первого числа устройства и инверсно ro значения 2 i-ro 20 разряда второго числа устройства, о т л и ч а ю щ е е с я тем, что, с целью уменьшения аппаратурных затрат, в него введены первый и второй выходные элементы ИЛИ.-НЕ.и выходной 25 элемент HE ячейка первого типа содержит первый и второй элементы И и первый и второй элементы ИЛИ-НЕ, причем первый и второй входы ячейки сравнения первого типа соединены со- 3р ответственно с первым и вторым входами первых элементов ИЛИ-НЕ и И, третий и четвертый входы этой ячейки сравнения первого типа соединены соответственно с первым и вторым входами вторых элементов ИЛИ-НЕ и И, выходы первого и второго элементов ИЛИ-HE объединены в МОНТАЖНОЕ ИЛИ и соединены с первым выходом этой ячейки сравнения первого типа, выходы первого и второго элементов И объединены в МОНТАЖНОЕ ИЛИ и соединены с третьим входом второго элемента ИЛИ-НЕ и с вторым выходом этой ячейки сравнения первого типа, ячейка сравнения второ- 45 го типа содержит элемент И, элемент .НЕ и элемент развязки, причем первый вход ячейки сравнения второго типа объединен в МОНТАЖНОЕ ИЛИ с выходом элемента И и соединен с первым выходом этой ячейки сравнения, второй вход этой ячейки сравнения второго типа соединен с входами элемента развязки и элемента НЕ, выход элемента НЕ соединен с первым входом элеИЬнта И, второй вход которого соединен с третьим входом этой ячейки сравнения второго типа, выход элемента развязки объединен в МОНТАЖНОЕ ИЛИ с четвертым входом этой ячейки сравнения второго типа и соединен с вторым выходом этой ячейки сравнения второго типа, первый выход узла сравнения и-го порядка соединен с первыми входами первого и второго выходных элементов ИЛИ-НЕ, выходы которых являются соответственно вторым и третьим выходами устройства, второй выход узла сравнения и-ro порядка соединен с вторым входом первого выходного элемента ИЛИ-НЕ и через выходной элемент НŠ— с вторым входом выходного элемента ИЛИ-НЕ. 2. Устройство по и. 1, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, к третьему и четвертому входам ячейки сравнения второго типа узла сравнения q-го порядка, где 4 «с q п, подключены соответственно первый и второй выходы узла сравнения q Ä-го порядка, где q„„ ax(G(c„),G(c ),G(c ),..., где G.(ñ )= 1 10 при с yq J (Зс.-2 при с1=п; с=2, с 3 " с 3с.-2 (1-;> F„(q)) при цФп; 3 сЙ f 1, если L1, 1 О в противном случае, где L =8 L =ÇL -4 k+s % R =8, R ÇR,+2. 1548783 РазрядНОСТЬ Время сра6атывания узла Старший узел Рмл 72 а 3 6 4 7 3 3 4 6 6 6 б 7 28А5 28 А 5 28 А 5 6 6 б 6 6 28 А 5 28 А 5 28 А 5 28 А 5 ЭОА6 32 А 6 34 А 6 36А6 4 28 А 5 28 А 5 28 А 5 38 А 6 40А6 42 6 44 6 28 А 5 4 б 8 А 8 В "10 А 10 В «12 A 12 В 14 16 18 «20 А 20 В «22 А 22 В 24 А 24 В «26 А 26 В "28 А 28 В «30 А 30 В 32 А 32 В +34 А 34 В 36 А 36 В +38 А 38 В «40 А 40 В 42 44 46 48 52 54 56 58 62 64 66 68 2 4 5 6 7 5 5 5 5 5 5 б 7 7 7 1 2 2 Э 3 3 3 3 3 3 3 3 3 3 3 Э 2 2 2 2 4 3 2 2 б 4 2 2 2 2 2 2 4 3 6 4 8 В 5 10А4 2 2 12 А 5 4 3 14 5 6 4 16 5 8 5 18 5 10 В 6 2 2 2 2 4 3 4 3 6 4 6 4 8 В 5 8 В S 10 В 6 10В6 12 А 5 12 В 7 14 5 16 5 18 6 20 В 6 22 В б 24В6 28 В 6 28 В б 1 1 1 1 2 3 3 3 3 Э 1 2 2 2 2 3 3 3 3 3 Младший узел 2 2 4 3 4 3 6 4 4 3 8 В 5 10 А 4 10В6 10 А 4 10 А 4 10А4 10А4 l8 5 10А4 18 5 10 А 4 18 5 10 А 4 l8 5 10 А 4 18 5 28 А 5 28В6 28 А 5 28 В б 28А5 28Вб 28 А 5 28В6 28 А 5 28 В б 28А5 28В6 28 А 5 28 А 5 28А5 28 А 5 28 А 5 Время jlog п1.+1 срабатывания устройства 1548783 Продолжение таблицы 31од,п(+1 Разрядность Время срабатыв анин узла Старший узел Младший узел Время срабатывания устройства Рст Т» Т Рмл Т23 Т Т 74 76 78 82 84 86 88 92 . 94 96 98 100 6 б б б б 7 . 7 7 7 5 5 5 4 4 4 46 6 48 6 4 50 6 4 52 6 4 54 б 4 56 б 4 ЗОВ 7 3 32В 7 3 34В73 36В 7 3 38В73 40В 7 3 14 5 3 16 5 3 28А5 28 А.5 28А5 28 A 5 28 А 5 28 А 5 56 6 56 б 56 6 56 6 56 б 56 6 84 6 84 6 4 7 4 7 4 7 4 7 4 8 4 8 4 8 4 8 4 8 5 8 5 8 9 9 9 9 9 9 21 «C7, @ 8 д, з ч в, Ф, а 8g bg Яу >r в Ду Дрф 8 о т Ц гзВ» В1 : „а„, и те а„а„, 8f9 8 а>, а, 2 22 а„а„ 4з я а„д, +5 +24 gqy 7гв в„в, 1548783 Фиг. 1548783 Редактор А. Ко зо риз Корректор Т.Малец Заказ 142 Тираж 558 Подписное ВНИЯПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб,, д. 4/5 Производственно-издательский комбинат "Патент", r, Ужгород, ул. Гагарина, 101 Ф4ф у y) @ 5a ъ (р ъ ф ъ ф Ь ф чь ©l t® O w C3 у в Составитель А.Александров Техред А. Кравчук ъ фЬ а ю ь Ф в Фз Ф9 (Вм
