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

(5 ТЕНИЯ о ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБР К А ВТОРСКОМУ СВИДЕТЕПЬСТ(21) 4620683/24 (22) 15.12.88 (46) 30.01.9. Бюл. 1 4 (72) В.А.Титов, 11.Т,Азанчеев, Е.В.Никоненко и П.Е.Шкурат в (53) 681.325.66(088.8) (56) Авторское свидетельство СССР В 997028, кл. Г Об Р 7/Э 4, 1981,Авторское свидетельство СССР1403059, кл, С 06 Р 7/04, 1984, (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ 1 АССИВОВ ЧИСЕЛ (57) Изобретение относится к пычисл тельной технике. Пель изобретения расширение функциональных возможностей за счет обеспечения ранжирования чисел в порядке возрастания или убывания, Устройство содержит генераторы 1 и 2 импульсов, блок 3 управления, и (по количеству чисел вЗд массиве) блоков сравнения 4.1-4,п, группу входных регистров 5.1 - 5.п, группу коммутаторов 6. 1-б.п+1, счетчики 7-9, сдвигающий регистр 10, дешифратор 11, группу 12 выходных регистров, группы элементов И 13, 14,в 14.п, группы элементов И перезаписи 15,1 - 15.п, группу 16 элементов ИЛИ, элементы И 17-20, элементы ИЛИ 21 - 24, вход 25 контрольного числа, входы 26.1-26.п чисел сортируемого массива, управляющие входы 27-31, вход запуска 32, выходы "равно" 33,1-33.п, "Больше" 34.1-34.п, "11 еньше" 35.1 - .35.п, выход 36 окончания работы уст - ройства. Устройство может работать в пя ги режимах: нахож;тония чисел боль- В ших, меньших, равных заданному, сортировки чисел в порядке возрастания и убывания. 3 ил., 1 табл, С:Изобрегецие огцосится к вычислительной технике и может быть использовано при рдзработке спецпроцессоров для организации аппаратной сортировки массивов чисел,Пель изобретения - расширениефункциональных возможностей за счетобес.печения ранжирования чисел в порядке возрастания или убывания,На фиг, 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, элементы И 17- 2520, элемец гы ИЛИ 21-24, вход контрольного числа 25, входы чисел соргируемого массива 26.1-26.п,управляющие входы 27-31, вход запуска 32,выходы "равно" 33.1-33.п, нБольше"34.1-24.п, "Иецьк 5 ен 35,1-35.п, выход окончания работы устройства 36.Блок 4 сравнения содержит триггеры 37-39, элементы И 40-45, элемент ИЛИ 46, элемент 2 ИЙЛИ-НЕ 47,элеменгы НЕ 48 и 49, формирователь 50импульсов.Блок 3 управления содержит триггеры 51-55, элементы И 56-62, элементы ИЛИ 63-70, формирователи 71 и72 импульсов, элемент 73 задержки,элемент НЕ 74.Устройство может. работать в пятирежимах, которые устанавливаются едицн 5 ным сигналом по одному из входов27-31 в соответствии с таблицей.РежимВход27 Нахождение чисел больших, чем50заданное28 Нахождение висел, меньших, чемзаданное29 Нахождение чисел, равных здданномуСоргировка чисел в порядкевозрастания31 Сор гиоонкд чисел в порядке убы 55 Д 55 И Я В режиме выбора чисел, больших, чем заданное, в счетчик 9 в параллельном коде заносится по входу 25 контрольное число. Счетчик 9 в этом режиме храниг записанный код до конца процесса определения чисел, больших заданного. Процесс анализа чисел, хранящихся в регистрдх 5, начинается со старших разрядов. Разряд счетчика 9 через коммутатор 6.1 под управлением сигналов с выхода счетчика 8 поступает на входы а блоков 4.1-4,псравнения.На другие входы б блоков 4.1- 4.п сравнения поступают соответствующие разряды исходных чисел с выходов регисгров 5.1-5.п через коммутаторы 6.26.п+1 под управлением сигналов с выхода счетчика 8.Сигналом начала сравнения в блоке 4 является появление на входе 3 2 блока управляющего сигнала с выхода бпока 3 управления.Переход к анализу очередных разрядов чисел, хранящихся в счетчике 9 и регистрах 5, осуществляется коммутагорами 6.16.п+1 под управлением кода с выхода счетчика 8.Изменение содержимого счетчика 8 происходиг под управлением сигналов с выхода генератора 1 импульсов, который первоначально запускается блоком 3 управления по управляющему сигналу В 7.После гого, как на счетчик 8 поступит с выхода генератора 1 щ счетных импульсов (где ш - количество разрядов сортируемых чисел), на блок 3 управления поступит с выхода счетчика 8 сигнал А 4 (сигнал переполнения), по которому блок 3 управления формирует выходной сигнал "К" (останов) и сбрасывает сигнал В 7 - сигнал об окончании процесса сравнения.После этого опрашиваются состояния выходов 33 блоков 4 сравнения. Единичный уровень на выходе 33 свидетельствует о том,что в соответсгвующем данному блоку 4 регистре 5, находится число, больше заданного. Рдбога устройства в режимах определения чисел, меньших заданного и равных заданному, аналогична,Устройство работает следующим образом.В режиме сортировки чисел в порядке убывания с выхода блока 3 управления в счегчике 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.Процесс поиска чисел, равных Х, продолжается Ло тех пор, пока регистр 1 О не опросит выходы 33 всех блоков 4 сравнения с записью н регистры 12 всех чисел, равных Х, после чего на выходе регистра 10 формируется сигнал А 5, который поступаег в блок 3 управления и сбрасывает сигнал В 8, останавливая работу генератора 2 импульсов. Затем блок 3 управления24440 6формирует сигнал В 9, по которомусодержимое счетчика 9 уменьшаегся наединицу, и вновь происходит процесс 5сравнения всех чисел, хранящихся в регистрах 5 с кодом (Х), и т.д.Процесс сортировки чисел и лорялке убывания будет происходить Ло техпор, пока на счетчике 9 не будет зафиксирован код нуля, после чего навыходе счетчика 9 сформируется сигналА 8, который поступает н блок 3 управления и переводит устройство нсостояние "Останов", формируя сигнална выходе 36.В режиме сортировки чисел н порядке убывания счетчик 9 сигналом черезэлемент И 17 устанавливается н нулевое состояние, а через элемент И 20 20 в режим сложения. Дальнейшая работаустройства аналогична. 50 55 25 30 35 40 45 Формула изобретения Устройство для сортировки массивов чисел, содержащее сдвигающий регистр, группу из и входных регистров, где и - количество сортируемых чисел, группу из и блоков сравнения и блок управления, нхол запуска которого и первый, второй и третий управляющие входы являются соответственно входом запуска устройства и первым, вторым и третьим управляющими входами устройства, выход "Конец" блока управления является выходом окончания работы устройстна, первый и второй управляющие выходы блока управления соединены соответственно с первым и вторым управляющими входами всех блоков сравнения, выход "Равно" 1-го блока сравнения, гле 1 = 1,2 и, является- м выходом "Равно" устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения ранжирования чисел в порядке возрастания или убывания, и неговведены дна генератора импульсов,четыре элемента И, дне группы элементов И, и групп элементов И перезаписи, группа элементов ИЛИ, четыреэлемента ИЛИ, три счетчика, группаиз и+1 коммутаторов, дешифратор игруппа из и выходных регистров, причем первый, второй и тре гий управляющие входы устройства соединенысоответственно с первым, вторым итретьим входами первого элементаЖП 1, "и кото 1 ого соединен с первыми входами элементов И первой группы, вход 1-го разряда контрольногочисла устройства, где 3 = 1,2ш, ш - количество разрядов сортируемых чисел, соединен с вторым входом 1-го элемента И первой группы,ныход которого соединен с установочным входом 1-го разряда первогосчетчика, выход 3-го разряда которого соединен с 3-и информационнымвходом первого коммутатора группы,выход которого соединен с первымиинформационными входами всех блоковсравнения, третий, четвертый, пятыйи шестой управляющие входы которыхподключены соответственно к третьему, четвертому, пятому и шестомууправляющим выходам блока управления, третий управляющий выход которого соединен с первыми входами первого и второго элементов И, входомусгановки в нулевое состояние первого сче гчика, входом установки вединичное состояние первого разрядасдвигающего регистра и входами установки в нулевое состояние его осгальных разрядов и первым входом вгорого элемента ИЛИ, выход которого соединен с входом установки в нулевое сос гояние второго счетчика, выход переполнения которого соединен с вторым входом второго элемента ИЛИ и с чегвертым управляющим входом блока управления, седьмой управляющий выход которого соединен с входом запуска первого генератора импульсов, выход которого соединен с тактовым входом блока управления и со счетным входом второго счетчика, выходы разрядов которого соединены с управляющими входами всех коммутаторов группы, восьмой управляющий выход блока управления соединен с первыми входами всех элементов И перезаписи групп и входом запуска вгорого генератора импульсов, выход которого соединен с первым входом третьего элемента ИЛИ и сдвиговым входом сдвигающего регистра, выход п-го разряда которого соединен с входом установки в нулевое состояние первого счетчика, информационным входом первого разряда сдвигаю- щего регистра и пятым управляющим 5 10 15 20 25 30 35 40 45 50 55 входом блока управления, девятыйуправляющий выход которого соединенс первыми нходами третьего и четвертого элементов И, четвертый и пятыйуправляющие входы устройства соединены соответственно с шестым и седьмым управляющими входами блока управления, вторыми входами соответственно первого и второго, а также соответственно четвертого и третьегоэлементов И, выходы которых соединены соответственно с входом установкитретьего счетчика в нулевое состояние, входом установки третьего счетчика в состояние "все единицы, егосуммирующим и вычитающим входами, выход переполнения которого соединенс восьмым управляющим входом блокауправления, вход 3-го разряда 1-госортируемого числа устройства соединен с информационным входом 1-го разряда 1-го входного регистра группы,выход 1-го разряда которого соединен с вторым входом 1-го элемента Иперезаписи 1-й группы и с 1-м информационным входом +1-го коммутатора,выход которого соединен с вторым информационным входом 1-го блока сравнения, вьжод "Равно" которого соединен с первым входом -го элемента Ивторой группы и с вторым входами всехэлементов И перезаписи 1-й группы,выход 1-го разряда сдвигающего регистра соединен с вторым входом 1-гоэлемента И второй группы, выход которого соединен с -м входом четвертого элемента ИЛИ, выход которого соединен с входом синхронизации всехвьмодных регистров группы и с вторымвходом третьего элемента ИЛИ, выходкоторого соединен со счетным входомпервого счетчика, выходы разрядов которого соединены с соответствующимивходами дешифратора, -й выход которого соединен с входом разрешения записи -го выходного регистра группы,выход 1-го элемента И перезаписи 1-йгруппы соединен с д-м входом 3-гоэлемента ИЛИ группы, вьжод которогосоединен с информационными входами1-х разрядов всех выходных регистровгруппы, выходы "Больше" и "г 1 еньше"1-го блока сравнения являются соответственно 1-м выходом "Больше" и1-м вьжодом "11 еньше" устройства.1624440 едактор К 1.Середа Тираж одписн НТ СССР оизводственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина ЗаказВНИИПИ сударственного комит 113035, Моск