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

Изобретение относится к автоматике и вычислительной технике и може ;6ыть использовано для поиска, орга;низации и упорядочения чисел. известно устройство для сортировки двоичных чисел, содержащее матрицу из ячеек (включакадих элементы И, запрета и ИЛИ), элементы НЕ, элементы И и ИЛИ, тригг1еры и элементы заде жки 1. Недостатком этого .устройства является его сложность. Наиболее близким к предлагаемому является устройство для определения положения числа на числовой оси, содержащее регистры, схемы сравнения, счетчики, генератор, блок синхронизации и элемент ИЛИ. первого регистра соединен со входом первой схемы сравнения, на второй вход которого подсоединен выход счетчика, на вход которого подсоединен выход генератора, выход блока синхронизации соединен со входом управления второго счетчика 2. Цель изобретения - расширение фун кциональных возможностей за счет фор мирования последовательности упорядоченных данных. Поставленная цель достигается тем, что в устройстве,содержащем регистры, счетчик,схему сравнения,элементы И, группы элементов И,блок управления, причем входная шина устройства соединена с первыми входами первого и второго элементов И, выходы которых подключены к информационным входам первого и второго регистров соответственно, выход1 первого регистра соединены со входс1ми первой группы схемы сравнения, выходы второго регистра подключены ко входам второй группы схемы сравнения, первый и второй выходы которой соединены с первым и вторым входами блока управления соответственно, выходы первого и второго регистров соединены с инфО 1ационными входами элементов И первой и второй групп соответственно, первый выход блока управления подключен к управляющим входам элементов И первой группы, выходы которых соединены со входами первой группы третьего регистра, второй выход блока управления подключен к управляющим входам элементов И второй группы, выходы которых соединены со входгили первого регистра и со входами второй группы третьего регистра, третий.четвертый .

и пятый выходы блока управления подключены ко входам управления первого, второго и третьего регистров с6ответственно, шестой и седьмой выходы блока управления соединены со вторыми входами первого и второго элементов И соответственно, восьмой выход блока управления подключен ко Jвxoдy сброса счетчика, информационщ|1 вход которого соединен с девятым выходом блока управления, вход запуска устройства подключен к третьему вход блока управления.

Кроме того, блок управления содержит элементы И, ИЛИ, триггеры, счетчик, дешифратор, генератор тактовых сигналов, выход которого соединен с первыми входами первого и второго элементов И блока управления, первый и второй входы блока управления соединены со входами установки в единичное состояние первого и второго триггеров, прямые выходы которых подключены к первому и второму управляющим входам дешифратора, первый выход которого подключен ко входам установки в нулевое состояние первого и второго триггеров, выходы которых соединены с первым и вторым выходами блока управления, выход первого элемента И блока управления подключен к первому входу элемента ИЛИ и к информационному входу счетчика блока управления, выходы которого соединены с информационными входами дешифратора, второй выход которого подключен ко второму входу второго элемента И блока управления, выход которого соединен со вторьил входом эл мента ИЛИ, выход которого подключен к первым входам третьего, четвертого, пятого, шестого и седьмого элементов И блока управления, третий выход дешифратора соединен со входами установки в нулевое состояние третьего триггера, вход установки в единичное состояние которого подключен к третьему входу блока управления, а прямой выход - ко второму входу первого элемента И блока управления, четвертый и пятый выходы дешифратора соединены со входом установки в единичное состояние четвертого и пятого триггеров шестой выход дешифратора подключен ко входам установки в ну тевое состояние четвертого и пятого триггеров, седьмой, восьмой .девятый, десятый и одиннадцатый выходы дешифратора соединены со вторыми .входами третьего, четвертого, пятого, шестого и седьмого элементов И блока управления соответственно, выходы третьего, четвертого и пятого элементов И блока управления, прямые выходы четвертого и пятого триггеров, выходы седьмого и шестого элементов И блока управления подключены к третьему, четвертому, пятому, шестому, седьмому, восьмому и девятому выходам блока управления соот.ветственно.

На фиг.1 приведена блок-схема .ч предлагаемого устройства/ на фиг.2 функциональная схема блока управле- ния.

Устройство содержит регистры 1, 2 и 3, элементы И 4 и 5, группы элементов И б и 7, счетчик 8, схему 9 сравнения,- блок 10 управления, вход- ную шину 11, вход 12 запуска, выходные шины 13 и 14. ,

Блок управления (фиг.2) содержит генератор 15 тактовых импульсов, счетчик 16, дешифратор 17, триггеры 18-22, элементы И 23-29, элемент ИЛИ 30, входы 31,32 и 33 и выходы 34-43. Устройство работает следунмцим образом.

Первоначально все регистры устанавливаются в нулевое состояние. На

0 выходах блока 10 управления отсутствуют сигналы разрешения для элементов И 4 и 5 и группы элементов И б и 7. При подаче сигнала на вход 12 запуска открывается элемент И 4, с

5 входной шины 11 от внешнего источника ( например из блока памяти) поступает первое число из заданного массива чисел на регистр 1. После записи первого числа в регистр 1 (содерQ жание регистра равно А) элемент И 4 закрывается (при помощи передачи эапрещакицего сигнала по первому выходу блока 10 управления), а второй элемент И 5 открывается, с входной шины

11 через открытый элемент И 5 на ре гистр 2 подается другое число из сравниваемого массива чисел. После записи числа в регистр 2 (содержание регистра 2 равно Ag) элемент И 5 закрывается.

0 Предположим, что число А. 10001 (записанное в регистр 1) больше числа АЗ. 00111 (записанного в регистр 2). Эти числа сравниваются между собой по величине на схеме 9 сравнения. На первом выходе схемы 9 сравнения в этом случае появляется сигнал (А,А2), который передается на первый вход блока 10 управления. Этот сигнал разрешает подачу с треQ тьего выхода блока 10 управления на управлянэдий вход первой группы элементов И 6 разрешающего сигнала. Содержание регистра 1 (А) при помсяци сигнала с пятого выхода блока ГОУправления через открытый блок элементов И б перезаписывается в регистр 3 (причем -содержание А остается в регистре 1), а содержание регистра 2 (число А)стирается сигналом с шестого выхода блока 10 управления. Затем блок элементов И б закрывается. В этой операции в регистрах 1 и 3 записано наибольшее из двух сравниваемых чисел.

Во второй операции элемент И 5

5 снова открывается на время записи с входной шины 11 на регистр 2 следующего сравниваемого числа. В случае, если это число меньше значения, находящегося в регистрах 1 и 3, то указанный процесс повторяется и число остается записанным в регистра 1 и 3, а число А2 стирается из регистра 2. В случае, если это число (А 10011) больше числа А 10001, то при их сравнении на схеме 9 срав-Нения на его втором выходе появляет-/ся сигнал () который поступает на второй вход блока 10 управления и разрешает подачу сигнала разрешения с четвертого выхода блока 10 управления для отпирания второй груп пы элементов И 7 (при этом группа элементов И б остается закрытой),сиг нал списывания информации с регистЕзОв 1, 2 и 3 (по пятому, шестому и седьмому выходам блока 10 управления При этом содержание Ку регистра 2 через открытую группу элементов И 7 перезаписывается в освобождающиеся разряды регистров 1 и 3. Затем блок элементов И 7 закрывается, в этом случае последнее сравниваемое число большее по величине, записано в регистрах 1 и 3. В случае, если А 2 со схемы 9 сравнения выд-ается сигнал с первого выхода и первое число А, остается записаннЕлм в регистрах 1 и 3, а второе число участвует в следующей операции сравнения. В следующей операции элемент И 5 открывается на время передачи с вход ной шины 41 на регистр 2 другого сравниваемого числа и т.д. После сравнения всех N чисел из требуемого массива данных в регистре 3 остается записанное самое большое по своей величине число из всего массива чисел. Во время выполнения последней N операции сравнения с восьмого выхо да блока 10 управления на вход счет чика 8 поступает тактовый импульс. Содержание счетчика 8 (в прямом и об ратном коде) является в данном .случ первым адресом отобранного наибольш го числа в первом цикле. Затем содержание регистра 3 (наи большее из сравниваемых чисел) и со держание счетчика 8 (первый адрес) переда1отся во внешнее устройство (например память или специализирова ное вычислительное устройство). При чем содержание регистра 3 передается также на внешний источник (блок памяти), в котором это значение (чи сло) стирается, чтобы не участвоват в поиске на следующих циклах. После этого регистры 1 и 3 списываются (очищаются), регистр 2 списывается в предьщущей операции сравнения, а, в счетчике 8 остается предыдущее содержание. Начинается второй цикл - поиск наибольшего числа из N-1 оставшихся чисел. Открывается элемент И 4 на время записи первого из сравниваемых чисел в регистр 1 и процесс повторяется аналогично указанному выше. После второго цикла на счетчик 8 выдается тактовый импульс и содержание счетчика равно второму адресу. Затем начинается третий цикл - поиск наибольшего числа из N-2 оставшихся чисел и т.д. В первом цикле выполняется N-1 операций сравнения, а во втором N-2 операций сравнения. В i-ом цикле выполняется N-i операций сравйения. В двух последних циклах (N-1)-OM и N-OM) выполняется только по одной операции сравнения (сС авнение N-1 н N чисел и соответственно одного из этих чисел с нулем).. В операцию сравнений входят собственно операция сравнения двух чисел в схеме 9 сравнения, запись чмсел в регистры 1 и 2 и перезапись чисел из регистров 1 или 2 в регистр 3. Общее количество операций сравнения в М циклах поиска . равно N(N-1) К 1 + S N-i 1 + Например, при N 100 необходимо выполнить К 4951 операций правнения. Считая, что все пересылки чисел в предлагаемом устройстве выполняются параллельно и принимая длительность такта в 1 мкс, получают время поиска 2 5 мс. Работа блока 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) выдаются сигналы по выходс1М 36 или 37, разрешающие перезапись чисел через блоки элементов И 6 или 7. При этом в случае сигнала на входе 32 с шестого выхода блока 10 (выход 39) выдается сигнгш установки нулевого состояния регистра 2. После выполнения всех действий операции сравнения вьщается сигнал с .выхода 41 в счетчик 8, а сигнал с выхода 43 дешифратора 37 перебрасывает триггер 18 (при этом элемент И 23 закрывается и тактовые импульсы перестают поступать в счетчик 16) и сбрасывает родержание счетчика 16. При этом элемент И 24 открывается и на выходах32-40 появляется тактовый импульс, который устанавливает нулевые сгостояния в регистрах 1, 2 и 3. Затем процесс,работы повторяется.

Данная структурная схема блока 1 управления составлена, для варианта, когда каждая операция сравнения определяется стартовым импульсом, подаваемым извне. Это целесообразно, когда количество сравниваемых чисел неизвестно. В противном случае така структурная схема должна быть дополнена еще одним распределителем, состоящим из триггера, элементов И, счетчика и дешифратора, один из выходов которого подсоединяется ко входу 33 (установочный вход триггер 18). Установочный вход триггера соединяется с третьим входом блока 10 управления (входная йина 11).

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

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

1. Устройство для сортировки чисел, содержащее регистры, счетчик, схему сравнения, элементы И, группы элементов И, блок управления, причем входная шина устройства соединена с первыми входами первого и второго элементой И, выходы которых подключены к информационным входам первого и второго регистров соответственно, выходы первого регистра соединены со входами первой группы схемы сравнения, выходы второго регистра подключены ко входам второй труппы схемы сравнения, первый и второй выходы которой соединены с первым и вторым входами блока управления соответственно, отличающеес я тем, что, с целью расширения функциональных возможностей з.а счет формирования последовательности упорядоченньь данн, в нем выходы первого и второго регистров соединены с информационными входами элементов И первой и второй групп соответственно, первый выход блока управления подключен к управлякяцим входам элементов И первой группы, выходы которых соединены со входами первой группы третьего регистра, второй выход блока управления подключен к управляющим входам элементов И второй группы, выходы KOtopbix соединечы со входами первого регистра и со входами второй группы третьего регистра,

третий, четвертый и пятый выходы блока управления подключены ко входам уп)авления первого, второго и третьего регистров соответственно, шестой и седьмой выходы блока управления

соединены со вторыми входами первого и второго элементов И соответственно, восьмой выход блока управ- ления подключен ко входу сброса счётчика, инфбрмационный вход которого соединен с девятым выходом блока управления, вход запуска устройства подключен к третьему входу блока управления.

2. Устройство по П.1, о тл и чающееся тем, что блок управления содержит элементы И, ИЛИ, триггеры, счетчик, дешифратор, генератор тактовых-сигналов, выход которого соединен с первыми входами первого и второго элементов И блока управления, первый и второй входы блока управления соединены со входами установки в единичное состояние первого и второго триггеров, прямые выходы которых подключены к первому и второму управляющим входам дешифратора, первый выход которого, подключен ко входам установки в нулевое состояйие первого и второго триггеров, выходы которых соединены с первьаи и вторым выходами блока управления, выход первого элемента И блока управления подключен к первому входу элемента ИЛИ и к информационному входу счетчика блока управления, выходы которого соединены с информационными входами дешифратора, второй ваход которого подключен ко второму входу второго элемента И блока управления выход которого соединен со вторьм входом элемента ИЛИ, выход которого подключен к первым входам третьего, четвертого, пятого, шестого и седьмого элементов И блока управления, третий выход дешифратора соединен со входами установки в нулевое состояние третьего триггера, вход установки в единичное состояние которого подключен к третьему входу блока управления, а прямой выход - ко второму входу первого элементаИ блока упргшления, четвертый и пятьй выходы дешифратора соединены со входом установки в единичное состояние четвертого и пятого триггеров, шестой выход дешифратора подключен ко входам установки в нулевое состояние четвертого и пятого триггеров, седьмой, восьмой, девятый, десятый и одиннадцатый выходы дешифратора соединены со вторыми входами третьего, четвертого, пятого, шестого и седьмого элементов И блока управления соответственно, выходы третьего, четвертого и пятого элементов. И блока управления, прямые выходы четвертого и пятого триггеров выходы седьмого и шестого элементов И блока управления подключены к треТьему, четвертому, пятому, шестому, седьмому, восьмому и девятому выходгм блока управления соответственно.

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

13

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

2.Авторское свидетельство СССР 561960, кл.а 06 F 7/06, 1975 (прототип).

11.

fZ