Устройство для сортировки -разрядных чисел

(088.8) кое свид 606 Ге свидете 606 Г тельство СССР7/00, 1972льство СССР,7/08, 1976 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ ВТОРСНОМ.Ф СВИДЕТЕЛЬСТВ(прототип),(54) (57) УСТРОИСТВО ДЛЯ СОРТИРОВКИ Фи РАЗРЯДНЫХ ЧИСЕЛ, содержащее м регис тров, ( в -1 ) схем сравнения, ( ь 1 -1) переключателей,причем выходы каждого 1-го регистра, кроме последнего, соединены с первой группой входов т -й схемы сравнения 11 щ, ю - число сравниваемых чисел, выходы 1-й схемы сравнения соединены с входами 1-го переключателя, о т л и ч а ю ш е е с я тем, что с целью повышения быстродействия путем сокрашения времени сортировки информации, устройство содержит группы элемен. тов ИЛИ, группы элементов И, причем выходы каждого 1 -го регистра, кроме первого, соединены с второй группой , входов ( 1 -1)-ой схемы сравнения, первая группа входов элементов ИЛИ первой группы соединена с шиной ввода информации, вьщоды 1 -й группы элементов ИЛИ соединены с информационными вхо дами 1 -го регистра, тактовые входы регистров,соединены с первым управляющим входом устройства, первая, вторая и третья группы входов-х элементов ИЛИ групгы соединены соответственно с выхода ми ( 1-1)-х элементов Ипервой ивторой групп и-х элементов И третьей группы,вто рая группа входов первой группы элементов ИЛИ соединена с выходами первых элементов И третьей группы,=2 ь, первая и вторая группы входов И 1-х элементов ИЛИ группы соединены соответственно с выходами ( И)-хэлементов И первой и второй группы, вы ходы 1-го регистра соединены с инфор- Е мационными входами-х элементов И первой и второй групп и ( 1 -1)-ми алементвми И третьей группы, 1 =1.,ю, второй упрввляюший вход устройства соединены с упрввлякшил 1 и входами элемен- Я тов И первой группы, третий управляю-щий вход устройства - с первыми управляющими входами нечетных элементов И второй и третьей групп, а четвертыйуправляющий вход устройства - с первыми управляющими входами четных элементов И второй и третьей групп, выход-го переключателя соединен с вторым управляющим входом, -х элементов И второй и третьей групп,1 10307Изобретение относится к автоматикеи. вычислительной технике и может быть,использовано в системах обработки информации при реализации техническихсредств цифровых вычислительных машини дискретной автоматики.Известно устройство для сортировкищп -разрядных чисел, содержащее ж ре 1гистров, выходы квждогоиз которых соединены с входами схем сравнения, другие %входы которых подключены к выходамрегистра результате, выходные шины схемсравнения соединены через переключатели с входами элемента ИЛИ, элементыИ, триггер, узлы запрета 115,Недостатком этого устройства является низкое быстродействие, так квк дляанализа информации во всем каталогенеобходимо сформировать и сравнить с хрв.нящимися числами 2 чисел, гдето2 Ойразрядность чисел.Наиболее близким к изобретению является устройство для сортировки у 1 и -разрядных чисел, содержащее М регистров,выходы каждого из которых соединены с 5входами схем сравнения, другие входыкоторых подключены к выходам регистре результате, выходные шины схем сравнения соединены через переключатели свходами элемента ИЛИ элементы И триг- ЗОгер, узлы запрета,Причем выход ревенства каждой схемысравнения соединен с управляющим входом соответствуквцего узле запрета, другие входы которого соединены с управляющими входами устройсгва, а выходыподключены к Одному из входов первогоэлемента И, другой вход которого соединен с входной шиной устройства, а выходс управляющим Входом схемы сравнения,выход элементе ИЛИ соединен с входомтриггера, другой вход которого соединен3 иной тактовых сигналов е выходычерез переключатель - с входом второгоэлемента И, другой вход которогосоединен с управляющей шиной устройства,а выход - с входом установки в нулевоесостояние регистра результата, входынорезрядного управления которого подключены к выходам коммутатора, вход которо.го соединен с шиной тактовых сигналов,е входы установки в единичное состояниеразрядов регистра результата соединены сс управляющей шиной устройства ( 2.Однако известное устройство, зетрачи 55вея для упорядоченного переборе сортируемых чисел М ( И +1) тактов работы, обладает сравнительно низким быстродействием,8Белью изобретения является повышениебыстродействия устроЖтвв,Указанная цель досжигеется тем, чтоустрой:;тво для сортировки еи-разрядныхчисел, содержащее и регистров, ( е -1)схем сравнения, ( ь -1) переключателей,причем выходы кеждого 1-го регистра,кроме последнего, соединены с первойгруппой входов-й схемы сравнения,=1ю у 1 -число сравниваемых чисел выходы;. -й схемы сравнения соединены с входами-го переключателя,устройство содержит группы элементов ИЛИ,группы элементов И, причем выходы каждогоэлементов И, причем выходы каждого-го регистре кроме первого, соединены с второй группой ВхоДОБ ( 1 -1)-Ойсхемы сравнения, первая группа входовэлементов ИЛИ первой группы соединенас шиной ввода информации, выходы 1 -йгруппь;. элементов ИЛИ соединены с информационньми входами-го регистра,тактовые входы регистров соединены спервым управляющим входом устройствапервая, вторая и третья группы входов-х элементов ИЛИ группы соединены соответственно с выходами ( -1)-хэлементов И первой и второй групп и-хэлементов И третьей группы, втораягрушв входов первой грчты элементовИЛИ соединена с выходами первых элементов И третьей груты=2, И.первая и вторая группы входов е-хэлементов ИЛИ группы соединены соответственно с выходами ( п -1)-х элементовИ первой и второй групп, выходы 1 -горегистра соединены с информационнымивходами-х элементов И первой и второй групп и (-1)-ми элементами Итретьей группы 1= 1 р 1, второй управляющий вход устройства соединен суправляющими входами элементов И первойгруппы, третий управляющий вход устройс 1 ве - с первыми управляющими входаминечетных элементов И второй и третьейгруппы, в четвертый управляющий Входустройства - с первыми управляющимивходами четных элементов И второй итретьей групп, выход 1-го переключателясоединен с вторым управляющим входом-х элементов И второй и третьей групп,На чертеже представлена функциональная схеме устройстве.Устройство содержит м регистров 1",1, (-1) схем сравнения 2( И 1 -1) групп элементов ИЗЗ ,4 .,45, , 5 ,; груап элементову -13 10307 ИЛИ 6 , 6, (и 1-1) йереключагелей771, информационную шину устройства, 8, выходную шину 9, управлякзцие входы устройства 10-13.Устройство работает следующим обра зом.В начале работы переключатели 7 переводятся в положение, соответсвукюцее перебору ,чисел в порядке их убывания или возрастания (на чертеже положение 10 переключателя соответствуег расположению чисел в порядке их возрастания после перебора от регистра 1 к регистру 1). В регистры 1 заносягся исходные числа по информационной шине 8 через группы 15 элементов 6, и далее в регистры 1 1 п через первую группу элементов И 3 3 и элементы ИЛИ 6 6 подачей сигналов по управляющему входу 11, открывающей первую группу 20 элементов И З,.З и импульса ввода информации в регистр по управлякецему входу 10. Процесс сортировки начинается после 25 ввода последнего числа. При этом производится поочередное открывание элементов И первых и вторых групп, причем вначале подается открывающий потенциал по управляющему входу 12 на группы эле ментов И первой и второй групп элементов И, связанных со схемами сравнения 97 42, 2, а затем по входу 13 на группы элементов И, связанные со схемами ми сравнения 2, 2, а по управля 1 ошему входу 10 подаегся импульс ввода информации в регистр, При этом в первом такте производится обмен между парами регистров 1 и 1, 1 и 1 ч причем большее число оказывается в, регистре с большим индексом. Во втором такте производится аналогичный обмен между царами регистров 1 и 1, 1 и 1 Таким образом, максимум через, ( и 1-1) тактов все сортируемые числа окажутся расположенными в порядке возрастания ог регистра 1 к регистру 1 После этого может быть произведен сьем отсортированных чисел открывающего сигнала по второму управляющему входу 11 и сигналов по первому управляющему входу 10 с выходной шины 9.Для исключения возможных ошибок при вводе, выводе и обмене информации в в регистрах регистры выполнены на тригге. рах с внутренней задержкой, позволяющие в одном такте совмещать процесс считывания и записи.Предлагаемое устройство обладает по сравнению с известным более высоким быстродействием, гвк как для сортировки требуется только 0 М -1 ) такт работы, в то время квк в извесгном требовалось п (о +1) такт.