Устройство пирамидальной сортировки чисел

Устройство пирамидальной сортировки чисел относится к автоматике и вычислительной технике и может быть использовано в составе вычислительных устройств и устройств обработки данных. Техническим результатом является сокращение аппаратных затрат на реализацию схемы за счет сокращения количества устройств сравнения чисел. Он достигается тем, что структура устройства состоит из (n-1) блоков выбора наибольшего/наименьшего числа, соединенных в виде пирамиды. Пирамидальное соединение содержит log ₂n (с округлением до большего целого) ярусов, где n - количество сортируемых чисел. При таком соединении верхний ярус (вершина пирамиды) устройства пирамидальной сортировки чисел содержит один блок 1 выбора наибольшего/наименьшего числа, нижний ярус состоит из (с округлением до меньшего целого) блоков 1 выбора наибольшего/наименьшего числа, где n - количество сортируемых чисел. Каждый блок выбора наибольшего/наименьшего числа состоит из устройства сравнения двух чисел, первого элемента ИЛИ, второго элемента ИЛИ, первого элемента И, второго элемента И, третьего элемента И, четвертого элемента И, третьего элемента ИЛИ, четвертого элемента ИЛИ, первого буферного элемента с высокоимпедансным состоянием по выходу и второго буферного элемента с высокоимпедансным состоянием по выходу.

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

Известно устройство для быстрой сортировки чисел (Шевкопляс Б.В. Микропроцессорные структуры. Инженерные решения. Справочник - 2-е изд. перераб. и доп. - М.: Радио и связь, 1990. - 512 с: ил., С.490-493), состоящее из арифметико-логических устройств, выполняющих сравнение чисел, мультиплексоров и постоянного управляющего устройства, ими управляющего.

Недостаток устройства состоит в том, что поскольку оно выполняет все возможные попарные сравнения чисел, то при увеличении количества чисел для сортировки, резко увеличиваются аппаратные затраты на реализацию устройства. Количество устройств сравнения в аналоге определяется по формуле:

Например, при сортировке четырех чисел требуется шесть устройств сравнения, при восьми - двадцать восемь, при шестнадцати - сто двадцать и так далее.

Техническая задача: сокращение аппаратных затрат на реализацию схемы.

Технический результат: сокращение аппаратных затрат на реализацию схемы за счет сокращения количества устройств сравнения чисел. Он достигается тем, что структура устройства реализуется в виде пирамиды, состоящей из блоков выбора наибольшего/наименьшего числа.

Предлагаемое устройство изображено на фиг.1. и фиг.2. На фиг.1 изображено устройство пирамидальной сортировки чисел, а на фиг.2 - структура блока выбора наибольшего/наименьшего числа.

Устройство пирамидальной сортировки чисел состоит из (n-1) блоков 1 выбора наибольшего/наименьшего числа, соединенных в виде пирамиды. Пирамидальное соединение содержит log₂n (с округлением до большего целого) ярусов, где n - количество сортируемых чисел. При таком соединении верхний ярус (вершина пирамиды) устройства пирамидальной сортировки чисел содержит один блок 1 выбора наибольшего/наименьшего числа, нижний ярус состоит из (с округлением до меньшего целого) блоков 1 выбора наибольшего/наименьшего числа, где n - количество сортируемых чисел. Причем выходом устройства пирамидальной сортировки чисел является выходная шина 16 максимального/минимального числа блока 1 выбора наибольшего/наименьшего числа, находящегося на верхнем ярусе (вершине) пирамиды. Через шину 13 подачи первого числа на первый вход блока 1 выбора наибольшего/наименьшего числа, находящегося на верхнем ярусе (вершине) пирамиды, подключается выходная шина 16 максимального/минимального числа одного блока 1 выбора наибольшего/наименьшего числа, находящегося на следующем, более низком ярусе пирамиды. Через шину 14 подачи второго числа на второй вход блока 1 выбора наибольшего/наименьшего числа, находящегося на верхнем ярусе (вершине) пирамиды, подключается выходная шина 16 максимального/минимального числа другого блока 1 выбора

наибольшего/наименьшего числа, также находящегося на следующем, более низком ярусе пирамиды и так далее, наращивая ярусы пирамиды и соответственно количество чисел для сортировки. Все линии 15 выбора режима сортировки по возрастанию/убыванию всех блоков 1 выбора наибольшего/наименьшего числа всех ярусов пирамиды, соединены между собой.

Каждый блок 1 выбора наибольшего/наименьшего числа (см. фиг.2) состоит из устройства 2 сравнения двух чисел, первого элемента ИЛИ 3, второго элемента ИЛИ 4, первого элемента И 5, второго элемента И 6, третьего элемента И 7, четвертого элемента И 8, третьего элемента ИЛИ 9, четвертого элемента ИЛИ 10, первого буферного элемента 11 с третьим (высокоимпедансным) состоянием по выходу и второго буферного элемента 12 с третьим (высокоимпедансным) состоянием по выходу. К входам 17 подачи первого числа устройства 2 сравнения двух чисел подключена шина 13 подачи первого числа. К входам 18 подачи второго числа устройства 2 сравнения двух чисел подключена шина 14 подачи второго числа. Выход 19 «первое число больше второго» устройства 2 сравнения двух чисел соединен с первым прямым входом 22 первого элемента ИЛИ 3. Выход 20 «первое число равно второму» устройства 2 сравнения двух чисел соединен со вторым прямым входом 23 первого элемента ИЛИ 3 и с первым прямым входом 25 второго элемента ИЛИ 4. Выход 21 «первое число меньше второго» устройства 2 сравнения двух чисел соединен со вторым прямым входом 26 второго элемента ИЛИ 4. Прямой выход 24 первого элемента ИЛИ 3 соединен с первым прямым входом 28 первого элемента И 5, первым инвертирующим входом 31 второго элемента И 6, первым инвертирующим входом 35 третьего элемента И 7 и первым прямым входом 39 четвертого элемента И 8. Прямой выход 27 второго элемента ИЛИ 4 соединен со вторым прямым входом 32 второго элемента И 6 и третьим прямым входом 37 третьего элемента И 7. Ко второму инвертирующему входу 29 первого элемента И 5, третьему прямому входу 33 второго элемента И 6, второму

инвертирующему входу 36 третьего элемента И 7, второму прямому входу 40 четвертого элемента И 8 подключена линия 15 выбора режима сортировки по возрастанию/убыванию. Прямой выход 30 первого элемента И 5 соединен с первым прямым входом 42 третьего элемента ИЛИ 9. Прямой выход 34 второго элемента И 6 соединен со вторым прямым входом 43 третьего элемента ИЛИ 9. Прямой выход 38 третьего элемента И 7 соединен с первым прямым входом 45 четвертого элемента ИЛИ 10. Прямой выход 41 четвертого элемента И 8 соединен со вторым прямым входом 46 четвертого элемента ИЛИ 10. Прямой выход 44 третьего элемента ИЛИ 9 соединен с входом 49 разрешения подключения первого буферного элемента 11 к выходной шине 16 максимального/минимального числа. Прямой выход 47 четвертого элемента ИЛИ 10 соединен с входом 51 разрешения подключения второго буферного элемента 12 к выходной шине 16 максимального/минимального числа. К входам 48 подачи первого числа первого буферного элемента 11 подключена шина 13 подачи первого числа. К входам 52 подачи второго числа второго буферного элемента 12 подключена шина 14 подачи второго числа. Выходы 50 первого числа первого буферного элемента 11 и выходы 53 второго числа второго буферного элемента 12 соединены с выходной шиной 16 максимального/минимального числа.

Устройство пирамидальной сортировки чисел имеет следующий алгоритм работы. Числа, предназначенные для сортировки, подаются на шины 13 подачи первого числа и 14 подачи второго числа соответствующих блоков 1 выбора наибольшего/наименьшего числа нижнего яруса пирамиды. В зависимости от режима работы устройства - сортировки по убыванию или возрастанию, на линию 15 выбора режима сортировки по возрастанию/убыванию подается либо уровень логического нуля, либо уровень логической единицы. Каждый блок 1 выбора наибольшего/наименьшего числа нижнего яруса пирамиды выбирает максимальное (в режиме сортировки по убыванию) или минимальное (в

режиме сортировки по возрастанию) из двух чисел, поданных на него по шинам 13 и 14 подачи первого и второго чисел и по выходной шине 16 максимального/минимального числа передает его на соответствующую шину 13 подачи первого числа или 14 подачи второго числа соответствующих блоков 1 выбора наибольшего/наименьшего числа следующего, более высокого яруса пирамиды. Процесс выбора максимальных или минимальных чисел блоками 1 выбора наибольшего/наименьшего числа устройства пирамидальной сортировки чисел будет продолжаться до момента, когда блок 1 выбора наибольшего/наименьшего числа верхнего яруса пирамиды произведет выбор максимального или минимального числа. Это число является первым отсортированным числом. Далее его следует исключить из процесса сортировки, подав, например, на соответствующую шину подачи числа блока 1 выбора наибольшего/наименьшего числа нижнего яруса пирамиды число, которое заведомо меньше наименьшего (для режима сортировки по убыванию, например, это может быть двоичное число, состоящее из нулей) или больше наибольшего (для режима сортировки по возрастанию это может быть двоичное число, состоящее из единиц) из чисел, предназначенных для сортировки. Далее, осуществляют аналогично процесс выбора следующего числа. Выполнение алгоритма следует продолжать, пока не будут отсортированы все числа, поданные на соответствующие шины подачи чисел блоков 1 выбора наибольшего/наименьшего числа нижнего яруса пирамиды.

При этом каждый блок 1 выбора наибольшего/наименьшего числа имеет следующий алгоритм работы. По шине 13 подачи первого числа на первый вход блока 1 выбора наибольшего/наименьшего числа и соответственно на его входы 17 подачи первого числа, подается первое число (в таблицах 1 и 2 оно обозначено как А), по шине 14 подачи второго числа на второй вход блока 1 выбора наибольшего/наименьшего числа и соответственно на его входы 18 подачи второго числа, подается второе число (в таблицах 1 и 2 оно обозначено как В). Одновременно первое число по

шине 13 подачи первого числа подается на входы 48 подачи первого числа первого буферного элемента 11, а второе число - по шине 14 подачи второго числа подается на входы 52 подачи второго числа второго буферного элемента 12.

Блок 1 выбора наибольшего/наименьшего числа, в зависимости от режима работы (сортировка по возрастанию или сортировка по убыванию), производит выбор одного из этих чисел - меньшего или большего, и подает его на выходы 50 первого числа первого буферного элемента 11 или выходы 53 второго числа второго буферного элемента 12 и выходную шину 16 максимального/минимального числа. Для этого устройство 2 сравнения двух чисел производит сравнение первого числа, находящегося на его входах 17 подачи первого числа и второго числа, установленного на входах 18 подачи второго числа и в зависимости от результата сравнения устанавливает на одном из выходов - выходе 19 «первое число больше второго», выходе 20 «первое число равно второму» или выходе 21 «первое число меньше второго» состояние логической единицы. Далее, в зависимости от режима работы блока 1 выбора наибольшего/наименьшего числа, который определяется состоянием линии 15 выбора режима сортировки по возрастанию/убыванию - уровень логического нуля на данной линии определяет режим сортировки по убыванию, а уровень логической единицы - режим сортировки по возрастанию и состояния входов и выходов первого элемента ИЛИ 3, второго элемента ИЛИ 4, первого элемента И 5, второго элемента И 6, третьего элемента И 7, четвертого элемента И 8, третьего элемента ИЛИ 9 и четвертого элемента ИЛИ 10, на одном из входов буферных элементов - входе 49 разрешения подключения первого буферного элемента 11 к выходной шине 16 максимального/минимального числа или входе 51 разрешения подключения второго буферного элемента 12 к выходной шине 16 максимального/минимального числа устанавливается уровень логической единицы, который подключает соответствующий буферный элемент к выходной шине 16 максимального/минимального числа.

Состояния всех входов и выходов блока 1 выбора наибольшего/наименьшего числа, которые определяют логику его работы, представлены в таблице 1 и таблице 2. В таблицах приняты следующие обозначения: 1 - уровень логической единицы; 0 - уровень логического нуля; А - на входах или выходах находится первое число; В - на входах или выходах находится второе число; Х - выходы находятся в высокоимпедансном состоянии (состоянии высокого выходного сопротивления) и отключены от выходной шины максимального/минимального числа.

Пусть, например, установлен режим работы сортировка по убыванию. Это означает, что каждым блоком 1 выбора наибольшего/наименьшего числа нижнего яруса устройства пирамидальной сортировки чисел, будет выбрано максимальное из двух чисел, поданных на соответствующие шины 13 подачи первого числа и шины 14 подачи второго числа, и передано с соответствующих выходных шин 16 максимального/минимального числа на соответствующие шины 13 подачи первого числа и шины 14 подачи второго числа блоков 1 выбора наибольшего/наименьшего числа следующего, более высокого яруса. Этот процесс выбора будет продолжаться, пока не будет выбрано первое максимальное число в блоке 1 выбора наибольшего/наименьшего числа верхнего яруса. Затем, после выбора первого максимального числа, его необходимо исключить из дальнейшей сортировки, и продолжать процесс выбора. Следующее число будет меньше максимального, выбранного на предыдущем шаге и т.д. Процесс выбора следует продолжать, пока не будут отсортированы в убывающем порядке все числа.

При этом каждый блок 1 выбора наибольшего/наименьшего числа имеет следующий алгоритм работы в режиме сортировки по убыванию. Пусть первое число больше второго (в соответствие с таблицами 1 и 2 - число А больше числа В). Первое число (число А) подается на входы 17 подачи первого числа устройства 2 сравнения двух чисел, второе число

(число В) - на входы 18 подачи второго числа устройства 2 сравнения двух чисел. На выходе 19 «первое число больше второго» устройства 2 сравнения двух чисел установится уровень логической единицы, а на выходах 20 «первое число равно второму» и 21 «первое число меньше второго» устройства 2 сравнения двух чисел - уровень логического нуля. Такое состояние выходов устройства 2 сравнения двух чисел соответствует первой строке таблицы 1 и таблицы 2. То есть на первом прямом входе 22 первого элемента ИЛИ 3 установится уровень логической единицы, на втором прямом входе 23 первого элемента ИЛИ 3 - уровень логического нуля, на прямом выходе 24 первого элемента ИЛИ 3 - уровень логической единицы. На первом прямом входе 25 второго элемента ИЛИ 4 установится уровень логического нуля, на втором прямом входе 26 второго элемента ИЛИ 4 - уровень логического нуля, на его прямом выходе 27 - уровень логического нуля. На первом прямом входе 28 первого элемента И 5 установится уровень логической единицы, на втором инвертирующем входе 29 первого элемента И 5 - уровень логического нуля, на прямом выходе 30 первого элемента И 5 - уровень логической единицы. На первом инвертирующем входе 31 второго элемента И 6 установится уровень логической единицы, на втором прямом входе 32 второго элемента И 6 - уровень логического нуля, на третьем прямом входе 33 второго элемента И 6 - уровень логического нуля, на прямом выходе 34 второго элемента И 6 - уровень логического нуля. На первом инвертирующем входе 35 третьего элемента И 7 установится уровень логической единицы, на втором инвертирующем входе 36 третьего элемента И 7 - уровень логического нуля, на третьем прямом входе 37 третьего элемента И 7 - уровень логического нуля, на прямом выходе 38 третьего элемента И 7 - уровень логического нуля. На первом прямом входе 39 четвертого элемента И 8 установится уровень логической единицы, на втором прямом входе 40 четвертого элемента И 8 - уровень логического нуля, на прямом выходе 41 четвертого элемента И 8 - уровень логического нуля. На первом прямом входе 42 третьего элемента ИЛИ 9 установится

уровень логической единицы, на втором прямом входе 43 третьего элемента ИЛИ 9 - уровень логического нуля, на прямом выходе 44 третьего элемента ИЛИ 9 - уровень логической единицы. На первом прямом входе 45 четвертого элемента ИЛИ 10 установится уровень логического нуля, на втором прямом входе 46 четвертого элемента ИЛИ 10 - уровень логического нуля, на прямом выходе 47 четвертого элемента ИЛИ 10 - уровень логического нуля. С прямого выхода 44 третьего элемента ИЛИ 9 уровень логической единицы подается на соединенный с ним вход 49 разрешения подключения первого буферного элемента 11 к выходной шине 16 максимального/минимального числа и разрешает передачу первого числа (числа А) с входов 48 подачи первого числа первого буферного элемента 11 на его выходы 50 и выходную шину 16 максимального/минимального числа. В то же время, с прямого выхода 47 четвертого элемента ИЛИ 10 уровень логического нуля подается на соединенный с ним вход 51 разрешения подключения второго буферного элемента 12 к выходной шине 16 максимального/минимального числа и переводит его выходы 53 в высокоимпедансное состояние, отключая их от шины 16 максимального/минимального числа и не позволяя второму числу (числу В) установиться на ней. Так каждым блоком 1 выбора наибольшего/наименьшего числа производится выбор максимального числа в режиме сортировки по убыванию. Остальные варианты состояний входов и выходов элементов для соотношений двух чисел (когда первое число равно второму А=В, второе число больше первого В>А) в режиме сортировки по убыванию представлены во второй и третьей строках таблицы 1 и таблицы 2.

Если установлен режим работы сортировки по возрастанию, то каждым блоком 1 выбора наибольшего/наименьшего числа нижнего яруса устройства пирамидальной сортировки чисел, будет выбрано минимальное из двух чисел, поданных на соответствующие шины 13 подачи первого числа и шины 14 подачи второго числа, и передано с соответствующих выходных шин 16 максимального/минимального числа на соответствующие шины 13 подачи

первого числа и шины 14 подачи второго числа блоков 1 выбора наибольшего/наименьшего числа следующего, более высокого яруса. Этот процесс выбора будет продолжаться, пока не будет выбрано первое минимальное число в блоке 1 выбора наибольшего/наименьшего числа верхнего яруса. Затем, после выбора первого минимального числа, его необходимо исключить из дальнейшей сортировки, и продолжать процесс выбора. Следующее число будет больше минимального, выбранного на предыдущем шаге и т.д. Процесс выбора следует продолжать, пока не будут отсортированы в возрастающем порядке все числа. Состояния всех входов и выходов элементов блока 1 выбора наибольшего/наименьшего числа для соотношений двух чисел в режиме сортировки по возрастанию представлены в четвертой, пятой и шестой строках таблицы 1 и таблицы 2.

При реализации предлагаемого устройства пирамидальной сортировки чисел для 4 чисел потребуется 3 устройства сравнения двух чисел, в то время как для реализации аналога потребуется 6 устройств сравнения двух чисел, при реализации предлагаемого устройства для 8 чисел потребуется 7 устройств сравнения двух чисел, в то время как для реализации аналога потребуется 28 устройств сравнения двух чисел. Таким образом, предлагаемое устройство обеспечивает сокращение аппаратных затрат на реализацию схемы по сравнению с аналогом, за счет сокращения количества устройств сравнения чисел.

УСТРОЙСТВО ПИРАМИДАЛЬНОЙ СОРТИРОВКИ ЧИСЕЛ

1 - уровень логической единицы;

0 - уровень логического нуля;

А - на входах или выходах находится первое число;

В - на входах или выходах находится второе число;

Х - выходы находятся в высокоимпедансном состоянии (состоянии высокого выходного сопротивления) и отключены от выходной шины максимального/минимального числа.

УСТРОЙСТВО ПИРАМИДАЛЬНОЙ СОРТИРОВКИ ЧИСЕЛ

1 - уровень логической единицы;

0 - уровень логического нуля;

А - на входах или выходах находится первое число;

В - на входах или выходах находится второе число;

Х - выходы находятся в высокоимпедансном состоянии (состоянии высокого выходного сопротивления) и отключены от выходной шины максимального/минимального числа.

Устройство пирамидальной сортировки чисел, состоящее из n-1 блоков выбора наибольшего/наименьшего числа, соединенных в виде пирамиды, которая содержит log₂n с округлением до большего целого ярусов, верхний ярус содержит один блок выбора наибольшего/наименьшего числа, нижний ярус состоит из с округлением до меньшего целого блоков выбора наибольшего/наименьшего числа, где n - количество сортируемых чисел, причем выходом устройства является выходная шина максимального/минимального числа блока выбора наибольшего/наименьшего числа, находящегося на верхнем ярусе пирамиды, через шину подачи первого числа на первый вход блока выбора наибольшего/наименьшего числа, находящегося на верхнем ярусе пирамиды, подключается выходная шина максимального/минимального числа одного блока выбора наибольшего/наименьшего числа, находящегося на следующем, более низком ярусе пирамиды, через шину подачи второго числа на второй вход блока выбора наибольшего/наименьшего числа, находящегося на верхнем ярусе пирамиды, подключается выходная шина максимального/минимального числа другого блока выбора наибольшего/наименьшего числа, также находящегося на следующем, более низком ярусе пирамиды, причем все линии выбора режима сортировки по возрастанию/убыванию всех блоков выбора наибольшего/наименьшего числа всех ярусов пирамиды соединены между собой, каждый блок выбора наибольшего/наименьшего числа состоит из устройства сравнения двух чисел, первого элемента ИЛИ, второго элемента ИЛИ, первого элемента И, второго элемента И, третьего элемента И, четвертого элемента И, третьего элемента ИЛИ, четвертого элемента ИЛИ, первого буферного элемента с высокоимпедансным состоянием по выходу и второго буферного элемента с высокоимпедансным состоянием по выходу, к входам подачи первого числа устройства сравнения двух чисел подключена шина подачи первого числа, к входам подачи второго числа устройства сравнения двух чисел подключена шина подачи второго числа, выход «первое число больше второго» устройства сравнения двух чисел соединен с первым прямым входом первого элемента ИЛИ, выход «первое число равно второму» устройства сравнения двух чисел соединен со вторым прямым входом первого элемента ИЛИ и с первым прямым входом второго элемента ИЛИ, выход «первое число меньше второго» устройства сравнения двух чисел соединен со вторым прямым входом второго элемента ИЛИ, прямой выход первого элемента ИЛИ соединен с первым прямым входом первого элемента И, первым инвертирующим входом второго элемента И, первым инвертирующим входом третьего элемента И и первым прямым входом четвертого элемента И, прямой выход второго элемента ИЛИ соединен со вторым прямым входом второго элемента И и третьим прямым входом третьего элемента И, ко второму инвертирующему входу первого элемента И, третьему прямому входу второго элемента И, второму инвертирующему входу третьего элемента И, второму прямому входу четвертого элемента И подключена линия выбора режима сортировки по возрастанию/убыванию, прямой выход первого элемента И соединен с первым прямым входом третьего элемента ИЛИ, прямой выход второго элемента И соединен со вторым прямым входом третьего элемента ИЛИ, прямой выход третьего элемента И соединен с первым прямым входом четвертого элемента ИЛИ, прямой выход четвертого элемента И соединен со вторым прямым входом четвертого элемента ИЛИ, прямой выход третьего элемента ИЛИ соединен с входом разрешения подключения первого буферного элемента к выходной шине максимального/минимального числа, прямой выход четвертого элемента ИЛИ соединен с входом разрешения подключения второго буферного элемента к выходной шине максимального/минимального числа, к входам подачи первого числа первого буферного элемента подключена шина подачи первого числа, к входам подачи второго числа второго буферного элемента подключена шина подачи второго числа, выходы первого числа первого буферного элемента и выходы второго числа второго буферного элемента соединены с выходной шиной максимального/минимального числа.