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

 

Изобретение относится к вычислительной технике и может быть использовано для построения устройств сорiO тировки и упорядочивания чисел. Цельн изобретения является повьшение быстродействия . Устройство содержит тразрядные кольцевые регистры сдвига 1, элементы И 2, элементы ИЛИ 3, эле- ;менты 2И-ИЛИ 4, триггеры 5, 6, 7, управляющий элемент И-ИЛИ 8, блок управления 9. Устройство выполняет анализ разрядов сортируеьвлх чисел, начиная со старших разрядов, выбор . максимального из них, затем исключения максимального числа из последовательности чисел, выбор максимального числа из оставшихся чисел и т.д. до упорядочивания всей последовательности чисел. 1 з.п. ф-лы, 2 ип. (Л 00 00

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИК (5В 4 С 06 F 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4035265/24-24 (22) 10.03.86 (46) 30,11.88. Бюл. К 44 (71) Институт кибернетики им. В.М.Глушкова (72) В.А.Вышинский, Б.M.Òèõîíîâ и Н.А.Карпенко (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

У 478303, кл, G 06 F 7/04, 1973.

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

Р 826339, кл. G 06 F 7/06, 1979. (54) УСТРОЙСТВО СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано для построения устройств сор.ЯО„, 1441384 А 1 тировки и упорядочивания чисел. Целыр изобретения является повышение быстродействия. Устройство содержит mразрядные кольцевые регистры сдвига

1, элементы И 2, элементы ИЛИ 3, эле-

;менты 2И-ИЛИ 4, триггеры 5, 6, 7, управляющы1 элемент И-ИЛИ 8, блок управления 9. Устройство выполняет анализ разрядов сортируежх чисел, начиная со старших разрядов, выбор максимального из них, затем исключения максимального числа из последовательности чисел, выбор максимального числа иэ оставшихся чисел и т.д. до упорядочивания всей последовательC ности чисел. 1 з.п. ф-хы, 2 ип.

1441384

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

Целью изобретения является повышение быстродействия.

На фиг. 1 изображено устройство сортировки чисел, на фиг. 2 — блок управления.

Устройство (фиг. 1) содержит mразрядные кольцевые регистры 1 сдвига, элементы И 2, элементы ИЛИ 3, элементы 2И-ИЛИ 4, триггеры 5-7, управляющий элемент И-ИЛИ 8, блок 9 . управления, вход 10 запуска, выходы

11-17 блока управления, адресный выход 18, выход 19 отсортированного числа, информационные входы.

Блок управления содержит двойной триггер 20, генератор 21 импульсов, счетчик 22, дешифратор 23, элементы

И 24 и 25, элемент НЕ 26, элемент

И 27, элемент НЕ 28.

В кольцевые регистры 1, — 1д каждого модуля устройства массив сортируемых чисел записывается любым известным способом. По сигналу, поступающему на вход 10 блока 9 управления с помощью синхроимпульсов с, и, поступающих из генератора

2 1 импульсов, двойной триггер 20, триггеры 5-7 всех модулей устанавливаются в состояние " 1", этими же сигналами управления и синхроимпульсами счетчик 22 устанавливается в состояние "0". После этого установившееся состояние "1 двойного триггера 20 с помощью очередной серии синхроимпульсов, и . устанавливает счетчик 23 в состояние

000...01 (младшие разряды справа) .

Это же единичное состояние триггера

20 разрешает прохождение синхроимпульсов ., и Г через элемент И 24 на кольцевые регистры 1,-1„каждого модуля. С помощью этих синхроимпульсов начинает сдвигаться на один двоичный разряд информация в кольцевых регистрах 1, -1„. Допустим, что в старшем разряде одного из кольце вых регистров t, — 1„ цифра равна 1, тогда на выходе управляющего элемента И-ИЛИ 8 сигнал будет равен единич. ному состоянию, т.е . состоянию, разрешающему прохождение сигналов через схемы И элементов 2И-ИЛИ 4. Другими словами, нулевое состояние, например, в старшем разряде кольцевого регистра 1 одного из модулей поступает через первый вход элемента

2И-ИЛИ 4 на его выход. С приходом синхроимпульса с, с выхода 16 блока 9 управления поступает сигнал, который устанавливает триггер 5 в состояние "0". Второй синхроимпульс поступающий с выхода f7 блока управления, устанавливает триггер 7 в состояние "0". Состояние старшего разряда всех кольцевых регистров переписывается в самый младший их разряд. На место старшего разряда поступает значение цифры разряда с весом на единицу меньше . Аналогично выход старшего разряда всех кольцевых регистров 1, -1„ в случае единичного состояния на выходе управляющего элемента И-ИЛИ действует на соответствующие триггеры 5 и 7.

Если выход управляющего элемента

И-ИЛИ 8 соответствует нулевому сос25 тоянню, а этой случай, когда все цифры кольцевых регистров 1 -1 рассматриваемого разряда равны нулю, всф элементы И-ИЛИ, одним из входов которых являются инверсные выходы коль30 цевых регистров 1 -1д, закрыты, и сброс триггеров 5 и 7 устройства в состояние "0" с приходом синхроимпульсов, и, не осуществляется.

В этом случае иифорьмщия в кольцевых

Р гистрах 1 -1 сдвинется на один разряд. Сброс триггеров 5 и 7 в состояние "0" свидетельствует о том, что число (содержимое данного кольцевого регистра) является меньшим пЬ величине, чем числа (других кольцевых регистров 1 других модулей), соответствующие триггеры 5 и 7 которых находятся в состоянии " 1" . Управ. ляющий элемент И"ИЛИ 8 исключает их операции сортировки с помощью сиг нала, поступакщего из прямого выхода данного триггера 7. Нулевое состояние этого выхода блокирует.информацию, поступаюшую из кольцевого реГистра 1 на соо Йе"Рств",ующий Вход управляющего элемента И-ИЛИ 8. Эта блокировка действувт в течение очередных сдвигов в кольцевых регистрах 1 -1„ до окончания полного цик55 ла сдвига, который . измеряется коли. чеством сдвигов, равных m где mразрядность чисел. В течение m-го сдвига, а именно иа этапе действия синхроимпульса С помощью сигнала, 41384 второй группы и входу запуска блока

40 управления, первый и второй выходы

55 з f4 поступающего с блока 9 управления с выхода 15, i-й триггер 6 сбрасываетмя в состояние "0", если соответствующий триггер 5 в это время находится в состоянии "0". С наступлением состояния счетчика 22 блока 9 управления, равного числу m подача сннхроимпульсов с выходов 16 и 17 на входы кольцевых регистров 1,-1„ прекращается ° Это осуществляется подачей запрещающего сигнала из дешифратора 23 на элемент И 28. В это же время (состояние сче;"чика 23, равное числу m) происходят перезапись состояния i-ro триггера 6 в триггер 5 .

Прямые выходы триггеров 7 являются адресными выходами 18 устройств, с них считывается адрес наибольшего числа иэ чисел, сортируемых в течение предь»дущих m сдвигов . Само же это число считывается в течение этих

m сдвигов поразрядно на выход 19.

После m сдвигов в течение действия очередной посылки пары синхроим-пульсов, и с состояния триггеров

5 и 7 приобретают состояние триггера 6 предлагаемого устройства, i-е . триггеры 5 и 7 каждого модуля будут в состоянии "0", если в соответствующем i-м кольцевом регистре 1 находится число, ранее отсортированное в ранг большйх чисел. Состояние

"0" прямого выхода триггера 7 исключает из дальнейшей сортировки соответствующий кольцевой регистр 1 с помощью управляющего элемента ИИЛИ 8 °

Состояние "1" триггеров 5 и 7 говорит о том, что содержимое соответ4 ствующего -го регистра, исключенное в течение предыдущей сортировки (m сдвигов) теперь участвует в сортировке . Процедура очередного этапа сортировки соответствует ранее описанной процедуре, т.е. в течение очередных сдвигов на выход 19 устройства последовательно поступает разряд за разрядом следующее по величине число из сортируемого массива, à по окончании m-ro сдвига на выход 18 поступает адрес этого числа.

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

1, Устройство сортировки чисел, содержащее и m-разрядных кольцевых регистров сдвига, где и — чис5

30 ло сортируемых чисел, информационные входы которых являются информационными входами устройства, управляющий элемент И-ИЛИ, п элементов 2И-ИЛИ два элемента И, элемент ИЛИ, блок управления, причем прямой выход старшего разряда i-го m-разрядного кольцевого регистра сдвига (i 1, п) соединен с управляющим входом

i-го элемента И управляющего элемен та И-ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью повышения быСтродействия, в устройство введены три группы триггеров п-2 элементов И, и-1 элементов ИЛИ, причем инверсный выход старшего разряда i-ro m-разрядного кольцевого регистра сдвига соединен с первым входом первого элемен» та И i-го элемента 2И-ИЛИ,. выход которого соединен с входом установки в "0" i-ro триггера первой группы, прямой выход которого подключен к входу установки в "0" i-го триггера второй группы и входу установки в единичное состояние i-ro триггера третьей группы, прямой выход которого является ».-и адресным выходом устройства и соединен с информациой- ным входом i-го элемента И управляю щего элемента И-ИЛИ, выход которого является выходом отсортированного числа устройства и соединен с вторым входом второго элемента И i-го элемента 2И-ИЛИ, вход запуска устройства подключен к первым входам всех элементов ИЛИ входам установки в единичное состояние всех триггеров которого подключены к входам управ" ления сдвигом всех m-разрядных регистров сдвига, а третий выход соединен с первыми входами всех элементов И, всех вторых элементов И, всех элементов 2И-ИЛИ, выход i-ro элемента И подключен к второму входу i-го элемента ИЛИ, выход которого соединен с входом установки в единичное состояние i-го триггера первой группы, инверсный выход которого нодключен к входу установки в "0" i-го триггера третьей группы, прямой и инверсный выходы i-го триггера второй группы соединены с вторыми входами соответственно i-ro элемента И и второго элемента И i-го элемента 2И-ИЛИ, четвертый, пятый и шестой выходы блока управления соединены с синхроСоставитель Е.Иванова

Техред М.Дидык Корректор, С.Шекмар

Редактор Е.Копча

Заказ 6289/52

Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4

5 1 входами триггеров соотве тственно первой, второй и третьей групп.

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

441384 6 элементов И, выходы которых являются соответственно четвертым и пятым выходами блока управления, а выход

5 второго элемента И через первый элемент НŠ— с шестым выходом блока управления, вход запуска блока управления подключен к входу установки в

"0" счетчика и информационному входу

10 двойного триггера, выход которого соединен с управляющим входом счетчика и первым входом третьего элемента И, второй выход которого соединен с первым выходом генератЬра

15 импульсов, а выход является первым выходом блока управления и через ,второй элемент НЕ соединен с вторым выходом блока управления.