Устройство для сортировки и выборки информации Советский патент 1984 года по МПК G06F7/06 

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

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

Недостатком этого устройства являются ограниченные функциональные возможности.

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

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

Целью изобретения является расширние функциональных возможностей устройства.

Поставленная цель достигается тем, что в устройство для сортировки и выборки информации, содержащее регистр результата,узел сравнения, узел анализа количества единиц и п узлов анализа несовпадения с константоИ сравнения (где п-количество сравнимых чисел), каждый из которых состоит из кольцевого регистра сдвига, элемента памяти, триггера и блока сравнения, причем информационный вход кольцевого регистра сдвига каждого 1-го узла анализа соединен с i-м информационным входом устройства где ,2,...,п выход кольцевого регистра сдвига каждого узла анализа несовпадения с константой сравнения подключен к входу соответствующего элемента памяти и первому входу блока сравнения, второй вход которого соединен с выходом узла сравнения, а выход - с входом установки в единичное состояние соответствующего триггера, вход установки в нулевое состояние которого подключен к шине начальной установки устройства, -а выход - к входу разрешения записи соответствующего элемента памяти, входы управления кольцевых регистров сдвига каждого узла анализа несовпадения с константой сравнения подключены к входу тактовых сигналов устройства, выходы узла анализа 6личества единиц соединены с входами первой группы узла сравнения, входы второй группы которого подключены к группе входов задания константы сравнения устройства, выход узла сравнения соединен с информационным входом регистра результата , управляющий вход которого подключен к входу тактовых сигналов устройства, узел анализа количества единиц содержит дешифратор, шифратор, элементы ИЛИ, причем входы узла аналиэаоколичества единиц соединены с входами дешифратора, каждый -и выход которого соединен с входом J-го элемента ИЛИ, где 2 1,2,...,К, ,2,...,(т-1), Кколичество выходов дешифратора, т- количество выходов с одинаковым количеством единиц во входном числе, выход каждого j-ro элемента ИЛИ подключен к j-му входу шифратора, выход дешифратора, соответствующие и , соединены с т- м и {п +1)-м входами шифратора соответственно, с целью расширения.функциональных возможностей путем обеспечения возможности сортировки произвольно меньшего, чем п, набора чисел, и выборки К из п, в него введен п-разрядный регистр маски и п двухвходных элемен тов И, выходы которых соединены с соответствующими входами узла анализа количества единиц, первый вход каждого i-го элемента И соединен с выходом элемента памяти i-го узла анализа несовпадения с константой сравнения, второй вход i-ro.элемента И соединен с соответствующим выходом регистра маски, входы регистра маски являются входами задания набора чисел устройства, входы синхронизации триггеров всех узлов анализа несовпадения с константой сравнения подключены к блокировочной шине устройства. На чертеже представлена блок-схема предлагаемого устройства. Устройство содержит сдвигающий регистр 1 результата, узел 2 сравнения, узел 3 анализа количества единиц, п узлов 4 анализа, каждый и которых состоит из кольцевого регист ра 5 сдвига, элемента б памяти, три гера 7 и схемы 8 сравнения, информационный вход 9 устройства, вход уст новки в исходное состояние 10, вход тактовых сигналов 11, группу входов задания констант 12, п-разрядный регистр 13 маски, входы которого являются входами устройства 14, двух входовые элементы 15, блокировочную шину 16. Устройство работает следующим образом. Под вьщелением числа с заданным рангом понимается нахождение в исходном массиве числа, относительная величина которого задана, начиная с минимального числа (например, найти девятое по величине число). Ранг чис ла R-это номер этого числа в отсортированном по возрастанию массиве чисел. Так, если необходимо найти девятое по величине число, то . В кольцевые сдвигающие регистры 5 при помощи импульсов, подаваемых на вход тактовых сигналов 11 устройства, записываются сортируекые числа, начиная со старших разрядов. На вход установки в исходное состояние 10 устройства подается импульс, который устанавливает триггер 7 в , при этом по блокировочному входу на входы синхронизации данных триггеров подается уровень логической , разрешающий установку триггеров в любое требуемое состояние. На управляющих входах элементов 6 памяти появляется разрешающий сигнал. На вход 12 задания константы подается константа сравнения А п+1 - R, где п - количество сортируемых чисел; R - ранг выбираемого числа. В п-разрядный регистр 13 маски через информационные входы 14 записываются единицы в те п-разрядов, которые соответствуют сортируемым числам, а в остальные (N-п) разрядов записываются нули. На первые входы элементов 15 И с соответствующих . элементов 6, памяти подаются сортируемые числа старшими разрядами вперед, а на вторые входы элементов 15 И подаются сигналы разрешения или запрещения с соответствующих выходов регистра 13 маски. После этого устройство переходит в режим выделения двоичного числа с наперед заданным рангом. Этот процесс проходит за m тактов, где т-разрядность сортируемых чисел. В первом такте на информационные входы элементов 6 памяти поступают значения старших разрядов чисел и проходят через схемы И на узел 3 анализа количества единиц. В этом узле подсчитывается количество единиц, содержащихся в стархиих разрядах сортируемых чисел и выдается результат подсчета на узел 2 сравнения. Если количество единиц в старших разрядах чисел не меньше константы сравнения А, то на выходе узла 2 , в противсравнения появляется Выходное значение ном случае узла 2 сравнения записывае гся в регистр 1 результата в качестве цифры старшего разряда выделяемого числа и подается на вторые входы схемы сравнения, на первые входы которых поступают сигналы старших разрядов сортируемых чисел. Каждая схема 8 сравнения выдает единичный сигнал, если значения, подаваемые на ее входы.,не совпадают, в противном случае - нулевой. Таким образом, если значения на выходах кольцевого сдвигающего регистра 5 и узла 2 сравнения не совпадают, то снимается разрешающий сигнал с соответствующего элемента 6 памяти, чем блокируется запись в него последующих значений в течение всех последующих тактов работы устройства. Заблокированный элемент 6 памяти выдает на элементы И, а затем на узел 3 анализа количества единиц то значение, которое было записано в него до снятия с управляющего входа разрешающего сигнала. Во втором такте на управляющий вход 11 устройства подается импульс по которому информация в регистрах 1 и 5 сдвигается на один разряд в сторонку старших разрядов. В дальнейшем устройство работает аналогично описанному.

После выполнейия m тактов в сдвигающем регистре 1 результата находится выделенное число, которое выводится из устройства.

Для обеспечения выполнения устроством функции выборки К из п на вход установки в исходное состояние 10 и на блокировочный вход 16 устройства подается импульс, который устанавливает триггер 7 в , после чего на блокировочный вход 16 подается уровень логического нуля и триггеры 7 запоминают исходное состояние, а на управляющих входах элементов 6 памяти в течении всего времени выборки установится разре- шающий сигнал.

В ir-M такте (где ,2,3,... ,т,гаразрядность анализируемых чисел) с выходов сдвиговых регистров 5 анализируемых чисел значения i-х р&зрядов поступают на элементы 6 памяти и проходят: на первые входы элементов 15 И, на вторые -входы которых поступают сигналы разрешения или

Ъапрета с соответствующих выходов регистра 13 маски. Текущие значения i-x разрядов выбранных регистров поступсиот на соответствукяцие входы узла 3 анализа количества единиц, где производится паргшлельная свертка числа единиц. Результат подсчета, представленный в прямом коде, поступает параллельно на первые входы узла сравнения 2, на вторые входы которого поступает константа сравнения, представленная в дополнительном коде, разрядностью Инверсия знакового разряда результата сравнения, получаемая на выходе узла 2 сравнения, поступает на информационный вход сдвигового регистра 1 результата.

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

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ И ВЫБОРКИ ИНФОРМАЦИИ, содержащее регистр результата, узел сравнения, узел анализа количества единиц и п узлов анализа несовпадения с константой сравнения (где п-количество сравнимых чисел) , каждый из которых состоит из кольцевого регистра сдвига, элемента памяти, триггера и блока сравнения, причем информационный вход кольцевого регистра сдвига каждого .i-ro узла анализа соединен с i-M информационным входом i устройства, где ,2,...,п, выход кольцевого регистра сдвига каждого узла анализа несовпсщения с константой сравнения подключен к входу соответствующего элемента памяти и первому входу блока сравнения, второй вход которого соединен с выходом узла сравнения, а выход - с входом установки в единичное состояние соответствующего триггера, вход установки в нулевое состояние которого подключен к шине начальной установки устройства, а выход - к входу разрешения записи соответствующего элемента.памяти, входы управления кольцевых регистров сдвига каждого узла анализа несовпадения с константой сравнения подключены к входу тактовых сигналов устройства, выходы узла анализа количества единиц соединены с входами первой группы узла сравнения, входы второй группы которого подключены к группе входов задания константы сравнения устройства, выход узла сравнения соединен с информационным входом регистра результата, управляющий вход которого подключен к входу тактовых сигналов устройства, узел анализа количества единиц содержит дешифратор, шифратор, элементы ИЛИ, причем входы узла анализа количества единиц соединены с входами дешифратора, кахсдый -и выход которого соединен с вхолюм j-ro элемента. ИЛИ, где е 1,2,. . .К,. j l,2,. . . , (m-1) , К - количество выходов дeшифpaтopa а о m - количество выходов с одинаковым количеством единиц во входном числе, (Л выход каждого j-ro элемента ИЛИ подключен к J-му входу шифратора, Bilхс1ды дешифратора, соответствующие и ,соединены с т- м и(т+1)-м входам шифратора соответственно, отличающееся тем, что, с целью расширения функциональных возможностей путем обеспечения возможности сортировки произвольно 00 меньшего, чем п, набора чисел, и vi выборки К из п, в него введен п-разрядный регистр маски и п двухвходных со элементов И, выходы которых соеди00 О) нены с соответствующими уходами узла анализа количества единиц, первый вход каждого i-го элемента И соединен с выходом элемента памяти i-го узла анализа несовпадения с константой сравнения, второй вход 1-го элемента И соединен с соответствующим выходом регистра маски, входы регистра маски являются входами задания набора чисел устройства, входы синх$--онизации трихтеров всех узлов анализа несовпадения с константой сравнения подключеньт к блокировочной шине устройства.