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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИРЕСПУБЛИК ЯО 110588 3(511 С 06 Р 7 ГОС О АНИЕ ИЗОБРЕТЕНИЯ,с Бйли.,ВТОРСНОМУ СВИДЕТЕЛЬСТВУ 24 че вДАРСТВЕННЫЙ КОМИТЕТ СССРЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(72) О.В.Журавлев и В,Н.Сороко (71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции(56) 1, Авторское свидетельство СССР 9 911510, кл. 6 06 Р 7/04, 1980.2. Авторское свидетельство СССР 1 Е 849202, кл. 6 06 Г 7/02, 1979 (прототип) .(54)(57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО ЧИСЛА, содержащее генератор импульсов, элемент И, и счетчиков, элемент ИЛИ, вычитающий счетчик, причем выходгенератора импульсов соединен с первым входом эле мента И, выход которого соединен со счетным входом вычитающего счетчика, счетные входы и счетчиков объединены установочные входы 1-го счетчика, где 1 = 1, 2, , и, соединены с ши ной ввода 1-го числа устройства, отличающее с я тем, что, с целью расширения функциональных воэможностей устройства эа счет сортировки чисел по критерию максимума,в него введены триггер управления, счетчик количества сортируемых чисел и группа элементов И, причем входы разрешения записи и счетчиков и счет" чика количества сортируемых чисел подключены к шине ф 1 Начало операции устройства, соединенной также с входом установки в единичное состояние вычитающего счетчика и триггера управления, вход установки в нулевое состояние которого подключен к выходу переполнения счетчика количества сортируемых чисел, установочные входы которого соединены с шиной количества .анализируемых чисел устройства, с тный вход которого соединен с упра ляющими входами элементов И группы 3 и выходом элемента ИЛИ, входы которого подключены к выходам переполне- Д ния и счетчиков, счетные входы которых соединены с выходом элемента И, С второй вход которого подключен к еди-Ф ничному выходу триггера управления, Я информационные входы элементов И группы соединены с выходами разрядов вычитающего счетчика, выходы эле- Маей ментов И группы являются информационными выходами устройства, выходы переполнения счетчиков являются вы- ( Д ходами адреса максимального числа, рИзобретение относится к автоматике и вычислительной технике, в частности к устройствам сортировки, иможет быть использовано в качествесоставной части блока нормализациипорядка чисел с плавающей запятой в 5ЭВМ, комплексах и системах на модулях с большей степенью интеграции.Известно устройство для поискамаксимального числа, содержащее прегистров для хранения сравнительных 10чисел в позиционном коде, вычитающийсчетчик, шифратор, генератор, триггер,блок элементов И, элементы И, ИЛИ,НЕ С 1 3.Устройство позволяет определитьмаксимальное из и чисел, однако непредусматривает их сортировку и изэа использования пространственногокодирования ",бладает значительнымиаппаратурными затратами при обработ=ке больших чисел.Наиболее близким по техническойсущности к предлагаемому являетсяустройство для сравнения двоичныхчисел, содержащее и счетчиков, группы 25элементов запрета, группы триггеров,элемент ИЛИ, генератор импульсов,выход которого соединен с входамисчетчиков, выход переполнения каждого 1-го счетчика, где 1 = 1, 2,п, подключен к инФормационным входам 1-х элементов запрета первой ивторой группы, выход каждого 1-гоэлемента запрета первой и второй группы соединен с входом установки в единичное состояние 1-го триггера первой и второй групп соответственно,прямые выходы триггеров первой группы подключены ко входам элементаИЛИ, выход которого соединен с входами управления элементов запрета пер Овой группы. Устройство содержит также дополнительный элемент запрета,элемент ИСКЛЮЧАЮШЕЕ ИЛИ, триггер,.элементы И, два вычитающих счетчика,причем прямые выходытриггеров второй группы соединены с входами элемента ИСКЛЮЧАЮШЕЕ ИЛИ, выход которого подключен к управляющему входуэлементов запрета второй группы идополнительного элемента запрета,выход которого соединен с входом установки в единичное состояние триггера, прямой выход которого подключен к первому входу первого элемента И, выход которого соединен свходом первого вычитающего счетчика,выход генератора импульсов подключенко второму входу первого элемента Ии к первому входу второго элемента И,второй вход которого соединен с выходом элемента ИЛИ, а выход - с входом 6 Овторого вычитающего счетчика, выходпереполнения каждого 1-го счетчикаподключен к 1-му информационномувходу дополнительного элемента запрета 23. 65 Устройство позволяет определитьмаксимальное и минимальное числа,однако не выполняет их сортировку,Цель изобретения - сокращение аппаратных .затрат на реализацию устройства и расширение функциональных возможностей за счет сортировки чиселпо критерию максимума.Указанная цель достигается тем,что в устройство, содержащее ;енератор импульсов, элемент И, п счетчиков, элемент ИЛИ, вычитающжй счетчик причем выход генератора импульсов соединен с первым вход:м элемента И, выход которого соединен со счетным входом вычнтающего счетчика, счетные входы п счетчиков объединены, установочные входы 1-го счетчика, где 3. = 1, 2.и, соединены с шиной ввода З.-го числа устройства,введены триггер управления, счетчикколичества сортируемых чисел и группа элементов И, причем входы разрешения записи и счетчиков и счетчикаколичества сортируемых чисел подключены к шине фНачало операцииф устройства, соединенной также с входомустановки в единичное состояние вычитающего счетчика и триггера управления, вход установки в нулевое состояние которого подключен к выходупереполнения счетчика количествасортируемых чисел, установочные входы которого соединены с шиной количества анализируемых чисел устройства, счетный вход которого соединенс управляющими входами элементов Игруппы и выходом элемента ИЛИ, входы которого подключены к выходам переполнения и счетчиков, счетные входы которых соединены с выходом элемента И, второй вход которого подключен к единичному выходу триггера управления, информационные входы элементов И группы соединены с выходами разрядов вычитающего счетчика, выходы элементов И группы являются информационными выходами устройства, выхо" ды переполнения счетчиков являютсявыходами адреса максимального числа.На чертеже представлена блок-схе"ма устройства для сортировки двоичных чисел.Устройство содержит п счетчиков1, шины ввода чисел 2, вычитающийсчетчик 3, счетчик количества сортируемых чисел 4, шинуНачало операцииф 5, элемент И 6, генераторимпульсов 7, триггер управления 8,шину 9 количества анализируемых чисел устройства, группу элементов И10, элемент ИЛИ 11, информационныевыходы 12 устройства, выходы 13 адреса максимального числа,Устройство работает следующим образом.По сигналу Начало операции,поступающему по шине 5 на счетчики+С+ С,ф Сг.н 50 55 Ы4(п )с + 1 од и) 65 1,1, по шинам 2.1 заносятся двоичные числа, подлежащие сортировке по критерию максимума, Вычитающий счетчик3 устанавливается н состояние ф 111, а на счетчик 4 по шине 9 поступает в обратном коде число, равноеколичеству чисел, подлежащих сортировке, при этом триггер 8 устанавливается в единичное состояние. Единичный сигнал с выхода триггера 8 подключает генератор 7 через схему И бк счетным входам счетчиков 1,1 и вычитающему входу счетчика 3, К содержимому счетчиков 1.1 добавляетсяпо единице, а из содержимого счетчика 3 вычитается единица. Этот процесс 15происходит до переполнения одногоиз счетчиков 1.1, что свидетельствует об обнаружении на 1-м счетчике максимального из сортируеиах чисел,В счетчике 3 в этот момент находится прямой код максимального числа. Снимаемый с выходов счетчика 3 параллельный код максимального числа через открытый в этот момент блок элементов И 10 поступает на выходную шину 12 устройства. Разрешающий эту операцию сигнал Формируется импульсом переполнения соотнетствующего 1-го счетчика 1. Кроме того, сигнал переполнения 1-го счетчика поступает иа соотнетстнующую шину 13.1 адреса 30 максимального числа, это позволяет определить .номер счетчика, в котором хранилось считанное по шине 12 максимальное число. Одновременно сигнал переполнения через элемент ИЛИ 11 З 5поступает на суммирующий вход счетчика 4, увеличивая его содержимое наединицу. После этого устройство повторяет цикл работы до следующего пепеРеполнения одного из счетчиков 1.1,40После анализа заданного количествачисел, информация о чем н обратномкоде хранится на счетчике 4, происходит переполнение счетчика 4, этопозволяет судить об окончании операции сортировки. Этот сигнал переводит триггер н нулевое состояние, отключая тем самым генератор от счетных входов счетчиков 1.1 и от вычитающего входа счетчика 3, Устройство закончило полный цикл работы и готово к сортировке очередного набора.Предлагаемое устройство позволяет значительно сократить аппаратные затраты и расширить функциональные возможности за счет обеспечения сортировки двоичных чисел по критерию максимума. Аппаратные затраты по базовому варианту, принятому за прототип, можно определить по Формуле: С С б + С 4.б Сб б С б м,+СГ + Снеб+ Си,б+ Стр.б Аппаратные затраты по предлагаемому варианту можно определить как: 1С е С +С +С +С +С +М" Ясч.ч бл. и,н сч,цтн тр. н где С - стоимость элементов памятинеобходимая для храненияанализируемых чисел;С, - стоимость счетчика;С - стоимость блока И;С- стоимость шифратора;С- стоимость элементов ИЛИ;С - стоимость генератора;С, - стоимость элемента НЕ;С- стоимость элемента И;С,р - стоимость триггера;(". - стоимость счетчика количества анализируемых чисел попредлагаемому варианту.Сии т Сиди б = Снли,н т С гб ССр т Стр б - Стри т ТО В даЛЬНЕйШЕМ расчете эти величины участновать не будут . Таким образом С 1 б - Сб тСт б + Сне г к С н СЯ и+Ссч,санОпределим необходимое количество элементов памяти для базового и предлагаемого вари антон .При пространственном кодировании К-разрядных чисел для предоставления одного числа необходимо (2 -1) разрядов памяти . При обычном двоичном кодировании одно число представляется К-разрядамн. Цля органиэации одного разряда счетчика и сдвигового регистра необходимо 4 двухвходовых элемента типа И-НЕ. Для органиэации счетчика количества анализируемых чисел необходимо 1 од и разрядов. Для окрганизации шифратора необходимо 2 1 од к двухнходовыхэлементов типа И-НЕ. Тогда: С = 4 еп(2 -1) а+(2 1 од )с) а + а,Сн = 4(п )с + 1 о 9 гп) а где а - стоимость одного двухнходового элемента типа И-НЕ, Отсюда коэфФициент эффективности С 4 п 2 -1 М + 2 а 1 оК+а1105886 Составитель Е.Ивановаедактор К.Волощук Техред С.Мигунова Корректор О,Тиг 5602/38 Тираж 699ВНИИПИ Государственного комитетапо делам изобретений и открыти 113035, Москва, Ж, Раушская н одписСР ак д Филиал ППППатент, г. Ужгород, ул. тная Таким образом, при увеличении разрядности сортируеьих чисел и их количества эффективность применения предлагаемого устройства растет. Кроме того, предлагаемое устройство может быть использовано в качестве устройства анализа приоритета, устройстваанализа порядка в числах с плавающейзапятой, что расширяет его областьприменения,