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

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ .ЧИСЕЛ, содержащее генератор импульсов , группу из П регистров и п счетчиков , где и - количество сортируемых чисел, триггер, элемент И, первую и вторую группы элементов И по П элементов И в каждой, первый элемент И-НЕ, элемент задержки, причем установочные входы одноименных регистра и счетчика группы соединены с входами соответствующего сортируемого числа устройства, выходы регистров и счетчиков являются соответствующими информационными выходами устройства, вход запуска устройства соединен с единичным входом триггера, прямой выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом генератора импульсов, а вьпсод подключен к первым входам элементов И первой группы, выходы переполнения счетчиков группы соединены с входами первого элемента И-НЕ, выйснгоюгжи 3.::.:::j3 Зйблйоте л ход элемента задержки подключен к первому входу первого элемента И второй группы, отличающеес я тем, что, с целью повышения быстродействия за.счет устранения зависимости времени сортировки чисел от разрядности счетчиков, в него введены группа из П триггеров, группа из п элементов ИЛИ и второй элемент И-НЕ, причем первые входы всех элементов И второй группы объединены и соединены с первым входом второго элемента И-НЕ, выход первого элемента И-НЕ подключен к i входу элемента задержки, вход запуска устройства соединен с единич (Л ными входами всех триггеров группы, с прямые выходы которых соединены с вторыми входами соответствующих элементов И первой группы, а инверсные выходы - с вторыми входами соответствующих элементов И второй группы и входами второго элемента И-НЕ соответственно с второго по

I (19) (11) СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИК (51)4 G 06 F 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

БИЬДМ() TERA

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3733909/24-24 (22) 18.04.84 (46) 30.09.85. Вкп. Р 36 (72) А.С.Дыкун, Я.С.Парамуд и Л.M.Ñåðãåé÷óê (53) 681. 325 (088. 8) (56) Авторское свидетельство СССР № 734675, кл. G 06 F 7/06, 1978.

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

¹ 1022150, кл. G 06 F 7/06, 1983. (54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ .ЧИСЕЛ, содержащее генератор импульсов, группу из П регистров и и счетчиков, где П вЂ” количество сортируемых чисел, триггер, элемент И, первую и вторую группы элементов И по

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

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

И-НЕ соответственно с второго по (l1 + 1)-й, выход которого является выходом конца сортировки устройства и подключен к нулевому входу триггера, выходы одноименных элементов И первой и второй групп соединены с входами соответствующих элементов

ИЛИ группы, выходы которых подключены к счетным входам соответствующих счетчиков группы, выходы переполнения.которых дополнительно подключены к нулевым входам соответствующих триггеров группы. ь 1182

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

Цель изобретения — повьппение быстродействия за счет устранения зависи 10 мости времени сортировки чисел от разрядности счетчиков для хранения переменных, На чертеже представлена схема предлагаемого устройства. 15

Устройство для сортировки о чисел содержит генератор импульсов 1, элемент И 2, триггер 3, группу из п регистров 4,...,4„, и счетчиков

5„,. ., 5>, первый элемент И-НЕ 6,- 20 элемент задержки 7, первую группу из

h элементов И 8,,..., 8,, группу из элементов ИЛИ 9,,..., 9„, вторую группу из р элементов И 101,..., 10п, группу из л триггеров 11,..., 1111, 25 второй элемент И-НЕ 12, входы 13 »

13д сортируемых чисел, выходы регистров, выходы 15, ..., 15„ счетчиков, вход 16 запуска, выход 17 конц сортировки. Величина задержки импульсов элемента 7 меньше периода следования сигналов генератора 1..

Разрядность регистров 4 и счетчиков

5 определяет максимальную величину подлежащего сортировке числа, которая

Щ равна 2 -2.

Устройство работает следующим образом.

Перед сортировкой в регистры 4 и счетчики 5 по входам 13,..., 13„ за- 40 писываются числа, подлежащие сортировке, причем в одноименные регистры и счетчики 41-5I., " 4„-5 h записываются одинаковые числа.

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

Сортировка чисел начинается по приходу импульсного пускового сигнала отрицате.льной полярности, который с входа 16 поступает на единич- 55

ые BxoUbl триггеров устанавливая их в единичное состояние. С прямого выхода триггера 3

510 2 на первый вход элемента И 2 поступает сигнал "1" ° С. прямых выходов триггеров 111, ..., 11„ поступают сигналы на вторые входы элементов

И 84, ° . °,8п И ульсы с в dopa геНератора 1 поступают через элемент

И 2, элементы И 8„,...,8 и элементы

ИЛИ 9» ..., 9 на счетные входы счетчиков 51, ..., 5,„. По каждому импульсу счетчики 5 увеличивают свое состояние на "1". Импульс переполнения, в первую очередь, появляется на выходе счетчика, в котором было записано максимальное число. Этот отрицательный импульс по нулевому входу переключает в нулевое состояние соответствующий триггер 11 группы триггеров. С инверсного выхода этого триггера разрешающий сигнал поступает на второй вход соответствующего элемента И 10 и на вход элемента И-НЕ 12.

Одновременно отрицательный импульс переполнения поступает на соответствующий вход элемента И-HE 6.

С его выхода положительный импульс, задержанный на элементе задержки 7, через открытый соответствующий элемент И 10, соответствующий элемент

ИЛИ 9 поступает на счетный вход соответствующего счетчика 5 и.увеличивает его состояние на "1". Если счетчик 5 вырабатывает сигнал переполнения при единичных сигналах во всех разрядах, он переходит в состояние, когда во всех разрядах нулевые сигналы. Следующий импульс переполнения возникает на выходе того счетчика, в котором записано число, являющееся максимальным из оставшихся. Этим отрицательным импульсом по нулевому входу сбрасывается в . нулевое состояние следующий соответствующий триггер 11 из группы триггеров. С его инверсного выхода разрешающий сигнал поступает на соответствующий вход элемента И-НЕ 12 и на второй вход соответствующего элемента И 10. С выхода элемента 7 задержанный импульс переполнения через открытые элементы И 10 группы, через элементы ИЛИ 9 группы увеличивает на "1" состояние счетчиков, в которых выработался сигнал переполнения. Аналогично процесс сортировки продолжается для других чисел.

При Возникновении импульса переполнения в счетчике, где записано

1182510 4 наименьшее число по нулевому входу, сбрасывается в нулевое состояние оставшийся соответствующий триггер

11, с инверсного выхода, которого сигнал разрешения поступает на второй вход соответствующего элемента И 10 и на соответствующий вход элемента

И-НЕ 12. При этом на входы элемента

И-НЕ 12 с инверсных выходов всех триггеров 11 поступают сигналы "1", 10 и по задержанному импульсу переполнения с выхода элемента 7 на выходе элемента И-НЕ 12 появляется сигнал

"Сортировка завершена" отрицательной полярности, который по нулевому 15 входу сбрасывает в нулевое состояние триггер 3. Сигнап О с прямого выхода триггера 3 поступает на первый вход элемента И 2 и запрещает прохождение импульсов генератора 1 на 20 счетчики 5, ..., 5 . Одновременно задержанный импульс переполнения с выхода элемента 7 через открытые элементы И 1О, элементы ИЛИ 9 увеличивает состояние счетчиков 5„, 25

5„на "1". Таким образом, в счетчике, где находилось наименьшее число, записан наименьший код, в счетчике, где находилось максимальное число, записан наибольший код, а в остальных счетчиках - "промежуточные" коды в соответствии с положением числа на числовой оси. Если все числа, подлежащие сортировке, разные, то в счетчиках 5,..., 5 записан код от О до — 1. Наименьыему числу соответствует код О, наибольшему — 1.

Если из состава чисел, подлежащих сортировке, будет несколько чисел с одинаковыми значениями, то после сор-40 тировки в соответствующих счетчиках будут записаны одинаковые значения.

Пример. Необходимо произвести сортировку четырех чисел, которые записаны в следующем порядке: в регистре 4 и счетчике 5, находится максимальное число, в регистре 44 и счетчике 5 находится второе по ве4 личине число, минимальное число находится в регистре 4 и счетчике 5».

Счетчики 5 вырабатывают сигнал переполнения в случае, когда во всех разрядах будут "1." °

После прихода импульса запуска с 55 входа 16 импульсы генератора 1 начинают поступать на счетные входы счетчиков 5 1, ..., 5, как описывалось выше. Импульс переполнения, в первую очередь, появится на выходе счетчика 5,, так как в нем было записано максимальное число. Импульс переполнения по нулевому входу сбросит в нулевое состояние триггер 11,, в результате чего элемент И 8 закроется для прохождения импульсов генератора, а с инверсного выхода триггера

11, на второй вход элемента И 10 з и на третий вход элемента И-НЕ 12 поступит сигнал "1". Одновременно импульс переполнения поступит чере..элемент И-НЕ 6 на элемент задержки

7. Задержанный импульс переполнения через элемент И 10,, элемент ИЛИ 1, ll )lt запишет С в счетчик 5 . Следующ.*н импульс переполнения возникнет на выходе счетчика 5, по которому сбросится в нулевое состояние триггер 11А . Элемент И 8 закроется для прохождения импульсов генератора, с инверсного выхода триггера 114 сигнал " 1" поступит на второй вход элемента И 104и на второй вход эле— мента И-НЕ 12. Задержанный импульс переполнения с выхода элемента 7 через элементы И 10, ИЛИ 9, запише-.

"О" в счетчик 5, а через элементы

И 10,, ИЛИ 9 †. 1" в счетчике 5, .

Следующий импульс переполнения появится на втором выходе счетчика

5,, по которому сбросится в нулевое состояние триггер 11 . Элемент И 8, закроется для прохождения импульсов генератора 1 на счетчик 5, . Сигнал

"1" с инверсного выхода триггера

11, поступит на второй вход элемента И 10 и на четвертый вход элемента И-НЕ 12 ° Задержанный импульс переполнения с выхода элемента 7 через соответствующие элементы запишет "0" в счетчик 5,, "1" — в счет,чик 54, 2 — в счетчик 5, . Последний импульс переполнения будет выработан на втором выходе счетчика

5», по которому установится в нулевое состояние триггер 111 и будет запрещено прохождение импульсов генератора 1 через элемент И 81 С инверсного выхода триггера сигнал

"1" поступит на второй вход элемента И 101 и на пятый вход элемента

И-НЕ 12. Так как на входы элемента

И-НЕ 12 с инверсных выходов триггеров 11,,..., 11 поступают сигналы

"1", по сигналу с выхода элемента

7 на выходе элемента И-НЕ 12 выра1182510

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

Редактор И.Циткина Техред А.Кикемезей Корректор Е.Сирохман

4аказ 6107/47 Тираж 709 Подписное

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

1 13035, Иосква, Ж-35, Рауыская наб., д. 4/5

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4 батывается отрицательный сигнал

"Сортировка завершена", по которому по нулевому входу сбрасывается в ну-. левое состояние триггер 3 и запрещается прохождение импульсов генератора 1 через элемент И ?. Одновременно задержанный импульс переполнения с выхода элемента 7 через соответствующие элементы запишет

"0 в счетчик 5, "1 — в счетчик

5, "2" — в счетчик 51, "3" - в счетчик 5 . Таким образом, в счетчиках

5 будутзаписаны коды, соответствующие величине подлежащихсортировке чисел.