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

Изобретение относится к вычислительнон технике и предназначено для логической обработки информации, в частности, для сортировки чисел по величине. Известно устройство для сортировки информации, состоящее из ячеек анализа, каждая из которых содержит входные и выходные элементы И, позволяющие принимать число из сортируемого массива в элементы памяти и считывать его соответственно, элементы НЕ и ИЛИ, группу элементов И и дешифратор. Сортировка информации в устройстве осуществляется путем параллельного анализа разрядов сортируемых чисел 1. Недостатком такого устройства является больщое количество оборудования. Наиболее близким техническим решением к предлагаемому является устройство для сортировки чисел, состоящее из узла управления, элементов ИЛИ-НЕ и N ячеек анализа, каждая из которых содержит регистр, группу выходных э;1ементов И, дешифратор на m выходов, группу элементов И, элементы ИЛИ, И и триггер, причем информационная группа входов регистра соединена соответственно с группой информационных входов устройства, каждая группа информационных выходов которого соединена соответственно с выходами выходных элементов И группы соответствующей ячейки, выходы соответствующих разрядов регистра в каждой ячейке подключены соответственно К информационным входам выходных элементов И группы и ко входам дешифратора, каждый i-й выход дешифратора соединен с первым входом (i-1)-го элемента И группы, первый выход дешифратора подключен к первому выходу ячейки анализа и первому входу элемента ИЛИ, выход j-ro элемента И группы, j l,2,...,(m-1), соединен с ( + 1)-м выходом ячейки и (J -f 1)-м входом элемента ИЛИ, каждый j-й выход к-й ячейки соединен с к-м входом j-ro элемента ИЛИ-НЕ устройства, выход элемента ИЛИ в каждой ячейке подключен к первому входу элемента И и к первым управляющим входам выходных э, ементов И группы, вторые управляющие входы которых соединены с выходом узла управления и вторым входом .элемента PI, выход элемента И в каждой ячейке подключен ко входу установки в нулевое состояние триггера, прямой выход которого соединен с управляющим входом дешифратора, а вход установки в единичное состояние - с входом запуска устройства и вторым входом узла управления, выход j-ro элемента ИЛИ-НЕ устройства .чючен к j-му входу блокировки каждой ячейки, соединенному с (j -f 1)-м входом ;-го и всех последующих элементов И группы данной ячейки, узел управления устройства содержит генератор, управляющий элемент И и TpvuTep запуска, причем выход генератора соединен с входом управляющего элемента И, выход которого подключен к выходу узла управления, а второй вход - прямому выходу триггера запуска, вход установки триггера в нулевое состояние является входом останова устройства, а вход установки триггера в единичное состояние - входом запуска устройства. Сортировка информации в устройстве осуществляется одновременным анализом разрядов всех сортируемых чисел 2. Недостатком известного устройства является его сложность. Цель изобретения - упрощение устройства. Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее узел управления, элементы ИЛИ- НЕ и N ячеек анализа, где N - количество сортируемых чисел, каждая из которых содержит регистр, группу выходных элементов И, дещифратор, группу элементов И, элементы ИЛИ, И и триггер, причем информационные входы регистра к-й ячейки анализа соединены соответственно с входами к-й группы информационных входов устройства, где к 1,2,...,N, выходы разрядов регистра подключены соответственно к входам дешифратора и к информационным входам соответствующих выходных элементов И группы, выходы которых соединены с выходами к-й группы устройства, i-й выход дешифратора, где i l,2,...,m m - число признаков сортировки, подключен к первому входу (i-1)го элемента И группы, первый выход дешифратора подключен к первому выходу ячейки анализа и первому входу элемента ИЛИ, выход j-ro элемента И группы, где j 1,2,...,{гп-1), соединен с (j + 1)-м выходом ячейки анализа и (j Ч- 1)-м входом элемента ИЛИ, каждый j-й выход к-й ячейки анализа соединен с к-м входом j-ro элемента ИЛИ-НЕ, выход элемента ИЛИ в каждой ячейке анализа подключен к первому входу элемента И и к входам разрешения выдачи выходных элементов И группы, управляющие входы которых соединены с выходом узла управления и вторым входом элемента И ячейки анализа, выход которого подключен ко входу установки в нулевое состояние триггера ячейки анализа, прямой выход которого соединен с управляющим входом дешифратора, а вход установки в единичное состояние - с входами запуска устройства и узла управления, содержащего генератор импульсов, элемент И и триггер, причем выход генератора импульсов соединен с первым входом элемента И, выход которого подключен к выходу узла управления, а второй вход - к прямому выходу триггера узла управления, входы установки в нулевое и единичное состояние которого соединены соответственно с входами останова и запуска устройства, введены m- 2 элементов И, причем выход j-ro элемента ИЛИ-НЕ соединен с j-ми входами элементов и с j-ro по (т-2)-и, второй вход j-ro элемента И группы каждой ячейки анализа соединен с выходом (j-1)-го элемента И, выход первого элемента ИЛИ-НЕ соединен с вторым входом первого элемента И группы каждой ячейки анализа. На чертеже представлена структурная схема устройства для сортировки чисел. В устройство входят ячейка анализа 1, элементы ИЛИ-НЕ 2, элементы И 3, узел управления 4, дешифратор 5, группа выходных элементов И 6, регистр 7, элементы И группы 8, элемент ИЛИ 9, элемент И ячейки анализа 10, триггер ячейки анализа 11, триггер узла управления 12, генератор 13, элемент И узла управления 14, группы информационных выходов устройства 15, группы информационных входов устройства 16, выход первого элемента ИЛИ-НЕ 17, выход первого 18, второго 19 и (т-2)-го 20 элементов И соответственно, выход узла управления 21, вход запуска устройства 22, вход останова устройства 23.

Каждое слово сортируемого массива состоит из кода числа п-S разрядов и S-разрядного кода признака этого числа. Регистры 7 ячеек анализа 1 устройства предназначены для приема и хранения слов, подлежащих сортировке. Запись слова в регистр 7 ячейки осуществляется по соответствующей группе информационных входов 16 устройства. Группа выходных элементов И 6 ячейки обеспечивает выдачу числа из регистра 7 потребителю в случае, если это число окажется результатом сортировки. Передача числа из регистра 7 ячейки потребителю осуществляется по соответствующим выходам группы выходов 15 устройства. Дешифратор 5 ячейки преобразует S-разрядный признак числа слова регистра 7 из двоичной системы счисления в однопозиционный код в виде разрещающего потенциала на одном из m его выходов. Элемент И 8 группы с номером j каждой ячейки предназначен для анализа (j + 1)-го выхода дешифратора 5. Элемент ИЛИ 9 ячейки управляет через группу выходных элементов И 6 процессом считывания слова из регистра 7, а через элемент И 10 - триггером 11, который позволяет исключить данную ячейку из дальнейщего анализа путем подачи на управляющий вход дешифратора 5 запрещающего потенциала. Ячейка исключается из дальнейшего анализа, если в результате сортировки слово регистра 7 данной ячейки передано потребителю. Элемент ИЛИ-НЕ 2 с номером j 1 предназначен для анализа потенциалов первых выходов дешифраторов 5 всех ячеек, а элементы ИЛИ-НЕ 2 с номерами j 2,m-1, - для анализа потенциалов выходов (j - 1)-х элементов И 8 группы всех ячеек. Каждый j-й элемент И 3 предназначен для анализа выходов первых j элементов ИЛИ-НЕ 2 устройства, триггер 12, генератор 13 и элемент И 14 - для

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

потенциал с выхода элемента ИЛИ 9 с поступлением с узла управления тактового сигнала обеспечивает выдачу слова через группу выходных элементов И 6 потребителю, а через элемент И 10 этой же ячейки - установку триггера 11 в единичное состояние,

с инверсного выхода которого запрещающий потенциал подается На управляющий вход дешифратора 5, исключив тем самым признак слова регистра 7 данной ячейки из сортировки в последующих тактах.

Если в текущем такте среди признаков

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

образуется единичный потеницал, который поступает на второй вход первого элемента И 8 группы всех ячеек и на первые входы всех элементов И 3 устройства в качестве разрещающего потенциала, при этом нулевой потенциал с выхода второго элемента

ИЛИ-НЕ 2 поступает на вторые входы элементов И 3. Нулевой потенциал с выхода j-ro элемента И 3 поступает на второй вход (j + 1) -го элемента И 8 группы всех ячеек формирования тактовых сигналов, управляющих работой устройства. Устройство осуществляет сортировку слов, содержащихся в регистрах 7 ячеек, по убыванию (возрастанию) значений их признаков. Оно работает по тактам. Длительность такта определяется периодом следования тактовых сигналов, формируемых узлом управления 4. В каждом такте устройство выделяет из сортируемого массива и выдает потребителю слова, значения признаков ; торых в данном такте сортировки оказалисо наибольшими (наименьшими). Для запуска устройства на вход запуска 22 подается сигнал «Пуск, который устанавливает в нулевое состояние триггеры 11 ячеек и в единичное состояние триггер 12 узла управления 4. С инверсного выхода триггера 11 ячейки разрещающий потеницал подается на управляющий вход дешифратора 5, а с прямого выхода триггера 12 узла управления 4 разрешающий потенциал подается на второй вход элемента И 14.

в качестве запрещающего потенциала. На выходе первого элемента И 8 группы и втором входе элемента ИЛИ 9 ячейки, в регистре 7 которой хранится слово с признаком (т-1), образуется единичный потенциал, который аналогично предыдущему случаю обеспечивает выдачу слова из регистра 7 потребителю и исключение его признака из сортировки в последующих тактах и т. д. Для прекращения процесса сортировки на вход останова 23 устройства подается сигнал «Останов, по которому триггер 12 узла управления 4 устанавливается в нулевое состояние и потенциал с его прямого выхода запрещает выдачу тактовых сигналов генератора 13 через элемент И 14 на выход узла управления 4. Для сортировки путем выделения слов по возрастанию их признаков необходимо в каждой ячейке ко входам дещифратора 5 подключить инверсные выходы регистра 7.

Сопоставительный анализ предлагаемого и известного устройств показывает, что выигрыщ в оборудовании от внедрения предлагаемого устройства составляет 20% и более, а снижение стоимости одного образца устройства достигает 1300 руб. и более.

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее узел управления, элементы ИЛИ-НЕ и N ячеек анализа, где N - количество сортируемых чисел, каждая из которых содержит регистр, группу выходных элементов И, дешифратор, группу элементов И, элемент ИЛИ, элемент И и триггер, причем информационные входы регистра к-й ячейки анализа соединены соответственно с входами к-й группы информационных входов устройства, где к 1,2,..., ,N, выходы разрядов регистра подключены соответственно к входам дешифратора и к информационным входам соответствующих выходных элементов И группы, выходы которых соединены с выходами к-й группы устройства, i-й выход дешифратора, где .1 1, ,2,...,т, ш - число признаков сортировки, подключен к первому входу (i-1)-го элемента И группы, первый выход дешифратора подключен к первому выходу ячейки анализа и первому входу элемента ИЛИ, выход j-ro элемента И группы, где j 1,2,...,m-1, соединен с (j + 1)-м выходом ячейки анализа и (J Ч- 1)-м входом элемента ИЛИ, каждый j-й выход к-й ячейки анализа соединен с к-м входом j-ro элемента ИЛИ-НЕ, выход элемента ИЛИ в каждой ячейке анализа подключен к первому входу элемента И и к входам разрешения выдачи выходных элементов И группы, управляющие входы которых соединены с выходом узла управления и вторым входом элемента И ячейки анализа, выход которого подключен ко входу установки в нулевое состояние триггера ячейки анализа, прямой выход которого соединен с управляющим входом дешифратора, а выход установки в единичное состояние - с входами запуска устройства и узла управления, содержащего генератор импульсов, с В элемент И и триггер, причем выход генератора импульсов соединен с первым входом (Л элемента И, выход которого подключен к выходу узла управления, а второй вход - к прямому выходу триггера узла управления, входы установки в нулевое и единичное состояние которого соединены соответственно с входами останова и запуска устройства, отличающееся тем, что, с целью упрощения устройства, в него введены m-2 элементов И, причем выход j-ro элемента ИЛИ-НЕ соединен с j-ми входами элементов И, с j-ro по (т-2)-и, второй вход j-ro элемен05 та И группы каждой ячейки анализа соединен с выходом (j-1)-го элемента И, выход первого элемента ИЛИ-НЕ соединен с вторым входом первого элемента И группы каж00 дой ячейки анализа. ю