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

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК

4 (51) ОПИСАНИЕ ИЗОБРЕТ

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3665658/24 — 24 (22) 24. 11.83 (46) 23.04.85. Бюл. Ф 15

{72) Б.С. Бог. * и: ..:- .т, Г.Я. Яцук и С.В. Сычев (53) 681.325.5(088.8) (56) 1. Авторское свидетельство СССР

Ф 658569, кл. (; 06 Р 7/06, 1977.

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

N 928343, кл. С 06 F 7/06, 1980 (прототип) . (54) (57) 1. УСТРОЙСТВО ЛЛЯ СОРТИРОВ—

КИ ЧИСЕЛ, содержащее узел формирования границы, узел анализа результата, регистр, вычитатель, элемент ИЛИ элемент И, счетчик, дешифратор, группу элементов И и узел управления, включающий генератор импульсов, распределитель импульсов и элемент задержки, причем выходы регистра соединены с первой группой входов вычитателя, вторая группа входов которого подключе— на к информационным выходам узла формирования границы, вход запуска устройства подключен к входам элемента задержки и установки в исходное состояние распределителя импульсов узла управления,и входу установки в нулевое состояние счетчика, выход которого соединены с входами дешифратора, выходы которого соединены с информационными входами элементов И группы, управляющие входы которых подключены к выходу разрешения выдачи узла анализа результата, выход i-го элемента

И группы, где i-=1,2, ... N (ll — число групп сортировки), является i-м выходом устройства, выход элемента И является (И+1)-м выходом устройства

„„SU„„1151952 А и соединен с первым входом элемента

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

0 — к входу останова узла управления.

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

1151952

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

;последнего разряда, являются информационными выходами узла формирования границы, выход"последнего разряда — выходом конца интервала узла формирования границы, счетный вход счетчика — входом изменения узла формирования границы.

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных. 5

Известно устройство пля сортировки чисел, содержащее узел анализа результата, элементы И, счетчик, дешифратор, переключатель, элементы ИЛИ, элемент задержки, узел уп- 10 равления и генератор импульсов (1 7.

Его недостатки — невозможность задания различных значений ширины .групп сортировкн и низкое быстродействие. 15

Наиболее близким к предлагаемо— му по технической сущности и достигаемому результату является устройство для сортировки чисел, содержащее узел анализа результата, ре- 20 гистры, дешифратор, элементы И, ИЛИ, элемент задержки, распределитель импульсов, счетчик, элемент запрета, сумматор, группы элементов И, ИЛИ, переключатель, генератор, причем 25.выход первого регистра соединен с выходом узла анализа результата, первый выход которого подключен к первым входам элементов И первой группы и к первому входу первого элемента И, выход которого соединен с первой выходной шиной и с первым входом первого элемента ИЛИ, второй выход узла анализа результата подключен к первому входу второго элемента И, выход которого соединен с ин35 формационным входом счетчика, выходы которого подключены к входам дешифра3. Устроиство по п.1, о т л и ч а ю щ е е с я тем, что узел анализа результата содержит два элемента И и элемент HE причем информационный вход узла анализа результата соединен с первым входом первого элемента И и через элемент НЕ с первым входом второго элемента И, вторые входы элементов И подключены к входу опроса узла анализа результата, а выходы являются соответственно выходами разрешения выдачи и разрешения счета узла. анализа результата. тора, каждый i-й выход которого (где

i=1,2...,,n) соединен с вторым входом

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

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

1151952 второй группы сумматора, выходы первого регистра соединены с пнфор— мационными входами элементов И пя— той группы, выходы которых подключены к входам второй группы входов элементов ИЛИ третьей группы, первый и второй выходы распределителя импульсов соединены с управляющими входами элементов И второй и четвер— той групп соответственно, третий, четвертый и пятый выходы распределителя импульсов подключены к второму входу первого элемента И и к управляющим входам элементов И пятой и третьей групп соответственно(2 3.

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

Цель изобретения — расширение области применения устройства за счет обеспечения воэможности задания групп сортировки различной ширины.

25

Поставленная цель достигается тем, что в устройстве для сортировки чисел, содержащем узел формирова— ния границы, узел анализа результата, регистр, вычитатель, элемент ИЛИ, элемент И, счетчик, дешифратор, груп- З0 пу элементов И и узел управления, включающий генератор импульсов, распределитель импульсов и элемент задержки, причем выходы регистра соединены с первой группой входов вычи- 35 тателя, вторая группа входов которого подключена к информационным выходам узла формирования границы, вход запуска устройства подключен к входам элемента задержки и установки в ис- 40 ходное состояние. распределителя импульсов узла управления и входу установки в нулевое состояние счетчика, выходы которого соединены с входами дешифратора, выходы которого 45 соединены с информационными входами элементов И группы, управляющие входы которых подключены к выходу раЗрешения выдачи узла анализа результата, выход i-го элемента И группы, 50 где i=1, 2,...,N (N — число группы сортировки), является х-м выходом устройства, выход элемента И является (И+1)-м выходом устройства и соединен с первым входом элемента 5

ИЛИ, выход которого подключен к входу останова узла управления, информационные входы устройства соединены с установочными входами регистра,. адресные входы устройства подключены к входам узла формирования границы, выход конца интервала которого подключен к первому входу элемента И, а вход изменения адреса — к первому выходу распределителя импульсов, второй выход которого соединен с входом опроса узла анализа результата, информационный вход которого подключен к выходу знакового разряда вычитателя, выход разрешения выдачи узла анализа результата соединен с вторым входом элемента ИЛИ, а выход разрешения счета — со счетным входом счетчика и вторым входом элемента И, в узел управления введены триггер и элемент И, первый вход которого соединен с выходом генератора импульсов, вшход подключен к входу распределителя импульсов, а второй вход соединен с прямым выходом триггера, вход установки в единичное состояние ко торого подключен к выходу элемента задержки, а выход установки в "О" к входу останова узла управления.

Узел формирования границы содержит счетчик и блок памяти, причем входы узла формирования границы соединены с установочными входами счет- чика, выходы которого соединены с адресными входами блока памяти, информационные выходы которого, кроме последнего разряда, являются информационными выходами узла формирования границы, выход последнего разряда - выходом конца интервала узла формирования границы, а счетный вход счетчика — входом изменения адреса узла формирования границы.

Узел анализа результата содержит два элемента И и элемент НЕ, причем информационный вход узла анализа результата соединен с первым входом первого элемента И и через элемент

НЕ с первым входом второго элемента И, вторые входы элементов И подключены к входу опроса узла анализа результата, а выходы являются соответственно выходами Разрешения выдачи и разрешения счета узла анализа результата.

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

Устройство содержит узел 1 формирования границы, узел 2 анализа результата, узел 3 управления, ре1151952 гистр 4, вычнтатель 5, элемент ИЛИ 6, элемент И 7 счетчик 8, дешифратор 9, группу 10 элементов И, вход 11 .запуска, адресные входы 12, информационные входы 13 и выходы 14, 14„, 5

14 {, I4N+ . Узел 1 содержит счетчик 15 и блок 16 памяти. Узел 2 содержит элемент НЕ !7 и элементы И 18 и 19. Узел 3 содержит распределитель

20 импульсов, элемент И 21, элемент

22 задержки, триггер 23 и генератор 24 импульсов.

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

В блоке 16 памяти хранятся следую." щие последовательности кодов чисел.

И { „. (i{ (1 ф - 1 13

И{21 М(2/ И(21 о {

„{О . 20

° Ф „{1{9

И(ь{ .

{,и{

° ° ° ° ° ° ° ° °

{v J (к! (k{ (к>

M M . ° ° ° ° у M { {ó

1 1 и

25 где К вЂ, количество последовательнос({{ U) {i{ (1 тей И„М„, М,, ..., М„,, (1=1, К), т.е. К вЂ” это количество используемых вариантов разбиений отрезка (О, log(N+1)) числовой оси 30

Х на группы сортировки (имеются ввиду только целые числа; (N+1) — это количество выходов полного дешифратора 9, à log>(N+1) — это количество различных кодов, которые могут быть д записаны в счетчик 8);

M(1i- верхняя граница i-й (i=1

1 и@) группы сортировки j-го.(j=1, К) варианта разбиения;

И. 1 — нижняя граница i-й (i=1, 40

n(ii) группы сортировки j-го (j=1 ..., К) варианта разбиения; — количество групп сортировки в j-м (j=1, ..., К) варианте разбиения. для всех j " "1 не должно превос- 4 вИ ходить И.

Каждое число М . хранится в от1 дельной ячейке блока 16 памяти. Чис-. ла М({1 сопровождаются единицей в послвднем разряде каждой ячейки паI мяти; остальные же числа М(11 (8=0, ..., a -1) сопровождаются нулем, (j1»

Ф

Последовательность границ групп сортировки каждого варианта разбиения должна находиться в смежных ячей-5 ках памяти.

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

При включении питания триггер 23 устанавливается в нулевое состояние. (не показано).

Предположим, необходимо использовать р-й (p=i ..., К) вариант разбиения отрезка числовой оси на группы сортировки. При этом код числа (AP-1), где А р — адрес числа И, записывается в счетчик 15 по группе входов 12, Код числа Х, подлежащего сортировке, по группе входов 13 заносится в регистр 4.

Устоойство запускается в работу импульсом по входу 11. При этом обну ляется счетчик 8, распределитель 20 устанавливается .в исходное состояние (сигнал ни на одном из выходов не выдается). Этот же импульс с задержкой, необходимой дпя обнуления счетчика 8 и установки распределителя 20 в исходное состояние, поступает на единичный вход триггера 23, устанавливая последний в единичное состояние. Импульсы с выхода генератора 24 через открытый элемент И 21 начинают поступать на вход распределителя 20. По первому прошедшему импульсу он выдает импульс на своем первом выходе. При этом содержимое счетчика 15 увеличивается на единицу и становится равным Ар.

На выходах узла 1 появляется код

И . Вычитатель 5, выполненный на (Pi комбинационных элементах, осуществляет вычитание м(1 из содержимого регистра 4. На выходе вычитателя 5 присутствует знак этой разности, причем "0" соответствует неотрицательному числу, а "1" — отрицательному. Если Х-M{P1LO, то открывается элемент И 18. Если X-M ь 0, то от{Р) крывается элемент И 19. Затем появляется импульс на втором выходе распределителя 20, который проходит

{через один из элементов И 18 или 19.

Следовательно, если Х-M о (О, то от({1 крывается группа 10 элементов И и появляется сигнал на выходе 14О

"Брак-минус", соответствукнций содержимому счетчика S; если же Х—

И(40, то к содержимому счетчика 8 добавляется единица. Кроме того, если выполнено второе условие и в последнем разряде ячейки, содержащей И, находится единица (вариант (P) разбиения только одну точку), то появляется сигнал на выходе 14 { +„

Н

Брак-плюс". При появлении сигнала

7 1151 на выходе одного иэ элементов И 7 или

18 триггер 23 устанавливается в нулевое состояние, элемент И 21 закрывается и работа устройства для чисел Х и (А -1) прекращается ° 5

Если Х-Мо ЪО и M P не последняя (Pl ) граница варианта разбиения, то последний разряд ячейки памяти, со-, держащий Mô обнулен. Следовательно, работа устройства не прекращается. 10

По следующему импульсу на первом выходе распределителя 20 содержимое счетчика 15 увеличивается на единицу и становится равным (А +1). В результате этого на вторую группу вхо- 15 дов вычитателя 5 подается код М

Вычитатель 5 выдает код разности

Х-М „l. .В зависимости от кода знака этой разности и содержимого последнего разряда ячейки памяти, со- 20 держащей М 1 по следующему импульсу с второго выхода распределителя 20 могут выполняться следующие действия1 если х-M(„1 0 и последний разряд ячейки обнулен, то появляется им- 25 пульс на выходе элемента И 19 и содержимое счетчика 8 увеличивается на единицу и становится равным двум; если .Х-Мф(0 и последний разряд ячейки обнулен, то появляется импульс на выходе элемента И 18, в результате чего открывается группа

10 элементов И и появляется сигнал на выходе 14, соответствующем коду единицы в счетчике 8 и свидетельсч 35 вующем о том, что число Х принадлежит первой группе сортировки, а также появляется импульс на выходе элемента ИЛИ 6, который устанавливает триггер 23 в нулевое состояние, запрещая дальнейшее сравнение.

Если Х-М 0 и последний разряд

1,Pl ячейки установлен в единицу (ntP 1), 952 8 то появляется сигнал на выходе элемента И 7, который поступает на выход 14 „ "Брак-пл с" и обнуляет триггер 23; если Х-М 0 и последний разряд ячейки установлен в единицу (n(Pl=1), то появляется сигнал на выходе элемента И 18 (как и в случае, когда Х-M®<0 и последний разряд ячейки обнулен).

Следовательно, работа устройст— ва продблжается, как описано вышее, только при возникновении случая, когда Х-М 3 О и последний разряд ячейки обнулен.

При необходимости отсортировать по группам массив чисел требуется вновь записать в счетчик 15 по группе входов 12 (AP-1), а в регистр 4 по группе входов 13 — следующее число. В дальнейшем устройство работает аналогично описанному выше.

Положительный эффект от использования предлагаемого устройства заключается в следующем. При использовании известного устройства залаются M 0 и 4М где М вЂ” нижняя гра ница групп сортировки, а ЬМ вЂ” ширина групп сортировки. Следовательно, граница Мр=М +РдМ,, где 1" — целое положительное число. Очевидно, что ширина всех групп сортировки одинакова и равна М. Это сужает функциональные воэможности устройства

В предлагаемом устройстве явно задается и затем используется при сортировке каждая граница М„ ° Вследствие этого ширина каждой группы может быть любой. Таким образом, использование изобретения позволяет расширить область применения устройства ,за счет обеспечения возможности за1 дания групп сортировки различной ширины.

1151952 0 7

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

Редактор Е. Папп ТекредС.йовжий Корректор О. Тигор

Заказ 2324/37 Тираж 710 Подписное

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

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

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4