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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Ресеублик

К АВТОРСКОМУ СВИ ЕТЕЛЬСТВУ (61) Дополнительное к авт. саид-ву— (зим. к.з

G 06 F 7/06 (22) Заявлено 19.10.79 (21)2845859/18-24 с присоединением заявки HP—

ГосударствеииыФ комитет

СССР ио делам изобретеиий и открытий (23) Приоритет—

Опубликовано 300981. Бюллетень Йо 36 (53) УДК 681. 325. 5 (088.8) Дата опубликования описания 300981 (72) Авторы изобретения й.Л.Рейхенберг и P.ß.Øåâ÷åíêî (71) Заявитель (54 ) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

Изобретение относится к автоматике и вычислительной технике и может

;быть использовано для поиска, орга.низации и упорядочения чисел.

Известно устройство для сортировки двоичных чисел, содержащее матрицу из ячеек (включающих элементы И, запрета и ИЛИ), элементы НЕ, элементы И и ИЛИ, триггеры и элементй задержки (1)е

Недостатком этого .устройства является его сложность.

Наиболее близким к предлагаемому является устройство для определения 15 положения числа на числовой оси, содержащее регистры, схемы сравнения, счетчики, генератор, блок синхронизации и элемент ИЛИ. Вь1Ход первого регистра соединен со входом первой 20 схемы сравнения, на второй вход которого подсоединен выход счетчика, на вход которого подсоединен выход генератора, выход блока аинхронизации соединен со входом управления 5 второго счетчика (2 ).

Цель изобретения — расширение функциональных возможностей за счет формирования последовательности упорядоченных данных. ЗО

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

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

В

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

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

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

Блок управления (фиг.2) содержит генератор 15 тактовых импульсов, счетчик 16, дешифратор 17, триггеры 5

18-22, элементы И 23-29 элемент ИЛИ

30, входы 31,32 и 33 и выходы 34-43.

Устройство работает следующим образом.

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

20 выходах блока 10 управления отсутствуют сигналы разрешения для элемен- тов И 4 и 5 и группы элементов И 6 и

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

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

40 . Предположим, что число А =10001 (записанное в регистр 1) больше числа А = 00111 {записанного в регистр

2). Эти числа сравниваются между собой по величине на схеме 9 сравнения. На первом выходе схемы 9 сравнения в этом случае появляется сигнал (A<,А2), который передается на первый вход блока 10 управления.

Этот сигнал разрешает подачу с тре о тьего выхода блока 10 управления на управляющий вход первой группы элементов И 6 разрешающего сигнала. Содержание регистра 1 (A<) при помощй сигнала с пятого выхода блока 10 управления через открытый блок элемен55 тов И 6 перезаписывается в регистр 3 (причем .содержание А„ остается в регистре 1), а содержайие регистра 2 (число А )стирается сигналом с шестого выхода блока 10 управления. ЗаgO тем блок элементов И 6 закрывается.

Б этой операции в регистрах 1 и 3 записано наибольшее из двух сравниваемых чисел.

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

65 снова открывается на вРемя записи с

868749 входной шины 11 на регистр 2 следующего сравниваемого числа. В случае, если это число меньше значения, находящегося в регистрах 1 и 3, то указанный процесс повторяется и число А4 остается записанным в регистрах

1 и 3, а число А> стирается йз регистра 2. В случае, если это число (А = 10011) больше числа Ag =10001, то при их сравнении на схеме 9 .срав-иения на его втором выходе появляет ся сигнал (А. ?A ), который поступает на второй вход блока 10 управления. и разрешает подачу сигнала разрешения с четвертого выхода блока 10 управления для отпирания второй груп- пы элементов И 7 (при этом группа элементов И б остается закрытой),сигнал списывания информации с регистров 1, 2 и 3 (по пятому, шестому и седьмому выходам блока 10 управления).

При этом содержание А регистра 2 20 через открытую группу элементов И 7 перезаписывается в освобождающиеся разряды регистров 1 и 3. Затем блок элементов И 7 закрывается. В этом случае последнее сравниваемое число, 5 большее по величине, записано в регистрах 1 и 3. В случае, если А< =А, со схемы 9 сравнения выдается сигнал с первого выхода и первое число

A остается записанным в регистрах

1 и 3, а второе число участвует в .1 следующей операции сравнения.

В следующей операции элемент И 5 открывается на время передачи с входной шины 11 на регистр 2 другого 35 сравниваемого числа и т.д. После сравнения всех и чисел из требуемого массива данных в регистре 3 остается записанное самое большое по своей величине число из всего массива чисел. Во время выполнения последней 40 и операции сравнения с восьмого выхода блока 10 управления на вход счетчика 8 поступает тактовый импульс.

Содержание счетчика 8 (в прямом и обратном коде) является в данном случае 4 первым адресом отобранного наибольшего числа в первом цикле.

Затем содержание регистра 3 (наибольшее из сравниваемых чисел) и содержание счетчика 8 (первый адрес) . gg передастся во внешнее устройство (например память или специализированное вычислительное устройство). При.— чем содержание регистра 3 передается также на внешний источник (блок памяти), в котором это значение (число) стирается, чтобы не участвовать в поиске на следующих циклах. После этого регистры 1 и 3 списываются (очищаются), регистр 2 списывается в предыдущей операции сравнения, а. Я} в счетчике 8 остается предыдущее содержание.

Начинается второй цикл †поиск наибольшего числа из й-1 оставшихся чисел. Открывается элемент И 4 на Q время записи первого из сравниваемых чисел в регистр 1 и процесс повторяется аналогично указанному выше. После второго цикла на счетчик 8 выдается тактовый импульс и содержание счетчика равно второму адресу.

Затем начинается третий цикл — поиск наибольшего числа из й-2 оставшихся чисел и т.д.

В первом цикле выполняется й-1 операций сравнения, а во втором— й-2 операций сравнения. В i — îì цикле выполняется N-i операций сравнения.

В двух последних циклах (N-1)-ом и й-ом) выполняется только по одной операции сравнения (сравнение N-1 и

N чисел и соответственно одного из этих чисел с нулем).. В операцию сравнения входят собственно операция сравнения двух чисел в схеме 9 сравнения, запись чсел в регистры 1 и 2 и перезапись чисел из регистров 1 или

2 в регистр 3. Общее количество операций сравнения в N циклах поиска . равно

N(N-1)

К = 1 +2 N— - i = 1 +

1-4

Например, при и = 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 управления составлена,для варианта, когда каждая операция сравнения определяется стартовым импульсом, подаваемым извне. Это целесообразно, когда количество сравниваемых чисел неизвестно. В противном случае такая структурная схема должна быть дополнена еще одним распределителем, состоящим из триггера, элементов И

1 счетчика и дешифратора, один из выходов которого подсоединяется ко входу 33 (установочный вход триггера

18). Установочный вход триггера соединяется с третьим входом блока 10 управления (входная шина 11). 20

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

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

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

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

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

ИЛИ, выход которого подключен к первым входам третьего, четвертого, пятого, шестого и седьмого элементов

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

И блока управления подключены к тре10

868749

1. Авторское свидетельство СССР

9 526888, кл.G 06 F 7/00, 1974.

2. Авторское свидетельство СССР

Р 561960, кл.G 06 F 7/06, 1975 (прототип).

Ри f

ПИ Заказ 8329/70 ж 748 Подписное

87 N ЮУ Ю Ь М

Pvr. Р тьему, четвертому, пятому, шестому, седьмому, восьмому и девятому выходам блока управления соответственно.

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

Филиал ППП "Патент", у®д.ород, ул.Проектная,4