Устройство для сортировки чисел Советский патент 1982 года по МПК G06F7/08 

(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах обработки информации при реализации технических средств цифровых вычислительных машин и дискретной автоматики. Известно устройство для сортировки чисел, содержащее ячейки, каждая из которых: содержит п триггеров, группу из 2 (п-1) входных элементов И, группу из (п-1) выходных элементов И деши( с п входами и m выходами, (т-2) элементов НЕ, из m элементов И, m элементов ИЛИ I Недостатком устройства является то, что выбор максимального числа в диапазоне 0-2 посредством дешифратора требует применения (т-2) элементов НЕ, m элементов И, m элементов ИЛИ, где , что увеличивает аппаратурные затраты (в предлагаемом техническом решении аппаратурные зат раты пропорциональны п). Известно также устройство для сор тировки чисел, содержащее матрицу ячеек, каждая из которых состоит иэ триггера со входными элементами И, инвертора, элементов И и ИЛИ ,2. Недостатком этого устройства является ограниченная область его применения за счет того, что оно предусматривает возможность сортировки только двоичных чисел. Наиболее близким к изобретению является устройство для сортировки чисел, содержит m регистров, в которые записываются исходные числа, га схем сравнения, регистр результата, в котором формируется очередное максимальное (минимальное) число, элемент ИЛИ, элементы И, триггер, узлы запрета, коммутатор,переключатель, причем выходы i-ro регистра соединены со входё1ми i-ой схема сравнения, выходы схем сравнения соединены со входами переключателя,первые входы кгиадого из первых элементов И являются управляющими входами устройства, или вторые выходы неравенства схем сравнения, в зависжмости от положения переключателя, связа11ы с соответствующими входами первого .элемента ИЛИ, выход которого соединен со входом установки в нулевое состояние триггера, выходы равенства схем сравнения подключены к управляющему входу соответствующих узлов запрета, вторые и третьи вхолы которых связаны соответственно S управляющими шинами устройства, кисоды узлов запрета соединены со вторыми входами соответствующих первых элементов И, выход которого соединен с управляда1цим входом схемы сравнения, вход установки в единичное состояние триг гера подключен к итне тактовых сигна лов, а его прямой и инверсный выходы связаны через переключатель с первым входом второго элемента И, второй вход которого подключен к управляюще шине устройства, выход второго элемента И соединен со входом установки в нулевое состояние,регистра реэультата, входы поразрядного управления регистра результата подключены к соответствукидим выходам коммутатора, вход которого связан с шиной тдктовых сигналов, входы установки разря ДОН регистра результата в единичное состояние соединены с управляющей шиной устройства З . Недостатком этого устройства является низкое быстродействие за счет того, что максимальное (минимальное) число формируется в регистре результата путем последовательного внесения в его разряды, начиная со старшего, значения О или J, вследствие чего сортировка m п-разрядных чисел осуществляется за (n-«-1)m такто работы. Цель изобретения - повьниение быст родействия устройства путем сравне-п ния одновременно различных пар чисел записанных в регистры. Поставленная цель достигается тем что устройство для сортировки чисел, содержащее m регистров, т-1 схем сра нения, многовходовой элемент НЛИ,эле менты И, переключатели, причем выходы i-ro и )-ro регистров поразряд но соединены со входами i-й схемы сравнения (,..,, т-1, где m - максимальное количество сортируемых чисел), выходы которой соединены со входами соответствующего переключателя, выходы переключателей соединеЯй .с соответствукицимн входами многовходового элемента ИЛИ, входы управления обменом соединены с первыми входами соответствующих элементов И, содержит элементы неравнозначности, элементы ИЛИ, дополнительные элементы И, причем выходы i-ro и (i-«-1)-ro регистров поразрядно соединены со входами элементов неравнозначности, собтве.тствуюших i-й схеме сравнения, выходы схем неравнозначности соединены с первыми входами соответственных дополнительных элементов И, вторые входы которых соединены с выходом соответствующего элемента И, вторые входы элементов И соединены с выходами соответствуклцих переключателей, выходы дополнительных элементов и, соответствующих i-й схеме сравнения соединены с первыми входами элементов ИЛИ, соответствующих i-му регистру и со входами элементов ИЛИ, соответствующих (1+1)-мУ регистру/ выходы элементов ИЛИ поразряд-. но соединены со вхЬдами соответствующих регистров, выход многовходового элемента ИЛИ соединен с выходом сигнализации о неупорядоченном расположении чисел в регистрах устройства. На чертеже представлена функциональная схема Устройства. Устройство содержит m регистров 1, т-1 схем сравнения 2, переключатели 3, многовходовой элемент ИЛИ 4, элементы И 5, входы управления обменом 6, элементы неравнозначности 7, дополнительные элементы И 8, элементы ИЛИ 9. Устройство работает следукщям образом. Схема сравнения 2, выбираемая в зависимости от кодировки чисел в регистрах, через соответствующий переключатель 3 сигнализирует о необходимости поменять местами числа в регистрах 1. Этот сигнал является разрешающим для выполнения операции обме на чисел в регистрах 1 и с помощью . элемента И 5 логически перемножается с управляющим сигналом, поступающим по входу 6 и передаваемым на вход схемы обмена чисел в регистрах, которая состоит из элементов неравнозначности If элементов И 8 и элементов ИЛИ 9. Наличие сигналов на выходе схем неравноэначнорти 7 свидетельствует о том, что соответствующие триггеры регистров 1 находятся в противоположных состояниях: один в состоянии О, другой - 1, или наоборот. Следовательно в момент появления управляющего сигнала по входу б, каждый из триггеров изменит свое состояние на противоположное, что эквивалентно обмену чисел в регистрах 1. Обмен происходит одновременно для всех разрядов сравниваекых чисел независимо от их кодировки. Переключатель 3 предназначен для подключения входов элементов И 5 и элемента ИЛИ 4 к выходам больше или меньше схем сравнения 2 для выбора одного из режимов сортировки: по невозрастанию или по неубыванию. Сигнал с выхода элемента ИЛИ 4 свидетельствует о существовании хотя бы одной неупорядоченной пары чисел в регистрах 1, т.е. о необходимости продолжать процесс сортировки чисел. Представленная на чертеже функциональная схема предлагаемого устройства имеет вид однородной периодической структ5Г1 а. Хотя минимально необходимое количество схем сравнения и обмена на единицу меньше количества регистров 1, наличие дополнительйой cxeru сравнения 2 и соотгвеств5гнвдей ей схемы обмена обеспечи. Bctei возможность расширения устройства посредством последовательного включения себе подобных. Поскольку входы дополнительной схемы сравнения 2 и входы элементов неравнозначности 7 соответствующей схёкы обмена соединены с выходами только одного регистра 1, управляющий вход б, соотвётствующе о им элемента И 5 должен быть обнулен.

Элементы неравнозначности 7, кроме своих основных функций в cocTaise схем обмена, могут играть вспомогательную роль для схем сравнения 2. Поэтому выхбды элемента неравнозначности 7 могут быть соединены с другими входами схем сравнения 2, как это показано на чертеже. Соединения этих схем с пря14ями и инверсными выходами регистров 1, а также использование счетных входов триггеров регистров 1 возможно и целесообразно в интегральном исполнении предлагаемого устройства. Необходимое количество схем сравнения 2 и схем обмена, их расположение между регистрами 1 и распределение управляю111ИХ сигналов по входам 6 выбиргиотся в зависимости от требований экономии времени или затрат на аппаратуру и в соответствии с известными алгоритмическими методами сортировки .

Технический эффект от использования предлагаемого технического решения заключается в повышении быстродействия работы устройства путем одновременного сравнения и обмена чисел различных пар регистров.При этом появляется возможность широкого выбора желаемого (требуемого) соотношения меткду ёшпаратурными затратами и временем работы устройства при заданном количестве регистрЬ 1 путем изменения количества схем сравнения и обмена, их расположения между регистрами 1 и распределения сигналов пО управляющим входам б.

Количество тактов работы известного устройства t (n-«-1)m.

Для предлагаемого устройства границы диапазонов изменения величин t - количество тактов работы устройства и S - количество схем сравнения и обмена не зависят от разрядности чисел п и при заданном m определяются следующим образом.

Минимальными аппаратурными затратаотс обладает известный метод четнонечетной сортировки с транспозициями

В этом случае в данном устройстве количество схем сравнения S т-1,

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

Минимальными затратами времени обладают методы Бэтчера. В этом случае в устройстве

S m(logjm)

Формула изобретения

Устройство для сортировки чисел, содержащее m регистров, т-1 схем сра нения, многовходовой элемент ИЛИ,элементы И, переключатели, причем вы.ходы i-ro и (i-t-l)-горегистров поразрядно соединены с входами 1-й схемы сравнения (,.,.,т-1, где m - максимальное количество сортируемых чисел) , выходы которой соединены с входами соответствующего переключателя, выходы переключателей соединены с соответствующими входами многовходового элемента ИЛИ, входы управления обменом соединены с первыми входами соответствующих элементов И отличающе ее я тем, что,с целью повышения быстродействия,устройство содержит элементы неравно3 н ачности, элементы ИЛИ, дополнительные элементы И, причем выходы i-ro и (1+1)-го регистров поразрядно соединены с входами элементов неравнозначности, соответствующих i-й схеме сравнения, шкоды схем неравнозначности соединены с первыми входами соответствукяцих дополнительных элементов И, вторые.входы которых соединены свыходом соответствующего элемента И, вт( входы эле 4ентов И соединены с выходами соответствующих переключателей, выходы дополнительных элементов И, соответствуиощх i-й схеме сравнения, соединены с первыми входами элементов ИЛИ, соответствующих i-му регистру, и с вторыми входами элементов ИЛИ, соответствующих (1+1)-му регистру, выходы элементов ИЛИ поразрядно соединены с входами соответствующих регистров, выход многовходового элемента ИЛИ соединен с выходом сигнализации . о неупорядоченном расположении чи-. сел в регистрах устройства. I

Источники информации, принятые во- внимание приэкспертизе

1.Авторское свидетельство СССР № 590728, кл/G Об F 7/00, 1978.

2.Авторское свидетельство, СССР № 424141, кл. G 06,F 7/00., 1974.

3.- Авторское свидетельство СССР В 637810, кл. G Об F 7/08, 1978 (прототип).