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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО ЧИСЛА, содержащее генератор импульсов, элемент И, п счетчиков, элемент ИЛИ, вычитающий счетчик, причем выход генератора импульсов соединен с первым входом элемента И, выход которого соединен со счетным входом вычитающего счетчика, счетные входы п счетчиков объединены, установочные входы i-ro счетчика, где i 1, 2, ..., п, соединены с шиной ввода i-ro числа устройства, отличающее сятем, что, с целью расширения функциональных возможностей устройства за счет сортировки чисел по критерию максимума. в него введены триггер управления, счетчик количества сортируемых чисел и группа элементов и, причем входы разрешения записи п счетчиков и счетчика количества сортируемых чисел подключены к шине Начало операции устройства, соединенной также с входом установки в единичное состояние вычитающего счетчика и триггера управления , вход установки в нулевое состояние которого подключен к выходу переполнения счетчика количества сортируемых чисел, установочные входы которого соединены с шиной количества .анализируемых чисел устройства, счетный вход которого соединен с управляющими входами элементов И группы и выходом элемента ИЛИ, входы которого подключены к выходам переполнения п счетчиков, счетные входы которых сюединены с выходом элемента И, второй вход которого подключен к единичному выходу триггера управления, j информационные входы элементов И группы соединены с выходами разрядов вычитающего счетчика, выходы элементов И группы являются информационными выходами устройства, выходы сл переполнения счетчиков являются выходами адреса максимального числа. 00 00. Oi

„„Я0„„1105886 А

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

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

3(511 G 06 F 7/04

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

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3586694/18-24 (22) 04.05.83 (46) 30.07.84. Вюл. Р 28 (72) О.В.Журавлев и В.Н.Сороко (71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (53) 681. 325 (088. 8) (56) 1. Авторское свидетельство СССР

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

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

849202, кл. G 06 F 7/02, 1979 (прототип) . (54)(57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

МАКСИМАЛЬНОГО ЧИСЛА, содержащее генератор импульсов, элемент И, и счетчиков, элемент ИЛИ, вычитающий счетчик, причем выход генератора импульсов соединен с первым входом элемента И, выход которого соединен со счетным входом вычитающего счетчика, счетные входы и счетчиков объединены, установочные входы 1-го счетчика, где i = 1, 2, ..., n, соединены с шиной ввода i-го числа устройства, отличающее с я тем, что, с целью расширения функциональных воэможностей устройства эа счет сортировки чисел по критерию максимума, в него введены триггер управления, счетчик количества сортируемых чисел и группа элементов И, причем входы разрешения записи и счетчиков и счетчика количества сортируемых чисел подключены к шине Начало операции устройства, соединенной также с входом установки в единичное состояние вычитающего счетчика и триггера управления, вход установки в нулевое состояние которого подключен к выходу переполнения счетчика количества сортируемых чисел, установочные входы которого соединены с шиной количества .анализируемых чисел устройства, счетный вход которого соединен с управляющими входами элементов И группы ф и выходом элемента ИЛИ, входы которого подключены к выходам переполне- Q7 ния п счетчиков, счетные входы которых соединены с выходом элемента И, С второй вход которого подключен к еди- с ничному выходу триггера управления, Я информационные входы элементов И группы соединены с выходами разрядов вычитающего счетчика, выходы эле- 0aaL ментов И группы являются информационными выходами устройства, выходы переполнения счетчиков являются вы- (Д ходами адреса максимального числа, р

1105886

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

ЭВМ, комплексах и системах на модулях с большей степенью интеграции.

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

УстРойство позволяет определить 5 максимальное из и чисел, однако не предусматривает их сортировку и изэа использования пространственного кодирования ",бладает значительными аппаратурными затратами при обработ=ке больших чисел.

Наиболее близким по технической сущности к предлагаемому является устройство для сравнения двоичных чисел, содержащее и счетчиков, группы 5 элементов запрета, группы триггеров, элемент ИЛИ, генератор импульсов, выход которого соединен с входами счетчиков, выход переполнения каждо-. го i ão счетчика, где i = 1, 2, п, подключен к информационным входам i-х элементов запрета первой и второй группы, выход каждого i-го элемента запрета перной и второй группы соединен с входом установки н единичное состояние i-го триггера пер- 35 вой и второй групп соответственно, прямые выходы триггеров первой группы подключены ко входам элемента

ИЛИ, выход которого соединен с входами управления элементов запрета пер- 4р ной группы. Устройство содержит также дополнительный элемент запрета, элемент ИСКЛЮЧАЮШЕЕ ИЛИ, триггер, .элементы И, два вычитающих счетчика, причем прямые выходы триггеров второй группы соединены с входами элемента ИСКЛЮЧАЮШЕЕ ИЛИ, выход которого подключен к управляющему входу элементон запрета нторой группы и дополнительного элемента запрета, выход которого соединен с входом установки в единичное состояние триггера, прямой выход которого подключен к первому входу первого элемента И, выход которого соединен с входом первого нычитающего счетчика, выход генератора импульсов подключен ко второму входу первого элемента И и к первому входу второго элемента И, нторой вход которого соединен с выходом элемента ИЛИ, а выход — с входом 6О второго вычитающего счетчика, выход переполнения каждого i-ro счетчика подключен к i-му информационному входу дополнительного элемента запрета С23. 65

Устройство позволяет определить максимальное и минимальное числа, однако не выполняет их сортировку, Цель изобретения — сокращение аппаратных .затрат на реализацию устройства и расширение функциональных нозможностей за счет сортировки чисел по критерию максимума.

Указанная цель достигается тем, что в устройство, содержащее хенератор импульсов, элемент И, п счетчиков, элемент ИЛИ, вычитаний счетчик„ причем выход генератора импульсон соединен с первым вход=м элемента

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

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

Устройство содержит п счетчиков

1, шины ввода чисел 2, вычитающий счетчик 3, счетчик количества сортируемых чисел 4, шину Начало операции 5, элемент И 6, генератор импульсов 7, триггер управления 8, шину 9 количества анализируемых чисел устройства, группу элементов И

10, элемент ИЛИ 11, информационные выходы 12 устройства, выходы 13 адреса максимального числа.

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

По сигналу Начал о операции, поступающему по шине 5 на счетчики

1105886

+С„д + С„,„„ г.н

55 я

4(n k + log>n) 65

l,i, по шинам 2.i заносятся двоичные числа, подлежащие сортировке по критерию максимума, Вычитающий счетчик

3 устанавливается н состояние ll °

1, а на счетчик 4 по шине 9 поступает в обратном коде число, равное количеству чисел, подлежащих сортировке, при этом триггер 8 устанавливается в единичное состояние. Единичный сигнал с выхода триггера 8 подключает генератор 7 через схему И б к счетным входам счетчиков 1, 1 и вычитающему входу счетчика 3. К содержимому счет чиков 1 . i добавл яется по единице, а из содержимого счетчика 3 вычитается единица. Этот процесс15 происходит до переполнения одного из счетчиков l.i, что свидетельствует об обнаружении íà i-м счетчике максимального из сортируеьжх чисел.

В счетчике 3 в этот момент находится прямой код максимального числа.

Снимаемый с выходов счетчика 3 параллельный код максимального числа через открытый в этот момент блок элементов И 10 поступает на выходную шину 12 устройства. Разрешающий эту операцию сигнал формируется импульсом переполнения соотнетствующего

i-го счетчика 1. Кроме того, сигнал переполнения i-го счетчика поступает иа соотнетстнующую шину 13.i адреса 30 максимального числа, это позволяет определить номер счетчика, в котором хранилось считанное по шине 12 максимальное число. Одновременно сигнал переполнения через элемент ИЛИ 11 З5 поступает на суммирующий вход счетчика 4, увеличивая его содержимое на единицу. После этого устройство повторяет цикл работы до следующего пепереполнения одного из счетчиков l.i.40

После анализа заданного количества чисел, информация о чем н обратном коде хранится на счетчике 4, происходит переполнение счетчика 4, это позволяет судить об окончании операции сортировки. Этот сигнал перево- 45 дит триггер н нулевое состояние, отключая тем самым генератор от счетных входов счетчиков l.i и от вычитающего входа счетчика 3. Устройство закончило полный цикл работы и готово к сортировке очередного набора.

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

Аппаратные затраты по базовому варианту, принятому за прототип, можно определить по формуле:

С = С П6 + С сч.6 Сб .и.e+ Сш я,б или.6

+Сг6 + С еб+ Си,6 + С Р.6

Аппаратные затраты по предлагаемому варианту можно определить как:

С =С +С +С +С +С +

С " д р .ч 6л. и.н cv,ц н Tfa. к где С вЂ” стоимость элементов памяти необходимая для хранения анализируемых чисел;

С,„- стоимость счетчика;

С вЂ” стоимость блока И;

С „- ст оимост ь шифр ат ора;

C»„- стоимость элементов ИЛИ;

C„стоимость генератора;

С„, — стоимость элемента НЕ;

С „- ст ои мост ь зле ме нт а И;

С,р — стоимость триггера; ("„„. — стоимость счетчика количества анализируемых чисел по предлагаемому варианту.

Сии г СNAH 6 СHAaa í I С г6

С С р 6 С р то в дальнейшем расчете эти величины участновать не будут. Таким обРазом C6 = C„6 +С „6+

Снр. 6 С- н " СЯ н+Ссч,сан

Определим необходимое количество элементов памяти для базового и предлагаемого вари анто s .

При пространственном кодировании

К-разрядных чисел для предоставления одного числа необходимо (2 -1) разрядов памяти. При обычном двоичном кодировании одно число представляется

К-разрядами. Цля органиэации одного разряда счетчика и сдвигового регистра необходимо 4 двухвходовых элемента типа И-НЕ. Для органиэации счетчика количества анализируемых чисел необходимо logan разрядов. Для организации шифратора необходимо 2 log к и двухнходовых элементов типа И-НЕ.

Тогда:

С = 4 n(2 -1) a+(2 log k) a + а, 1(C í „=4 (n k + log>n) a где а — стоимость одного двухнходового элемента типа И-НЕ. Отсюда коэффициент эффективности

С ЮпД -1)a + 2 al k+a

1 6

4a(n k + 1оу п7

4п (2 -1) +2 lo zk) +1

Пусть n = 2, k 2, тогда:

4 2 (2 -1)+2 1о 2 + 1

4(2 2 + log 2) Пусть n = 4, k = 4, тогда;

4 4(2 - + 1ос124 + 1 3 8

4(4.4 + log 4) 1105886

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

Редактор К.Волощук Техред С.Мигунова Корректор 0,Тигор

Заказ 5602/38 Тираж 699 Подписное

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

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

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

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