Устройство для упорядочения @ чисел

Устройство для упорядочения @ чисел

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении средств обработки данных. Цель изобретения расширение области применения за счет сортировки чисел большей разрядности. Устройство содержит N блоков 1 выделения наименьшего числа, (N-1) блоков 2 исключения наименьшего числа и (N-2) групп элементов ИЛИ 3. Блок выделения наименьшего числа содержит матрицу (N<SP POS="POST">.</SP>M) схем анализа. Схема анализа содержит два элемента ИЛИ и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ. Устройство построено по комбинационной схеме, не требует синхронизации, отличается простотой, однородностью структуры и высоким быстродействием. Быстродействие устройства зависит от количества одновременно обрабатываемых чисел. 1 з.п. ф-лы, 4 ил.

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

И

РЕСПУБЛИК 5ц 4 G 06 F 7/06

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

CA 3

Ю

h4

Ю лс лю

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

flQ ИЗОБР1 ЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР! (21) 427 7380/24-24 (22) 06. 07. 87 (46) 23.10.89. Бюл. Ж 39 (71) Институт технической кибернетики АН БССР (72) В.П.Загорский и И.С.Пугачев (53) 681 . 325 (088. 8) (56) Авторское свидетельство СССР

9 1203509, кл. G 06 F 7/96, 985.

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

K 1062687, кл. G 06 F 7/06, 1983 ° (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ и

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

2 ретения — расширение области применения за счет сортировки чисел большей раз ряднос ти. Устройство содержит и блоков 1 выделения наименьшего числа, (и-1) блоков 2 исключения наименьшего числа и (и-2) групп элементов ИЛИ 3. Блок выделения наименьшего числа содержит матрицу (nXm) схем анализа. Схема анализа содержит два элемента ИЛИ и элемент ИСКЛИЧАЮЦЕЕ

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

151 7020

11зобретение относится к вычисли1 тельной технике и может быть использовано для построения возрастающих (Ь, < b. ) или убывающих (Ь,? b;+,) вариацчонных рядов В = Ь; i = 1.,п ( из. массива чисел А = (а; I i = 1,п, э<данного в виде произвольных значе|пш двоичного кода.

11ель изобретения — расширение облзс гп применения устройства за счет сортировки чисел большей цазрядно сти прн "охранении высокого. быстродействия.

11» фиг. 1 показана схема устройс ва, на фиг . 2 — схема блока вьделеIll. > I<;

c:;c" а блока исключения наы еньшего

«псла; па фиг. 4 — схема группы элементов 1<1(.

Устройство содержит (фпг. 1) и б.мхов 1 выд<еления наименьшего числа,, и-1) блоков 2 исключения наи.:.:ньщсго <псла, (п-2) групп элемен<о : 1ГП1 3, группы информационных вход<ОЛ к<дон чисел Л 1, A z, ° ° °, A„, Груп пы информационных выходов кодов упоБло«1 вь<деления наименьшего чис— ла содержит и э< rn схем 4 анализа, гор;.зо1<-. альнь<е ряды которых соединены последовательно IIO линиям переноса и разр".пения. Выходы переноса последних рядах огических схем с номерами

4

/,, Zqy..., Е „ блокирования, а инфорvационнь е выходы вертикальных рядов логг<о-к гх хем 4 объединены и образуют «и< . о рмационные выходы b „, b .. „блока. Входы разрешения пер: or о столбца схем анализа соединены с входом логического нуля, а входы у< тройства переноса являются входами б:<окщ..< «<и<ля Р,, P P „входных

-<нсе-t блo:<а. Информационные входы горизо«т<1 гьных рядов логических схем

>б ра зу <гt г руппь. Л,, A Л „входов

<<Одпе< ни<сел.

Схс. <а 4 анализа состоит из двух:3-;. дового элемента ИЛИ 5, элемента

ИСК.,МЧЛ101 1ЕЕ ИЛИ 6 и трехвходового

«мента И 111 7. Два входа элемента

11.1:1 5 < б.ьединены с двумя входами элем<я га ИЛИ 7 и образуют входы перенос

Трег1<й вход элемента ИЛИ 7 соединен с первым входом элемента ИСКЛЮЧАИЦЕЕ

11.:"1 6 и информационным входом а схе" .< анализа. Второй вход элемента б и

50 выход элемента 7 образуют информационный выход Ь, а выходы элементов

ИЛИ 5 и ИСКЛЮЧАЮЦ<ЕЕ ИЛИ б являются выходами переноса и разрешения соответственно .

Блок 2 исключения наименьшего числа (фиг. 3) состоит из и элементов

ИЛИ, первые входы которых образуют входы блока, а выходы каждого i-го элемента (i E «1, и-1)) соединены с (i+1)-ми входами всех элементов с номерами от (i+1) до и. Выходами блока являются выходы элементов ИЛИ.

Устройство работает следующим образом.

Двоичные коды чисел исходного массива параллельно подаются на группы входов А „ A Л,„ так, что а,, — старший разряд, а, — младший.

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

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

Е,, Е,...„ Z „ вырабатываются уровни логического "И" на тех выходах, номер которых соответствует номеру группы входов А,,..., Л „ с наимень— шим числом. Таким образом, если во входной комбинации имеется несколько одинаковых и наименьших чисел, то на выходах Z, Z,..., Z „ также присутствует несколько уровней логического

40 нуля. В блоке 2 исключения наименьшего числа по сигналам Z Z „ ..., Z „ выбирается и передается на выход P

) в виде уровня логической единицы тот, который имеет наименьший номер j, 45 т.е. из множества одинаковых наименьших чисел выбирается одно с наименьшим номером. Сигналы Р,, Р,..., Р„ поступают на входы Р,, Р..., P „ второго блока 1 и уровень логической единицы на линии P . исключается

J наименьшее число, вьделенное в блоке

1 „из дальнейшего рассмотрения. Та1" ким образом, блок 1, вьделяет наименьшее из оставшихся чисел и т.д.

На выходах В „сформировано наибольшее число .

Для формирования ускоренного переноса исключ ающих сигналов и реди аз начены группы элементов ИЛИ 3. При этом

) 51 7020

1О

I5

55 сигнал Р1 1 одновременно действует на соответствующие входы P всех nof следующих блоков вьщеления наименьшего числа, практически одновременно исключая число A ° из анализа.

На выходах В,, В,..., В„сформирована упорядоченная последовательность кодов чисел из входного массива А ° А у,A

Блок 1 выделения наименьшего числа построен по комбинационной схеме и работает следующим образом.

Иа горизонтальные ряды схем 4 аналиха подаются двоичные коды исходных чисел так, что а. соответствует11 старшему разряду, а, — младшему. Из комбинации входных кодов анализируются только те, для которых на входах

Р; и Р присутствуют уровни логического нуля.

В блоке I использован алгоритм поразрядного сравнения чисел. Такое сравнение выполняется вертикальными рядами схем анализа. Если хотя бы в одном числе в старшем разряде присутствует "9", то этот "9" передается на выход элемента ИЛИ 7 (при наличии уровней "9" на двух других его входах) и соответственно на информа— ционный выход логической схемы 4. Так как информационные выходы вертикальных рядов схем анализа объединены, то этот уровень логического нуля блокирует все уровни логической единицы на выходах элемента ИЛИ 7 других схем анализа, на которых поданы заведомо большие числа.

При наличии такого блокирования на выходе элемента ИСКЛПЧАИГ,ЕЕ ИЛИ

6 вырабатывается уровень логической единицы, который поступает на выход разрешения данной схемы 4 анализа и, транспортируясь через все остальные схемы анализа в горизонтальном ряду, исключает данное заведомо большее число из рассмотрения, а на выходе

Ь, формируется уровень "9".

Предположим, что во втором разряде из оставшихся чисел все имеют уровни "1", тогда и на выходе Ь будет уровень ")". Если в третьем разряде хотя бы в одном из оставшихся чисел будет присутствовать уровень

"9", то на Ь будет g, а из дальнейшего рассмотрения будут исключены те числа, в которых а, = 1.

В последнем m-м вертикальном столбце анализируется последний младший разряд. Те числа иэ оставшихся, в которых а, „= 9, и есть наименьшие.

1 ю

При этом на выходах блокирования Z, соответствующим наименьшим числом выработаюгся уровни логического нуля, на остальных — логической единицы.

Предложенное решение блока I выделения наименьшего числа отличается высоким быстродействием, которое оценивается как (m+1)r и не зависит от количества чисел п. формула изобретения

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

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

1,..., n-2), выходы которых соединены с соответствующими входами разрешения (К+2) -ro блока выделения наименьшего числа, выходы элементов ИЛИ

1-й группы (1 = 1,..., n-3) соединены с соответствующими входами второй группы входов элементов ИЛИ (1+1)-й группы, выходы первого блока исключения наименьшего числа соединены с соответствующими входами второй группы входов элементов ИЛИ первой группы, группы входов блокирования первого и группы входов разрешения первого и второго блоков вьщеления наименыпего числа соединены с входом логического нуля устройства, информационные выходы р-ro блока вьщеления наимень— шего числа являются р-ми информационными выходами устройства (р = 1,..., n).

2. Устройство по и. I, о т л и ч а ю щ е е с я тем, что блок яьщеления наименьшего числа -oil,f р>лп ат-1517020

° ° ° ° ° ° ° ° ° ° ° ° ° Э ° ° рицу (num) схем анализа (n - число строк, ш — число столбцов), схема анализа содержит первый и второй элементы ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, причем первый и второй входы первого . элемента ИЛИ соответственно соединены с первым и вторым входами второго элемента ИЛИ, третий вход которого соединен с первым входом элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого соединен с вьюсодом второго элемента

ИЛИ, причем первый и второй входы первого элемента HJIH ij-й схемы анализа (i I,...,n, j 2,...,m) соот- 15 ветственно соединены с выходами первого элемента ИЛИ и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1(j-1)-й схемы анализа, в

1-м столбце (1 1..., m) выходы вто.— рых элементов ИЛИ всех схем анализа объединены по схеме монтажного И и являются выходом блокирования блока выделения наименьшего числа, 11.-й информационный выход блока выделения наименьшего числа соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ li-й схемы анализа, первый и второй входы первого элемента ИЛИ (1 )-й схемы анализа соединены соответственно с . i-м входом блокирования н i-м входом разрешения блока выделения .наименьшего числа, выходы первого элемента ИЛИ ш-й схемы анализа являются -м информационным выходом блокирования блока выделения наименьшего числа.

151 7020

Фиг. 3

Составитель В.Журавлев

Редактор О.Ирковецкая Техред Л,Олийнык Корректор В.Кабаций

Заказ 6391/51 Тираж 668 Подл исно е

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101