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

(51)5 с 06 Р 70 ЗОБРЕТЕНИЯТЕЛЬСТВУ ськив ство СССР 06, 1985. во СССР 06, 1985.(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычисли ОСУДАРСТВЕННЫЙ НОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯРИ ГКНТ СССР(56) Авторское свидетелВ 1305659, кл. С 06 Р 7Авторское свидетельсУ 1267403, кл. С 06 Р 7 тельной технике. Цель иэобретения -повышение быстродействия. Устройство содержит стековые блокн памяти(СБП) 1 и 2, операционнье регистры3-6, элемент 7 сравнения, дешифраторы 8 и 9, элементы НЕ 10 и 11, группу регистров 12,-12где .п - количество сортируемых чисел, блок 13управления, вход 14 запуска, выход15 окончания работ. Сортируемый массив размещается в регистрах 12. Происходит перезапись отсортированнойчасти массива из СБП 2 в СБП 1, покане будет найдено место, в котороеследует поместить очередной элементсортируемого массива. 1 ил.Изобретение относится к вычислительной технике и может быть использовано при реализации техническихсредств ЭВМ и систем обработки инфор"5мации,Цель изобретения - повышение быстродействия.На чертеже приведена схема устройства.10Устройство содержит стековые блоки памяти (СБП) 1 и 2, операционныерегистры 3-6, элемент 7 сравнения,дешифраторы 8 и 9, элементы НЕ 10 и11, группу регистров 12,-12, гдеи - количество сортируемых чисел,блок 13 управления, вход 14 запускаустройства и вход 15 окончания работы устройства, Выходы 16.,-16 блока13 управления соединены соответственно с управляющим входом элемента7 сравнения, входами разрешения считывания и записи операционных регистров 3-6, входами записи регистров группы 12, входами "Начало операции", 113 апись" и "Чтение" СБП 1 и 2,стробирующими входамп дешифраторов8 и 9. Входы 17 -17 блока 13 управ 9ления, подсоединены к выходам дешифраторов 8 и 9, элементов НЕ 10 и 11,элемента 7 сравнения, выходам "1(овецоперации" СБП 1 и 2, выходу (тл+1)-горазряда (п - количество разрядовсравниваемых чисел) регистра 3. Блок13 может быть выполнен по известнойсхеме микропрограммного управления,Устройство работает следующим образом,Первоначально сортируемые числазаписываются в регистры, и послесигнала по входу 14 происходит ихсдвиг в сторону регистров 12 с младшими номерами, при этом первое изчисел оказывается в регистре 3. Затемосуществляется сравнение чисел, нахо 45дящихся в регистрах 3 и 4. Если(РЗ) ( (Р 4), то (Р 4) (число, находящееся в регистре 4) переписывается:в регистр 5 и в вершину СБП 1. Послеокончания операции записи (что фиксируется сигналом на шине 17 ) число(Р 4) записывается в регистр 6, азатем - в СБП 2, Число иэ СБП 1 запи"сывается в регистр 5 и затем в регистр 4. Далее происходит сравнение(Р 4) и (РЗ). Если (Р 4) ) (РЗ), тоописанная последовательность опера"ций повторяется, если же (Р 4)(РЗ),то (Р 4) записывается в СБП 1. Затемв СБП 1 переписывается (РЗ) черезрегистры 4 и 5, а затем - содержимоеСБП 2, кроме последнего числа, причем момент окончания перезаписи иэСБП 2 в СБП 1 определяется дешифратором 9. После сдвига исходного массива чисел в регистрах 12 работа устройства повторяется,После поступления в регистр 3 числа, в (ш+1)-м разряде которого находится единица (вначале это число было записано в регистре 12 ,; ), (Р 4) записывается в СБП 1, а затем туда же переписывается и содержимое СБП 2, после чего на выходе 15 формируется сигнал окончания работы устройства.Формула изобретенияУстройство для сортировки чисел, содержащее группу из и регистров, где и- количество сортируемых чисел и элемент сравнения причем выходыразрядов -го регистра, где- 2,3п, соединены с соответствующими информационными входами (х)"го регистра, входы синхронизации всех регистров группы объединены, о т л и ч а ю щ е е с я тем, что, с целью повьппения быстродействия, в него введены первый и второй стековые блоки памяти,. первый и второй дешифраторы, первый и второй элементы НЕ, четыре операционных регистра, блок управления, а также (и+1)-й регистр группы, выходы разрядов которого соединены с соответствующими информационными входами и-го регистра группы, выходы разрядов первого регистра группы соединены с соответствующими информационными входами первого операционного регистра, выхо" ды разрядов которого соединены с со" ответствующими информационными входами первой группы элемента сравнения и второго операционного регистра, выходы разрядов которого соединены с соответствующими информационными входами второй группы элемента сравнения и с соответствующими информацион ными входами первой группы третьего и четвертого операционных регистров,Составитель В.ГороховТехред М.Ходанич Корректор В.Гирняк Редактор И.ДербакЗаказ 2829 Тираж 566 Подписное ВНИИПИ Государственного комитета по изобретениям н открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб д. 4/5 Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 5 159452 выходы разрядов которых соединены с соответствующими информационными входами соответственно второй и третьей групп второго операционного регистра, а также с информационными входами соответственно первого и второго стековых блоков памяти, информационные выходы которых соединены с вторыми информационными входами соответственна третьего и четвертого операционных регистров, выходы разрядов третьего операционного регистра соединены с информационными входами третьей группы четвертого операционного регистра, выходы разрядов адреса стековых блоков памяти соединены с соответствующими входами соответственно первого и второго дешифраторов, выходы которых соединены соответст венно с первым и вторым входами блока. управления и через соответственно первый и второй элементы НЕ - с третьим и четвертым входами блока управления, пятый и шестой входы 25 которого подключены соответственно к первому и второму выходам элемента сравнения, управляющий вход которого подключен к первому выходу блока управления выходы с второго по пя-тый которого. соединены с входами 6разрешения считывания соответственно с первого по четвертый операционных регистров, шестой выход блока управления соединен с входом записи первого операционного регистра и всех регистров группы, седьмой, восьмой и девятый выходы блока управления соединены с входами записи (соответственно второго, третьего и четвертого операционных регистров выходы с десятого по пятнадцатый блока управления соединены соответственно с входами "Начало операции", "Запись" и "Чтение" первого и второго стековых блоков памяти, выходы "Коней операции" которых соединены соответственно с седьмым и восьмым входами блока управления, шестнадцатый и семнадцатый выходы которого соединены со стробирующими входами соответственно первого и второго дешифра", торов, вход запуска устройства и выход (ш+1)-го разряда первого операционного регистра, где ш - количество разрядов сортируемых чисел, соединены соответственно с девятым и деся тым входами блока управления, восемнадцатый выход которого является выходом окончания работы устройства.