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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социали:тических

Республик

<п928343 (6i) Дополнительное к авт. сеид-ву— (22) Заявлено 2504,80 (21) 294205.8/18-24 с присоединением заявки N (23) Приоритет

{31)М Кл з

G 06 F 7/06

Государственный комитет

СССР по делам изобретений и открытий

Опубликовано 150582, Бюллетень ¹ 18 (531УДК 681.325. ,5 (088.8)

Дата опубликования описания 150582

Э. П. Чернаков, В. М. Цыганков и Б.С. В6гумирсКий

J (72) Авторы изобретения (7! ) Заявитель (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

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

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

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

Кроме того, оно обладает низким быстродействием.

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

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

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

928343

Недостатком этого устройства является низкое быстродействие, так как число тактов. работы устройства при определении попадания заданного числа в 6сакую-нибудь группу растет с увеличением ширины, групп сортировки.

Цель изобретения — повышение быстродействия устройства.

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

i-ro переключателя, выход каждого

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

10 с управляющими входами элементов И второй и четвертой групп соответственно, третий, четвертый и пятый выходы распределителя импульсов подключены к второму входу первого эле15 мента И и к управляющим входам элементов И пятой и третьей групп соответственно.

На чертеже представлена блок-схе ма устройства.

Устройство содержит узел анализа !, результата 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, выходы

301,30 ...30 устройств, выходы 31,32,...35 распределителя.

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

Перед началом работы устройства по руппам входов 27 и 28 на ре- . гистры 17 и 16 записываются соотнет4р ственно значения аМ и М, где ь М— задаваемая ширина групп сортировки, а Мц — задаваемая нижняя граница групп сортировки. Нри помощи переключателя 6 устанавливается необхо45 димое число грУпп сортировки (от 0 до N-1) без учета группы Бракминус . Под действием сигнала на входе устройства 26 код числа Х, поступающий на группу входов устройства 29, записывается .в приемный регистр 13, счетчик 3 устанавливается в нулевое состояние, а распределитель 12 импульсов — в исходное. С некоторой задержкой, необходимой для установки схемы в исходное положение и приема Х на регистр 13,этот. сигнал проходит через элемент 9 задержки на разрешающий вход элемента

10 запрета, По сигналу от блока 10

-Управления запускается генератор 11

60 импульсов. С его выхода импульсы поступают на вход распределителя 12 импульсов, который распределяет их цо управляющим точкам устройства.

Первый импульс появляется на выходе

65 31 и открывает группу клапанов 22.

928343

Сумматор 14 вычисляет значение Х-h4 .

Второй импульс. с выхода 32 распределителя 12 импульсов открывает груп- пу элементов И 23 и значение Х-Мо принимается в регистр 15 результата. .Из него значение Х-No поступает в узел анализа результата 1. Если ре5 зультат вычитания не больше нуля, то сигнал появляется на верхнем выходе узла анализа результата 1, в противном случае — на нижнем. Ймпульс на выходе 33 распределителя импульсов открывает элемент И 2 и если

Х-Мц О, то на.выходе устройства

30 — 0 появляется сигнал, свидетельствующий о попадании значения Х в нулевую группу cQpTHpoBKH Бракминус . Следующий импульс появляет,ся на выходе 34 распределителя импульсов 12 и открывает группу эле.ментов И 24 и элемент И 25. Если

Х-Мо) О, то к содержимому счетчика 20 добавляется единица и появляется сигнал на следующем выходе дешифратора (в .данном случае — на первом).

Код из регистра 15 результата заносится в регистр 13. Импульсом на 5 выходе 35 распределителя 12 импульсов открывается .группа элементов

И 21 и на выходах сумматора 14 появляется значение Х-Мо-д М. В дальнейшем работа устройства происходит аналогично под действием импульсов, периодически появляющихся на выходах 32, 34., 35 распределителя 12 импульсов. Необходимо помнить, что элемент И 2 открывается только в

35 нервом цикле работы устройства.

Когда содержимое регистра 15 реО зультата становится меньше либо равно нулю, на верхнем выходе схемы анализа 1 появляется сигнал, который поступает на управляющий вход груп- 40 пы элементов И 5. Сигнал, имеющийся на одном из выходов дешифратора 4, проходит через соответствующие элементы И 5 группы и элемент ИЛИ группы элементов ИЛИ 7 на соответ- 45 ствующий выход устройства, свидетельствуя о принадлежности значения к данной группе сортировки. Если на вход клапана на группы элементов

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

Х к группе Брак-плюс .

Появляющийся на одном из выходов устройства 30 сигнал проходит через элемент ИЛИ 8 на запрещающий вход QQ узла 10 запрета,. который останавливает генератор 11 импульсов. Работа устройства прекращается.

Использование предлагаемого уСтройства позволяет повысить быстродействие устройства, так как определение попадает ли заданное .число в данную группу, происходит за 3 такта работы устройства после проверки предыдущей группы, в известном устройстве число тактов растет с увеличением ширины групп сортировки.

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

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

27 28

ВНИИПИ Эакаэ 3241/61 Тираж 732 Подписное

ФиЛиал ППП "Патент", г. Ужгород, ул. Проектная, 4 пы входов элементов ИЛИ третьей группы, выходы которых соединены с входами четвертого регистра, выходы которого подключены к входам второй группы сумматора, выходы первого регистра соединены с информационными входами элементов И пятой группы, выходы которых подключены к входам второй группы входов. элементов ИЛИ третьей группы, первый и второй выходы распределителя импульсов соединены с управляющими входами элементов И второй и четвертой групп соответственно, третий, четвертый и пятый выходы распределителя импульсов подключены к второму входу первого элемента И и к управляющим входам элементов И пятой и третьей групп соответственно.

Источники информации, принятые во внимание при экспертизе

1. Лвторское свидетельство СССР

9 249764, кл. G 06 F 7/00, 1967. 0 2. Авторское свидетельство СССР

Р 658569, кл. G 06 F 7/06, 1977 (прототип) .