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

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

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

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

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

Каждое слово из сортируемого массива состоит из кода числа (n-S) разрядов и S- разрядного кода признака этого числа. Регистры 4 ячеек 1 анализа устройства предназначены для приема и хранения слов, подлежащих сортировке. Запись слова в регистр 4 ячейки осуществляется по соответствующей группе входов 15 устройства. Группа выходных элементов И 5 ячейки обеспечивает выдачу числа из регистра 4 потребителю в случае, если это число окажется результатом сортировки. Передача числа из регистра 4 ячейки потребителю осуществляется по соответствующим выходам группы выходов 14 устройства. Дешифратор 6 ячейки преобразует S-разрядный признак числа регистра 4 из двоичной системы счисления в однопозиционный код в виде разрешающего потенциала на одном из ш его выходов. Элемент группы элементов И 7 с номером i каждой ячейки анализа предназначен для анализа i-ro выхода дешифратора 6.

Элемент ИЛИ 8 ячейки управляет через группу выходных элементов И 5 процессом считывания слова из регистра 4 и триггером 9, который позволяет исключить данную ячейку из дальнейшего анализа путем подачи на управляющий вход дешифраторов запрещающего потенциала. Ячейка исключается из дальнейшего анализа, если в результате сортировки слово регистра 4 данной ячейки передано потребителю. Регистр 2 сдвига предназначен для циклического анализа потенциалов выходов дешифраторов всех ячеек анализа, обеспечивая выдачу слова с i-M признаком в i-м такте потребителю.

Регистр 2 сдвига выполнен т-разрядным, где m - количество признаков сортировки.

Генератор 10 импульсов, элемент И 11 и триггер 12 узла 3 управления предназ5

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

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

Сортировка слов, содержащихся в регистрах 4 ячеек анализа, осуществляется по убыванию (возрастанию) значений их признаков. Устройство работает по тактам. Длительность такта определяется периодом следования тактовых сигналов, формируемых уз0 лом 3 управления. В каждом такте устройство выделяет из сортируемого массива и выдает потребителю слова, значения признаков которых в данном такте оказались наибольщими (наименьщими). В исходном состоянии триггеры 9 ячеек 1 анализа находятся в единичном состоянии, а триггер 12 узла 3 управления установлен в нулевое состояние, при этом потенциал прямого выхода триггера 12 запрещает выдачу тактовых сигналов генератора 10 через первый

0 вход элемента И 11 на выход узла 3 управления. Для запуска устройства на вход 17 запуска подается сигнал «Пуск, который устанавливает в нулевое состояние триггеры 9 ячеек анализа и в единичное состояние триггер 12 узла 3 управления. С

5 инверсного выхода триггера 9 ячейки анализа разрешающий потенциал подается на управляющий вход дещифратора 6, а с прямого выхода триггера 12 узла 3 управления разрешающий потенциал подается на второй вход элемента И 11.

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

В первом такте работы устройства единичный сигнал появляется на первом вы- 0 ходе регистра 2 сдвига, который поступает на другой вход первого элемента группы элементов И 7.

При наличии двух сигналов на входах с первого элемента группы элементов И 7 на его выходе появляется единичный сигнал, который поступает на вход элемента ИЛИ 8. Сигнал с выхода элемента ИЛИ 8 обеспечивает выдачу слова через группу выходных элементов И 5 потребителю и установ- 0 ку триггера 9 в единичное состояние. С инверсного выхода этого триггера потенциал подается на управляющий вход дешифратора 6, исключив тем самым признак слова регистра 4 данной ячейки из сортировки в последующих тактах. 5

В i-M такте paбotы устройства потребителю выдаются слова с i-м признаком. При этом единичный потенциал появляется на

i-M выходе дешифратора ячейки анализа, в который хранится слово с i-м признаком. Этот потенциал поступает на один вход i-ro элемента группы элементов И 7. С поступлением i-ro тактового импульса из узла 3 управления на вход регистра 2 сдвига единичный сигнал появляется на i-M выходе регистра, который поступает на другой вход i-ro элемента группы элементов И 7. При наличии двух сигналов на входе i-ro элемента группы элементов И 7 на его выходе появляется единичный сигнал, который поступает на вход элемента ИЛИ 8. Сигнал с выхода элемента ИЛИ 8 обеспечивает выдачу слова с i-M признаком через группу выходных элементов И 5 потребителю и установку триггера 9 в единичное состояние в i-м такте. С инверсного выхода этого триггера запрещающий потенциал подается на управляющий вход дешифратора 6, исключив тем самым 1-й признак слова регистра 4 данной ячейки из сортировки в последующих тактах и т. д.

Для прекращения процесса сортировки на вход 16 останова устройства сигнал «Останов через элемент ИЛИ 13 подается на триггер 12 узла 3 управления. Он устанавливает его в нулевое состояние и потенциал с прямого выхода триггера 12 запрещает выдачу тактовых сигналов генератора 10 через элемент И 11 на выход узла управления. Кроме того, с целью обеспечения автоматического останова устройства, окончание процесса сортировки осуществляется также сигналом, формируемым регистром сдвига, по окончанию цикла работы. При этом сигнал «Окончание цикла с ( + 1)-го выхода регистра сдвига через элемент ИЛИ 13 воздействует на триггер 12. Это позволяет исключить дополнительно из вычислительных устройств систему синхронизации записи во входные регистры информации ячеек памяти в каждом цикле сортировки. Для сортировки путем выделения слов по возрастанию их признаков необходимо в каждой ячейке к входам дешифратора 6 подключить инверсные выходы регистра 4.

Формула изобретения

Устройство для сортировки чисел, содержащее узел управления, который включает генератор импульсов, триггер и элемент 5 И и п ячеек анализа, где п - число сортируемых чисел, каждая из которых включает регистр, группу выходных элементов И, дешифратор, группу элементов И, элемент ИЛИ и триггер, причем информационные входы регистра k-й ячейки анализа соединены соответственно с входами k-ro сортируемого числа устройства, где k 1, 2, ..., п, в k-й ячейке анализа выходы разрядов регистра подключены соответственно к входам дешифратора и к информационным вхо5 дам соответствующих выходных элементов И группы, выходы которых являются информационными выходами устройства, выходы дешифратора соединены с первыми входами соответствующих элементов И группы, выходы которых подключены к входам элемен0 та ИЛИ, управляющий вход дешифратора подключен к инверсному выходу триггера, вход установки в ноль которого соединен с входом запуска устройства, и с входом установки в единичное состояние триг5 гера узла управления, в котором выход генератора импульсов соединен с входом запуска устройства и с входом установки в единичное состояние триггера узла управления, в котором выход генератора импульсов соединен с первым входом элемента И,

0 второй вход которого соединен с прямым выходом триггера, отличающееся тем, что, с целью упрощения устройства, оно содержит регистр сдвига и элемент ИЛИ, выходы которого соединены соответственно с входом останова устройства и (m-f- 1)-м выходом ре5 гистра сдвига, где ш - число признаков сортировки, выход элемента ИЛИ соединен с входом установки в ноль триггера узла управления, выход элемента И которого соединен с тактовым входом регистра сдвига, i-й выход которого, где , 2, ..., т, соединен с вторым входом i-ro элемента И группы каждой ячейки анализа, в которой выход элемента ИЛИ подключен к управляющим входам выходных элементов И группы и входу установки в единичное состояние триггера.

Изобретение относится к вычислительной технике и предназначено для логической обработки информации, в частности для сортировки чисел по величине. Цель изобретения - упрощение устройства. В устройство, содержащее ячейки анализа, включающие в себя дешифратор, регистр, триггер, группу выходных элементов И, группу элементов И, элемент ИЛИ, устройство управления, включающее в себя генератор импульсов, триггер, элемент И, дополнительно введены регистр сдвига и элемент ИЛИ. Дешифратор ячейки преобразует S-разрядный признак числа регистра в однопозиционный код на одном из его выходов, который анализируется соответствующим элементом И каждой ячейки анализа. Элемент ИЛИ ячейки анализа управляет через группу выходных элементов И считыванием слова сигналом с триггера, который позволяет исключить данную ячейку из дальнейшего анализа, если в результате сортировки слово регистра данной ячейки передано потребителю. Регистр сдвига осуществляет циклический анализ потенциалов выходов дещифра- Q торов всех ячеек анализа, обеспечивая вы- S дачу слова с i-м признаком в i-м такте потребителю. I ИЛ. (Л to ю 00 ю to