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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Республик («>960800 (61) Дополнительное к авт. сеид-ву— (22) Заявлено 25. 02. 81 (21} 3250579/18-24 с присоединением заявки № (23) Приоритет

Опубликовано 2309.82 ° Бюллетень ¹ 35

f51)hA Кл з

С Об F 7/04

Государственный комитет

СССР по Хеттам мзобретений и открытий

f53) УДК 681..325. . 5 (088. 8) Дата опубликования описания 23,09. 82 аявит (5 4) . JJCTPOACTBO ДЛЯ СОРТИРОВКИ ЧИСЕЛ

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

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

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

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

Наиболее близким техническим реше,нием к изобретению является устройство для сортировки чисел, состоящее из ячеек, каждая из которых содержит первую и вторую группы выходов, соединенных с одноименными входами соответственно первой и второй групп входов данной и очередной ячейки, и триггеров (n - количество разрядов в сортируемых числах), 2п входных элементов И, выходных элементов И, дешифратор, имеющий и входов и m = 2" выходСв, (m-1) элементов НЕ, группу на

m элементов И и m элементов" ИЛИ.

В каждой ячейке выход k-го триггера (k = 1Г, и) соединен с k-жл входом деввлфратора и с первым входом k-ro выходного элемента И, второй вход которого .соединен с вторжл входом ячейки. Первый вход 2k-го входного элемента И соединен с выходом k-ro элемента НЕ. Вторые входы входных

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

25 элемента И (ь = Г, в) группы соединен с выходом дешнфратора. Второй вход: У элемента И группы соединен с третьим входом ячейки. Остальные (J.-1) входов Р элемента И группы соЗ0 единены соответственно с выходами

960800 первого, второго (У-1)-го элементо

Н

I в

Е. Выход Х элемента И группы соединен с первым входом элемента ИЛИ и с (m-У+ 1) входом m-ro элемента

ИЛИ. Первый вход (Zk-1) входного элемента И соединен с входом k-го элемента НЕ, выходом k-го выходного элемента .И и с R-входом первой группы входов ячейки. Входы остальных элементов HE каждой ячейки соединены с одноименными входами первой группы входов. Второй вход р элемента ИЛИ (p = 1, m-1) каждой ячейки соединен с выходом р элемента ИЛИ и с р выходом второй группы выходов ячейки.

Выход m-го элемента ИЛИ соединен с выходом ячейки, Сортировка информации.в устройстве. осуществляется путем параллельного анализа разрядов сортируемых чисел(3).

Недостатком такого устройства является его сложность, Цель изобретения — упрощение устройства.

Поставленная цель достигается тем, что в устройство для сортировки -чисел, содержащее узел управления и п ячеек анализа, каждая из которых состоит из регистра, группы выходных элементов И, дешифратора, группы элементов ИЛИ, причем информационная группа входов регистра соединена соответственно с группой информационных входов устройства, выходы разрядов регистра подклкиены соответственно к информационным входам выходных элементов И группы и ко входам дешифратора, каждый i-ый. выход дешифратора, где i = 1, 2, ..., m сбединен с первым входом (i-1)-го элемента ИЛИ группы, первый выход дешифратора подключен к первому выходу 40 ячейки анализа, выход каждого j-го элемента ИЛИ группы, где j 1, 2, (m-7), соединен с (j+7)-ым выходом ячейки анализа, выход выходного элемента И i-ой ячейки анализа 45 подключен к 1-му выходу устройства, выход узла управления соединен со входами опроса ячеек анализа, введены элементы ИЛИ-НЕ, причем каждый

i-.ый выход каждого k-ro Узла анали- 50 за соединен с k-ым входом i-ro элемента ИЛИ-НЕ, а выход каждого i-го элемента ИЛИ-НЕ подключен к i-му входу блокировки всех ячеек анализа, каждая ячейка анализа дополнительно содержит элементы ИЛИ, И, триггер, причем выход каждого j-го элемента И группы соединен с j-ым входом элемента ИЛИ, выход которого подключен к. управляющему входу дешифратора и к первому входу элемента И, выход кото- 60 рого соединен со входом установки в единичное состояние триггера, прямой выход которого подключен к первым управляющим входам выходных элементов И группы, вход опроса ячейки 65 анализа подключен ко вторым учравляющим входам выходных элементов И группы H ко второму входу элемента И

I вход установки в нулевое состояние тРиггера каждой ячейки анализа. соединен со входом запуска устройства каждый i-ый вход блокировки ячейки анализа соединен с (i+1) -ми входами

1, 2, ...,.(п-i+1)-го элементов И группы.

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

Ф ход которого соединен с выходом узла . управления.

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

Устройство содержит и ячеек 1с, 11, ..., 1гс анализа, элементы ИЛЙ-НЕ

2,, 2, ..., 2щ, генератор 3, триггер 4 запуска, управляющий элемент

И 5 °

Каждая ячейка 1 анализа содержит дешифратор б, выходные элементы И 7, регистр 8, элементы И 9г, 9, ..., 9щ: группы, элемент ИЛИ 10, элемент И 11, триггер 12, группу информационных входов 13 устройств, группу выходов

14 устройства, выходы 151, 15, 15 элементов ИЛИ ячейкй, входы 16г, 16, .. °, 16ю блокировки ячеек анализа, вход 17 запуска устройства, вход 18 останова устройства.

Каждое слово состоит из кода чис" ла (n-S разрядов) и s-разрядного кода признака этого числа.

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

Передача слова потребителю осуществляется Во соответствующим выходам группы выходов 14 устройства.

Дешифратор 6 ячейки преобразует

s-разрядный призна числа слова регистра 8 as двоичной систегж счисле» ния,в однопозиционный код s виде разрешающего потенциала на одном из М его выходов..

Элемент И 9 с номером i группы каждой ячейки предназначен для анализа (i+1)-го выхода дешифратора б данной ячейки и выходов первых i элементов ИЛИ-ИЕ.2 устройства.

Элемент ИЛИ 10 ячейки управляет через выходные элементы И 7 процес-. .сом считывания слова регистра 8 потребителю и через элементы И. 11триггером 12, который позволяет исклю1 чить данную ячейку из дальнейшего

960800

6 анализа путем подачи на управляющий вход дешифратора б запрещающего потенциала. Ячейка исключается из дальнейшего анализа, если в результате сортировки слово регистра 8 данной ячейки передается потребителю. Элемент ИЛИ-НЕ 2 с номером i = 1 предназначен для анализа потенциалов первых выходов дешифраторов б всех яче.ек, а элементы ИЛИ-НЕ 2 с номерами

2, М-1 - для анализа потенциалов 10 выходов (i-1)-ых элементов И 9 группы всех ячеек. Генератор 3, триггер 4 запуска и управляющий элемент И 5 представляют собой блок управления устройства, 15

Устройство работает следующим образом.

Устройство осуществляет сортировку слов, содержащихся в регистрах 8 ячеек айализа, по убыванию (возрастанию) gp .значений их признаков.

Устройство работает по тактам. Длительность такта определяется периодом следования импульсов генератора.3.

В каждом такте устройство выделяет из сортируемого массива и выдает потребителю слова, значения признаков которых максимальные (минимальные).

Для запуска устройства. на его первый вход 17 подается сигнал "Пуск" > ко-.. торый устанавливает в нулевое состо« янке триггеры 12 каждой ячейки и триггер 4 запуска, с нулевых выходов которых разрешающий потенциал подается на управляющий вход дешифратора б соответствующей ячейки и на вход .управляющего элемента И 5 устройства . соответственно.

Если в текущем такте среди признаков сортируемых слов найдется хотя 40 бы один с значением М, то на первом выходе дешифратора б ячейки анализа, где хранится слово с этим признаком, образуется разрешающий потенциал, который через первый элемент ИЛИ-НЕ 45

2 поступает на вход первого и всех последующих элементов И 9 группы всех ячеек в качестве запрещающего потенциала. Таким образом, единичный потенциал на входах элемента И 10 имеет место только в тех ячейках, в регистрах 8 которых хранится слово, значение признака которого равно М.

Единичный потенциал с выхода элемента ИЛИ 10 с поступлением ОчеРеднОГО импульса генератора 3 обеспечивает выдачу слова данной ячейки через выходные элементы И 7 потребителю и

- . через элемент И 11 - установку триггера 12 в единичное состояние, который, в свою. очередь, обеспечивает по- 60 дачу запрещающего потенциала с нулевого выхода 16 на управляющий вход дешифратора б,- исключив тем самым признак слова регистра 8 данной ячейки из сортировки в последующих тактах. 65

Если в текущем такте среди признаков сортируемых слов нет признаков с значением М, но есть с значением (M-1), то на выходе первого элемента

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

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

8 которой хранится слово с признаком (М-l), образуется единичный потенциал, который аналогично предыдущему случаю обеспечивает выдачу слова из регистра 8 потребителю и исключение . его признака из сортировки в последующих тактах и т.д.

Для прекращения процесса сортировки на второй вход 18 устройства подается сигнал "Остайов", который устанавливает триггер 4 запуска в единичное состояние, исключив тем самым возмож ость прохождения импульсов генератора 3 .через управляющий элемент И 5.

Для сортировки путем выделения слов. по возрастанию значений их приз наков необходимо на входы дешифратора б каждой ячейки подать инверсные выходы регистра 8. . Сопоставительный анализ предлагаемого и известного устройств показывает, что выигрыш в оборудовании от использования устройства составляет 15 и более процентов.

Формула изобретения

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

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

ИЛИ-НЕ, причем каждый i-ый выход каж960800

ВНИИПИ Заказ 7282/58 Тираж 731 Подписное

Филиал ППП "Патент, г. Ужгород, ул.Проектная; 4 дого k-ro узла анализа соединен с k-им входом i-го элемента ИЛИ-НЕ, а выход каждого i-го элемента ИЛИ-HE подключен к i-му входу блокировки всех ячеек анализа, каждая ячейка анализа дополнительно содержит элемен-5 ты ИЛИ, И, триггер, прнчем выход каждого j-го элемента И группы соединен с j-ым входом элемента ИЛИ, выход которого подключен к управляющему входу деииФратора и к первому входу 1О. элемента- И, выход которого соединен

Фо входом. установки в единичное состояние триггера, прямой вьиод кото рого подключен к.первым управляющим входам выходных элементов И группы, вход опроса ячейки анализа подключен ко вторым управляющим входам выход. ных элементов И группы и ко второму входу элемента И, вход установки в нулевое состояние триггера каждой . ячейки анализа соединен со входом запуска устройства, каждый i-ый вход блокировки ячейки анализа соединен с (i+1)-ми входами 1, 2, (n-i+1)-ro элементов И группы.

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

463968, кл, G Об Р 7/00, 1973 °

2. Авторское свйдетельство СССР

424141 кл ° G 06 F 7/00 1972 °

3. Авторское свидетельство СССР

9 590728, кл. G Об F 7/00, 1976 (прототип).