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

(22) Заявлено 10.12. 80 (21) 3214008/18-24 РЦМК з С Об Р 7/Об сприсоединениемзаявки ЖГосударстатениый комитет СССР по делам изобретений и открытийДата опубликования описания 1512.82(71) Заявитель РОЙС 54 СОРТИРОВКИ ЧИСЕЛ Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных.Известно устройство для сортировки и-разрядных чисел, содержащее а регистров, регистр . результата,щ схем сравнения, элемент ИЛИ, переключатель группы элементов И, триггер, узлы запрета и распределитель импульсов Щ .Недостаток устройства - низкое бы стродействиб, так как сортировка всего исходного массива чисел требует ав+1) тактов, где щ - количество, а и - разрядность сортируемых чисел.Наиболее близким по технической сущности и достигаемому результату к изобретению является устройство для. сортировки чисел, содержащее распределитель импульсов, а регистров, а схем сравнения, группы элементов И,счетчик сущматор и регистр результата 2.; Недостатком его является низкое быстродействие, так как запись како го-либо числа в регистр результата и сравнение его с остальными числа-: ми осуществляется последовательно во времени. Цель изобретения - повышение быст-,родействия устройства путем совмещения во времени операций записи числав регистр результата и сравнения егос другими числами.Поставленная. цель достигается тем,что в устройство для сортироки чисел, содержащее распределитель им10 пульсов, щ регистров, щ элементовсравнения, а групп элементов И, счетчик, суюатор,.и регистр результата,причем выходы 1-го 1.в .1а) регистра соединены с первой группой входов 1-ого элемента сравнения л сервыми входами элементов И 1-ой группы, выходы- которой соединены с 1-ой,а вторые входы - с 1-выходом распре делителя импульсов, вход которогоявляется первым управляющим входомустройства, выход 1-ого элемента сравнения соединен с 1-и входом счетчика, выходы которогЬ соединены спервой группой входов сумматора, вто рая группа входов которого соединенас группой информационных входов устройстваа выходи - с.первыми входамиэлементов И первой выходной группы,выходы которых являются первой группой выходов устройства, первые входыэлементов И второй выходной группы соединены с выходами регистра результата, а выходы являются второй группой выходов устройства, введены отличительные связи - выходы элементов И 1-ой группы соединены с (1- 1) -ыми группами входов элементов сравнения с первой по (1-1)-ую и к 1-ым группам входов элементоз сравнения с (1+1)-ой по а-ую,На чертеже приведена схема устрой 10 ства.Устройство содержит распределитель импульсов 1, в регистров 2, а элементов сравнения 3, группы 4-б элементов И, счетчик 7, сумматор 8,регистр 9 результата, управляющие входы 10 и 11, группу 12 информационных входов и группы 13 и 14 информационных выходов.Устройство работает следующим образом. 25 30 Э 5 40 Формула изобретения 5560, х-ми группами входов элементов срав 65 нения с (1+1)-го по а-й. В регистры 2 заносятся сортируеже числа, в регистр 9 результата- нуль, а распределитель импульсов 1. устанавливается в начальное состояние (на чертеже не показано). После этого устройство готово к сортировке чисел в порядке возрастания.На вход 10 устройства подаются первый тактовый сигнал, по которому появляется импульс на первом выходе,распределителя игйульсов 1. При этом открывается первая группа элементов И 4, и число из первого регистра 2 переписывается в регистр.9 результата и одновременно с этим, подается на соответствующие группы входов (в)-го элемента сравнения 3, где оно сравнивается со всеми сортируегыми числами. Сигнал на выходах элементов сравнения 3 появляется лишь в том случае, если числа, находящиеся в соответствующем регистре 2 меньше числа, поступаемого на вторые входыэлемента сравнения через группы элементов И. Счетчик 7 подсчитг;вает количество поступающих сигналов с блоков элементов сравнения 3, т,е.подсчитывает количество чисел, которые меньше, чем выделенное распреде"лителем импульсов 1 и записанного врегистр 9 результата. Это число поступает на первую группу входов сумматора 8, а на его вторую группу входов - код адреса области памяти, начиная с которого необходимо разместить отсортированный массив чисел. Тогда адрес областн памяти, по которому следует записать число, находящееся в регистре 9 результата, определяется, как А = Ансгц+ М, где Анац, адрес области памяти, начиная с Которого необходимо размертить отсорти" рованные числа; Х - количество чисел,меньших числа, записанного в регистре 9 результата. СумматОр 8 вычисляет суМму Анди+1. По сигналу на управляющем входе 11 устройства, число, находящееся в ре" гистре 9 результата, переписывается в запоминакщее устройство по адресу, находящемуся в сумматоре 8Следугощий такт, работы устройства начинается с подачи следующего тактового сигнала на вход 10 устройства. При этом появляется импульс на следующем выходе распределителя импульсов 1, который откр.гвает следующую группу 4 элементов И, вследствие чего в регистр 9 результата переписывается число из следукщего регистра 2 группы и одновременно с этим осуществля-. ется сравнение этого числа с остальными числами. В дальнейшем устройство работает так, как описано выае. Для сортировки чисел в порядке убывания необходимо в регистры 2 записать инверсные коды сортируемюх чисел.Таким образом, предлагаемое устройство по сравнению с прототипом обладает более высоким быстродействием, так как операции записи числа в регистр результата и сравнения его с другими числами совмещены во времени. Устройство для сортировки чисел, содержащее распределитель импульсов, в регистров, в элементов сравнения, в групп элементов И, счетчик, сумМатор и регистр результата, причем выходы .1-го (1=1в) регистра соединены с первой группой входов 1-го элемента сравнения и с первыми входами элементов И 1-й группы, выходы которых соединены с 1-.й т;руппой входов регистра результата, а вторые входы - с 1-м выходом распределителя импульсов, вход которого является первым управляющим входом устройства, выход 1-го элемента сравнения соединен с 1"м входом счетчика, выходы которого соединены с первой группой входов сумматора, вторая группа входов которого соединена с группой информационных входов устройства, а выходы - с первыми входами элементов И первой выходной группы, выходы которых являются первой группой выходов устройства, а первые входы элементов И второй выходной группы соединены с выходами регистра результата, а выходы являются второй группой выходов устройства, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, выходы элементов И 1-й группы соединены с (1-1)-ми группами входов элементов сравнения с первого по (1-1)-й и с981988 Составител ТехредМ.Г тин редактор Гираж 731осударстве нного комиам изобретений и открысква, Ж, Раушская Эаказ 9712/ д. 4/ П фНатентф, г. Ужгород, ул. Проектн фил Источники информации,принятые во внимание при .экспертизе1. Авторское свидетельство СССР9 526888, кл, 6 06 Р 7/00, 1974. ВНИИПИ Г по дел 113035, Мо2. Авторское свидетельство СССРпо заявке 9 2893485/18-24,кл. С 06 Р 7/06 10.0380 4 прототи 4 .