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

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

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

На чертеже представлена функциональная схема предлагаемого устройства.

Устройство содержит к блоков 1 сортировки, каждый из которых содержит группу регистров 2, счетчик 3, сдвиговый регистр 4, элементы 2И-ИЛИ 5, элемент И 6, триггер 7, элемент И 8, счетчик 9, схему 10 сравнения, элемент ИЛИ 11, коммутатор 12, мультиплексор 13, приемный регистр 14, регистр 15 результата, вход 16 начальной установки, тактовый вход 17, вход 18 разрешения работы, информационные входы 19, выходы 20.

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

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

Перед началом работы на вход 16 начальной установки поступает импульс, по которому все регистры 2, все триггеры 7 и счетчики 9 устанавливаются в нуль. Работа устройства начинается с приходом сигнала «Разрешение работы (потенциал логической «1) на вход 16 и первого числа из сортируемого массива на информационный вход 17.

Рассмотрим работу i-ro блока 1, сортировки, начиная с поступления разрешения (потенциал логической «1) на информационный вход триггера 7, которое передним фронтом i-ro тактового импульса записывается в триггер 7. Потенциал логической «1 на выходе триггера 7 разрешает поступление тактовых импульсов на вход счетчика 9, который работает по заднему фронту. Информация с выхода счетчика 7 поступает на установочный вход счетчика 3 и установочный вход сдвигового регистра 4 и устанавливает их в нуль (на выходе счетчика 9 потенциал логической «1) или разрешает их работу (на выходе счетчика 9 потенциал логического «О). Кроме того, информация с выхода счетчика 9 поступает

5

на вход элемента ИЛИ 11 и устанавливает на его выходе потенциал логической «1 (на выходе счетчика 9 потенциал логической «1) или разрешает (на выходе счетчика 9 потенциал логического «О) прохождение на выход данного элемента 11 информации с выхода схемы 10 сравнения. В случае, когда на выходе счетчика 9 потенциал логической «1, в регистры 14, 2 и 15 по заднему фронту тактовых импуль0 сов записывается первый упорядоченный список следующим образом: меньшее число - в первый регистр группы, самое большое - в регистр результата. В то же время, потенциал логической «1 на управляющем входе коммутатора 12 устанавливает данный коммутатор 12 в положение, когда на его выход поступает информация с выходов регистра результата. В момент, когда на выходе счетчика 9 устанавливается вместо потенциала логической «1 потенциал логичес0 кого «О на приемном регистре имеем самое большое число из второго упорядоченного списка, а на остальных регистрах - первый упорядоченный список.

Информация с выходов счетчика 3 поступает на управляющие входы мультиплек5 сора 13 и устанавливает его в положение, когда на его выход поступает Информация с выходов приемного регистра. На схеме сравнения происходит сравнение числа с выходов регистра результата с числом с выходов мультиплексора 13. В случае, если число с регистра результата больще числа с выходов мультиплексора 13, то выход схемы сравнения будет иметь потенциал логической «1, во всех других случаях - потенциал логического «О. Единица с выхода

схемы 10 сравнения, проходя через элемент ИЛИ 11, устанавливает коммутатор 12 на прохождение информации с выходов регистра результата, а также разрешает прохождение тактовых импульсов через элемент И 6 и элементы 2И-ИЛИ 5. Нуль на

выходе схемы 10 сравнения устанавливает коммутатор 12 в положение, когда на его выход поступает информация с выходов мультиплексора 13, а также блокирует прохождение тактовых импульсов через элемент И 6 и через вторую схему И элементов 2И- ИЛИ 5. Следующим задним фронтом тактового импульса в приемный регистр записывается второе число второго упорядоченного списка. В случае, когда на выходе схемы 10 сравнения имеем потенциал логиQ ческой «1, то тем же фронтом этого же импульса переписывается информация с предыдущих регистров в последующие регистры группы, в первый разряд сдвигового регистра 4 записывается единица, а содержимое счетчика 3 увеличивается на едини5 цу. Информация с выходов счетчика 3 управляет переключением мультиплексора 13 так, что при содержимом счетчика 3, равным нулю, на его выход поступает инфор0

мация с выходов приемного регистра, при содержимом счетчика 3, равным единице - информация с выходов первого регистра группы и т. д.

Информация с выходов сдвигового регистра поступает на первые входы соответствующих элементов 2И-ИЛИ 5 и разрешает (потенциал логической «1) или блокирует (потенциал логического «О) прохождение тактовых импульсов через первую схему И элементов 2И-ИЛИ 5.

На выходе коммутатора 12 получаем упорядоченный по убыванию список длиной 2 чисел, полученный из двух упорядоченных списков длиной чисел за время, равное 2 тактов.

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

Устройство для сортировки чисел, содержащее К блоков сортировки (K log2m где m - количество сортируемых чисел в массиве), каждый из которых содержит приемный регистр и регистр результата, схему сравнения и коммутатор, причем в каждом блоке сортировки выходы регистра результата соединены с первой группой входов схемы сравнения и первой группой информационных входов коммутатора, информационные входы устройства соединены с информационными входами приемного регистра первого блока сортировки, выходы коммутатора j-ro блока сортировки, где ,2, ..., (К-1), соединены с соответствующими информационными входами приемного регистра (j + 1) -го блока сортировки, вход начальной установки устройства подключен к входам установки в ноль приемных регистров всех блоков сор- тировки, тактовый вход устройства соединен с синхровходами приемных регистров всех блоков сортировки, отличающееся тем, что, с целью повыщения быстродействия, в каждый блок сортировки введены группа из ( - 1) регистров, ( - 1) элемен- тов 2И-ИЛИ, триггер, два счетчика, два элемента И, элемент ИЛИ, сдвиговый регистр и мультиплексор, причем тактовый вход устройства в каждом блоке сортировки соединен с синхровходом триггера, первыми входами элементов И, синхровходом приемного регистра, первыми и вторыми входами всех элементов 2И-ИЛИ, выходы которых подключены к синхровходам соответствующих регистров группы, прямой выход триггера подключен к второму входу первого элемента И, выход которого подключен к счетному входу первого счетчика, выход которого соединен с входами установки в ноль второго счетчика и сдвигового регистра и первым входом элемента ИЛИ, второй вход которого подключен к выходу схемы сравнения, а выход соединен с управляющим входом коммутатора, с третьими входами всех элементов 2И-ИЛИ и вторым входом второго элемента И, выход которого подключен к синхровходам регистра результата, сдвигового регистра и второго счетчика, выходы разрядов которого соединены с соответствующими управляющими входами мультиплексора, выходы которого подключены к второй группе входов схемы сравнения и второй группе информационных входов коммутатора, информационный вход первого разряда сдвигового регистра подключен к входу логической единицы устройства, выходы разрядов сдвигового регистра соединены с четвертыми входами соответствующих элементов 2И-ИЛИ, выход приемного регистра подключен к первой группе информационных входов мультиплексора и информационным входам первого регистра группы, выходы i-ro регистра группы, где ,2, ..., ( - 1), соединены с информационными входами (i + 1) -го регистра группы и (i + 1) - ой группы информационных входов мультиплексора, вход начальной установки устройства подключен к входам установки в ноль триггера и всех регистров группы, вХод- разрещения работы устройства соединен с информационным входом триггера первого блока сортировки, выход триггера j-ro блока сортировки соединен с информационным входом триггера (j + 1) -го блока сортировки, выходы коммутатора К-го блока сортировки являются информационными выходами устройства.

16 17 18

19

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации. Устройство содержит блоки сортировки, каждый из которых содержит группу регистров, счетчик, сдвиговый регистр, элемент 2И-ИЛИ, И, триггер, мультиплексор. Сортировка чисел в устройстве выполняется методом слияния, который заключается в получении упорядочения списка из двух упорядоченных списков меньшей длины. На первом этапе слияния исходный массив разбивается на пары таких списков, после чего путем сравнения каждой пары списков (и при необходимости их перестановки) формируется упорядоченный список. 1 ил. IND to со tsD tC IsD