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

(51)М. Кд. С 06 Р 7/0 с присоединением заявки М Ъаударстацпвй квинтет СССР вф аааак нзабрвтеннй и аткрктвйДата опубликования описания 17,07,82(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ 1Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных.Известно устройство для сортировки двоичных чисел, содержащее М сдвигающих регистров сортируемых чисел, элементы управления Ц . Данное устройство позволяет выбирать из 8 двоичных кодов чисел только минимальные или максимальные значения, что ограничивает область его применения.Наиболее близким по технической сущности и достигаемому результату к предложенному является устройство со. держащее 8 сдвигающих регистров сортируемых чисел, узел сравнения, узел анализа количества единиц и СДвигаюе щнй регистр результата 2.Это устройство обладает низким быстродействием. Целью изобретения является повышение быстродействия.Поставленная цель достигается тем,что в устройство для сортировки чисел,содержащее регистр результата, узел 5сравнения и узел анализа количестваединиц, выходы которого соединены совходами первой группы узла сравнения,входы второй группы которого подключены к группе входов задания константы устройства, выход узла сравнениясоединен с информационным входом регистра результата, управляющий входкоторого подключен ко входу тактовыхсигналов устройства, введены и узлованализа, каждый из которых состоитиз кольцевого регистра сдвига, элементапамяти, триггера и схемы сравнения,причеминформационный вход кольцевого и регистра сдвига каждого 1-го узда ам- лиза соединен с 1-м ивформациончымвходом устройства, где 1 1,2 й,выход кольцевого регистра сдвига каж-.дого узла анализа подклеен ко входу9437элемента памяти и к первому входусхемы сравнения, второй вход которойсоединен с выходом узла сравнения, авыход - со входом установки в единичное состояние триггера, вход установкив нулевое состояние которого подключенко входу управления устройства, а выходко входу управления элементапамяти, выход элемента памяти каждого1 -го узла анализа соединен с 1 -м входомузла анализа количества единиц, входыуправления кольцевых регистров сдвигакаждого узла анализа подключены ковходу тактовых сигналов устройства,Узел анализа количества единиц состоит из дешифратора, шифратора, элементов ИЛИ, причем входы узла анализасоединены со входами дешифратора,каждый 0-й выход которого для единицво входном числе соединен со входом 2 О-го элемента ИЛИ, где 8 = 1, 2, к,= 1 211 -1, к - количество выходовдешифратора; п 1 - количество выходовс одинаковым количеством единиц вовходном числе, выход каждого-го элемента ИЛИ подключен к-му входу шифратора, выходы дешифратора, соответствующие 1 =0 и= п соединены сщ-м и (ь+ 1) -м входами шифраторасоответственно,зоНа фиг. 1 представлена блок-рхемаустройства; на фиг. 2 - схема узла анализа количества единиц.Устройство содержит регистр результата 1, узел сравнения 2, узел анализа35количества единиц 3, и узлов анализа 4,состоящих из элементов. памяти 5 триггеров 6, схем сравнения 7, кольцевыхсдвигающих регистров 8, входов тактовых сигналов 9, вход установки в исходное состояние 10, вход задания констант11, информационные входы 12. Узеланализа количества единиц 3 (фиг. 2)содержит дешифратор 13, элементы ИЛИ14, шифратор 15, входы 16 и выходы 17.45Элементы памяти 5 могут представлять собой Ц-триггеры с синхронизируюшими входами.Устройство работаеч следующим образомм.50Под выделением числа с заданным рангом понимается нахождение в исходноммассиве числа, относительная величинакоторого задана, начиная с минимальногочисла (например, найти девятое йо вели чине число). Ранг числа К - это номер55этого числа в отсортированном по возрастанию массиве чисел, Так если необходимо найти девятое по величине чис 07 ф,ло, то й = 9. В кольцевые сдвигаюшиерегистры 4 при помощи импульсов, подаваемых на вход тактовых сигналов 9устройства, записываются сортируемыечисла, начиная со старших разрядов. Навход установки в исходное состояние 10устройства подается импульс, которыйустанавливает триггеры 6 в "1", и науправляющих входах элементов 5 памятипоявляется разрешающий сигнал. Науправляющий вход 8 устройства подается константа сравнения где М - количество сортируемых чисел; Я - ранг выбираемого числа. После этого устройство переходит в режим выделения двоичного числа с наперед заданным рангом.Этот процесс проходит за гп тактов, где П - разрядность сортируемых чиселВ первом такте на информационные входы элементов 5 памяти поступают значения старших разрядов Й чисел и проходят на узел анализа количества единиц 3. В этом узле подсчитывается количество единиц, содержашихся в старших разрядах сортируемых чисел, и выдается результат подсчета на узел 2 сравнения. Если количество единиц в с, старших разрядах чисел не меньше кон станты сравнения И, то на выходе узла 2 сравнения появляется "1", в противном случае - "0". Выходное значение узла 2 сравнения записывается в регистр результата 1 в качестве цифры старшего разряда выделяемого числа и подается на вторые входы схем сравнения 7, на первые входы которых поступают сигналы старших разрядов сортнруемых чисел. Каждая схема 7 сравнения выдает единичный сигнал, если значения, подаваемые на ее входы, не совпадают, в противном случае - нулевой. Таким с образом, если значения на выходах кольцевого сдвигающего регистра 4 и узла сравнения 2 не совпадают, то снимается разрешающий сигнал с соответствующего элемента 5 памяти, чем блокируется запись в него последуюших значений в течение всех последуюших тактов работы устройства.Заблокированный элемент 5 памяти выдает в узел анализа количества единиц 3 то значение, которое было записано в него до снятия с управляющего входа разрешающего сигнала. Во втором такте на управляющий вход 9 устройства подается импульс, по которому информация5 9437 в регистрах 1 и 4 сдвигается на один разряд в сторону старших разрядов, причем в регистрах 4 осуществляется кольцевой сдвиг. В дальнейшем устройство работает аналогично описанному. После выполнения 1 ъ тактов в сдвигающем регистре 1 результата находится выделенное число, которое выводится ю устройства, а в регистрах 4 - сортируемые числа. Для последующего выделения чис .ла с заданным рангом из этого же набора двоичных чисел необходимо подать импульс на управляющий вход 10 устройства, а затем повторить все операции, описанные выше. 1Таким образом, использование данного устройства позволяет сократить время выборки из исходного массива двоичных чисел нескольких значений в определенном порядке. 20 формула изобретения 1, Устройство для сортировки чисел, 25 содержащее регистр результата, узел сравнения и узел анализа количестваединиц, выходы которого соединены со входами первой группы узла сравнения, входы второй группы которого подклю- З 0 чены к группе входов задания константы устройства, выход узла сравнения соединен с информационным входом регистра результата, управляющий вход которого подключен ко входу тактовых сигналов устройства, о т л и ч а ю щ е е с я .тем, что, с целью повышения быстродействия, в него введены п узлов анализа, каждый из которых состоит ю кольцевого регистра сдвига, элемента памяти, триггера и схемы сравнения, причем информационный вход кольцевого регистра сдвига каждого 1-го узла анализа соединен 07 6с 1 -м информационным входом устройства,где 1 -1, 2 а, выход кольцевого ре-гистра сдвига каждого узла анализаподключен ко входу элемента памяти ик первому входу схемы сравнения, второйвход которой соединен с выходом узласравнения, а выход - со входом установки в единичное состояние триггера,вход установки в нулевое состояние которого подключен ко входу управленияустройства, а выход - ко входу управления элемента памяти, выход элементапамяти каждого 1 -го узла аналюа соединен с 1 -м входом узла анализа количества единиц, входы управления кольцевых регистров сдвига каждого узлаанализа подключены ко входу тактовыхсигналов устройства,2. Устройство по п. 1, о т л и ч а -ю щ е е с я тем, что узел анализа количества единиц состоит из дешифратора,шифратора, элементов ИЛИ, причем входь 1узла анализа соединены со входами дешифратора, каждый Г -й выход которого идяединиц во входном числе соединен со входом-го элемента ИЛИ, где=1,2,к,) =.12%-1, к - количество выходовдешифратора; т - количество выходов содинаковым количеством единчц во входном числе, выход каждого 1-го элемента ИЛИ подключен к 1-му входу шифратора, выходы дешифратора, соответствующие 1 =0 и 1 =1 п, соединены с щ -м и(111+1)-м входами шифратора соответственно. Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР% 285347, кл, (д 06 Г 7/00, 1963,2. Авторское свидетельство СССР Ж 610107, кл. 6 06 Г 7/06, 1978.2 Составитель Б. Богумирскийедактор И; Дылын Техред И. Гайду Корректо акаэ 5110 сно е Филиал ЛПП "Патент", г. Ужгород, ул. Проектная, 4/55 Тираж 731 В НИИПИ Государственногпо делам изобретею 113035, Москва, ЖПодпиомитета СССРоткрытийушская наб., д.