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

фиг 1

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

Известно устройство для сортировки чисел, содержащее коммутирующие блоки, элементы И, элементы ИЛИ, триггер, счетчик, формирователь значения переменных, блок управления.

Недостатком устройства Тявляется низкое быстродействие.

Известно также устройство для сортировки чисел, содержащее п кольцевых регистров, управляющие элементы И-ИЛИ, выходные элементы И-ИЛИ, дешифраторы, счетчики, элементы И, ИЛИ, регистр, узел синхронизации.

Недостатком устройства является относительно низкое быстродействие.

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

(1 1п) соединен с управляющим входом

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

элемента ИЛИ, выход которого соединен с входом установки в единичное состояние 1-го триггера первой группы, инверсный выход которого подключен к входу установки в О 1-го триггера третьей группы, прямой и

0 инверсный выходы 1-го триггера второй группы соединены с вторыми входами соответственно 1-го элемента И и второго элемента И 1-го элемента 2И-ИЛИ, четвертый, пятый и шестой выходы блока управления

5 соединены с синхровходами триггеров соответственно первой, второй и третьей групп.

Блок управления содержит генератор импульсов, двойной триггер, счетчик, де0 шифратор, три элемента И и два элемента НЕ, причем выходы генератора импульсов подключены к синхровходам двойного триггера, первым входам соответственно первого и второго элементов И и счетным входам

5 счетчика, выходы разрядов которого соединены с входами дешифратора, выходы которого соединены соответственно с третьим выходом блока управления и вторыми входами первого и второго элементов И, выхо0 ды которых являются соответственно четвертым и пятым выходами блока управления, а выход второго элемента И через первый элемент НЕ - с шестым выходом блока управления, вход запуска блока уп5 равления подключен к входу установки в О счетчика и информационному входу двойного триггера, выход которого соединен с управляющим входом счетчика и первым входом третьего элемента И, второй выход

0 которого соединен с первым выходом генератора импульсов, а выход является первым выходом блока управления и через второй элемент НЕ соединен с вторым выходом блока управления. |

5 Недостатком устройства-прототипа является его неспособность выполнить операцию сортировки за время, пропорциональное разрядности сортируемых чисел, т.е. за m.n тактов. Это обстоятельство за0 трудняет использование такой сортировки в составе более сложных процессов, например, скалярной обработке матриц, где подобные операции выполняются в конвейерном режиме.

5 Целью изобретения является повышение быстродействия.

Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее блок управления, элемент И-ИЛИ, п регистров сдвига, где п - количество сортируемых чисел, первую и вторую группы из п триггеров, первую группу из п элементов И, первую группу из п элементов ИЛИ и триггер задержки, причем информационные входы регистров сдвига являются информационными входами устройства, вход начальной установки устройства соединен с входом запуска блока управления, первый и второй выходы которого соединены с входами управления сдвигом всех регистров сдвига, третий выход блока управления соединен с первыми прямыми входами всех элементов И первой группы, четвертый выход блока управления соединен с первыми входами всех элементов ИЛИ первой группы, пятый выход блока управления соединен с входами синхронизации всех триггеров первой группы, шестой выход блока управления соединен с входом синхронизации триггера задержки, прямой выход старшего разряда 1-го регистра сдвига

(1 1,2п) соединен с первым входом 1-го

элемента И элемента И-ИЛИ, второй вход которого подключен к 1-му адресному выходу устройства, выход 1-го элемента И первой группы соединен с вторым входом 1-го элемента ИЛИ первой группы, выход которого соединен с входом установки в единичное состояние 1-го триггера второй группы, выход которого соединен с входом установки в нулевое состояние 1-го триггера первой группы, введены вторая группа из п элементов ИЛИ и четыре группы из п элементов И каждая, причем второй выход блока управления соединен с входами синхронизации всех триггеров второй группы, четвертый выход блока управления соединен с первыми входами всех элементов ИЛИ второй группы, пятый выход блока управления соединен с прямыми входами всех элементов И второй группы и с инверсными входами всех элементов И третьей группы, инверсный выход старшего разряда 1-го регистра сдвига соединен с первым входом 1-го элемента И четвертой группы, выход которого соединен с инверсным входом 1-го элемента И первой группы и с входом установки г нулевое состояние 1-го триггера второй группы, выход которого соединен с первым входом 1-го элемента VI пятой группы и с инверсным входом 1-го элемента И второй группы, выход которого соединен с вторым входом 1-го элемента ИЛИ второй группы, выход которого является 1-м адресным выходом устройства, выход 1-го элемента ИЛИ первой группы соединен с входом установки в единичное состояние 1-го триггера первой группы, выход которого соединен с прямым входом 1-го элемента И третьей группы, выход которого соединен с вторыми

прямыми входами 1-х элементов И первой, четвертой и пятой групп, выход 1-го элемента И пятой группы соединен с третьим входом 1-го элемента ИЛИ второй группы, 5 выход элемента И-ИЛИ соединен с информационным входом триггера задержки, выход которого соединен с третьими входами всех элементов И четвертой группы и является информационным выходом устройства.

0 Блок управления содержит генератор импульсов, триггер, счетчик, элементы И, ИЛИ и элемент задержки, причем вход запуска блока управления соединен с его четвертым выходом, первым входом элемента ИЛИ,

5 входом запуска генератора импульсов, входом установки в нулевое состояние счетчика, информационным входом и входом синхронизации триггера, выход которого соединен с первым входом элемента И, вы0 ход которого соединен со счетным входом счетчика, выход переполнения которого является третьим выходом блока управления, и соединен с входом элемента задержки, выход которого является пятым выходом

5 блока управления, первый и второй выходы генератора импульсов соединены с вторыми входами соответственно элементов ИЛИ и И и являются соответственно первым и вторым выходами блока управления, выход

0 элемента ИЛИ является шестым выходом блока управления.

Проверим соответствие изобретения той цели, которая указана в формуле изобретения. Для этого определим выигрыш в

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

Схема прототипа имеет особенность, что на каждом этапе сортировки прекраща0 ется подача синхроимпульсов на входы управления сдвигов n-разрядных кольцевых регистров 1 сдвига, т.е. происходит остановка работы, во время которой происходит перезапись состояния 1-го триггера 6 в триггер

5 5. Сигнал с выхода 15устройствауправления прототипа поступает через каждые m тактов работы, сигнал с выхода 12 поступает в следующем такте, уже после сигнала с выхода 15, что также выполняется с использованием

0 счетчика. В результате по истечении (т+1) тактов работы устройства прототипа будет выполнена операция выбора максимального числа из п m-разрядных чисел, а в(т+1)также его адрес будет считан с выхода 18 устройст5 ва. При этом нужноучесть начальную установку, которая также вносит задержку.

. Для схемы прототипа время выполнения операции сортировки тпр массива из п т-раз- рядных чисел определяется выражением

Гпр (П + Г2) (m + 1) П + (Гно + Г1 + Г2) ,

(1)

где в последних скобках учитывается начальная установка устройства прототипа в исходное состояние.

В схеме заявленного устройства повышение быстродействия достигается за счет того, что начало поиска следующего по рангу числа совмещено с исключением из просмотра уже найденного максимального числа. Кроме того, установка устройства в исходное состояние для работы совмещена с началом предварительного просмотра старших разрядов чисел. Для схемы заявленного устройства время выполнения операции сортировки гзу массива из п гл- разрядных чисел определяется выражением:

Гзу (Т1 + Tz) т П + Тн

(2)

где THO TI Г2 (по длительности).

Причем, в отличие от прототипа, младший разряд максимального числа выдается уже во время действия синхроимпульса ri m-ro такта, а его адрес - во время действия синхроимпульса Тг m-ro такта. В схеме прототипа эти результаты выдаются одновременно, причем уже после (т+1)-го такта, на котором они получены, усложняет выдачу результата при ограничении на число контактных площадок.

Из сравнения выражений (1) и (2) определим выигрыш в быстродействии Дт:

Дг гпр - г3у (t + тг) (п -Ы) .

Способность заявленного устройства выполнять этап операции сортировки за m тактов позволяет организовать работу в конвейерном режиме с устройствами, осуществляющими процесс обработки информации за время, пропорциональное разрядности операндов.

Заявленное устройство входит в состав блока скалярной обработки матриц матрич- но-алгебраической ЭВМ, разрабатываемой в Институте кибернетики АН УССР. Блок изготовляется по технологии микросборки. При этом применяется гибридный метод конструирования и изготовления БИС с использованием универсальных вентильных матриц типа 18068П1 (КМОП).

Проведенный анализ известных устройств и схемы устройства прототипа позволяет сделать вывод, что существенные отличительные признаки, а именно: вторая группа из п элементов ИЛИ и четыре группы из п элементов И каждая, а также их связи с другими элементами устройства, отнесенные к отличительной части формулы изобретения, позволили придать заявленному устройству новое неизвестное свойство - совмещение начала поиска следующего по

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

Т.о., заявленный объект проявляет новое техническое свойство, не присущее известным объектам и прототипу, следовательно, заявленное техническое решение соответствует критерию Существенные отличия. На фиг. 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.

Особенностью схемы устройства для сортировки чисел является снятие информации с m-разрядных кольцевых регистров 10 сдвига, которые построены на двойных триггерах RS-типа. Инверсный выход старшего разряда регистра 10 сдвига снимается с инверсного выхода вспомогательного

триггера разряда, управляемого синхроимпульсом Т2 , а прямой выход старшего разряда - с прямого выхода основного триггера старшего разряда, управляемого синхроимпульсом Г1 .

Триггер 26 блока управления и триггер 22 задержки представляют собой синхронизируемые однотактные D-триггеры, построенные на базе RS-триггера.

Триггеры 14, 15 первой и второй групп

асимметричные, с несинхронизируемой установкой в единичное состояние и синхронизируемым сбросом в нулевое состояние. Устройство выполняет сортировку чисел, организованных в массив. Сравнение

чисел выполняется поразрядно, начиная со старших разрядов. В случае, если все числа в рассматриваемом разряде имеют единичное значение, если же все они имеют нулевое значение, то к продолжению просмотра

все числа находятся в равных условиях. В случае, если часть чисел в рассматриваемом разряде имеют единичное, а часть - нулевое значение, то, при рассмотрении следующего меньшего по весу разряда, имевшая нулевое значение часть чисел исключается.

Такт работы устройства определяется суммарной длительностью синхроимпульсов ri и Т2 . После каждого такта работы устройства состояние старших разрядов регистров 10i-10n перепишется в их младшие разряды. На место старших разрядов поступят значения цифр следующих разрядов, с весом на единицу меньшим, чем у предыдущего разряда. Для определения одного максимального числа (один этап сортировки) выполняются m старших тактов работы устройства, т.е. сколько разрядов в числе и в регистре. Таким образом, для сортировки все х чисел массива необходимо nxm тактов работы устройства (п этапов сортировки).

В исходном состоянии в регистры любым известным способом записывается массив сортируемых чисел (п т-разрядных чисел). После этого на вход блока 3 управления поступает единичный сигнал запуска 1. Длительность сигнала запуска 1 выбирается достаточной для установки триггера 26, триггеров 14, 15 первой и второй групп в единичное состояние. Под действием этого сигнала производится запуск генератора 24 импульсов и сброс в начальное состояние счетчика 28. Элементом И-ИЛИ 21 производится сравнение значений старших разрядов регистров 10 с единичным значением сигнала запуска, прошедшего через 1-е элементы ИЛИ 19i второй группы на первые входы 1-х элементов И элемента И-ИЛИ 21. Если хотя бы в одном регистре в старшем разряде записано единичное значение, то триггер 22 задержки установится в единичное состояние.

В таком состоянии устройство готово к работе.

После окончания действия сигнала запуска 1, генератор 24 импульсов блока 3 управления начинает вырабатывать синхроимпульсы ri и Та . С прямого выхода триггера 26 на первом входе элемента И 27 блока 3 управления будет поддерживаться единичное значение в течение времени выполнения устройством операции сортировки чисел. В результате счетчик 28 будет считать единичные значения синхроимпульсов т и через каждые m тактов работы устройства

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

Пусть в регистры 10i-10n сдвига записаны числа А {aia2...am}. В {bib2...bm}

C {C1C2 ..Cm}.

Рассмотрим работу устройства для сор- 5 тировки чисел. Допустим, что старшие разряды ai, bi,.., ci равны единице, т.е. ai bi ... 01 1. Тогда перед начзлом работы устройства триггер 22 задержки будет находиться в единичном состоянии.

0 Начинается первый этап сортировки чисел. Его результатом будет найденное максимальное число из массива. В момент действия синхроимпульса г, 1-е элементы И 12i четвертой группы сформируют нулевые

5 сигналы и 1-е триггеры 14| второй группы останутся в единичном состоянии, а с информационного выхода 23 снимется значение старшего разряда максимального числа, равного единице. Одновременно в

0 регистрах 10 информация сдвинется на

один разряд. Допустим, что разряды 32, Ь2,

.... С2 равны нулю, т.е. 32 Ь2 ... С2 0. В

момент действия синхроимпульса тг эле- мент И-ИЛИ 21 сформирует нулевой сигнал,

5 значение которого запишется в триггер 22 задержки. Закончен первый такт работы устройства.

В момент действия синхроимпульса t второго такта i-e элементы И 12 четвертой

0 группы сформирует нулевые сигналы и 1-е триггеры 14| второй группы останутся в единичном состоянии, а с информационного выхода снимется нулевое знзчение, соответствующее второму разряду максималь5 ного числа. Одновременно в регистрах 10 информация сдвинется на один разряд.

Допустим, что j-e разряды Ь,.., cj равны единице, т.е. bj ... cj 1, а разряд а 0. Тогда в момент действия синхроимпульса

0 Т2 )-го такта работы устройства элемент

И-ИЛИ 21 сформирует единичный сигнал,

который запишется в триггер 22 задержки.

Во время действия синхроимпульса

Ti j-ro такта элементы И четвертой

5 группы, соответствующие регистрам 102-1 On, сформируют нулевые сигналы и триггеры второй группы останутся в единичном состоянии. Элемент И 12i четвертой группы, соответствующий первому регистру

0 id сформирует единичный сигнал, под действием которого первый триггер 14т второй группы сбросится в нулевое состояние. Сброс первого триггера 14i второй группы в нулевое состояние говорит в данном случае

5 о том, что число, находящееся в первом регистре 10i является меньшим по величине, нежели числа в других регистрах 102-10п, соответствующие которым триггеры 142-14п второй группы сохранили единичное состояние. Нулевой сигнал с прямого выхода триггера 14i второй группы, блокируя вход первого элемента И элемента И-ЙЛИ 21, исключает из поиска максимального числа число, записанное в первом регистре 10i.

С информационного выхода 23 снимается значение j-ro разряда максимального числа, равное единице. Информация в регистрах 10 сдвинется на один разряд.

Во время действия синхроимпульса Г2 j-ro такта элемент И-ИЛИ 21 сформирует сигнал, соответствующий анализу (j+1)-x разрядов сортируемых чисел. Его значение будет записано в триггер 22 задержки. Число, блокированное в J-м такте, где j 1, 2,.... m, не участвует в сортировке до окончания полного цикла сдвига в регистре 10, который определяется разрядностью числа и регистра т. Закончен j-й такт работы устройства.

В т-м такте работы устройства во время действия синхроимпульса ri будет определен адрес максимального числа, а с информационного выхода 23 будет выдано значение младшего разряда максимального числа. Информация в регистрах 10 сдвинется на один разряд, и они будут готовы к второму этапу сортировки.

Во время действия синхроимпульса Г2 m-ro такта с адресного выхода 20 будет считан адрес максимального числа первого этапа сортировки (инверсное значение адреса). Одновременно счетчик 28 выдаст синхроимпульс TZ , совпадающий с Синхроимпульсом Га . Под действием синхроимпульса Г2 информация с прямых выходов триггеров 14 второй группы будет принята на входы установки в нуль триггеров 15 первой группы. При этом каждый триггер 15 первой группы установится в состояние, противоположное состоянию соответствующего триггера 14 второй группы. После m первых сдвигов в регистрах 10v-10n в единичном состоянии будут оставаться триггеры 14 второй группы, в соответствующих регистрах 10 которых находится максимальное число для данного этапа сортировки.

Синхроимпульс тг , поступая на инверсный вход 1-го элемента И 17, третьей группы блокирует прохождение сигнала с прямого выхода 1-го триггера 15i первой группы. Т.е. производится отключение влияния момента возможного процесса переключения i-ro триггера 15i первой группы в нулевое состояние на работу схемы. Нулевой сигнал с выхода 1-го элемента И 17i третьей группы блокирует прохождение единичного сигнала с выхода i-ro триггера 14| второй группы через 1-й элемент И 18i пятой группы.

В момент действия синхроимпульса га m-ro такта элемент И-ИЛИ 21 сформирует сигнал, соответствующий предварительному анализу старших разрядов чисел, участвующих во втором этапе сортировки.

Триггеры 14| второй группы соответствующих чисел еще находятся в нулевом состоянии. Поэтому для участия в предварительном просмотре старших разрядов соответствующих им чисел необходимо преобразование нулевого сигнала. Для этого прямой выход 1-го триггера 14| второй группы соединен с инверсным входом 1-го элемента И 16i второй группы.

Если на прямой вход 1-го элемента И 16i второй группы поступает синхроимпульс Т2 , то на первый вход 1-го элемента И элемента И-ИЛИ 21 поступает единичный сигнал для участия в новом этапе сортировки.

Если же 1-й триггер 14| второй группы находится в данный момент в единичном состоянии, то с помощью 1-го элемента И 18i пятой группы и 1-го элемента И 16i второй группы единичный сигнал блокируется, а на

первый вход i-ro элемента И элемента И- ИЛИ 21 подается нулевой сигнал. То есть производится исключение влияния уже выбранных в пройденных этапах сортировки чисел на последующие этапы сортировки

оставшегося массива.

Закончен первый этап сортировки. Начинается второй этап сортировки чисел, соответствующий ранее описанной процедуре, т.е. поиск меньшего по рангу максимального числа.

В момент действия синхроимпульса Ti первого такта элементы И 12 четвертой группы сформируют сигналы, соответствующие результату сравнения старших разрядов чисел, участвующих во втором этапе сортировки. Одновременно, под действием синхроимпульса TI , совпадающего с синхроимпульсом п , будет производиться установка в единицу триггеров 14 второй группы для чисел, продолжающих сортировку в начавшемся этапе. При этом сигнал, сформированный элементом И 12 второй группы обладает большим приоритетом, по сравнению с единичным сигналом о восстановлении состояния триггера 14 второй группы, снимаемого с прямого выхода соответствующего триггера 15 первой группы (так как нет необходимости устанавливать триггер в единичное состояние, если уже пришел сигнал на его обнуление в новом этапе сортировки). Для этого выход 1-го элемента И 12| четвертой группы соединен с инверсным входом 1-го элемента И 11| первой группы и

с входом установки в нуль 1-го триггера 14i второй группы.

Если 1-й элемент И 12| четвертой группы сформирует нулевой сигнал, то, под действием синхроимпульса т (это задержанный на полтакта синхроимпульс Т2) и единичного сигнала с выхода соответствующего 1-го триггера 15i первой группы произойдет восстановление единичного состояния 1-го триггера 14| второй группы.

Для исключения чисел из процесса сортировки достаточно обнуления соответствующего триггера 15 первой группы, которое производится в конце каждого этапа сортировки. Нулевой сигнал блокировки с выхода этого обнуленного триггера 15 первой группы с помощью соответствующих элемента И 12 четвертой группы и элемента И 18 пятой группы производится отключение числа из сортируемого массива на все последующие этапы сортировки. При этом не требуется дополнительно обнулять соответствующий максимальному числу этапа триггер 14| второй группы, находящийся в единичном состоянии, т.к. исключено его дальнейшее влияние на работу схемы.

Аналогичные действия выполняются на каждом этапе сортировки. Нулевое состояние триггера 14 второй группы говорит о том, что содержимое соответствующего ему регистра 10 исключено из текущего этапа сортировки (т тактов сдвига), и что данное число будет участвовать в следующем этапе сортировки. Нулевое состояние триггера 15 первой группы соответствует запрещению участия числа во всех последующих этапах сортировки. Процедура очередного этапа сортировки соответствует ранее описанным действиям, т.е. в течение очередных m тактов сдвига с информационного выхода 23 устройства последовательно будет поступать разряд за разрядом следующее число из сортируемого массива (меньшее по рангу максимальное число), а по окончании каждого m-го сдвига - на адресный выход 20 устройства поступит адрес этого числа. Причем адрес инвертированный, т.е. его указывают нулевые значения сигналов с адресного выхода 20 устройства.

В результате работы устройства для сортировки чисел с информационного выхода 23 устройства будут последовательно выданы отсортированные числа из массива, начиная с большего по рангу максимального числа и кончая меньшим по рангу числом из массива. На адресных выходах 20 устройства будут через каждые m тактов работы устройства (в конце каждого этапа сортировки) выдаваться адреса максимальных чисел, соответствующих по рангу номеру рассматриваемого этапа сортировки. Формула изобретения 1. Устройство для сортировки чисел, со- 5 держащее блок управления, элемент И- ИЛИ, п регистров сдвига, где п - количество сортируемых чисел, первую и вторую группы из п триггеров, первую группу из п элементов И, первую группу из п элементов

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

5 первый и второй выходы которого соединены с входами управления сдвигом всех регистров сдвига, третий выход блока управления соединен с первыми прямыми входами всех элементов И первой группы,

0 четвертый выход - с первыми входами всех элементов ИЛИ первой группы, пятый выход-с входами синхронизации всех триггеров первой группы, шестой выход - с входом синхронизации триггера задержки,

5 прямой выход старшего разряда 1-го регистра сдвига (1 1,2, ..., п) соединен с первым входом 1-го элемента И, элемента И-НЕ, второй вход которого подключен к i-му адресному выходу устройства, выход 1-го

0 элемента И первой группы соединен с вторым входом 1-го элемента ИЛИ первой группы, выход которого соединен с входом установки в единичное состояние 1-го триггера второй группы, выход которого соеди5 нен с входом установки в нулевое состояние 1-го триггера первой группы, отличающееся тем, что, с целью повышения быстродействия, в него введены вторая группа из п элементов ИЛИ и четыре группы из п

0 элементов И каждая, причем второй выход блока управления соединен с входами синхронизации всех триггеров второй группы, четвертый выход - с первыми входами всех элементов ИЛИ второй группы, пятый выход

5 - с прямыми входами всех элементов И второй группы и с инверсными входами всех элементов И третьей группы, инверсный выход старшего разряда 1-го регистра сдвига соединен с первым входом 1-го элемента И

0 четвертой группы, выход которого соединен с инверсным входом 1-го элемента И первой группы и с входом установки в нулевое состояние 1-го триггера второй группы, выход которого соединен с первым входом 1-го эле5 мента И пятой группы и с инверсным входом 1-го элемента И второй группы, выход которого соединен с вторым входом 1-го элемента ИЛИ второй группы, выход которого является 1-м адресным выходом устройства, выход 1-го элемента ИЛИ первой группы соединен с входом установки в единичное состояние 1-го триггера первой группы, выход которого соединен с прямым входом 1-го элемента И третьей группы, выход которого соединен с вторыми прямыми входами 1-х элементов И первой, четвертой и пятой групп, выход 1-го элемента И пятой группы соединен с третьим входом 1-го элемента ИЛИ второй группы, выход элемента И-ИЛИ соединен с информационным входом триггера задержки, выход которого соединен с третьими входами всех элементов И четвертой группы и является информационным выходом устройства.

2. Устройство по п. 1, о т л и ч а ю щ е е- с я тем, что блок управления содержит генератор импульсов, триггер, счетчик, элементы И и ИЛИ и элемент задержки, причем

вход запуска блока управления соединен с его четвертым выходом, с первым входом элемента ИЛИ, входом запуска генератора импульсов, входом установки в нулевое состояние счетчика, информационным входом и входом синхронизации триггера, выход которого соединен с первым входом элемента И, выход которого соединен со счетным входом счетчика, выход переполнения

которого является третьим выходом блока управления и соединен с входом элемента задержки, выход которого является пятым выходом блока управления, первый и второй выходы генератора импульсов соединены с вторыми входами соответственно элементов ИЛИ и И и является соответственно первым и вторым выходами блока управления, выход элемента ИЛИ является шестым выходом блока управления.

Изобретение относится к области вычислительной техники и может быть использовано для построения устройств сортировки, ранжировки и упорядочиЁания чисел. Цель изобретения - повышение быстродействия. Устройство содержит блок 1 управления, первую, вторую, третью, четвертую и пятую группы из п элементов И 2, 5, б, 8, 10, где п - количество сортируемых чисел, п регистров 7 сдвига, первую и вторую группы из п элементов ИЛИ 3, J1, первую и вторую группы из п триггеров 5, 9, элемент И-ИЛИ 12 и триггер № задержки. Повышение быстродействия устройства происходит за счет того, что начало поиска следующего по рангу числа совмещено с исключением из просмотра уже найденного максимального числа. 1 з.п. ф-лы, 2 ил.

(ход yuiycKet.

гедооеелчор имщлбсоъ

myOi

игге,

,элемент.

эле/wcwm, И ълдернки,

Фие.2.

элемент,

МАИ