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

I

Изобретение относится к области автоматики и вычислительной техники и может быть использовано при реализации технических средств цифровых устройств сортировки массивов чисел и в ассоциативных процессорах.Известно устройство для сравнения m,nразрядных чисел, представленных в виде параллельных кодов, содержащее элементы №, ИЛИ, НЕ, предназначенное для определения большего, меньшего из сравниваемых чисел или фиксации нх равенства (1J.

Известное устройство содержит схемы сравнения одноименных разрядов и инверторы, каждая схема сравнения содержнт логические ячейки по числу сравниваема кодов, многовходовой элемент И и иивер.тор; ячейка схемы сравнения старших разрядов содержит элемент И, первый вход н выход которого являются соответственно первым. входом li первым выходом ячейки, а второй вход является входом устройства и соединен с соответствующим входом многовходового элемента И, выход которого соединен со входом инвертора, выход которого соединен с первыми входами всех ячеек данной схемы сравнения; в остальных схемах сравнения ячейка содержит тгервый и второй элементы ИЛИ и элемент И, второй вход которого, является входом устройства н соединен со вторым входом второго инвертора, выход которого соединен со входом инвертора, первый вход элемента И явлйется первым входом ячейки, а выход соединен со вторым входом первого элемента ИЛИ, первый вход которого соединен с первым входом второго элемента ИЛИ и вторым входом ячейки, а выход соединен с

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

Недостатком этого устройства является то, что в нем отсутствует возможность одновременного сравнения кодов числа с одним заданным кодом, что ограничивает функциональпые йозможности и область применения устройства, а также сложна структура логической ячейки. Наиболее близким техническим решением к предлагаемому изобретению является устройство для сравнения m п-разрялных чисел, содержащее п поразрядных узлов анализа, каждый из которых состоит из элементов И, НЕ и m ячеек сравнения, элементы И. НЕ 2., Недостатком -этого устройства является то, что в нем отсутствует возмои ность одновременного сравнения кодов чисе. с одним заданным кодорл, что ограничивает функцнональиые возможности устройства и область его применения. Целью изобретения является расширение функциональных Г5Озможностей устройства путем обеспечения одновременного сравнения всех кодов чй.сел с одним заданным чисПоетавленна55 цель достигается тем, что в устройстве первый вход каждой i-й ячейки сравнении j-ro поразрядного узла анализа, где i I, 2,...jra, j 1, 2,..., {si-i) соединен с входной ШИНОЙ j-ao разряда 1-го сравниваемого числа, первый выход каждой j-й ячейки сравнения J-ro поразрядного узла анализа подключен к одному нз входов первого элемента И, выход которого через элемент НЕ соединен со входом второго элеьзё.чта И, выход которого подключен ко-вторым входам всех ячеек сравнения J-ro поразрядного узла анализа, одни нз входов первого и второго элементов И соединен с управляющими входами поразрядн,ы; узлов анализа, второй и третий выходы каждой 1-й ячейки сравнения каждого i-ro поразрядного узла анализа, кроме первого, подключены соотБетственно к третьему и четвертому входам i-й яче{1ки сравнения (j--|)-го поразрядного узла ана., первый вход каждой -й ячейки сравнения л-го поразряд юго узла анализа и одни кз входов первого а.гземснта И соединены с входной шиной п-го разряда i-ro числа, а выход первого элемента И чер&з элемент НЕ подключен .к одному нз входов второго элемента И, выход которого соединен со вторыми выходами всех ячеек сравнения п-го поразрядного узла анализа, одни из входов первого и второго элементов И подключеггы к управляющим входам п-го поразрядного узла анализа, первый и второй выходы каждой из ячеек сравнения первого поразрядкого узла анализа соединены со входамн соответствующих элемен1Х)в И и НЕ, причем другой вход элемента И подключен к выходу элемента НЕ. Кроме этого, каждай i-ячейка сравнения всех поразрядных узлов анализа, кроме п-го, содержит элементы И, ИЛИ, причем первая и вторая входные шнны ячейки соединены со входами первого элемента ИЛИ и первого элемента И, третий вход которого подключен к третьей BXOAIUJH П1ипе и к одному нз входов второго племен га И, другой вход которого cot/tHfieH с выходом мерного элемента ИЛИ, .четвертая входная тина ячейки cpaBiieHHH (юдключена к одним из входов второго и третьего элементов И.Ш, другие входы которых соединены с выходом первого элемента И н первой входной ичной соответственно, выходы третьего элемента- ИЛИ, второго элемента И и второго элемента ИЛИ подключены к первой, второй и третьей выхбдным шинам ячейки сравнения соответственно. Кроме этого, ячейки сравне1{ия п-го поразрядного узла анализа содержат элементы И и ИЛИ, причем первая и вторая входные 11ины ячейки соединены с одним из входов элементов И .и ИЛИ, а их выходы подключены к выходным шинам ячейки. Сущность пред.лагаемого устройства поясняется схемой, прнведен} ой на фиг. . На фиг. 2 показана структура ячейки сравнения, за исключением ячейки сравнения старизихфазрядов. На фиг. 3 показана структура логической ячейки сравнения тарших разрядов. На фиг. 1-3 используются следующие обозначеиня: элементы И I, входы устройства 2, элементы НЕ 3, входы ячеек сравнения 4,5, ячейки сравнения старших разрядов 6, входы .устройства 7, выходы ячеек сравнения 8, 9, входы ячеек сравнения 10, П, выход ячейки сравнения 12, ячейки сравнения. 13, выходы устройства 14, 5, элемент ИЛИ 16, поразрядные узлы анализа 17. Устройство работает следующим образом. Режим сравнения кодов чисел между собой устанавливается подаче л на входы устройства 2 и 7 потенциалов,соответствуюцднх логической единице. Если в результате сравнения кодов чисел нужно выбрать наименьшее число, то на вход.ы 4 логических ячеек подаются потенциалы, соответст зу ощие значениям разрядов кодов сравпивае.йых чисел; если же в результате сравнения необходн.мо Bbs6paTb наиболыпее число, то на входы 4 логических йчеек подаются потенциалы, соответствуюи..,ие значениям разрядов инверсных кодов сравниваемых чисел. Для этого случая подробно рассмотрим работу устройства, начиная с ячеек сравнения старших разрядов. Если на входы 4 пора.эрядного узла анализа 17 старшего разряда поданы потенциалы, соответствующие логическому нулю, то на выходах 9 всех ячеек сравнения 6 также устанавливаются потенциалы, соответствующие логическому нулю. Если же йа входы 4 всех ячеек сравнения 6 поданы потенциалы соответствующие логической единице, то на выходе многовходового элемента И 1 установится потенциал «, а на выходе элеме} та НЕ 3 потенциал нуля; таким образо.м, потенциал нуля установится на входа.х 5 всех 51чеек сравнения 6, и в силу этого на выходах 9

всех ячеек сравнения б г(оразряд 1ого узла анализа старших разрядов 7 также установится потенциал нуля. Отсюда видно, что потенциал нуля на выходах 9 этого узла устанавливается всегда, когда у сравниваемых чисел старите разряды кодов равны. Если же имеет место неравенство старших разрядов кодов, то на входах 5 ячеек сравнения 8 устанавливается поте1ишал единицы; у тех ячеек сравнения 6, у которых потенциал на входе 4 соответствует единице, на выходе 9 также устанавливается потенциал единицы, а у остальных - потенциал нуля. Так как на входы 4 подаются инверсные значения старших разрядов сравниваемых кодов, то из гфиведенного описания следует, что в случае неравенства старших разрядов потенциал единицы возникает на выходах 9 и тех ячеек сравнения 6, по входам 4 которых подключены меньшие из сравниваемых чисел.

Следуюш.ий поразрядный узел анализа 17 работает аналогично, за исключением того, что если для некоторых чисел из числа сравниваемых при сравнении старших разрядов, было принято решение, что они являются наименьшими, и это было зафиксировано на выходах 9 соответствующих ячеек сравнения 6, то на выходе 9 и на выходе 12 ячеек сравнения 13, соответствующих этим числам, сразу установится потенциал единицы, независимо от значений разрядов кодов, подключенных ко входам 4 этих ячеек. Это обусловлено тем, что вы.ход 9 каждой ячейки сравнения предыдущего поразрядного узла анализа 17 подключен ко входу 11 соответствующей ячейки сравнения последующего поразрядного узла анализа. Если в предыдущем поразрядно.м узле анализа 17 oпpeдe eiш меньшие по значению старших разрядов числа, то при анализе младших разрядов следующим поразрядным узлом анализа 17 эти числа з сравпеиии не участвуют, и выбор большего числа производится только среди оставшиеся чисел аналогично тому, как это производилось в поразрядном узле анализа 17 старших разрядов. В результате на выходах 9 поразрядных узлов анализа 17 младших разрядов устанавливается код, состоящий из всех единиц и нуля, причем ноль устана У1ивается на выходе той ячейки сравнения 13, которая соответствует наибольшему числу нз сравниваемых. Код может также включать несколько нулей, если имеется несколько равных по величине и наибольших по сравнению с прочими числами, или состоять из одних нулей, если все сравниваемые числа между собой равны. Этот код инвертируется элементами НЕ 3 и на выходах 15 устройства такнм образом логическая единица отмечает наибольщее из сравниваемых чисел.

Режим сравнения все.ч чисел с одним R устройслве реализуется путем гюдачи на в.ходы 7 устройства потенциалов, соответствующие уров.ию логического нуля. На Г5холи 4 ячеек сравнения при этом подаются иннерсиые значения разрядов кодов сравниваемых чисел, а на входы 2 подаются прямые значения разрядов кода числа, с которым произвОх1ится сравнение. Так как на входы 7 подан потенциал логического нуля, то в пределах каждой схе.мы яче.чки сравнения будут работать независимо друг от друга. Поэто.му для того, чтобы проанализировать порядок вь полиен1 я операций пр.ч сравнении, достаточно рассмотреть одну цепочку последовательно вю1юченных ячеек сравнения, начиная с ячейки 6. На вход 5 ячейки 6 подан потенциал, соответствуЮ ций прямому значению старшего разряда кода чиста, с которым производится сравнение, а на вход 4 потенциал, соответствующий инверсному старшего разряда кода сраоииваемого числа. Если старшие разряды сравнйваеиых чисел равны ы&жду собой, то на Бы.чоде 9 ячейки сравнения 6 установится потс-ициал, соответствующий логическому нулю, а на вы.чоде 8 - потенциал, соответствующий логической единице. Есдц значение старшего разряда сравиииаемого числа менее значенип старшего разряда числа, с которым пронзвод -;тся сравнение, то на nejJBOM 9- и вч-ором 8 .выходах ячейки сравне Н:я 6 установится потенциалы, соотсетствуюг1и1е логической единице. Е-1сли же значение старшего рчззряла сравмивае.мого чиста больше зна1ения старшего разряда числа,, с KOTOpL iN; про зводится сравьеиие, то на выходе 9 уста ювится г отеьциал нуля, а на выходе 8,- потенциал единицы.

Рассмотрим работу ячейки сравнения 13 из числа ячеек, отьосяши.хся к одному и тому же сравниваемому числу следующего

пораз эядного узла анализа 17. Есл в ячейке сравнения 6 зафиксгфоваио раве1 ство OTapUJHX разрядов, т.е. на входе 10 ячейки сравиеиг я 13 установи-тсп потег) логической единицы, а па входе П потенциал - логяческоЕо нуля, то ртбота ячейки сравмения 13 аналогична работе ячейки сравнения 6. Если же в ячейке сравнения 6 было зафиксировано, что сравннваемое число меньше, то независимо от значений разрядов чисел, сравниваемых в ячейке сравнения 13,

на ее выходе 9 установится потенциал единицы. Если в ячейке сравнения 6 было зафиксировано, что сравниваемое число больше, то независимо от значений разрядов чисел, сравниваемых в ячейке сравнения 13, на ее выходе 9 и на выходе 8 установятся

потенциалы нуля. Работа всех остальных ячеек сравнения 13, относящихся к одному сравнивае.мому числу, аналогична. Из этого следует, что, если сравниваемое число больше числа, с которым производится сравнение, то на выходе 8 и 9 ячейки-сравнения 3 младших разрядов установятся потенциалы логического нуля, а на соотоетствую щих вьаходах устройства 15 и 14 усталовятся потенциалы единицы и нуля соответственно. Если сравниваемое число меньше числа, с которым производится сравнение, то на выходе 9 яч|;йки сравнения 13 младших разрядов установится потенциал единицы, а на соответствующих выходах 14 и 5 устройства - потенциалы нуля. В случае равенства сравниваемых чисел на выходах 8 н 9 поразрядного узла анализа 17 младших разрядов установятся потенциалы единицы и нуля соответственно, а на соответствующих выходах устройства 15 и 14 - гштеициалы единиюЕЫ. Введение в устройство допачнительных связей позволяет не только аыйолнять параллельное сравнение чисел между собой, но и параллельное сравнение всех чисел с одним заданным числом. Это Б СВОЮ очередь при нспользовапии данного устройства в качестве устройства сортировки данных Позволяет не только реализовать алгоритм сортировки данных с последовательным выбором наибольших (наименьших) чисел, но и другиеболее эффективные алгоритмы, включающие отбор всех чисел больших, меньших илк равных заданному числу. Кроме этого, CTaHOBHTCJT возможным применить данное устройство в ассоциативных устройствах o6ga6oTKH информации (процессорах) для одновременного выполнения арифметических операций над несколькими числами.

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

}, Устройство для сравнения т, п-резрйдных Чисел, содержащее п поразряд 1ых узлов анализа, каждый из которых сосгокт из элементов И. НЕ и m ячеек сравнения, элеме11ты И, НЕ, отличающееся тем, что, с целью расишреиия фун1сцйО Ш.( воэг южностей, в нем первый вход каждой i-й ячейки сравнення j-ro поразрядного узла анализа, где 1 1, 2,...,(т), | 1, 2,...,() соединен с входной шнной j-ro разряда i-ro сравниваемого числа, первый выход каждой |--й ячейки сравнення j-ro поразрядного узла анализа подключен к олпощ нз входов первого элемента И, выход которого через ,элемент НЕ соединен со входом второго элемента И, выход котЪрото подключен ко вторым входам всех ячеек сравнения j-ro поразрядного узла анализа, одн1 из входов первого и второго элементов И соединены с управляк) входами поразрядных узлов анализа, второй и третий вь ходы каждой i-й ячейки сравнения каждого j-ro иоразрядного узла анализа, кроме перпого, подключены соответственно к третьему и четвертому входам i-й ячейки сравнения (J - 1)-го поразрядного узла анализа, первый вход каждой i-й ячейки сравнения п-го поразрядного узла анализа и один из входов первого элемента И соединены с входной шикой п-го разряда I-го числа, а выход первого элемента И через элемент НЕ подключен к одному из входов второго элемент та И, выход которого Соединен со вторыми входами всех ячеек сравнения п-го поразрядного узла анализа, одни из входов первого и второго, элементов И подключены к управляющим входам п-го поразрядного узла анализа, первый и второй выходы каждой из ячеек сравнения первого поразрядного узла анализа соединены со входами

соответствующих элементов И иНЕ, причем другой вход элемента И подключен к выходу элемента НЕ.

2. Устройство по п. 1, отличающееся тем, что-в нем каждая i-я ячейка-сравнения всех поразрядных узлов анализа, кроме п-го, содержит элел{енты И,, ИЛИ, причем первая и вторая входные шины ячейки соедт-гены со входами первого ИЛИ и первого элемента И, третий вкод которого подключен к третьей ЕХОДКОЙ шнпе ПК одному HS входов второго элемента И. другой вход которого соедини с выходом первого элемента ИЛМ, четвертая входная шина ячейки сравнения подключена к из входов второго и третьего элементов ИЛИ, другие входы которых соединены с

5 выходом первого злеиекта И и первой входной шиной соответственно, выходы третьего злемеьтз ИЛИ, второго элемента И н второго элемента ИЛИ подключены к первой, второй к третьей выходным шинарл ячейки сравнения соответственно.

3. Устройство по ЯП. 1, 2, отличающееся

TL.-:, что в кем ячейки сравнения it-го поразрядного узла анализа содержат элементы И и ИЛИ, приче& первая и вторая входные шины ячейки соединены с кз

5 входов элементов И И ИЛИ, а выходы подключены к выходным шинам ячейки.

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

1.Степанов А- В.,Ватин В. В. Комбинационная cxefvja сравнения кодов нескольких

50 чисел. - «Автоматика и вычислительная техника, 1974,.№ 5, Рига, «Зинатне, с. 92 - 93.

2.Авторское свидетельство СССР № 446510. кл. О 06 F 7/50, 28.09.7i.

/7