Устройство для сравнения двух n-разрядных чисел

(56) АвторскоеУ 947854, кл. САвторское свидУ 1193659, кл. С Бюл. Ъ 9088.8)свидетел06 Р 7/ ство СС 4, 1980 во СССР 04, 198 етел 06 Р неипа,ния к автома еньшение апппение быстрока (4 кения сх равиоотвзелит яч ого типов азрядногов соответм подде- иплиной яче элеме попар вто ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЭОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР(54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ ДВУХ и-РАЗРЯДНЫХ ЧИСЕЛ(57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения - уменьшение аппаратурных затрат и повышение быстродвйствия. Устройство содержит и/2 ячеек сравнения первого типа и и/2-1 ячеоек сравнения второго типа, объединенных в узлы сравнения, элемент НЕ и два элемента ИЛИ-НЕ. Ячейка срав ния первого типа содержит два элеменИзобретение относится ке и вычислительной техник Цель изобретения - ум паратурных затрат и повь действия,На фиг. 1 представлена ройства; на фиг. 2 и 3 - с ек сравнения первого и вто на фиг, 4 и 5 - схемы 20-р устройства, реализованные ствии с бинарным соединени ревьев и предлагаемой дисц соединения узлов сравнения Устройство содержит и/2 первого типа, (и/2-1) ячее2та ИЛИ-НЕ и два элемента И, выходыкоторых попарно объединены в МОНТАЖНОЕ ИЛИ. Ячейка сравнения второго типа содержит элемент И, элемент НЕ иэлемент развязки. Выход элемента Ис первым входом объединены в МОНТАЖНОЕ ИЛИ. Выход элемента развязкиобъединен с четвертым входом в МОНТАЖНОЕ ИЛИ. Ячейки сравнения образуют в узлах сравнения. древовиднуюструктуру, сбалансированную по длительности формирования сигналов насвоих выходах. Ячейка сравнения первого типа анализирует соотношениедвух смежных разрядов сравниваемыхчисел. Ячейка сравнения второго типаанализируют результаты, сформирован-.ные двумя смежными ячейками сравненияпредыдущего каскада. На выходе устройства формируются сигналы А) В,А=В и А ( В. 1 з.п. ф-лы, 5 ил.,1 табл.фй объединенных в узлы 3 сравнего порядка, выходные элементы ИЛИ-НЕ 5 и 6, входы первого 7 ого 8 чисел, выходы 9-11. аждый узел сравнения р-го поряд- С р (и) содержит ячейку 2 сраввторого типа и узлы ЗРи 3 рСт млния р -го и р-го порядкатственно, причем р +р =р.2ст млсравнения 2-го порядка содерейку 1 сравнения первого типа.йка 1 сравнения первого типа жит элементы ИЛИ-НЕ 12 и 13,ты И 14 и 15, выходы которыхо объединены соединением МОНТАЖНОБ ИЛИ. Ячейка имеет выходы 16 и 17.Ячейка 2 второго типа содержит элементы И 18, НЕ 19 и элемент 20 развязки, первый 21, второй 22, третий 23 и четвертый 24 входы и первый 25 и второй 26 выходы. Выход элемента И 18 объединен с первым входом ячейки МОНТАЖНОЕ ИЛИ, выход элемента 20 развязки объединен в МОНТАЖНОЕ ИЛИ с четвертым входом ячейки. В качестве элемента развязки может ,быть использован одновходовой элемент И (ИЛИ) или многовходовой элемент И (ИЛИ), на другие входы которого подаются постоянные сигналы логической единицы (нуля).Устройство работает следующим образом.На входы 7 и 8 подаются числа А и В соответственно в прямом и инверсном кодах, причем первый разряд является старшим. Каждая ячейка 1 первого типа анализирует два смежных разряда сравниваемых чисел и формирует результат на своих выходах 16 и 17: результат 00, если в анализируемых этой ячейкой разрядах зафиксировано равенство а 1=Ь а 1+,=Ь;+, Результат О 1, если а;Ь или если а,=Ь и а Ь,; результат 1 О или 11,фесли а (Ь., или если а,=:Ь, и а Ь,Р 1Ячейка 2 сравнения второго типа, входящая в состав узла 3 сравненияР р-го порядка обьединяет результаты сравнения, выработанные узлами Зр ,и Зрсравнения р -го и р Р -го порядека с учетом старшинства анализируе - мых этими узлами сравнения разрядов.Ячейка 2 сравнения второго типа, входящая в узел 3 сравнения и-го порядка, формирует на своих выходах 25 и 26 результаты сравнения чисел А и В: 00, если А=В; 01 если А ) В, 10 или 11, если АВ, Эти сигналы преобразуются дешийратором, состоящим из элементов НЕ 4, ИЛИ-НЕ 5 и 6, в сигнал логической единицы на одном из трех выходов 9-11 устройства, если соответственно А С В, А ) В, А=В.Элемент 20 развязки ячейки 2 сравнения предназначен для исключения влияния сигнала, сформированного на втором выходе узла сравнения р -горМЛпорядка и поданного на вход 24 этой ячейки.на состояние выхода элементов НЕ 19 и 18В то же время элемент 20 развязки не препятствует Формированию на выходе 26 ячейки сигналаР 2=Р+Рл, реализуемого соединениемМОНТАЖНОЕ ГЛИ.5Если принять что время срабатываФния элементов И, ИЛИ-НЕ, НЕ и элемента развязки=1 = =1 =Т а, вреи или не эр эф.мя задержки при формировании сиг 1 саласоединением. МОНТАЖНОЕ ИЛИ пренебрежимо мало по сравнению с, то на выходах 16 и 17 ячейки 1 сравнения сигналы будут сформированы через С =2в зс момента подачи кодов сравниваемых чисел.Время формирования сигналов навыходах 25 и 26 ячейки 2 сравненияопределяется какю =шах 1" 81 1 "и+ "э 1 " з "эф 1 -шах+ Поэтому, соединяя ячейки сравненияв определенном порядке, с учетомновой дисциплины соединения узловсравнения можно добиться, чтобы длительности Формирования сигналов навходах ячейки 2 сравнения, входящейв состав узла сравнения с 1-го порядка(4с (и), были сбалансированы.30 Рассмотрим пример построения устройства для п=28 в соответствии спредлагаемой дисциплиной соединенияузлов сравненияУзел 28-го порядка состоит из ячейки 2 сравнения второго типа и узлов28сравнения с 1-го и с -го порядка,28где с 1 мл шах сС(с 1) С(с 2) фС (с д) фС (с),3,40 где =1,2 со причем, так как28=с=п; с=2, то с =Зс -2, т.е,С(с,)=2, С(с)=4; С(сз)=О, С(сл)==10, а с =с-с 1 л=18.Теперь выполняют соединение дляузла 18-го порядка (с=18). Этот узелсостоит из ячейки 2 сравнения и уз 18 1850 лов сс,-го и с -го поРЯдка, пРичемс =шахС(с,),С(с),С(с), 1.Поскольку теперь с 1 Фп, то с;=.Фю5Так как с 1=18 не принадлежит ниному из этих интервалов, то=шах 2, 4, 10, О 1=10. Следовательно,Для узла сравнения 1 О-го порядкаР к(10) =Оф поз ГомуК=1 10 с 1 =шахС(2), С(4), С(10),=4 а с 1 =6,152 Ст Для узла сравнения 8-го порядка 1(с 1 (Р поэтому Р(8)=1, иР(8)= =1, поэтому для узла 8-го порядка20 с =2, с =б, с =18 и с 1 ,=шах С (2), С (6), С (18)=шах 2,6, О,=6.Далее получают для узла 6-го пасрядка с 1 =3, с 1 ст=2, для узла 4-го порядка с 14 =с 1 =2. Узлы сравнения 2-гоО - 4ст мл 25 порядка не разбиваются на другие узлы, а содержат ячейки 1 сравнения первого типа.Устройство для и=28 (фиг. 5) состаит иэ элементов НЕ 4, ИЛИ-НЕ 5 и 6 и узла 3 сравнения 28-го порядка.2Этот узел состоит из ячейки 2, сравнения второго типа и двух узлов 3 5 и 3 сравнения 18-го и 10-го порядка соответственно. Узел 3 сравнения 18-го порядка состоит из ячейки 2, 351 Юузла 3 10-го порядка и узла 30 8-го порядка. Узлы 3 сравнения 10-го по 1 орядка содержат ячейку 2 (2 ) сравнения и узлы 3 и 3 4-го и 6-го поряд 4 Ька соответственно и т.д.На фиг.5 указано время формирования правильных сигналов (в единицах й ) на выходах всех ячеек сравнения с момента поступления кодов сравниваемых чисел на входы 7 и 8 устройства. Правильный результат сравнения будет сформирован на выходах 9-11 устройства через время 6 й с момента поступления кодов сравниваемых чисел на входы.50Результаты расчетов сведены в таблицу.Рассмотрим процесс конструирования устройства с помощью таблицы для и=28. В графе "Разрядность" находят требуемое и=28, Если строк с нужным инесколько, выбирается та, которая отмечена звездочкой, В графах "Старший узел" и "Младший узел" находят порядок соответственно старшего и младшего узлов с 1 18, с 110.Ю 2 ВАналогично находят порядок старшего и младшего узлов для с 1=18 (с 11 т =8 ф с 1 =1.0) и.для с 1=10 (с 1 щб, с 1 сф =4). Если в графе "Порядок узла"млпроставлена буква А или В (например 10 А), то для данного узла сравнения следует выбирать строку с тем же порядком и той же буквой, Эту процедуру следует повторять до тех пор, пока не будут обработаны все узлы сравнения более чем второго порядка, Узлы сравнения второго порядка заменяются на ячейки 1 сравнения первого типа.Время формирования правильного результата сравнения на выходах 9-11 6. На фиг. 4 изображено устройство для и=28, в котором использована иная дисциплина соединения ячеек сравнения в узлы сравнения. В этом варианте соединенияячеек в узлы (как и в любом другом иэ 560074 возможных вариантов устройства для и=28, кроме изображенного на фиг. 5).время формирования результата на выходах 9-11 устройства превышает 6В таблице приведено время формирования результата для устройства с и 100. Там же для сравнения приведена величина Т=(1 о 8 и +1) - время срабатывания устройств с бинарным соединением поддеревьев, в том числе у известного устройства.Формула изобретения1, Устройство для сравнения двух и-разрядных чисел, содержащее и/2 ячеек сравнения. первого типа и (и/2- -1) ячеек сравнения второго типа, объединенных в узел сравнения и-го порядка, первый выход которого является первым выходом устройства, причем узел сравнения р-го порядка, где 4 с р ( и, р - четное,. содержит узлы сравнения р ,-го и р -го порядка иРячейку сравнения второго типа, причем р +р=р, первый и второй выходы узла сравнения р-го порядка соединены соответственно с первым и вторым входами ячейки сравнения второго типа р-го узла сравнения, первый и второй выходы которой являются соответственно первым и вторым выходами узла сравнения р-го порядка, пер 1548783вый и второй выходы узла сравнения р -го порядка соединены соответстРвенно с третьим и четвертым входами ячейки сравнения второго типа р-го узла сравнения, причем узел сравне 5 ния второго порядка содержит ячейку сравнения первого типа, первый и второй выходы которой являются соответственно первым и вторым выходами это О го узла сравнения, первый, второй, третий и четвертый входы д-й ячейки сравнения первого типа, где 1.=1,2, и/2, являются соответственно входами прямого значения (21-1)-го разряда15 первого числа устройства, инверсного значения (21-1)-го разряда второ го числа устройства, прямого значения 21-го разряда первого числа устройства н инверсного значения 2-го разряда второго числа устройства, о т л и ч а ю щ е е с я тем, что, с целью уменьшения аппаратурных затрат, в него введены первый и второй выходные элементы ИЛИ-НЕ.и выходной 25 элемент НЕ, ячейка первого типа содержит первый и второй элементы И и первый и второй элементы ИЛИ-НЕ, причем первый и второй входы ячейки сравнения первого типа соединены со- ЗО ответственно с первым и вторым входами первых элементов ИЛИ-НЕ и И, третий и четвертый входы этой ячейки сравнения первого типа соединены соответственно с первым и вторым входами вторых элементов ИЛИ-НЕ и И, выходы первого и второго элементов ИЛИ-НЕ объединены в МОНТАЖНОЕ ИЛИ и соединены с первым выходом этой ячейки сравнения первого типа, выходы первого и второго элементов И объединены в МОНТАЖНОЕ ИЛИ и соединены с третьим входом второго элемента ИЛИ-НЕ и с вторым выходом этой ячейки сравнения первого типа, ячейка сравнения второ го типа содержит элемент И, элемент НЕ и элемент развязки, причем первый вход ячейки сравнения второго типа объединен в МОНТАЖНОЕ ИЛИ с выходомэлемента И и соединен с первым выходом этой ячейки сравнения, второйвход этой ячейки сравнения второготипа соединен с входами элемента развязки и элемента НЕ, выход элементаНЕ соединен с первым входом элеИЬнтаИ, второй вход которого соединен стретьим входом этой ячейки сравнениявторого типа, выход элемента развязки объединен в МОНТАЖНОЕ ИЛИ с четвертым входом этой ячейки сравнениявторого типа и соединен с вторым выходом этой ячейки сравнения второготипа, первый выход узла сравненияи-го порядка соединен с первыми входами первого и второго выходных элементов ИЛИ-НЕ, выходы которых являются соответственно вторым и третьимвыходами устройства, второй выходузла сравнения и-го порядка соединенс вторым входом первого выходногоэлемента ИЛИ-НЕ и через выходной элемент НЕ - с вторым входом выходногоэлемента ИЛИ-НЕ,2, Устройство по и. 1, о т л ич а ю щ е е с я тем, что, с цельюповышения быстродействия, к третьемуи четвертому входам ячейки сравнениявторого типа узла сравнения и-го порядка, где 4 ( о (п, подключены соответственно первый и второй выходы узла сравнения ц -го порядка,где с,"шах С (с ), С (с ), С (с),где С.(с )= 1 11548783 Старший узел Младший узел Время срабатывания .узла Разрядность Рмл Рс 3 3 3 6 4 73 4 3 4 3 4 4 4 4 6 7 6 7 6 б 6 6 7 7 1 28 А 5 28 А 5 28 А 5 6 6 6 6 б 6 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 24б8 А8 В1548783 Продолжение таблицы 31 ое и(+1 Разрядность Время сраба- Старший узел Младший узел Времясраб атыванияустройства тывания узла 74 76 78 80 82 84 86 88 90 92 , 94 96 98 1 ОО 6 б б б б б 7 .7 7 7 7 7 7 7 5 5 У 5 5 5 4 4 5 5 46 648 6 450 6 452 6 454 б 456 б 4ЗОВУ 332 В 7 334 В 7 336 В 7 338 В 7 340 В 7 314 5 316 5 3 28 А 5 28 А.5 28 А 5 28 А 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 7 4 7 4 8 4 8 4 8 4 8 4 8 4 8 5 8 5 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9Ю 4 д д,з ч в, 8, аа 8 6 ф 7 Ь а,а 8 фо Вют фзаззйч В 1; а,пфе аа Зщ 8 и Ьг фй ф 22 аа фаз Аф аа 635 28 Дгу Дгв вв,иг1548783 А. Козо риз Корректор Т.Мап едакт водственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 10 Эь В Ъ р ь Фиф 4 р, зоставительехред А, Кра" Ъй" % Зеь файв А.Александров чук аказ 142 Тираж 558НИИПИ Государственного комитета по изобретени113035, Москва, Ж, Раушская Щ,Я Яв ф Вф,чь МФ" Ф 9 фФ 8" Подписноеи открытиям при ГКНТ СССРб, д. 4/5