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

40 45 50 55 Изобретение относится к вычислительной технике и может найти применение в вычислительных процессах в управляющих устройствах при выполнении операций сравнения по величинам некоторого числа многоразрядных кодовых комбинаций с целью их упорядочения по мере возрастания или уменьшениях их величины.Цель изобретения - упрощение устройства.На чертеже представлена структурная схема устройства для сортировки чисел.В устройство входит ячейка 1 анализа, регистр 2 сдвига, узел 3 управления, регистр 4, группа выходных элементов И 5, дешифратор 6, группа элементов И 7, элемент ИЛИ 8, триггер 9 ячейки анализа, генератор 10 импульсов, элемент И 11 узла управления, триггер 12 узла управления, элемент ИЛИ 13, группа информационных выходов 14 устройства, входы 15 сортируемого числа устройства, вход 16 останова устройства, вход 17 запуска устройства.Каждое слово из сортируемого массива состоит из кода числа (и-Ь) разрядов и Ь- разрядного кода признака этого числа. Регистры 4 ячеек 1 анализа устройства предназначены для приема и хранения слов, подлежащих сортировке. Запись слова в регистр 4 ячейки осуществляется по соответствующей группе входов 15 устройства. Группа выходных элементов И 5 ячейки обеспечивает выдачу числа из регистра 4 потребителю в случае, если это число окажется результатом сортировки. Передача числа из регистра 4 ячейки потребителю осуществляется по соответствуюш,им выходам группы выходов 14 устройства. Дешифратор 6 ячейки преобразует 5-разрядный признак числа регистра 4 из двоичной системы счисления в однопозиционный код в виде разрешающего потенциала на одном из гп его выходов. Элемент группы элементов И 7 с номером 1 каждой ячейки анализа предназначен для анализа 1-го выхода дешифратора 6,Элемент ИЛИ 8 ячейки управляет через группу выходных элементов И 5 процессом считывания слова из регистра 4 и триггером 9, который позволяет исключить данную ячейку из дальнейшего анализа путем подачи на управляющий вход дешифраторов запрещающего потенциала, Ячейка исключается из дальнейшего анализа, если в результате сортировки слово регистра 4 данной ячейки передано потребителю. Регистр 2 сдвига предназначен для циклического анализа потенциалов выходов дешифраторов всех ячеек анализа, обеспечивая выдачу слова с 1-м признаком в 1-м такте потребителю.Регистр 2 сдвига выполнен т-разрядным, где гп - количество признаков сортировки.Генератор 10 импульсов, элемент И 11 и триггер 12 узла 3 управления предназ 5 1 О 15 20 25 30 35 начены для формирования тактовых сигналов, управляющих работой устройства.Устройство работает следующим образом.Сортировка слов, содержащихся в регистрах 4 ячеек анализа, осуществляется по убыванию (возрастанию) значений их признаков. Устройство работает по тактам. Длительность такта определяется периодом следования тактовых сигналов, формируемых узлом 3 управления. В каждом такте устройство выделяет из сортируемого массива и выдает потребителю слова, значения признаков которых в данном такте оказались наибольшими (наименьшими). В исходном состоянии триггеры 9 ячеек 1 анализа находятся в единичном состоянии, а триггер 12 узла 3 управления установлен в нулевое состояние, при этом потенциал прямого выхода триггера 12 запрещает выдачу тактовых сигналов генератора 10 через первый вход элемента И 11 на выход узла 3 управления. Для запуска устройства на вход 17 запуска подается сигнал Пуск, который устанавливает в нулевое состояние триггеры 9 ячеек анализа и в единичное состояние триггер 12 узла 3 управления. С инверсного выхода триггера 9 ячейки анализа разрешающий потенциал подается на управляющий вход дешифратора 6, а с прямого выхода триггера 12 узла 3 управления разрешающий потенциал подается на второй вход элемента И 11.Если в первом такте среди признаков сортируемых слов есть хотя бы одно с максимальным (минимальным) значением, то на первом выходе дешифратора в ячейке анализа, где хранится слово с этим признаком, образуется разрешающий потенциал, который поступает на один вход первого элемента группы элементов И 7. В первом такте работы устройства еди. ничный сигнал появляется на первом выходе регистра 2 сдвига, который поступает на другой вход первого элемента группы элементов И 7. При наличии двух сигналов на входах первого элемента группы элементов И 7 на его выходе появляется единичный сигнал, который поступает на вход элемента ИЛИ 8. Сигнал с выхода элемента ИЛИ 8 обеспечивает выдачу слова через группу выходных элементов И 5 потребителю и установку триггера 9 в единичное состояние. С инверсного выхода этого триггера потенциал подается на управляющий вход дешифратора 6, исключив тем самым признак слова регистра 4 данной ячейки из сортировки в последующих тактах. В 1-м такте работы устройства потребителю выдаются слова с 1-м признаком. При этом единичный потенциал появляется на1-м выходе дешифратора ячейки анализа, в который хранится слово с 1-м признаком. Этот потенциал поступает на один вход 1-го элемента группы элементов И 7. С поступлением 1-го тактового импульса из узла 3 управления на вход регистра 2 сдвига единичный сигнал появляется на 1-м выходе регистра, который поступает на другой вход 1-го элемента группы элементов И 7, При наличии двух сигналов на входе 1-го элемента группы элементов И 7 на его выходе появляется единичный сигнал, который поступает на вход элемента ИЛИ 8. Сигнал с выхода элемента ИЛИ 8 обеспечивает выдачу слова с 1-м признаком через группу выходных элементов И 5 потребителю и установку триггера 9 в единичное состояние в 1-м такте. С инверсного выхода этого триггера запрещающий потенциал подается на управляющий вход дешифратора 6, исключив тем самым 1-й признак слова регистра 4 данной ячейки из сортировки в последующих тактах и т. д. Для прекращения процесса сортировки на вход 16 останова устройства сигнал Останов через элемент. ИЛИ 13 подается на триггер 12 узла 3 управления. Он устанавливает его в нулевое состояние и потенциал с прямого выхода триггера 12 запрещает выдачу тактовых сигналов генератора 10 через элемент И 11 на выход узла управления. Кроме того, с целью обеспечения автоматического оста нова устройства, окончание процесса сортировки осуществляется также сигналом, формируемым регистром сдвига, по окончанию цикла работы.При этом сигнал Окончание цикла с (т+ +1)-го выхода регистра сдвига через элемент ИЛИ 13 воздействует на триггер 12. Это позволяет исключить дополнительно из вычислительных устройств систему синхронизации записи во входные регистры информации ячеек памяти в каждом цикле сортировки. Для сортировки путем выделения слов по возрастанию их признаков необходимо в каждой ячейке к входам дешифратора 6 подключить инверсные выходы регистра 4. формула изобретения Устройство для сортировки чисел, содержащее узел управления, который включает генератор импульсов, триггер и элемент 5 И и и ячеек анализа, где п - число сортируемых чисел, каждая из которых включает регистр, группу выходных элементов И, дешифратор, группу элементов И, элемент ИЛИ и триггер, причем информацион О ные входы регистра 1-й ячейки анализа соединены соответственно с входами Е-го сортируемого числа устройства, где 1= 1, 2, , п, в 1-й ячейке анализа выходы разрядов регистра подключены соответственно к входам дешифратора и к информационным вхо дам соответствующих выходных элементовИ группы, выходы которых являются информационными выходами устройства, выходы дешифратора соединены с первыми входами соответствующих элементов И группы, выходы которых подключены к входам элемен та ИЛИ, управляющий вход дешифратора подключен к инверсному выходу триггера, вход установки в ноль которого соединен с входом запуска устройства, и с входом установки в единичное состояние триггера узла управления, в котором выход генератора импульсов соединен с входом запуска устройства и с входом установки в единичное состояние триггера узла управления, в котором выход генератора импульсов соединен с первым входом элемента И, ЗО второй вход которого соединен с прямымвыходом триггера, отличающееся тем, что, с целью упрощения устройства, оно содержит регистр сдвига и элемент ИЛИ, выходы которого соединены соответственно с входом останова устройства и (т+ 1) -м выходом реЗ 5 гистра сдвига, где т - число признаковсортировки, выход элемента ИЛИ соединен с входом установки в ноль триггера узла управления, выход элемента И которого соединен с тактовым входом регистра сдвига, 1-й выход которого, где 1=1, 2, , гп, сое О динен с вторым входом 1-го элемента Игруппы каждой ячейки анализа, в которой выход элемента ИЛИ подключен к управляющим входам выходных элементов И группы и входу установки в единичное состояние триггера.ошк едакто аказ 7 Со Техред Тираж И Государс делам изо осква, Ж -Патент,/5ВНИИПпо113035, МФилиал ППП ставитель И. Верее 67твенногоретений35, Рау г Ужго Е, ИвановаКорректорПодписноекомитета СССРи открытийшская наб., д, 4/5од, ул. Проектная