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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее узел управления, элементы ИЛИ-НЕ и 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 дой ячейки анализа. ю

COlO3 СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

%5D G 06 F 7/Об

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМЪГ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕ.1АМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3437290/18-24 (22). 10.05.82 (46) 15.12.83. Бюл. № 46 (72) К. С. Барашев, В. Я. Сычев, И. А. Зай ков и В. В. Насонов (53) 681.325.5 (088.8) (56) 1. Авторское свидетельство СССР № 590728, кл. G 06 F 7/00, 1976.

2. Авторское свидетельство СССР № 960800, кл. G 06 F 7/04, 1981 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее узел управления, элементы ИЛИ вЂ” НЕ и N ячеек анализа, где

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

j-ro элемента И группы, где j = 1,2,...,m — 1, „„SU„„1061132 A соединен с (j + 1)-м выходом ячейки анализа и (j + 1)-м входом элемента ИЛИ, каждый j-й выход к-й ячейки анализа соединен с к-м входом j-го элемента ИЛИ-НЕ, выход элемента ИЛИ в каждой ячейке анализа подключен к первому входу элемента И и к входам разрешения выдачи выходных элементов И группы, управляющие входы которых соединены с выходом узла управления и вторым входом элемента И ячейки анализа, выход которого подключен ко входу установки в нулевое состояние триггера ячейки анализа, прямой выход которого соединен с управляющим входом дешифратора, а выход установки в единичное состояние— с входами запуска устройства и узла управления, содержащего генератор импульсов, элемент И и триггер, причем выход генератора импульсов соединен с первым входом элемента И, выход которого подключен к выходу узла управления, а второй вход— к прямому выходу триггера узла управления, входы установки в нулевое и единичное состояние которого соединены соответственно с входами останова и запуска устройства, отличающееся тем, что, с цел ью уп рощей и я устройства, в него введены m — 2 элементов

И, причем выход j-го элемента ИЛИ вЂ” НЕ соединен с j-ми входами элементов И, с

j-го по (m — 2)-й, второй вход j-го элемента И группы каждой ячейки анализа соединен с выходом (j — 1)-го элемента И, выход первого элемента ИЛИ вЂ” НЕ соединей с вторым входом первого элемента И группы каждой ячейки анализа.

1061132

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

Известно устройство для сортировки информации, состоящее из ячеек анализа, каждая нз которых содержит входные и выходные элементы И, позволяющие принимать число:гз сортируемого массива в элементы па, ÿòè и считывать его соответственно, элементы HE и ИЛИ, группу элементов И и дешифратор. Сортировка ичформации в устройстве осуществляется путем параллельного анализа разрядов сортиру емых чисел (!).

10 состояние — с входом запуска устройства

50 и вторым входом узла управления, выход

;-го элемента ИЛИ вЂ H устройства подключен к (-му входу блокировки каждой ячейки, соединенному с (j + 1) -м входом

,-го и всех последующих элементов И группы данной я ейки, узел управления устройства содержит генератор, управляющий элемент И и триггер запуска, причем выход генератора соединен с входом управляк>щего

Недостатком такого устройства является большое количество оборудования.

Наиболее близким техническим решением к предлагаемому является устройство для сортировки чисел, состоящее из узла управления, элементов ИЛИ вЂ” НЕ и N ячеек анализа, каждая из которых содержит регистр, 20 группу выходных элементов И, дешифратор на m выходов, группу элементов И, элементы ИЛИ, И и триггер, причем информационная группа входов регистра соединена соответственно с группой информационных входов устройства, каждая группа информационных выходов которого соединена соответственно свыхода,ми выходных элементов И группы соответствующей ячейки, выходы соответствующих разрядов регистра в каждой ячейке подключены соответственно 30 к информационным входам выходных элементов И группы и ко входам дешифратора, каждый -й выход дешифратора соединен с первым входом (i — 1)-го элемента И группы. первый выход дешифратора подключен к первому выходу ячейки анализа и первому входу элемента ИЛИ, выход j-ro элемента И группь1, j = 1,2„... (m — 1), соединен с (j + 1) -м выходом ячейки и (j + 1) -м входом элемента ИЛИ, каждый j-й выход к-й ячейки соединен с к-м входом j-ro элемента

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

Недостатком известного устройства является его сложность.

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

Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее узел управления, элементы ИЛИ—

НЕ и N ячеек анализа, где N — количество сортируемых чисел, каждая из которых содержит регистр, группу выходных элементов

И, дешифратор, группу элементов И, элементы ИЛИ, И и триггер, причем информационные входы регистра к-й ячейки анализа соединены соответственно с входами к-й группы информационных входов устройства, где к = 1,2,...,N, выходы разрядов регистра подключены соответственно к входам дешифратора и к информационным входам соответствующих выходных элементов И группы, выходы которых соединены с выходами к-й группы устройства, i-й выход дешифратора, где i = 1,2,...,m m — число признаков сортировки, подключен к первому входу (i — 1)ro элемента И группы, первый выход дешифратора подключен к первому выходу ячейки анализа и первому входу элемента ИЛИ, выход j-го элемента И группы, где j =

= 1,2,, (m — 1), соединен с (j + 1) -м выходом ячейки анализа и (j + 1) -м входом элемента ИЛИ, каждый j-й выход к-й ячейки анализа соединен с к-м входом j-го элемента ИЛИ вЂ” HE, выход элемента ИЛИ в каждой ячейке анализа подключен к первому входу элемента И и к входам разрешения выдачи выходных элементов И группы, управляющие входы которых соединены с выходом узла управления и вторым входом элемента И ячейки анализа, выход которого подключен ко входу установки в нулевое состояние триггера ячейки анализа, прямой выход которого соединен с управляющим входом дешифратора, а вход установки в единичное состояние — с входами запуска устройства и узла управления, содержащего генератор импульсов, элемент И и триггер, причем выход генератора импульсов соединен с первым входом элемента И, выход которого подключен к выходу узла управления, а второй вход — к прямому выходу триггера узла управления, входы устаНоВКН в нулевое и единичное состояние которого соединены соответственно с входами останова и запуска устройства, введены m—

2 элементов И, причем выход j-го элемента

ИЛИ вЂ” НЕ соединен с j-ми входами элемен1061132

3 тов И с j-ro по (m — 2)-й, второй вход j-го элемента И группы каждой ячейки анализа соединен с выходом (j — 1)-го элемента

И, выход первого элемента ИЛИ вЂ соединен с вторым входом первого элемента И группы каждой ячейки анализа.

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

В устройство входят ячейка анализа 1, элементы ИЛИ вЂ” НЕ 2, элементы И 3, узел управления 4, дешифратор 5, группа выходных элементов И 6, регистр 7, элементы И группы 8, элемент ИЛИ 9, элемент И ячейки анализа 10, триггер ячейки анализа 11, триггер узла управления 12, генератор 13, элемент И узла управления 14, группы информационных выходов устройства 15, группы информационных входов устройства 16, выход первого элемейта ИЛИ вЂ” НЕ 17, выход первого 18, второго 19 и (m — 2)-го

20 элементов И соответственно, выход узла управления 21, вход запуска устройства 22, вход останова устройства 23.

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

5 ячейки преобразует S-разрядный признак числа слова регистра 7 из двоичной системы счисления в однопозиционный код в виде разрешающего потенциала на одном из

m его выходов. Элемент И 8 группы с номером j каждой ячейки предназначен для анализа (j + 1)-ro выхода дешифратора 5.

Элемент ИЛИ 9 ячейки управляет через группу выходных элементов И 6 процессом считывания слова из регистра 7, а через элемент И 10 — триггером 11, который позволяет исключить данную ячейку из дальнейшего анализа путем подачи на управляющий вход дешифратора 5 запрещающего потенциала. Ячейка исключается из дальнейшего анализа„если в результате сортировки слово регистра 7 данной ячейки передано потребителю. Элемент ИЛИ вЂ” НЕ 2 с номером ) = 1 предназначен для анализа потенциалов первых выходов дешифраторов

5 всех ячеек, а элементы ИЛИ вЂ” НЕ 2 с номерами j = 2,m — 1, — для анализа потенциалов выходов (j — 1) -х элементов И 8 группы всех ячеек. Каждый J-й элемент И 3 предназначен для анализа выходов первых

j элементов ИЛИ вЂ” НЕ 2 устройства, триг;ер 12, генератор 13 и элемент И 14 — для

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

Устройство осуществляет сортировку слов, содержащихся в регистрах 7 ячеек, по убыванию (возрастанию) значений их признаков. Оно работает по тактам, Длительность такта определяется периодом следования тактовых сигналов, формируемых узлом управления 4. В каждом такте устройство выделяет из сортируемого массива и выдает потребителю слова, значения признаков торых в данном такте сортировки оказалис наибольшими (наименьшими) .

Для запуска устройства на вход запуска 22 подается сигнал «Пуск», который устанавливает в нулевое состояние триггеры

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

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

9 имеет место только в тех ячейках, в регистрах 7 которых хранится слово, значение признака которого равно m. Единичный потенциал с выхода элемента ИЛИ 9 с поступлением с узла управления тактового сигнала обеспечивает выдачу слова через группу выходных элементов И 6 потребителю, а через элемент И 10 этой же ячейки — установку триггера ll в единичное состояние. с инверсного выхода которого запрещающий потенциал подается на управляющий вход дешифратора 5, исключив тем самым признак слова регистра 7 данной ячейки из сортировки в последующих тактах.

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

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

ИЛИ вЂ” НЕ 2 поступает на вторые входы элементов И 3. Нулевой потенциал с выхода

j-го элемента И 3 поступает на второй вход (j + 1)-го элемента И 8 группы всех ячеек

1061132

Составитель Е. Иванова

Редактор К. Волощук Техред И. Верес Корректор О. Билак

3 а к аз 1004 1/51 Тираж 706 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, K — 35; Раушская наб., д. 4/5

Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4 в качестве запрещающего потенциала. На выходе первого элемента И 8 группы и втором входе элемента ИЛИ 9 ячейки, в регистре 7 которой хранится слово с признаком (m — 1), образуется единичный потенциал, который аналогично предыдущему случаю обеспечивает выдачу слова из регистра

7 потребителю и исключение его признака из сортировки в последующих тактах и т. д.

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

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