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

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

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

На чертеже дана схема устройства для сортировки чисел.

Устройство для сортировки чисел содержит первую группу счетчиков 1, входы 2 сортируемых чисел, группу элементов ИЛИ 3 первый входной элемент И 4, вход 5 тактовых импульсов, группу запрещающих элементов И 6, второй входной элемент И 7, элемент ИЛИ 8, выходной счетчик 9, блок 10 анализа числа нулей, блок 11 сравнения, элемент 12 задержки, сдвиговый регистр 13, вторую группу счетчиков 14, информационные-выходы 15, вход 16 начальной установки выход 17 конца работы.

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

Перед началом работы в счетчики 1 с входов 2 заносятся исходные числа сортируемого массива. Счетчики 9 и 14 и регистр 13 по сигналу с входа 16 обнуляются. На входе 18 появляется сигнал, соответствующий уровню логической единицы.

Работа устройства начинается подачей тактовых импульсов на вход 5. Пусть каждое из, сортируемых чисел отлично от нуля. Тогда в исходном состоянии на первом выходе блока 11 сравнения формируется сигнал такого уровня (например, логической единицы), который открывает элемент И 4 для прохождения через него тактовых импульсов с входа 5. Эти импульсы будут поступать на счетные (вычитающие) входы счетчиков 1 и через запрещающие элементы И 6 - на счетные (суммирующие) входы счетчиков 14 до тех пор, пока какой-либо из счетчиков 1 не обнулится. При этом на выходе соответствующего элемента из группы элементов ИЛИ 3 появится сигнал, соответствующий уровню логического нуля. Блок 10 анализа числа нулей преобразует унитарный код нулей и единиц в позиционный код числа нулей на выходах элементов ИЛИ 3. Таким образом, на выходе блока 10 формируется код 00...01. Коды в счетчике 9 и на выходе блока 10 окажутся различными, и на первом выходе блока М сравнения сформируется сигнал, который закроет элемент И 4, а на втором выходе - сигнал, который откроет элемент И 7 для прохождения тактовых импульсов. Вследствие этого следующий тактовый .импульс поступит через элемент И 7 на счетный (суммирующий) вход счетчика 9 и сдвигающий вход регистра 13.

Так как на входе 18 сигнал соответствует уровню логической единицы, то при сдвиге в младщий разряд регистра 13 записывается единица, которая в дальнейщем запрещает прохождение через соответствующий запрещающий элемент И 6 сигналов с выхода элемента И 4. Тем самым фиксируется содержимое счетчика 14, соответствующего младщему разряду регистра 13. Указанный счетчик будет хранить минимальное из сортируемых чисел. Если обнулялось сразу несколько (например, 1) счетчиков 1, что соответствует наличию в сортируемом массиве I одинаковых чисел, то через элемент И 7 проходит I тактовых импульсов подряд, и содержимое регистра 13 сдвигается на разрядов. Освобождающиеся младщие разряды заполняются единицами, и в результате в регистре 13 будет записан код 00...011...1. Тем самым фиксируется содержимое I счетчиков 14, соответствующих освобождающимся младщим разрядам регистра 13. Так как тактовые импульсы поступают также и на счетный вход счетчика 9, то с приходом Е-го импульса его содержимое окажется равным коду, сформированному блоком 10, и на первом выходе блока 11 сравнения снова появится сигнал, открывающий элемент И 4.

В исходное нулевое состояние счетчик 9 устанавливается очередным тактовым импульсом. Элемент 12 задержки необходим для согласования времен прохождения сигнала с выхода элемента И 4 по цепи: счетчик 1, элемент ИЛИ 3, блок 10 и эле.мент

12задержки, элемент ИЛИ 8, счетчик 9, в результате чего обеспечивается устойчивая работа устройства. Далее работа устройства повторяется, т. е. снова тактовые импульсы через элемент И 4 начнут уменьшать содержимое счетчиков 1 и наращивать содержимое тех счетчиков 14, для которых в в соответствующих им разрядах регистра 13 содержатся нули, и т.д. Устройство заканчивает работу, когда на выходе 17 появится уровень логической единицы (в регистре

13установится код 11.1). При этом в счетчиках 14 в направлении сверху вниз будут записаны исходные числа, упорядоченные по возрастанию.

Если среди сортируемых чисел содержатся числа, равные нулю, то в исходном состоянии с выхода блока 11 сравнения будет сниматься уровень, открывающий элемент И 7. Следовательно, тактовые импульсы сразу после их подачи на вход 5 будут поступать на счетчик 9 и на регистр 13. В дальнейщем работа устройства аналогична рассмотренной.

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

возрастанию, если к выходу 17 подключить К-й разряд регистра 13. Как только на этом выходе появится уровень логической единицы, значит в счетчиках 14, соответствующих единичным разрядам регистра 13, в направлении сверху вниз содержатся первые К членов последовательности чисел, упорядоченных по возрастанию.

Необходимо отметить, что устройство можно легко модифицировать на случай нахождения чисел, упорядоченных по убыванию. Для этого достаточно присоединить выход первого входного элемента И 4 не к вычитающим, а к суммирующим счетным входам счетчиков 1, а выходы запрещающих элементов И 6 - не к суммирующим, а к вычитающим счетным входам счетчиков 14. Тогда по окончании работы устройства, т.е. когда на выходе 17 появится уровень логической единицы, в счетчиках 14 в направлении сверху вниз будут записаны исходные числа, упорядоченные по убыванию.

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее входной элемент И, группу элементов ИЛИ, выходной счетчик, группу запрещающих элементов И, элемент ИЛИ, первую группу счетчиков, информационные входы которых являются входами сортируемых чисел устройства, а выходы подключены к входам соответствующих элементов ИЛИ группы, вход тактовых импульсов устройства соединен с первым входом первого элемента И, выход которого подключен к первым входам запрещающих элементов И, отличающееся тем, что, с целью расщирения области применения за счет возможности сортировки одинаковых и нулевых чисел, в него введены блок анализа числа нулей, блок сравнения, элемент задержки, второй входной элемент И, сдвиговый регистр и вторая группа счетчиков, выходы которых являются информационными выходами устройства, а счетные входы соединены с выходами соответствующих запрещающих элементов И группы, вторые входы которых соединены с выходами соответствующих разрядов сдвигового регистра, выход старшего разряда которого является выходом конца работы устройства, вход начальной установки устройства подключен к входам установки в «О сдвигового регистра и счетчиков второй группы и первому входу элемента ИЛИ, второй вход которого через элемент задержки соединен с выходом первого входного элемента И, подключенного также к счетным входам счетчиков первой группы, выходы элементов ИЛИ группы соединены с соответствующими входами блока анализа числа нулей, выходы которого подключены к первой групI пе входов блока сравнения, вторая группа входов которого соединена с выходами раз(Л рядов выходного счетчика, вход установки в «О которого подключен к выходу элемента ИЛИ, а счетный вход - к выходу второго входного элемента И и входу управления сдвигом сдвигового регистра, информационный вход которого соединен с входом логической единицы устройства, первый вход второго входного элемента И соединен с О5 входом тактовых импульсов устройства, втоСХ) рые входы первого и второго элементов И со ю соединены с выходами соответственно равенства и неравенства блока сравнения.