Устройство для сортировки двоичных чисел Советский патент 1992 года по МПК G06F7/06 

Изобретение относится к вычислительной технике и может быть использовано в вычислительных процессорах при выполнении операций сравнения многоразрядных кодовых комбинаций с целью их упорядочения или в задачах экстремального управления.

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

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

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

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

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

со С

VI

со

GJ СЛ

регистров соединены с соответствующими информационными входами первого блока сортировки Управляющие входы блоков сортировки соединены с соответствующими выходами блока управления, управляющие выходы всех блоков сортировки кроме первого и дополнительный выход блока управления соединены с входами элемента ИЛИ, выход которого подключен к управляющим входам элементов И группы и к второму входу блока управления. Каждый блок сортировки содержит группу коммутаторов, элемент задержки, элемент И и элемент ИЛИ-НЕ, управляющий вход блока сортировки соединен с управляющими входами всех коммутаторов группы и через элемент задержки - с первым входом элемента И, второй вход и выход которого соединены соответственно с выходом элемента ИЛИ- НЕ и управляющим выходом блока сортировки Входы элемента ИЛИ соединены с управляющими выходами всех коммутаторов группы, каждый из которых содержит две группы информационных входов, две группы информационных выходов, четыре группы ключей, схему сравнения, и два регистра, причем первая группа информационных входов коммутатора соединена с гругГпами информационных входов первой и третьей групп ключей, и с первой группой входов схемы сравнения Вторая группа информационных входов коммутатора соединена с группами информационных входов второй и четвертой групп ключей и с второй группой входов схемы сравнения. Одноименные выходы ключей первой и второй групп объединены и подключены к информационным входам первого регистра, одно- именые выходы ключей третьей и четвертой групп объединены и подключены к информационным входам второго регистра, первый выход схемы сравнения соединен с управляющими входами первой и четвертой групп ключей, второй выход - с управляющими входами второй и третьей групп ключей и является управляющим выходом коммутатора. Выходы первого и второго регистров являются соответственно первой и второй группами информационных выходов коммутатора, каждая схема сравнения содержит группу К дешифраторов, где К - разрядность сортируемых чисел, группу К-1 элементов И, группу К-1 элементов ИЛИ, выходной элемент ИЛИ и элемент НЕ, причем вход элемента НЕ соединен с выходом выходного элемента ИЛИ и является вторым выходом схемы сравнения а выход - первым выходом схемы сравнения, входы 1-го дешифратора, i 1, К, соединены с 1-ми входами первой и второй групп информационных входов коммутатора, первый и второй выходы j-ro дешифратора, J 2, К, соединены с входами (j-l)-ro элемента ИЛИ группы, выход которого подключен к входам

элементов И группы с первого по J-1-й. третий выход i-ro дешифратора 1 1. К-1, соединен с соответствующим входом 1-го элемента И группы, выходы элементов И группы и третий выход К-ro дешифратора

соединены с входами выходного элемента ИЛИ.

Из фиг. 1 приведена структурная схема устройства для сортировки двоичных чисел; на фиг. 2 - структурная схема блока управления; на фиг. 3 - структурная схема блока сортировки; на фиг. А - структурная схема коммутатора; на фиг. 5 - возможная структурная схема схемы сравнения; на фиг. 6 и 7 - иллюстрации упорядочения чисел (сортировки)для четного и нечетного m соответственно.

Устройство для сортировки двоичных чисел содержит m групп по К входов, соединенных соответственно с информационными входами регистровой группы 2i-2m

(соответственно входы 1i1-1iIm1- ™)

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

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

3 имеет m групп по К входов соответственно 7ц-7тк. Выходы 8ц-8тк блока 4 являются выходами устройства. Вход 9 блока управления является входом записи устройства. Выходы 10i-10m блока 5 являются управляющими выходами блока 5, и соединены с управляющими входами соответствующих блоков 3.

Блок 5 управления (см. фиг. 2) содержит триггер 11, генератор 12 тактовых импульсов и распределитель 13 импульсов.

Блок 3 сортировки (см. фиг. 3) содержит группу 14 коммутаторов, элемент 15 ИЛИ- НЕ, элемент 16 И и элемент 17 задержки. Каждый коммутатор 14 (см. фиг. 4) содержит четыре группы ключей 18i-184. схему сравнения 19 и два регистра 20t и 202 Первый выход 21 схемы сравнения соединен с управляющими входами групп 18i и 1&j ключей, второй выход 22 схемы сравнения соединен с управляющими входами групп 182 и 18з ключей и является управляющим выходом коммутатора.

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

элементов 251 25к-1 И, выходной элемент 26 ИЛИ и элемент 27 НЕ.

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

Приведенное описание иллюстрируется фиг. 6 и 7 (соответственно для четного 8 и нечтетного 7 количества сортируемых чи- сел). На фиг. 6 и 7 приведены примеры с наименее благоприятными вариантами исходного расположения сортируемых чисел, что доказывает гарантированное завершение сортировки за m тактов При этом на фиг. 6 и 7 пары чисел в квадратах - содержимое соответствующих выходов - первых (сверху) и вторых (снизу) коммутаторов. Отдельные числа в крайних строках соответствуют числам, для которых на данной ступени нет пары; при этом данное число сразу переводится (без изменения) в следующую ступень упорядочения.

Устройство сортировки работает следующим образом.

Совокупность сортируемых чисел запм- сывается параллельным кодом в регистры 2 (по входам 1. причем по входу 1i записывается младший разряд числа а по входу 1к старший). Вход управления записью не показан на чертежах.

По входу 9 поступает сигнал запуска устройства. Этот сигнал устанавливает в единичное состояние триггера 11 блока управления 5, положительным сигналом с прямого выхода которого запускается генератор 12. Этим же импульсом устанавливается в исходноеьсостоян ие (в младшем разряде - единица, в остальных - нули) распределитель 13, реализуемый, например, на регистре сдвига. При этом единич- ным значением сигнала в младшем разряде распределителя 13 запускается работа первой ступени сортировки (блок 3i) Рассмотрим работу устройства сортировки для четного.

К моменту подачи импульса запуска на вход 9 в регистры 2 уже записаны двоичные числа, они присутствуют на входах 7 коммутаторов 14 блока 3 сортировки первой ступени, который (как и для всех нечетных ступеней в соответствии с фиг. 6) имеет m/S коммутаторов 14. В каждом коммутаторе 14 соответствующие числа некоторой пары поданы в виде сигналов на входы ключей групп 18 и схемы 19 сравнения. Так как схема сравнения 19 - комбинационное устройство, то на ее выходах 21 и 22 также к моменту подачи импульса на вход 9 сформированы соответствующие сигналы, и группы ключей 18 скоммутированы соответствующим образом на входы регистров 20. Рассмотрим работу устройства 14.

Коммутатор (см. фиг. 4) коммутирует входные числа таким образом, что на выходах первой группы (с меньшим индексом j) формируется число с большим значением, а на выходах с индексом J+1 - меньшее число Это реализуется тем, что, схема 19 формирует разрешающий сигнал на выходе 21 в случае, когда число с мён ииГим мндет сом (в дальнейшем - число А) больше или равно числу с большим индексом (в дальнейшем - числу В) Если В А, разрешающий сигнал формируется на выходе 22 и открывает группу ключей 18а и 18з, обспечивая коммутацию входов - на входы регистра 20i, а входы на входы регистра 21 а- В противном случае (А В) осуществляется обратная коммутация. Одна из модификаций устройства сравнения 19 приведена на фиг. 5. При этом схема 19 реализует следующую функцию

(22) Ак Вк(Ак-Вк Ак- В к) X ХАк-|Вк-1(Ак Вкх-Ак-Вк)

х(Ак|Вк-1 АК|Вк-1) Ак-1Вк-2

V(AK-BK AK BK) (AKIBK-IV

vAK-iB K-i)- ...-(А2 B2VA2 62) Av Bi5

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

При поступлении управляющего сигнала по входу 10 осуществляется запись соответствующих чисел в регистры 20 первой ступени и с некоторой задержкой (за- 30 даваемой элементом 17) формируется сигнал опроса блока 3i. Регистры 20 pea- ; лизованы таким образом, что лишь при наличии сигнала на их входах от соответствующего входа 10 обеспечивается фор- 35 мирование сигналов на их выходах - в противном случае регистры 20 отключены от выходной шины 7. Это обеспечивается, например, использованием регистров, включающих в свой состав элементы с тре- лл мя состояниями (например, регистры типа К 589 ИР 12), выходы которых при отсутствии управляющего сигнала находятся в высокоимпедансном состоянии Таким образом, в первой ступени осуществляется ,- попарная сортировка чисел.

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

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

С каждым тактовым импульсом производится сортировка чисел очередным блоком 3 сортировки аналогичным образом. По окончании упорядочения на выходах 7i 1-7ж устройства содержится наибольшее число, а на выходах 7mi-7mK - наименьшее число, то есть числа массива рассортированы по убыванию.

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

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

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

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

Устройство для сортировки двоичных чисел, содержащее m входных регистров, где m - количество сортируемых чисел, m групп элементов И и блок управления, содержащий триггер, генератор импульсов и распределитель импульсов, причем входы регистров являются информационными входами устройства, вход запуска устройства соединен с входом установки триггера блока управления в единичное состояние, выход которого соединен с входом запуска генератора импульсов, отличающееся тем, что, с целью повышения быстродействия, в него введены элемент ИЛИ и m блоков сортировки, каждый из которых содержит элемент ИЛИ-НЕ, элемент И, элемент задержки и группу узлов коммутации, каждый из которых содержит схему сравнения, два регистра и четыре группы ключей, причем 1-я группа информационных входов узла коммутации (1 1,2) соединена с информационными входами ключей i+2-й группы и с 1-й группой входов схемы сравнения, 1-й вход которой соединен с управляющими входами ключей 1-й и 5-Ьй групп, выходы ключей 2М-й и 21-й групп соединены с информационными входами 1-го регистра, выходы разрядов которого являются 1-й группой информационных выходов узла коммутации, в блоке сортировки информационные входы и выходы узлов коммутации являются соответствующими входами и выходами блока сортировки, вторые выходы схем сравнения всех узлов коммутации данного блока сортировки соединены с соответствующими входами элемента ИЛИ-НЕ, выход которого соединен с первым входом элемента И, второй вход которого соединен

с выходом элемента задержки, выходы разрядов входных регистров соединены с соответствующими информационными входами первого блока сортировки, соответствующие информационные выходы первого блока сортировки, одноименные входы и выходы остальных блоков сортировки и первые входы элементов И соответствующих групп объединены, выходы элементов И групп являются выходами устройства, в блоке управления выход генератора импульсов соединен со счетным входом распределителя импульсов, вход установки в начальное . состояние которого соединен с входом запу ска устройства, j-й выход которого 0 1.2,

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

состояние триггера блока управления.

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

Фиг.1

L

Ч

oo

8

7 tpcfZ