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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИН 09 (11) 7 06 94 С ИСАНИЕ ИЗОБРЕТЕНИЯ СТВУ ОРСКОМУ СВИД К 4/24-24.85 ыми знака ассивов чисел с чис о сорровк в сравнедвух чисели групп оров в каж тов НЕ по уппе и и ЭВ о позвонаи знакаалдо го ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ(56) Братальский Е.А Крупский А.А. Способы упорядочения массива с помощью ассоциативного устройства.Вопросы радиоэлектроники, сер Т, 1973, вып. 7, с. 90-93.Авторское свидетельство СССР В 1065854, кл. С 06 Р 7/06, 1982. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано в ассоциативных процессорах, в системах обработки и сортировки данных, в системах распознавания образов. Цель изобретения - расширение области применения за счет обеспечения сортировки тем учета знака сортируемо для управления процессом е ровки. Устройство для сорт сел содержит и групп блоко ния по и блоков сравнения в каждой группе, сумматоры коммутаторов по и коммутат дой группе, и групп элемен п элементов НЕ в каждой гр блоков коммутации. Устройс ляет сортировать по неубыв чений массивы чисел с разн ми за счет того, что знак числа управляет процессом сортировки, так как коммутирует значениячисел, поступающих на входы блоковсравнения, а результаты сравнения чисел определяют номер входного числав упорядоченной по неубыванию последовательности выходных чисел. 1 ил.Изобретение относится к автоматике и вычислительной технике и может быть испоЛьзовано в ассоциативных процессорах, системах обработки и сортировки данных, в системах распоз навания образов.Цель изобретения - расширение области применения за счет обеспечения сортировки массивов чисел с разными знаками. 1 ОНа чертеже показана схема устройства.Устройство для сортировки чисел содержит входы знаковых разрядов 1 , 1 1 сортируемых чисел хе19 х , ,х , инФормационные входы 2еее 9 9 9 2 2 сортируемых чисел, и групп элементов НЕ 3 39939 коммутаторы знака 4 -49 блоки сравнения 5 -5, сумматоры б 9 б . .96 , 20 коммутаторы 7 -7 и выходы 8 8998Устройство для сортировки чисел 1работает следующим образом.Массив чисел х , х . х, под,259 9 е9 лежащих сортировке по убыванию, поступает на входы устройства 11 1 , 2 , 2 2, причем первый раз 9 19 199 еее 9 199Ряд о,9 Ыд 9 9 о(каждого сортируемого числа х х х содержит30 знак числа (ноль для хО и единицу для х с О) и поступает соответственнона входи 1, 1 1 устройства, а г последующих значащих раз -1ряДОВ х 9 Х 9 .ее Хкаждого сорти 35 руемого числа поступают на входы 2 , 299 2 устройства соответственно. Знаковый разряд сС, каждого сортируемого числа х инвертируется первым элементов НЕ 1-й группы 3 и 40 поступает в качестве первого разряда числа на первые входы блоков сравнения 5 , 5 , , 5; и на вторые,11 9входы .-х блоков сравнения всех групп 5 5,2; 99 5; . ИнФормация, посту пающая на остальные входы г разрядов блоков сравнения 5; 5, 5;и О числа х; , которое поступает на управляющий вход -го коммутатора 50 знака 4,. Если сортируемое число не отрицательное, т.е, хО и с- = О, то на входы второго й последующих разрядов блоковсравнения поступает г значащих разрядов х 19 поступивших 55 на Вход устройства 2;, а если сортируемое число отрицательное, т.е.:, х;,с О и К; = 1, тогда навходы вто. рого и последующих разрядов блоков сравнения 2 , 2; , 2 и 2111 9 2 , , 2 поступят г входных значащих разрядов х после их инвертирования вторым и последующими элементами НЕ -й группы 3; . В результате все неотрицательные сортируемые числа, поступающие на соответствующие входы блоков сравнения, содержат в первом разряде единицу, а отрицательные сортируемые числа - ноль, причем остальные г разрядов положительных чисел совпадают с их значениями на входе, тогда как значения г остальных разрядов отрицательных чисел на входе блоков сравнения инверсны соответствующим значениям входного числа х. В блоках сравнения 5;, 5 5 1-й группы производится сравнение числа х;, поступившего на 1-е сортируемые Входы устройства 1, 2;, со всеми числами массива, при этом инвертированное значение входного знака числа используется в качестве первого значащего разряда, На выходе каждого блока сравнения 5;, Формируется высокий уровень 9 если число у., поступившее на его первый вход, не меньше числа у на втором входе, т.е. у.у., в противном случае, т.е. если у. с у, на выходе блока сравнения будет низкий уровень. Определим результаты сравнения двух сортируемых чисел хи х, которые Формируются на выходе блока сравнения51, ееЕсли оба сортируемых числа х. ихположительны, т,е. первый их знаковый разряд на входах 1;, 1 устройства равен нулю (К; = с 9= 0), тогдачисла у, у, поступающие на первыйи второй входы блока сравнения 5; 94совпадут с входными числами х;, х 19исключая первый разряд, который уобоих чисел у; и у будет одинаков,но равен единице. Поэтому результатсравнения чисел у и у; будет определяться соотношением входных чиселх и х , причем если х;х., то и1ь 99у;у и на выходе блока сравнения5; будет Формироваться высокий уро-вень, а если х ( х , то у с у. и9на выходе блока сравнения будет формироваться низкий уровень,Если первое сортируемое число хположительное а второе хотрицательное, тогда на выходе блока сравнения 5, независимо от величин чи з 1 сел х., х формируется высокий уровень. Это определяется тем, что знак первого положительного числа х, на входе устройства 1 равен нулю, а1знак второго отрицательного числа х на входе устройства 1 равен еди ,4 нице, поэтому первые разряды числел у , у , поступающих на входы блока. фсравнения 5; будут соответственно равны 1 и О, что и определит результат сравнения уу1 3Если первое сортируемое число х, 273915 4 10 ние х. с х, что определяет у, с у.,4 в результате этого и формируется низкий уровень на выходе блока сравнения 2,.Таким образом, на выходе каждого блока сравнения 2; у ув зависимости от знаков Ы.;, с/ сортируемыхчисел х х и значений чисел х х формируются двоичные результаты сравнения Т в соответствии с выра 1жением:отрицательное, а второе хположительное, тогда на выходе блока сравнения 5; фдрмируется независимо от величин чисел х , х низкий уровень. Это обусловлено тем, что знак ос первого числа на входе 1, устройстваравен единице, поэтому первый старший разряд числа у; будет равен ну О лю, а знак второго сортируемого числа Кна входе 1; устройства равен нулю, поэтому первый старший разряд числа у будет равен единице, что и определит результат сравнения у. с у 5Если оба сортируемых числа х; и хотрицательны, т.е. первый их знаковый разряд на входах 1 1. устройства равен единице (с.; = ос = 1), тогда первый разряд сравниваемых чисел 1 О у и у будет равен О, а остальныедг разрядов чисел у и у будут ин 1версны по отношению к значениям соответствующих разрядов х., х; на входах 1 , 1. устройства. Поэтому ре 1 4зультат сравнения чисел у и у в блоке сравнения 5 будет определяться соотношением отрицательных чисел х . и х на входах устройства. Если 1х,х, тогда на выходе блока срав О кения 2 формируется высокий уро 1,вень, так как в этом случае значащая часть х; числа х; не больше значащей части х числа х., т.е,х;сх, а на входы блока сравнения 2; посту пят проинвертированные коды х. и х, для которых справедливо обратное соотношение, т.е. х,х поэтому и уу . Аналогично, если отрицатель/ное число х . меньше отрицательного числа х тогда значащая часть х.1 числа х больше значащей части х .1числа х ., поэтому для обратных кодов,3формируемых на выходах блоков НЕ х-й и 3-групп 3;, 3. и поступающих на входы вторых и последующих разрядов блока сравнения 5; через коммутаторы знака 4;, 4, справедливо соотноше -=О,о =1,при о( =О,с;=О,х.) х 4 при Ы при оС пи о(; =1,Ы =О,приК;=О,оО,х сх Каждая д-я группа блоков сравненияв резуль ате срав нения числа х; со всеми числами массива формирует на выходах в соответствии с выражением (1) двоичные результаты сравнения УЯкоторые поступают на входы сумматора 6;. В результате сложения на выходе каждого сумматора 6, формируется двоИчный код номера позиции числа х в рассортированном массиве,1который равен сумме количества чисел массива. При этом для числа х которое больше всех чисел массива, формируется максимальное значение двоичного кода на выходе сумматора 6;, равное и, т.е, числу чисел в сортируемом массиве, а для наименьшего числа х массива формируется на выходе сумматора 6 наименьшее значение кода, равное 1, Для массивов с неравными числами двоичные коды номеров позиций на выходах сумматоров 5 , 5, , 5 представляют собой ряд несовпадаюцих дискретных чисел, заключенных в интервале 11, п, которые поступают на управляющие входы коммутаторов 7 ц -7 и разрешают прохождение на выход 7 только того числа х, из входного массива чисел, для которого значение двоичного кода на выходе сумматора 5 равно Б, где 3 = 1, 2.и.Таким образом, при поступлении на устройства для сортировки чисел массива из и чисел с различными знака.ми на выходах 7 , 7 , , 7 устройь ства они поступают упорядоченно по убыванию, причем на первые выходыЗаказ 6477/46 Тираж 67 1 Подписное ВН 1 ЫЯ Государственного комитета СССР по делам изобретений и открытий 113035 Москва ЖРаушская наб,д д. 4/5Производственно-полиграФическое предприятие, г, Ужгород, ул. Проектная, 4 3 12739 устройства поступают положительные числа так, что максимальное из них будет на первом выходе 7 , если положительные числа будут в исхбдном массиве, а за положительными числами на выходах устройства будут следовать в порядке убывания с ростом номера выхода отрицательные числа. При этом на последнем выходе устройства будет либо наименьшее отрицательное число, 1 О если в массиве исходных чисел есть отрицательные, либо наименьшее положительное число, если в массиве нет отрицательных чисел,Формула изобретенияУстройство для сортироки чисел, содержащее и групп блоков сравнения по и блоков сравнения в каждой группе, сумматоры и и групп коммутаторов по и коммутаторов в каждой группе, причем информационные входы коммутаторов -й группы, где 1 = 1,2п, где п - количество сортируемых чисел соединены с информационными входами р д-го сортируемого числа устройства, выходы блоков сравнения -й группы соединены с соответствующими входами -го сумматора, выход которого подключен к управляющим входам коммутаторов 1-% группы, входы первых групп блоков сравнения 1-й группы поразрядно объединены и подключены к соответствующим входам вторых групп -хблоков сравнения .1-х групп блок 6 всравнения, где 1 = 1,2п, выходы1-х коммутаторов 1-групп объединеныи являются соответствующими выходамиустройства, о т л и ч а ю щ е е с ятем, что, с целью расширения областиприменения за счет обеспечения сортировки массивов чисел с различнымизнаками, в устройство введены и группэлементов НЕ по и элементов НЕ в каждой группе и и коммутаторов знака,причем вход знакового разряда 1-госортируемого числа соединен с входомпервого элемента НЕ -й группы, с управляющим входом -го коммутаторазнака и с первыми Информационнымивходами коммутаторов 1-й группы, информационные входы -го сортируемого числа устройства соединены с первой группой информационных входовх-го коммутатора знака и входамиэлементов НЕ х-й группы с второго поп-й выходы которых подключены к второй группе информационных входовго коммутатора знака, выход первогоэлемента НЕ 1-й группы соединен спервыми входами первой и второйгрупп блоков сравнения х-й группыостальные входы первых групп блоковсравнения д-й группы соединены с соответствующими выходами -го коммутатора знака.