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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 09 о 4 С ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ОПИСАНИЕ ИЗОБ н двторскомУ СвидетеЛьСт(56) Братальский Е.А. и Крупский А.А. Способы упорядочения массива с помощью ассоциативного устройства. - Вопросы радиоэлектроники. Сер, ЭВТ.Вып. 7, 1973, с. 90-93.Авторское свидетельство СССР У 1065854, кл. 0 06 Р 7/06, 1982, (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано в устройствах обработки и сортировки данных систем контроля и регулирования, в 247860 А ассоциативных процессорах, в системахраспознавания образов, Цель изобретения - упрощение устройства. Устройство для сортировки чисел содержитигрупп блоков сравнения двух чиселпо и-(-1) блоков сравнения в -йгруппе, и сумматоров, и групп коммутаторов по и коммутаторов в каждойгруппе и игрупп элементов НЕ, количество которых в каждой группе равно -1, Устройство позволяет сокра-тить количество оборудования эа счетсравнения каждого сортируемого числатолько с последующими числами массива и формирования результатов сравнения каждого числа за счет инвертирования результатов сравнения предыдущих чисел с данным, 1 ил.Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах обработки и сортировки данных систем контроля и регулирования, в ассоциативных про цессах, в системах распознавания образов.Цель изобретения - упрощение устройства.На чертеже дана схема устройства,Устройство для сортировки чисел содержит входы 1, блоки 2 сравнения, группы элементов НЕ 3, сумматоры 4, коммутаторы 5, выходы 6.Устройство для сортировки чисел 15 работает следующим образом.В момент времени 1 на входы 1 1 1 устройства поступает массив еффиз и чисел х х,хи подлежащих1сортировке В блоках 2,1,2112;20 сравнения х-й группы число х сравнивается со всеми последующими числами массива, т.е, с хх, ,х. В Результате сравнения двух чисел х; и х на выходах каждого блока 2; сравнения формируется двоичный признак сравнения Ъ; в соответствии с выражением:,зц 11э 1х-.ОЙ группы поступают на первую группу (и-) входов сумматора 4;, кроме последнего сумматора 4. На вторую группу входов всех сум 40 маторов 4;, исключая первый сумматор 4 поступают признаки сравнения 6,В,6; которые сформированы блоками сравнения 2, ,2 ;, ,2и проинвертированы (-1)-м элементом НЕ (5.-1)-й группы 3; Вследствие того, что двоичные признаки сравнения В и ш представляют полную груп-е,Ф пу возможных результатов сравнения чисел хи х 1, т.е. х; З, х и х (х50 при инвертировании двоичного призйака равнения 6,; формируется двоичныйпризнак сравнения ш;который является результатом сравнения числа х; с предшествующим ему числом х , где И1,2-1 и определяется выра.жением (3) после замены индекса Ю на;1 и введения вместо интервала изме нения 1 интервала изменения1 -1В результате этого на первую группу входов сумматора 3; поступают признаки сравнения В;е числа х; со всеми последующими числами хе массива, а на вторую группу входов - двоичные признаки сравнения ш числа х; со всеми предыдущими числами х массива, где 1 =+ 1, +2и)= 1,23.-1. После суммирования на выходе сумматора 3; формируется управляющий сигнал У;, который является суммой результатов сравнения щ;е числа х; со всемичислами массива и результатов сравнения г; е числа х; со всеми последующими числами массива: н(4) Признаки сравнения ш,ш; отличныот 0 при сравнении неравных чисел",массива, в то время как если .х =хЕ,и е= ше 1= О, а признак г отличен,е е 9от О,В том случае, если в массиве исортируемых нет одинаковых чисел,т.е. все числа массива попарно не равны, тогда второе слагаемое в ооотношении (4) равно нулю. Поэтому формирование управляющего сигнала Р; длямассива неравных чисел заключаетсяв суммировании признаков сравненияш 1 е по 1 от 1 до и, при этом такоепреобразование не нарушает исходныхсоотношений в сортируемом массиве,при которых из условиях х,хЕследует Я;Уе, где х= 1,и; 1=1,и,В том случае, если в сортируемоммассиве все числа одинаковы, тогдавсе признаки ш, в соотношении (4)равны 0 и величина управляющего сигнала равна ; =- и-х, для = 1,и. Поэтому для массива равных чисел навходах устройства значения управляющих сигналов 3.; на выходах сумматоров 41,424 и прин ают последовательность дискретных несовпадающихзначений (ь - 11, (и)О. В результате массиву равных входных чиселх, = х ==х ставится в соответствие .соотношение управляющих сигналов р, ) р ) р ., которое числу хна входе с наименьшим номером приписывает наибольшее значение управляющего сигнала, а числу х на входе с наибольшим номером - наименьшее значение, что обеспечивает сортировку массива равных чисел.В общем случае для сортировки любого массива из и чисел преобразования (1) - (4) позволяют сформировать , иа выходах сумматоров 4; последовательность несовпадающих дискретных значений управляющих сигналов р;, 1 О принадлежащих интервалу О,п, причем значение р, указывает номер позиции числа х, в линейно упорядоченном по неубыванию массиве выходных чисел, 15Коммутаторы 5 -5 выполняют сорутировку чисел х; входного массива в зависимости от номера позиции числа х; на выходе сумматора 4;, при этом коммутатор 5,пропускает число х; 20 на выход 6 в том только случае, если р = в.Таким образом, при поступлениина входы 1 ,1 1 устройства мас-)5сива чисел х ,х х на выходыустройства 61,6 6 поступаетпоследовательность неубывающих чиселх , ), х вЪ х , при этом каждыеравных чисел оказываются рассорти- ЗОрованными по 1 соседним выходам. Формула изобретенияУстройство для сортировки чисел,35 содержащее пгрупп блоков сравнения двух чисел по п-(-1) блоков в 1247860 4каждой группе, где 3.= 2,3 ,и",п - количество чиселв массиве, пгрупп коммутаторов, и сумматоров,причем входы первого сравниваемогочисла устройства соединены с первымигруппами входов блоков сравненияпервой группы и с информационнымивходами коммутаторов первой группы,входы -го сравниваемого числа устройства соединены с первыми группамивходов блоков сравнения -й группы,информационными входами коммутаторов-й группы и вторыми группами входов-х блоков сравнения р-х групп, гдеР = 12 .,3.-1, вход и-го сравниваемого числа устройства соединен с информационными входами коммутаторови-й группы и вторыми группами входов(п)-х блоков сравнения всех групп,выходы блоков сравнения каждой К-йгруппы, где К = 1,2и, соединены с первой группой входов К-го сумматора, выходы всех и сумматоров соединены с управляющими входами коммутаторов соответствующих групп, разрядные выходы 1-х коммутаторов всехгрупп объединены, где = 1,2,. ,п,и подключены к 1-м выходам устрой"ства, о т л и ч а ю щ е е с я тем,что, с целью упрощения устройства,оно содержит игрупп элементов НЕ,причем входы элементов НЕ(-1)-йгруппы соединены соответственно с вы- .Эходами -х блоков сравнения р-х .групп, а выходы элементов НЕ (1-1)-йгруппы подключены к второй группевходов 1-го сумматора.1247860 ВхОды Составитель А. АлександровТехред М.Ходанич Коррект Редактор И С. Шек егл сное ака дПроектна Ужгород,ият 26/48 Тираж 671 ВНИИПИ Государственног по делам изобретений 113035, Москва, Ж, Рароизводственно-полиграфическо КцнШОрмоцоОнньщ ЙОдам инрсркцццОнным йаЬю ОтщпттЮРОВ 3 ц ЬРУаПИ Под омитета ССС открытий кая наб.,