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

)5 С 06 Р 7/ ации, емые 5 7 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯПРИ ГКНТ СССР ВТОРСНОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССР У 959065, кл. 6 06 Г 7/04, 1982.Авторское свидетельство СССР У 1049900, кл. С 06 Р 7/06, 1982. (54) УСТРОЙСТВО ДПР СОРТИРОВКИ ЧИС (57) Изобретение относится к вычи лительной технике и может быть использовано в специализированных ус ройствах обработки информации, пре назначенных для параллельной сорти ровки массивов данных, поступающих последовательным кодом в реальном масштабе времени, Целью изобретеш является повышение быстродействия Устройство содержит тактовый вход информационные входы 2, вход 3 начальной установки, блок 4 сравнени блок 5 дешифрации, блок 6 коммут информационные выходы 7, Сортиру чнслапоступают последовательным ко дом на вход устройства старшими ра рядами вперед. На выходе устройств получают отсортированный массив в последовательном коде, 3 з.п,ф-лы,Изобретение относится к вычислитЕльной технике и может быть использвано в специализированных устройствах обработки информации, предназначЕнных для параллельной сортировкимассивов данных, поступающих последовательным кодом в реальном масштабевремени.Цель изобретения - повышение быстр действия,На йиг,1 представлена функциональн я схема устройства для сортировкич сел; на Лиг.2 - схема блока сравн ния; на йиг.3 - схема узла сравнения; на фиг,4 - схема блока дешифрации; на фиг,5 - схема блока коммутсции,Устройство содержит тактовый вход1 информационные входы 2, вход 3начальной установки, блок 4 сравненля, блок 5 дешифрации, блок 6 коим 1 тации и инйормационные выходы 7,ща щБлок 4 сравнения включает --2улов 8 сравнения (щ-количество сортруемых чисел), каждый из которыхсдержит схему 9 сравнения, элемент ИЛИ 10-10, триггеры 11 и 11.Блок 5 дешифрации образуют 2 щ сумматоров 12 и 2 щ дешийраторов 13.Бпок 6 коммутации содержит регистр 14и щ коммутаторов 15.Устройство работает следующимобразом.Перед началом сортировки чиселиМпульсом положительной полярностис входа 3 триггеры 11 и 11 во всеху лах 8 сравнения устанавливаютсяв "0". Сортируемые числа с входа 2по щ каналам старшими разрядами вперед поступают на входы блоков 4 и 6сравнения и коммутации, причем вкаждом р-м такте (р,2 п+ 1;(8=1,2 п) сортируемых чисел,Блок 4 сравнения предназначен дляпопарного сравнения сортируемых чисел и йормирования на выходах результатов данного сравнения. Попарньм сравнением каждого 1-го числа(3=1,2 щ) с остальными числамии;олучают информацию о количествечисел, больших 1-го числа, и количестве чисел, меньших 1-го числа,Информация о сравнении 1-го числапроступает на (21-1)-ю и 21-ю группывыходов, причем каждая из групп име ет по (щ) выходов. Количествоединиц в (21-1)-й группе определяютколичество чисел, меньших 1-го числа, а количество единиц в 21-й группе - количество чисел, больших 3-гочисла.Результаты сравнения с выходовблока 4 сравнения поступают на входыблока 5 дешифрации, который для каждого 3-го числа производит подсчетколичества чисел меньших и больших)данного числа, и йормирует на выходах блока 5 щ групп сигналов управления блоком 6 коммутации, В блоке6 коммутации комутаторы 15,15 щинйормацией о соответствующих управляющих групп входов устанавливаютсяв положение, при котором на их выход поступают разряды чисел согласно результатам сравнения., т.е. навыход коммутатора 15- максимальноечисло, на выход коммутатора 15 -следующее по величине и т,д.Рассмотрим работу устройства вр-м такте,е С информационного входа 2 д-еразряды сортируемых чисел поступаютна входы регистра 14 и на входысхем 9 сравнения всех узлов 8 сравнения, где они попарно сравниваются каждый с каждым. В зависимостиот инйормации на первом и второмвходах схем 9 сравнения на их первоми втором выходах получают следующее:00 - инйормация на первом входеравна информации на второмвходе;01 - информация на первом входеменьше информации на второмвходе; 4010 - информация на первом входебольше инйормации на второмвходе,В узле 8;, сравнения (=1,23-1, 1 с=1,2,) на схеме 9 срав нения происходит сравнение р-х разрядов Е-го и 3-го чисел. Результатысравнения данных разрядов с первогои второго выходов схемы 9 сравненияпоступают на входы злементов ИЛИ 10и 10.Триггеры 11 и 11, в зависимости от результатов сравнения старших предыдущих разрядов Ь.-го и 1-го55чисел могут быть установлены следующим образом:00 - И-е число равно -му;01 - К-е число меньше -го;10 - 1-е число больше 1"го.2, Устройство по п, 1, о т л и - ч а ю щ е .е с я тем, что блок сравнения содержит (ш) групп узлов сравнения (ш - количество сортируемых чисел), причем -я группа ( = 1 ш) содержит д узлов сравнения, а каждый узел сравнения содержит схему сравнения, два триггера и четыре элемента ИЛИ, причем в каждом узлесравнения выходы больше и меньше схемь. сравнения соединены с первыми входами соответственно первого и второго элементов ИЛИ, выходы которых соединены с информационными входами соответственно первого и второго триггеров, синхровходы которых соединены с тактовым входом блока сравнения, вход начальной установки блока сравнения соединен с первыми входами третьего и четвертого элементов ИЛИ, выходы которых соединены с входами установки в "О" соответственно первого и второго триггеров, выход первоготриггера соединен с вторыми входами первого и четвертого элементов ИЛИ, выход второго триггера соединен с вторыми входами второго и третьего элементов ИЛИ, -й вход блока срав 5156461Если в одном из триггеров 11 и 11 записана единица (например, в триггере 11,), то она проходит через элемент ИЛИ 10 и удерживает триггер 11 в нулевом состоянии, а также устанавливает на выходе элемента ИЛИ 10 сигнал "1".Результаты сравнения с выходов блока 4 сравнения поступают на входымноговходовых сумматоров 12 12, 12 блока 5 дешифрации, причем результаты, сравнения 1-го числа с остальными числами поступают на многовходовые сумматоры 12 ди 12 На выходе многовходового сумматора 12получают число, указывающее, какое количество сортируемых чисел меньше 1-го числа, а на выходе многовходового сумматора 12 , число, ука зывающее, какое. количество сортируемых чисел больше 1-го числа. Инфор-;.ация с выходов 1-го многовходового сумматора 12 ( 1 =, 1, 2 2 ш) поступает на входы 1-го дешифратора 25 13, который при нуле на входах формирует на выходах "1", а при числе на входе, равном 1, на первом, втором, , -ш выходах - "0" при "1" на остальных входах.30В блоке 6 коммутации на информационные входы коммутаторов 15 1515, поступают (ц)-е разряды сбртируемых чисел с выходов регистра,14. Информация с выходов дешифраторов 13 , и 13 разрешает ( 1 )35 илизапрещ-ет ("0") прохождение (ц)-го разряда 1-го числа на выходы коммутаторов 15, 15, 15 Так, 1-е число больше двух чисел сорти 40 руемого массива и меньше трех, то информация с 1-го выхода регистра 14 поступает на выходы коммутаторов 15, 15 . , 15,. Как видно из данного примера, "0" с первых трех выходов дешифратора 13запрещает45 прохождение информации с 1-го информационного входа на выходы коммутаторов 15 - 15, а "0" с первых двух выходов дешифратора 13, запрещает прохождение информации с 1-го инфор 50 мационного входа на выходы коммутаторов 1515 в-На выходах коммутаторов 1515, ., 15 получают (ц) -е разряды просортиро- . ванных чисел, которые поступают на информационные выходы устройства 7. По переднему фронту Р-го тактового импуьса происходит запись ц-х разря 1 6дав сортируемых чисел в регистр 14и запись результатов сравнения втриггеры 11 и 11во всех узлах8 сравнения. Формула изобретения 1. Устройство для сортировки чисел, содержащее блок коммутации,блок дешифрации, блок сравнения, причем информационные входы блока коммутации объединены с соответствующими входами блока сравнения, о тл н ч а ю щ е е с я тем, что, сцелью повышения быстродействиявходы чисел устройства соединены ссоответствующими информационными входами блока коммутации, выходы которого являются выходами отсортированных чисел устройства, а управляющиевходы соединены с соответствующимивыходами блока дешифрации, входы которого соединены с соответствующимивыходами результатов поразрядногосравнения блока сравнения, вход начальной установки которого является входом начальной установки устройства, тактовый вход устройствасоединен с тактовыми входами блокасравнения и блока коммутации,нвния соединен с первым входом -й схемы сравнения групп с х-й по (ш) - ю, (д + 1)-й вход блока сравнения соединен с вторыми входами всех схем сравнения -й группы, выходы первого и второго триггеров -х узлов сравненйя -х групп являются выходами поразрядного сравнения блока сравнения.3, Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блок дешиф - рации содержит 2 н сумматоров и 2 т дешифраторов, причем входы сумматоров являются соответствующими входами блока дешифраций, выходы сумматоров соединены с входами соответствующих де ифраторов 2 ш выходов блока дешифра ии соединены с входом логической ед ницы устройства, выходы дешифраторов являются соответствующими выходами блока дешифрации. 4. Устройство по п. 1, о т л и ч аю щ е е с я тем, что блок коммутациисодержит регистр и в коммутаторов,причем 1-й выход регистра -1ш) соединен с 1-м информационным входом всех коммутаторов, информационные входы регистра являются информационными входами блока коммутации,а синхровход регистра является тактовым входом .блока коммутации, управляющие входы коммутаторов являютсясоответствующими управляющими входамиблока коммутации, выходы коммутаторов являются выходами блока коммутации,