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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 801151952 А 4 (51) ОПИСАНИЕ ИЗОБРЕТН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ) и со зла управления, е с я тем, чт ста с личаю целью рас и С. (53) (56) В 65 ененпя рения оолас за счет ооеспеч дания групп сор ширины, информац ва соединены с и регистра, адр подключены к вх ия в устроистваможности зразличнойды устройс детельство СССР7/06, 1977.тельство СССР7/06, 1980 (про и вхоонн У 928 тотип ль ходьла ными входа устройства м интервала которого подключен к первому входу элемента И, а вход изме - нения адреса - к первому выходу распределителя импульсов, второй выход которого соединен с входом опроса узла анализа результата, информационный вход которого подключен к выходу знакового разряда вычитателя, выход разрешения выдачи узла анализа результата соединен с вторым входом элемента ИЛИ, а выход разрешения счета - со счетным входом счетчика и вторым входом элемента И, в узел управления введены триггер и элемент И, пер ый вход которого соединен с выходом генератора импульсов, выход в подключен импульсов с прямым тановки в од у распределителя ой вход соединен триггера, вход у ое состояние кот к выходу элемен ыход установки остаиова узла уп а вто ходом ини орого подклзадержки"0" - к вравления. ена та в 2. Устройство ч а ю щ е е с мирования гра о п отлчто узел форжит счетч и я теницы с ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ(54)(57) 1. УСТРОЙСТВО ЛЛЯ СОРТИРОВ -КИ ЧИСЕЛ, содержащее узел формирования границы, узел анализа результата,регистр, вычитатель, элемент ИЛИэлемент И, счетчик, дешифратор, группу элементов И и узел управления, включающий генератор импульсов, распределитель импульсов и элемент задержки,причем выходы регистра соединены спервой группой входов вычитателя, вто.рая группа входов которого подключена к информационным выходам узла формирования границы, вход запуска устройства подключен к входам элементазадержки и установки в исходное состояние распределителя импульсов узлауправления,и входу установки в нулевое состояние счетчика, выход которого соединены с входами дешифратора,выходы которого соединены с информационными входами элементов И группы,управляющие входы которых подключенык выходу разрешения выдачи узла анализа результата, выход -го элементаИ группы, где д=1,2 И (11 - число групп сортировки), является д-мвыходом устройства, выход элемента Иявляется (И+1)-м выходом устройства инен с первым входом элемента1151952 30 и блок памяти, причем входы узлаформирования границы соединены с установочными входами счетчика, выходыкоторого соединены с адреснымивходами блока памяти, информационные выходы которого, кроме;последнего разряда, являются информационными выходами узла формирования границы, выход"последнегоразряда - выходом конца интервалаузла формирования границы, счетныйвход счетчика - входом измененияузла формирования границы. Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных. 5Известно устройство для сортировки чисел, содержащее узел анализа результата, элементы И, счетчик, дешифратор, переключатель, элементы ИЛИ, элемент задержки, узел уп О равления и генератор импульсов 1.1 1.Его недостатки - невозможность задания различных значений ширины групп сортировкИ и низкое быстродействие. 15Наиболее близким к предлагаемому по технической сущности и достигаемому результату является устройство для сортировки чисел, содержащее узел анализа результата, ре гистры, дешифратор, элементы И, ИЛИ,элемент задержки, распределитель импульсов, счетчик, элемент запрета сумматор, группы элементов И, ИЛИ, переключатель, генератор, причем 25 выход первого регистра соединен с выходом узла анализа результата, первый выход которого подключен к первым входам элементов И первой группы и к первому входу первого элемента И, выход которого соединен с первой выходной шиной и с первым входом первого элемента ИЛИ, второй выход узла анализа результата подключен к первому входу второго элемента И, выход которого соединен с ин 35 формационным входом счетчика, выходы которого подключены к входам дешифра 3. устройство по п.1, о т л и ч а ю щ е е с я тем, что узел анализа результата содержит два элемента И и элемент НЕ, причем информационный вход узла анализа результата соединен с первым входом первого элемента И и через элемент НЕ с первым входом второго элемента И, вторые входы элементов И подключены к входу опроса узла анализа результата, а выходы являются соответственно выходами разрешения выдачи и разрешения счета узла анализа результата,тора, каждый 1.-й выход которого (где1=1,2 п) соединен с вторым входом1-го элемента И первой группы и спервым выводом 1-го переключателя,выход каждого 1-го элемента И первойгруппы и второй вывод -го переключателя подключены к первому и второмувходам соответственно х-го элементаИЛИ первой группы, выход каждого изкоторых соединен с (1+1)-м входом.первого элемента ИЛИ, выход которогоподключен к входу управления элементазапрета, выход которого соединен свходом генератора, выход которого подключен к входу распределителя импульсов, вход управления устройства соединен с входом установки в нулевое состояние счетчика и распределителя импульсов, с первым входом третьегоэлемента И и через элемент задержкис входом элемента запрета, выходывторогои третьего регистров подключены к информационным входам элементов второй и третьей групп соответственно, выходы которых соединены свходами элементов ИЛИ второй группы,выходы которых соединены с входамипервой группы сумматора, выходы которого подключены к информационным входам элементов И четвертой группы,информационные входы устройства соединены с информационными входамиэлементов И пятой группы, выходы которых подключены к входам первойгруппы входов элементов ИЛИ третьей группы, выходы которых соединеныс входами четвертого регистра, выходы которого подключены к входам1 О Поставленная цель достигается тем, что в устройстве для сортировки чисел, содержащем узел формирования границы, узел анализа результата, регистр, вычитатель, элемент ИЛИ, элемент И, счетчик, дешифратор, груп. ЗО пу элементов И и узел управления, включающий генератор импульсов, распределитель импульсов и элемент задержки, причем выходы регистра соединены с первой группой входов вычи тателя, вторая группа входов которого подключена к информационным выходам узла формирования границы, вход запуска устройства подключен к входам элемента задержки и установки в ис ходное состояние. распределителя импульсов узла управления и входу установки в нулевое состояние счетчика, выходы которого соединены с входами дешифратора, выходы которого 45 соединены с информационными входами элементов И группы, управляющие входы которых подключены к выходу разрешения выдачи узла анализа результата, выход -го элемента И группы, 50 где =1, 2. И (И - число группы сортировки), является х-м выходом устройства, выход элемента И является (И+1)-м выходом устройства и соединен с первым входом элемента 55 ИЛИ, выход которого подключен к вхо" ду останова узла управления, информационные входы устройства соединевторой группы сумматора, выходы первого регистра соединены с информационными входами элементов И пятой группы, выходы которых подключены к входам второй группы входов элементов ИЛИ третьей группы, первый и второй выходы распределителя импульсов соединены с управляющими входами элементов И второй и четвертой групп соответственно, третий, четвертый и пятый выходы распределителя импульсов подключены к второму входу первого элемента И и к управляющим входам элементов И пятой и третьей групп соответственно 2 3.Недостатком известного устройства является невозможность задания различных значений ширины групп ,сортировкиЦель изобретения - расширение 20 области применения устройства за счет обеспечения воэможности задания групп сортировки различной ширины. ны с установочными входами регистра,. адресные входы устройства подключены к входам узла формирования границы, выход конца интервала которого подключен к первому входу элемента И, а вход изменения адреса - к первому выходу распределителя импульсов, второй выход которого соединен с входом опроса узла анализа результата, информационный вход которого подключен к выходу зцакового разряда вычитателя, выход разрешения выдачи узла анализа результата соединен с вторым входом элемента ИЛИ, а выход разрешения счета - со счетным входом счетчика и вторым входом элемента И, в узел управления введены триггер и элемент И, первый вход которого соединен с выходом генератора импульсов, вшход подключен к входу распределителя импульсов, а второй вход соединен с прямым выходом триггера, вход установки в единичное состояние которого подключен к выходу элемента задержки, а выход установки в "0" к входу останова узла управления.Узел формирования границы содержит счетчик и блок памяти, причем входы узла формирования границы соединены с установочными входами счет- чика, выходы которого соединены с адресными входами блока памяти, информационные выходы которого, кроме последнего разряда, являются информационными выходами узла формирования границы, выход последнего разряда - выходом конца интервала узла формирования границы, а счетный вход счетчика - входом изменения адреса узла формирования границы.Узел анализа результата содержит два элемента И и элемент НЕ, причем информационный вход узла анализа результата соединен с первым входом первого элемента И и через элемент НЕ с первым входом второго элемента И, вторые входы элементов И подключены к входу опроса узла анализарезультата, а выходы являются соответственно выходами Разрешения выдачи и разрешения счета узла анализарезультата.ВНа чертеже приведена схема устройства.Устройство содержит узел 1 формирования границы, узел 2 анализа результата, узел 3 управления, ре 1151952гистр 4, вычнтатель 5, элемент ИЛИ 6,элемент И 7, счетчик 8, дешифратор 9,группу 10 элементов И, вход 11 .запуска, адресные входы 12, информационные входы 13 и выходы 14 , 14, 514), 14)+ь. Узел 1 содержитсчетчик 15 и блок 16 памяти . Узел 2 содержит элемент НЕ 7 и элементы И 18и 19, Узел 3 содержит распределитель20 импульсов, элемент И 21, элемент1 О22 задержки, триггер 23 и генератор 24 импульсов,Устройство предназначено для разбраковки (сортировки) изделий нагруппы по их характеристикам, представленным кодовыми значениями,В блоке 16 памяти хранятся следую"щие последовательности кодов чисел,(1), 20 ьи" М(ц . И)(и) (к (к) (к)ММ, М, М(и25где К в , количество последовательнос( И О)тей Мо 1 М М (, (Д=1,К), т.е. К - это количествоиспользуемых вариантов разбиенийотрезка (О, 1 од(И+1 числовой оси 30на группы сортировки (имеются ввидутолько целые числа;(И+1) - это количество выходов полного дешифратоРа 9, а 1 о 8 е(И+1) - это количестворазличных кодов, которые могут быть Ззаписаны в счетчик 8);М(- верхняя граница 1-й (1=11и( группы сортировки )-го (3=1,К) варианта разбиения;М,) - нижняя граница 1-й (1=1, 4 Ои( группы сортировки 3-гоЦ=1, , К) варианта разбиения;1 - количество групп сортировкив 3-м (3=1. . . К) варианте разбиения. Для всех 3 " " не должно превос фоИходить И.Каждое число М .1 хранится в отдельной ячейке блока 16 памяти. Чис-.ла Н(, сопровождаются единицей впослвднем разряде каждой ячейки памятиу остальные же числа М( (К=О,, и -1) сопровождаются нулем,Ц) ъеПоследовательность границ группсортировки каждого варианта разбиения должна находиться в смежных ячей ках памяти.Устройство работает следующимобразом. При включении питания триггер 23 устанавливается в нулевое состояние. (не показано).Предположим, необходимо использовать р-й (р=1, , К) вариант разбиения отрезка числовой оси на группы сортировки, При этом код числа (АР), где Ар - адрес числа М, записывается в счетчик 15 по группе входов 12, Код числа Х, подлежащего сортировке, по группе входов 13 заносится в регистр 4.Устоойство запускается в работу импульсом по входу 11, При этом обнуляется счетчик 8, распределитель 20 устанавливается .в исходное состояние (сигнал ни на одном из выходов не выдается). Этот же импульс с задержкой, необходимой дпя обнуления счетчика 8 и установки распределителя 20 в исходное состояние, поступает на единичный вход триггера 23, устанавливая последний в единичное состояние. Импульсы с выхода генератора 24 через открытый элемент И 21 начинают поступать на вход распределителя 20. По первому прошедшему импульсу он выдает импульс на своем первом выходе. При этом содержимое счетчика 15 увеличивается на единицу и становится равным АР, На выходах узла 1 появляется код М , Вычитатель 5, выполненный на(Р)комбинационных элементах, осуществля. ет вычитание М( ) из содержимого регистра 4, На выходе вычитателя 5 присутствует знак этой разности, причем 0" соответствует неотрицательному числу, а1" - отрицательному. Если Х-М(Р)дЭ, то открывается элемент И 18. Если Х-М ь ъО, то от(Р)крывается элемент И 19. Затем появляется импульс на втором выходе распределителя 20, который проходит )через один из элементов И 18 или 19, Следовательно, если Х-М о (О, то от(Р)крывается группа 10 элементов И и появляется сигнал на выходе 14 О "Брак-минус", соответствукнций содержимому счетчика 8; если же Х - МфЬО, то к содержимому счетчика 8 добавляется единица. Кроме того,если выполнено второе условие и впоследнем разряде ячейки, содержащей М , находится единица (вариант(Р)разбиения только одну точку), топоявляется сигнал на выходе 14 к)+1НБрак-плюс". При появлении сигнала7 1151 на выходе одного иэ элементов И 7 или 18 триггер 23 устанавливается в нулевое состояние, элемент И 21 закрывается и работа устройства для чисел Х и (АР) прекращается. 5Если Х-М 0 ЪО и М 0 Р не последняя(Р )граница варианта разбиения, то последний разряд ячейки памяти, со-, держащий Мф обнулен. Следовательно, работа устройства не прекращается.1 О По следующему импульсу на первом выходе распределителя 20 содержимое счетчика 15 увеличивается на единицу и становится равным (АР+1). В результате этого на вторую группу вхо дов вычитателя 5 подается код М Вычитатель 5 выдает код разности Х-М(1. В зависимости от кода знака этой разности и содержимого последнего разряда ячейки памяти, со О держащей Мф 1, по следующему импульсу с второго выхода распределителя 20 могут выполняться следующие действия 1 если х-м(10 и последний разряд ячейки обнулен, то появляется им пульс на выходе элемента И 19 и содержимое счетчика 8 увеличивается на единицу и становится равным двум; если Х-Мф(0 и последний разряд ячейки обнулен, то появляется импульс на выходе элемента И 18, в результате чего открывается группа 10 элементов И и появляется сигнал на выходе 14, соответствующем коду единицы в счетчике 8 и свидетельсч вующем о том, что число Х принадлежит первой группе сортировки, а также появляется импульс на выходе элемента ИЛИ 6, который устанавливает триггер 23 в нулевое состояние, запрещая дальнейшее сравнение, Если Х-М70 и последний разряд1 Р 1ячейки установлен в единицу МР 1),952 8то появляется сигнал на выходе элемента И 7, который поступает навыход 14 я"Брак-плс" и обнуляеттриггер 23; если Х-М Р 0 и последний разряд ячейки установлен в единицу (п(Р 1=1), то появляется сигнална выходе элемента И 18 (как и вслучае, когда Х-М(0 и последнийразряд ячейки обнулен),Следовательно, работа устройст -ва продолжается, как описано вьппе,только при возникновении случая,когда Х-М 1 Ъ О и последний разрядячейки обнулен,При необходимости отсортироватьпо группам массив чисел требуетсявновь записать в счетчик 15 по группе входов 12 (АР), а в регистр 4по группе входов 13 - следующее число. В дальнейшем устройство работает аналогично описанному вьппе,Положительный эффект от использования предлагаемого устройствазаключается в следующем, При использовании известного устройства залаются М 0 и 4 М где М нижняя граница групп сортировки, а ЬМ - ширина групп сортировки. Следовательно,граница МР=М+ГдМ где 1" - целоеположительное число. Очевидно, чтоширина всех групп сортировки одинакова и равна М. Это сужает функциональные воэможности устройствя.В предлагаемом устройстве явно задается и затем используется при сортировке каждая граница МВследствие этого ширина каждой группы можетбыть любой. Таким образом, использование изобретения позволяет расширить область применения устройства,за счет обеспечения возможности за 1дания групп сортировки различной ширины.1151952 Составитель Е, Ивановадактор Е. Папп ТекредС.Йовжий Коррек Тигор каз 2324 исноеСР ВНИИПИ по д3035,Филиал ППП "Патент", г. Ужгор ул. Проектная, 4 од,ираж 710осударственноам изобретениисква, Ж, Р Под омитета С открытий кая наб.,