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

/06 ЕТ ВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬГИЙ ОПИСАНИЕ ИЗО Н АВТОРСКОМУ СВИДЕТЕЛЬС(56) 1, Авторское свидетельство СССР В 637810, кл. С 06 Р 7/08, 1974,2, Авторское свидетельство СССР В 911513, кл. С 06 Р 7/06, 1980 (прототип).(54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее и регистров, и схем сравнения, группы элементов И, счетчик, регистр, результата, причем выходы каждого 1-го регистра,где х=1,2 и, соединены с информационными входами первой группы -й схемы сравнения и элементов И 1-й группы, выходы которых подключены к входам -й группы регистра результата, выходы которого соединены с информационными входами второй группы всех схем сравнения, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены два дешифратора, второй счетчик, регистр адреса, дополнительная схема сравнения, до полнительные группы элементов И, и триггеров, 2 п элементов ИЛИ, (и+1) элементов задержки, узел блокировки причем каждый ).-й выход первого дешифратора соединен с управляющими входами элементов И -й группы, эле- й ментов И первой -й дополнительной группы и первым входом первого д-го элемента ИЛИ, второй вход которого соединен с т-и выходом второго дешифратора с управляющими входами эле" ментов И второй д-й дополнительной группы и через 1-й элемент задержки с управляющими входами элементов И третьей -й дополнительной группы выход первого -го элемента ИЛИ подключен к входу установки в единичное состояние -го триггера, единичный выход которого соединен с д-м входом узла блокировки и первым входом-го элемента И четвертой группы, второй вход которого подключен к выходу равенства ).-й схемы сравнения, а выход- к первому входу второго -го элемента ИЛИ, второй вход которого соединен с выходом неравенства -й схемы сравнения, а выход - с 1-м входом первого счетчика, выходы которого соединены с информационными входами соответствующих элементов И пятой группы и входами первой группы дополнительной схемы сравнения, входы второй группы которой соедйнены с соответствующими входами первого дешифратора и выходами регистра адреса, входы которого подключены к выходам элементов И шестой группы, входы которых сбедифф иены с выходами второго счетчика, входы которого соединены с выходами узла блокировки, выход равенства дополнительной схемы сравнения подклюфчен к управляющим входам элементов И шестой группы, а выход неравентства - к управляюп 1 им входам элементов И пятой группы, выходы которых соединены с соответствующими входами второго дешифратора, выходы -го регистра сое-, динены с информационными входами соответствующих элементов И второй д-й дополнительной группы, входы которых соединены с мнформационнымй входами соответствующих элементов И всех первых дополнительных групп, шина тактовых импульсов устройстваподключена к синхронизирующему входу первого дейифратора и через (и+1)-й элемент задержки к синхронизирующе.му входу второго дешифратора.2. Устройство по,п,1, о т л и - ч а ю щ е е с я тем, что узел блокировки содержит (и) элементов И, причем первый вход узла блокировки ;соединен с его первым и вторым выхо 1 Ц 7 б 31Ф дами, 1-й вход узла блокировки, где 12,3 и, соединен с первым входом (1-1)-го элемента И, второй вход которого соединен с 1-м выходом узла блокировки, выход К-го элемента И где К 1,2(и 2), соединен с вторым входом (К+)-.го элемента И, выход (и"1)-го элемента И является и-м выходом узла .блокировки.Изобретение относится к автома"тике и вычислительной технике иможет быть использовано в специализированных вычислительных машинахи устройствах обработки данных для 5упорядочения произвольных массивовчисел.Известно устройство для сортировки чисел, содержащее а регистров,выходы которых соединены с входаьйю 1 Осхем сравнения, другие входы которых.подключены к выходам регистра результата, выходы схем сравнения соединены через переключатель с входом элемента ИЛИ, элементы И, триггер, 5узлы запрета и временной распределитель 11.Недостатком этого устройства является низкое быстродействие.Наиболее близким по технической 20сущности к предлагаемому являетсяустройство для .сортировки чисел,содержащее распределитель импульсов,и регистров, и схем сравнения, груп"1 пы элементов И счетчик, сумматор, 25регистр результата, причем выходыкаждого 1-го регистра, где 1=1,2и, соединены с информационными вхо дами первой группы 1 й схейы сравнения и 1"й группы элементов И, З 0выходы которых подключены к входам1-й группы регистра результата, акаждый 1-й выход распределителя импульсов соединен с управляющим входом элементов И 1-й группы, выходырегистра результатаподключены кинформационным входам второй группы.,всех схем сравнения и к информационным входам первых выходных элементовИ группы ВыхОд каждой 1 й схемы 40сравнения соединен с 1-м входом счет,чика, выходы которых подключены квходаМ первой группы сумматора, входы второй группы которого соединенны с входными шинами-устройства, а выходы - е информационными входами выходных элементов И второй группы элементов, управляющие входы выходных элементов И первойи второй групп "подключены к управляющей шине устрой ства 12Однако известное устройство имеет ряд недостатков, Во-первых, для формирования отсортированного массива чисел требуется и обращений к запоминающему устройству, что приводит к существенной зависимости от быстро. действия.и работы последнего. Во-вто" рых, сортировка всего исходного мас-. сива чисел требует и тактов сравне" ния, тогда как уже после (и) такта можно сделать заключение о месте и-го числа в отсортированном массиве.Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее и регистров, и схем сравнения, группы элементов И, счетчик, регистр результата, причем выходы каждого 1-го регистра, где 1=1,2 и, соединены с информационными входами первой группы 1"й схемы сравнения и элементов И 1-й группы, выходы которых подключены к входам 1-й группы регистра результата, выходы которого соединены с информационными входами второй группы всех схем срав" кения, введены два дешифратора, второй счетчик, регистр адреса, дополнительная схема сравнения,дополнительные группы элементов И, и триггеров, 2 и элементов. ИЛИ, (и+1) элементов задержки, узел блокировки, причем каждый .-й выход первого дешифрато1117631 При подаче первого тактового сиг-,нала на синхронизирующий вход дешифра. тора б.происходит расшифровка адре 55 са ипоявляется сигнал на первом(верхнем) выходе дешифратора. При этом устанавливаеся в единичное сос тояние верхний триггер 7, подготав ра соединен с управляющими входами элементов И 1 -й группы, элементов И первой 1 -й дополнительной группы и первым входом первого.1 -го элемен-та ИЛИ, второй вход которого соединен с 1 -м выходом второго дешифратора с управляющими входами элементов И второй 1 -й дополнительной груп. пы и через 1 -й элемент задержки с управляющими входами элементов И , 0тертьей 1 -й дополнительной группы, выход первого 1 -го элемента ИЛИ подключен к входу установки в единичное состояние.1 -го триггера, единич ный выход которого соединен с 1 -м 5 входом узла блокировки и первым входом 1 -го элемента И четвертой группы, второй вход которого подключен к выходу равенства 1 -й схемы сравнения, а выход - к первому входу второго 1 -го элемента ИЛИ, второй вход которого соединен с выходом неравенства 1 -й схемы сравнения, а выход " с 1-м входом первого счетчиКа, выходы которого соединены с информационными входами соответствующих элементов И пятой группы и входами первой группы дополнительной схемы сравнения, входы второй группы которой соединены с соответствующими входами первого30 дешифратора и выходами регистра адреса, входы которого подключены к выходам элементов И шестой группы, входы которых соединены с входами второго счетчика, входы которого соединены с выходами узла блокировки, выход равенства дополнительной схемы сравнения подключены к управляющим входам элементов И шестой группы, а выход неравенства - к управляющим входам элементов И пятой группы, выходы которых соединены с соответствующими входами второго дешифрато ра, выходы 1-го регистра соединены с информационными входами соответствующих элементов И второй 1 -й дополнительной группы, выходы которых соединены с информационными входами соответствующих элементов И всех пер" вых дополнительных групп, шина тактовых импульсов устройства подключена к синхронизирующему входу первого дешифратора и через (и+1)-й элемент задержки к синхронизирующему входу второго дешифратора.Узел блокировки содержит (и) элементов И, причем первый вход узла блокировки соединен с его первым и вторым выходами, 1 -й вход узла бло 4скировки, где 1 =2,3,п, соединенс первым входом (1-1)го элемента И,второй вход которого соединен с-мвыходом узла блокировки, выход К-гоэлемента И, где =1,2 (и) сое"динен с вторым входом (111)-го элемента И, выход (и)-го элемента Иявляется-м выходом узла блокировки,На фиг, представлена блок-схемаустройства; на фиг2 - схема узлаблокировки.Устройство содержит П регистров 1,схем 2 сравнения, группу 3 элемен 1,тов И, счетчик 4, регистр 5 результата, дешифраторы 6 и 7, счетчик 8, регистр 9 адреса, дополнительную схемуО сравнения, группы 1-16 элементов И,и тригерров 17 по я элементов ИЛИ 18и 19, И элементов 20 задержки, узел21 блокировки, элемент 22 задержки,шину тактовых импульсов 23 устройства. Узел 21 блокировки содержит элементы И 24.Сигнал "меньше" на выходе схемы 2сравнения появляется в том случае,если число в регистре 1 меньше числа, записанного в регистр 5 результата, и "равно" на выходе в том случае,если числа равны.Триггер 17 решает двойственнуюзадачу. Установленный в единичноесостояние, он показывает, что,данное число уже участвовало в сравнении, а также вместе с элементами И14 и ИЛИ 19 обеспечивает правильноеформирование отсортированного массива при наличии одинаковых чисел,Регистр 9 адреса предназначендля хранения адреса числа в исходноммассиве, сравниваемого в текущем такте со всеми.Устройство работает следующим образом.В регистр 1 заносят сортируемыечисла, регистр 5 результата, триггеры17 устанавливаются в нуль, регистр 9.адреса в единичное состояние (не по"казано), После этого устро;"1 ство готово к сортировке чисел в порядкевозрастания.ливаются элементы И 11 и открываетсягруппа элементов И Э. Число из верхнего регистра 1 перезаписывается врегистр 5 результата и сравниваетсясо всеми сортируемыми числами в схемах 2 сравнения. Счетчик 4 подсчиты-.вает количество схем сравнения,имеющих сигнал на своем выходеТа-,ким образом определяется истинныйадрес данного числа в отсортирован" 0ном массиве.В схеме 10 сравненияпроисходит его сравнение с адресомчисла в исходном массиве.При неравенстве адресов сигналапоявляется на инверсном выходе схемы 1 О, по которому открываются элементы И 5 и код с выхода счетчикапоступает на дешифратор 7,на синхронизирующий вход которого подается задержанный в элементе 22 задержки20управляющий сигнал. При этом на выходе дешифратора 7, соответствующемистинному адерсу, появляется сигнал,по которому устанавливается в единичное состояние соответствующий 25триггер 17, открывается группа элементов И 12 и число нз этого регистразаписывается в верхний регистр 1,По задержанному в элементе 20. задержки сигналу число регистра 5 результата записывается на свое место в отсортированном массиве чисел. Таким образом, числа меняют"ся местами, изменение содержимогорегистра 9 адреса не происходит.Параллельно с определением истинного адреса числа в счетчике 4 подготавливается адрес следующего попорядку числа, не участвовавшего ещев сравнении. Нулевой сигнал с бли 40жайшего по порядку триггера 17, поступая на соответствующий элемент И24 узла 21 блокировки, блокирует работу последующих. Тогда на счетчик8 с выходов узла 21 поступает толькораздвоенный единичный сигнал с пер 1 вого триггера 17. Счетчик 8 подсчитывает количество единичных сигналов.При равенстве значений счетчика 4и регистра 9 адреса появляется сиг"иал на прямом выходе схемы 1 О сравнения, по которому открываются элементы И 16 и в регистр 9 адреса сосчетчика 8 записывается адрес следующего подлежащего проверке числа.Хотя на синхронизирующий вход дешиФратора 7 поступает управляющий сигнал, нулевые уровни на его входек выработке выходных сигналов не приводят,Второй такт работы устройства начинается с подачи второго тактовогосигнала на вход 23 устройства. Приэтом появляется сигнал на выходедешиФратора 6, соответствующий со"держимому регистра 9, по которомуоткрывается соответствующая группаэлементов И 3, вследствие чего врегистр 5 результата перезаписывается число из регистра 1. Дальнейшаяработа устройства аналогична рассмот.ренному вьпце,После того, как устройство отработает (и) тактов в регистрах 1,начиная с первого. находится отсортированный массив чисел, так как положение и -го числа однозначно соответствует его истинному адресу.Далее по внешнему запросу числа выводятся из устройства.Для сортировки чисел в порядкеубывания необходимо в регистры 1записать известные значения кодовсортируемых чисел.Использование предлагаемого устройства позволяет повысить егобыстродействие на один такт; Формирование сортировочного массива чисел происходит независимо, без после"тактовых обращений к запоминающемуустройству, что позволяет потом вывести массив, за один сеанс обмена,11117 б 31 едактор ЕЛушннков аказ 7221/ ал ППП "Патент", г.Ужгород, ул,Проектная, 4 ВНИИПИ Государс по делам изоб113035,Москва, Ж" оставитель Е.Ивановаехред СЛегеза . Корректор: С, Черни Тираж б 98 Подписиенного комитета СССРтеннй и открытий