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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциали:тическихРеспублик пп 928343(22) Заявлено 250480 (21) 2942058/18-24с присоединением заявки Мо(51 М. Кл.з 6 06 Р 7/06 Государственный комитет СССР по делам изобретений и открытий. 5 (0888)4 Дата опубликования описания 150582 Э.П. Чернаков, В,М. Цыганков и Б.С. ВогумирсКий(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ Изобретение относится к автомати.ке и вычислительной технике и можетбыть использовано для разбраковкииз группы изделий по их характеристикам,. представленным кодовыми значениями.Известно устройство для сортировки чисел, содержащее два счетчика,блок сравнения, дешифратор, два переключателя, блок управления, генератор, элементы И, ИЛИ, элемент задержки, причем выходы первого счетчика подключены к первой группевходов блока сравнения, вторая группа входов которого подключена к выходам первого переключателя, выходблока управления соединен с входомгенератора, выход которого подключен к управляющему входу первогосчетчика, выходы второго счетчикасоединены со входами дешифратора,входы установки в нулевое состояние счетчиков подключены к шинеуправления 1,Недостатками этого устройстваявляется то, что оно обеспечиваетустановку ширины группы только кратной числам 2, 4, 8 в нем отсутствует возможность задания раз-.личного количества групп сортировки. Кроме того, оно обладает низким быстродействием. 5 Наиболее близким по техническойсущности к предлагаемому является устройство, содержащее схему анализа, первый клапан, счетчик, дешифратор, первую группу клапанов, переключатель, первую группу элементов ИЛИ, элемент ИЛИ, элемент задержки, блок управления и генератор импульсов, управляющий вход которого подключен к выходу блока управления, запрещающий вход которого соединен с выходом элемента ИЛИ, входы которого, кроме одного, подключены к выходам первой группы элементов ИЛИ, являющимся выходами устройства, первые входы первой группы элементов ИЛИ соединены с выходами первой группы клапанов, первый выход схемы анализа через первый клапан подключен к выходу устройства, вход установки в нуль счетчика соединен с управляющим входом устройства, а выход - со входом дешифратора, выходы которого подключены ко входам первой. группы клапанов, а через переключатель - ко вторым входам первой группы элементов ИЛИ 2), 928343Недостатком этого устройства является низкое быстродействие, так как число тактов. работы устройства при определении попадания заданного числа в 6 сакую-нибудь группу растет с увеличением ширины, групп сортировки.Цель изобретения - повышение быстродействия устройства.Эта цель достигается тем, что в устройстве для сортировки чисел, содержащем узел анализа результата, регистры, дешифратор, элементы И, ИЛИ, элемент задержки, распределитель импульсов, счетчик, элемент запрета, сумматор, группы элементов, И, ИЛИ, переключатель, генератор, причем выход первого регистра соединен со входом узла анализа результата, первый выход которого подключен к первым входам элементов И первой группы и к первому входу первого элемента И, выход которого соединен с первой выходной шиной и с первым входом первого элемента ИЛИ, второй выход узла анализа результата подключен к первому входу второго элемента, выход которого соединен с информационным входом счетчика, выходы которого подключены ко входам дешифратора, каждый 1-ий выход которого (где .1 = 1,2,п) соединен со вторым входом 1-го элемента И. первой группы и с первым выходом 1-го переключателя, выход каждого 1-го элемента И первой группы и второй выход 1-го переключателя подключены к первому и второму входам сортветственно 1-го элемента ИЛИ первой группы, выход каждого из которых соедийен с (.+1) -ым входом.первого элемента ИЛИ, выход которого подключен к. входу управления элемента запрета, выход которого соединен с входом генератора, выход которого подключен к входу распределителя импульсов, вход управления уст" ройства соединен с входом установки в нулевое состояние счетчика и распределителя импульсов, с первым вхо" дом третьего элемента И и через .элемент задержки - с входом элемента запрета, выходы второго и третьего регистров подключены к информационным входам элементов И второй и третьей групп соответственно, выходы которых соединены с входами элементов ИЛИ второй группы, выходы которых соединекы с входами первой группы сумматора, выходы которого подключены к информационным входам элементов И четвертой группы, информационные входы устройства соединены с йнформационными входами эЛемента И пятой группы, выходы котовых подключены к входам первой группы входов элементов ИЛИ третьей группы, выходы которых соединены с входами четвертого регистра, выходы которогоподключены к входам второй группысумматора, выходы первого регистрасоединены с информационными. входамиэлементов И, пятой группы, выходыкоторых подключены к входам второйгруппы входов элементов ИЛИ третьейгруппы, первый и второй выходыраспределителя импульсов соединены10 с управляющими входамк элементов Ивторой и четвертой групп соответственно, третий, четвертый и пятыйвыходы распределителя импульсов подключены к второму входу первого эле 15 мента И и к управляющим входам элементов И пятой и третьей групп соответственно.На чертеже представлена блок-схема устройства.20 Устройство содержит узел анализа,результата 1, элемент И 2, счетчик3, дешифратор 4, группу элементовИ 5, переключатель 6, группу элементов ИЛИ 7, элемент ИЛИ 8, эле 25 мент 9 задержки, элемент 10 запрета,генератор 11, распределитель 12 импульсов, регистр 13, сумматор 14,регистры 15-17, группу элементовИ 18, группу Элементов ИЛИ 19, элемент И 20, группы элементов И 21-24,элемент И 25, вход 26 управления,информационные входы 27-29, выходы3030 30 устройств, выходы31,32,35 распределителя.Устройство работает следующимофдаз ом.Перед началом работы устройствапо группам входов 27 и 28 на ре-,гистры 17 и 16 записываются соответ 40 ственно значения ЬМ и М, где ь М -задаваемая ширина групп сортировки,а Мо - задаваемая нижняя границагрупп сортировки. Нри помощи переключателя 6 устанавливается необхо 45 димое число групп сортировки (от 0до И) без учета группы Бракминус, Под действием сигнала навходе устройства 26 код числа Х,поступающий на группу входов устройства 29, записывается",в приемный регистр 13, счетчик 3 устанавливаетсяв нулевое состояние, а распределитель 12 импульсов - в исходное. Снекоторой задержкой, необходимойдля установки схемы в исходное положение и приема Х на регистр 13,этот.сигнал проходит через элемент 9 задержки на разрешающий вход элемента10 запрета, По сигналу от блока 10.Управления запускается генератор 1160 импульсов, с его выхода импульсы поступают на вход распределителя 12 импульсов, который распределяет их цо управляющим точкам устройства, Первый импульс появляется на выходе65 31 и открывает группу клапанов 22.Сумматор 14 вычисляет значение Х-М . Второй импульс с выхода 32 распределителя 12 импульсов открывает груп- пу элементов И 23 и значение Х-Мо принимается в регистр 15 результата. .Из него значение Х-Мо поступает в узел анализа результата 1. Если ре 5 зультат вычитания не больше нуля, то сигнал появляется на верхнем выходе узла анализа результата 1, в противном случае - на нижнем. Ймпульс на выходе 33 распределителя импульсов открывает элемент И 2 и если Х-МО, то на.выходе устройства 30 - 0 появляется сигнал, свидетельствующий о попадании значения Х в нулевую группу сортировки Брак минусф. Следующий импульс появляет,ся на выходе 34 распределителя импульсов 12 и открывает группу эле.ментов И 24 и элемент И 25. Если Х-Мо) О, то к содержимому счетчика 20 добавляется единица и появляется сигнал на следующем выходе дешифратора (в .данном случае - на первом). Код из регистра 15 результата заносится в регистр 13. Импульсом на 25 выходе 35 распределителя 12 импульсов открывается группа элементов И 21 и на выходах сумматора 14 появляется значение Х-Мо-ьМ. В дальнейшем работа устройства происходят аналогично под действием импульсов, периодически появляющихся на выходах 32, 34, 35 распределителя 12 импульсов. Необходимо помнить, что элемент И 2 открывается только в35 нервом цикле работы устройства.Когда содержимое регистра 15 реОзультата становится меньше либо равно нулю, на верхнем выходе схемы анализа 1 появляется сигнал, который поступает на управляющий вход груп пы элементов И 5. Сигнал, имеющийся на одном из выходов дешифратора 4, проходит через соответствующие элементы И 5 группы и элемент ИЛИ группы элементов ИЛИ 7 на соответ ствующий выход устройства, свидетельствуя о принадлежности значения к данной группе сортировки, Если на вход клапана на группы элементов И 5, соответструющего установленной переключателем б перемычки, от дешифратора 4 поступает сигнал, то он проходит через соответствующий элемент ИЛИ из группы элементов ИЛИ 7 на соответствующий выход устройства, свидетельствуя о попадании значения Х к группе Брак-плюс. Появляющийся на одном из выходов устройства 30 сигнал проходит через элемент ИЛИ 8 на запрещающий вход 0 узла 10 запрета,. который останавливает генератор 11 импульсов. Работа устройства прекращается.Использование предлагаемогоУСтройства позволяет повысить быст родействие устройства, так как определение попадает ли заданное.число в данную группу, происходит за 3 такта работы устройства после проверки предыдущей группы, в известном устройстве число тактов растет с увеличением ширины групп сортировки.Формула изобретенияустройство для сортировки чисел, содержащее узел анализа результата, регистры, дешифратор, элементы И, ИЛИ, элемент задержки, распределитель импульсов, счетчик, элемент запрета, сумматор, группы элементоя И,ИЛИ, переключатель, генератор,причем выход первого регистра соединен с входом узла анализа результата, первый выход которого подключен к первым входам элементов И первой группы. и к первому входу первого элемента И, выход которого соединен с первой выходной шиной и с первым входом первого элемента ИЛИ, второй выход узла анализа результата подключен к первому входу всорого элемента И, выход которого соединен с информационным входом счетчика выходы которого подключены к входам дешифратора, каждый (. -й выход которого (где= 1,2п) соединен с вторым входом -го элемента И первой группы и с первым выводом-го переключателя, выход каждого-го элемента И первой группы и второй вывод;го переключателя. подключены к первому и второму входам соответственно-го элемента ИЛИ первой группы, выход каждого из которых соединен с +1)-ым входом первого элемента ИЛИ, выход которого подключен к входу управления элемента запрета, выход которого соединен с входом генератора, выход которого подключен к входу распределителя импульсов, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в нем вход управления устройства соединен с входом установки в нулевое состояние счетчика и распределителя импульсов, с первым входом третьего элемента И и через элемент задержки с входом элеМента запрета, выходы вторбго и гретьего регистров подключены к информационным входам элементов И второй и третьей групп соответственно, выходы которых соединены с входами элементов ИЛИ второй группы, выходы которых соединены с входами первой группы сумматора, выходы которого подключены к информационным входам элементов И четвертой группы, информационные входы устройства соедине" ны с информационными входами.элементов И пятой группы, выходы которых подключены к входам первой груп928343 27 28 тираж 732 Подписн ИИПИ Эакаэ 3241 Проектная, 4 ФиЛиал ППП "Патент Ужго пы входов элементов ИЛИ третьейгруппы, выходы которых соединены свходами четвертого регистра, выходыкоторого подключены к входам второйгруппы сумматора, выходы первогорегистра соединены с информационнымивходами элементов И пятой группы,выходы которых подключены к входамвторой группы входов. элементов ИЛИтретьей группы, первый и второй выходы распределителя импульсов соединены с управляющими входами элементов И второй и четвертой групп соответственно, третий, четвертый и пятый выходы распределителя импульсовподключены к второму входу первогоэлемента И и к управляющим входамэлементов И пятой и третьей группсоответственно.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРМ 249764, кл, С 06 Р 7/00, 1967. 0 2. Авторское свидетельство СССРР 658569, кл. С 06 Г 7/06, 1977