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

/08 ПИСАНИЕ ИЗОБРЕТЕНИЯ СКОМУ СВИДЕТЕЛЬСТ, Зыков, С.А. Удинк автоматике и ь изобретения - Устройство соимального чис 4 г Ь 7 ь ОСУДАРСТВЕННЫЙ КОМИТЕТ О ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетельство СССРВ 1179317, кл. 6 06 Г 7/08, 1985.Авторское свидетельство СССРМ 1474639, кл, 0 06 Р 7/08, 1987.(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИСЕЛ(57) Изобретение относитсявычислительной технике, Целповышение быстродействия.держит блок выделения мин Ы 1725215 А 1 ла(БВМЧ) 1, регистр исключения отсортированных чисел (РИОС) 2, блоки определения числа единиц в двоичном коде (БОЧЕ) 3, 4, блок памяти (БП) 5, выходные регистры 6 отсортированных чисел, элементы ИЛИ 7, Среди исходных чисел БВМЧ 1 определяет и отмечает минимальное число (числа). БОЧ Е 4 и 3 определяют соответственно, сколько минимальных чисел выделено БВМЧ - С 1 и сколько их уже было отсортировано(сколько единиц записано в РИОС 2) - С 1, Полученные коды поступают на адресные входы БП 5, который формирует маску типа "Окно", содержащую единицы в остальных разрядах. Выделенное минимальное число записывается в отмеченные выходные регистры 6. 1 табл 2 ил.Изобретение относится к вычислительной технике и может быть использовано вмашинах баз данных и системах поиска информации.Известны устройства для сортировки 5чисел, содержащие дешифраторы, группыэлементов ИЛИ, узлы анализа и шифраторы. В основу работы данных устройств положен алгоритм последовательногосокращения множества сортируемых чисел 10исключением из него на каждом очередномшаге наименьшего числа.Недостатком устройств является их непригодность для сортировки чисел большойразрядности. Указанный недостаток обусловлен использованием в устройствахпринципа двойного преобразования кодовчисел - позиционных в распределительные,а распределительных - в позиционные. Сростом разрядности сортируемых чисел 20резко увеличиваются аппаратурные затраты на дешифрацию-шифрацию их кодов, чтозатрудняет практическую реализацию устройств.Известно также устройство для сортировки чисел, содержащее формирователиимпульсов, группу элементов ИЛИ, регистрисключения отсортированных чисел и блокопределения числа единиц.Недостатком устройства является его 30низкое быстродействие, обусловленное затратами нескольких тактов на выделение ивыдачу каждого отсортированного числа.Наиболее близким по технической сущности к предлагаемому является устройство 35для сортировки и чисел, содержащее блоквыделения наименьшего числа, п входныхсумматоров, выходной сумматор, регистрисключения отсортированных чисел, блокопределения числа единиц, счетчик, формирователи импулсов, элементы И, ИЛИ - НЕ игруппу элементов ИЛИ.Недостатком известного устройства является его низкое быстродействие, обусловленное разнесением во времени процесса 45поочередного выделения наименьших чисел и процесса формирования результирующего массива. Обработка исходногонеупорядоченного массива, содержащегосреди п своих элементов Н попарно различных чисел, выполняется (устройством) за(Н+ и) тактов, из которых Н тактов затрачивается на собственную сортировку, а и тактов - на формирование и поэлементнуювыдачу результирующего массива. 55Цель изобретения - повышение быстродействия устройства за счет совмещения вовремени процессов выделения наименьшихчисел и формирования из них упорядоченного массива,Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее блок выделения минимального числа, регистр исключения чисел, первый блок определения числа единиц и группу элементов ИЛИ, причем входы 1-го числа устройства (1 = 1, 2п; и - количество сортируемых чисел) соединены соответственно с информационными входами 1-й группы блока выделения минимального числа, прямые выходы разрядов регистра исключения чисел - с входами первого блока определения числа единиц, введены второй блок определения числа единиц, блок памяти и п выходных регистров, причем инверсный выход 1-го разряда регистра исключения чисел соединен с 1-м разрешающим входом блока выделения минимального числа, 1-й адресный выход которого соединен с входом установки 1-го разряда регистра исключения чисел в единичное состояние, 1-м входом второго блока определения числа единиц и первым входом 1-го элемента ИЛИ группы, второй вход которого подключен к прямому выходу 1-го разряда ре; гистра исключения чисел, вход установки в нулевое состояние которого является входом начальной установки устройства, информационные выходы блока выделения минимального числа соединены с информационными входами всех выходных регистров, выходы первого и второго блоков определения числа единиц - с адресными входами блока памяти, 1-й выход которого соединен с входом разрешения записи 1-го выходного регистра, выходы разрядов которого являются информационными выходами 1-.й группы устройства, тактовый вход устройства соединен с тактовыми входами всех регистров, выходы всех элементов ИЛИ группы объединены монтажным И и являются выходом окончания работы устройства.На фиг.1 представлена схема устройства; на фиг.2 - вариант схемы блока выделения минимального числа.Устройство содержит (фиг.1) блок 1 выделения минимального числа, регистр 2 исключения отсортированных чисел, первый 3 и второй 4 блоки определения числа единиц в двоичном коде, блок 5 памяти, и выходных регистров 6 отсортированных чисел (и - размер обрабатываемых числовых массивов), группу из и двухвходовых элементов ИЛИ 7, информационные входы сортируемых чисел А 1, А 2, , Ап, вход "НУ" начальной установки устройства, информационные выходы отсортированных чисел В 1ВгВо, выход а окончания работы устройства.Блок 1 выделения минимального числа (фиг,2) содержит прямоугольную матрицу иэ и х К ячеек анализа, где М - разрядность сортируемых чисел. Каждая ячейка 1 и, где= Гй, 1= Ц, имеет вход разрешения Ри, выход разрешения Рн, информационный вход аи и информационный выход. Ячейки анализа, образующие отдельную строку матрицу, соединены последовательно по входам и выходам разрешения. Входы разрешения ячеек 11, 121,".,1 1 первого столбца являются разрешающими входами блока 1, Выходы разрешения ячеек 1 а, 2 ь,.1последнего столбца являются адресными выходами блока 1. Информационные входы ячеек 1-й строки образуют информационные входы сортируемого числа А = а 1 аааа. Информационные выходы ячеек объединены по столбцам и образуют информационные выходы Ь 1, Ь 2 Ь блока 1.Ячейкаи анализа состоит из повторителя 8, элемента 9 равнозначности и элемента 10 импликации.Элементы 7-10 выполняются по схеме, обеспечивающей реализацию функции МОНТАЖНОЕ И в точках соединения выходов.В основу работы устройства положен алгоритм последовательного сокращения множества сортируемых чисел. Алгоритм включает Н шагов, где Н - количество попарно различных чисел в исходном массиве. При этом на каждом и-М шаге из текущего множества еще не отсортированных чисел исключается группа из С (ь) одинаковых наименьших чисел.Устройство работает следующим образом.Сортируемые числа, образующие неупорядоченный массив, подаются через входы А 1, А 2.Ап устройства в блок 1 выбора минимального числа. Одновременно на вход "НУ" устройства подается сигнал начальной установки, по которому производится асинхронное обнуление всех разрядов регистра 2. С инверсных выходов регистра 2 на соответствующие входы блока 1 поступают единичные сигналы Р 1, Р 2, , Рп, разрешающие анализ в блоке 1 всех и сортируемых чисел.В блоке 1 среди чисел А 1, А 2Ап отыскивается минимальное число В(1) = мин (А 1, А 2, , Ап). Код этого числа передается с информационных выходов блока 1 на информационные входы всех регистров 6. На адресных выходах блока 1 формируется набор сигналов ч 1, ч 2, . чп, в котором единичными значениями отмечаются позиции выделенного числа В в исходном массиве.10 Сформированный набор сигналов чь, ч 2, , ч поступает на входы установки в "1" разрядов регистра 2 и на входы блока 4.Блоком 4 определяется количество единичных сигналов в наборе ч 1, ч 2, ., чп. Получаемый при этом на выходах блока 4 код С р) = с 1 с 2 с я, где ц =,1 о 92(и+1)(, показывает, сколько наименьших чисел, равных В(1), содержится в исходном массиве. Одновременно блоком 3 подсчитывается количество единиц, находящихся в разрядахрегистра 2. Код С = с 1 сгся = 0; формируемый на выходах блока 3, показывает,сколько чисел исходного массива уже отсор 15 тировано,Коды С (1) и С с выходов блоков 4 и 3поступают на адресные входы блока 5 памяти. Блок 5 формирует и-разрядную маскутипа "окно", содержащую серию из С(1) еди 20 ниц в разрядах с (С(1)+1)-го по(С(1) +С (1)-й инули в остальных разрядах,Блок 5 может быть выполнен в виде ПЗУемкостью 4 ч и-разрядных слов, Пример"прошивки" ПЗУ для случая и = 4 приведен25 в таблице. Ячейки ПЗУ, адреса которых втаблице не указаны, могут содержать п роизвольную информацию.С выходов блока 5 разряды сформированной маски поступают на входы разреше 30 ния записи регистров 6. При этом 1-й разрядмаски подается на вход разрешения записирегистра 6 и разрешает либо запрещаетприем информации этот регистр с информационных выходов блока 1.35 По очередному синхроимпульсу (цеписинхронизации на фиг.1 не показаны) коднаименьшего числа В, выделенного блоком 1, принимается в регистры 61 - 6 С,разблокированные по записи единичными40 разрядами маски, Содержимое остальныхрегистров 6 с 1+1, - 6 п не меняется. Одновременно набором сигналов ч, ч 2,"чп,поступающих с адресных выходов блока 1,устанавливаются в "1" разряды регистра 2,соответствующие позициям выделенногочисла В в исходном массиве. Тем самымэти числа исключаются из дальнейшегорассмотрения в блоке 1, поскольку количество нулевых сигналов на разрешающихвходах Р 1, Р 2,РП блока 1 возрастает навеличину С . В результате текущее множество сортируемых чисел сокращается за1счет исключения из него С (1) одинаковыхнаименьших чисел,В очередном такте работа устройстваповторяется аналогичным образом. Приэтом на выходах блоков 4 и 3 формируютсякоды С(2) и С(2) = С(1) + С(1) = С(1)соответственно, а на выходах блока 5 обра10 15 20 25 30 35 40 45 50 55зуется маска с "окном" шириной в С (2) разрядов и левой границей, равной С(2) + 1. При этом Очередное число В(2)В(1), выделенное блоком 1, принимается на регистры бс 1+1 - бс 1 +с 2, а в регистре 2 дополнительно устанавливаются в единичное состояние С (2) разрядов, соответствующих позициям числа Вр) в исходном массиве.Таким образом, в каждом 11-м такте работы устройства текущее множество сортируемых чисел сокращается исключением из него С(ь) одинаковых наименьших чисел, а текущее множество уже отсортированных чисел пополняется этими числами, формируемое блоком 5 "окно" смещается от такта к такту вправо. Единичные сигналы, снимаемые с прямых выходов регистра 2, отмечают позиции уже отсортированых чисел, а единичные сигналы на инверсных выходах регистра 2 - позиции еще не отсортированных чисел в исходном массиве. Отсортированные к концу 11-го такта числа В 1В 2Вс(п) находятся в регистрах 61 - бс(н,Сортировка исходного массива заканчивается в Н-м такте, где НС(1, 2, ,и) - количеству попарно различных чисел среди А 1, А 2, ,Ап. В этом такте на выходах блоков 4 и 3 формируются величины С(н) и С(н), причем С (н) + С(н) = п. Одновренно на выходах всех элементов ИЛИ 71 - 7 л появляются единичные сигналы, что приводит к выработке единичного признака а, свидетельствующего Об окончании процесса сортировки. К концу Н-го такта по очередномусинхроимпульсу последнее из Н чисел, выделенных блоком 1, принимается в регистры бои)+1 - бл, В следующем такте на входы А 1, А 2;, Ап устройства можно подавать очередной массив сортируемых чисел,Блок 1 выделения минимального числа работает следующим образом.На горизонтальные ряды ячеек анализа 111 11 ь 121 12 ь , 1 п 1 пав подаются двоичные коды сортируемых чисел А 1, А 2, , Ап так, что ац соответствует старшему, аа - младшему разряду 1-го числа. Из всех и входных кодов анализируются только те, для которых на разрешающих входах блока 1 присутствуют сигналы логической "1",В блоке 1 использован алгоритм поразрядного сравнения чисел.Если число А не участвует в сравнении, то на разрешающем входе Р блока 1 присутствует сигнал логического "0", Данный сигнал распространяется через повторители 8 всех ячеек анализа 1-й строки и появляется на выходе блока 1 в виде нулевого сигнала исключения чь В каждой ячейке анализа 1-й строки нулевой сигнал разрешения Ри поступает на второй вход элемента 10 импликации, создавая условия для появления на выходе этого элемента сигнала Логической "1" (Рп-а = 0 только при аи = 0 иРи = 1). Таким образом, исключение числа А из анализа в блоке 1 равносильно его замене максимальным числом, содержащим единицы во всех разрядах.Если хотя бы одно из участвующих в сравнении чисел содержит "0" в старшем разряде, то этот "0" передается на выход элемента 10 импликации и появляется на информационном выходе Ь 1 блока 1, поскольку выходы всех элементов 10 первого столбца соединены по схеме МОНТАЖНОЕ И,Если участвующее в сравнении число А; содержит единицу в старшем разряде (ац = =1), а на выходе Ь 1 блока 1 сформирован сигнал логического "0" (Ь 1 = 0), то это означает, что А не является минимальным среди анализируемых чисел. В таком случае на выходе элемента 9 равнозначности ячейки )ц появляется сигнал логического "0" (ацЭЬ 1= ФИ= 0), который распространяется через повторители 8 ячеек 2 - 1 а и появляется на 1-м адресном выходе блока 1 в виде нулевого сигнала ч 1, Появление сигнала логического "0" на входах разрешения ячеек 12 в1 а создает условия для получения на выходах элементов 10 импликации этих ячеек сигналов логической "1". Тем самым число 4; исключается из дальнейшего анализа по оставшимся младшим разрядам.Если все участвующие в сравнении числа содержат единицу в старшем разряде, то на информационном выходе Ь 1 блока 1 появляется сигнал логической "1". В этом случае сравнение чисел продолжается по оставшимся младшим разрядам. При этом в ячейках 112 - 11 к, 122 - 121, 1 п 2 - пав анализа протекают процессы, аналогичные рассмотренному,Таким образом, выделение минимального числа блоком 1 происходит в результате распространения сигналов по строкам ячеек анализа слева направо. Значения разрядов выделенного числа появляются на информационных выходах Ь 1,Ь 2,.,Ь блока 1, а позиции выделенного числа, занимаемые им е исходном массиве, отмечаются сигналами логической "1" на соответствующих адресных выходах ч 1, ч 2,чп блока 1. В качестве базового объекта выбрано устройство (4) для сортировки чисел - прототип заявляемого изобретения.Существенным техническим преимуществом заявляемого устройства перед базовым объектом является более высокое(2) Тз = Г 1, + гЗ + г 5 + т 6,ти; 55 быстродействие. Указанное преимущество достигается. исключением из исходного массива группы одинаковых наименьших чисел на каждом шаге сортировки. Действительно, сортировка исходного массива, содержащего 5 Н попарно различных чисел, выполняется ба- зовым объектом за(Н+п) тактов. Заявляемое устройство осуществляет сортировку такого же массива за Н тактов, обеспечивая повышение быстродействия в(Н+и)/Н =(1+и/Н) 10 раз. Максимальный выигрыш в быстродействии в (и+1) раз достигается в том случае, когда исходный массив состоит из п одинаковых чисел. В этом случае сортировка массива базовым объектом занимает (и+1) 15 тактов, а заявляемым устройством -такт. Минимальный выигрыш (в 2 раза) имеет место, когда исходный массив не содержит одинаковых чисел. В этом случае сортировка массива базовым объектом требует 2 п тактов, 20 а заявляемым устройством - п тактов.Сравнение базового объекта и заявляемого устройства по длительности такта работы показывает следующее.Длительность такта работы базового 25 объекта составляет Т т 5 + Т 1 + 710 + т 15 + т 16, (1)где гЪ - время срабатывания блока выделе ния минимального числа;г 1 - время суммирования двух к-разрядных кодов на сумматоре;Тю - время приема информации в регистр; 35т 16- время срабатывания блока определения числа единиц;ы - время приема информации в счетчик,Для заявляемого устройства длительность 40 такта работы определяется выражением где т 1 - время срабатывания блока 1 выделения минимального числа;тз - время срабатывания блока 3 определения числа единиц;тЪ - время срабатывания блока 5 памя 50т 6 - время приема информации в регистры 6.Из выражений (1) и (2) следует справедливость соотношения Т-Т. б,показывающего, что длительность такта работы базового объекта превышает длительность такта работы заявляемого устройства по крайней мере на время тсуммирования двух 1-разрядных чисел.Таким образом, заявляемое устройство отличается от базового объекта как минимум вдвое меньшим количеством тактов, необходимых для сортировки исходного массива, и меньшей длительностью каждого такта. Вследствие этого заявляемое устройство обладает по крайней мере вдвое более высоким быстродействием.При необходимости поочередной выдачи отсортированных чисел заявляемое устройство может быть использовано совместно с любым известным устройством параллельно-последовательной буферизации, В этом случае на сортировку каждого массива будет затрачиваться ровно и тактов, т.е. на Н тактов меньше, нежели в базовом объекте,Формула изобретения Устройство для сортировки чисел, содержащее блок выделения минимального числа, регистр исключения чисел, первый блок определения числа единиц и группу элементов ИЛИ, причем входы 1-го числа устройства ( = 1, 2, ,и, и - количество сортируемых чисел) соединены соответственно с информационными входами 1-й группы блока выделения минимального числа, прямые выходы разрядов регистра исключения чисел соединены с входами первого блока определения числа единиц, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействияв него введены второй блок определения числа единиц, блок памяти и и входных регистров, причем инверсный выход 1-го разряда регистра исключения чисел соединен с 1-м разрешающим входом блока выделения минимального числа, 1-й адресный выход которого соединен с входом установки -го разряда регистра исключения чисел в единичное состояние, -м входом второго блока определения числа единиц и первым входом 1-го элемента ИЛИ группы, второй вход которого подключен к прямому выходу 1-го разряда регистра исключения чисел, вход установки в нулевое состояние которого является входом начальной установки устройства, информационные выходы блока выделения минимального числа соединены с информационными входами всех выходных регистров, выходы первого и второго блоков определения числа единиц соединены с адресными входами блока памяти, 1-й выход которого соединен с входом разрешения записи 1-го выходного регистра, выходы разрядов которого являются ин 17252151112формационными выходами 1-й группы уст- выходы всех элементов ИЛИ группы объедиройства, тактовый вход устройства соеди- нены монтажным И и являются выходом нен с тактовыми входами всех регистров, окончания работы устройства.