Устройство для сортировки и выборки информации

9) Я О и 1) СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИК 98 3(59 6 06 Г 7 06 ОБРЕТЕНИ ПИСА ЕТЕЛЬСТ АВТОРСКОМ(прототип) . Бюл. М 15и Е.К.Пьянков088.8)ое свидетельство06 Р 7/06, 1975.свидетельство СС06 Р 7/06, 1980 5 00 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ( 4) (57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИИ ВЫБОРКИ ИНФОРМАЦИИ, содержащеерегистр результата, узел сравнения,узел анализа количества единиц ип узлов анализа несовпадения с константой сравнения (где и-количествосравнимых чисел), каждый йз которыхсостоит из кольцевого регистра сдвига, элемента памяти, триггера иблока сравнения, причем информационный вход кольцевого регистра сдвига каждого .1-го узла анализа соединен с 1-м информационным входомустройства, где 1=1,2. и, выходкольцевого регистра сдвига каждогоузла анализа несовпадения с константой сравнения подключен к входусоответствующего элемента памятии первому входу блока сравнения,второй вход которого соединен свыходом узла сравнения, а выход - свходом установки в единичное состояние соответствующего триггера, входустановки в нулевое состояние которого подключен к шине начальнойустановки устройства, а выход - квходу разрешения записи соответствую"щего элемента, памяти, входы управления кольцевых регистров сдвига каждого узла анализа несовпадения сконстантой сравнения щдключены квходу тактовых сигналов устроЪства,выходы узла анализа количества единиц соединены с входами первой группы узла сравнения, входы второйгруппы которого подключены к группевходов задания константы сравненияустройства, выход узла сравнениясоединен с информационным входомрегистра результата, управляющийвход которого подключен к входутактовых сигналов устройства, узеланализа количества единиц содержитдешифратор, шифратор, элементы ИЛИ,причем входы узла анализа количества единиц соединены с входами дешифратора, каждый 1 -й выход которогосоединен с входом 3-го элемента. ИЛИ,где Г=.1,2,К 3=1,2 (в),К - количество выходов дешифратора,в - количество выходов с одинаковым эколичеством единиц во входном числе,выход каждого 3-го элемента ИЛИ подключен к 3 - му входу шифратора, вй ходы дешифратора, соответствующие С3=0 и Э=в,соединены с щ- м и (щ+1)-мвходам шифратора соответственно, фо т л и ч а ю щ е е с я тем что сррЦцелью расширения функциональных воз.можностей путем обеспечения воз- (:Рможности сортировки произвольноменьшего, чем и, набора чисел, ивыборки К из п, в него введен и-раз- ф 3рядный регистр маски и и двухвходных цфэлементов И, выходы которых соединены с соответствующими, входами узла 00анализа количества единиц, первыйвход каждого 1-го элемента И соединен с выходом элемента памяти 1-гоузла анализа несовпадения с константой сравнения, второй вход 1-гоэлемента И соединен с соответствую- фр,щим выходом регистра маски, входырегистра маски являются входами задания набора чисел устройства, входысинхронизации триггеров всех узлованализа несовпадения с константойсравнения подключены к блокировочной шине устройства,Изобретение относится к автоматике и вычислительной технике и можетбыть использовано в специализированных вычислительных машинах и уст-ройствахобработки данныхИзвестно устройство для сортировки чисел, содержащее регистр результата, узел сравнения и узел анализаколичества единиц, регистры анализируемых чисел, элементы преобразования Г 13. 10Недостатком этого устройства являются ограниченные функциональныевозможности,Наиболее близким по техническойсущности к предложенному являетсяустройство для сортировки чисел,содержащее регистр результата, узелсравнения и узел анализа количестваединиц, и узлов анализа, каждый изкоторых состоит из кольцевого регист ра сдвига, элемента памяти, триггера и схемы сравнения, причем выходыузла анализа количества единиц соединены с входами первой группы узласравнения, входы второй группы которого подключены к. группе входов задания константы устройства, выходузла соединен с информационным входом регистра результата, управляющий вход которого подключен к входутактовых сигналов устройства, информационный вход кольцевого регистрасдвига каждого 1-го узла анализасоединен с 1-м информационным входомустройства, где 1=1,2 п, выходкольцевого сдвига каждого узла анализа подключен к входу элементапамяти и первому входу схемы сравнения, второй вход которой соединенс выходом узла сравнения, а выходс входом установки в единичное состояние триггера, вход установкив нулевое состояние которого подключен к входу управления устройства,а выход - к входу управления элемента памяти, выход элемента памяти 45какдого 1-го узла анализа соединенс 1-м входом узла анализа количестваединиц, входы управления кольцевыхрегистров сдвига каждого узла ава 9 ти.,за подключены ко входу тактовых сиг.налов устройства, узел анализа количества единиц состоит из дедифратора, шифратора, элементов ИЛИ, причем входы узла анализа соединены совходами дешифратора, каждый Г-ый вы-ход которого соединен со входом-го элемента ИЛИ, где 1=1,2К, 1 =1,2(в), К - количествовыходов дешифратора, в - количествовыходов с одинаковым количествомединиц во входном канале, выход 60каждого -го элемента ИЛИ подключенк- му входу шифратора, выходы дешифратора, соответствующие =0 и=в, соединены с в-ым и (в+1)-мвходами шифратора соответственно 23. 65 Однако известное устройство имеет ограниченные функциональные возможности, так как производит всегда сортировку только всех чисел, в то время как иногда возникает задача сортировки произвольного, меньшего чем и, набора чисел, например М, где 0 Мп, Кроме того, известное устройство не может выполнять функцию выборки чисел К из и.Целью изобретения является расширение функциональных возможностей устройства.Поставленная цель достигается тем, что в устройство для сортировки и выборки информации, содержащее регистр результата, узел сравнения, узел анализа количества единиц и и узлов анализа несовпадения с константой сравнения (где п-количество сравнимых чисел), каждый из которых состоит из кольцевого регистра сдвига, элемента памяти, триггера и блока сравнения, причем информационный вход кольцевого регистра сдвига каждого 1-го узла анализа соединен с 1-м информационным входом устройства, где 1=1,2п, выход кольцевого регистра сдвига каждого узла анализа несовпадения с константой сравнения подключен к входу соответствующего элемента памяти и первому входу блока сравнения, второй вход которого соединен с выходом узла сравнения, а выход - с входом установки в единичное состояние соответствующего триггера, вход установки в нулевое состояние которого подключен к шине начальной установки уст-. ройства, а выход - к входу разрешения записи соответствующего элемента памяти, входы управления кольцевых регистров сдвиГа каждого узла анализа несовпадения с константой сравнения подключены к входу тактовых сигналов устройства, выходы узла анализа Количества единиц соединены с входами первой группы узла сравнения, входы второй группы которого подключены к группе входов задания константы сравнения устройства, выход узла сравнения соединен с информационным входом регистра результата, управляющий вход которого под" ключен к входу тактовых сигналовустройства, узел анализа количестваединиц содержит дешифратор, шифратор, элементы ИЛИ, причем входы узла анализаоколичества единиц соединены с входами дешифратора, каждый-й выход которого соединен с входом З-го элемента ИЛИ, где =1,2К, =1,2(в), К количество выходов дешифратора, в- количество выходов с одинаковым количеством единиц во входном числе, выход каждого 3-го элемента ИЛИ подключен к -му входу шифратора, выходы40 дешифратора, соответствующие 3=0 и 3=тп, соединены с п- м и (в +1)-м входами шифратора соответственно, с целью расширения, функциональных возможностей путем обеспечения возможности сортировки произвольно меньше го, чем и, набора чисел, и выборки К из и, в него введен и-разрядный регистр маски и и двухвходных элементов И, выходы которых соединены с соответствующими входами узла авали за количества единиц, первый вход каждого 1-го элемента И соединен с выходом элемента памяти 1-го узла анализа несовпадения с константой сравнения, второй вход 1-го элемента 15 И соединен с соответствующим выходом регистра маски, входы регистра маски являются входами задания набора чисел устройства, входы синхронизации триггеров всех узлов анализа. несовпадения с константой сравнения подключены к блокировочной шине устройства.На чертеже представлена блок-схема предлагаемого устройства. 25Устройство содержит сдвигающий регистр 1 результата, узел 2 сравнения, узел 3 анализа количества единиц, и узлов 4 анализа, каждый из которых состоит из кольцевого регистра 5 сдвига, элемента б памяти, триг-З 0 гера 7 и схемы 8 сравнения, информационный вход 9 устройства, вход уста" нонки в исходное состояние 10, вход тактовых сигналов 11, группу входов задания констант 12, и-разрядный 35 регистр 13 маски, входы которого являются входами устройства 14, двух- входовые элементы 15, блокировочную шину 16.Устройство работает следующим образом,Под выделением числа с заданным" рангом понимается нахождение в исходном массиве числа, относительная величина которого задана, начиная с 45 минимального числа (например, найти девятое по величине число). Ранг числа К-это номер .этого числа н отсортированном по возрастанию массивеф чисел. Так, если необходимо найти девятое по величине число, то К=9. В кольцевые сдвигающие регистры 5 при помощи импульсов, подаваемых на вход тактовых сигналов 11 устройства, записываются сортируеьые числа, начиная со старших разрядов. На вход установки в исходное состояние 10 устройства подается импульс, который устананлинает триггер 7 в 1, при этом по блокироночному входу на входы синхронизации данных 60 триггеров подается уровень логической 1, разрешающий установку триггероВ н любое требуемое состояние. На управляющих нходах элементон 6 памяти появляется разрешающий 65 сигнал, На вход 12 задания константыподается константа .сравненияА = и+1 - Н,где и - количество сортируемых чисел;В - ранг выбираемого числа.В и-разрядный регистр 13 маскичерез информационные входы 14 записываются единицы в те и-разрядон,которые соответствуют сортируемымчислам, а в остальные (Б - и) разрядовзаписываются нули, На первые входыэлементов 15 И с соответстнующих .элементов б,памяти подаются сортируемые числа старшими разрядами вперед,а на вторые входы элементов 15 Иподаются сигналы разрешения или запрещения с соответствующих выходоврегистра 13 маски.После этого устройство переходитв режим выделения двоичного числас наперед заданным рангом,Этот процесс проходит за щ тактов,где в-разрядность сортируемых чисел.В первом такте на информационныевходы элементов б памяти поступаютзначения старших разрядов чисел ипроходят через схемы И на узел 3анализа количества единиц. В этомузле подсчитывается количество единиц, содержащихся в старших разрядахсортируемых чисел и выдается результат подсчета на узел 2 сравненияЕсли количество единиц в старшихразрядах чисел не меньше константысравнения А, то на выходе узла 2сравнения появляется 1, в противном случае 0. Выходное значениеузла 2 сравнения записывается в регистр 1 результата в качестве цифрыстаршего разряда выделяемого числаи подается на вторые входы схемысравнения, на первые входы которыхпоступают сигналы старших разрядовсортируемых чисел. Каждая схема 8сраннения выдает единичный сигнал,если значения, подаваемые на еевходы,не совпадают, в противномслучае - нулевой. Таким образом, если значения на выходах кольцевогосднигающего регистра 5 и узла 2сравнения не совпадают, то снимается разрешающий сигнал с соответствующего элемента б памяти, чем блокируется запись в него последующихзначений в течение всех последующихтактов работы устройства.Заблокированный элемент б памятивыдает на элементы И, а затем наузел 3 анализа количества единицто значение, которое было записано ннего до снятия с управляющего входаразрешающего сигнала. Во втором такте на управляющий вход 11 устройстваподается импульс по которому информация в регистрах 1 и 5 сдвигаетсяна один разряд в сторону старшихразрядов. В дальнейшем устройствоработает аналогично описанному.1087986 Т После выполнения й тактов в сдвигающем регистре 1 результата находится выделенное число, которое выводится иэ устройства,Для обеспечения выполнения устрой.ством функции выборки К из и навход установки в исходное состояние10 и на блокировочный вход 16 устройства подается импульс, которнйустанавливает триггер 7 в 1,после чего на блокировочннй вход 16 10подается уровень логического нуляи триггеры 7 запоминают исходноесостояние, а на управляющих входахэлементов 6 памяти в течении всеговремени выборки установится разрешающий сигнал.В 1 - .м такте(где 1=1,2,3.,щщ-.раэрядность анализируеьаюх чисел) свыходов сдвиговых регистров 5 анализируемых чисел значения 1-х разрядов поступают на элементы 6 памятии проходят. на первые входы элементов 15 И, на вторые -входы которыхпоступают сигналы разрешения или запрета с соответствующих выходоврегистра 13 маски. Текущие значения1-х разрядов выбранных регистров поступают на соответствующие входыузла 3 анализа количества единиц,где производится параллельная свертка числа единиц. Результат подсчета,представленный в прямом коде, поступает параллельно на первые входыузла сравнения 2, на вторые входыкоторого поступает константа сравнения, представленная в дополнительном коде, разрядностью 1 о М. Инверсия знакового разряда результатасравнения, получаемая на выходе узла 2 сравнения, поступает на информационный вход сдвигового регистра1 результата,Использование предложенного устройства позволит реализовать сортировку любого набора чисел иэ имеощихся М чисел, кроме того устройство позволяет на проходе реализоватьвыборку из массива чисел с переменным уровнем мажоритации. НИИПИ Заказ 2673/45 ирак 699 Подписи илиал ППП "Патент",