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

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

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 7/06

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4780946/24 (22) 09.01.90 (46) 15.12.92. Бюл. % 46 (71) Институт кибернетики им.В.М.Глушкова (72) В.А.Вышинский и Н.Б.Фесенко (56) Авторское свидетельство СССР

М 826339, кл. G 06 F 7/06, 1979.

Авторское свидетельство СССР

М 1441384, кл. G 06 F 7/06, 1986, (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ (57) Изобретение относится к области вычислительной техники и может быть использовано для построения устройств сортировки, Ы,, 1781680 А1 ранжировки и упорядочивания чисел. Цель изобретения — повышение быстродействия.

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

1781680

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

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

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

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

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

m-разрядного кольцевого регистра сдвига (1 = 1, .„, n) соединен с управляющим входом

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

m-разрядного кольцевого регистра сдвига соединен с первым входом первого элемента И.!-го элемента 2И-ИЛИ, выход которого соединен с входом установки в "0" 1-го триггера первой группы, прямой выход которого подключен к входу установки в "0" i-ro триггера второй группы и входу установки в единичное состояние 1-ro триггера третьей группы, прямой выход которого является 1-м адресным выходом устройства и соединен с

45 информационным входом i-го элемента И::=" управляющего элемента И-ИЛИ, выход ко- 50 торого является выходом отсортированного числа устройства и соединен с вторым входом второго элемента И 1-ro элемента 2ИИЛИ, вход запуска устройства подключен к. первым входам всех элементов ИЛИ, вхо- 55 дам установки s единичное состояние всех триггеров второй группы и входу запуска блока управления, первый и второй выходы которого подключены к входам управления сдвигам всех m-разрядных регистров сдвига, а третий выход соединен с первыми входами всех элементов И, всех вторых элементов И, всех элементов 2И-ИЛИ, выход 1-ro элемента И подключен к второму входу I-ro элемента ИЛИ, выход которого соединен с входом установки в единичное состояние

I-ro триггера первой группы, инверсный выход которого подключен к входу установки в

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

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

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

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

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

Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее блок управления, элемент И-ИЛИ, и регистров сдвига, где и — количество сорти1781680

15

25

35

45

55 руемых чисел, первую и вторую группы из и триггеров, первую группу из и элементов И, первую группу из и элементов ИЛИ и триггер задержки, причем информационные входы регистров сдвига являются информационными входами устройства, вход начальной установки устройства соединен с входом запуска блока управления, первый и второй выходы которого соединены с входами управления сдвигом всех регистров сдвига, третий выход блока управления соединен с первыми прямыми входами всех элементов И первой группы, четвертый выход блока управления соединен с первыми входами всех элементов ИЛИ первой группы, пятый выход блока управления соединен с входами синхронизации всех триггеров первой группы, шестой выход блока управления соединен с входом синхронизации триггера задержки, прямой выход старшего разряда I-ro регистра сдвига (1 - 1, 2, ..., n) соединен с первым входом I-ro элемента И элемента И-ИЛИ, второй вход которого подключен к i-му адресному выходу устройства, выход 1-го элемента.И первой группы соединен с вторым входом I-ro элемента ИЛИ первой группы, выход которого соединен с входом установки в единичное состояние i-го триггера второй группы, выход которого соединен с входом установки в нулевое состояние i-го триггера первой группы, введены вторая группа из и элементов ИЛИ и четыре группы из и элементов И каждая, причем второй выход блока управления соединен с входами синхронизации всех триггеров второй группы, четвертый выход блока управления соединен с первыми входами всех элементов ИЛИ второй группы, пятый выход блока управления соединен с прямыми входами всех элементов

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

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

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

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

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

5". Сигнал с выхода 15 устройства управления прототипа поступает через каждые m тактов работы, сигнал с выхода 12 поступает. в следующем такте, уже после сигнала с выхода 15, что также выполняется с использованием счетчика, 8 результате по истечении (m+1) тгктов работы устройства прототипа будет выполнена операция выбора максимального числа из n m-разрядных чисел, а в (m+1) также его адрес будет считан с выхода 18 устройства. При этом нужноучесть начальную установ- . ку, которая также вносит задержку., Для схемы прототипа время выполнения операции сортировки т,р массива из n m-разрядных чисел определяется выражением

1781680

T n p (T 1 + <2) (m + 1 ) и + (гн о + T 1 + <2) (1) где в последних скобках учитывается начальная установка устройства прототипа в исходное состояние.

B схеме заявленного устройства повышение быстродействия достигается за счет того, что начало поиска следующего по рангу числа совмещено с исключением из просмотра уже найденного максимального числа. Кроме того, установка устройства в исходное состояние для работы совмещена с началом предварительного просмотра старших разрядов чисел. Для схемы заявленного устройства время выполнения операции сортировки т,у массива из n mразрядных чисел определяется выражением; зу (г1 + т2) m и + тно (2) где т =т =тг(по длительности).

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

ri m-ro такта, а его адрес — во время действия синхроимпульса t2 m-го такта. В схеме прототипа эти результаты выдаются одновременно, причем уже после (m+1}-го такта, на котором они получены, усложняет выдачу результата при ограничении на число контактных площадок, Из сравнения выражений (1) и (2) определим выигрыш в быстродействии Лт;

A z = напр Гзу (71 + 72} (и + 1) Способность заявленного устройства выполнять этап операции сортировки за m тактов позволяет организовать работу в конвейерном режиме с устройствами, осуществляющими процесс обработки информации эа время, пропорциональное разрядности операндов.

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

При этом применяется гибридный метод конструирования и изготовления БИС с использованием универсальных вентильных матриц типа 18068П1 (КМОП).

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

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

Т,о., заявленный объект проявляет новое техническое свойство, не присущее известным объектам и прототипу, следовательно, заявленное техническое решение соответствует критерию "Существенные отличия".

На фиг. 1 изображено устройство для сортировки чисел; на фиг. 2 — блок управления, Устройство содержит управляющий 1 и информационные 2 входы, блок 3 управления, его выходы 4, 5, 6, 7, 8, 9, регистры 10, группы элементов И 11, 12, tpynny элементов ИЛИ 13, группы триггеров 14, 15, группы элементов И 16, 17, 18, группу элементов

ИЛИ 19, адресные входы 20, элемент И-ИЛИ

21, триггер 22 задержки, информационный выход 23. Блок 3 управления содержит генератор 24 синхроимпульсов, элемент ИЛИ

25, триггер 26, элемент И 27, счетчик 28, элемент задержки 29.

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

Триггер 26 блока управления и триггер

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

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

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

1781680

30 триггеров 14, 15 первой и второй групп в единичное состояние. Под действием этого сигнала производится запуск генератора 24 импульсов и сброс в начальное состояние счетчика 28, Элементом И-ИЛИ 21 произво35 дится сравнение значений старших разрядов регистров 10 с единичным значением сигнала запуска, прошедшего через I-e элементы ИЛИ 19t второй группы на первые входы I-x элементов И элемента И-ИЛИ 21.

Если хотя бы в одном регистре в старшем

40 разряде записано единичное значение, то триггер 22 задержки установится в единичное состояние.

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

После окончания действия сигнала запуска 1, генератор 24 импульсов блока 3 управления начинает вырабатывать синхроимпульсы r> и гг. С прямого выхода тригге- 50 ра 26 на первом входе элемента И 27 блока

3 управления будет поддерживаться единичное значение в течение времени выполнения устройством ойерации сортировки чисел. В результате счетчик 28 будет считать 55 единичные значения синхроимпульсов х1 и через каждые m тактов работы устройства выдавать единичный синхроимпульс tz, совпадающий с синхроимпульсом rz, все числа находятся в равных условиях. В случае, если часть чисел в рассматриваемом разряде имеют единичное, а часть — нулевое значение, то, при рассмотрении следующего меньшего по весу разряда, имевшая ну- 5 левое значение часть чисел исключается.

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

nxm тактов работы устройства (n этапов сортировки), В исходном состоянии в регистры 10>-10п любым известным способом записывается массив сортируемых чисел (п m-разрядных 25 чисел), После этого на вход блока 3 управления поступает единичный сигнал запуска 1.

Длительность сигнала запуска 1 выбирается достаточной для установки триггера 26, Пусть в регистры 10 -10ï сдвига записаны числа А = (àtàz...Bm}, В = (btbz."bm} ..., С =-(с1сг„.с }, Рассмотрим работу устройства для сортировки чисел. Допустим, что старшие разряды а1, Ь1, ..., c> равны единице, т,е. a< = Ь1 = ...

= c> = 1. Тогда перед началом работы устройства триггер 22 задержки будет находиться в единичном состоянии.

Начинается первый. этап сортировки чисел. Его результатом будет найденное максимальное число из массива. B момент действия синхроимпульса r, l-e элементы И

12t четвертой группы сформируют нулевые сигналы и t-e триггеры 14t второй группы останутся в единичном состоянии, а с информационного выхода 23 снимется значение старшего разряда максимального числа, равного единице. Одновременно в регистрах 10 информация сдвинется на один разряд. Допустим, что разряды аг, bz, „., сг равны нулю, т,е. аг = Ьг = ... = сг = О. В момент действия синхроимпульса тг элемент И-ИЛИ 21 сформирует нулевой сигнал, значение которого запишется в триггер 22 задержки. Закончен первый такт работы устройства.

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

t> второго такта I å элементы И 12 четвертой группы сформирует нулевые сигналы и I-e триггеры 14 второй группы останутся в единичном состоянии, а с информационного выхода снимется нулевое значение, соответствующее второму разряду максимального числа. Одновременно в регистрах 10 информация сдвинется на один разряд.

Допустим, что|-е разряды bl, ..., cI равны единице, т е. bt = ... = cl = 1, а разряд at - О.

Тогда в момент действия синхроимпульса тг О-1)-ro такта работы устройства элемент

И-ИЛИ 21 сформирует единичный сигнал, который запишется в триггер 22 задержки.

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

<1 1-го такта элементы И 12г — "2n четвертой группы, соответствующие регистрам 10z-10, сформируют нулевые сигналы и триггеры

14г 14п второй группы останутся в единичном состоянии, Элемент И 121 четвертой группы, соответствующий первому регистру

10 сформирует единичный сигнал, под действием которого первый триггер 141 второй группы сбросится в нулевое состояние.

Сброс первого триггера 14> второй группы в нулевое состояние говорит в данном случае о том, что число, находящееся в первом регистре 101 является меньшим по величине, нежели числа в других регистрах 10z — 10п, соответствующие которым триггеры 14z-14П второй группы сохранили единичное состо1781680

12 яние. Нулевой сигнал с прямого выхода триггера 141 второй группы, блокируя вход первого элемента И элемента И-ИЛИ 21, исключает из поиска максимального числа число, записанное в первом регистре 101. 5

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

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

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

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

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

rz в-го такта с адресного выхода 20 будет считан адрес максимального числа первого З0 этапа сортировки (инверсное значение адреса). Одновременно счетчик 28 выдаст сийхрримпульс rq, совпадающий с синхроимпульсом т2 . Под действием синхроимпульса т2 информация с прямых выходов З5 триггеров 14 второй группы будет принята на входы установки в нуль триггеров 15 первой группы. При этом каждый триггер 15 первой группы установится в состояние, противоположное состоянию соответствую- 40 щего триггера 14 второй группы. После rn первых сдвигов в регистрах 10 -10ï в единичном состоянии будут оставаться триггеры 14 второй группы, в соответствующих регистрах 10 которых находится максималь- 45 ное число для данного этапа сортировки.

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

14l второй группы через i-й элемент И 18 пятой группы.

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

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

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

Если на прямой вход i-го элемента И 16 второй группы поступает синхроимпульс

tz, то на первый вход l ro элемента И элемента И-ИЛИ 21 поступает единичный сигнал для участия в новом этапе сортировки.

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

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

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

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

1781680

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

Если 1-й элемент И 12 четвертой группы сформирует нулевой сигнал, то, под дейстI вием синхроимпульса т (это задержанный

I на полтакта синхроимпульс t2) и единичного сигнала с выхода соответствующего 1-го триггера 15 первой группы произойдет восстановление единичного состояния i-ro триггера 14 второй группы, Для исключения чисел из процесса сортировки достаточно обнуления соответствующего триггера 15 первой группы, которое производится в конце каждого этапа сортировки. Нулевой сигнал блокировки с выхода этого обнуленного триггера 15 первой группы с помощью соответствующих элемента И

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

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

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

Формула изобретения

1. Устройство для сортировки чисел, cn-

5 держащее блок управления, элемент ИИЛИ, прегистров сдвига,,где n — количество сортируемых чисел, первую и вторую группы из и триггеров;:первую группу из и элементов И, первую группу из и элементов

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

15 первый и второй выходы которого соединены с входами управления сдвигом всех регистров сдвига, третий выход блока управления соединен с первыми прямыми входами всех элементов И первой группы, 20 четвертый выход — с первыми входами всех элементов ИЛИ первой группы, пятый выход — с входами синхронизации всех триггеров первой группы, шестой выход — с входом синхронизации триггера задержки, 25 прямой выход старшего разряда I-ro регист. ра сдвига (i = 1, 2, ..., n) соединен с первым входом I-го элемента И, элемента И-НЕ, второй вход которого подключен к I-му адресному выходу устройства, выход I-го

30 элемента И первой группы соединен с вторым входом I-го элемента ИЛИ первой группы, выход которого соединен с входом установки в единичное состояние I-ro триггера второй группы, выход которого соеди35 нен с входом установки в нулевое состояние

i ão триггера первой группы, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, в него введены вторая группа из п элементов ИЛИ и четыре группы из и

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

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

50 четвертой группы, выход которого соединен с инверсным входом i-го элемента И первой . группы и с входом установки в нулевое состояние 1-ro триггера второй группы, выход которого соединен с первым входом i-го эле55 мента И пятой группы и с инверсным входом

i-го элемента И второй группы, выход которого соединен с вторым входом i-го элемента ИЛИ второй группы, выход которого является I-м адресным выходом устройства, выход l-го элемента ИЛИ первой группы со1781680

15

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

CCRepct э имкуласоб .

Злежеюв

ЮФ

8хоЯ этмене Lf s® ð®рес, Фиг.2

Составитель Н.Фесенко

Техред М.Моргентвл Корректор Л.Филь

Редактор

Заказ 4275 . Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж 35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101 единен с входом установки в единичное состояние I-ro триггера первой группы, выход . которого соединен с прямым входом I-го элемента И третьей группы, выход которого соединен с вторыми прямыми входами I-x элементов И первой, четвертой и пятой групп, выход I-го элемента И пятой группы соединен с третьим входом I-ro элемента

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

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