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

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее п регистров, п групп элементов И-ИЛИ, о т л и ч аю ад е вся тем, что, с целью повышения быстродействия, устройство содержит п элементов И первой группы , п элементов задержки, (п-1) элемент И второй группы, схемы сравнения , причем входная шина устройства соединена поразрядно с первыми входами схем сравнения и первыми входами групп элементов И-ИЛИ, вторые входы Г-ой схемы сравнения поразрядно соединены.с выходами i-го регистра, где ,. .;. , п , п число сравниваемых чисел, выходы j-ro регистра поразрядно соединены с вторыми входами элементов И-ИЛИ (+1)-ой группы, где ,..., п-1, выходы элементов И-ИЛИ i-ой группы соединены с срответствующими разрядами i-ro регистра, вход .управления сравнения устройства соединен с . входом первого элемента задержки и первыми входами п-го элемента И первой группы и( И-17-го элемента И второй группы, выход k-ro Элемента задержки соединен с первьми входами (H-.k)-ro элемента И первой группы и (n-k-t)-ro элемента И второй группы, где ,...,п-1, выход i-ro элемента И первой группы соединены с третьими входами элементов И-ИЛИ 1-ой группы, где i 2,. . . ,| , выход первого элемента И первой группы соединен с вторыми входами элементов (Л И-ИЛИ первой группы, выход ) -го элемента И второй группы соединен с четвертыми входами элементов И-Ир (J группы, j 1,..., n-l, первый выход К-ой схемы сравнения сое .динен с вторыми входами -ък эЛементов И первой и второй групп, где k 1,..., И-1, второй вход /-ой схемы сравнения соединен с третьим входом ( элемента И первой со ю группы (j 1,... , VI -1 К О)

СОО3 G08ETCHHX

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК ае (и) 9 УР G F 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСНОМУ СОИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3422917/18-24 (22) 22.02.82 (46). 23.08.83, Бюл. Р 31 (72) Н.И.Крылов и В.В;Соколов (53) 681.325 (088.8) (56) 1..Авторское свидетельство СССР

Р 478303, кл. G 06 F 7/04, 1973.

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

Р 826339, кл. G 06 F 7/06, 1979 (прототип)..(54) (57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ., содержащее и регистров, и групп элементов И-ИЛИ, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия, устройство содержит п элементов И первой группы, я. элементов. задержки, (n-1), элемент И второй группы, схемы сравнения, причем входная шина устройства соединена поразрядно с первыми входами схем сравнения и первыми входами групп элементов И-ИЛИ, вторые входы i-ой схемы сравнения поразрядно соединены.с выходами

i-го регистра, где i=i, . ., n, n число сравниваемых чисел, выходы

j-го регистра поразрядно соединены с вторыми входами элементов И-ИЛИ (j+1) -ой группы, где j =1...,, n-1, выходы элементов И-ИЛИ I-ой группы соединены с срответствующими разрядами i-ro регистра, вход управления сравнения устройства соединен с входом первого элемента задержки . и первыми входами и -ro элемента И первой группы и(й-1)-ro элемента И второй группы, вьмод k-го элемента задержки соединен с первыми входами (И-k) -ro элемента И первой группы и (n -k-1)-ro элемента И второй группы, где k--1,..., n -1, выход i-ro элемента И первой группы соединены с третьими входами элементов И-ИЛИ

1-ой группы, где 1=2,...,в, выход первого элемента И первой группы щ

O соединен с вторыми входами элементов

И-ИЛИ первой группы, выход y --ro элемента И второй группы соединен с четвертыми входами влемеитов И-Иды (y +Ц вЂ”.ой группы, 1 =1,..., И -1, первый выход К -ой схемы сравнения сое- ,динен с вторыми входами k-ых элементов. И первой и второй групп, где

К =1,..., g -1, второй вход j -ой схемы сравнения соединен с третьим 4® ) входом (3+Ц-го элемента И первой ф группы (j =1,..., .И -1 ) .

1037246

Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации технических средств 3BN и создании .устройств обработки статистической ин формации.

Известно устройство для сортировки чисел,.содержащее и кольцевых регистров сдвига, входы которых соединены между собой и подключены к входной шине устройства, прямые выходы всех кольцевых регистров сдвига соединены с входами первой схемы ИЛИ и с одним из входов соответствующей схемь равнозначности а инверсные. выходы †. с входами второй схемы ИЛИ, выходы схем ИЛИ подключены ко входам схемы И, второй вход каждой из схем равнозначности соединен с шиной управления, а управляющие входы подключены к выходу схемы И, выходы схем равнозначности связаны со входами сброса соответстьующих кольцевых регистров. сдвига (13.

Недостаток этого устройства заключается в том, что оно имеет ограниченные функциональные возможности так как позволяет определять только экстремальные числа из и сравниваемых чисел с потерей информации о значениях остальных чисел.

Наиболее близким к предлагаемому является устройство для сортировки. чисел, содержащее n кольцевых регистров, управляющие элементы И-HJIH входные элементы И-ИЛИ, дешифраторы, счетчики, элементы ((, ИЛИ, регистр, узел синхронизации, первый выход которого соединен с установочными входами кольцевых регистров, с управляющим входом схемы сравнения и со входом первого счетчика, выходы которого подключены ко входам первого дешифратора и с установочными входами второго счетчика, выходы которого соединены со входами второго дешифратора, каждый (-ый выход первого дешифратора, где 1 =1,2,..., И -1) соединен с -ым входом первого управляющего элемента И-ИЛИ и с первым входом < -ro входного элемента И-ИЛИ, выХод каждого s --ro входного элемента И-ИЛИ подключен ко входу j -го кольцевого регистра, выход каждого -го кольцевого регистра соединен с ) +(.И -1)-ым входом первого управляющего элемента И-ИЛИ, выход которого подключен к первому информационному входу схемы сравнения и к первому входу первого элемента И, выход которого соединен с первым установочным входом регистра, первый выход которого подключен ко вторым входам 1, 2,...,(и -1) -го входных элементов И-ИЛИ, каждый 1 -ый выход второго дешифратора соединен

65

Цель изобретения — повышение быстродействия работы устройства.

Поставленная цель достигается тем, что устройство для сортировки чисел, содержащее Vl регистров, групп элементов И-ИЛИ, содержит h. элементов И первой группы, И элементов задержки, И -1 элемент И второй группы, схемы сравнения, причем входная шина устройства соединена поразрядно с йервыми входами схем сравнейия и первыми входами групп элементов И-ИЛИ, вторые входы (-й схемы сравнения поразрядно соединены с выходами -го регистра, где

> =1,...,и,И вЂ” число сравниваемыми чисел, вы<оды )-го регистра поразрядно соединены с вторыми входами элементов И-HJGi (g +1)-ой группы, где 1 =1,..., И -1, выходы элементов И-ИЛИ (-й группы. соединены с соответствующими разрядами 1 -го регистра, вход управления сравнения с 1 -ым входом второго управляющего элемента И-ИЛИ, каждый ) -йй выход второго дешифратора, где 1 =1,2,..., (» -2), подключен к третьим входам

+1 -го входного элемента И-ИЛИ

I (И-1)-ый выход второго дешифратора соединен с первым входом И-го входного. элемента И-ИЛИ, выход которого соединен со входом и -ro кольцевого регистра, выход которого подключен к

10 М-му входу второго управляющего элемента И-ИЛИ, выход каждого К-го кольцевого регистра, где К =2,..., ..(tt -1), соединен с К +(и-1) входом второго управляющего элемента И-ИЛИ, 15 выход которого подключен ко второму .информационному входу схемы сравне-, ния и к первому входу второго элемента И, выход которого соединен со вторым установочным входом регистра, второй вход которого подключен к четвертым входам 2,3,...,(и-1) входных элементов И-ИЛИ и ко второму входу n-ro элемента И-ИЛИ, первый выход схемы сравнения соединен со вторыми входами элементов И, с первым управляющим входом узла синхро низации, второй выход которого подключен к информационному входу регистра и ко вторым установочным входам кольцевых регистров, второй выход схемы сравнения соединен с первым входом элемента ИЛИ, второй ..вход которого подключен к третьему выходу узла синхронизации, а выход к информационному входу второго счетчика, выход которого соединен со вторым управляющим входом узла синхронизации (2 .

Недостаток известного устройства заключается в.том, что оно имеет

40 низкое быстродействие, обусловленное тем, что сортировка чисел осуществляется за И /2 тактов.

1037246 устройства соединен с входом первого элемента .задержки и первыми входами и -ro элемента И первой группы и(и-1)-го элемента И второй группы, выход K-ro-элемента задержки соединен с первыми входами .(И -K,)-го элемента И первой группы и (й- I(-3-)ro элемента И второй группы, где к=1,..., й-1, выход 1-го элемента И.первой группы соединены с третьими входами элементов И-ИЛИ 10

1 -ой группы, где 1 =2,..., И, выход первого элемента И первой группы соединен с вторыми входами элементов И-ИЛИ первой группы, выход j --го элемента И второй группы соединен с 15 четвертыми входами элементов И-ИЛИ (j+1) -ой группы, =1,..., и -1, пер вый вход К-ой схемы сравнения соединен с вторыми входами К-ых элементов И первой и. второй группы, где

l< =1,..., и-1, второй выход j -ой схемы сравнения соединен с третьим входом () +1)-ro элемента И первой группы (1=1,..., И -1) .

На чертеже представлена блок-схе ма предлагаемого устройства.

Устройство содержит и схем 1 сравнения, И регистров 2, группы эле- . ментов И 3, 4, д групп элементов

И-ИЛИ 5 и(Й-1) элементы 6 задержки.

Устройство работает следующим образом.

В исходном состоянии во все регистры 2 записаны нули.

Для удобства описания работы устройства рассмотрим поступление на его информационный вход 7 следующих друг за другом чисел Х4 = 70, Х =110, Х = 110, ".4 =105, охватывающих все возможные случаи соот- . ношений как значений, так и последо- 40 вательности их постуйления на вход устройства.

При приходе первого числа Х и

его поступлении на первые входй .схем

1 сравнения, .вследствие подачи с вы- 45 ходов регистров 2: на вторые входы схем 1 сравнения нулевых потенциалов, с первых Выходов схем 1 сравнения подается разрешаюций потенциал на элемент И З.Поданный на клеммУ 8 сит -,50 нал поступит на и-ые элементы И 3 и

И 4. Пройдя у-ый элемент И 3, сигнал поступит на четвертые входы и -ой . группы элементов И-ИЛИ 5, осуцествляя перепись информации из(и-1) -го регистра в р -ый регистр 2.Перезапись информации из 1-го регистра 2 (1 = — 1,2,..., р-1) в (1 +1)-ый регистр 2 осуществляется аналогично, т.е.. подобно работе сдвигового регистра.

Элементы 6 задержки служат для устой-60 чивости и надежности работы устройства. Пройдя все элементы 6 задержки и поступив на первый элемент И 4, поданный на клемму. 8 сигнал разрешает запись первого числа в первый регистр 2.

При появлении на информационном входе числа Х на первьж выходах схем

1 сравнения появится единичный сигФ нал, поскольку второе число Х< больше чисел, записанных в регистре 2;

Управляющий импульс, поступивший на вход 8, разрешает перезапись чисел из j -го регистра в (и-1) регистр 2 ° В результате.в первом регистре 2 будет записано число. Х 2

110, во втором — число Х„= 70.

При поступлении третьего числа

Х>--110 на первых выходах схем 1 сравнения также появится единичный сигнал, так как поступившее очередное число не меньше чисел, записанных в регистрах 2. Управляющий импульс, поступивший на вход 8, осуществляет перепись информации из

q -ro регистра .2 в (a1)-ый регистр 2, а в первый регистр заПишется чис-.

ХЗ °

При поступлении четвертого числа

Х = 105 на втором выходе первой и второй схем 1 сравнения и на первых выходах остальных схем сравнения появится единичный сигнал, открываю.— щий третий элемент И 5 и все элементы И 3 кроме двух первых . При поступлении управляюцего импульса на вход 8 информация перепишется из j-го регистра 2 в () +1) -ый ре1 гистр 2 =3,4,..., )> -1, а в -третий регистр запишется исло Х . .Таким образом, в первом регистре будет записано максимальное число из чисел, поступивших .на вход устройства, т.е. 110, во .втором также — 110, в третьем — 105, в чет-. вертом — 70. Далее устройство работает аналогично.

Таким образом, поступающие числа записываются в регистры 2 в порядке убывания. Для того, чтобы числа записать в порядке возрастания, достаточно, поменять выходы схем сравнения или подавать числа в обратном коде на схемы сравнения.

Предлагаемое устройство обладает большим быстродействием,чем известное устройство. В предлагаемом устройстве поступающее число одновременно сравнивается с числами, записанными в запоминающих регистрах, и осуцествляется одновременный сдвиг и запись числа, поступившего на вход устройства,. в порядке убывания (возрастания).

Дпя упорядочения массива чисел в известном устройстве требуется И /2 тактов работы, тогда как предлагаемое устройство обеспечивает сорти-. ровку чисел за И тактов работы.

103724б . Составитель A.Ñóýäàëåí

Редактор Г. Волкова Техред А. Бабинец Корректор A.Èëüèè

Закаэ 6011/50 Тирж 706 Подписное

ВНИИПИ Государственного комитета СССР по делам иэобретений и открытий

113035, Москва, И-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Уч<город, ул. Проектная, 4