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

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

2. Устройство по П.1, о т л и чающееся тем, что узел блокировки содержит (п-1) элементов И, причем первый вход узла блокировки {Соединен с его первым и вторым выхоМ7631

дамй, j-й вход узла блокировки, где ,3...n, соединен с первым входом (j-iO-ro элемента И, второй вход которого соединен с j-м выходом узла блокировки, выход К-го элемента Ijj, где К 1,2... (п-2), соединен С вторым входом (К+1)-го элемента И, выход (n-l)-ro элемента И является п-м выходом узла блокировки.

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее п регистров, п схем сравнения, группы элементов И, счетчик, регистр, результата, причем выходы каждого 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-й дополнительной группы, ходы которых соединеЕШ с -информационными входами соответствуювснх элементов И всех первых дополнительных групп, шина такто вых импульсов устройства

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специали ированных вычислительнБШ машинах и устройствах обработки данных для упорядочения произвольных массивов чисел. Известно устройство для сортиров ки чисел, содержащее m регистров, выходы которых соединены с входами схем сравнения, другие вхрды которы подключены к выходам регистра резул тата, выходы схем сравнения соедине ны через переключатель с входом эле мента ИЛИ, элементы И, триггер, узлы запрета и временной распределитель D3 Недостатком этого устройства является низкое быстродействие. Наиболее близким по Фехнической СУ1ЦНОСТИ к предлагаемому является устройство для сортировки чисел, содержащее распределитель импульсов п регистров, п схем сравнения, груп шы элементов И;счетчик, сумматор, регистр результата, причем выходы кайвдого i-ro регистра, где ,2,.. П, соединены с информационными входами первой группы схемы сравнения и i-й группы элементов И, выходы которых подключены к входам i-й группы регистра результата, а каждый i-й выход распределителя импульсов соединен с управляющим входом элементов И i-й группы, выходы регистра результата подключены к информационным входам второй группы .всех схем сравнения к к информацион ным входам первых выходных элементо И группы, выход каждой i-й схемы сравнения соединен с i-м входом C4e чика, выходы которых подключены к входам первой группы сумматора, вхо ды второй группы которого соединенны с входными шинами-устройства, а выходы - с информационными входами выходных элементов И второй группы элементов, управляющие входы выходных элементов И первойи второй групп 1подключены к управляющей шине устройства 2 . Однако известное устройство имеет ряд недостатков. Во-первых, для формирования отсортированного массива чисел требуется п обращений к запоминающему устройству, что приводит к существенной зависимости от быстродействия и работы последнего. Во-вторых, сортировка всего исходного массива чисел требует п тактов сравнения, тогда как уже после (п-1) такта можно сделать заключение о месте п-го числа в отсортированном массиве. Цель изобретения - повыщение быстродействия устройства. Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее п регистров, п схем сравнения, группы элементов И, счетчик, регистр результата, причем выходы каждого i-ro регистра, где ,2,..,,п, соединены с информационными входами первой группы i-й -схемы сравнения и элементов И i-й группы, выходы которых подключены к входам i-й группы регистра результата, выходы которого соединены с информационными .входами второй группы всех схем сравнения, введены два дешифратора, второй счетчик, регистр адреса, дополнительная сзсема сравнения,дополнительные группы элементов И, п триггеров, 2п элементов. ИЛИ, (п+1) элементов задержки, узел блокировки, причем каждый {.-и выход первого дешифратоpa соединён с управляющими входами элементов И 1-й группы, элементов И первой 1-и дополнительной группы и первым входом первого i-го элемен та ИЛИ, второй вход которого соединен с-1 -м выходом второго дешифратора с управляющими входами элементов И второй 1 -и дополнительной гру и 4jpe4 1 й элемент задержки с управляющими входами элементов И тертьей 1-и дополнительной группы, выход первого i-го элемента ИЛИ подключен к входу установки в единич ное состояние.1-го триггера, единичный выход которого соединен с i -м входом узла блокировки и первым входом i -го элемента И четвертой группы, второй вход которого подключен к выходу равенства i-и схемы сравнения, а выход - к первому входу второго 1 -го элемента ИЛИ, второй вход которого соединен с выходом неравенства i-и схемы сравнения, а выход с «-м входом первого счетчика, выходы которого соединены с информационн ми входами соответствующих элементо И пятой группы и входами первой груп пы дополнительной схемы сравнения, входы второй группы которой соединены с соответствующими входами первог дешифратора и выходами регистра адреса, входы которого подключены к выходам элементов И шестой группы, входы которых соединены с входами второго счетчика, входы которого сое динены с выходами узла блокировки, выход равенства дополнительной схемы сравнения подключены к управляющим входам элементов И шестой группы, а выход неравенства - к управляющим входам элементов И пятой группы, выходы которых соединены с соответствующими входами второго дещифратора, выходы 1-го регистра соединены с информационными входами соответствующих элементов И второй i -и дополннтельной группы, выходы которых соединены с информационными входами соответствующих элементов И всех пер вых дополнительных групп, шина такто вых импульсов устройства подключена к синхронизирующему входу первого дешифратора и через (п+1)-й элемент задержки к синхронизирующему входу второго дешифратора. Узел блокировки содержит (п-1) элементов И, причем первый вход узла блокировки соединен с его первым и вторым выходами, i-и вход узла бло кировки, где 2,3..,.,п, соединен с первым входом (j-I) элемента И, i второй вход которого соединен с j -м выходом узла блокировки, выход К-го элемента И, где 1,2,..., (п-2), соединен с вторым входом (kfl)-ro элемента И, выход (п-1)-го элемента И является п м выходом узла блокировки, На фиг.1 представлена блок-схема устройства; на фиг.2 - схема узла блокировки. I Устройство содержит Г) регистров 1, схем 2 сравнения, группу 3 эЛемен- тов И, счетчик 4, регистр 5 результата, дешифраторы 6 и 7, счетчик 8, -9 адреса, дополнительную схему 10 сравнения, группы 11-16 элементов И, П тригерров 17 по /fl элементов ИЛИ 18 и 19, И элементов 20 задержки, узел 21 блокировкиj элемент 22 задержки, шину тактовых импульсов 23 устройства. Узел 21 блокировки содержит эле- менты И 24. Сигнал меньше на выходе схемы 2 сравнения появляется в том случае, если число в регистре 1 меньше числа, записанного в регистр 5 результата, и равно на выходе в том случае, если числа равны. Триггер 17 решает двойственную задачу:. Установленный в единичное состояние, он показывает, что,данное число уже участвовало в сравнении, а также вместе с элёмеитами И 14 и ИЛИ 19 обеспечивает правильное формирование отсортированного массива при наличии одинаковых чисел. Регистр 9 адреса предназначен для хранения адреса числа в исходном массиве, сравниваемого в текущем такте со всеми. Устройство работает следующим образом. В регистр 1 заносят сортируемое . числа, регистр 5 результата, триггеры 17 устанавливаются в нуль, регистр 9. адреса в единичное состояние (не показано) . После этого устройство готово к сортировке чисел в порядке возрастания. При подаче первого тактового сиг- . нала на синхронизирующий вход депшфратора 6 происходит расшифровка адреса и появляется сигнай на первом (верхнем) выходе дешифратора. При этом устанавливается в бдининное состояние верхний триггер ,17, подготав

лишаются элементы И 11 и открывается группа элементов И 3. Число из верхнего регистра 1 перезаписывается в регистр 5 результата и сравнивается со всеми сортируемыми числами в схемах 2 сравнения. Счетчик 4 подсчитыг

вает количество схем сравнения, имеющих сигнал на своем выходе. ТаКИМ образом определяется истинный адрес данного числа в отсортированном массиве.В схеме 10 сравнения происходит его сравнение с адресом числа в исходном массиве.

При неравенстве адресов сигнала появляется на инверсном выходе схемы 10, по которому открываются элементы И 15 и код с выхода счетчика / поступает на дешифратор 7,на синхронизирующий вход которого подается задержанный в элементе 22 задержки управляющий сигнал. При этом на выхо.де дешифратора 7, соответствукицем истинному адерсу, появляется сигнал, по которому устанавливается в единичное состояние соответствующий триггер 17, открывается группа элементов И 12 и число из этого регистр записывается в верхний регистр 1. По задержанному в элементе 20 задержки сигналу число регистра 5 результата записывается на свое место в отсортированном массиве чисел. Таким образом, числа меняются местами, изменение содержимого регистра 9 адреса не происходит.

Параллельно с определением истинного адреса числа в счетчике 4 подготавливается адрес следующего по порядку числа, не участвовавшего еще в сравнении. Нулевой сигнал с ближайшего по порядку триггера 17, поступая на соответствующий элемент И 24 узла 21 блокировки, блокирует работу последующих. Тогда на счетчик 8 с выходов узла 21 поступает только раздвоениый единичный сигнал с пер63I«

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

Хотя на синхронизирующий вход дешифратора 7 поступает управляющий сигнал, нулевые уровни на его входе к выработке выходных сигналов не приводят.

Второй такт работы устройства начинается с подачи второго тактового сигнала на вход 23 устройства. При этом появляется сигнал на выходе дешифратора 6,;соответствующий со-.

держимому регистра 9, по которому открывается соответствующая группа элементов ИЗ, вследствие чего в, регистр 5 результата перезаписывается число из регистра 1. Дальнейшая

работа устройства аналогична рассмотренному вьше.

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

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

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

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

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