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

(19 5)5 0 06 Г 7/06 ННОЕ СССР СССР) ГОСУДАРС ВЕДОМСТ (ГОСПАТЕ НТН ПИСАНИЕ И Б ТЕНИЯ ВТОРСКО ВИДЕТЕЛЬСТВУ В.Б. Паий, А,Л. Кузьмитенкоидетельство ССС06 Р 7/06, 1982.идетельство ССС06 Г 7/06, 1985,(54) УСТРОЙСТВСЕЛ(57) Изобретение вычислительной тносится к а хнике и мож матике и быть исние относится к авной технике и можеассоциативных прбработки и сортирораспознавания обрустройство для сорщее группы блоковгруппы коммутаторются выходами устрками известногоая область примененость работы. томатике и т быть исоцессорах, ки данных азов.тировкичисравнения, ов, выходы ойства,ройства я и ниэрНаиболее близким по технической сущности к заявляемому является устройство для сортировки чисел, содержащее группы блоков сравнения, группы коммутаторов, сумматоры, группы элементов НЕ и коммутаторы знака, причем выходы коммутаторов объединены и являются выходами устройства,(21) 4871439/24(71) Московский иданской авиации(56) Авторское свЙ. 1065854, кл. 6Авторское свЙ. 1273915, кл, 6 Изобрет вычислитель пользовано в системах о и в системахИзвестно сел, содержа сумматоры и которых являНедоста являются узк кая достове титут инженеров граж ЛЯ СОРТИРОВКИ ЧИпользовано в ассоциативных процессорах, в системах обработки и сортировки данных, в системах распознавания образов, Целью изобретения является расширение области применения за счет возможности сортировки равных чисел и учета рангов групп сорируемых чисел, Устройство для сортировки чисел содержит й групп блоков сравнения по Й блоков сравнения в каждой группе, Й сумматоров, Й групп коммутаторов по й коммутаторов в каждой группе, Й групп элементов НЕ и Й коммутаторов знака 4, где й - количество сортируемых чисел, Й - 1 групп дополнительных блоков сравнения, йдополнительных блоков 12 вычитания, йдополнительных сумматоров, 1 табл., 1 ил. Недостатком известного устройства является узкая область применения, обусловленная отсутствием возможности сортировки чисел, среди которых есть совпадающие по значению, а также отсутствие возможности сортировать числа в соответствии с присвоенными им рангами,Целью изобретения является расширение области применения эа счет возможности сортировки равных чисел и учета рангов групп сортируемых чисел,Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее Й групп блоков сравнения по й блоков сравнения в каждой группе, Й сумматоров, Й групп коммутаторов по Й коммутаторов в каждой группе, й групп элементов НЕ по й элементов НЕ в каждой группе и й коммутаторов знака, где Й - количество сортируемых чисел, причем вход знакового разряда-го сортируемого числаустройства, где 1=1 М, соединен с входом первого элемента НЕ 1-ой группы, с управляющим входом 1-го коммутатора знака и с первыми информационными входами первой группы коммутаторов 1-ой группы, ин формационные входы 1-го сортируемого числа устройства соединены с информационными входами первой группы 1-го коммутатора знака, с информационными входами первой группы с второго по И-ый коммута торов 1-ой группы и с входами элементов НЕ 1-ой группы с второго по Й-ый, выходы которых подключены к информационным входам второй группы 1-го коммутатора знака, выход первого элемента НЕ 1-ой группы со единен с первыми входами первой и второй подгрупп соответственно первой и второй групп блоков сравнения 3-ой группы, другие входы которых соединены с соответствующими выходами -го коммутатора знака, вхо ды первых подгрупп первых групп блоков сравнения 1-ой группы поразрядно обьединены и подключены ксоответствующим входам первых подгрупп вторых групп 1-ых блоков сравнения -ых групп блоков сравне ния, где )=1,2 Л, выходы блоков сравнения 1-ой группы соединены с соответствующими входами -го сумматора, выход первого сумматора соединен с управляющими входами коммутаторов первой группы, выходы 1-ых 30 коммутаторов 1-ых групп объединены и являются соответству 1 ощими выходами устройства, введены Мгрупп дополнительных блоков сравнения по й-1 блоков сравнения в каждой, Мблоков вы читания и Йдополнительных сумматоров, причем входы ранга 1-го сортируемого числаустройства соедйнены с соответствующими, поразряднообъединенными входами вторых подгрупп первых групп блоков сравне ния 1-ой группы, вторых подгрупп вторых групп блоков сравнения -ых групп и с соответствующими информационными входами второй группы коммутаторов 1-ой группы, еыходы 1-го сумматора соединены с входами 45 первых групп М-1-ых блоков сравнения . о-ой группы, о=1 Я,:вцходц+1-го сумматора собдинен с входами вторых групп ц+1- 1-ых дополнительных блоков сравнения К-ых групп, К=1,д, выходы ц+1-го сум матора соедйнейы с входами уменьшаемого о-го блока вйчитания, входы вычитаемого первого блока вйчитания соединены с выходами первого дополнительного блока сравнения первой группы, входы вычитаемога 55 р-го блока вычитания, где р=2 М, подключены к вйходам р-го дополнительного сумматора, выходы о-го блока вычитания со.- единены с управляющими входами коммутаторов ц+1-ой группы, входы г-го дополнительного сумматора, где г=1Й - 2,соединены с выходами г-ц+2-ых дополнительных блоков сравнения о-ых групп,На чертеже представлена структурнаясхема устройства для сортировки чисел,Устройство для сортировки чисел содержит знаковые входы 1 сортируемых чисел, иинформационные входы 2 сортируемых чисел, группы элементов НЕ 3, коммутаторы 4знака, й групп блоков 5 сравнения по Иблоков в каждой группе, сумматоры 6, йгрупп коммутаторов 7 по М коммутаторов вкаждой группе, выходы 8 устройства, входы9 рангов сортируемых чисел, Йгрупп дополнительных блоков 10 сравнения, йдополнительных сумматоров 11 и И дополнительных блоков 12 вычитания. Выходы 13 блоков сравнения 5 соединены свходами соответствующих сумматоров 6.Выходы 14 дополнительных сумматоров 11соединены с входами соответствующих блоков 12 вычитания; выходы 15 блоков 12 иблока 61 соединены с управляющими входами соответствующих коммутаторов 7 соответствующих групп,Устройство работает следующим образом.. Массив К чисел, подлежащих сортировке, поступает на входы 1, 2 и 9 устройства -соответственно знак числа ("0" для положительного и "1" для отрицательного числа),абсолютная величина числа и ранг числа,Ранг числа представляет собой двоичныйкод, причем чем больше этот код, тем вышеранг числа, Сортировка чисел с разнымирангами осуществляется фактически подвум критериям. числа, имеющие более высокий ранг (приоритет) упорядочиваются впервую очередь, иначе говоря, группа чисел,имеющих ранг выше остальных располагается после сортировки впереди остальныхнезависимо от знаков и абсолютных значений чисел более низких рангов; числа одного ранга сортируются в порядке убывания с,учетом значения и знака. Сортировка с учетом ранга числа является более. общим случаем, нежели сортировка чисел без учета ихранга,Знаковый разряд числа инвертируется первым элементом НЕ группы 3, а информационные - остальными элементами этой группы, В зависимости от значения знакового разряда числа на соответствующем входе 1, соответствующий коммутатор 4 знака коммутирует на выходы либо непосредственно информационные разряды числа с входа 2, либо инвертированные значения информационных разрядов с выходов элементов НЕ 3.510 15 20 25 30 35 40 45 5055 Коды с блоков б поступают на блоки сравнения 10, конструктивно образующие треугольную матрицу, причем выход 1-го На блоки сравнения 5 числа поступают в следующем формате: старшие раэряды - разряды ранга; далее - инвертированный знаковый разряд; младшие разряды - информационные разряды числа, Таким образом, реализуется следующий принцип: числа большего ранга заведомо больше любых чисел низших рангов; для чисел одного ранга положительные числа больше любых отрицательных независимо от абсолютного значения; из двух отрицательных чисел меньше то, у которого абсолютная величина больше, так как его инверсный (обратный) код меньше.На выходах блоков 5 формируется сигнал высокого уровня в том случае, когда сигнал на первом входе больше или равен коду на втором входе,Поскольку результат сравнения чисел разных рангов однозначно определен рангом чисел, рассмотрим особенности сортировки чисел одного ранга, Здесь возможны четыре ситуации; (пусть числа - А и В),1) А 0 и В О. При этом знаковые разряды равны нулю, а информационные коды - прямые, Результат определяется информационными разрядами. При А В на выходе блока 5 - высокий уровень сигнала,2) А 0, В 0. Знак числа А равен "1", а числа В - "О" (от инверторов 3), Независимо от абсолютных значений чисел на выходе блока 5 - положительный сигнал;3) А 0, В 0. Из тех же соображений выходной сигнал с блока 5 - нулевой;4) А 0, В 0. Инвертированные знаковые разряды чисел - нулевые, За счетинвертирования информационных разрядов чисел, если АВ 1, на выходе блока 5 - низкий потенциал, иначе - высокий.Каждая 1-ая группа блоков 5 сравнения формирует совокупность двоичных значений - результатов сравнения, которые суммируются на соответствующем сумматоре б, В результате сравнения и суммирования на выходе каждого сумматора б формируется код номера места данного числа в порядке возрастания (меньший номер - для меньшего числа, больший - для большего). Так, для максимального из всех чисел, с учетом ранга, знака и абсолютного значения, код с выхода соответствующего сумматора равен "К", а для минимального - "1" (для случая несовпадающих чисел). сумматора 6 соединен с первыми входами блоков 10 1-ой "строки" и вторыми входами блоков 10 1-1-го "столбца" укаэанной конструктивной матрицы. Иначе говоря, в 1-ой строке матрицы блоков 10 код с 1-го сумматора б сравнивается со всеми последующими кодами - с 1+1 по 1 ч-ый.На выходах блоков сравнения 10 формируются единичные сигналы, если коды на первом и втором входах совпадают, Сигналы с блоков 10 каждого столбца суммируются на сумматорах 11 и полученные суммы вычитаются из кодов, полученных в блоках б; вычитание одноименных кодов производится на блоках вычитания 12, При этом, если в массиве чисел есть совпадающие, то для них коды с выходов сумматоров б равны, но на выходах 15 в любом случае формируется ряд несовпадающих чисел от "1" до "К". Это позволяет и для совпадающих чисел входного массива однозначно производить сортировку.Коды с выходов 15 поступают на управляющие входы блоков 7 (коммутаторов) и в каждой группе этих блоков разрешают прохождение на соответствующий выход 81-того числа, для которого значение кода с соответствующего выхода 15 равно "1" (1=1 ., К).Таким образом, на выходах 8 формируется массив, рассортированный по рангам, а внутри каждого ранга - по значениям с учетом знака,Пусть все числа имеют один ранг, пусть И=8, и сортируемые числа с первого по восьмое имеют значения: (все числа - положительныее); 3, 7, 11, 2, 3, 2, 3, 6,Ниже приведены сведенные в таблицу сигналы и эквивалентные десятичные значения кодов (двоичных) на выходах соответствующих блоков.В последней графе таблицы гриведены упорядоченные числа (в порядке возрастания с возрастанием номеров) и(в соответствующих случаях - через дробь) - их начальные номера из первой графы. Таким образом. заявляемое устройство позволяет осуществить более общий принцип сортировки чисел - с учетом их рангов, а не только знаков и абсолютных значений; кроме того, заявленное устройство позволяет корректно сортировать массивы чисел, в которых встречаются несколько равных чисел. Эти факторы позволяют расширить область применения устройства.Формула изобретенияУстройство для сортировки чисел, содержащее И групп блоков сравнения по И блоков сравнения в каждой группе, И сумматоров, К групп коммутаторов по Й комму таторов в каждой группе, Й групп элементов НЕ по й элементов НЕ в каждой группе и К коммутаторов знака, где Й - количество сортируемых чисел, причем вход знакового разряда 1-го сортируемого числа устройства, 1 О где 1=1 Й, соединен с входом первого элемента НЕ 1-й группы, с управляющим входом 1-го коммутатора знака и С первыми информационными входами первой группы коммутаторов 1-й группы, информационные 15 входы 1-го сортируемого числа устройства соединены с информационными входами первой группы 1-го коммутатора знака, с информационными входами первой группы с второго по И-й коммутаторов 1-й группы и с 20 входами элементов НЕ 1-й группы с второго по И-й, выходы которых подключены к информационным входам второй группы 1-го коммутатора знака, выход первого элемента НЕ 1-й группы соединен с первыми входа ми первой и второй групп соответственно первой и второй группы блоков сравнения 1-й группы, другие входы которых соединены с соответствующими выходами 1-го. коммутатора знака, входы первых подгрупп ЗО первых групп блоков сравнения 1-й группы поразрядно абьединены и подключены к соответствующим входам первых подгрупп вторых групп 1-х блоков сравнения 1-х групп блоков сравнения, где)=1,2 Ы,выходы блоков 35 сравнения 1-й группы соединены с соответствующими входами 1-го сумматора, выход первого сумматора соединен с управляющими входами коммутаторов первой груп 40 пы, выходы 1-х коммутаторов)-х групп обьединены и являются соответствующими выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет возможности сортировки равных чисел и учета рангов групп сортируемых чисел, в него введены (И) групп дополнительных блоков сравнения по (Й- 1) блоков сравнения в каждой, (И) блоков вычитания и (й - 2) дополнительных сумматоров, причем входы ранга 1-го сортируемого числа устройства соединены с соответствующими поразрядно обьединенными входами вторых подгрупп первых групп блоков сравнения 1-й группы, вторых подгрупп вторых групп блоков сравнения )-х групп и с соответствующими информационными входами второй группы коммутаторов 1-й группы, выходы 1-го сумматора соединены с входами первых групп (М-1)-х блоков сравнения цй группы, ц=1.И, выход(ц+1)-го сумматора соединен с входами вторых групп (ц+1-К)-х дополнительных блоков сравнения К-х групп К"1, ц - 1, выходы (ц+1)-го сумматора соединены с входами уменьааемого ц-го блока вычитания, входы вычитаемого первого блока вычитания соединены с выходом первого дополнительного блока сравнения первой группы, входы вычитаемого р-го блока вычитания, где рйподключены к выходам р-го дополнительного сумматора, выходы ц-го блока вычитания соединены с управляющими входами коммутаторов (ц+1)-й группы, входы г-го дополнительного сумматора, где 1 М, соединены с выходами (г-ц+2)-х дополнительных блоков сравнения ц-х групп,1795449 Составитель С.КишенскийТехред М.Моргентал рректор Л.Ф ктор Заказ 430 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Раушская наб., 4/5 роизводственн А 9 Ь тельский комбинат "Патент", г, Ужгород, ул.Гагарина, 101