Устройство для определения максимального из @ чисел

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 100881 (21) 3326709/18-24 с присоединением заявки ¹вЂ” (23) Приоритет

Опубликовано 230283. Бюллетень ¹ 7

Дата опубликования описания 230283

Р Ут g> з

0 06 F 7/02

Государственный комитет

СССР ио делам изобретении и открытий

Р ) УДК 681.325. .5(088.8) В.И. Корнейчук, В.П. Тарасенко, А. Й

M. Зеебауэр (ВНР) и В.

« т

Й (72) Авторы изобретения

Киевский ордена Ленина политехничес

Великой Октябрьской социалис

-летия (73) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО ИЗ m ЧИСЕЛ

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

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

И-НЕ, m узлов сравнения, каждый из которых содержит полусумматор, элемент запрета, D-триггер, элемент

И-НЕ (1) .

Недостатком этого устройства является низкое быстродействие.

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

И, регистр результата, элементы задержки, причем вход управления началом работы со динен с первым входом первого управляющего элемента И и с входом первого элемента задержки, выход каждого j -го управляющего элемента И, где j = l 2,... п, n — число разрядов сравниваемых ммсел, подключен к информационному входу j -го разряда регистра результата, инверсный выход каждого первого элемента памяти К-й группы, где К =. 1,2,...т, соединен с первым входом первого элемента И К-й группы, выход каждого из которых подключен к входу установки в нулевое состояние второго элемента памяти К-й группы и к первому входу первого элемента ИЛИ К-й группы, выход каждого P-ro элемента ИЛИ каж15 дой К-й группы, гге Р = 1,2...,(п-2), соединен с первым входом (Р+1)-.го элемента ИЛИ К-й группы, инверсный выход каждого 1-го элемента памяти

К-й группы, где 1 = 2,3, ...,(n-1), подключен к первому входу 1-ro элемента И К-й группы> выход которого подключен к второму входу {Х-1)-го элемента ИЛИ К-й группы, прямой выход каждого. j -го элемента памяти

25 К-й группы соединен с К-ым входом

)-го многовходового элемента ИЛИ, выход каждого из,которых подключен ко второму входу ) -го. Управляющего элемента И, вЫход каждого -го управляюЗО щего элемента H соединен со вторыми

999041 входами j --ых элементов И всех групп (2) .

Недостатком укаэанного устройства является низкое быстродействие, связанное с тем, что цикл сравнения производится поразрядно, т.е. для выделения максимального числа из m двоич-, ных чисел необходимо произвести и тактов поразрядного сравнения, где

n — число разрядов сравниваемых чисел.

Целью изобретения является повышение быстродействия.

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

ИЛИ, m групп элементов ИЛИ, регистр результата., п узлов управления, причем информационные входы устройства 20 соединены с информационными входами элементов памяти групп, прямой выход каждого i-ro элемента памяти j -й группы, где 1 = 1,2. .. n, = 1,2...m, подключен к i-му входу j -rom-входо-25 вого элемента ИЛИ группы, выход каждого из которых соединен с первым входом i-ro узла управления, инверсный выход каждого К-го элемента памя,ти -й группы подключен к первому входу. К»го элемента И j -й группы, где

К = 1,2,... (n-l), выход каждого P-го элемента И каждой j;A группы, где

Р = 1,2,... (n-l), соединен с входом установки в нулевое состояние(Р+1) -ro, элемента памяти -й группы и с первым ( входом (Р-1) -ro элемента. ИЛИ j -й группы, выход первого элемента И каждой группы подключен к входу установки в нулевое состояние второго эле.мента памяти -й группы и к второму 40 уходу первого элемента ИЛИ j -й груп,пы, выход каждого 1-ro элемента ИЛИ каждой ) -й группы .соединен с вторым входом (2+1)-го элемента ИЛИ, где

2 =, 1,2,... n-3 j -й группы, первый 45 выход каждого i-го узла управления соединен с i-ым.входом регистра результата и с вторым входом i-ых элементов И всех групп, вход управления: устройства подключен к второму входу 50 первого узла управления, второй выход каждого К-го узла управления соединен с вторым входом {К+1)-го узла управления.

Кроме того, карый К-ый узел управ- 55 ления состоит из элементов И, ИЛИ, НЕ, элемента задержки, причем первый вход узла соединен с первым входом первого элемента И и через элемент

НŠ— с первым входом второгб элемен-, gp та И, выход которого подключен к первому входу элемента ИЛИ, второй вход узла соединен с вторыми входами первого и второго элементов И, выход первого элемента, И подключен к первому выходу узла и через .элемент задержки к второму входу элемента ИЛИ, выход которого соединен с вторым выходом узла, и-ый узел управления содержит элемент И, первый и второй входы которого соединены с первым и вторым входами узла соответственно, а выход— с первым выходом узла.

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

Устройство содержит m групп элемен4 1 1 % 2

УоВ И 1,, l. — 1„„, 1,, 1, — 1,, „, Я N )Ъ

1,, 1, — 1„ групп элементов ИЛИ

22, — 2п-д, 2„у 22 ., 2п

ITl m tA

?„, 2, ... 2„, ю групп элементов

1 ,памяти 3„, 3, ° ° ° 3,, 3,, 32

m m

Зпp 3 р 3)g ° ° ° g Зя(и П1 Входовых элементов ИЛИ 4, 4, ... 4n, и узлов управления 5, 5, ... 5n каждый из которых состоит из элемента задержки б, элемента НЕ 7, элемента И 8, эле-, мента ИЛИ 9, .элемента И 10, выход 11 устройства, регистр 12 результата, вход 13 управления устройства.

Устройство работает следующим образом.

Перед началом работы регистр 12 результата сбрасывается в нулевое состояние, так же как и все элементы па- мяти 3 перед приемом чисел. В элементы 3 памяти заносятся m, и-разрядных чисел и в устройство поступает импульс начала операции по входу 13 управления устройства, который разрешает прохождение сигнала через элемент

И 10 узла 5< управления. Если хотя бы

:в одном элементе памяти Зо, j = 1 2, m записана единица, сигнал через элемент ИЛИ 4 и элемент И 10 поступает .в первый разряд регистра 12 результата и .записывает в него единицу, этот же сигнал, с выхода элемента И 10 поступает на вторые входы элементов И . Если в i-.ом (i Я(1 2,... i

m) ) числе старший разряд равен нулю, то с инверсного выхода i ão элемента

3 памяти снимается разрешающий потенциал, открывающий элемент.И 1, и на все элементы 3 памяти младших разря- дов i-го числа через элемент ЕЛИ 2 поступает сигнал, сбрасывакщий их в нулевое состояние. 1аким1образом данное число исключается из процесса дальнейшего сравнения. Если на выходе элемента И 10 сформирован был единичный сигнал, то он поступает на элемент 5 задержки управления, обеспечивающий задержку сиг нала на время переключения элементов 3 памяти, и затем, пройдя через управлякщий элемент ИЛИ 9 узла 5 управления, поступает на вход управляющего элемента

И 10 узла 5 управления, обеспечивая обработку второго разряда всех сравниваемых чисел описанным образом. Если в каком-то из обрабатываемых раз999041 рядов всех сравниваемъвс чисел окажутся затн еаниыии нули, то сбрасыванйя в нуль элементов 3 памяти.не потребуется. В этом случае на выходе элемента ИЛИ 4, где 1 — номер обрабатываемого разряда, 1 = 1,2,... (n-l), будет сформирован сигнал нулевого уровня, который, инвертируясь элементом

НЕ 7 1-го узла 5 управления и пройдя через элемент И 8, открытый тем же сигналом, который открывает элемент 10

И i0, через элемент ЙЛИ 9 поступит на вход элемента И (1+1)го узла управления, блокируя таким образом, задержку сигнала элементом 6 задержки. Описанная операция позволяет сократить 15 обработку разряда, не требующего сбро- са в нуль элементов З.памяти, примерно вдвое..

Такюю образом,-предлагаемое устройство позволяет повысить быстродействие в.средием на 16% при среднем повышении аппаратурных затрат на 5,8 в, причем эффективность устройдтва повы.}яается при увеличении числа сравниваемых чисел и числа разрядов. 25

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

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

ИЛИ, в групп элементов ИЛИ, регистр результата, и узлов управления, причем информационийе входы устройства З5 соединены с информационныки входами:." элементов памяти групп, прямой .выход каждого .i-ro элемента памяти j --й группы, где i = 1,2,...п, = 1,2,....

m, ïoäêëþ÷åí к i-ìó входу ) -ro е-вхо- 40 дового элемента ИЛИ группы, выход каж-, дого из которых соединен с первы входом i-ro узла управления, инверсный выход каждого х-ro элемента памяти . -й группы подключен к первому 45 .входу к-ro элемента И .(-й груйпы, где к = 1,2,...(n-l),âûõîä каждого р-го элемента И каждой - ой группы где р = 2,3,...-(n-l}, соединен с входом установки в нулевое состояние (р+1)-го элемента памяти j -й группы и с первым входом (р-1)-го элементаИЛИ j -и группы, выход первого элемента И каждой 1 -й группы подключен к входу установки в нулевое состояние второго элемента памяти -) -й группы и к второму входу первого элемента

ИЛИ -й группы, выход каждого 1-го элемента ИЛИ каждой j -й группы соединен с вторым входом (1+1)-,го элемента ИЛИ, где 1 1,2,...(xi-3), j -й группы, о т л и ч а в щ е е с я тем, что, с целью повышения быстродейст-. вия, в нем первый выход..каждого i-ro узла управления соединен с 1-.ык входом регистра результата и с вторым входом i-ых элементов И всех групп, вход управления устройства подключен к второму входу первого .узла управления, второй выход каждого к-ro узла управления соединен с вторъм входом (К+1) -го узла управления.

2. Устройство по п.l, о т л.и ч а« ю щ е е с я тем, что к-ый узел управления состоит из элементов И, ИЛИ, НЕ, элемента задержки, причем первый вход узла соединен с первым входом первого элемента И и через элемент

НŠ— с первым входом второго элемента

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

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

l. Авторское свидетельство СССР

9 726528, кл.. G 06 F 7/04, 1980.

2. Авторское свидетелЬство СССР по заявке 9 2886601/18-24, кл. 6 06 .F 7/04, 1980 (прототип}.

999041

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

Техред N. Гергель Корректор A- Дзятко

Редактор T. Киселева

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

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

113035, Москва, Ж-35, Раумская наб., д. 4/5

Заказ 1156/71

Филиал ППП Патент, г. ужгород, ул. Проектная, 4