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

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

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

На фиг. 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.ri, группу элементов ИЛИ 16, элементы И 17- 20, элементы ИЛИ 21-24, вход контрольного числа 25, входы чисел сортируемого массива 26 . 1-26.п,управляющие входы 27-31, вход запуска 32, выходы равно 33.1-ЗЗ.п, Ьольше 34.1-24.п, Меньше 35.1-35.п, выход окончания работы устройства 36. Клок 4 сравнения содержит триггеры 37-39, элементы И 40-45, элемент ИЛИ 46, элемент 2И-2ИЛИ-НК 47, элементы НЕ 48 и 49, формирователь 5 импульсов.

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

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

Вход

Режим

чисел больших, чем

чисел, меньших, чем

чисел, рапных за

чисел в порядке

чисел в порядке убы-

5

0

5

0

5

0

5

0

5

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

На другие входы Ь блоков 4.1- 4.п сравнения поступают соответствующие разряды исходных чисел с выходов регистров 5.1-5.П через коммутаторы 6.2,...,6.п+1 под управлением сигналов с выхода счетчика 8.

Сигналом начала сравнения в блоке 4 является появление на входе R 2 блока управляющего сигнала с выхода бпока 3 управления.

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

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

После того, как на счетчик 8 поступит с выхода генератора 1 m счетных импульсов (где m - количество разрядов сортируемых чисел), на блок 3 управления поступит с выхода счетчика 8 сигнал А 4 (сигнал переполнения) , по которому блок 3 управления формирует выходной сигнал К (останов) и сбрасывает сигнал В 7 - сигнал об окончании процесса сравнения. После этого опрашиваются состояния выходов 33 блоков 4 сравнения. Единичный уровень на выходе 33 свидетельствует о том,что в соответствующем данному блоку (ч регистре 5t- находится число, больше заданного. Работа устройства в режимах определения чисел, меньших заданного и равных заданному, аналогична.

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

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

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

в нуль.

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

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

По сигналу В 8 блока 3 управления запускается генератор 2 импульсов,

16244406

формирует сигнал В 9, по которому содержимое счетчика 9 уменьшается на единицу, и вновь происходит процесс сравнения всех чисел.хранящихся в регистрах 5 с кодом (Х-1), и т.д.

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

15 на выходе 36.

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

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

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

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

Изобретение относится к вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет обеспечения ранжирования чисел в порядке возрастания или убывания. Устройство содержит генераторы 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

который путем последовательного сдви- ми устройства, выход Конец блока

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

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

управления является выходом окончания работы устройства, первый и второй управляющие выходы блока управления соединены соответственно с пер40 вым и вторым управляющими входами

всех блоков сравнения, выход Равно 1-го блока сравнения, где ,2,..., п, является i-м выходом Равно устройства, отличающееся

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

50 четыре элемента И, две группы элементов И, п групп элементов И перезаписи, группа элементов ИЛИ, четыре элемента ИЛИ, три счетчика, группа из п+1 коммутаторов, дешифратор и

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

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

5

0

5

0

5

0

5

0

5

входом блока управления, девятый управляющий выход которого соединен с первыми входами третьего и четвертого элементов И, четвертый и пятый управляющие входы устройства соединены соответственно с тестым и седьмым управляющими входами блока управления, вторыми входами соответственно первого и второго, а также соответственно четвертого и третьего элементов И, выходы которых соединены соответственно с входом установки третьего счетчика в нулевое состояние, входов установки третьего счетчика в состояние все единицы, его суммирующим и вычитающем входами, выход переполнения которого соединен с восьмым управляющим входом блока управления, вход j-ro разряда 1-го сортируемого числл устройства соединен с информационным входом j-ro разряда 1-го входного регистра группы, выход j-ro разряда которого соединен с вторым входом j-ro элемента И перезаписи i-й группы и с j-м информационным входом 1+1-го коммутатора, выход которого соединен с вторым информационным входом 1-го блока сравнения, выход Равно которого соединен с первым входом 1-го элемента И второй группы и с вторым входами всех элементов И перезаписи 1-й группы, выход 1-го разряда сдвигающего регистра соединен с вторым входом 1-го элемента И второй группы, выход которого соединен с i-м входом четвертого элемента ИЛИ, выход которого соединен с входом синхронизации всех выходных регистров группы и с вторым входом третьего элемента ИЛИ, выход которого соединен со счетным входом первого счетчика, выходы разрядов которого соединены с соответствующими входами дешифратора, i-й выход которого соединен с входом разрешения записи 1-го выходного регистра группы, выход j-ro элемента И перезаписи 1-й группы соединен с i-м входом j-ro элемента ИЛИ группы, выход которого соединен с информационными входами j-x разрядов всех выходных регистров группы, выходы Больше и Меньше 1-го блока сравнения являются соответственно i-м выходом Колыпе и i-м выходом Меньше устройства.

Фиг. 2