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

.ЯО,б Г 706 ГОСУДАРСТВЕННЫЙ ПО ДЕЛАМ ИЗОБРЬ ИТЕТ СССР И ОТНРЬ,(54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИЧИСЕЛ., содержащее и регистров, игрупп элементов И-ИЛИ, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия, устройствосодержит и элементов И первой группы, и. элементов. задержки, (и),элемент И второй группы, схемы сравнения, причем входная шина устройства соединена поразрядно с первымивходами схем сравнения и первымивходами групп элементов И-ИЛИ, вторые входы -ой схемы сравненияпоразрядно соединены,с выходами1-го регистра, где 1=1 , и, ичисло сравниваемых чисел, выходы)-го регистра поразрядно соединеныс вторыми входами элементов И-ИЛИ+1)-ой группы, где )=1 и, выходы элементов И-ИЛИ 1-ой группы соединены с срответствующими разрядами 1-го регистра, вход управления сравнения устройства соединен с входом первого элемента задержки .и первыми входами и -го элемента И первой группы и(й)-го элемента И второй группы, вьмод Е-го элемента задержки соединен с первыми входами (Ис)-го элемента И первой группы и (и -1 с)-го элемента И второй группы, где 1=1 и -1, выход 1-го элемента И первой группы соединены с третьими входами элементов И-ИЛИ 1-ой группы, где 1 =2 и, выход первого элемента И первой группы ЕС соединен с вторыми входами элементов И-ИЛИ первой группы, выход-го элемента И второй группы соединен с четвертыми входами влемеитов И-ИдИ С ( +Ц - .ой группы,=1 И -1, первый выход К -ой схемы сравнения сое,динен с вторыми входами 1-ых эЛементов. И первой и второй групп, где К=1И, второй вход -ой схемы сравнения соединен с третьим входом+Ц -го элемента И первой группы ( =1 й -1).Изобретение относится к автоматике и вычислительной технике и можетбыть использовано при реализации технических средств ЭВИ и создании .устройств обработки статистической ин формации.Известно устройство для сортировки чисел, содержащее и кольцевых регистров сдвига, входы которых соединены между собой и подключены к входной шине устройства, прямые выходы всех кольцевых регистров сдвига соединены с входами первой схемы ИЛИ и с однимиз входов соответствующей схемьравнозначности а инверсные. выходы в . с входами второй схемы ИЛИ, выходы схем ИЛИ подключены ко входам схемы И, второй вход каждой из схем равнозначности соединен с шиной управления, а управляющие входы подключены к выходу схемы И, выходы схем равнозначности связаны со входами сброса соответстьующих кольцевых регистров. сдвига11,Недостаток этого устройства заключается в том, что оно имеет ограниченные функциональные возможности так как позволяет определять только экстремальные числа из и сравниваемых чисел с потерей информации о значениях остальных чисел. Наиболее близким кпредлагаемому является устройство для сортировки, чисел, содержащее и кольцевых регистров, управляющие элементы И-ИЛИ, входные элементы И-ИЛИ, дешифраторы, счетчики, элементы И, ИЛИ, регистр, узел синхронизации, первый выход которого соединен с установочными входами кольцевых регистров, с управляющим входом схемы сравнения и со входом первого счетчика, выходы которого подключены ко входам первого дешифратора и с установочными входами второго счетчика, выходы которого соединены со входами второго дешифратора, каждый 1-ый выход первого дешифратора, где=1,2 И -1) соединен с-ым входом первого управляющего элемента И-ИЛИ и с первым входом 1 -го входного элемента И-ИЛИ, выХод каждого-го входного элемента И-ИЛИ подключен ко входу 1 -го кольцевого регистра, выход каждого 1 -го кольцевого регистра соединен с ) +И -1)-ым входом первого управляющего элемента И-ИЛИ, выход которого подключен к первому информационному входу схемы сравнения и к первому входу первого элемента И, выход которого соединен с первым установочным входом регистра, первый выход которого подключен ко вторым входам 1, 2(и -1) -го входных элементов И-ИЛИ, каждый 1-ый выход второго дешифратора соединен45 50 55 60 65 Цель изобретения - повышение быстродействия работы устройства,11 оставленная цель достигаетсятем, что устройство для сортировкичисел, содержащее И регистров,групп элементов И-ИЛИ, содержит И,элементов И первой группы, И элементов задержки, И -1 элемент И второй группы, схемы сравнения, причемвходная шина устройства соединенапоразрядно с йервыми входами схемсравнейия и первыми входами группэлементов И-ИЛИ, вторые входы-йсхемы сравнения поразрядно соединены с выходами-го регистра, где) =1, , и,И - число сравниваемьвсчисел, вью:оды )-го регистра поразрядно соединены с вторыми входамиэлементов И-ИЛИ+1)-ой группы,где=1 И, выходы элементов И-ИЛИ )-й группы. соединены ссоответствующими разрядами 1 -горегистра, вход управления сравнения с 1 -ым входом второго управляющегоэлемента И-ИЛИ, каждый ) -йй выходвторого дешифратора, где 1 =1,2(И)-ый выход второго дешифраторасоединен с первым входомИ-го входного. элемента И-ИЛИ, выход которогосоединен со входом и -го кольцевогорегистра, выход которого подключен к 10 М-му входу второго управляющегоэлемента И-ИЛИ, выход каждого К-гокольцевого регистра, где К =2.(й -1, соединен с К +1,И) входомвторого управляющего элемента И-ИЛИ, 15 выход которого подключен ко второмуинформационному входу схемы сравне-,ния и к первому входу второго элемента И, выход которого соединен совторым установочным входом регистра, второй вход которого подключенк четвертым входам 2,3и) входных элементов И-ИЛИ и ко второмувходу и-го элемента И-ИЛИ, первыйвыход схемы сравнения соединен совторыми входами элементов И, с первым управляющим входом узла синхронизации, второй выход которого подключен к информационному входу регистра и ко вторым установочным входам кольцевых регистров, второйвыход схемы сравнения соединен спервым входом элемента ИЛИ, второйвход которого подключен к третьемувыходу узла синхронизации, а выходк информационному входу второго 35 счетчика, выход которого соединенсо вторым управляющим входом узласинхронизации 1 2.Недостаток известного устройствазаключается в.том, что оно имеет 40 низкое быстродействие, обусловленное тем, что сортировка чисел осуществляется за И/2 тактов.устройства соединен с входом первого элемента .задержки и первымивходами и -го элемента И первойгруппы и(и)-го элемента И второйгруппы, выход К-го.элемента задержки соединен с первыми входами.с третьими входами элементов И-ИЛи 101 -ой группы, где ( =2 и, выходпервого элемента И первой группысоединен с вторыми входами элементов И-ИЛИ первой группы, выход-гоэлемента И второй группы соединен с 15четвертыми входами элементов И-ИЛИ(1 +1) -ой группы,=1 и -1, пер- вый вход К-ой схемы сравнения соединен с вторыми входами К-ьж элементов И первой и. второй группы, гдеК =1 и, второй выход.) -ойсхемы сравнения соединен с третьимвходом (1 +1)-го элемента И первойгруппы (1=1 И -1),На чертеже представлена блок-схема предлагаемого устройства.Устройство содержит и схем 1 сравнения, И регистров 2, группы эле- .ментов И 3, 4, и групп элементовИ-ИЛИ 5 и(Й) элементы 6 задержки.Устройство работает следующимобразом.В исходном состоянии во все регистры 2 записаны нули.Для удобства описания работы устройства рассмотрим поступление на З 5его информационный вход 7 следующих друг за другом чисел Х 4 = 70,Х=110, Х= 110, Х 4=105, охватывающих все возможные случаи соотношений как значений, так и последовательности их поступления на входустройства,При приходе первого числа Х иего поступлении на первые входй .схем1 сравнения, .вследствие подачи с выходов регистров 2: на вторые входысхем 1 сравнения нулевых потенциалов,с первых Выходов схем 1 сравненияподается разрешаюций потенциал наэлемент И З.Поданный на клемму 8 сит -,50нал поступит на п-ые элементы И 3 иИ 4. Пройдя -ый элемент И 3, сигналпоступит на четвертые входы и -ой. группы элементов И-ИЛИ 5, осуцествляя перепись информации из.(и) -горегистра в И -ый регистр 2.Перезаписьинформации из (-го регистра 2=- 1,2 р) в (+1)-ый регистр 2осуществляется аналогично, т.еподобно работе сдвигового регистра.Элементы 6 задержки служат для устой чивости и надежности работы устройства. Пройдя все элементы 6 задержки и поступив на первый элемент И 4,поданный на клемму 8 сигнал разрешает запись первого числа в первыйрегистр 2,При появлении на информационномвходе числа Х,1 на первьж выходах схем1 сравнения появится единичный сигФнал, поскольку второе число Х больше чисел, записанных в регистре 2;Управляющий импульс, поступившийна вход 8, разрешает перезаписьчисел из-го регистра в (Ф 1) регистр 2В результате в первом регистре 2 будет записано число. Х110, во втором - число Х= 70,При поступлении третьего числаХ=110 на первых выходах схем 1сравнения также появится единичныйсигнал, так как поступившее очередное число неменьше чисел, записанных в регистрах 2. Управляющий импульс, поступивший на вход 8, осуществляет перепись информации из-го регистра 2 в (+1) -ый регистр 2,а в первый регистр запишется число Х 3. При поступлении четвертого числа Х 4 = 105 на втором выходе первой и второй схем 1 сравнения и на первых выходах остальных схем сравнения появится единичный сигнал, открываю. - щий третий. элемент И 5 и все элементы И 3 кроме двух первых., При поступлении управляюцего импульса на вход 8 информация перепишется из )-го регистра 2 в +1) -ый регистр 21 =3,4 )1-1, а в третий регистр запишется Число Х 4Таким образом, в первом регистре будет записано максимальное число из чисел, поступивших .на вход устройства, т.е, 110, во .втором также - 110, в третьем - 105, в чет-. вертом - 70. Далее устройство работает аналогично.Таким образом, поступающие числа записываются в регистры 2 в порядке убывания. Для того, чтобы числа записать в порядке возрастания, достаточно, поменять выходы схем сравнения или подавать числа в обратном коде на схемы сравнения.Предлагаемое устройство обладает большим быстродействием,чем известное устройство. В предлагаемом устройстве поступающее число одновременно сравнивается с числами, записанными в запоминающих регистрах, и осуцествляется одновременный сдвиг и запись числа, поступившего на вход устройства,. в порядке убывания (возрастания). Дпя упорядочения массива чиселв известном устройстве требуется И/2 тактов работы, тогда как предлагаемое устройство обеспечиваетсорти-. ровку чисел за И тактов работы.. Составитель А.СуэдалеТехред А.Бабинец орректор А.Ильин ктор Г.Вол дписное нлиал ППП "Патент", г, Учгород, ул. Проектнаи Закаэ 6011/50 Тирам 706 ВНИИПИ Государственног по делам иэобретений 113035, Москва, И, Ракомитета СССРоткрытийокая наб д, 4/5