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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз СоветскихСоциалистическихРеспублик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(61) Дополнительное к авт. свид-ву(22) Заявлено 250480 (21) 2916946/18-24 5 Ц М. Кп.з З 06 Р 7/06 с присоединением заявки Мо(23) Приоритет -Государственный комитет СССР но делам изобретений и открытий(72) Авторыизобретения Э.П. Чернаков и Б.С, Богумирский Военный инженерный Краснознаменный институт им. А.ф. Можайского(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ Изобретение относится к автоматике и вычислительной технике и можетбыть использовано в специализированных вычислительных машинах и устройствах обработки данных,Известно устройство для сортировки тап-разрядных чисел, содержащеещ регистров, выходы каждого из которых соединены со входами схем сравнения, другие входы которых подКлючены .к выходам регистра результата,выходы схем сравнения соединены через переключатели со входами элемента ИЛИ, клапаны и триггер, узлызапрета 11 . Недостаток этого устройства -низкое быстродействие,. Наиболее близким по техническойсущности к предлагаемому являетсяустройство, содержащее щ регистров,регистр результата, клапаны, узлызапрета, элемент ИЛИ, триггер и временной распределитель, причем выходы регистров подключены ко входамсхеМ сравнения, другие входы которых соединены с выходами регистрарезультата, а выходы схем сравнения - с узлами запрета и входамиэлемента ИЛИ 21. Недостатками этого устройстваявляются значительные аппаратурныезатраты.Цель изобретения - упрощениеустройств.Для достижения цели в устройстведля сортировкИ чисел, содержащемрегистры, схемы сравнения, элементыИ, элементы запрета, регистр результата, распределитель импульсов,причем выходы каждого 1-го регистра,где 1. - 1,2,,и, соединены совходами первой группы входов 1-ойсхемы сравнения, первый выход которой соединен со входом управления1-го элемента запрета, выход каждого из которых подключен к первомувходу 1-го элемента И, выход которого соединен со входом управления1-ой схемы сравнения, вход опросаустройства подключен ко вторым вхо,:дам элементов И, вход тактовых,сиг:налов устройства соединен со входомраспределителя импульсов, выходы 25 которого подключены ко входам управления установкой разрядов регистрарезультата, выходы которых соединенысо входом второй группы схем сравнения, первыйи второй входы управле ния устройства подключены к .первыми вторым информационным входам соответственно элементов запрета, входзаписи устройства соединен со входами установки в единичное состояние разрядов регистра результата,второй выход каждой 1-ой схемы сравнения соединен с 1-ым входом (1+1)-гоэлемента И, выход которого подключен ко входам установкИ в нулевоесостояние разрядов регистра результата, вход записи результата устройства .соединен с О+1) -ым входом(1+1)-го элемента И,На чертеже приведена функциональная схема предлагаемого устройства.Устройство содержит регистры 15111 т,1, схемы сравнения2,2. . .2, регистр результата 3распределитель импульсов 4, элементы.запрета 5,525, элементы И6,626, элемент И 7, вход записи устройства 8, вход тактовыхсигналов 9, входы управления устройства 10 и 11, вход опроса устрайства 12, вход записи результатов 13.Устройство работает следующимобразам,В регистры 1 заносятся числа, подлежащие сортировке, регистр результата 3 устанавливается в нулевое состояние, а временной"распредели- ЗО тель 4 - в исходное состояние (цепи занесения информации в регистры 1, установки в нулевое состояние регистра результата 8, а также установки в исходное состояние распреде лителя 4 (не показаны). На вход управления устройства 11 подается сигнал переводящий все элементы запрета 5 в такое состояние, что элементы б оказываются открытыми. 40 После проведения этих операций устройство готово к работе, На вход тактовых сигналов устройства 9 пода- ется первый тактовый сигнал, по которому на первом выходе Распределителя 4 появляется сигнал. Он проходит на управляющий вход старшего разряда регистра результата 3, разрешая запись в него информации, Затем на вход записи устройства 8 подается сигнал, по которому в старший разряд регистра результата 3 заносится единица. После этого сигнал подается на вход опроса устройства 12. Он 1 проходит на управляющие входы схем сравнения 2 через открытые элементы б. Схемы сравнения 2 осуществляют сравнение чисел, находящихся в соответствующих регистрах 1, с числом, находящимся в регистре результата 3. Если число в каком-либо 40 регистре 1 меньше числа, находящегося в регистре результата 3, то на выходе фменьшеф соответствующей схемы сравнения 2 появляется сигнал если числа равны, то сигнал появля ется на выходе фравно., Сигналы,появляющиеся на выходах равносхем сравнения 2,не оказывают воздействие на элементы запрета 5, таккак сигнал на запрещающие входы не:подан. Затем подается сигнал на входустройства 13. Если на выходахменьше всех схем сравнения 2 присутствует сигнал, то он появляетсяна выходе элемента И 7 и проходитна нулевой вход старшего разрядарегистра 3. Таким образом, если, всесортируемые числа меньше числа, записанного в регистре результата,тов его старший разряд записываетсянуль. После этого на вход устройства 9 подается второй тактовый сигнали устройство работает так же, какв первом такте. К концу в.торого такта работы устройства во втором разряде регистра результата записываетсянуль, если все сортируемые числаменьше числа, сформированнрго в,начале второго такта, в противном случае - единица, После окончания птактов в регистре результата 3 сформируется максимальное из хранящихсяв регистрах 1 чисел. В (и+1) тактераспределитель 4 по сигналу на входетактовых сигналов устройства 9 переводится в исходное состояние, прикотором сигналы на его выходах отсутствуют. На вход устройства 10 по"дается сигнал, который проходит науправляющйе входы узлов запрета 5,Затем подается сигнал на вход опроса устройства 12, который поступаетЫа управляющие входы всех схем сравнения 2, но появляется на выходахравно только тех схем сравнения3, где в принадлежащих им регистрах1 записаны числа, равные числу,сформированному в регистре результата 3. Соответствующие этим схемамсравнения элементы запрета 5 переводятся в такое состояние, что соединенные с ним клапаны закрываются.Таким образом регистры 1, в которыхзаписано максимальное число, в дальнейшей работе участия не принимают,После этого содержимое регистра результата 3 выбирается и он переводится в нулевое состояние. Затем на вход тактовых сигналов устройства 9 подается очередной так товый сигнаЛ и устройство начинает формировать максимальное число из оставшихсяРабота устройства циклически повторяется до тех пор, пока ,не отсортируются все числа, находятнеся в регистрах 1, в порядке их убывания. Для сортировки чисел в порядке их возрастания необходимо в регистры 1 записать инверсные коды сортируемых чисел и инвертировать. коды, считываемые с регистра результата 3928342 формула изобретения г Использование предлагаемого устройства позволяет сократить аппаратурные затраты на один триггер и элемент И. Устройство для сортировки чисел, содержащее регистры, схемы сравнения, элементы И, элементы запрета, регистр результата, распределитель импульсов, причем выходы каждого 1-го регистра, где 1 - 1,2п соединены со входами первой группы входов 1"ой .схемы сравнения, первый выход которой соединен со входом управления 1-го элемента запрета, выход каждого из которых подключен к первому входу 1-го элемента И, выход которого соединен со входом управления 1-ой схемы сравнения, вход 20 опроса устройства подключен ко вторым входам элементов И, вход тактовых сигналов устройства соединен со входом распределителя импульсов, ,выходы которого подключены ко Ьходам ВНИИПИ Заказ 3241/61Тираж 732 Подписное лиал ППП "Патент"Ужгород, ул. Проектная,управления установкой разрядов регистра результата, выходы которыхсоединены со входом второй группысхем сравнения, первый и второй входы управления устройства подключенык первым и вторым информационнымвходам соответственно элементов запрета, вход записи устройства соединен со входами установки в единичноесостояние разрядов регистра результата, о т л и ч а ю щ е е с я тем,что, с целью упрощения устройства,в нем второй выход каждой 1-ой схемы сравнения соединен с 1-ым входом(1+1) -го элемента И, выход которогоподключен ко входам установки в нулевое состояние разрядов регистра "результата, вход записи результатаустройства соединен с (1+1) -ым входом (1+1)-го элемента И,Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 263277, кл. 6 06 Р 7/00, 1956.2. Авторское свидетельство СССРМ 687810, кл. 6 06 Р 7/08, 1976