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

Союз Советских Социалистических Республик/18 аеударвтеейиьб хемвтет ссср ее делам нзебретеее и етхрвткйо 05,01.79,бюллетень1 йК 681.З 2 Г,3(088,8) та опубликования описания 07.01,7 Хаокяп(71) Заявите АЗРЯДНЫХ ЧИСЕЛ Изобретение относится к области автоматики и вычислительной техники и может быть Использовано при реализации технических средств цифровых устройств сортйровки массивов чисел и в ассоциативных процессорах.Известно устройство для сравнения гп, и- разрядных чисел, представленных в виде параллельных кодов, содержащее элементы И; ИЛИ, НЕ, предназначенное для определения большего, меньшего из сравниваемых чисел или фиксации их равенства 1.Известное устройство содержит схемы сравнения одноименных разрядов и инверторы, каждая схема сравнения содержит логические ячейки по числу сравииваемеех кодов, многовходовой элемент И и янвертор; ячейка схемы сравнення старших разрядов содержит элемент И, первый вход и выход которого являются соответственно первым. входом ю первым выходом ячейки, а второй вход является входом устройства и соединен с соответствующим входом многовходового элемента И, выход которого соединен со входом инвертора, выход которого соединен с первыми входамн всех ячеек данной схемы сравнения; в остальных схемах сравнения ячейка содержит первый и второй элементы ИЛИ и элемент И, второй вход которого. является входом устройства и соединен со вторым входом второго нивертора, выход которого соединен со входом инвертора, первый вход элемента И является первым входом ячейки, а выход соединен со вторым входом первого элемента ИЛИ, первый вход которого соединен с первым входом второго элемента ИЛИ и вторым входом ячейки, а выход соединен с 10 первым выходом ячейки, выход инвертора. в каждой схеме сравнения соединен с первымн входами ячеек данной схемы сравнения, ячейки, относящиеся к одному срав.ниваемому коду соединены так, что первый выход каждой ячейки предыдущего разря.да, начиная с ячейки старшего разряда,под.ключен ко второму входу ячейки последующего разряда, первый выход ячейки младшего разряда подключен ко входу соответствующего инвертора, выход которого явля.2 В ется выходом устройства.Недостатком этого устройства являетсято, что в нем отсутствует возможность одновременного сравнения колов числа с одним заданным кодом, что ограничивает функ35 40 5 55 1(иональ(е воямжности н обляс(ь примеиенил устройства, а также сложна структу. ра логической ячейки.Наибслее близким техцическим репинем к предлагаемому изобретению является устройство для сравнения гп п.разрядных чисел, содержащее и поразрядных узлов анализа, каждый из которых состоит из элементов И, НЕ и гп ячеек сравнения, элементы И, НЕ 121.Недостатком зтОГО устройства является то, что в нем отсутствует возможность одновременного сравнения кодов чисел с одним заданным кОдом, что ОГранцчивает фуик(еионвлы 1 ые Возможности устроиства и Область его применеец(я,Целью цзобретеция является расшипецце фуе(кц 1цальн (х возможцостсй устройства пут"м ООсспечепия одновременноГО сравнения всех кодов цисел с одним заданным чис- ЛОМ.11 оставлецная цель достигаетсл тем, что В уОО(стве пеы 11 Вуод кзждОЙ 1-й ячейки с 1)авцения ).ГО ПОрязрлднОГО узла аиялизя, Где 1 =-3 е)3 1 =.:2 и 1) гое днцен с входной шиной 1-го разряда 1-го сравиваемс(ГО числа пеВЫЕЕ вь(ход каждои 1-й ячейки сравнения 1-го поразрядного узла а нализа подкл 1 очен к Одному из ВхОЛОВ первого элемента И, Выход которого через элемент БЕ соединен со Входом второго элемента И, Вь(ход кото)ОГО подк(Очеи ко Вторым Входам Вс(зх ячеек сравнеццл 1-ГО по)азряднОГО )зла анализа, Один цз Входов первого и второГО элемее(тов И соедц 1 гецупвавляющцми Входаме( поразрлде(ых з. ЛОВ апалиаа В ГОРОИ И ТРЕТ 111 ВЫХОДЫ Каж дой 1-Й ячейки срав(ения кждог 1-Го по)вэрядиОГО узла анализа к 1)Оме первОГО, подключены соотВетствеццо к третьему и че вертому Входам 31 ячейки сравнения ( - 1) -ГО пораз 1)лдного узла анализа, пе 13" Вый Вхбд каждой 1 1"Й ячейки сравненя и-ГО пораз 1)ядного узла анализа и Один из ВходОВ перВОГО элемента И соединсиы с ВхОдчо)( шциОИ и"ГО 13 азряда 1 "ГО числа, а ВыхОд первого элемента И через элемент НЕ подкл 1 Очен .к ОднОму из ВхОЙОВ ВтОроГО злемее 1- та И, выход которого соединен со Вторыми входами всех яцеек сравнения и-го пораз- ряднОГО узла яиализа Одни из Входов пе 13- вого и второго, элементов И г(одеьочецы к управляющим Входам и-го поразрядного узла анализа, первыЙ и врОЙ хд каждой из лчеек сране(енцл первого поразрядного узла анализа Соединены со да соответствующих элементов И и НЕ, причем другой вход элемента И подключен к выходу элемента НЕ.Кроме этого, каждая 1-ячейка сравнения Всех ораз)ядных узлов анализа, кроме п-го, содержит элементы И, ИЛИ, причем цсрвая н вторая входные шиы ячейки соединены со входами первого элемента И(111 и первого элемецта И, третий вход которого подключе к треЙ вхдой 1( и( н к Одомч из (ходов второго э.(ех(е гз И, дру ОЙ Вход которОГО (о(чИе ( ныходом церо О эле мента ИЛ И, (етвсрта 51 Входяя ц(ия ячс й ки срявеня подключена к одним из входов второго и третьего элементов ИЛИ, другие Входы которых соединены с выхо)ом перВОГО элемента И и первой Входной шиной соответственно, Выходы третьего элемента ИЛИ, второго эдемета И ц второго элемента ИЛИ подкл(очены к первой, второй и третьей выхбде(ым шинам ячейки сравнеил соответстВенно, Кроме зтОГО, ячеЙки сравения и-ГО поразрядного узла анализа содержат элементы И и ИЛИ, причем первая и вторая ВХОДНЫЕ ЦИНЫ ЯЧЕЙК СОЕДИНЕНЫ С ОДИМ из ВходОВ элементов И .и ИЛИ, а их Рллхо. ды подклО(сны к выходным шпям лчеЙки. Сущеюсть предлагаемого устройства поясняется схемОЙ, приведее(ОЙ ця фиГ. 1. На фнг. 2 показана структура ячейки сравнения, за исключением ячейки сравнения саршцУ разряов На фи( 3 покязяця с руктура логической ячеЙкн с 1)Ивения старших разрядов. На фиг, 1 - 3 используются следующие Обозеачепня: элементы И 1, ВхОды устройства 2, элементы НЕ 3, входы лцеек сряВненил 4, 5, ЯчеЙки сравнениЯ стя)ших разрядов 6, входы устройства 7 выходи ячеек сравнения 8, 9, входы ячеек срявее(ня О, 11, выход ччейки сравнения 12, ячейки сравнения 13, выходы устройства 14, 5, злемепт ИЛИ 16, поразрядные узлы яа. лизе 17,;:(стрОЙство работа следу(ощим образом. Режим сравнее 1 ия кодов чисел между сббОЙ устанаВливается подачеЙ ца ВхОды устоойства 2 и 7 потенциалов, соответствующих логической едиеее. Если В 1)езуль. тате сравнения кодов чисел нужно выбрать наименьшее число, то на Входы 4 логических ячеек подаются поте(це(алы сООтВетству(ощие значениям разрядов кодов сравниваемых чиел: если же В результате сра 3- пения необходимо выбрать наибольшее число 10 на Входы 4 логе(че кех ццеек подаютсл еОтенциаль(, соответсте(юц(не эначенилм разрядов ицверсых кодов сравниваемых чисел. Для этого случая подробно рассмотрим работу устройства, цячияя с ячеек с 1)авнения старших разрядов. Если ня входы 4 поразрядного узла анялцза 17 старшего разряда поданы потенциалы, соответствующие логицескому нулю, то на выходах 9 всех ячеек сравнения 6 также устацавливаются потенциалы, ссютветствующие логичес. кому нулю, Если же ця входы 4 всех ячеек сравнения 6 поданы потец(еия,(ы соответству(ощце ЛОГическоЙ едце(ие, то ня Рыходе многовходового злемее(а И 1 установится потецнал , а ня выходе элемента НЕ 3 потенциал нуля; таким образом, п(угепиал нуля установится на Вхс)дах 5 всех,1 чеек сравненя 6, и в силу этого ня выходах 9всех ячеек сравнения 6 поразрядного узла анализа старших разрядов 17 также установится потенциал нуля. Отсюда видно, что потенциал нуля на выхолах 9 этого узла устацавливается всегда, когда у сравниваемых чисел старцгие разряды кодов равны. Если же имеет место неравенство старших разрядов колов, то ца входах 5 ячеек срав. цеция 6 устанавливается потенциал единицы; у тех ячеек сравнения 6, у ко. торых потенциал на входе 4 соответствует единице, на выходе 9 также ус. тянавливается потенциал единицы, а у остальных - потенциал нуля. Так как на входы 4 подаются инверсные значения старших разрядов сравниваемых кодов, то из приведенного описания следует, что в случае неравенства старших разрядов потенциал единицы возникает на выходах 9 и тех ячеек сравнения 6, ио входам 4 которых подключены меньшие из сравниваемых чисел. Следующий поразрядцый узел анализа 17 работает аналогично, за исключением того, что если для некоторых чисел из числа сравниваемых при сравнении старших Г)азрядов, было принято решениечто Онц НВляются наимееьшимии это было зафиксирОВЯИО на выходах 9 соответствующих ячеек срав. кения 6, то на выходе 9 и ня Выходе 12 ячеек сравнения 13, соответствующих этим числам, сразу установится поте)циал единицы, независимо От значений разрядов кодов, подключенных ко входам 4 этих ячеек, Зто обусловлено тем, что выход 9 каждой ячейки сравнения предыдущего пораз. рядного узла анализа 17 подключен ко входу 11 соответствувщей ячейки сравнения последующего поразрядного узла анализа. Если в предыдущем поразрядном узле анализа 17 определены меньшие по значению старц)их разрядов числа, то при анализе младцих разрядов следующим порязрялцьм узлом анализа 17 эти числя В с 1)яВцеции не участвуют, и выбор большего чйсла производится только среди Оставшися чисел аналогично тому, как это производилось в поразрядном узде анализа 17 старших разрядов. В результате на выходах 9 поразрядных узлов анализа 17 младших разрядов устанавливается код, состоящий цз всех единщ и нуля, причем ноль устанавливается иа выходе той ячейки сравнения 13, которая соответствует наибольшему числу из сравниваемых. Код может также включать несколько нулей, если имеется несколько равных по величине и паиболыпих по сравнению с прочими числами, или состоять из одних нулей, если все сравниваемые числа между собой равны. Этот код инвертцруется элсментами НЕ 3 и на выходах 15 устройства таким образом логическая единица отмечает наибольшее из сравниваемых чисел.25 зО 55 4 О 4 ю 55 Режим с)11 цеци 51 Всех сел с ОДи 5 усройс)вереализуется путем пода ц ца Бхг. ды 7 устройства потенциалов, сгютветстцуощие ъровю ЛОГическоГОъля. 1 я Сходы 4 51 еек сравнения при этом цодгк)тся цнверс. цые значения разрялов кодов сравниваемых чисел, а на входы 2 подаютсярямые значения разрядов кода числя, с которым 1 ро. изводится сравнение, Так как на входи 7 подан потенциал лопческого нуля, то в пределах каждой схемы ячейки сравнения будут работать независимо друг от друга, Поэтому для того, чтобы проанализировать порядок ьыполсцця Операций при сравнении, достаточно рассмотреть одну цепочку последовательно В)лоецных ячеек срявце. ция, начиняя с ячецки 6. Ня вход 5 ячейки сравнения 6 подан потенциал, соответствующий прямому значению старшего разряда кода числа, с которым роизводится ср"в. иенце, а ца вход 4 потенциал, соответствующий инверсному зцачеццю старшего разряда кода сраиццваемого числа. Есл стар- ШИЕ РЯЗРЯГГ 1 С 1)ЯВВЯЕМЫХ ЧИСЕЛ РЯВЦЫ МЕЖ- д; сОбОЙ, то на БыхОдс 9 Ячекц сг)ЯВнения 6 УСТЯЦОБИТС 51 ЦОТЕНЦЦЯЛ, СООТБЕТСТБУЮЦНЙ ЛОГичесгому нулю, я ця Выходе 8 - потенцн- ЯЛ, СООТБСТСТБуОГИЙ ЛОГИЧССКОЙ ЕЛ 1 НИ 1 Е, ЕСЛИ ЗЦЯЧЕЦЦС СТЯРШЕГО г)ЯЗРЯЛЯ СРЯЦНИГЯЕ)0- го числа менее значения старшего разряда числя. с которым производится сравнение, то на пе)1 юм 9 и Вором 8 Бьходах ячеЙкц рявцеция 6 хгстя;овцтс 51 гготег 1 ял 11, сш)т- ВЕтСтВУЮЦПЕ ЛОГЦЧССКГ)1 СЛИЦИЦЕ. ЕСЛИ жЕ ЗнацвнгЕ СГ ЯРггвго ВЯЗОВ гга РавгЦБЯЕМОГО г)ИС.За)Г)Л 11 Е ЗИЯЧЕН 1 я СТЯ;)ШС;0 р;Зр);да ЧИСЛЯ С КОТОРЫМ НРОЦЗБОДТСЯ СБЯБЦЕ 1 ЦЕ,гТг Иа ВЫХОДЕ .1 ) СТЯ 0 БИТСН ГготсцЯЛ Н")1 а на Выходе 8 - поте 11 ад едцццы. Рассмотрий ргботу ячцк сг)яцнеция 13 1 З ЧИСЛЯ ЯЧЕЕК, ОТОСЯ).ГИХСЯ К одгОГ 1)г И То)НЕ Р)ЯвигвауоМ) е 1, гу гЕДХвцЕГО поразрялцого узла анализа 7. Если в ячейсрявСпич 6 яг)цк :,р,Вчцо равество ста р 1 вих )азрядов т е 1 Я Входе 1 О яч ейки СранЕц)г 13,СтацОБИтся ОТЕНИЯЛ ЛОГИ- ческой единицы, а ца Вхоле 11 потецал - логическо о нуля, то р)бота ячейки свагцения 13 аналогична рабо ячейки сравнения 6. Если же в ячейке сравценич 6 было зафиксировано, что сравниваемое число мень. ШЕ, ТО НЕЗЯВИСИМО ОТ ЗЯЧЕНИЙ РЯЗРЯДОВ чисел, сравниваемых в ячейке сравнения 3, ца ее выходе 9 усановится потенциал еди. Н 11 цы. Если В ячеике сравнения 6 бьло За. фиксировано, что сравниваемое число боль. ше, то независимо от значений разрядов чисел, сравниваемых в ячейке сравнения 13, на ее выходе 9 и ца Выходе 8 устяш)вятся потенциалы нуля. Работа Всехстальных ячеек сравнения 13, Относящихся к олому сравниваемому числу, аналогична. 11 з этого следует, что, если сравниваемое число боль.ше числа, с которым роизводится сравнение, то ца выходе 8 н 9 ячейки сравнения 3 младших разрядов установятся потеццялы логического нуля, а на соответствую щих ВыхОдах устройстВЯ Ь" и 14 устаОвят.ся потенциалы единицы и цулл соответст.ценно, Если сравниваемое число меньше чцс.ла, с которым производится сравнение, то на Выходе 9 ячейки сравнения 13 младших разрядов установится потенциал единицы, а на соответствующих выходал 14 и 15 устройства - потенциалы уля. В случае раВенства сравниваемых чисел на Выходах 8 и 9 поразряднОГО узла аализа 1 младших разрчдов установятся потенциалы едишщы и нуля соответственно, а на соответствующих выходах устройства 15 и 14 - потенциалы едицицы. Введение в устройство дополнительных связей позволяет не только выОлнять параллельное сравнение чисел между собой, но и параллельное сравнение всех чисел с одшп заданным числом. Это в своо очередь при использовании даНого устройства в качестве устройства сортировки данных пОзвОляет не тОлькО реалцзоваГь алгоритм сортировки данных с "последовательным выбором наибольших (ЯименьпИх) 25 чисел, но и другие более эффективные алгоритмы, Вклочающце отбор всех чисел боль-, ших, меньших или равных заданному ислу.Кроме этОГО, стацОВится Возможым приме" нить данное устройстВО в ассоциятцвных устройствах ОбгЯботк ицфор лац (Процессорах) для одОвреме Ого Вьпол е ия арифметических операций цад несколькими числами.Формула изабретеии1. Устройство для сравнения и, и-разядных сСел, содеркащее п поразрядных узлов анализа, кажд. Нз которых сосоГ из элементов И, НЕ и и ячеек сравнения, элеметы И, НЕ, атлцчоаеесл те,то, с целью расИрея фуИоЯльпь,; о .о, ностей, в нем первый Вход каждой -й лчсйки сравнения ,-го поразрядного узла анализа, где =- 1, 2,(ш),= - " 1. 2и - 1) соединен с ВходнОЙ шиОЙ -ГО разряда -ГО4 сравниваемого числа, первый выход каждой -Й ячейки сравнения 1-Го поразрядного чзлв а".,ализа подключен к Одному цз входов первого элемента И., выход которого через, элемент НЕ соединен со входом второго элемента И, выход которого подключен 5 о ко вторым входам всех ячеек сравнения -го поразрядного узла анализа, однц из входов первого и второго элементов И сое.динены с управляюНими входами поразрлд. цых узлов анализа, второй и третий выходы каждой -й ячейки сравнения каждого 1-го поразрядного узла анализа, кроме первого, подключены соответственно к третьему и четвертому входам -й ячейки сравнения- 1)-го поразрядного узла анализа, первый вход каждой -й ячейки сравнения и-го поразрядного узла анализа и один из входов первого элемента И соединены с входной шиной и-го разряда .го числа, а выход первого элелецтя И через элемент НЕ подключен к одному из входов второго элемента И, выход которого соединен со вторыми входами всех ячеек сравнения и-Го поразрядного узла анализа, одни из входов первого и второго элементов И подключены к управляющим входам и-го поразрядного узла анализа, первый и второй выходы каждой из ячеек сравнения первого поразрядного узла анализа соединены со входами соответствующих элементов И и НЕ, причем другой вход элемента И подключен к выходу элемента НЕ.2. Устройство по и. 1, атличаОщееся тем, что В нем каждая 1-л ячейкаферавнеция Всех поразрядных узлов анализа, кроме п-го, содержит элементы ИИЛИ, причем первая и вторая входные шины ячейки соединецы ср Входами первого элеменга И,Г)И и первого элемента И, третий вход которого подклочен к третьеи входной шПе и к одному из входов второго элемента И другой вход которого соединен с выходом первого элемецтаЛИ, четвеЯя Входная шина ячейки сравнения подключена к одним цз входов второго и третьего элементов ИЛИ, другие входы которых соединень с вьходом п рвоГО элемента И и ервоц Вход. ной шиной соответственно, выходы третьего эле е 1 тя ИЛи второго элемГцтя И и второ.Лемецта И,1 И подлОчеыпервой Взорой и третье Выходным шинам ячейки СЗз Б 11 ел соответствеО.8 Устройство по пп2 ат,ечуацееслЧТО :,:Е:; ЛЧЕи СРЯВНЕЦ.Л П Г- Поразрядного узла анализа содержат элементы И и ИЛИ, причем первая и Вторап входные цНь ячейки соединены с сди ;з входов элементов И ц ИЛИ, а выходы подклочецы к выходным шинам ячейки.Источники информации, принятые во вцимаци=- при экспертизе1. Степанов А. ВВатин В. В. Комбинационная схема сравнения кодов нескольких чисел. - Автоматика и вычислительцял техника, 1974,5, Рига, 3 инатце, с. 92 - 982, Авторское свидетельство СССР448510, кл. С 06 Г 750, 28.09.71.64443 77Составитель В. БелкинТехред О. Луговая Корректор /1. Пебол Тираж 773 Подписное Редактор Э. ГубнннкЗэк аз 754/44 4Фнлна ИПИ Государственного комитета по леван изобретениИ н отк 5. Москва, Ж.35, Раушскан н 3 ГП кПатента, г, Ужгород, ул ьпнй аб. д. 4/5 Г 1 роектнзн