Устройство для сортировки чисел
Изобретение относится к области вычислительной техники. Целью изобретения является повышение быстродействия. Устройство содержит группу из К входных сумматоров 1, выходной сумматор 2, блок 5 выбора максимального числа, регистр 10, преобразователь 15 числа единиц в двоичный код, счетчик 16, элементы И, ИЛИ, ИЛИ-НЕ, формирователи импульсов. Сортируемые числа в обратном коде поступают на блок выбора максимального числа, который определяет максимальный из них /т.е. минимальное из чисел/. Ко всем кодам прибавляется такой код, при котором сумма с максимальным обратным ходом переполняет соответствующий сумматор. Этот же код прибавляется к выходному сумматору ,содержимое которого выдается на выход устройства столько раз, сколько сумматоров переполнилось в данном такте. В каждом такте к выходному сумматору добавляется код разности между выданным на выход числом и следующим за ним по возрастанию числом. Переполненные сумматоры блокируются. Таким образом, в каждом такте либо формируется следующее число для выдачи на выход, либо выдается на выход следующее заранее выданным по возрастанию число. 2 ил.
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИН (191 (11) 4 39 А 1 (51) 4 G 06 F 7/08
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К A ВТОРСНОМ .Ф СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР (21) 4275972/24-24 (22) 02.07,87 (46) 23.04.89. Бюл. Ь - 15 (72) М.М. Зарецкий, С.В. Ефимов, В.В. Мазаник и И.H. Лучин (53) 681.325(088.8) (56) Авторское свидетельство СССР
N- 993251, кл. G 06 F 7/08, 1981.
Авторское свидетельство СССР
N - 1179317, .кл. С 06 F 7/08, 1985. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к области вычислительной техники. Целью изобретения является повышение быстродействия. Устройство содержит группу из
К входных сумматоров 1, выходной сумматор 2, блок 5 выбора максимального числа, регистр 10, преобразователь
15 числа единиц в двоичный код, счетчик 16, элементы И, ИЛИ, ИЛИ-НЕ, формирователь импульсов. Сортируемые числа в обратном коде поступают на блок выбора максимального числа, который определяет максимальный иэ них (т.е. минимальное из чисел). Ко всем кодаи прибавляется такой код, при котором его сумма с максимальным обрат.ным ходом переполняет соответствующий сумматор. Этот же код прибавляется к выходному сумматору, содержимое которого выдается на выход устройства. столько раз, сколько сумматоров переполнилось в данном такте. В каждом такте к выходному сумматору добавля ется код разности между выданным на выход числом и следующим за ним по возрастанию числом. Переполненные сумматоры блокируются. Таким образом, в каждом такте либо формируется слее дующее число для выдачи на выход, либо выдается на выход следующее за ранее выданным по возрастанию число, 1 з.п. ф-лы 2 ил.
1474639
Изобретение относится к вычислительной технике и может использоваться в устройствах обработки сигналов.
Цель изобретения — повышение быст5 родействия устройства путем организации изменения содержимого счетчиков за один такт на число единиц, равное разности между двумя соседними сортируемыми числами. !О
На фиг. 1 приведена структурная схема устройства; на фиг. 2 — схемы блока выбора.
Устройство содержит группу из К входных сумматоров 1, выходной сумма- 15 тор 2, группу из К элементов ИЛИ 3, элемент ИЛИ 4, блок 5 выбора максимального числа, группу из К+1 блоков элементов И 6, элемент И 7, группу выходных элементов И 8, группу из К формирователей 9 импульсов, регистр
10 элемент ИЛИ-НЕ 11, элемент 12 задержки, элемент И 13, формирователь
14 импульсов, преобразователь 15 числа единиц в двоичный код, счетчик
16, элемент ИЛИ-HE 17, элемент И 18, группу из К входов 19 блока 5 выбора, выход 20 блока 5 выбора, тактовый вход 21 устройства, информационный вью:од 22 устройства, выход 23 разрешения выдачи устройства. Блок 5 выбора максимального числа содержит мат - рицу 24 элементов сравнения, группу из К элементов И 25, блок элементов
И-ИЛИ-НЕ 26 и сумматор 27.
Устройство работает следующим об35 разом.
Во входные сумматоры 1 заносятся (при сортировке в порядке возрастания) обратные коды сортируемых чисел. 40
Регистр 10 и счетчик 16 обнулены.
Сумматор 2 установлен в максимальное состояние (значение "1" на всех разрядах). На выходах элементов ИЛИ 4, ИЛИ-НЕ 11 и 17 — единичные потенциа45 лы. Коды с сумматоров 1 поступают на входы 19 блока 5 выбора максимального числа, который выбирает из них максимальный код, инвертирует его, прибавляет к результату единицу младшего разряда и выдает на выход 20.
На вход 21 устройства подается тактовый импульс, который проходит через элемент И 7 и открывает блоки элементов И 6. Код 20 прибавляется содержимому накапливающих сумматоров 1 и 2. При этом в сумматорах 1, где был максимальный код, получается
"0" (сСТ! p + (вых20) = m +(m+1) — (m+m) + I = II..II + ОО..ОЕ
00..00), а в сумматоре 2 — код минимального числа из сортируемых ((СТ2> + (вых20) = II II + (и+Е) (II..II + ОО..OI) + m = 00..00 +
+ m = m), так как в сумматорах. были обратные коды чисел, а единица переноса (переполнения) при суммировании отбрасывается. По нулевым содержимым сумматоров 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,7,5.
В сумматоре 2 код "7". В сумматоры 1 заносятся обратные коды 4,4,0,2. Блок
5 выбора выбирает максимальный из них, инвертирует и добавляет "1":
4 + 1 = 3 + 1 = 4. Этот код прибавляется ко всем сумматорам 1 (получаем
8,8,4,6) и 2 (получаем 11) и после отбрасывания единицы переноса (пере1474639 полнения), т.е. числа 8, имеем 0,0,4, 6 и 3. В регистре 10 будут 2 единицы (в 1 и 2 разрядах) . В двух следующих тактах код сумматора 2 (равный "3")
5 дважды выдается на выход 22.
В это время блок 5 выбирает максимальный код "6" и выдает число 6+ 1 =
1 + 1 = 2. После прибавления (по тактовому импульсу) на сумматорах по- 1р лучаем 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 сравнения матрипы. Результаты сравнения i-ro числа (i = 1-, К) с остальными группируются на входах
\ р-ro элемента И 25 группы, Для максимального числа (при равных максимальных для числа с меньшим номером входа) все результаты сравнения имеют единичное значение, и соответствующий этому числу элемент И 25 вы- 35 дает единичный сигнал. Выбранное таким образом число проходит через блок элементов И-ИЛИ-НЕ 26, инвертируясь на выходе. На сумматоре 27 к полученному коду прибавляется едини- 40 ца младшего разряда, результат выдается на выход 20.
Для сортировки чисел, начиная с максимального, надо записать их в сумматоры 1 в прямом коде и резуль- . 45 тат получать с инверсных выходов сумматора 2.
Таким образом, устройство позволяет отсортировать числа за число тактов, равное сумме количества раз- 5р личных чисел среди сортируемых и количества сортируемых чисел (время затрачивается на выдачу чисел на выход 22).
Формула изобретения
l .ÓñòðîéñòHo для сортировки чисел, содержащее группу элементов ИЛИ, элемент ИЛИ, группу элементов И, группу выходных элементов И, первый, второй и третий элементы И, группу формирователей импульсов, регистр, преобразователь числа единиц в двоичный код, счетчик, первый и второй элементы
ИЛИ-НЕ, формирователь импульса и элемент задержки, причем тактовый вход устройства подключен к первым входам первого, второго и третьего элементов И, выход i-ro элемента ИЛИ группы, где = 1,...,К, К число сортируемых чисел, подключен к входу группы и 1 му входу элемента ИЛИ и входу i-го формирователя импульса группы, выход которого подключен к i-му входу регистра, выходы разрядов которого подключены к Вхо дам преобразователя числа единиц в двоичный код и входам первого элемента ИЛИ-НЕ, выход которого пoäêÿîчен к второму входу первого элемента
И, выход которого соединен с входом управления записью счетчика, к информационным входам котороro подключены выходы преобразователя числа единиц в двоичный код, выходы разрядов счетчика соединены с входами второго элемента ИЛИ-НЕ, выход ко:.орого через формирователь импульса подключен к входу сброса регистра, выход второго элемента И подключен к вычитающему входу счетчика, управляющему входу группы выходных элементов И и является выходом разрешения выдачи устройства, выходы элементов
И выходной группы являются информационными выходами устройства, о т л и— ч а to щ е е с я тем, что, с целью повышения быстродействия, в него введены группа сумматоров, выходной сум— матор, К групп элементов И и блок выбора максимального числа, причем выход первого элемента ИЛИ-НЕ и выход элемента ИЛИ подключены соответственно к второму и третьему входам третьего элемента И, выход которого соединен с первыми управляющими входами элементов И всех групп, выходы элементов И i-й группы подключены к входам i-ro сумматора группы, выходы которого подключены к входам i-ro элемента ИЛИ группы и к входам i-й группы блока выбора максимальногo числа, выходы которого соединены с информационными входами элементов И всех групп, выход -го элемента 1ПИ группы подключен к вторым управляющим входам
)474639
Фиг. 2
Составитель В, Журавлев
Техред 1р1.Дидык
Корректор М. Васильева
Редактор В. Данко
Заказ 1894/46 Тираж 667 Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 элементов И i-й группы, выходы элементов И (К+1)-й группы подключены к входам выходного сумматора, выходы которого подключены к информационным входам выходных элементов И группы, выход второго элемента ИЛИ-НЕ подключен к третьему входу первого элемента И и через элемент задержки — к второму входу второго элемента И, 10
2. Устройство по п. l о т л и— ч а ю щ е е с я тем, что блок выбора максимального числа содержит матрицу элементов сравнения, группу элементов
И, блок элементов И-ИЛИ-hE и сумма- 15 тор, причем первая и вторая группы входов pj-го элемента сравнения матрицы (р — номер строки, р = 1, К вЂ” 1, номер столбца, j = P,К) подключены соответственно к р-й и j+I) и группам входов блока, прямой и инверсный выходы данного элемента сравнения матрицы подключены соответственно к 3-му входу и р-му входам (j+1)-ro элемента И группы, выход
i-ro элемента И (i = I,...,К) группы и j-й вход блока подключены соответственно к j-му управляющему и
j-му информационному входам блока элементов И-ИЛИ-НЕ, выходы которого подключены к информационным входам сумматора,. управляющий вход которого подключен к уровню логической единицы, а выход является выходом блока выбора максимального числа.
