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

Изобретение относится к автомати ке и вычислительной технике, в част ности к устройствам сортировки, и может быть использовано в качестве составной части блока нормализации порядка чисел с плавающей запятой в ЭВМ, комплексах и системах на моду ях с большей степенью интеграции. Известно устройство для поиска максимсшьного числа, содержащее п регистров для хранения сравнительны чисел в позиционном коде, вычитающи счетчик, шифратор, генератор, тригг блок элементов И, элементы И, ИЛИ, НЕ Cl К Устройство позволяет определить максимальное из п чисел, однако не предусматривает их сортировку и изза использования пространственного кодирования обладает значительными аппаратурными затратами при обработ ке больших чисел. Наиболее близким по технической сущности к предлагаемому является устройство для сравнения двоичных чисел, содержащее п счетчиков, груп элементов запрета, группы триггеров элемент ИЛИ, генератор импульсов, выход которого соединен с входами счетчиков, выход переполнения каждо го i-ro счетчика, где i 1, 2f ... n, подключен к информационным входам i-x элементов запрета первой и второй группы, выход каждого 1-го элемента запрета первой и второй гр пы соединен с входом установки в ед ничное состояние i-ro триггера первой и второй групп соответственно, прямые выходы триггеров первой груп пы подключены ко входам элемента ИЛИ, выход которого соединен с вход ми управления элементов запрета пер вой группы. Устройство содержит так же дополнительный элемент запрета, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, триггер, элементы И, два вычитающих счетчика причем прямые выходытриггеров второй группы соединены с входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которо го подключен к управляющему входу элементов запрета второй группы и дополнительного элемента запрета, выход которого соединен с входом ус тановки в единичное состояние триггера, прямой выход которого подключен к первому входу первого элемента И, выход которого соединен с входом первого вычитающего счетчика выход генератора импульсов подключе ко второму входу первого элемента И и к первому входу второго элемента второй вход которого соединен с вых дом элемента ИЛИ, а выход - с входо второго вычитающего счетчика, выход переполнения каждого i-ro счетчика подключен к i-му информационному входу дополнительного элемента запрета 23. Устройство позволяет определить максимальное и минимальное числа, однако не выполняет их сортировку. Цель изобретения - сокращение аппаратных .затрат на реализацию устройства и расширение функциональных возможностей за счет сортировки чисел по критерию максимума. Указанная цель достигаетсй гем, что в устройство, содерясашее хенератор импульсов, элемент И, п счетчиков, элемент ИЛИ, вычитающими счетчик,, причем выход генёраторй импульсов соединен с первым входом, зле.жнта И, выход которого соединен со счетным входом вычктаюшего счетчика, счетные входы п счетчиков объединены, установочные входы i-ro счетчигде i 1,, 2, п, соединены с шиной ввода i-ro числа устройства, введены триггер управления, счетчик количества сортируемых чисел и группа- элементов И, причем входы разрешения записи п счетчиков и счетчика количества сортируемых чисел подключены к шине Начало операции устройства, соединенной также с входом установки в единичное состояние вычитающего счетчика и триггера управления, вход установки в нулевое состояние которого подключен к выходу переполнения счетчика количества сортируеких чисел, установочные входы которого соединены с шиной количества анализируемых чисел устройства, счетный вход которого соединен с управляюошмн входами элементов И группы и выходом элемента ИЛИ, входы которого подключены к выходам переполнения п счетчиков, счетные входы которых соединены с выходом элемента И, второй вход которого подключен к единичному выходу триггера управления, информационные входы элементов И группы соединены с выходами разрядов вычитающего счетчика, выходы элементов И группы являются информационными выходакш устройства, выходы переполнения счетчиков являются выходами ащреса максимального числа. На чертеже представлена блок-схема устройства для сортировки двоичных чисел. Устройство содержит п счетчиков 1, шины ввода чисел 2, вычитающий счетчик 3, счетчик количества сортируемых чисел 4, шину Начало опе5, элемент И б, генератор рации импульсов 7, триггер управления 8, шину 9 количества анализируемых чисел устройства, группу элементов И 10, элемент ИЛИ 11, информационные выходы 12 устройства, выходы 13 адреса максимального числа. Устройство работает следующим образом. По сигналу Начало операции, поступающему по шине 5 на счетчики l.i, по шинам 2.i заносятся двоичные числа, подлежащие сортировке по критерию максимума. Вычитающий счетчик 3 устанавливается в состояние 11,. 1, а на счетчик 4 по шине 9 поступает в обратном коде число, равное количеству чисел, подлежащих сортировке, при этом триггер 8 устанавливается в единичное состояние. Единич ный сигнал с выхода триггера 8 подключает генератор 7 через схему И 6 к счетным входам счетчиков 1.1 и вычитающему входу счетчика 3. К содержимому счетчиков 1,1 добавляется по единице, а из содержимого счетчика 3 вычитается единица. Этот процес происходит до переполнения одного из счетчиков 1,1, что свидетельствуе об обнаружении на 1-м счетчике максимального из сортируелгих чисел, В счетчике 3 в этот момент находи ся прямой код максимального числа. Снимаемый с выходов .счетчика 3 парал лельный код -максимального числа через открытый в этот момент блок элементов И 10 поступает на выходную ши ну 12 устройства. Разрешающий эту операцию сигнал формируется импульсом переполнения соответствующего i-ro счетчика 1, Кроме того, сигнал переполнения 1-го счетчика поступает на соответствующую шину 13,1 адреса максимального числа, это позволяет определить номер счетчика, в котором хранилось считанное по шине 12 максимальное число. Одновременно сигнал переполнения через элемент ИЛИ 11 поступает на суммирующий вход счетчи ка 4, увеличивая его содержимое на единицу. После этого устройство повторяет цикл работы до следующего пепереполнения одного из счетчиков 1.1 После анализа згщанного количества чисел, информация о чем в обратном коде хранится на счетчике 4, происходит переполнение счетчика 4, это позволяет судить об окончании опера ции сортировки. Этот сигнал переводит триггер в нулевое состояние, отключая тем самым генератор от счетных входов счетчиков 1.1 и от вычитгиощего входа счетчика 3, Устройство закончило полный цикл работы и готово к сортировке очередного набора. Предлагаемое устройство позволяет значительно сократить аппаратные затраты и расширить функциональные возможности за счет обеспечения сортировки двоичных чисел по критерию максимума. Аппаратные затраты по базовому варианту, принятому за прототип, МОЖ но определить по формуле: -& пб CM-S бл.и.б -ШИФ. или.б неб -.м.Б СТР.6 Cr.6 + С Аппаратные затраты по предлагаемому варианту можно определить как: S Ся H+CCV.H+C е,, „.„+С,, ,„+С,р „-ь -СиЛ + ...«.«- г.н где Cjj - стоимость элементов памяти необходимая для хранения анализируемых чисел; GC - стоимость счетчика; СТОИМОСТЬ блока И; стоимость шифратора; -и стоимость элементов ИЛИ; С - стоимость генератора; - стоимость элемента НЕ; С„ - стоимость элемента И; СТР- стоимость триггера; Ял чен стоимость счетчика количества анализируемых чисел по предлагаемому варианту. Поскольку с и СКД.И.Е - Cf. -мли.6 -или.н f с r.S С„Б СТ-Р„, ТО В дальнейшем расчете эти величины участвовать не будут. Таким образом Cj -Hr.f а .f/. Определим необходимое количество элементов памяти для базового и предлагаемого вариантов. При пространственном кодировании К-разрядных чисел для предоставления одного числа необходимо () разрядов памяти. При обычном двоичном кодировании одно число представляется К-разрядами, .Для организации одного разряда счетчика и сдвигового регистра необходимо 4 двухвходовых элемента типа И-НЕ. Для организации счетчика количества анализируе|«ых чисел необходимо разрядов. Для организации шифратора необходимо 2 двух ходовых элементов типа И-НЕ, Тогда: С 4.n()a+(,k)a + а, о CJ, 4(n-k + )a где а - стоимость одного двухвходового элемента типа И-НЕ. Отсюда коэффициент эффективности i 4n().a + 2а1одгК- -а 4a(n.k , ftJ «л 4п () (logzk) +1 4(n.k + ) Пусть n 2, k 2, тогда: лр - 4-2()+2 1og22 + 1 2,25 4(2-2 + log-, 2) Пусть n 4, k 4, тогда; 4 4() -ь 1одг4 + 1 - 3,8 4(4 -4 + )

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

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

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