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

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

Иллюстрации

Показать все

Реферат

 

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

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

РЕСПУБЛИК

g i) G 06 F 7/06

ОПИСАНИЕ ИЗОБРЕП.:НИ

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3354592/18-24 (22) 20.11.81 (46) 23.06.83. Бюл. ¹ 23 (72) В. М. Цыганков и Э.П. Чернаков (53) 681,325,66 (088.8) . (56) 1. Авторское свицетельство СССР

Ж 658559, кл. G 06F 7/06, 1977.

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

IIo заявке Ж 2942058/24, кл. G 06F 7/06, 1980 (прототип). (54) (57) УСТРОЙСТВО ДЛЙ СОРТИРОВКИ ЧИСЕЛ, соцержашее узел ана лиза результата, регистры, цешифратор, первый и второй элементы И, первый элемент ИЛИ, элемент зацержки, первый распрецелитель импульсов, счетчик, узел запрета, сумматор, группы элементов И, ИЛИ, переключатель, генератор, причем выхоцы первого и второго регистров со ецинены с первыми вхоцами элементов И первой и второй групп. соответственно, BbIxoabI которых соединены с первыми вхоцами элементов ИЛИ первой группы, информационные вхоцы устройства соединены с первыми вхоцами элементов И третьей группы, Bblxoabl которых соедине ны с первыми входами элементов ИЛИ второй группы, вторые входы которых поцключены K выходам элементов И четвер той группы, а выхоцы соецинены с уста новочными цхоцами третьего регистра, выходы которого соединены с первой груп пой входов сумматора, первый выхоц узла анализа результата соединен с первыми входами элементов И пятой группы, с первым входом первого элемента И, выход которого является первым выходом устройства и соецинен с первым входом первого элемента ИЛИ, второй выхоц узла анализа результата соединен с первым

„„SU„„1024903 А

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

solo элемента ИЛИ, выход которого сое»

asses с первым входом узла запрета, вход < управления устройства соецинен с входом установки s нулевое состояние счетчика и первого распрецелителя импульсов, вторым аховом узла запрета, о вторыми вхопами С элементов И третьей группы и входом

Фа элемента зацержки, выхоц которого сое- ». динен с третьим входом узла запрета, выход которого соединен с управляюшим вхоцом генератора, первый и второй выхо цы первого распределителя импульсов соецинены с вторыми входами элементов И соответственно первой и второй групп, третий выход первого распрецели» теля импульсов соединен с вторым входом первого элемента И, о т л и ч а ю m e е с 5f тем, что, с целью повьппения

Са7

6ыстродействия, в него ввецены третий и четвертый элементы И, триггер, второй распределитель импульсов, второй и тре» фф тий элементы ИЛИ и четвертый регистр, установочные входы которого соецинены с выходами элементов ИЛИ первой груп» пы, а выходы - с второй группой входов сумматора, инверсные выходы которого соецинены с группой входов узла анали1024903 за результата и с первыми вхоцами эле-, ментов .И четвертой группы, знаковый вы»

xotl сумматора соединен с входом знака анализатора, выход генератора соединен с первыми входами третьего и четвертого элементов И, вторые вхоцы которых под ключены соответственно к нулевому и еаиничному выходам триггера, выходы третьего и четвертого элементов И сое цинены с входами первого и второго рас пределителя импульсов соответственно, нулевой вход триггера подключен к вхоцу установки в нулевое состояние второго

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

Известно устройство цля сортировки чисел, соцержащее блок сравнения, два счетчика переключатели,.аепитель час

/ тоты, дешифратор, генератор, блок управ пения, элементы И, ИЛИ и элемент за- щ цержки С 1 J °

Однако устройство обеспечивает уста новку ширины группы только кратной числам 2, 4, 8..., в нем отсутствует воз-. можнОсть задания раэпичнОГО кОличества групп сортировки, и оно облацает низким быстродействием.

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

Недостатком цанного устройства является низкое быстроцействие, так как ра ботой устройства управляет расйреаелитель импульсов, имеющий пять выхоцов, причем в процессе работы устройства (эа исключением первого цикла) использу» ются лишь три выхоца распределителя импульсов, а ава другие не используются.

Бейзтвительно, при вычитании чисел, ha хоцящихся в регистрах устройства, йояв распределителя импульсов и i вхоцу.управ пения устройства, ециничный вход тригге ра поцключен к первому выходу первого распредели теля импульсов, четвертый и пятый выхоцы которого подключены к первым входам второго и третьего элемен тов ИЛИ соответственно, вторые вхоцы которых соецинены с первым и вторым выхоцами второго распределителя импульсов соответственно, а выхоцы - с управляющими вхоцами элементов И чет вертой группы и второго элемента И соответственноо.

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

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

1 чены к выхоцам элементов И четвертой

I группы„а выхоцы соецинены с устано ночными вхоцами третьего регистра, выхоцы которого соединены с первой группой входом сумматора,- первый выхоц, узла анализа результата соецинен с первыми входами элементов И пятой группы и с первым входом первого элемента И, выход которого является первым выходом устройства и соединен с первым вхоцом

3 10249 первого элемента ИЛИ, второй выход узла анализа результата соецинен с первым вхоцом второго элемента И, выхоп кото рого соецинен со счетным входом счетчика> выходы которого соединены с вхоцами 3 цешифратора, кажцый i -й выхоц которого, гце 1 = 1,2,..., р, соединен с вторым входом элемента И пятой группы и с первым вывоцом 1- го переключателя, выхоц каждого 1-го элемента И пятой группы и второй вывод1-го переключателя соецинены с первым и вторым вхопами соот» ветственно -го элемента ИЛИ третьей группы, выход кажцого иэ которых явля

15 ется соответственно (1+1}м выхоцом устройства и соединен с (+1)-м входом первого элемента ИЛИ, выход которого соецинен с первым входом узла запрета, вход управления, устройства соецинен с входом установки в нулевое состояние

20 счетчика и первого распрецелителя импульсов, вторым вхоцом узла запрета, с вторыми вхоцами элементов И третьей группы и вхоцом элемента зацержки, вы23 хоп которого соецинен с третьим вхоцом узла запрета, выход которого соецинен с улравляюшим вхоцом генератора,,первый и второй выхоцы первого раслрецелителя импульсов соецинены с вторыми вхоцами элементов И соответственно первой и второй групп, третий выход первого распределителя импульсов соецинен с вторым входом первого элемента И, ввецвны третий и четвертый элементы И, триггер, второй распрецелитель импульсов, второй 3$ и третий элементы ИЛИ и четвертый регисгр, установочные вхоцы которого совцинены с sblxollBMH элементов ИЛИ пер вой группы, а выхоцы - с второй группой вхоцов сумматора, инверсные вьгхопы 40 разрядов которого соединены с группой вхоцов узла анализа результата и с первыми входами элементов И четвертой группы, знаковый выхоп сумматора соецинен с вхоцом знака анализатора, выхоц З генератора соединен с первыми вхопами третьего и четвертого элементов И, вторые входы которых подключены соответственно к нулевому и единичному выхоцам триггера, выхоцы третьего и четвертого элементов И соединены с вхоцами первого и второго распрецелитвля импульсов соответственно, нулевой вхоц триггера подключен к входу установки в нулевое состояние второго распределителя импульсов и к вхоцу управления устройства, ециничный вход триг гера попключен к первому выхоцу перво го распределителя импульсов, четвертый

03 4 и пятый выходbl которого лоцключены к первым sxoaaM второго и третьего эле ментов ИЛИ соответственно, вторые вхо .ды которых соепинены с первым и вторым выходами второго распрвцелителя импуль сов соответственно, а выходы с управ ляюшими вхопами элементов И четвертой группы и второго элемента И соотвеъ» отвеяно, На фиг. 1 привепена схема устройства на фиг. 2 - схема узла анализа результа у та; на фиг. 3 - схема узла запрета.

Устройство содержит узел 1 анализа результата, регистры 2 - 4, цешифра» тор 5, элементы ИЛИ 8, элемент 9 за» держки, распределитель 10 импульсов, счетчик 11, элемент 12 запрета, сум» матор 13, группы элементов И 14 - 18, группы элементов ИЛИ 19 - 21, перек» лючатель 22, генератор 23, информацион ные входы 24 - 26, вход 27 управле ния, выходы 28 О, 28-1,,..., 28-л, элементы И 29 и 30, триггер 31, распре» целитель 32 импульсов, элементы ИЛИ ЭЗ и 34, регистр 35, выхоцы 36» 40 рас» пррпелителя 10 импульсов.

Узел 1 анализа результата содержит многовхоцовой элемент И 41, эле мент ИЛИ 42 и элемент НЕ 43, вхоц 44 знака, группы входов 45, первый 46 и второй 47 выходы, причем первый вход элемента ИЛИ 42 является вхоцом знаga 44 анализатора, второй вход эле« мейта ИЛИ 42 поцключвн к выхоцу многовхоцового элемента И 41, вхоцы кото» рого являются группой вхоцов 45 анали затора, выход элемента ИЛИ 42 являет ся первым выходом 46 анализатора и сов» динен с вхоцом элемента НЕ 43, выход которого является вторым выхоцом 47 анализатора.

Узел 12 запрета содержит триггер 48 и элемент ИЛИ 49, причем первый и вто рой вхоцы элемента ИЛИ 49 и вциничный вход триггера 48 являются соотввтстввн но первым 50, вторым 51 и третьим 52 входами узла, выход элемента ИЛИ 49 соепинен с нулевым вхоцом триггера 48, единичный выход которого является выходом 53 узла.

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

Перец началом работы устройства ло группам входов 24 и 25 в регистры 2 и 3 записываются соответственно значв5 10249 ния ЬМ и М „где 6.М - задаваемая ширина групп сортировки, а Мо - задана» емая нижняя граница групп сортировки, При помоши переключателя 22 устанавли вается необходимое число групп сортиров» > ки (от 0 до и-1) без учета группы "бракминус". Под действием сигнала на входе 27 устройства код числа Х, поступаю ший на группу входов 26 устройства, записывается в приемный регистр 4, счетчик 11 и триггер 31 устанавливаются в нулевое состояние, а распределители10 и 32 импульсов - в исходное. С некоторой задержкой, необхоцимой цля установки схемы в исхоцное положение и приема числа Х в регистр 4, этот сигнал прохо- цит через элемент 9 задержки на третий вхоц„узла 12 запрета, который запускает генаратор 23. С его выхода импульсы через открытый элемент И 29 поступают на вхоц распрецелитепя 10 импульсов.

Первый импульс появляется на выходе 36 и открывает группу элементов И 15.

Значение числа Х заносится в регистр 35.

Сумматор 13 вычисляет значение Х-М,, Если результат вычитания не больше нуля, то сигнал появляется на первом выхоце узла 1 анализа результата, и при появпе нии второго импульса íà выходе 37 рас прецелит еля 10 импульсов открывается элемент И 6, и на выхоце 28-0 появля ется сигнал, свидетельствующий о попа» цании Х в нулевую группу сортировки

"брак-минус". Если ХМо 0, то сиг нал появляется на втором выходе узла 1 3$ анализа результата, и при появлении третьего импульса на выходе 38 распре делителя 10 импульсов через эле мент ИЛИ 34 к соцержимому счетчика il прибавляется ециница, и появляется сиг» 40 нал на слецуюшем выхоце дешифратора 5 (в данном случае на первом). По импульсу на выходе 39 распределителя 10 импульсов значение X-Мо заносится с вы хоца сумматора 13 в регистр 4. По им 4s пульсу на выхоце 40 в регистр 35 занесется значение ЬМ, и триггер ЗХ установится в единичное состояние, в результа те чего закроется элемент И 29, выклю чив из работы распрецелитель 10 им щ пульсов, и откроется элемент И 30, под кпючив к работе распрецепитель 32 им пульсов, который осуществляет дальией03 б шую обработку. На выходе сумматора образуется значение(Х-Мо)-b,N. Первый имл пульс с выхода распределителя 32 им пульсов поступает через элемент ИЛИ 34 на вхоц эйемента И 7. Второй импульс с второго выхода распределителя 32 импул сов, открывая группу элементов И 17, записывает результат вычитания в регистр 4. Дальнеашая работа устройства происходит под действием этих поочередно появля юшихся импульсов.

Когда содержимое сумматора 13 станет не большим нуля, на первом выходе схемы 1 анализа результата появится сигнал, который поступит на управляющий вход группы элементов И 18. Сит нал с оцного из выходов цешифрато ра 5 поступит через соответствуюшие группы элементов И 18 и ИЛИ 21 на соответствуюший выхоц устройства, сви» детельствуя î принацле>киости значения к цанной. группе сортировки.,Если на вход группы элементов И, соответствую ший установленной переключателем 22 перемычки, от цешифратора 5 поступит сигнал, то он пройдет через соответствую щую группу элементов ИЛИ 21 на соот» ветствуюший выход устройства, свице тепъствуя о попацвнии-значения Х в соот» иетствующую группу.

Появляющийся на однем из выходов 28 устройства сигнал через элемент ИЛИ 8 поступает на первый вхоц узла 12 запре .та, останавливая генератор 23 и прекра». шая работу устройства.

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

Так как кажцыР цикл работы предла» гаемого устройства (кроме первого) со стоит из цвух тактов против пяти тактов в известном, то быстродействие предлагаемого устройства повышается в 2,5 раза.

1024903

1024903

Составитель В. Горохов

Редактор В. l3aatao expei М.Тепер Корректор В. Гирняк

Заказ 4396/45 Тираж 706 . Подиисное

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

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

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