Устройство для сортировки чисел

.ПО ДЕЛАМ ИЗОВ ЯТЕНИй И ОТКРЫТИЙОПИСАНИЕ ИЗОБРЕТЕНИЯН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, состоящее из уп.ячеек, где тколичество чисел в выходном множестве, причем каждая ячейка содержит элемент сравнения и приемный регистр, выходы разрядов которого соединены с первой группой информационных входов элемента сравнения, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, каждая ячейка содержит коммутатор и регистр результата, причем выходы регистра результата соединены с второй группой информационных входов элемента сравнения и первой группой информационных входов коммутатора, установочФ ные входы приемного регистра являются информационными входами ячейки, а выходы разрядов приемного регистра соединены с установочнымивходами регистра результата и с вто"рой группой информационных входовкоммутатора, а выходы коммутатораявляются выходами ячейки, входы ус-.тановки приемного регистра и регистрарезультата в исходное состояниесоединены с входом установки ус йства в исходное состояние, входуправления записью приемного регистра и первый вход управления записьюрегистра результата соединены свходом тактовых сигналов устройства,выход элемента сравнения соединенс вторым входом управления записьюрегистра результата и управляющимвходом коммутатора, управляющийвход элемента сравнения соединенс управляющим входом устройства,группы информационных входов каждойячейки, кроме первой, соединены сгруппой выходов предыдущей ячейки,а группа информационных входов первой ячейки является группой информационных входов устройства,1 1007Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах обработки информации при реализации технических средств цифровых вычислительных мащин и дискретной автоматики.Известно иногокаскадное сортировочное устройство, содержащее магазинные памяти для упорядочения 16 списка входных чисел, состоящее из И каскадов, соединенных последовательно, каждый из которых состоит из межкаскадных средств памяти, стека, элементов памяти, Средств сравнения 1 1 .Недостатками этого устройства являются его сложность и неоднородность структуры вследствие использования принципа разбиения сортируемых чисел на группы и многокаскад . ного сравнения.1Известно также устройство для сортировки п-разрядных чисел, содер,жащее щ ячеек, каждая из которых Зу содержит элементы сравнения, прием" ный регистр, переключатели, элемент ИЛИ, элемент И, триггер, узлы запрета, регистр результата, причем вы" ходы приемного регистра соединены ЗЕ с первой группой входов элементов сравнения, вторая групга входов ко" торых подключена к выходам регистра результата 2.Недостатком этого устройства является низкое быстродействие, посколь 33 ку для сортировки п чисел, каждое из которых содержит п-разрядов, требуется л(п+1)тактов работы, что определяется принципом поразрядного Формирования в регистре результата46 очередного сортируемого числа.Целью изобретения является повыщение быстродействия.Поставленная цель достигается тем, что устройство, состоящее из в ячеек, где т - количество чисел в выходном множестве, причем каждая ячейка содержит элемент сравнения и приемный регистр, выходы разрядов которого соединены с первой группой информационных входов элемента сравнения, каждая ячейка содержит коммутатор и регистр результата причем выходы регистра результата соединены с второй группой информацион- фф ных входов элемента сравнения и первой группой информационных входов . коммутатора, установочные входы приемного регистра являются информационными входами ячейки, а выходы разрядов приемного регистра соедине ны с установочными входами регистра результата и с второй группой входов коммутатора, а выходы коммута" тора являются выходами ячейки, входы установки приемного регистра и регистра результата в исходное состояние соединены с входом установки устройства в исходное состояние, вход управления записью приемного регистра и первый вход управления записью регистра результата соединены с вхо дом тактовых сигналов устройства, выход элемента сравнения соединен с вторым входом. управления записью регистра результата и управляющим входом коммутатора, управляющий вход элемента сравнения соединен с управляющим входом устройства, группы информационных входов каждой ячейки, кроме первой, соединены с группОй выходов предыдущей ячейки, а группа информационных входов первой ячейки является группой информационных входов устройства.Это позволяет уменьшить время ,сортировки до 2 ттактов вследствие применения конвейерного метода и проведения операции сравнения одновременно по всем 1 разрядам сортируемых чисел. На чертеже представлена схема устройства.Устройство состойт из ъ одинаковых ячеек 1, ,1 п 1, где ь - крличество чисел в выходном Множестве, причем каждая ячейка содержит приемный ре-. гистр 2, регистр 3 результата, элемент 4 сравнения и коммутатор 5, при этом выходы приемного регистра 2 соединены с первой группой информационных входов элемента 4 сравнения, вторая группа информационных входов которой подключена к выходам регистра 3 результата, а информационные входы б ячейки соединены с установочными входами приемного регистра 2, выходы которого соединены с установочными входами регистра 3 результата и с первой группой входов коммутатора 5, вторая группа входов которого подключена к выходам регистра 3 результата, а группа выходов коммутатора 5 является группой выходов 7 ячейки, причем входы установки приемного регистра 2 и регистСоставитель В. ГороховТехред Ц.Коштура Корректор.р. Йакаренко Редактор Т. Кугрышева Е В Заказ 2140/72 Тираж 704 Подписное ВНИИПИ Государственного .комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 5 1007099 бва памяти для хранения отсортирован" Количество чисел во входной посленых чисел, что сокращает количество довательности не ограничено, при оборудования. этом из них выбирается в наибольших