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

 

li УСТРОЙСТВО ДЛЯ РАНЖИРОВАНИЯ ЧИСЕЛ, содержащее регистр сдвига , схему сравнения, блок подсчета номера ранга, причем выход регистра сдвига соединен с первым входом схемы сравнения, отличающеес я тем, что, с целью повышения быстродействия устройства, регистр сдвига выполнен пг-разрядным, ще m - количество разрядов сортируемых чисел, в устройство введешь (N-2) регистров сдвига, где N - число сортируемых чисел, (N-2) схем сравнения , (N-lL блоков подсчета ранга, одноразрядных регистров и элементов НЕ, причем выход 1-го регистра, где i « « 2,3,. ., (N-1), соединен, с первым входом i-й схемы сравнения, вторые входы схем сравнения соединены с пкной входных чисел и с входом первого регистра сдвига, вход f-ro регистра сдвига соединен с выходом (J-l)-ro регистра сдвига, выход j-й схемы сравнения, где j - I, 2,...,(N-1), подключен к входу первого одноразрадного регистра из цепочки последовательно соединенных (N-1-J) одноразрядных регистров, к одному из входов первого блока подсчета номера ранга и через соответствующий злемент НЕ к одному из входов (j+l)-ro блока подсчета номера ранга, выход k-ro одноразрядного регистра J-й цепочке одноразрядных регистров, где ,2,,,,, (N-1-j), подключен к (Л одному из входов (k+l)-ro блока подсчета номера ранга и через соот-вет- . ствукщий злемент НЕ к одному из входов (k+j+l)-ro блока подсчета номера ранга, (шихронизирукицие входы всех регистров соединены с шиной сигналов сдвига устройства. 2. Устройство по п. 1, о т л и .чающеесятем, что блок подел ел :счета номера ранга содержит сумматор 1с (N-I) входами, соединенными с вхо|дани блока подсчета номера ранга, Ш11ХОД сумматора соединен с выходом бпока подсчета номера ранга.

, СОЮЭ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

PECllVEi JEHH (19) П1) <51) 6 Об 1= 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ"

H ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3477634/ E 8-24 (22) 30.07,82 ,(46) 30.!0.83. Бюл. В 40

"(72)А.А. Иамаев, Ю.Н. Ложкин и Р,Д. Яхонтов .(53) 681.325(088.8) (56) l. Авторское свидетельство СССР

534762» кл. С 06 7/06» 1975 °

2. Патент СИА ЕЕ» 3829664, кл. 06 Р 7/02, 1974 (прототип) . (54).(57) 1» УСТРОЙСТВО ДЛЯ РАНЖИРОВАНИЯ ЧИСЕЛ, содержащее регистр сдвига, схему сравнения, блок подсчета номера ранга, причем выход регистра сдвига соединен с первым входом схемы сравнения, о т л и ч а ю щ е ес я тем, .что, с целью повышения быстродействия устройства, регистр сдвига выполнен m-разрядным, где щ - 1соличество разрядов сортируемых чисел, в устройство введены («"2) регистров сдвига, где « - число сортируемых чисел, («"2) схем сравнения, («"l) блоков подсчета номера

М - "»М-2 ранга, — -=ъ — — -- одноразрядных

N(N- ) регистров и — элементов HE причем выход 1""го -регистра, где 1

2,3,...,(«-1), соединен с первым входом i-й схемы сравнения, вторые входы схем сравнения соединены с виной входных чисел и с входом перво. го регистра сдвига, вход i-го регист ра сдвига соединен с выходом (i-1)-го регистра сдвига, выход j-й схемы сравнения, где -J i 2, ° . °,(«-1), подключен к :входу первого одноразрядного регистра иэ цепочки последовательно соединенных («-1"3) одноразрядных регистров, к одному иэ входов первого блока подсчета номера ранга и через соответствующий элемент HE K одному иэ входов (J+i) го блока подсчета номера ранга, выход

k"ãî одноразрядного регистра в J-й цепочке одноразрядных регистров, где ° Е

С2

k 1, 2,..., («-1-3), подключен к одному из входов (k+1)-ro блока подсчета номера ранга и через соответствующий элемент НЕ к одному иэ sxo- дов (k+3+1) "го блока подсчета нома- а ра ранга, синхронизирующие входы всех регистров соединены с пиной сигналов сдвига устройства.

2 .. устройство по п. 1, î т л ич а ю щ е е с я тем, что блок под:счета номера ранга содержит сумматор

1с (М-1) входами, соединенньаж с входами блока подсчета номера ранга, выход сумматора соединен с выходом блока подсчета номера ранга.

1051532

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах абра= ботки данных. 5

Известно устройство для пойска экстремальных значений, решающее задачу определения ранга числа, содержащее регистры, группу элементов

И, генератор, триггеры, счетчик, де- 10 шифратор, группу элементов НЕ,, блок регистрации экстремального значения, блок регистрации ранжированного ряда параметров, блоки определения ранга параметра, разрядные коммутаторы (1), 5

Недостатком известного устройства являются большие. аппаратные затраты.

Наиболее близким к предлагаемому па технической сущности является устройство для ранжирования чисел, щ содержащее регистр сдвига для хранения чисел буферный регистр для хранения эталонного числа иэ заданной последовательности чисел, схему сравнения устройства подсчета номера ран- 25 га, элементы И, ИЛИ, блок управления, блок синхронизации, счетчик -циклов сравнения, счетчик числа величин, блок определения конца цикла сравнения и блок индикации результата, при- 30 чем шина ввода данных соединена с первым входом первого элемента ИЛИ, выход которого соединен с входом регистра сдвига, выход которого соединен с первым входом схемы сравнения, 35 с вторым входом первой схемы ИЛИ и с первым входом первого элемента И, выход которой подключен к первому входу второго элемента ИЛИ, соединенной выходом с входом -буферного ре" гистра, выход которого подключен к первым входам схемы сравнения н второго элемента ИЛИ, первый выход схе- мы сравнения подключен к первому входу вторсго элемента И, выход .которого соединен с входом устройства

45 подсчета номера ранга и с первым входам третьего элемента ИЛИ, выход которого подключен к устройству подсчета номера коллективно""î ранга, первый выход блока управления соединен с управляющим входом регистра сдвига и первыми входами третьего и четвертого элементов И, вторые входы которых подключены соответственно к первому и второму выходам блока синхронизации, выход третьего элемен.та И подключен к второму входу первого элемента И и управляющим входам устройств подсчета номера ранга, выход четвертora элемента И соединен с вторыми входаьж второго и пятого элементов И, второй вход которого

c:oeäèHeH с вторым выходом схемы сравненияД а выход — с вторым входом третьего элемента ИЛИ, второй выход блока управления падключеH к первым входам шестого, седьмого, восьмого и девятого элементов И, вторые входы которых соединен ч соатветственно с выходами буферного регистра„. счетчика числа циклов сравне мя и устройств подсчета номера ранга, а выходы — с входами блока индикации, третий выход блока управления соединен с управ яюшим входом счетчика циклов сравнения, четвертый выход блока управления подключен к входу блока синхронизации, первый вход блока управления соединен с шиной начала работы и счет. ь11 входом счетчика циклов сравнения, информационный выход которого соединен с первым входом блока определения конца цикла сравнения, второй. вход которого подключен к информационному выходу счетчика числа величин, вход которого соединен с шиной заггиси номера числа, выход блока определения конца цикла соединен с вторым входом блока управления t2j устройство служит для определения ранг-.: числа, принятого за эталонньй иэ последовательности ", --.-.-.сел эа Н циклов. Для определения рангов всех чисел последовательности потребуется И . тактов.

Цепь изобретения — повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройстве для paíÿèpîçàHHÿ чисел, содержащее регистр сдвига„. схему. сравнения, блок. подсчета номера ранга, причем выход регистра сдвига соединен с первым входом схемы сравнения, регистр сдвига выполнен ш-.-разрядным, где m - количество разрядов сортируемых чисел, в устройство введены (11 "2) регистров сдви""a, где N - число сортируемых исел:, (Й-2) схем сравнения, (N" 1) блоков я <3N<2 подсчета номера ранга.

- Ч(й -s1 одноразрядных регистров и †- --элементов НЕ, причем выход i".ão ре гистра, где i 2, 3,..., (Й"1), соединен с первым входам 1-й схемы

С сравнения, вторые входы схем сравнения соединены с шиной входных чисел

1051532 4 и с входом первого регистра сдвига, вход i -ro регистра сдвига соединен с выходом (i-1)-ro регистра сдвига, выход j-й схемы сравнения, где j 1, 2,..., (М- 1), подключен к входу первого одноразрядного регистра из цепочки последовательно соединен" ных (М- 1-j) одноразрядных регистров, к одному из входов первого блока подсчета номера ранга и через соответ- !О ствующий элемент,НЕ к одному иэ входов (j+I)-го блока подсчета номера ранга, выход k-ro одноразрядного регистра в J-й цеопчке одноразрядных РегистРов, где k = 1, 2..., (М- 1-j) подключен к одному из входон (k+1)-ro блока подсчета номера ранга и через соответствующий элемент НЕ к одному из входов (k+j+1)"го бла <а подсчета номера ранга, синхронизирующие входы всех регистров сое-. динены с шиной сигналов сдвига устройства.

Кроме того, блок подсчета номера ранга содержит сумматор с (М-1) вхо- 2 дами, соединенными с нходами блока подсчета номера ранга, выход суммато ра соединен с выходом блока подсчета номера ранга.

На чертеже представлена структур

В ная схема устройства для N g.

Устройство для ранжирования чисел содержит входную шину 1 устройства, по которой подается. последовательность чисел, выраженных ш-разрядным параллельным кодом, m-разрядный вход- З ной регистр 2, схему 3 сравнения днух m-разрядных чисел, одноразрядный.регистр 4, элемент НЕ 5, блок 6 подсчета номера ранга шину 7 сигнаФ

40 лон сдвига.

Устройство работает следующим образом.

На входную шину 1 при каждом такте -поступает число, выраженное m-раз-. рядным параллельным кодом. Через

45 (М-1) тактов с выходов последовательно-соединенных m-разряднь»х регистров

2 на входы схем 3 сраннения будут поданы числа, поступившие соответственно на вход 1 в (М-1) предыдущих тактах.

Эти числа на схемах 3 сравнения сравниваются с входным числом, пришед"

-:шим на входную шину 1 в М-м такте.

Если входное число н М-м такте И равно или больше числа, снимаемого с выходов одного из регистров 2, то на выходе соответствующей схемы 3 сравнения образуется сигнал, равный логической единице. Если же число на входной шине 1 меньше, чем число с выхода регистра 2, то на выходе соответствующей схемы 3 сравнения образуется сигнал, равный логическому нулю.

Сигнал с выхода J""й схемы сравнения (j=-1,..., М-1), общее количество схем сравнения равно (М-1), подается на вход цепочки иэ последовательно соединенных (М-1"j) одноразрядных регистров 4, а также к одному из входов первого блока 6 подсчета номера ранга и через элемент НЕ 5 к одному

1 из входов (j+ I ) "го блока 6 подсчета номера ранга. Отметил», что общее количестно одноразрядных регистров

»»-, l в составе устройства равно Е (М-1-! 1=

Н - „ »»+» общее количество эле»»- ментов НЕ 5 равно М" 1+ g (М-1- !) !

»»», j=» — общее количество блоков подсчета номера ранга 2 равно N.

Сигнал с выхода k"ãî регистра 4

j-й цепочки одноразрядных регистров подается на один из входов (k+1)"го .блока 6 подсчета номера ранга и че рез соответствующий элемент НЕ 5— на один из входов (j+!+k)-го блока .: подсчета номера рангов 6. На выходе й-го блока подсчета. номера ранга. 6 (R = 1,..., М) образуется число (выраженное, например, двоичным кодом), которое равно количеству пришедших на нходы этого блока подсчета ° номера ранга, единиц и которое характеризует номер ранга В-го числа входной последовательности в данном такте. г

Таким образом, на выходе первого .блока подсчета номера ранга через М тактов будет присутствовать число, характеризующее номер ранга входного числа, пришедшего по шине в N-м такте, а на выходе И-го блока подсчета номера ранга будет присутствовать число, характеризующее номер ранга входного числа, пришедшего на входную шину в 1-м такте.

Число на выходе блока подсчета номера ранга, характеризующее минимапьн:.Л ранг входного числа, будет равно нулю; число, на выхоце блока подсчета номера ранга, характеризующае максимальный Ранг входного числа, будет равно N-I.

Иэ рассмотрения работы устройства видно, что на выходе К-го блока подсчета номера ранга в каждом такте

1051532

ВНИИПИ Заказ 8667/48 Тираж 706 Нодписное и

Филиал ППП " патент", г. Ужгород, ул„ Проектная, 4 присутствует число, равное рангу

R"ro числа числовой последовательности (понимается, что -в й-и такте иа входйую шину i приходит число с индексом Й1, а число с индексом

R J+1 снимается с выхода j -ro входного регистра 2()1,..., .М-1).

Таким образом, по сравнению с прототипом предлагаемое техническое решение обладает более высоким быстродействием и решает принципиально но5 вую задачу определения в течение од- ного такта рангов всех членов числавой последовательности.