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

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - повышение быстродействия. Устройство содержит информационные входы 1, регистры 2, блоки 3 сортировки, группу элементов 4, блок управления 5. элемент ИЛИ 6, входы блоков сортировки 7. выходы устройства 8. Устройство выполняет сортировку массива чисел методом пузырька. Каждый блок сортировки 3 сравнивает попарно соседние числа и переставляет их в возрастающем порядке. Элемент ИЛИ 8 фиксирует наличие хотя бы одной перестановки , при их отсутствии сортировка с итается законченной. 7 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si>s G 06 F 7/06

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4798982/24 (22) 05,03.90 (46) 23.12.92, Бюл. ¹ 47 (71) Московский институт инженеров гражданской авиации (72) С.Ж. Кишенский, Н.С. Вдовиченко, Е.Н.Надобных и О.Ю.Христенко (56) Авторское свидетельство СССР

N 746501, кл. G 06 F 7/02, 1978.

Авторское свидетельство СССР

¹ 1049900, кл, G 06 F 7/06, 1982. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ДВОИЧНЫХ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретеИзобретение относится к вычислительной технике и может быть использовано в вычислительных процессорах при выполнении операций сравнения многоразрядных кодовых комбинаций с целью их упорядочения или в задачах экстремального управления.

Известно устройство для сортировки двоичных чисел, содержащее регистры, первые, вторые и третьи элементы И, триггеры, блоки сравнения, элементы ИЛИ и НЕ. Недостатком известного устройства является низкое быстродействие и узкие функциональные возможности, Наиболее близким по технической сущности к заявляемому является устройство для сортировки двоичных чисел, содержащее группу входных регистров. блок групп элементов И, дешифраторы и блоки сравнения, блок управления, блок выявления равных чисел, формирователь сброса и. коммутатор. й.«„1783511 А1 ния — повышение быстродействия. Устройство содержит информационные входы 1, регистры 2, блоки 3 сортировки, группу элементов 4, блок управления 5, элемент ИЛИ

6, входы блоков сортировки 7, выходы устройства 8. Устройство выполняет сортировку массива чисел методом "пузырька", Каждый блок сортировки 3 сравнивает попарно соседние числа и переставляет их в возрастающем порядке. Элемент ИЛИ 8 фиксирует наличие хотя бы одной перестановки, и ри их отсутствии сорти ров ка считается законченной. 7 ил.

Недостатком прототипа является низкое быстродействие; так как независимо от . расположения чисел перед сортировкой для сортировки К чисел требуется К тактов рабо-. ты устройства-прототипа.

Целью изобретения является повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство для сортировки двоичных чисел, содержащее группу m регистров, где m — количество сортируемых чисел, входы регистров являются информационными входами устройства, и блок управления, первый вход которого является входом запуска устройства, введены m блоков сортировки, соединенные последовательно по информационным входам, и выходам, груп.пу элементов И и элемент ИЛИ-НЕ. Выходы всех блоков сортировки подключены к информационной шине устройства, соединенной с соответствующими информационными входами элементов И группы, выходы

1783511 регистров соединены с соответствующими информационными входами первого блока сортировки, Управляющие входы блоков сортировки соединены с соответствующими выходами блока управления, управляющие выходы всех блоков сортировки кроме первого и дополнительный выход блока управления соединены с входами элемента ИЛИ, выход которого подключен к управляющим входам элементов И группы и к ВТороМу входу блока управления. Каждый блок сортировки содержит групйу коммутаторов, элемент задержки, элемент И и элемент

ИЛИ-НЕ, управляющий вход блока сортировки соединен с управляющими входами всех коммутаторов группы и через элемент задержки — с первым входом элемента И, второй вход и выход которого соединены соответственно с выходом элемента ИЛИНЕ и управляющим выходом блока сортировки. Входы элемейта ИЛИ соединены с управляющими выходами всех коммутаторов труппы, каждый из которых содержит две группы информационных входов, две группы информационных выходов, четыре группы ключей, схему сравнения, и два регистра, причем первая группа информационных входов коммутатора соединена с группами информационных входов первой и третьей групп ключей, и,с первой группой входов схемы сравнения. Вторая группа информационных входов коммутатора соединена с группами информационных входов второй и четвертой групп ключей и с второй группой входов схемы сравнения. Одноименные выходы ключей первой и второй групп объединены и подключены к информационным входам первого регистра, одноименые выходы ключей третьей и четвертой групп обЪединены и подключены к информационным входам второго регистра, первый выход схемы сравнения соединен с управляющими входами первой и четвертой групп ключей, второй выход — с управляющими входами второй и третьей групп ключей и является управляющим выходом коммутатора. Выходы первого и второго регистров являются соответственно первой и второй группами информационных выходов коммутатора, каждая схема сравнения содержит группу К дешифраторов, где К вЂ” раз рядность сортируемых чисел, группу К-1 элементов И, группу К-1 элементов ИЛИ, выходной элемент ИЛИ и элемент НЕ, причем вход элемента НЕ соединен с выходом выходного элемента ИЛИ и является вторым выходом схемы сравнения, а выход— первым выходом схемы сравнения, входы

i-ro дешифратора, i = 1, К, соединены с i-ми входами первой и второй групп информационных входов коммутатора, первый и второй выходы J-го дешифратора, J= 2, К, соединены с входами (J-1)-го элемента ИЛИ группы, выход которого подключен к входам элементов И группы с первогопо)-1-й, третий выход i-го дешифратора i= 1, К-1, соединен с соответствующим входом l-го элемента И группы, выходы элементов И группы и третий выход К-го дешифратора

10 соединены с входами выходного элемента

ИЛИ.

На фиг. 1 приведена структурная схема устройства для сортировки двоичных чисел; на фиг. 2 — структурная схема блока управ15 ления; на фиг. 3 — структурная схема блока сортировки; на фиг. 4 — структурная схема коммутатора; на фиг, 5 — возможная структурная схема схемы сравнения; на фиг. 6 и

7 — иллюстрации упорядочения чисел (сортировки) для четного и нечетного m соответственноо.

Устройство для сортировки двоичных чисел содержит m групп по К входов, соединенных соответственно с информационными входами регистровой группы 21 — 2 и (соответственно входы 11 -11, ..., 1п -1П ).

Группы выходов регистров соединены с информационными входами первого блока 31

СартИрОВКИ. БЛОКИ СартИрОВКИ 31-3m СОЕдИ30 нены последовательно по информационным входам и. выходам, Устройство содержит также группу 4 элементов И, блок управления 5 и элемент ИЛИ 6. Каждый блок

35 3 имеет m групп по К входов соответственно

711 7mк. Выходы 811 SmK блока 4 являются выходами устройства. Вход 9 блока управления является входом записи устройства.

Выходы 101 — 10m блока 5 являются управля40 ющими выходами блока 5, и соединены с управляющими входами соответствующих блоков 3.

Блок 5 управления (см. фиг. 2) содержит триггер 11. генератор 12 тактовых импуль45 сов и распределитель 13 импульсов, Блок 3 сортировки (см. фиг. 3) содержит . группу 14 коммутаторов, элемент 15 ИЛИНЕ, элемент 16 И и элемент 17 задержки.

Каждый коммутатор 14 (см. фиг. 4) содержит четыре группы ключей 181-184, схему сравнения 19 и два регистра 201 и 202.

Первый выход 21 схемы сравнения соединен с управляющими входами групп 181 и

18а ключей, второй выход 22 схемы сравнения соединен с управляющими входами групп 18 и 18з ключей и является управляющим выходом коммутатора.

Каждая схема 19 сравнения (см, фиг, 5) содержит группу дешифраторов 231-23к, группу элементов ИЛИ 241-24к-1, группу

1783511

5 6 элементов 251-25к-1 И, выходной элемент старший). Вход управления записью не по26 ИЛИ и элемент 27 НЕ,, казан на чертежах.

Принцип работы устройства. сортиров- .. По входу 9 поступает сигнал запуска ки заключается в"следующем, Совокупность устройства. Этот сигнал устанавливает в двоичных чисел разбивается на пары и про- 5 единйчное состояние триггера 11 блока упизводится, сравнение чисел каждой пары равленйя 5, положительным сигналом с (например, при m — числе еортируемых чи- прямого выхода которого запускается гесел — четном). В результате сравнения в нератор 12. Этим же импульсом устанавликаждом блоке сортировки производится пе- вается в исходное"состояние (в младшем рекоммутация сравниваемыхчисел пары та- 10 разряде — едйница, в остальных — нули) ким образом, что большее число каждой распределитель 13, реализуемый, найрипары появляется на выходах блока сорти- мер, нарегиСтресдвига. Приэтомединичровки (соответствующего коммутатора) с н ы м з н а ч е н и е м сй гн а л а -в м л ад ш е м меньшим номером; На следующей ступени разряде распределителя 13 запускается (в следующем блоке сортировки) меньшее 15 работа первой ступени сортировки (блок число пары с меньшими номерами сравни- 31). Рассмотрим работу устройства сортивается с большим числом смежной пары с ровки для четного. большими номерами и также производится перекоммутация, Если на какой-либо ступе- . К моменту подачй импульса запуска на ни сравнения некоторые (например. край- 20 вход 9 в регистры 2 уже запйсаны двоичные ние) числа не имеют пары для сравнения, то " числа, они йрисутствуют"на входах 7 коммуони запоминаются и передаются сразу в" таторов 14 блока 3 сортировки первой стуследувщую ступень сравнения (в следую- пени, который (как и для всех нечетных щий блок сортировки). Таким образом, по. ступеней всоответствйиc фиг. 6) имеет m/k мере продви>кения чисел по блокам сорти- 25 коммутаторов 14. В каждом коммутаторе 14 ровки, соединенным последовательно, — соответствующими числа некоторой пары большие числа постепенно передвигаются подайы в вИДе сигналов на входы ключей на группы входов(выходов с меньшими но- групп 18 и схемы" 19; Так как

Э мерами, а меньшие числа — на группы вхо- схема сравнения 19-, комбинационное устдов) выходов с большими номерами. После 30 ройство, то на ее выходах 21 и 22 также к полной сортировки на первой группе выхо- моменту подачиимпульса на"вход9сформи- дов устройства наличествует. наибольшее " рованы соответСтвуюфие сигналы, и группы число, а на последней группе выходов — на- - ключей 18 скоммутированы соответствую- " именьшее число. При любом исходном рас-.. щим образом на входы регистров 20. Рас-. положении сортируемых чисел сортировка 35 смотрйм работу устройства 14. заканчивается не более, чем за m тактов, а: Коммутатор (см. фиг. 4) коммутирует . в ряде случаев — раньше. входние числа таким образом; что на выхоПриведенное описание иллюстрирует- дах первой группы (с меньшим индексом j) ся фиг. 6 и 7 (соответственно для четного 8 формируется число с большим значением, а и нечтетного 7 количества сортируемых чи- 40. на выходах с индексом J+1 — меньшее число. сел). На фиг, 6 и 7 приведены примеры с Это реализуется тем, что, схема 19 форминаименее благоприятными вариантами ис- рует разрешающий сигнал на выходе 21 в ходного расположения сортируемых чисел, случае, когда чиСло с мейьшим"Ийдексом (в что доказывает гарантированное заверше- дальйейшем — число А) больше или равно ние сортировки за m тактов. При этом на 4 числу с большим индексом (в дальнейшем— фиг. 6 и 7 пары чисел в квадратах — содер- числу Б). Если В > А, разрешающий сигнал жимое соответствующих выходов — первых формируется на выходе 22 и открывает груп(сверху) и вторых (снизу) коммутаторов. От- пу ключей 18г и 18з. обспечивая коммутадельные числа в крайних строках соответст-, цию входов 7> — 7к на входы регистра вуют числам, для которых на данной 20>, а входы 7> -7к>- на входы регистра 212. ступени нет пары; при этом данное число В противном случае (А В) осуществляется

50 сразупереводится(без изменения) вследу- обратная коммутация, Одна из модификающую ступень упорядочения, . ций устройства сравнения 19 приведена на

Устройство сортировки работает следу- фиг. 5. При этом. схема 19 реализует следующим образом. ющую функцию

Совокупность сортируемых чисел записывается параллельным кодом s регистры 2 (22) = Ак Вк (Ак Вк Ак Вк) X (по входам I, причем по входу 1i записыва ется младший разряд числа, а по входу1к — X АкчВк1 (Ак Вк Ак Вк) х

1783511

„(AK-iBK-1+AK- Вк.1). AK-g BK-2 г(Ак By, Ак BK) (Ак-IBK-1

М

+ ÀÈÂK-1) ° ... ° (А2 В2 А2 В2) А1 В1 где (22) — обозначение наличия разрешающего сигнала на выходе 22, Сигнал на выходе 21 является инверсным относительно. сигнала на выходе 22 схемы 10 сравнения. На входы каждого дешифратора

23 подаются одноименные разряды сравниваемых чйсел. Выходы 28 и 30 каждого дешифратора (положительные сигналы на них) соответствуют следующим соотношениям значений разрядов чисел: А= 1 и В= 1; А= О и В= О. Сигнал на выходе 29 соответствует соотношению А= О и В= 1. Таким образом (см. фиг. 5) числа анализируются, начиная со старших разрядов и в случае, когда при рав- 20 ных старших разрядах чисел А и В значение очередного разряда числа B больше соответствующего значения разряда числа А, выполняется условие В > А, Логическая функция, приведенная выше, реализуется эле- 25 ментами 25, 26 и 27.

При поступлении управляющего сиг-. нала по входу 10 осуществляется запись соответствующих чисел в регистры 20 первой ступени и с некоторой задержкой (за- 30 даваемой, элементом 17) формируется

„сигнал опроса блока 31. Регистры 20 реализованы таким образом, что лишь при наличии сигнала на их входах от соответствующего входа 10 обеспечивается фор- 35 мирование сигналов на их выходах — в противном случае регистры 20 отключены от выходной шины 7. Это обеспечивается, например, использованием регистров, включающих в свой состав элементы с тре- 40 мя состояниями (например. регистры типа

К 589 ИР 12), выходы которых при отсутствии управляющего сигнала находятся в высокоимпедансном состоянии. Таким образом, в первой ступени осуществляется попарная сортировка чисел.

Далее генератор 12 формирует тактовый импульс, который сдвигает единичный сигнал в следующий разряд распределителя

13; отключается блок сортировки первой ступени и включается в работу блок сорти. ровки второй ступени, который (соответственно фиг. 6, как и все блоки сортировки

m четных ступеней) содержит -1 коммута2 торов. Работа блока сортировки 3 второй ступени в остальном аналогична работе блока сортировки первой ступени.

С каждым тактовым импульсом производится сортировка чисел очередным блоком 3 сортировки аналогичным образом. По окончании упорядочения на выходах 711-71к устройства содержится наибольшее число, а на выходах 7m1 — 7 ПK — наименьшее число, то есть числа массива рассортированы по убыванию.

Процесс сортировки может закончиться ранее, чем за m тактов. Это происходит следующим образом. При срабатывании очередной ступени сортировки — кроме первой — анализируется факт срабатывания хотя бы одного коммутатора, то есть, его схемы сравнения 19- появления сигнала разрешения на ее выходе 22. Если на выходе 22 хотя бы одного из устройств 19 данной ступени формируется положительный сигнал, это означает, что сортировка не закончена. Если же ни одна схема 19 не формирует сигнал на выходе 22 — сортировка закончена, на входах элемента 15 ИЛИ-НЕ соответствующего блока 3 — "нули". на выходе "единица", которая проходит через открываемый сигналом с элемента 17 задержки элемент 16 И на вход элемента 6 ИЛИ, сигнал с выхода которого открывает элементы И 4 и выдает информацию на выход устройства, а также. сбрасывает триггер 11 блока управления 5, останавливая работу устройства. Сигналы сортированных чисел выдаются на выходы устройства до поступления следующего сигнала запуска на вход 9.

П ри нечетном количестве упорядочивэемых чисел для корректной работы устрой- ства следует подать ва первую группу входов код числа, заведомо большего, чем число сортируемого массива. либо Hà последнюю группу входов — код числа, заведомо меньшего, чем любое из чисел сортируемого массива. При этом процесс сортировки протекает аналогично, а из выходной информации соответственно исключается первая или последняя группа выходов. Если окончательное упорядочение чисел происходит лишь на последней ступени, сигнал на элемент ИЛИ 6 формируется с дополнительного выхода блока 5 (с гп+1-го разряда распределителя 13).

Таким образом. устройство позволяет осуществлять сортировку чисел, причем время сортировки зависит от исходного расположения чисел в сортируемом массиве, что позволяет в ряде случаев закончить сортировку раньше, чем через m тактов.

Формула изобретения

Устройство для сортировки двоичных чисел. содержащее m входных регистров, где m — количество сортируемых чисел, в групп элементов И и блок управления, со1783511

У 71 держащий триггер, генератор импульсов и распределитель импульсов, причем входы

РЕгистров являются информационными входами устройства, вход запуска устройства соединен с входом установки триггера 5 блока управления в единичное состояние, выход которого соединен с входом запуска генератора импульсов, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены элемент ИЛИ и m блоков 10 сортировки, каждый из которых содержит элемент ИЛИ-НЕ. элемент И, элемент задержки и группу узлов коммутации, каждый из которых содержит схему сравнения, два регистра и четыре группы ключей, причем 15

I-я группа информационных входов узла коммутации (I = 1, 2) соединена с информационными входами ключей I+2-й группы и с

i-й группой входов схемы сравнения, i-й вход которой соединен с управляющими 20 входами ключей i-й и 5- -й групп, выходы ключей 2I-1-й и 2i-й групп соединены с информационными входами i-ro регистра, выходы разрядов которого являются i-й группой информационных выходов узла 25 коммутации, в блоке сортировки информационные входы и выходы узлов коммутации являются соответствующими входами и выходами блока сортировки, вторые выходы схем сравнения всех узлов коммутации дан- 0 ного блока сортировки соединены с соответствующими входами элемента ИЛИ-НЕ, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом элемента задержки, выходы разрядов входных регистров соединены с соответствующими информационными входами первого блока сортировки, соответствующие информационные выходы первого блока сортировки, одноименные входы и выходы остальных блоков сортировки и первые входы элементов И соответствующих групп объединены, выходы элементов И групп являются выходами устройства, в блоке управления выход генератора импульсов соединен со счетным входом распределителя импульсов, вход установки в начальное . состояние которого соединен с входом запуска устройства, j-й выход которого (J = 1. 2, ...„m) соединен с входом элемента задержки

J-ro блока сортировки и входами считывания регистров всех узлов коммутации J-ro блока сортировки, m+ 1-й выход распределителя импульсов блока управления и выходы элементов И всех блоков сортировки. кроме первого, соединены с соответствующими входами элемента ИЛИ, выход которого соединен с вторыми входами элементов И всех групп и входом установки в нулевое состояние триггера блока управления.

1783511

° ° с

Ь11S ЮК и лг с

1783511

1783511

Составитель С.Кишенский

Редактор Г.Мельникова Техред М.Моргентал, Корректор С.Лисина

Заказ 4516 Тираж Подписное . ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", r, Ужгород, ул.Гагарина, 101