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

. Зай Р (прото ОСУДАРСТВЕННЫЙ КОМИТЕТ СССР О ДЕ.1 АМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ ТОРСКОМУ СВИДЕТЕЛЬСТВ(54) (57) УСТРОЛСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее узел управления, элементы ИЛИ - НЕ и М ячеек анализа, где Х - количество сортируемых чисел, каждая из которых содержит регистр, группу выходных элементов И, дешифратор, группу элементов И, элемейт ИЛИ, элемент И и триггер, причем информационные входы регистра к-й ячейки анализа соединены соответственно с входами к-й группы информационных входов устройства, где к = 1,2 ,И, выходы разрядов регистра подключены соответственно к входам дешифратора и к информационным входам соответствующих выходных элементов И группы, выходы которых соединены с выходами к-й группы устройства, 1-й выход дешифратора, где 1 = 1, ,2в, т - число признаков сортировки, подключен к первому входу (1 - 1)-го элемента И группы, первый выход дешифратора подключен к первому выходу ячейки анализа и первому входу элемента ИЛИ, выход 1-го элемента И группы, где 1 = 1,2гп - 1,801061132 А соединен с (1+ 1)-м выходом ячейки анализа и (1+ 1)-м входом элемента ИЛИ, каждый 1-й выход к-й ячейки анализа соединен с к-м входом 1-го элемента ИЛИ-НЕ, выход элемента ИЛИ в каждой ячейке анализа подключен к первому входу элемента И и к входам разрешения выдачи выходных элементов И группы, управляющие входы которых соединены с выходом узла управления и вторым входом элемента И ячейки анализа, выход которого подключен ко входу установки в нулевое состояние триггера ячейки анализа, прямой выход которого соединен с управляющим входом дешифратора, а выход установки в единичное состояние - с входами запуска устройства и узла управления, содержащего генератор импульсов, элемент И и триггер, причем выход генера- Я тора импульсов соединен с первым входом элемента И, выход которого подключен к выходу узла управления, а второй вход - к прямому выходу триггера узла управления, входы установки в нулевое и единичное состояние которого соединены соответственно ф с входами останова и запуска устройства, отличающееся тем, что, с целью упрощения устройства, в него введены гп - 2 элементов И, причем выход 1-го элемента ИЛИ - НЕ соединен с 1-ми входами элементов И, с 1-го по (а - 2)-й, второй вход 1-го элемента И группы каждой ячейки анализа соеди- ( неи с выходом (1 - 1)-го элемента И, выход ф первого элемента ИЛИ - НЕ соединей с вторым входом первого элемента И группы каждой ячейки анализа.ЮИзобретение относится к вычислительной технике и предназначено для логической обработки информации, в частности, для сортировки чисел по величине.Известно устройство для сортировки информации, состоящее из ячеек анализа, каждая нз которых содержит входные и выходные элементы И, позволяющие принимать число пз сортируемого массива в элементы памяти и считывать его соответственно, элементы НЕ и ИЛИ, группу элементов И и дешифратор. Сортировка ичформации в устройстве осуществляется путем параллельного анализа разрядов сортиру емых чисел И) 5 10состояние - с входом запуска устройства 50 и вторым входом узла управления, выход ;-го элемента ИЛИ вустройства подключен к 1-му входу блокировки каждой ячейки, соединенному с+ 1)-м входом ,-го и всех последующих элементов И группы данной ячейки, узел управления устройства содержит генератор, управляющий элемент И и триггер запуска, причем выход генератора соединен с входом управлякщего Недостатком такого устройства является большое количество оборудования,Наиболее близким техническим решением к предлагаемому является устройство для сортировки чисел, состоящее из узла управления, элементов ИЛИ ви Й ячеек анализа, каждая из которых содержит регистр, 20 группу выходных элементов И, дешифратор на гп выходов, группу элементов И, элементы ИЛИ, И и триггер, причем информационная группа входов регистра соединена соответственно с группой информационных входов устройства, каждая группа информационных выходов которого соединена соответственно с выходами выходных элементов И группы соответствующей ячейки, выходы соответствующих разрядов регистра в каждой ячейке подключены соответственно к информационным входам выходных элементов И группы и ко входам дешифратора, каждый 1-й выход дешифратора соединен с первым входом 11 - 1)-го элемента И группы, первый выход дешифратора подключен к первому выходу ячейки анализа и первому входу элемента ИЛИ, выход )-го элемента И группь 1, ) = 1,2 гп - 1), соединен с (1+ 1)-м выходом ячейки и+ 1).м входом элемента ИЛИ, каждый )-й выход к-й ячейки соединен с к-м входом )-го элемента ИЛИ. - НЕ устройства, выход элемента ИЛИ д 0 в каждой ячейке подключен к первому входу элемента И и к первым управляющим входам выходных элементов И группы, вторые управляющие входы которых соединены с выходом узла управления и вторым входом элемента И, выход элемента И в каждой ячейке подключен ко входу установки в нулевое состояние триггера, прямой выход которого соединен с управляющим входом дешифратора, а вход установки в единичное элемента И, выход которого подключен к выходу узла управления, а второй вход - прямому выходу триггера запуска, вход установки триггера в нулевое состояние является входом останова устройства, а вход установки триггера в единичное состояние - входом запуска устройства. Сортировка информации в устройстве осуществляется одновременным анализом разрядов всех сортируемых чисел 2) .Недостатком известного устройства является его сложность,Цель изобретения - упрощение устройства. Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее узел управления, элементы ИЛИ - НЕ и Х ячеек анализа, где М - количество сортируемых чисел, каждая из которых содержит регистр, группу выходных элементов И, дешифратор, группу элементов И, элементы ИЛИ, И и триггер, причем информационные входы регистра к-й ячейки анализа соединены соответственно с входами к-й группы информационных входов устройства, где к = 1,2И, выходы разрядов регистра подключены соответственно к входам дешифратора и к информационным входам соответствующих выходных элементов И группы, выходы которых соединены с выходами к-й группы устройства, 1-й выход дешифратора, где 1 = 1,2, ,пт гп - число признаков сортировки, подключен к первому входу (1 - 1)- го элемента И группы, первый выход дешифратора подключен к первому выходу ячейки анализа и первому входу элемента ИЛИ, выход )-го элемента И группы, где = 1,2, ,(т - 1), соединен с+ 1)-м выходом ячейки анализа и+ 1)-м входом элемента ИЛИ, каждый )-й выход к-й ячейки анализа соединен с к-м входом )-го элемента ИЛИ - НЕ, выход элемента ИЛИ в каждой ячейке анализа подключен к первому входу элемента И и к входам разрешения выдачи выходных элементов И группы, управляющие входы которых соединены с выходом узла управления и вторым входом элемента И ячейки анализа, выход которого подключен ко входу установки в нулевое состояние триггера ячейки анализа, прямой выход которого соединен с управляющим входом дешифратора, а вход установки в единичное состояние - с входами запуска устройства и узла управления, содержащего генератор импульсов, элемент И и триггер, причем выход генератора импульсов соединен с первым входом элемента И, выход которого подключен к выходу узла управления, а второй вход - к прямому выходу триггера узла управления, входы установки в нулевое и единичное состояние кото. рого соединены соответственно с входами останова и запуска устройства, введены т - 2 элементов И, причем выход )-го элемента ИЛИ всоединен с )-ми входами элемен5 10 15 20 3тов И с 1-го по (гп - 2)-й, второй вход 1-го элемента И группы каждой ячейки анализа соединен с выходом (1 - 1)-го элемента И, выход первого элемента ИЛИ всоединен с вторым входом первого элемента И группы каждой ячейки анализа,На чертеже представлена структурная схема устройства для сортировки чисел.В устройство входят ячейка анализа 1, элементы ИЛИ в2, элементы И 3, узел управления 4, дешифратор 5, группа выходных элементов И б, регистр 7, элементы И группы 8, элемент ИЛИ 9, элемент И ячейки анализа 10, триггер ячейки анализа 11, триггер узла управления 12, генератор 13, элемент И узла управления 14, группы информационных выходов устройства 15, группы информационных входов устройства 16, выход первого элемейта ИЛИ - НЕ 17, выход первого 18, второго 19 и (гп - 2)-го 20 элементов И соответственно, выход узла управления 21, вход запуска устройства 22, вход останова устройства 23. Каждое слово сортируемого массива состоит из кода числа и - 5 разрядов и Я-разрядного кода признака этого числа. Регистры 7 ячеек анализа 1 устройства предназначены для приема и хранения слов, подлежащих сортировке. Запись слова в регистр 7 ячейки осуществляется по соответствующей группе информационных входов 16 устройства. Группа выходных элементов И б ячейки обеспечивает выдачу числа из регистра 7 потребителю в случае, если это число окажется результатом сортировки. Передача числа из регистра 7 ячейки потребителю осуществляется по соответствующим выходам группы выходов 15 устройства. Дешифратор 5 ячейки преобразует 5-разрядный признак числа слова регистра 7 из двоичной системы счисления в однопозиционный код в виде разрешающего потенциала на одном из т его выходов. Элемент И 8 группы с номером 1 каждой ячейки предназначен для анализа (1+ 1)-го выхода дешифратора 5. Элемент ИЛИ 9 ячейки управляет через группу выходных элементов И 6 процессом считывания слова из регистра 7, а через элемент И 10 - триггером 11, который позволяет исключить данную ячейку из дальнейшего анализа путем подачи на управляющий вход дешифратора 5 запрещающего потенциала, Ячейка исключается из дальнейшего анализаесли в результате сортировки слово регистра 7 данной ячейки передано потребителю. Элемент ИЛИ в2 с номером 1 = 1 предназначен для анализа потенциалов первых выходов дешифраторов 5 всех ячеек, а элементы ИЛИ - НЕ 2 с номерами 1 = 2,гп - 1, - для анализа потенциалов выходов (1 - 1) -х элементов И 8 группы всех ячеек. Каждый 1-й элемент И 3 предназначен для анализа выходов первых 1 элементов ИЛИ - НЕ 2 устройства, триг;ер 12, генератор 13 и элемент И 14 - для 25 30 35 40 45 50 55 формирования тактовых сигналов, управляющих работой устройства.Устройство осуществляет сортировку слов, содержащихся в регистрах 7 ячеек, по убыванию (возрастанию) значений их признаков. Оно работает по тактам, Длительность такта определяется периодом следования тактовых сигналов, формируемых узлом управления 4, В каждом такте устройство выделяет из сортируемого массива и выдает потребителю слова, значения признаковвторых в данном такте сортировки оказались наибольшими (наименьшими) .Для запуска устройства на вход запуска 22 подается сигнал Пуск, который устанавливает в нулевое состояние триггеры 11 ячеек и в единичное состояние триггер 12 узла управления 4. С инверсного выхода триггера 11 ячейки разрешающий потеницал подается на управляющий вход дешифратора 5, а с прямого выхода триггера 12 узла управления 4 разрешающий потенциал подается на второй вход элемента И 14. Если в текущем такте среди признаков сортируемых слов есть хотя бы один с значением в, то на первом выходе дешифрато. ра 5 ячейки, где хранится слово с этим признаком, образуется разрешающий потенциал, который через первый элемент ИЛИ - НЕ 2 поступает на второй вход первого элемента И 8 группы, а через элементы И 3 - на вторые входы соответствующих элемен. тов И 8 группы всех ячеек в качестве запрещающего потенциала, Таким образом, единичный потенциал на входах элемента ИЛИ 9 имеет место только в тех ячейках, в регистрах 7 которых хранится слово, значение признака которого равно т. Единичнвй потенциал с выхода элемента ИЛИ 9 с поступлением с узла управления тактового сигнала обеспечивает выдачу слова через группу выходных элементов И 6 потребителю, а через элемент И 10 этой же ячейки - установку триггера 1 в единичное состояние. с инверсного выхода которого запрещающий потенциал подается на управляющий вход дешифратора 5, исключив тем самым признак слова регистра 7 данной ячейки из сортировки в последующих тактах.Если в текущем такте среди признаков сортируемых слов наибольшим оказывается признак с значением (гп - 1), то единичный потенциал имеет место на вторых выходах дешифраторов 5 соответствующих ячеек, а йа выходе первого элемента ИЛИ - НЕ 2 образуется единичный потеницал, который поступает на второй вход первого элемента И 8 группы всех ячеек и на первые входы всех элементов И 3 устройства в качестве разрешающего потенциала, при этом нулевой потенциал с выхода второго элемента ИЛИ - НЕ 2 поступает на вторые входы элементов И 3. Нулевой потенциал с выхода 1-го элемента И 3 поступает на второй вход (1 + 1)-го элемента И 8 группы всех ячеек1061132 Составитель Е, Иванова Редактор К. Волощук Техред И. Верее Корректор О, Билак Заказ 10041/51 Тираж 706 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж - 35; Раушская наб д, 4/5 Филиал ППП Патент, г. Ужгород, ул, Проектная, 4в качестве запрещающего потенциала. На выходе первого элемента И 8 группы и втором входе элемента ИЛИ 9 ячейки, в регистре 7 которой хранится слово с признаком (гп - 1), образуется единичный потенциал, который аналогично предыдущему случаю обеспечивает выдачу слова из регистра 7 потребителю и исключение его признака из сортировки в последующих тактах и т. д.Для прекращения процесса сортировки на вход останова 23 устройства подается 10 сигнал Останов, по которому триггер 12 узла управления 4 устанавливается в нулевое состояние и потенциал с его прямого выхода запрещает выдачу тактовых сигналов генератора 13 через элемент И 14 на выход узла управления 4. Для сортировки путем выделения слов по возрастанию их признаков необходимо в каждой ячейке ко входам дешифратора 5 подключить инверсные выходы регистра 7. Сопоставительный анализ предлагаемого и известного устройств показывает, что выигрыш в оборудовании от внедрения предлагаемого устройства составляет 20% и более, а снижение стоимости одного образца устройства достигает 1300 руб. и более.