Устройство для сортировки чисел Советский патент 1985 года по МПК G06F7/06 

и блок памяти, причем входы узла формирования грании;ы соединены с установочными входами счетчика, выходы которого соединены с адресными входами блока памяти, информа..ционные выходы которого, кроме последнего разряда, являются информационными выходами узла формирования границы, выход последнего разряда - выходом конца интервала узла формирования границы, счетный вход счетчика - входом изменения узла формирования границы.

51952

3. Устройство по П.1, отличающее ся тем, что узел анализа результата содержит два элемента И и элемент НЕ, причем информационный вход узла анализа результата соединен с первым входом первого элемента И и через элемент НЕ с первым входом второго элемента И, вторые входы элементов И подключены к входу опроса узла анализа результата, а выходы являются соответственно выходами разрешения выдачи и разрешения счета узла анализа результата. i

1. УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее узел формирования границы, узел анализа результата, регистр, вычитатель, элемент ИШ элемент И, счетчик,дешифратор, группу элементов И и узел управления, включающий генератор импульсов, распределитель импульсов и элемент задержки, причем выходы регистра соединены с первой группой входов вычитателя, вторая группа входов которого подключена к информационным выходам узла формирования границы, вход запуска устройства подключен к входам элемента задержки и установки в исходное состояние распределителя импульсов узла управления .и входу установки в нулевое состояние счетчика, выход которого соединены с входами депшфратора, выходы которого соединены с информационными входами элементов И группы, управляющие входы которых подключены к выходу разрешения вьщачи узла анализа результата, выход i-ro элемента И группы, где ,2, ... N (N - число групп сортировки), является i-м выходом устройства, выход элемента И является (N+1)-M выходом устройства и соединен с первым входом элемента ИЛИ, выход которого подключен к входу останова узла управления, о т ЛИ чающееся тем, что, с целью расширения области применения устройства за счет обеспечения возможности задания групп сортировки различной ширины, информационные входы устройства соединены с установочными входами регистра, адресные входы устройства подключены к входам узла формирования границы, выход конца интервала которого подключен к первому входу элемента И, а вход изменения адреса - к первому выходу распределителя импульсов, второй выход которого соединен с входом опроса (Л узла анализа результата, информационный вход которого подключен к выходу знакового разряда вычитателя, выход разрешения выдачи узла анализа результата соединен с вторым входом элемента ШШ, а выход разрешения сче- ,та - со счетным входом счетчика и вторым входом элемента И, в узел управления введены триггер и элемент И, первый вход которого соединен с выходом генератора импульсов, выход подключен к входу распределителя импульсов, а второй вход соединен с прямым выходом триггера, вход установки в ед;иничное состояние которого подключен к выходу элемента: задержки , а выход установки в О - к входу останова узла управления.2. Устройство по п.1, о т л и чающееся тем, что узел формирования границы содержит счетчик

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных. Известно устройство для сортиров ки чисел, содержащее узел анализа результата, элементы И, счетчик, дешифратор, переключатель, элементы ИЛИ, элемент задержки, узел управления и генератор импульсов Li J Его недостатки - невозможность задания различных значений )пирины Хрупп сортировки и низкое быстродействие, Наиболее близким к предлагаемому по технической сущности и достигаемому результату является устройство для сортировки чисел, содер жащее узел анализа результата, регистры, дешифратор, элементы И, ИЛИ элемент задержки, распределитель им пульсов, счетчик, элемент запрета, сумматор, группы элементов И, ИЛИ, переключатель, генератор, причем выход первого регистра соединен с выходом узла анализа результата, первьй выход которого подключен к первым входам элементов И первой группы и к первому входу первого элемента И, выход которого соединен с первой выходной шиной и с первым входом первого элемента ИЛИ, второй выход узла анализа результата подкл чен к первому входу второго элемента И, выход которого соединен с информационным входом счетчика, выход которого подключены к входам дешифр тора, каждый i-й вьсход которого (где ,2,...,n) соединен с вторым входом i-ro элемента И первой группы и с первым выводом i-ro переключателя, выход каждого i-ro элемента И первой группы и второй вывод i-ro переключателя подключены к первому и второму входам соответственно i-ro элемента ИЛИ первой группы, выход каждого из которых соединен с (i+1)-M входом первого элемента ИЛИ, выход которого , подключен к входу управления элемента запрета, выход которого соединен с входом генератора, выход которого подключен к входу распределителя импульсов, вход управления устройства соединен с входом установки в нулевое состояние счетчика и распределителя импульсов, с первым входом третьего элемента И и через элемент задержки с входом элемента запрета, выходы второго и третьего регистров подключены к информационным входам элементов второй и третьей групп соответственно, выходы которых соединены с входами элементов ИЛИ второй группы, выходы которых соединены с входами первой группы сумматора, выходы которого подключены к информационньм входам элементов И четвертой группы, информационные входь устройства соединены с информационными входами элементов И пятой группы, выходы которых подключены, к входам первой группы входов элементов Ш1И третьей группы, выходы которых соединены с входами четвертого регистра, выходы которого подключены к входам второй группы сумматора, выходы первого регистра соединены с информационными входами элементов Н пятой группы, выходы которых подключены к входам второй группы входов элементов ИЛИ третьей группы, первьй и второй выходы распределителя импульсов соединены с управляющими входами элементов И второй и четвер той групп соответственно, третий, четвертый и пятьш выходы распределителя импульсов подключены к второму входу первого элемента И и к управлякяцим входам элементов И пято и третьей групп соответственноL2}, Недостатком известного устройства является невозможность задания различных значений ширины групп .сортировки . Цель изобретения - расширение области применения устройства за Счет обеспечения возможности задания групп сортировки различной шириПоставленная цель достигается тем, что в устройстве для сортировки чисел, содержащем узел формирова ния границы, узел анализа результат регистр, вычитатель, элемент ИЛИ, элемент И, счетчик, дешифратор, гру пу элементов И и узел управления, включающий генератор импульсов, рас пределитель импульсов и элемент задержки, причем выходы регистра соединены с первой группой входов вычи тателя, вторая группа входов которо подключена к информациоиньм выходам узла формирования границы, вход запуска устройства подключен к входам элемента задержки и установки в исходное состояние, распределителя импульсов узла управления и входу установки в нулевое состояние счетчика, выходы которого соединены с входами -дешифратора, выходы которог соединены с информационными входами элементов И группы, управляющие вхо ды которых подключены к/выходу решения выдачи узла анализа результата, выход i-ro элемента И группы, где ,2,...,N (N - число группы сортировки), является i-м выходом устройства, выход элемента И являет ся (N+1)-M выходом устройства и соединен с первым входом элемента ИЛИ, выход которого подключен к вхо ду останова узла управления, информационные входы устройства соединены с установочными входами регистра,. адресные входы устройства подключены к входам узла формирования границы, выход конца интервала которого подключён к первому входу элемента И, а вход изменения адреса - к первому выходу распределителя импульсов, второй выход которого соединен с входом опроса узла анализа результата, информационный вход которого подключен к выходу знакового разряда вычитателя, выход разрешения выдачи узла анализа результата соединен с вторым входом элемента ИЛИ, а выход разрешения счета - со счетным входом счетчика и вторым входом элемента И, в узел управления введены триггер и элемент И, первьй вход которого соединен с выходом 1енератора импульсов, В 51ход подключен к входу распределителя импульсов, а второй вход соединен с прямым выходом триггера, вход установки в единичное состояние которого подключен к выходу элемента задержки, а выход установки в О к входу останова узла управления. Узел формирования границы содержит счетчик и блок памяти, причем входы узла формирования границы соединены с установочными входами счетчика, выходы которого соединены с адресными входами блока памяти, ийформационные выходы которого., кроме последнего разряда, являются информационными выходами узла формирования границы, выход последнего разряда - выходом конца интервала узла формирования границы, а счетный вход счетчика - входом изменения адреса узла формирования границы. Узел анализа результата содержит два элемента И и элемент НЕ, причем информационный вход узла анализа результата соединен с первым входом первого элемента И и через элемент НЕ с первым входом второго элемента И, вторые входы элементов И подключены к входу опроса узла анализа результата, а выходы являются соответственно выходами разрешения вьщачи и разрешения счета узла анализа результата. На чертеже приведена схема устройства. Устройство содержит узел 1 формирования границы, узел 2 анализа результата, узел 3 управления, регистр 4, вычитатель 5, элемент ИЛИ элемент И 7, счетчик 8, дешифратор группу to элементов И, вход 11 .запуска, адресные входы 12, информационные входы 13 и выходы 14(, 14, Узел 1 содержит счетчик 15 и блок 16 памяти.Узел 2 сод жит элемент НЕ 17 и элементы И 18 и 19, Узел 3 содержит распределител 20 импульсов, элемент И 21, элемент 22 задержки, триггер 23 и генератор 24 импульсов. Устройство предназначено для раз браковки (сортировки) изделий на групга по их характеристикам, представленным кодовыми значениями, В блоке 16 памяти хранятся следу щие последовательности кодов чисел. где К - количество последовательнос тей мФ, С 1 1 теи Up, U , и, 5 n(j) J ,,,, К), т.е. К- это количество используемых вариантов разбиений отрезка (О, log(N+1)) числовой оси на группы сортировки (имеются ввиду только целые числа;(N+1) - это коли чество выходов полного дешифратора 9, а log(N+1) - это количество различных кодов, которые могут быть записаны в счетчик 8); Mv- верхняя граница i-й (, , , ,,,, пЩ группы сортировки j-ro (j .,,, к) варианта разбиения; - нижняя граница i-й (, .,., пЩ группы сортировки j-ro (, ,, к) варианта разбиения; i - количество групп сортировки в J-M (, ..,, .К) варианте разбие ния. Для всех не должно превос ходить N. Каждое число М. хранится в от дельной ягчейке блока 16 памяти, Чнс Яа сопровождаются единицей в последнем разряде каждой ячейки паMHTHj остальные же числа мУ (0, ..,, сопровождаются нулем. Последовательность границ групп сортировки каждого варианта разбиения должна находиться в смежгшх яче как памяти. Устройство работает следующим образом. При включении питания триггер 23 устанавливается в нулевое состояние (не показано), Предположим, необходимо использовать (, ,,., К) вариант разбиения отрезка числовой оси на группы сортировки. При этом код числа (Ар-1), где Ар - адрес числа М, записывается в счетчик 15 по группе входов 12, Код числа X, подлежащего сортировке, по группе входов 13 заносится в регистр 4, Устоойство запускается в работу импульсом по входу 11, При этом обнуляется счетчик 8, распределитель 20 устанавливается .в исходное состояние (сигнал ни на одном из выходов не выдается). Этот же импульс с задержкой, необходимой дпя обнуления счетчика 8 и установки распределителя 20 в исходное состояние, поступает на единичный вход триггера 23, устанавливая последний в единичное состояние. Импульсы с выхода генератора 24 через открытый элемент И 21 начинают поступать на вход распределителя 20, По первому прошедшему импульсу он выдает импульс на своем первом выходе. При этом содержимое счетчика 15 увеличивается на единицу и становится равным Ар, На выходах узла 1 появляется код Вычитатель 5, выполненный на комбинационных элементах, осуществляет вычитание М из содержимого регистра 4, На выходе вычитателя 5 присутствует знак этой разности, причем О соответствует неотрицательному числу, а 1 - отрицательному. Если ), то открывается элемент И 18, Если К-н- О, то открывается элемент И 19, Затем появляется импульс на втором выходе распределителя 20, который проходит через один из элементов И 18 или 19, Следовательно, если , то открывается группа 10 элементов И и появляется сигнал на выходе 14 Брак-минус, соответствукнций содержимому счетчика 8; если же X , то к содержимому счетчика 8 добавляется единица. Кроме того, если выполнено второе условие и в последнем разряде ячейки, содержащей , находится единица (вариант разбиения только одну точку), то появляется сигнал на выходе t4 ц+1 Брак-плюс. При поярлении сигнала

7,

на выходе одного из элементов И 7 или 18 триггер 23 устанавливается в нулевое состояние, элемент И 21 закрывается и работа устройстра для чисел X и (Ар-1) прекращается.

Если и непоследняя граница варианта разбиения, то последний разряд ячейки памяти, содержащий обнулен. Следовательно работа устройства не прекращается. По следующему импульсу на первом выходе распределителя 20 содержимое счетчика 15 увеличивается на единицу и становится равным (Ар+1). В результате этого на вторую группу входоз вычитателя 5 подается код М. Вычитатель 5 вьщает код разности . В зависимости от кода знака этой разности и содержимого последнего разряда ячейки памяти, содержащей по следукядему импульсу с второго выхода распределителя 20 могут выполняться следующие действия: если и последний разряд ячейки обнулен, то появляется импульс на выходе элемента И 19 и содержимое счетчика 8 увеличивается на единицу и становится равным двум если и последний разряд ячейки обнулен, то появляется импульс на выходе элемента И 18, в результате чего открьшается группа 10 элементов И и появляется сигнал на выходе 14, соответствующем коду единицы в счетчике 8 и свидетельс -вующем о том, что число X принадлежит первой группе сортировки, а также появляется импульс на выходе элемента ИЛИ 6, которьй устанавливает триггер 23 в нулевое состоя- ние, запрещая дальнейшее сравнение. Если и последний разряд ячейки установлен в единицу ()

528

то появляется сигнал на выходе элеента И 7, который поступает на ыход 14fj+ Брак-плюс и обнуляет триггер 23; если Х-М , и последний разряд ячейки установлен в единицу (), то появляется сигнал на выходе элемента И 18 (как и в случае, когда и последний разряд ячейки обнулен).

Следовательно, работа устройства продолжается, как описано вьше, только при возникновении случая, когда О и последний разряд ячейки обнулен.

При необходимости отсортировать по группам массив чисел требуется вновь записать в счетчик 15 по группе входов 12 (Ар-1), а в регистр 4 по группе входов 13 - следующее чисо. В дальнейшем устройство работае аналогично описанному вьше.

Положительный эффект от использования предлагаемого устройства заключается в следующем. При использовании известного устройства задаются MQ и лМ где М - нижняя граница групп сортировки, а дМ - ширина групп сортировки. Следовательно, граница )+faM,., где целое положительное число. Очевидно, что i ширина всех групп сортировки одинакова и равна М. Это сужает функциональные возможности устройства. В предлагаемом устройстве явно задается и затем используется при сортировке каждая граница М. Вследствие этого ширина каждой группы может быть любой. Таким образом, использование изобретения позволяет расширить область применения устройства за счет обеспечения возможности задания групп сортировки различной ширины. % ;