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

(51)4 С 0 ОПИСАНИЕ ИЗОБРЕТЕН ВИДЕТЕЛЬСТВУ Н АВТОРСКОМ(54 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ(61) 11825 10 (21) 4046222/4-24 (22) 31.03,86 (46) 07.07.87. Бил. Ф 25 (72) В.Н, Горшков, В.П. Невский, А.М. Заяц и В.Г. Терехов (53) 681,325 5 (088.3) (56) Авторское свидетельство СССР У 1182510, кл. С 06 Е 7/06, 1984,) УСТРОЙСТВО ДЛЯ СОРТИРОВЕИ ЧИСЕ (57) Изобретение относится к ычислительной технике и может быть использовано для анализа процессов, в частности для определения функции распределения случайньх процессов и для других вычислений, требующих сортировки значений переменных в зависимости от их величины и являет ся усовершенствованием устройстваГ по а.с. к" 1182510. Цель изобретенияповышение быстродействия устройства.Устройство содержит генератор 1 импульсов, группу регистров 4 и счетчиков 5, триггер 3, элемент И 4,группы элементов И 8, 10 и 16, дваэлемента И-НЕ 6 и 12, элемент задержки, группу триггеров 11 и группуэлементов ИЛИ 9, элемент НЕ 17, дополнительньй элемент 18 задержки.Введение третьей группы элементов И16 позволяет производить предварительный анализ сортируемых чисел,если все они содержат в 1-м разрядекод "0", то происходит увеличениесодержимого всех счетчиков на величину 2, Соответственно количествотактов, затрачиваемых на сортировку,уменьшается на 2, что повьппает быстродействие устройства. 1 ил.ИЗОбГ)СТО 1 С ООГ)тс 51 К ВЫГЛ- тотС) тГХСГ МО)Кот бттт ЦГП 05 Ьзоца О дття дцдлизд процессов, в частности для Определения 1)уцктци рдспРС:тЕ)тепЯ СЛУЧайНЫХ ПРОЦЕСГОВ И ДЛЯ других вычислений, требующ гх сортировки значений переменцых в эдвисимости от их величцы, и является усо ершецствованием устройстид по ацт. св. К 1182510.Цель изобретения - повышение бы- СтРОДГйСтГ)т)т УСтРОйСтВа.Нд чертеже гредстдтленд схелд цредлдгдемого устройства,Устротство для сортировки и чисел содержит генератор 1 импульсов, эле.н.цг И 2, триггер 3, группу з и ре- гистРОВ 4, . . 4счетчков 5,ффр.р РУштУ из и э)теметот) И 8 р 8. группу цз элементов ИЛИ 9 .9., Вторук группу из т )лсГтОВ И 10, р,10, группу 1 грт геро)1 1111, элемент И-Н"., 12, т)ходы 13 р,13 сорруомтх чисел, Выхтд 141)регсрОВ р Выходы 15 .15 счетчиков, группу эле- ).тОВ И 16, элсмецт НЕ 17, дополцигсьгй элемент 18 эддер)к 1, вход 19 .1;т)уГКд ц ВЫход 20 КОтт, Сот)ттроКИ.1 )цццд эддержк Вцтульсов зле:)стд 7 мГьце периода Гледовдция с:;1 .тд ст гс:цердторд 1, Эд тсржкд эле.)с )ГГдЯ дт"т. )и бмтт ОС.тдттОЧой дц:)ДсжОО Срт) С т 11 ) 11 СЧ 1 Ч кО 1) ),дрядос 1 т)тзГ 11 Гтрот 4 11 сч гт 1 и )тдц ;1 п;1сДс) тл е 1 М 1) С )511 С) т)т:1 тУ Г)5)тСтжтЦС ОтС) 1;1, ) д т ут) 2 - 2Ус трс)йстт)с) р;)ботс)т т следуа)цм обрдэо.т,Нсрец ссртиро 1 кой В ригстры 4 ис 1 е гчк)1 . по В ходм 1 т) рэ р 1 3З,тт ЫВ:)ВтС.)1 ЧГЛД, ЦС;)ЛижапЕ СОРтцРС)т;С ЦР)СМ С)ДЦО.1 ЕЦЫГ РЕГстр 1. 11 счстчкц т), - 54т;1 Гьтт)т)0)Г)т ОДЦ)КО В,)О ЧЦС.),1,8:,Одь 13 Вкгст;1 т 111)с)р 1511 Оццые11 у 1 )т) т 1)1)ц 11" Пц,)ЭдпГЬ "СЕЛ В)Ггсры 5 .1 Гчстчкц 5 с)е г осуЩС т Гтся КДК ДРтп)Е)ЬЦ)р тДК ИГсОДО)дтсл) тц ц) ГОГОбОм В здвс М, т ) С)т КОКрвт)ПХ усгОВ ПрМЕЕ)) УГтНОйстд,Пр., псГтулецт цд Вход 19 мпульс.Гт О цу.)сс)Ого сгцдлд Отр;ательой ЦЛЯРОС.т ЦД ЫХОДС. )ЛС МЕЦ Га1)1,7 ,тут. 1)я с;т 1 ит)ци с цгцдл,.1322257 2поступающий на первые входы всех элементов И 16. Если все сортируемыечисла в каком-либо или несколькихразрядах содержат т)0, то за счетсигналов на инверсных выходах регистров 4 откроются соответствующиеэлементы И 16. Это обеспечивает установку в 1" определенных разрядоввсех счетчиков 5.10 Через время задержки элемента18 сигнал отрицательной полярностипоступает на единичные входы триггеров 3 и 1,.,11, устанавливая ихв единичное состояние. С прямого выхода триггера 3 на первый вход элемента И 2 поступает сигнал "1". Спрямых выходов триггеров 11 ,..,р11 поступают сигналы на вторые входыэлементов И 8,. 8. Импульсы с вы 20 хода генератора 1 поступают черезэлемент И 2, элементы И 8 8н элементы ИЛИ 9,9 на счетныерифрвходы счетчиков 55.2511 о каждому импульсу счетчики 5увеличивают свое состояние на "1"Импульс переполнения, в первую очередьр появляется на выходе счетчика,в котором было записано максимальноечисло. Этот отрицательный импульс поцулевому входу переключает в нулевое состояние соответствующий триггер 11 группы триггеров. С инверсного выхода этого триггера разрешающийсигнал поступает на второй вход со 35 Ветстцующего элемента И 1 О и наВход элемента И-НЕ 12,Одновременно отрицательный импульспереполнения поступает на соответствующтий вход элемента И-НЕ 6. С еговыхода положительный импульс, задержанный ца элементе 7 задержки черезОткрытый соответствующий элемент И10, соответствующий элемент ИЛИ 9поступает на счетный вход соответствующего счетчика 5 и увеличиВдет его состояние на "1"Еслисчегчик 5 вырабатывает сигнал пере 1)опения при единичных сигналах вовсех разрядах,он переходит в состояние,50 когда во всех разрядах нулевые сигналы,Следующий импульс переполнениявозникает нд выходе того счетчика,в котором записано число, являющеесямаксимальным из оставшихся. Этим55отрицательным импульсом по нулевомувходу сбрасывается в нулевое состояние следующий соответствующий триггер 11 из группы триггеров. С егоинверсного выхода разрешающий сигналпоступает на соответствующий входэлемента И-НЕ 12 и на второй вход соответствующего элемента И 10, С выхода элемента 7 задержанный импульс 5 10 15 20 25 30 35 40 45 50 55 переполнения через открытые элементыИ 10 группы, через элементы ИЛИ 9группы увеличивает на "1" состояниесчетчиков, в которых выработалсясигнал переполнения. Аналогично процесс сортировки продолжается для других чисел,При возникновении импульса переполнения в счетчике, где записанонаименьшее число по нулевому входу,срабатывается в нулевое состояниеоставшийся соответствующий триггер1, с инверсного выхода которого сигнал разрешения поступает на второйвход соответствующего элемента И 10и на соответствующий вход элементаИ-НЕ 12, При этом на входы элемента И-НЕ 12 с инверсных выходов всехтриггеров 11 поступают сигналы "1"и по задержанному импульсу переполнения с выхода элемента 7 на выходеэлемента И-НЕ 12 появляется сигналнСортировка завершенан отрицательной полярности, который по нулевомувходу сбрасывает в нулевое состояниетриггер 3,Сигнал "0 с прямого выхода триггера 3 поступает на первый вход элемента И 2 и запрещает прохождениеимпульсов генератора 1 на счетчики5,.,5. Одновременно задержанныйимпульс переполнения с выхода элемента 7 через открытые элементыИ 10, элементы ИЛИ 9 увеличивает состояние счетчиков 5 5 на "1",Таким образом, в счетчике, где находилось наименьшее число, записаннаименьший код, в счетчике, где находилось максимальное число, записаннаибольший код, а в остальных счетчиках - "промежуточные" коды в соответствии с положением числа на числовой оси, Если из состава чисел,подлежащих сортировке, несколько чисел с одинаковыми значениями, то после сортировки в соответствующихсчетчиках будут записаны одинаковыезначения.П р и м е р. Необходимо произвести сортировку четырех чисел, которыезаписаны в следующем порядке: в регистре 4 и счетчике 5 находитсямаксимальное число 00110 (младший разряд справа ), в регистре 4 и счетчике 5 - второе по величине число 00101, в регистре 4 и счетчике 5 - число 00010, минимальное , число 00001 находится в регистре 4 и счетчике 5, . Счетчики 5 вырабатывают сигнал переполнения в случае, ког. да во всех разрядах будут "1".При поступлении на вход 19 импульсного пускового сигнала отрицательной полярности на выходе элемента НЕ 17 формируется единичный сигнал, поступающий на первые входы всех элементов И 16. Так как в двухстарших разрядах сортируемых чиселсодержится код 0, то за счет сигналов на инверсных выходах регистров 4 открываются два соответствующих элемента И 16, Это обеспечиваетустановку в "1" двух старших разрядов всех счетчиков 5: в счетчике5 знаходится число 11110, в счетчике5 - число 11101, в счетчике 5число 11010 и в счетчике 5, - число11001,Через время задержки элемента 18импульсы генератора 1 начинают поступать на счетные входы счетчиков5 5 . Импульс переполнения, в1первую очередь, появится на выходесчетчика 5, так как в нем было записано максимальное число. Импульспереполнения по нулевому входу сбросит в нулевое состояние триггер 11Фв результате чего элемент И 8 зак 3роется для прохождения импульсов генератора, а с инверсного выходатриггера 11 на второй вход элемента И 10 и на третий вход элементаИ-НЕ 12 поступит сигнал "1".Одновременно импульс переполненияпоступит через элемент И-НЕ 6 на элемент 7 задержки. Задержанный импульспереполнения через элемент И 10,элемент ИЛИ 9 запишет "0" в счет 3чик 5 . Следующим импульс переполнения возникнет на выходе счетчика 5Впо которому сбросится в нулевое состояние триггер 11, Элемент И 8закроется для прохождения импульсов генератора с инверсного выхода триггера 11 , сигнал "1 поступит навторой вход элемента И 10 и на второй вход элемента И-НЕ 12,Задержанный импульс переполненияс выхода элемента 7 через элементыИ 10 и ИЛИ 9 запишет "0" в счетчик 5 , а через элементы И 1 О ИПИ 91322257 Формула изобретения Сэставитель Е. ИвановаТехред А. Кравчук Корректор С. Шекмар Редактор П. Гереши Заказ 28 б 4/44 Тираж 672 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб д,4/5"1" в счетчик 5 . Следующий им 3пульс переполнения появится на втором выходе счетчика 52, по которому сбросится в нулевое состояние триггер 11 , Элемент И 8 закроется для про2хождения импульсов генератора 1 на счетчик 52, Сигнал "1" с инверсного выхода триггера 11 поступит, на второй вход элемента И 102 и на четвертый вход элемента И-НЕ 1210Задержанный импульс переполнения с выхода элемента 7 через соответствующие элементы запишет 11011 в счетчик 5 , "1" - в счетчик 5 , "2" в счетчик 53 . Последний импульс переполнения будет выработан на втором выходе счетчика 5, по которому устанавливается в нулевое состояние триггер 11, и будет запрещено прохождение импульсов генератора 1 через 20 элемент И 8 .С инверсного выхода триггера сигнал "1" поступит на второй вход элемента И 1 О и на пятый вход элемента И-НЕ 12. Так как на входы элемента И-НЕ 12 с инверсных выходов триггеров 1111 поступают сигналы "1", по сигналу с выхода элемента 7 на выходе элемента И-НЕ 12 вырабатывается отрицательный сигнал 1 Сортировка завершена , по которому по нулевому входу сбрасывается в нулевое 6состояние триггер 3 и запрещается прохождение Импульсов генератора 1 через элемент И 2.Одновременно задержанный импульс переполненияс выхода элемента 7 через соответствующие элементы запишет "0" в счетчик 5 "1" - в счетчик 5 , "2" - в счетчик 5 , "3" - в счетчик 5 . Таким образом, в счетчик 5 будут записаны коды, соответствующие величине подлежащих сортировке чисел. Устройство для сортировки чисел по .авт.св. 1 1182510, о т л и ч а ющ е е с я тем, .что, с целью повышения быстродействия, в него введены третья группа из м элементов И, элемент НЕ и дополнительный элемент задержки, выход которого соединен с единичными входами всех триггеров, а вход является входом запуска устройства и соединен через элемент НЕ с первыми входами элементов И третьей группы, инверсные выходы -х разрядов регистров группы, где =1,2 ш, подключены к входам с второго по (и+1)-й элемента И третьей группы, выход которого соединен с дополни 11 11 тельными входами установки в-х разрядов всех счетчиков .