Устройство для ранжирования чисел Советский патент 1984 года по МПК G06F7/06 

1 Изобретение относится к вычислительной технике и может быть исполь зоваио в специализированных вычисли тельных машинах и устройствах обработки данных. Известно устройство для ранжиров ния чисел, содержащее регистр сдвиг для хранения чисел, буферный регист эталонного числа, схему сравнения устройства подсчета номера ранга, элементы И,ИЛИ, блок управления, блок синхронизации, счетчик циклов сравнения, счетчик числа величин, блок определения конца цикла сравне ния и блок индикации результата С Это устройство служит для опреде ления ранга числа, принятого за эталонный из последовательности чис за циклом. Для определения рангов всех чисел последовательности в этом устройстве потребуется N такто Наиболее близким к предлагаемому по технической сущности является устройство, которое обладает более высоким быстродействием и решает задачу определения в течение одного такта рангов всех чисел последовательности, содержащее (п-1|регистров сдвига tY -разрядных чисел,(N-I) схем сраънениЛ двух m-разрядных чисел, N блоков подсчета номера ранN -3Nt одноразрядных регистров и- - элементов НЕ, выход i-ro регистра сдвига, где i 2,3,. . ,{N-1) соединен с первым входом -и схемы сравнения, вторые входы схем сравнения соединены с шиной входных чисел и с. входом первого регистра сдвига, вход i-ro регистра сдвига соединен с выходом (i-l)-ro регистра сдвига, выход j-й схемы сравнения, где j 1,2,...,{N-I), подключен к входу первого одноразрядного регистра из цепочки последовательно соединенных (N - 1-j)oднopaзpядныx регистров, к одному из входов первого блока подсчета номера ранга и через соответствующий элемент НЕ к одному из входов (j+))-ro блока подсчета ранга, выход к-го одноразрядного регистра в j-й цепочке одноразрядных регистров, где к 1 ,2,.. . ,(N -1 - j) , подклю чен к одному из входов 1к+1)-го блока подсчета номера ранга и через соответствующий элемент НЕ к одному из входов(к+ блока подсчета номера ранга, синхронизирующие входы 9 всех регистров соединены с шиной сигналов сдвига устройства, блок подсчета номера ранга содержит сумматор c(N-l) входами, соединенными с входами блока подсчета номера ранга , а выход сумматора соединен с выходом блока подсчета номера ранга 2J. Недостатком известного устройства является усложнение устройства с ростом количества сортируемых чисел. Цель изобретения - сокращение аппаратурных затрат при больших значениях N , Поставленная цель достигается тем, что в устройство для ранжирования чисел, содержащее (N-1)т--разрядных регистров сдвига, -где N -число сортируемых чисел, (N-ljcxeM сравнения двухРп-разрядных чисел и блок подсчета номера ранга входного числа, причем выход i-ro m-разрядного регистра сдвига, где i l ,2,, . . ,(N-1), соединен с первым входом )-й схемы сравнения, выход j-го т-разрядного . регистра сдвига, где,. ,2,.. . ,(N-2), соединен с входом (j + l )-го m -разрядного регистра сдвига, вторые входы всех схем сравнения подключены к шине входных чисел и входы первого fn-разрядного регистра сдвига, а выходы - к входам блока подсчета номера ранга входного числа, шина сдвига устройства соединена .с синхронизирующими входами всех m-разрядных регистров сдвига, содержит N fi-разрядных регистров сдвига, где п - количество разрядов ранга, и (N -1)корректоров ранга, корректор ранга содержит две схемы сравнения и п-разрядный сумматор, причем выходы блока подсчета номера ранга входного числа подключены к входам первого п-разрядного регистра сдвига, выходы которого подключены к соответсгвующим входам первой группы сумматора первого корректора ранга и соответствующим входам первых групп первых схем сравнения всех корректоров ранга, входы вторых rjjynn схем сравнения первого корректора ранга и входы первых групп вторых схем сравнения всех корректоров ранга соединены с соответствующими выходами N-го п-разрядного регистра сдвига, выходы п-разрядного сумматора i-ro корректора ранга подключены к соответствующим входом (i+l)-ro п-разрядного регистра сдвига и выходам ранга i-ro числа устройства, выходы Ч-го п-разрядного регистра сдвига, где ,3,,.. ,(М-), подключены к входам первой группы п -разрядного сумматора и входам вторых групп схем сравнения корректора ранга, в каждом корректоре ранга выход первой схемы сравнения соединен с входом переноса сумматора, выход второй схемы сравнения подключен к объединенным входам h -разрядного сумматора, синхронизирующие входы всех п -разрядных регистров сдвига соединены с шиной сдвига устройства, выходы m-разрядных регистров сдвига являются выхода ми ранжируемых чисел устройства. На.фиг, 1 показана структурная схема устройства для ранжирования чисел; на фиг. 2 - структурная схема корректора ранга; на фиг. 3 и 4- процесс коррекции для случая . Устройство содержит входную шину 1, по которой подается последователь ность чисел, выраженных m-разрядным параллельным кодом, m-разрядный сдви говый регистр 2 (общее количество . регистров равно N), схему 3 сравнения двух .т-разрядных чисел, блок 4 подсчета номера ранга 4{ -входовый сумматор ), н-разрядный регистр 5 сдвига, задерживающий информацию на один такт(общее количество регистров равно N+1), корректор 6 ранга, шину 7, выходы 8 ранжируемых чисел, выходы 9 соответствующих входных чисел, шину 10, по которой на коррек тор поступает значение текущего рангаR, выраженное h-разрядным параллельным кодом, входные шины 11 - 13, на которые поступают значе ния текущего ранга R, ранга R, вы работанного sl-sxoдoвым сумматором 4 и проЩедшего первый регистр 5 сдвиг цепочки регистров(фиг. 2), и ранга Rg выходящего с последнего регистра 5сдвига цепочки регистров, схемы 14 и 15 сравнения двух п-разрядных чисел. Напряжение на выходе схемы сравнения равно логической единице ЫйиЦ ир.где УдИ Us - соответствен но числа на входах Л и В схемы сравне ния. Устройство также содержит П-разрядный параллельный сумматор 1 и выходную шину 17. Устройство работает следующим образом. На входную шину 1(фиг. 2)каждый такт поступает число, выраженное т-разрядным параллельным кодом. Через N тактов с выходов последовательно соединенных m-разрядных регистров 2 на входы схем 3 сравнения подаются числа, поступающие на вход 1 в N последовательных тактах. Эти числа на схемах 3 сравнения сравниваются с входным числом,пришедшим на входну1р шину 1 B(N + I)-M такте. Если входноечисло B(N+n-M такте равно или больше числа, снимаемого, с выхода одного из регистров 2, на выходе соответствующей схемы 3 сравнения образуется сигнал, равный логической единице. Если число на входной шине 1 меньше, чем число с выхода регистра 2, на выходе соответствующей схемы 3 сравнения образуется сигнал, равный логическому нулю. Сигналы с выходов схем сравнения поступают на N-входовый сумматор 4 (схему подсчета единицJ. На выходе сумматора образуется выраженное параллельным п-разрядным двоичным кодом число Pgj , равное количеству пришедших на входы сумматора единиц. ЧислоRgjj характеризует .номер ранга (N+1) -го числа входной последовательности в данном такте. Очевидно, что в зависимости от результата сравнения (N+1) -го входного числа с N числами на выходах регистров 2 Rgy может принимать любое значение в пределах O...N. Выработанное в Nвходовом сумматоре 4 значение номера paHraRgj(N+l)-го числа входной последовательности поступает на вход цепочки из последовательно включенных регистров 5 сдвига. Текущие значения номера ранга R церемещаются вдоль цепочки регистров 5 сдвига точно так же, как значения входных чисел перемещаются вдоль цепочки регистров 2 сдвига. Каждому из N чисел входной последовательности, имеющихся на выходах 8 цепочки регистров 2, соответствует ранг этого числа на соответствующем выходе 9 цепочки регистров 5. Однако определенный для(N +1)-го числа входной последовательности ранг Rg не обязательно сохраняется неизменным в течение всего времени нахождения числа в окне ранжирования: за N тактов полностью изменяется содержимое окна ранжирования и, следовательно от такта к такту может изменяться ранг одного и того же числа. Для получения истинных текущих значений paijra N входных чисел последовательно с регистрами 5 сдвиг.а включены корректоры 6 ранга.Их назначение - коррекция текущего значения ранга R зависимости от рангов чисел, поступающих в окно ранжирования и уходящих из него. Процесс коррекции для частного случая схематически иллюстрируется ца фиг. 3 и 4. ЦИФРЫ вдоль горизонтальной оси означают номера рангов чисел, содержащихся в регистрах 5, а та1сже рангК, поступающий на первый корректор 6 с первого регистра 5 сдвига, и рангВ, выходящийс последнего,регистра 5 сдвига. На фиг. 3 представлен случай бх вых В этом случае присвоенный входному числу в предьщущем,такте ранг R ц без изменения (без коррекции )остается рангом этого числа; пределах R g Ь1х i 6x текущие ранги в понижаются на единицу. На фиг. 4 представлен случай R R .В этом случае выработанный в предыдущем такте ранг и все текущие ранги в пределах Rgx R повышаются на единицу. В результате коррекции в соответствии с изложенной логикой на выходах 9 схем коррекции образуются текущие коды рангов N чисел входной последовательности, имеющие значения от 1 до N, при наличии в окне ранжирования двух или более одинаковых чисел более высокий ранг присваивает ся числу, поступивщему позднее. Указанная логика реализуется в схеме корректора ранга(фиг. 2 Все N корректоров ранга, входящие в устройство, выполнены по однотипной схеме. Отличия в схеме включения первого корректора по сравнению с ос;тальными показаны на фиг. 2. Корректор содержит две схемы сравнения h-разрядных чисел (14 и 15), вырабаты вающие сигнал логической единицы (V и Vg - числа на входах / и В схемы cpaвнeния и -разрядный параллельный сумматор 16. На входы А -А| первого слагаемого сумматора поступает число, подле жащее коррекции. Выход схемы 14 сравнения соединен с параллельно включенными входами второго слагаемого сумматора, Выход схемы I5 сравнения соединен с входом переноса сумматора. При наличии логической единицы на Выходе схемы I5 сравнения с выходов сумматора снимается число, поданное на входы ,но увеличенное на единицу. При наличии логической единицы на выходе схемы 14 сравнения значение числа, поданного на входы сумматора, увели-, чивается на 1+2+.. . , что для .h -разрядного числа эквивалентно уменьщению его значения на единицу. При наличии на выходах схем 14 и 15 сравнения одновременно нулей или единиц значение сигнала .5 -5 на выходах .JiyMMaTOpa совпадает с значением числа, поданного на входы А. -А„ сумматора. В первом корректоре, установленном в начале цепочки регистров 2, .схема 14 сравнения всегда получает на входы /4 и В одно и уо же число и вырабатывает.сигнал логического нуля. На схеме I5 сравнения производится сравнение рангов Rg и Rg и вырабатывается сигнал логической единицы при КР,.В этом спучае ранг входного числа увеличивается на единицу. В остальных корректорах схема 14 сравнения вырабатывает сигнал логической единицы при .,j, схема сравнения 15 - при ,- Rg, Таким образом, значение текущего ранга Rf остается неизменным при «BXJ b- Raxj величивается на единицу при .вш уменьшается на единицу при .л1 («. г что соответствует принципам коррекции ранга, изложенным выше. Технико-экономические обоснования, Произведем сравнительную оценку сложности построения предлагаемого устройства по сравнению с известным (базовым устройством J. Оценку будем производить по количеству элементов. Общее количество элементов в предлагаемом устройстве равно ,+ К, ,, : , где ((. - количество rvi -разрядых .сдвиговых регистров 2() Ку- количество скем сравнения ,) , К - количество N-входовых сумматоров (. Кл количество ,п-разрядных регистр.ов сдвига (К -количество одноразрядных регистN 2 3 4 5 6 7 8 9 М 5 11 19 29 41 :i55 71 89. ,К 18 20 36 46 56 68 74 87

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

Использование предлагаемого постро ения позволило почти вдвое.уменьшить количество элементов устройства. В результате вдвое сократился объем устройства, упростился процесс настройки и проверки устройства, поскольку предлагаемое устройству 1109739 5 О зл :в н

I

состоит из одинотипных, повторяющихся элементов.

Если стоимость комплектующих изделий, использованных для изготовления известного устройства при 14 16 на основе применения микросхем 133 серии равна 1350 руб., то стоимость комштектукмцих изделий в предлагаемом устройстве при использовании микросхем той же 133 серии 830 руб., т.е. имеется экономия только на комплектующих изделиях 520 руб. .8 ров сдвига Kj N + 1 ,(N+-t| где 3 X U наименьшее целое число, не количество схвм 14 сравнения(илиЛ5)); К/- количество п-разрядньк Параллельных сумматоров : равнительная оценка количества енп-ов в схеме известного{М)и едлагаемом устройстве (К)приведев таблице. , 10 15 16 109 239 271 98 154 166

УСТРОЙСТВО ДЛЯ РАНЖИРОВАНИЯ ЧИСЕЛ, содержащее (,М-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-разрядных регистров сдвига являются выходами ранжируемых чисел устройства.

пад

ff

L/ AL

1Б

«

1сУ-.

Г

8мд I

В}(одЗ

ВмдЧ

г

г

Т7

Выход

15Фиг.2 О г 3 f $ 6 7 В 9 |К5д О 1 2 3 Ч 5678 9 Фиг.З Фмг. 1Q П 1Z 13 1 15 К t W П 11 а IV JS