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

 

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

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

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

РЕСПУБЛИК (д) 4 G 06 F 7/08

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

Ф

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3703948/24-24 (22) 22.02.84 (46) 07.04.86. Бюл. № 13 (72) А. А. Мельник и И. Г. Цмоць (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 928342, кл. G 06 F 7/08, 1980.

Авторское свидетельство СССР № 1007099, кл. G 06 F 7/08,,1981. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в

„SU„„1223222 А специализированных устройствах обработки информации. Устройство содержит блоки сортировки, каждый из которых содержит группу регистров, счетчик, сдвиговый регистр, элемент 2И-ИЛИ, И, триггер, мультиплексор. Сортировка чисел в устройстве выполняется методом слияния, который заключается в получении упорядочения списка из двух упорядоченных списков меньшей длины.

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

1223222

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

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

Устройство содержит к блоков 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, получается упорядоченный список длиной 2 .

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

Перед началом работы на вход 16 начальной установки поступает импульс, по которому все регистры 2, все триггеры 7 и счетчики 9 устанавливаются в нуль. Работа устройства начинается с приходом сигнала

«Разрешение работы» (потенциал логической «!») на вход 16 и первого числа из сортируемого массива на информационный вход 17.

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

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

5 ! о !

25 зо

4О

55 на вход элемента ИЛИ 11 и устанавливает на его выходе потенциал логической «1» (на выходе счетчика 9 потенциал логической «1») или разрешает (на выходе счетчика 9 потенциал логического «О») прохождение на выход данного элемента 11 информации с выхода схемы 10 сравнения.

В случае, когда на выходе счетчика 9 потенциал логической «1», в регистры 14, 2 и 15 по заднему фронту тактовых импульсов записывается первый упорядоченный список следующим образом: меньшее число— в первый регистр группы, самое большое— в регистр результата. В то же время, потенциал логической «1» на управляющем входе коммутатора 12 устанавливает данный коммутатор 12 в положение, когда на

его выход поступает информация с выходов регистра результата. В момент, когда на выходе счетчика 9 устанавливается вместо потенциала логической «1» потенциал логического «О» на приемном регистре имеем самое большое число из второго упорядоченного списка, а на остальных регистрах— первый упорядоченный список.

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

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

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

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

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

t5

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

Устройство для сортировки чисел, содержащее К блоков сортировки (К= log m, где m — количество сортируемых чисел в 20 массиве), каждый из которых содержит приемный регистр и регистр результата, схему сравнения и коммутатор, причем в каждом блоке сортировки выходы регистра результата соединены с первой группой входов схемы сравнения и первой группой информационных входов коммутатора, информационные входы устройства соединены с информационными входами приемного регистра первого блока сортировки, выходы коммутатора j-го блока сортировки, где j = 1,2, ..., (К вЂ” 1), соединены

30 с соответствующими информационными входами приемного регистра (j+ 1) -го блока сортировки, вход начальной установки устройства подключен к входам установки в ноль приемных регистров всех блоков сор35 тировки, тактовыи вход устройства соединен с синхровходами приемных регистров всех блоков сортировки, отличающееся тем, что, с целью повышения быстродействия, в каждый блок сортировки введены группа из (2" — 1) регистров, (2" — 1) элемен- 40 тов 2И-ИЛИ, триггер, два счетчика, два элемента И, элемент ИЛИ, сдвиговый регистр и мультиплексор, причем тактовый вход устройства в каждом блоке сортировки соединен с синхровходом триггера, первыми входами элементов И, синхровходом приемного регистра, первыми и вторыми входами всех элементов 2И-ИЛИ, выходы которых подключены к синхровходам соответствующих регистров группы, прямой выход триггера подключен к второму входу первого элемента И, выход которого подключен к счетному входу первого счетчика, выход которого соединен с входами установки в ноль второго счетчика и сдвигового регистра и первым входом элемента ИЛИ, второй вход которого подключен к выходу схемы сравнения, а выход соединен с управляющим входом ком м утатора, с третьими входами всех элементов 2И вЂ” ИЛИ и вторым входом второго элемента И, выход которого подключен к синхровходам регистра результата, сдвигового регистра и второго счетчика, выходы разрядов которого соединены с соответствующими управляющими входами мультиплексора, выходы которого подключены к второй группе входов схемы сравнения и второй группе информационных входов коммутатора, информационный вход первого разряда сдвигового регистра подключен к входу логической единицы устройства, выходы разрядов сдвигового регистра соединены с четвертыми входами соответствующих элементов 2И-ИЛИ, выход приемного регистра подключен к первой группе информационных входов мультиплексора и информационным входам первого регистра группы, выходы i-го регистра группы, где i=1,2, (2 — 1), соединены с информационными входами (i+ 1) -ro регистра группы и (i+ 1)ой группы информационных входов мультиплексора, вход начальной установки устройства подключен к входам установки в ноль триггера и всех регистров группы, вХодразрешения работы устройства соединен с информационным входом триггера первого блока сортировки, выход триггера j-го блока сортировки соединен с информационным входом триггера (j+ 1) -го блока сортировки, выходы коммутатора К-го блока сортировки являются информационными выходами устройства.

l223222

18 f7 18

Составитель Е. Иванова

Редактор Г. Волкова Техред И. Верес Корректор М. Демчик

Заказ 1714/51 Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4 5

Филиал ППП «Патент», r. Ужгород, ул. Проектная, 4