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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ И ВЫБОРКИ ИНФОРМАЦИИ, содержащее регистр результата, узел сравнения, узел анализа количества единиц и п узлов анализа несовпадения с константой сравнения (где п-количество сравнимых чисел) , каждый из которых состоит из кольцевого регистра сдвига , элемента памяти, триггера и блока сравнения, причем информационный вход кольцевого регистра сдвига каждого .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-го элемента И соединен с соответствующим выходом регистра маски, входы регистра маски являются входами задания набора чисел устройства, входы синх$--онизации трихтеров всех узлов анализа несовпадения с константой сравнения подключеньт к блокировочной шине устройства.

87986 A

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19> S 0 (и ) 3(511 6 06 Е 7 06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

hO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3557294/18-24 (22) 28. 02. 83 (46) 23.04.84. Бюл. М 15 (72) A.N.Êåíèí и Е.К.Пьянков (53) 681. 325.5 (088.8) (56) 1. Авторское свидетельство СССР

9 610107, кл.6 06 F 7/06, 1975.

2. Авторское свидетельство СССР

М 943707, кл. Q 06 F 7/06, 1980 (прототип) . (54). (57) УСТРОЙСТВО 1(ЛЯ СОРТИРОВКИ

И ВЫБОРКИ ИНФОРМАЦИИ, содержащее регистр результата, узел сравнения, узел анализа количества единиц и и узлов анализа несовпадения с константой сравнения (где и-количество сравнимых чисел), каждый йз которых состоит из кольцевого регистра сдвига, элемента памяти, триггера и блока сравнения, причем информационный вход кольцевого регистра сдви«

ra каждого .i-ro узла анализа соединен с i-м информационным входом устройства, где i=1 2,...,n, выход кольцевого регистра сдвига каждого узла анализа несовпадения с константой сравнения подключен к входу соответствующего элемента памяти и первому входу блока сравнения, второй вход которого соединен с выходом узла сравнения, а выход — с входом установки в единичное состояние соответствующего триггера, вход установки в нулевое состояние которого подключен к шине начальной установки устройства, а выход — к входу разрешения записи соответствующего элемента, памяти, входы управления кольцевых регистров сдвига каждого узла анализа несовпадения с константой сравнения . одключены к входу тактовых сигналов устройства, выходы узла анализа количества единиц соединены с входами первой группы узла сравнения, входы второй группы которого подключены к группе входов задания константы сравнения устройства, выход узла сравнения соединен с информационным входом регистра результата, управляющий вход которого подключен к входу тактовых сигналов устройства, узел анализа количества единиц содержит дешифратор, шифратор, элементы ИЛИ, причем входы узла анализа количества единиц соединены с входами дешифратора, каждый t -й выход которого соединен с входом j-го элемента. ИЛИ, где 0 =. l, 2,... К,. 3 = 1, 2,..., (m-l ), К вЂ” количество выходов дешифратора, m — количество выходов с одинаковым у количеством единиц во входном числе, выход каждого j-го элемента ИЛИ подключен к j — му входу шифратора, вйходы дешифратора, соответствующие С

j =0 и j =m, соединены с m- м и (m+1) -м входам шифратора соответственно, ф о т л и ч а ю щ е е с я тем„ что с с « «,«, целью расширения функциональных возможностей путем обеспечения воз- CO можности сортировки произвольно меньшего, чем и, набора чисел, и выборки К из и, в него введен п-ðàçрядный регистр маски и и двухвходных ц> элементов И, выходы которых соединены с соответствующими, входами узла 90 анализа количества единиц, первый вход каждого 1-го элемента И соединен с выходом элемента памяти i ãî узла анализа несовпадения с константой сравнения, второй вход 1-ro элемента И соединен с соответствую- «ф» щим выходом регистра маски, входы регистра маски являются входами задания набора чисел устройства, входы синхронизации триггеров всех узлов анализа несовпадения с константой сравнения подключены к блокировочной шине устройства.

1087986

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

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

Недостатком этого устройства являются ограниченные функциональные возможности, Наиболее близким по технической сущности к предложенному является устройство для сортировки чисел, содержащее регистр результата, узел сравнения и узел анализа количества единиц, и узлов анализа, каждый из которых состоит из кольцевого регист- 0 ра сдвига, элемента памяти, триггера и схемы сравнения, причем выходы узла анализа количества единиц соединены с входами первой группы узла сравнения, входы второй группы которого подключены к. группе входов задания константы устройства, выход узла соединен с информационным входом регистра результата, управляющий вход которого подключен к входу тактовых сигналов устройства, информационный вход кольцевого регистра сдвига каждого i-го узла анализа соединен с i-м информационным входом устройства, где i=1 2,...,n, выход кольцевого сдвига каждого узла ана- 35 лиза подключен к входу элемента памяти и первому входу схемы сравнения, aropoA вход которой соединен с выходом узла сравнения, а выход с входом установки в единичное сос- 40 тояние триггера, вход установки в нулевое состояние которого подключен к входу управления устройства, а выход — к входу управления элемента памяти, выход элемента памяти 45 каждого i-ro узла анализа соединен с i-м входом узла анализа количества единиц, входы управления кольцевых регистров сдвига каждого узла анаяти.,за подключены ко входу тактовых сиг.налов устройства, узел анализа количества единиц состоит из деыифраI тора, шифратора, элементов ИЛИ, причем входы узла анализа соединены со входами дешифратора, каждый f.-ый вы- ход которого соединен со входом

j-го элемента ИЛИ, где 0=1,2,..., К, (=1,2...,,(m-1), К вЂ” количество выходов дешифратора, m — количество выходов с одинаковым количеством единиц во входном канале, выход 60 каждого j-го элемента ИЛИ подключен к j — му входу шифратора, выходы дешифратора, соответствующие j=0 и

j, соединены с m-ым и (m+1)-м входами шифратора соответственно 2 . g5

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

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

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

Поставленная цель достигается тем, что в устройство для сортировки и выборки информации, содержащее регистр результата, узел сравнения, узел анализа количества единиц и и узлов анализа несовпадения с константой сравнения (где и-количество сравнимых чисел), каждый из которых состоит из кольцевого регистра сдвига, элемента памяти, триггера и блока сравнения, причем информационный вход кольцевого регистра сдвига каждого i-ro узла анализа соединен с

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

=1,2,...,К, =1,2,...,(т-1), К количество выходов дешифратора, mколичество выходов с одинаковым количеством единиц во входном числе, выход каждого j-ro элемента ИЛИ подключен к j-му входу шифратора, выходы

1087986

40 дешифратора, соответствующие j =0 и

j, соединены с m- м и (m +1)-м входами шифратора соответственно, с целью расширения, функциональных возможностей путем обеспечения возможности сортировки произвольно меньшего, чем и, набора чисел, и выборки

К из п, в него введен и-разрядный регистр маски и и двухвходных элементов И, выходы которых соединены с соответствующими входами узла анали- 10 за количества единиц, первый вход каждого i ãî элемента И соединен с выходом элемента памяти i-го узла анализа несовпадения с константой сравнения, второй вход i-го элемента 5

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

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

Устройство содержит сдвигающий регистр 1 результата, узел 2 сравнения, узел 3 анализа количества единиц, п узлов 4 анализа, каждый из которых состоит из кольцевого регистра 5 сдвига, элемента б памяти, триг-З0 гера 7 и схемы 8 сравнения, информационный вход 9 устройства, вход установки в исходное состояние 10, вход тактовых сигналов 11, группу входов задания констант 12, n — разрядный 35 регистр 13 маски, входы которого являются входами устройства 14, двух- входовые элементы 15, блокировочную шину 16.

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

Под выделением числа с заданным рангом понимается нахождение в исходном массиве числа, относительная величина которого задана, начиная с 45 минимального числа (например, найти девятое по величине число). Ранг числа R-это номер .этого числа н отсортированном по возрастанию массиве чисел. Так, если необходимо найти девятое по величине число, то R=9.

В кольцевые сдвигающие регистры 5 при помощи импульсов, подаваемых на вход тактовых сигналов 11 устройства, записываются сортируеьые числа, начиная со старших разрядов. На 55 вход установки в исходное состояние

10 устройства подается импульс, который устананлинает триггер 7 в 1, при этом по блокироночному входу на входы синхронизации данных 60 триггеров подается уровень логической 1, разрешающий установку триггеров н любое требуемое состояние. На управляющих нходах элементон 6 памяти появляется разрешающий 65 сигнал. На вход 12 задания константы подается константа .сравнения

A -= -n+1 — Rt где n — количество сортируемых чисел;

R — ранг выбираемого числа.

В п ðàçðÿäíûé регистр 13 маски через информационные входы 14 записываются единицы в те п ðàçðÿäîí, которые соответствуют сортируемым числам, а в остальные (N — n) разрядов записываются нули. На первые входы элементов 15 И с соответстнующих . элементов б,памяти подаются сортируемые числа старшими разрядами вперед, а на вторые входы элементов 15 И подаются сигналы разрешения или запрещения с соответствующих выходов регистра 13 маски.

После этого устройство переходит в режим выделения двоичного числа с наперед заданным рангом.

Этот процесс проходит за т тактов, где m ðàçðÿäíîñòü сортируемых чисел.

В первом такте на информационные входы элементов 6 памяти поступают значения старших разрядов чисел и проходят через схемы И на узел 3 анализа количества единиц. В этом узле подсчитывается количество единиц, содержащихся в старших разрядах сортируемых чисел и выдается результат подсчета на узел 2 сравнения °

Если количество единиц в старших разрядах чисел не меньше константы сравнения А, то на выходе узла 2 сравнения появляется 1, в противном случае 0 . Выходное значение узла 2 сравнения записывается в регистр 1 результаTà в качестве цифры старшего разряда выделяемого числа и подается на вторые входы схемы сравнения, на первые входы которых поступают сигналы старших разрядов сортируемых чисел. Каждая схема 8 сраннения выдает единичный сигнал, если значения, подаваемые на ее входы,не совпадают, в противном случае — нулевой. Таким образом, если значения на выходах кольцевого сднигающего регистра 5 и узла 2 сравнения не совпадают, то снимается разрешающий сигнал с соответстнующего элемента б памяти, чем блокируется запись в него последующих значений в течение всех последующих тактов работы устройства.

Заблокированный элемент б памяти выдает на элементы И, а затем на узел 3 анализа количества единиц то значение, которое было записано н него до снятия с управляющего входа разрешающего сигнала. Во втором такте на управляющий вход 11 устройства подается импульс по которому информация в регистрах 1 и 5 сдвигается на один разряд в стор ну старших разрядов. В дальнейшем ус тройстно работает аналогично опи:анному.

1087986

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

Для обеспечения выполнения устройством функции выборки К из и на вход установки в исходное состояние

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

В i †.м такте(где i=1 2,3,. ° .,m,m-. разрядность анализируеьвюх чисел) с выходов сдвиговых регистров 5 анализируемых чисел значения i-х разрядов поступают на элементы 6 памяти и проходят . на первые входы элементов 15 И, на вторые -входы которых поступают сигналы разрешения или запрета с соответствующих выходов регистра 13 маски. Текущие значения

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

1 результата.

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

ВНИИПИ 3 аказ 26 7 3/4 5

Тираж 699 Подписное

Филиал ППП "Патент", г.ужгород,ул.Проектная,4