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

(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

Изобретение относится к автоматике и вычислительной технике и може« быть использовано в специализированны вычислительных машинах и устройствах обработки данных. Известно устройство дяя сортировки п-разрядных чисел, содержащее m регистров, регистр результата, m схем сравнения, элемент ИЛИ, переключатель группы злементов И, триггер, узлы запрета и распределитель импульсов 1.4 Недостаток устройства - низкое быстродействие, так как сортировка всего исходного массива чисел требует m(n+1) тактов, где m - количество, an- разрядность )тяруемых чисел. Наиболее близким по технической сущности и достигаенюму результату i изобретению является устройство для сортировки чисел содержащее распределитель импульсов, m решстров, m схем сравнения, группы элементов И, счетчик, суЛматор и регистр результата 2 . : ; Недостатком его является низкое быстродейстйие, так как запись какого-либо числа в регистр результата и сравнение его с остальными числами осущестнпяется поетёдовательно во времени. Цель изобретения - повышение быстродействия устройства путем совмацения во времени операций .записи числа в регистр результат а и сравнения его с другими числами. Поставленная цель достигается тем, что в устройство для сортиройки чисел, содержащее распределитель им пульсов, m регистров, m злементов сравнения, m групп элементов И, сметчик, сумматор,и регистр результата, причем выходы i-ro (,...,m) регистра соединены с первой группой входов i-oro элемента сравнения я с первыми входами элементов И i-ой груп пы, выходы-которой соединены с i-ой группой входов регистра результата,. ,а вторые входы - с i-выходом распределителя импульсов, вход которого является первым управляющим входом устройства, выход i-oro элемента сравнения соединён с 1-м входом счетчика, шходы KOTt Jorto соединены с первой группой входов сумматора/ вторая группа входов которого соединена с группой информационных входов устройства, .а выходы - с первыми входами элемен го19 И первой выходной группы , выходы которых являются первой группой ВЫХОДОВ: устройства, первые входы элементов И второй выходной группы соединены с выходами регистра резуль тата, а выходы являются второй группой выходов устройства, введены отличительные связи - выходы элементов И i-ой группы соединены с (1-1)-ыми группами входов элементов сравнения с первой по (i-l)-yfo и к i-ым группам входов элементов сравнения с )-ой по т-ую. На чертеже приведена схема устрой Устройство содержит распределител импульсов 1, m регистров 2, m элеме тов сравнения 3, группы 4-6 элементо И, счетчик 7, сумматор 8,регистр 9 результата, управляющие входы 10 и 11, группу 12 информационных входов и группы 13 и 14 информационных выходов. Устройство работает следующим образом,. В регистры 2 заносятся сортируе «e числа, в регистр 9 результата нуль, а рарпределитель импульсов 1 устанавливается в начальное состояние (на чертеже не показано). После этого устройство готовоК сортировке чисел в порядке возрастания.На вход 10 .устройства подаются первый тактовый сигнал, по которому появляется иМпульс на первом выходе .распределителя иь11ульсов 1. При этом открывается первая группа элементов И 4, и число из первого регистра 2 переписывается в регистр,9 результата и одновременно с этим,подается на соответствующие группы входов т-.1)-го элемента сравнения 3, где оно сравнивается со всеми сортируе№ши числами. Сигнал на выходах элементов сравнения 3 появляется лишь в том случае, если числа, находящиеся в соответствующем регистре 2, меньше числа, поступаемого на вторые входы элемента сравнения через группы элементов И, Счетчик 7 подсчит вает количество поступающих сигналов с блоков элементов сравнения 3, т,е, подсчитывает количество чисел, которые меньше, чем выделенное распределителем импульсов 1 и записанного в регистр 9 результата. Это число поступает на первую группу входов сумматора 8, а на его вторую группу вхо дов - код адреса области памяти, начиная с которого необходимо разместить отсортированный массив чисел. Тогда адрес области памяти, по которому следует записать число, находящееся в регистре 9 результата, определяется, как А N, где .адрес области памяти, начингш с Кото рого необходимо размертить отсортированные числа; N - количество чисел меньших чигла, записанного в регистре 9 результата, Сумматор 8 вычисляет сумму , По сигналу на управляющем входе 11 устройства, число, находящеес в ре-гистре 9 результата, переписывается в запоминаищее устройство по адресу, находящемуся в сумматоре 8. Следу - . щий такт, работы устройства начинается с подачи следующего тактового сигнала на вход 10 устройства. Приэтом появляется импульс на следующем выходе рас пределителя импульсов 1, который откр:лвает следующую группу 4 элементов И, вследствие чего в регистр 9 результата переписывается число из следующего регистра 2 группы и одновременно с этим осуществля ется сравнение этого числа с остальными числами. В дальнейшем устройство работает так, как описано выше. Для сортировки чисел в порядке убывания необходимо в регистры 2 записать инверсные коды сортируемых чисел. Таким образом, предлагаемое устройство по сравнению с прототипом обладает, более высоким быстродействием, так как операции записи числа в регистр результата и сравнения его с другими числами совмещены во времени. Формула изобретения Устройство для сортировки чисел, содержащее распределитель импульсов, m регистров, m элементов сравнения, m групп элементов И, счетчик, cyMMeiтор и регистр результата, причем выходы i-ro С ,,..,m) регистра соединены с первой группой входов i-ro элемента сравнения и с первыми входами элементов И i-й группы, выходы которых соединены с i-гй группой входов регистра результата, а вторые входы - с i-M выходом распределителя импульсов, вход которого является первЕлм управляющим входом устройства, выход i-ro элемента сравнения соединен с 1-м входом счетчика, выходы которого соединены с первой группой входов сумматора, вторая группа входов которого соединена с группой информационных входов устройства,, а выходы - с первыми входами элементов И первой выходной группы, выходы которых являются первой группой выходов устройства, а первые входы элементов И второй выходной группы соединены с выходами регистра результата , а выходы являются второй группой выходов устройства, отличающееся тем, что, с целью повышения быстродействия, выходы элементов И i-й группы соединены с (i-1)-ми группами входов элементов сравнения с первого по (i-1)-й и с i-MH группами входов элементов сравн.ения с (i + 1)-ro по т-й.

Источники информации, 1финятые во внимаййе при экспертизе

: 2. Авторское свидетельство СССР

|ПО заявке 2893485/18-24,

кп. G 06 F 7/06, 10.03.80 .(протЪ.ТИ1 .

I I

&