Устройство для ранжирования чисел
УСТРОЙСТВО ДЛЯ РАНЖИРОВАНИЯ ЧИСЕЛ, содержащее (,М-1|гг -разрядных регистров сдвига, где N - число сортируемых чисел,(N-nсхем сравнения двух тп разрядных чисел и блок подсчета номера ранга входного числа, причем выход i-ro т-разрядного регистра сдвига, где ,2(N-1), соединен с первым входом i-й схемы сравнения,выход j-ro m-разрядного .регистра сдвига .где j 1,2,... Дм -2), соединен с входом j+l)-го т-разрядного регистра сдвига, вторые входы всех схем сравнения подключены к шине входных чисел и входу первого m -разрядного регистра сдвига, a выходы - к входам блока подсчета номера ранга входного числа, шина сдвига устройства соединена с синхронизирующими входами всех m -разрядных регистров сдвига, отличающееся тем, что, с целью сокращения аппаратурных затрат при больших значениях N , устройство содержит | -разрядных регистров сдвига, где .г - количество разрядов ранга, и IN - lJ KOppeKTopoB ранга, корректор содержит две схемы сравнения и Ъ -разрядный сумматор, причём выходы блока подсчета номера ранга входного числа подключены к входам первого п-разрядного регистра сдвига, выходы которого подключены к соответствующим входам первой группы сумматора первого корректора ранга и соответствующим входам первых групп первых схем сравнения всех корректоров ранга, входы вторых групп схем сравнения первого корректора ранга и входы первых групп вторых схем сравнения всех корректо9 ров ранга соединены с соответствующими выходами N-ro п-разрядного регистра сдвига, выходы h-разрядного сумматора i-ro корректора ранга подг. ключены к соответствующим входам (+1)-го Г -разрядного регистра сдвига и выходам ранга i-ro числа устройства , выходы h-разрядного регистра сдвига, где ,3,. .. ,(м-1), подключены к входам первой группы ;о П-разрядного сумматора и входам вторых групп схем сравнения It-го 00 корректора ранга, в каждом корректоре ранга выход первой схемы сравнения соединен q входом переноса сум- i матора, выход второй схемы сравнения подключен к объединенным входам ,п-разрядного сумма-рора, синхронизирующие входы всех п-разрядных регистров сдвига соединены с шиной «сдвига устройства , выходы rft-разрядных регистров сдвига являются выходами ранжируемых чисел устройства.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК SU„„11097
g(g) С 06 F 7/06
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
AO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОЧНРЫТИЙ
Н ABTOPCklDhllV СВИДВТВЛЬСТВУ (21) 3575827/18-24 (22) 08.04 ° 83 .(46) 23.08. 84 ° Бюл. У 31 (72) Ю.Н.Ложкин, A.À.Ìàìàåâ и P.Ä.ßõoíòîâ (53) 681.325.66(088.8) (56) I. .Патент США У 3829664, кл. G 06 F 7/02, опублик. 1974.
2. Авторское свидетельство СССР по заявке 11- 3477634, кл. С 06 F 7/06, 1982(прототип). (54)(57) УСТРОЙСТВО ДЛЯ PAHiKHPOBAHHH
ЧИСЕЛ, содержащее (N-I)m-разрядных регистров сдвига, где М вЂ” число сортируемых чисел,(N-11схем сравнения двух tn-разрядных чисел и блок подсчета номера ранга входного числа, причем выход i-ro rn-разрядного регистра сдвига, где i=1,2,...,(N-I), соединен с первым входом i-й схемы сравнения, выход j-го m -разрядного регистра сдвига, где j = I, 2,...,(N -2), соединен с BxopoM(j+I)-rom-разрядно- го регистра сдвига, вторые входы всех схем сравнения подключены к шине. входных чисел и входу первого
m --разрядного регистра сдвига, а выходы — к входам блока подсчета номера ранга входного числа, шина сдвига устройства соединена с синхронизирующими входами всех rn -разрядных регистров сдвига, о т л и ч аю щ е е с я тем, что, с целью сокращения аппаратурных затрат при больших значениях N, устройство содержит М и -разрядных регистров сдвига, где .и — количество разрядов ранга, и (й — 11корректоров ранга, корректор ранга .содержит две схемы сравнения и h --разрядный сумматор, причем выходы блока подсчета номера ранга входного числа подключены к входам первого п -разрядного регистра сдвига, выходы которого подключены к соответствующим входам первой группы сумматора первого корректора ранга и соответствующим, входам первых групп первых схем сравнения всех корректоров ранга, входы вторых групп схем сравнения первого корректора ранга и входы первых групп вторых схем сравнения всех корректо" ров ранга соединены с соответствующими выходами N-ro n -разрядного регистра сдвига, выходы и-разрядного сумматора i-ro корректора ранга под"... ключены к соответствующим входам (i +I)-го и -разрядного регистра сдвиO га и выходам ранга i-го числа устройства, выходы .М-го и -разрядного регистра сдвига, где к=2,3,... (N-l), подключены к входам первой группы и-разрядного сумматора и входам вторых групп схем сравнения %-ro корректора ранга, в каждом корректоре ранга выход первой схемы сравнения соединен с входом переноса сумматора, выход второй схемы сравнения подключен к объединенным входам ,р-разрядного сумматора, синхронизирующие входы всех и-разрядных регистров сдвига соединены с шиной сдвига устройства, выходы rh-.ðàýðÿäíûõ регистров сдвига являются выходами ранжируемых чисел устройства.
1109739
Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных. 5
Известно устройство для ранжирования чисел, содержащее регистр сдвига для хранения чисел, буферный регистр эталонного числа, схему сравнения устройства подсчета номера ранга, 10 элементы И,KIN, блок управления, блок синхронизации, счетчик циклов сравнения, счетчик числа величин, блок определения конца цикла сравнения и блок индикации результата Г13.
Это устройство служит для определения ранга числа, принятого за эталонный из последовательности чисел за циклом. Для определения рангов всех чисел последовательности в 20 этом устройстве потребуется 1Ч тактов.
Наиболее близким к предлагаемому по технической сущности является устройство, которое обладает более высоким быстродействием и решает задачу определения в течение одного . такта рангов всех чисел последовательности, содержащее (I1-1}регистров сдвига tn -разрядных чисел,(N-1) схем сравнения двух rn -разрядных 30 чисел, К блоков подсчета номера ранМ -3М+г га, одноразрядных регистров
К(К-1) и
2 элементов НЕ выход 1-горегистра сдвига, где i =2,3,...,(N -1), соединен с первым входом i-й схемы сравнения, вторые входы схем сравнения соединены с шиной входных чисел и с входом первого регистра сдвига, 40 вход 1-го регистра сдвига соединен с выходом (i — I)-ro регистра сдвига, выход j-й схемы сравнения, где
=1,2,...,(К -1), подключен к входу первого одноразрядного регистра из цепочки последовательно соединенных (К вЂ” 1 -1)одноразрядных регистров, к одному из входов первого блока подсчета номера ранга и через соответствующий элемент НЕ к одному из вхо-, 50 дов () +1)-ro блока подсчета ранга, выход к-го одноразрядного регистра в j --й цепочке одноразрядных регистров, где к= l, 2,...,(Й -1 — j), подключен к одному из входов (к+1) -ro блока подсчета номера ранга и через
55 соответствующий элемент НЕ к одному из входов(к+ +1)-го блока подсчета номера ранга, синхронизирующие входы всех регистров соединены с шиной сигналов сдвига устройства, блок подсчета номера ранга содержит сумматор с(К вЂ )входами, соединенными с входами блока подсчета номера ранга, а выход сумматора соединен с выходом блока подсчета номера ранга(2).
Недостатком известного устройства является усложнение устройства с ростом количества сортируемых чисел.
Цель изобретения — сокращение аппаратурных затрат при больших значениях К.
Поставленная цель достигается тем, что в устройство для ранжирования чисел, содержащее (N -1)в-разрядных регистров сдвига, где К -число сорти- руемых чисел, (N -1)схем сравнения двух п-разрядных чисел и блок подсчета номера ранга входного числа, причем выход i-ro в-разрядного регистра сдвига, где i=I,2,...,(К вЂ” 1), соединен с первым входом 1-й схемы сравнения, выход j-ro п1-разрядного регистра сдвига, где,, 1=1,2,...,(К -2), соединен с входом (j +I ) — ro rn -разрядного регистра сдвига, вторые входы всех схем сравнения подключены к шине входных чисел и входы первого
1п-разрядного регистра сдвига, а выходы — к входам блока подсчета номера ранга входного числа, шина сдвига устройства соединена с синхронизирующими входами всех п -разрядных регистров сдвига, содержит
К и-разрядных регистров сдвига, где и — количество разрядов ранга, и (К -1)корректоров ранга, корректор ранга содержит две схемы сравнения и и --разрядный сумматор, причем выходы блока подсчета номера ранга входного числа подключены к входам первого и-разрядного регистра сдвига, выходы которого подключены к соответствующим входам первой группы сумматора первого корректора ранга и соответствуннцим входам первых групп первых схем сравнения всех корректоров ранга, входы вторых групп схем сравнения первого корректора ранга и входы первых групп
6 вторых схем сравнения всех корректоров ранга соединены с соответствующими выходами К -ro n-разрядного регистра сдвига, выходы и -разрядного сумматора i-го корректора ранга подключены к соответствующим входом (i +1)-ro n-разрядного регистра сдвига и выходам ранга i-го числа!!09739 устройства, выходы ) -го h -разрядного ъ-разрядным параллельным кодом. регистра сдвига, где к=2,3,...,(М-1), Через М тактов с выходов последоваподключены к входам первой группы тельно соединенных м-разрядных и -разрядного сумматора и входам Регистров 2 на входы схем 3 сравневторых групп схем сравнения М-го 5 ния подаются числа, поступающие на корректора ранга, в каждом корректо- «вход 1 в(4 последовательных тактах. ре ранга выход первой схемы сравне- Эти числа на схемах 3 сравнения сравни(1 ния соединен с входом переноса сум- ваются с входным числом, пришедшим на матора, выход второй схемы сравне- входную шину 1 в(И+1)-м такте. ння подключен к объединенным входам !0 Если входное число a(N+1)-м такте и -разрядного сумматора, синхрони- . равно или больше числа, снимаемого. зирующие входы всех и -разрядных с выхода одного иэ регистров 2, на регистров сдвига соединены с шиной выходе соответствующей схемы 3 сравсдвига устройства, выходы m разряд- нения образуется сигнал, равный ных регистров сдвига являются выхода- !5 логической единице. Если число на ми ранжируемых чисел устройства. входной шине l меньше, чем число
На фиг, 1 показана структурная с выхода РегистРа 2, на выходе соотсхема устройства для ранжирования ветствующей схемы 3 сравнения обрачисел; на фиг. 2 — структурная эуется сигнал, равный логическому схема корректора ранга; на фиг. 3 и 20 нулю.
Сигналы с выходов схем сравнения .поступают на N -входовый сумматор 4
1ч Юг ° (схему подсчета единиц ). На выходе ст ойство содержит входную шину сумматора образуется выраженное по кото ой подается последователь25 параллельным -разрядным двоичным сть чисел вы аженных rn -разрядным кодом число R, равное количеству аллельным кодом, m-разрядный сдви- 8r пришедших на входы сумматора единиц. говый егистр 2 (общее количество говый регистр (щ
Числой характеризует. номер ранга ист ов авно Н схему 3 сравнения sx (Й+!) -ro числа входной последовательЗ0 ности в данном такте. Очевидно, что х .т — аэ я ных чисел, блок 4 подсчета номера ранга (д т номе а анга 4(Ч -входовый в зависимости от результата срав нения(Я+1) -го входного числа с М числами на выходах регистров 2 К8х может принимать любое значение .в
1) ° корр к Р Р пределах О...И . Выработанное в Нвходовом сумматоре 4 значение номера нжи емых чисел 35 выходы соответствующих входных „ ( довательности поступает на вход
8х цепочки из последовательно включенрангаЯ, выраженное п-разрядным ных регистров 5 сдвига. Текущие ом вхо ные шины 40 значения номера ранга R; перемещаются
4 на кото ые поступают значе- . вдоль цепочки регистров 5 сдвига текУЩего 1 < > т - 8х точно так же, как значения входных анга R вычисел перемещаются вдоль ц почки й- о овым с мматором 4 и прошедшего первый регистр 5 сдвига чисел входной последовательности о иг. 2) и ранга 45 имеющихся на выходах 8 цепочки
5 сдвиг цепочк Регистр
Ьмх р егист ов схемы
14 и 15 сравнения двух и-разрядных этого числа на соответствующем вычисел. Напряже и На выходе ходе 9 цепочки регистров сравнения равно логической единице ри U> > 08, rye О и 08 - соответствен» но числа на входах и
А 9 схемы сравне- Однако определенный для(!ч +!) -ro числа входной последовательности ния. Устройство также содержит анг R не обязательно сохраняется
h-разрядный параллельный сумматор 16 р неизменным в течение всего времени и выходную шину 17. 55
У "ство работает следующим нахождения числа в окне ранжирования:за N тактов полностью изменяетобразом.
На входную шину (фиг. )каждь" ся содержимое окна ранжирования и, такт поступает число, выр е раженное следовательно, от такта к такту
1109739
20 или ;<Р
Й (R вх
5 может изменяться ранг одного и того же числа.
Для получения истинных текуших значений ранга 8 входных чисеа последовательно с регистрами 5 сдвига включены корректоры 6 ранга.их назначение — коррекция текущего значения ранга R зависимости от рангов чисел, поступающих в окно ранжирования и уходящих из него. !О
Процесс коррекции для частного случая N=15 схематически иллюстрируется на фиг . 3 и 4. Цифры вдоль горизонтальной оси означают номера
I рангов чисел, содержащихся в регистрах 5, а также ранг@ поступающий на первый корректор 6 с первого регистра 5 сдвига, и рангй, выходящий с последнего регистра 5 сдвига.
На фиг. 3 представлен случай
Р „ ) Rв,„ . В этом случае присвоенный входному числу в предыдущем,такте ранг R в„без изменения (без коррекции )остается рангом этого числа; 25 текущие ранги в пределах RS uX С !С, С 1 ВХ
1 понижаются на единицу.
" На фиг. 4 представлен случай
R < R . В этом случае выработанный вх вь х предыдущем ТВКТе ранг текущие ранги в пределах К „с Р (R» повышаются на единицу.
В результате коррекции в соответствии с изложенной логикой на выходах 9 схем коррекции образуются текущие коды рангов !ч чисел входнои
35 последовательности, имеющие значения от 1 до М, при наличии в окне ранжирования двух или более одинаковых чисел более высокий ранг присваивает40 ся числу, поступившему позднее.
Укаэанная логика реализуется в схеме корректора ранга(фиг. 2)
Все Я корректоров ранга, входящие в устройство, выполнены по однотипной схеме. Отличия в схеме включения первого корректора по сравнению с остальными показаны на фиг. 2. Корректор содержит две схемы сравнения и-разрядных чисел(14 и 15), вырабатывающие сигнал логической единицы
50 при, )V (V H V — числа на входах д и В схемы сравнения)и и-разрядный параллельный сумматор !6.
На входы А -А первого слагаемои го сумматора поступает число, подлежащее коррекции. Выход схемы 14 сравнения соединен с параллельно включенными входами В>-В„ второго слагаемого сумматора, Выход схемы 15 сравнения соединен с входом переноса сумматора.
При наличии логической единицы на выходе схемы 15 сравнения с выходов S — - 5„ сумматора снимается число, подайное на входы A„-А,но увеличенное на единицу, Прй наличии логической единицы на выходе схемы
14 сравнения значение числа, поданного на входы А -А> сумматора, увели чивается на 1+2+...+2 =2"-l что для и -разрядного числа эквивалентно уменьшению его значения на единицу»
При наличии на выходах схем 14 и 15 сравнения одновременно нулей или единиц значение сигнала 5 --5
1 на выходах. сумматора совпадает с значением числа, поданного на входы
А„-А„ сумматора °
В первом корректоре, установленном в начале цепочки регистров 2, схема 14 сравнения всегда получает на входы Д и В одно и уо же число и вырабатывает. сигнал логического нуля. На схеме 15 сравнения производится сравнение рангов Râõ. и Râü вьу и вырабатывается сигнал логическои единицы GPH Рвь,х)Рв„.В этом слУчае ранг входного числа увеличивается на единицу. В остальных корректорах схема 14 сравнения вырабатывает сигнал логической единицы при RÄ- Я1) кв вх увеличивается на единицу при R. < Я 1 ВЫХ Rвx уменьшается на единицу при i) вь . с (Я Рвх что соответствует принципам коррекции ранга, изложенным вышее. Технико-экономические обоснования. Произведем сравнительную оценку сложйости построения предлагаемого устройства по сравнению с известным (базовым устройством ). 1109739 Н 2 3 4 5 6 7 8 9 F 10 15 16 - M 5 11 19 29 41 з55 71 : 89. 109 239 271,K - -18 20 36 46 56 68 74 87 98 154 166 Оценку будем производить по количеству элементов. Общее количество элементов в предлагаемом устройстве равно K=K + K + K,,+ K++ K5+ К +К ,где (. — колйчество m -разрядых ..сдвиговых регистров 2(К ф) ; К вЂ” количество схем сравнения (К: N ) К вЂ” количество Я -входовых сумма3 торов (К: -1) К " количество,h -разрядных регистров сдвига (К -количество одноразрядных регистИз таблицы следует, что целесооб. разность в применении предлагаемого устройства возникает при N 8. В частности, в одном из вариантов по- строения аппаратуры возникла необходимость в разработке устройства для ранжирования 16 чисел. Использование предлагаемого постро-30 ения позволило почти вдвое. уменьшить количество элементов устройства. В результате вдвое сократился объем устройства, упростился процесс настройки и проверки устройства, 35 поскольку предлагаемое устройство ров сдвига К = К+1,б=Яо - (g+ej(где 3 7 i " наименьшее целое число, не Х> K:— — количество схем 14 сравне5 ния (или. 15)(К =2@);. К вЂ” количество и -разрядных 4 параллельных сумматоров (КЬ= 1) Сравнительная оценка количества элеманпов в схеме известного(М)и в предлагаемом устройстве (К)приведе" на в таблице.! состоит из одинотипных, повторяющихся элементов. ! Если стоимость комплектующих изделий, использованных для изготовления известного устройства при Й =16 на основе применения микросхем 133 серии равна 1350 руб., то стоимость комплектующих изделий в предлагаемом устройстве при использовании микросхем той же 133 серии равна 830 руб., т.е. имеется экономия только на комплектующих иэделиях 520 руб. 1109739 1109739 <беп 0 f g 9 Ю 5 д 7 Составитель Е.Иванова Техред M.Pàäü . Корректор Л.Пилипенко Редактор А.Мотыль Заказ 6085/34 Тираж 699 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 13035, Москва, Ж-35, Раушская наб., д.4/5 Филиал ППП "Патент", г. Ужгород, ул. Проектная,4 1 8 3 4 f б 7 8 9 Ю И 12 13 /Ф 15 Х Фиг. 3
