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

 

Изобретение относится к вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет обеспечения ранжирования чисел в порядке возрастания или убывания. Устройство содержит генераторы 1 и . импульсов, блок 3 управления , п (по количеству чисел в Ус т 0 its Jjd 3D массиве) блоков срсзвнения 4.1-4.п, группу входных регистров 5.1-5.П, группу коммутаторов 6.1-6.П+1, счетчики 7-9, сдвигающий регистр 10, дешифратор 11, группу 1 выходных регистров , группы элементов И 13, 14.1- 14.п, группы элементов И перезаписи 15,1-15.п, группу 16 элементов ИЛИ, элементы И 17-20, элементы ИЛИ 21-24, вход 25 контрольного числа, входы 26.1-26.П чисел сортируемого массива , управляющие входы 27-31, вход запуска 32, выходы равно 33.1-ЗЗ.п, Больше 34.1-34.п, Меныле 35.1- 35.п, выход 36 окончания работы устройства . Устройство может работать в пяти режимах: нахождения чисел больших , меньших, равных заданному, сортировки чисел в порядке возрастания и убывания. 3 ил., 1 табл. 261 Ч8г Ј (Л N 4ь 4ь 4

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

СОЦИАЛИСТИЧЕСНИК

РЕСПУБЛИК (g)) g С 06 F 7/04

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

К А BTOPCKOMY СВИДЕТЕЛЬСТВУ

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

llO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4620683/24 (22) 15.12.88 (46) 30.01.91. Бюл. H 4 (72) В.А.Титов, L11.Т,Азанчеев, Е.В.Никоненко и П.F,.Шкуратов (53) 681.325.66(ORR.8) (56) Авторское свидетельство ССГР

В 997028, кл. Г 06 F 7/Э4, 1981.

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

1403059, кл, Г 06 F 7/04, 1984. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ 1!АССИВОВ ЧИСЕЛ (57) Изобретение относится к вычисли-. тельной технике. Пель изобретения расширение функциональных возможноcreA за счет обеспечения ранжирования чисел в псрядке возрастания или убывания, Устройство содержит генераторы 1 и 2 импульсов, блок 3 управления, и (по количеству чисел в

Зд

„„SU„„) 624440 A 1

2 массиве) блоков сравнения 4.1-4.п, группу входных регистров 5.1 — 5.п группу коммутаторов 6. 1-6.п+1, счетчики 7-9, сдвигающий регистр 10, дешифратор 11, группу 12 выходных регистров, группы элементов И 13, 14.!в

14.п, группы элементов И перезаписи

15,1 †!5.п, группу 16 элементов ИЛИ, элементы И 17-20, элементы ИЛИ 21 — 24, вход 25 контрольного числа, входы

26.1-26.п чисел сортируемого массива, управляющие входы ?.7-31, вход запуска 32, выходы "равно" 33.1-33.п, "Больше" 34.1-34.п, "Меньше" 35.1—

35.п, выход 36 окончания работы уст— ройства. Устройство может работать в ля ни режимах: нахож;тония чисел боль- В ших, меньших, равных заданному, сортировки чисел в порядке возрастания и убывания. 3 ил., 1 табл. С:

1624440

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

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

На фиг. 1 приведена схема предлагаемого устройства; на фиг. 2 — схема блока сравнения, на фиг. 3 — схема блока управления.

Устройс гво содержит генераторы 1 и 2 импульсов, блок 3 управления, п (по количеству чисел в массиве) блоков 4.1-4.п сравнения, группу входных регис гров 5.1-5.п, группу коммугаторов 6.1-6.п+1, счетчик 7-9, сдвигающий регистр 10, дешифратор 11, группу выходных регистров 12, группы элементов И 13 и 14, группы элемен гов И перезаписи 15.1 — 15.п, группу элементов ИЛИ 16, элементы И 1720, элеменгы ИЛИ ?1-24, вход контрольного числа 25, входы чисел соргируемого массива ?6.1-?6.n,óïðàâляюшие входы 27-31, вход запуска 32, выходы "равно" 33.1-33.п, Больше"

34.1-24.п, "Меньше" 35.1-.35.п, выход окончания рабогы устройства 36.

Блок 4 сравнения содержит триггеры 37-39, элементы И 40-45, элемент ИЛИ 46, элемент 2И-2ИЛИ-HF. 47, элеменгы HF. 48 и 49, формирователь 50 импульсов.

Блок 3 управления содержит триггеры 51-55, элементы И 56-62, элементы ИЛИ 63-70, формирователи 71 и

72 импульсов, элемент 73 задержки, элемент HF. 74.

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

27-31 в соответствии с таблицей.

Режим

Вход

27 Нахождение чисел больших, чем

50 заданное

?8 Нахождение исел, меньших, «ем заданное

29 Нахожу;ение чисел, равных заданному

Соргировка «исел в порядке возрастали»

31 Сор гиоонка «исел в порядке убын;1ни»

В режиме выбора чисел, больших, чем заданное, в счетчик 9 в параллельном коде заносится по входу 25 контрольное число. Счетчик 9 в этом режиме храни г записанный код до конца процесса определения чисел, больших заданного. Процесс анализа чисел, хранящихся в регистрах 5, начинается со старших разрядов. Разряд счетчика

9 через коммутатор 6.1 под управлением сигналов с выхода счетчика 8 поступает на входы е блоков 4.1-4.п сравнения.

На другие входы б блоков 4.14.п сравнения поступают соответствующие разряды исходных чисел с выходов регисгров 5.1-5.п через коммутаторы

6.2,...,6.п+1 под управлением сигналов с выхода счетчика 8.

Сигналом начала сравнения в блоке

4 является появление на входе 5 2

1 блока управляющего сигнала с выхода бпока 3 управления.

Переход к анализу очередных разрядов чисел, хранящихся в счетчике 9 и регистрах 5, осуществляется коммутагорами 6.1,...,6.п+1 под управлением кода с выхода счетчика 8.

Изменение содержимого счетчика 8 происходиг под управлением сигналов с выхода генератора 1 импульсов, который первоначально запускается блоком 3 управления по управляющему сигналу В 7.

После гого, как на счетчик 8 поступит с выхода генератора 1 m счетных импульсов (где m — количество разрядов сортируемых чисел), на блок

3 управления поступит с выхода счетчика 8 сигнал A 4 (сигнал переполнения), по которому блок 3 управления формирует выходной сигнал "К" (останов) и сбрасывает сигнал В 7 — сигнал об окончании процесса сравнения.

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

5; находится число, больше заданного.

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

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

В режиме сортировки чисел в порядке убывания с выхода блока 3 управления в c÷åг«ике 9 через элемент

5 16

И 18 устанавливается код "Все единицы", счетчик 9 сигналом через элемент И 19 переводится и режим вычитания, а счетчик 8 устанавливается в нуль.

Изменение содержимого счетчика 9 происходит по управляющему сигналу

В 9, который формируется в блоке 3 управления, после того как произойдет сравнение по всем разрядам текущего значения счетчика 9 и значений регистров 5. После сравнения всех разрядов очередного кода Х, записанного в счетчике 9, с соответствующими разрядами исел, находящихся на регистрах 5,, устройство работает следующим образом.

По сигналу А 4 с выхода счетчика

8 блок 3 управления сбрасывает сигнал В 7, после чего останавливается генератор 1 импульсов. Наличие "1" на выходах 33 блоков 4; свидетельствует о наличии в соответствующих регистрах 5 чисел, равных Х, которые далее следует поместить в группу регистров 12. Информация на входы регистров 12 поступает с выходов соответствующих регистров 5; через группы элементов И 15 и элементов

ИЛИ 16 под управлением сигнала В 8 с выхода блока 3 управления.

По сигналу В 8 блока 3 управления запускается генератор 2 импульсов, который путем последовательного сдвига единицы в регистре 10 опрашивает выходы 33 всех блоков 4 сравнения.

При наличии единицы на соответствующем выходе 33, элементы И 14, и ИЛИ

24 формируют сигнал разрешения записи, по которому код из соответствующего регистра 5; через элементы И 15 и ИЛИ 16 поступает на вход гоуппы регистров 12 по адресу, заданному счетчиком 7 и дешифратором 11. Этот же сигнал разрешения записи с выхода элемента ИЛИ 24 увеличивает содержимое счетчика 7, т.е. формирует следующий адрес в группе регистров 12.

Процесс поиска чисел, равных Х, продолжается до тех пор, пока регистр

10 не опросит выходы 33 всех блоков

4 сравнения с записью в регистры 12 всех чисел, равных Х, после чего на выходе регистра 10 формируется сигнал А 5, который поступаег в блок 3 управления и сбрасывает сигнал В 8, останавливая работу генератора 2 импульсов. Затем блок 3 управления

24440 6 формирует сигнал В 9, по которому содержимое счетчика 9 уменьшаегся на единицу, и вновь происходит процесс

5 сравнения всех чисел, хранящихся в регистрах 5 с кодом (Х-1), и т.д.

Процесс сортировки чисел в порядке убывания будет происходить до тех пор, пока на счетчике 9 не будет зафиксирован код нуля, после чего на выходе счетчика 9 сформируется сигнал

А 8, который поступает н блок 3 управления и переводит устройство в состояние "Останов", формируя сигнал на выходе 36.

В режиме сортировки чисел в порядке убывания счетчик 9 сигналом через элемент И 17 устанавливается в нулевое состояние, а через элемент И 20

20 в режим сложения. Дальнейшая работа устройства аналогична.

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

Устройство для сортировки массивов чисел, содержащее сдвигающий регистр, группу из п входных регистров, где n — количество сортируемых чисел, группу из и блоков сравнения и блок управления, вход запуска которого и первый, второй и третий управляющие входы являются соответственно входом запуска устройства и первым, вторым и третьим управляющими входами устройства, выход, "Конец" блока управления является выходом окончания работы устройства, первый и второй управляющие выходы блока управления соединены соответственно с первым и вторым управляющими входами всех блоков сравнения, выход "Равно"

i-ro блока сравнения, где i = 1,2,..., и, является i ì выходом "Равно" устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения ранжирования чисел в порядке возрастания или убывания, в него введены два генератора импульсов, четыре элемента И, две группы элементов И, п групп элементoR И перезаписи, группа элементов ИЛИ, четыре элемента ИЛИ, три счетчика, группа из n+1 коммутаторов, дешифратор и группа из и выходных регистров, причем первый, второй и тре гий управляющие входы устройства соединены соответственно с первым, вторым и третьим входами пер»ого элемента

1624440

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

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

55 входoM блока управления, девятый управляющий выход которого соединен с первыми входами третьего и четвертого элементов И, четвертый и пятый управляющие входы устройства соединены соответственно с шестым и седьмым управляющими входами блока управления, вторыми входами соответственно первого и второго, а также соответственно четвертого и третьего элементов И, выходы которых соединены соответственно с входом установки третьего счетчика в нулевое состояние, входом установки третьего счетчика в состояние "все единицы, его суммирующим и вычитающим входами, выход переполнения которого соединен с восьмым управляющим входом блока управления, вход j-го разряда i-го сортируемого числа устройства соединен с информационным входом j-го разряда i-ro входного регистра группы, выход 1-го разряда которого соединен с вторым входом J — го элемента И перезаписи i-и группы и с J ì информационным входом i+1-го коммутатора, выход которого соединен с вторым информационным входом i-го блока сравнения, вьжод "Равно" которого соединен с первым входом 1-гo элемента И второй группы и с вторым входами всех элементов И перезаписи i — и группы, выход i-ro разряда сдвигающего регистра соединен с вторым входом i-го элемента И второй группы, выход которого соединен с -м входом четвертого элемента ИЛИ, выход которого соединен с входом синхронизации всех вьмодных регистров группы и с вторым входом третьего элемента ИЛИ, выход которого соединен со счетным входом первого счетчика, выходы разрядов которого соединены с соответствующими входами дешифратора, i-й выход которого соединен с входом разрешения записи i-ro выходного регистра группы, выход j-ro элемента И перезаписи i-й группы соединен с i-м входом j-го элемента ИЛИ группы, вьжод которого соединен с информационными входами

J-х разрядов всех выходных регистров группы, выходы "Больше" и "Меньше"

i-го блока сравнения являются соответственно i-м выходом "Больше" и

i-м выходом "Г1еньше" устройства.

l62i440

az

Bs

В1

1624440

А5

Составитель В. Горохов

Техрел М. Дидык Корректор И.Пожо

Редактор lO.Ñåpåäà

Заказ 190 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101