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

Изобретение относится к автомати ке и вычислительной технике и может быть использовано при реализации технических средсгв ЭВМ и создании .устройств обработки статистической формации. . Известно устройство для сортиров ки чисел, содержащее и кольцевых регистров сдвига, входы которых соединены между собой и подключены к входной шине устройства, прямые выходы всех кольцевых регистров сдвига соединены с входами первой схемы ИЛИ и с одним из входов соответствующей схемы равнозначности а инверсные, выходы - с входами второй схемы ИЛИ, выходы схем ИЛИ подключены ко входам схемы И, второй вход каждой из схем равнозначности соединен с шиной управления, а управляющие входы подключены к выходу схемы И, выходы схем равнознач ности связаны со входами сброса соответствующих кольцевых регистров. сдвига и 13. Недостаток этого устройства закл чается в том, что .оно имеет с граниченные функциональные возмояшости так как позволяет определять только экстремальные числа из и срав ваемых чисел с потерей -информации о значениях остальных чисел. Наиболее близким к предлагаемому является устройство для сортировки чисел, содержащее v кольцевых регистров, управляющие элементы И-ИЛИ входные элементы -И-ИЛИ, дешифраторы счетчики, элементы И, ИЛИ/ регистр узел синхронизации, первый выход которого соединен с установочными входами кольцевых регистр.ов, с управляющим входом схемы сравнения и со входом первого счетчика, выходы которого подключены ко входам первого дешифратора и с установочными входами второго счетчика, выходы которого соединены со входами второго дешифратора, каждый -i-ый выхо первого дешифратора, где i 1,2,., In -1) соединен с i -ым входом первого управляющего элемента И-ИЛИ и с первым входом i-го входного элемента И-ИЛИ, каждого -i-го входного элемента И-ИЛИ подключен к входу i-го кольцевого регистра, вы ход каждого 1 -го кольцевого регистр соединен с -1+Си-1)-ым входом перво управляющего элемента И.-ИЛИ, выход которого подключен к первому инфор мационному входу схемы сравнения к первому входу первого элемента И выход которого соединен с первым установочным входом регистра, первый выход которого подключен ко вто рым входам 1, 2,...,(м -1)-го вход ных элементов И-ИЛИ, каждый i ый выход второго дешифратора соединен с 1 -ым входом второго управляющего элемента И-ИЛИ, каждый /-ий выход второго дешифратора, где i 1,2,,.., {и-2), подключен к третьим входам j +1 -го входного элемента И-ШШ ( и-1)-ый выход- второго дешифратора соединен с первым входом V-го входного, элемента И-ИЛИ, выход которого соединен со входом и-го кольцевого регистра, выход которого подключен к И-му входу второго управляющего элемента И-ИЛИ, выход каждого К-го кольцевого регистра, где К 2 ,.,., (n-l), соединен с К -ьСи-1) входом второго управляющего элемента И-ИЛИ, выход которого подключен ко второму информационному входу схемы сравне- . нйя и к первому входу второго элемента И, которого соединен со вторым установочным входом регистра, второй вход которого подключен к четвертым входам 2,3, . . ., 1и-1) входных элементов И-ИЛИ и ко второму входу и-го элемента И-ИЛИ, первый выход схемы сравнения соединен со вторыми входами элементов И, с первым управляющим входом узла синхронизации, второй выход которого подключен к информационному входу регистра и ко вторьвл установочным входам кольцевых регистров, второй выход схемы сравнения соединен с первьж1 входом элемента ИЛИ, второй .вход которого подключен к третьему выходу узла синхронизации, а выход к информационному входу второго счетчика, выход которого соединен со вторым управляющим входом узла синхронизации 2. Недостаток известного устройства заключается в.том, что оно имеет низкое быстродействие, обусловленное тем, что.сортировка чисел осуществляется за VIV2 TaiKTOB. Цель изобретения - повышение быстродействия работы устройства. Поставленная цель достигается тем, что устройство для сортировки чисел, содержащее И регистров, групп элементов И-ИЛИ, содержит п, элементов И первой группы, и элементов задержки, и-1 элемент И второй группы, схегМ сравнения,причем выгодная шина устройства соединена поразрядно с первыми входгими схем сравнения и первыми входами групп элементов И-ИЛИ, вторые входы 1-й схемы сравнения поразрядно соединены с выходами 1 -го регистра, где 1 1, ... ,И,И - число сравниваемых чисел, выходы -го регистра поразрядно соединены с вторыми входами элементов И-ИЛИ ( j+1 )-ой группы, где -} 1,. .., И -1, выходы элементов И-ИЛИ л-и группы, соединены с соответствующими разрядами i -го регистра,вход управления сравнения устрюйства соединен с входом первого элемента .задержки и nepat /iM входами и-го элемента Н первой группы и(и-1)-го элемента и второй группы, выход К-го-элемента задержки соединен с первыми входами -(и -К.)-го элемента Н первой группы и ()го элемента И второй группы, где. ,,.., и-1, выход 1-го элемента Н.первой группы соединены с третьими входами элементов И-ИЛИ i -ой группы, где i 2,..,,И , выход первого элемента И первой группы соединен с вторыми входами элементов И-ИЛИ первой группы, выход i -го элемента И второй группы соединен с четверт1 ла входами элементов П-ИЛИ t-j +1) -ой группы, .J ,,.., и -1, пер вый вход К-ой схемы сравнения соеди нен с вторыми входами К-ых элементов И первой и. второй группы, где К 1, .. ., и -1, второй выход ) -ой схемы сравнения .соединен с третьим входом (.J ч-1)-го элемента И первой группы (,. .., И-1) . - На чертеже представлена блок-схе ма предлагаемого устройства. Устройство содержит и схем 1 сра нения, И регистров 2, группы эле- . ментов ИЗ, 4, и групп элементов И-ИЛИ 5 и(11-1) элементы 6 задер;1б и Устройство работает следующим образом./ В исходном состоянии во все регистры 2 записаны нули. Для удобства описания работы уст ройства рассмотрим поступление на его информационный вход 7 следующих друг за другом чисел Х 7.0,. , Хз 110, , охватывающих все возможные случаи соотношени.й как значений, так и последо вательности их поступления на вход устройства. При приходе первого числа Х и его поступлении на первые входы .схе 1 сравнения, .вследствие подачи с вы ходов регистров 2: на вторые входы схем 1 сравнения нулевых потенциало с первых йыходов схем 1 сравнения подается разрешающий потенциал на элемент И 3.Поданный на клемму 8 си нал поступит на п-ые элементы И 3 и И 4. Пройдя 1-ый элемент И 3, сигна поступит на четвертые входы ц ой группы элементов И-1ШИ 5, осуществляя перепись информации из .(и-) -го регистра в п-ый регистр 2.Перезапис информации из 1-го регистра 2 (i 1,2,..., п-1) в (1Ч-1)-ый регистр осуществляется аналогично, т.е. подобно работе сдвигового регистра. Элементы б задержки служат для усто чивости и надехсности работы устройства . Пройдя все элементы 6 задержки и поступив на первый элемент И поданный на клсм/лу 8 сигнал разрешает запись первого числа в первый ре истр 2. При появлении на информационном входе числа Х на первых выходах схем 1 сравнения появится единичный сигнал, поскольку второе число Х больше чисел, записанных в регистре 2, Управляющий и шульс, поступивший на вход 8, разрешает перезапись чисел из i-го регистра в (1) регистр 2. В результатев .первом регистре 2 будет записано число. Х, 110,-во втором - число Х 70. При поступлении третьего Х,,110 на перВЕлх выходах схем 1 сравнения также появится единичный сигнал, так как поступившее очередное число неменьше чисел, записанных в регистрах 2. Управляющий импульс, поступивший на вход 8, осуществляет перепись информации из . . -го регистра -2 в {н-1)-ый регистр 2, а в первый регистр запишется число ХзПри поступления четвёртого числа Хд 105 на втором выходе первой-и второй схем 1 сравнения и на первых вьлходах остальных схем сравнения появится единичный сигнал, открываю.щий третий. элемент И 5 и вс.е элементы И 3 к роме двух первых.- При поступлении управляющего импульса на вход 8 информация перепишется из :j-го регистра 2 в (/+1)-ый регистр 2 / J 3,4,..., П-1/, а в третий регистр запишется Число Х . Таким образом, в первом регистре будет, записано максимальное число из чисел, поступивишх на вход устройства, т..е. 110, во .втором такхсе - 110, в третьем - 105, в четвертом - 70. Далее устройство работает аналогичноТ Таким образом, поступающие числа записываются в регистры 2 в порядке убывания. дАя того, чтобы числа записать в порядке возраста.ния, достаточно . поменять выходы схем сравнения или подавать числа в обратном коде на схемы сравне- . ния. Предлагаемое устройство обладает большим быстродействием,чем известное устройство. В предлагаемом устройстве поступающее число одновременно сравнивается с числами, записанными в запоминающих регистрах, и осуществляется одновременный сдвиг и запись числа, поступившего на вход устройства, в порядке убывания (возрастания). ля упорядочения массива чиселв известном устройстве требуется тактов работы, тогда как предлагаеое устройство обеспечивает сорти-. овку чисел за и тактов работы.

t о о7

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее п регистров, п групп элементов И-ИЛИ, о т л и ч аю ад е вся тем, что, с целью повышения быстродействия, устройство содержит п элементов И первой группы, п элементов задержки, (п-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 К О)