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

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - повышение быстродействия. Устройство содержит m (по количеству сортируемых чисел) ячеек сравнения (ЯС) 1,1+1,т, каждая из которых содержит регистр (Р) 2, коммутаторы 3, 4, блок сравнения 5. Устройство содержит также элемент НЕ 6, триггер 7,управляющий коммутатор 8, вход 9 выбора режима, тактовый вход 10, информационные входы 11.1-11.т. Исходный массив записывается в Р 2. В зависимости от состояния триггера 7, который управляет коммутаторами 3, число, находящееся в Р 2 ЯС 1.1 (,3...пл-1), сравнивается либо с числом, находящимся в Р 2 ЯС 1.1-1, либо с числом, находящимся в Р-2 ЯС 11+1. Ежетактно состояние триггера 7 меняется на противоположное. Через m тактов в Р 2 ЯС 1.1-1.ГП будет сформирован отсортированный массив. 1 ил. Ё

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

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

РЕСПУБЛИК

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

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

ПРИ ГКНТ СССР,(Й 1 1:Т1 .1::1 E iê! .,L3 1ЕЗ 1Й0 E

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4624875/24 (22) 26.12.88 (46) 30.06.91, Бюл. 1Ф 24 (72) С.Я.Перепичка и Ю.Я.Соллогуб (53) 681.325.66 (088.8) (56) Авторское свидетельство СССР

М 637810, кл. G 06 F 7/08, 1976, Авторское свидетельство СССР

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

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

Схема устройства представлена на чертеже.

Устройство содержит m (по количеству сортируемых чисел) ячеек сравнения 1.11.m, каждая из которых содержит регистр 2, коммутаторы 3,4 и блок сравнения 5, Устройство содержит также элемент HE 6, триггер 7, управляющий коммутатор 8, вход 9 выбора режима, тактовый вход 10, информационные входы 11.1 — 11.m. с

Устройство работает следующим образом., Я2 „1659998 А1 (я) 5 6 06 F 7/08

1ИЗИ3

1,1+1,m, каждая из которых содержит регистр (P) 2, коммутаторы 3, 4, блок сравнения 5. Устройство содержит также элемент

Н Е 6, триггер 7, управляющий коммутатор 8, вход 9 выбора режима, тактовый вход 10, информационные входы 11.1 — 11.m. Исходный массив записывается в Р 2. В зависимости от состояния триггера 7, который управляет коммутаторами 3, число, находящееся в P 2 ЯС 1.1(1=2,3...m-1), сравнивается либо с числом, находящимся в Р 2 ЯС 1.1-1, либо с числом, находящимся в P 2 ЯС 11+1.

Ежетактно состояние триггера 7 меняется на противоположное. Через m тактов в Р 2

ЯС 1.1 — 1 m будет сформирован отсортированный массив. 1 ил, Исходный массив чисел по входам 11.111.m записывается в регистры 2. На вхдод 9 подается сигнал. в зависимости от которого устанавливается режим сортировки чисел либо в порядке убывания, либо в порядке возрастания.

В зависимости от состояния триггера 7, который управляет коммутаторами 3, число, находящееся в регистре 2 ячейки сравнения

1.1 (1=2,3,..„m — 1), сравнивается либо с числом, находящимся в регистре 2 ячейки 1.1-1, либо с числом, находящимся в регистре 2 ячейки 1.1+1. В зависимости от выбранного режима сортировки коммутатор 8 выдает управляющие сигналы на блоки сравнения

5 четных и нечетных ячеек сравнения, поэтому по окончании сравнения в регистр 2 ячейки со старшим номером (11, 1 1-1, либо

1.1, 1.1+1) записывается большее (меньшее) .1659998

70, Составитель В. Горохов

Редактор Т, Орловская Техред М,Моргентал Корректор С. Черни

Заказ 1846 Тираж 402 Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101 из двух чисел данных ячеек, а в ячейку с младшим номером — меньшее (большее) из этих чисел. Следующим тактовым импульсом, подаваемым по входу 10, триггер 7 переключается в противоположное состояние и содержимое регистра 2 ячейки 1Л будет сравниваться с содержимым регистра 2 ячейки 1.2Н, где г - номер ячейки, с содержимым регистра 2 которого сравнивалось содержимое регистра 2 ячейки 1,l в предыдущем такте. Через, по крайней мере, m тактов в регистрах 2 будет сформирован отсортированный массив.

Формула изобретения устрдйство для сортировки чисел, содержащее m ячеек сравнения (m — количество сортируемых чисел),.причем каждая ячейка сравнения содержит регистр, блок, сравнения и первый коммутатор, причем выходы разрядов регистра соединены с ин.формационными входами первой группы

;первого коммутатора и блока сравнения, информационные входы вторых групп которых соответственно объединены, выход блока сравнения соединен с управляющим входом первого коммутатора, отл и ч а ю щ ее с я тем, что, с целью повышения быстродействия, оно содержит триггер, управляющий коммутатор и элемент НЕ, а каждая ячейка сравнения содержит второй коммутатор, причем тактовый вход устройства соединен со счетным входом триггера и через элемент НŠ— с входами разрешения записи регистров всех ячеек сравнения, установочные входы этих регистров являются информационными входами устройства, прямой выход триггера соединен с первым информационным входом управляющего коммутатора и с управляющим входом второго коммутатора I-й ячейки сравнения, где

5 i=2,4,...,m, где m=m при m-четном, и m=m-1 при m-нечетном, инверсный выход триггера соединен с вторым информационным входом управляющего коммутатора и с управляющим входом второго коммутатора J-й

10 ячейки сравнения, где j=1,3,...,(2m-m-1), вход выбора режима устройства соединен с управляющим входом управляющего коммутатора, прямой и инверсный выходы которого соединены с управляющими входами бло15 ков сравнения соответственно i-х и j-x ячеек сравнения, в каждой ячейке сравнения выходы второго коммутатора соединены с информационными входами второй группы первого коммутатора, выходы которого сое20 динены с информационными входами регистра, выходы разрядов регистра первой ячейки сравнения соединены с информационными входами первой группы второго коммутатора той же ячейки сравнения, вы25 ходы разрядов регистра k-й ячейки сравнения, где k=1,2,...,(m-1), соединены с информационными входами первой группы второго коммутатора (k+1)-й ячейки сравнения, выходы разрядов регистра

30 (k+1)-й ячейки сравнения соединены с информационными входами второй группы второго коммутатора k-й ячейки сравнения, выходы разрядов регистра m-й ячейки сравнения соединены с информационными вхо35 дами второй группы втброго коммутатора той же ячейки сравнения.