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

)5 6 06 Р 7/О ОПИСАНИЕ ИЗОБРЕТ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ВКИ вы- ольвки,ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР(56) Авторское свидетельство СССРМ 826339, кл. 6 06 Р 7/06, 1979.Авторское свидетельство СССРМ 1441384, кл. 6 06 Р 7/06, 1986,(54) УСТРОЙСТВО ДЛЯ ССРТИРОЧИСЕЛ(57) Изобретение относится к областичислительной техники и может быть испзовано для построения устройств сортиро ранжировки и упорядочивания чисел. Цель изобретения - повышение быстродействия. Устройство содержит блок 1 управления, первую, вторую, третью, четвертую и пятую группы из и элементов И 2, 5, 6, 8, 10, где п - количество сортирувмых чисел, и регистров 7 сдвига, первую и вторую группы из и элементов ИЛИ 3, 11, первую и вторую группы из и триггеров 5, 9, элемент И-ИЛИ 12 и триггер 13 задержки, Повышение быстро- . действия устройства происходит за счет того, что начало поиска следующего по рангу числа совмещено с исключением из просмотра уже найденного максимального числа.1 з.п, ф-лы,2 ил,ЮИзобретение относится к области вычислительной техники и может быть использовано для построения устройств сортировки, ранжировки и упорядочивания чисел.Известно устройство для сортировки чисел, содержащее коммутирующие блоки, элементы И, элементы ИЛИ, триггер, счетчик, формирователь значения переменных, блок управления.Недостатком устройства является низкое быстродействйе.Известно также устройство для сортировки чисел, содержащее и кольцевых регистров, управляющие элементы И-ИЛИ, выходные элементы И-ИЛИ, дешифраторы,счетчики, элементы И, ИЛИ, регистр, узелсинхронизации, Недостаткам устройства является относительно низкое быстродействие. Наиболее близким по технической сущности к предлагаемому устройству являетсяустройство сортировки чисел, содержащееи щ-разрядных кольцевых регистров сдвига, где п - число сортируемых чисел, информационные входы которых являются информационными входами устройства, управляющий элемент И-ИЛИ, и элементов 2 И-ИЛИ, два элемента И, элемент ИЛИ, блок управления,причем прямой выход старшего разряда 1-го т-разрядного кольцевого регистра сдвига(1 = 1, и) соединен с управляющим входом1-го элемента И управляющего элемента ИИЛИ, отличающееся тем, что, с целью повыщения быстродействия, в устройство введены три группы триггеров, иэлементов И, иэлементов ИЛИ, причем инверсный выход старшего разряда -гов-разрядного кольцевого регистра сдвига соединен с первым входом первого элемента И.-го элемента 2 И-ИЛИ, выход которогосоединен с входом установки в "0" 1-го триггера первой группы, прямой выход которогоподключен к входу установки в "0" 1-го триггера второй группы и входу установки в единичное состояние 1-го триггера третьейгруппы, прямой выход которого является 1-м адресным выходом устройства и соединен с 5 10 15202530354045 информационным входом 1-го элемента И-.управляющего элемента И-ИЛИ, выход которого является выходом отсортированного числа устройства и соединен с вторым входом второго элемента И 1-го элемента 2 ИИЛИ, вход запуска устройства подключен к.первым входам всех элементов ИЛИ, входам установки в единичное состояние всехтриггеров второй группы и входу запуска блока управления, первый и второй выходыкоторого подключены к входам управления сдвигам всех гп-разрядных регистров сдвига, а третий выход соединен с первыми входами всех элементов И, всех вторых элементов И, всех элементов 2 И-ИЛИ, выход 1-го элемента И подключен к второму входу 1-го элемента ИЛИ, выход которого соединен с входом установки в единичное состояние 1-го триггера первой группы, инверсный выход которого подключен к входу установки в "0" 1-го триггера третьей группы, прямой и инверсный выходы 1-го триггера второй группы соединены с вторыми входами соответственно 1-го элемента И и второго элемента И 1-го элемента 2 И-ИЛИ, четвертый, пятый и шестой выходы блока управления соединены с синхровходами триггеров соответственно первой, второй и третьей групп.Блок управления содержит генератор импульсов, двойной триггер, счетчик, дешифратор, три элемента И и два элемента НЕ, причем выходы генератора импульсов подключены к синхровходам двойного триггера, первым входам соответственно первого и второго элементов И и счетным входам счетчика, выходы разрядов которого соединены с входами дешифратора, выходы которого соединены соответственно с третьим выходом блока управления и вторыми входами первого и второго элементов И, выходы которых являются соответственно четвертым и пятым выходами блока управления, а выход второго элемента И через первый элемент НЕ - с шестым выходом блока управления, вход запуска блока управления подключен к входу установки в "0" счетчика и информационному входу двойного триггера, выход которого соединен с уп-. равляющим входом счетчика и первым входом третьего элемента Ивторой выход которого соединен с первым выходом генератора импульсов, а выход является первым выходомблока управления и через второй элемент КЕ соединен с вторым выходом блока управления.Недостатком устройства-прототипа является его неспособность выполнить операцию сортировки за время, пропорциональное разрядности сортируемых чисел, т,е. за гп.п тактов. Это обстоятельство затрудняет использование такой сортировки в составе более сложных процессов, например, скалярной обработке матриц, где подобные операции выполняются в конвейерном режиме.Целью изобретения является повыше-. ние быстродействия.Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее блок управления, элемент И-ИЛИ, п регистров сдвига, где и - количество сорти1781680 10 20 30 35 40 45 55 руемых чисел, первую и вторую группы из и триггеров, первую группу из и элементов И, первую группу из и элементов ИЛИ и триггер задержки, причем информационные входы регистров сдвига являются информационными входами устройства, вход начальной установки устройства соединен с входом запуска блока управления, первый и второй выходы которого соединены с входами управления сдвигом всех регистров сдвига, третий выход блока управления соединен с первыми прямыми входами всех элементов И первой группы, четвертый выход блока управления соединен с первыми входами всех элементов ИЛИ первой группы, пятый выход блока управления соединен с входами синхронизации всех триггеров первой группы, шестой выход блока управления соединен с входом синхронизации триггера задержки, прямой выход старшего разряда 1-го регистра сдвига (1 - 1, 2, ., и) соединен с первым входом 1-го элемента И элемента И-ИЛИ, второй вход которого подключен к 1-му адресному выходу устройства, выход 1-го элемента.И первой . группы соединен с вторым входом 1-го элемента ИЛИ первой группы, выход которого соединен с входом установки в единичное состояние 1-го триггера второй группы, выход которого соединен с входом установки в нулевое состояние 1-го триггера первой группы, введены вторая группа из и элементов ИЛИ и четыре группы из и элементов И каждая, причем второй выход блока управления соединен с входами синхронизации всех триггеров второй группы, четвертый выход блока управления соединен с первыми входами всех элементов ИЛИ второй группы, пятый выход блока управления соединен с прямыми входами всех элементов И второй группы и с инверсными входами всех элементов И третьей группы, инверсный выход старшего разряда 1-го регистра сдвига соединен с первым входом 1-го элемента И четвертой группы, выход которого соединен с инверсным входом 1-го элемента И первой группы и с входом установки г. нулевое состояние 1-го триггера второй группы, выход которого соединен с первым входом 1-го элемента И пятой группы и с инверсным входом 1-го элемента И второй группы, выход которого соединен с вторым входом 1-го элемента ИЛИ второй группы, выход которого является 1-м адресным выходом устройства, выход 1-го элемента ИЛИ первой группы соединен с входом установки в единичное состояние 1-го триггера первой группы, выход которого соединен с прямым входом 1-го элемента И третьей группы, выход которого соединен с вторыми прямыми входами 1-х элементов И первой, четвертой и пятой групп, выход 1-го элемента И пятой группы соединен с третьим входом 1-го элемента ИЛИ второй группы, выход элемента И-ИЛИ соединен с информационным входом триггера задержки, выход которого соединен с третьими входами всех элементов И четвертой группы и является информационным выходом устройства. Блок управления содержит генератор импульсов, триггер, счетчик,элементы И, ИЛИ и элемент задержки, причем вход запуска блока управления соединен с его четвертым выходом, первым входом элемента ИЛИ, входом запуска генератора импульсов, входом установки в нулевое состояние счетчика, информационным входом и входом синхронизации триггера, выход которого соединен с первым входом элемента И, выход которого соединен со счетным входом счетчика, выход переполнения которого является третьим выходом блока управления, и соединен с входом элемента задержки, выход которого является пятым выходом блока управления, первый и второй выходы генератора импульсов соединены с вторыми входами соответственно элементов ИЛИ и И и являются соответственно первым и вторым выходами блока управления, выход элемента ИЛИ является шестым выходом блока управления.Проверим соответствие изобретения той цели, которая указана в формуле изобретения. Для этого определим выигрыш в быстродействии схемы устройства для сортировки чисел по сравнению со схемой и рототипа.Схема прототипа имеет особенность, что на каждом этапе сортировки прекращается подача синхроимпульсов на входы управления сдвигов и-разрядных кольцевых регистров 1 сдвига, т.е. происходит остановка работы, во время которой "происходит перезапись состояния 1-го триггера 6 в триггер 5". Сигнал с выхода 15 устройства управления прототипа поступает через каждые в тактов работы, сигнал с выхода 12 поступает. в следующем такте, уже после сигнала с выхода 15, что также выполняется с использованием счетчика, 8 результате по истечении (а+1) тгктов работы устройства прототипа будет выполнена операция выбора максимального числа из и а-разрядных чисел, а в(в+1) также его адрес будет считан с выхода 18 устройства. При этом нужноучесть начальную установку, которая также вносит задержку., Для схемы прототипа время выполнения операции сортировки тр массива из и а-разрядных чисел определяется выражением(1) где в последних скобках учитывается начальная установка устройства прототипа в исходное состояние,В схеме заявленного устройства повышение быстродействия достигается за счет того, что начало поиска следующего по рангу числа совмещено с исключением из просмотра уже найденного максимального числа, Кроме того, установка устройства в исходное состояние для работы совмещена с началом предварительного просмотра старших разрядов чисел. Для схемы заявленного устройства время выполнения операции сортировки т,умассива из и а- разрядных чисел определяется выражением; зу - (Г 1 +т 2) аи +тно (2) где тно =т 1 =г 2(по длительности),Причем, в отличие от прототипа, младший разряд максимального числа выдается уже во время действия синхроимпульса т 1 в-го такта, а его адрес - во время действия синхроимпульса т 2 щ-го такта, В схеме прототипа эти результаты выдаются одновременно, причем уже после (а+1)-го такта, на котором они получены, усложняет выдачу результата при ограничении на число контактных площадок,Из сравнения выражений (1) и (2) определим выигрыш в быстродействии Ьт; Ь= напр - Гзу(71 + 72) (и + 1) Способность заявленного устройства выполнять этап операции сортировки за гп тактов позволяет организовать работу в конвейерном режиме с устройствами, осуществляющими процесс обработки информации эа время, пропорциональное разрядности операндов,Заявленное устройство входит в состав блока скалярной обработки матриц матрично-алгебраической ЭВМ, разрабатываемой в Институте кибернетики АН УССР. Блок изготовляется по технологии микросборки. При этом применяется гибридный метод конструирования и изготовления БИС с использованием универсальных вентильных матриц типа 18068 П 1 (КМОП),Проведенный анализ известных устройств и схемы устройства прототипа позволяет сделать вывод, что существенные отличительные признаки, а именно: вторая группа из и элементов ИЛИ и четыре группы из и элементов И каждая, а также их связи с другими элементами устройства, отнесен 30 35 40 45 50 55 ные к отличительной части формулы изобретения, позволили придать заявленному устройству новое неизвестное свойство - совмещение начала поиска следующего по рангу числа с исключением иэ просмотра уже найденного максимального числа, что обусловило достижение положительного эффекта. Вторым свойством, проявляемым заявленным объектом, является выполнение устройством в одном полутакте функций анализа и принятия. решения, а в другом полутакте функций исполнения решения.Т,озаявленный объект проявляет новое техническое свойство, не присущее известным объектам и прототипу, следовательно, заявленное техническое решение соответствует критерию "Существенные отличия".На фиг. 1 изображено устройство для сортировки чисел; на фиг. 2 - блок управления,Устройство содержит управляющий 1 и информационные 2 входы, блок 3 управления, его выходы 4, 5, 6, 7, 8, 9, регистры 10, группы элементов И 11, 12, группу элементов ИЛИ 13, группы триггеров 14, 15, группы элементов И 16, 17, 18, группу элементов ИЛИ 19, адресные входы 20, элемент И-ИЛИ 21, триггер 22 задержки, информационный выход 23. Блок 3 управления содержит генератор 24 синхроимпульсов, элемент ИЛИ 25, триггер 26, элемент И 27, счетчик 28, элемент задержки 29.Особенностью схемы устройства для сортировки чисел является снятие информации с а-разрядных кольцевых регистров 10 сдвига, которые построены на двойных триггерах ВЯ-.типа. Инверсный выход стар-. шего разряда регистра 10 сдвига снимается с инверсного выхода вспомогательного триггера разряда, управляемого синхроимпульсом т 2, а прямой выход старшего разряда - с прямого выхода основного триггера старшего разряда, управляемого синхроимпульсом х 1Триггер 26 блока управления и триггер 22 задержки представляют собой синхронизируемые однотактные Р-триггеры, построенные на базе ВЯ-триггера,Триггеры 14, 15 первой и второй групп асимметричные, с несинхронизируемой установкой в единичное состояние и синхронизируемым сбросом в нулевое состояние.Устройство выполняет сортировку чисел, организованных в массив. Сравнение чисел выполняется поразрядно, начиная со старших разрядов. В случае, если все числа в рассматриваемом разряде имеют единичное значение, если же все они имеют нулевое значение, то к продолжению просмотра30 триггеров 14, 15 первой и второй групп в единичное состояние. Под действием этого сигнала производится запуск генератора 24 импульсов и сброс в начальное состояние счетчика 28, Элементом И-ИЛИ 21 произво 35 дится сравнение значений старших разрядов регистров 10 с единичным значением сигнала запуска, прошедшего через 1-е элементы ИЛИ 191 второй группы на первые входы 1-х элементов И элемента И-ИЛИ 21. Если хотя бы в одном регистре в старшем 40 разряде записано единичное значение, тотриггер 22 задержки установится в единичное состояние. В таком состоянии устройство готово к 45работе.После окончания действия сигнала запуска 1, генератор 24 импульсов блока 3управления начинает вырабатывать синхроимпульсы т 1 и т 2. С прямого выхода триггера 26 на первом входе элемента И 27 блока3 управления будет поддерживаться единичное значение в течение времени выполнения устройством ойерации сортировкичисел. В результате счетчик 28 будет считать 55единичные значения синхроимпульсов Г 1 ичерез каждые е тактов работы устройстваФвыдавать единичный синхроимпульс т 2,совпадающий с синхроимпульсом т 2,все числа находятся в равных условиях. Вслучае, если часть чисел в рассматриваемомразряде имеют единичное, а часть- нулевоезначение, то, при рассмотрении следующего меньшего по весу разряда, имевшая нулевое значение часть чисел исключается.Такт работы устройства определяетсясуммарной длительностью синхроимпульсов г 1 и г 2, После каждого такта рабаты устройства состояние старших разрядов 10регистров 101-10 п перепишется в их младшие разряды, На место старших разрядовпоступят значения цифр следующих разрядов, с весом на единицу меньшим, чем упредыдущего разряда. Для определения одного максимального числа (один этап сортировки) выполняются в старших тактовработы устройства, т.е. сколько разрядов вчисле ив регистре. Таким образом, для сортировки всех чисел массива необходимо 20пхп 1 тактов работы устройства (и этапов сортировки),В исходном состоянии в регистры 101-10 плюбым известным способом записываетсямассив сортируемых чисел (и в-разрядных 25чисел), После этого на вход блока 3 управления поступает единичный сигнал запуска 1.Длительность сигнала запуска 1 выбираетсядостаточной для установки триггера 26,Пусть в регистры 101-10 п сдвига записаны числа А = (а 1 а 2 аль, В = (Ь 1 Ь 2 Ь 4), ", С =- (с 1 с 2.сп),Рассмотрим работу устройства для сортировки чисел, Допустим, что старшие разряды а 1, Ь 1, , с 1 равны единице, т,е. а 1= Ь 1== с 1= 1. Тогда перед началом работы устройства триггер 22 задержки будет находиться в единичном состоянии.Начинается первый. этап сортировки чисел. Его результатом будет найденное максимальное число из массива. В момент действия синхроимпульса г, 1-е элементы И 12 четвертой группы сформируют нулевые сигналы и 1-е триггеры 14 второй группы останутся в единичном состоянии, а с информационного выхода 23 снимется значение старшего разряда максимального числа, равного единице. Одновременно в регистрах 10 информация сдвинется на один разряд, Допустим, что разряды а 2, Ь 2, ., С 2 равны нулю, т,е. а 2 = Ь 2 == С 2 = О, В момент действия синхроимпульса т 2 элемент И-ИЛИ 21 сформирует нулевой сигнал, значение которого запишется в триггер 22 задержки, Закончен первый такт работы устройства.В момент действия синхроимпульса х 1 второго такта 1-е элементы И 12 четвертой группы сформирует нулевые сигналы и 1-е триггеры 141 второй группы останутся в единичном состоянии, а с информационного выхода снимется нулевое значение, соответствующее второму разряду максимального числа. Одновременно в регистрах 10 информация сдвинется на один разряд,Допустим, что)-е разряды Ь,. с равны единице, т е. Ь = . = с = 1, а разряд аг- О, Тогда в момент действия синхроимпульса т О)-го такта работы устройства элемент И-ИЛИ 21 сформирует единичный сигнал, который запишется в триггер 22 задержки.Во время действия синхроимпульса т 1 )-го такта элементы И 122 - 12 П четвертой группы, соответствующие регистрам 102-10, сформируют нулевые сигналы и триггеры 142-14 п второй группы останутся в единичном состоянии, Элемент И 121 четвертой группы, соответствующий первому регистру 101 сформирует единичный сигнал, под действием которого первый триггер 141 второй группы сбросится в нулевое состояние. Сброс первого триггера 141 второй группы в нулевое состояние говорит в данном случае о том, что число, находящееся в первом регистре 101 является меньшим по величине, нежели числа в других регистрах 102 - 10 п, соответствующие которым триггеры 142-14 п второй группы сохранили единичное состояние. Нулевой сигнал с прямого выхода триггера 141 второй группы, блокируя вход первого элемента И элемента И-ИЛИ 21, исключает из поиска максимального числа число, записанное в первом регистре 101. 5С информационного выхода 23 снимается значение )-горазряда максимального числа, равное единице. Информация в регистрах 10 сдвинется на один разряд.Во время действия синхроимпульса 10 г 2 )-го такта элемент И-ИЛИ 21 сформирует сигнал, соответствующий анализу 0+1)-х разрядов сортируемых чисел. Его значение будет записано в триггер 22 задержки. Число, блокированное в)-м такте, где) = 1, 2, в, 15 не участвует в сортировке до окончания полного цикла сдвига в регистре 10, который Определяется разрядностью числа и регистра в. Закончен )-й такт работы устройства,В в-м такте работы устройства во время 20 действия синхроимпульеа х 1 будет определен адрес максимального числа, а с информационного выхода 23 будет выдано значение младшего разряда максимального числа. Информация в регистрах 10 сдвинет ся на один разряд, и они будут готовы к второму этапу сортировки.Во время действия синхроимпульса т 2 в-го такта с адресного выхода 20 будетсчитан адрес максимального числа первого 30 этапа сортировки (инверсное значение адреса). Одновременно счетчик 28 выдаст сийхрримпульс т 2, совпадающий с синхроимпульсом т 2 . Под действием синхроимпульса т 2 информация с прямых выходов 35 триггеров 14 второй группы будет принята на входы установки в нуль триггеров 15 первой группы, При этом каждый триггер 15 первой группы установится в состояние, противоположное состоянию соответствую щего триггера 14 второй группы. После в первых сдвигов в регистрах 101-10 п в единичном состоянии будут оставаться триггеры 14 второй группы, в соответствующих регистрах 10 которых находится максималь ное число для данного этапа сортировки.Синхроимпульс х 2, поступая на инверсный вход 1-го элемента И 17, третьей груп-.пы блокирует пРохождение сигнала с . прямого выхода 1-го триггера 15 первойгруппы. Т,е. производится отключение влияния момента возможного процесса переключения 1-го триггера 15 первой группы в нулевое состояние на работу схемы. Нулевой сигнал с выхода-го элемента И 17 третьей. группы блокирует прохождение единичного сигнала с выхода 1-го триггера 14 второй группы через 1-й элемент И 18 пятой группы. В момент действия синхроимпульса т 2 в-го такта элемент И-ИЛИ 21 сформирует сигнал, соответствующий предварительному анализу старших разрядов чисел, участвующих во втором этапе сортировки.Триггеры 14 второй группы соответствующих чисел еще находятся в нулевом состоянии. Поэтому для участия в предварительном просмотре старших разрядов соответствующих им чисел необходимо преобразование нулевого сигнала. Для этого прямой выход 1-го триггера 14 второй группы соединен с инверсным входом 1-го элемента И 16 второй группы.Если на прямой вход 1-го элемента И 16 второй группы поступает синхроимпульс х 2, то на первый вход 1-го элемента И элемента И-ИЛИ 21 поступает единичный сигнал для участия в новом этапе сортировки. Если же 1-й триггер 141 второй группы находится в данный момент в единичном состоянии, то с помощью 1-го элемента И 18 пятой группы,и 1-го элемента И 16 второй группы единичный сигнал блокируется, а на первый вход 1-го элемента И элемента ИИЛИ 21 подается нулевой сигнал. То есть производится исключение влияния уже выбранных в пройденных этапах сортировки чисел на последующие этапы сортировки оставшегося массива.Закончен первый этап сортировки, Начинается второй этап сортировки чисел, соответствующий ранее описанной процедуре, т,е. поиск меньшего по рангу максимального числа.В момент действия синхроимпульса т 1 первого такта элементы И 12 четвертой группы сформируют сигналы, соответствующие результату сравнения старших разрядов чисел, участвующих во втором этапе сортировки. Одновременно, под действием синхроимпульса т 1, совпадающего с синхроимпульсом г 1, будет производиться установка в единицу триггеров 14 второй группы для чисел, продолжающих сортировку в начавшемся этапе. При этом сигнал, сформированный элементом И 12 второй группы обладает большим приоритетом, по сравнению с единичным сигналом о восстановлении состояния триггера 14 второй группы, снимаемого с прямого выхода соответствующего триггера 15 первой группы (так как нет необходимости устанавливать триггер в единичное состояние, если уже пришел сигнал на его обнуление в новом этапе сорти- ровки). Для этого выход 1-го элемента И 121 четвертой группы соединен с инверсным входом 1-го элемента И 11 первой группы ис входом установки в нуль 1-го триггера 14 второй группы.Если 1-й элемент И 12 четвертой группы сформирует нулевой сигнал, то, под действием синхроимпульса т 1 (это задержанный1на полтакта синхроимпульс т 2) и единичного сигнала с выхода соответствующего 1-го триггера 15 первой группы произойдет восстановление единичного состояния 1-го триггера 14 второй группы,Для исключения чисел из процесса сортировки достаточно обнуления соответствующего триггера 15 первой группы, которое производится в конце каждого этапа сортировки. Нулевой сигнал блокировки с выхода этого обнуленного триггера 15 первой группы с помощью соответствующих элемента И 12 четвертой группы и элемента И 18 пятой группы производится отключение числа из сортируемого массива на все последующие этапы сортировки, При этом не требуется дополнительно обнулять соответствующий максимальному числу этапа триггер 14 второй,группы, находящийся в единичном состоянии, т,к. исключено его дальнейшее влияние на работу схемы.Аналогичные действия выполняются на каждом этапе сортировки. Нулевое состояние триггера 14 второй группы говорит о том, что содержимое соответствующего ему регистра 10 исключено из текущего этапа сортировки (а тактов сдвига), и что данное число будет участвовать в следующем этапе сортировки. Нулевое состояние триггера 15 первой группы соответствует запрещению участия числа во всех последующих этапах сортировки. Процедура очередного этапа сортировки соответствует ранее описанным действиям, т.е. в течение очередных а тактов сдвига с информационного выхода 23 устройства последовательно будет поступать разряд за разрядом следующее число из сортируемого массива (меньшее по рангу максимальное число), а по окончании каждого е-го сдвига - на адресный выход 20 устройства поступит адрес этого числа, Прйчем адрес инвертированный, т.е. его указывают нулевые значения сигналов с адресного выхода 20 устройства,В результате работы устройства для сортировки чисел с информационного выхода 23 устройства будут последовательно выданы отсортированные числа из массива, начиная с большего по рангу максимального числа и кончая меньшим по рангу числом из массива. На адресных выходах 20 устройства будут через каждые а тактов работы устройства (в конце каждого этапа сортировки) выдаваться адреса максимальных чисел, соответствующих по рангу номеру рассматриваемого этапа сортировки,Формула изобретения 1. Устройство для сортировки чисел, со держащее блок управления, элемент ИИЛИ, и регистров сдвига, где и - количествосортируемых чисел, первую и вторую группы из и триггеров; первую группу из и элементов И, первую группу из и элементов10 ИЛИ и триггер задержки, причем информационные входы регистров сдвига являютсяинформационными входами устройства, вход начальной установки устройства соединен с входом запуска блока управлений;15 первый и второй выходы которого соединены с входами управления сдвигом всех регистров сдвига, третий выход блока управления соединен с первыми прямымивходами всех элементов И первой группы, 20 четвертый выход - с первыми входамивсех элементов ИЛИ первой группы, пятый выход - с входами синхронизации всех триггеров первой группы, шестой выход - с входом синхронизации триггера задержки, 25 прямой выход старшего разряда 1-го регист. ра сдвига (1 = 1, 2, и) соединен с первымвходом 1-го элемента И, элемента И-НЕ, второй вход которого подключен к 1-му адрес- .ному выходу устройства, выход 1-го 30 элемента И первой группы соединен с вторым входом 1-го элемента ИЛИ первой группы, выход которого соединен с входом установки в единичное состояние 1-го триггера второй группы, выход которого соеди нен с входом установки в нулевое состояние1-го триггера первой группы, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, в него введены вторая группа из и элементов ИЛИ и четыре группы из и 40 элементов И каждая, причем второй выходблока управления соединен с входами синхронизации всех триггеров второй группы, четвертый выход - с первыми входами всех элементов ИЛИ второй группы, пятый выход 45 - с прямыми входами всех элементов И второй группы и с инверсными входами всех элементов И третьей группы, инверсный выход старшего разряда 1-го регистра сдвига соединен с первым входом 1-го элемента И 50 четвертой группы, выход которого соединенс инверсным входом 1-го элемента И первой. группы и с входом установки в нулевое состояние 1-го триггера второй группы, выход которого соединен с первым входом 1-го эле мента И пятой группы и с инверсным входом1-го элемента И второй группы, выход которого соединен с вторым входом 1-го элемента ИЛИ второй группы, выход которого является 1-м адресным выходом устройства, выход 1-го элемента ИЛИ первой группы со1781680 16 15 ЬМезаефер имкулссоб . злемеювЮФ 8 хоРфффффк ерзаю,Фиг. 2 Составитель Н.ФесенкоТехред М.Моргентвл Корректор Л.Ф едак аказ 4275 . Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ С 113035, Москва, Ж, Раушская наб., 4/5 зводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 1 единен с входом установки в единичное состояние 1-го триггера первой группы, выход . которого соединен с прямым входом 1-го элемента И третьей группы, выход которого соединен с вторыми прямыми входами 1-х элементов И первой, четвертой и пятой групп, выход 1-го элемента И пятой группы соединен с третьим входом 1-го элемента ИЛИ второй группы, выход элемента И-ИЛИ соединен с информационным входом триггера задержки, выход которого соединен с третьими входами всех элементов И четвертой группы и является информационным выходом устройства. 2. Устройство по п.1, отл и ча ю щеес я тем, что блок управления содержит генератор импульсов, триггер, счетчик, элементы И и ИЛИ и элемент задержки, причем вход запуска блока управления соединен с его,четвертым выходом, с первым входом элемента ИЛИ, входом запуска генератора импульсов, входом установки в нулевое со стояние счетчика, информационным входоми входом синхронизации триггера, выход которого соединен с первым входом элемента И, выход которого соединен со счетным входом счетчика, выход переполнения 10 которого является третьим выходом блокауправления и соединен с входом элемента задержки, выход которого является пятым выходом блока управления, первый и второй выходы генератора импульсов соедине ны с вторыми входами соответственноэлементов ИЛИ и И и является соответственно первым и вторым выходами блока управления, выход элемента ИЛИ является шестым выходом блока управления, 20