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

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее п регистров, п схем сравнения, группы элементов И, счетчик , регистр, результата, причем выходы каждого i-ro регистра, где ,2... п, соединены с информационными входами первой группы i-и схемы сравнения и элементов И i-й группы, выходы которых подключены к входам i-й группы регистра результата, выходы которого соединены с информационными входами второй группы всех схем сравнения , отличающееся тем, что, с целью повышения быстродействия , в него введены два дешифратора , второй счетчик, регистр адреса, дополнительная схема сравнения, до полнительные группы элементов И, п триггеров, 2п элементов ИЛИ, (п+1) элементов задержки, узел блокировки причем каждый i-й выход первого дешифратора соединен с управляющими входами элементов И i-й группы, эле-и ментов И первой i-й дополнительной группы и первым входом первого i-ro элемента ИЛИ, второй вход которого соединен с i-м выходом второго дешифратора с управляющими входами элементов И второй i-й дополнительной группы и через i-й элемент задержки с управляющими входами элементов И третьей i-й дополнительной группы, выход первого i-ro элемента ИЛИ подключен к входу установки в единичное состояние i-ro триггера, единичный выход которого соединен с i-M входом узла блокировки и первым входом i-ro элемента И четвертой группы, второй вход которого подключен к выходу равенства i-й схемы сравнения , а выход - к первому входу второго i-ro элемента ИЛИ, второй вход которого соединен с выходом неравенства i-й схемы сравнения, а выход с i-M входом первого счетчика, выходы которого соединены с информационнымивходами соответствующих элементов И пятой группы и входами первой группы дополнительной схемы сравнения, входы второй группы которой соеданены с соответствующими входами первого дешифратора и выходами регистра адреса, входы которо го подключенц к выходам элементов И шестой группы, входы Kotopbix сйеди нены с выходами второго счетчика, входы которого соединены с выхода ми узла блокировки, выход равенства а &о дополнительной схемы сравнение подклю чен к управляющим входам элементов И шестой г руппы, а выход неравентства к управляюп4им входам элементов И пятой группы, выходы которых соединены с соответствующими входами второго дешифратора , выходы i-ro регистра соединены с информационными входами . соответствующих элементов И второй i-й дополнительной группы, ходы которых соединеЕШ с -информационными входами соответствуювснх элементов И всех первых дополнительных групп, шина такто вых импульсов устройства

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

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

РЕСПУБЛИК

09) (11):

3/З) С 6 7/06

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

fl0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3596552/18-24 (22) 30.05.83 (46) 07.10.84. Бюл.11 - 37 (72) И.Б.Мичков ,(53) 681.325.5(088.8) (56) I. Авторское свидетельство СССР

Ф 637810, кл. G 06 F 7/08, 1974.

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

Ф 911513, кл. G 06 F 7/06, 1980 (прототип). (54)(57) .УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ, содержащее и регистров, и схем сравнения, группы элементов И, счетчик, ре нстр результата, причем выходы каждого i-го регистра,где i-=1,2... и, соединены с информационными входами первой группы i-й схемы сравнения и элементов И i-й группы, выходы которых подключены к входам i-й группы регистра результата, выходы которого соединены с информационными входами второй группы всех схем сравнения, о т л и ч а ю щ е е с я тем, / что, с целью повьппения быстродействия, в него введены два дешифратора, второй счетчик, регистр адреса, дополнительная схема сравнения, до полнительные группы элементов И, и триггеров, 2п элементов ИЛИ, (и+1) элементов задержки, узел блокировки причем каждый i-й выход первого дешифратора соединен с управляющими входами элементов И i-й группы, эле- и ментов И первой i-й дополнительной группы и первым входом первого i-ro элемента ИЛИ, второй вход которого соединен с i-и выходом второго дешифратора с управляющими входами эле" ментов И второй i-й дополнительной группы и через i-й элемент задержки с управляющими входами элементов И третьей -й дополнительной группы„ выход первого i-го элемента ИЛИ подключен к входу установки в единичное . состояние i-ro триггера, единичный выход которого соединен с i-м входом узла блокировки и первым входом

i-ro элемента И четвертой группы, второй вход которого подключен к выходу равенства i-й схемы сравнения, а выход - к первому входу второго i-го элемента ИЛИ, второй вход которого соединен с выходом неравенства i-й схемы сравнения, а выход— с i-H входом первого счетчика, выходы которого соединены с информационными входами соответствующих элементов И пятой группы и входами первой группы дополнительной схемы сравнения, входы второй группы которой соедйнены с соответствующими входами первого дешифратора и выхо- 1 дами регистра адреса, входы котороФ го подключены к выходам элементов И шестой группы, входы которых сбеди=" иены с выходами второго счетчика, входы которого соединены с выходами узла блокировки, выход равенства дополнительной схемы сравнения подклю° чек к управляющим входам элементов И шестой руппы, а выход неравентства— к управляюп1им входам элементов И пятой группы, выходы которых соединены с соответствующими входами второго дешифратора, выходы i-ro регистра сое-, е динены с информационными входами соответствующих элементов И второй

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

2. Устройство по,п.l, о т л и— ч а ю щ е е с я тем, что узел блокировки содержит (n-1} элементов И, причем первый вход узла блокировки

:;соединен с его первым и вторым выхо1 Ц 7á31

Ф дами, j-й вход узла блокировки, где ) 2,3... n, соединен с первым входом (j-1)-го элемента И, второй вход которого соединен с )-м выходом узла блокировки, выход -ro элемента И где K 1,2. ° ° (n 2), соединен с вторым входом (K+1)-.ãî элемента И, выход (n"1)-го элемента И является и-м выходом узла .блокировки.

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

Известно устройство для сортировки чисел, содержащее ш регистров, выходы которых соединены с входаьй 1О схем сравнения, другие входы которых .подключены к выходам регистра результата, выходы схем сравнения соединены через переключатель с входом элемента ИЛИ, элементы И, триггер, l5 узлы запрета и временной распределитель Я .

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

Наиболее близким по технической 20 сущности к предлагаемому является устройство для .сортировки чисел, содержащее распределитель импульсов, и регистров, п схем сравнения, груп"

1пы элементов И> счетчик, сумматор, 25 регистр результата, причем выходы каждого 1-го регистра, где 1=1,2,..., п соединены с информационными вхо дами первой группы 1 и схейы сравнения и 1"й группы элементов И, выходы которых подключены к входам

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

И группы ВыхОД каждой 1 Й схемы 40 сравнения соединен с 1-м входом счет, чика, выходы которых подключены к входаМ первой группы сумматора, входы второй группы которого соединенны с входными. шинами-устройства, а выходы - e информационными входами выходных элементов И второй группы элементов, управляющие входы выходных элементов И первой и второй групп

"подключены к управляющей шине устрой. ства )2) ..

Однако известное устройство имеет ряд недостатков. Во-первых, для формирования отсортированного массива чисел требуется и обращений к запоминающему устройству, что приводит к существенной зависимости от быстро. действия и работы последнего. Во-вто" рых, сортировка всего исходного массива чисел требует п тактов сравне" ния, тогда как уже после (и-1) такта можно сделать заключение о месте и-го числа в отсортированном массиве.

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

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

i=1,2,...,n, соединены с информационными входами первой группы i-й схемы сравнения и элементов И i-й группы, выходы которых подключены к входам

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

При подаче первого тактового сиг-, нала на синхронизирующий вход дешифра. тора б.происходит расшифровка адре55 са и появляется сигнал на первом (верхнем) выходе дешифратора. При этом устанавливае ся в единичное сос. тояние верхний триггер !7, подготавра соединен с управляющими входами элементов И 1 -й группы, элементов

И первой 1 -й дополнительной группы

I и первым входом первого.1 --го элемен- ° та ИЛИ, второй вход которого соединен с 1 -м выходом второго дешифратора с управляющими входами элементов И второй 1 -й дополнительной груп.

I пы и через q -й элемент задержки с управляющими входами элементов И, 10

I тертьей 1 -й дополнительной группы, выход первого j -ro элемента ИЛИ подключен к входу установки в единичное состояние.) --ro триггера, единичФ ный выход которого соединен с 1 -м !5 входом узла блокировки и первым входом < --го элемента И четвертой группы, второй вход которого подключен к выходу равенства 1 -й схемы сравнения, а выход — к первому входу второго 1 --го элемента ИЛИ, второй вход которого соединен с выходом неравенства 1 -й схемы сравнения, а выход— с -м входом первого счетчиКа, выходы которого соединены с информационны- 5 ми входами соответствующих элементов

И пятой группы и входами первой группы дополнительной схемы сравнения, входы второй группы которой соединены с соответствующими входами первого

30 дешифратора и выходами регистра адреса, входы которого подключены к выходам элементов И шестой группы, входы которых соединены с входами второго счетчика, входы которого соединены с выходами узла блокировки, выход равенства дополнительной схемы сравнения подключены к управляющим входам элементов И шестой группы, а выход неравенства — к управляющим входам элементов И пятой группы, выходы которых соединены с соответствующими входами второго дешифрато ра, выходы 1-го регистра соединены с информационными входами соответствующих элементов И второй 1 -й до- 45 полнительной группы, выходы которых соединены с информационными входами соответствующих элементов И всех первых дополнительных групп, шина тактовых и пульсов устройства подключена 50 к синхронизирующему входу первого дешифратора и через (n+l)-й элемент задержки к синхронизирующему входу второго дешифратора.

Узел блокировки содержит (n-1) элементов И, причем первый вход узла блокировки соединен с его первым и вторым выходами, 1 --й вход узла бло

4 с кировки,. где 1 =2,3,....,n, соединен с первым входом (j-1) го элемента И, второй вход которого соединен с -м выходом узла блокировки, выход К-го элемента И, где =1,2,..., (и-2)1 сое" динен с вторым входом (KII)-го элемента И, выход (и-1)-ro элемента И является 11 -м выходом узла блокировки, На фиг.l представлена блок-схема устройства; на фиг ° 2 — схема узла блокировки..

Устройство содержит 11 регистров 1,,схем 2 сравнения, группу 3 элеменt ,тов И, счетчик 4, регистр 5 результата, дешифраторы 6 и 7, счетчик 8, регистр 9 адреса, дополнительную схему !

О сравнения, группы 11-16 элементов И, и тригерров 17 по я! элементов ИЛИ 18 и 19, И элементов 20 задержки, узел

21 блокировки, элемент 22 задержки, шину тактовых импульсов 23 устройства. Узел 21 блокировки содержит элементы И 24.

Сигнал "меньше" на выходе схемы 2 сравнения появляется в том случае, если число в регистре 1 меньше числа, записанного в регистр 5 результата, и "равно" на выходе в том случае, если числа равны.

Триггер 17 решает двойственную задачу. Установленный в единичное состояние, он показывает, что,данное число уже участвовало в сравнении, а также вместе с элементами И

14 и ИЛИ 19 обеспечивает правильное формирование отсортированного массива при наличии одинаковых чисел.

Регистр 9 адреса предназначен для хранения адреса числа в исходном массиве, сравниваемого в текущем такте со всеми.

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

В регистр I заносят сортируемые числа, регистр 5 результата, триггеры

l7 устанавливаются в нуль, регистр 9. адреса в единичное состояние (не показано). После этого устройство готово к сортировке чисел в порядке возрастания.

1147631 ливаются элементы И ll и открывается группа элементов И Э. Число из верхнего регистра 1 перезаписывается в регистр 5 результата и сравнивается со всеми сортируемыми числами в схе- % мах 2 сравнения. Счетчик 4 подсчиты-. вает количество схем сравнения, имеющих сигнал на своем выходе..Та-, ким образом определяется истинный адрес данного числа в отсортирован" !0 ном массиве. В схеме 10 сравнения происходит его сравнение с адресом числа в исходном массиве.

При неравенстве адресов сигнала появляется на инверсном выходе схе- 15 мы 10 по которому открываются элементы И L5 и код с выхода счетчика

Д поступает на дешифратор 7,на синхронизирующий вход которого подается задержанный в элементе 22 задержки 20 управляющий сигнал. При этом на выходе дешифратора 7, соответствующем истинному адерсу, появляется сигнал, по которому устанавливается в единичное состояние соответствующий 2 триггер 17, открывается группа элементов И 12 и число нз этого регистра записывается в верхний регистр 1.

По задержанному в элементе 20. задержки сигналу число регистра 5 ре- 30 зультата записывается на свое место в отсортированном массиве чисел. Таким образом, числа меняют" ся местами, изменение содержимого регистра 9 адреса не происходит.

Параллельно с определением истинного адреса числа в счетчике 4 подготавливается адрес следующего по порядку числа, не участвовавшего еще в сравнении. Нулевой сигнал с бли40 жайшего по порядку триггера 17, поступая на соответствующий элемент И

24 узла 21 блокировки, блокирует работу последующих. Тогда на счетчик

8 с выходов узла 21 поступает только 4> раздвоенный единичный сигнал с пер1 вого триггера 17. Счетчик 8 подсчитывает количество единичных сигналов.

При равенстве значений счетчика 4 и регистра 9 адреса появляется сигнал на прямом выходе схемы 10 сравнения, по которому открываются элементы И 16 и в регистр 9 адреса со счетчика 8 записывается адрес следующего подлежащего проверке числа.

Хотя на синхронизирующий вход дешифратора 7 поступает управляющий cHI нал, нулевые уровни íà его входе к выработке выходных сигналов не приводят, Второй такт работы устройства начинается с подачи второго тактового сигнала на вход 23 устройства. При этом появляется сигнал на выходе дешифратора 6, соответствующий содержимому регистра 9, по которому открывается соответствующая группа элементов И 3, вследствие чего в регистр 5 результата перезаписывается число из регистра 1. Дальнейшая работа устройства аналогична рассмотренному выше.

После того, как устройство отработает (n-1) тактов,, в регистрах 1, начиная с первого. находится отсортированный массив чисел, так как положение n --го числа однозначно соответствует его истинному адресу.

Далее по внешнему запросу числа выводятся из устройства.

Для сортировки чисел в порядке убывания необходимо в регистры l записать известные значения кодов сортируемых чисел.

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

1117631

1117631.

ФР2. 2

Составитель Е.Иванова

Техред С.Легеза . Корректор.:С,Черни

Редактор Е.31ушннкова

Подписное

Филйал ППП. "Патент", r.Óæãoðîä, ул,Проектная, 4

Заказ 7221/33 Тираж 698

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

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