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

(54).УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

И.зобретение относится к автоматике и вычислительной технике и предназначено для логической обработки информации, в частности для сортировки чисел по величине.;

Известно устройство для сортировки чисел, содержащее элементы памяти, , схемы сравнения И: мажоритарный элемент. Сортировка осуществляется последователь ным анализом одноименных разрядов сортируемых чисел 11.

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

Недостатком известных устройств является их низкое быстродействие.

Наиболее близким техническим раые|НИем к изобретению является устройство для сортировки чисел, состоящее

из ячеек, каждая из которых содержит первую и вторую группы выходов, соединенных с одноименными входами соответственно первой и второй групп входов данной и очередной ячейки, п триггеров (п - количество разрядов в сортируемых числах), 2п входных элементов И, выходных элементов и, дешифратор, имеющий п входов и m 2 вы10ходов, (т-1) элементов НЕ, группу на m элементов И и га элементов ИЛИ. В каждой ячейке выход k-ro триггера (k f, п) соединен с k-ым входом дешифратора и с первым входом k-ro 5 выходного элемента И, второй вход которого соединен с втopы I входом ячейки. Первый вход 2k-ro входного элемента И соединен с выходом k-ro элемента НБ. Вторые входы входных

20 элементов И соединены с первым входом ячейки. Выходы C2k-1)-ro и 2k-ro входных элементов И ячейки соединены соответственно с единичным и нулевым входами k-ro триггера. Первый вход В

25 элемента И (t 1, m) группы соединен с выходом дешифратора. Второй вход I элемента И группы соединен с третьим входом ячейки. Остальные (2-1) входов I элемента И группы со30единены соответственно с выходами первого, второго, (J-l)-ro элементо НЕ. Выход I элемента И группы соеди нен с первым входом элемента ИЛИ и с ( 1) входом т-го элемента ИЛИ. Первый вход (Zk-l) входного эл мента И соединен с входом k-ro элемента НЕ, выходом k-ro выходнодо эл мента И и с R-входом первой группы входов ячейки. Входы остальных элем тов НБ каждой ячейки соединены с од ноименными входами первой группы входов. Второй вход р элемента ИЛИ (р 1, т-1) каждой ячейки соединен с выходом р элемента ИЛИ и с р выходом второй группы выходов ячейки. Выход т-го элемента ИЛИ соединен с выходом ячейки. Сортировка информации.в устройств осуществляется путем параллельного анализа разрядов сортируемых чисел С Недостатком такого устройства является его сложность, . Цель изобретения - упрощение устройства. Поставленная цель достигается тем что в устройство для сортировки -чисел, содержащее узел упрсшления и п ячеек анализа, каждая из которых состоит из регистра, группы выходных элементов И, деьшфратора, группы элементов ИЛИ, причем инфор«ационная группа входов регистра соединена соответственно с группой информа ционных входов устройства, выходы разрядов регистра подклинены соответ ственно к информационным входам выходных элементов И группы и кЬ входам деишфратора, каждый 1-ый выход дешифратора, где i 1, 2, ..., m сб единен с первым входом (i-1)-го элемента ИЛИ группы, первый выход дешиф ратора подключен к первому выходу ячейки анализа, выход каждого j го элемента ИЛИ группы, где j 1, 2, ..., (ra-f), соединен с (д+1)-ым выходом ячейки анализа, выход выходного элемента И i-ой ячейки анализа подключен к ж-му выходу Устройства, выход узла управления соединен со входами опроса ячеек анализа, введены элементы ИЛИ-НЕ, причем каждый i-ый выход каждого k-ro узЛа анали- за соединен с k-ым входом i-ro элемента ИЛИ-НЕ, а выход каждого i-ro элемента ИЛИ-НЕ подключен к i-му вхо ду блокировки всех ячеек ансшиза, 1саждая ячейка анализа дополнительно содержит элементы ИЛИ И, Триггер, причем выход каждого j-ro элемента И группы соединен с j-ым входом элемен та ИЛИ, выход которого подключен к. управляющему входу дешифратора и к первому входу элемента И, выход кото рого соединен со входом-установки в единичное состояние триггера, прямой выход которого подключен к первым управляющим входам выходны элементов И группы, вход опроса ячейки анализа подключен ко вторым управля ющим входам выходных элементов И группы и ко второму входу элемента И, вход установки в нулевое состояние триггера каждой ячейки анализа.соединен со входом запуска устройства, каждый i-ый вход блокировки ячейки анализа соединен с (i-«-1)-MH входами 1, 2, ... , . fn-i- -1)-ro элементов И группы. При этом узел управления содержит генератор, триггер, элемент И, вход (Генератора соединен с первым входом элемента И, вход установки в нулевое состояние триггера подключён ко. входу запуска устройства, вход установки в единичное состояние триггера соединен со входом останова устройства, прямой выход триггера подключен ко второму входу элемента И, выход которого соединен с выхЬдом узла |управления. На чертеже представлена структурная схема устройства для сортировки чисел. Устройство содержит п ячеек l-i, «««f n анализа, элементы ИЛИ-НЕ 2, 2, ...,2m г генератор 3, триггер 4 запуска, управляющий элемент .И 5. .;,. ,, . . Каждая ячейка 1 анализа содержит дшлифратор ё, выходные элементы И 7, регистр 8, элементы И 9., 92 ..., Эщ группы, элемент ИЛИ 10, элемент И 11, триггер 12, группу информационных входов. 13 устройств, группу выходов 14 устройства, выходы 15-,, IS-j, ..., 15m элементов ИЛИ ячейки, входы 16, 16, ..., 16 tn блокировки ячеек анализа, вход 17 запуска устройства, вход 18 останова устройства. Каикдое словЬ состоит из кода числа fn-S разрядов) и s-разрядного кода признака этого числа. Выходные элементы И 7 ячейки обеспечивают выдачу потребителю слова из регистра 8 в случае, если оно оказывается результатом сортировки. Передача слова потребителю осуществляется по соответствукицим выходам группы выходов 14 устройства. JeIJифpaтop 6 ячейки преобразует s-разрядный признёЛс числа слова регистра 8 из Двоичной системы счисления ,в однопоэициоиный kpin в виде разрешающего потенциала на из М его выходов. Элемент И 9 с номером i группы каждой ячейки предназначен для анализа (i+1)-ro выхода дешифратора 6 данной ячейки и выходов первых i элементов ИЛИ-НЕ 2 устройства. Элемент ИЛИ 10 ячейки управляет через выходные элементы И 7 процессом считывания слова регистра 8 потребителю и через элементы И 11 триггером 12, который позволяет исключить данную ячейку из дальнейшего анализа путем подачи на управляющий вход дешифратора б запрещающего потенциала. Ячейка исключается из даль нейшего анализа, если в результате Ьортировки слово регистра 8 данной ячейки передается потребителю. Элемент ИЛИ-НЕ 2 с номером 1 1 пред назначен для анализа потенциалов пер вых выходов дешифраторов 6 всех ячеeio а элементы ИЛИ-НЕ 2 с номерами 1 2,М-1 - для анализа потенциалов выходов (1-1)-ых элементов И 9 групп всех ячеек. Генератор 3, триггер 4 запуска и управляющий элемент И 5 представляют собой блок управления устройства,, Устройство работает следующим образом. Устройство осуществляет сортировку слов, содержащихся в регистрах 8 яче ек анализа, по убываний (возрастанию значений их признаков. Устройство работает по тактам. Дли тельность такта опреДеляется периодо следования импульсов генератора 3. В каждом такте устройство выделяет из сортируемого массива и выдает пот ребителю слова, значения признаков которых максимальные (минимальные), Для запуска устройства на его первый вход 17 подается сигнал Пуск, ко-:. торый устанавливает в нулевое состо яние триггеры 1.2 казвдой ячейки и триггер 4 запуска, с нулевых выходов которых разрешающий потенциал подает ся на управляющий вход дешифратора 6 соответствующей ячейки и на вход управляющего элемента И 5 устройства соответственно. t , .. ; ,;,;: -,. Если в текущем такте среди признаков сортируемых слов найдется хотя бы один с значением М, то на первом выходе дешифратора б ячейки анализа, гДе хранится слово с этим признаком, образуется разрешающий потенциал, который через первый элемент ИЛИ-НЕ 2поступает на вход первого и всех последующих элементов И 9 группы все ячеек в качестве запрещающего потенциала. Таким образом, единичный потенциал на входах элемента И Ю имеет место только в тех ячейках, в регистрах 8 которых хранится слово, значение признака которого ра.вно М, Единичный потенциал с выхода элемента ИЛИ 10 с поступлением очередного импульса генератора 3 обеспечивает выдачу слова данной ячейки через выходные элементы И 7 потребите) и через элемент И 11 - установку триггера 12 в единичное состояние, который, в свою очередь, обеспечивает по дачу запрещающего потенциала с нулевого выхода 16 на управляющий вход дешифратора 6, исключив тем самым пр нак слова регистра 8 данной ячейки из сортировки в последующих тактах, Если в текущем такте, среди признаков сортируемых слов нет признаков с значением М, но есть с значением (М-1), то на выходе первого элемента ИЛИ-НЕ 2 образуется единичный потенциал, который поступает на входы первого и всех последующих элементов И 9 группы всех ячеек в качестве разрешающего потенциала. На выходе первого элемента И 9 группы и втором входе 31лемента ИЛИ 10 ячейки, в регистре 8 которой хранится слово с признаком (М-1), образуется единичный потенциал, который аналогично предыдущему случаю обеспечивает выдачу слова из регистра 8 потребителю и исключение его признака из сортировки в последующих тактах и t,д, Для прекращения процесса сортировки на второй вход 18 устройства подается сигнал Остайов, который устанавливает триггер 4 запуска в единичное состояние, исключив тем самым возмодность прохождения млпульсов генератора 3 .через управляющий элемент И 5, Для сортировки путем выделения слов, по возрастанию значений их приз|Наков необходимо на входы дешифратоisa 6 каждой ячейки подать инверсные iвыходы регистра 8, Сопоставительный анализ предлагаемого и известного устройств показывает, что выигрьвы в оборудовании от использования устройства составляет 15 и более процентов. Формула изобретения . . . 1, Устройство для сортировки чисел, содержащее узел управления и п ячег ек анализа, каждая из которых состоит из )регистра, группы выходных элементов Hf дешифратора, группы элементов ИЛИ, причем информационная группа входов регистра соединена соответственно с группой информационных входов устройства, выходы разрядов регис1 ра подключены соответственно к информационным входам выходных элементов И группы и ко входам дешифратора, каждый i-ый выход дешифратора, где i 1,2, ,,,, m соединен с первьш входом (1-1)-го элемента ИЛИ группы, первый выход дешифратора подключен к первому выходу ячейки анализа, выход каждого j-ro элемента ИЛИ группы, где j 1, 2, ,.., (m-1) , соединен с (j 1) -ым выходом ячейки анализа, выход выходного элемента И i-ой ячейки анализа подключен к i-му выходу устройства, выход узла управления соединен со входами опроса ячеек анализа, отличающееся тем, что, с целью упрощения устройства, в него введены элементы ИЛИ-НЕ, причем каждый i-ый выход каждого k-го узла анализа соединен b k-ым входом i-ro элемента ИЛИ-НЕ, а выход каждого i-ro элемента ИЛИ-НЕ подключен к i-My входу блокировки всех ячеек анализа, каждая ячейка анализа дополнительно содержит элеме ты ИЛИ, И, триггер, причем выход каж дого j-ro эле1данта И группы соединен с j-ым входом элемента ИЛИ, выход которого, подключен к управляющему входу )ратора и к первому входу элемента И, выход которого соединен bo входом установки в единичное состояние триггера, прямой вькод которого подключен к первым управлянвдим входам выходных элементов И группы, вход опроса ячейки анализа подключен ко вторым управляюиим входам выходных элементов И группы и ко второму входу элемента И, вход установки в нулевое состояние триггера каждой лчейки анализа соединен со входом запуска устройства, каждой г-ий вход блокировки ячейки анализа соед

y-L..

ff. нен с (i - 1) -ми входами 1, 2, . .., (п-1+1)-го элементов И группы. 2. Устройство по п. 1, о т л и ч аю « е е с я тем, что.узел управления содержит генератор, триггер, элемент И, вход генератора соединен с первы входом элеглента И, вход установки в нулевое состояние триггера подключен ко входу запуска устройства, вход установки в единичное состояние триггера соединен со входом останова устройства, пршой выход триггера подключен ко второму входу элемента И, выход которого соединен с выходом узла управления Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР № 46396:8, кл. G 7/00, 1973. 2. Авторское свидетельство СССР № 424141, кл. G Об F 7/00, 1972. i 3. Авторское свидетельство СССР № 590728, кл. G 06 F 7/00, 1976 (прототип).