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

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

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

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

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

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

Исходный массив чисел по входам 11.1- 11 .т записывается в регистры 2. На вхдод 9 подается сигнал, в зависимости от которого устанавливается режим сортировки чисел либо в порядке убывания, либо в порядке возрастания.

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

О СП

о ч ю

00

из двух чисел данных ячеек, а в ячейку с младшим номером - меньшее (большее) из этих чисел. Следующим тактовым импульсом, подаваемым по входу 10, триггер 7 переключается в противоположное состояние и содержимое регистра 2 ячейки 1.1 будет сравниваться с содержимым регистра 2 ячейки 1.21-|( где l - номер ячейки, с содержимым регистра 2 которого сравнивалось содержимое регистра 2 ячейки 1,1 в предыдущем такте. Через, по крайней мере, m тактов в регистрах 2 будет сформирован отсортированный массив.

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

выход триггера соединен с первым информационным входом управляющего коммутатора и с управляющим входом второго коммутатора 1-й ячейки сравнения, где

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

ячейки сравнения, ,3(2m-m-1), вход

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

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

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - повышение быстродействия. Устройство содержит 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 ил. Ё

11т