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

1868749 ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИ ВТЕЛЬСТВУ Сефз Советских Социалистических Реслублик(22) Заявлено 19,10. 79 (212845859/18-24 О 06 Г 7/06 исоедииейием заявки Ж осударствеииый комитет СССР ио дедам изобретеиий и открытий(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ ожетаменз адер 1Изобретение относится к автоматике и вычислительной технике и м.низации и упорядочения чисел.Известно устройство для сортиров.ки двоичных чисел, содержащее матрицу из ячеек (включающих элементы И,запрета и ИЛИ), элементы НЕ, элеты И и ИЛИ, триггеры и элементйжки 11,Недостатком этого .устройства является его сложность. Наиболее близким к предлагаемомуявляется устройство для определенияположения числа на числовой оси, содержащее регистры, схемы сравнения,счетчики, генератор, блок синхронизации и элемент ИЛИ, Вь 1 Ход первогорегистра соединен со входом первойсхемы сравнения, на второй вход которого подсоединен выход счетчика,на вход которого подсоединен выходгенератора, выход блока аинхронизации соединен со входом управлениявторого счетчика 2 ,Цель изобретения - расширение функциональных возможностей за счет формирования последовательности упорядоченных данных. Поставленная цель достигается тем,что в устройстве, содержащем регистры, счетчик, схему сравнения, элементы И, ,группы элементов И,блок управления, причем входная шина устройства соединена с первыми входами первого. и второго элементов И, выходы которых подключены к информационным входам первого и второго регистров соответственно, выходы первого регистра соединены со входами первой группы схемы сравнения, выходы второго регистра подключены ко входам второй группы схемы сравнения, первый и второй вы ходы которой соединены с первым ивторым входами блока управления соответственно, выходы первого и второго регистров соединены с информационными входами элементов И первой и вто рой групп соответственно, первый выход блока управления подключен к управляющим входам элементов И первой группы, выходы которых соединены со входами первой группы третьего ре гистра, второй выход блока управленияподключен к управляющим входам элементов И второй группы, выходы которых соединены со входами первого регистра и со входами второй группы ЗО третьего регистра, третий четвертыйи пятый выходы блока управления подключены ко входам управления первого, второго и третьего регистров соответственно, шестой и седьмой выходы блока управления соединены со вторыми входами первого и второго элементов И соответственно, восьмой выход блока управления подключен ко входу сброса счетчика, информационщ 3 й вход которого соединен с девятым выходом блока управления, вход запускаустройства подключен к третьему входу блока управления.Кроме того, блок управления содержит элементы Й, ИЛИ, триггеры, счетчик, дешифратор, генератор тактовых сигналов, выход которого соединен с первыми входами первого и второго элементов И блока управления, первый и второй входы блока управления соединены со входами установки в единичное состояние первого и второго триггеров, прямые выходы которых подключены к первому и второму управляю"щим входам дешифратора, первый выход которого подключен ко входам установки в нулевое состояние первого и второго триггеров, выходы которых соединены с первым и вторым выходами блока управления, выход первого элемента И блока управления подключен к первому входу элемента ИЛИ и к информационному входу счетчика блока управления, выходы которого соединены с информационными входами дешифратора, второй выход которого подключен ко второму входу второго элемента И блока управления, выход которого соединен со вторым входом эл,мента ИЛИ, выход которого подклю" чс.н к первым входам третьего, четвертого, пятого, шестого и седьмогоэлементов И блока управления, третийвыход дешифратора соединен со входами установки в нулевое состояние третьего триггера, вход установки в единичное состояние которого подключен к третьему входу блока управления, а прямой выход - ко второму входу первого элемента И блока управления, четвертый и пятый выходы дешифратора соединены со входом установки в единичное состояние четвертого и пятого триггеров шестой выходдешифратора подключен ко входам установки в ну евое состояние четвертогои пятого триггерЬв, седьмой, восьмой, девятый, десятый и одиннадцатый выходы дешифратора соединены со вторыми входами третьего, четвертого, пятого, шестого и седьмого элементов И блока управления соответственно, выходы третьего, четвертого и пятого элементов И блока управления, прямые выходы четвертого и пятого триггеров, выходы седьмого и шестого элементов И блока управления подключены к третьему, четвертому, пятому, шестому, седьмому, восьмому и девятому выходам блока управления соот-.,ветственно.На фиг.1 приведена блок-схемапредлагаемого устройства " на фиг 2ффункциональная схема блока управления.устройство содержит регистры 12 и 3, элементы И 4 и 5, группы элеРментов И 6 и 7, счетчик 8, схему 9сравнения; блок 10 управления, входную шину 11, вход 12 запуска, выходные шины 13 и 14.Блок управления (Фиг.2) содержитгенератор 15 тактовых импульсов,счетчик 16, дешифратор 17, триггеры118-22, элементы И 23-29 элемент ИЛИ30, входы 31,32 и 33 и выходы 34-43.Устройство работает следующим образом.Первоначально все регистры устанавливаются в нулевое состояние. На20 выходах блока 10 управления отсутствуют сигналы разрешения для элемен-тов И 4 и 5 и группы элементов И 6 и7. При подаче сигнала на вход 12 запуска открывается. элемент И 4, свходной шины 11 от внешнего источника ( например из блока памяти) поступает первое число из заданного массива чисел на регистр 1. После записи первого числа в регистр 1 (содержание регистра равно А) элемент И 4закрывается (при помощи передачи запрещающего сигнала по первому выходублока 10 управления), а второй элемент И 5 открывается. С входной шины11 через открытый элемент И 5 на регистр 2 подается другое число изсравниваемого массива чисел. Послезаписи числа в регистр 2 (содержаниерегистра 2 равно А) элемент И 5 закрывается.40 Предположим, что число А =10001(записанное в регистр 1) больше числа А = 00111 (записанного в регистр2). Эти числа сравниваются между собой по величине на схеме 9 сравнения. На первом выходе схемы 9 сравнения в этом случае появляется сигнал (АА 2), который передается напервый вход блока 10 управления.Этот сигнал разрешает подачу с трео тьего выхода блока 10 управления науправляющий вход первой группы элементов И 6 разрешающего сигнала. Содержание регистра 1 (А) при помощйсигнала с пятого выхода блока 10 управления через открытый блок элемен 55 тов И 6 перезаписывается в регистр 3(число А)стирается сигналом с шестого выхода блока 10 управления. За 60 тем блок элементов И 6 закрывается.В этой операции в регистрах 1 и 3записано наибольшее из двух сравниваемых чисел,Во второй операции элемент И 565 снова открывается на время записи свходной шины 11 на регистр 2 следующего сравниваемого числа. В случае,если это число меньше значения, находящегося в регистрах 1 и 3, тоуказанный процесс повторяется и число А 4 остается записанным в регистрах1 и 3, а число А стирается йз регистра 2, В случае, если это число(А = 10011) больше числа А, =10001,то при их сравнении на схеме 9 .срав-йения на его втором выходе появляется сигнал (АА ), который поступаетна второй вход блока 10 управленияи разрешает подачу сигнала разрешения с четвертого выхода блока 10управления для отпирания второй группы элементов И 7 (при этом группаэлементов И б остается закрытой),сигнал списывания информации с регистров 1, 2 и 3 (по пятому, шестому иседьмому выходам блока 10 управления).При этом содержание А регистра 2 20через открытую группу элементов И 7перезаписывается в освобождающиесяразряды регистров 1 и 3. Затем блокэлементов И 7 закрывается. В этомслучае последнее сравниваемое число, 25большее по величине, записано в регистрах 1 и 3. В случае, если А =А,со схемы 9 сравнения выдается сигнал с первого выхода и первое числоА остается записанным в регистрах1 и 3, а второе число участвует вследующей операции сравнения,В следующей операции элемент И 5открывается на время передачи с входной шины 1 на регистр 2 дрУгогосравниваемого числа и т,д. Послесравнения всех й чисел из требуемогомассива данных в регистре 3 остается записанное самое большое по своей величине число из всего массивачисел. Во время выполнения последней 40й операции сравнения с восьмого выхода блока 10 управления на вход счетчика 8 поступает тактовый импульс.Содержание счетчика 8 (в прямом и обратном коде) является в данном случае 45первым адресом отобранного наибольшего числа в первом цикле.Затем содержание регистра 3 (наибольшее из сравниваемых чисел) и содержание счетчика 8 (первый адрес) 50передастся во внешнее устройство(например память или специализированное вычислительное устройство). Причем содержание регистра 3 передается также на внешний источник (блокпамяти), в котором это значение (число) стирается, чтобы не участвоватьв поиске на следующих циклах. Послеэтого регистры 1 и 3 списываются(очищаются), регистр 2 списываетсяв предыдущей операции сравнения, а, 40в счетчике 8 остается предыдущеесодержание.Начинается второй цикл впоискнаибольшего числа из йоставшихсячисел, Открывается элемент И 4 на Я время записи первого из сравниваемых чисел в регистр 1 и процесс повторяется аналогично указанному выше. После второго цикла на счетчик 8выдается тактовый импульс и содержание счетчика равно второму адресу.Затем начинается третий цикл - поискнаибольшего числа из йоставшихсячисел и т.д.В первом цикле выполняется й операций сравнения, а во втором -Мопераций сравнения. В 1-ом циклевыполняется М- операций сравнения.В двух последних циклах (й)-ом иМ-ом) выполняется только по однойоперации сравнения (сравнение Мий чисел и соответственно одного изэтих чисел с нулем),. В операцию сравнения входят собственно операция сравнения двух чисел в схеме 9 сравнения, запись чсел в регистры 1 и 2 иперезапись чисел из регистров 1 или2 в регистр 3. Общее количество операций сравнения в М циклах поиска .равной(й)К = 1 + , й в= 1 +2Например, при й = 100 необходимо выполнить К = 4951 операций сравнения.Считая, что все пересылки чисел впредлагаемом устройстве выполняютсяпараллельно и принимая длительностьтакта в 1 мкс, получают время поиска25 мс.Работа блока 10 управления осуществляется следующим образом.Первоначально при запуске генератора 15 тактовых импульсов и при нулевом содержании счетчика 8 элементИ 24 открывается и через элемент ИЛИ30 на выходах 38-40 и 42 появляетсятактовый импульс для установки в нулевое состояние регистров 1,2 и 3 исчетчика 8. После подачи стартовогосигнала по входу 33 элемент И 24 закрывается,При поступлении по шине 11 (вход33) стартового импульса триггер 18открывает элемент И 23 и тактовые импульсы из генератора 15 тактовых импульсов поступают в счетчик 16, Стриггеров 19 и 20 выдаются сигналы,разрешающие запись в регистры 1 и 2сравниваемых чисел. Затем по результатам сравнения чисел (по сигналам свходов 31 или 32) выдаются сигналыпо выходам 36 или 37, разрешающие перезапись чисел через блоки элементовИ б или 7. При этом в случае сигналана входе 32 с шестого выхода блока10(выход 39) выдается сигнал установки нулевого состояния регистра 2.После выполнения всех действий операции сравнения выдается сигнал с.выхода 41 в счетчик 8, а сигнал с выхода 43 дешифратора 17 перебрасываеттриггер 18 (при этом элемент И 23 закрывается и тактовые импульсы перестают поступать в счетчик 16) и сбра 868749сывает содержание счетчика 1 б. При этом элемент И 24 открывается и на выходах 32-40 появляется тактовый импульс, который устанавливает нулевые состояния в регистрах 1, 2 и 3. Затем процесс, работы повторяется.Данная структурная схема блока 10 управления составлена,для варианта, когда каждая операция сравнения определяется стартовым импульсом, подаваемым извне. Это целесообразно, когда количество сравниваемых чисел неизвестно. В противном случае такая структурная схема должна быть дополнена еще одним распределителем, состоящим из триггера, элементов И( счетчика и дешифратора, один из вы" ходов которого подсоединяется ко входу 33 (установочный вход триггера 18). Установочный вход триггера соединяется с третьим входом блока 10 управления (входная шина 11). 20Аппаратная реализация алгоритма поиска и упорядочения позволяет повысить быстродействие как за счет исключения ряда служебных операций (выборки команд, формирования Нроме жуточных адресов, проверки условий выхода из цикла и др.), так н за счет совмещения во времени большого числа разных элементарных операций.Формула изобретения1. Устройство для сортировки чисел, содержащее регистры, счетчик, схему сравнения, элементы И, группы элементов И, блок управления, причем входная шина устройства соединена с первыми входами первого и второго элементов И, выходы которых подключены к информационным входам перво го и второго регистров соответственно, выходы первого регистра соединены со входами первой группы схемы сравнения, выходы второго регистра подключены ко входам второй группы 45 схемы сравнения, первый и второй выходы которой соединены с первым и вторым входами блока управления соответственно, о т л и ч а ю щ е е - с я тем, что, с целью расширения 5 О Функциональных возможностей за счет Формирования последовательности упорядоченны данных, в нем выходы первого и второго регистров соединены с информационными входами элементов И первой и второй групп соответствен" но, первый выход блока управления подключен к управляющим входам элементов И первой группы, выходы которых соединены со входами первой группы третьего. регистра, второй выход ЬО блока управления подключен к управ" ляющим входам элементов И второй группы, выходы которых соединены со входами первого регистра и со входами второй группы третьего регистра, 65 третий, четвертый и пятый выходыблока управления подключены ко входамуправления первого, второго и третьего регистров соответственно, шестойи седьмой выходы блока управлениясоединены со вторыми входами первого и второго элементов И соответственно, восьмой выход блока управления подключен ко входу сброса счет-,чика, инфдрмационный входкоторогосоединен с девятым выходом блока управления, вход запуска устройстваподключен к третьему входу блока управления,2. Устройство по п.1, о т л и -ч а ю щ е е с я тем, что блок управления содержит элементы И, ИЛИ, триггеры, счетчик, дешифратор, генератортактовых сигналов, выход которого соединен с первыми входами первого ивторого элементов И блока управления,первый и второй входы блока управле"ния соединены со входами установкив единичное состояние первого и второго триггеров., прямые выходы которыхподключены к первому и второму управляющим входам дешифратора, первыйвыход которого подключен ко входамустановки в нулевое состояние первого н второго триггеров, выходы которых соединены с первьм и вторым выходами блока управления, выход первогоэлемента И блока управления подключенк первому входу элемента ИЛИ и к информационному входу счетчика блокауправления, выходы которого соединены с информационными входами дешифратора, второй выход которого подключен ко второму входу. второго элемента И блока управления, выход которогосоединен со вторым входом элементаИЛИ, выход которого подключен к первым входам третьего, четвертого, пятого, шестого и седьмого элементовИ блока управления, третий выход дешифратора соединен со входами установки в нулевое. состояние третьеготриггера, вход установки в единичное состояние которого подключен ктретьему входу блока управления, апрямой выход - ко второму входу пер"вого элемента И блока управления,четверть 1 й и пятый выходы дешифраторасоединены со входом установки в единичное состояние четвертого и пятого триггеров, шестой выход,дешифратора подключен ко входам установкив.нулевое состояние четвертого и пятого триггеров, седьмой, восьмой,девятый, десятый и одиннадцатый выходы дешифратора соединены со вторыми входами третьего, четвертого, пятого, шестого и седьмого элементов Иблока управления соответственно, выходы третьего, четвертого и пятогоэлементов, И блока управления, прямыевыходы четвертого и пятого триггеров,выходы седьмого и шестого элементовИ блока управления подключены к тре868749 ПИ Заказ 8329/7 ж 748 Подписное тьему, четвертому, пятому, шестому, седьмому, восьмому и девятому выходам блока управления соответственно,Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР У 526888, кл,б 06 Г 7/00, 1974.2, Авторское свидетельство СССР Р 561960, кл.С 06 Е 7/Об, 1975 (прототип). филиал ППП "Патент", 1. Уагород, ул.Проек