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

 

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

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

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

РЕСПУБЛИК (5!)5 G 06 F 7/06

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4871439/24 (22) 05.10.90 (46) 15.02,93. Бюл, N 6 (71) Московский институт инженеров гражданской авиации (72) С,Ж. Кишенский, А.Л. Кузьмин, В.Б. Панова и О.Ю. Христенко (56) Авторское свидетельство СССР

N 1065854, кл. G 06 F 7/06, 1982.

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

N 1273915, кл, G 06 F 7/06, 1985, (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть исИзобретение относится к автоматике и вычислительной технике и может быть использовано в ассоциативных процессорах, в системах обработки и сортировки данных и в системах распознавания образов.

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

Недостатками известного устройства являются узкая область применения и низкая достоверность работы.

Наиболее близким по технической сущности к заявляемому является устройство для сортировки чисел, содержащее группы блоков сравнения, группы коммутаторов, сумматоры, группы элементов НЕ и коммутаторы знака, причем выходы коммутаторов объединены и являются выходами устройства, 1 ... Ж,, 1795449 А1 пользовано в ассоциативных процессорах, в системах обработки и сортировки данных, в системах распознавания образов. Целью изобретения является расширение области применения за счет возможности сортировки равных чисел и учета рангов групп сортируемых чисел. Устройство для сортировки чисел содержит N групп блоков сравнения по N блоков сравнения в каждой группе, N сумматоров, N групп коммутаторов по N коммутаторов в каждой группе; N групп элементов HE и Nкоммутаторов знака 4,,где N — количество сортируемых чисел, N — 1 групп дополнительных блоков сравнения, N-1 дополнительных блоков 12 вычитания, N-2 дополнительных сумматоров, 1 табл., 1 ил.

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

Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее N групп блоков сравнения по N блоков сравнения в каждой группе, N сумматоров, N групп коммутаторов по Й коммутаторов в каждой группе, N групп элементов НЕ по N элементов НЕ в каждой группе и N коммутаторов знака, где N— количество сортируемых чисел, причем вход знакового разряда 1-го сортируемого числа

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

i-ой группы с второго na N-ый, выходы которых подключены к информационным входам втОрой группы 1-ro коммутатора знака, выход первого элемента НЕ 1-ой группы со- 15 единен с первыми входами первой и второй подгрупп соответственно первой и второй групп блоков сравнения 1-ой группы, другие входы которых соединены с соответствующими выходами i-го коммутатора знака, вхо- 20 ды первых подгрупп первых rpynn блоков сравнения 1-ой группы поразрядно объединены и подключены ксоответствующим Входам первых подгрупп вторых групп 1-ых блоков сравнения J-ых групп блоков сравне- 25 ния, где J=1.2.. N, выходы блоков сравнения

1-ой группы соединены с соответствующими входами i-го сумматора, выход первого сумматора соединен с управляющими входами коммутаторов первой группы, выходы 1-ых 30 коммутаторов 1-ых групп объединены и яв- ляются соотаетству1ощими выходами устройства, введены . N-1 групп дополнительных блоков сравнения по N-!-1 блоков сравнения в каждой, N-1 блоков вы- 35 читания и N-2 дополнительных сумматоров, причем входы ранга 1-го сортируемого числа устройства соедйнены с соответствующими, поразрядно объединенными входами аторых подгрупп йераь1х групп блоков сраане- 40 ния 1-ой группы, вторых подгрупп вторых групп блоков сравнения j-ых групп и с соответствующими информационными входами второй группы коммутаторов l-ой группы, аыходы i-ro сумматора соединены с входами 45 первых групп N-i-1-ых блоков сравнения

q-ой группы, q=.1,. М-1,:выход ц+1-ro сумматора соединен с входами вторых групп с1+1k-ых дополнительных блоков сравнения

К-ых групп, К=1,...д-1, выходы о+1-го сум- -0 матора соедйнейы с входами уменьшаемого

q-го блока вйчитания, входы вычитаемого первого блока вйчитания соединены с выходами первого дополнительного блока сравнения первой группы, входы вычитаемога 55 р-ro блока вычитания, где р=2...N-1, подключены к айходам р-го дополнительного сумматора, выходы q-го блока вычитания со.единены с управляющими входами коммутаторов q+1-ой группы, входы г-го дополнительного сумматора, где г=1,...,N — 2, соединены с выходами r q+2-ых дополнительных блоков сравнения q-ых групп, На чертеже представлена структурная схема устройства для сортировки чисел.

Устройство для сортировки чисел содержит знаковые входы 1 сортируемых чисел, и информационные входы 2 сортируемых чисел, группы элементов НЕ 3, коммутаторы 4 знака, N групп блоков 5 сравнения по N блоков в каждой группе, сумматоры 6, N групп коммутаторов 7 по N коммутаторов в каждой группе, выходы 8 устройства, входы

9 рангов сортируемых чисел, N-1 групп допблнительных блоков 10 сравнения, N-2 дополнительных сумматоров 11 и N 1 дополнительных блоков 12 вычитания. Выходы 13 блоков сравнения 5 соединены с входами соответствующих сумматоров 6.

Выходы 14 дополнительных сумматоров 11 соединены с входами соответствующих блоков 12 вычитания; выходы 15 блоков 12 и блока 6 соединены с управляющими входами соответствующих коммутаторов 7 соответствующих групп, Устройство работает следующим образом .

Массив N чисел, подлежащих сортировке, поступает на входы 1, 2 и 9 устройства— соответственно знак числа ("0" для положительного и "1" для отрицательного числа), абсолютная. величина числа и ранг числа.

Ранг числа представляет собой двоичный код, причем чем больше этот код, тем выше ранг числа. Сортировка чисел с разными рангами осуществляется фактически по двум критериям . числа, имеющие более высокий ранг (приоритет) упорядочиваются в первую очередь, иначе говоря, группа чисел, ймеющих ранг выше остальных располагается после сортировки впереди остальных независимо от знаков и абсолютных значений чисел более низких рангов; числа одного ранга сортируются в порядке убывания с, учетом значения и знака. Сортировка с учетом ранга числа является более. общим случаем, нежели сортировка чисел без учета их ранга.

Знаковый разряд числа инвертируется первым элементом HE группы 3, а информациОнные — остальными элементами этой группы. В зависимости от значения знакового разряда числа на соответствующем входе 1, соответствующий коммутатор 4 знака коммутирует на выходы либо непосредственно информационные разряды числа с входа 2, либо инвертированные значения информационных разрядов с выходов элементов HE 3.

1795449

10

На блоки сравнения 5 числа поступают в следующем формате: старшие раэряды— разряды ранга; далее — инвертированный знаковый разряд; младшие разряды — информационные разряды числа, Таким образом, реализуется следующий принцип: числа большего ранга заведомо больше любых чисел низших рангов; для чисел одного ранга положительные числа больше любых отрицательных независимо от абсолютного значения; из двух отрицательных чисел меньше то, у которого абсолютная величина больше, так как его инверсный (обратный) код меньше.

На выходах блоков 5 формируется сигнал высокого уровня в том случае, когда сигнал на первом входе больше или равен коду на втором входе.

Поскольку результат сравнения чисел разных рангов однозначно определен рангом чисел, рассмотрим особенности сортировки чисел одного ранга. Здесь возможны четыре ситуации: (пусть числа — А и В).

1) А=О и В 0. При этом знаковые разряды равны нулю, а информационные коды — прямые, Результат определяется информационными разрядами. При А В на выходе блока 5 — высокий уровень сигнала.

2) А>0, В<0. Знак числа А равен "1", а числа  — "0" (от инверторов 3). Независимо от абсолютных значений чисел на выходе блока 5 — положительный сигнал;

3) А<0, В>О. Из тех же соображений выходной сигнал с блока 5 — нулевой;

4) А<0, В<0. Инвертированные знаковые разряды чисел — нулевые. За счет инвертирования информационных разрядов чисел, если А l > !В(, на выходе блока 5— низкий потенциал, иначе — высокий.

Каждая !-ая группа блоков 5 сравнения формирует совокупность двоичных значений — результатов сравнения, которые суммируются на соответствующем сумматоре

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

Так, для максимального из всех чисел, с учетом ранга, знака и абсолютного значения, код с выхода соответствующего сумматора равен "К", а для минимального — "1" (для случая несовпадающих чисел).

Коды с блоков 6 поступают на блоки сравнения t0, конструктивно образующие треугольную матрицу, причем выход l-го

45 сумматора 6 соединен с первыми входами блоков 10 t-ой "строки" и вторыми входами блоков 10 i-1-го "столбца" укаэанной конструктивной матрицы. Иначе говоря, в i-ой строке матрицы блоков 10 код с l-ro сумматора 6 сравнивается со всеми последующими кодами — с !+1 по N-ый.

На выходах блоков сравнения 10 формируются единичные сигналы, если коды на первом и втором входах совпадают. Сигналы с блоков 10 каждого столбца суммируются на сумматорах 11 и полученные суммы вычитаются из кодов, полученных в блоках

6; вычитание одноименных кодов производится на блоках вычитания 12, При этом, если в массиве чисел есть совпадающие, то для них коды с выходов сумматоров 6 равны, но на выходах 15 в любом случае формируется ряд несовпадающих чисел от "1" до "К".

Это позволяет и для совпадающих чисел входного массива однозначно производить сортировку.

Коды с выходов 15 поступают на управляющие входы блоков 7 (коммутаторов) и в каждой группе этих блоков разрешают прохождение на соответствующий выход 8l-того числа, для которого значение кода с соответствующего выхода 15 равно "l" (!=1 „., N).

Таким образом, на выходах 8 формируется массив, рассортированный по рангам, а внутри каждого ранга — по значениям с учетом знака.

Пусть все числа имеют один ранг, пусть

N--8, и сортируемые числа с первого по восьмое имеют значения: (все числа — положительные); 3, 7, 11, 2, 3, 2, 3, 6.

Ниже приведены сведенные в таблицу сигналы и эквивалентные десятичные значения кодов (двоичных) на выходах соответствующих блоков.

В последней графе таблицы приведены упорядоченные числа (в порядке возрастания с возрастанием номеров) и(в соответствующих случаях — через дробь) — их начальные номера из первой графы.

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

1795449

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

Устройство для сортировки чисел, содержащее N групп блоков сравнения по N блоков сравнения в каждой группе, N сумматоров, N групп коммутаторов по N комму- 5 таторов в каждой группе, Й групп элементов

НЕ по Й элементов НЕ в каждой группе и N коммутаторов знака, где N — количество сортируемых чисел, причем вход знакового разряда 1-ro сортируемого числа устройства, 1О где l=- l...N, соединен с входом первого элемента НЕ l-й группы, с управляющим входом i-ro коммутатора знака и С первыми информационными входами первой группы коммутаторов 1-й группы, информационные 15 входы 1-го сортируемого числа устройства соединены с информационными входами первой группы i-го коммутатора знака, с информационными входами первой группы с второго по N-й коммутаторов i-й группы и с 20 входами элементов HE i-й группы с второго по N-й, выходы которых подключены к информационным входам второй группы l-го коммутатора знака, выход первого элемента HE l-й группы соединен с первыми входа- 25 ми первой и второй групп соответственно первой и второй группы блоков сравнения

1-й группы, другие входы которых соединены с соответствующими выходами t-ra. коммутатора знака, входы первых подгрупп 30 первых групп блоков сравнения i-й группы поразрядно объединены и подключены к соответствующим входам первых подгрупп вторых групп t-x блоков сравнения )-х групп блоков сравнения, где j=1,2 Ы,выходы блоков35 сравнения i-й группы соединены с соответствующими входами i-го сумматора, выход первого сумматора соединен с управляющими входами коммутаторов первой груп40 пы, выходы i-x коммутаторов j-x групп обьединены и являются соответствующими выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет возможности сортировки равных чисел и учета рангов групп сортируемых чисел, в него введены (N-1) групп дополнительных блоков сравнения по (N-i — 1) блоков сравнения в каждой, (N-1) блоков вычитания и (N — 2) дополнительных сумматоров, причем входы ранга l-го сортируемого числа устройства соединены с соответствующими поразрядно объединенными входами вторых подгрупп первых групп блоков сравнения t-й группы. вторых подгрупп вторых групп блоков сравнения j-x групп и с соответствующими информационными входами второй группы коммутаторов i-й группы, выходы l-ro сумматора соединены с входами первых групп (М-t-1)-х блоков сравнения qй группы, q=1„.N-1, выход (ц+1)-го сумматора соединен с входами вторых групп (q+1-К)-х дополнительных блоков сравнения К-х групп К-1, q — 1, выходы (ц+1)-ro сумматора соединены с входами уменьшаемого ц-ro блока вычитания, входы вычитаемого первого блока вычитания соединены с выходом первого дополнительного блока сравнения первой группы, входы вычитаемого р-го блока вычитания, где р-2...И-1 подключены к выходам р-ro дополнительного сумматора, выходы ц-го блока вычитания соединены с управляющими входами коммутаторов (ц+1)-й группы, входы r-го дополнительного сумматора, где -1...N-2, соединены с выходами (r-q+2)-х дополнительных блоков сравнения q-х групп.

1795449

Редактор

Заказ 430 Тираж Подписное

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

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

А тг

Составитель С.Кишенский

Техред М.Моргентал Корректор Л.Филь

Производственно-издательский комбинат "Патент", r, Ужгород, ул.Гагарина, 101