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

(51)4 С Об Р 7 0 ЫЙ КОМИТЕТ СССР ОБРЕТЕНИЙ И ОТНРЫТИЙСУДАРСТВЕО ДЕЛАМ И БРЕТ я, чис его чи ОПИСАНИЕ ИЗ 21) 4130094/24-24(56) Авторское свидетельство СССР Р 1185326, кл, О Об Р 7/06, 1983.Авторское свидетельство СССР В 959065, кл. 8 06 Р 7/04, 1982,а.(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ 57) Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массивов данных. Целью изобретения является рас" ширение области применения за счет ,обеспечения возможности сортировки массивов. чисел, поступающих последовательным кодом одно за другим вреальном масштабе времени. Устройство содержит ш узлов сравнения 12,триггеры 5,6,7,9, управляющие элементы И 8,10, Каждый узел сравнения содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 18,триггеры 14,16,20, элементы И 13,15,17,19, коммутатор 21, регистр 22,Информация в устройство поступает последовательным кодом, старшими разрядами вперед. В основу работы устройства положен алгоритм сортировки чиселметодом прямого включения, Поступаю"щие числа поразрядно сравниваются счислами, хранящимися в регистрах 22 8узлов сравнения 12, и записываются врегистр 22 того узла сравненило в котором меньше поступающ с" Сла, 2 ил.Изобретение относится к вычислительной технике н может быть использовано в специализированных устройствах обработки информации, предназна" ченных для сортировки массивов данных, поступающих последовательным ко, дом одно за другим в .реальном масштабе времени.Цель изобретения - расширение об О ласти применения за счет возможности сортировки массивов чисел в последовательном коде в реальном масштабе времени.На фиг,1 представлена схема уст ройства; .на фиг. 2 - временная диаграмма работы устройства.Устройство содержит тактовый вход 1, информационный вход 2, вход 3 гра" ниц числа, вход 4 наЧальной установ ки, триггеры 5, б.н 7, управляющий элемент И 8, триггер 9, управляющий элемент И 10, выход 1 ш узлов 12 сравнения (где ш - количество сорти" руемых чисел в массиве). Каждый узел12 сравнения содержит элемент И 13,триггер 14, элемент И 15, триггер 16, элемент И 17, элемент ИСКЛЮЧАЮТЕ ИЛИ 18, элемент И 19, триггер 20 коммутатор 21 и регистр 22.Устройство работает следукяцим образом.Информация в устройство поступа ет последовательным кодом старшимиразрядами вперед, Поступление инфор мации в устройство привязано к тактовым импульсам которые синхронизиру"ют работу устройства. Числа в устройство поступают с информационного входа 2 и сопровождаются импульсами 40 начала и конца поступления числа из входа 3. Импульсы начала и конца поступления числа являются положительными импульсами и совпадают с такто-выми импульсами, поступающими с входа 1 (см.фиг.2). Перед началом сортировки импульсом положительной полярности, поступившим с входа 4 триггер б устанавЭ50ливается в единицу, а регистры 22 вузлах 121,12сравнения и тригогеры 7 и 9 в нуль. Сигнал лог. 1с выхода триггера 6 поступает на вхо-.ды установки в нуль триггеров 20 вузлах 12 12 , сравнения и уста"навливает их в "О". Сортировка массива из ш чисел производится за ш пик лов, каждый из которых выполняется за (и+2) тактов (и - разрядность сортируемых чисел).В основу работы устройства поло" жен алгоритм сортировки чисел методом прямого включения.Рассмотрим работу устройства при сортировке первого массива чисел. В первом такте первого цикла с приходом импульса начала первого числа на выходе элемента И 10 получаем лог. "1", которая поступает на установочные входы триггеров 14 узлов 12,23 ю сравнения и триггера 9 и устанавливает их в единицу. В каждом узле 12 сравнения сигнал лог."1" с прямого выхода триггера 14 поступает на .вход установки триггера 16 и устанавливает его в единицу. Задним фронтом (перепадом уровня сигнала с лог. "1" в лог."0") импульса начала первого числа триггер 6 устанавливается в нуль. Во втором такте старший разряд первого сортируемого числа поступает на информационный вход 2 и по заднему фронту тактового импульса записывается в триггер 5. Задним фронтом этого же импульса в триггер 7 запи-, сывается единица. Сигнал лог. "1" на втором и третьем входах элемента И 8 разрешает прохождение тактовых импульсов через данный элемент. В каждом иэ узлов 1212, сравнения коммутатор 21 установлен в положение, когда на его выход поступает, информация с выхода старшего разряда регистра 22 предыдущего узла 1 2 сравнения. Коммутатор 21 первого узла 12 сравнения установлен в положение,когда на его выход поступает информация с выхода триггера 5. В третьем и следующих тактах данного цикла задним фронтом тактового импульса производится запись входной информации в триггер 5, сдвиг и запись информации в регистры 22 узлов 12 сравнения. В (и+2)-ом такте работы задним фронтом импульса конца первого числатриггер 6 устанавливается в единицу, а зад" ним фронтом тактового импульса производится сдвиг и запись информации в регистры 22 в уздах: 12 сравнения, Перепадом уровня сигнала на выходе триггера 6 с лог. "О" в лог. "1" производится запись лог. "О" в триггер 14 первого узла 12 сравнения и лог. "1" - в триггер 9 и триггеры 14141001элементов И всех узлов сравнения объединены, первые входы третьих эле-, ментов И всех узлов сравнения объеди" иены, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет возможности сортировки массивов чисел в последовательном коде в реальном масштабе времени, в него введены четыре триггера и в ь-й 10 узел сравнений три триггера, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и коммутатор, причем информационный вход устройства соединен с информационным входом первого триггера, синхровход которого являет ся тактовым входом устройства и соединен с синхровходом второго триггера, с первым входом четвертого элемента И ", го узла сравнения и первым входом первого управляющего элемента 20 И, второй вход которого соединен с информационным входом второго тригге" ра и с инверсным выходом третьего триггера, а третий вход - с прямым выходом второго триггера, вход уста новки в "0" которого является входом начальной установки устройства и соединен с входом установки в "1" третье" го триггера, с входами установки в начальное положение всех узлов срав" 30 кения и с входом установки в "О" четвертого триггера, синхровход которого соединен .с первым входом второго управляющего элемента И, с синхровходом первого триггера, с первым входом второго элемента И, с входом установ.ки в "0" второго триггера х-го узла сравнения и прямым выходом третьего триггера, синхровход которого являет" ся входом границ числа устройства и соединен с вторым входом второго управляющего элемента И, третий вход которого соединен с инверсным выходом четвертого триггера и с информационным входом первого триггера первого узла сравнения, а выход соединен с входом установки в единичное состояние четвертого триггера и с входом установки в единичное состояние первого триггера всех узлов сравнения, информационный вход первого триггера 1"го узла сравнения соединен с прямым выходом первого триггера (х)-го узла сравнения, в каждом узле сравнения прямой выход первого триггера соединен с входом установки в единичное состояние третьего триггера, синхровход которого соеди 9 6нен с синхровходом второго триггераи с выходом четвертого элемента И,второй вход которого соединен с инверсным выходом второго триггера, атретий -вход - с инверсным выходомтретьего триггера, с первым входомкоммутатора этого же узла сравнения,.инверсный выход третьего триггера(-1)-го узла сравнения соединен свторым и третьим входами коммутатораь-го узла сравнения, в каждом узлесравнения четвертый вход коммутаторасоединен с первым входом первогоэлемента И и с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, четвертый входкоммутатора (-1)-го узла сравненияобъединен с пятым входом коммутаторах-го узла сравнения, шестой входкоммутатора х-го узла сравнения соединен с прямым выходом третьеготриггера и с седькдм входом коммутатора (-1)-го узла сравнения, восьмые входы коммутаторов всех узловсравнения объединены и соединены спрямым выходом первого триггера, вкаждом узле сравнения второй входэлемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен спервым входом третьего элемента И,а выход соединен с вторым входом первого элемента И и с вторым входомтретьего элемента И, выход которогосоединен с информационным входомтретьего триггера, вход установкив нО" которого соединен с выходомвторого элемента И, второй. вход которого соединен с инверсным выходомпервого триггера, выход коммутаторасоединен с входом младшего разрядарегистра, вход сдвига регистров всехузлов сравнения соединен с выходомпервого управляющего элемента И, пятый и шестой входы коммутатора перво"го узла сравнения соединены.с вхо"дом логического нуля устройства, второй и третий входы коммутатора пер"вого узла сравнения соединены с входом логической единицы устройства,прямой выход первого триггера ш"гоузла сравнения соединен с информационным входом четвертого триггера,выход старшего разряда регистра ш-гоувла сравнения является информационным выходом устройства, прямой выходтретьего триггера ш"го узла сравнения соединен с седьмым входом комму"татора этого узла сравнения.-ом (,1 = 1 ш) цикле сортировки,В начале первого такта -го цикла врегистрах 22 узлов 12112 1,сравнения находятся просортированныечисла в порядке убывания, наибольшеев первом 12, а наименьшее в 1-1-ом 10узле 12 сравнения. Триггеры 14 узлов12,.,12, сравнениянаходятсяв нуле, а триггер 9 и триггеры 14 узлов 12, 12сравнения - в единице, В узлах 12 , 12 , сравнения 15триггеры 16.и 20 установлены в нуль.В узлах 12,.,12 ь, сравнения триггеры 16 установлены в единицу, а триггеры 20 - в нуль, В каждом из,узлов12 ,12 ., сравнения коммутатор 2021 установлен в положение, когда наего выход поступает информация с выхода старшего разряда регистра 22.В узле 12 сравнения коммутатор 21установлен в положение, когда на его 25выход поступает информация с выходатриггера 5. В узлах 1212 ,сравнения коммутатор 21 установленв положение, когда на его выход поступает информация с выхода старшего 30разряда регистра 22 предыдущего узла12 сравнения. В первом такте 1-го цикла задним фронтом импульса начала 1-го числа35 триггер 6 устанавливается в руль, Во втором и последующих тактах работь 1 устройства в каждом узле 12 сравнения на первый вход элемента ИСКЛЮЧАЮЩЕЕ ИИ 18 поступает "й Разряд ( = 40 = 1, и) 1-го числа, а на второй вход " информация с выхода старшего разряда регистра 22, и в случае,.если информация на входах одинакова, то на выходе имеем лог. 0 в против ном случае в .лог. "1". Информация с выхода элемента ИСКЛЮЧАЮЩЕЕ ИИ 18 поступает на входы элементов И 17 и 19 и разрешает (лог."1") или запрещает (лог. "0") прохождение информации через эти элементы. Получение лог. "1":на выходе элемента И 17 указывает на то, что -й разряд 1"го числа равен единице, а -й разряд числа из регистра 22 - нулю. В случае если 1-й разряд числа из регистра 22 равен единице, а -й разряд 1"го числа " нулю, - то на выходе элемента И 19 получаем сигнал лог,"1". 94По заднему фронту второго тактового импульса производится запись информации в триггер 5 (старшего разряда), в триггеры 16 и 20 узлов 1212сравнения и в триггер 7 (лог."1"). Сигнал лог. "1" на втором и третьем входах элемента И 8 разрешает прохождение тактовых импульсов через данный элемент. Запись лог. "1" в триггер 16 или в триггер 20 в узле 12 сравнения блокирует поступление тактовых импульсов через элемент И 13 в данном узле сравнения. Если произошла запись лог. "1" в триггер 16 узла 12 , сравнения и в группу триггеров 16 иэ предыдущих узлов 12 сравнения, то коммутаторы 21 в этих узлах сравнения устанавливаются на передачу информации из старшего разряда регистра 22 предыду" щего узла 12 сравнения, кроме узла 12 сравнения с наименьшим порядковым номером из данной группы. Коммутатор 21 в данном узле 12 сравнения устанавливается в положение, когда на его выход поступает информация иэ выхода триггера 5, В третьем и последующих тактах работы по заднему фронту каждого тактового импульса производится запись информации в триггер 5, сдвиг и запись информации в регистры 22 узлов 12 сравнения, а также запись информации в триггеры 16 и 20 тех же узлов 12 сравнения, в которых разрешено прохождение тактовых импульсов через элемент И 13,После выполнения ш-го цикла сор" тировки в регистрах 22 узлов 12 срав" нения получаем первый просортированный в порядке убывания массив информации (наибольшее число находится в регистре 22 первого узла 12 сравнения, следующее число по величине " в регистре 22, второго узла,12 сравнения и т.д наименьшее - в регистре 22 ш-го узла 12 сравнения). Формула изобретения Устройство для сортировки чисел, содержащее два управляющих элемента, И и ш узлов сравнения (ш - количество сортируемых чисел в массиве), каждый из которых содержит четыре элемента И и регистр, причем в каждом узле сравнения выход старшего разряда регистра соединен с первым входои,первого элемента И, первые входыВторых1410019сСоставитель Е.ИвановТехред Л.Сердюкова 1а ректор В.Б едактор А.Дол Тираж акаэ 3480/44 одписн ектная Ужгород, ул зводственно-полиграфическое предприят ВНИИПИ Государственного комитета СС по делам изобретений,и открытий113035, Москва, Ж, Раушская наб., д