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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Сфюз СоветскнкСоцналнстнческнкРеспублнк щ 981989(61) Дополнительное к авт. свнд-ву(22) Заявлеио 27.04,81 (21) 3278025/18-24 1 И 1 М. Кп. с присоединением заявки ЙоС 06 Р 7/06 Государствеииый комитет СССР ио делам изобретеиий и открытий(23) ПриормтетОпубликовано 15,12,82.Бюллетень йо 46 Дата опубликования описания 15 . 12. 82(72) Авторизобретения А.С.Ильин 1) Заявител 54) УСТРОИСТВО ОРТИРОВКИ ЧИСЕЛ зульедисло,Известтировкн чиячеек, каждтриггераинвертора О Изобретение относится к автоматике н вычислительной технике и может быть использовано в системах обработки информации при реализации5 технических средств цифровых .вычнслительйых машин и дискретной автоматики.Известно устройство для сортировки чисел, содержащее ячейки, каждая 1 О из которых: содержит и триггеров, группу из 2 (и) входных элементов И, группу из (и) выходных элементов И, дешифратор с и входами и щ выходами щ) элементов НЕ, группуВ1 из щ элементов И, щ элементов ИЛИ 11,Недостатком устройства является то, что выбор максимального числа в диапазоне 0-2 посредством дешифраитора требует применения (щ) элементов НЕ, щ элементов И, щ элементов ИЛИ, где щ=2", что увеличивает аппаратурные затраты (в предлагаемом техническом решении аппаратурные зат" раты пропорциональны и).2 также устройство для сорел, содержащее матрицуая из которых состоит извходными элементами И,элементов И и ИЛИ 21. Недостатком этого устройства является ограниченная область его применения за счет того, что оно предусматривает возможность сортировкитопько двоичных чисел,Наиболее близким к изобретениюявляется устройство для сорткровкичисел, которое содержит щ регистров,в которые записываются исходные числа, щ схем сравнения, регистр ретата, в котором формируется очерное максимальное (минимальное) чэлемент ИЛИ, элементы И, триггер,узлы запрета, коммутатор,переключатель, причем выходы 1-го регистрасоединены со входами 1-ой схемы сравнения, выходы схем сравнения соединены со входами переключателя, первыевходы каждого из первых элементов Иявляются управляющими входами устройства, первые илн вторые выходынеравенства схем сравнения, в зависимости от положенияпереключателя,связайы с соответствующими входамипервого, элемента ИЛИ, выход которогосоединен со входом установки в нулевое состояние триггера, выходы равенства схем сравнения подключены куправляккцему входу соответствующихузлов запрета, вторые и третьи вхо 981989ды которых связаны соответственно г управляющими шинами устройства,щисодн узлов запрета соединены со вторыми входами соответствующих первых элементов И, выход которого соединен с управляющим входом схема сравнения, вход установки в единичное состояние триг- гера подключен к шине тактовых сигна-; лов, а его прямой и инверсный выходы связаны через переключатель с первым входом второго элемента И, второй 10 вход которого подключен к управляющей шине устройства, выход второго эле мента и соедйнен со входом установки в нулевое состояние, регистра результата, входы поразрядного управления 15 регистра результата подключены к соответствующим выходам коммутатора, вход которого связан с шиной тактовых сигналов, входы установки разрядов регистра результата в единичное состояние соединены с управляющей шиной устройства 3 .Недостатком этого устройства является низкое быстродействие за счет того, что,максимальное (минимальное) число формируется в регистре результата путем последовательного внесения в его разряды, начиная со стар" шего, значения "0" или ф", вследствие чего сортировка щ и-разрядных чисел осуществляется за (и+1)щ тактов работы.Цель изобретения - повышение бЫст- родействия устройства путем сравие ния одновременно различных пар чисел,35 записанных в регистры.Поставленная цель достигается тем, что устройство для сортировки чисел, содержащее щ регистров, щсхем сравнения, многовходовай элемент ИЛИ,элементы И, переключатели, причем выходы 1-го и (1+1)-го регистров поразряуР- но соединены со входами 1-й схемы сравнения (1 1 щ, где щ - максимальное количество сортируемых чи сел), выходы которой соединены со входами соответствующего переключателя, выходы переключателей соединенЫ .с соответствующими входами многовходового элемента ИЛИ, входы управления обменом соединены с первыми входами соответствующих элементов И, содержит элементы неравнозначности, элементы ИЛИ, дополнительные элементы И, причем выходы 1-го и 1+1)-го регистров поразрядно соединены со входами элементов неравнозначности, собтветствуюших 1-й схеме сравнения, выходы схем неравноэначности соединены с первыми входами соответственных дополнительных элементов И, вто" 60 рые входы которых соединены с выходом соответствующего .элемента И, вторые входы элементов И соединены с выходами соответствующих переключателей, выходы дополнительных элемен тов И, соответствующих 1-й схеме сравнения соединены с первыми входами элементов ИЛИ, соответствующих 1-му регистру и со входами элементов ИЛИ, соответствующих (1+1)-му регистру; выходы элементов ИЛИ поразряд-. но соединены со входами соответствующих регистров, выход многовходового элемента ИЛИ соединен с выходом сигнализации о неупорядоченном расположении чисел в регистрах устройства.На чертеже представлена функциональная схема устройства.Устройство содержит щ регистров 1, щсхем сравнения 2, переключатели 3, многовходовой элемент ИЛИ 4, элементы И 5, входы управления обменом б, элементы неравнозначности 7, дополнительные элементы И 8, элементы ИЛИ 9Устройство работает следуквим образом.Схема сравнения 2, выбираемая в зависимости от кодировки чисел в регистрах, через соответствующий пере ключатель 3 сигнализирует о необходимости поменять местами числа в регистрах 1. Этот сигнал является разре- шающим для выполнения операции обме на чисел в регистрах 1 и с помощью элемента И 5 логически перемножается с управляющим сигналом, поступающим по входу б и передаваеизм на вход схемы обмена чисел в регистрах, которая состоит из элементов неравнозначности 7, элементов И 8 и элементов ИЛИ 9. Йапичие сигналов на выходе схем неравнозначности 7 свидетельствует о том, что соответствующие триггеры регйстров 1 находятся в противоположных состояниях: один в состоянии "О", другой - "1", или наоборот, Следовательно, в момент появления управляющего сигнала по входу б,каждый из триггеров изменит свое состояние иа противоположное, что эквивалентно обмену чисел в регистрах 1. Обмен происходит одновременно для всех разрядов сравниваемых чисел независимо от их кодировки. Переключатель 3 предназначен для подключения входов элементов И 5 и элемеита ИЛИ 4 к выходам "больше" или "меньше" схем сравнения 2 для выбора одного из режимов сортировки: по невозрастанию или по неубыванию. Сигнал с выхода элемента ИЛИ 4 свидетельствует о существовании хотя бы одной неупорядоченной пары чисел в регистрах 1, т.е. о необходимости продолжать процесс сортировки чисел.Представленная на чертеже Функциональная схема предлагаемого устройства имеет вид однородной периодической структуры. Хотя минимально необходимое количество схем сравнения и обмена на единицу меньше количества регистров 1, наличие допол8 а(1 ор а)22 Формула изобретения Устройство для сортировки чисел,содержащее а регистров, асхем сравкения, многовходовой элемент ИЛИ,элементы И, переключатели, причем вы.ходы 1-го и (1+1)-го регистров поразрядно соединены с входами 1-й схемысравнения (1=1а-, где а - максимальное количество сорткруемях чисел), выходы которой соединены свходами соответствующего переключателя, выходы переключателей соединены с соответствукарии входами многовходового элемента ИЛИ, входы управления обменом соединены с первымивходами соответствующих элементов И,о т л и ч аю щ е е с я тем, что,сцелью повыаенкя быстродействия,устройство содержит элементы неравнозначности, элементы ИЛИ,дополнительные элементы И, причем выходы 1-го и(1+1)-го регистров поразрядно соединены с входами элементов неравнозначности, соответствующих 1-й схемесравнения, выходы схем неравнозначностк,соединены с первымк входамисоответствующихдополнительных элементов И, вторые. входы которых соединены свыходом соответствующегоэлемента И, вторые входы элементовИ соединены с выходами соответствующих переключателей, выходы дополнительных элементов Й, соответствукщкх1-й схеме сравнения, соединены с пер.выми входами элементов ИЛИ, соответствующих 1-му регистру, и с вторымивходами элементов ИЛИ, соответствующих (3.+1)-иу регистру, выходы элементов ИЛИ поразрядно соединены свходами соответствующих регистров,выход многовходового элемента ИЛИоединен с выходом сигнализациинеупорядоченном расположении чиел в регкстрах устройства.Источники информации,ринятые во.внкмание при экспертизе1. Авторское свидетельство СССР590728 ф кл, С 06 Р 7/00, 1978.2, Авторское свидетельство СССР424141 р кл, С. 06 Р 7/00, 1974.3.Авторское свйдетельство СССР637810 кл. С .06 Р 7/08, 1978прототип). сДля предлагаемого устройства грао ницы диапазонов изменения величинй - количество тактов работы устройс ства и Я - количество схем сравнения и обмена не зависят от разрядности п чисел и и при заданном а определяются следующим образом. ВМинимальными аппаратурными затратафи обладает известный метод четно- Р нечетной сортировки с транспозициями.В этом случае в данном устройстве Р количество схем сравнения Я = а, ( нительной схемы сравнения 2 и соответствукщей ей схемы обмена обеспечи.вает воэможность расширения устройства посредством последовательного включения себе подобных. Поскольку входы дополнительной схемы сравнения 2 и входы элементов неравнозначности 7 соответствующей схемы обмена соединены с выходами только одного регистра 1, управляющий вход б, соответствующего им элемента И 5 должен - 10 быть обнулен.Элементы неравнозначности 7, кроме своих основных функций в составе схем обмена, могут играть вспомогательную роль для схем сравнения 2. 15 Поэтому выходы элемента неравнозначности 7 могут быть соединены с другими входаии схем сравнения 2, как это показано на чертеже. Соединения этих схем с пряьами и инверсными 20 выходами регистров 1, а также использование счетных входов триггеров регистров 1 возможно и целесообразно в интегральном исполнении предлагаемого устройства. Необходимое количество схем сравнения 2 и схем обмена, их расположение между регистрами 1 и распределение управляющих сигналов по входам б выбираются в зависимости от требований экономии времени или затрат на аппаратуру и в соответствии с известными алгоритмическими методами сортировки.Технический эффект от использования предлагаемого .технического решения заключается в повышении быстродействия работы устройства путем одновременного сравнения и обмена чисел различных пар регистров.При этом появляется возможность широко го выбора желаемого требуемого) 46 соотношения между аппаратурными затратами и временем работы. устройства при заданном количестве регистров 1 путем изменения количества схем сравнения и обмена, их располо 45 женкя между регистрами 1 и распределения сигналов по управляющим вхо даи б.Количество тактоз работы извест- . ного устройства 50(и+1)а,количество тактов работы устройства й = а, а управляюцне сигналы. должны подаваться поочередно на все четные управляющие входы, затем на все нечетные и т.д.Минимальными затратами времени обладают методы Бэтчера. В этом случае в: устройстве981989 Составитель А. СуздалевТехред Т,Маточка Корректор Н. Корол Редактор М. Товт к филиал ППП "Патент", г. Ужгород, ул ектная, 4 712/68 Тираж 731 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д.4/5