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

 

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

СОЮЗ СОНЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

А1 (51)4 G 06 Р 7 04

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21 ) 4130094/24-24 (22) 03,10.86 (46) 15.07.88. Бюл. Р 26 (72) Е.Я.Ваврук, А.А.Мельник и И.Г.Цмоць (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Р 1185326, кл, G 06 F 7/06, 1983.

Авторское свидетельство СССР

11 959065, кл. G 06 Р 7/04, 1982. а.(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для сортировки массивов дан ных. Целью изобретения является рас" ширение области применения за счет ,обеспечения возможности сортировки

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

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

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

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

Устройство содержит тактовый вход

1, информационный вход 2, вход 3 гра- ниц числа, вход 4 начальной установ- 20 ки, триггеры 5, 6.н 7, управляющий элемент И 8, триггер 9, управляющий элемент И 10, выход 1) m узлов 12 сравнения (где m — количество сорти" руемых чисел в массиве). Каждый узел

12 сравнения содержит элемент И 13, триггер 14, элемент И 15, триггер 16, элемент И 17, элемент ИСКЛЮЧАЮПДЕ

ИЛИ 18, элемент И 19, триггер 20, коммутатор 21 и регистр 22.

Устройство работает следукяцим образом. (Информация в устройство поступа ет последовательным кодом старшими разрядами вперед. Поступление информации в устройство привязано к тактовым импульсам„ которые синхронизиру" ют работу устройства. Числа в устройство поступают с информационного входа 2 и сопровождаются импульсами 40 начала и конца поступления числа из входа 3. Импульсы начала и конца поступления числа являются положительными импульсами и совпадают с такто- выми импульсами, поступающими с вхо- 45 да 1 (см.фиг.2).

Перед началом сортировки импульсом положительной полярности, поступившим с входа 4 триггер 6 устанавЭ

50 ливается в единицу, а регистры 22 в узлах 12»...,,12> сравнения и триго геры 7 и 9 в нуль. Сигнал лог. 1 с выхода триггера 6 поступает на вхо-. ды установки в нуль триггеров 20 в узлах 12,...,12 „, сравнения и уста" навливает их в "0". Сортировка массива из ш чисел производится за ш циклов, каждый из которых выполняется за (n+2) тактов (n - разрядность сортируемых чисел).

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

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

В первом такте первого цикла с приходом импульса начала первого числа на выходе элемента И 10 получаем лог. "1", которая поступает на установочные входы триггеров 14 узлов 12,,...,23 сравнения и триггера 9 и устанавливает их в единицу.

В каждом узле 12 сравнения сигнал лог."i" c прямого выхода триггера

14 поступает на .вход установки триггера 16 и устанавливает его в единицу. Задним фронтом (перепадом уровня сигнала с лог. "1" в лог."0") импульса начала первого числа триггер 6 устанавливается в нуль. Во втором такте старший разряд первого сортируемого числа поступает на информационный вход 2 и по заднему фронту тактового импульса записывается в триггер 5. Задним фронтом этого же импульса в триггер 7 запи- ., сывается единица. Сигнал лог. "1" на втором и третьем входах элемента

И 8 разрешает прохождение тактовых импульсов через данный элемент. В каждом иэ узлов 12,...,12,„ сравнения коммутатор 21 установлен в положение, когда на его выход поступает, информация с выхода старшего разряда регистра 22 предыдущего узла 1 2 сравнения. Коммутатор 21 первого узла 12 сравнения установлен в положение,когда на его выход поступает информация с выхода триггера 5. В третьем и следующих тактах данного цикла задним фронтом тактового импульса проиэво» дится запись входной информации в триггер 5, сдвиг и запись информации в регистры 22 узлов 12 сравнения. В (n+2)-ом такте работы задним фронтам импульса конца первого числа триггер

6 устанавливается в единицу, а зад" ним фронтом тактового импульса производится сдвиг и запись информации в регистры 22 в уздах: 12 сравнения, Перепадом уровня сигнала на выходе триггера 6 с лог. "0" в лог. "1" производится запись лог. "0" в триггер

14 первого узла 12 сравнения и лог. "1" — в триггер 9 и триггеры 14

1 41001 элементов И всех узлов сравнения объединены, первые входы третьих эле-, ментов И всех узлов сравнения объеди" иены, отличающееся тем, что, с целью расширения области применения за счет возможности сортировки массивов чисел в последовательном коде в реальном масштабе времени, в него введены четыре триггера и в i-й 10 узел сравнений три триггера, элемент

ИСКЛЮЧАЮЩЕЕ ИЛИ и коммутатор, причем информационный вход устройства соединен с информационным входом первого триггера, синхровход которого являет" )5 ся тактовым входом устройства и соединен с синхровходом второго триггера, с первым входом четвертого элемента

И i". го узла сравнения и первым входом первого управляющего элемента

И, второй вход которого соединен с информационным входом второго тригге" ра и с инверсным выходом третьего триггера, а третий вход - с прямым выходом второго триггера, вход уста- 25 новки в "0" которого является входом начальной установки устройства и соединен с входом установки в "1" третье"

r0 триггера, с входами установки в начальное положение всех узлов срав- Зо кения и с входом установки в "0" четвертого триггера, синхровход которого соединен .с первым входом второго управляющего элемента И, с синхровходом первого триггера, с первым входом 35 второго элемента И, с входом установ.ки в "0" второго триггера i-го узла сравнения и прямым выходом третьего триггера, синхровход которого являет" ся входом границ числа устройства и 40 соединен с вторым входом второго управляющего элемента И, третий вход которого соединен с инверсным выходом четвертого триггера и с информационным входом первого триггера первого узла сравнения, а выход соединен с входом установки в единичное состояние четвертого триггера и с входом установки в единичное состояние первого триггера всех узлов сравнения, информационный вход первого триггера g"го узла сравнения соединен с прямым выходом первого триггера (i-1)-го узла сравнения, в каждом ysле сравнения прямой pblxop первого триггера соединен с входом установки в единичное состояние третьего триггера, синхровход которого соеди9 6 нен с синхровходом второго триггера и с выходом четвертого элемента И, второй вход которого соединен с инверсным выходом второго триггера, а третий -вход — с инверсным выходом третьего триггера, с первым входом коммутатора этого же узла сравнения,. инверсный выход третьего триггера (i-1)-ro узла сравнения соединен с вторым и третьим входами коммутатора

i-го узла сравнения, в каждом узле сравнения четвертый вход коммутатора соединен с первым входом первого элемента И и с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, четвертый вход коммутатора (i-1)-ro узла сравнения объединен с пятым входом коммутатора

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

3 141001 остальных узлов 12,...,12 щ сравнения.

Рассмотрим работу устройства в

J-ом (J = 1,..., m) цикле сортировки.

В начале первого такта J-го цикла в регистрах 22 узлов 12„,...,12 сравнения находятся просортированные числа в порядке убывания, наибольшее в первом 12, а наименьшее в J-1-ом 10 узле 12 сравнения. Триггеры 14 узлов

12„,. ° .,12 °, сравнения находятся в нуле, а триггер 9 и триггеры 14 ysлов 12,,...,12 сравнения - в единице, В узлах 12,,...,12, сравнения )5 триггеры 16 и 20 установлены в нуль.

В узлах 12...,.,12ь, сравнения триггеры 16 установлены в единицу, а триггеры 20 — в нуль, В каждом из,узлов

12, ° ...12, сравнения коммутатор 20

21 установлен в положение, когда на

его выход поступает информация с выхода старшего разряда регисТра 22.

В узле 12 сравнения коммутатор 21 установлен в положение, когда на его 25 выход поступает информация с выхода триггера 5. В узлах 12 „,...,12 „, сравнения коммутатор 21 установлен в положение, когда на его выход поступает информация с выхода старшего 30 разряда регистра 22 предыдущего узла

12 сравнения.

В первом такте J-го цикла задним фронтом импульса начала J-ro числа

35 триггер 6 устанавливается в руль, Во втором и последующих тактах работь1 устройства в каждом узле 12 сравнения на первый вход элемента ИСКЛЮЧАЮПДЕ ИЛИ 18 поступает i-й разряд (i = 40

= 1,... n) J-ro числа, а на второй вход " информация с выхода старшего разряда регистра 22, и в случае,.если информация на входах одинакова, то на выходе имеем лог. »0, в против- 45 ном случае — лог. "i". Информация с выхода элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 18 поступает на входы элементов И 17 и

19 и разрешает (лог."1") или запрещает (лог. "0") прохождение информации через эти элементы. Получение лог. "1":на выходе элемента И 17 указывает на то, что i-й разряд J""го числа равен единице, а i-й разряд числа.из регистра 22 — нулю. В случае если i-й разряд числа из регистра 22 равен единице, а i-й разряд J"ro числа " нулю, — то на выходе элемента

И 19 получаем сигнал лог."1".

4

По заднему фронту второго тактового импульса производится запись информации в триггер 5 (старшего разряда), в триггеры 16 и 20 узлов

12,...,12 1 сравнения и в триггер 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 сравнения).

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

Устройство для сортировки чисел, содержащее два управляющих элемента .

И и m узлов сравнения (m - количество сортируемых чисел в массиве), каждый из которых содержит четыре элемента

И и регистр, причем в каждом узле сравнения выход старшего разряда регистра соединен с первым входои,первого элемента И, первые входы::Вторых

1410019

° Ф

° °

° ° . °

° °

° °

° ° Ф° Ф

Ф °

° °

Составитель Е. Иванова

Техред Л. Сердюкова

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

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

Тираж 704

Подписное

Заказ 3480/44

ВНИИПИ Государственного комитета СССР по делам изобретений .и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4