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

(72) А.С.Дыкун,юп. Р 36 Я.С.Пара Л.М.Сергейчу ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССРУ 734675, кл. С 06 Р 7/06, 1978.Авторское свидетельство СССРУ 1022150, кл. С 06 Р 7/06, 1983.(54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ.ЧИСЕЛ, содержащее генератор импульсов, группу из П регистров и и счетчиков, где П - количество сортируемых чисел, триггер, элемент И, первую и вторую группы элементов И поП элементов И в каждой, первый элемент И-НЕ, элемент задержки, причемустановочные входы одноименных регистра и счетчика группы соединеныс входами соответствующего сортируемого числа устройства, выходы регистров и счетчиков являются соответствующими информационными выходами устройства, вход запуска устройства соединен с единичным входомтриггера, прямой выход которого соединен с первым входом элемента И,второй вход которого соединен с выходом генератора импульсов, а выходподключен к первым входам элементовИ первой группы, выходы переполнения счетчиков группы соединены свходами первого элемента И-НЕ, выход элемента задержки подключен к первому входу первого элемента И второй группы, о т л и ч а ю щ е е - с я тем, что, с целью повышения быстродействия за.счет устранения зависимости времени сортировки чисел от разрядности счетчиков, в него введены группа из П триггеров, группа из П элементов ИЛИ и второй элемент И-НЕ, причем первые входы всех элементов И второй группы объединены и соединены с первым входом второго элемента И-НЕ, выход первого элемента И-НЕ подключен к входу элемента задержки, вход запуска устройства соединен с единичными входами всех триггеров группы, прямые выходы которых соединены с С вторыми входами соответствующих элементов И первой группы, а инверс- Я ные выходы - с вторыми входами соответствующих элементов И второй группы и входами второго элемента И-НЕ соответственно с второго по ( П + 1)-й, выход которого является выходом конца сортировки устройства и подключен к нулевому входу триггера, выходы одноименных элементов И первой и второй групп соединены с входами соответствующих элементов ИЛИ группы, выходы которых подключены к счетным входам соответствующих счетчиков группы, выходы переполне- )ь ния.которых дополнительно подключены к нулевым входам соответствующих триггеров группы.1 1182 Устройство относится к вычисли-. тельной технике и может быть исполь зовано для анализа процессов, вчастности для определения функциираспределения случайных процессов идля других вычислений, требующих сортировки значений переменных в зависимости от их величины.Цель изобретения - повышение быстродействия за счет устранения зависи 10мости времени сортировки чисел отразрядности счетчиков для храненияпеременных,На чертеже представлена схемапредлагаемого устройства, 15Устройство для сортировки и чиселсодержит генератор импульсов 1, элемент И 2, триггер 3, группу из лрегистров 4 4, и счетчиков5,, 5, первый элемент И-НЕ 6,. 20элемент задержки 7, первую группу изЬ элементов И 8 , , 8 группу изэлементов ИЛИ 9, 9, вторуюгруппу из и элементов И 10 10 л,группу из л триггеров 11 11 1, 25второй элемент И-НЕ 12, входы 13,13 л сортируемых чисел, выходырегистров, выходы 15, , 15 счетчиков, вход 16 запуска, выход 17конца сортировки, Величина задержкиимпульсов элемента 7 меньше периодаследования сигналов генератора 1.Разрядность регистров 4 и счетчиков5 определяет максимальную величинуподлежащего сортировке числа, котораяравна 2 -2,Устройство работает следующимобразом,Перед сортировкой в регистры 4 исчетчики 5 по входам 13 13 записываются числа, подлежащие сортировке, причем в одноименные регистры и счетчики 4,-5 4"5записываются одинаковые числа,Входы 13 включают информационныеи управляющие шины, Запись чисел врегистры 4 и счетчики 5 может осуществляться как параллельным, таки последовательным способом в зависимости от конкретных условий приме Онения устройства.Сортировка чисел начинается по приходу импульсного пускового сигна" ла отрицательной полярности, который с входа 16 поступает на единичные входы триггеров 3, 11 11, устанавливая их в единичное состояние. С прямого выхода триггера 3 510 2 на первый вход элемента И 2 поступает сигнал "1"С.прямых выходов триггеров 111, , 11 поступают сигналы на вторые входы элементовИ 88. Импульсы с выхода генератора 1 поступают через элементИ 2, элементы И 88, и элементыИЛИ 91 9 на счетные входысчетчиков 51, , 5,. По каждомуимпульсу счетчики 5 увеличивают своесостояние на "1". Импульс переполнения, в первую очередь, появляетсяна выходе счетчика, в котором былозаписано максимальное число. Этототрицательный импульс по нулевомувходу переключает в нулевое состояние соответствующий триггер 11 группы триггеров. С инверсного выходаэтого триггера разрешающий сигналпоступает на второй вход соответствующего элемента И 10 и на входэлемента И-НЕ 12. Одновременно отрицательный импульс переполнения поступает на соот ветствующий вход элемента И-НЕ 6. С его выхода положительжй импульс,задержанный на элементе задержки 7,через открытый соответствующий элемент И 10, соответствующий элементИЛИ 9 поступает на счетный входсоответствующего счетчика 5 и.увеличивает его состояние на "1". Еслисчетчик 5 вырабатывает сигнал переполнения при единичных сигналах вовсех разрядах, он переходит в состояние, когда во всех разрядах нулевыесигналы. Следующий импульс переполнения возникает на выходе того счетчика, в котором записано число,являющееся максимальным из оставшихся, Этим отрицательным импульсом по нулевому входу сбрасывается в . нулевое состояние следующий соответствующий триггер 11 из группы триггеров. С его инверсного выходаразрешающий сигнал поступает на соответствующий вход элемента И-НЕ 12 и на второй вход соответствующего элемента И 10. С выхода элемента 7 задержанный импульс переполнения через открытые элементы И 10 группы, через элементы ИЛИ 9 группы увеличивает на "1" состояние счетчиков, в которых выработался сигнал переполнения, Аналогично процесс сортировки продолжается для других чисел,При возникновении импульса переполнения в счетчике, где записанонаименьшее число по нулевому входу, сбрасывается в нулевое состояние оставшийся соответствующий триггер 11, с инверсного выхода, которого сигнал разрешения поступает на второй вход соответствующего элемента И 10 и на соответствующий вход элемента И-НЕ 12. При этом на входы элемента И-НЕ 12 с инверсных выходов всех триггеров 11 поступают сигналы "1", 10 и по задержанному импульсу переполнения с выхода элемента 7 на выходе элемента И-НЕ 12 появляется сигнал "Сортировка завершена" отрицательной полярности, который по нулевому 15 входу сбрасывает в нулевое состояние триггер 3. Сигнап 0 с прямого выхода триггера 3 поступает на первый вход элемента И 2 и запрещает прохождение импульсов генератора 1 на 20 счетчики 5, , 5. Одновременно задержанный импульс переполнения с выхода элемента 7 через открытые элементы И 1 О, элементы ИЛИ 9 увеличивает состояние счетчиков 5, 255 на "1", Таким образом, в счетчике, где находилось наименьшее число, записан наименьший код, в счетчике, где находилось максимальное число, записан наибольший код, а в остальных счетчиках - "промежуточные" коды в соответствии с положением числа на числовой оси. Если все числа, подлежащие сортировке, разные,то в счетчиках 5 5записанкод от 0 до - 1. Наименьыему числусоответствует код О, наибольшему - 1.Если из состава чисел, подлежащихсортировке, будет несколько чисел содинаковыми значениями, то после сор тировки в соответствующих счетчикахбудут записаны одинаковые значения.П р и м е р. Необходимо произвести сортировку четырех чисел, которые записаны в следующем порядке: в регистре 4 и счетчике 5, находится максимальное число, в регистре 44 и счетчике 5 находится второе по ве 4личине число, минимальное число находится в регистре 41 и счетчике 5. Счетчики 5 вырабатывают сигнал переполнения в случае, когда во всех разрядах будут "1,"После прихода импульса запуска с 55 входа 16 импульсы генератора 1 начинают поступать на счетные входы счетчиков 5 1, , 5, как описывалось выше. Импульс переполнения, в первую очередь, появится на выходе счетчика 5 так как в нем было записано максимальное число. Импульс переполнения по нулевому входу сбросит в нулевое состояние триггер 11 в результате чего элемент И 8 э закроется для прохождения импульсов генератора, а с инверсного выхода триггера 11, на второй вход элемента И 10з и на третий вход элемента И-НЕ 12 поступит сигнал 1111. Одновременно импульс переполнения поступит чере элемент И-НЕ 6 на элемент задержки 7. Задержанный импульс переполнения через элемент И 10 элемент ИЛИ о,1 1запишет С в счетчик 5 . Сл ед ующн импульс переполнения возникнет на выходе счетчика 5 , по которому сбросится в нулевое состояние триггер 1 1 4 . Элемент И 8 закроется для прохождения импульсов генератора, с инверсного выхода триггера 1 1 4 , сигнал " 1 " поступит на второй вход элемента И 1 04 и на второй вход эле - мента И-НЕ 1 2 . Задержанный импульс переполнения с выхода элемента 7 через элементы И 1 О, ИЛИ 9, з апише -. " 0 " в счетчик 5 , а через элементы И 1 О, , ИЛИ 9 в .1 " в счетчике 5, . Следующий импульс переполнения появит ся на втором выходе счетчика 5, , по которому сбросится в нулевое состояние триггер 1 1 2 . Элемент И 8, закроется для прохождения импульсов генератора 1 на счетчик 5, . Сигнал " 1 " с инверсного выхода триггера 1 1, поступит на второй вход эл еме нта И 1 О и на четвертый вход элемента И-НЕ 1 2Задержанный импульс переполнения с выхода элемента 7 через соответствующие элементы з апишет " 0 " в счетчик 5, , " 1 " - в счет,чик 54 , " 2 " - в счетчик 5, . Последний импульс переполнения будет выр абота н на втором выходе счетчика 5 , по которому установится в нулевое состояние триггер 1 1 1 и будет запрещено прохождение импульсов генератора 1 через элемент И 8 1 , С инверсного выхода триггера сигнал " 1 " поступит на второй вход элемент а И 1 01 и на пятый вход элемента И-НЕ 1 2 , Так как на входы элемента И-НЕ 1 2 с инверсных выходов три г геров 1 1, , . . ., 1 1поступают сигналы " 1 ", по сигналу с выхода элемента 7 на выходе элемента И-НЕ 1 2 выра.Сирохма актор И.Циткина Заказ 6107/47 Филиал ППП Патент, г. Ужгород, ул. Проектна батывается отрицательный сигнал"Сортировка завершена", по которомупо нулевому входу сбрасывается в нулевое состояние триггер 3 и запрещается прохождение импульсов генератора 1 через элемент И 2. Одновременно задержанный импульс переТираж 09 НИИПИ Государственного по делам изобретений 5, Иосква, Ж 35 Рауысполнения с выхода элемента 7 через соответствующие элементы запишет О в счетчик 5, 1 - в счетчик" - в счетчик 5 ф3 - в счетчик 5 . Таким образом, в счетчиках 5 будутзаписаны коды, соответствующие величине подлежащихсортировке чисел. Подписноеомитета СССРоткрытийя наб., д, 4/5