Устройство для выбора упорядоченной последовательности данных

,1059 19) 06 3(51) б 0 МИТЕТ СССРИЙ И ОТКРЫТИЙ ГОСУДАРСТВЕННЫЙПО ДЕЛАМ ИЗОБРЕТЕ ИЕ ПИ ЕТ ЕТЕЛЬСТВ. К АВТОРСКО ов ле на уп(56) 1. Авторское свидетельство СССР9 928342, кл. С Об7/06, 1980.2, Авторское свиДетельство СССРВ 903864, кл. 6 067/06, 1980(54)(57) 1. УСТРОЙСТВО для ВЬ)БОРАУПОРЯДОЧЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ДАННЫХ, содержащее входные регистры,дешифраторы, регистр результата, ягрупп элементов И, группу элементИЛИ, блок анализа, состоящий из эментов ИЛИ и поразрядных узлов ализа, причем выходы каждого 1-горегистра, где 1- = 1, 2. . . и , соединены с входами -го дешифратораи с инФормационньми входами элементов И 1"й группы, а выходы 1-го элемента ИЛИ подключены к входам управления элементов И 1-й группы,выходы элементов И каждой 1-й гр пысоединены с входами элементовИЛИгруппы, выходы которых подключены квходам регистра результата, каждыйу -ый выход каждого 1-го дешифраторасоединен с )-м входом 1-го поразрядного анализа, где ) =1, 2а,(И - число разрядов сортируемыхчисел), каждый 1-й выход )-го поразрядного узла анализа подключен к ) -мувходу .1"го элемента ИЛИ, а выходпереносов каждого %-го поразрядногоузла анализа, где М = 1, 2, , ((К+3)-го поразрядного узла анализа,каждый 4-й поразрядный узел анализасостоит из элементов И, ь. ,элементовНЕ и многовходового элемента И, причем кажФюй 1-й вход поразрядногоузла анализа подключен к первоМувходу 1-го элемента И, вход управления поразрядного узла анализа.соединен с в,торыми вхЬдами элементов И,каждый 1-й вход к-го поразрядногоузла аналиаа подключен через 1-йэлемент НЕ к ( 1 +2)-му входу (1+1),(1+2), , й -го элементов И и к3-му входу многовходового элемента И,выход которого подключен к выходупереносов )-го поразрядного узлаанализа, выход каждого -го элементаИ соединен с 1-м выходом )-го поразрядного узла анализа, П)-й пораз"рядный узел анализа состоит из элементов И и (П)-го элемента НЕ,причем каждый. р-й вход узла, гдеР.=1, 2, , (н.-1), соединен с пер"вым входом ф-го, элемента Ивходпереносов р-го поразрядного узла Еанализа подкюцочен к вторык входамэлементов И, каждый -й вход оч-гопоразрядного узла анализа через-й даавэлемент НЕ соединен с (р +2)-м вхо- %юедом (р+1), (р+2), , и -го элементов И, Ф -й вход,в-го поразрядного Яузла анализа подключен к (т+2-мувходу,п-го элемента И,выход каждо"го .1-го элемента И.соединен с-мвыходом в-го поразрядного узла Юанализа, о т л и ч а ю щ е е с ятем, что, с целью расширения егофункциональных возможностей путем ( Добеспечения воэможности получения ., уаупорядоченного массива чисел любого еффразмера и выдачи его на хранение, в ЯДнего введены блок управления,коммута.тор,0 регистров результата,где 9 23,Ь, Т групп элементов ЙЛИ,(1) групп элеменвов И, элементИЛИ, группы входнви элементов И иИЛИ, шины Начало операции,1,Начальноегашение 1.-и 1 Размер массива, причем 1"й вход блока анализа, соединенный с выходом )-го элемента ИЛИ блака анализа, подключенк первьм управлякщим входам )-хэлементов И в каждой из 0 групп, информационные входы которых соединены1059565 соединен с первым входом элемента И,второй вход которого соединен с прямым выходом триггера управления ипервыми входами элементов И группы,а выход - со счетным входом счетчиКа, информационные выходы которогоподключены к дешифратору,-й выходкоторого соединен с вторым входом-го элемента И группы, выход которого является т-м выходом блокауправления, выход сигнала переполне.ния счетчика прдключен к первому входуэлемента ИЛИ,.второй вход которогосоединен с шиной Начальное гашениеУа выход элемента ИЛИ.подключен кнулевому входу триггера управления,единичный вход которого соединен с .входом установки блока управления, аинверсный выход является управляющимвыходом блока управления, информационные входы блока управления подключены к установочным входам счетчика.2. устройство по п.1, о т л и ч аю щ е е с я тем, что коммутаторсодержит Ь групп элементов И, дешифратор, регистр, входы которого соединены с входами коммутатора, а выходы -с соответствующими входами дешифратора, .-й выход которого подключен кпервым входам 1, 2-х группэлементов И, информационные входы(-й группы коммутатора подключены квторым входам элементов И -й группырупразляющие входы элементовИ всех групп соединены суправляющим входом коммутатора,печивает формирование упорядоченой 10 последовательности чисел из исходных, что обуславливает Его низкие функциональные воэможности.Наиболее, близким к предлагаемому по технической сущности является устройство для определения наименьшего из и чисел, содержащее последовательно соединенные входные регистры,входы которых являются информаиионныс выходами-го входного регистра, и к первому входу, -го элемента И группы входных элементов И, вторые взводы всех элементов группы входных элементов И соединены с выходом элемента ИЛИ, выход л -го элемента группы входных элементов И соединен с первьм входом 1-го элемента группы входных элементов ИЛИ, выход которого подключен к входу установки в нуль л -го входного регистра,-й выход блока управления подключен к вторым управляющим входам всех эле.ментов И -й группы и к "му входу элемента ИЛИ, выходы элементов И . -й группы из (0 ф и ) групп подключены к соответствующим входам 1-го элемента ИЛИ 1 группы, выходы которого соединены с информационными входами-го регистра результата, группа информационных выходов-го регистра результата соединена с соответствующими информационными входа" ми"й группы коммутатора, выходы которого являются информационными . выходами устройства, управляющий вход коммутатора подключен к выходу блока Управления, шина, Начальное гашение соединена с входом установки блока управления, с нулевыми входами выходных регистров и с вторыми входами всех элементов группы входных элементов ИЛИ, шина ". Размер массивафф соединена с информационными входами коммутатора и блока,управления, который содержит триггер управления, счетчик, деиифратор, элементы И, ИЛИ, группу б элементов И, генератор импульсов, выход котЬрого 1Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации систем обработки данных и автоматизированных систем управления (АСУ).Известно устройство для сортировки чисел, содержащее й входных регистров, где й "число анализируемых чисел, и элементы И 11(.Однако данное устройство не обес 2ми входами устройства, дешифраторы, поразрядные узлы анализа и элементы ИЛИ, причем-й выход каждого -го деиифратора соединен с . "и входом1-го поразрядного узла анализа, где 1 т 1, 2,.;., и; ) =1,2, ,В, (очисло разрядов сравниваемых чисел), каждый 1-и выход )"го поразрядного узла анализа подключен к 1-муфвходу -го элемента ИЛИ, а выход переносов каждого Ф-го поразрядного узла анализа, где 1 с "1, 2 (в), соединен с входом управления (Ж+1)-го поразрядного узла анализа, каждый -й поразрядный узел анализа устройства состоит из и элементов И,п элементов НЕ и многовходового элемента И, причем каждый 1 -й вход узла анализа подключен к первомувходу 4-го элемента И, вход управления узла45 сординен с Вторнми входами элементови, каждый 1-й вход узла подключенчерез 1-й элемент НЕ к (1+2)-мувходу ( 1 +1), (1 +2).-го элементов И и к -му входу многовходового элемента и,выход которого подключенк выходу переносов узла, выход кажЛОго 1-го элемента И соединен с 1-мвыходом узла,т,-й поразрядный узеланализа состоит из 1 элементов И и(п), соединен с первич входомр-го элемента И, вход переносов узла подключен к вторил входам элементов И, каждыйр-й вход узла чЕрезр-й элемент НЕ соединен с (р+2)-мвходом (р+1), (р+2);н -гоэлементов И,п -й вход узла подключен к (п 1+2)-му входу я-го элементаИ, выход каждого 1-го элемента И соединен с Ф-м выходом узла Г 2 3Известное устройство обеспечиваетвыбор одного минимального из пчисел и для Формирования упорядоченной последовательности в очередном 25цикле работы необходимо выбрать из(Ф) оставшихся чисел наименьшеечисло,и т.д. и при этом организоватьхранение этих чисел во внешней памяти устройства. Таким образом, дляупорядбчения чисел требуется ь цяклов. Кроме того, в очередном циклеработы следует исключить из анализавыбранное в предыдущем цикле число.Пель изобретения - расширениеФункциональных воэможностей устройства путем обеспечения воэможностиполучения упорядоченного массивачисел любого размера и выдачи егона хранение.40Поставленная цель достигаетсятем, что в устройство для выбораупорядоченной последовательностиданньщ, содержащее входные регистры, дешифраторы, регистр результата, блок анализа, состоящий изэлементов ИЛИ и поразрядных узлованализа,п групп элементов И, Группуэлементов ИЛИ, причем выходы каждого (-ГО регистра, Где = 1, 2,..,М, соединены с входами 1.-го девиФратора и с информационными входамиэлементов И 1-й группы, а выходы1-го элемента ИЛИ подключены к входам управления элементов И -йгруппы, выходы элементов И каждой 1-й 55группы соединены с входами элементов ИЛИ группы, выходы которых подключены к входам регистра результата, каждый 1-й выход каждого 1 -годешиФратора соединен с ф -м входом 601-го поразрядного узла анализа, .где ) = 1, 2(сп - число разрядов сортируемых чисел), каждый.анализа подключен к-му Входу 1-Го 65 зламеента ИЛИ, а выход переносов каждогоЪ-го поразрядного узла анализа, где -1, 2,м" 1), соединен с входом управления (+1)-го поразрядного узла анализа, каждый Ф -й поразрядный узел анализа состоит из элементов И,о;.элементов НЕ и многовходового элемента И, причем каждый 1 -й вход поразрядного анализа подключен к первому входу 1-го элемента И, вход управления поразрядного узла анализа соединен с вторыми входами элементов И, каждый 1 -й вход М-го поразрядного узла анализа подключен через ( -й элемент НЕ к (1.+2)-му входу (1-+1), ( +2) .в -го элементов И и к 3-му входу многовходового элемента И, выход которого подключен к выходу переносов 1-го поразрядного узла анализа выход каждого 1-го элемента И соединен с 1-мвыходом к-го пораз рядного узла анализа, 61-й поразрядный узел анализа состоит из элементов И и (и)-го элемента НЕ, причем каждый ф-й вход узла, где р-.= 1, 2(ь), соединен с первым входом р -го элемента И, вход переносов Ит-го поразрядного узла анализа под.ключен к вторьи входам элементов И, каждый р-й вход п-Го поразрядного узла анализа через р-.й элемент НЕ сое- . динен с ( р+2)-м входом (р+1), (р+2),я -го элементов И, Ф-й вход в-го поразрядного узла анализа подключен.к. М+2)-му.входу о-го элемента И,.выход. каждого 1-го элемента И соединен с 1-ыа выходом 4 е-Го поразрядного узла анализа, введены коммутатор, блок управления, 2 регистров результата, где Я:2, 3 Ъ, 0 групп элементов ИЛИ, . ( 8 игрупп элементовИ, .элемент ИЛИ, .группы входных элементов И и ИЛИ шины Начало операции, Начальное гашение и Размер массива., причем 1-й выход блока анализа, соединенный.с выходом 1-го элемента ИЛИ блока анализа, подключен к первьм управляющим входам .1-х элементов И в .каждой из 1 групп, инФорационные входы которых соединены с выходами 1-Го входного регистра, и к первому входу 1-го элемента И группы входных. элементов И, вторые входы всех элементов группы входных Элементов .И соединены с выходом элемента ИЛИ, выход (-го элемента групйы входных элементов И соединен с первым. входом 1-го элемента груп" пы:входных элементов ИЛИ, выход которого подключен.к входу установки в нуль 1-го входного регистра, 1 -й выход блока управления подключен к вторьи управляющим входам всех элементов И -й Группы и,к -му входу элемента ИЛИ, выходв ЭЛЕМеНтОв И 1-й группы из ( 6 ь ) групп под 1059565ключены к соответствукщим входам1-го элемента ИЛИ 3 группы, выходыкоторого соединены с информационными входами 9 -го регистра результата,группа информационных выходов-горегистра результата соединена ссоответствующими информационнымивходами -й группы коммутатора, выходы которого являются информационными выходами устройства, управляющийвхоД коМмутатора подключен к выходублока управления, шина Начальноегашение соединена с входом установки блока управления, с нулевымивходами выходных регистрови с.вто-рыми входами всех элементов группы 15входных элементов ИЛИ, шина Рв.змермассива" соединена с информационными входами коммутатора и блокауправления, который .содержит триггеруправления, счетчик, дешифратор, 20элементы И, ИЛИ, группуэлементовИ, генератор импульсов, выход которого соединен с первЫм входом элемента И, второй вход которого соединен с прямым выходом триггера 25управления и первыми входами элементов И группы, а выход - со счетнымвходом счетчика, информационныевыходы которого подключены к дешифратору,-й выход которого соединен З 0с вторым входом -го.элемента Игруппы, выход которого является -мвыходом блока управления, выход сигнала переполнения счетчика подключенк первому входу элемента ИЛИ, второй З 5вход которого соединен с шинойффНачальное гашениеф, а выход элемента ИЛИ подключен к нулевому входутриггера управления, единичный входкоторого соединен с входом установкиблока управления, а инверсный выходявляется управляющим выходом блокауправления, информационные входы блокауправления подключены к установочнымвходам счетчика,Кроме того, коммутатор. содержит 45Ь групп элементов И, дешифратор,регистр, входЫ которого соединеныс входами коммутатора, а выходы -с соответствующими. входами дешифра. -тора, -й выход которого подключен 50к первым входам 1, 2-х группэлементов И, информационные входы1-й группы коммутатора. подключены квторым входам элементов И 1-йгруппы, управляющие входы. элементов 55И всех групп соединены с управляющим входом коммутатора.На фиг.1.показана блоксхема устройства; на фиг.2 -схема блока уп.равления;.на фиг.3. " схема коммутатора; на фиг.4 - схема блока анализа.Устройство содержит входные ин-Формационные шины 1-1 входныерегистры 2-2, дешифраторы 3-3 , у выходные шины 4,-4, которых подклю 6чены к блоку 5 анализа, выходныешины 6-6 блока анализа,о группно и элементов И 7 - 7 -.7в каждой группы элементов ИЛИ 8-8 ,л регистров 9 -9. результата,выходные шины, 10 -10 которыхподключены к коммутатору 11, и выходные шины 12 - 12 устройства,элемент ИЛИ 13, подключенный к вторым управляющим входам входных эле-,ментов И 14-14 группы,. выходы которых соединены с группой входныхэлементов ИЛИ 15-15, шину 16Размер массива, по которой подается информация о размере массивана выходе устройства, формируемогоиз о исхоцных чисел, блок 17 управления, обеспечивающий заданный режимустройства, выходные шины 18-18блока управления, шину 19 Йачалооперации, по которой поступаетсигнал запуска устройства, и шину20 Начальное гашениеф, по которойпоступает сигнал установки устройства в исходное состояние,Блок управления содержит выходнуюшину 21 . блока, элемен т ИЛИ 22, три ггер 2 3управления, .генератор 24 импульсовэлемент И 25, счетчик 26, накоторый принимается информация оразмере выходного массива по шине16, дешифратор 27 и ь элементовИ 28 -28,Коммутатор содержит регистр 29, накоторый принимается информация о раз-мере выходного массива по шине 16,дешифратор 30, обеспечивающий выдачумассива чисел, размер которого указанв регистре 29, через элементы И 31. -"31Блок анализа содержите поразрядных узлов 32-32 анализа каждый из коРкоторых,кройе пч-го,состоит из л эле"ментов НЕ 33, многовходового элементаИ 34,п элементов И 35, а,ъ -й узел 32анализа состоит из о)-х элементовНЕ 33, -33 и 6 элементов И35 -35., а также и элементов ИЛИ36.,-36,Устройство работает следующимобразом.На вход устройства может быть подан масоив 1 различных по значениючисел, причем 1 ( в. С помощью устройства необходимо расставитьчиселв.порядке из убывания, причем :61Задача сводится к определениюмаксимального числа, записи его в первый,выходной регистр и гашению тоговходного регистра, откуда оно передано в выходной для исключения анализа уже выбранного числа. Затем этотпроцесс повторяется, пока не выполнитсяциклов. По завершениициклов в выходных регистрах буДетнаходиться упорядоченная последователь ность чисел, составлякщих вырезанный массив размером вчисел из исходного массива в 1 чисел, причем 1 (и.управление формированием упорядоченного массива производится блоком управления на основе требуемого размера массива.Коммутатор обеспечивает выдачу упорядоченного массива из выходных регистров.Выбор максимального числа из массива исходных чисел в каждом цикле работы устройства производится в блоке анализа и основан на одновременном анализе одноименных выходов , 15 дешифраторов исходных чисел.Определение минимального :(максимального) числа сводится к анализу одноименных выходов дешифраторов, причем номер выхода, где имеется 20 неравнозначность или же единичные значения сигналов при равных числах, будет указывать на меньшее (большее 1 число. Если начать анализ с младших по номеру выходов дешифраторов, то 25 выбирается меньшее число, если со старших - то большее. Если на дешифраторы подать обратные коды чисел, то при анализе с младших выходоввыбирается большее число, а со стар ших - меньшее. В предлагаемом устройстве анализ одноименных выходов дешифраторов начинается с младших выходов дешиф раторов. Поэтому если необходимо получить упорядоченную последовательность из исходных чисел возрастающую, то исходные числа следует подавать в обратном коде, если 4 О убывакщую - то в прямом коде. Причем упорядоченный массив чисел представ. ляется в том же коде, что и исходные числа.Работа устройства начинается С установки входных регистров 2-2, выходных регистров 9-9 и трйггера 23 управления блока 17 управления в нулевые состояния сигналом, поступающим по шине 20 фНачальное гашение, после чего производится прием во входные регистры 2-2 чисел,пос тупающих по шинйм 1-1. По шине 16 Размер массива в счетчик 26 блока 17 управления и в регистр 29 коммутатора 11 и подается двоичный код требуемого размера массива. По окончании приема исходных чисел сигналом, поступающим по.шине 19 Начало операции, устанавливается в единичное состояние триггер, бО 23 управления блока 17 управления.Рассмотрим дальнейшую работу устройства при следукщих условиях необходимо получить возрастающую последовательность из Ф,чисел; 65 наибольшее число находится в регистре 2 , а наименьшее - в регистре 2.При этих условиях исходные числа необходимо подать во входные регистры 2-2 д в обратном коде. В счетчик 26 число принимается в дополнительном коде, а в регистр 29 - в прямом. Тогда в дешифраторе 30 ком-. мутатора 11 возбуждается р -й выход, разрешакщий формирование выходных сигналов на шинах 1 2-12устройства. В дешифраторе 27 блока управления возбужден выход, и, так как трИггер 23 управления находится в единичном состоянии, на выходной шкые 18 имеется единичный сигнал, разрешакщий работу элементов И 7,-7. Одновременно в блоке 5 анализа производится анализ выходных сигналов, поступакщих по шинам 4-4с дешифраторов 3-3. Так как найбольшее число находится в регистре 2, то в дешифратор 3 возбужден первый выход. При этом все первые выходы остальных дешифраторов нулевые, поэтому выходные единичные сигналы элементов НЕ 33:"-33,разрешают прохождение сигнала через элемент И 35в узле 32 анализа. Этот сигнал поступает через элемент И 35 на выходную шину бблока 5 анализа и разрешает через группу элементов И 7и элемент ИЛИ 8 второй группы передачу содержимого регистра 2: в регистр 9. результата. Этим же сигналом через элемен И 14 на первом входе которого действует единичный сигнал, с выхода 18 блока 17 управления через элемент ИЛИ 13 и -элемент ИЛИ 15 производится гашение регистра 2, чем исключается выбранное уже число из дальнейшего анализа в . очередном цикле. Очередной цикл начинается по импульсу от генератора 24 импульсов, который переводит счетчик 26 в очередное состояние, по которому возбуждается выход 182 блока 17 управления. Работа по анализу и передаче числа в выходной регистр 92 производится аналогично описанной.В последнем п-м цикле меньшее число окажется в выходном регистре 9,. По очередному импульсу ат генератора 24 импульсов в блоке 17 управления триггер 23 управления устанавливается в нулевое состояние сигналом переполнения счетчика 26, поступакщим на нулевой вход триггера управления через элемент ИЛИ 22.Единичный сигнал с нулевого выхода триггера по шине 21 поступает в коммутатор 11, и на выходные шины 12-12 устройства через элементы .И 31. -31, передается содержимое выходных регистров 9"9 по шинам 10 -10,представлякщее собой возрастающую последовательность из н исходных чисел.При необходимости получения убывающей последовательности из и чиселна входные шины 1.,-1устройстваподаются числа в прямом коде,Если необходимо получить последовательность чисел, вырезанную иэ иисходных чисел, по шине 1 б подаетсязначение размера массива, определяющего число циклов работы устройства.Работа устройства в дальнейшем неотличается от описанной эа исключени ем того,что в дешифраторе 30 коммутатора 11 будет возбужден выход, номеркоторого соответствует размеру требу-,емого массива.В соответствии с этимбудет возбуждено и необходимое число 15выходных шин 12 устройства.Таким образом, по сравнению с прототипом предлагаемое устройство имеет большие функциональные возможности,так как оно позволяет получить упорядоченный массив любого размерав пределах исходного,Проведем сравнительную оценку предлагаемого устройства и базового 25 объекта, в качестве которого выбран прототип, при использовании их в вычислительных системах, где требуется структурное преобразование массивов данных. 30Если испольэовать прототип, то для получения упорядоченного массива необходимо выполнить одинаковые действия, состоящие в передаче мас-, 35 сива чисел в устройство, причем в первом цикле очнсе 1 во втором (п -1) чисел и т.д., а в последнем цикле одно число, анализе и выборе наибольшего числа и передаче выбран ного числа в ЭВМ для заполнения упорядоченного массива,Если принять, что одно число педаеФся за один такт ЭВМ, а анализ и передача выбранного числа в ЭВМ 45 происходят тоже за.один таКт, то суммарное время Формирования.упорядоченного массива аостаэляет- "-п 1 +Ф, (п)1 ф 1+1 +Ф-1+й2 Фгде 1 з - время такта ЭВМ.Воспользовавшись формулой подсчета суммы первых л членов арифметической прогрессииа+ ф,Эо= 2 игде о- первый член арифметическойпрогрессии,о" М-й член арифметическойпрогрессии,получимй(п+ 3)+, (1)1При использовании предлагаемогоустройства необходимо передать массив исходных чисел в устройство заО тактов ЭВМ, выполнить и циклов вустройстве по анализу и передачевыбранного числа в выходной региструстройства,Тогда суммарное время формирования упорядоченного массива составитФу- п 1; +ьФ, = оФ +1 1, 22Сравнивая величины, получаемые.по выражениям (1) и (2), получимвыигрыш в быстродействииЕ. п( + з), ьэ . з)эПусть Ф:С, в:1 огиТогда по выражению (3) получим( (О з 1 з2(1+1 4Из выражения (3) следует, .что с увеличением размера преобразуемого массива чисел и приведенного расчета в связи с этим применение предлагаемого устройства более цеЛесообразно, так как обеспечивается снйжение общих затрат машинного времени.. Надь Корректор А, Тяско 842/53 Тираж 706ВНИИПИ Государствен по делам изобрете 13035, Москва, ЖииЗака д. 4/ аб. Филиал ППП фПатент , г.ужгород, улЛ 1 роектная Состктор Ъ.Ргар Техр ого коми й и откр Раушская эдписновта СССРий