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

Изобретение относится к автоматике и вычислигельной технике и может быть использовано в ассоциативных процессорах, системах обработки и сортировки данных, в системах распоз навания образов. Цель изобретения - расширение области -применения за счет обеспечения сортировки массивов чисел с разными знаками. На чертеже показана схема устройства. Устройство для сортировки чисел содержит входы знаковых разрядов 1 , 1 ,...,1( сортируемых чисел х , 1 ..х, информационные входы 2 , .,,2 сортируемых чисел, п групп элементов НЕ 3, , Зг,, . . . ,3, коммутаторы знака , блоки сравнения сумматоры b 1 hn 5 и выходы 8 , коммутаторы 7, -7 8 э . . ., о . Устройство для сортировки чисел I работает следующим образом. Массив чисел х., х. -, -,.- -.п подлежащих сортировке по убыванию, поступает на входы устройства 1, , 1 , . . Ч, 2,...,2, причем первый -раз ряд сА ,сУ-,2 , .. ., oij каждого сортируеX;,, X 5f гопетзжит х содержит 4Hcjia л, л,, . . ., знак числа .(ноль для х О и единицу для X 0) и поступает соответственнона входы 1, 1,..., 1 устрой ства, а г последующих значавщх разрядов х, x,j, .. . х каждого сортируемого числа поступают на входы 2, 2,.,,, 2 устройства соответственно. Знаковый разряд Ы.-, каждого сортируемого числа х инвертируется первым элементов НЕ i-й группы 3 и поступает в качестве первого разряда числа на первые входы блоков срав 5;„ , . . ., 5.К и на вторые нения , 2 входы i-x блоков сравнения всех груп Информация, посту /2, пающая.на остальные входы г разрядо блоков сравнения 5, , 1-2 J , зависит от знака 5 21 ot. числа Х-, , которое поступает на управляющий вход i-ro коммутатора знака 4 j. Если сортируемое число не отрицательное, т.е. у.- Q и ot-j О, то на входы второго и последующих разрядов блоков;сравнения поступает г значащих разрядов Xj, поступивших на вход устройства 2, а если сорти руемое число отрицательное, т.е.- . X, О и oti i, тогда навходы вто рого и последующих разрядов блоков сравнения 2. , 2,-.2.- и 2, поступят г входных значащих разрядов х j после их инвертирования вторым и последующими элементами НЕ группы 3 . В результате все неотрицательные сортируемые числа, поступающие на соответствующие входы блоков сравнения,содержат в первом разряде единицу, а отрицательные сортируемые числа - ноль, причем остальные г разрядов положительных чисел совпадают с их значениями на входе, тогда как значения г остальных разрядов отрицательных чисел на входе блоков сравнения инверсны соответствующим значениям входного числа х. В блоках сравнения 5,; , 5 i , i-й группы производится сравнение числа , поступившего на i-e сортируемые входы устройства 1 , 2 , со всеми числами массива, при этом инвертированное значение входного знака числа используется в качестве первого значащего разряда. На выходе каждого блока сравнения 5,-,j формируется высокий уровень, если число у. , поступившее на его первый вход, не меньше числа yj на втором входе, т.е. у. : у., в противном случае, т.е. если у . - У} j вькоде блока сравнения будет низкий уровень. Определим результаты сравнения двух сортируемых чисел X и Xj, которые формируются на выходе блока сравнения 5п- Если оба сортируемых числа х.- и Xj положительны, т.е. первьй их знаковый разряд па входах 1, 1: устройства равен нулю (ot- o.j 0), тогда числа yj, yj5 поступающие на первый и второй входы блока сравнения 5 ,J совпадут с входными числами , xj, исключая первьй разряд, который у обоих чисел и yj будет одинаков. но равен единице. Поэтому результат сравнения чисел и у будет определяться соотношением входных чисел х и Xj, причем если х,- х- , то и у, У- и на выходе блока сравнения 5 i будет формироваться высокий уровень, а если , и на выходе блока сравнения будет формироваться низкий уровень. Если первое сортируемое число xJ положительное,, а второе Xj отрицательное, тогда на выходе блока сравнения независимо от величин чисел х. , х. формируется высокий уровень. Это определяется тем, что знак первого положительного числа х, на входе устройства 1- равен нулю, а знак второго отрицательного числа Xj на входе устройства 1 равен единице, поэтому первые разряды числел у- , у , поступающих на входы блока сравнения 5;, будут соответственно равны 1 и О, что и определит результат сравнения у у.. Если первое сортируемое число х отрицательное, а второе Xj положительное, тогда на выходе блока сравнения 5jj фс5 мируется независимо от величин чисел х-, х. низкий уровень обусловлено тем, что знак otj пер вого числа на входе 1. устройства равен единице, поэтому первый старший разряд числа у будет равен нулю, а знак второго сортируемого числа oCj на входе 1 устройства равен нулю, поэтому первый старший разряд числа yj будет равен единице, что и определит результат сравнения у. . у. Если оба сортируемых числа х | и X отрицательны, т.е. первыр их знаковый разряд на входах Ij , 1j устрой ства равен единице (oL- oi 1) тог да первый разряд сравниваемых чисел у, и у будет равен О, а остальные г разрядов чисел у и у будут инверсны по отношению к значениям соот ветствующих разрядов , Xj- на входах 1- , 1. устройства. Поэтому результат сравнения чисел у и yj в блоке сравнения 5jj будет определять ся соотношением от1)ицательных чисел X . и х- на входах устройства. Если Xj Xj, тогда на выходе блока сравнения 2- формируется высокий уровень, так как в этом случае значащая часть х; числа х не больше значащей части Kj числа х., T.e.x-iXj, а на входы блока сравнения 2jj поступят проинвертированные коды xJ t для которых справедливо обратное соотношение, т.е. х. х- поэтому и у- : у- . Аналогично, если отрицатель ное число X L- меньше отрицательного числа X ., тогда значащая часть х числа X больше значащей части х . числа X.,. поэтому для обратных кодов формируемых на выходах блоков НЕ i-й и j-групп 3j , 3j и поступающих на входы BTopfbix и последующих разрядов блока сравнения 5,-j через коммутатор знака 4, 4j, справедливо соотношение X. .i. Xj , что определяет у, у. , в результате этого и формируется низкий уровень на выходе блока сравнения 2 ; . Таким образом, на выходе каждого блока сравнения у,-, у в зависяV IJ мости от знаков сА- , Ы-j сортируемых чисел Xj, Xj и значений чисел х , xj формируются двоичные результаты сравнения У . в соответствии с вьфажением: 0,otj 1,npno(,,x.,Xj, присА ,01. 1, х-5 о Т J Q при o(,,,пpиo(..,c-J-0,, при оС , 1, 1, X. 4 Xj Каждая i-я группа блоков сравнения 2,, ,,.., 2 в результате сравнения числа X-J со всеми числами массива формирует на выходах в соответствии с выражением (1) двоичные ре зультаты сравнения Y, . , ..., У. , которые поступают на входы сумматора 6;. В результате сложения на выходе каждого сумматора 6 формируется двоичный код номера позиции числа х- в рассортированном массиве, который равен сумме количества чисел массива. При этом для числа Xj , которое больше всех чисел массива, формируется максимальное значение двоичного кода-на выходе сумматора 6( , равное п, т.е. числу чисел в сортируемом массиве, а для наименьшего числа X j массива формируется на выходе сумматора 6j наименьшее значение кода, равное 1. Для массивов с неравными числами двоичные коды номеров позиций на выходах сумматоров 5, Sg, ..., 5 представляют собой ряд несовпадаюрцтх дискретных чисел, заключенных в интервале t1, п, которые поступают на управляюш {е входы коммутаторов 7,, 7 и разрешают прохождение на выход 7j только того числа X. из входного массива чисел, для которого значение двоичного кода на выходе сумматора 5 равно S, где S 1, 2, ... п. Таким образом, при поступлении на входы 1,, Ц,..., 1,, 2,, 2, ..., 2н устройства для сортировки чисел массива из п чисел с различными знакаи на выходах 7, 7,,.., 7 устройтва они поступают упорядоченно по быванию, причем на первые выходы

Изобретение относится к области автоматики и вычислительной техники и может быть использовано в ассоциативных процессорах, в системах обработки и сортировки данных, в системах распознавания образов. Цель изобретения - расширение области применения за счет обеспечения сортировки массивов чисел с разными знаками путем учета знака сортируемого числа для управления процессом его сортировки. Устройство для сортировки чисел содержит п групп блоков сравнения по п блоков сравнения двух чисеп в каждой группе, сумматоры, п групп коммутаторов по п коммутаторов в каждой группе, п групп элементов НЕ по п элементов НЕ в каждой группе и п блоков коммутации. Устройство позволяет сортировать по неубыванию значений массивы чисел с разными знаками за счет того, что знак каждого числа управляет процессом сортиров ки, так как коммутирует значения чисел, поступающих на входы блоков СО сравнения, а результаты сравнения чисел определяют номер входного числа в упорядоченной по неубыванию последовательности выходных чисел. 1 ил. ю со со