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

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

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

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

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

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

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

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

xi ю ел

ю

устройства, где ..,N, соединен с входом первого элемента НЕ i-ой группы, с управляющим входом 1-го коммутатора знака и с первыми информационными входами первой группы коммутаторов 1-ой группы, информационные входы t-ro сортируемого числа устройства соединены с информационными входами первой группы 1-го коммутатора знака, с информационными входами первой группы с второго по N-ый коммутаторов 1-ой группы и с входами элементов НЕ 1-ой группы с второго по N-ый, выходы которых подключены к информационным входам второй группы 1-го коммутатора знака, выход первого элемента НЕ 1-ой группы соединен с первыми входами первой и второй подгрупп соответственно первой и второй групп блоков сравнения i-ой группы, другие входы которых соединены с соответствующими выходами 1-го коммутатора знака, входы, первых подгрупп первых групп блокое сравнения 1-ой группы поразрядно объединены и подключены соответствующим входа м пер в ых по д гру пп. вторых групп 1-ых блоков сравнения j-ых групп блоков сравнения, где 1,2...N, выходы блоков сравнения I-ой группы соединены с соответствующими входами i-ro сумматора, выход первого сумматора соединен с управляющими входами коммутаторов первой группы, выходы 1-ых коммутаторов j-bix групп объединены и являются соответствующими выходами устройства, введены N.-1 групп дополнительных блоков сравнения по ISH-1 блоков сравнения в каждой, N-1блоков вычитания и М-2 дополнительных сумматоров, причем входы ранга i-ro сортируемого числа устройства соединены с соответствующими поразрядно: объединенными входами вторых подгрупп первых групп блоков сравнения i-ой группы, вторых подгрупп вторых групп блоков сравнения j-ых групп и с соответствующими информационными входами .второй групгты коммутаторов 1-ой группы, выходы 1-го сумматора соединены с входами первых групп N-i-т-ых блоков сравнения q-ой групп ы, ,...N-1, выход q+ 1-го сумматора Соединён с входами вторых групп q-И- k-ых дополнительных блоков сравнения К-ых групп; ,...,q-1, выходы q+1-го сумматора соедйн ей ы с входами уменьшаемо го q-ro блока вычитания, входы вычитаемого первого блоки вычитания соединены с выходами первого дополнительного блока сравнения первой группы, входы вычитаемого р-го блока вычитания, где ...М-1, подключены к выходам р-го Дополнительного сумматора, выходы q-ro блока вычитания соединены с управляющими входами коммутаторов q+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 и лока 6i соединены с управляющими входами соответствующих коммутаторов 7 соответствующих групп,

Устройство работает следующим образом. - . :

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

ранг числа, Сортировка чисел с разными рангами осуществляется фактически по двум критериям: числа, имеющие более высокий ранг (приоритет) упорядочиваются в первую очередь, иначе говоря, группа чисел,

имеющих ранг выше остальных располагается после сортировки впереди остальных независимо от знаков и абсолютных значений чисел более низких рангов; числа одного ранга сортируются в порядке убывания с

учетом значения и знака. Сортировка с учетом ранга числа является более.общим слу- чаем, нежели сортировка чисел без учета их

ранга.

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

входе 1, соответствующий коммутатор 4 знака коммутирует на выходы либо непосредственно информационные разряды числа с входа 2, либо инвертированные значения информационных разрядов с выходов элементов НЕ 3.

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

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

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

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

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

3) , . Из тех же соображений выходной сигнал с блока 5 - нулевой;

4) , . Инвертированные знако- вые разряды чисел-нулевые. За счет инвертирования информационных разрядов чисел, если I А В1 , на выходе блока 5 - низкий потенциал, иначе - высокий.

Каждая i-ая группа блоков 5 сравнения формирует совокупность двоичных значений - результатов сравнения, которые суммируются на соответствующем сумматоре 6. В результате сравнения и суммирования на выходе каждого сумматора 6 формирует- ся код номера места данного числа в порядке возрастания (меньший номер - для меньшего числа, больший - для большего). Так, для максимального из всех чисел, с учетом ранга, знака и абсолютного значе- ния, код с выхода соответствующего сумматора равен N, а для минимального - 1 (для случая несовпадающих чисел).

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

сумматора б соединен с первыми входами блоков 10 l-ой строки и вторыми входами блоков 10 1-1-го столбца указанной конструктивной матрицы. Иначе говоря, в 1-ой строке матрицы блоков 10 код с 1-го сумматора 6 сравнивается со всеми последующими кодами - с 1+1 по N-ый.

На выходах блоков сравнения 10 формируются единичные сигналы,если коды на первом и втором входах совпадают. Сигналы с блоков 10 каждого столбца суммируются на сумматорах 11 и полученные суммы вычитаются из кодов, полученных в блоках 6; вычитание одноименных кодов производится на блоках вычитания 12. При этом, если в массиве чисел есть совпадающие, то для них коды с выходов сумматоров б равны, но на выходах 15 в любом случае формируется ряд несовпадающих чисел от 1 до N. Это позволяет и для совпадающих чисел входного массива однозначно производить сортировку.

Коды с выходов 15 поступают на управляющие входы блоков 7 (коммутаторов) и в каждой группе этих блоков разрешают прохождение на соответствующий выход 81-то- го числа, для которого значение кода с соответствующего выхода 15 равно Г (M....N).

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

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

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

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

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

Формула изобретения . Устройство для сортировки чисел, содержащее N групп блоков сравнения по N блоков сравнения в каждой группе, N сумматоров, N групп коммутаторов по М комму- таторов в каждой группе, N групп элементов НЕ по N элементов НЕ в каждой группе и N коммутаторов знака, где N - количество сортируемых чисел, причем вход знакового разряда 1-го сортируемого числа устройства, где ...N, соединен с входом первого элемента НЕ 1-й группы, с управляющим входом 1-го коммутатора знака и с первыми информационными входами первой группы коммутаторов 1-й группы, информационные входы 1-го сортируемого числа устройства соединены с .информационными входами первой группы 1-го коммутатора знака, с информационными входами первой группы с второго по N-й коммутаторов 5-й группы и с входами элементов НЕ i-й группы с второго по N-й, выходы которых подключены к информационным входам второй группы i-ro коммутатора знака, выход первого элемента НЕ 1-й группы соединен с первыми входа- ми первой и второй групп соответственно первой и второй группы блоков сравнения 1-й группы, другие входы которых соединены с соответствующими выходами 1-го, коммутатора знака, входы первых подгрупп первых групп блоков сравнения i-й группы поразрядно объединены и подключены к соответствующим входам первых подгрупп вторых групп t-x блоков сравнения j-x групп блоков сравнения, где ,2 М,выходы блоко сравнения i-й группы соединены С соответствующими входами i-ro сумматора, выход первого сумматора соединен с управляющими входами-коммутаторов первой груп

пы, выходы 1-х коммутаторов j-x групп объединены и являются соответствующими выходами устройства,отличающееся тем, что, с целью расширения области применения за счет возможности сортировки равных чисел и учета рангов групп сортируемых чисел, в него введены (N-1) групп дополнительных блоков сравнения по (N-I-1) блоков сравнения в каждой, (N-1) блоков вычитания и (N-2) дополнительных сумматоров, причем входы ранга 1-го сортируемого числа устройства соединены с соответствующими поразрядно объединенными входами вторых подгрупп первых групп блоков сравнения 1-й группы, вторых подгрупп вторых групп блоков сравнения j-x групп и с соответствующими информационными входами второй группы коммутаторов 1-й группы, выходы 1-го сумматора соединены с входами первых групп (N-i-1)-x блоков сравнения q- й группы, ...N-1, выход (q+1)-ro сумматора соединен с входами вторых групп (q+1-K)-x дополнительных блоков сравнения К-х групп , q-1, выходы (q+1)-ro сумматора соединены с входами уменьшаемого q-ro блока вычитания, входы вычитаемого первого блока вычитания соединены с выходом первого дополнительного блока сравнения первой группы, входы вычитаемого р-го блока вычитания, где .,. подключены к выходам р-го дополнительного сумматора, выходы q-ro блока вычитания соединены с управляющими входами коммутаторов (р+-1)-й- группы, входы r-го дополнительного сумматора, где ...N-2, соединены с выходами (r-q+2)-x дополнительных блоков сравнения q-xгрупп.

/W

8j

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

fj/vt

;

13f1

$21

V;//

s@Ј

fe

Щ

fjf

t

8

ff«

iSl

A/-f,

15