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

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

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

На фиг.1 представлена функциональная схема устройства для сортировки чисел; на фиг.2 - схема блока сравнения; на фиг.З - схема узла сравнения; на фиг.4 - схема блока дешифра- на фиг.З - схема блока комму- .

Устройство содержит тактовый вход

1, информационные входы 2 9 вход 3 начальной установки, блок 4 сравнения, блок 5 дешифрации, блок 6 коммутации и информационные выходы 7.

Блок 4 сравнения включает

m

2.

га

узлов 8 сравнения (m-количество сор- трруемых чисел), каждый из которых содержит схему 9 сравнения, элемен- TIJ,I ИЛИ , триггеры 11,, и 11. Блок 5 дешифрации образуют 2т сум- м&торов 12 и 2т дешифраторов 13. Блок 6 коммутации содержит регистр 14 и m коммутаторов 15.

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

Перед началом сортировки чисел иКпульсом положительной полярности с, входа 3 триггеры 11,, и 11 во всех увлах 8 сравнения устанавливаются в О. Сортируемые числа с входа 2 по га каналам старшими разрядами вперед поступают на входы блоков 4 и 6 сравнения и коммутации, причем в каждом р-м такте (р-1,2,.,., n-t-1; п - разрядность сортируемых чисел) в устройство поступают g-e разряды (,2,..., n) сортируемых чисел.

Блок 4 сравнения предназначен для попарного сравнения сортируемых чисел и формирования на выходах результатов данного сравнения. Попарным сравнением каждого j-ro числа (j 1,2,..., in) с остальными числами получают информацию о количестве чисел, больших j-ro числа, и количестве чисел, меньших j-ro числа. Информация о сравнении j-ro числа Поступает на (2J-1)-K и 2j-ю группы выходов, причем каждая из групп име0

5

0

5

0

5

0

5

0

5

ет по (т-1) выходов. Количество единиц в (2j-1)-j t группе определяют количество чисел, меньших j-ro числа, а количество единиц в 2j-ft группе - количество чисел, больших j-ro числа.

Результаты сравнения с выходов блока 4 сравнения поступают на входы блока 5 дешифрации, который для каждого j-ro числа производит подсчет количества чисел меньших и больших данного числа,-и формирует на выходах блока 5 m групп сигналов управления блоком 6 коммутации. В блоке 6 коммутации комутаторы 15,,..,15т информацией о соответствующих управляющих групп входов устанавливаются в положение, при котором на их выход поступают разряды чисел согласно результатам сравнения,, т.е. на выход коммутатора 15,,- максимальное число, на выход коммутатора 15„ - следующее по величине и т.д.

Рассмотрим работу устройства в р-м такте.

С информационного входа 2 g-e разряды сортируемых чисел поступают на входы регистра 14 и на входы схем 9 сравнения всех узлов 8 сравнения, где они попарно сравниваются каждый с каждым. В зависимости от информации на первом и втором входах схем 9 сравнения на их первом и втором выходах получают следующее:

00- информация на первом входе

равна информации на втором входе;

01- информация на первом входе

меньше информации на втором

входе; i

10 - информация на первом входе

больше информации на втором

входе.

В узле 8;ксравнения (,2,..., j-1, ,2,...,i) на схеме 9 сравнения происходит сравнение g-x разрядов k-ro и j-ro чисел. Результаты сравнения данных разрядов с первого и второго выходов схемы 9 сравнения поступают на входы элементов ИЛИ 10, и 10. Триггеры 11,, и 11 в зависимости от результатов сравнения старших предыдущих разрядов k-ro и j-ro чисел могут быть установлены следующим образом:

00- k-e число равно j-му;

01- k-e число меньше j-ro; 10 - k-e число больше j-ro.

Если в одном из триггеров 11 и 112 записана единица (например, в триггере 11 ,), то она проходит через

элемент ИЛИ Ю4 и удерживает триггер 117в нулевом состоянии, а также устанавливает на выходе элемента ИЛИ 10,| сигнал 1.

Результаты сравнения с выходов блока 4 сравнения поступают на входы многовходовых сумматоров 121, 12а,.. 122(Y) блока 5 дешифрации, причем результаты сравнения j-ro числа с остальными числами поступают на мно- говходовые сумматоры и . На выходе многовходового сумматора 122- ,, получают число, указывающее, какое количество сортируемых чисел меньше j-ro числа, а на выходе многовходового сумматора 12г; -число, ука- зывающее, какое количество сортируемых чисел больше j-ro числа. Инфор- ация с выходов 1-го многовходового сумматора 12 g (, 2, ,.., 2m) поступает на входы 1-го дешифратора 13, который при нуле на входах формирует на выходах 1, а при числе на входе, равном i, на первом, втором, ..., i-m выходах - О при 1 на остальных входах.

В блоке 6 коммутации на информационные входы коммутаторов 154, 15г

15 m поступают (q-1)-e разряды

го

сортируемых чисел с выходов регистра ДА Информация с выходов дешифраторов 13j , и 134J разрешает ( 1) или запрещ ет (О) прохождение (q-l)-ro разряда j-ro числа на выходы коммутаторов 15, 154,... 15т. Так, j-e число больше двух чисел сортируемого массива и меньше трех, то информация с j-ro выхода регистра 14 поступает на выходы коммутаторов 15±,

15

5

15 . Как видно из дан- 0

ного примера, U с первых трех выходов дешифратора 13 ц } запрещает прохождение информации с j-ro информационного входа на выходы коммутаторов 151 - 153, а О с первых двух выходов дешифратора запрещает прохождение информации с j-ro инфор- мационного входа на выходы коммутаторов 15m, 15W.,.

На выходах коммутаторов 154,154,..., 15т получают (q-1)-e разряды просортиро ванных чисел, которые поступают на информационные выходы устройства 7. По переднему фронту Р-го тактового импуьса происходит запись q-x разряз

р И

15646116

дов сортируемых чисел в регистр 14 и запись результатов сравнения в триггеры 11, и 11 Ј во всех узлах 8 сравнения.

JQ jr 0 5

0

5

0

5 0

,

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

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

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

I 3. Устройство по п. 1, о т л и - ч|ающееся тем, что блок дешиф - рации содержит 2га сумматоров и 2га дешифраторов, причем входы сумматоров являются соответствующими входами блока дешифраций, выходы сумматоров соединены с входами соответствующих дешифраторов, 2т выходов блока дешифрации соединены с входом логической единицы устройства, выходы дешифраторов являются соответствующими выходами блока дешифрации,

I

4, Устройство по п. 1, отличающееся тем, что блок коммутации содержит регистр и m коммутаторов, причем j-й выход регистра (j-1,..,, m) соединен с j-м информационным вхо- дом всех коммутаторов, информационные входы регистра являются информационными входами блока коммутации, а синхровход регистра является тактовым входом блока коммутации, управ- ляющие входы коммутаторов являются

соответствующими управляющими входами блока коммутации, выходы коммутаторов являются выходами блока коммутации.

«г й/

Л% Г W/

«Uf

г

I %l W

fttUf:

№

«4jj.40t

шг/ 0 %-«/ « j/-«в;k

(г,

f/f ft

/ft

/TV/

япр

тер uif

M

ОД;

шг.

/+

Ш;

«:

Г

J k .

d- q

7//-

4 г/

f/-«d

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для параллельной сортировки массивов данных, поступающих последовательным кодом в реальном масштабе времени. Целью изобретения является повышение быстродействия. Устройство содержит тактовый вход 1, информационные входы 2, вход начальной установки 3, блок сравнения 4, блок дешифрации 5, блок коммутации 6, информационные выходы 7. Сортируемые числа поступают последовательным кодом на вход устройства старшими разрядами вперед. На выходе устройство получают отсортированный массив в последовательном коде. 3 з.п. ф-лы, 5 ил.

«чгп

J L

-шг.

5 I I % I I -%/ I I г& I I

i/fr, /I i. /I Л fi |,, j h- J

у-«Jn,

1 I f (l I I i f V 1 L I -и J I

4 ArT . f; гТ 7/гТ /Г Л Я Л ft Л

41

7Г k

J

Јгпф

//

Пш

л л