Устройство для сортировки разрядных чисел

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(и 16378 1) М. Кл. 606 Р 7 Госуда Совета по д(45) Дата опубликования описания 15.1273 зобретеиия в.Р.пота) уСтРОЙСтВО ДЛЯ СОРТИРОВКИ 1 т 1 Д -РЕез: ЯД 11 ЫКЧИСЕЛ 2" чис тение относится к области и и вычислительной техники и ь использовано в системах информации при реализации их средств цифровых вычисли ашин и дискретной автоматики. но устройство для сортировых чисел 11, в котором исы программные методы сортио не имеет схемы для пере мажоритарного элемента, поможет быть использовано для нного выбора чисел. Это устбладает низким быстродейстбр с хранящимися числ - разрядность чис лью изобретения яв ыстродействия устр ить де яется повьпйства. е ие вием. 16Наиболее близким к данному изобретению техническим решением является устройство для сортировки 111 11-разрядных чисел, содержащее т 1 регистров, выходы каждого из которых соединены а 0 со входами схем сравнения, другие входы которых подключены к выходам регистра результата, выходные шины схем сравнения соединены через переключатели со входами элемента ИЛИ, элемента И, триггер, узлы запрета 2Недостатком этого устройства является низкое быстродействие, так как для анализа информации во всем каталоге необходимо сформировать и срававтоматиможет быобработктехничестельных мИзвески двоичпользоваровки. Оключенияэтому неупорядочройство Это достигается тем, 1 то в предлагаемом устройстве ьыход равенства каждой схемы сравнения соединен с управляющим входом соответству ощего узла запрета, другие входы которого подключены к управляющим шинам устройства, а выход - к одному из входов первого элемента И, другой вход которого соедине с входной шиной устройства, а выход - с управляющим входом схемы сравнения, выход элемента ИЛИ соединен со входом триггера, другой вход которого соединен с шиной тактовых сигналов, а выходы - через переключатель - со входом второго элемента И, другой вход которого соединен с управляющей шиной устройства, а выход со входом установки в нулевое состояние регистра результатавход 1 л Гсразрядного управления которого подключены к выходам коммутатора, вход которого соединен с шинсй тактовых сигналов, а входы установки в единич йое состояние разрядов регистра результата подключены к управляющей шина устройства.Благодаря указанным конструктивным связям повьпаается быстродействие, так как для упорядоченного перебора этих чисел требуется (641). Ф тактов ра боты.Это позволяет значительно (на 2-4 порядка) повысить быстродействие уст, ройства для сортировки я я -Разрядных чисел.Функциональная схема устройства приведена на ертее.Устройство СОдержит Ф реГистров 1, Я В кОтОрые записываются исходные чис ла, и регистр результата 2, в котором Формируется ОчереДнОе максимальное (минимальное) число. Единичные и нулеВые выходы Регистров 1 и 2 соединены )5 с инФОРмационными входами схем сраВ нения 3 управляющие Вх которы подключены к входной шине 4 через перВые элементы И 5, Первые и втОРые ВыхОДы неравенства схем 3 В заВиси мости от положения переключателя б, связаны с соответствующими входами элемента ИЛИ 7, выход которого соединен со входом установки В нулевое состояние тригра 8, Выоды Раенс схем сравнения 3 подключены к управ 25 ляющему входу соответствующих узлов запрета 9, вторые и третьи входы которых связаны соответственно с управляющими шинами 10 и 11. Выходы узлов 9 соединены со вторыми входами соответствующих элем нтов И 5. Вход установки в единичное состояние триггера 8 подключен к шине тактовых сигналов 12, а его прямой к инверсный Выходы связаны через переключатель б с пер вым входом второго элемента И 13, Второй вход которого подключен к управляющей шине 14. Выход элемента И 13 соединен с входом установки в нулевое состояние Регистра результата 2.Входы 40 поразрядного управления регистра результата 2 подключены к соответствующим выходам коммутатора 15, вход которого связан с шиной тактовых сигналов 12. Входы установки разрядов Регистра результата 2 в единичное состояние соединены с управляющей шиной 1 б.устройство Работает следующим образом.В начале работы переключатель б переводится в положение, соответствующее сортировке чисел в порядке их убывания илн возрастания (положение переключателя б на чертеже соответствует сортировке чисел в порядке их убывания). Затем в Регистры 1 заносятся исходные числа, а регистр результата 2 и коммутатор 15 сбрасываются в исходное состояние ( цепи занесения информации в Регистры 1 и установки в нуль регистра 2 н коммутатора 15 на чертеже не показаны). На шину 11 подается сигнал. устанавливающий все узлы запрета 9 в такое положение, что элементы И 5 оказываются открытыми. После этОЕО устройство ГОТОВО к работеЯ Теперь на шину 12 подается первыйтактовый сигналкоторый переводиткоммутатор 15 в первое положение. Приэтом подготавливается к работе ( попервому входу поразрядного управления)первый (старший) разряд регистра результата 2. Кроме того, триггер 8устанавливается в 1 и подготавливает элемент И 13 к работе. Затемна шину 16 подается сигнал, которыйзаносит в первый (старший) разрядрегистра результата 2 единицу ( поцепи, подготовленной первым Выходомкоммутатора 15). После этого на шину 4 подается сигнал, который проходитчерез Открытые элементы И 5 на управляющие входы всех схем сравнения 3(в качестве их могут быть использованы любые известные схемы для сравнения двух П -разрядных чисел, имеющие выходы неравенства, ( и выходравенства), Схемы сравнения 3 осущестВляют сравнение чисел (Н, находящихся в принадлежащих им регистрах 1,с числом, находящимся в регистре результата 2 (1000). В результатеэтого сравнения сигнал на выходенеравенства больше или Равно в,какой-либо схеме сравнения 3 появитсяВ том случае, если число в соответствующем регистре 1 М Ь 1000 (сигналы, появляющиеся на выходах равенства схем 3 не оказывают Воздействияна узлы запрета 9, так как сигнал науправляющую шину 10 не подан),Таким образом, если хотя бы в одномиз регистров 1 найдется число М;100.,0, то сигнал появится на выхо"де соответствующей схемы сравнения 3,пройдет через переключатель б, элемент ИЛИ 7 и поступит иа вход установки В нулевое состояние триггера8, Триггер 8 установится в нуль иподаст на вход элемента И 13 запрещающий сигнал.После окончания сигнала на шине4 подается сигнал на шину 14, таккак элемент И 13 закрыт, то этот сигнал дальше в устройство не поступит,а в регистре результата 2 сохранится записанная в старшем разряде 1 1,Итак, к концу первого такта работыв первом разряде регистра результата2 будет записана 11 ф, если, хотябы в одном из регистров 1, найдетсячисло, большее или равное 1000.Если же во всех регистрах 1 окажутся числа меньшие, чем 1000,то на выходах неравенства большеили Равно схем сравнения 3 сигналов,не будет, следовательно, триггер 8останется в положении 1. Тогдасигнал с шины 14 пройдет через открытый элемент И 13 на входы установкив нулевое состояние регистра результата 2. Через подготовленную цепь(по первому входу поразрядного управления) первый Разряд регистра результата 2 вернется в положение фО.Таким образом, если во всех регистрах 1 окажутся числа меньшие,чем 1000, то к концу первого такта работы в первом (старшем) разряде регистра результата 2 будет записан 0.Затем на шину 12 подается второйтактовый сигнал, и работа устройства 5повторяется. К концу второго тактаработы во втором разряде регистра 2будет записана фф 1, если хотя бы водном из регистров 1 найдется число,большее или равное числу, сформирован ному в регистре результата 2 за дватакта работы. В противном случае вовтором разряде регистра результата 2будет записано ф 0.После окончания а тактов в регистре результата 2 будет сформированочисло, равное максимальному значениючисла, хранящемуся .в одном из регистров 1,В (0+1) такте коммутатор 15 сигналом по шине 12 переводится в (П+1)положение, чтобы не изменить содержимое регистра 2. Затеи на шину 10подается управляющий сигнал, подготавливающий к работе узлы запрета 9,Сигналы по другим шинам (4, 14,16)поступают также, как и в предыдущихтактах. Сигнал по шине 16 никакихизменений в регистре результата 2 невызовет, так как коммутатор 15 переведен в (я+1) положение. Сигнал, 30поступающий по шине 4, пройдет кауправляющие входы всех схем сравнения 3, но появится на выходе равенства только той схемы сравнения 3, гдев принадлежащем ей регистре 1 эаписано максимальное число, равное сформированному в регистре результата 2.Сигнал с выхода равенства соответствующей схемы сравнения 3 поступитна управляющий вход узла запрета 9, 40принадлежащего данной схеме сравнения 3. Узел запрета 9 переведется, взакрытое состояние и элемент И 5 Окажется закрытым по второму входу. Таким образом в дальнейшем сигнал с шины 4 уже ие будет проходить ка даннуюсхему сравнения 3, а значит регистр 451, где находится уже найденное максимальное число, в дальнейшей работеучастия принимать ке будет.После этого содержимое регистрарезультата 2 выбирается (максимальное число), а он сбрасывается в исходное (нулевое) состояние.Затем ка шику 12 подается очередной тактовый сигнал, и устройствоначинает поиск максимального чиспаиэ оставшихся чисел (без учета ужевыбранных), Работа устройства циклически повторяется до тех пор, покаке будет осуществлена сортировкавсех чисел, находящихся в регистрах1, в порядке их убывания.Для сортировки чисел в порядкеих Возрастания переключатель 6 пере водится в другое положение. Работа устройства происходит аналогично ранее описанному, только теперь каждый раз будет Осуществляться выбор минимального из оставшихся чисел. При этом в очередном разрядке регистра 2 будет сохраняться ф 1 ф, если в данном такте работы числа во всех кеисключенных иэ работ регистров 1 будут больше или равны числу, сформированному в регистре 2 зв прошецшие такты работы (включая и данный). Впротивном случае в данном разрядерегистра 2 будет сФормирован ОфеНа (П +1) такте очередное минимальное число будет выбрано из регистра 2, а соответствующий регистр 1 будет исключен из дальнейшей работы с помОщью Узла запрета 9прикадледаИго данному регистру 1.Устройство Обладает Высоккм быст"одействием, так как для сортировки Ф к -разрядных чисел требуетск й 1 (0+1) тактов работы, В то Время:(ак для изВестных УстрОЙстВ неОбходкмо 2 тактов.Формула кзобретеккяУстройстВО для сорткровкк П 1 П Разрядных чисел, содержащее П регистров, ыоды каждого кз которых соедкк:.Вы со Входамк схем сравнения, другие входы которых подключены к Выходам регистра результата, Выходные шккы схем сравнения соединены через переключатели со Входами элемента ИлИ 1, элементы И триггер Узлы запретд.у О т л и ч а ю щ е е с я тем, что, с целью повыаекия быстродействия, в кем выход равенства каждой схемы сравнения соединен с управляющим Входом соответствующего узла запрета, другие Входы которого подключе):ы к управляющим шикам устройстка, а ВыХОД - К ОДКОМУ Из ВХОДОВ ПЕРВОГО ЭЛЕ- мента И, другой Вход котОРОго соединен с ВходнОЙ микОЙ устройства, а выход - с управляющим Входом схемы сравнения, Выход элемента ИЛИ сое- ДИКЕК СО ВХОДОМ ТРКГГЕРа, ДРУГОЙ вход которого соедккек с шккой тактовых сигналов, а Выходы - через переключатель - со Входом Второго элемента И, другой ВХОД КОТОРОГО СОЕ- дикек с управляющей шиной устройства, а выход - со Входом устакоэкк В нулевое состоякке регистра результата, Входы поразрядкого управлеккя которого подключены к Выходам коммутатора, Вход которого соединен с шиной так" товых сигналов, а Входы устакоэкк В едкккчное состояние разрядов регистра результата подключекы к управляющей шине устройства.источники информации, принятые во внимание прк экспертизе:1. Авторское свидетельство СССР М 463968, кл. Й 06 Г 7/00, 1954.2.Авторское свидетельство СССР2 б 3277, кл, С 1 06 Р 7 /00, 1956637810 Составитель В.БелкинРедактор Н.Каменская Техред М,Борисова Корректор Д.Мельничен ноестров ССС т й д,4/5 лиал ППП Патент, г.ужгород, ул. Проектная,аказ 7107/39 ЦНИИПИ Государствен по делам 113035, Москираж 784ого ксмитиэобретена, Ж,По вета ткрыт ая на