Устройство для определения максимального из @ чисел Советский патент 1983 года по МПК G06F7/02 

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

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

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

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

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

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

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

20 подключен к первому входу 1-го элемента И К-й группы; выход КОТОРОГО

подключен к второму входу (f-l)-ro элемента ИЛИ К-й группы, прямой выход каждого j -го элемента памяти

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

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

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

Поставленная цель достигается тем что в устройстве для определения максимального из m чисел, содержащем m групп элементов памяти, m групп элементов И, группу т-входовых элементов ИЛИ m групп элементов ИЛИ, регистр результата., п узлов управления, причем информационные входы устройства соединены с информационными входами элементов памяти групп, прямой выход каждого i-ro элемента памяти j -и группы, где i 1,2,..,- п, j 1,2.. .m, подключен к i-му входу j -го т-входового элемента ИЛИ группы, выход каждого из которых соединен с первым входом i-ro узла управления, инверсный .выход каждого К-го элемента памя,ти -и группы подключен к первому входу К-го элемента И j-и группы, где К - 1,2,,... (п-1), выход каждого Р-го элемента И каждой j ,-и группы, где Р 1,2,... (п-1), соединен с входом установки в нулевое состояние (Р+1)-го элемента памяти fi группы и с первым V входом (P-l)-ro элемента. ИЛИ j -и группы, выход первого элемента И каждой группы подключен к входу установки в нулевое состояние второго элемента памяти { -и группы и к второму рходу первого элемента .ИЛИ ;j -и груп,пы, выход каждого-1-го элемента ИЛИ каждой j-и группы соединен с вторым входом (2+1)-го элемента ИЛИ, где f 1,2,... п-3, j -и группы, первый выход каждого i-ro узла управления соединен с 1-ым.входом регистра результата и с вторым входом i-ых элементов И всех групп, вход управления, устройства подключен к второму входу .первого узла управления, второй выход kaждoгo К-го узла управления соединен с вторым входом (К+1)-го узла управления. .

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

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

Устройство содержит m групп

элемеMl 1 - I 1 1

I1--I

mi i n-1

m тгп

, - l., групп лементов ИЛИ i i 2

ni -).2 -,: 1 . 21 ..n-2

/ Г А

2 f

п-а

,m

m

211Гл .

, m групп элементов

( . 2.

т . ч2 о

3

памяти 3 ,

2

2 - -jtn tfn

Зп, п т-входовых

П ... 4,, п узло элементов ИЛИ 4, управления 5, 5

5f,, каждый из

которых состоит из элемента задержки б, элемента НЕ 7, элемента И 8, эле-, мента ИЛИ 9, .элемента И 10, выход 11 устройства, регистр 12 результата, вход 13 управления устройства.

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

Перед началом работы регистр 12 результата сбрасывается в нулевое сотояние, так же как и все элементы памяти 3 перед приемом чисел. В 3 памяти заносятся т, п-разрядных чисел и в устройство поступает импульс начала операции по входу 13 управления устройства, который разрешает прохождение сигнала через элемент И 10 узла 5 управления. Если хотя б в одном элементе памяти 3,} 1/2, ..., т, записана единица, сигнал через элемент ИЛИ 4 и элемент И IQ поступает в первый разряд регистра 1 результата и .записывает в него единицу, этот же сигнал, с выхода элемента И lOf поступает на вторые входы элементов К. Если в 1-ом (,.. m} ) числе старший разряд равен нулю то с инверсного выхода 1-го элемента 3 памяти снимается разрешаюций потенциал/ открывающий элемент.И 1/ и на все элементы 3 памяти младшихразрядОв i-ro числа через элемент ИЛИ 2 поступает сигнал, сбрасывающий их в нулевое состояние. Таким обраэом данное число исключается из процесса дальнейшего сравнения. Если на выходе элемента. И 10 сформирован был единичный сигнал/ то он поступает на элемент 5 задержки управления, обеспчиваквдий задержку сигнала на время переключения элементов 3 памяти, и затем, пройдя через управляющий элемент ИЛИ 9 узла 5 управления, поступает на вход управляющего элемента И 10 узла 52 управления, обеспечивая обработку второго разряда всех сравниваемьк чисел описанным образом. Ес.ли в каком-то из обрабатываемых разрядов всех сравниваемьвс чисел окажутся записанными, нули, то сбрасывания в нуль элементов 3 памяти не потр буется. В этом случае на выходе элемента ИЛИ 4, где 1 - номер обрабатывае мого разряда, i 1,2,... (п-1), будет сформирован сигнал нулевого уровня, который, инвертируясь элементом НЕ 7 i-ro узла 5 управления и пройдя через элемент И 8, открытый тем же сигнале), который открывает элемент И 10, через элемент ИЛИ 9 поступит на вход элемента и (1+1) то узла управления, блокируя таким образе, задерж ку сигнала элементом б задержки. Опи санная операция позволяет сократить обработку разряда, не требующего сбр са в нуль элементов 3. памяти, пример но вдвое. . Такшл образом, предлагаемое устро ство позволяет повысить быстродействие в среднем на 16% при с эеднем пов шении аппаратурных затрат на 5,8 %, причем эффективность устройства йовы ,|цается при увеличении числа сравнива мых чисел и числа разрядов. I - - . . Формула изобретения 1. Устройство для определения максимального из m чисел, содержащее m групп элементов памяти, m групп элементов И, группу .т-входовых элементов ИЛИ, m групп элементов ИЛИ, регистр результата, п узлов управления, причем информационные входы устройства соединены с информационными входами:.элемеитов памяти групп, прямой .выход каждого .i-ro элемента памяти j -и группы, где 1 1,2,...п j 1,2,.. m ,пoдключeн к -му входу -го щ-входового элемента ИЛИ группы,выход каждого из которых соединен с первыг входом 1-го узла управления, инверсный выход кгикдого к-го э.лемента памяти .J -и группы подключе н к первому .входу к-го элемента И . 1 -и группы, где к 1,2,...(п-1),выход каждого р-го элемента И каждой, -ой группы, где р 2,3,... (п-1), соедииеда с входом установки в нулевое состояние (р+1)-го элемента памяти j -и группы и с первым входом (p-l)-ro элементаИЛИ ) -и группы, выход первого элемента И каждой j -и группы подключен к входу установки в нулевое состояние в.тоЕюго элемента памяти -J -игруппы и к второму входу первого элемента ИЛИ j -и группы, выход каждого 1-го элемента ИЛИ каждой j -и группы соединен с вторым входом (1+1)гго элемента ИЛИ, где I 1,2,...(п-З), -и группы, отличающееся тем, что, с целью повышения быстродействия, в нем первый выход..каждого i-ro узла управления соединен с входом регистра результата и с вторым входом i-ых элементов И всех групп, вход управления устройства подключен к второму входу первого .узла управления, второй выход каждого к-го узла управления соединен с вторьм входом (К+1)-го узла управления. 2. Устройство по П.1,о т ли ч аю щ е е с я тем, что к-ый узел управления состоит из элементов И, ИЛИ, НЕ, элемента задержки, причем первый вход узла соединен с первым входом первого элемента И и через элемент НЕ - с первым входом второго элемента И; выход которого подключен к первому входу элемента ИЛИ, второй вход узла соединен с вторьзми. входами первого и второго элементов И, выход первого элемента И подключен « первому выходу узла и через элемент задержки - к.второму входу элементаИЛИ, выход которого соединен с вторым выходом узла, п-ый узел управления содержит элемент И, первый и второй входы которого соединены с первым и вторШ входами узла соответственно, а выходс nepBfcW выходом узла. - ., Источники инфо{ 4ации, принятые во внимание при эксперти зе 1.Авторское свидетельство СССР 726528, кл. G 06 F 7/04, 1980 2.Авторское свидетельство СССР по заявке 1 2886601/18-24, кл. G 06 F 7/04, 1980 (прототип).