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

 

УСТРОЙСТВО ДЛЯ ВЬЩЕЛЕНИЯ МАКСИМАЛЬНОГО ЧИСЛА, содержшцее (л . групп элементов И, m групп элементов памяти, где m - число сравниваемых двоичных, чисел, элементы ИЛИ, управляющие элементы И, регистр результата и элементы задержки, причем Вход управления началом работы устройства соединен с первым входом первого управляющего элемента И. и входом первого элемента задержки, выход г -го элемента задержки (где i 1, 2..., (п-2)J м - количество разрядов сравниваемых чисел) подключен к первому входу ( +1)-го управляющего элемента И и входу (+1)-го элемента задержки, выход (n-l).-ro элемента задержки соединен с выходной шиной устройства, прямой выход первого элемента памяти К-и группы (где k 1, 2,...,m) соединен с k-м входом первого элемента ИЛИ, о тличающе е с я тем, что, с целью упрощения устройства, в негр введены элементы НЕ, причем вход ) -го элемента НЕ (где , 2, ..., Ч) соединен с выходом j-го элемента ИЛИ, а выход подключен к второму входу j-го управляющего элемента И, выход которого подключен к входу установки в нуль j-го разряда регистра результата и входам установки в единичное состояние j-х элементов па (Л мяти всех групп, выход первого элемента памяти k-и группы соединен с с первым входом первого элемента И той же группы, выход 8 -го элемента И k-й группы (где 1, 2,..., (h-2) подключен к первому входу (-И)-го элемента И той же группы, второй вход р-го элемента И k-й группы (где , 2,...,

СОЮЗ СОВЕТСНИХ

OUWI

РЕСПУБЛИК (19) (Н) >(5O G 06 F . 04

ОПИСАНИЕ ИЗОБРЕТЕНИ

Н ABTOPGHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

Д Ю (21) 3458684/18-24 (22) 29.06.82 (46) 23 ° 09.83. Бюл. 9 35 (,72) В.И.Корнейчук, Марта Зеебауэр, A.Ï.Ìàðêoâñêèé и В.П.ТАрасенко (71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (53) 681.325.5(088.8) (56) 1. Авторское свидетельство СССР

В 444180, кл . G 06 F 7/04, 1972.

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

9 877523, кл. G 06 .F 7/04, 1980, 3. Авторское свидетельство СССР

Р 875376, кл. G 06 F 1/04, 1980 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ВЦНЕЛЕНИЯ

МАКСИМАЛЬНОГО ЧИСЛА, содержащее в групп элементов И, щ групп элементов памяти, где щ - число сравниваемых . двоичных. чисел, элементы ИЛИ, управляющие элементы И, регистр результата и элементы задержки, причем вход управления началом работы устройства соединен с первым входом первого управляющего элемента И и входом первого элемента задержки, выход i. -го элемента задержки (где =1, 2..., (n-2); п - количество разрядов сравниваемых чисел) подключен к первому входу (j +1) -го управлякщего элемента

И и. входу (i+1) -го элемента задержки, выход (n -1).-го элемента задержки соединен с выходной шиной устройства, прямой выход первого элемента памяти )(-й группы (где k =.1, 2,...,й) соединен с k -м входом первого элемента

ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, в него введены элементы НЕ, причем вход -го элемента НЕ (где ) =1, 2, ..., и ) соединен с выходом j "го элемента ИЛИ, а выход подключен к второму входу j --го управляющего элемента

И, выход которого подключен к входу установки в нуль j -ro разряда регист. ра результата и входам установки в

Р единичное состояние j -х элементов памяти всех групп, выход первого элемента памяти k-й группы соединен с первым входом первого элемента И той С же группы, выход -ro элемента И

k-й группы (где 6 =1, 2,..., (и-2) Я подключен к первому входу (0+1)-го . элемента И той же группы, второй вход p--ro элемента И k-й группы (где

1, 2,..., (й-1) соединен с выходом (P+1)-го элемента памяти той же

iiгруппы, выход Р -го элемента И k -й группы соединен с )(-м входом (p+l)го элемента ИЛИ.

1 043634

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

Недостатками данного устройства являются его сложность и применение значительного числа элементов памяти, 15 что в целом, не позволяет создать регулярную структуру с большой степенью интеграции.

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

И, управляющий элемент ИЛИ, элемент

ИЛИ-НЕ, задающие элементы И и элементы задержки (2).

Наиболее близким к изобретению по технической сущности и достигаемому эффекту является устройство для выделения максимального числа из п двоичных чисел, содержащее Е групп элементов И, m групп элементов памяти, п групп элементов ИЛИ, многовходоные элементы ИЛИ, управляющие элементы И, регистр результата, элементы задержки, причем вход управления началом работы устройства соеди- 40 нен с первым входом первого управляю" щего элемента И и входом перного элемента задержки, выход каждого -ro элемента задержки (1=1,2,..., Р -1)«) и - количество сранниваемых чисел) 45 подключен к первому входу (1+1)-го управляющего элемента И и входу (« +1)-ro элемента задержки, выход (n-„1)-го элемента задержки соединен с выходной шиной устройства, выход каждого ) -ro управляющего элемента (j=1 2,..., n) подключен к информационному входу j -ro разряда регистра результата, инверсный выход каждого первого элемента памяти К-й группы (К=l, 2,..., и ) соединен с первым входом первого элемента и К-й группы, выход каждого из которых подключен к входу. установки н нулевое состояние второго элемента памяти

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

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

1-го многовходоного элемента ИЛИ, вы. ход каждого из которых подключен к второму входу (-го управляющего элемента И, выход каждого -ro управляющего элемента И соединен с вторыми входами (-х элементов И всех групп(3)

Недостатком известных устройств является их сложность.

Цель изобретения - упрощение устройства.

Поставленная цель достигается тем, что н устройство для выделения максимального числа, содержащее N групп элементов И, rn ãðóïï элементов памяти, где и) число сравниваемых двоичных чисел, элементы ИЛИ, управляющие элементы И, регистр. результата и элементы задержки, причем вход управления началом работы устройства соединен с первым входом первого управляющего элемента И и нходом первого элемента задержки, выход < -го элемента задержки (где =1, 2,..., и -2)уИ -количество разрядов сравниваемых чисел) подключен к первому входу (я +1) -ro управляющего элемента И и входу (< +1)-го элемента задержки, выход (rl-1)-го элемента задержки соединен с выходной шиной устройства, прямой выход первого элемента памяти К-й группы (где К=l, 2,..., я1) соединен с К-м входом первого элемента ИЛИ, введены элементы НЕ, причем вход

j-го элемента НЕ (где j =1, 2,...,П ) соединен с выходом j -ro элемента ИЛИ, а выход подключен к второму входу

)-го управляющего элемента И, выход . которого подключен к входу установки в нуль ) -го разряда регистра результата и входам установки в едйничное состояние ) -х элементов памяти всех, групп, выход первого элемента памяти К-й группы соединен с пер" вым входом первого элемента И той же группы, выход 6 -ro элемента И К-й группы (где Р =1, 2..., (0-2)) подключен к первому входу (3+1)-го элемента И той же группы, второй вход

Р-го элемента И К-й группы (где Р=

1, 2..., (-1)) соединен с выходом (Р+1)-ro элемента памяти той же группы, выход P-ro элемента И К-й группы соединен с К-м входом (Р+1)-го элемента ИЛИ.

На чертеже представлена блок-схема предлагаемого устройства.

Устройство содержит и« групп эле1 . « l2 l2 2 ментов„1, 12 ° ° ° 1 я ° 1 < 11 ° ° 4

В

1, 1,... и l„памяти, m групп

1 2 элементов И 2,, 2,..., 2... 2,, 2

« 3

° ° °, 2 1, ° ° °, 2 р 22 у ° . ° р ю„... многовходовые элементы ИЛИ 3, 32,..., 1

10436

3, элементы НЕ 44, 42,..., 4п, управляющие элементы И 51, 52,..., 5, элементы 6», 6),..., 6 задержки, вход 7 управления началом работы, выходную шину 8 и регистр 9 результата. Выходы всех элементов 1, 1„, 5

1,. памяти подключены к первым

В входам многовходового элемента ИЛИ 3( выход каждого элемента памяти 1 (где .3 =2, .3,..., t1; К=l, 2,..., М ) связан с вторым входом элемента И 2О, пер- (() вый .вход элемента И 2„(где Р=l, 2,о (n-2)) подключен к первому вхо ду.элемента И 2„ . Кроме того, выход каждого элемента И 2„ (где j =1, 2,. .-., (З -1)) связан с К-м входом многовходового элемента ИЛИ 3),1. Выход каждого многовходового элемента ИЛИ 3 (где

{ =1 2 ° ° ° . ll ) подсоединен через элемент НЕ 4, 4,..., 4„) к входу управляющего элемента И 5;, первый вход управлякщего элемента И 5, соединен с входом каждого элемента задержки

61 . Вход 7 управления началом работы связан с первым входом элемента И 5g и входом первого из последовательно соединенных элементов задержки бр, 62,..., б„ „, выход последнего соединен с выходной шиной устройства 8.

ВЫход каждого управляющего элемента

И 5 подключен к входу установки в единичное. состояние элементов памяУ/ IVI ти 1;, 1;,..., 1; и входу установки в нуль i -го разряда регистра 9 рет зультата.

Устройство работает следующим образом. 35 lIep началом работы все разряды регистра 9 устанавливаются в единичное состояние. В элементы 1 памяти заносится Я и -разрядных чисел. По сигналу начала операции,- который пос- 4р тупает на вход 7, разрешается обработка сигналов с выхода элементов

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

ИЛИ 3 и соответствующего элемента НЕ

4 формируется сигнал нулевого уровня, а с выхода элемента И 5 снимается также сигнал нулевого уровня и, таким образом, первый разряд регистра

9 остается в единичном состоянии. С выходов элементов памяти 1, 1

1, в которых записан нуль, снимаете ся сигнал нулевого уровнй, который, поступая на соответствующие элементы (I Ю

И 2, 21,..., 2 „, исключает дальней шее участие чисел, в старшем разряде которых записан нуль, в последующих тактах сравнения. В случае, если Щ в старших разрядах всех сравниваемых чисел записаны нули, элементами ИЛИ

3, HE 4 и И 5 последовательно формируются сигналы единичного уровня и старший разряд регистра 9 результата сбрасывается в нуль, а элементы паI N мяти 1,, 1,,..., 1 устанавливаются

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

2 памяти 12, 1,..., 1 . При появлении сигнала на выходе элемента 6g задержки производится анализ содержимого элементов памяти k4а, 1,,..., 1Ф, . а ° не исключенных на предыдущем такте работы устройства. Если на указанных элементах памяти записана хотя бы одна единица, элементами ИЛИ 3g.

HE 4 и И 5 последвватвльно формируются сигналы нулевого уровня - во втором разряде регистра 9 результата остается записанной единица, а с выходов элементов памяти 12, 12 ... 12

-в которых записан нуль, снимается. г, сигнал нулевого уровня, который, поступая на входы соответствующих элемек1 2 Щ тов И 22, 22,..., 22, исключает соответствующие числа из процесса сравнения на. последующих тактах работы. Если на не исключенных на первом такте элементах памяти 1, 1 ... °, 12 записаны все нули, сигнал единичного уровня последовательно формируется на выходах элементов ИЛИ 32НЕ 42 и

И 52. Сигналом с выхода элемента И 5,: второй разряд регистра 9 результата устанавливается в нуль, а элементы ! 2 m памяти 1, 1,..., 12 устанавливаются в,нуль, а элементы памяти 1 1 ю

Я I t

12 устанавливаются в единицу т.е. во втором такте, таким образом, не исключается ни одно число из дальнейших тактов сравнения. Аналогичным образом, последовательно во времени анализируются остальные разряды сравниваемых чисел. При выдаче единично" го сигнала с выхода элемента бя (задержки на выходную шину 8 устройства на регистре 9 результата фиксируется код максимального числа, Изобретение позволяет упростить структуру устройства по сравнению с известным за счет сокращения количества логических элементов, используемых в устройстве. . В известном устройстве число логических элементов

С, - 2ni.п,(2 и - 3), (1) а в предлагаемом

С ) -2nirn (ю -1), (2)

Таким образом, в среднем число логических элементов в предлагаемом устройстве на 45% меньше, чем в известном.

1043б34

Составитель Е.Иванова

Техред И.Гайду Корректор С.Шекмар

Редактор I .Беэвершенко

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

Заказ 7338/51 Тираж 706 Подписное

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

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