Устройство для выбора упорядоченной последовательности данных Советский патент 1983 года по МПК G06F7/06 

с выходами -го входного регистра, и к первому входу i -го элемента И группы входных элементов И, вторые входы всех элементов группы входных элементов И соеди1аены с выходом элемента ИЛИ, выход .1-го элемента группы входных элементов И соединен с первым входом i-го элемента группы входных элементов ИЛИ, выход которого по(ключен к входу установк,и в нуль :i-го входного perHdTpa, i-и выход блока управления подключен к вторым управляюцим входс1м всех эле.ментов И 1-й группы и к i-му входу элемента ИЛИ, выходы элементов И .i -и группы из (е п) групп подключены к соответствующим входам -t-ro элемента ИЛИ 6 группы, В.ЫХОДЫ которого соединены с информационными входами е -го регистра результата, группа информационных выходов 1-го регистра результата соединен а с соответствующими информационными входами i-и группы коммутатора, выходы которого являются информационными выходами устройства, управляюиИй вхо коммутатора подключен к Выходу блока управления, шина, IНачальное гашение соединена с входом установки блока управления, с нулевыми входами выходных регистров и с вторыми входа1ми всех элементов группы входны элементов ИЛИ, шина Размер массива соединена с информационньми входами коммутатора и блока.управления, который содержит триггер управления, счетчик, дешифратор, элементы И, ИЛИ, группу элементов И, генератор импульсов, выход котброго

соединен с лервым входом элемента И, второй вход которого соединен с прямым выходом триггера управления и первыми входами элементов И группы, а выход - со счетным входом счетчиka, информационные выходы.которого подключенЕл к дешифратору, i -и выход которого соединен с вторым входом 1-го элембшта, И группы, выход которого является т-м выходом блока управления, выход сигнала переполнения счетчика прдключен кпервому вход элемента ИЛИ, второй вход которого Соединен с шиной . .Начальное гашение а выход элемента ИЛИ.подключен к нулевому входу триггера управления, единичный вход которого соединен с входом установки блока управленияр а инверсный выход является управлянвдим выходом блока управления, информационные входы блока управления подключены к установочным входам счетчика. . .., .

2. Уст1хэйство поп.1,отличаю щ е е с я тем, что коммутатор содержит Ь rpyftn элементов И, дешифратор, регистр, входы которого соединены с входами коммутатора, а выходы с сортаетеТВугацими входами дешифратора, i -и выход которого подключен к первым входам 1, 2,..., п-х групп элементов И, информационные входы i-й группы коммутатора подключены к вторым входам элементов И i-й группы/ упрайляющие входы элементов .И всех групп соединены с управляющим входом коммутатора.

1. УСТРОЙСТВО ДЛЯ ШБОРА УПОРЯДОЧЕННОЙ.ПОСЛЕДОВАТЕЛЬНОСТИ ДАННЫХ, содержащее.входные регистры, дешифраторы, регистр результата, ц групп элементов И, группу элементов ИЛИ, блок анализа, состоящий из элементов ИЛИ и поразрядных узлов анализа, причем выходы каждого i-ro регистра, где i. l, 2, ... n , соединены с входами i-ro дешифратора и с информационньми входа ми элементов И i-и группы, а выходы i-ro элемента ИЛИ подключены к входам управления элементов И i-ft группы, выходы элементов И каждой j-й группы соединены с входами элементовИЛИ группы, выходы которых подключены к входам регистра результата, каждый J -ый выход каждого 1-го дешифратора соединен с J-M входом поразрядного анализа, где j 1, 2,.. ., m, (m - число разрядов сортируемых чисел) , каждый i-й выход }-го поразрядного узла анализа подключен к j-му входу ;i-ro элемента ИЛИ, а выход переносов каждого Ic-ro поразрядного узла анализа, где 1с 1, 2,... , (fti-1), соединен с входом управления (К+1)-го поразрядного узла анализа, каждый поразрядный узел анализа состоит из элементов И, п. элементов НЕ и многовходового элемента И, причем кажйый Zi-й вход поразрядного уэла а нализа подключен к первому входу,1-го элемента И, вход управления поразрядного узла анализа.соединен с в,торыми вхйдами элементов И,, каждый Ч -и вход к-го поразряд1ного узла анализа подключен через i-й элемент НЕ к

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

Известно устройство для сортировки чисел, содер; ащее ih, входных регистров, где «-число анализируемых чисел, и элементы И

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

Наиболее, близким к предлагаемому по технической сущности является

устройство для определения наименьшего из п чисел, содержащее последовательно соединенные входные регистры входы которых являются информакионными входами устройства, дешифраторы, .поразрядные узлы анализа и элементы ИЛИ, причем -й выход каждого /j-го дешифратора соединен с .i -м входом -го поразрядного узла анализа, где 1 г 1, 2 ,. .. , и ; j 1, 2, . ., , rh , { m чисЛо раз:рядов сравниваемых чисел) , капдый Y-й выход j-го поразрядного узла анализа подключен к -мувходу 1-ГО-элемента ИЛИ, а выход переносов .каждого поразрядного узла анализа, где-Kil, 2,. .., (m-1), соединен с входом управления Ck+l)-ro пораэ 1Ядного узла анализа, каждый k-й поразрядный узел анализа устрой. ства состоит из П элементов И,п элементов НЕ и многовходового элемента И, причем каждый -i -и вход узла анализа подключен к первому входу i-ro элемента И, вход управления узла . соединен с вторьпии входами элементо И, каждый 1-и вход узла подключен через i-й элемент НБ к (+2)-му входу (+1), (), ...,h -го элементов И и к i-му входу многовходов го элемента И,выход которого подклю к выходу переносов узла, выход, кажл го i-го элемента И соединен с i -м выходом узла, т.-и поразрядный узел анализа состоит из V элементов И (n-l)-ro элемента НЕ, причем каждый р-й вход узла, где Р 1, 2, ... (п-1), соединен с первый входом р-го элемента И, вход переносов узла подключен к вторьм входе м элементов И, каждыйр-й вход узла чере (j-й элемент НЕ соединен с {р+2)-м. входом (p+l) , (р42) , ...,,п-го элементов И,гп-й вход узла подключен к (т+2)-му входу п-го элемента И, выход каждого i-ro элемента И со единен с t-м выходом узла 1:2 J. Известное устройство обеспечивае выбор одного минимального из п чисел и для формирования упорядоче ной последовательности в очередном цикле работы необходимо выбрать из (п-1) оставшихся чисел наименьшее число,и т.д. и при этом организоват хранение этих чисел во внешней памяти устройства. Таким образом, дл упорядочения чисел требуется h гиклов. Кроме того, в очередном цикле работы следует исключить из анализа выбранное в предьвдущем цикле число Цель изобретения - расширение функциональных возможностей устройства путем обеспечения возможности получения упорядоченного массива чисел любого размера и вьщачи его на хранение. Поставленная цель достигается тем, что в устройство для выбора упорядоченной последовательности данных, содержащее входные регистра, дешифраторы, регистр реэультата, блок анализа, состоящий из элементов ИЛИ и поразрядных узлов анализа,п групп элементов И, группу элементов ИЛИ, причем выходы каждого i-ro регистра, где 1, 2,..., , соединены с входами -го дешифратора, и с информационными входами элементов И -й группы, а выходы i-ro элемента ИЛИ подключены к входам управления элементов И i-й группы, выходы элементов И каждой i группы соединены с входами элементов ИЛИ группы, выходы которых подключены к входам регистра результата, каждый j-й выход ка ждого i -го дешифратора соединен с о-м входом j-rp поразрядного узла анализа, . где , 2,...,m(in- число разрядов сортируемых чисел), каждый i-й выход j-ro поразрядного узла .анализа подключен к j-му входу Ч-го элемента ИЛИ, а вьжод переносов каждого V- го поразрядного уэла анализа, где Vsi, 2, ..., (tin-1), соединен с входом управления (It-H)-ro поразрядного узла анализа, каясдый ti-й поразрядный узел анализа состоит из элементов И,rt; элементов НЕ и многовходового элемента И, причем- каждый i-и вход поразрядногб анализа подключен к первому вхдду 1-го элемента И, вход управления поразрядного узла анализа соединен с вторыми входами элементов И, каждый i-и вход V-го поразрядного узла анализа подключен через 5.-и элемент НЕ к (.+2)-му входу (i-+l), (i +2) , .. ., и -го элементов И и к i-му входу многовходового элемента И, выход которого подключен к выходу переносов It-го поразрядного узла . анализа, выход каждого i-ro элемента И соединен с i-мвыходом 1с-го пораз- рядного узла анализа, hi-и поразрядный узел анализа состоит из элементов И и (п-1)-го элемента НЕ, причем каждый вход узла, где , 2,..., .. ., (h-1) , соединен с первым входом р -го элемента И, вход переносов ; ht-ro поразрядного узла анализа подключен к вторым входам элементов И, каждый р-й вход т-го поразрядного узла анализа через р-й элемент НЕ соединен с ( р+2)-м входом (р+1), (р+2) , ..., rt -го элементов И, rt -и вход т-го поразрядного уэла анализа подключен .к (h+2)-My.входу п-го элемента И, выход каждого i-ro элемента И соединен с Ч-ым выходом t«-го Поразрядного узла анализа введены коммутатор, блок управления, С регистров результата, где в 2, 3 , . .., ,Н , С групп элементов ИЛИ, { в h ) rpjmn элементов . И, элемент ИЛИ, группы входных эл ементов И и ИЛИ ошны Начало операции, Начальное гашение и Размер массива , причем -и выход блока анализа, соединенный с выходом i-ro элемента ИЛИ блока анализа, подключен к первым управЛЯЮ14ИМ входам 1-х элементов И в каждой из е групп, инфоредионные входы которых соединены с выходами В-го входного регистра, и к первому входу i -го элемента И группы входных элементов И, вторые входы всех элементов группы входных элементов И соединены с выходом элемента ИЛИ, выход 1-го элемента группы входных элементов И соединен с первым входом i-го элемента группы входных элементов ИЛИ, выход которого подключен к в,ходу установки в нуль i-ro входного регистра, i -И выход блока управления подключен к BfopEM управляющим входам всех элементов И -г-й группы и ,к i -му входу элемента ИЛИ, выходы элементов И Ч-и группы из ( Ё h ) групп подключены к соответствуюцим входам 1-го элемента ИЛИ Е группы, выходы которого соединены с информационными входами в -го регистра результата группа информационных выходов -i-го регистра результата соединена с соответствующими информационньми входами i-й группы коммутатора, выходы которого являются информационны ми выходами устройства, управляющий вход KONtMyTaTopa подключен к выходу блока управления, шина Начальное гашение соединена с входом установ ки блока управления, с нулевыми входами выходных регистров.Ht-c.. вторыми входами всех элементов группы входных элементов ИЛИ, шина Рй.змер массива соединена с инфор- ационны ми входами к.оммутатора и блока . управления, который содержит триггер управления, счетчик, дешифратор, элементы И, ИЛИ, группу п элементов И, генератор импульсов, выход которого соединен с первьйм входом элемента И, второй вход которого соединен с прямьм выходом триггера управления и первыми входами элемен тов И группы., а выход - со счетным входом счетчика, информационные выходы которого подключены к дешифратору, 1 -и выход которого соединен с вторым входом 1-го., элемента И группы, выход которого является i-м выходом блока управления, выход сиг нала переполнения счетчика подключе к первому входу элемента ИЛИ, второ вход которого соединен с шиной Начальное гашение, а выход элемента ИЛИ подключен к нулевому вход триггера управления, единичный вход которого соединен с входом установк блока управления, а инверсный выход является управляющим выходом блока управления,информационные входы бло управления подключены к устанойочны входам счетчика. Кроме того, коммутатор .содержит h групп элементов И, дешифратор, регистр, входы которого соединены с входами коммутатора, а выходы С соответствующими.входами дешифратора, 1-й ВЫХ.ОД которого подключен к первым входам 1, 2,..., i-х групп элементов И, информационные входы 1-й группы коммутатора.подключены к вторым входам элементов И i-и группы, управляющие входы.элементов И всех групп соединены с управляющим входом коммутатора. На фиг. 1 показана блок « схема уст ройства; на фиг,2 - схема блока уп.равления;.на фиг.З. - схема коммутатора; на фиг.4 - схема блока айали за. . . . . Устройство содержит входные информационные шины 1.-1„, входные регистры , дешифраторы , выходные .шины . которых подключены к блоку 5 анализа, выходные шины 6j|-6n блока анализа,п групп по пэлементов И 7j,- Ti,,. . ., , в каждой группы элементов ИЛИ р, /1 регистров 9.j-9f,..- результата, выходные ШИНЫ- которых подключены к коммутатору 11, и выходные шины 12;,- 12 устройства, элемент- ИЛИ 13, подключенный к вторым управлякщим входам входных эле-, ментов И I4f,-14.j группы,, выходы которых соединены с группой входных элементов ИЛИ I5.i-15, шину 16 Размер массива, по которой подается информация о размере массива на выходе устройства, формируемого из h исходных чисел, блок 17 управления, обеспечивающий заданный режим устройства, выходные шины , блока управления, шину 19 Начало операции , по которой поступает сигнал запуска устройства,.и шину 20 Начальное гашение, по которой поступает сигнал установки устройства в исходное состояние. , Блок управления содержит выходную шину 21 .блока,элемент ИЛИ 22,триггер 23 управления, ..генератор 24 импульсов элемент и 25, счетчик 26, на который принимается информация о размере в лходного массива по шине 16, дешифратор 27 и п элементов И 28 ,-28,. Коммутатор содержит эегистр 29, на который принимается информация о размере выходного массива по шине 16, дешифратор 30, обеспечивающий выдачу массива чисел, размер которого указан в регистре 29, через элементы И 31. -31, Блок анализа содержитm поразрядных узлов 32-32 анализа каждый из кО которых,кроМе т-го, состоит из п элементов НЕ 33, многовходового эл.емента И 34,п элементов И 35, a.m-и узел 32 йнализа состоит из Cri-l)-x элементов (r, и п элементов И , а также п элементов ИЛИ , Устройство работает следующим образом. На вход устройства может быть подан масошз различных по значению чисел, причем п,. С помощью устройства необходимо расставить § чисел .Б .порядке из убывания, причем . Задача сводится к определению максимального числа,записи его в ,выходной регистр и гашению того входного регистра, откуда оно передано в вькодной для исключения анализа уже выезранного числа. Затем этот процесс повторяется, пока не выполнится циклов. По завершении е- циклов в выходных регистрах будет находиться упорядоченная последовательность чисел, составлякадих вырезанный массив размером в чисел из исходного массива в ц чисел, причем г . Управление формированием упорядо ченного массива производится блоком управления на основе требуемого раз мера массива. Коммутатор обеспечивает вьщачу упорядоченного массива из выходных регистров. Выбор максимального числа из мас сива исходных чисел в каждом цикле работы устройства производится в блоке анализа и основан на одновременном анализе одноименных выходов дешифраторов исходных чисел. Определение минимального Чмаксимального) числа сводится к анализу одноименных выходов дешифраторов, причем номер выхода, где имеется неравнозначность или же единичные значения сигналов при равных числах будет указывать на меньшее (большее число. Если начать анализ с младших по номеру выходов дешифраторов, то выбирается меньшее число, если со старших - то большее. Если на дешифраторы подать обратные коды чисе то при анализе с младших выходов выбирается большее число, а со стар ших -.меньшее. В предлагаемом устройстве анализ одноименных выходов дешифраторов начинается с младших выходов дешифраторов. Поэтому если необходимо получить упорядоченную последовательность из исходных чисел возрастакяцую, то исходные числа следует подавать в обрао ном коде, если убывагадую - то в прямом коде. Приче упорядоченный массив чисел представ ляется в том же коде, что и исходные числа. Работа устройства начинается с установки входных iэeгиcтpoв ,, выходных регистров 9-,-9j, и триггера 23 управления блока 17 управления в нулевые состояния сигналом, поступающим по шине 20 Начальное гаш ние , после чего производится прием во входные регистры 2-,-2 чисел,пос тупающих по шинАм 1-,-lf,. По шине 16 Размер массива всчетчик 26 , блока 17 управления и в регистр 29 коммутатора 11 и подается двоичный код требуемого размера массива. По окончании приема исходных чисел сигналом, поступающим по.шине 19 Начало операции, устанавливаетс в. единичное состояние триггер, 23 управления блока 17. управления. Рассмотрим дальнейшую работу устройства при следующих условиях t необходимо получить возрастакяцую послёдовагельность из rt . чисел; наибольшее число находится в регистре 2, а наименьшее - в регистре 2,, При этих условиях исходные числа необходимо подать во входные регистры 2 .,-2 п в обратном коде. В счетчик 26 число принимается в дополнительном коде, а в регистр 29 - в п эямом. Тогда в дешифраторе 30 ком-, мутатора И возбуждается щ-и выход, разрешающий формирование выходных сигналов на шинах , устройства. В дешифраторе 27 блока управления возбужден выход, и, так как триггер 23 управления находится в единич ном состоянии, на выходной шкые 18 имеется единичный сигнал, разрешающий работу элементов И . Одновременно в блоке 5 анализа производится анализвыходных сигналов, поступающих по шинам , с дешифраторов . Так как наибольшее число находится в регистре 2, то в дешифратор 3 возбужден первый выход. При этом все первые выходы остальных дешифраторов нулевые,, поэтому выходные единичные сигналы элементов НЕ 33с, . раз решают прохождени.е сигнала через элемент И 35:,.f, в узле 32 анализа. Этот сигнал поступает через элемент И 35, на выходную шину 6 j, блока 5 анализа и разрешает через группу элементов И 7 f, и элемент ИЛИ 8- второй группы передачу содержимого регистра 2j в регистр 2,- результата. Этим же сигналом через элемен И 14, на первом входе которого действует единичный сигнал, с выхода 18блока 17 управления через элемент ИЛИ 13 и -элемент ИЛИ 15 производится гашение регистра 2, чем исключается выбранное уже число из дальнейшего анализа в очередном цикле. Очередной цикл начинается по импульсу от генератора 24 импульсов, который переводит счетчик 26 в очередное состояние, по которому возбуждается выход 182 блока 17 управления. Работа по анализу и передаче числа в выходной регистр 9 производится аналогично описанной. В последнем п-м цикле меньшее число окажется в выходном регистре 9. По очередному импульсу от генератора 24 импульсов в блоке 17 управления триггер 23 управления устанавливается в нулевое состояние -сигналом переполнениясчетчика 26, поступающим на нулевой вход триггера управлення .через элемент ИЛИ 22.Единичный сигнал с нулевого выхода триггера по шине 21 поступает в коммутатор 11, и на выходные шины устройства через элементы .И , передается содержимое .выходных регистров 9-,-9 по шинам 10, -10f,,представляющее собой возрастающую последовательность из п исходных чисел. При необходимости получения убывапщей последовательности из п чисел на входные шины устройства подаются числа в прямом коде. Если необходимо получить последо нательность чисел, вырезанную из п исходных чисел, по шине 16 подается значение размера массива, определяющего .число циклов работы устройства Работа устройства в дальнейшем не отличается от описанной-за исключен ем того,что в дешифраторе 30 коммут тора 11 будет возбужден выход,номер которого соответствует размеру требу ;емого массива.В соответствии с этим будет возбуждено и необходимое числ выходных шин 12 устройства. Таким образом, по сравнению с про тотипом предлагаемое устройство имеет большие функциональные возможност так как оно позволяет получить упорядоченный массив любого размера в пределах исходного. Прюведем сравнительную оценку предлагаемого устройства и базового объекта, в качестве которого выбран прототип, при использовании их в вычислительных системах, где требуется структ5фное преобразование массивов данных. Если использовать прототип, то дл получения упорядоченного массива необходимо вьшолнить одинаковые :действия, состоящие в передаче массива чисел в устройство, причем в первом цикле пчисеЛ, во втором (п-1) чисел и т.д., а в последнем цикле одно числоу анализе и выборе наибольшего числа и передаче выбран ного числа в ЭВМ для заполнения упордяоченного массива. .; Если принять, что одно число пёдaetcя за один такт ЭВМ, а анализ -и передача выбранного числа в ЭВМ происходят тоже за один lakT, то суммарное время фО 1ирования . упорядоченного массива боставляет t.nt,.t.tn-i)i,tj.....t.t. n+1+n+.,. + 2j tj , где ij - время такта ЭВМ. Воспользовавшись формулой подзчетй суммы первых h членов арифмеической прогрессии «.«п первый член арифметической прогрессии, а|.,--И|-й член арифметической прогрессии, олучим t/, (,, При использовании предлагаемого устрюйства необходимо передать массив исходных чисел в устройство за П тактов ЭВМ, выполнить п циклов в устройстве По анализу и передаче выбранного числа в выходной регистр устройства. Тогда суммарное время формирования упорядоченного массива составит ,nt,cn{t,.t,J . (2Г Сравнивая величины, получаемые по выражениям (1) и (2), получим выигрыш в быстродействии t .,„.я,. 5, (VVJn-. пусть .± Тогда по выражению (3) получим ,. Из выражения (3) следует,-.что с увеличением размера преобразуемого массива и приведенного расчета в связи с этим применение предлагаемого устройства более целесообразно, так как обеспечивается снижение общих затрат машинного времени .

//%

t t

-

- -АЛ

F1