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

 

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

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

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

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

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

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

Фиг.

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

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

ПРИ ГКНТ СССР (21) 4415509/24-24 (22) 25.04.88 (72) А.А.Мельник и И.Г.Цмоць (46) 15.05.90. Бюл. ¹- 18 (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 959065, кл. G 06 F 7/04, 1982.

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

¹ 1049900, кл. G 06 F 7/06, 1982. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации, предназначенных для параллельной сортировки массивов данных, поступающих последовательным кодом в реальном масштабе времени. Целью изобретения является повышение быстродействия.

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

1564611

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

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

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

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

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

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

2 у лов 8 сравнения (m-количество сорт руемых чисел), каждый из которых ( с )держит схему 9 сравнения, элементы ИЛИ 10»-10, триггеры 11» и 11 .

Блок 5 дешифрации образуют 2т сумматоров 12 и 3m дешифраторов 13.

Бпок 6 коммутации содержит регистр 14 и m коммутаторов 15.

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

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

Блок 4 сравнения предназначен для попарного сравнения сортируемых чисел и .формирования на выходах результатов данного сравнения. ПопарнЫм сравнением каждого j-го числа (j=1,2,..., ш) с остальными числами и;олучают инфармацию о количестве ч исел, больших j-ro числа, и количестве чисел, меньших j-ro числа, Информация о сравнении j-ro числа проступает íà (2j-1)-ю и 2j-ю группы выходов, причем каждая из групп имеет по (m-i) выходов. Количество единиц в (2j 1)-й группе определяют количество чисел, меньших j-ro чис5 ла, а количество единиц в 2j-й группе — количество чисел, больших j-ro числа.

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

) данного числа,.и формирует на выходах блока 5 m групп сигналов управления блоком 6 коммутации, В блоке

6 коммутации комутаторы 15,,,...15m информацией о соответствующих управляющих групп входов устанавливаются в положение, при котором на их выход поступают разряды чисел согласно результатам сравнения., т.е. на выход коммутатора 15„- максимальное число, на выход коммутатора 15 — следующее по величине и т.д.

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

00 — информация на первом входе равна информации.на втором входе;

01 — информация на первом входе меньше информации на втором входе;

40 !

10 — информация на первом входе больше информации на втором входе.

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

55 чисел могут быть установлены следующим образом:

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

01 — k-e число меньше j-го;

10 — k-e число больше j-ro.

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

II 11 fl сравнения выходы больше и меньше схемь. сравнения соединены с первыми входами соответственно первого и второго элементов ИЛИ, выходы которых соединены с информационными входами соответственно первого и второго триггеров, синхровходы которых соединены с тактовым входом блока сравнения, вход начальной установки блока сравнения соединен с первыми входами третьего и четвертого элементов ИЛИ, выходы которых соединены с входами установки в "0" соответственно первого и второго триггеров, выход первого триггера соединен с вторыми входами первого и четвертого элементов ИЛИ, выход второго триггера соединен с вторыми входами второго и третьего элементов ИЛИ, i-й вход блока срав5

156461

Если в одном из триггеров 11 и

11< записана единица (например, в триггере 11,), то она проходит через элемент ИЛИ 10 и удерживает триггер

11 в нулевом состоянии, а также устанавливает на выходе элемента ИЛИ

10 сигнал "1".

Результаты сравнения с выходов блока 4 сравнения поступают на входы многовходовых сумматоров 12,, 12<,...

12 блока 5 дешифрации, причем результаты, сравнения j-го числа с остальными числами поступают на многовходовые сумматоры 12д < и 12

На выходе многовходового сумматора

1? О „ получают число, указывающее, какое количество сортируемых чисел меньше j-ro числа, а на выходе многовходового сумматора 12, .число, ука- 20 зывающее, какое. количество сортируемых чисел больше j-го числа. Инфор- ,.ация с выходов 1-го многовходового сумматора 12 (1 =, 1, 2, ..., 2m) поступает на входы 1-го дешифратора 25

13, который при нуле на входах формирует на выходах "1", а при числе на входе, равном i на первом, втором, ..., i-m выходах — "0" при "1" на остальных входах.

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

15,„ поступают (q-1)-е разряды сбртируемых чисел с выходов регистра 14. Информация с выходов дешифраторов 13, и 13 > разрешает (1 )

35 или запрещ-ет ("0") прохождение (q-1)-ro разряда j-го числа на выходы коммутаторов 15, 15,... 15>.

Так, j-e число больше двух чисел сорти40 руемого массива и меньше трех, то информация с j-ro выхода регистра 14 поступает на выходы коммутаторов 15, 15 . .., 15 „, . Как видно из данного примера, "0" с первых трех выходов дешифратора 13 g запрещает

45 прохождение информации с j-го информационного входа на выходы коммутаторов 15 — 15, а "0" с первых двух выходов дешифратора 13 < запрещает прохождение информации с j-ro инфор50 мационного входа на выходы коммутаторов 15,„, 15 .

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

По переднему фронту Р-го тактового импуьса происходит запись q-x разря1 6 дав сортируемых чисел в регистр 14 и запись результатов сравнения в триггеры 11„ и 11 во всех узлах

8 сравнения.

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

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

15б4611 нвния соединен с первым входом -й схемы сравнения групп с i-й по (ш-1)— ю, (i + 1)-й вход блока сравнения соединен с вторыми входами всех схем сравнения 1-й группы, выходы первого и lBToporo триггеров i-х узлов сравненйя i-х групп являются выходами поразрядного сравнения блока сравнения. ( 3. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блок дешиф— рации содержит 2m сумматоров и 2m деши фраторов,. причем входы сумматоров являются соответствующими входами блока дешифраций, выходы сумматоров соединены с входами соответствующих де ифраторов„ 2m выходов блока дешифра ии соединены с входом логической ед ницы устройства, выходы дешифраторов являются соответствующими вы— ходами блока дешифрации.

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

l5646I)

С о ставит ель В . Козлов

Редактор А.Огар Техред М.Дидык

Корректор В. Кабаций

Заказ 1160 Тираж 559 Подписное

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

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

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