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

(5t) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

I

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

Известно устройство для сортировки чисел, содержащее m регистров, выхбды которых соединены с входами. Схем сравнения, другие входы которых подключены к выходам регистра результата, выходы схем сравнения соединены через переключатели с входами элемента ИЛИ, элементы И, триггер и узлы запрета l.

Недостатком этого устрой ства является низкое быстродействие.

Наиболее близкое по технической сущности к предлагаемому устройство, содержащее m регистров, выходы которых соединены с входами схем сравнения, другие входы которых подключены к выходам регистра результата, выходы схем сравнения соединены через переключатель с входами элемента ИЛИ, элементы И, триггер, узлы запрета и временной распределитель 21

Недостатком этого устройства является также низкое быстродействие, так как сортировка всего исходного массива чисел требует m(n+1) тактов работы устройства, где т - число, an- разност-ь сортируемых чисел.

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

«0

Указанная цель достигается тем, что в устройстве для сортировки чисел, содержащем распределитель импульсов, п регистров, п схем сравнения, группы элементов И, счетчик,

ts сумматор, регистр результата, причем выходы каждого i-ro регистра, где i 1,2,...,п, соединены с информационными входами первой группы i-ой схемы сравнения и i-ой группы

20 элементов И, выходы которых подключены к входам i-ой группы регистра результата, а каждый i-ый выход распределителя импульсов соединен 3-9 с управляющим входом элементов И i-ой группы, выходы регистра результата подключены к информационным вхо дам второй группы всех схем сравнения и к информационным входам первых выходных элементов И группы, выход каждой i-ой схемы сравнения соединен с i-ым входом счетчика, выходы которых подключены к входам первой .группы сумматора, входы второй группы которого соединены с входными шинами устройства, а выходы - с информацион ными входами вь1ходных элементов И эт рой группы элементов, управляющие входы выходных элементов И первой и второй групп подключены к управляющей шине устройства. На чертеже представлена схема предлагаемого устройства. Устройство содержит распределитель 1 импульсов, п регистров 2, п схем 3 сравнения, регистр k реэультгта, группы 5-7 элементов И, сумматор 8, счетчик 3, входы устройства 10 и 11, вход 12 управления устройства и выходы 13 и 14 устройства. Устройство работает следующим образом. В регистры 2 заносятся сортируёмые числа, регистр 4 результата уста навливается в нуль, а распределитель 1 импульсов - а исходное состояние (не показано). После этого устройство готово к сортировке чисел в порядке возрастания. Затем на вход 10 устройства подается первый тактовый сигнал, по которому появляется сигнал на,первом (верхнем) выходе распределителя 1 импульсов. При этом открывается группа 6 элементов И и число из верх него регистра 2 перезаписывается в регистр 4 результата. Это число срав нивается со всеми сортируемьв1И числами в схемах 3 сравнения, сигнал на выходе которых появляется лишь в том случае, когда числа, находящиеся в соответствующих регистрах 2, меньше числа, записанного в регистре 4 результата. Счетчик 9 подсчитывает количество схем 3 сравнения, имеющих сигнал на своем выходе. Таким образом, с выхода счетчика 9 на один из входов сумматора 8 пода ется код количества сортируемых чисел, меньших числа, записанного в р гистре 4 результата. На второй вход сумматора 8 подается код адреса об4ласти памяти, начиная с которого необходимо разместить отсортированную информацию. Тогда адрес области памяти, по которому следует записать чисо, находящееся в регистре 4 результата, определяется соотношением А N, где Ацдц - адрес области памяти, начиная с которого необходимо разместить отсортированные числа; N - число чисел, меньших числа, записанного в регистре результата. Сумматор 8 вычисляет сумму Ыцд11+ N. По сигналу на входе 12 устройства число, находящееся в регистре 4 результата, записывается в запоминающее устройство по адресу, выдаваемому сумматором 8, Второй такт работы устройства начинается с подачи второго тактов ого сигнала на вход 10 устройства. При этом появляется сигнал на втором выходе распределителя 1 импульсов, который открывает соответствующую группу 6 элементов И, вследствие чего в регистр 4 результата перезаписывается число из регистра .Дальнейшая работа устройства аналогична рассмотренному выше. После того, как устройство отработает п тактов, в запоминающем устройстве будет записан отсортированный массив чисел по адресу, заданному на входе 11 устройства. Для сортировки чисел в порЯдке убывания необходимо в регистры 2 записать инверсные значения кодов сортируемых чисел. Предлагаемое устройство обладает высоким быстродействием, так как ДЛЯ сортировки п чисел требуется п тактов работы. Формула изобретения Устройство для сортировки чисел, содержащее распределитель импульсов, п регистров, п схем сравнения, группы элементов И, счетчик, сумматор, регистр peзyльтata,. причем выходы каждого i-ro регистра, где i 1,2,...,п, соединены с информационными входами первой группы

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

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

Источники информации, принятые во внимание при экспертизе

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