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

СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИХ(51)5С 0 ГОСУДАРСТВЕННОЕ ПАТЕНТНВЕДОМСТВО СССР(71) Московский инсданской авиации(56) Авторское свидетельство СССРВ 746501, кл. 6 06 Р 7/02, 1978,Авторское свидетельство СССРК. 1049900, кл, 6 06 Е 7/06, 1982.(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКДВОИЧНЫХ ЧИСЕЛ(57) Изобретение относится к автоматикевычислительной технике. Цель изобрет Изобретение относится к вычислительной технике и может быть использовано в вычислительных процессорах при выполнении операций сравнения многоразрядных кодовых комбинаций с целью их упорядочения или в задачах экстремального управления.Известно устройство для сортировки двоичных чисел, содержащее регистры, первые, вторые и третьи элементы И, триггеры, блоки сравнения, элементы ИЛИ и НЕ.достатком известного устройства явля низкое быстродействие и узкие функ нальные возможности,Наиболее близким по технической сущности к заявляемому является устройство для сортировки двоичных чисел, содержащее группу входных регистров. блок групп элементов И, дешифраторы и блоки сравнения, блок управления, блок выявления равных чисел, формирователь сброса и. коммутатор. ния - повышение быстродействия. Устройство содержит информационные входы 1, регистры 2, блоки 3 сортировки, группу элементов 4, блок управления 5, элемент ИЛИ 6, входы блоков сортировки 7, выходы устройства 8, Устройство выполняет сортировку массива чисел методом "пузырька", Каждый блок сортировки 3 сравнивает попарно соседние числа и переставляет их в возрастающем порядке. Элемент ИЛИ 8 фиксирует наличие хотя бы одной перестановки, при их отсутствии сортировка с;итается законченной. 7 ил. Недостатком прототипа является низкое быстродействие; так как независимо от расположения чисел перед сортировкой для сортировки К чисел требуется К тактов рабо-. ты устройства-прототипа.Целью изобретения является повышение быстродействия устройства.Поставленная цель достигается тем, что в устройство для сортировки двоичных чисел, содержащее группу и) регистров, где в - количество сортируемых чисел, входы регистров являются информационными входами устройства, и блок управления, первый вход которого является входом запуска устройства, введены а блоков сортировки, соединенные последовательно по информационным входам, и выходам, группу элементов И и элемент ИЛИ-НЕ, Выходы всех блоков сортировки подключены к информационной шине устройства, соединенной с соответствующими информационными входами элементов И группы, выходырегистров соединены с соответствующими информационными входами первого блока сортировки, Управляющие входы блоков сортировки соединены с соответствующими выходами блока управления, управляющие выходы всех блоков сортировки кроме первого и дополнительный выход блока управления соединены с входами элемента ИЛИ, выход которого подключен к управляющим входам элементов И группы и к второму входу блока управления. Каждый блок сортировки содержит групйу коммутаторов, элемент задержки, элемент И и элемент ИЛИ-НЕ, управляющий вход блока сортировки соединен с управляющими входами всех коммутаторов группы и через элемент задержки - с первым входом элемента И, второй вход и выход которого соединены соответственно с выходом элемента ИЛИНЕ иуправляющим выходом блока сортировки. Входы элемейта ИЛИ соединены с управляющими выходами всех коммутаторов труппы, каждый из которых содержит две группы информационных входов, две группы информационных выходов, четыре группы ключей, схему сравнения, и два регистра, причем первая группа информационных входов коммутатора соединена с группами информационных входов первой и третьей групп ключей, и,с первой группой входов схемы сравнения, Вторая группа информационных входов коммутатора соединена с группами информационнь 1 х входов второй и четвертой групп ключей и с второй группой входов схемы сравнения. Одноименные выходы ключей первой и второй групп объединены и подключены к информационным входам первого регистра, одноименые выходы ключей третьей и четвертой групп объединены и подключены к информационным входам второго регистра, первый выход схемы сравнения соединен с управляющими входами первой и четвертой групп ключей, второй выход - с управляющими входами второй и третьей групп ключей и является управляющим выходом коммутатора. Выходы первого и второго регистров являются соответственно первой и второй группами информационных выходов коммутатора, каждая схема сравнения содержит группу К дешифраторов, где К - раз рядность сортируемых чисел, группу Кэлементов И, группу Кэлементов ИЛИ, выходной элемент ИЛИ и элемент НЕ, причем вход элемента НЕ соединен с выходом выходного элемента ИЛИ и является вторым выходом схемы сравнения, а выход - первым выходом схемы сравнения, входы 1-го дешифратора, 1= 1, К, соединены с 1-ми входами первой и второй групп информа ционных входов коммутатора, первый и второй выходы)-го дешифратора,)= 2, К, соединены с входами О)-го элемента ИЛИ группы, выход которого подключен к входам элементов И группы с первогопо-й, третий выход 1-го дешифратора 1= 1, К, соединен с соответствующим входом 1-го элемента И группы, выходы элементов И группы и третий выход К-го дешифратора 10 соединены с входами выходного элемента. устройства для сортировки двоичных чисел; на фиг. 2 - структурная схема блока управ 15 ления; на фиг. 3 - структурная схема блокасортировки; на фиг. 4 - структурная схема коммутатора; на фиг, 5 - возможная структурная схема схемы сравнения; на фиг. 6 и 7 - иллюстрации упорядочения чисел (сортировки) для четного и нечетного а соответственноо. 20 Устройство для сортировки двоичныхчисел содержит щ групп по Квходов, соединенных соответственно с информационными входами регистровой группы 21 - 2 п (соответственно входы 11 -11, , 1 п 1 -1 П 1 ), Группы выходов регистров соединены с информационными входами первого блока 31 30 сортировки. Блоки сортировки 31-Зп соединены последовательно по информационным входам и выходам, Устройство содержит также группу 4 элементов И, блок управления 5 и элемент ИЛИ 6. Каждый блок 35 3 имеет в групп по К входов соответственно711-7 пк. Выходы 81 1-8 вк блока 4 являются выходами устройства. Вход 9 блока управления является входом записи устройства.Выходы 101 - 10 п 1 блока 5 являются управля ющими выходами блока 5, и соединены суправляющими входами соответствующих блоков 3.Блок 5 управления (см. фиг. 2) содержиттриггер 11, генератор 12 тактовых импуль сов и распределитель 13 импульсов,Блок 3 сортировки (см. фиг. 3) содержитгруппу 14 коммутаторов, элемент 15 ИЛИН Е, элемент 16 И и элемент 17 задержки.Каждый коммутатор 14 (см. фиг. 4) содержит четыре группы ключей 181-18 а, схему сравнения 19 и два регистра 201 и 202.Первый выход 21 схемы сравнения соединен с управляющими входами групп 181 и 1 йа ключей, второй выход 22 схемы сравнения соединен с управляющими входами групп 182 и 18 з ключей и является управляющим выходом коммутатора.Каждая схема 19 сравнения (см, фиг, 5)содержит группу дешифраторов 231-23 к, группу элементов ИЛИ 241-24 к, группу1783511 5 6элементов 251-25 кИ, выходной элемент старший). Вход управления записью не по ИЛИ и элемент 27 НЕ, казан на чертежах.Принцип работы устройства. сортиров-По входу 9 поступает сигнал запуска ки заключается вследующем, Совокупность устройства. Этот сигнал устанавливает в двоичных чисел разбивается на пары и про единйчное состояние триггера 11 блока упизводится, сравнение чисел каждой пары равленйя 5, положительным сигналом с (например, при щ - числе еортируемых чи- прямого выхода которого запускается гесел - четном). В результате сравнения в нератор 12. Этим же импульсом устанавликаждом блоке сортировки производится пе- вается в исходное"состояние(в младшем рекоммутация сравниваемых чисел пары та разряде - едйница, в остадьных - нули) ким образом, что большее число каждой распределитель 13, реализуемый, найрипары появляется на выходах блока сорти- мер,нарегиСтресдвига. Приэтомединичровки (соответСтвующего коммутатора) с ным значенйем сигнала -в младшем меньшим номером; На следующей ступени разряде распределителя 13 запускается (в следующем блоке сортировки) меньшее 15 работа первой ступени сортировки (блок.число парыс меньшими номерами сравни). Рассмотрим работу устройства сортивается с большим числом смежной пары с ровки для четного,большими номерами и также производитсяперекоммутация, Если на какой-либо ступе- . К моменту подачй импульса запуска на ни сравнения некоторые (например, край вход 9 в регистры 2 уже запйсаныдвоичные ние) числа не имеют пары для сравнения, то " числа, онийрисутствуют"навходах 7 коммуони запоминаются и передаются сразу в" таторов 14 блока 3 сортировки первой стуследуащую ступень сравнения (в следую- пени, который (как и для всех нечетных щий блок сортировки). Таким образом, по. ступеней в соответствйи с фиг. 6) имеет а/2 мере продвикения чисел по блокам сорти коммутаторов 14. В каждом коммутаторе 14 ровки, соединенным последовательно, - соответствующими числа некоторой. пары большие числа постепенно передвигаются подайы"в"вйде сигналов на входы ключей на группы входов(выходов с меньшими но- групп 18 и схемы" 19 сравнения; Так какЭмерами, а меньшие числа - на группы вхо- схема сравнения 19-, комбинационное устдов) выходов с большими номерами, После 30 ройство, то на ее выходах 21 и 22 также к полной сортировки на первой группе выхо- моменту подачиимпульса на"вход 9 сформи-дов устройства наличествует. наибольшее " рованы соответСтвуюЩие сигналы, и группы число, а на последней группе выходов - на- ключей 18 скоммутированы соответствуюименьшее число. При любом исходном рас-щим образом на входы регистров 20. Расположении сортируемых чисел сортировка 35 смотрймработу устройства 14.заканчивается не более, чем заа тактов, а: Коммутатор (см. фиг, 4) коммутирует . в ряде случаев - раньше. входныечисла таким образом; что на выхоПриведенное описание иллюстрирует- дах первой группы (с меньшим индексомся фиг. 6 и 7 (соответственно для четного 8 формируется число с большим значением, а и нечтетного 7 количества сортируемых чи на выходах с индексом 1+1 - меньшее число.сел), На фиг, 6 и 7 приведены примеры с Это реализуется тем, что, схема 19 форминаименее благоприятными вариантамиис- рует разрешающий сигнал навыходе 21 в ходного расположения сортируемых чисел,случае, когда чиСло сменьшим"Ийдексом (в что доказывает гарантированное заверше- дальйейшем - число А) больше или равно ние сортировки за а тактов. При этом на 4 числус большим индексом(вдальнейшем - фиг, 6 и 7 пары чисел в квадратах - содер- числу Б), Если ВА, разрешающий сигнал жимое соответствующих выходов - первых формируется на выходе 22 и открывает груп- (сверху) и вторых (снизу) коммутаторов. От-пу ключей 182 и 18 з, обспечивая коммутадельные числа в крайних строках соответст-, цию входов 71" - 7 к 1 на входы регистра вуют числам, для которых на данной 201, а входы 71-7 к-на входы регистра 212.ступени нет пары; при этом данное число В противном случае (АВ) осуществляется50сразу переводится(без изменения) в следу- обратная коммутация, Одна из модификающую ступень упорядочения ций устройства сравнения 19 приведена наУстройство сортировки работает следу- фиг, 5. При этом. схема 19 реализует следующим образом, ющую функциюСовокупность сортируемых чисел записывается параллельным кодом в регистры 2 (22) = Ак Вк(Ак ВкАк Вк) Х (по входам 1, причем по входу 11 записыва ется младший разряд числа, а по входу 1 к - Х АкчВк(Ак ВкчАк Вк) хк (АкчВкАк- Вк) АкВк г(АК Вк гАК Вк) (Ак 1 Вк Ц тттАкчВК)(А 2 Вг" Аг Вг) А 1 В 1где (22) - обозначение наличия разрешающего сигнала на выходе 22,Сигнал на выходе 21 является инверснымотносительно сигнала на выходе 22 схемы 10сравнения. На входы каждого дешифратора23 подаются одноименные разряды сравниваемых чйсел. Выходы 28 и 30 каждого дешифратора(положительныесигналы на них)соответствуют следующим соотношениям 15значений разрядов чисел; А= 1 и В= 1; А= 0и В= О. Сигнал на выходе 29 соответствуетсоотношению А= 0 и В= 1. Таким образом(см. фиг.5) числа анализируются, начиная состарших разрядов и в случае, когда при равных старших разрядах чисел А и В значениеочередного разряда числа В больше соответствующего значения разряда числа А,выполняется условие ВА, Логическая функция, приведенная выше, реализуется элементами 25, 26 и 27.При поступлении управляющего сиг-.нала по входу 10 осуществляется записьсоответствующих чисел в регистры 20 первой ступени и с некоторой задержкой (задаваемой, элементом 17) формируетсясигнал опроса блока 31, Регистры 20 реализованы таким образом, что лишь приналичии сигнала на их входах от соответствующего входа 10 обеспечивается формирование сигналов на их выходах - впротивном случае регистры 20 отключеныот выходной шины 7. Это обеспечивается,например, использованием регистров,включающих в свой состав элементы с тремя состояниями (например. регистры типа ОК 589ИР 12), выходы которых при отсутствии управляющего сигнала находятся ввысокоимпедансном состоянии. Таким образом, в первой ступени осуществляетсяпопарная сортировка чисел.Далее генератор 12 формирует тактовый импульс, который сдвигает единичныйсигнал в следующий разряд распределителя13; отключается блок сортировки первойступени и включается в работу блок сорти. ровки второй ступени, который (соответственно фиг. 6, как и все блоки сортировкиП 1четных ступеней) содержит-1 коммута 2торов. Работа блока сортировки 3 второйступени в остальном аналогична работе блока сортировки первой ступени.С каждым тактовым импульсом производится сортировка чисел очередным блоком 3 сортировки аналогичным образом. По окончании упорядочения на выходах 711-71 кустройства содержится наибольшее число, а на выходах 7 ы - 7 мк - наименьшее число, тоесть числа массива рассортированы по убыванию.Процесс сортировки может закончиться ранее, чем за в тактов. Это происходит следующим образом. При срабатывании очередной ступени сортировки - кроме первой- анализируется факт срабатывания хотя быодного коммутатора, то есть, его схемы сравнения 19- появления сигнала разрешения на ее выходе 22, Если на выходе 22 хотя бы одного из устройств 19 данной ступениформируется положительный сигнал, это означает, что сортировка не закончена. Если же ни одна схема 19 не формирует сигнална выходе 22 - сортировка закончена, навходах элемента 15 ИЛИ-НЕ соответствующего блока 3 - "нули", на выходе "единица",которая проходит через открываемый сигналом с элемента 17 задержки элемент 16 Ина вход элемента 6 ИЛИ, сигнал с выходакоторого открывает элементы И 4 и выдаетинформацию на выход устройства, а также.сбрасывает триггер 11 блока управления 5,останавливая работу устройства, Сигналысортированных чисел выдаются на выходыустройства до поступления следующего сигнала запуска на вход 9,При нечетном количестве упорядочиваемых чисел для корректной работы устрой-ства следует подать ва первую группувходов код числа, заведомо большего, чемчисло сортируемого массива. либо на последнюю группу входов - код числа, заведомо меньшего, чем любое из чиселсортируемого массива, При этом процесссортировки протекает аналогично, а из выходной информации соответственно исключается первая или последняя группавыходов. Если окончательное упорядочениечисел происходит лишь на последней ступени, сигнал на элемент ИЛИ 6 формируется сдополнительного выхода блока 5 (с гп+1-горазряда распределителя 13),Таким образом. устройство позволяетосуществлять сортировку чисел, причемвремя сортировки зависит от исходного расположения чисел в сортируемом массиве,что позволяет в ряде случаев закончить сортировку раньше, чем через п 1 тактов,ФФормула изобретения Устройство для сортировки двоичных чисел. содержащее щ входных регистров, где п 1 - количество сортируемых чисел, п 1 групп элементов И и блок управления, содержащий триггер, генератор импульсов и распределитель импульсов, причем входы рЕгистров являются информационными входами устройства, вход запуска устройства соединен с входом установки триггера 5 блока управления в единичное состояние, выход которого соединен с входом запуска генератора импульсов, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены элемент ИЛИ и п блоков 10 сортировки, каждый из которых содержит элемент ИЛИ-НЕ, элемент И, элемент задержки и группу узлов коммутации, каждый из которых содержит схему сравнения, два регистра и четыре группы ключей, причем 15 1-я группа информационных входов узла коммутации (1. = 1, 2) соединена с информационными входами ключей 1+2-й группы и с 1-й группой входов схемы сравнения, 1-й вход которой соединен с управляющими 20 входами ключей 1-й и 5й групп, выходы ключей 21-1-й и 21-й групп соединены с информационными входами 1-го регистра, выходы разрядов которого являются 1-й группой информационных выходов узла 25 коммутации, в блоке сортировки информационные входы и выходы узлов коммутации являются соответствующими входами и выходами блока сортировки, вторые выходы схем сравнения всех узлов коммутации дан ного блока сортировки соединены с соответствующими входами элемента ИЛИ-НЕ, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом элемента задержки, выходы разрядов входных регистров соединены с соответствующими информационными входами первого блока сортировки, соответствующие информационные выходы первого блока сортировки, одноименные входы и выходы остальных блоков сортировки и первые входы элементов И соответствующих групп объединены, выходы элементов И групп являются выходами устройства, в блоке управления выход генератора импульсов соединен со счетным входом распределителя импульсов, вход установки в начальное, состояние которого соединен с входом запуска устройства, )-й выход которого= 1, 2, .в) соединен с входом элемента задержки )-го блока сортировки и входамисчитывания регистров всех узлов коммутации -го блока сортировки, е+ 1-й выход распределителя импульсов блока управления и выходы элементов И всех блоков сортировки. кроме первого, соединены с соответствующими входами элемента ИЛИ, выход которого соединен с вторыми входами элементов И всех групп и входом установки в нулевое состояние триггера блока управления..Лисина роизводственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 каз 4516 Тираж Подписное . ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5