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

 

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

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

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

РЕСПУБЛИК

09) (11)

151) 4 С 06 F 7/06

А1

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3869434/24 — 24 (.22) 07. 03. 85 (46) 30.11.86. Вюл.№ 44 (72) Э.Д.Еремеева и В.А.Черепов (53) 681.325(088.8) (56) Братальский E.A., Крупский А.A.

Способы упорядочения массива с помощью ассоциативного устройства.

Вопросы радиоэлектроники, сер. ЭВТ, 1973, вып. 7, с. 90-93.

Авторское свидетельство СССР

¹ 1065854, кл. С 06 F 7/06, 1982. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано в ассоциативных процессорах, в системах обработки и сортировки данных, в системах распознавания образов. Цель изобретения — расширение области применения за счет обеспечения сортировки массивов чисел с разными знаками путем учета знака сортируемого числа для управления процессом его сортировки. Устройство для сортировки чисел содержит и групп блоков сравнения по и блоков сравнения двух чисел в каждой группе, сумматоры, и групп коммутаторов по и коммутаторов в каждой группе, и групп элементов НЕ по и элементов НЕ в каждой группе и и блоков коммутации. Устройство позволяет сортировать по неубыванию значений массивы чисел с разными знаками за счет того, что знак каждого числа управляет процессом сортировки, так как коммутирует значения чисел, поступающих на входы блоков сравнения, а результаты сравнения чисел определяют номер входного числа в упорядоченной по неубыванию последовательности выходных чисел. 1 ил.

1273915

Изобретение относится к автоматике и вычислительной технике и может быть испоЛьзовано в ассоциативных процессорах, системах обработки и сортировки данных, в системах распознавания образов.

Цель изобретения — расширение области применения за счет обеспечения сортировки массивов чисел с разными знаками. 10

На чертеже показана схема устройства.

Устройство для сортировки чисел содержит входы знаковых разрядов

1, 1,...,1„ сортируемых чисел х

9 9 9 99 19 х,...,х, информационные входы 2

g9 9 999

2,...,2„ сортируемых чисел, и групп элементов НЕ 3,, 3>,...,3„, коммутаторы знака 4„ -4 19 блоки сравнения

5,1 -5„„, сумматоры 6„, 6,...,6„, 20 коммутаторы 7„ -7 „ и выходы 8,, 8,...,8„.

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

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

Массив чисел х, х,...,х„, под, 25

9 9 ° ° 9 лежащих сортировке по убыванию, поступает на входы устройства 1,,1

1, 2, 2,...,2„, причем первый раз9 19 9 9 Ь9 ряд о,,оь.д 9..., о(„ каждого сортируемого числа х,, х,..., х„ содержит

30 знак числа (ноль для х > 0 и единицу для х < О) и поступает соответственно на входи 1„, 1,..., 1„ устройства, а r последующих значащих раз—

1 I рядов х 9 х 9 а е х каждого сорти 35 руемого числа поступают на входы

2 „, 2,...9 2„ устройства соответственно. Знаковый разряд ol, каждого сортируемого числа х инвертируется ,1 первым элементов НЕ i-й группы 3 и 40

1 поступает в качестве первого разряда числа на первые входы блоков сравнения 5, 5„,, 5;„ и на вторые

9 входы i — x блоков сравнения всех групп

5„;; 5;,..., 5„; . Информация, посту- 45 пающая на остальные входы r разрядов блоков сравнения 5;,, 5,,..., 5;„и

oL числа х;, которое поступает на

i управляющий вход i-го коммутатора 50 знака 4;. Если сортируемое число не отрицательное, т.е. х 0 и сь- = О, то на входы второго и последующих разрядов блоков сравнения поступает

r значащих разрядов х 9 поступивших 55 на вход устройства 2;, а если сортируемое число отрицательное, т.е.:. х; .r О и о ; = 1, тогда на входы второго и последующих разрядов блоков сравнения 2, 2;,,..., 2 и 2, 1

2,, 2 поступят r входных значащих разрядов х после их инвертиI рования вторым и последующими элементами НЕ i-й группы 3; . В результате все неотрицательные сортируемые числа, поступающие на соответствующие входы блоков сравнения, содержат в первом разряде единицу, а отрицательные сортируемые числа — ноль, причем остальные r разрядов положительных чисел совпадают с их значениями на входе, тогда как значения r остальных разрядов отрицательных чисел на входе блоков сравнения инверсны соответствующим значениям входного числа х. В блоках сравнения 5; 5 ;,..., 5„;, i-й группы производится сравнение числа х9 9 поступившего íà i-e сортируемые входы устройства 1„-, 2;, со всеми числами массива, при этом инвертированное значение входного знака числа используется в качестве первого значащего разряда. На выходе каждого блока сравнения 5;,„ формируется высокий уровень9 если число у., поступившее на его первый вход, 1 не меньше числа у „. на втором входе, т.е. у. у., в противном случае, 1 J т.е. если у. с у, на выходе блока I

9 сравнения будет низкий уровень. Определим результаты сравнения двух сортируемых чисел х „и х„., которые формируются на выходе блока сравнения

5;„..

Ю

Если оба сортируемых числа х.- и 1 х „. положительны, т.е. первый их знаковый разряд на входах 1;, 1„ устройства равен нулю (<. = < О), тогда числа у„, у„., поступающие на первый и второй входы блока сравнения 5; совпадут с входными числами х;, х ь, исключая первый разряд, который у обоих чисел у; и у„ будет одинаков, но равен единице. Поэтому результат сравнения чисел у„. и у; будет определяться соотношением входных чисел х. и х, причем если х; > х., то и

Ь9 r,9 9 у; > у. и на выходе блока сравнения

5; будет формироваться высокий уро- вень, а если х (х ., то у с у. и

1 ь 1 Л на выходе блока сравнения будет формироваться низкий уровень.

Если первое сортируемое число х,„. положительное,, а второе х „ отрицательное, тогда на выходе блока сравнения 5„> независимо от величин чи273915 4

10 при Ы. при о(. отрицательное, а второе х „положительное, тогда на выходе блока сравнения 5;„ фсфмируется независимо от величин чисел х, х низкий уровень. (J

Это обусловлено тем, что знак о(. первого числа на входе 1. устройства I

5$ равен единице, поэтому первый старший разряд числа у; будет равен ну- О лю, а знак второго сортируемого числа К „ на входе 1; устройства равен нулю, поэтому первый старший разряд числа у„ будет равен единице, что и определит результат сравнения у. с у..t5

Если оба сортируемых числа х; и х „ отрицательны, т.е. первый их знаковый разряд на входах 1;, 1 устройства равен единице (d.; = ос = 1), тогда первый разряд сравниваемых чисел у и у будет равен О, а остальные д

r разрядов чисел у. и у будут инт S версны по отношению к значениям соответствующих разрядов х „., х; на вхо( дах 1, 1. устройства. Поэтому ре1 .( зультат сравнения чисел у. и у в блоке сравнения 5. будет определять1,5 ся соотношением отрицательных чисел х . и х. на входах устройства. Если х, > х„-, тогда на выходе блока срав- 4О кения 2 формируется высокий уро1,( вень, так как в этом случае значащая часть х; числа х; не больше значащей части х . числа х., т.е.х ;сх „, а на входы блока сравнения 2;„ посту- 4 пят проинвертированные коды х. и х „., для которых справедливо обратное соотношение, т.е. х . > х поэтому и ( у > у . Аналогично, если отрицатель) ное число х . .меньше отрицательного 1 числа х ., тогда значащая часть х.

1 числа х больше значащей части х .

1 J числа х ., поэтому для обратных кодов, 3 формируемых на выходах блоков НЕ i-й и j-групп 3;, 3„. и поступающих на входы втофь5х и последующих разрядов блока сравнения 5;„. через коммутаторы знака 4;, 4„, справедливо соотноше— з 1 сел х., х формируется высокий уро5 вень. Это определяется тем, что знак первого положительного числа х, на входе устройства 1 равен нулю, а

1 знак второго отрицательного числа х на входе устройства 1 равен едиJ .( нице, поэтому первые разряды числел у, у., поступающих на входы блока ( сравнения 5;„ будут соответственно равны 1 и О, что и определит результат сравнения у > у..

Если первое сортируемое число х, ние х. < х>, что определяет у, с у., (.( в результате этого и формируется низкий уровень на выходе блока сравнения 2,„.

Таким образом, на выходе каждого блока сравнения 2;„. у,, у „ в зависимости от знаков (5.;, с -„. сортируемых

I чисел х,, х„и значений чисел х

1 х формируются двоичные результаты сравнения (.. в соответствии с выраl4 жением:

=О,о(. =1,при Ы.=О,о((;=О,х.> x

4,5 п (и о(; =1,Ы =О,приК;=О,о(-„.-O,х. сх

Каждая i-я группа блоков сравнения

2„,, 2,д,..., 2„„ в результате сравнения числа х; со всеми числами массива формирует на выходах в соответствии с выражением (1) двоичные результаты сравнения 7„„, (.

s7 которые поступают на входы сумматора 6;. В результате сложения на выходе каждого сумматора 6,. формируется двоичный код номера позиции числа х в рассортированном массиве, 1 который равен сумме количества чисел массива. При этом для числа х,, которое больше всех чисел массива, формируется максимальное значение двоичного кода на выходе сумматора 6;, равное и, т.е. числу чисел в сортируемом массиве, а для наименьшего числа х массива формируется на выJ ходе сумматора 6„ наименьшее значение кода, равное 1. Для массивов с неравными числами двоичные коды номеров позиций на выходах сумматоров

5, 5, ..., 5„ представляют собой ряд несовпадаюцих дискретных чисел, заключенных в интервале 1, и), которые поступают на управляющие входы коммутаторов 7„ -7„„ и разрешают прохождение на выход 7s(только того числа х. из входного массива чисел, 1 для которого значение двоичного кода на выходе сумматора 55 равно S, где

Я = 1, 2. .. и.

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

15

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

Редактор М.Дылын Техред Л.Сердюкова Корректор N.Ïîæî

Заказ 6477/46 Тираж 67 1 Подписное

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

113035 Москва Ж-35 Раушская наб д д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4

% 12739 устройства поступают положительные числа так, что максимальное из них будет на первом выходе 7, если положительные числа будут в исхбдном массиве, а за положительными числами на выходах устройства будут следовать в порядке убывания с ростом номера выхода отрицательные числа. При этом на последнем выходе устройства будет либо наименьшее отрицательное число, 10 если в массиве исходных чисел есть отрицательные, либо наименьшее положительное число, если в массиве нет отрицательных чисел. формула изобретения

Устройство для сортироки чисел, содержащее и групп блоков сравнения по и блоков сравнения в каждой группе, сумматоры и и групп коммутаторов по и коммутаторов в каждой группе, причем информационные входы коммутаторов i-й группы, где i = 1,2,...,n, где и — количество сортируемых чисел соединены с информационными входами р5

i † сортируемого числа устройства, выходы блоков сравнения i-й группы соединены с соответствующими входами

i-го сумматора, выход которого подключен к управляющим входам коммутаторов i-% группы, входы первых групп блоков сравнения i-й группы поразрядно объединены и подключены к соответствующим входам вторых групп i-x блоков сравнения .j — x групп блоков сравнения, где j = 1,2,...,п, выходы

i-x коммутаторов j ãðóïï объединены и являются соответствующими выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет обеспечения сортировки массивов чисел с различными знаками, в устройство введены и групп элементов НЕ по и элементов НЕ в каждой группе и и коммутаторов знака, причем вход знакового разряда >-го сортируемого числа соединен с входом первого элемента НЕ i-й группы, с управляющим входом i-го коммутатора знака и с первыми Информационными входами коммутаторов i-й группы, информационные входы -го сортируемого числа устройства соединены с первой группой информационных входов

i-го коммутатора знака и входами элементов НЕ i-й группы с второго по п-й выходы которых подключены к второй группе информационных входов го коммутатора знака, выход первого элемента НЕ i-й группы соединен спервыми входами первой и второй групп блоков сравнения i-й группы остальные входы первых групп блоков сравнения i-й группы соединены с соответствующими выходами i-ro коммутатора знака.