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

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

Иллюстрации

Показать все

Реферат

 

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