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

/.

(pue.i

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массивов данных, поступающих последовательным кодом одно за другим в .реальном ма сшта- бе времени.

Цель изобретения - расширение области применения за счет возможности сортировки массивов чисел в последовательном коде в реальном масштабе времени.

На фиг.I представлена схема устройства; На фиг. 2 - временная диаграмма работы устройства

Устройство содержит тактовый вход 1, 11нформационный вход 2, вход 3 границ числа, вход 4 начальной установки, триггеры 5, 6,.и 7, управляющий элемент И 8, триггер 9, управлякщий элемент И 10, выход 1 j, in узлов 12 сравнения (где m - количество сортиг руемых чисел в массиве). Каждый узел 12 сравнения содержит элемент И 13, триггер 14, элемент И 15, триггер 16, элемент И 17, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 18, элемент И 19, триггер 20, коммутатор 21 и регистр 22о

Устройство работает следукядим об- раэом.

Информация в устройство поступа ет последовательным кодом старшими разрядами вперед Поступление информации в устройство привязано к тактовым импульсам,, которые синхронизируют работу устройства. Числа в устройство поступают с информационного вхо- I да 2 и сопровождаются импульсами

начала и конца поступления числа из I входа Зв Импульсы начала и конца пос тупления числа являются положительными импульсами и совпадают с тактовыми импульсами, поступающими с вхо- . да 1 (см,фиг.2)о

Перед началом сортировки импульсом положительной полярности, поступившим с входа 4, триггер 6 устанавливается в единицу, а регистры 22 в узлах 12,00.1,12 сравнения и триггеры 7 и 9 нуль. Сигнал лог 1 с выхода триггера 6 поступает на входы установки в нуль триггеров 20 в узлах 12,,.о.,12„ сравнения и устанавливает их в О. Сортировка масси ва из m чисел производится за m цик- лов, каядый из которых выполняется

за (п+2) тактов (п - разрядность сортируемых чисел).

В основу работы устройства положен алгоритм сортировки чисел мето- . дом прямого включения

Рассмотрим работу устройства при сортировке первого массива чисел.

Q В первом такте первого цикла с приходом импульса начала первого числа на выходе элемента И. 10 полу чаем лог о 1, которая поступает на установочные входы триггеров 14 уз5 лов 12,,о о о,23 сравнения и триггера 9 и устанавливает их в единицу. В каждом узле 12 сравнения сигнал лоГо М с прямого выхода триггера 14 поступает на .вход установки тригQ гера 16 и устанавливает его в единицу Задним фронтом (перепадом уровня сигнала с лог. 1 в лог.О) импульса начала первого числа триггер 6 устанавливается в нуль Во

5 втором такте старший разряд первого сортируемого числа поступает йа информационный вход 2 и по заднему фронту тактового импульса записывается в триггер 5. Задним фронтом

0 этого же импульса в триггер 7 запи- . сьшается единица. Сигнал лог. 1 на втором и третьем входах элемента И 8 разрешает прохолздение тактовых импульсов через данный элемент. В

с каждо14 из узлов 12/j,.,o,12n,- сравнения коммутатор 21 установлен в положение, когда на его выход поступает , информация с выхода старшего разряда регистра 22 пр дьщущего узла 12 срав0 нения. Коммутатор 21 первого узла 12 сравнения установлен в положение,когда на его выход поступает информация с выхода триггера 5, В третьем и следующих тактах данного цикла задним

с фронтом тактового импульса произво дится запись входной информации в триггер 5, сдвиг и запись информации в регистры 22 узлов 12 сравнения. В (п+2)-ом такте работы задним фронтом импульса конца первого числа триггер 6 устанавливается в единицу, а задним фронтом тактового импульса производится СДВИГ и запись информации в регистры 22 в уздах 12 сравнения. Перепадом уровня сигнала на выходе триггера 6 с лог О в лог. 1 производится запись лого О в триггер 14 первого узла 12 сравнения и лог. 1 - в триггер 9 и триггеры 14

0

5U

элементов И всех узлов сравнения объединены, первые входы третьих эле- ментов И всех узлов сравнения объедииены, ОТЛИ-.чающееся тем-, что, с целью расширения обл(зсти применения за счет возможности сортировки массивов чисел в последовательном коде в реальном масштабе времени, в него введены четыре триггера и в i-й узел сравнений три триггера, элемент ИСКЛЮЧАЮПЩЕ ИЛИ и коммутатор, причем информаю ионный вход устройства соединен с информационным входом первого триггера, синхровход которого являет- ся тактовым входом устройства и соединен с синхровходом второго триггера, с первым входом четвертого элемента И irro узла сравнения и первым входом первого управляющего элемента И, второй вход которого соединен с информационным входом второго триггера и с инверсным вькодом третьего триггера, а третий вход - с прямым выходом второго триггера, вход уста- новки в О которого является входом начальной установки устройства и соединен с входом установки в 1 третьего триггера, с входами установки в начальное положение всех узлов срав- нения и с входом установки в О четвертого триггера, синхровход которого соединен .с первым входом второго управляющего элемента И, с синхровходом первого триггера, с первым входом второго элемента И, с входом установки в О второго триггера i-ro узла сравнения и прямым выходом третьего триггера, синхровход которого является входом границ числа устройства и соединен с вторым входом второго управляющего элемента И, третий вход которого соединен с инверсным выходом четвертого триггера и с информационным входом первого триггера первого узла сравнения, а выход соединен с входом установки в единичное состояние четв.ертого триггера и с входом установки в единичное состояние первого триггера всех узлов сравнения, информационный вход первого триггера j-ro узла сравнения соединен с прямым выходом первого триггера (i-l)-ro узла сравнения, в каждом узле сравнения прямой выход первого триггера соединен с входом установки в единичное состояние третьего триггера, синхровход которого соеди-

5 0 5 о д 0 5 g g

9 . 6

иен с синхровходом второго триггера и с выходом четвертого элемента И, второй вход которого соединен с инверсным выходом второго триггера, а третий ВХОД - с инверсным выходом третьего триггера, с первым входом коммутатора этого же увла сравнения,, инверсный выход третьего триггера (i-1)-го узла сравнения соединен с вторым и третьим входами коммутатора i-ro узла сравнения, в каждом узле сравнения четвертый вход коммутатора соединен с первым входом первого элемента И и с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, четвертый вход коммутатора (i-l)-ro узла сравнения объединен с пятым входом коммутатора i-ro узла сравнения, шестой вход коммутатора i-ro узла сравнения соединен с прямым выходом третьего триггера и с седьмым входом коммутатора (i-l)-ro узла сравнения, восьмые входы коммутаторов всех узлов сравнения Объединены и соединены с прямым выходом первого триггера, в каждом узле сравнения второй вход элемента ИСКЛГОЧАКШЩЕ ИЛИ соединен с первым входом третьего элемента И, а выход соединен с вторым входом первого элемента И и с вторым входом третьего элемента И, выход которого соединен с информационным входом третьего триггера, вход установки в О которого соединен с выходом второго элемента И, второй-вход которого соединен с инверсным выходом первого триггера, выход коммутатора соединен с входом младшего разряда регистра, вход сдвига регистров всех узлов сравнения соединен с выходом первого управляющего элемента И, пятый и шестой входы коммутатора первого узла .сравнения соединены с входом логического куля устройства, второй и третий входы коммутатора первого узла сравнения соединены с входом логической единицы устройства, прямой выход первого триггера т-го узла сравнения соединен с информационным входом четвертого триггера,выход старшего разряда регистра т-го увла сравнения является информационным выходом устройства, прямой выход третьего триггера т-го узла сравнения соединен с седьмьм входом коммутатора этого узла сравнения.

14

остальных узлов 2.,,,2 сравне- ния.

Рассмотрим работу устройства в (j 1,..о, m) цикле сортировки В начале первого такта J-ro цикла в регистрах 22 узлов 12, о.,12 ;., сравнения находятся просортированкые числа в порядке убывания, наибольшее в первом 12, а наименьшее в j-1-ом узле 12 сравнения. Триггеры 14 узлов 12,„..,12 сравнения находятся в нуле, а триггер 9 и триггеры 14 узлов 12, о.,, 12 сравнения - в единице, В узлах 1 2,,,., 12 ., сравнения триггеры 16-И 20 установлены в |1уль, В узлах 12,...,12 сравнения триггры 16 установлены в единицу, а триггеры 20 - в нуль, В каждом из .узлов 12, ,..., 1 2 :., сравнения коммутатор 21 установлен в положение, когда на его выход поступает информация с выхода старшего разряда регистра 22. В узле 12/ сравнения коммутатор 21 установлен в положение, когда на его выход поступает информация с выхода триггера 5. В узлах 12, ,.,,,12 сравнения коммутатор 21 установлен в положение, когда на его выход поступает информация с выхода старшего разряда регистра 22 предыдущего узла 12 сравнения.

В первом такте J -ro цикла задним фронтом импульса начала J-ro числа триггер 6 устанавливается в руль. Во Втором и последующих тактах работы устройства в каждом узле 12 сравнения на первый вход элемента ИСКЛЮЧАЮ- ЩЕ ИЛИ 18 поступает i-й разряд (i 1,,,, п) j-ro числа, а на второй ВХОД - информация с выхода старшего разряда регистра 22, и в случае;если информация на входах одинакова, то на выходе имеем лог. О, в против- ном случае - лог. 1. Информация с выхода элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 18 поступает на входы элементов И 17 и 19 и разрешает (лог.1) или запре- щйет (лого О) прохождение информа- дин через эти элементы Получение лог о 1 на выходе элемента И 17 указывает на то, что i-й разряд j-ro числа равен единице, а i-й разряд

числа из регистра 22 - нулю. В случае если 1-й разряд числа из регистра 22 равен единице, а i-й разряд J-ro числа - нулю, то на выходе элемента И 19 получаем сигнал лог.

01

5 0 5 0

5

0 . g

5

94

По заднему фронту второго тактового импульса производится запись информации в триггер 5 (старшего разряда), в триггеры 16 и 20 узлов 12 J-1 сравнения и в триггер 7 (лог,Г ). Сигнал лог. 1 на втором и третьем входах элемента И 8 разрешает прохождение тактовых импульсов через данный элемент. Запись лог о 1 в .триггер 16 или в триггер

20в узле 12 сравнения блокирует поступление тактовых импульсов через элемент И 13 в данном узле сравнения. Если произошла запись лог. 1 в триггер 6 узла 12 , сравнения и

в группу триггеров 16 из предьщущих узлов 12 сравнения, то коммутаторы

21в этих узлах сравнения устанавливаются на передачу информации из старшего раз-ряда регистра 22 предыдущего узла 12 сравнения, кроме узла

12 сравнения с наименьшим порядковым номером из данной группы. Коммутатор

21в данном узле 12 сравнения устанавливается в положение,. когда на его выход поступает информация из выхода триггера 5, В третьем и последующих тактах работы по заднему фронту каждого тактового импульса производится запись информации в триггер 5, сдвиг и запись информации в регистры 22 узлов 12 сравнения, а также запись информации в триггеры 16 и

20 тех же узлов 12 сравнения, в которых разрешено прохождение тактовых импульсов через элемент И 13

После выполнения ш-го цикла сортировки в регистрах 22 узлов 12 сравнения получаем первый просортирован- ный в порядке убывания массив информации (наибольшее число находится в регистре 22 первого узла i2 сравнения, . следующее число по величине - в регистре 22 .второго узла .12 сравнения и т.д., наименьшее - в регистре

22ш-го узла 12 сравнения).

Фо рмула изобр етения

Устройство для сортировки чисел, содержащее два управляющих элемента . И и m узлов сравнения (т - количество сортируемых чисел в массиве), каждый из которых содержит четыре элемента И и регистр, причем в каидом узле сравнения выход старшего разряда регистра соединен с первым входов, первого элемента И, первые входы ;.вторых

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массивов дан ньк. Целью изобретения является расширение области применения за счет ,обеспечения возможности сортировки массивов.чисел, поступающих последовательным кодом одно за другим в реальном масштабе времени. Устройство содержит m узлов сравнения 12, триггеры 5,6,7,9, управляющие элементы И 8,10. Каждый узел сравнения содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 18, (Триггеры 14,16,20, злементы И 13,15, 17,19j коммутатор 21, регистр 22оИн- формация в устройство поступает последовательным кодом, старшими разрядами вперед. В основу работы устройства положен алгоритм сортировки чисел методом прямого включения. Поступаю- щие числа поразрядно сравниваются с числами, хранящимися в регистрах 22 узлов сравнения 12, и записываются в регистр 22 того узла сравнения, число в котором меньше поступающего ла, 2 ил.

Редактор А.Долинич

Составитель Е.Иванова Техред Л.Сер дюкова

Закаэ 3480/44

Тираж 704

ВНИИПИ Государственного комитета СССР

по делам изобретений .и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Корректор В.Бутяга

Подписное