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

 

Союз Советских

Социалистических

Республик

< и 644443 (6!) Дополнительное к авт. свил-ву(22) Заявлено 20.02.76 (2! ) 2327130/18-24 с присоединением заявки № (23) Приоритет

Опубликовано 05.01.795юллетень ¹ 1

Дата опубликования описания 07.01.79 (5l) М. Кл, ц06 F 7/04

Гкудаувтейхиьб х5мвтВТ ссср ва делам кзебретвей к агх пкй (Я) УДК 681.З25. .53 (088.8} (У2) Автор изобретения

IO. A. Хаскяи

P l) Заявитель (54) УСТРОЙСТВО ДЛЯ СРЛВг1ЕНИЯ m,é- АЗРЯДНЫХ ЧИСЕЛ

Изобретение относится к области автоматики и вычислительной техники и может быть использовано при реализации технических средств цифровых устройств сортировки массивов чисел и в ассоциативных процессорах.

Известно устройство для сравнения m, празрядных чисел, представленных в виде параллельных кодов, содержащее элементы

И; ИЛИ, НЕ, предназначенное для определения большего, меньшего из сравниваемых чисел или фиксации их равенства jl j.

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

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

Недостатком этого устройства является то, что в нем отсутствует возможность одновременного сравнения колов числа с одним заданным кодом, что ограничивает функfi414 (:!

Я5

5D

55 ционалы}ые ВОзм«жности «Об. }Яс! ь прим(. иенил устройства, а также сложна с}руктура логической ячейки.

Наиболее близким техническим репи ««ем к предлагаемому изобретен!}ю является устройство для сравнения m H-разрядных чисел, содержащее п поразрядных узлов анализа, каждый из которых состоит из элементов И, HE H m ячеек сравнения, элементы

И, HE (2j.

НедОстятком 3Tof 0 устройства явллетсл то, что н нем отсутствует возможность одновременного сравнения кодов чисел с одНИМ ЗЯДЯННЫМ КОДОМ, ЧТО ОГРЯНИЧИВЯЕТ ФУНКцHGHBJIb«bte возможности устроистня H область его применения.

j IeqbK2 tz0gpe-;eHH5I )твл5!етс51 расшиоение функцнОнальных Возможностей уcTpOAcTB3 путем обсспечепия одновреме}!ного сравнения всех кодов чисел с одним заданным чисЛОМ.

j jocT3BJIe}tI}35I цель достигяетсл тем, что

В у> i)oцстне перрый BYof} каждой j II ячеЙки сравнения 1-10 ПО(эязряднОГО узла яиялизя, Где i =- (, 2,...,(п, ) =-- j, 2,..., (и — 1) соединен с входной шиной 1-30 разряда 1-го сРЯнниваемого ftePBhIA Bbfxof!, кажДОЙ

1-й ячейки сравнения 1-го поразрядного узла янялиза подклlОчен к ОднОм)> из ВхОдОВ

f!epBot 0 элемента И, ВыхОд которого через элемент БЕ соединен со Входом второ" î элемента И, Вь}ход которОГО подк 1!Очеи Ko BTGрым входам Всех ячеек сравнения 1-Го noP33PHÄÍ0Ã0 ) ЗЛЯ Э НЕ)ЛИЗЯ, ОДИН НЗ ВХОДОВ первого и второго элементов И соеди}ген

Упв" в}}Я}0>щ(>ми и (Од3мн !10РЯзР5!диы;((i3 лов анализа, в Горои H третий выходы каждой i-Й ячейки сравнения каждого i-го порязрлдног0 узла анализа, кроме первого, подключены соответственно к третьему и че вертом) входам t" и ячейки срВВНВННН (j — 1)-го порязрлдного узла ае}ализа, перВЫЙ ВХОД Каждойl 1 "И Я "Ейкн СРЯВНЕНИЯ il-ГО поразрлпно}0 узла анализа и один из ьходОВ He(2BGro элемента И соединсиы с ВхОдНОИ ШИНОЙ П-ГО (ЗЯЗРЯДЯ I-ГО ЧИСЛЯ, 3 ВЫХОД первого элемента И через элемент НЕ подклlбчен .к ОднОму из ВхОдОВ BTGporo элемента И> ВыхОд KGToporo СОединен со ВтООыми

Входами Всех и ieeK сраниення и-ГО ПОразряд ного узла аня >)изя Од!)и «3 Входов !)ep

B0ro и второго элементов H подклlочены к управляющим входам ri-го поразрядного узла анализа, первый и второй выходы каждой из ячеек (.p38«eHHII пер .)ОГО по()язрядИОГО )")Ë3 ЯНЯЛИЗЯ СОЕДИНЕНЫ CG ВХОДЯМИ соответствующих элементов И и НЕ, причем другой вход элемента И подключен к выход) злеMCHT3 НЕ.

Кроме этого, каждая i-ячейка сравнения всех поразрядных узлов анализа, кроме и-го, содержит элементы И, ИЛИ, причем псрвал и вторая входные шипы ячейки соединены со входами первого элемента И„ПИ «первого элемента И, третий вход которого п«дключе«

TP(.i h(Й нх«. е}}«}! Ii« li(H K «}е«()м> > HB е\ход«н Бт«рОГ«э. }(м(и Гя И, дру! ОЙ ВхОд к«торОГО (<)ед««(>«с Выход()м и j)«()! 0 элемi. íò3 И.Г1И, ч(тBcpò3л Входная п}и«я лч(Йки сравнения подключена к одним из входов

Второго и третьего элементов ИЛИ, другие

ВХОДЫ KOTOPblX СОЕДИН(Hbl С БЫХ )flOM ПЕРВОГО элемента И H t}epBOII Bxof(HOB шинОЙ cOÎTветственно, выходы третьего элемента ИЛИ, второго BJ!eMCI}Ta И и второго элемента ИЛИ подкл}очены к первой, второй и третьей выхбдным шиiiaM ячейки сван«ения соотнетстBe««0 Кр051е этОГО, ячеЙки сравнения и-ГО поразрядного узла анализа содержат элементы И и ИЛИ, причем первая и вторая

ВХОДНЫЕ H!ИНЫ ЛЧЕЙК«СОЕДИН(.«bl из ВхОдОВ элементов И и ИЛИ Я нх нь!хо ды подкл!очены к выходным шипам ячейки.

Су!цность предлагаемого устройства поясняется схем>ОЙ, «риведе«ной i!3 фиг. 1.

На фиг. 2 показана структура ячейки сравнения, зя исключением ячейки сравнения

c I 3ðm«x.р3зрлд0в. j-j3 yHf ., 2 показана сгруктувя АОГическои ячеЙки сравнения стяl)ц!Их разрлдон. На фиг. 1 — 3 используются следующие Обозе}ячепн)1: BJ!eMCHTb! И 1, устройства 2, элементы HE 3, входы лчеек сряВненил 4, 5, ячейки сравнения ста()шнх разрядов 6, входы устройства 7, выходы ячеек сравнения 8, 9, входы ячеек сра>в«ения ! О, 1 j, выход ччейки сравнения 12. ячейки сравнения. 13, выходы устройства 14, !5, элемент ИЛИ 16, поразрядные узлы я«а.>!Изя (7.

;1стройство работает следу}оп!им Обра30м. j eNим ср3вненHH кодов чисeJI между собой устананлинаетсл подачеЙ h3 входы устпойстня 2 и 7 потенциалов, соотнетству-!

Ощих логической единице. Если в результате сравнения колов чисел нужно выбрать наименьшее число, TO HB Входы 4 логичеcких ячеек подяк)тся потенциалы, cOÎTBBTcTВУ!ОЩИЕ ЗНЯЧЕНИЯМ РЯЗРЯДОВ КОДОВ СР38«НВяемых чисел:, если же В резулbT3те с03Впения необходимо выбрать наибольшее число, то íà Bxofttë 4 логических ичеек под3ЮТСЯ ПОТЕНЦИЯЛЫ, СООТВЕТСТВУЮЩИЕ ЭНЯЧЕнилм разрядов инверсных кодов cp3BtilHOB подробно р3ссмотрим работу устройства, нячн«яя с лчеC p 3 B H(". H H H CT 3 p LU H X p 3 3 pB>i3 0 B. Е сл и входы 4 поразрядного узла 3«3JI«33 (7 старшего разряда поданы потенциалы, соответствующие логическому нулю, то на выходах 9 всех ячеек сравнения 6 также устанавливаются потенциалы, ссютветствующие логическому нулю. Если же на входы 4 всех ячеек сравнения 6 поданы потенциалы соответствующие лОГическОЙ единице, То на выходе многовходоного элемента И 1 уста «Овнтся

«Отенциял «!», я на выходе элемента НЕ 3 потенциал нуля; таким образом, п<)те!}}!}!я.:! нуля установится на входах 5 всех,>чеек сране}еннл 6, и в силу этогo «а выходах 9

641443 всех ячеек сравнения 6 поразрядного узла анализа старших разрядов 17 также устаH0BHTcR потенциал нуля. Отсюда видно, !TÎ потенциал нуля на выходах 9 этого узла устанавливается всегда, когда у сравниваемых чисел cTBpf((«e разряды кодов равны.

Если же имеет место неравенство старших разрядов колов, то на входах 5 ячеек сравнения 6 устанавливается потенциал единицы; у тех ячеек сравнения 6, у которых потенциал на входе 4 соответстВует единице, на выходе 9 также устанавливается потенциал единицы, а у остальных — потенциал нуля. Так как на входы 4 подаются инверсные значения старших разрядов сравниваемых кодов, (о из приведенного описания следует, что в случае неравенства старших разрядов потенциал единицы вози«Кает иа выходах 9 и тех ячеек сравнения 6, но входам 4 которых подключены меньшие из сравниваемых чисел.

Следующий поразрядный узел анализа 17 работает аналогично, за исключением того, что если для некоторых чисел из числ3 сравниваемых при сравнении старших разрядов, былО fl pH нято решение, чтО oHH я Вл я lотся наименьцн(ми, и это было зафикси1?она«о на выходах 9 соответствующих ячеек сравнения 6, то на выходе 9 v на Выходе 12 ячеек сравнения 13, соответствующих этим числам, сразу установится поте!щи л ед«ницы, независимо of значений p33pf!30B кодов, подключенных ко входам 4 этих ячеек. Зто обусловлено тем, что выход 9 каждой ячейки сравнения предыдущего поразрядно"0 узла анализа 17 подключен ко входу 11 соответствующей ячейки сравнения последующего поразрядного узла анализа.

Если в предыдущем поразрядном узле анализа 17 определены меньшие по значению

cT3pfHHx разрядов числа, то при анализе млад!инх разрядов следующим поразрядным узлом анализа 17 эти числа в cp3BIIB! не участвуют, и выбор большего чйсла производится только среди Оставши;;ся чисел аналогично тому, как это производилось В поразрядном узле анализа 17 старц!их разрядов. В результате на выходах 9 поразрядных узлов анализа 17 младших разрядов устанавливается код, состоящий из всех единиц и нуля, причем ноль устанавливается иа выходе той ячейки сравнения 13, которая соответствует наибольшему числу из сравниваемых. Код может также включать несколько нулей, если имеется несколько равных по величине и наибольших по сравнению с прочими числами, или состоять из одних нулей, если все сравниваемые числа между собой равны. Этот код инвертируется элементами НЕ 3 и на выходах 15 устройства таким образом логическая единица отмечает наибольшее из сравниваемых чисел.

2х

3(( з5

4О з ю

РЕЖИ Ы CPi! E3ÈÅH« I! ВСЕХ iè((1 С OËÍ«!!I 8 устpojlclве 1?еализуется путем подачи на Вх<(ды 7 устройства иотенц«алов, соответстиу(Ощне ров((о лоп .ческого ((ля. !13 гходы 4 ячеек сравнения при этом подаются 1!HBерсиые значения разрядов кодов сравниваемых чисел, а на Входы 2 подаются прямые значения разрядов кода числа, с которым производится сравнение. Так как на входи 7 подан потенциал лоп(ческого нуля, то в пределах каждой схемы ячейки сравнения будут работать независимо друг от друга.

Поэтому для того, чтобы проанализировать порядок ьыполнсн«я Операц«й при сравнении, достаточно рассмотреть одну цепочку последовательно в(:?-!Оченных ячеек сравнения, начиная с яче«ки 6. На вход 5 ячейки сравнения 6 подан потенц«ал, соответствующий прямому значению старшего разряда кода числа, с которым производится ср"внение, а на вход 4 поте(щиал, соответствующий инверсному зпаче;шю старшего разряда f(0ji3 сp3«lti!B3(!HOf0 ч«(ча. ЕС3« СТ3рц(ие P33j;.«(I(,(С113ВИ«вас(IRx Hccл Равны,;(е?иду c000A, TO H3 Bhlx0.(1 9 H IBÉHI! сравнения 6 установится потеиц!!ал, cooTBt TcTB)!юц(ий Jjor«-!Bcl(o! нулю, 3 «3 Выходе 8 — потенци3f, c00fBcTcTBу!Оп(и!1 л(?! «чсской един(1((е. Есл«3!t3!BH«с старшего разряда сравш!Ваемого числя менее значен«л старшего разряда числа. с которым произиод«тся сравнение, То на первом 9 и В(ором 8 В!.,(ходах ячейки

cp3BlIBfIf!я 6 1 ст311(?В(1тс!1 (!Отенш(алы, cooiветствующпе ло: пиеской един«це. Если же

3jf3uejHtB CT3P1Hel 0 j!P3DP ДB СРВВН«вс(ЕМОГО

0«.! (>(i!B 3!(3 !Bн «я (Тапшс(ii p33pH, !3 чн .,(13> с 1(отОры1.* jj110((звод!(тся (!!ВВ!«ение, ! (О на Вы?:оде i ycTановится (ю;(!i!1;iал ну„(я, 3 на Выходе 8 — !!OT(«i! ци?lл един«цы.

Рассмотрим работу Я1!е!(к«сра Биения 13

If3 числа ячеек, оп(исящи. ся к одному и томъ же с )3ВИ((ваемому 1!!" !у cтеду(оц его поразрядного узла анал«за !7. Если в ячейке сравнения 6 33(liHHclipOBBI(0 раве! .сТВо ст31?1й»x р33р«30В, т. е. i!3 Входе 10 ячейки (р .1В Bi (< 1 3 у(T3j!0! 1(TÃß (1(?те(12! !j3 ло -и ческой единицы, а на Входе l1 потенциал— логическо о нуля, то работа ячейки сравнеHHH 13 аналогHHHB работе R!IBjf((ji сраВнсния 6. Если же в ячейке сравнеHHB 6 было зафиксировано, что сравниваемое число меньШЕ, TG Н(ЗВВИСИМО ОТ З«3ЧЕНИй P33PBДОВ чисел, сравниваемых в ячейке срВВНСН>!Н 13, на ее выходе 9 ус(ановится потенциал единицы. Если в ячейке сравн"-ния 6 было зафиксировано, что сравниваемое число больше, То независи (о от значений разрядов чисел, сравниваемых в ячейке сравнения 13, на ее выходе 9 и на B (ходе 8 усташ?вятся потенциалы нуля. Работа всех остальиых ячеек сравнения 13, относящихся к одному сравниваемому числу, аналогична. 11з этого следует, что, если сравниваемое число боль64 i 143 ше числа, с которым производится сравиеННе, то на выходе 8 и 9 ячейки сравнения

13 младшлх разрядов установятся потенциалы логического нуля, а на соответствую щих ВыхОдах устройстВа Ь" и 14 )ста!!Овятся по-енциалы единицы и иулл соответстВенно. Если сравниваемое число меньше числа, с которым производится сравнение, то на Выходе 9 ячейки сравнения 13 младших разрядов установится потенциал единицы, а на соответствующих выходах 14 и 15 упройства — потенциалы нуля. В случае равенства сравниваемых чисел на выходах 8 и 9 поразряднОГО узла анализа 17 младших разрчдов установятся потенциалы едишщы и нуля соответственно, а на соответствую щих выходах устройства 15 и 14 — потенциалы единицы. Введение в устройство дополнительных связей позволяет ие только

Выполнять параллельное сравнение чисел между собой, но и параллельное сравнение всех чисел с ОД1(им заданным числом. Это в сво(о очередь при использовании да!иного устройства в качестве устройства сортировки данных позволяет не только реализовать алгоритм сортировки данных с последовательным выбором наибольших (наимеиьп(их) чисел, но и другие более эффективные алгоритмы, вкл(очающие отбор всех чисел боль-, ших, меньших или pBBHbIx заданному Iислу.

Кроме этого, станОВится Возмои(ным п13именить даннОе уcTpoffcTBQ В ассоциати Вяых устрОЙствах ОбДаботки иц(1)О1)мации (процессорах 1 для (3д1цэврсм ецио! о Выполнения арифметических операций иад несколькими числами.

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

1. Уст1)ойстВО для сравнения 1ть и-разрядных чисел, содержащее и поразрядных узлов анализа, кажд1.!11 из которых cocro!! f из элементов И, hL u HI ячеек сравнения, элементы И, НЕ, атлича(ащггея тем, что, с 4(1 цел!,ю расширения футц(п(попал ь;! -.:: Bоз О;:.иостей, в нем первый Вход каждой i-й ячейки сравнения,-го поразрядного узла анализа, где i =- 1, 2,...,1тп), j = — 1, 2,...„(п — l) соединен с входнОЙ шинОЙ 1-(о разряда 1-го

Я сравниваемого числа, первый выход каждой i-Й ячейки сравнения 1-го поразрядного чзлв ацализа подключен к гздиому из входов первого элемента И., выход которого через, элемент HE соединен со входом второго элемента И, выход которого подключен 50 ко вторым входам всех ячеек сравнения

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

1-го поразрядного узла анализа, кроме первого, подключены соответственно к третьему н четвертому входам i-й ячейки сравнеиил (j — 1) -го поразрядного узла анализа, первый вход каждой 1-й ячейки сравнения и-го поразрядного узла анализа и один из входов первого элемента И соединены с входной шиной и-ro разряда i-го числа, а выход первого элемента И через элемент HE подключен к одному из входов второго элемента И, выход которого соединен со вторыми входами всех ячеек сравнения и-го поразрядного узла анализа, одни из входов первого и второго элементов И подключены к управляющим входам и-го поразрядного узла анализа, первый и второй выходы каждой из ячеек сравнения первого поразрядного узла анализа соединены со входами соответствующих элементов И и НЕ, причем другой вход элемента И подключен к выходу элемента HE.

2. Устройство по и. 1, отличающееся тем, что -В нем каждая i-л ячейкаеравнения Всех поразрядных узлов анализа, кроме п-го, содержит элементы И., И-.1Ц1, причем первая и вторая входные шины ячейки соединены СО входами первого элеме:1та

И,г1И и первого элемента И, трети" ехоп которого подкл(очрн к третьеи Bxодной !Нине ц к ОдиОму из Входов ВтОрОГО элемента И другой вход которого соединен с вь(ходом первого эле(цр;1та (",Яи, четве ая Bxon«л ши(га ячейки сравнения подключена к одним -IB входов второго и третьего элементов

ИЛИ, другие входы которых соединены с в! ходой H PBQ(o B feffeHTB H и п f" Bofч в од.

HOf". ШИНОЙ СООТВРТСТВЕННО, ВЫХОДЫ ТРЕТЬЕГО эле1,",еита ИЛИ второго элемента И и второ1О злемецта И.,11И под.(л(очеиы к первой, В-го13ой и третьей выходцым шицам ячейки

"pзБиенил cooTBeTcTÂeffío.

3, Устро((ство 110 HA 1 2, ат гичающеесяя тБ в::е:,.: лчеик(1 с13авценил i го !1(3разрядного узла анализа содержат элементы И и ИЛИ, причем первая и Вторая вход,ные 11НН! ы ячейки соединены с одц(:-:.:.:и входов элементов И и ИЛИ, а выходы Нопклк1чецы к выходным шинам ячейки.

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

l. Степанов A. B.,ÂàTHH В. В. Комбинационная схема сравнения кодов нескольких чисел. — «Автоматика и вычислительцал техника», 1974, № 5, Рига, «3инатне», с. 92—

93

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

64!443

17 I

1S 14 lt

Фяа.1

Фиг,у

Составитель В. Белкин

Техред О. Луговая Корректор Л. Пебола

Тираж 773 Подписное

Редактор Э. Губннцкаи

Зэк аз 75 I 4/44!

П!ИИПИ Государственного комитета СССР по делам изобретений н открьпий

I I. I0:I5. Москва. Ж-35, Раушскаи наб. д. 4/5

Филиал Illlll Патента, г. Ужгород, ул. Г1роектнаи. 4