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

(504 С 06 ЕН ЪюуЕЛЬСТ В Н АВТОРСКО тельство СССР7/06, 1980.ельство СССРР 7/06, 1983.СОРТИРОВКИ ЧИСЕ ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ПИСАНИЕ ИЗ(57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки данных.Целью изобретения является повыше ние быстродействия при сортировкемассива, содержащего равные числа.Устройство содержит распределительимпульсов, регистры, элементы сравнения, группы входных и выходных элементов И, счетчик, сумматор, регистррезультата, дешифраторы, шифратор,генератор импульсов, элементы И,триггер управления, ассоциативныерегистры, группы элементов И, ИЛИ,элементы запрета, задержки, элементИЛИ-НЕ. Как следует из изобретения,работа устройства состоит из двухэтапов. На первом этапе путем последовательного сравнения содержимогосоответствующего регистра со всемиостальными определяется количествочисел, меньших размещенного в данном регистре, фиксируемого счетчикомв текущем цикле, Затем с помощью первого дешифратора определяется номерассоциативного регистра, в которыйзаписывается двоичный код, номеранализируемого регистра. Этот кодформируется шифратором из выходныхсигналов распределителя импульсов,которые отражают номер цикла работыустройства, т,еномер анализируемого регистра. 1 ил.этого производится поочередное сравнение чисел, и в ассоциативных регистрах 19 фиксируются номера регистров 2 так, что они отражают размещение чисел исходного массива в возрастающем порядке.Пусть при п=10 в регистрах мащен следующий массив чисел: а =5; а =1; а=2; а =6; а =5; 2 раза,=2; а =4 у 9 По первому импульсу с распределителя 1, в качестве которого может быть использован регистр сдвига,Изобретение относится к вычислительной технике и может быть использовано в системах обработки данных.Целью изобретения является повышение быстродействия при сортировкемассива, содержащего равные числа,На чертеже приведена функциональная схема устройства.Устройство содержит распределитель 1 импульсов, регистры 2, элементы 3 сравнения, группы входныхэлементов И 4, группы выходных элементов И 5 и 6, счетчик , сумматор 8, регистр 9 результата, дешифратор 10, группу элементов ИЛИ 11,шифратор 12, элементы И 13, 14, триггер 15 управления, элемент И 16,генератор 17 импульсов, дешифратор18, ассоциативные регистры 19, группы элементов И 20 переписи, группуэлементов И 21, элемент 22 задержки,группу элементов ИЛИ 23, элементы24 запрета, группы элементов И 25результата, группу элементов ИЛИ 26,элемент ИЛИ-НЕ 27, выход 28 разрешения выдачи, вход 29 запуска, выходы30, вход 31 разрешения выдачи, выход32 конца работы, выходы 33, вход 34задания начального адреса устройства.Устройство работает следующим образом.Исходное состояние устройства характеризуется тем, что распределитель1 импульсов, триггер 15 управленияи регистры 19 установлены в состояние вО" (не показано).Сортировка чисел устройством совместно с ЭВМ производится в дваэтапа.На первом этапе после принятияисходного массива в регистры 2 иАпо входам 34 в сумматор 8 понач,сигналу "ПУСК, поступающему повходу 29, триггер 15 управления устанавливается в состояние "1". Послеоткрываются элементы И 4 и число изрегистра 2, передается в регистр 9результата и одновременно сравнивается со всеми числами, находящимисяв регистрах 22, , в соответствующих элементах 33,0 сравнения. На выходах "Меньше" элементов 3 и 3 сравнения формируются единичные сигналы, а в счетчике 7 - значение И=2. При этом на третьем выходе дешифратора 18 возникает единичный сигнал, открывающий элементы И 20 . Одновременно единичный сигнал с первого выО хода распределителей 1 поступает нашифратор 12, на выходе которого формируется двоичный кс.,д числа 1. Так как триггер 15 установлен в состояние "1", то двоичный код номера регистра 2;, т.е. выходные сигналы шифратора 12, записывается в регистр 19. 20 По второму, очередному импульсугенератора 17 на втором выходе расДо поступления данного сигнала после того, как триггер 15 устано пределителя 1 формируется сигнал,и число а =-5 сравнивается во всехг25 элементах 3 сравнения, кроме 3.2.При этом единичные сигналы на выходах Меньше" формируют элементы3 Зз, 34, 3, 38, и 3 сравненияи аналогичным образом номер регистра 2 и так далее, т,е. двоичныйкод числа два будет записан в регистр 19, . Дальнейшая работа устройства аналогична. По десятому импульсу с распределителя 1 в регистрах 19 будут записаны номера регистров 2, однозначно соответствующиевозрастающему порядку размещенияв них чисел. Так для указанного примера в регистрах 19 размещены сле 4 О дующие номера регистров 2: 19,=9;19=0; 19 з=4; 19=0; 19,=8; 19 =7;отражает порядок возрастания чисел - 1-7.45По сигналу с 10-го выхода распределителя очередным импульсом генератора 17 устанавливается в "0" триг -гер 15, и элементом И 14 на выходе28 формируется единичный сигнал,5 Окак готовности устройства к выдачеотсортированного массива чисел. Од-.новременно устанавливается в "0"распределитель 1,Второй этап работы устройстваначинается при приходе сигнала наВход 3 1,1254467 0 20 3вился в состояние "0", на выходахэлементов ИЛИ 23 формируется следующий позиционный код в соответствии с содержимым регистров 19::1010111011, Посредством элементовзапрета 24, соединенных по приоритетной схеме, этот код преобразуется в позиционный код следующеговида: 1000000000, так как единичнымсигналом с выхода элемента ИЛИ 23по инверсным входам закрываютсяэлементы 24 запрета,По единичному сигналу с выходаэлемента ИЛИ 23, открываются элементы И 25, и двоичный код из регистра 19 т,е, код числа 9, через элементы И 25 и ИЛИ 26 поступает надешифратор 10. Так как триггер 15находится в 0, то по входу управления дешифратор 10 открыт, и наего 9-м выходе формируется единичный сигнал, которым через элементИЛИ 11 открыты элементы И 4 . Содержимое регистра 2 через эти элементы передается в регистр 9 результата, в котором фиксируется число а =1.9По сигналу с входа 31 через элементы И 5 выдается двоичный кодАнчч из сумматора 8 по вь одам 33, 30а через элементы И 6 на выходы 30 -содержимое регистра 9 результата.По адресу А,=Ачисло а =1 записывается в ячейку внешней памяти.Через время с определяемое зле З 5ментом 22 задержки, устанавливаетсяв "0" регистр 19, через открытыйэлемент И 21, . Одновременно в сумма-.тор 8 формируется очередной адресА =А 1+ 1. Время 7 выбирается таким,чтобы обеспечить надежное считываниевыходных сигналов элементов И 5, 6р ЭВМ. После установки в "0" регистра 45 19 на выходах элементов ИЛИ 23 формируется позиционный код 0010111011, преобразуемый элементами И 24 в код 0010000000. Единичным сигналом с выхода элемента И 24 открываются 50 элементы И 25 и содержимое регистра 19 т.е. двоичный код номера регистра 2. передается через элементы И 25и ИЛИ 26 на дешифратор 10. На четвертом выходе дешифратора 10 55 формируется единичный сигнал, который, через элемент ИЛИ 11открывает элементы И 4 4, и содержимое регистра 24 (а 4=2) фиксируется в регистре 9результата,По импульсу с входа 31 код адреса А и двоичный код числа 2 из регистра 9 передается во внешнее устройство,Через время с регистр 19устанавливается в "0", и работа устройства затем аналогична рассмотреннойвыше.По седьмому импульсу на входе 31последнее число а, =7 выдается вовнешнее устройство и все регистры 19оказываются в состоянии "0". При этомна выходе элемента И-НЕ 27 формируется единичный сигнал, поступающийпо выходе 32 в качестве сигналаконца работы устройства во второмэтапе. При необходимости сортировки чисел в убывающем порядке исходный массив должен быть принят в регистры 2 в обратном коде. Формула изобретения Устройство для сортировки чисел, содержащее распределитель импульсов, И регистров, п элементов сравнения, и групп входных элементов И, и -1 элементов запрета, счетчик, сумматор, две группы выходных элементов И, регистр результата, причем выходы-го регистра (=1,2п, где и - количество сортируемых чисел) соединены с первой группой входов -го элемента сравнения и с первыми входами соответствующих входных элементов И-й группы, выходы которых соединены с-й группой входов регистра результата и с (+1)ми группами входов элементов сравнения соответственно с (+1)-го по и -й, выходы входных элементов И-й группы, где=2,3ь, соединены с -ми группами входов элементов сравнения соответственно с первого по (1 -1)-й, выходы регистра результата соединены с первыми входами выходных элементов И первой группы, выходы которых являются выходами отсортированного числа устройства, выход не 1равенства-го элемента сравнениясоединен с-м входом счетчика, вход задания начального адреса устройства подключен к первому входу сумматора, выходы которого соединены с первыми входами соответствующих выходных5 1254 элементов И второй группы, выходы которых являются выходами адреса числа устройства, вторые входы выходных элементов И первой и второй групп подключены к входу разрешения выдачи результата устройства, 0 -е инверсные входы элементов запрета, где 3=1,2,о, объединены, о т л и - ч а ю щ е е с я тем, что, с целью повышения быстродействия при сорти О ровке массива, содержащего равные числа, в него введены два дешифратора, шифратор, п групп элементов И переписи, в групп элементов И результата, три группы элементов ИЛИ, груп па элеметов И, и ассоциативных регистров,- элемент задержки, триггер управления, три элемента И, элемент ИЛИ-НЕ, генератор импульсов, выход которого соединен с первыми входами 2 О первого и второго элементов И, второй вход первого элемента И подключен к прямому выходу триггера управления и первым входам элементов И переписи всех групп, а выход соеди нен с входом запуска распределителя1импульсов,-й выход которого соединен с первым входом 1 -го элемента ИЛИ первой группы и с 1 -м входом шифратора, п -й выход распределите- ЗО ля импульсов дополнительно подключен к первому входу третьего элемента И и второму входу второго элемента И, выход которого подключен к входу уски в "О" триггера управления, вход установки в которого является входом запуска устройства, инверсный выход которого соединен с инверсным входом элемента ИЛИ-НЕ, входом установки в "О" распределителя импульсов, уп-, равляющим входом первого дешифрато" ра и вторым входом третьего элемента И, выход которого является вйходом разрешения выдачи устройства . 45-й выход первого дешифратора соеди 467нен с вторым входом-го элемента ИЛИ первой группы, выход которого подключен к вторым входам входных элементов И-й группы, выходы разрядов счетчика соединены с соответствующими входами второго дешифратора, 1-й выход которого соединен с вторыми входами элементов И переписи-й группы, выходы которых подключены кинформационным входам 1 -го ассоциативного регистра, выходы которого1соединены с входами-го элемента ИЛИ второй группы и с информационными входами элементов И результата 11-й группы, выходы которых подключены к входам соответствующих элементов ИЛИ третьей группы, выходы которых соединены с соответствующими входами первого дешифратора, выходы шифратора соединены с третьими входами соответствующих элементов И переписи всех групп, 1 -е инверсные входы каждого 8 -го элемента запрета (1 =1, 26; б =1, 2и -1) соединены с выходом 1 -го элемента ИЛИ второй группы, выход первого элемента ИЛИ второй группы соединен с управляющими входами элементов И результата первой группы, с первым входом первого элемента И группы ц с первым входом элемента ИЛИ-НЕ, вы" ход-го элемента ИЛИ второй группы ( =2,3 и) соединен с прямым входом (-1)-го элемента запрета и с -м входом элемента ИЛИ-НЕ, выход б-го элемента запрета соединен с управляющими входами элементов И результата (5+1)-й группы и с первым входом Ь+1)-го элемента И группы, вторые входы элементов И группы соединены с вторымвходом сумматора и выходом элемента задержки, вход которого соединен с.входом разрешения выдачи устройства, выход элемента ИЛИ-НЕявляется выходом конца работы устройства.,юг оставитель Е. Иванова ехред Л.Сердюкова 52 Тир Подп омитета СССР открытий ая наб., д. 4/5Вака н ИИПИ Гос рст по делам13035, Москва зо Жоизводстве полиг еское дприяти дактор Н. Слободян 671нного ктенийРаушс Корректор В.Синицка жгород, ул. Проектная,