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

(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к области вычислительной техники. Целью изобретения является повышение быстродей ствия, Устройство содержит группу из К входных сумматоров 1, выходной сум матор 2, блок 5 выбора максимального числа, регистр 10, преобразователь 15 числа единиц в двоичный код, счет чик 16, элементы И, ИЛИ, ИЛИ-НЕ, фор мирователь импульсов. Сортируемые числа в обратном коде поступают наблок выбора максимального числа, который определяет максимальный иэ них(т.е. минимальное из чисел). Ко всемкодам прибавляется такой код, при котором его сумма с максимальным обратным ходом переполняет соответствующийсумматор. Этот же код прибавляется квыходному сумматору, содержимое которого выдается на выход устройства.столько раз, сколько сумматоров переполнилось в данном такте, В каждомтакте к выходному сумматору добавлят":ется код разности между выданным навыход числом и следующим за нимпо возрастанию числом. Переполненсумматоры блокируются. Таким обрав каждом такте либо формируется сле,дующее число для выдачи на выход, либо выдается на выход следующее эа ранее выданным по возрастанию число1 з.п. ф-лы, 2 ил.Изобретение относится к вычислительной технике и может использоваться в устройствах обработки сигналов.Цель изобретения - повышение быст 5родействия устройства путем организации изменения содержимого счетчиковза один такт на число единиц, равноеразности между двумя соседними сортируемыми числами. ОНа фиг. 1 приведена структурнаясхема устройства; на фиг. 2 - схемыблошка выбора.Устройство содержит группу из Квходных сумматоров 1, выходной сумматор 2, группу из К элементов ИЛИ 3,элемент ИЛИ 4, блок 5 выбора максимального числа, группу из К+1 блоковэлементов И 6, элемент И 7, группувыходных элементов И 8, группу из К 20формирователей 9 импульсов, регистр10 элемент ИЛИ-НЕ 11, элемент 12 задержки, элемент И 13, формирователь14 импульсов, преобразователь 15 числа единиц в двоичный код, счетчик 516, элемент ИЛИ-НЕ 17, элемент И 18,группу из К входов 19 блока 5 выбора,выход 20 блока 5 выбора, тактовыйвход 21 устройства, информационныйвью:од 22 устройства, выход 23 разрешения выдачи устройства. Блок 5 выбора максимального числа содержит матрицу 24 элементов сравнения, группуиз К элементов И 25, блок элементовИ-ИЛИ-НЕ 26 и сумматор 27.Устройство работает следующим об 35разом,Во входные сумматоры 1 заносятся(при сортировке в порядке возрастания) обратные коды сортируемых чисел. 40Регистр 10 и счетчик 6 обнулены.Сумматор 2 установлен в максимальноесостояние (значение "1" на всех разрядах). На выходах элементов ИЛИ 4,ИЛИ-НЕ 11 и 17 - единичные потенциа 45лы. Коды с сумматоров 1 поступают навходы 19 блока 5 выбора максимальногочисла, который выбирает из них максимальный код, инвертирует его, прибав-ляет к результату единицу младшегоразряда и выдает на выход 20.50На вход 21 устройства подаетсятактовый импульс, который проходитчерез элемент И 7 и открывает блокиэлементов И 6. Код 20 прибавляетсяк содержимому накапливающих сумматоров 1 и 2. При этом в сумматорах 1,где был максимальный код, получается"0" (сСТ+ (вых 20) = ш +(ш+1)- (ш+т) + 1 = 1111 + 000100,.00), а в сумматоре 2 - код минимального числа из сортируемыхСТ 2 + (вых 20) = 11.11 + (и+1)+ ш = ш), так как в сумматорах были обратные коды чисел, а единица переноса (переполнения) при суммировании отбрасывается. По нулевым содержимым сумматоров 1 элементы ИЛИ 3 выдают нулевой сигнал, закрывающий соответствующие блоки элементов И 6,исключая данные числа из дальнейшегоанализа. Соответствующие формирователи 9 по отрицательному фронту выдаютсигналы, которые фиксируются на регистре 10. Элемент ИЛИ-НЕ 11 выдаетнулевой сигнал, закрывающий элементИ 13. Преобразователь 15 формируеткод количества сумматоров 1, обнуленных в данном такте. Блок 5 выборамаксимального числа формирует слепчющий код 20.По концу тактового импульса срабатывает элемент И 13, разрешая приемколичества выделенных наименьших чисел в счетчик 16. Элемент ИЛИ-НЕ 17переключается в 0, закрывая элементИ 13 и подготавливая (через Г наэлементе 12 задержки) к открытию элемент И 18.По следующим нескольким тактовымимпульсам, проходящим через элементИ 18, отнимается единица от содержимого счетчика 16 и выдается сигнална выходе 23 и код 22 выделенного.числа на выходы устройства, покасчетчик 16 не обнулится. При этомэлемент ИЛИ-НЕ 17 переключается в "1",закрывая (через - =импульса) элемент И 18. Формирователь 14 выдаетимпульс, гасящий регистр 10, и элемент ИЛИ-НЕ 11 переключается в "1",открывая элемент И 7,Далее цикл обработки повторяется,пока все сумматоры 1 не обнулятся иэлемент ИЛИ 4 не закроет элемент И 7.П р и м е р (сортировки по возрастанию трехзарядных чисел). Пусть требуется отсортировать числа 3,3,75,В сумматоре 2 код "7". В сумматоры 1заносятся обратные коды 4,4,0,2. Блок5 выбора выбирает максимальный изних, инвертирует и добавляет "1":4 + 1 = 3 + 1 = 4. Этот код прибавляется ко всем сумматорам 1 (получаем8,8,4,6) и 2 (получаем 11) и послеотбрасывания единицы переноса (пере(в 1 и 2 разрядах) . В двух следующихтактах код сумматора 2 (равный "3")5дважды выдается на выход 22.В это время блок 5 выбирает максимальный код "6" и выдает число 6 + 1 =1 + 1 = 2. После прибавления (потактовому импульсу) на сумматорах по Олучаем 0,0,6,8 и 5, а после отбрасывания "8" - 0,0,6,0 и 5, Код "5" выдается 1 раз на выход 22 по следующему тактовому импульсу.Блок 5 снова выбирает максимальный 5и икод 6 и выдает число 2. На сумматорах получаем 0,0,8,0 и 7 (после отбрасывания "8" - 0,0, 0,0 и 7), код7 выдается на выход 22.Все сумматоры обнулены, сортировка закончена, Числа выданы на выход22 в порядке 3,3,5,7 в прямом коде.Блок 5 выбора максимального числаработает. следующим образом,Поступающие на входы 19 числа25сравниваются между собой на элементах24 сравнения матрипь. Результатысравнения 1-го числа (1 = 1, К) состальными группируются на входахр-го элемента И 25 группы, Для максимального числа (при равных максимальных для числа с меньшим номеромвхода) все результаты сравнения имеют единичное значение, и соответствующий этому числу элемент И 25 выдает единичный сигнал. Выбранное таким образом число проходит черезблок элементов И-ИЛИ-НЕ 26, инвертируясь на выходе. На сумматоре 27 кполученному коду прибавляется единица младшего разряда, результат выдается на выход 20.Для сортировки чисел, начиная смаксимального, надо записать их всумматоры 1 в прямом коде и резуль-д 45тат получать с инверсных выходов сумматора 2.Таким образом, устройство позволяет отсортировать числа за числотактов, равное сумме количества раз рличных чисел среди сортируемых и количества сортируемых чисел (время затрачивается на выдачу чисел на выход 22). 55Фо рмула из обре тения 1.устройство для сортировки чисел,содержащее группу элементов ИЛИ, элемент ИЛИ, группу элементов И, группу выходных элементов И, первый, второй и третий элементы И, группу формирователей импульсов, регистр, преобразователь числа единиц в двоичный код, счетчик, первый и второй элементы ИЛИ-НЕ, формирователь импульса и элемент задержки, причем тактовый вход устройства подключен к первым входам первого, второго и третьего элементов И, выход -го элемента ИЛИ группы, где 1 = 1К, К число сортируемых чисел, подключен к входу группы и 1-му входу элемента ИЛИ и входу д-го формирователя импульса группы, выход которого подключен к -му входу регистра, выходы разрядов которого подключены к входам преобразователя числа единиц в двоичный код и входам первого элемента ИЛИ-НЕ, выход которого подклюг чен к второму входу первого элемента И, выход которого соединен с входом управления записью счетчика, к информационным входам которого подключены выходы преобразователя числа . единиц в двоичный код, выходы разрядов счетчика соединены с входами второго элемента ИЛИ-НЕ, выход которого через формирователь импульса подключен к входу сброса регистра, выход второго элемента И подключен к вычитающему входу счетчика, управляющему входу группы выходных элементов И и является выходом разрешениявыдачи устройства, выходы элементовИ выходной группы являются информационными выходами устройства, о т л и -ч а ю щ е е с я тем, что, с цельюповышения быстродействия, в него введены группа сумматоров, выходной сумматор, К групп элементов И и блок выбора максимального числа, причем выход первого элемента ИЛИ-НЕ и выходэлемента ИЛИ подключены соответственно к второму и третьему входам третьего элемента И, выход которого соединен с первыми управляющими входамиэлементов И всех групп, выходы элементов И -й группы подключены к входам д-го сумматора группы, выходы которого подключены к входам 1.-го элемента ИЛИ группы и к входам 1-й группы блока выбора максимального числа,выходы которого соединены с информационными входами элементов И всехгрупп, выход 1-го элемента 1 ПИ группыподключен к вторым управляющим входам4639 Фиг. 8Составитель В, ЖуравлевТехред МеДидык Корректор М. Васильев едактор ко аказ 1894/46 Тираж 667 ПодписноеНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5 оизводственно-издательский комбинат"Патент", г.ужгород, ул, Гагарина,101 5 147 элементов И д-й группы, выходы элементов И (К+1)-й группы подключены к входам выходного сумматора, выходы которого подключены к информационным входам выходных элементов И группы, выход второго элемента ИЛИ"НЕ подключен к третьему входу первого элемента И и через элемент задержки - к второму входу второго элемента И,2. Устройство по п. 1, о т л и - ч а ю щ е е с я тем, что блок выбора максимального числа содержит матрицу элементов сравнения, группу элементов И, блок элементов И-ИЛИ-НЕ и сумматор, причем первая и вторая группыевходов р-го элемента сравнения матрицы (р - номер строки, р = 1, К - 1,номер столбца, 3 = Р,К) подключены соответственно к р-й и 3+1)-йгруппам входов блока, прямой и инверсный выходы данного элемента сравнения матрицы подключены соответственно к 3-му входу и р-му входамЦ т 1)-го элемента И группы, выходт-го элемента й тт = 1К) груп пы и 3-й вход блока подключены соот.ветственно к 3-му управляющему и1-му информационному входам блокаэлементов И-ИЛИ-НЕ, выходы которогоподключены к информационным входам 15 сумматора,. управляющий вход которогоподключен к уровню логической единицы, а выход является выходом блокавыбора максимального числа.