Устройство для ранжирования чисел

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН а 1 С 06 Е 7(06 АРСТВЕННЫй КО ЛАМ ИЗОБРЕТЕНИ СР1.ТИЙ ПИСАНИ АВТОРСКОМУ ЭОБРЕТЕНИидвтвъстви л а 64,1974.тво СССР06 Г 7/06,Ряд а- океги анж(54)(57) УСТРОЙСТВО ДЛЯ РАНЖИРОВАННЯЧИСЕЛ, содержащее (й)т-разрядныхрегистров сдвига, где ч - числосортируемых чисел,(М-схем сравнения двухи-разрядных чисел и блокподсчета номера ранга входного числа,причем выход 1-го в-разрядногорегистра сдвига, где 1=1,2(ч),соединен с первым входом 1-й схемысравнения, выход 1-го гл -разрядногорегистра сдвига,где 1=1,2 (,й),соединен с входом(+1)-го п-разрядно-го регистра сдвига, вторые входывсех схем сравнения подключены кшине входных чисел и входу первогов -разрядного регистра сдвига, авыходы - к входам блока подсчетаномера ранга входного числа, шинасдвига устройства соединена с синхронизирующими входами всех пч -разных регистров сдвига, о т л и чю щ е е с я тем, что, с целью сращения аппаратурных затрат прибольших значениях Н, устройствосодержит М ь -разрядных регистровсдвига, где,п - количество разрядов 8011097 ранга, и ( - 11 корректоров ранга, корректор Ранга .содержит две схемы сравнения и Ь -разрядный сумматор, причем выходы блока подсчета номера ранга входного числа подключены к входам первого я -разрядного регист" ра сдвига, выходы которого подключены к соответствующим входам первой группы сумматора первого корректора ранга и соответствующим, входам первых групп первых схем сравнения всех корректоров ранга, входы вторых групп схем сравнения первого корректора ранга и входы первых групп вторых схем сравнения всех корректо" ров ранга соединены с соответствующими выходами 8-го и -разрядного регистра сдвига, выходы Ь-разрядного сумматора 1-го корректора ранга под" ключены к соответствующим входам+1)-го Ь -разрядного регистра сдвига и выходам ранга 1-го числа устройства, выходы .-го и -разрядногорегистра сдвига, где к=2,3,. 44 1) подключены к входам первой группы п-разрядного сумматора и входам вторых групп схем сравнения %-го корректора ранга, в каждом корректоре ранга выход первой схемы сравнения соединен с входом переноса сумматора, выход второй схемы сравнения подключен к объединенным входам р-разрядного суммарора, синхронизирующие входы всех и-разрядных регистров сдвига соединены с шиной сдвига устройства, выходы е-,разрядных р стров сдвига являются выходами р ируемых чисел устройства.Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных. 5Известно устройство для ранжирования чисел, содержащее регистр сдвига для хранения чисел, буферный регистр эталонного числа, схему сравнения устройства подсчета номера ранга, Ю элементы И,И 1 И, блок управления, блок синхронизации, счетчик циклов сравнения, счетчик числа величин, блок определения конца цикла сравне" ния и блок индикации результата Г 11 15Это устройство служит для определения ранга числа, принятого за эталонный из последовательности чисел за циклом, Для определения рангов всех чисел последовательности в 20 этом устройстве потребуется К тактов.Наиболее близким к предлагаемому по технической сущности является устройство, которое обладает более высоким быстродействием и решает 25 задачу определения в течение одного . такта рангов всех чисел последовательности, содержащее (и)регистров сдвига п -разрядных чисел,(Ксхем сравнения двух в -разрядных 30 чисел, К блоков подсчета номера ранК-Э К+гга,одноразрядных регистровМ(8-1)и2элементов НЕ выход 1-го регистра сдвига, где 1=2,3(К -1), соединен с первым входом 1-й схемы сравнения, вторые входы схем сравнения соединены с шиной входных чисел и с входом первого регистра сдвига, 40 вход 1-го регистра сдвига соединен с выходом Ь в )-го регистра сдвига, выход 1-й схемы сравнения, где =1,2(К), подключен к входу первого одноразрядного регистра из цепочки последовательно соединенных (К - 1 -)одноразрядных регистров, к одному из входов первого блока подсчета номера ранга и через соответствующий элемент НЕ к одному из вхо-,50 дов ( +1)-го блока подсчета ранга, выход к-го одноразрядного регистра в ) -й цепочке одноразрядных регистров, где к=1, 2(Й -1 - 1), подключен к одному из входов (к+1) -го блока подсчета номера ранга и через55 соответствующий элемент НЕ к одному из входов(к++1)-го блока подсчета номера ранга, синхронизирующие входы всех регистров соединены с шинойсигналов сдвига устройства, блокподсчета номера ранга содержит сумматор с(К)входами, соединеннымис входами блока подсчета номера ранга, а выход сумматора соединен с выходом блока подсчета номера ранга 2).Недостатком известного устройстваявляется усложнение устройства с ростом количества сортируемых чисел.Цель изобретения - сокращениеаппаратурных затрат при больших значениях К,Поставленная цель достигается тем,что в устройство для ранжированиячисел, содержащее (К -1)в-разрядныхрегистров сдвига, где К -число сорти-руемых чисел, (К -1)схем сравнениядвух в-разрядных чисел и блок подсчета номера ранга входного числа,причем выход 1-го в-разрядногорегистра сдвига, где 1=1,2(К -1),соединен с первым входом 1-й схемысравнения, выход 1-го п 1-разрядногорегистра сдвига, где 1=1,2(К -2),соединен с входом ( +1 ) - го п -разрядного регистра сдвига, вторые входывсех схем сравнения подключены кшине входных чисел и входы первогои-разрядного регистра сдвига, авыходы - к входам блока подсчетаномера ранга входного числа, шинасдвига устройства соединена с синхронизирующими входами всехв -разрядных регистров сдвига, содержитК и-разрядных регистров сдвига, гдеи - количество разрядов ранга, и(К -1)корректоров ранга, корректорранга содержит две схемы сравненияи и -разрядный сумматор, причемвыходы блока подсчета номера рангавходного числа подключены к входампервого н-разрядного регистра сдвига,выходы которого подключены к соответствующим входам первой группысумматора первого корректора рангаи соответствуннцим входам первыхгрупп первых схем сравнения всехкорректоров ранга, входы вторыхгрупп схем сравнения первого корректора ранга и входы первых групп6вторых схем сравнения всех корректоров ранга соединены с соответствующими выходами К -го и-разрядногорегистра сдвига, выходы 1-разрядного сумматора -го корректора рангаподключены к соответствующим входомустройства, выходы )-го ь-разрядного ъ-разрядным параллельным кодом.регистра сдвига, где к=2,3(М), Через М тактов с выходов последоваподключены к входам первой группы тельно соединенных в-разрядныхи -разрядного сумматора и входамРегистров 2 на входы схем 3 сравневторых групп схем сравнения М-го 5 ния подаются числа, поступающие накорректора ранга, в каждом корректо- входвгпоследовательных тактах,ре ранга выход первой схемы сравне- Эти числа на схемах 3 сравнения сравни( /ния соединен с входом переноса сум- ваются с входным числом, пришедшим наматора, выход второй схемы сравне- входную шину 1 в(И+1)-м такте.ния подключен к объединенным входам 0Если входное число в(И+1)-м тактеи -разрядного сумматора, синхрони- . равно или больше числа, снимаемого,зирующие входы всех и -разрядных с выхода одного иэ регистров 2, нарегистров сдвига соединены с шиной выходе соответствующей схемы 3 сравсдвига устройства, выходы п-разряд- нения образуется сигнал, равныйных регистров сдвига являются выхода логической единице. Если число нами ранжируемых чисел устройства. входной шине 1 меньше, чем числоНа.фиг, 1 показана структурная с выхода регистра 2, на выходе соотсхема устройства для ранжирования . ветствующей схемы 3 сравнения обрачисел; на Фиг. 2 - структурная зуется сигнал, равный логическомусхема корректора ранга; на фиг. 3 и 20 нулю,Сигналы с выходов схем сравнения(схему подсчета единиц ). На выходест ойство содержит входную шинусумматора образуется выраженноепо кото ой подается последователь 25 параллельным и-разрядным двоичнымсть чисел вы аженных в -разряднымкодом число Р , равное количествуаллельным кодом, т-разрядный сдви- Вх фпар пришедших на входы сумматора единиц.говый егистр 2 (общее количествоговый регистр ( щЧислой характеризует. номер рангаист ов авно Н схему 3 сравнения Вх(8+1) -го числа входной последовательдвух ю Разрядны хЗ 0 ности в данном такте, Очевидно, чтох .в - аэ я ных чисел, блок 4 подсчета номера ранга ( дт номе а анга 4(Ч -входовыйв зависимости от результата сравнения(8+1) -го входного числа с Мсдвига, задерживающий информац числами на выходах регистров 2 ЙВХодин такт(общее количество Регистррв может принимать любое значение .вравно 8+1), корректор 6 Ранга шину пределах ОИ . Выработанное в Н 7, выходы 8 ранжируемы ф, входовом сумматоре 4 значение номеранжи емых чисел 35выходы соответствующих входныхчисел, шину О довательности поступает на вход8 хцепочки из последовательно включенрангайт, выраженное и-разряднымных регистров 5 сдвига. Текущиеом вхо ные шины 40значения номера ранга Й; церемещаютсяФна кото ые поступают значевдоль цепочки регистров 5 сдвигания текущего Ранга РТ 1 Р ах точно так же, как значения входныханга Й выриботанного Й входовым су Р чисел перемещаются вдоль цепочким- о овым с мматором 4и прошедшего первый Регистр 5 сдвига регистров 2 сдвига. Каждому иэ йцепочки регистров(фиг. ) Р чисел входной последовательности,о иг, 2) и ранга 45имеющихся на выходах 8 цепочкисдвига цепочки РегистРрегистров 2, соответствует рангВМИегист ов схемы14 и 15 сравнения двух и-разрядныхэтого числа на соответствующем вычисел. Напряжение на выходе схемы ходе 9 цепочки регистров 5.сравнения равно логической единицери 0) 0 ,где Ои 0 - соответствен"но числа на входах иА 8 схемы сравне- Однако определенный для(ч +) -гочисла входной последовательностиния. Устройство также содержитанг Й не обязательно сохраняетсяь-разрядный параллельный сумматор 16 рнеизменным в течение всего времении выходную шину 17. 55Устройство работает следующим нахождения числа в окне ранжирования:за М тактов полностью изменяетобразом.На входную шину (Фиг. )каждь" ся содержимое окна ранжирования и,такт поступает число, выр ераженное следовательно, от такта к такту1109739 20 или ЯСЙ Яквх 5может изменяться ранг одного итого же числа,Для получения истинных текущихзначенийранга М входных чисеа последовательно с регистрами 5 сдвига включены корректоры 6 ранга.Их назначение - коррекция текущего значения ранга Р зависимости от рангов чисел, поступающих в окно ранжирования и уходящих из него. 0Процесс коррекции для частного случая 8=15 схематически иллюстрируется на фиг. 3 и 4. Цифры вдоль горизонтальной оси означают номераМ рангов чисел, содержащихся в регист" 15 рах 5, а также рангй поступающий на первый корректор б с первого регистра 5 сдвига, и рангй , выходящий с последнего регистра 5 сдвига.На фиг. 3 представлен случай Р )4 вь,. В этом случае присвоенный входному числу в предыдущем,такте ранг Я вбез изменения ( без коррекции )остается рангом этого числа; 25текущие ранги в пределах ЙВЫХЙ,сЯВХ понижаются на единицу." На фиг, 4 представлен случай Р С Я . В этом случае выработанный вх вьхв предыдущем такте ранг Яв и все текущие ранги в пределах Я С Я;С Йповышаются на единицу.В результате коррекции в соответствии с изложенной логикой на выходах 9 схем коррекции образуются текущие коды рангов М чисел входнои35 последовательности, имеющие значения от 1 до М, при наличии в окне ранжирования двух или более одинаковых чисел более высокий ранг присваивает 40 ся числу, поступившему позднее. Укаэанная логика реализуется в схеме корректора ранга(фиг. 2).Все г корректоров ранга, входящие в устройство, выполнены по однотипной схеме. Отличия в схеме включения первого корректора по сравнению с остальными показаны на фиг. 2. Корректор содержит две схемы сравнения и-разрядных чисел(14 и 5), вырабатывающие сигнал логической единицы50 при 1)Ч (Уи 7 - числа на входах д и В схемы сравнения)и и-разрядный параллельный сумматор 16.11 а входы А -А первого слагаемовго сумматора поступает число, подлежащее коррекции. Выход схемы 14 сравнения соединен с параллельно включенными входами В-В второго слагаемого сумматора, Выход схемы 15 сравнения соединен с входом переноса сумматора.При наличии логической единицы на выходе схемы 15 сравнения с выходов 5 - 5 сумматора снимается число, подайное на входы А-А ,но увеличенное на единицу, Прй наличии логической единицы на выходе схемы 14 сравнения значение числа, поданного на входы А 1-А 1 сумматора, увели . чивается на 1+22 =2"-1, что для и -разрядного числа эквивалентно уменьшению его значения на единицуПри наличии на выходах схем 14 и 15 сравнения одновременно нулей или единиц значение сигнала 5 -5 на выходах. сумматора совпадает с зна. чением числа, поданного на входы А-А сумматораВ первом корректоре, установленном в начале цепочки регистров 2, схема 14 сравнения всегда получает на входы Д и В одно и уо же число и вырабатывает, сигнал логического нуля. На схеме 15 сравнения производится сравнение рангов Йв. и Яв,вь(Х и вырабатывается сигнал логическои единицы при Явь ) Я в х,В этом случае ранг входного числа увеличивается на единицу. В остальных корректорах схема 14 сравнения вырабатывает сигнал логической единицы при ЯСавв схема сравнения 15 - при Я; ) РТаким образом, значение текущего ранга Й; остается неизменным привыхЯ;) Явх увеличивается на единицу при К,СК 1 вых вуменьшается на единицу при 1 вь . С1Я -"вх что соответствует принципам коррекции ранга, изложенным вышее. Технико-экономические обоснования.Произведем сравнительную оценку сложйости построения предлагаемогоустройства по сравнению с известным (базовым устройством ),,К - 18 20 36 46 56 68 74 87 98 154 166 Оценку будем производить по количеству элементов. Общее количество элементов в предлагаемом устройстве равно К=К+ Кг+ КЗ+ К К 5+ К 6+Кмэ ,где (. - колйчество е -разрядых.,сдвиговых регистров 2 К Й;К - количество схем сравненияК: ай 1К - количество 11-входовых сумма 3торов К =1);К" количество,п -разрядныхрегистров сдвига (К-количество одноразрядных регистИз таблицы следует, что целесооб. разность в применении предлагаемого устройства возникает при й8. В частности, в одном из вариантов по-строения аппаратуры возникла необходимость в разработке устройства для ранжирования 16 чисел.Использование предлагаемого построения позволило почти вдвое. уменьшить количество элементов устройства. В результате вдвое сократился объем устройства, упростился процесс настройки и проверки устройства,35 поскольку предлагаемое устройство ров сдвига К= К+1,ь=Яо (йм где Д" наименьшее целое число,не .,Х 1,К - количество схем 14 сравне 6 ния или. 15 ЯК=28);Сравнительная оценка количестваэлеменпов в схеме известного(М)ив предлагаемом устройстве (К)приведе"на в таблице.состоит из одинотипных, повторяющихся элементов,Если стоимость комплектующих изделий, использованных для изготовления известного устройства при Й =16 на .основе применения микросхем 133 серии равна 1350 руб., то стоимость комплектующих изделий в предлагаемом устройстве при использова" нии микросхем той же 133 серии равна 830 руб., т.е, имеется экономия только на комплектующих иэделиях 520 руб."бах 08 Я 9 У б 7 8,9 Ю78 О IФ О ХФиг, 3 О2 3 Ю 5 д 7 Риг.Ф Редактор А.Мотыль Заказ 6085/34Тираж 699 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 1.13035, Москва, Ж, Раушская наб., д,4/5