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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИН И 9) И 1) 4 С 06 Г 7 08 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ПИСАНИЕ ИЗОБРЕТЕНИ Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТР (57) Изоб лительной пользова троиств знач а данных кодом однмасштабе(21) 4007494/2 (22) 10.01.86 (46) 30.09.87. (72) Е.Я.Ваврук (53) 681.325(0 (56) Авторское В 1007099, кл.Авторское св В 1112362, кл. Бюл. В 36и В,М.Равский8.8)свидетельство СССРС 06 Г 7/08, 1981,идетельство СССРС 06 Г 7/08, 1983. СТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ тение относится к вычисехнике и может быть исв специализированных обработки информации, нных для сортировки масси оступающих параллельным за другим в реальном емени. Цель изобретения -1341631 расширение функциональных возможностей за счет возможности определениячисел, ближайших к заданному.Устройство для сортировки чисел содержит входной регистр 1, регистр 2заданного числа,вычитатель 3, (ш)узлов 4 сравнения (ш - количествосортируемых слоев, причем каждыйузел 4 сравнения содержит элементИ 5, регистр 6, схему 7 сравнения икоммутатор 8, сумматор-вычитатель9, выходной регистр 10, Устройствовыполняет сортировку разностей сортируемых чисел и заданного числа. 1Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массива данных, поступающих параллельным кодомодно за другим в реальном масштабевремени.Цель изобретения - расширение функциональных возможностей за счетвозможности определения чисел,ближайших к заданному.На чертеже приведена Функциональная схема устройства,Устройство для сортировки чиселсодержит входной регистр 1,регистр2 заданного числа, вычитатель 3,(ш) узлов 4 сравнения (ш - количество сортируемых чисел),причемкаждый узел 4 сравнения содержит элементы И 5, регистр 6, схему 7 сравнения, коммутатор 8, сумматор-вычитатель 9, выходной регистр 10, вход 11сортируемых чисел, входы 12 заданного числа, вход 13 тактовых импульсовустройства и вход 14 начальной установки,Устройство работает следующим об, разом.По сигналу начальной установки навходе 14 регистры 6 устанавливаютсяв нулевое положение. Сортируемаяпоследовательность чисел в прямомкоде с информационных входов 11 поступает на.входы регистра 1.В каждом В сумматоре-вычитателе формируетсясумма или разность заданного числас наименьшей разностью. После поступления (ш+1) импульсов ближайшеек заданному число будет записанов выходной регистр. В регистрах 6узлов сравнения будут записаны разности между заданным числом и сортируемыми числами, при этом наибольшая разность будет записана в регистре 6 первого узла сравнения.Присчитывании чисел в сумматоре-вычитателе формируется ранжированная последовательность чисел,1 ил . 4 табл. такте работы в регистр 1 записывается одно из чисел этой последовательности. Информация с выхода регистра1 поступает на первые входы вычитателя.В регистре 2 записывается число(с входов 12), ккоторому необходимонайти ближайшее (сигнал записи начертеже не приведен).Схема сравнения формирует сигнал 10 "1", когда содержимое регистра 6меньше содержимого вычитателя 3.Этотсигнал служит для передачи на выходкоммутатора 8 содержимого регистра6. На выходах разности вычитателя 3 15 формируется разность между содержимым регистров 1 и 2, на выходе знака - знак разности, который записывается в регистр 6.Устройство работает в трех режи мах: .в режиме определения числа ближайшего к заданному ,в режиме сортировки по возрастанию, и в режимесортировки по убыванию.Рассмотрим работу устройства в 25 режиме определения чисел, ближайшегок заданному.По первому тактовому импульсу врегистр 1 записывается первое число, которое с его выхода поступает 30 на входы уменьшаемого вычитателя 3,на входы вычитаемого которого поступает число с регистра 2.Значениеразности этих чисел с вычитателя 3поступает на входы регистра 6,входывторых групп схемы 7 сравнения и1341631 4ние (если сортируемое число меньше заданного) заданной и сортируемой разности. Режимом сумматора-вычитателя 9 управляет второй выход5 коммутатора 8 (ш) узла 4 сравнения.Дальнейшая работа устройства вданном режиме происходит аналогично.После поступления (ш+1) импульсовчисла массива сортируются в порядкеближайшего к заданному.При этом ближайшее к заданному число записывается з регистр 10, а в регистрах 6узлов 4 сравнения записывается разность между заданным и сортируемым.числом (в регистре 6 первого узла 4сравнения - наибольшая разность).Для считывания чисел с выхода Фегист 2 О ра 10 необходимо подать еще (ш)тактовый импульс, предварительноустановив регистр 2 в "0".В режиме сортировки по убываниюи возрастанию работа устройства про- ходит аналогично за исключением того,что в регистр 2 записывается соответственно минимальное (нули) и максимально допустимое число (все "1").Работа устройства при сортировкеЗО чисел: 8, 12, 9, 10, 14 при заданномчисле 10 происходит следующим образом. Таблица Начальная установка х 0-2 а коммутатора 8. На выходе всех схем 7 сравнения формируется сигнал "1"По второму тактовому импульсу в регистр 1 записывается второе из массива,в регистр 6 первого узла 4 сравнения переписывается число иэ вычитателя 3, а в регистры 6 остальных узлов 4 сравнения записывается информация с выходов коммутаторов 8, т.е. нули. В регистры 6 записывается и знак разности, который присутствует и на выходе коммутаторов 8. Вторая разность сравнивается с содержимым регистра 6 каждого узла 4 сравнения, и если вторая разность больше первой,тона выходе всех схем 7 сравнения формируется сигнал ".".Ес ли же вторая разность меньше первой, тона выходе схемы 7 сравнения перв го узла 4 сравнения формируется сиг нал "0"По третьему тактовому импульсу происходит запись третьего числа в регистр 1, запись второй разности (для случая, когда вторая разность больше первой) в регистр 6 первого узла 4 сравнения, запись информации с выходов коммутаторов 8 предыдущих узлов 4 сравнения в регистры 6 последующих узлов 4 сравнения.Так как знак разности проходит через все регистры и коммутаторы, на сумматоре-вычитателе 9 происходит суммирование (если сортируемое число меньше заданного) или. вычитаРежим определения числа, ближайшего к заданному показан в табл. 1.+5 5 0+4=1 Режим сортировки по возрастанию нвта Таблиц= 3 меча 8 0 гис записывается минимальнчисло "0" 8 9 и считывании эт сла складываютс ычитаются с "О" стра 2 на сумма ре вычитателе о- казан в табл,-7 сортировки по убыв числ 15 ного13416318гистра (+1)-го узла сравнения, соответствующие информационные входы вторых групп схем сравнения и коммутаторов всех углов сравнения объединены, отличающееся тем, что, с целью расширения функциональных воэможностей за счет определения чисел, ближайших к заданному, в него введены .вычитатель, сумматор-вычитатель и реЮ гистр заданного числа, причем выходыразрядов входного регистра соединены с входами уменьшаемого вычитателя,. входы вычитаемого которого соединены с вхоДами. первой группы сумматора-вы"15 читателя и выходами разрядов регистразаданного числа, информационные входы которого являются входами заданного числа устройства, выходы разности вычитателя подключены к информационным входам регистра первого узла сравнения и информационным входам вторых групп схем сравнения коммутаторов всех узлов сравнения, выход знакового разряда вычитателя подключен к входу знакового разряда регистра первого узла сравнения,и входам знаковых разрядов второй группы коммутаторов всех узлов сравнения,а каждом узле сравнения выход знакового разряда регистра подключен к входу знакового разряда второй группы, информационные выходы коммутатора (ш)-го узла сравнения соединены с информационными входами второй группы сумматора-вычитателя, управляющий вход которого соединен с выходом знака коммутатора(ш)-го узла сравнения, выход знака коммутатора -го узла сравнения подключен к входу знакового разряда регистра (х+1)-го узла сравнения, выходы сумматора-вычитателя соединены с информационными входами выходного регистра, вход начальной установки устройства подключен к входам установки в"0" регистров всех узлов сравнения. При считывании информации в регистр 10 происходит следующее: 1,см. табл. 4). Т а б л и ц а 4 10 ТБ(15-6) = 9 (15-7) = 8 формула изобретенияУстройство для сортировки чисел, содержащее входной и выходной регистры и (ш) узлов сравнения, где ш - количество чисел сортируемого массива, каждый узел сравнения содержит элемент И, схему сравнения коммутатор и регистрвыходы разрядов которого соединены с соответствующи-, ми информационными входами первых групп схемы сравнения и групп ком мутатора, управляющий вход которого соединен с выходом схемы сравнения и первым входом элемента И, выход которого подключен к входу управления записью регистра, вход тактовых 35 импульсов устройства подключен к входам управления записью входного и выходного регистров и вторым входам элементов И всех узлов сравнения,входы сортируемых чисел устройст ва соединены с информационными входами входного регистра, информаци онные выходы коммутатора -го узла "сравнения, где 3. = 1,2 .,(ш),сое- динены с информационными входами ре Составитель Е, ИвановаТехред М.Дидык Корректор С.Черни Редактор Е. Копча Заказ 4437/52 Тираж 672 Подписное.ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4